命題論理

logic

余談:ドジソンの4つの法則

• “Begin of the beggining” 「始めから始めよ」
• わからないまま次に進むな
• 3回読んでわからなかったらその日は休もう
• できれば人と話しながら進めよう

命題論理

• $\top$: true, $\perp$: false
• $\leftrightarrow$: iff(if and only if)
• $\models A$: トートロジー(恒真式)

命題論理の証明論

任意の論理式 $A,P_a\cdots P_n$ に対して 開いた前提 $B_1\cdots B_n$ をもつ $A$ の証明構造

命題論理の自然演繹体系(NK)

1. ∧-導入規則(∧-I) $\frac{AB}{A\wedge B}$
2. ∧-除去規則(∧-I) $\frac{A\wedge B}{A},\frac{A\wedge B}{B}$
3. →-I $\frac{[A{]}^n\cdots B}{A\to B}$
4. →-E $\frac{AA\to B}{B}$
5. ¬-I $\frac{[A{]}^n\cdots \perp }{\neg A}$
6. ¬-E $\frac{A\neg A}{\perp }$
7. ∨-I $\frac{A\vee B}{\perp }$
8. ∨-E $\frac{A\vee B[A{]}^n\cdots C[B{]}^n\cdots C}{C}$
9. ¬¬-E $\frac{\neg \neg A}{A}$

命題論理の証明

証明

論理式 $A$ を終論理式とする証明が存在する時 証明可能 $⊢A$ と書く
仮定 $B_1\cdots B_n$ から証明できるとき, $B_1\cdots B_n⊢A$

健全性(soundness)

証明可能な論理式は全てトートロジーである. NKは健全

完全性(completeness)

任意のトートロジーな論理式は証明可能, NKは完全
論理式 A を終論理式とする証明が存在する時 証明可能  ⊢ A と書く
仮定 B1⋯Bn から証明できるとき, B1⋯Bn ⊢ A
-> 古典論理 LK

例