폐쇄계 가정

지식표현에 사용되는 논리학의 형식 체계에서 폐쇄세계 가정(CWA)은 사실인 진술도 사실로 알려져 있다는 가정이다.따라서 반대로 현재 사실로 알려져 있지 않은 것은 거짓이다.같은 이름은 레이먼드 리페어(Raymond Repeat)가 이 가정을 논리적으로 공식화한 것을 가리키기도 한다.^[1]폐쇄적인 세계 가정과 반대되는 것은 지식의 부족이 거짓을 의미하지 않는다는 것을 명시하는 개방적인 가정(OWA)이다.CWA 대 OWA에 대한 결정은 개념의 동일한 개념들을 가진 개념 표현식의 실제 의미론의 이해를 결정한다.자연어 의미론의 성공적인 공식화는 일반적으로 암묵적 논리 배경이 CWA에 기초하는지 OWA에 기초하는지 여부에 대한 노골적인 폭로를 피할 수 없다.

실패라고 부정하는 것은 사실이라고 증명될 수 없는 모든 술어를 거짓으로 믿는 것과 같기 때문에 폐쇄적인 세계 가정과 관련이 있다.

예

지식관리의 맥락에서, 폐쇄세계 가정은 (1) 지식기반이 완성되었다고 알려진 경우(예: 모든 직원의 기록을 포함하는 기업 데이터베이스)와 (2) 지식기반이 불완전하다고 알려져 있지만 "최상의" 확답은 불완전한 정보에서 도출되어야 하는 경우 등 최소한 두 가지 상황에서 사용된다.예를 들어, 데이터베이스에 주어진 기사를 작업한 다음 표의 보고 편집자들이 포함되어 있다면, 형식논리에 관한 기사를 편집하지 않은 사람들에 대한 질의가 "Sarah Johnson"을 반환할 것으로 예상된다.

편집
편집자	기사
존 도	형식 논리학
조슈아 A.노턴	형식 논리학
세라 존슨	공간 데이터베이스 소개
찰스 폰지	형식 논리학
엠마 리춘	형식 논리학

폐쇄적인 세계 가정에서는 테이블이 완성되었다고 가정한다(모든 편집자와 기사 관계를 나열한다). 사라 존슨만이 형식논리에 관한 기사를 편집하지 않았다.이와는 대조적으로, 오픈월드 가정과 달리 테이블에는 모든 편집자-기사 튜플이 포함되어 있다고 가정하지 않으며, 누가 형식논리 기사를 편집하지 않았는지에 대한 답은 알 수 없다.표에 나열되지 않은 편집자 수가 알 수 없고, 표에도 나열되지 않은 사라 존슨에 의해 편집된 기사 수가 알 수 없다.

논리 형식화

형식논리학에서 폐쇄세계 가정의 첫 공식화는 지식기반에 현재 그것에 수반되지 않는 문자의 부정을 추가하는 데 있다.이 추가의 결과는 지식 기반이 Horn 형태인 경우 항상 일관성이 있지만, 그렇지 않으면 일관성이 보장되지 않는다.예를 들어, 기술 자료

\{영어(Fred)\vee Ilish(Fred)\}

$English(Fred)$ $English(Fred)$ $English(Fred)$ s $English(Fred)$ ( $English(Fred)$ $English(Fred)$ 도 $English(Fred)$ , I $Irish(Fred)$ i $Irish(Fred)$ $Irish(Fred)$ ( $Irish(Fred)$ $Irish(Fred)$ 도 포함하지 않는다 $Irish(Fred)$

이 두 리터럴의 부정을 지식 베이스에 추가하면

\{영어(Fred)\vee Irish(Fred),\neg English(Fred),\neg Irish(Fred)\}

일관성이 없는 거야즉, 폐쇄적인 세계 가정의 이러한 공식화는 때로는 일관된 지식 기반을 일관성 없는 지식기반을 일관성 없는 지식기초로 변화시킨다. $K$ $K$ 의 모든 Herbrand 모델의 교차점이 K ${\displaystyle$ K $}$ 의 모델인 $K$ 경우 정확히 $K$ 기반K {\ $displaystyle$ K}에 비일관성을 도입하지 않는다 $K$ 제안 사례에서 이 조건은 $K$ ${\displaystyle$ K $}$ 이 단일 mi를 갖는 $K$ 것과 동일하다.nimal 모델, 다른 모델에 True에 할당된 변수의 하위 집합이 없는 경우 모형이 최소인 경우.

이 문제로 고통받지 않는 대체 공식화가 제안되었다.다음 설명에서 고려된 지식 기반 $K$ $K$ 을(를) 제안적인 것으로 가정한다 $K$ .모든 경우에 있어서 폐쇄형 가정의 공식화는 $K$ $K$ 에 대해 $K$ "부정이 자유로운" 공식을 $K$ K ${\displaystyle$ K}, 즉 거짓이라고 가정할 수 있는 공식을 K {\displaysty K $}$ 에 추가하는 것에 기초한다.즉, 지식 $기반$ K {\ $displaystyle$ K $}$ 에 적용된 폐쇄형 가정은 지식 $K$ 기반(knowledge base K {\displaystyle K}

K\cup \{\neg f~|~f\in F\}

\

f

f

~F

}

{\displaystyle K\cup \{\

neg

f~~f\in

F

K\cup \{\neg f~|~f\in F\}

$K$ $K$ 에서 부정이 자유로운 $F$ 의 $F$ F{\ $displaystyle F}$ 은(는) 여러 가지 방법으로 정의될 $K$ 수 있으며, 폐쇄 세계 가정을 서로 다르게 공식화할 수 있다. $f$ 은 f $f$ 이(가) 다양한 공식화에서 부정이 자유롭다는 $f$ 정의다.

CWA(폐쇄 세계 가정): $f$ $f$ 은 $f$ (는) $K$ $K$ 이(가) 수반하지 않는 양의 리터럴이다 $K$

GCWA(일반 CWA): $f$ ${\displaystyle f$ $}$ 은 $f$ (는) $K\not \vdash c$ $K\not \vdash c$ $절$ c ${\displaystyle K\not \vdash$ c $}$ 에 $c$ 대해 K $K\not \vdash c$ $K\not \vdash c\vee f$ c $K\not \vdash c\vee f$ f {\ $displaystyle K\not \vdash c\ve f$ ^[2]을(를)을(를) 포함할 수 있는 양의 문자다.

EGCWA(확장 GCWA): 위와 동일하지만, $f$ $f$ 은(는) 양의 리터럴을 결합한 것이다 $f$ .

CCWA(관심 CWA): GCWA와 동일하지만, 양수 조항은 주어진 세트의 양의 리터럴과 다른 세트의 (양수 및 음수) 리터럴로 구성된 경우에만 고려된다.

ECWA(확장 CWA): CCWA와 유사하지만 $f$ ${\displaystyle$ f $}$ 은(는) 특정 집합의 리터럴을 포함하지 않는 임의의 공식이다 $f$ .

ECWA와 할례의 형식주의는 명제 이론에서 일치한다.^[3]^[4]질의 응답의 복잡성(폐쇄계 가정 하에서 공식이 다른 공식이 수반되는지 여부를 확인하는 것)은 일반적으로 일반 공식을 위한 다항식 계층의 두 번째 수준에 있으며, Horn 공식의 경우 P에서 coNP까지 범위가 다양하다.원래 폐쇄 세계 가정이 비일관성을 도입하는지 여부를 확인하는 것은 NP 신탁에 대한 로그 수만큼의 통화를 필요로 하지만, 현재 이 문제의 정확한 복잡성은 알려져 있지 않다.^[5]

모든 술어에 대해 닫힌 세계를 가정할 수는 없지만, 그 중 일부는 닫힌 것으로 알려져 있는 상황에서는 부분적으로 닫힌 세계 가정을 사용할 수 있다.이 체제는 일반적으로 지식기반이 개방되어 있다고 생각하는데, 즉 잠재적으로 불완전하다고 생각하지만, 완전한 주장을 사용하여 닫힌 지식기반의 일부를 명시할 수 있다.^[6]

참고 항목

참조

^ 반복한다, 레이먼드(1978)"폐쇄된 세계 데이터 베이스에"갈레르, 헤르베, 밍커, 잭.논리 및 데이터 베이스.플레넘 프레스 119-140 페이지 ISBN 9780306400605.
^ Minker, Jack (1982), "On indefinite databases and the closed world assumption", 6th Conference on Automated Deduction, Lecture Notes in Computer Science, vol. 138, Springer Berlin Heidelberg, pp. 292–308, doi:10.1007/BFb0000066, ISBN 978-3-540-11558-8
^ 에이터, 토마스; 고틀롭, 게오르크 (1993년 6월)"제안적 할례와 확장된 폐쇄 세계 추론은 π 2 ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ 2 p - ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ 2 ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ - ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ p - o p - $o$ e ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ e e ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ ${\displaystyle \{2}^{p}}}\Pi _$ {2 $}^{p}-완료}"$ 이다. ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ 이론 컴퓨터 과학. 114 (2): 231–245. doi:10.1016/0304-3975(93)90073-3.ISSN 0304-3975.
^ 리프시츠, 블라디미르 (1985년 11월)"폐쇄형 데이터베이스 및 할례"인공지능. 27(2): 229–235. doi:10.1016/0004-3702(85)90055-4.ISSN 0004-3702.
^ 카돌리, 마르코, 렌제리니, 마우리치오(1994년 4월)"명제적으로 폐쇄적인 세계 추론과 할례의 복잡성"컴퓨터 및 시스템 과학 저널. 48 (2): 255–310. doi:10.1016/S0022-0000(05)80004-2.ISSN 0022-0000.
^ Razniewski, Simon; Savkovic, Ognjen; Nutt, Werner (2015). "Turning The Partial-closed World Assumption Upside Down" (PDF). {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

외부 링크

[1] 반복한다, 레이먼드(1978)"폐쇄된 세계 데이터 베이스에"갈레르, 헤르베, 밍커, 잭.논리 및 데이터 베이스.플레넘 프레스 119-140 페이지 ISBN 9780306400605.

[2] Minker, Jack (1982), "On indefinite databases and the closed world assumption", 6th Conference on Automated Deduction, Lecture Notes in Computer Science, vol. 138, Springer Berlin Heidelberg, pp. 292–308, doi:10.1007/BFb0000066, ISBN 978-3-540-11558-8

[3] 에이터, 토마스; 고틀롭, 게오르크 (1993년 6월)"제안적 할례와 확장된 폐쇄 세계 추론은 π 2 ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ 2 p - ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ 2 ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ - ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ p - o p - $o$ e ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ e e ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ ${\displaystyle \{2}^{p}}}\Pi _$ {2 $}^{p}-완료}"$ 이다. ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$ 이론 컴퓨터 과학. 114 (2): 231–245. doi:10.1016/0304-3975(93)90073-3.ISSN 0304-3975.

[4] 리프시츠, 블라디미르 (1985년 11월)"폐쇄형 데이터베이스 및 할례"인공지능. 27(2): 229–235. doi:10.1016/0004-3702(85)90055-4.ISSN 0004-3702.

[5] 카돌리, 마르코, 렌제리니, 마우리치오(1994년 4월)"명제적으로 폐쇄적인 세계 추론과 할례의 복잡성"컴퓨터 및 시스템 과학 저널. 48 (2): 255–310. doi:10.1016/S0022-0000(05)80004-2.ISSN 0022-0000.

[PCWA2015-6] Razniewski, Simon; Savkovic, Ognjen; Nutt, Werner (2015). "Turning The Partial-closed World Assumption Upside Down" (PDF). {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[1]

[2]

[3]

[4]

[5]

[6]

Search

폐쇄계 가정

네임스페이스

더

목차

예

논리 형식화

참고 항목

참조

외부 링크