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

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

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

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

2.1解答かいとう

否定ひていは

である。

2.2解説かいせつ

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

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

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

3.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 である。

3.2解説かいせつ

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

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

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

4.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を持もたない。

4.2解説かいせつ

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

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

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

を示しめせ。

5.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 でも成立せいりつする。

5.2解説かいせつ

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