用于生成n个变量的所有可能布尔函数的算法

Question

对于n个变量,存在2 ^(2 ^ n)个不同的布尔函数.例如,如果n = 2,则存在16种可能的布尔函数,这些函数可以以产品形式或和形式的乘积的总和来编写.可能的函数数量随n呈指数增长.

我正在寻找一种算法,它可以为n个变量生成所有这些可能的布尔规则.我试图在各个地方搜索,但到目前为止还没找到任何合适的地方.大多数算法都与将布尔函数简化或简化为标准形式有关.

我知道即使n = 8或9,规则的数量也会变得太大,但有人可以帮我解决相关的算法吗？

Answer 1

n个变量的布尔函数有2 ^ n个可能的输入.这些可以通过打印范围中的值的二进制表示来枚举0 <= x < 2^n.

对于那些可能的输入中的每一个,布尔函数可以输出0或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