今日の論理学:練習問題83(補助定理44-2-2の前提がAPLで成立することの確認)

前回までの論理学

• 公理系APLの完全性を証明したい
  • ヘンキンの定理を証明する必要がある
    • 証明で使いたい補助定理をあらかじめ証明しておく
    • 【補助定理44-1 リンデンバウムの補助定理(Lindenbaum's lemma)】→done
    • 【補助定理44-2 極大無矛盾集合の充足可能性補助定理】→done
      • 補助定理44-2-1 Γ⊢AかつΓ⊆Γ*であるとき、A∈Γ* →done
      • 補助定理44-2-2 Γ*を極大無矛盾集合とし、AとBを任意の論理式とすると以下が成り立つ→ 前回やった
        • この定理が公理系に要求している6つの性質がある→APLで成り立っていることを確認する演習問題を今回やる

補助定理44-2-2の証明の注意点
- A∧B⊢A
- A∧B⊢B
- A,B⊢A∧B
- A,A→B⊢B
- ¬A⊢A→B
-  B⊢A→B

はその公理系で成り立つことを示しておく必要がある。
(いくつかのものがAPLで成り立つことを証明する練習問題を次回やる)

yuyubu-sub.hateblo.jp

APLで¬A⊢A→BおよびB⊢A→Bが成り立つことを示せ

• おさらい:公理系APLについてp250

公理系APL(axiomatic system for propositional logic)

A1 A→(B→A)
A2 (A→(B→C))→((A→B)→(A→C))
A3 (¬B→¬A)→((¬B→A)→B)

R1 MP

• A1-3は推論規則と呼ばれる
• R1のMPは分離と呼ばれる

R1 AとA→BからBを引き出して良い(分離規則・modus ponens,略してMPという) (p249)

¬A⊢A→B

no	deduction	detail
( 1)	¬A	premise
( 2)	(¬B→¬A)→((¬B→A)→B)	A3
( 3)	¬A→(¬B→¬A)	A1(A=¬A;B=¬B)
( 4)	¬B→¬A	(1)(3) MP
( 5)	(¬B→A)→B	(2)(4) MP
( 6)	A	premise
( 7)	A→(¬B→A)	A1(A=A;B=¬B)
( 8)	¬B→A	(6)(7) MP
( 9)	B	(5)(8) MP
(10)	B→(A→B)	A1(A=B;B=A)
(11)	A→B	(9)(10) MP

• 本の回答だとp263の定理39,矛盾した式からは任意の式がdeduction可能であることの証明ですでに示されている。
• 本中のdeductionではA3を使ってもっと早く演繹してる。(本中だと9回しかdeductionnしてない。私より2回少ない)

B⊢A→B

no	deduction	detail
1	B	assumption
2	B→(A→B)	A1
3	A→B	(1)(2)MP

• これは簡単。

論理学をつくる