6.20 비단조 논리(Non-monotonic Logic)를 통한 불완전성 우회 전략

1. 단조성의 정의와 고전 논리에서의 역할

고전 논리(classical logic)에서 단조성(monotonicity)은 추론의 핵심적 구조적 속성이다. 전제 집합 \Gamma에서 결론 \varphi가 도출 가능하면, \Gamma에 임의의 추가 전제 \psi를 포함한 \Gamma \cup \{\psi\}에서도 \varphi가 도출 가능하다. 형식적으로 다음이 성립한다.

\Gamma \vdash \varphi \implies \Gamma \cup \{\psi\} \vdash \varphi

단조성은 고전 논리의 추론이 정보의 추가에 의해 무효화되지 않음을 보장한다. 한 번 도출된 결론은 새로운 정보에 의해 철회될 수 없다. 이 속성은 수학적 증명의 영속성—참인 정리는 영원히 참이다—을 보장하며, 형식 체계의 축적적(cumulative) 성격을 가능하게 한다.

그러나 단조성은 불완전한 정보 하에서의 실제적 추론과 근본적으로 충돌한다. 일상적 추론에서 인간은 새로운 정보에 기반하여 이전의 결론을 수정하거나 철회한다. “새는 날 수 있다“라는 결론은 “이 새는 펭귄이다“라는 추가 정보에 의해 철회된다. 이러한 철회 가능한 추론(defeasible reasoning)은 단조 논리로 직접 표현할 수 없다.

2. 비단조 논리의 동기와 기본 원리

비단조 논리(non-monotonic logic)는 단조성을 포기함으로써 새로운 정보에 의한 결론의 철회를 형식적으로 허용하는 논리 체계이다. 이 체계에서는 다음이 가능하다.

\Gamma \vdash_{nm} \varphi \text{ 이지만 } \Gamma \cup \{\psi\} \nvdash_{nm} \varphi

여기서 \vdash_{nm}은 비단조적 도출 관계를 나타낸다. 비단조 논리는 불완전한 지식을 기반으로 잠정적 결론을 도출하되, 모순되는 정보가 도착하면 이전 결론을 합리적으로 철회하는 추론을 형식화한다.

비단조 논리의 핵심 원리는 폐쇄 세계 가정(closed world assumption, CWA)이다. 알려진 정보만으로부터 결론을 도출하되, 명시적으로 참이라고 알려지지 않은 것은 잠정적으로 거짓으로 간주한다. 이는 데이터베이스 시스템에서 “질의에 대한 답이 존재하지 않으면 해당 사실은 성립하지 않는다“는 부정에 의한 실패(negation as failure) 원리로 구현된다.

3. 주요 비단조 논리 체계

3.1 맥카시의 외접법(Circumscription)

McCarthy(1980)가 제안한 외접법은 술어의 외연(extension)을 최소화하는 비단조적 추론 방법이다. 주어진 공리 집합 \Gamma에서 술어 P의 외연을 최소화한다는 것은, \Gamma를 만족하면서 P의 외연이 가장 작은 모델을 선호하는 것이다.

형식적으로, 모델 \mathcal{M}_1이 모델 \mathcal{M}_2보다 P에 대해 최소적이라 함은, P^{\mathcal{M}_1} \subseteq P^{\mathcal{M}_2}이고 다른 모든 술어의 외연은 동일한 것이다. 외접법은 이 최소 모델에서 성립하는 명제를 비단조적으로 도출한다.

외접법은 비정상적 사례(abnormality)를 최소화하여 기본값 추론(default reasoning)을 가능하게 한다. “새는 날 수 있다“를 형식화할 때, “비정상적이지 않은(abnormal하지 않은) 새는 날 수 있다“로 기술하고, 비정상 술어 Ab를 외접하여 비정상 사례를 최소화한다.

3.2 라이터의 기본값 논리(Default Logic)

Reiter(1980)가 제안한 기본값 논리는 기본값 규칙(default rule)이라는 새로운 형태의 추론 규칙을 도입한다. 기본값 규칙은 다음의 형태를 갖는다.

\frac{\alpha : \beta_1, \ldots, \beta_n}{\gamma}

이는 “전제 \alpha가 성립하고, \beta_1, \ldots, \beta_n이 현재 신념과 모순되지 않으면, \gamma를 결론으로 채택한다“를 의미한다. \beta_i는 정당화(justification)라 불리며, 이것이 현재 지식과 일관적(consistent)인지를 점검하는 것이 비단조성의 원천이다.

기본값 논리의 의미론은 확장(extension)의 개념으로 정의된다. 확장은 고전 논리적 결론과 적용 가능한 기본값 규칙으로부터 도출된 결론의 일관적 집합이다. 하나의 기본값 이론이 여러 확장을 가질 수 있으며, 이는 추론의 다의성(ambiguity)을 반영한다.

3.3 무어의 자기 인식 논리(Autoepistemic Logic)

Moore(1985)가 제안한 자기 인식 논리는 이상적 추론자의 자기 신념에 대한 반성적 추론을 형식화한다. 양상 연산자 L을 도입하여, L\varphi는 “나는 \varphi를 믿는다“를 나타낸다. 자기 인식 논리에서 추론자는 자신이 무엇을 알고 무엇을 모르는지에 대한 완전한 내성(introspection)을 가정하며, “\varphi를 믿지 않으므로(\neg L\varphi) \psi를 결론짓는다“는 형태의 추론이 가능하다.

자기 인식 논리의 의미론은 안정 확장(stable expansion)으로 정의된다. 안정 확장 T는 전제 집합 A와 T 자신에 대한 양상적 진술의 도출적 폐포(deductive closure)로서, 고정점(fixed-point) 조건을 만족한다. 이 고정점 정의는 기본값 논리의 확장 개념과 밀접하게 관련되며, Konolige(1988)가 두 체계 사이의 형식적 대응을 확립하였다.

4. 비단조 논리와 불완전성 정리의 관계

비단조 논리가 불완전성 정리를 “우회“할 수 있는지에 대한 정밀한 분석이 필요하다. 이 문제에 대한 답은 “우회“의 의미에 의존한다.

불완전성 정리의 직접적 극복에 대하여. 비단조 논리가 괴델의 불완전성 정리를 직접적으로 극복하는 것은 아니다. 불완전성 정리는 재귀적으로 공리화 가능하고 페아노 산술을 포함하는 무모순 형식 체계에 적용된다. 비단조 논리 체계가 이 조건을 충족하는 한, 불완전성 정리의 제약으로부터 자유로울 수 없다. 비단조 논리의 결론이 철회 가능하다는 사실은 형식 체계의 무모순성이나 완전성 문제와 직접적으로 관련되지 않는다.

불완전한 정보 하에서의 추론 능력에 대하여. 비단조 논리가 실질적으로 “우회“하는 것은 고전 논리의 단조성에 의한 실천적 제약이다. 고전 논리에서 불완전한 정보 하의 추론은, 가능한 모든 완성(completion)을 고려하는 방식으로 처리되어야 하며, 이는 계산적으로 비용이 극히 높다. 비단조 논리는 잠정적 결론의 도출과 철회라는 경제적 메커니즘을 통해, 불완전한 지식 기반에서도 실용적 추론을 가능하게 한다.

형식 체계의 유연성 확장에 대하여. 고전 형식 체계는 공리 집합이 고정되면 도출 가능한 정리 집합도 고정된다. 비단조 논리는 지식 기반의 변화에 따라 도출 가능한 결론 집합이 동적으로 변화하는 체계를 제공한다. 이 동적 특성은 고정된 형식 체계에서 발생하는 불완전성의 실천적 영향을 완화한다. 형식 체계가 결정할 수 없는 명제에 대해, 비단조 논리는 잠정적 판단을 내리고 이후 정보에 따라 이를 수정할 수 있다.

5. 비단조 논리의 계산 복잡도

비단조 논리의 유연성은 계산적 비용의 증가를 수반한다. 기본값 논리에서 확장의 존재 여부 판정은 \Sigma_2^P-완전이며, 이는 NP-완전 문제보다 엄격히 어렵다고 추정되는 복잡도 클래스에 속한다. 외접법에서의 추론 역시 \Pi_2^P-완전이다.

구체적으로, 기본값 논리에서 다음의 문제들이 분석되었다.

이 높은 계산 복잡도는 비단조 논리의 실용적 적용을 제한하는 요인이다. 다항 시간 내에 결정 가능한 부분 문제의 식별과, 근사 알고리즘의 개발이 이 제약에 대한 실천적 대응이다.

6. 인공지능에서의 비단조 추론의 적용

비단조 논리는 인공지능의 여러 핵심 과제에서 이론적 기반을 제공한다.

**상식 추론(commonsense reasoning)**에서 비단조 논리는 기본값과 예외를 형식적으로 처리한다. “새는 일반적으로 난다“와 같은 일반화는 비단조적 기본값 규칙으로 표현되며, “펭귄은 날지 못한다“와 같은 예외는 이 기본값을 무효화하는 추가 정보로 처리된다.

**행동 계획(action planning)**에서 비단조 논리는 관성 공리(frame axiom)의 문제를 해결한다. 행동이 변경하지 않는 상태는 기본적으로 유지된다는 가정은 비단조적 추론의 자연스러운 적용이다. 상황 미적분(situation calculus)에서의 프레임 문제에 대한 Reiter(1991)의 해법은 기본값 논리에 기반한다.

**진단 추론(diagnostic reasoning)**에서 비단조 논리는 관찰된 증상으로부터 원인을 추론하되, 새로운 증상이 추가되면 진단을 수정하는 과정을 형식화한다. 이는 의료 진단, 기계 고장 진단 등의 실용적 영역에서 활용된다.

7. 답집합 프로그래밍과 실용적 구현

답집합 프로그래밍(Answer Set Programming, ASP)은 비단조 논리의 실용적 구현 패러다임이다. Gelfond와 Lifschitz(1988)가 제안한 안정 모델 의미론(stable model semantics)에 기반하며, 논리 프로그램의 안정 모델(stable model, 또는 답집합)을 계산함으로써 비단조적 추론을 수행한다.

ASP의 규칙은 다음의 형태를 갖는다.

h \leftarrow b_1, \ldots, b_m, \text{not } c_1, \ldots, \text{not } c_n

여기서 “not“은 부정에 의한 실패(negation as failure)를 나타낸다. b_1, \ldots, b_m이 모두 참이고 c_1, \ldots, c_n 중 어느 것도 참으로 도출되지 않을 때, h를 도출한다.

현대 ASP 풀기—Clingo(Gebser et al., 2011), DLV(Leone et al., 2006)—는 SAT 풀기의 기법을 활용하여 답집합을 효율적으로 계산하며, 조합 최적화, 계획, 구성(configuration) 등의 실용적 문제에 적용된다.

8. 비단조 논리의 한계와 불완전성 정리의 잔존하는 제약

비단조 논리가 불완전성 정리의 실천적 영향을 완화하는 데 기여하지만, 근본적 한계가 잔존한다.

첫째, 비단조 논리의 형식화 자체가 형식 체계 내에서 이루어지는 한, 이 형식화에 대해 불완전성 정리가 적용될 수 있다. 비단조 논리의 메타이론(metatheory)—확장의 존재성, 추론의 건전성 등—을 형식적으로 증명하려면 충분히 강력한 형식 체계가 필요하며, 이 체계는 불완전성 정리의 제약을 받는다.

둘째, 비단조 논리의 비단조성은 진리 보존(truth-preservation)의 포기를 의미한다. 비단조적 추론의 결론은 잠정적이며 후속 정보에 의해 철회될 수 있다. 이는 유연성의 원천인 동시에, 추론의 신뢰성에 대한 보장을 약화시킨다.

셋째, 비단조 논리 체계에서 다중 확장(multiple extensions)의 존재는 추론의 결정성(determinacy)을 훼손한다. 동일한 전제 집합에서 상호 모순되는 결론을 포함하는 서로 다른 확장이 존재할 수 있으며, 어느 확장을 채택할지에 대한 메타수준의 선택 기준이 필요하다. 이 선택 기준 자체의 정당화는 또 다른 이론적 문제를 야기한다.

이러한 분석은 비단조 논리가 불완전성 정리의 실천적 영향을 완화하는 유효한 전략이지만, 불완전성 정리가 설정하는 근본적 한계를 제거하는 것은 아님을 확인한다. 비단조 논리는 형식적 추론의 유연성을 확장하여 불완전한 정보 하에서의 추론을 가능하게 하나, 추론 체계의 원리적 완전성을 달성하는 것은 아니다.