論理ろんりlogicと証明法しょうめいほうproof method 基本きほん演習えんしゅう

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

1対応たいおうする講義こうぎlecture

2Corresponding lectures講義こうぎ

3問題もんだい1：量化りょうかquantificationを否定ひていする

次つぎの命題めいだいpropositionの否定ひていを書かけ。

3.1解答かいとう

否定ひていは

である。

3.2解説かいせつ

全称量化ぜんしょうりょうかuniversal quantificationの否定ひていは存在量化そんざいりょうかexistential quantificationになる。また、含意がんいimplication $$P\Rightarrow Q$$P\Rightarrow Q の否定ひていは $$P\wedge \neg Q$$P\land\lnot Q である。

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

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

4.1Answer

The negation is

4.2Explanation

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

5問題もんだい2：包含ほうがんinclusionの推移性すいいせいtransitivityを示しめす

$$A\subseteq B$$A\subseteq B かつ $$B\subseteq C$$B\subseteq C のとき、$$A\subseteq C$$A\subseteq C を示しめせ。

5.1解答かいとう

任意にんいの $$x$$x を取とり、$$x\in A$$x\in A とする。$$A\subseteq B$$A\subseteq B より $$x\in B$$x\in B である。さらに $$B\subseteq C$$B\subseteq C より $$x\in C$$x\in C である。したがって $$x\in A\Rightarrow x\in C$$x\in A\Rightarrow x\in C が任意にんいの $$x$$x で成なり立たつので、$$A\subseteq C$$A\subseteq C である。

5.2解説かいせつ

これは直接証明ちょくせつしょうめいdirect proofである。包含関係ほうがんかんけいinclusion relationは、すべての元げんelementに対たいする含意がんいimplicationとして読よむ。

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

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

6.1Answer

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

6.2Explanation

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

7問題もんだい3：反例はんれいcounterexampleを作つくる

「任意にんいの関係かんけいrelationは対称たいしょうsymmetricである」という主張しゅちょうに反例はんれいcounterexampleを与あたえよ。

7.1解答かいとう

$$A=\{1,2\}$$A=\{1,2\} 上うえの関係かんけいrelation $$R=\left\{\right(1,2\left)\right\}$$R=\{(1,2)\} を考かんがえる。$$(1,2)\in R$$(1,2)\in R だが $$(2,1)\notin R$$(2,1)\notin R である。したがって $$R$$R は対称性たいしょうせいsymmetryを持もたない。

7.2解説かいせつ

反例はんれいcounterexampleでは、主張しゅちょうの対象たいしょうになっている条件じょうけんを満みたす例れいを作つくり、その結論けつろんが成なり立たたないことを示しめす。この問題もんだいでは $$R\subseteq A\times A$$R\subseteq A\times A なので、確たしかに $$A$$A 上うえの関係かんけいrelationである。

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

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

8.1Answer

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

8.2Explanation

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

9問題もんだい4：帰納法きのうほうinductionで示しめす

すべての $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$n\ge 1 について、

を示しめせ。

9.1解答かいとう

$$n=1$$n=1 のとき、左辺さへんは $$1$$1、右辺うへんは $$1·2/2=1$$1\cdot2/2=1 なので成なり立たつ。

$$n=k$$n=k で成なり立たつと仮定かていする。

このとき

である。したがって $$n=k+1$$n=k+1 でも成なり立たつ。

9.2解説かいせつ

基底段階きていだんかいbase caseと帰納段階きのうだんかいinduction stepを分わけて書かく。文字式もじしきで割わり算ざんが表あらわれるが、分母ぶんぼは定数ていすう $$2$$2 なので、零除算れいじょざんの確認かくにんは不要ふようである。

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

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

10.1Answer

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

Assume the statement holds for $$n=k$$n=k:

Then

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

10.2Explanation

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