CNF簡略化アルゴリズム

Question

ブール式が結合正規形であると仮定すると、CNF内に保持しながら簡略化する単純なアルゴリズムがありますか？

特に、次の表現のどのような特性がこの単純化を引き起こしますか？

(~a+b+c)(a+~b+c)(a+~c) 

あなたの例のKarnaugh mapがある

(~a+b+c)(a+~b)(a+~c) 

Answer 1

...に簡単になります。

簡略化DNFを取得するには、 '1' 細胞を得るためにグループ化されていますカバーの最小数はmintermsです。

同様に、最小数の項で逆カバーを得るために '0'セルをグループ化することができます。

逆マップ：

得られた用語のリテラルが所望の最小CNF

（A +〜B）（A +〜に到達するために反転されなければなりませんc）（〜a + b + c）

この手順では、の逆数0は、逆リテラルを含むmaxterm（一般的にはCNF clauseと呼ばれます）です。