(01)
7 実際上、われわれの規則DNはつぎの2つの規則が結合したものである。
(ⅰ)Aから~~Aを導出すること、そして、
(ⅱ)~~AからAを導出すること、
(ⅰ)は他の原始的規則から導出されることを示せ(規則MTT、すなわち連式55、対する、これに対応する証明を参照せよ)。
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、81頁)
(02)
〔解答〕
1 (1) P A
2(2) ~P A
12(3) P&~P 12&I
1 (4)~~P 23RAA
(5) P→~~P 14CP
cf.
ただし、「E.J.レモン、論理学初歩」には、「練習問題の解答」は、載ってゐません。
従って、
(02)により、
(03)
1 (1) (P) A
2(2) (~P) A
12(3) (P)&(~P) 12&I
1 (4)~(~P) 23RAA
(5) (P)→~(~P) 14CP
然るに、
(04)
1 (1) (P) A
2 (2) (~P) A
12 (3) (P)&(~P) 12&I
1 (4) ~(~P) 23RAA
(5) (P)→~(~P) 14CP
6(6) ~~(~P) A
6(7) (~P) 56MTT
(8) ~~(~P)→ (~P) 67CP
然るに、
(05)
系Ⅰ:任意の連式は、それがトートロジー的であるときまたそのときに限って導出可能である。
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、114頁)
従って、
(03)(04)(05)により、
(06)
① (P)→~(~P)
② ~~(~P)→ (~P)
は、「恒真式(トートロジー)」である。
然るに、
(07)
① (P)→~(~P)
といふ「式」は、
① (P)→~~(P)
といふ「式」に、「等しい」。
従って、
(06)(07)により、
(08)
① (P)→~~(P)
② ~~(~P)→ (~P)
といふ「式」は、「恒真式(トートロジー)」である。
然るに、
(09)
(S1)証明された定理の任意の代入例に対して、証明が見いだされうる。
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、69頁)
1 代入の規則
一つの恒真式のなかの命題変項を他の命題変項、または論理式でおきかえることによって得られた式は同じく恒真式である。
(沢田允、現代論理学入門、1962年、173頁)
従って、
(08)(09)により、
(10)
① (P)→~~(P)
② ~~(~P)→ (~P)
に於いて、
~P=P
といふ「代入(Substitution)」を行へば、
① (P)→~~(P)
② ~~(P)→ (P)
といふ「式」は、「恒真式(トートロジー)」である。
従って、
(10)により、
(11)
① P→~~P
② ~~P→ P
といふ「式」は、「恒真式(トートロジー)」である。
然るに、
(01)により、
(12)
① 仮定(A)
② 前件肯定(MPP)
③ 後件否定(MTT)
④ 二重否定(DN)
⑤ 条件法的証明(CP)
⑥ 連言導入(&I)
⑦ 連言除去(&E)
⑧ 選言導入(∨I)
⑨ 選言除去(∨E)
⑩ 背理法(RAA)
といふ「10個の規則」を、「原始的規則(10 primitive rules)」といふ。
従って、
(01)(11)(12)により、
(13)
実際上、われわれの規則「二重否定(DN)」はつぎの2つの規則が結合したものである。
(ⅰ)Aから~~Aを導出すること、そして、
(ⅱ)~~AからAを導出すること、そして、
(ⅰ)は他の原始的規則(A、&I、RAA、CP)」 から導出されることを示せるし、
(ⅱ)も他の原始的規則(A、&I、RAA、CP、MTT)から導出されることを示せる。
といふことが、分かった、ことになる。
従って、
(12)(13)により、
(14)
① 仮定(A)
② 前件肯定(MPP)
③ 後件否定(MTT)
④ 二重否定(DN)
⑤ 条件法的証明(CP)
⑥ 連言導入(&I)
⑦ 連言除去(&E)
⑧ 選言導入(∨I)
⑨ 選言除去(∨E)
⑩ 背理法(RAA)
から、
④ 二重否定(DN)
を除いて、「原始的規則(9 primitive rules)」としても、「支障」は無い。
然るに、
(15)
"「Pではない」ではないならば、Pである"
つまり、否定を~で表すと「~~PならばP」だと言ってます。
……何か問題が?
けどこれ「二重否定の除去」といって、成り立つことが示せないんですよ。
(排中律、二重否定の除去、パースの法則 - Qiita)
従って、
(13)(14)(15)により、
(16)
けどこれ「二重否定の除去」といって、成り立つことが示せないんですよ。
といふことには、ならない。
然るに、
(17)
直観主義論理
出典: フリー百科事典『ウィキペディア(Wikipedia)』
証明論的な視点から見ると、直観主義論理は古典論理の制限であって排中律や二重否定除去が公理として許容されないものである。排中律や二重否定除去はいくつかの論理式に対しては個別に証明できることがあるけれども、古典論理のように普遍的に成立することはない。
然るに、
(18)
―「排中律」の証明 ―
44 ├ P∨~P
1 (1) ~(P∨~P) A
2(2) P A
2(3) P∨~P 2∨I
12(4) ~(P∨~P)&
(P∨~P) 13&I
1 (5) ~P 24RAA
1 (6) P∨~P 5∨I
1 (7) ~(P∨~P)&
(P∨~P) 16&I
1 (8)~~(P∨~P) 17RAA
(9) P∨~P 8DN
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、66頁)
従って、
(16)(17)(18)により、
(19)
「直観主義論理は古典論理の制限であって排中律や二重否定除去が公理として許容されないものである。」
といは言ふものの、
「自然演繹からすれば、排中律や二重否定除去は、固より、公理ではなく、規則から演繹される所の、定理に、過ぎない。」
(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)
「パースの法則は、排中律と等価である。」と、敢へて、言ふ「必要」はない。
と、私自身は、思ってゐる。