標準形

標準形

　全ての論理式は () を含まずに　and or not だけの演算子からなる式に変形できることが分かっています。これは変数または変数の否定をand で結んだもの(積)をorで結んだものになっているので、積和標準形(conjunctive canonical form)といい、式の簡単化に有用であることが分かっています。積和標準形に直す時次の公式が有用です。

19. not(A or B) = not A and not B (ﾄﾞ･ﾓﾙｶﾞﾝ則　De'Morgan)

これを用いて括弧を式からなくすことができます。

　　例　A or not(C and (not(B or A) or C))

= A or (not C or not(not (B or A) or C)) (ﾄﾞ･ﾓﾙｶﾞﾝ則　18.　より)

= A or not C or not not (B or A) and not C (ﾄﾞ･ﾓﾙｶﾞﾝ則　19.　とorの結合則)

= A or not C or (B or A) and not C (not not D=D 公式1.より)

= A or not C or (B and not C or A and not C) (分配則より)

= A or not C or B and not C or A and not C (or の結合則より)

これで一応()がなくなりました。以上の変形では演算子の優先順序に非常な注意を払っています。上の式は更に簡単になります。

= A or not C or A and not C (orの結合則と公式12.)

= A or not C (orの結合則と公式12.)

各積の中の変数をｱﾙﾌｧﾍﾞｯﾄ順に並べ積は辞書の順に並べておけばきれいです。例えば紫の式は　A or A and not C or B and not C or not C とします。