連言標準形
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になるところに注目する
例
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を作る
(①)∨(②)∨(③)∨(④)