Algorithm for generating all possible boolean functions of n variables

Question

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?

Answer 1

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 

Answer 2

As mentioned in comments, there's a one-to-one relation between numbers and truth tables. For example, we can represent the truth table

0 0 0  | 1
0 0 1  | 1
0 1 0  | 0
0 1 1  | 0
1 0 0  | 1
1 0 1  | 0 
1 1 0  | 1
1 1 1  | 0

by the binary number 01010011 (the topmost row is represented by the least-significant bit).

It is obviously just a matter of looping over numbers to generate these representations:

for f := 0 to 2^(2^n) - 1:
    # do something with f

What can we do with f? We can evaluate it, for example. Say we want to know f(0,1,0). It's as simple as interpreting the argument as the binary number x = 010 and doing some bit-magic:

def evaluate(f, x):
    return (f & (1<<x)) != 0

We can also find its disjunctive normal form by just checking which bits are 0:

def dnf(f):
    for x := 0 to 2^n - 1:
        if f & (1<<x) != 0:
            print binary(x) + " OR "

Giving a result like 000 OR 001 OR 100 OR 110 (OR) for the function above.

Answer 3

I've changed the code posted by Raymond Hettinger. Now you can:

1. generate all Boolean expressions up to n_ary,
2. pick a particular function,
3. perform evaluation, and
4. get answers in binary or True/False manner.

Code:

    from itertools import product

    def allBooleanFunctions(kk):
        """Finds all Boolean functions for indegree kk"""
        inputs1 = list(product([0, 1], repeat=kk))
        variables = 'abcdefghijklmnopqrstuvwxyz'[:kk]
        pairs = [('( not '+var+' )', var) for var in variables]
        inputs = list(product(*pairs))

        bool_func=[]

        for i, outputs in enumerate(product([0, 1], repeat=len(inputs))):
            terms = [' and '.join(row) for row, output in zip(inputs, outputs) if output]
            if not terms:
                terms = ['False'] 
            bool_func.append(('('+(') or ('.join(terms))+')'))
        return bool_func

    n_ary=2 # number of inputs; keep it n_ary<=5

    boolean_function_analytical=allBooleanFunctions(n_ary)

    print('All Boolean functions of indegree:'+str(n_ary)+'\n')
    print(boolean_function_analytical)
    print
    print('A Boolean function:'+'\n')
    print(boolean_function_analytical[2])
    # Evaluate third boolean function:
    a=1 # first input
    b=0 # second input
    c=0 # third input
    d=0 # fourth input
    print('a='+str(a)+'; b='+str(b)+'; c='+str(c)+'; d='+str(d)+'\n')
    print('Evaluation in 0/1 manner:')
    print(int(eval((boolean_function_analytical[2]))))
    print('Evaluation in True/False manner:')
    print(bool(eval((boolean_function_analytical[2]))))

Result:

    All Boolean functions of indegree:2

    ['(False)', '(a and b)', '(a and ( not b ))', '(a and ( not b )) or (a and b)', '(( not a ) and b)', '(( not a ) and b) or (a and b)', '(( not a ) and b) or (a and ( not b ))', '(( not a ) and b) or (a and ( not b )) or (a and b)', '(( not a ) and ( not b ))', '(( not a ) and ( not b )) or (a and b)', '(( not a ) and ( not b )) or (a and ( not b ))', '(( not a ) and ( not b )) or (a and ( not b )) or (a and b)', '(( not a ) and ( not b )) or (( not a ) and b)', '(( not a ) and ( not b )) or (( not a ) and b) or (a and b)', '(( not a ) and ( not b )) or (( not a ) and b) or (a and ( not b ))', '(( not a ) and ( not b )) or (( not a ) and b) or (a and ( not b )) or (a and b)']

    A Boolean function:

    (a and ( not b ))
    a=1; b=0; c=0; d=0

    Evaluation in 0/1 manner:
    1
    Evaluation in True/False manner:
    True

Have fun!!!