기본 논리

Default logic

디폴트 논리레이먼드 리페어가 디폴트 가정으로 추론을 공식화하기 위해 제안한 비단조 논리다.

기본 논리는 "기본적으로 무엇인가 진실"과 같은 사실을 표현할 수 있다; 대조적으로, 표준 논리는 어떤 것이 진실이거나 어떤 것이 거짓이라는 사실만을 표현할 수 있다. 이것은 문제가 된다. 왜냐하면 추리는 대부분의 경우 사실이지만 항상 그렇지는 않은 사실들을 수반하기 때문이다. 고전적인 예는 다음과 같다: "새들은 전형적으로 날아다닌다." 이 규칙은 펭귄이 날지 않는다는 사실과 모순되는 "모든 새들이 날아다닌다"나 규칙의 모든 예외를 명시해야 하는 "펭귄이 아니고 타조도 아닌 모든 새들"에 의해 표준 논리로 표현할 수 있다. 디폴트 논리는 모든 예외를 명시적으로 언급하지 않고 이와 같은 추론 규칙을 공식화하는 것을 목표로 한다.

기본 논리 구문

기본 이론은 쌍 , 이다 W는 배경 이론이라 불리는 논리 공식의 집합으로, 확실히 알려진 사실들을 공식화한다. D기본 규칙 집합이며, 각 규칙은 다음과 같다.

이 디폴트에 따르면 전제조건이 참이라고 믿으며, a 이(가) 우리의 현재 신념과 일치한다면, 결론은 참이라고 믿게 된다.

W의 논리 공식과 디폴트에서의 모든 공식은 원래 1차 논리 공식으로 가정되었지만, 임의 형식 논리에서는 잠재적으로 공식일 수 있다. 그들이 명제논리학에서 공식화된 경우는 가장 많이 연구된 사례 중 하나이다.

기본 규칙 "birds presently fly"는 다음과 같은 기본값으로 공식화된다.

이 규칙은 "X가 새인데, 그것이 날아간다고 가정할 수 있다면, 우리는 그것이 날아간다고 결론을 내릴 수 있다"는 것을 의미한다. 새에 대한 몇 가지 사실을 담고 있는 배경 이론은 다음과 같다.

.

이 기본 규칙에 따르면, 전제조건인 버드(콘도르)가 사실이고 정당성 플라이스(콘도르)가 현재 알려진 것과 일치하지 않기 때문에 콘도르가 날아간다. 반대로 버드(펜구인)플라이스(펜구인): 디폴트 버드(펜구인)의 전제조건이 사실이라고 해도 정당성 플라이스(펜구인)는 알려진 것과 모순된다. 이 배경 이론과 이 기본값에서 버드(Bee)는 결론을 내릴 수 없다. 왜냐하면 기본 규칙은 버드(X)로부터 파리(X)를 얻는 것만을 허용하지만, 그 반대의 경우는 허용하지 않기 때문이다. 추론 규칙의 선행자를 결과로부터 도출하는 것은 결과에 대한 설명의 한 형식이며, 유괴 추론의 목적이다.

일반적인 채무불이행 가정은 사실로 알려져 있지 않은 것이 거짓으로 믿어진다는 것이다. 이것은 폐쇄-세계 가정이라고 알려져 있으며, 모든 사실 F에 대해 다음과 같은 기본값을 사용하여 디폴트 로직으로 공식화된다.

예를 들어, 컴퓨터 언어 프롤로그는 부정(negative)을 다룰 때 일종의 기본 가정을 사용한다: 만약 음의 원자가 사실이라고 증명될 수 없다면, 그것은 거짓으로 가정된다. 그러나 프롤로그는 소위 부정(negation)을 실패(failure)로 사용한다는 점에 유의하십시오. 통역자가 F F을 평가해야 할F가 진실임을 증명하려고 하며, 실패하면 F 이 진실이라고 결론짓는다. 대신 기본 논리에서는 F을(를) 정당성으로 사용하는 기본값은 F(가) 현재 지식과 일치하는 경우에만 적용할 수 있다.

제한사항

기본값은 사전 요구 사항이 없는 경우(또는 동등하게, 사전 요구 사항은 tautological) 범주형 또는 사전 조건이 없는 경우. 채무불이행은 결론에 해당하는 단일 명분을 갖는 경우 정상이다. 기본값은 범주형 및 정규 분포를 모두 사용할 경우 수퍼 정규 분포를 따른다. 채무불이행의 모든 정당성이 그 결론에 수반된다면 채무불이행은 불가결한 것이다. 기본 이론은 포함된 모든 기본값이 각각 범주형, 정규, 슈퍼 정규 또는 세미노멀인 경우 범주형, 일반형 또는 세미노멀이라고 한다.

기본 논리 의미론

기본 규칙은 그 전제조건이 이론에 수반되고 그 정당성이 이론과 모두 일치한다면 이론에 적용될 수 있다. 기본 규칙을 적용하면 그 결과가 이론에 추가된다. 다른 기본 규칙은 결과 이론에 적용될 수 있다. 그 이론이 다른 디폴트를 적용할 수 없을 때, 그 이론은 디폴트 이론의 확장이라고 불린다. 기본 규칙은 다른 순서로 적용될 수 있으며, 이는 다른 확장으로 이어질 수 있다. 닉슨 다이아몬드 예는 두 개의 확장자를 가진 기본 이론이다.

닉슨공화당원이자 퀘이커인 만큼 두 디폴트 모두 적용이 가능하다. 그러나 첫 번째 디폴트를 적용하면 닉슨이 평화주의자가 아니라는 결론이 나와 두 번째 디폴트를 적용할 수 없게 된다. 마찬가지로, 두 번째 디폴트(채무불이행)를 적용하면 닉슨이 평화주의자라는 것을 얻게 되고, 따라서 첫 번째 디폴트(채무불이행)는 적용되지 않게 된다. 따라서 이 특별한 디폴트 이론은 평화주의자(닉슨)진실이고 평화주의자(닉슨)가 거짓인 두 개의 확장을 가지고 있다.

디폴트 논리의 원래 의미론들은 함수의 고정점에 기초했다. 다음은 등가 알고리즘 정의다. 디폴트에 자유 변수가 포함된 공식이 포함된 경우, 이 모든 변수에 값을 부여하여 얻은 모든 디폴트 집합을 나타내는 것으로 간주한다. A default is applicable to a propositional theory T if and all theories are consistent.디폴트를 T에 적용하면 T T\\}}이(가) 생성된다 확장자는 다음과 같은 알고리즘을 적용하여 생성할 수 있다.

T = W /* 현재 이론 */ A = 0 /* 지금까지 적용된 기본값 집합은 기본값 시퀀스를 적용 */에 없는 기본 d가 있고 T에 적용 가능한 기본 d가 있는 동안 D에 결과를 추가하면 A /*의 모든 기본값이 일치하면 최종 일관성 검사 */ d와 출력 T의 모든 정당화를 통해 

이 알고리즘은 비결정론적인데, 이는 여러 가지 기본값을 주어진 이론 T에 대안으로 적용할 수 있기 때문이다. 닉슨 다이아몬드 예에서, 첫 번째 디폴트 적용은 두 번째 디폴트를 적용할 수 없는 이론으로 이어지고, 그 반대의 경우도 마찬가지다. 그 결과 닉슨이 평화주의자이고 닉슨이 평화주의자가 아닌 두 가지 연장이 발생한다.

적용된 모든 채무불이행의 정당화에 대한 일관성을 최종 점검하는 것은 일부 이론에 확장자가 없다는 것을 암시한다. 특히, 적용 가능한 모든 디폴트 순서에 대해 이 점검이 실패할 때마다 이러한 현상이 발생한다. 다음의 기본 이론에는 연장이 없다.

( ) (가) 배경 이론과 일치하므로 을 적용할 수 있으므로 A( 이(가) 거짓이라는 결론을 내릴 수 있다. 그러나 이 결과는 첫 번째 채무불이행을 적용하기 위해 이루어진 가정을 훼손한다. 결과적으로, 이 이론은 확장성이 없다.

정상적인 기본 이론에서 모든 기본 이론은 정상이다: 각 기본 이론은 : { {\{\ 정상적인 기본 이론은 적어도 하나의 확장자를 갖는 것이 보장된다. 더욱이, 정상적인 채무불이행 이론의 확장은 상호 일관성이 없다. 즉, 서로 일관성이 없다.

가입

기본 이론은 0, 1 또는 그 이상의 확장을 가질 수 있다. 기본 이론에서 공식의 포함은 가지 방법으로 정의될 수 있다.

회의적인
공식은 모든 확장자에 의해 수반되는 기본 이론에 의해 수반된다.
크레디티어
공식은 적어도 하나 이상의 확장자에 의해 수반되는 경우 기본 이론에 의해 수반된다.

따라서 닉슨 다이아몬드 사례론에는 닉슨이 평화주의자라는 것과 그가 평화주의자가 아니라는 두 가지 확장이 있다. 결과적으로 평화주의자(닉슨)¬파시피스트(닉슨)는 회의론적으로 개입하지 않는 반면, 두 사람 모두 신빙성 있게 개입한다. 이 예에서 알 수 있듯이, 디폴트 이론의 잘 믿는 결과는 서로 모순될 수 있다.

대체 기본 추론 규칙

기본 논리에 대한 다음의 대체 추론 규칙은 모두 원래 시스템과 동일한 구문에 기초한다.

정당화됨
설정된 T가 적용된 디폴트의 정당성과 일치하지 않을 경우 디폴트가 적용되지 않는다는 점에서 원래 디폴트와 다르다.
간결한
채무불이행은 그 결과가 T에 의해 이미 수반되지 않은 경우에만 적용된다(정확한 정의는 이 정의보다 더 복잡하다. 이것은 단지 그 뒤에 있는 주요 아이디어일 뿐이다).
구속됨
디폴트는 배경 이론, 적용된 모든 디폴트의 정당성 및 적용된 모든 디폴트(이 디폴트 포함)의 결과가 일치하는 경우에만 적용된다.
이성적
제한된 디폴트 논리와 유사하지만, 추가할 디폴트의 결과는 일관성 검사에서 고려되지 않는다.
조심스럽다
적용할 수 있지만 서로 상충하는 디폴트(예: 닉슨 다이아몬드 예시)는 적용되지 않는다.

추론 규칙의 정당하고 제한된 버전은 최소한 모든 기본 이론에 대한 확장을 할당한다.

기본 논리 변형

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

주장 변형
어설션은 공식과 공식으로 구성된 쌍 p :{ 1 ,,r { 이다. 쌍은 공식 1,… ,r p가 사실임을 증명하기 위해 일관성이 있다고 가정하는 동안 p가 참임을 나타낸다. 주장적 기본 이론은 배경 이론이라고 불리는 주장 이론(주장적 공식의 집합)과 원래의 구문에서와 같이 정의된 기본 이론으로 구성된다. 주장 이론에 디폴트가 적용될 때마다, 그 결과 및 일련의 정당화로 구성된 쌍이 이론에 추가된다. 다음의 의미론에서는 주장 이론을 사용한다.
  • 누적 기본 논리
  • 기본 논리에 대한 가정 약속
  • 준디폴트 논리학
약한 확장자
배경 이론과 적용된 채무불이행의 결과로 구성된 이론에서 전제조건이 유효한지를 확인하는 것이 아니라, 생성될 연장선에서 유효성을 확인하는 것이다. 즉, 확장 생성 알고리즘은 이론을 추측하여 ba 대신에 그것을 사용하는 것으로 시작한다.ckground 이론;연장 생성의 과정에서 생기는 결과는 사실 처음에 추측된 이론과 동등한 경우에만 연장이다. 이러한 기본 논리의 변형은 원칙적으로 자기 논리이 있는데, 여기서 이론 x→ x 가) x{\(가) 이라고 가정하면 공식initial → x x 초기 가정을 지지한다는 이유만으로 x가 참인 모델을 갖는다.
이항 기본 논리
디폴트의 결과는 하나의 공식 대신 공식의 집합이다. 디폴트가 적용될 때마다 적어도 그 결과 중 하나는 비결정적으로 선택되고 실현된다.
기본값에 대한 우선 순위
디폴트의 상대적 우선순위를 명시적으로 지정할 수 있다. 이론에 적용되는 디폴트 중 가장 선호하는 디폴트 중 하나만 적용할 수 있다. 디폴트 논리의 일부 의미론은 우선순위를 명시적으로 명시할 필요가 없다. 오히려 더 구체적인 디폴트(더 적은 경우에 적용되는 디폴트)가 덜 구체적인 디폴트보다 선호된다.
통계적 변종
통계적 채무불이행은 그 오류 빈도에 상한이 첨부된 채무불이행이다. 다시 말해서, 채무불이행은 그 일부가 적용되는 경우에 잘못된 추론 규칙으로 간주된다.

번역

디폴트 이론은 다른 논리학에서 이론으로 번역될 수 있고 그 반대의 경우도 있다. 번역에 관한 다음과 같은 조건이 고려되었다.

결과 보존
원본 및 번역된 이론은 동일한 (비교적) 결과를 가진다.
충실한
이 조건은 두 변종의 디폴트 로직 사이에 또는 연장과 유사한 개념이 존재하는 디폴트 로직과 논리 사이에 번역할 때만 이치에 맞는다(예: 모달 로직의 모델들, 번역된 테오리의 확장(또는 모델들)과 번역된 테오리의 확장(또는 모델들) 사이에 매핑(수정, 바이어싱)이 존재한다면 번역은 충실한 것이다es;
모듈러
디폴트 논리에서 다른 논리로의 번역은 디폴트와 배경 이론이 별도로 번역될 수 있다면 모듈형이다. 더욱이 배경 이론에 공식을 추가하면 번역 결과에 새로운 공식을 추가하게 된다.
동알파벳
원본과 번역된 이론은 같은 알파벳에 기초한다.
다항식
번역의 실행 시간이나 생성된 이론의 크기는 원래 이론의 크기에서 다항식이어야 한다.

번역은 일반적으로 충실하거나 최소한 결과를 보존해야 하는 반면, 모듈화와 같은 알파벳의 조건은 무시되기도 한다.

명제 기본 논리와 다음과 같은 로직 사이의 투명성이 연구되었다.

  • 고전적 명제 논리학
  • 자기 계파적 논리
  • 이론에 국한된 명제적 디폴트 논리.
  • 기본 논리의 대체 의미론
  • 할례

번역은 어떤 조건이 부과되느냐에 따라 존재하거나 그렇지 않다. 발의안 기본 논리로부터 고전적인 발의안 논리로의 번역은, 다항식 계층 구조가 붕괴되지 않는 한, 항상 다항식 크기의 발의안 이론을 생성할 수는 없다. 자동역학 논리에 대한 번역은 모듈화가 필요한지 또는 동일한 알파벳의 사용이 필요한지에 따라 존재한다.

복잡성

기본 논리에 관한 다음과 같은 문제의 연산 복잡성은 알려져 있다.

연장유무
제안적 기본 이론에 적어도 하나의 확장자가 있는지 여부를 결정하는 것은 P -완료;
회의적 참여
명제 기본 이론이 명제 공식을 회의적으로 수반하는지 여부를 결정하는 것은 -완료;
믿을 수 있는 가입
명제적 기본 이론이 명제적 공식을 신빙성 있게 수반하는지 여부를 결정하는 것은 {\ \{2}^{ -완료;
연장조회
명제 공식이 명제 기본 이론의 확장과 동일한지 여부를 결정하는 것은 P[ -완료;
모델체크
명제적 해석이 명제적 디폴트 이론의 확장의 모델인지 아닌지를 결정하는 것은 -완전이다.

구현

디폴트 로직을 구현하는 4개의 시스템은 DeReS[permanent dead link], XRay, GADeL, Catala이다.

참고 항목

참조

  • G. 안토니우(1999년). 기본 로직에 대한 자습서. ACM 컴퓨팅 설문 조사, 31(4):337-359.
  • M. 카돌리, F. M. 도니니, P. 리베라토레, M. 샤에르프(2000). 명제적 지식의 공간 효율성은 형식주의를 나타낸다. 인공지능 연구 저널, 13:1-31
  • P. Cholewinski, V.Marek, M. 트러스츠친스키(1996년). 기본 추론 시스템 DeReS. 제5차 국제지식표현추론의 원리 회의(KR'96)의 518-528페이지.
  • J. 델란데와 T. 샤우브(2003년). Repeat의 기본 논리와 그 (주요) 변종 사이의 관계에 대하여. 불확실성을 이용한 추론에 관한 제7차 유럽 회의(ECSQARU 2003)에서는 452-463페이지에 이른다.
  • J. P. Delgrande, T. Shaub, W. K. Jackson(1994) 등이 있다. 기본 논리에 대한 대안적 접근 방식. 인공지능, 70:167-237
  • G. Gottlob(1992년). 비단조 로직의 복잡성 결과. Logic and Computing, 2:397-425.
  • G. 고틀롭(1995년). 기본 논리를 표준 자동 단계적 논리로 변환. ACM 저널, 42:711-740
  • T. 이미엘린스키(1987년). 기본값을 할부로 변환하는 결과. 인공지능, 32:131-146
  • T. 얀후넨(1998년). 자동 기록, 기본우선 순위 로직 병렬 원곡선의 상호 투명성. 제6차 유럽 인공지능 논리 워크숍(JEIA'98)의 216-232페이지.
  • T. 얀후넨(2003년). 채무불이행의 표현성에 대한 반정규범의 영향 평가. 인공지능, 144:233-250
  • H. E. 키버그와 C-M. Teng(2006년). 비모노토닉 로직과 통계적 추론적 논리와 통계적 추론. 컴퓨터 인텔리전스, 22(1) : 26-51
  • P. 리베라토어와 M. 샤에르프(1998년). 제안형 기본 로직의 모델 검사 복잡성. 제13차 유럽 인공지능 회의(ECAI'98호)의 절차에서, 18~22페이지.
  • W. 루카스체위츠(1988) 기본 논리에 대한 고려사항: 대안적 접근법. 컴퓨터 인텔리전스, 4(1):1-16.
  • W. 마렉과 M. 트러스츠친스키(1993년). 비모노틱 로직: 상황에 따른 추론. 스프링거.
  • A. 미키티우크와 M. 트러스츠친스키(1995년). 제한적이고 합리적인 기본 로직. 인공지능에 관한 제14차 국제공동회의(IJCAI'95호)에 1509-1517페이지.
  • P. 니콜라스, F. 사우비온과 나. 스테판(2001) 기본 논리 추론 시스템의 경험적 접근. 국제 인공 지능 도구 저널, 10:503-523.
  • R. 반복(1980). 기본 추론을 위한 논리. 인공지능, 13:81-132
  • T. 샤우브, S. 브뤼닝, P. 니콜라스(1996년). XRAY: 기본 추론을 위한 프롤로그 기술 정리: 시스템 설명. 제13차 국제자동공제회(CADE'96)의 절차에서 293-297페이지.
  • G. 휠러(2004) 리소스 경계 기본 논리. 제10회 비단조적 추론에 관한 국제 워크숍(NMR-04)의 진행에서 휘슬러, 브리티시 컬럼비아, 416-422.
  • G. 휠러와 C. 다마시오(2004년). 통계 기본 논리의 구현. 제9차 유럽 인공지능 논리학 회의(JELIA 2004)의 진행에서 LNCS 시리즈, 스프링어는 121-133페이지에 이른다.

외부 링크