logic - 2 つのブール式の等価性

Question

私は2つのブール式を持っています:

¬aΛ¬b V ¬aΛ¬c V aΛ¬bΛ¬c #1

¬aΛ¬b V ¬aΛ¬c V ¬bΛ¬c #2

真理値表が同一であるため、それらが同一であることはわかっています。私の質問は、どうすればそれらを表現的に等しくすることができるかということです。

それらの唯一の違いは、#1 の最後の OR 項に余分な「a」があることです。余分な「a」を取り除こうとするさまざまな因数分解法は成功していません。

Answer 1

「表現的に」とはどういう意味か正確にはわかりませんが、 a が true か false かに基づいて分解すると、簡単にわかります。

a が真の場合 (Eq1 と Eq2 の両方で最初の 2 つの項が偽):
Eq1 => ~b & ~c
Eq2 =>~b & ~c

a が偽の場合:
Eq1 => ~b | ~c
Eq2 => ~b | ~c | (~b & ~c)== Eq1

編集：ブールIDを使用して、この同じ引数をより正式にすることができます：

(~a & ~b | ~a & ~c | ~b & ~c) == ((~a & ~b) | (~a & ~c) | (~b & ~c)) & (a | ~a)

それ以来 (a | ~a) == 1 、x & 1 = x

&次に、 overの分布を使用し|ます。

== (((~a & ~b) | (~a & ~c) | (~b & ~c)) & a) | (((~a & ~b) | (~a & ~c) | (~b & ~c)) & ~a)

これで、各「ケース」がメインの両側に追加の事実として表示されます|。ディストリビューションを再度適用すると、この事実が内部ケースにプッシュされ、最終的には上記と同じキャンセルが行われます。左側の最初の分布だけを見ると、次のようになります。

((~a & ~b) | x) & a) == (a & ~a & b) | (a & x) == 0 | (a & x) == a & x

ここで、x は他の 2 つの or 式です。この戦略に従うと、上記と同じ答えが得られます。行き詰まった場合は先に進めますが、ここから先に進むことができるはずです。

Answer 2

一般的には、式を選言標準形に変換する必要があります。これを行うには、基本接続詞の論理和を作成します。真理値表の各 1 について、すべての変数またはそれらの反転の対応する論理積を書き出してから、それらすべての接続詞の論理和を作成します。接続法標準形も存在しますが、使用されることはめったにありません。

選言正規形は、多くの変数の式に対して非常に大きくなります。その場合、最小化アルゴリズム ( Quine-McCluskey アルゴリズムなど)を使用したい場合がありますが、それは非常に複雑で計算コストが高くなります (最小化の問題はNP 困難であり、これらのアルゴリズムの実行時間は通常、単に真実を計算するよりも指数関数的に悪くなります)。テーブル）。

同じ変数のブール式を比較するために普遍的な表現が必要な場合は、それらの式の真理値表を比較することもできます。

• 辞書式順序で変数の可能なすべての組み合わせの式の値 (0 または 1) の文字列として、
• または、式が真である真理値表の行番号のソートされたリストとして。行は、変数の辞書順で番号が付けられています。