ブール式ソルバー

2つの変数AとBにおける式は!(A & B)です。結果が1になる行の数を数え、この関数を最小項の和として書き、この1つのゲートだけから何が構築できるかを解き明かしてください。

1. 変数は2つあり、それぞれ0または1の値を自由にとるため、表にはペアごとに1つの行が割り当てられます。パーサーは何かを評価する前にその行数を報告します。なぜなら問題の規模は、その上に書かれた式ではなく変数によって定まるからです。

   $$2^2=4$$

2. まず内側の列を埋めます。A & Bは両方の入力が1のときのみ1になるため、3つの行は0、最後の行は1となります。表はこの部分式を結果の隣に独自の列として出力するため、答えだけでなく構文解析結果も確認できます。

   $$A\wedge B:0,0,0,1$$

3. NOTはすべてのエントリを反転させ、それ以外の動作は行いません。3つの0は1になり、1つの1は0になるため、結果の列は上の列のちょうど反対となります。

   $$\neg (A\wedge B):1,1,1,0$$

4. これにより、全4行のうち3行で結果が1となります。分数では0.75となり、パネルには入力の組み合わせに対する割合として表示されます。

   $$\frac{3}{4}=0.75=75.0\%$$

5. 真となる各行を、その行でのみ1となり他の行では1とならない連言（すなわち最小項）によって命名し、それら3つをORで結合します。これが主選言標準形であり、ツールが表の下に出力するリストです。

   $$(\neg A\wedge \neg B)\vee (\neg A\wedge B)\vee (A\wedge \neg B)$$

次に!A | !Bを取り上げます。これは!(A & B)と演算子を全く共有していません——括弧の否定も、どこにもANDもありません。その列を一から構築し、どこに行き着くかを確認しましょう。

1. 2つのNOTの列があり、どちらも結果の隣に出力されます。!AはAが0である2つの行で1となり、!BはBが0である2つの行で1となります。それらは1つの行で一致し、1つの行でともに不成立となります。

   $$\neg A:1,1,0,0\neg B:1,0,1,0$$

2. ORは両方の入力が0である場合にのみ0となり、それはまさに1つの行、すなわちA=1、B=1の否定のどちらも残らない行で発生します。他のすべての行には、少なくとも1つの1が含まれています。

   $$\neg A\vee \neg B:1,1,1,0$$

3. したがって、4行中3行が1となります——同じ0.75であり、同じパーセンテージとして表されます。

   $$\frac{3}{4}=75.0\%$$

4. 最小項も一致し、最初の問題と項ごとに同じ順序となります。

   $$(\neg A\wedge \neg B)\vee (\neg A\wedge B)\vee (A\wedge \neg B)$$

5. ここで、表を一切使わずに2つの式を比較してみましょう。A & Bはまさに1つの行で1となるため、!(A & B)はまさにその行で0となり、それは!A | !Bを不成立にしたのと同じ行です。同じ場所で0になり、他のすべての場所で1になる2つの列は、同じ1つの列です。

   $$\neg (A\wedge B)\equiv \neg A\vee \neg B$$

6. これにはどれほど感銘を受けるべきでしょうか？4行の真理値表には4つの結果セルがあり、それぞれが0または1となるため、2つの変数が取り得る個別の関数は全体で16個しかありません。それほど小さな集合の中で一致することは容易です——だからこそステップ5が重要な意味を持ちます。それは1つの行を固定し、残りを数えることがなかったからです。

   $$2^{2^2}=2^4=16$$