第172回 裏の裏は表(後編)

「ミルカさまから《パターンを見抜け》って言われてるもん!」とユーリが言う。「論理と証明」第1章後編。
登場人物紹介
:数学が好きな高校生。
ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。
$ \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\text{かつ}Q$の真理値表
$$ \begin{array}{|cc|c|} \hline P & Q & P \text{かつ} Q \quad \\ \hline \text{偽} & \text{偽} & \text{偽} \\ \text{偽} & \text{真} & \text{偽} \\ \text{真} & \text{偽} & \text{偽} \\ \text{真} & \text{真} & \text{真} \\ \hline \end{array} $$

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

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

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

「そうだよ」

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

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

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

$P\text{かつ}Q$の真理値表(書き換え)
$$ \begin{array}{|c|cc|} \hline \text{かつ} & \text{偽} & \text{真} \\ \hline \text{偽} & \text{偽} & \text{偽} \\ \text{真} & \text{偽} & \text{真} \\ \hline \end{array} $$

「いいねえ!」

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

「リサちゃん?」

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

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

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

「ああ、あのとき?」

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

論理積(ビット単位) $$ \begin{align*} 0 \BITAND 0 &= 0 && \\ 0 \BITAND 1 &= 0 && \\ 1 \BITAND 0 &= 0 && \\ 1 \BITAND 1 &= 1 && \text{両方が$1$ $\HIRANO$ときだけ$1$} \\ \end{align*} $$

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

論理積(かつ) $$ \begin{align*} F \LAND F &= F && \\ F \LAND T &= F && \\ T \LAND F &= F && \\ T \LAND T &= T && \text{両方が$T$ $\HIRANO$ときだけ$T$} \\ \end{align*} $$

$F$は偽、$T$は真、$\LAND$は《かつ》を表す。

ユーリ「同じ計算だ」

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

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

「『わたしたち』」

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

「時事ネタ自重!」

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

「まじめに行こう」

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

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

ユーリ「そんな感じ」

または

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

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

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

$P\text{または}Q$の真理値表
$$ \begin{array}{|cc|c|} \hline P & Q & P \text{または} Q \quad \\ \hline \text{偽} & \text{偽} & \text{偽} \\ \text{偽} & \text{真} & \text{真} \\ \text{真} & \text{偽} & \text{真} \\ \text{真} & \text{真} & \text{真} \\ \hline \end{array} $$

「そうだね」

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

論理和(ビット単位) $$ \begin{align*} 0 \BITOR 0 &= 0 && \text{両方が$0$ $\HIRANO$ときだけ$0$} \\ 0 \BITOR 1 &= 1 && \\ 1 \BITOR 0 &= 1 && \\ 1 \BITOR 1 &= 1 && \\ \end{align*} $$

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

論理和(または) $$ \begin{align*} F \LOR F &= F && \text{両方が$F$ $\HIRANO$ときだけ$F$} \\ F \LOR T &= T && \\ T \LOR F &= T && \\ T \LOR T &= T && \\ \end{align*} $$

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

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

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

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

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

「何を?」

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

「?」

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

「書いてみようよ」

置き換えたらどうなる?
$$ \begin{array}{ccc} F & \RELATED & T \\ \LAND & \RELATED & \LOR \\ \end{array} $$
真理値表の置き換え

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

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

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

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

ユーリ「なにそれ」

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

ユーリ「へー」

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

ド・モルガンの法則
命題$P$と命題$Q$の真偽に関わらず、 $$ P \LAND Q $$ と $$ \LNOT((\LNOT P) \LOR (\LNOT Q)) $$ の真偽はつねに一致する。

このことを $$ P \LAND Q \equiv \LNOT((\LNOT P) \LOR (\LNOT Q)) $$ と書く。

$\equiv$は《論理同値》を表す。

ユーリ「へ?」

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

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

「同じだよ。ユーリは$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$つの真理値表が一致することがわかるよ」

$P \LAND Q$の真理値表

$\LNOT((\LNOT P) \LOR (\LNOT Q))$の真理値表

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

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

ユーリ「……」

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

ド・モルガンの法則
$$ \begin{align*} P \LAND Q &\equiv \LNOT((\LNOT P) \LOR (\LNOT Q)) \\ P \LOR Q &\equiv \LNOT((\LNOT P) \LAND (\LNOT Q)) \\ \end{align*} $$
この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の女子高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わってください。本シリーズはすでに何冊も書籍化されている人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

CookieFebruary6 数理論理学を読んでるのでタイムリー でも終盤のユーリ、 _人人人人人人人人人人_ >そんな中学生がいるか<  ̄Y^Y^Y^Y^Y^Y^Y^Y^Y ̄ 2年以上前 replyretweetfavorite

hyuki 金曜日は『数学ガールの秘密ノート』の日。最新回はお休み。無料リンク2個をツイート。公式 「論理と証明」第1章(前・後編)12/16 13:37まで無料。 https://t.co/u99dwzjdPO https://t.co/xViUNZkaNY 2年以上前 replyretweetfavorite

hilbert_d 【はてブ新着IT】 2年以上前 replyretweetfavorite

inaba_darkfox 真理値表を命題論理の記号で全部作るところとか面白かった。 2年以上前 replyretweetfavorite