分解布尔逻辑表达式

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) 该表达式可能会更复杂，但始终由用OR分隔的AND组成。

我正在寻找一个能够分配逻辑表达式的库。类似于Sympy的库，但应用于逻辑而不是代数。

- Dionys

Answer 1

看起来你可以使用包boolean.py来完成这个操作（使用pip install boolean.py从Pip安装）：

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')
  )
)

- jdehesa

---

我必须选择一个答案来接受。你的答案也是可以接受的。我只是更喜欢使用@BPL建议的Sympy。非常感谢你的帮助。 - Dionys

@Dionys 是的，我认为Sympy的答案更有用，因为它是一个更常见的库（我只是不知道它也实现了布尔代数）。 - jdehesa

Answer 2

Sympy是这方面的完美选择，只需看一下逻辑模块，特别是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

- BPL

---

哇，我错过了所有的内容！我甚至不知道CNF和DNF，非常有教育意义。事实上，我想要的是将DNF转换为CNF。谢谢，我会更详细地查看这个模块。 - Dionys