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

  • Z时代
  • 2024-01-10
  • 分类：问答

对于n个变量，存在2 ^（2 ^ n）个不同的布尔函数。例如，如果n =

2，则存在16个可能的布尔函数，这些布尔函数可以乘积形式或乘积形式写入。可能函数的数量呈n指数增长。

我正在寻找一种算法，可以为n个变量生成所有这些可能的布尔规则。我曾尝试在各个地方进行搜索，但直到现在都找不到合适的东西。大多数算法与将布尔函数简化或减少为标准形式有关。

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

回答：

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

对于这些可能的输入中的每个输入，布尔函数可以输出 0 或 1 。列举所有可能性（即每个可能的真值表）。列出range中的二进制值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

以上是 生成n个变量的所有可能布尔函数的算法 的全部内容， 来源链接： utcz.com/qa/427007.html

回到顶部