An algorithm for generating all possible Boolean functions from n variables

Question

For n variables, there are 2 ^ (2 ^ n) different Boolean functions. For example, if n = 2, then there are 16 possible Boolean functions that can be written in the sum of the product form or the product of the sum form. The number of possible functions increases exponentially with n.

I am looking for an algorithm that can generate all these possible logical rules for n variables. I tried to search in different places, but so far I have not found anything suitable. Most algorithms involve simplifying or reducing Boolean functions to standard forms.

I even know that the number of rules is getting too large even for n = 8 or 9, but can someone please help me with the corresponding algorithm, if it exists?

Answer 1

A Boolean function of n variables has 2 ^ n possible inputs. They can be listed by printing a binary representation of values ​​in the range 0 <= x < 2^n .

For each of these possible inputs, a logic function can output 0 or 1. Enumerate all the possibilities (i.e., all possible truth tables). List binary values ​​in the 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 result is as follows:

 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 to get the result in algebraic form, not a truth table, then the algorithm will be 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 result is as follows:

 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 the comments, there is a one-to-one relationship between numbers and truth tables. For example, we can present a 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 

binary number 01010011 (the 01010011 line is represented by the least significant bit).

Obviously, the point is to iterate over the 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 appreciate it, for example. Say we want to know f(0,1,0) . It is as simple as interpreting the argument as a binary number x = 010 and doing some bit magic:

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

We can also find our disjunctive normal form by simply checking which bits are 0:

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

Give a result, for example 000 OR 001 OR 100 OR 110 (OR) for the above function.

Answer 3

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

• generate all boolean expressions before n_ary,
• select a specific function,
• perform an assessment and
• Get answers in binary or True / False way.

the 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 

Good luck !!!