論理ろんりと真理値表しんりちひょうの基本きほん

1導入どうにゅう

この講義こうぎでは、命題めいだいから複合命題ふくごうめいだいを構成こうせいする論理結合子ろんりけつごうしを定義ていぎし、真理値表しんりちひょうによって論理式ろんりしきの性質せいしつを判定はんていする方法ほうほうを説明せつめいする。特とくに、含意がんいの方向ほうこうと必要条件ひつようじょうけん・十分条件じゅうぶんじょうけんの対応たいおうを明確めいかくにする。

2命題めいだいと真理値しんりち

命題めいだいProposition とは、真しんまたは偽ぎのいずれかに確定かくていする平叙文へいじょぶんである。命題めいだいが真しんであることを $\mathrm{T}$\mathrm{T}、偽ぎであることを $\mathrm{F}$\mathrm{F} と表記ひょうきし、この $\mathrm{T}$\mathrm{T} または $\mathrm{F}$\mathrm{F} を真理値しんりちtruth valueという。疑問文ぎもんぶんや、変数へんすうの値あたいを指定していしなければ真偽しんぎが確定かくていしない文ぶんは、そのままでは命題めいだいではない。

3論理結合子ろんりけつごうし

$P,Q$P,Q を命題めいだいとする。

• 否定ひていnegation $\text{[PARSE ERROR: Undefined("Command("neg")")]}P$\neg P は、$P$P と反対はんたいの真理値しんりちをもつ。
• 論理積ろんりせきconjunction $P\wedge Q$P\land Q は、$P,Q$P,Q がともに真しんであるとき、かつそのときに限かぎり真しんである。
• 論理和ろんりわdisjunction $P\vee Q$P\lor Q は、$P,Q$P,Q の少すくなくとも一方いっぽうが真しんであるとき、かつそのときに限かぎり真しんである。したがって、ここでの「または」は両方りょうほうが真しんである場合ばあいも含ふくむ。
• 含意がんいimplication $P\to Q$P\to Q は、$P$P が真しんで $Q$Q が偽ぎである場合ばあいに限かぎり偽ぎである。$P$P を前件ぜんけん、$Q$Q を後件こうけんという。
• 同値どうちbiconditional $P\leftrightarrow Q$P\leftrightarrow Q は、$P,Q$P,Q の真理値しんりちが一致いっちするとき、かつそのときに限かぎり真しんである。

4真理値表しんりちひょう

真理値表しんりちひょうTruth table とは、構成要素こうせいようそとなる命題めいだいの真理値しんりちのすべての組合くみあわせについて、論理式ろんりしきの真理値しんりちを列挙れっきょした表ひょうである。二ふたつの命題めいだいからなる基本的きほんてきな論理式ろんりしきは、次つぎの表ひょうで定義ていぎされる。

$P\to Q$P\to Q について、前件ぜんけん $P$P が偽ぎである二ふたつの行ぎょうでは含意がんいは真しんである。これは、$P\to Q$P\to Q が因果関係いんがかんけいを主張しゅちょうする表現ひょうげんではなく、「$P$P が真しんなのに $Q$Q が偽ぎとなる反例はんれいは存在そんざいしない」という条件じょうけんだからである。

5恒真式こうしんしき・矛盾式むじゅんしき・論理同値ろんりどうち

恒真式こうしんしきTautology とは、構成要素こうせいようその真理値しんりちにかかわらず常つねに真しんとなる論理式ろんりしきである。矛盾式むじゅんしきContradiction とは、常つねに偽ぎとなる論理式ろんりしきである。たとえば、$P\vee \text{[PARSE ERROR: Undefined("Command("neg")")]}P$P\lor\neg P は恒真式こうしんしきであり、$P\wedge \text{[PARSE ERROR: Undefined("Command("neg")")]}P$P\land\neg P は矛盾式むじゅんしきである。

二ふたつの論理式ろんりしき $A,B$A,B が、すべての真理値しんりちの割当わりあてにおいて同一どういつの真理値しんりちをもつとき、$A$A と $B$B は論理同値ろんりどうちlogically equivalentであるといい、$A\equiv B$A\equiv B と表記ひょうきする。これは、$A\leftrightarrow B$A\leftrightarrow B が恒真式こうしんしきであることと同値どうちである。例れいとして、含意がんいは

と変形へんけいできる。

6含意がんいの方向ほうこうと必要十分条件ひつようじゅうぶんじょうけん

$P\to Q$P\to Q において、$P$P は $Q$Q の十分条件じゅうぶんじょうけんsufficient conditionであり、$Q$Q は $P$P の必要条件ひつようじょうけんnecessary conditionである。すなわち、$P$P の成立せいりつは $Q$Q の成立せいりつを保証ほしょうし、$P$P が成立せいりつするためには $Q$Q が必要ひつようである。

$Q\to P$Q\to P は $P\to Q$P\to Q の逆ぎゃくconverseであり、一般いっぱんには元もとの含意がんいから導出どうしゅつできない。これに対たいし、$\text{[PARSE ERROR: Undefined("Command("neg")")]}Q\to \text{[PARSE ERROR: Undefined("Command("neg")")]}P$\neg Q\to\neg P は対偶たいぐうcontrapositiveであり、

が成立せいりつする。変数へんすうを含ふくむ条件じょうけん $P\left(x\right),Q\left(x\right)$P(x),Q(x) について、考察対象こうさつたいしょうのすべての $$x$$x で $P\left(x\right)\to Q\left(x\right)$P(x)\to Q(x) と $Q\left(x\right)\to P\left(x\right)$Q(x)\to P(x) が成立せいりつするとき、$P\left(x\right)\leftrightarrow Q\left(x\right)$P(x)\leftrightarrow Q(x) が恒真こうしんとなり、$P\left(x\right)$P(x) は $Q\left(x\right)$Q(x) の必要十分条件ひつようじゅうぶんじょうけんnecessary and sufficient conditionである。単一たんいつの真理値割当しんりちわりあてで二ふたつの含意がんいがともに真しんであることだけでは、この関係かんけいは導出どうしゅつできない。

7例れい

整数せいすう $$n$$n に対たいし、$P\left(n\right)$P(n) を「$$n$$n は 4 の倍数ばいすうである」、$Q\left(n\right)$Q(n) を「$$n$$n は偶数ぐうすうである」とする。$P\left(n\right),Q\left(n\right)$P(n),Q(n) は $$n$$n を指定していするまで命題めいだいではなく、整数せいすうを真理値しんりちへ対応たいおうさせる述語じゅつごpredicateである。すべての整数せいすう $$n$$n について $P\left(n\right)\to Q\left(n\right)$P(n)\to Q(n) が成立せいりつするため、「4 の倍数ばいすうであること」は「偶数ぐうすうであること」の十分条件じゅうぶんじょうけんである。一方いっぽう、$Q\left(2\right)$Q(2) は真しんで $P\left(2\right)$P(2) は偽ぎであるため、$$n=2$$n=2 は $Q\left(n\right)\to P\left(n\right)$Q(n)\to P(n) の反例はんれいである。

8要点ようてん

• 論理結合子ろんりけつごうしの意味いみは、自然言語しぜんげんごの印象いんしょうではなく真理値表しんりちひょうによって確定かくていする。
• 恒真式こうしんしきと矛盾式むじゅんしきは、それぞれすべての行ぎょうが真しんまたは偽ぎとなる論理式ろんりしきである。
• 論理同値ろんりどうちは、すべての真理値しんりちの割当わりあてにおける一致いっちを意味いみする。
• $P\to Q$P\to Q では $P$P が十分条件じゅうぶんじょうけん、$Q$Q が必要条件ひつようじょうけんであり、逆ぎゃくと対偶たいぐうを混同こんどうしてはならない。

9関連かんれんリンク