選言標準形とは、以下の条件で論理式を表すことです。
・論理否定を使う場合は、個々の命題に対してのみ使う
※例えば、AはOK、A ∧ BはNG
・論理積と論理和を使う場合は、論理積の論理和のみ使う
※例えば、(A ∧ B) ∨ (C ∧ D)はOK、(A ∨ B) ∧ (C ∨ D)はNG
例えば、以下は、選言標準形の論理式です。
A
A
A ∧ B
A ∨ B
(A ∧ B) ∨ C
(A ∧ B) ∨ (C ∧ D)
(A ∧ B) ∨ (C ∧ D) ∨ (E ∧ F)
選言標準形でない論理式も変形して、選言標準形にすることが可能です。
真理値表は、選言標準形の論理式で表すことができます。
例えば、命題Aと命題Bと命題Cを使った論理判定をYとし、その真理値表が以下だったとします。
| A | B | C | Y |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
このとき、上記の真理値表は、選言標準形の論理式を使って、以下のように表せます。
(A ∧ B ∧ C) ∨ (A ∧ B ∧ C) ∨ (A ∧ B ∧ C)
Yが1になる行で論理積の論理式を作り、Yが1になる行が複数あれば、それらの論理式の論理和を求めます。
例えば、Xを含む、以下の真理値表があったとします。
| A | B | C | Y |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | X | 1 |
この場合、真理値表を選言標準形の論理式で表すと、A ∧ Bになります。
Xが0でも1でも良いことを考慮すると、上記の真理値表の選言標準形の論理式は、(A ∧ B ∧ C) ∨ (A ∧ B ∧ C)になります。
論理演算の分配則を用いて、A ∧ B ∧ (C ∨ C)に変形します。
論理演算の法則より、C ∨ C=1なので、A ∧ B ∧ 1になります。
論理演算の法則より、B ∧ 1=Bなので、A ∧ Bになります。
導出できました。