ＮＡＮＤゲートのみによるＥＸ－ＯＲ

締切済

質問者：yuruyurugakusei
質問日時：2013/06/13 22:45
回答数：3件

ＮＡＮＤゲートのみによるＥＸ－ＯＲが動作する事をブール代数の公式を用いて理論的に証明したのですが…
全然分かりません、誰か説明して頂けませんか？

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (3件)

最新から表示
回答順に表示

No.3

回答者： hirotn
回答日時：2013/06/14 00:19

NANDのみによる、EX-OR（以下XORとします）は承前とさせてください。

また、
￢否定
∧かつ　(A ∧ B) A and B ￢(A ∧ B) A nand B
∨または（A∨B）　A or B とします。

まずNANDだけを使って全部書きます。

￢( ￢( A ∧ ￢ ( A ∧ B ) ) ∧　￢( B ∧ ￢ ( A ∧ B ) ) )　　・・・（１）

ここから(A ∧ ￢B)∨(￢A ∧ B)　　　　　　　　　　　　　　　・・・（２）

まで持っていくわけですが、さっぱりわかりません。ド・モルガンの法則を用いて（１）式を、
前半・後半にわけます。一番最初の否定が消えます。

￢￢( A ∧ ￢ ( A ∧ B ) ) ∨　￢￢( B ∧ ￢ ( A ∧ B ) )　　・・・（３）

￢が2つ並ぶと元に戻るので（￢￢A = A )、

( A ∧ ￢ ( A ∧ B ) ) ∨　( B ∧ ￢ ( A ∧ B ) )　　　　・・・（４）

同じようにして、￢ ( A ∧ B )の部分もド・モルガンの法則で展開します。

( A ∧ ( ￢A ∨ ￢B ) ) ∨　( B ∧ ( ￢A ∨ ￢B ) )　　　・・・（５）

と、なりました。分配則(x ∨ y)∧ z = (x ∧ z)∨(y ∧ z)から、
(A ∧ ￢A) ∨ ( A ∧ ￢B ) ∨ ( B ∧ ￢A ) ∨ ( B ∧ ￢B )　　・・・（６）

が得られます。（５）の∨を中心に左半分、右半分それぞれに分配則を適用したためです。

A ∧ ￢A や、 B ∧ ￢B は補元則より1ですからこの演算に影響しません。故に、

(A ∧ ￢B) ∨ (B ∧ ￢A)　・・・（目的のXOR）

が得られて証明終了です。