20201118『数理論理学』輪講のノート

選言標準形に比べて連言標準形は「分かりにくい」「ひと手間、多い」と感じたかもしれませんが、双対性の理解を深めると全く対等に感じられるようになります。「双対性」とは何かを理解するために、次のようなパズルを考えます。

下の表において、「♪」は「かつ」か「または」のいずれかですが、どちらなのかは伏せられています。さらに、「★」と「■」は一方が「真」、他方が「偽」ですが、どちらが「真」なのかは伏せられています。この表だけを見て、各記号の意味を当てることはできるでしょうか?\[\begin{array}{ccc}P&Q&P♪Q\\★&■&■\\■&★&■\\★&★&★\\■&■&■\end{array}\]実際に検討してみると、「♪・★・■」は「または・偽・真」でもよいし、「かつ・真・偽」でもよいことが分かります。つまり「真/偽」と「かつ/または」とを同時に入れ替えると区別がつかないわけです。このような性質を(定義が曖昧ですが)「双対性」と呼びます。

これまで真偽表では「1」を真、「0」を偽とみなしてきましたが、ここで真偽をひっくり返して、「1」は偽、「0」は真だと思うことにしましょう。すると「P∨Q」の真偽表\[\begin{array}{ccc}P&Q&P\vee Q\\1&1&1\\1&0&1\\0&1&1\\0&0&0\end{array}\]は「両方とも真(0)のときだけ真(0)だが、一方でも偽(1)なら偽(1)になってしまう」ということになり、これは「PかつQ」という意味だと解釈できます。今まで「または」だと思っていた「∨」が、真偽を入れ替えることにより「かつ」になってしまいました。まったく同様に考えると、「∧」は「または」という意味になります。

以上のような悟りを開いた状態で、教科書p56の例\[\begin{array}{ccc|c}P&Q&R\\1&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{array}\]を見ると、この論理式が真(0)になるのは
・\(P\):偽(1) かつ \(Q\):偽(1) かつ \(R\):真(0)
または
・\(P\):偽(1) かつ \(Q\):真(0) かつ \(R\):偽(1)
または
・\(P\):真(0) かつ \(Q\):偽(1) かつ \(R\):真(0)
または
・\(P\):真(0) かつ \(Q\):真(0) かつ \(R\):偽(1)
の場合です。これらを、「かつ」と唱えながら「∨」で、「または」と唱えながら「∧」で結んでゆくと、\[(\neg P\vee\neg Q\vee R)\wedge(\neg P\vee Q\vee\neg R)\wedge(P\vee\neg Q\vee R)\wedge(P\vee Q\vee\neg R)\]
となり、教科書p59の結果と一致します。双対性を用いることにより、ド・モルガン則や二重否定除去による変形の手間が省けましたが、「これらの法則そのものが双対性を端的に表している」と言うこともできます。