HOL에서 일차 모달 논리: 자동 충실도를 갖는 깊은 및 얕은 임베딩 (확장 프리프린트)
요약
Isabelle/HOL 환경에서 일차 모달 논리(FML)를 심층 및 얕은 임베딩 방식으로 확장하는 연구를 소개합니다. 상수 도메인 Kripke 의미론을 활용하여 세 가지 임베딩 방식을 제안하며, Löwenheim-Skolem 정리를 메커제니제이션하여 충실성 증명을 자동화했습니다.
핵심 포인트
- Isabelle/HOL 기반의 일차 모달 논리(FML) 임베딩 방법론 확장
- 깊은, 무거운 최대 얕은, 가벼운 최소 얕은 임베딩의 세 가지 방식 제공
- Löwenheim-Skolem 정리를 통한 임베딩 간 충실성 증명 자동화 지원
- 비가산 도메인에서의 전사 문제 해결을 위한 로케일 확장 기법 적용
- 일차 양자화를 위한 정교한 치환 기계 장치(substitution machinery) 개발
우리는 Isabelle/HOL 환경에서 이전 연구의 명제 논리(propositional logic) 기반 심층-얕은 임베딩 방법론을 상수 도메인 Kripke 의미론을 가진 일차 모달 논리(First-Order Modal Logic, FML)로 확장합니다. 클래식 고계 논리(classical higher-order logic, HOL)로의 세 가지 FML 임베딩이 나란히 제공됩니다: 깊은 임베딩(deep embedding), 무거운 최대 얕은 임베딩(heavyweight maximal-shallow embedding), 그리고 가벼운 최소 얕은 임베딩(lightweight minimal-shallow embedding)입니다. 최소 얕은 임베딩은 접근성 관계(accessibility relation), 세계 인덱스 해석(world-indexed interpretation), 세계의 우주(universe of worlds), 변수 할당(variable assignment)으로 매개변수화된 Isabelle/HOL 로케일(locale)로 제시됩니다. 이 로케일 형태는 모든 최소 얕은 해석에 대한 양자화가 정확히 깊은 타당도(deep validity)를 복구한다는 것을 명시하는 전역 충실성 정리(global faithfulness theorem)를 가집니다. 핵심적인 기술적 기여는 상수 도메인 Kripke 의미론을 가진 FML에 대해 (가산) 하향 Löwenheim-Skolem 정리를 메커니제이션한 것인데, 이는 깊은 임베딩과 최소 얕은 임베딩 사이의 충실성 증명 자동화를 뒷받침합니다. 이를 최소 얕은 로케일 확장 내부에 배포함으로써, 개체의 비가산 도메인에 대해 발생하는 전사 문제(surjectivity problem)를 해결합니다. 이 문제는 로케일의 변수 할당이 가산 도메인 V = nat을 가지므로 도메인으로 전사될 수 없기 때문에 발생하며, 그 결과 전체 도메인에 걸쳐 충실성을 제공합니다. 이전 연구가 명제 단편(propositional fragment)만을 다루었기 때문에, 여기서는 일차 양자화(first-order quantifiers)에 필요한 치환 기계 장치(substitution machinery)(자유/바운드 변수 술어, 신규 변수 함수, 포획 회피 치환(capture-avoiding substitution), 알파벳 이름 변경(alphabetic renaming), 치환 가능성 술어(substitutability predicate), 치환 보조정리(substitution lemma), 그리고 크기 기반 귀납 원리(size-based induction principles))를 개발합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.AI의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기