기본 논리

**기본 논리**(default logic)는 비단조 논리의 일종으로, 기본 가정(default assumptions)을 이용한 추론을 공식화하기 위해 레이먼드 라이터가 제안했다.

기본 논리는 “기본적으로 무엇은 참이다”와 같은 사실을 표현할 수 있다. 반면 표준 논리는 무엇이 참이거나 거짓이라는 사실만을 표현할 수 있다. 추론은 대다수의 경우 참이지만 항상 그렇지는 않은 사실을 포함하는 경우가 많기 때문에 이는 문제가 된다. 고전적인 예로 “새는 일반적으로 난다”가 있다. 이 규칙을 표준 논리로 표현하려면, 펭귄은 날지 못한다는 사실과 모순되는 “모든 새는 난다”라고 하거나, 규칙에 대한 모든 예외를 명시해야 하는 “펭귄도 아니고 타조도 아니고 ...이 아닌 모든 새는 난다”라고 해야 한다. 기본 논리는 모든 예외를 명시적으로 언급하지 않고도 이와 같은 추론 규칙을 공식화하는 것을 목표로 한다.

## 기본 논리의 구문
기본 이론(default theory)은 쌍 \langle W, D \rangle이다. 는 배경 이론(background theory)이라 불리는 논리식의 집합으로, 확실히 알려진 사실들을 공식화한다. 는 기본 규칙(default rules)의 집합으로, 각 규칙은 다음과 같은 형태를 가진다.

: \frac{\mathrm{Prerequisite : Justification}_1, \dots , \mathrm{Justification}_n}{\mathrm{Conclusion}}

이 기본 규칙에 따르면, 만약 (전제조건)가 참이라고 믿고, i = 1, \dots, n에 대한 각 \mathrm{Justification}_i(정당화)가 현재의 믿음과 일치한다면(모순되지 않는다면), (결론)이 참이라고 믿게 된다.

에 있는 논리식과 기본 규칙의 모든 식은 원래 1차 논리 식으로 가정되었으나, 잠재적으로 임의의 형식 논리 식일 수 있다. 이들이 명제 논리 식인 경우는 가장 많이 연구된 사례 중 하나이다.

### 예시
“새는 일반적으로 난다”라는 기본 규칙은 다음과 같은 기본 규칙으로 공식화된다.

:D = \left\{ \frac{\mathrm{Bird}(X) : \mathrm{Flies}(X)}{\mathrm{Flies}(X)} \right\}

이 규칙은 "만약 가 새이고, 그가 난다고 가정할 수 있다면, 그가 난다고 결론지을 수 있다"는 의미이다. 새에 관한 몇 가지 사실을 포함하는 배경 이론은 다음과 같다.

:W = \{ \mathrm{Bird}(\mathrm{Condor}), \mathrm{Bird}(\mathrm{Penguin}), \neg \mathrm{Flies}(\mathrm{Penguin}), \mathrm{Flies}(\mathrm{Bee}) \}.

이 기본 규칙에 따르면, 전제조건 가 참이고 정당화 가 현재 알려진 사실과 모순되지 않으므로 콘도르는 난다. 반대로 은 이라는 결론을 허용하지 않는다. 기본 규칙의 전제조건인 이 참일지라도, 정당화 이 알려진 사실과 모순되기 때문이다. 이 배경 이론과 기본 규칙에서 는 결론지을 수 없는데, 기본 규칙은 오직 로부터 를 도출하는 것만 허용하며 그 반대는 허용하지 않기 때문이다. 결과로부터 추론 규칙의 전제를 도출하는 것은 결과에 대한 일종의 설명이며, 이는 귀추법의 목표이다.

흔히 쓰이는 기본 가정 중 하나는 참이라고 알려지지 않은 것은 거짓이라고 믿는 것이다. 이는 폐세계 가설로 알려져 있으며, 기본 논리에서는 모든 사실 에 대해 다음과 같은 기본 규칙을 사용하여 공식화된다.

: \frac{:{\neg}F}{{\neg}F}

예를 들어, 컴퓨터 언어 프롤로그는 부정을 다룰 때 일종의 기본 가정을 사용한다. 만약 부정 원자(negative atom)가 참임을 증명할 수 없다면, 그것은 거짓으로 간주된다.
그러나 프롤로그는 소위 부정 허위 가정을 사용한다는 점에 유의해야 한다. 인터프리터가 원자 \neg F를 평가해야 할 때, 그것은 가 참임을 증명하려 시도하고, 실패하면 \neg F가 참이라고 결론짓는다. 반면 기본 논리에서 \neg F를 정당화로 갖는 기본 규칙은 오직 \neg F가 현재의 지식과 일치할 때만 적용될 수 있다.

### 제약
전제조건이 없는(또는 전제조건이 항진식인 것과 동등한) 기본 규칙을 무조건적(categorical) 또는 전제조건 없는 기본 규칙이라고 한다. 정당화가 단 하나이며 그것이 결론과 동등한 기본 규칙을 정상(normal) 기본 규칙이라고 한다. 무조건적이면서 동시에 정상인 기본 규칙을 초정상(supernormal) 기본 규칙이라고 한다. 모든 정당화가 결론을 함축하는 기본 규칙을 준정상(seminormal) 기본 규칙이라고 한다. 기본 이론에 포함된 모든 기본 규칙이 각각 무조건적, 정상, 초정상, 준정상인 경우 그 기본 이론을 무조건적, 정상, 초정상, 준정상 기본 이론이라고 부른다.

## 기본 논리의 의미론
기본 규칙의 전제조건이 이론에 의해 함축되고 정당화가 모두 이론과 **일치할** 때, 그 규칙을 이론에 적용할 수 있다. 기본 규칙을 적용하면 그 결론이 이론에 추가된다. 그 후 결과 이론에 다른 기본 규칙들이 적용될 수 있다. **더 이상 어떤 기본 규칙도 적용할 수 없는 상태의 이론을 기본 이론의 확장(extension)이라고 한다.** 기본 규칙들은 서로 다른 순서로 적용될 수 있으며, 이는 서로 다른 확장으로 이어질 수 있다. 닉슨 다이아몬드 예시는 두 개의 확장을 갖는 기본 이론이다.

:
\left\langle
\left\{
\frac{\mathrm{Republican}(X):\neg \mathrm{Pacifist}(X)}{\neg \mathrm{Pacifist}(X)},
\frac{\mathrm{Quaker}(X):\mathrm{Pacifist}(X)}{\mathrm{Pacifist}(X)}
\right\},
\left\{\mathrm{Republican}(\mathrm{Nixon}), \mathrm{Quaker}(\mathrm{Nixon})\right\}
\right\rangle


닉슨은 공화당원이자 퀘이커교도이므로 두 기본 규칙을 모두 적용할 수 있다. 그러나 첫 번째 규칙을 적용하면 닉슨은 평화주의자가 아니라는 결론에 이르게 되어 두 번째 규칙을 적용할 수 없게 된다. 마찬가지로 두 번째 규칙을 적용하면 닉슨은 평화주의자라는 결론을 얻게 되어 첫 번째 규칙을 적용할 수 없게 된다. 따라서 이 특정 기본 이론은 이 참인 확장과 이 거짓인 확장, 두 가지 확장을 가진다.

기본 논리의 원래 의미론은 함수의 고정점에 기반했다. 다음은 이와 동등한 알고리즘적 정의이다. 만약 기본 규칙이 자유 변수를 포함하는 식을 가지고 있다면, 그것은 이 변수들에 값을 부여하여 얻을 수 있는 모든 기본 규칙의 집합을 나타내는 것으로 간주된다. 기본 규칙 \frac{\alpha:\beta_1,\ldots,\beta_n}{\gamma}이 명제 이론 에 적용 가능하려면 T \models \alpha이고 모든 이론 T \cup \{\beta_i\}가 일관되어야 한다. 이 기본 규칙을 에 적용하면 이론 T \cup \{\gamma\}가 된다. 확장은 다음 알고리즘을 적용하여 생성할 수 있다.

 T = W         /* 현재 이론 */
 A = 0         /* 지금까지 적용된 기본 규칙의 집합 */
 &nbsp;
               /* 일련의 기본 규칙 적용 */
 **while** A에 속하지 않으면서 T에 적용 가능한 기본 규칙 d가 존재함
     d의 결론을 T에 추가
     d를 A에 추가
 &nbsp;
               /* 최종 일관성 검사 */
 **if**
     A의 모든 기본 규칙 d에 대하여
         T가 d의 모든 정당화와 일치함
 **then**
     T를 출력

이 알고리즘은 비결정적 알고리즘인데, 주어진 이론 에 대해 여러 기본 규칙을 선택적으로 적용할 수 있기 때문이다. 닉슨 다이아몬드 예시에서 첫 번째 규칙을 적용하면 두 번째 규칙을 적용할 수 없는 이론으로 이어지고 그 반대도 마찬가지이다. 결과적으로 두 개의 확장이 생성되는데, 하나는 닉슨이 평화주의자인 경우이고 다른 하나는 닉슨이 평화주의자가 아닌 경우이다.

적용된 모든 기본 규칙의 정당화에 대한 최종 일관성 검사는 일부 이론이 어떠한 확장도 갖지 않을 수 있음을 시사한다. 특히, 적용 가능한 모든 가능한 기본 규칙 시퀀스에 대해 이 검사가 실패할 때마다 이런 일이 발생한다. 다음 기본 이론은 확장이 없다.

:
\left\langle
\left\{
\frac{:A(b)}{\neg A(b)}
\right\},
\emptyset
\right\rangle


A(b)가 배경 이론과 일치하므로 기본 규칙을 적용할 수 있고, 이로 인해 A(b)가 거짓이라는 결론에 도달한다. 그러나 이 결과는 첫 번째 기본 규칙을 적용하기 위해 세웠던 가정을 훼손한다. 따라서 이 이론은 확장이 없다.

정상 기본 이론에서는 모든 기본 규칙이 정상이다. 즉, 각 기본 규칙은 \frac{\phi : \psi}{\psi} 형태를 가진다. 정상 기본 이론은 적어도 하나의 확장을 가짐이 보장된다. 나아가 정상 기본 이론의 확장들은 서로 모순된다. 즉, 서로 일치하지 않는다.

### 함축
기본 이론은 확장을 0개, 1개 또는 그 이상 가질 수 있다. 기본 이론으로부터 논리식의 함축은 두 가지 방식으로 정의될 수 있다.

; 회의적(Skeptical) : 논리식이 모든 확장에 의해 함축될 때 그 기본 이론에 의해 함축된다.

; 신용적(Credulous) : 논리식이 적어도 하나의 확장에 의해 함축될 때 그 기본 이론에 의해 함축된다.

예를 들어 닉슨 다이아몬드 예시 이론은 두 개의 확장을 가지며, 하나는 닉슨이 평화주의자인 경우이고 다른 하나는 아닌 경우이다. 결과적으로 이나  모두 회의적으로 함축되지 않지만, 둘 다 신용적으로는 함축된다. 이 예시에서 보듯이 기본 이론의 신용적 결과들은 서로 모순될 수 있다.

### 대안적 기본 추론 규칙

다음의 기본 논리를 위한 대안적 추론 규칙들은 모두 원래 시스템과 동일한 구문을 기반으로 한다.

; 정당화형(Justified): 기본 규칙을 적용했을 때 집합 가 이미 적용된 기본 규칙의 정당화와 모순되게 된다면 해당 규칙을 적용하지 않는다는 점이 원래 것과 다르다.

; 간결형(Concise): 기본 규칙의 결론이 아직 에 의해 함축되지 않은 경우에만 규칙을 적용한다(정확한 정의는 이보다 복잡하며, 이것은 주요 아이디어일 뿐이다).

; 제약형(Constrained): 배경 이론, 적용된 모든 기본 규칙의 정당화, 그리고 (현재 규칙을 포함한) 적용된 모든 기본 규칙의 결론으로 구성된 집합이 일관된 경우에만 규칙을 적용한다.

; 합리형(Rational): 제약형 기본 논리와 유사하지만, 추가할 기본 규칙의 결론은 일관성 검사에서 고려되지 않는다.

; 신중형(Cautious): 적용 가능하지만 서로 충돌하는 기본 규칙들(닉슨 다이아몬드 예시와 같은 경우)은 적용하지 않는다.

정당화형과 제약형 추론 규칙 버전은 모든 기본 이론에 대해 적어도 하나의 확장을 할당한다.

## 기본 논리의 변형

다음의 기본 논리 변형들은 구문과 의미론 모두에서 원래의 것과 차이가 있다.

; 단언적 변형(Assertional variants) : 단언(assertion)은 논리식과 논리식 집합의 쌍 \langle p: \{r_1,\ldots,r_n\} \rangle이다. 이러한 쌍은 가 참인 것을 증명하기 위해 논리식 r_1,\ldots,r_n이 일관되다고 가정되었음을 나타낸다. 단언적 기본 이론은 단언적 이론(배경 이론)과 원래 구문에서 정의된 기본 규칙들의 집합으로 구성된다. 단언적 이론에 기본 규칙이 적용될 때마다 그 결론과 정당화 집합으로 구성된 쌍이 이론에 추가된다. 다음 의미론들은 단언적 이론을 사용한다.

* 누적 기본 논리(Cumulative default logic)
* 가정 전념 기본 논리(Commitment to assumptions default logic)
* 유사 기본 논리(Quasi-default logic)

; 약한 확장(Weak extensions) : 배경 이론과 적용된 기본 규칙들의 결론으로 구성된 이론에서 전제조건이 유효한지 확인하는 대신, 생성될 확장 자체에서 전제조건의 유효성을 확인한다. 즉, 확장 생성 알고리즘은 이론을 추측하는 것으로 시작하여 배경 이론 대신 그것을 사용한다. 확장 생성 과정에서 나온 결과는 처음에 추측한 이론과 동등할 때만 실제로 확장이 된다. 이 변형은 원칙적으로 자기인식 논리(autoepistemic logic)와 관련이 있는데, 여기서 이론 \Box x \rightarrow x는 \Box x가 참이라고 가정할 때 가 참이라는 모델을 가지며, 식 \Box x \rightarrow x가 초기 가정을 뒷받침하기 때문이다.

; 선언적 기본 논리(Disjunctive default logic) : 기본 규칙의 결론이 단일 논리식이 아닌 논리식의 집합이다. 기본 규칙이 적용될 때마다 그 결론 중 적어도 하나가 비결정적으로 선택되어 참이 된다.

; 기본 규칙의 우선순위 : 기본 규칙 간의 상대적 우선순위를 명시적으로 지정할 수 있다. 이론에 적용 가능한 기본 규칙들 중 가장 선호되는 것들 중 하나만 적용할 수 있다. 일부 의미론은 우선순위를 명시적으로 지정할 필요가 없으며, 대신 더 구체적인 기본 규칙(더 적은 경우에 적용 가능한 규칙)을 덜 구체적인 규칙보다 선호한다.

; 통계적 변형 : 통계적 기본 규칙은 오류 빈도에 대한 상한선이 첨부된 기본 규칙이다. 즉, 기본 규칙이 적용될 때 최대 그 비율만큼은 잘못된 추론 규칙일 수 있다고 가정한다.

## 변환
기본 이론은 다른 논리의 이론으로 변환될 수 있으며 그 반대도 가능하다. 다음과 같은 변환 조건들이 고려되었다.

; 결과 보존(Consequence-Preserving) : 원래 이론과 변환된 이론이 동일한 (명제적) 결과를 가진다.

; 충실(Faithful) : 이 조건은 기본 논리의 두 변형 사이를 변환하거나, 기본 논리와 확장과 유사한 개념(예: 양상 논리의 모델)이 존재하는 논리 사이를 변환할 때만 의미가 있다. 원래 이론과 변환된 이론의 확장(또는 모델) 사이에 매핑(일반적으로 전단사 함수)이 존재하면 변환은 충실하다.

; 모듈식(Modular) : 기본 규칙과 배경 이론을 개별적으로 변환할 수 있는 경우, 기본 논리에서 다른 논리로의 변환은 모듈식이다. 또한 배경 이론에 논리식을 추가하면 변환 결과에도 새 논리식을 추가하는 것으로 이어진다.

; 동일 알파벳(Same-Alphabet) : 원래 이론과 변환된 이론이 동일한 알파벳을 기반으로 구축된다.

; 다항 시간(Polynomial) : 변환의 실행 시간이나 생성된 이론의 크기가 원래 이론의 크기에 대해 다항식이어야 한다.

변환은 일반적으로 충실하거나 적어도 결과를 보존해야 하며, 모듈성과 동일 알파벳 조건은 때때로 무시된다.

명제 기본 논리와 다음 논리들 사이의 변환 가능성이 연구되었다.

* 고전 명제 논리
* 자기인식 논리
* 준정상 이론으로 제한된 명제 기본 논리
* 기본 논리의 대안적 의미론
* 한정(Circumscription)

변환의 존재 여부는 어떤 조건이 부과되느냐에 따라 달라진다. 명제 기본 논리에서 고전 명제 논리로의 변환은 다항 위계가 붕괴되지 않는 한 항상 다항식 크기의 명제 이론을 생성할 수는 없다. 자기인식 논리로의 변환은 모듈성이나 동일 알파벳 사용 요구 여부에 따라 존재 여부가 달라진다.

## 복잡도
기본 논리에 관한 다음 문제들의 계산 복잡도가 알려져 있다.

; 확장의 존재성 : 명제 기본 이론이 적어도 하나의 확장을 갖는지 결정하는 것은 \Sigma^P_2-완전이다.

; 회의적 함축 : 명제 기본 이론이 명제식을 회의적으로 함축하는지 결정하는 것은 \Pi^P_2-완전이다.

; 신용적 함축 : 명제 기본 이론이 명제식을 신용적으로 함축하는지 결정하는 것은 \Sigma^P_2-완전이다.

; 확장 확인 : 명제식이 명제 기본 이론의 확장과 동등한지 결정하는 것은 \Delta^{P[\log]}_2-완전이다.

; 모델 확인 : 명제 해석이 명제 기본 이론의 확장에 대한 모델인지 결정하는 것은 \Sigma^P_2-완전이다.

## 구현
기본 논리를 구현하는 네 가지 시스템으로는 [ftp://www.cs.engr.uky.edu/cs/manuscripts/deres.ps DeReS], XRay, GADeL , 그리고 가 있다.

## 같이 보기
* 응답 집합 프로그래밍
* 가추 논리
* 비단조 논리
* 논리형 프로그래밍

## 각주
* G. Antoniou (1999). A tutorial on default logics. ACM Computing Surveys, 31(4):337-359.
* M. Cadoli, F. M. Donini, P. Liberatore, and M. Schaerf (2000). Space efficiency of propositional knowledge representation formalisms . Journal of Artificial Intelligence Research, 13:1-31.
* P. Cholewinski, V. Marek, and M. Truszczynski (1996). Default reasoning system DeReS. In Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR'96), pages 518-528.
* J. Delgrande and T. Schaub (2003). On the relation between Reiter's default logic and its (major) variants. In Seventh European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2003), pages 452-463.
* J. P. Delgrande, T. Schaub, and W. K. Jackson (1994). Alternative approaches to default logic. Artificial Intelligence, 70:167-237.
* G. Gottlob (1992). Complexity results for nonmonotonic logics. Journal of Logic and Computation, 2:397-425.
* G. Gottlob (1995). Translating default logic into standard autoepistemic logic. Journal of the ACM, 42:711-740.
* T. Imielinski (1987). Results on translating defaults to circumscription. Artificial Intelligence, 32:131-146.
* T. Janhunen (1998). On the intertranslatability of autoepistemic, default and priority logics, and parallel circumscription. In Proceedings of the Sixth European Workshop on Logics in Artificial Intelligence (JELIA'98), pages 216-232.
* T. Janhunen (2003). Evaluating the effect of semi-normality on the expressiveness of defaults. Artificial Intelligence, 144:233-250.
* H. E. Kyburg and C-M. Teng (2006). Nonmonotonic Logic and Statistical Inference. Computational Intelligence, 22(1): 26-51.
* P. Liberatore and M. Schaerf (1998). The complexity of model checking for propositional default logics. In Proceedings of the Thirteenth European Conference on Artificial Intelligence (ECAI'98), pages 18–22.
* W. Lukaszewicz (1988). Considerations on default logic: an alternative approach. Computational Intelligence, 4(1):1-16.
* W. Marek and M. Truszczynski (1993). Nonmonotonic Logics: Context-Dependent Reasoning. Springer.
* A. Mikitiuk and M. Truszczynski (1995). Constrained and rational default logics. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI'95), pages 1509-1517.
* P. Nicolas, F. Saubion and I. Stéphan (2001). Heuristics for a Default Logic Reasoning System . International Journal on Artificial Intelligence Tools, 10(4):503-523.
* R. Reiter (1980). A logic for default reasoning. Artificial Intelligence, 13:81-132.
* T. Schaub, S. Brüning, and P. Nicolas (1996). XRay: A prolog technology theorem prover for default reasoning: A system description. In Proceedings of the Thirteenth International Conference on Automated Deduction (CADE'96), pages 293-297.
* G. Wheeler (2004). A resource bounded default logic. In Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR-04), Whistler, British Columbia, 416-422.
* G. Wheeler and C. Damasio (2004). An Implementation of Statistical Default Logic. In Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004), LNCS Series, Springer, pages 121-133.

## 외부 링크
* Schmidt, Charles F. RCI.Rutgers.edu, Default Logic. Retrieved August 10, 2004.
* Ramsay, Allan (1999). UMIST.ac.uk, Default Logic. Retrieved August 10, 2004.
* Stanford.edu, Defeasible reasoning, 스탠퍼드 철학 백과사전.

분류:지식 표현
분류:논리 프로그래밍
분류:비고전 논리