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