論理学 シェーファーの棒 NAND

論理学　シェーファーの棒　NAND

シェーファーの棒を用いた命題の変形が理解できません。

A) (1)P∧Q ⇔ (2)￢(P｜Q) ⇔ (3)(P｜Q)｜(P｜Q)
B) (1)P∨Q ⇔ (2)￢(￢P∧￢Q) ⇔ (3)￢P｜￢Q ⇔ (4)(P｜P)｜(Q｜Q)

A)の(2)から(3)、B)の(3)から(4)への変形が分かりません。

　理解できる範囲と理解できない範囲をもう少し明確にします。
A｜Bが￢(A∧B)と同じ真理関数を表現するために、NAND(NOT+AND)と呼ばれることは分かります。
A)の(2)から(3)、B)の(3)から(4)への変形を理解するには、＜￢P ⇔ P｜P＞という基本的な公式を理解しておくことが前提になると思うのですが、この基本的な部分が既に分かりません。項目が一つしかないので、<￢(A∧B)>に由来するNANDの性質を満たしていないように感じてしまうのです。Pでないを<P｜P>とも書けるという単なる決まりとも思えません。
　<￢P>から<P｜P>へと変化する際にPの数が倍になっていることと、<(P｜Q)｜(P｜Q)><(P｜P)｜(Q｜Q)>というPとＱが二つずつある形との間には何かつながりがあると思うのですが、PとQが交互に出てくるか、続けて出てくるかの違いを生じさせる原因が分かりません。

分かる方がおられましたら、よろしければ説明していただけないでしょうか。
お願いいたします。

No.2 ベストアンサー 回答者： taparon 回答日時： 2010/07/22 21:11

今日は、疲れているので、詳しく説明できません（もしかしたらミスするかも(^^;)）。

すみません。今、できるだけの回答をしてみます。
A)の右側の変形の場合、R⇔P|Q とすれば、￢(P｜Q) ⇔ ￢R ⇔ R|R ⇔ （P|Q)|(P|Q)
となります。
B)の最後の変形では、￢P ⇔ P|P と ￢Q ⇔ Q|Q の変形を同時にやれば答えがでるはずです。
そこで、このPとQの出現順番の違いについてですが。
NANDは交換法則 P|Q ⇔ Q|P は成り立つのですが、結合法則 (P|Q)|S ⇔ P|(Q|S) が成り立ちません。
もし結合法則が成り立てば、(P｜Q)｜(P｜Q) ⇔ (P|Q)|(Q|P) ⇔ P|(Q|Q)|P ⇔P|P|(Q|Q) ⇔ (P|P)|(Q|Q) となって楽なのですが、一般にはできないわけです。それでA)とB)での結果は異なるわけです。
この結合法則が成り立たない、というのは人間にとって非常に直感が効きにくいので計算が分かりにくくなります。
そのため、ブール代数はNANDだけ、とかNORだけのひとつの演算でも表現できるにもかかわらず、AND、OR、NOT、などの方がよく使われます。
（とはいえ、論理回路の設計などでは、例えばNANDの数をできるだけ少なくなるように変形する、などの話は必要になります。）

この回答へのお礼

詳しくありがとうございました。
おかげで完璧に理解できました。
単純な原理が見ぬけていなかったのですね。

すぐにご返事をさしあげたつもりだったのですが、
正しい操作が出来ていなかったのか、
返事が出来ていませんでした。
申し訳ありませんでした。

お礼日時：2010/08/08 10:10

No.1 回答者： taparon 回答日時： 2010/07/18 02:18

基本的な問題は、￢P⇔P|P の部分ですね。

￢(A∧B)のAとBは何でもいいので、等しくともかまわないわけです。
NANDの定義により、P|P ⇔ ￢(P∧P） ⇔ ￢P　が証明されます。
AND（∧）はべき等律 P∧P ⇔ P が成り立つのでこうなりますが、｜はべき等率P|P ⇔ Pは成り立ちません。それでPの数が倍になります。
NANDは、通常使われる式の変形が成り立たないことが多いので、ひとつひとつ形式的に変形していくしかないと思います。

この回答への補足

ご回答ありがとうございました。

おかげさまで、￢P⇔P|Pの変形が分かりました。
￢PからP|Pに至る変化に、￢Pと等しい￢(P∧P）が潜んでいたのですね。

説明していただいた内容で本来は全て解決するはずだとおもうのですが、
こうした問題は本当に苦手で、まだ疑問が残っています。

A) (1)P∧Q ⇔ (2)￢(P｜Q) ⇔ (3)(P｜Q)｜(P｜Q)
B) (1)P∨Q ⇔ (2)￢(￢P∧￢Q) ⇔ (3)￢P｜￢Q ⇔ (4)(P｜P)｜(Q｜Q)

A)の(2)から(3)の変化では、PとQの数が倍になって、両者がPQPQと交互に出てきます。
B)の(3)から(4)の変化でも、PとQの数は倍になりますが、両者はPPQQと二つ続けて出て来ます。この違いはどうして生じるのでしょうか？

より基本的な部分が分かっていないのが問題だと思います。

￢Pが￢(P∧P） と等しい（=べき等律がなりたつ）ために、Pの数が倍になったP|Pになるのは分かります。
ですが、￢(P｜Q)から(P｜Q)｜(P｜Q)、￢P｜￢Qから(P｜P)｜(Q｜Q)というように、すでにシェーファー記号が用いられた論理式が、シェーファー記号を使った別の論理式にさらに変形できるのは何故なのか、その際にPとQの数が倍になるのは何故なのかが理解できません。

何度も申し訳ありませんが、よろしければもう少し説明していただけないでしょうか？

補足日時：2010/07/18 13:01