分发布尔逻辑表达式

Question

我有什么：

(A.B.C) + (D.E) + (F.G.H.I) 

我想用分配律：

(A + D + F).(A + D + G).(A + D + H).(A + D + I). 
(A + E + F).(A + E + G).(A + E + H).(A + E + I). 
(B + D + F).(B + D + G).(B + D + H).(B + D + I). 
(B + E + F).(B + E + G).(B + E + H).(B + E + I). 
(C + D + F).(C + D + G).(C + D + H).(C + D + I). 
(C + E + F).(C + E + G).(C + E + H).(C + E + I) 

两个表达式是等效的。我用分配法得到第二个：A + (B . C) ⇔ (A + B) . (A + C)

该表达式可以更大，但总是由AND的组合构成，由OR分隔。 我在找的是一个能够分配逻辑表达式的库。像Sympy这样的库，但是应用于逻辑而不是代数。

Answer 1

Sympy是这个完美的选择，只取一请看logic模块，特别是Equivalent和to_cnf的功能，下面的例子：

from sympy import * 

A, B, C, D, E, F, G, H, I = symbols('A,B,C,D,E,F,G,H,I') 

formula = (
    (A & B & C) | (D & E) | (F & G & H & I) 
) 
formula2 = (
    (A | D | F) & (A | D | G) & (A | D | H) & (A | D | I) & 
    (A | E | F) & (A | E | G) & (A | E | H) & (A | E | I) & 
    (B | D | F) & (B | D | G) & (B | D | H) & (B | D | I) & 
    (B | E | F) & (B | E | G) & (B | E | H) & (B | E | I) & 
    (C | D | F) & (C | D | G) & (C | D | H) & (C | D | I) & 
    (C | E | F) & (C | E | G) & (C | E | H) & (C | E | I) 
) 

print(to_cnf(formula)) 
print(Equivalent(to_cnf(formula), formula2)) 

结果：

(A | D | F) & (A | D | G) & (A | D | H) & (A | D | I) & (A | E | F) & (A | E | G) & (A | E | H) & (A | E | I) & (B | D | F) & (B | D | G) & (B | D | H) & (B | D | I) & (B | E | F) & (B | E | G) & (B | E | H) & (B | E | I) & (C | D | F) & (C | D | G) & (C | D | H) & (C | D | I) & (C | E | F) & (C | E | G) & (C | E | H) & (C | E | I) 
True 

Answer 2

看起来你可以做到这一点的包boolean.py（从皮普与pip install boolean.py安装）：

from boolean import BooleanAlgebra 

exp1 = algebra.parse("(A*B*C) + (D*E) + (F*G*H*I)") 
# Convert to conjunctive normal form (CNF) 
exp2 = algebra.cnf(exp1) 
print(exp2.pretty()) 

输出：

AND(
    OR(
    Symbol('A'), 
    Symbol('D'), 
    Symbol('F') 
), 
    OR(
    Symbol('A'), 
    Symbol('D'), 
    Symbol('G') 
), 
    OR(
    Symbol('A'), 
    Symbol('D'), 
    Symbol('H') 
), 
    OR(
    Symbol('A'), 
    Symbol('D'), 
    Symbol('I') 
), 
    OR(
    Symbol('A'), 
    Symbol('E'), 
    Symbol('F') 
), 
    OR(
    Symbol('A'), 
    Symbol('E'), 
    Symbol('G') 
), 
    OR(
    Symbol('A'), 
    Symbol('E'), 
    Symbol('H') 
), 
    OR(
    Symbol('A'), 
    Symbol('E'), 
    Symbol('I') 
), 
    OR(
    Symbol('B'), 
    Symbol('D'), 
    Symbol('F') 
), 
    OR(
    Symbol('B'), 
    Symbol('D'), 
    Symbol('G') 
), 
    OR(
    Symbol('B'), 
    Symbol('D'), 
    Symbol('H') 
), 
    OR(
    Symbol('B'), 
    Symbol('D'), 
    Symbol('I') 
), 
    OR(
    Symbol('B'), 
    Symbol('E'), 
    Symbol('F') 
), 
    OR(
    Symbol('B'), 
    Symbol('E'), 
    Symbol('G') 
), 
    OR(
    Symbol('B'), 
    Symbol('E'), 
    Symbol('H') 
), 
    OR(
    Symbol('B'), 
    Symbol('E'), 
    Symbol('I') 
), 
    OR(
    Symbol('C'), 
    Symbol('D'), 
    Symbol('F') 
), 
    OR(
    Symbol('C'), 
    Symbol('D'), 
    Symbol('G') 
), 
    OR(
    Symbol('C'), 
    Symbol('D'), 
    Symbol('H') 
), 
    OR(
    Symbol('C'), 
    Symbol('D'), 
    Symbol('I') 
), 
    OR(
    Symbol('C'), 
    Symbol('E'), 
    Symbol('F') 
), 
    OR(
    Symbol('C'), 
    Symbol('E'), 
    Symbol('G') 
), 
    OR(
    Symbol('C'), 
    Symbol('E'), 
    Symbol('H') 
), 
    OR(
    Symbol('C'), 
    Symbol('E'), 
    Symbol('I') 
) 
)