選言標準形
from 命題論理
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})
Aはリテラル
任意の論理式に対して、DNFを作ることができる
真理値表から論理式を作れるのが嬉しい
真理値表から論理式を作ることを考える
通常は論理式が与えられて、そこから真理値表を作るが、逆に。
例
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,Y,Z)と意味論的同値になる
つまり、(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)
や、すごい！