18

ブール式を単純化するアルゴリズムを知っている人はいますか?

ブール代数と Karnaught マップを覚えていますが、これは EVERITHING がブール値であるデジタル ハードウェアを対象としています。一部の部分式がブール値ではないことを考慮したものが欲しいです。

例えば：

a == 1 && a == 3

これは、純粋なブール式に変換できます。

a1 && a3

しかし、これは式が既約であるということですが、算術について少し知識があれば、誰もが式が正しいことを判断できます。

false

誰かがいくつかのリンクを知っていますか？

4

6 に答える 6

10

KマップとQuine–McCluskeyアルゴリズムに興味があるかもしれません。

SymPyはブール式を解いて単純化できると思います。ソースを調べると便利かもしれません。

于 2011-03-15T14:10:06.600 に答える
7

あなたの特定の例は、SMT ソルバーによって解決されます。(変数の設定が式を真にすることはできないと判断します。したがって、それは常に偽です。より一般的な単純化は、そのようなソルバーの範囲外です。) 式が同等であるか、trueまたはfalseもちろん NP 困難であることを示す算数を取引に持ち込むことなく、これだけの実用的なソフトウェアがあるのはかなりクールです. 範囲内の算数の知識の程度によっては、問題が決まらない場合があります。

于 2011-03-15T23:35:53.370 に答える
5

この問題には、論理的な単純化と表現の単純化という 2 つの部分があります。

論理的な単純化のために、Quine-McCluskey. 表現を簡略化するために、分布単位 (0&1|0&2) == 0&(1|2) を使用して項を再帰的に抽出します。

ここでプロセスを詳しく説明しました。これは & と | のみを使用した説明ですが、すべてのブール演算子を含めるように変更できます。

于 2014-03-05T18:50:53.553 に答える
3

可能な個別の値の数は有限であり、既知ですか? もしそうなら、各式をブール式に変換できます。たとえば、 a に 3 つの異なる値がある場合、変数、a1、a2およびtrue はなどを意味します。これを行うと、Quine-McCluskey アルゴリズムに頼ることができます (これは、カルノー マップよりも大きな例ではおそらく優れています)。Quine-McCluskey のJava コードを次に示します。a3a1a == 1

この設計が実際に物事を単純化するのか、それともより複雑にするのかについては、私には語れませんが、少なくとも検討することをお勧めします.

于 2011-03-15T14:33:36.407 に答える
-1

これは難しい人です。私が見つけた最も単純な方法のアルゴリズムは、すべての出力の組み合わせと各入力の組み合わせを一致させることでした。しかし、これは基本的なアルゴリズムであり、すべての式を解決したわけではありません。

すべての出力 (q1、q2、q3、q4) が入力 A の組み合わせと同じである場合、単純化の結果は A になります。

そうでない場合は、別の変数/入力依存関係を試します。

于 2015-03-24T13:39:40.327 に答える