https://leanprover-community.github.io/mathlib4_docs/Mathlib/Tactic/Explode.html#Mathlib.Explode.«command#explode_» 링크의 설명 가운데:
For example, exploding the following theorem:
#explode iff_of_true
produces:
iff_of_true : ∀ {a b : Prop}, a → b → (a ↔ b)
0│ │ a ├ Prop
1│ │ b ├ Prop
2│ │ ha ├ a
3│ │ hb ├ b
4│ │ x✝ │ ┌ a
5│4,3 │ ∀I │ a → b
6│ │ x✝ │ ┌ b
7│6,2 │ ∀I │ b → a
8│5,7 │ Iff.intro │ a ↔ b
9│0,1,2,3,8│ ∀I │ ∀ {a b : Prop}, a → b → (a ↔ b)
매스리브(Mathlib)의 #explode 명령은 린으로 작성된 증명 항을 피치식 증명(Fitch-style proof) 또는 메타매스(Metamath) 증명 양식과 비슷한 형식으로 내보내요.
저는 맥락[context], 종류[sort], 시퀀트 연산자 |- 등이 포함된 대상 논리를 고안해서 이를 메타매스 원(Metamath One)으로 형식화하려 해요. 그러고 나서, 제 대상 논리의 증명을 피치식 증명과 비슷한 형식으로 내보내는 프로그램을 만들 계획이에요.
a b : wff; · |- a → b → (a ↔ b)
ctx │ 0.1-0.2 │ ┌ a b : wff │
hyp │ 1 ha │ ├ a │
hyp │ 2 hb │ ├ b │
hyp │ 3.1 │ │ ┌ a │
│ 3.2 │ │ │ b │ hb
│ 3.3 mp │ │ a → b │ →I, 3.1-3.2
hyp │ 4.1 │ │ ┌ b │
│ 4.2 │ │ │ a │ ha
│ 4.3 mpr │ │ b → a │ →I, 4.1-4.2
│ 5 iff │ │ a ↔ b │ ↔I, mp, mpr
│ │ │ └───────────────────┐
│ 6 │ a b : wff; · |- a → b → (a ↔ b) │ →I, ctx, ha, hb, iff
그런 대상 논리를 어떻게 만들지는 저도 좀 더 생각해야 하지만, 그 대상 논리로 작성한 증명을 이용자가 위와 같은 형식으로 읽고 편집할 수 있으면 좋겠어요.
그동안 증명 보조기가 뭔지 모르는 분들이 이해할 수 있는 방식으로 형식 증명을 그분들에게 보여 드리지 못해서 제가 불편함을 느낀 적이 많았어요. 피치식 증명도 여전히 그분들이 읽기 쉬운 편은 아니지만, 일단 이런 양식으로 형식 증명을 내보내는 프로그램부터 제가 직접 만들려 해요.
4개의 좋아요
저는 형식 증명을 사람이 읽기 쉬운 형태로 보여 주는 프로그램을 나중에 제 교육용 게임에 포함할까 해요. 그래서 고도(Godot) 게임 엔진을 이용하는 방법을 이번 주부터 배울 예정이에요.
2개의 좋아요
지금 제가 바빠서 아직 글을 못 썼는데, 시퀀트(sequent)로 자연 연역 규칙들을 서술한 증명 체계를 이달 만들었어요. 이 증명 체계에서 도출(유도) 가능한 시퀀트에 대응하는 조건문이 린(Lean)의 유형론에서 참임을 밝히는 데 성공했어요.
사실 그 방법이 별로 어렵지도 않더군요. 이를 알아내기까지 너무 오랜 시간이 걸렸지만요.
맥락과 종류는 뺐어요. 이 둘을 증명 체계에 넣으면, 그에 관한 규칙들도 제가 직접 다 만들어야 해요. 논리학 입문자에게 적합한 증명 체계는 되도록 단순해야 한다고 판단했어요.
2개의 좋아요
명제 논리의 잘세운식(잘 형성된 식, 정형식, well-formed formula, wff)은 제가 다음과 같이 정의했습니다.
/-- Well-formed formulas in propositional logic. -/
inductive Wff : Type where
| Tru : Wff
| Fal : Wff
| And (φ ψ : Wff) : Wff
| Or (φ ψ : Wff) : Wff
| Imp (φ ψ : Wff) : Wff
아래의 함수 Wff.toProp는 잘세운식을 린의 유형론에서의 명제로 번역합니다.
namespace Wff
def toProp : Wff → Prop
| Tru => True
| Fal => False
| And φ ψ => φ.toProp ∧ ψ.toProp
| Or φ ψ => φ.toProp ∨ ψ.toProp
| Imp φ ψ => φ.toProp → ψ.toProp
end Wff
시퀀트[sequent] φ ⊢ ψ는 ψ가 φ에서 도출된다는 뜻입니다. 그리고 ⊢ φ 표기는 시퀀트 ⊤ ⊢ φ를 나타냅니다. 제 연역 체계[deduction system]는 다음 추론 규칙[inference rule]을 갖고 있습니다.
id : φ ⊢ φ. 동일 규칙.
simpl : (⊢ φ) → (ψ ⊢ φ). 단순화 규칙.
syl : (φ ⊢ ψ) → (ψ ⊢ χ) → (φ ⊢ χ). 삼단 논법 규칙.
falE : ⊥ ⊢ φ. 거짓 제거 규칙.
andI : (φ ⊢ ψ) → (φ ⊢ χ) → (φ ⊢ ψ ∧ χ). 연언(논리곱) 도입 규칙.
andEL : ψ ∧ χ ⊢ ψ. 연언 왼쪽 제거 규칙.
andER : ψ ∧ χ ⊢ χ. 연언 오른쪽 제거 규칙.
orIL : φ ⊢ φ ∨ ψ. 선언(논리합) 왼쪽 도입 규칙.
orIR : ψ ⊢ φ ∨ ψ. 선언 오른쪽 도입 규칙.
orE : (φ ⊢ ψ ∨ χ) → (φ ∧ ψ ⊢ θ) → (φ ∧ χ ⊢ θ) → (φ ⊢ θ). 선언 제거 규칙.
impI : (φ ∧ ψ ⊢ χ) → (φ ⊢ ψ → χ). 함의(조건문) 도입 규칙.
impE : (φ ⊢ ψ → χ) → (φ ⊢ ψ) → (φ ⊢ χ). 함의 제거 규칙.
도출[derivation]될 수 있는 시퀀트가 명제로 번역될 때, 그 명제가 참임을 제가 증명하는 데 성공했습니다.
namespace Sequent
/-- For all well-formed formulas `φ` and `ψ`, if `ψ` is derivable from `φ`, then the proposition
`φ.toProp → ψ.toProp` is true. -/
theorem toProp {φ ψ : Wff} (d : φ ⊢ ψ) (h : φ.toProp) : ψ.toProp :=
match d with
| id => h
| simpl d => d.toProp trivial
| @syl φ _χ ψ d₁ d₂ => d₂.toProp (d₁.toProp h)
| falE => h.elim
| @andI φ χ θ d₁ d₂ => ⟨d₁.toProp h, d₂.toProp h⟩
| @andEL χ θ => h.1
| @andER χ θ => h.2
| @orIL χ θ => Or.inl h
| @orIR χ θ => Or.inr h
| @orE φ _χ _θ ψ or left right =>
(or.toProp h).elim (and_imp.mp left.toProp h) (and_imp.mp right.toProp h)
| @impI χ θ ψ d => and_imp.mp d.toProp h
| @impE φ _χ ψ d₁ d₂ => (d₁.toProp h) (d₂.toProp h)
end Sequent
그러나 린의 유형론으로 서술된 명제 논리식[propositional formula]의 구성적 증명을 시퀀트의 도출[derivation]로 번역하는 일이 제 예상보다 훨씬 어려웠습니다. 그래서 제가 린 줄립 챗에 메시지를 올렸는데, 아직은 해결책이 나오지 않았습니다.
3개의 좋아요
여러분, 이 정의에 무슨 문제가 있는지 파악하셨나요? 잘세운식이 명제 변수(원자 명제, 명제 글자) 없이 구성됐어요. 그래서 모든 잘세운식이 결정 가능해요. 이를 바탕으로 배중률을 증명할 수가 있어요. 제가 만든 연역 체계는 직관주의 논리를 바탕으로 해야 하는데도요!
근데 제가 작성한 앞선 메시지를 다시 보니, 제가 직관주의 논리를 위한 연역 체계를 만든다는 말을 안 했네요. 음, 이건 제 실수예요.
메타매스 직관주의 집합론 데이터베이스의 초반부도 원자 명제를 따로 잘세운식에 포함하지 않았어요. 이래도 거기서는 잘세운식에 대한 재귀 원리 자체가 없어서 문제가 안 생기는 듯해요.
재귀자[recursor]는 참 미묘하고 어려워요. 아직도 저도 이를 충분히 이해하지 못하고 있다는 점을 절감했어요.
여기서 제 추측이 계속 틀리는 과정을 보실 수 있어요.
2개의 좋아요
제가 린(Lean) 증명 보조기의 이용법을 배우면서 비고전 논리에 대한 관심도 많아졌어요.
2개의 좋아요
Lean하고 Coq가 브라우어의 직관주의에 영향을 받은 계산적 해석(구성주의)를 기반으로 하고 있거든요.
2개의 좋아요
조금 더 부연하자면, 린의 공리에는 선택 공리가 있어서 배중률이 성립하긴 해요. 현재 린의 몇몇 전략(전술, tactic)은 배중률을 기본으로 이용해요.
2개의 좋아요
드디어 제가 직관주의 명제 논리를 위한 힐베르트 체계의 변종을 만들었어요. 자연 연역과 비슷하게 증명을 작성할 수 있도록 공리와 추론 규칙을 골랐어요. https://git.sr.ht/~chabulhwi/lean-notes/tree/master/Notes/PropositionalLogic.lean
사실 메타매스 집합론 데이터베이스는 이런 추론 규칙들을 이미 활용하고 있었어요. 앞으로도 제가 할 일이 남아 있는데, 그 일을 끝내면 새로운 주제를 열게요.
2개의 좋아요
감사합니다! 제 연역 체계가 그다지 독창적이지는 않아요. 그렇지만 전건 긍정 논법(모두스 포넨스) 말고도 동일 공리, 단순화 규칙 , 삼단 논법이 필요하다는 점을 제가 깨닫기까지 적어도 4년이 걸렸어요.
마리오 카네이로(Mario Carneiro) 박사님, 메타매스(Metamath) 커뮤니티, 린(Lean) 커뮤니티의 저작물이 제게 큰 도움을 줬어요.
3개의 좋아요