第172回　裏の裏は表（後編）

$ \newcommand{\LAND}{\mathrel{\land}} \newcommand{\LOR}{\mathrel{\lor}} \newcommand{\LNOT}{\lnot} \newcommand{\BITAND}{\mathrel{\&}} \newcommand{\BITOR}{\mathrel{|}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\RELATED}{\dashleftarrow\dashrightarrow} $

僕の部屋

真理値表

僕「命題は真か偽か判断できる。真の命題と偽の命題という$2$通りがある。でも、命題が多くなってくると、真と偽の組み合わせはどんどん増える。 それを整理するために真理値表（しんりちひょう）というものがある」

ユーリ「しんりちひょう」

僕「命題$P$は真か偽の$2$通りのどちらか。そのそれぞれに対して、命題$Q$は真か偽の$2$通りのどちらか。だから組み合わせは全部で何通り？」

ユーリ「$4$通り」

僕「そうだね。$2 \times 2 = 4$通りある。それをこんなふうにまとめたものが真理値表」

ユーリ「ふんふん。これ、見たことある」

僕「まあ、よく書くからね」

ユーリ「……これって、命題$P$が真で、命題$Q$が真のときに限って、$P \text{かつ} Q$が真になるっていってるんでしょ？」

僕「そうだよ」

ユーリ「これって《計算》してるみたい」

僕「そうだね！　その通り。その考えで合ってるよ。真と偽という$2$つの値を使って、《かつ》という計算をしていると考えることができる。 《真かつ真》のときだけ計算結果が真になるという計算だね」

ユーリ「んー、だったら、真理値表って、こー書いてもいいね！」

僕「いいねえ！」

ユーリ「ね！　九九の表みたい！　……あ、思い出した。ほら、リサ姉（ねー）のこと」

僕「リサちゃん？」

ユーリ「あのね、双倉図書館でリサ姉からお話聞いたとき、同じ計算が出てきた！」

僕「いつのことだろう……」

ユーリ「お兄ちゃんはいなかったよ。インフルインフル。双倉図書館（ならびくらとしょかん）の《変幻ピクセル》イベント（第103回変幻ピクセル（前編）参照）」

僕「ああ、あのとき？」

ユーリ「そんときは、《ビット単位の論理積》てゆーのがあった。《かつ》と同じだよ」

僕「確かにそうだね。$0$を偽に置き換えて、$1$を真に置き換えて、$\BITAND$を《かつ》に置き換えればぴったり同じだね。 書くのがたいへんだから、偽を《$F$》と書いて、真を《$T$》と書いて、《かつ》を《$\LAND$》にするよ」

ユーリ「同じ計算だ」

僕「そうだね。文字の置き換え、記号の置き換えをするだけで、完全に入れ替わるってことは、同じ計算といえるよね」

ユーリ「『もしかして』」

僕「『わたしたち』」

ユーリ「『いれかわってる〜？』」

僕「時事ネタ自重！」

ユーリ「お兄ちゃんのノリツッコミ初めて見た」

僕「まじめに行こう」

ユーリ「あのね、《変幻ピクセル》イベントで、 リサ姉が機械見せてくれたの。紙をスキャンして、 色が黒いところが$1$になって、白いところが$0$になるとき、 黒と黒が重なるときだけ黒をプリントする……みたいなの。 それが論理積」

僕「なるほどね。それは計算結果を図形の色に対応させてるんだ」

ユーリ「そんな感じ」

または

ユーリ「否定と、《かつ》と、それから《または》でしょ？」

僕「そうだね。命題を扱う命題論理だと、その$3$つは大事だね。《または》の真理値表はわかる？」

ユーリ「お兄ちゃんから聞いたことある。少なくとも片方が真のときだけ、全体が真になるんでしょ？」

僕「そうだね」

ユーリ「ビット単位の論理和ってゆーのもあったよ！」

僕「それに合わせて、$F$と$T$で書いてみようか。《または》は$\LOR$にして」

ユーリ「こっちも、《$\BITOR$》と《$\LOR$》は同じ計算なんだね！」

僕「そうだね。同じ計算をやってるように見えるね」

ユーリ「あれ？　もしかして……」

僕「もう時事ネタはいいよ」

ユーリ「違うの！　そーじゃなくて、思いついたの！」

僕「何を？」

ユーリ「同じなの！　《かつ》と《または》って同じ計算じゃん！」

僕「？」

ユーリ「置き換えちゃう。$F$と$T$を置き換えて、$\LAND$と$\LOR$を置き換えるの！」

僕「書いてみようよ」

ユーリ「ね？　ね？　でしょでしょ？　$F$と$T$を交換して、$\LAND$と$\LOR$を交換しても、真理値表は正しいじゃん？」

僕「まったくその通り！　すごいな！」

ユーリ「ねー、これって大発見？」

僕「そうだね！　ユーリのこの発見は、《ド・モルガンの法則》の言い換えになっているよ」

ユーリ「なにそれ」

僕「ド・モルガンの法則っていうのは、論理の法則の一つだよ。 真偽を交換することと、論理和と論理積を交換することの関係を表してる」

ユーリ「へー」

僕「ド・モルガンの法則はいろんな書き方ができるけど、たとえばこんなふうに書ける。$\LNOT P$というのは$P$の否定のこと」

ユーリ「へ？」

僕「何が『へ？』なの？　ユーリが発見したことと同じになってるよ」

ユーリ「お兄ちゃん得意の数式が出てきたけど、これってユーリが言ったことと同じなの？」

僕「同じだよ。ユーリは$F$と$T$を交換して、$\LAND$と$\LOR$を交換しても、正しい真理値表ができるっていってたわけだろう？」

ユーリ「まーね」

僕「$F$と$T$を交換するということは、真偽を交換するわけだから、否定$\LNOT$を使えばいいよね。 $P$があったら$\LNOT P$にして、 $Q$があったら$\LNOT Q$にする。 最後に全体の式もまとめて否定$\LNOT$する」

ユーリ「そっか……」

僕「そういうつもりでもう一度式を読んでごらんよ」

ユーリ「じー」

$$ P \LAND Q \equiv \LNOT((\LNOT P) \LOR (\LNOT Q)) $$

僕「ね？」

ユーリ「なーるほど！　わかった。ほんとだ。左辺の$P$を$\LNOT P$で置き換えて、$Q$を$\LNOT Q$で置き換えて、 $\LAND$を$\LOR$で置き換えて、全体に$\LNOT$付けたのが右辺になってる」

僕「そうそう。それで正しく式を読んでいるよ。左辺$P \LAND Q$の真理値表と、 右辺$\LNOT((\LNOT P) \LOR (\LNOT Q))$の真理値表を比べてみれば、 そうすると、この$2$つの真理値表が一致することがわかるよ」

ユーリ「……両方とも、$F F F T$？」

僕「そうだね。ということは、$P,Q$の真偽に関わらず、この$2$つの式の真偽は一致するといえる。 $P \LAND Q$が$T$のとき、 $\LNOT((\LNOT P) \LOR (\LNOT Q))$も$T$になるし、 片方が$F$なら、他方も$F$」

ユーリ「……」

僕「ド・モルガンの法則はもう一つあるよ。もう一度$\LAND$と$\LOR$を置き換えたものだね。 まとめて書いておこうか」

ユーリ「……」

僕「ユーリは黙っている」

ユーリ「……ねーお兄ちゃん。さっきの$P$とか$Q$って命題だよね？」

僕「そうだね。値が真か偽かどちらかに決まる。$T$か$F$かどちらかになるのが命題だから」

ユーリ「$P \LAND Q$とか$P \LOR Q$も命題だよね？」

僕「そうだね。そして$\LNOT P$も命題……って、ねえ、ユーリは何を考えているんだろう」

ユーリ「だったら、さっきの《ド・モルガンの法則》も命題だよね！！」

$$ P \LAND Q \equiv \LNOT((\LNOT P) \LOR (\LNOT Q)) $$

僕「そうだね！　それを考えていたのか。その通りだよ、ユーリ」

ユーリ「だったら、ねえ、$\equiv$の真理値表も書けるでしょ？　ね？」

僕「書けるねえ！」

ユーリ「両辺が$F$のとき。両辺が$T$のとき。そのときだけが$T$になる！　そーゆー真理値表！　満足ぅ！」

僕「確かに、それが論理同値の意味だね。やるなあ、ユーリ……って、そうか、これ、排他的論理和の否定だね。リサちゃんがビット単位の計算でやってた（第102回 冒険ビット（後編）参照）」

ユーリ「どゆこと？」

僕「ほら、論理同値の$\equiv$は《左辺と右辺の真偽が等しいときだけ真になる》っていう計算だろう？」

ユーリ「そだね」

僕「そしてビット単位の排他的論理和は《$0$と$1$が不一致のときだけ$1$になる》というんだから、$\equiv$の否定になるよね」

ユーリ「そかそか。両辺の真偽が不一致のときに真になる！」

演算子は何種類？

ユーリ「論理の計算ってたくさんあるんだね」

僕「そうだね。《かつ》の論理積、《または》の論理和、《〜でない》の否定、《等しい》の論理同値……そうだ！　こういう命題代数の演算子は全部で何種類あると思う？　$P$と$Q$という$2$つの命題から真偽値が定まる演算子」

ユーリ「え？　無数にあるんじゃないの？」

僕「……どうしてそう思ったんだろう」

ユーリ「だって、いくらでも複雑な式って作れるじゃん？　$P \LAND Q$とか、$P \LAND (Q \LOR P)$とか、$(\LNOT P) \LAND ((\LNOT Q) \LAND P)$とか……」

僕「ああ、確かにそうなんだけど、その中には論理同値なものも含まれているよね。 式をいくら複雑に書いたとしても、$P$と$Q$の真偽に応じて、 まったく同じ結果になるとしたら、それは同じものと見なすとして」

ユーリ「そっか……えーと？　てことは、真理値表が何種類あるかってこと？」

僕「そうだね。その通り。ただし、$P$と$Q$の$2$つだけが出てくるものだよ。$P,Q,R$みたいに命題$3$つは出てこない。演算子を仮に$\circ$で表すと、こういう形ってことだね」

ユーリ「ははーん。わかったわかった。この真理値表の$\text{?}$のところに$F$か$T$かが入るんでしょ？」

僕「そうだね」

ユーリ「だったらカンタン！　一つの$\text{?}$には$F,T$の$2$通りあるんだから、$$ 2 \times 2 \times 2 \times 2 = 2^4 = 16 $$ で、$16$通りの真理値表が作れる！」

僕「はい、正解です！」

ユーリ「えー、でも、ほんとに$16$通りもあるの？　$8$種類くらいかと思ってた」

僕「真理値表を書けば納得するよ」

ユーリ「$15$通りしかないじゃん……って、$0$から始まってるから$16$種類ってことか」

僕「そうだね。$\circ_0$から$\circ_{15}$まで、演算子に番号を付けてみたんだけど」

ユーリ「ご苦労」

僕「偉そうだな。ところで、この中ですでに出てきたものもあるよね。$\circ_{6}$と$\circ_{8}$と$\circ_{9}$と$\circ_{14}$」

ユーリ「ふんふん……あれ？　全部$F$とか全部$T$というのもある」

僕「そりゃそうだね。すべてのパターンを作ったわけだから。$P$のままとか、$Q$のままというのもあるよ」

ユーリ「そっか。残りは$6$個だね」

僕「たとえば、$P \circ_{1} Q$はどんな計算だろう」

ユーリ「$P$と$Q$の両方が$F$のときだけ、$F$になる計算……そっか、$P \LOR Q$は両方が$F$のときだけ、$T$になるから、その否定？　$\LNOT(P \LOR Q)$じゃない？」

僕「うん、そうだね」

$$ P \circ_{1} Q \equiv \LNOT(P \LOR Q) $$

ユーリ「$P \circ_{2} Q$は、$P$が$F$で、$Q$が$T$のときだけ$T$になる」

僕「$P$を否定しておいて、$\LAND$を計算すればいいんだから、$(\LNOT P) \LAND Q$ということだね」

$$ P \circ_{2} Q \equiv (\LNOT P) \LAND Q $$

ユーリ「あったまいー！　あっ、次の$P \circ_{4} Q$も同じようにできるよ。$Q$を否定しておいて、$\LAND$の計算」

$$ P \circ_{4} Q \equiv P \LAND (\LNOT Q) $$

僕「そうだね。そして$P \circ_{11} Q$は、$P \circ_{4} Q$を否定すればいいから、$\LNOT(P \LAND (\LNOT Q))$になるね」

$$ \begin{align*} P \circ_{4} Q & \equiv \LNOT(P \circ_{4} Q) \\ & \equiv \LNOT(P \LAND (\LNOT Q)) \\ \end{align*} $$

ユーリ「うわ、ややこしい！」

僕「そこで、ド・モルガンの法則を使おう！」

ユーリ「お？」

僕「$\LNOT(P \LAND (\LNOT Q))$は、ド・モルガンの法則を使えば、$(\LNOT P) \LOR (\LNOT(\LNOT Q))$になるよね」

ユーリ「余計ややこしいよーな……」

僕「うん、でも$\LNOT(\LNOT Q)$って$Q$と論理同値だから、簡単にできる。否定の否定はなくせるから」

$$ \begin{align*} P \circ_{4} Q & \equiv \LNOT(P \circ_{4} Q) \\ & \equiv \LNOT(P \LAND (\LNOT Q)) \\ & \equiv (\LNOT P) \LOR (\LNOT(\LNOT Q))) && \text{ド・モルガン$\HIRANO$法則} \\ & \equiv (\LNOT P) \LOR Q && \text{否定$\HIRANO$否定をなくした} \\ \end{align*} $$

僕「だから、$$ P \circ _{11} Q \equiv (\LNOT P) \LOR Q $$ ということになる」

ユーリ「あ、意外にすっきり？」

僕「うん、$(\LNOT P) \LOR Q$というのは、《$P$でないか、または、$Q$》だね。これはよく$P \to Q$と書いて《$P$ならば$Q$》と呼ぶよ」

ユーリ「ならば？」

僕「そうだね」

• $P$が$F$だったら、$Q$が$F$でも$T$でも、$P \to Q$は問答無用で$T$とする。
• $P$と$Q$の両方が$T$だったら、$P \to Q$は$T$とする。
• $P$が$T$で、$Q$が$F$のときに限り、$P \to Q$は$F$になる。

ユーリ「それって、《$P$ならば$Q$》なの？　なんだか変なの」

僕「どこが変？」

ユーリ「$P$が偽で、$Q$が真のとき、《$P$ならば$Q$》って真になるの？」

僕「そうだね。命題論理ではそういうふうに決めているね」

ユーリ「あのね、$P$が偽で、それなのに、$Q$が真だったら、$P \to Q$は偽になるよーな気がしたの。何となく」

僕「うん、そこは気になるところだよね。でも、そうすると、ユーリがいう《ならばモドキ》は、こういう真理値表になるよね」

ユーリ「そだね……あり？　これって$P \equiv Q$じゃん。$P$と$Q$が同じときだけ$T$だから」

僕「そうだね。ユーリがさっきいってた、《$P$ならばモドキ$Q$》は《$P \equiv Q$》という論理同値になっちゃう」

ユーリ「そっか……それは、それで違うよーな」

僕「最後に残った$P \circ_{13} Q$は$\LNOT(P \circ_{2} Q)$だから、$$ P \circ_{13} Q \equiv \LNOT((\LNOT P) \LAND Q) $$ になるね。ド・モルガンの法則を使えば、 $$ P \circ_{13} Q \equiv P \LOR (\LNOT Q) $$ と書くこともできる。これで全種類できたね。まとめて書いてみようか」

ユーリ「うーん……」

僕「ごちゃごちゃしちゃったかな」

ユーリ「んにゃ。あのね、この表の中の《パターン》を見てたの」

僕「《パターン》というと？」

ユーリ「あのね、$T$が$1$個だけ出てくる《パターン》は$4$個あるの」

僕「うんうん、そうだね」

ユーリ「でね、$T$が$1$個ってゆーのは、$P \LAND Q$の仲間じゃん？」

僕「なるほどなるほど。そうだね。$x \LAND y$の形をしていて、$x$と$y$に$P$と$Q$をそのまま入れるか、$\LNOT$つけて入れるかの違い」

ユーリ「そー！　それそれ！　だから、こんなふーに$\LAND$でまとめられる！」

僕「なるほどね」

ユーリ「そんでね、同じよーにして、今度は$F$が$1$個ってゆーのは、$P \LOR Q$の仲間！」

僕「確かに。さっきとそっくりだ」

ユーリ「あと、$F$と$T$が$2$個ずつってゆーのは$P \equiv Q$の仲間と、$P,Q$単独の仲間なのであった！」

僕「おもしろいなあ。$16$のパターンを$T$の個数で分類できるっていうわけだね」

ユーリ「あと$T$が$0$個のやつと、$T$が$4$個のもあるけどね」

ならば、再び

僕「真理値表を眺めているのはおもしろいなあ」

ユーリ「……」

僕「また何か見つけた？」

ユーリ「お兄ちゃん！　$P \to Q$って、$(\LNOT P) \LOR Q$だよね？」

僕「そうだね」

ユーリ「だったら、$P \LOR (\LNOT Q)$は$P \gets Q$になる？」

僕「ああ、そうだね。そうなるよ。$P \gets Q$は$Q \to P$と論理同値だと定義すれば」

ユーリ「えーと、それじゃ、もしかして、$(P \to Q) \LAND (P \gets Q)$って、$P \equiv Q$になる？」

僕「……！！」

ユーリ「ねー、そうなるよね？」

僕「……なるよ、ユーリ！ 真理値表書けば証明できる」

ユーリ「やっぱり」

僕「どうしてそう思ったんだろう」

ユーリ「なんとなく。あのね。《$P$ならば$Q$》でしかも《$Q$ならば$P$》だったら、$P$と$Q$は同じじゃね？　って思ったの」

僕「……」

ユーリ「ほら、さっきユーリが《$P$ならばモドキ$Q$》を考えたとき、$P$が偽で$Q$が真のときに全体を偽にしたから、《$P \equiv Q$》になっちゃったじゃん？　あのとき、 ユーリは《$P \to Q$》を考えてるつもりで、《$(P \to Q) \LAND (P \gets Q)$》を考えてたんだね！　やっとわかった」

僕「……！」

ユーリ「どしたの？　『お兄ちゃん、変やよ』」

僕「いや……そういうふうに、論理同値と《ならば》を関連づけて考えたことなかったからなんだけど。うまく言葉にできない感動がやってきてるんだ、いま。それに、 $$ P \equiv Q $$ という命題は、 $$ P \leftrightarrow Q $$ と書くこともあるし、 $$ P \leftrightarrows Q $$ と書くこともあるんだよ！　確かに$(P \to Q) \LAND (P \gets Q)$だね！」

ユーリ「にゃるほど！」

対偶

僕「ところで、これだけ真理値表を調べてくると、《逆は必ずしも真ならず》という言葉の意味を命題論理で考えることができる」

ユーリ「逆は……？」

僕「……必ずしも真ならず。さっき出てきた、$$ P \to Q $$ という形の命題と、 $$ P \gets Q $$ という形の命題があるよね」

ユーリ「うん」

僕「命題$P \to Q$の逆っていうのは、$P \gets Q$の命題のこと。反対に$P \gets Q$の逆は$P \to Q$」

ユーリ「矢印の向きを逆にしているから？」

僕「そうだね。それでね、《逆は必ずしも真ならず》っていうのは、 命題論理風にいえば、 $P \to Q$が$T$のときでも、$P \gets Q$が$T$になるとは限らない……となる」

ユーリ「ふーん……って、それ、あたりまえじゃない？　だって、真理値表比較すればわかるもん」

僕「そうだね」

ユーリ「だよね」

僕「それから、数学でよく出てくるのは《もとの命題と対偶は論理同値》というものだね」

ユーリ「たいぐー」

僕「命題$P \to Q$の対偶っていうのは、$(\LNOT P) \gets (\LNOT Q)$という命題のこと」

ユーリ「むむ？」

僕「矢印を逆にしただけなのが《逆》で、《対偶》はさらに$P$と$Q$をそれぞれ否定しているんだよ」

ユーリ「それが同じになるの？」

僕「すぐはわからないと思うけど……」

ユーリ「真理値表でわかる？」

僕「そうだね」

ユーリ「えーと……」

僕「……」

ユーリ「そっか、そーなるね」

僕「いま、どういう経路で納得したんだろう」

ユーリ「んーとね、$P \to Q$って、$T \to F$のときだけ$F$になるでしょ。だから、そこを見てたの。それがちょうど$(\LNOT P) \gets (\LNOT Q)$が$F \gets T$になるところと合ってる」

僕「めざといなあ……式変形でもできるはずだよ」

$$ \begin{align*} P \to Q &\equiv (\LNOT P) \LOR Q && \text{$\to$ $\HIRANO$定義から} \\ &\equiv Q \LOR (\LNOT P) && \text{$x \LOR y \equiv y \LOR x$だから} \\ &\equiv (\LNOT(\LNOT Q)) \LOR (\LNOT P) && \text{$Q \equiv \LNOT(\LNOT Q)$だから} \\ &\equiv (\LNOT Q) \to (\LNOT P) && \text{$\to$ $\HIRANO$定義から} \\ &\equiv (\LNOT P) \gets (\LNOT Q) && \text{$x \to y \equiv y \gets x$だから} \\ \end{align*} $$

ユーリ「へー……ほんとだ。$Q$を$(\LNOT(\LNOT Q))$に直すところ、おもしろーい」

実際は？

僕「ややこしいけれど、なかなかおもしろいなあ」

ユーリ「対偶って、数学でよく使うの？」

僕「そうだね。何かを証明しようとして、直接証明するのが難しいとき、対偶を証明してしまえばいいから。《$P$ならば$Q$》という形のものを証明する代わりに、 《$Q$でないならば$P$でない》という対偶の方を証明するってことだね」

ユーリ「かえってややこしーじゃん」

僕「そうだね。《$P$でないならば$Q$でない》という命題を証明する代わりに、《$Q$ならば$P$》を証明する。これなら簡単になっているよね」

ユーリ「そっか」

僕「たとえば、こんなの。《実数$x$が$1$より大きくないならば、実数$x$は$3$より大きくない》は正しい？」

ユーリ「えーと？　正しい……？」

僕「正しいね。直接考えてもいいけれど、対偶を考えるとすっきりわかる。 だって《実数$x$が$3$より大きいならば、実数$x$は$1$より大きい》を考えればいいから」 $3$より大きいなら、$1$より大きいというのはすぐわかる」

ユーリ「ふんふん……ん？　ダウト！」

僕「なぜダウト？」

ユーリ「ねえ、お兄ちゃん。《実数$x$が$3$より大きい》っていうのは、命題なの？」

僕「ああ、それはね……」

（第172回終わり。第173回へ続く）

参考文献

• The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1』（Donald E. Knuth）
• 『論理と集合から始める数学の基礎』（嘉田勝）
• 『コンピュータのための数学—論理的アプローチ』（D. グリース, F.B. シュナイダー）
• 『プログラマの数学』（結城浩）

14230 true