(01)
排中律や二重否定の除去と等価な命題のひとつで、変なものとして、パースの法則があります。
任意の命題P, Qについて、
((P→Q)→P)→P
が成り立つ
『「PならばQ」ならばP』ならばP
なんか、パズルのような命題ですね。
(排中律、二重否定の除去、パースの法則 - Qiita)
(02)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
(c)├((P→Q)→P)→P
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、80頁と、原文)
cf.
ただし、「E.J.レモン、論理学初歩」には、「練習問題の解答」は、載ってゐません。
然るに、
(03)
(ⅰ)
1 (1) (P→ Q)→P A
1 (2) ~(P→ Q)∨P 1含意の定義
3 (3) ~(P→ Q) A
4 (4) ~P∨ Q A
4 (5) P→ Q 3含意の定義
34 (6) ~(P→ Q)&
(P→ Q) 5&I
3 (7)~(~P∨ Q) 46RAA
3 (8) P&~Q 7ド・モルガンの法則
3 (9) P 8&I
ア(ア) P A
1 (イ) P 239アア∨E
(ウ) ((P→Q)→P)→P 1イCP
(〃)((PならばQ)ならばP)ならばP。
(ⅱ)
(1) ~P∨P TI(排中律)
2 (2) ~P A
2 (3) ~P∨Q 2∨I
2 (4) P→Q 2含意の定義
2 (5) (P→Q)&~P 24&I
2 (6)~(~(P→Q)∨ P) 5ド・モルガンの法則
9 (7) (P→Q)→ P A
9 (8) ~(P→Q)∨ P 7含意の定義
49 (9)~(~(P→Q)∨ P)&
(~(P→Q)∨ P) 68&I
4 (ア) ~((P→Q)→ P) 79RAA
4 (イ) ~((P→Q)→ P)∨P ア∨I
ウ(ウ) P A
ウ(エ) ~((P→Q)→ P)∨P ウ∨I
(オ) ~((P→Q)→ P)∨P 12イウエ∨E
(カ) ((P→Q)→ P)→P オ含意の定義
(〃) ((PならばQ)ならばPならば)Pである。
(ⅲ)
1 (1) (P→ Q)→P A
2 (2) ~(P&~Q) A
3 (3) P A
4 (4) ~Q A
34 (5) P&~Q 34&I
234 (6) ~(P&~Q)&
(P&~Q) 25&I
23 (7) ~~Q 46RAA
23 (8) Q 7DN
2 (9) P→ Q 38CP
(ア) ~(P&~Q)→(P→Q) 29CP
イ (イ) ~(P&~Q) A
1 イ (ウ) (P→Q) アイMPP
1 イ (エ) P 1ウMPP
1 (オ) ~(P&~Q)→ P イエCP
1 (カ)~~(P&~Q)∨ P 含意の定義
キ (キ)~~(P&~Q) A
キ (ク) P&~Q キDN
キ (ケ) P ク&I
コ (コ) P A
1 (サ) P カキケココ∨E
(シ) ((P→Q)→ P)→P 1サCP
(〃) ((PならばQ)ならばP)ならばP。
従って、
(02)(03)により、
(04)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
5 兎に角、証明せよ。
(c)├((P→Q)→P)→P
といふ「問題」に対する「解答」は、少なくとも、
(ⅰ)
(ⅰ)12行の「計算」
(ⅱ)15行の「計算」
(ⅲ)21行の「計算」
による、少なくとも、「3通りの証明」が有ることになる。
然るに、
(05)
① 仮定(A)
② 前件肯定(MPP)
③ 後件否定(MTT)
④ 二重否定(DN)
⑤ 条件法的証明(CP)
⑥ 連言導入(&I)
⑦ 連言除去(&E)
⑧ 選言導入(∨I)
⑨ 選言除去(∨E)
⑩ 背理法(RAA)
といふ「10個の規則」を、「原始的規則(primitive rules)」といふ。
従って、
(03)(04)(05)により、
(06)
5 次の連式を、原始的規則のみによって証明せよ
5 Prove the following sequent by primitive rules alone:
(c)├((P→Q)→P)→P
といふ「問題」であるならば、
(ⅰ)12行の「計算」
(ⅱ)15行の「計算」
(ⅲ)21行の「計算」
に於いて、
(ⅰ)からは、「含意の定義+含意の定義+ド・モルガンの法則」 を除く「必要」が有り、
(ⅱ)からは、「排中律+含意の定義+ド・モルガンの法則+含意の定義+含意の定義」を除く「必要」が有り、
(ⅲ)からは、「含意の定義」 を除く「必要」が有る。
然るに、
(07)
(ⅰ)
1 (1) (P→ Q)→P A
1 (2) ~(P→ Q)∨P 1含意の定義
3 (3) ~(P→ Q) A
4 (4) ~P∨ Q A
4 (5) P→ Q 3含意の定義
34 (6) ~(P→ Q)&
(P→ Q) 5&I
3 (7)~(~P∨ Q) 46RAA
3 (8) P&~Q 7ド・モルガンの法則
3 (9) P 8&I
ア(ア) P A
1 (イ) P 239アア∨E
(ウ) ((P→Q)→P)→P 1イCP
(〃) ((PならばQ)ならばP)ならばP。
から、「含意の定義+含意の定義+ド・モルガンの法則」を除くのであれば、
(ⅳ)
1 (1) (P→ Q)→P A
2 (2) ~(~(P→ Q)∨P) A
3 (3) ~(P→ Q) A
3 (4) ~(P→ Q)∨P 3∨I
23 (5) ~(~(P→ Q)∨P)&
(~(P→ Q)∨P) 24&I
2 (6) ~~(P→ Q) 35RAA
2 (7) (P→ Q) 6DN
12 (8) P 17MPP
12 (9) ~(P→ Q)∨P 8∨I
12 (ア) ~(~(P→ Q)∨P)&
(~(P→ Q)∨P) 29&I
1 (イ)~~(~(P→ Q)∨P) 2アRAA
1 (ウ) ~(P→ Q)∨P イDN(2)
エ (エ) ~(P→ Q) A(選言支左)
オ (オ) ~P∨ Q A
カ (カ) P&~Q A
キ (キ) ~P A
カ (ク) P カ&E
カキ (ケ) ~P&P キク&I
キ (コ) ~(P&~Q) カケRAA
サ (サ) Q A
カ (シ) ~Q カ&E
カ サ (ス) Q&~Q サシ&I
サ (セ) ~(P&~Q) カスRAA
オ (ソ) ~(P&~Q) オキコシセ∨E
タ (タ) P A
チ (チ) ~Q A
タチ (ツ) P&~Q タチ&I
オ タチ (テ) ~(P&~Q)&
(P&~Q) コツ&I
オ タ (ト) ~~Q チテRAA
オ タ (ナ) Q トDN
オ (ニ) P→ Q タナ
エオ (ヌ) ~(P→ Q)&
(P→ Q) エニ&I
エ (ネ) ~(~P∨ Q) オヌRAA
ノ (ノ) ~P A
ノ (ハ) ~P∨ Q ノ∨I
エ ノ (ヒ) ~(~P∨ Q)&
(~P∨ Q) ネハ&I
エ (フ) ~~P ノヒRAA
エ (ヘ) P フDN
ホ(ホ) P A(選言支右)
1 (マ) P ウエヘホホ∨E
(ミ) ((P→Q)→P)→P 1マCP
(〃) ((PならばQ)ならばP)ならばP。
従って、
(06)(07)により、
(08)
(ⅰ)12行の「計算」
(ⅱ)15行の「計算」
(ⅲ)21行の「計算」
に於いて、
(ⅰ)からは、「含意の定義+含意の定義+ド・モルガンの法則」を除くならば、
(ⅰ)12行の「計算」は、「30行」増へて、「42行」になる。
従って、
(06)(08)により、
(09)
(ⅰ)12行の「計算」
(ⅱ)15行の「計算」
(ⅲ)21行の「計算」
に於いて、
(ⅱ)からは、「排中律+含意の定義+ド・モルガンの法則+含意の定義+含意の定義」を除くならば、
(ⅱ)15行の「計算」は、恐らく、「90行」近くになる。
然るに、
(06)により、
(10)
(ⅲ)21行の「計算」に対しては、
(ⅴ)
1 (1) (P→ Q)→P A
2 (2) ~(P&~Q) A
3 (3) P A
4 (4) ~Q A
34 (5) P&~Q 34&I
234 (6) ~(P&~Q)&
(P&~Q) 25&I
23 (7) ~~Q 46RAA
23 (8) Q 7DN
2 (9) P→ Q 38CP
(ア) ~(P&~Q)→(P→Q) 29CP
イ (イ) ~(P&~Q) A
1 イ (ウ) (P→Q) アイMPP
1 イ (エ) P 1ウMPP
1 (オ) ~(P&~Q)→ P イエCP
カ (カ) ~(P&~Q)&~P A
カ (キ) ~(P&~Q) カ&E
1 カ (ク) P オキMPP
カ (ケ) ~P カ&E
1 カ (コ) P&~P クケ&I
1 (サ)~~(P&~Q) カコDN
1 (シ) (P&~Q) サDN
1 (ス) (P&~Q)∨ P サ∨I
セ (セ) P&~Q A
セ (ソ) P ス&E
タ(タ) P A
1 (チ) P スセソタツ∨E
(ツ)((P→Q)→P)→P 1タCP
(〃)((PならばQ)ならばPならば)Pである。
であるため、
(ⅲ)21行の「計算」に対しては、
(ⅴ)27行の「計算」に変へることによって、
(ⅲ)からは、「含意の定義」を除くことが、出来る。
従って、
(06)~(10)により、
(11)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
5 兎に角、証明せよ。
(c)├((P→Q)→P)→P
といふ「問題」ではなく、
5 次の連式を、原始的規則のみによって証明せよ
5 Prove the following sequent by primitive rules alone:
(c)├((P→Q)→P)→P
といふ「問題」であるならば、
(ⅰ)12行の「計算」は、「42行」になり、
(ⅱ)15行の「計算」は、「90行」近くになり、
(ⅲ)21行の「計算」は、「27行」になる。
cf.
こうしてその証明を、最初の基本的規則からのより長い証明に変形できる。この場合に必要なのは、ある番号の付けかえのみである。
and thus transform the proof into a lengtheir proof form first principles: only a certain renumbering of lines is involved.
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、72頁と、原文)
従って、
(11)により、
(12)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
(c)├((P→Q)→P)→P
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、80頁と、原文)
といふ「問題」になってゐる。といふことからも分かるやうに、いづれにせよ、
├((P→Q)→P)→P≡((PならばQ)ならばP)ならばPである。
といふ「パースの法則」は、「自然演繹」で、「証明」出来る。
といふ、ことになる。
然るに、
(13)
├((P→Q)→P)→P
といふ「定理(Theorem)」を「証明」するといふことは、
(1)((P→Q)→P) から、
(2) Pが「演繹」出来ることを、「証明」することに「等しい」。
然るに、
(14)
「含意の定義」により、
(1) ((P→Q)→P) は、
(2)~(~P∨Q)∨P に「等しい」。
然るに、
(15)
「ド・モルガンの法則」により、
(2)~(~P∨Q)∨P は、
(3) (P&~Q)∨P に「等しい」。
然るに、
(16)
(3) (P&~Q)∨P からは、
(4) P ∨P が「演繹」出来る。
然るに、
(17)
(4) P ∨P からは、
(5) P が「演繹」出来る。
従って、
(14)~(17)により、
(18)
(1) ((P→Q)→P)
(2)~(~P∨Q)∨P :含意の定義
(3) (P&~Q)∨P :ド・モルガンの法則
(4) P ∨P
(5) P
(6)((P→ Q)→P)→P
となるものの、このことは、「含意の定義・ド・モルガンの法則」を、理解してゐる人間にとっては、「当然」である。
従って、
(19)
├ ((PならばQ)ならばP)ならばPである。
といふ風に、「言葉」で言ふと、「パースの法則」は、「不思議な感じ」がするものの、
(1) ((P→Q)→P)
(2)~(~P∨Q)∨P
(3) (P&~Q)∨P
(4) P ∨P
(5) P
(6)((P→ Q)→P)→P
といふ「計算」を見てしまふと、「そんなことは、当然」である。
といふことに、なる。
従って、
(20)
「含意の定義」と「ド・モルガンの法則」を、理解してゐるのであれば、
(ⅰ)
1 (1) (P→ Q)→P A
1 (2) ~(P→ Q)∨P 1含意の定義
3 (3) ~(P→ Q) A
4 (4) ~P∨ Q A
4 (5) P→ Q 3含意の定義
34 (6) ~(P→ Q)&
(P→ Q) 5&I
3 (7)~(~P∨ Q) 46RAA
3 (8) P&~Q 7ド・モルガンの法則
3 (9) P 8&I
ア(ア) P A
1 (イ) P 239アア∨E
(ウ) ((P→Q)→P)→P 1イCP
(〃)((PならばQ)ならばP)ならばP。
といふ「計算」は、「当然」であって、それ故、
├ ((PならばQ)ならばP)ならばPである。
といふ「パースの法則」は、「当然」である。
(21)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
5 兎に角、証明せよ。
(c)├((P→Q)→P)→P
といふ「問題」を、解いた際には、「特に、不思議な定理である」とは思はないまま、多分、
(1) ((P→Q)→P)
(2)~(~P∨Q)∨P
(3) (P&~Q)∨P
(4) P ∨P
(5) P
(6)((P→ Q)→P)→P
といふ「計算」をして、「そのやうな計算」をしたことを、忘れてゐた。
然るに、
(22)
排中律や二重否定の除去と等価な命題のひとつで、変なものとして、パースの法則があります。
任意の命題P, Qについて、
((P→Q)→P)→P
が成り立つ。
といふ「記事」に接して、「それならば、排中律を使って、証明しよう。」と思って、
(ⅱ)
(1) ~P∨P TI(排中律)
2 (2) ~P A
2 (3) ~P∨Q 2∨I
2 (4) P→Q 2含意の定義
2 (5) (P→Q)&~P 24&I
2 (6)~(~(P→Q)∨ P) 5ド・モルガンの法則
9 (7) (P→Q)→ P A
9 (8) ~(P→Q)∨ P 7含意の定義
49 (9)~(~(P→Q)∨ P)&
(~(P→Q)∨ P) 68&I
4 (ア) ~((P→Q)→ P) 79RAA
4 (イ) ~((P→Q)→ P)∨P ア∨I
ウ(ウ) P A
ウ(エ) ~((P→Q)→ P)∨P ウ∨I
(オ) ~((P→Q)→ P)∨P 12イウエ∨E
(カ) ((P→Q)→ P)→P オ含意の定義
(〃) ((PならばQ)ならばPならば)Pである。
といふ「計算」をした。
然るに、
(23)
(ⅰ)
1 (1) (P→ Q)→P A
1 (2) ~(P→ Q)∨P 1含意の定義
3 (3) ~(P→ Q) A
4 (4) ~P∨ Q A
4 (5) P→ Q 3含意の定義
34 (6) ~(P→ Q)&
(P→ Q) 5&I
3 (7)~(~P∨ Q) 46RAA
3 (8) P&~Q 7ド・モルガンの法則
3 (9) P 8&I
ア(ア) P A
1 (イ) P 239アア∨E
(ウ) ((P→Q)→P)→P 1イCP
(〃)((PならばQ)ならばP)ならばP。
といふ「計算」があるのだから、固より、
(ⅱ)
(1) ~P∨P TI(排中律)
から始まる「計算」をする「必要」などは、無かった。
といふことが、分かった。
然るに、
(24)
(ⅰ)
1(1) P A
1(2) ~Q∨P 1∨I
1(3) Q→P 2含意の定義
(4)P→(Q→P) 13CP
(〃)Pならば(QならばPである)。
といふ「計算」であっても、
(ⅱ)
(1) P∨~P TI(排中律)
(2) P A
(3) ~Q∨P 1∨I
(4) Q→P 2含意の定義
(5) P→(Q→P) 13CP
6(6) ~P A
6(7)~P∨(Q→P) 6∨I
6(8) P→(Q→P) 7含意の定義
(9) P→(Q→P) 12567∨E
(〃) Pならば(QならばPである)。
といふ風に、「排中律」から始めて、「ワザワザ、無駄な計算」をすることが、出来る。
cf.
「ルカジェヴィッツの公理1」。
従って、
(01)~(24)により、
(25)
排中律や二重否定の除去と等価な命題のひとつで、変なものとして、パースの法則があります。
とは、言はれてはゐる(?)ものの、今は、
「パースの法則」と「排中律」が、「等価」であるならば、例へば、
「ルカジェヴィッツの公理1」等々も、そうである。
といふことを、知ってゐる。
従って、
(26)
「パースの法則は、排中律と等価である。」と、敢へて、言ふ「必要」はない。
と、私自身は、思ってゐる。
令和02年02月04日、毛利太。
0 件のコメント:
コメントを投稿