命題めいだいproposition・述語じゅつごpredicateと量化りょうかquantification

document_iddoc_d3754eaff4287068e2708202c25cd9a8title命題・述語と量化講義type講義content_typelecturedate2026-07-14categorymathdescription離散数学で集合・関係・写像を正しく扱うために必要な命題、述語、量化、含意、同値、否定の基本を説明する。

離散数学りさんすうがくdiscrete mathematicsで最初さいしょに固定こていしたいのは、「何なにについて述のべている文ぶんなのか」を曖昧あいまいにしないことである。集合しゅうごうset、関係かんけいrelation、写像しゃぞうmapは、どれも「ある対象たいしょうが条件じょうけんを満みたすか」を材料ざいりょうにして作つくられる。したがって、命題めいだいpropositionと述語じゅつごpredicateを先さきに整理せいりしておくと、後あとの定義ていぎが自然しぜんに読よめる。

data/lecture/math/discrete-math/proof-methods-and-counterexamples.lecture.n.md

1命題めいだいpropositionとは何なにか

命題めいだいpropositionとは、真しんか偽ぎかが定さだまる文ぶんである。

2 + 3 = 5

は真しんである。一方いっぽう、

x + 3 = 5

は、 $x$ を決きめなければ真偽しんぎが定さだまらない。そのため、これは $x$ についての述語じゅつごpredicateである。

述語じゅつごpredicateは、対象たいしょうを入いれると命題めいだいpropositionになる文ぶんである。たとえば $P (x) : x は偶数である$ とおけば、 $P (2)$ は真しんで、 $P (3)$ は偽ぎである。

命題めいだいpropositionは真しんか偽ぎが決きまる文ぶんであり、自由変数じゆうへんすうが残のこる文ぶんは述語じゅつごpredicateとして扱あつかう。述語じゅつごpredicateは、値あたいを代入だいにゅうするか量化りょうかquantificationすると命題めいだいになる。

2真理集合しんりしゅうごうtruth setとして読よむ

この節せつは次つぎの集合しゅうごう講義こうぎを先取さきどりする。ここでは集合しゅうごうsetを対象たいしょうの集あつまり、元げんelementをそこに含ふくまれる対象たいしょう、全体集合ぜんたいしゅうごうuniversal setを議論ぎろんの対象たいしょう全体ぜんたいを収おさめる集合しゅうごうと読よむ。

述語じゅつごpredicateを集合しゅうごうsetと結むすびつける見方みかたが重要じゅうようである。全体集合ぜんたいしゅうごうuniversal setを $U$ とし、述語じゅつご $P (x)$ を考かんがえる。このとき

{x \in U ∣ P (x)}

は、 $P (x)$ を真しんにする元げんelement全体ぜんたいの集合しゅうごうsetである。この集合しゅうごうsetを真理集合しんりしゅうごうtruth setと呼よぶ。

直感的ちょっかんてきには、述語じゅつごpredicateは「ふるい」であり、真理集合しんりしゅうごうtruth setはそのふるいを通過つうかした対象たいしょうの集あつまりである。

真理集合しんりしゅうごうtruth setは、対象たいしょうとして許ゆるす領域りょういきdomainに依存いぞんする。同おなじ式しきでも領域りょういきを変かえると、真理集合しんりしゅうごうや全称量化ぜんしょうりょうかuniversal quantification・存在量化そんざいりょうかexistential quantificationの真偽しんぎが変かわることがある。

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

命題めいだいpropositionから新あたらしい命題めいだいpropositionを作つくる操作そうさを論理結合子ろんりけつごうしlogical connectiveという。

記号きごう	読よみ	意味いみ
$P \land Q$	かつ	$P$ も $Q$ も真しん
$P \lor Q$	または	少すくなくとも一方いっぽうが真しん
$\neg P$	でない	$P$ の真偽しんぎを反転はんてんする
$P \Rightarrow Q$	ならば	$P$ が真しんなら $Q$ も真しん
$P \Leftrightarrow Q$	同値どうち	$P$ と $Q$ の真偽しんぎが一致いっちする

含意がんいimplication $P \Rightarrow Q$ は「 $P$ が真しんである状況じょうきょうでは $Q$ も真しんである」という主張しゅちょうである。

4全称量化ぜんしょうりょうかuniversal quantificationと存在量化そんざいりょうかexistential quantification

量化りょうかquantificationは、変数へんすうの範囲はんいを指定していして命題めいだいを作つくる操作そうさである。

\forall x \in A, P (x)

は「 $A$ のすべての $x$ について $P (x)$ が成立せいりつする」という意味いみである。これを全称量化ぜんしょうりょうかuniversal quantificationという。

\exists x \in A, P (x)

は「 $A$ の中なかに $P (x)$ を満みたす $x$ が少すくなくとも 1 つ存在そんざいする」という意味いみである。これを存在量化そんざいりょうかexistential quantificationという。

5否定ひていは量化りょうかの外そとに出だす

量化りょうかを含ふくむ命題めいだいを否定ひていするときは、量化りょうか記号きごうが入いれ替かわる。

\neg (\forall x \in A, P (x)) \Leftrightarrow \exists x \in A suchthat \neg P (x)

\neg (\exists x \in A, P (x)) \Leftrightarrow \forall x \in A, \neg P (x)

「すべてが成立せいりつする」の否定ひていは「少すくなくとも 1 つ反例はんれいがある」である。「条件じょうけんを満みたすものが存在そんざいする」の否定ひていは「どの候補こうほもその条件じょうけんを満みたさない」である。

data/lecture/math/discrete-math/proof-methods-and-counterexamples.lecture.n.md

6具体例ぐたいれい：包含関係ほうがんかんけいinclusion relationを論理ろんりで読よむ

$A \subseteq B$ は次つぎの命題めいだいである。

\forall x, x \in A \Rightarrow x \in B

したがって、 $A \subseteq B$ を否定ひていすると、

\exists x suchthat x \in A and x \notin B

となる。つまり、 $A$ に属ぞくするが $B$ には属ぞくさない元げんelementが 1 つでも見みつかれば、包含ほうがんは壊こわれる。

7演習えんしゅうリンクとまとめ

data/exercise/math/discrete-math/logic-and-proof-methods.exercise.n.md

命題めいだいpropositionは真偽しんぎが定さだまる文ぶんであり、述語じゅつごpredicateは対象たいしょうを入いれると命題めいだいpropositionになる文ぶんである。量化りょうかquantificationは変数へんすうの範囲はんいを固定こていする操作そうさであり、集合しゅうごうset、関係かんけいrelation、写像しゃぞうmapの定義ていぎを支ささえる。