초직관 논리

논리학에서 초직관 논리(超直觀論理, 영어: superintuitionistic logic) 또는 중간 논리(中間論理, 영어: intermediate logic)는 직관 논리보다는 더 강하지만, 고전 논리보다 더 약한 논리 체계이다.

정의

초직관 논리의 통사론적 체계 L은 다음의 조건을 만족하는 정식들의 집합으로 구성된다.

직관 논리의 모든 공리들은 L에 속한다.
(전건 긍정의 형식에 대해 닫힘) P와 Q가 정식이며 P와 P→Q가 L에 속한다면, Q도 L에 속한다.
(치환에 대해 닫힘) 명제 변수 p, q, r, ...에 대하여 F(p, q, r, ...)가 L에 속하는 정식이고 G₁, G₂, G₃, ...가 임의의 정식이라면, F(G₁, G₂, G₃, ...)도 L에 속하는 정식이다.

예

초직관 논리는 직관 논리에서 특정한 공리를 추가하여 정의할 수 있다. 명제 논리인 초직관 논리의 예는 다음을 들 수 있다.

직관 논리(IPC): IPC
고전 논리학(CPC): IPC + p ∨ ¬p = IPC + ¬¬p → p = IPC + ((p → q) → p) → p (마지막 것은 퍼스의 법칙)
약한 배중률 논리학(얀코프 논리학 또는 드 모르간 논리학^[1], KC): IPC + ¬p ∨ ¬¬p
괴델-더밋 논리학(LC, G): IPC + (p → q) ∨ (q → p)
크라이젤-퍼트넘 논리학(KP): IPC + (¬p → (q ∨ r)) → ((¬p → q) ∨ (¬p → r))
스콧 논리학 (SL): IPC + ((¬¬p → p) → (p ∨ ¬p)) → (¬¬p ∨ ¬p)
스메타니치 논리학(SmL): IPC + (¬q → p) → (((p → q) → p) → p)
유계 기수 논리학 (BC_n): $\textstyle \mathbf {IPC} +\bigvee _{i=0}^{n}{\bigl (}\bigwedge _{j<i}p_{j}\to p_{i}{\bigr )}$
유계 폭(width) 논리학 또는 유계 반사슬 논리학(BW_n, BA_n): $\textstyle \mathbf {IPC} +\bigvee _{i=0}^{n}{\bigl (}\bigwedge _{j\neq i}p_{j}\to p_{i}{\bigr )}$
유계 깊이(depth) 논리학(BD_n): IPC + p_n ∨ (p_n → (p_n−1 ∨ (p_n−1 → ... → (p₂ ∨ (p₂ → (p₁ ∨ ¬p₁)))...)))
유계 최대폭(top width) 논리학 (BTW_n): $\textstyle \mathbf {IPC} +\bigvee _{i=0}^{n}{\bigl (}\bigwedge _{j<i}p_{j}\to \neg \neg p_{i}{\bigr )}$
유계 분지(branching) 논리학 (T_n, BB_n): $\textstyle \mathbf {IPC} +\bigwedge _{i=0}^{n}{\bigl (}{\bigl (}p_{i}\to \bigvee _{j\neq i}p_{j}{\bigr )}\to \bigvee _{j\neq i}p_{j}{\bigr )}\to \bigvee _{i=0}^{n}p_{i}$
괴델 n치 논리학 (G_n): LC + BC_n−1 = LC + BD_n−1

이러한 초직관 논리들은 직관 논리를 최소 원소로, 고전 명제 논리를 최대 원소로 하는 유계 완비 격자를 형성한다. 또한 스메타니치 논리학(SmL)은 이런 초직관주의 논리학들의 격자에서 유일한 공원자(coatom)이다.

의미론

헤이팅 대수 의미론

초직관 논리의 명제들의 린덴바움-타르스키 대수는 헤이팅 대수를 이루며, 반대로 주어진 헤이팅 대수에 대하여, 이를 린덴바움-타르스키 대수로 하는 초직관 논리 이론을 정의할 수 있다. 따라서, 주어진 초직관 논리에 대하여, 적절한 성질을 만족시키는 헤이팅 대수를 사용하여 의미론을 정의할 수 있다.

만약 이 헤이팅 대수가 불 대수라면 이렇게 얻어지는 논리는 고전 논리이고, 반면 이 헤이팅 대수가 자유 헤이팅 대수라면 이렇게 얻어지는 논리는 직관 논리이다.

양상 논리와의 관계

초직관 논리는 양상 논리로 다음과 같이 번역할 수 있다. 이를 괴델-타르스키 번역(Gödel–Tarski translation)이라 한다.

$T(p_{n})=\Box p_{n}$
$T(\lnot A)=\Box \lnot T(A)$
$T(A\land B)=T(A)\land T(B)$
$T(A\lor B)=T(A)\lor T(B)$
$T(A\to B)=\Box (T(A)\to T(B))$

M을 어떤 양상 논리 체계라 하자, 그러면, 이상의 번역에 의해,

C(M) := {A | T(A) ∈ M}

은 어떤 초직관 논리 체계가 되는데, 이때 M을 C(M)의 양상 동반원(modal companion)이라 한다. 몇 가지 예로,

IPC = C(S4)
KC = C(S4.2)
LC = C(S4.3)
CPC = C(S5)

등이 있다. 이 대응은 유일하지 않을 수 있다. 즉, 어떤 초직관 논리에 대해 여러 양상 동반원이 있을 수 있다.

크립키 모형

양상 논리와 직관 논리와 마찬가지로, 초직관 명제 논리의 의미론 역시 크립키 모형으로 정의할 수 있다.

각주

↑ Constructive Logic and the Medvedev Lattice, Sebastiaan A. Terwijn,Notre Dame J. Formal Logic Volume 47, Number 1 (2006), p. 73-82.

Umezawa, Toshio (1959년 6월). “On logics intermediate between intuitionistic and classical predicate logic”. 《Journal of Symbolic Logic》 (영어) 24 (2): 141–153. doi:10.2307/2964756. JSTOR 2964756. MR 115906. Zbl 0143.01004.
Hosoi, Tsutomu; Hiroakira Ono (1973). “Intermediate propositional logics (a survey)”. 《Journal of Tsuda College》 (영어) 5: 67–82.
Ono, Hiroakira (1972). “A study of intermediate predicate logics”. 《Publications of the Research Institute of Mathematical Sciences of Kyoto University》 (영어) 8: 619–649. Zbl 0281.02033.
Alexander Chagrov, Michael Zakharyaschev. Modal Logic. Oxford University Press, 1997.

외부 링크

“Intermediate logic”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Moschovakis, Joan (2014년 5월 23일). “Intuitionistic logic”. 《Stanford Encyclopedia of Philosophy》 (영어).

[1] Constructive Logic and the Medvedev Lattice, Sebastiaan A. Terwijn,Notre Dame J. Formal Logic Volume 47, Number 1 (2006), p. 73-82.

[1]