一个布尔函数n变量有2^n可能的输入。可以通过打印范围内值的二进制表示来枚举这些0 <= x < 2^n
.
对于每一个可能的输入,布尔函数可以输出0 or 1。枚举所有可能性(即每个可能的真值表)。列出范围内的二进制值0 <= x < 2^(2^n)
.
这是 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)
输出如下所示:
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
如果您想要代数形式而不是真值表的输出,算法是相同的:
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))
输出如下所示:
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