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

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

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

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量化りょうか.

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存在量化そんざいりょうか.

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.

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存在量化そんざいりょうか.

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

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.

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写像しゃぞう.