うさぎでもわかる離散数学　第2羽　命題・真理値表の書き方

2019年4月7日 2019年4月7日 27分5秒

ももうさ

スポンサードリンク

こんにちは！　ももやまです！
今日は、命題、論理演算（ブール代数）・真理値表（場合分け）の書き方をまとめてみました。
最後に、今までの知識を使った論理パズルがあるので離散数学未履修の人でもぜひ見てください！

※第2羽を二項関係にしていたのですが、訳あって第4羽にさせてください。よろしくおねがいします。

第1羽はこちらから↓

www.momoyama-usagi.com

スポンサードリンク

１．命題

本当か嘘かが判定できる文、つまり真偽が明確にわかる文章を命題といいます。
また、命題をいちいち日本語で書くのはめんどいので、命題変数 \( p \),\( q \) みたいに小文字や、\( A \), \( B \) のように大文字で表す。また、命題が真（本当）であれば、1 (True）、偽（うそ）であれば0（False）で表し、命題変数には0か1のいずれかが入る。（普段数学で使ってる変数 \( a, b, x, y \) に0か1しか入らないものが命題変数だと思ってください。）

例えば、「私はうさぎである。」という命題があるとし、この命題を \( p \) としましょう。このとき、本当に私がうさぎであればこの命題は真となり、\( p = 1 \) が代入されます。しかし、もし私がうさぎでなかったらこの命題は偽となり、\( p =0 \) が代入されます。

スポンサードリンク

２．論理演算

(1) and演算 \( p \land q \) (\( AB \))　

まずは、and演算です。これは、２つの変数 \( p,q \) がともに1のときのみ、答えが1となり、それ以外のときは0となります。\( \land \) が and の意味を持ちます。論理積ともいうので、情報系の場合は、 \( A \cdot B \) とすると and 演算となります。（\( \cdot \) を省略して \( AB \) と書くことが多い。）

これを表で表すと、

\( p \)	\( q \)	\( p \land q \)
0	0	0
0	1	0
1	0	0
1	1	1

\( p \)	\( q \)	\( p \land q \)
T	T	T
T	F	F
F	T	F
F	F	F

となります。このように、変数のすべてのパターンとそのパターンに対する結果をすべて表にしたものを真理値表といいます（場合分け）。真理値表は0を偽、1を真とする書き方でも、Tを真、Fを偽とする書き方でもどちらでも構いません。ただし、全パターン網羅するのを忘れずに。具体例を１つ挙げてみます。

例えば「中間試験が60点以上である」を \( p \) とし、「期末試験が60点以上である」を \( q \) とする。すると、「中間試験が60点以上かつ期末試験が60点以上」というのが \( p \land q \) となります。

この場合、確かに「中間試験が60点以上」、「期末試験が60点以上」のうち、どちらか一方でも偽になると、「中間試験が60点以上かつ期末試験が60点以上」とは言えませんよね。表を見ても、どちらか片方が0になっていたら \( p \land q \) が0になっていますよね。

\( p \land q \) の真理値表の書き方

(1) まず \( p \) が0のところは結果が0なので \( p \land q \) に 0 を書きます。
(2) つぎに \( q \) が0のところも結果が0なので \( p \land q \) に 0 を書きます。
(3) 残ったところが両方とも真のところなので \( p \land q \) に 1 を書きます。

これで書けます。みなさん試しにやってみてください！

(2) or演算 \( p \lor q \) (\( A + B \))　

つぎに or 演算です。2つの変数 \( p,q \) が一方でも1である場合、答えが1となり、両方とも0のときだけ答えが0となります。\( \lor \) が or の意味を持ちます。論理和ともいうので、情報系の場合は、 \( A + B \) とすると or 演算となります。(1と同様にこれを真理値表で表してみましょう。

\( p \)	\( q \)	\( p \land q \)
0	0	0
0	1	1
1	0	1
1	1	1

\( p \)	\( q \)	\( p \land q \)
T	T	T
T	F	T
F	T	T
F	F	F

先程の例と同じく、「中間試験が60点以上である」を \( p \) とし、「期末試験が60点以上である」を \( q \) とする。すると、「中間試験が60点以上または期末試験が60点以上」というのは \( p \lor q \) となります。

「中間試験が60点以上」・「期末試験が60点以上」のどちらかを満たせば。\( p \lor q \) が正しいといえるので、で結果が1となっていることがわかりますね。

\( p \lor q \) の真理値表の書き方

(1) まず \( p \) が1のところは結果が1なので \( p \lor q \) に 1 を書きます。
(2) つぎに \( q \) が1のところも結果が1なので \( p \lor q \) に 1 を書きます。
(3) 残ったところが両方とも偽のところなので \( p \lor q \) に 0 を書きます。

これで書けます。みなさん試しにやってみてください！

(3) not演算 \( \lnot p \) (\( \overline{A} \))　

つぎに not 演算です。1つの変数 \( p \) の値が 0 (False) であれば 1 を、逆に 1 (True) であれば 0 (False) となります。真理値表を下に表示しておきます。

\( p \)	\( \lnot p \)
0	1
1	0

\( p \)	\( \lnot p \)
T	F
F	T

日本語で言うと、「私はうさぎだ！」という命題の否定は「私はうさぎではない。」となります。

このように、not演算は真偽を逆にする演算だということがわかりますね。

\( \lnot p \) の真理値表の書き方

(1) まず \( p \) が0のところは結果が1なので \( \lnot p \) に 1 を書きます。
(2) つぎに \( q \) が1のところは結果が0なので \( \lnot p \) に 0 を書きます。

(4) 含意 \( p \to q \)　

高校でもこの記号を見た方は多いと思います。「\( p \)ならば \( q \)」・「\( p \) は \( q \) の十分条件」・「\( q \) は \( p \) の十分条件」と読みます。

この式は \( p \) が真のときは \( q \) も真であるという意味を持ちます。下に真理値表を書きます。

\( p \)	\( q \)	\( p \land q \)
0	0	1
0	1	1
1	0	0
1	1	1

\( p \)	\( q \)	\( p \land q \)
T	T	T
T	F	F
F	T	T
F	F	T

式だけだとわかりにくいので、日本語でも説明したいとおもいます。例えば「工業大生である」を \( p \) とし、「男性である」を \( q \) とする。すると、\( p \to q \) は、桃山さんは「工業大生であるならば男性である」となる。

まず桃山さんが「工業大生」であるとする。もし桃山産「男性」なら日本語の文章を満たし、\( p \to q \) が真となるが、「女性」の場合は「工業大生であるが女性」となってしまい、反例となり命題を満たしません。よって \( (p,q) = (1,0) \) のときは \( p \to q \) は0となります。

一方桃山さんが「工業大生」でないとする。この場合は桃山さんが男性だろうが女性だろうが上の命題の反例とはなりません。このように前提 \( p \) が偽の場合は \( p \to q \) は \( q \) は常に真となります。

\( p \to q \) の真理値表の書き方

(1) まず \( p \) が0のところは結果が1なので \( p \to q \) に 1 を書きます。
(2) つぎに \( q \) が1のところは結果が1なので \( p \to q \) に 1 を書きます。
(3) 残ったところの \( p \to q \) に 0 を書きます。

これで書けます。

(5) xor演算 \( p \oplus q \) (\( A \oplus B \))　

別名「排他的論理和」といいます。離散分野ではあまり使いませんが、情報分野では頻出するので紹介しておきます。名前の通り \( p \) と \( q \) が両方等しい値のときは0となり、2つで違う値のときは1となります。こちらも真理値表をしめしておきます。

\( p \)	\( q \)	\( p \oplus q \)
0	0	0
0	1	1
1	0	1
1	1	0

\( p \)	\( q \)	\( p \oplus q \)
T	T	F
T	F	T
F	T	T
F	F	F

ちなみにカッコ( )で囲まれた式は優先的に計算をしてください（四則演算と同じ）。
論理演算の場合はカッコで計算順序が示されることが多いので and と or のどっちが先に計算されるか、などを考える必要は基本的にありません（厳密に言うと and が先で or が後に計算されます）。

スポンサードリンク

３．論理的同値

2つの論理式の真理値表のすべての場合の真偽において結果が一致するものは、論理的に同値ということができ、\( \equiv \) という記号で表します。例えば、\( p \to q \) と、\( \lnot p \lor q \) は論理的に同値です。下に真理値表で証明しておきます。

\( p \)	\( q \)	\( \lnot p \)	\( \lnot p \lor q \)	\( p \to q \)
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	0	1	1

真理値表を見てみると、\( p \) と \( q \) がどんな値（4パターン）であっても、結果の0と1は2つとも全部等しくなっていますよね。なのでこの2つの式は論理的に同値であると言えます。つまり、\( p \to q \equiv \lnot p \lor q \) となります。

もう1つ同値を証明してみましょう。 \( p \to q \) の対偶、つまり \( \lnot q \to \lnot p \) の真理値表も記します。

\( p \)	\( q \)	\( \lnot q \)	\( \lnot p \)	\( \lnot q \to \lnot p \)	\( p \to q \)
0	0	1	1	1	1
0	1	0	1	1	1
1	0	1	0	0	0
1	1	0	0	1	1

よって、\( p \to q \equiv \lnot q \to \lnot p \) となり、対偶も真になることがわかると思います。

論理的同値となるものの法則をいくつかあげてみます。
これらの法則をつかって論理的同値を示すのも良いですが、あまりおすすめしません。論理的同値使って示せと言われたときだけつかってください…。

(1) 可換則

\( A \lor B \equiv B \lor A \)

\( A \land B \equiv B \land A \)

どちらから計算しても計算結果は変わりません。日本語でも「大学生かつ男性」と「男性かつ大学生」の意味は変わりませんよね。

(2) 結合則

\( A \land (B \land C) \equiv (A \land B) \land C \)

\( A \lor (B \lor C) \equiv (A \lor B) \lor C \)

論理和同士、論理積同士はどこから計算しても計算結果は変わりません。

(3) 分配則

\( A \land (B \lor C) \equiv (A \land B) \lor (A \land C) \)

\( A \lor (B \land C) \equiv (A \lor B) \land (A \lor C) \)

このように分配をすることもできます。\( \lor, \land \) の記号より\( +,\times \) の記号で論理和、論理積を表したほうが直感的にいいかもしれません。

(4) 吸収則

\( A \land (A \lor B) \equiv A \)

\( A \lor (A \land B) \equiv A \)

(5) 相補則

\( A \land \lnot A \equiv 0 \)

\( A \lor \lnot A \equiv 1 \)

日本語に直したらすぐにわかります。「男性かつ男性じゃない人」なんていませんよね…。同じく「男性または男性じゃない人」と言ったら全員になっちゃいます。

(6) 同一則

\( A \land A \equiv A \)

\( A \lor A \equiv A \)

(7)

\( A \lor 1 \equiv 1 \)

\( A \lor 0 \equiv A \)

\( A \land 1 \equiv A \)

\( A \land 0 \equiv 0 \)

(8) 二重否定

\( \lnot \lnot A \equiv A \)

日本語の場合、二重否定は強調の意味があることがありますが、論理式ではただ打ち消されてもとの式に戻るだけです。

てなわけで例題を1つ解いてみましょう。

(9) ド・モルガン

\( \lnot(A \lor B) \equiv \lnot A \land \lnot B \)

\( \lnot(A \land B) \equiv \lnot A \lor \lnot B \)

集合でも成り立つのですが、論理式でもド・モルガンが成立します。
え、本当？　とおもった人は真理値表書いて証明してみてください。

例題1

論理式 (a) \( p \to (q \to r) \) (b) \( (p \lor r) \land (q \to r) \) (c) \( (p \land q) \to r \) がある。これについて、次に問いに答えなさい。

(1) (a),(b),(c) の真理値表を書きなさい。
(2) (a),(b),(c) から2つ同値な式を選びなさい。
(3) (2)で選んだ2つの論理式が同値なことを式変形を用いて示しなさい。
（真理値表は使わずに）

解答1

地道に真理値表を書いていきます。
今までは2つの変数 \( p,q \) だけだったので4パターンの列挙でよかったのですが、今回は \( p,q,r \) と3つの変数があるため、8パターンの列挙が必要となります。

(a) \( p \to (q \to r) \) の真理値表

\( p \)	\( q \)	\( r \)	\( q \to r \)	\( p \to (q \to r) \)
0	0	0	1	1
0	0	1	1	1
0	1	0	0	1
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	0	0
1	1	1	1	1

(b) \( (p \lor r) \land (q \to r) \) の真理値表

\( p \)	\( q \)	\( r \)	\( p \lor r \)	\( q \to r \)	\( (p \lor r) \land (q \to r) \)
0	0	0	0	1	0
0	0	1	1	1	1
0	1	0	0	0	0
0	1	1	1	1	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	1	0	0
1	1	1	1	1	1

\( p \)	\( q \)	\( r \)	\( p \land q \)	\( (p \land q) \to r \)
0	0	0	0	1
0	0	1	0	1
0	1	0	0	1
0	1	1	0	1
1	0	0	0	1
1	0	1	0	1
1	1	0	1	0
1	1	1	1	1

となる。

(2) 真理値表の色のついた部分より、同値なものは (a),(c) であることがわかる。
つまり、\( p \to (q \to r) \equiv(p \land q) \to r \) であることがわかる。

(3)

\( p \to (q \to r) \equiv p \to (\lnot q \lor r) \equiv \lnot p \lor (\lnot q \lor r) \equiv (\lnot p \lor \lnot q) \lor r \\ \equiv \lnot (p \land q) \lor r \equiv (p \land q) \to r \)

と示すことができる。

また、第1羽で学習した「商集合」の知識を用いて、論理的同値関係 \( \equiv \) による商集合を求めることもできる。これも例題でやってみよう。

例題2

集合 \( L \) をつぎのように定義する。

\( L = \{ (p \to q) \to (p \land r),(\lnot p \to r) \land (q \to r) , p \land (q \to r) , (p \to q) \to r \} \)

このとき、論理的同値関係 \( \equiv \) による集合 \( L \) の商集合 \( L/{\equiv} \) を求めなさい。

解答2

4つの論理式の真理値表をそれぞれ記す。

(1) \( (p \to q) \to (p \land r) \)

\( p \)	\( q \)	\( r \)	\( p \to q \)	\( p \land r \)	\( (p \to q) \to (p \land r) \)
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	1
1	0	1	0	1	1
1	1	0	1	0	0
1	1	1	1	1	1

(2) \( (\lnot p \to r) \land (q \to r) \)

\( p \)	\( q \)	\( r \)	\( \lnot p \)	\( \lnot p \to r \)	\( q \to r \)	\( (\lnot p \to r) \land (q \to r) \)
0	0	0	1	0	1	0
0	0	1	1	1	1	1
0	1	0	1	0	0	0
0	1	1	1	1	1	1
1	0	0	0	1	1	1
1	0	1	0	1	1	1
1	1	0	0	1	0	0
1	1	1	0	1	1	1

(3) \( p \land (q \to r) \)

\( p \)	\( q \)	\( r \)	\( q \land r \)	\( p \land (q \to r) \)
0	0	0	1	0
0	0	1	1	0
0	1	0	0	0
0	1	1	1	0
1	0	0	1	1
1	0	1	1	1
1	1	0	0	0
1	1	1	1	1

(4) \( (p \to q) \to r \)

\( p \)	\( q \)	\( r \)	\( p \to q \)	\( (p \to q) \to r \)
0	0	0	1	0
0	0	1	1	1
0	1	0	1	0
0	1	1	1	1
1	0	0	0	1
1	0	1	0	1
1	1	0	1	0
1	1	1	1	1

となる。（同値なものごとに色でわけています）

よって、\( (p \to q) \to (p \land r) \equiv p \land (q \to r) \) と \( (\lnot p \to r) \land (q \to r) \equiv (p \to q) \to r \) という同値関係が得られる。よって商集合 \( L/{\equiv} \) は、

\( L/{\equiv} = \{\{(p \to q) \to (p \land r),p \land (q \to r)\},\{(\lnot p \to r) \land (q \to r),(p \to q) \to r\}\} \)

となります。

おまけ

論理式変形でも同値なことを示してみます。

\( p \land (q \to r) \equiv p \land (\lnot q \lor r) \equiv (p \land \lnot q) \lor (p \land r) \equiv \lnot (\lnot p \lor q) \lor (p \land r) \\ \equiv \lnot(p \to q) \lor (p \land r) \equiv (p \to q) \to (p \land r) \)

\( (p \to q) \to r \equiv (\lnot p \lor q) \to r \equiv \lnot (\lnot p \lor q) \lor r \equiv (p \land \lnot q) \lor r \\ \equiv (p \lor r) \land (\lnot q \lor r) \equiv (p \lor r) \land (q \to r) \equiv (\lnot p \to r) \land (q \to r) \)

と示すことができます。しかし、このようにどの論理式が同値であるかがわからないときに変形で同値なものを見つけようとするのは絶対にやめてください。真理値表の場合は、8パターンすべて列挙すれば同値のものが見つかるし、ミスがあってもすぐに修正できますが、論理式の変形の場合はただ同値でないのかそれともミスなのかがわからないので真理値表で同値なものを探してください。