Robinson의 해결 절차의 단점은 무엇입니까?

Question

Paulson et alii. LCF에서 Isabelle / HOL까지 말한다 :

1 차 논리에 대한 해결, 원칙적으로는 완전하지만 실제로는 종종 실망 스럽습니다.

완전하다는 것은 그들이 1 차 논리로 정확한 공식을 증명할 수 있다는 것을 의미한다고 생각합니다. 에서 자동화 된 추론의 핸드북 I 찾을 수 있습니다 :

해결은 반박 할 수있는 완전한 정리 증명 방법입니다. 만족할 수없는 절 집합에서 모순 (즉, 빈 절)을 추론 할 수 있습니다.

Wikipedia에서 :

만족할 수있는 1 차 공식을 만족스럽지 않은 것으로 증명하려고하면 계산이 종료되지 않을 수 있습니다.

왜 실망 스럽습니까?

Answer 1

확실히 정의 공식적으로 (실제로 의미 하는가 "결국 모든 사실 공식을 증명할 수"있는), 그것은 아주 쉽게 예를 찾을이다 "완전한"다른 아니다 "실제로 실망"하지만 순진한 해상도도 원격으로 적합하지, 즉, 예 해야을 증명하기 쉽지만 어떤 해상도가 매우 느립니다.

유명한 예제의 부호화 인 비둘기 집 원리 에 대한$n$ 명제 논리의 허점 ( "$n+1$ 비둘기는 들어갈 수 없다 $n$중복이없는 구멍). 이 진술에 대한 증거는 없습니다.$n$.

빠른 해결 증명없이 명령문을 찾기가 매우 쉬운 조건 자 논리에서는 상황이 더욱 악화됩니다.

해결의 모든 구현은 이미 매우 어려운 문제인 해결 방법을 선택하기위한 전략과 활발한 연구 영역을 구현해야합니다. 정리 증명을위한 대부분의 실제 알고리즘 은 순진한 해결 (예 : 초 해상도)의 향상 이기 때문 입니다.