데이비스-푸트남 알고리즘

더 데이비스-퍼트남 알고리즘은 마틴 데이비스와 힐러리 푸트남이 제안형 논리에 대한 분해능 기반 의사결정 절차를 사용하여 1차 논리 공식의 유효성을 확인하기 위해 개발했다.유효한 1차 공식의 집합은 재귀적으로 열거되지만 재귀적이 아니기 때문에, 이 문제를 해결하기 위한 일반적인 알고리즘은 존재하지 않는다.그러므로 데이비스-Putnam 알고리즘은 유효한 공식에서만 종료된다.오늘날, "데이비스-Putnam 알고리즘"은 종종 결의안 기반의 제안적 의사결정 절차와 동의어로 사용된다(Davis–Putnam procedure)는 실제로 원래 알고리즘의 단계 중 하나일 뿐이다.

개요

제안적 그라운드 인스턴스(instance)에 대한 Davis-Putnam 절차의 2회 실행.Top to bottom, Left: Starting from the formula ${\displaystyle (a\lor b\lor c)\land (b\lor \lnot c\lor \lnot f)\land (\lnot b\lor e)}$, the algorithm resolves on ${\displaystyle b}$, and then on ${\displaystyle c}$. Since no further resolution is possible, the algorithm stops; s빈 조항을 도출할 수 없었기 때문에, 결과는 "유효하다".오른쪽: $b{\displaystyle }$ ${\displaystyle$ $b$$},$그 $다음{\displaystyle }$ ${\displaystyle$ a$\},$ $그{\displaystyle }$ 다음 c ${\displaystyle c}$에서 주어진 공식을 해결하면 빈 절이 생성되므로$$ 알고리즘은 "불만족"을 반환한다.

이 절차는 만족스럽지 못한 공식이 만족스럽지 못한 지상 인스턴스를 가지고 있다는 것을 암시하는 헤르브란드의 정리, 그리고 그 부정성이 만족스럽지 못한 경우에만 공식이 유효하다는 사실에 근거한다.이러한 사실들을 종합하면 φ의 타당성을 입증하는 것은 ¬의 기초적인 사례가 만족스럽지 못함을 증명하기에 충분하다는 것을 암시한다.만약 φ이 유효하지 않다면, 불만족스러운 그라운드 인스턴스 검색은 종료되지 않을 것이다.

공식 φ의 유효성을 확인하는 절차는 대략 다음과 같은 세 부분으로 구성된다.

• formula pren 공식을 혼전 양식에 넣고 정량자를 제거하다.
• 모든 제안적 그라운드 인스턴스를 하나씩 생성한다.
• 각 사례가 만족스러운지 확인하다
  • 만약 어떤 예가 불만족스럽다면, 그 φ은 유효하다고 반환한다.그렇지 않으면 계속 확인하십시오.

마지막 부분은 분해능에 기반한 SAT 해결사(그림에 나타난 바와 같이)로서 단위 전파와 순수 리터럴 제거(공식에서 극성 하나만 있는 절의 제거)를 간절히 사용한다.^{[clarification needed]}

알고리즘 DP SAT 해결사 입력: 조항 φ의 집합.출력: 진리 값: φ이 충족될 수 있으면 참이고, 그렇지 않으면 거짓이다. 

function DP-SAT(Φ)     if Φ is a consistent set of literals then return true;     if Φ contains an empty clause then return false;     for every unit clause {l} in Φ do         Φ ← unit-propagate(l, Φ);     for every literal l that occurs pure in Φ do         Φ ← pure-literal-assign(l, Φ);     // Davis-Putnam procedure: for every literal l that occφ의 양쪽 극성 모두 c를 포함한 모든 조항과 φ do r c resolve(c, n), φ do do ← ← aadd-to-formula(r, φ), φ ← ← remove-from-formula(c, n, φ; DP-SAT(()를 반환한다.

SAT 해결사의 각 단계에서 생성된 중간 공식은 원래 공식과 동일하지만 동일하지는 않을 수 있다.분해능 단계는 공식의 크기에 있어서 최악의 경우 지수적인 폭발로 이어진다.

더 데이비스-Putnam-Logemann-Loveland 알고리즘은 데이비스의 제안 만족도 단계를 1962년에 개선한 것이다.최악의 경우 선형 메모리만 필요한 퍼트남 절차.그것은 분할 규칙의 해상도를 회피한다: 리터럴 l를 선택한 다음, l가 할당된 참 값을 가진 단순화된 공식이 만족스러운지 또는 l가 할당된 거짓이 있는 단순화된 공식이 만족스러운지 재귀적으로 검사한다.오늘날(2015년 기준) 가장 효율적인 전체 SAT 해결사의 기반이 되고 있다.

참고 항목

• 허브랜드화

참조

• Davis, Martin; Putnam, Hilary (1960). "A Computing Procedure for Quantification Theory". Journal of the ACM. 7 (3): 201–215. doi:10.1145/321033.321034.
• Davis, Martin; Logemann, George; Loveland, Donald (1962). "A Machine Program for Theorem Proving". Communications of the ACM. 5 (7): 394–397. doi:10.1145/368273.368557. hdl:2027/mdp.39015095248095.
• R. Dechter; I. Rish. "Directional Resolution: The Davis–Putnam Procedure, Revisited". In J. Doyle and E. Sandewall and P. Torasso (ed.). Principles of Knowledge Representation and Reasoning: Proc. of the Fourth International Conference (KR'94). Kaufmann. pp. 134–145.
• John Harrison (2009). Handbook of practical logic and automated reasoning. Cambridge University Press. pp. 79–90. ISBN 978-0-521-89957-4.

이 형식적인 방법 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t