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

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

Propositions命題めいだい, predicates述語じゅつご, and quantification量化りょうか

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

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

In discrete mathematics離散数学りさんすうがく, the first thing to fix is what a statement is about. Sets集合しゅうごう, relations関係かんけい, and maps写像しゃぞう are all built from conditions on objects. Therefore organizing propositions命題めいだい and predicates述語じゅつご first makes later definitions easier to read.

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すると命題めいだいになる。

1What is a proposition命題めいだい?

A proposition命題めいだい is a statement whose truth value is determined.

2 + 3 = 5

is true. In contrast,

x + 3 = 5

does not have a truth value until $x$ is specified. Therefore it is a predicate述語じゅつご about $x$ .

A predicate is a statement that becomes a proposition after an object is inserted. For example, if $P (x) : x iseven$ , then $P (2)$ is true and $P (3)$ is false.

A proposition is a statement whose truth value is fixed. A statement with a remaining free variable is treated as a predicate述語じゅつご. A predicate becomes a proposition after a value is substituted or after it is quantified量化りょうか.

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の真偽しんぎが変かわることがある。

2Reading a predicate as a truth set真理集合しんりしゅうごう

This section previews the next lecture on sets. Here a set集合しゅうごう is a collection of objects, an element元げん is an object in that collection, and a universal set全体集合ぜんたいしゅうごう contains all objects currently under discussion.

It is important to connect a predicate述語じゅつご with a set集合しゅうごう. Fix a universal set全体集合ぜんたいしゅうごう $U$ and consider a predicate $P (x)$ . Then

{x \in U ∣ P (x)}

is the set of all elements元げん that make $P (x)$ true. This set is called the truth set真理集合しんりしゅうごう.

Intuitively, a predicate is a filter, and the truth set is the collection of objects that pass through the filter.

A truth set真理集合しんりしゅうごう depends on the domain領域りょういき of objects being allowed. Even with the same formula, changing the domain can change the truth set and the truth value of universal quantification全称量化ぜんしょうりょうか or 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$ も真しんである」という主張しゅちょうである。

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

Operations that build new propositions命題めいだい from propositions are called logical connectives論理結合子ろんりけつごうし.

Symbol	Reading	Meaning
$P \land Q$	and	both $P$ and $Q$ are true
$P \lor Q$	or	at least one of $P, Q$ is true
$\neg P$	not	reverses the truth value of $P$
$P \Rightarrow Q$	implies	if $P$ is true, then $Q$ is true
$P \Leftrightarrow Q$	equivalent	$P$ and $Q$ have the same truth value

The implication含意がんい $P \Rightarrow Q$ asserts that whenever $P$ is true, $Q$ is also true.

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という。

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

Quantification量化りょうか creates a proposition by specifying the range of a variable.

\forall x \in A, P (x)

means that $P (x)$ holds for every $x$ in $A$ . This is universal quantification全称量化ぜんしょうりょうか.

\exists x \in A, P (x)

means that there is at least one $x$ in $A$ satisfying $P (x)$ . This is 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

5Move negation outside quantifiers

When negating a proposition with quantifiers, the quantifier switches.

\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) .

The negation of “everything holds” is “there is at least one counterexample反例はんれい.” The negation of “there exists” is “every candidate fails.”

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 つでも見みつかれば、包含ほうがんは壊こわれる。

6Example: read an inclusion relation包含関係ほうがんかんけい logically

The statement $A \subseteq B$ means

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

Therefore the negation of $A \subseteq B$ is

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

Thus a single element元げん that belongs to $A$ but not to $B$ breaks the inclusion.

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

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

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

7Exercise link and summary

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

A proposition命題めいだい has a truth value, and a predicate述語じゅつご becomes a proposition after an object is inserted. Quantification量化りょうか fixes the range of a variable and supports the definitions of sets集合しゅうごう, relations関係かんけい, and maps写像しゃぞう.