5

特にKマップの最適性に対処している文献を見つける手助けをいただければ幸いです。

たとえば、SOP (積和) 式と K マップをどのようにマッピングできるか、および 1 の最大グループを見つけるので、K マップ最適化式がより単純であると一般に期待する理由を理解しています。単純な SOP 式の冗長性のいくつかを見つけることに対応します。

私たちが実際に行っていることは、ブール代数の分配と単位 (A + A' = 1) の特性を利用することだけのように思われるため、K マップ法が最適な解を生成しない可能性があることが漠然とわかります。しかし、K マップを使用して実行していない代数操作が何であるかはよくわかりません。これにより、より最適な解に到達できる可能性があります。

結論として、K マップが常に最適であるとは限らないことを示す証明を開始する方法がわかりません。

私は読み込もうとしていました: this but that paperでは、最適なブール式を見つける問題がNPにあることが引用されているだけであり、アルゴリズムとしてそれらはNP時間で実行されていません。

「反例」のような方法だけでなく、Kマップが最適ではないのはなぜですか..実際にはなぜですか? それを私に証明するか、証明するように指示してもらえますか?

4

2 に答える 2

1
于 2012-11-26T15:12:08.620 に答える