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

P∨(Q∧R)⊢(P∨Q)∧(P∨R)

P∨(Q∧R)

P

(P∨Q)

(P∨R)

(P∨Q)∧(P∨R)

(Q∧R)

(P∨Q)

(P∨R)

(P∨Q)∧(P∨R)

(P∨Q)∧(P∨R)

(P∨Q)∧(P∨R)⊢P∨(Q∧R)

1 (P∨Q)∧(P∨R) 前提

1 (P∨Q)

3 P

3 P∨(Q∧R)

5 Q

1 P∨R

7 P

7 P∨(Q∧R)

9 R

5,9 Q∧R

5,9 P∨(Q∧R)

1,9 P∨(Q∧R) 2,3-4,5-11,∨除去

1 P∨(Q∧R) 6,7-8,9-12,∨除去

否定の導入

i A

…,i

…,i ⊥

… A→⊥

… ¬A否定の導入

否定の導入と背理法は違う

直観主義論理では否定の導入はできるけど、背理法はできない

最初は違いわかりにくいところよね〜

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,¬導入

⊢¬(P∧¬P)

1 (P∧¬P) 仮定

1 P 1,∧除去

1 ¬P 1,∧除去

1 ⊥ 2,3,¬除去

¬(P∧¬P) 1-4,¬導入

⊢P→¬¬P

二重否定導入だ！熱い！

でも二重否定除去は最小論理ではできないですねー

1 P 仮定

2 ¬P 仮定

1,2 ⊥ 1,2,¬除去

1 ¬¬P 1-3,¬導入

P→¬¬P 1-4,→導入

¬(P∨Q)⊢¬(P∧Q)

(P∧Q)→(P∨Q)の双対じゃん！最小論理でも成り立つんだなぁ熱い！

1 ¬(P∨Q) 前提

2 (P∧Q) 仮定

2 P 2,∧除去

2 P∨Q 3,∨導入

1,2 ⊥ 1-4,¬除去

1 ¬(P∧Q) 5,¬導入

⊢(P→Q)→(¬Q→¬P)

元の命題が成り立つならば、対偶も成り立つってことだ！熱い！！

⊢(¬Q→¬P)→(P→Q)はまだ証明できないよ(最小論理ではね)

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,→導入

(P→Q)→(¬Q→¬P) 1-7,→導入

最小論理(∧,∨,¬,→の推論規則が使える論理)

⊢¬¬(A∨¬A)

証明可能

⊢(A∨¬A)

証明できない

DN規則(二重否定除去)があれば証明できるようになる

それが古典論理

例題4は飛ばします

爆発律じゃん

別に証明してもよくない？。ちょっとややこしい感じもするけどそこまでじゃない？

P∨Q,¬P⊢Q

1 P∨Q 前提

2 ¬P 前提

3 P 仮定

2,3 Q 2,3爆発律

5 Q 仮定

1 Q 1,3-5 ∨除去

1 P∨Q 前提

2 ¬P 前提

3 ¬Q 仮定

4 P 仮定

2,4 ⊥ 2,4,除去

6 Q 仮定

3,6 ⊥ 3,6,¬除去

1,2 ⊥ 1,4-5,6-7,∨除去

1,2 ¬¬Q 3-8,¬導入

1,2 Q 9,DN規則

⊢¬¬P→P

1 ¬¬P 仮定

1 P 1,DN規則

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

P→S,Q→¬S⊢¬(P∧Q)

1 P→S 前提

2 Q→¬S 前提

3 (P∧Q) 仮定

3 P 3,∧除去

3 Q 3,∧除去

1,3 S 1,4,→除去

2,3 ¬S 2,5,→除去

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

1,2 ¬(P∧Q) 3-8,¬導入

選言的三段論法から爆発律を

爆発律から選言的三段論法を最小論理上で導けるかな？

選言的三段論法(A∨B,¬A⊢B)から爆発律(⊥⊢A)

⊥ をC∧¬C の略記とする

1 C∧¬C 前提

1 C 1,∧除去

1 C∨A 2,∨導入

1 ¬C 1,∧除去

1 A 3,4,選言的三段論法

爆発律(⊥⊢A)から選言的三段論法(A∨B,¬A⊢B)

1 A∨B 前提

2 ¬A 前提

3 A 仮定

2,3 ⊥ 2,3,¬除去

2,3 B 4,爆発律

6 B 仮定

1,2 B 1,3-5,6,∨除去