思考の論理入門の授業メモ12

p91

問題1

P,P→Q,¬R→¬Q⊢¬(P→¬R)

1 P 前提

2 P→Q 前提

3 ¬R→¬Q 前提

4 P→¬R 仮定

1,4 ¬R 1,4,→除去

1,3,4 ¬Q 3,5,→除去

1,3 Q 1,2,→除去

1,2,3,4 ⊥ 6,7,¬除去

1,2,3 ¬(P→¬R) 4-8,¬導入

P∨(Q→R),Q⊢P∨R

1 P∨(Q→R) 前提

2 Q 前提

3 P 仮定

3 P∨R 3,∨導入

5 Q→R 仮定

2,5 R 2,5,→除去

2,5 P∨R 6,∨導入

1,2 P∨R 1,3-4,5-7,∨除去

R→¬P,Q→(P∨¬S),Q⊢S→¬R

1 R→¬P 前提

2 Q→(P∨¬S) 前提

3 Q 前提

4 S 仮定

5 R 仮定

2,3 P∨¬S 2,3,→除去

7 P 仮定

1,5 ¬P 1,5,→除去

1,5,7 ⊥ 7,8¬除去

10 ¬S 仮定

4,10 ⊥ 4,10,¬除去

1,2,3,4,5 ⊥ 6,7-9,10-11,¬除去

1,2,3 ¬R 5-12,¬導入

1,2,3 S→¬R 4-13,→導入

P→Q,¬P→Q⊢Q

1 P→Q 前提

2 ¬P→Q 前提

3 ¬Q 仮定

4 P 仮定

1,4 Q 1,4,→除去

1,3,4 ⊥ 3,5,¬除去

1,3 ¬P 4-6,¬導入

1,2,3 Q 2,7,→除去

1,2,3 ⊥ 3,8,¬除去

1,2 ¬¬Q 3-9,¬除去

1,2 Q 10,DN規則

P→Q⊢¬Q→¬P

1 P→Q 前提

2 ¬Q 仮定

3 P 仮定

1,3 Q 1,3,→除去

1,2,3 ⊥ 2,4,¬除去

1.2 ¬P 3-5,¬導入

1 ¬Q→¬P 2-6,→導入

A⇄B := (A→B)∧(B→A)

Aのとき、かつそのときに限りBである

AならばBである

Aのときに限ってBである

¬A→¬B

つまりB→A

if and only if

iff

教科書p92

補助規則def.

A⇄B と(A→B)∧(B→A)

definition

問題2

P⇄Q⊢Q⇄P

1 P⇄Q 前提

1 (P→Q)∧(Q→P) 1.def.⇄

1 P→Q 2.∧除去

1 Q→P 2.∧除去

1 (Q→P)∧(P→Q) 3,4.∧導入

1 Q⇄P 5.def.⇄

P→Q,Q→R,R→P⊢P⇄Q

1 P→Q 前提

2 Q→R 前提

3 R→P 前提

4 Q 仮定

2,4 R 2,4.→除去

2,3,4 P 3,5.→除去

2,3 Q→P 4-6.→導入

1,2,3 (P→Q)∧(Q→P) 1,7.∧導入

1,2,3 P⇄Q 8.def.⇄

演習1

P⇄¬¬P

1 P 仮定

2 ¬P 仮定

1,2 ⊥ 1,2.¬除去

1 ¬¬P 2-3.¬導入

P→¬¬P 1-4.導入

6 ¬¬P 仮定

6 P 6.DN規則

¬¬P→P 6-7.→導入

(P→¬¬P)∧(¬¬P→P) 5,8.∧導入

P⇄¬¬P 9.def.⇄

めんどくさいから依存関係ちゃんと書いてない……

まあ読めるよね(未来の僕へ)

¬(P∨Q)⇄(¬P∧¬Q)

1 ¬(P∨Q) 仮定

2 P 仮定

P∨Q

⊥

¬P

Q 仮定

P∨Q

¬Q

¬(P∨Q)→(¬P∧¬Q)

(¬P∧¬Q)仮定

P∨Q 仮定

P

¬P

⊥

Q

¬Q

⊥

⊥

¬(P∨Q)

(¬P∧¬Q)→¬(P∨Q)

¬(P∨Q)→(¬P∧¬Q)∧(¬P∧¬Q)→¬(P∨Q)

¬(P∨Q)⇄(¬P∧¬Q) def.⇄

問題の3,4も冬休みで解いてきてね〜

¬(P∧Q)⇄(¬P∨¬Q)

¬(P∧Q) 仮定

¬(¬P∨¬Q) 仮定

P 仮定

Q 仮定

P∧Q 3,4

⊥ 1,5

1,4 ¬P 3-6¬導入

¬P∨¬Q

1,2,4 ⊥

1,2 ¬Q 4-9 ¬導入

¬P∨¬Q

1,2 ⊥

1 ¬¬(¬P∨¬Q)

1 (¬P∨¬Q)

¬(P∧Q)→(¬P∨¬Q)

¬P∨¬Q 仮定

P∧Q 仮定

¬P仮定

P

⊥

¬Q仮定

Q

⊥

⊥

¬(P∧Q)

(¬P∨¬Q)→¬(P∧Q)

¬(P∧Q)→(¬P∨¬Q)∧(¬P∨¬Q)→¬(P∧Q)

¬(P∧Q)⇄(¬P∨¬Q) def.⇄

(P∨Q)⇄¬(¬P∧¬Q)

P∨Q 仮定

¬P∧¬Q 仮定

P 仮定

¬P

⊥

Q 仮定

¬Q

⊥

⊥

¬(¬P∧¬Q)

(P∨Q)→¬(¬P∧¬Q)

¬(¬P∧¬Q) 仮定

¬(P∨Q) 仮定

P 仮定

P∨Q

⊥

¬P

Q 仮定

P∨Q

⊥

¬Q

¬P∨¬Q

⊥

¬¬(P∨Q)

(P∨Q) DN規則

¬(¬P∧¬Q)→(P∨Q)

(P∨Q)→¬(¬P∧¬Q)∧¬(¬P∧¬Q)→(P∨Q)

(P∨Q)⇄¬(¬P∧¬Q)

(P→(Q→R))⇄((P∧Q)→R)

(P→(Q→R)) 仮定

(P∧Q) 仮定

P

Q→ R

R

((P∧Q)→R)

(P→(Q→R))→((P∧Q)→R)

((P∧Q)→R) 仮定

P 仮定

Q 仮定

(P∧Q)

R

(Q→R)

(P→(Q→R))

((P∧Q)→R)→(P→(Q→R))

(P→(Q→R))→((P∧Q)→R)∧((P∧Q)→R)→(P→(Q→R))

(P→(Q→R))⇄((P∧Q)→R)

(P∧Q)⇄(Q∧P)

P∧Q 仮定

P

Q

Q∧P

(P∧Q)→(Q∧P)

(Q∧P) 仮定

Q

P

(P∧Q)

(Q∧P)→(P∧Q)

(P∧Q)→(Q∧P)∧(Q∧P)→(P∧Q)

(P∧Q)⇄(Q∧P)

(P∨Q)⇄(Q∨P)

(P∨Q) 仮定

P 仮定

(Q∨P)

Q 仮定

(Q∨P)

(Q∨P)

(P∨Q)→(Q∨P)

(Q∨P) 仮定

Q 仮定

(P∨Q)

P 仮定

(P∨Q)

(P∨Q)

(Q∨P)→(P∨Q)

(P∨Q)⇄(Q∨P)