Logic論理ろんり and proof methods証明法しょうめいほう: basic exercises

document_iddoc_e5b67ffb45f07185379a145613a42e68title論理と証明法基本演習type問題演習content_typeexercisedate2026-07-14categorymathdescription命題、述語、量化、否定、直接証明、対偶証明、反例の基本演習。prerequisites命題・述語と量化 / 証明法と反例 / 数学的帰納法と再帰的定義

1Corresponding lectures講義こうぎ

data/lecture/math/discrete-math/propositions-predicates-and-quantifiers.lecture.n.md data/lecture/math/discrete-math/proof-methods-and-counterexamples.lecture.n.md data/lecture/math/discrete-math/mathematical-induction-and-recursive-definitions.lecture.n.md

2Problem 1: negate quantification量化りょうか

Write the negation of the following proposition命題めいだい.

\forall x \in A, P (x) \Rightarrow Q (x)

2.1Answer

The negation is

\exists x \in A suchthat P (x) and \neg Q (x) .

2.2Explanation

The negation of universal quantification全称量化ぜんしょうりょうか becomes existential quantification存在量化そんざいりょうか. Also, the negation of the implication含意がんい $P \Rightarrow Q$ is $P \land \neg Q$ .

3Problem 2: prove transitivity推移性すいいせい of inclusion包含ほうがん

Assume $A \subseteq B$ and $B \subseteq C$ . Prove $A \subseteq C$ .

3.1Answer

Take arbitrary $x$ and assume $x \in A$ . Since $A \subseteq B$ , we have $x \in B$ . Since $B \subseteq C$ , we have $x \in C$ . Thus $x \in A \Rightarrow x \in C$ holds for every $x$ , so $A \subseteq C$ .

3.2Explanation

This is a direct proof直接証明ちょくせつしょうめい. An inclusion relation包含関係ほうがんかんけい is read as an implication含意がんい about every element元げん.

4Problem 3: construct a counterexample反例はんれい

Give a counterexample反例はんれい to the claim “every relation関係かんけい is symmetric対称たいしょう.”

4.1Answer

Consider the relation関係かんけい $R = {(1, 2)}$ on $A = {1, 2}$ . We have $(1, 2) \in R$ but $(2, 1) \notin R$ . Therefore $R$ does not have symmetry対称性たいしょうせい.

4.2Explanation

A counterexample反例はんれい must satisfy the assumptions of the claim and make the conclusion fail. Here $R \subseteq A \times A$ , so it really is a relation関係かんけい on $A$ .

5Problem 4: prove by induction帰納法きのうほう

Prove that for every $n [PARSE ERROR: Undefined("Command(\"ge\")")] 1$ ,

1 + 2 + \dots + n = \frac{n (n + 1)}{2} .

5.1Answer

For $n = 1$ , the left-hand side is $1$ and the right-hand side is $1 \cdot 2 / 2 = 1$ , so the statement holds.

Assume the statement holds for $n = k$ :

1 + 2 + \dots + k = \frac{k (k + 1)}{2} .

Then

1 + 2 + \dots + k + (k + 1) = \frac{k (k + 1)}{2} + (k + 1) = \frac{(k + 1) (k + 2)}{2} .

Thus the statement also holds for $n = k + 1$ .

5.2Explanation

Write the base case基底段階きていだんかい and the induction step帰納段階きのうだんかい separately. Division appears in the algebraic expression, but the denominator is the constant $2$ , so there is no zero-division issue to check.