ブール式を簡略化するアルゴリズムは誰もが知っていますか？ブール式アルゴリズムの簡略化
私はブール代数とKarnaughtマップを覚えていますが、これはEVERITHINGがブール値のデジタルハードウェアを意味します。私は、いくつかのサブ式がブール値ではないことを考慮に入れた何かが好きです。これは、純粋なブール式に変換することができる
a == 1 && a == 3
：
例えばa1 && a3
これは算術演算の知識の少しでeveribody決定することができるしながら発現は、既約です式がちょうどであること：
false
オメのリンク？もちろん
http://hopper.unco.edu/KARNAUGH/Algorithm.html
、非ブール部分式を扱っていない：Googleのを使用して
最初のショットは、この論文を見つけました。しかし、この一般的な形式の後半部分は本当に難しいです。なぜなら、任意の算術式が真、偽、その他であるかどうかをチェックするアルゴリズムがないからです。あなたが求めているのは、compiler optimizationのフィールドに深く入ります。
私は前にこの論文を読んでいましたが、私はそれもかなり注意深く、コードは提供されていませんでした。 – Olmo
K-mapsとQuine–McCluskey algorithmに興味があるかもしれません。
私はSymPyがブール式を解決して単純化することができると考えています。ソースを見ると便利かもしれません。
可能な異なる値の数は有限で既知ですか？そうであれば、各式をブール式に変換できます。たとえば、aが3つの異なる値を持つ場合、変数a1,a2およびa3が得られます。a1が真であることは、a == 1などを意味します。これを行うと、Quine-McCluskeyアルゴリズムに頼ることができます。カルノー地図よりも）。ここにはQuine-McCluskeyのためのJava codeがあります。
このデザインが実際に単純化したり、複雑にするかどうかは言えませんが、少なくとも考慮する必要があります。
正確には、それは私が意味するものですが、このようなアルゴリズムでは、私の例では、a1 && a3は実際には偽であるとは考えられません。 aは同時に1と3になることはできないためです。私は必要なのは、変数を変数に結びつけ、Karnaughtの未来派の矛盾を見つけることだと思います。 – Olmo
具体例はSMT solverで解決します。 （式を真にすることができないと判断するので、常にfalseです。より一般的な単純化は、そのようなソルバーの範囲外です）。式がtrueまたはfalseと等価であることを示すことはもちろんNP-算数を算入しなくてもハードなので、これでも実用的なソフトウェアがあることはとても涼しいです。算術知識の範囲に応じて、問題may be undecidable。
この問題には、論理簡素化と表現の簡略化という2つの部分があります。
論理簡略化のために、Quine-McCluskey。表現の簡略化のために、分布アイデンティティ（0 & 1 | 0 & 2）== 0 &（1 | 2）を使用して、再帰的に用語を抽出する。
詳細はhereです。これは、&と|のみを使用して説明を与えますが、すべての論理演算子を含めるように変更できます。
これは難しい人です。私が見つけた最も単純な方法でのアルゴリズムは、すべての出力の組み合わせをそれぞれの各入力と組み合わせて一致させました。しかし、それは基本的なアルゴリズムであり、すべての式を解決しませんでした。
すべての出力（Q1、Q2、Q3、Q4）はすなわち、入力のための組み合わせと同じ場合でない場合は、単純化の結果はA.
だろう、あなたは別のvariabel /入力依存性をしようとします。
'a'がそれらを可能にする言語/ランタイムの揮発性変数/フィールドとして宣言され、別のスレッドで値が1と3の間で変動するとどうなりますか？私はそれが良いデザインだと言っているわけではありませんが、ソフトウェアでは、「常に」と「決して」は通常相対的な用語です。 –
これは問題ではなく、実際の使用はLINQプロバイダー用であり、実際の値はクエリが翻訳されたときの値です。それらのクエリが再度実行されると、更新された値を用いて再度簡略化が実行されます。 – Olmo
一般的には不可能です。例えば 'a> 0、b> 0、n> 2、a^n + b^n = c^n'は常に偽ですが、証明するのは簡単ではありません。つまり、あなたはアドホックな単純化に悩まされています。あなたの質問にはきれいな答えはありません（あなたが見たいと思う表現の性質に依存するので）。 –