Algorithm for generating all possible boolean functions of n variables

algorithm, boolean-logic

Solution

A boolean function of n variables has 2^n possible inputs. These can be enumerated by printing out the binary representation of values in the range `0 <= x < 2^n`.

For each one of the those possible inputs, a boolean function can output 0 or 1. To enumerate all the possibilities (i.e. every possible truth table). List the binary values in range `0 <= x < 2^(2^n)`.

Here's the algorithm in Python:

from __future__ import print_function
from itertools import product       # forms cartesian products
n = 3                               # number of variables

print('All possible truth tables for n =', n)
inputs = list(product([0, 1], repeat=n))
for output in product([0, 1], repeat=len(inputs)):
    print()
    print('Truth table')
    print('-----------')
    for row, result in zip(inputs, output):
        print(row, '-->', result)

The output looks like this:

All possible truth tables for n = 3

Truth table
-----------
(0, 0, 0) --> 0
(0, 0, 1) --> 0
(0, 1, 0) --> 0
(0, 1, 1) --> 0
(1, 0, 0) --> 0
(1, 0, 1) --> 0
(1, 1, 0) --> 0
(1, 1, 1) --> 0

Truth table
-----------
(0, 0, 0) --> 0
(0, 0, 1) --> 0
(0, 1, 0) --> 0
(0, 1, 1) --> 0
(1, 0, 0) --> 0
(1, 0, 1) --> 0
(1, 1, 0) --> 0
(1, 1, 1) --> 1

Truth table
-----------
(0, 0, 0) --> 0
(0, 0, 1) --> 0
(0, 1, 0) --> 0
(0, 1, 1) --> 0
(1, 0, 0) --> 0
(1, 0, 1) --> 0
(1, 1, 0) --> 1
(1, 1, 1) --> 0

Truth table
-----------
(0, 0, 0) --> 0
(0, 0, 1) --> 0
(0, 1, 0) --> 0
(0, 1, 1) --> 0
(1, 0, 0) --> 0
(1, 0, 1) --> 0
(1, 1, 0) --> 1
(1, 1, 1) --> 1

... and so on

If you want the output in algebraic form rather than truth tables, the algorithm is the same:

from __future__ import print_function
from itertools import product       # forms cartesian products
n = 3                               # number of variables

variables = 'abcdefghijklmnopqrstuvwxyz'[:n]
pairs = [('~'+var, var) for var in variables]
print('All possible algebraic expressions for n =', n)

inputs = list(product(*pairs))
for i, outputs in enumerate(product([0, 1], repeat=len(inputs))):
    terms = [''.join(row) for row, output in zip(inputs, outputs) if output]
    if not terms:
        terms = ['False']
    print('Function %d:' % i, ' or '.join(terms))

The output looks like this:

All possible algebraic expressions for n = 3
Function 0: False
Function 1: abc
Function 2: ab~c
Function 3: ab~c or abc
Function 4: a~bc
Function 5: a~bc or abc
Function 6: a~bc or ab~c
Function 7: a~bc or ab~c or abc
Function 8: a~b~c
Function 9: a~b~c or abc
Function 10: a~b~c or ab~c
Function 11: a~b~c or ab~c or abc
Function 12: a~b~c or a~bc
Function 13: a~b~c or a~bc or abc
Function 14: a~b~c or a~bc or ab~c
Function 15: a~b~c or a~bc or ab~c or abc
Function 16: ~abc
Function 17: ~abc or abc
Function 18: ~abc or ab~c
Function 19: ~abc or ab~c or abc
Function 20: ~abc or a~bc
Function 21: ~abc or a~bc or abc
Function 22: ~abc or a~bc or ab~c
Function 23: ~abc or a~bc or ab~c or abc
Function 24: ~abc or a~b~c
Function 25: ~abc or a~b~c or abc
Function 26: ~abc or a~b~c or ab~c
Function 27: ~abc or a~b~c or ab~c or abc
Function 28: ~abc or a~b~c or a~bc
Function 29: ~abc or a~b~c or a~bc or abc
Function 30: ~abc or a~b~c or a~bc or ab~c
Function 31: ~abc or a~b~c or a~bc or ab~c or abc
Function 32: ~ab~c
Function 33: ~ab~c or abc

... and so on

Problem

For n variables, there exists 2^(2^n) distinct boolean functions. For example, if n=2, then there exists 16 possible boolean functions which can be written in sum of product form, or product of sum forms. The number of possible functions increases exponentially with n. I am looking for an algorithm which can generate all these possible boolean rules for n variables. I have tried to search at various places, but have not found anything suitable till now. Most of the algorithms are related to simplifying or reducing boolean functions to standard forms. I know even for the number of rules become too large even for n=8 or 9, but can somebody please help me out with the relevant algorithm if it exists?

Original source