Algoritmus Davis – Putnam - Davis–Putnam algorithm

The Algoritmus Davis – Putnam byl vyvinut společností Martin Davis a Hilary Putnam pro kontrolu platnosti a logika prvního řádu vzorec pomocí a rozlišení - postup rozhodování na základě výroková logika. Protože sada platných vzorců prvního řádu je rekurzivně spočetné ale ne rekurzivní, neexistuje žádný obecný algoritmus, který by tento problém vyřešil. Algoritmus Davis – Putnam proto končí pouze na platných vzorcích. Dnes se termín „Davis – Putnamův algoritmus“ často používá jako synonymum pro proceduru výrokového rozhodování založenou na rozlišení, která je ve skutečnosti pouze jedním z kroků původního algoritmu.

Přehled

Dva běhy Davis-Putnamův postup například výrokové výroky. Zhora dolů, vlevo: Počínaje vzorcem ${ Displaystyle (a lor b lor c) země (b lor lnot c lor lnot f) land ( lnot b lor e)}$, algoritmus řeší dále ${ displaystyle b}$a potom dál ${ displaystyle c}$. Protože další rozlišení není možné, algoritmus se zastaví; od prázdná klauzule nelze odvodit, výsledek je „uspokojivý". Že jo: Řešení daného vzorce na ${ displaystyle b}$, pak dál ${ displaystyle a}$, pak dál ${ displaystyle c}$ získá prázdnou klauzuli; proto se algoritmus vrací "neuspokojivý".

Postup je založen na Herbrandova věta, což znamená, že neuspokojivý vzorec má nevyhovující pozemní instance, a na skutečnosti, že vzorec je platný právě tehdy, je-li jeho negace neuspokojivá. Dohromady tyto skutečnosti naznačují, že k prokázání platnosti φ stačí dokázat, že pozemní instance ¬φ je neuspokojivý. Li φ není platný, pak hledání nevyhovující základní instance nebude ukončeno.

Postup zhruba sestává z těchto tří částí:

• vložte vzorec prenex tvoří a eliminuje kvantifikátory
• generovat všechny výrokové výklady, jeden po druhém
• zkontrolujte, zda je každá instance uspokojivá

Poslední část je pravděpodobně nejinovativnější a funguje následovně (viz obrázek):

• pro každou proměnnou ve vzorci
  • za každou klauzuli ${ displaystyle c}$ obsahující proměnnou a každou klauzuli ${ displaystyle n}$ obsahující negaci proměnné
    • odhodlání C a n a přidejte resolvent do vzorce
  • odebrat všechny původní klauzule obsahující proměnnou nebo její negaci

V každém kroku je vygenerovaný přechodný vzorec vyrovnatelný, ale možná ne ekvivalent k původnímu vzorci. Krok řešení vede k nejhoršímu exponenciálnímu zvětšení velikosti vzorce.

The Algoritmus Davis – Putnam – Logemann – Loveland je zdokonalení kroku výrokové uspokojivosti postupu Davis – Putnam z roku 1962, který v nejhorším případě vyžaduje pouze lineární množství paměti. Stále tvoří základ pro dnešní (od roku 2015) nejefektivnější kompletní SAT řešitelé.

Viz také

• Herbrandizace

Reference

• Davis, Martin; Putnam, Hilary (1960). „Postup výpočtu pro teorii kvantifikace“. Deník ACM. 7 (3): 201–215. doi:10.1145/321033.321034.
• Davis, Martin; Logemann, George; Loveland, Donald (1962). „Strojový program pro dokazování věty“. Komunikace 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“. V J. Doyle a E. Sandewall a P. Torasso (ed.). Principy reprezentace a odůvodnění znalostí: Proc. čtvrté mezinárodní konference (KR'94). Kaufmann. str. 134–145.
• John Harrison (2009). Příručka praktické logiky a automatizovaného uvažování. Cambridge University Press. str.79 –90. ISBN  978-0-521-89957-4.

Tento formální metody související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.