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

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関連かんれんリンク

Logic and Truth Tables: Fundamentals

1Introduction

This lecture defines the logical connectives used to construct compound propositions and explains how truth tables determine properties of logical formulas. In particular, it clarifies the direction of implication and the roles of necessary and sufficient conditions.

2Propositions and Truth Values

A {proposition} is a declarative sentence that has exactly one of the two truth values: true or false. We write $\mathrm{T}$\mathrm{T} when a proposition is true and $\mathrm{F}$\mathrm{F} when it is false. A question, or a sentence whose truth cannot be determined until a variable is specified, is not itself a proposition.

3Logical Connectives

Let $P$P and $Q$Q be propositions.

• The {negation} $\text{[PARSE ERROR: Undefined("Command("neg")")]}P$\neg P has the truth value opposite to that of $P$P.
• The {conjunction} $P\wedge Q$P\land Q is true if and only if both $P$P and $Q$Q are true.
• The {disjunction} $P\vee Q$P\lor Q is true if and only if at least one of $P$P and $Q$Q is true. Thus, this inclusive “or” includes the case in which both propositions are true.
• The {implication} $P\to Q$P\to Q is false if and only if $P$P is true and $Q$Q is false. We call $P$P the antecedent and $Q$Q the consequent.
• The {biconditional} $P\leftrightarrow Q$P\leftrightarrow Q is true if and only if $P$P and $Q$Q have the same truth value.

4Truth Tables

A {truth table} lists the truth value of a logical formula for every assignment of truth values to its component propositions. The basic formulas involving two propositions are defined by the following table.

For $P\to Q$P\to Q, the implication is true in both rows in which the antecedent $P$P is false. This convention reflects that $P\to Q$P\to Q is not an assertion of causation; instead, it states that there is no counterexample in which $P$P is true while $Q$Q is false.

5Tautologies, Contradictions, and Logical Equivalence

A {tautology} is a formula that is true under every assignment of truth values. A {contradiction} is a formula that is false under every assignment. For example, $P\vee \text{[PARSE ERROR: Undefined("Command("neg")")]}P$P\lor\neg P is a tautology, whereas $P\wedge \text{[PARSE ERROR: Undefined("Command("neg")")]}P$P\land\neg P is a contradiction.

Two formulas $A$A and $B$B are {logically equivalent}, written $A\equiv B$A\equiv B, if they have the same truth value under every assignment. Equivalently, $A\leftrightarrow B$A\leftrightarrow B is a tautology. For example, implication satisfies

6Direction of Implication and Necessary and Sufficient Conditions

In $P\to Q$P\to Q, $P$P is a {sufficient condition} for $Q$Q, and $Q$Q is a {necessary condition} for $P$P. That is, the truth of $P$P guarantees the truth of $Q$Q, and $Q$Q must be true whenever $P$P is true.

The statement $Q\to P$Q\to P is the {converse} of $P\to Q$P\to Q and, in general, does not follow from the original implication. In contrast, $\text{[PARSE ERROR: Undefined("Command("neg")")]}Q\to \text{[PARSE ERROR: Undefined("Command("neg")")]}P$\neg Q\to\neg P is its {contrapositive}, and

For conditions $P\left(x\right)$P(x) and $Q\left(x\right)$Q(x) containing a variable, if both $P\left(x\right)\to Q\left(x\right)$P(x)\to Q(x) and $Q\left(x\right)\to P\left(x\right)$Q(x)\to P(x) hold for every object $$x$$x under consideration, then $P\left(x\right)\leftrightarrow Q\left(x\right)$P(x)\leftrightarrow Q(x) is a tautology, and $P\left(x\right)$P(x) is a {necessary and sufficient condition} for $Q\left(x\right)$Q(x). The fact that both implications are true under one particular truth-value assignment does not establish this relationship.

7Example

For an integer $$n$$n, let $P\left(n\right)$P(n) mean “$$n$$n is divisible by 4,” and let $Q\left(n\right)$Q(n) mean “$$n$$n is even.” Until $$n$$n is specified, $P\left(n\right)$P(n) and $Q\left(n\right)$Q(n) are not propositions; they are {predicates} that assign truth values to integers. The implication $P\left(n\right)\to Q\left(n\right)$P(n)\to Q(n) holds for every integer $$n$$n, so divisibility by 4 is sufficient for being even. In contrast, $Q\left(2\right)$Q(2) is true and $P\left(2\right)$P(2) is false, so $$n=2$$n=2 is a counterexample to $Q\left(n\right)\to P\left(n\right)$Q(n)\to P(n).

8Key Points

• The meanings of logical connectives are determined by truth tables, not by informal impressions of natural-language expressions.
• A tautology is true in every row of its truth table, whereas a contradiction is false in every row.
• Logical equivalence means agreement under every assignment of truth values.
• In $P\to Q$P\to Q, $P$P is sufficient and $Q$Q is necessary; the converse must not be confused with the contrapositive.

9Related Links