폐세계 가설

3. 논리적 형식화

형식 논리에서 폐세계 가설을 처음 형식화할 때는 지식 베이스에 포함되지 않은 리터럴(참 또는 거짓으로 판별 가능한 명제)의 부정(¬)을 지식 베이스에 추가했다. 이 경우, 지식 베이스가 혼 절로 표현되면 일관성이 유지되지만, 그렇지 않으면 일관성이 유지되지 않을 수 있다. 예를 들어 "프레드는 영국인 또는 아일랜드인이다."라는 지식 베이스는 프레드가 영국인인지 아일랜드인인지 명확히 알 수 없다.

이때, "프레드는 영국인이 아니다"와 "프레드는 아일랜드인이 아니다"를 지식 베이스에 추가하면, "프레드는 영국인 또는 아일랜드인"이라는 기존 지식과 모순되어 일관성을 잃게 된다.

이처럼 폐세계 가설을 형식화하면 일관성 있는 지식 베이스가 일관성을 잃는 경우가 발생한다. 폐세계 가설을 도입해도 일관성이 유지되는 경우는, 지식 베이스 K의 모든 에르브랑 모델의 교집합과 K의 모델이 동일한 경우뿐이다. 명제 논리에서 이 조건은 K가 단 하나의 최소 모델만을 가지는 것과 같으며, 이는 참으로 할당된 변수의 부분 집합을 갖는 다른 모델이 존재하지 않음을 의미한다.

이러한 문제를 해결하기 위해 다른 형식화 방법들이 제안되었다.

3. 1. 다양한 형식화

• CWA(폐세계 가설): $f$는 $K$에 의해 수반되지 않는 양의 리터럴이다.
• GCWA(일반화된 CWA): $f$는 $K\; \backslash not\backslash vdash\; c$인 모든 양의 절 $c$에 대해 $K\; \backslash not\backslash vdash\; c\; \backslash vee\; f$가 성립하는 양의 리터럴이다.^[2]
• EGCWA(확장 GCWA): 위와 같지만 $f$는 양의 리터럴의 결합이다.
• CCWA(주의 CWA): GCWA와 같지만, 양의 절은 주어진 집합의 양의 리터럴과 다른 집합의 (양과 음) 리터럴로 구성된 경우에만 고려된다.
• ECWA(확장 CWA): CCWA와 유사하지만 $f$는 주어진 집합의 리터럴을 포함하지 않는 임의의 공식이다.^[3][4]

4. 부분 폐쇄 세계 가설

강한 부정을 사용한 논리 프로그램 언어는 일부 명제에 대해 폐쇄 세계 가정을 가정하고 다른 명제는 열린 세계 가정의 영역에 남겨둘 수 있게 해준다.^[9] OWA와 CWA 사이의 중간 지점은 부분 폐쇄 세계 가정(PCWA)에 의해 제공된다. PCWA 하에서, 지식 기반은 일반적으로 열린 세계 의미론 하에 처리되지만, 완전성 주장을 통해 폐쇄 세계 의미론 하에 처리되어야 하는 부분을 주장할 수 있다. PCWA는 개방된 도메인으로 인해 CWA를 적용할 수 없지만, OWA가 무엇이든 가능하다고 지나치게 믿는 상황에 특히 필요하다.^[10][11]

5. 한계 및 유의점

폐세계 가설은 지식 베이스에 명시적으로 참이라고 증명되지 않은 사실은 거짓이라고 가정하는 것이다. 이러한 가정은 유용할 수 있지만, 몇 가지 한계와 유의점이 존재한다.

• 일관성 문제: 원래의 폐세계 가설은 지식 베이스에 모순을 일으킬 수 있다. 예를 들어, "프레드는 영국인 또는 아일랜드인이다"라는 지식 베이스에 "프레드는 영국인이 아니다"와 "프레드는 아일랜드인이 아니다"를 추가하면 모순이 발생한다.
• 복잡성 문제: 폐세계 가설 하에서 어떤 사실이 참인지 확인하는 문제는 계산적으로 복잡할 수 있다. 특히, 일반적인 경우 다항식 계층의 두 번째 수준에 해당하며, 혼 절의 경우에도 P에서 coNP 사이의 복잡도를 가진다.

• CWA (Closed World Assumption): 지식 베이스에 포함되지 않은 긍정 리터럴은 거짓으로 간주한다.
• GCWA (Generalized CWA): $K\; \backslash not\backslash vdash\; c$인 모든 양의 절 $c$에 대해 $K\; \backslash not\backslash vdash\; c\; \backslash vee\; f$가 성립하는 양의 리터럴 $f$는 거짓으로 간주한다.^[2]
• EGCWA (Extended GCWA): GCWA와 유사하지만, 여러 긍정 리터럴의 결합도 거짓으로 간주할 수 있다.
• CCWA (Careful CWA): GCWA와 유사하지만, 특정 집합의 리터럴만 고려한다.
• ECWA (Extended CWA): CCWA와 유사하지만, 특정 집합에 포함되지 않는 임의의 논리식도 거짓으로 간주할 수 있다.^[3][4]

폐세계 가설 하에서는 위 표가 완전하다고 가정하고, Sarah Johnson만이 "Formal Logic" 편집에 참여하지 않은 유일한 편집자라고 결론 내릴 수 있다. 반면, 개방 세계 가설에서는 표에 모든 정보가 있다고 확신할 수 없으므로, 답을 내릴 수 없다.

참조

_[1] 서적 On Closed World Data Bases Plenum Press 1978
_[2] 간행물 On indefinite databases and the closed world assumption Springer Berlin Heidelberg 1982
_[3] 간행물 Evaluation of Queries under Closed-World Assumption. https://www.deepdyve[...] 1997
_[4] 간행물 Evaluation of Queries under Closed-World Assumption. Part II: The Hierarchical Case https://www.deepdyve[...] 2000
_[5] 논문 Propositional circumscription and extended closed-world reasoning are Π 2 p $\{\backslash displaystyle\; \backslash Pi\; \_\{2\}^\{p\}\}\; \backslash Pi^p\_2-complete$ 1993-06
_[6] 논문 Closed-world databases and circumscription 1985-11
_[7] 논문 The complexity of propositional closed world reasoning and circumscription 1994-04
_[8] 간행물 Turning The Partial-closed World Assumption Upside Down http://ceur-ws.org/V[...] 2015
_[9] 서적 Artificial Intelligence: A Modern Approach Prentice Hall 2010
_[10] 간행물 Integrity = Validity + Completeness https://dl.acm.org/d[...] 1989
_[11] 웹사이트 Turning The Partial-closed World Assumption Upside Down http://ceur-ws.org/V[...] 2015