連言標準形
CNF, Conjunctive normal form
乗法標準形
和積形
以下のような形のもの
$ (A_{1,1}\lor\dots\lor A_{1,n_1})\land(A_{2,1}\lor\dots\lor A_{2,n_2})\land\dots\land(A_{m,1}\lor\dots\lor A_{m,n_m})
真理値表から論理式を作れるのが嬉しい
真理値表から論理式を作ることを考える
通常は論理式が与えられて、そこから真理値表を作るが、逆に。
選言標準形と異なり、$ \varphiが$ Fになるところに注目する 例
table:xyz
X Y Z φ(X,Y,Z)
T T T F ←①¬X∨¬Y∨¬Z
T T F T
T F T F ←②¬X∨Y∨¬Z
T F F F ←③¬X∨Y∨Z
F T T T
F T F T
F F T F ←④X∨Y∨¬Z
F F F T
この真理値表の結果がTになるものを論理和で組み合わせればいい
これらから、こんなCNFを作る
(①)∨(②)∨(③)∨(④)