Auflösung (Logik) – Wikipedia wiki

Posted on November 28, 2020 by lordneo

before-content-x4

Inferenzregel in Logik, Beweistheorie und automatisiertem Theorem -Beweis

after-content-x4

In mathematischer Logik und automatisiertem Theorem beweisen, Auflösung ist eine Inferenzregel, die zu einer Widerlegung komplettem Theorem-Probier-Technik für Sätze in der Aussagelogik und der Logik erster Ordnung führt. Für die Aussagelogik fungiert die Anwendung der Lösungsregel systematisch als Entscheidungsprozedur für die Formel, die die (Ergänzung des) booleschen Erfüllbarkeitsproblems löst. Für die Logik erster Ordnung kann die Logik als Grundlage für einen halbalgorithmus für das nicht wahrnehmbaren Problem der Logik erster Ordnung verwendet werden, was eine praktischere Methode bietet als eine, die aus Gödels Vollständigkeitstheorem folgt.

Die Lösungsregel kann auf Davis und Putnam (1960) zurückgeführt werden; ^[Erste]Ihr Algorithmus musste jedoch alle Bodeninstanzen der angegebenen Formel ausprobieren. Diese Quelle der kombinatorischen Explosion wurde 1965 durch John Alan Robinsons syntaktischer Vereinigungalgorithmus beseitigt, mit der man die Formel während des Beweises “On Demand” so weit wie erforderlich machte, um die Vollständigkeit der Resiedat zu erhalten. ^[2]

Die durch eine Auflösungsregel erzeugte Klausel wird manchmal als a genannt Resolvent .

Table of Contents

Auflösung in der Aussagelogik [ bearbeiten ]

Lösungsregel [ bearbeiten ]

Der Lösungsregel In der Aussagen ist Logik eine einzige gültige Inferenzregel, die eine neue Klausel erzeugt, die durch zwei Klauseln mit komplementären Literalen impliziert wird. Ein wörtliches ist eine sätzevolle Variable oder die Negation einer Aussagevariablen. Zwei Literale sollen Komplemente sein, wenn einer die Negation des anderen ist (im Folgenden,

{displayStyle lnot c}

$lnot c$ wird als Ergänzung zu sein

after-content-x4

{displayStyle c}

$c$ ). Die resultierende Klausel enthält alle Literale, die keine Ergänzungen haben.
Formal:

{displayStyle {frac {a_ {1} lor a_ {2} lor cdots lor c, quad b_ {1} lor b_ {2} lor cdots lor neg c} {a_ {1} lor a_ {2} lor cdots lor b_ {{{{{{{{{ 1} lor b_ {2} lor cdots}}}

alle

{displayStyle a_ {i}}

Die Trennlinie steht für “mit sich bringen”.

Das obige kann auch geschrieben werden als:

oder 2} land cdots) rightArrow (b_ {1} lor b_ {2} lor cdots)}}}

Oder schematisch als:

{displaystyle {frac {Gamma _{1}cup left{ell right},,,,Gamma _{2}cup left{{overline {ell }}right}}{Gamma _{1}cup Gamma _{2}} } | ell |}

Wir haben die folgende Terminologie:

Die von der Auflösungsregel erzeugte Klausel wird als die genannt Resolvent der beiden Eingangsklauseln. Es ist das Prinzip von Konsens angewendet auf Klauseln und nicht auf Begriffe. ^[3]

Wenn die beiden Klauseln mehr als ein Paar komplementärer Literale enthalten, kann die Auflösungsregel (unabhängig) für jedes solche Paar angewendet werden. Das Ergebnis ist jedoch immer eine Tautologie.

Modus-Ponens können als Sonderfall der Auflösung (einer einliteralen Klausel und einer zweiliteralen Klausel) angesehen werden.

{displayStyle {Frac {prightarrow q, quad p} {q}}}

ist äquivalent zu

{displayStyle {Frac {lnot plor q, quad p} {q}}}

Eine Auflösungstechnik [ bearbeiten ]

In Verbindung mit einem vollständigen Suchalgorithmus ergibt die Auflösungsregel einen Ton und einen vollständigen Algorithmus für die Entscheidung des Erfüllbarkeit einer Aussageformel und im weiteren Sinne die Gültigkeit eines Satzes unter einer Reihe von Axiomen.

Diese Auflösungstechnik verwendet Beweise nach Widerspruch und basiert auf der Tatsache, dass jeder Satz in der Aussagelogik in einem äquivalenten Satz in konjunktiver normaler Form umgewandelt werden kann. ^[4]Die Schritte sind wie folgt.

Alle Sätze in der Wissensbasis und die Negation des zu beweisenden Satzes (die Vermutung ) sind konjunktiv verbunden.
Der resultierende Satz wird in eine konjunktive normale Form mit den Konjunkten umgewandelt, die als Elemente in einem Satz angesehen werden. S von Klauseln. ^[4]
- Zum Beispiel, $oder$
Die Auflösungsregel wird auf alle möglichen Klauseln angewendet, die komplementäre Literale enthalten. Nach jeder Anwendung der Auflösungsregel wird der resultierende Satz durch Entfernen von wiederholten Literalen vereinfacht. Wenn die Klausel komplementäre Literale enthält, wird sie (als Tautologie) verworfen. Wenn nicht, und wenn es im Klauselsatz noch nicht vorhanden ist S , es wird hinzugefügt zu S und wird für weitere Lösungsschlüsse in Betracht gezogen.
Wenn nach Anwendung einer Auflösungsregel die leere Klausel wird abgeleitet, die ursprüngliche Formel ist nicht zufriedenstellbar (oder widersprüchlich ), und daher kann der Schluss gezogen werden, dass die anfängliche Vermutung aus den Axiomen folgt.
Wenn andererseits die leere Klausel nicht abgeleitet werden kann und die Auflösungsregel nicht angewendet werden kann, um mehr neue Klauseln abzuleiten, ist die Vermutung kein Satz der ursprünglichen Wissensbasis.

Ein Instanz dieses Algorithmus ist der ursprüngliche Davis -Putnam -Algorithmus, der später in den DPLL -Algorithmus verfeinert wurde, der die Notwendigkeit einer expliziten Darstellung der Resolvents beseitigte.

Diese Beschreibung der Auflösungstechnik verwendet einen Satz S als die zugrunde liegende Datenstruktur zur Darstellung von Auflösungsableitungen. Listen, Bäume und gerichtete acyclische Grafiken sind weitere mögliche und gängige Alternativen. Baumpräsentationen sind der Tatsache treu, dass die Lösungsregel binär ist. Zusammen mit einer sequenten Notation für Klauseln macht eine Baumdarstellung auch klar, wie die Auflösungsregel mit einem Sonderfall der Schnittregel zusammenhängt, die auf atomare Schnittformula beschränkt ist. Baumdarstellungen sind jedoch nicht so kompakt wie festgelegt oder listen Darstellungen auf, da sie explizit redundante Subdersivationen von Klauseln zeigen, die mehr als einmal in der Ableitung der leeren Klausel verwendet werden. Grafikdarstellungen können in der Anzahl der Klauseln ebenso kompakt sein wie Listendarstellungen und speichern auch strukturelle Informationen darüber, welche Klauseln entschlossen wurden, um jedes Resolvent abzuleiten.

Ein einfaches Beispiel [ bearbeiten ]

{displayStyle {Frac {Avee B, Quad Neg Avee C} {Bvee C}}}

${frac {avee b,quad neg avee c}{bvee c}}$

In einfacher Sprache: Angenommen

{displayStyle a}

$a$ ist falsch. Um die Prämisse zu

{DisplayStyle Avee B}

$avee b$ wahr sein,

{displayStyle b}

$b$ Muss wahr sein.
Alternativ nehmen Sie an

{displayStyle a}

$a$ ist wahr. Um die Prämisse zu

{displayStyle neg avee c}

$neg avee c$ wahr sein,

{displayStyle c}

$c$ Muss wahr sein. Daher unabhängig von Falschheit oder Wahrhaftigkeit von

{displayStyle a}

$a$ Wenn beide Räumlichkeiten gilt, dann die Schlussfolgerung

{DisplayStyle bvee c}

$bvee c$ ist wahr.

Auflösung in Logik erster Ordnung [ bearbeiten ]

Die Lösungsregel kann auf Logik erster Ordnung verallgemeinert werden, um: ^[5]

{displayStyle {frac {gamma _ {1} cup links {l_ {1} rechts} ,,,, gamma _ {2} cup links {l_ {2} rechts}} {(gamma _ {1} cup gamma _ {2 2 2 {2 2 {2) }) phi}} phi}

{displayStyle phi}

$phi$ ist ein allgemeiner Einfaser von

{displayStyle l_ {1}}

$L_{1}$ Und

{displayStyle {overline {l_ {2}}}}

$overline {L_{2}}$ , Und

{displayStyle gamma _ {1}}

$Gamma _{1}$ Und

{displayStyle gamma _ {2}}

$Gamma _{2}$ keine gemeinsamen Variablen haben.

Beispiel [ bearbeiten ]

Die Klauseln

{displayStyle p (x), q (x)}

$P(x),Q(x)$ Und

{displayStyle neg p (b)}

$neg P(b)$ kann diese Regel mit anwenden

{displayStyle [b/x]}

$[b/x]$ sich einheitlich haben.

Hier ist x eine Variable und B eine Konstante.

{displayStyle {Frac {p (x), q (x) ,,,, neg p (b)} {q (b)}} [b/x]}

Hier sehen wir das

Informelle Erklärung [ bearbeiten ]

In der Logik erster Ordnung kondensiert die Auflösung die traditionellen Syllogismen logischer Inferenz auf eine einzelne Regel.

Um zu verstehen, wie die Lösung funktioniert, berücksichtigen Sie den folgenden Beispiel -Syllogismus der Begriffslogik:

Alle Griechen sind Europäer.

Homer ist ein Griechisch.

Daher ist Homer ein Europäer.

Oder allgemeiner:

{displayStyle forall x.p (x) rightarrow q (x)}

{displayStyle p (a)}

Deshalb,

{displayStyle q (a)}

Um die Argumentation mithilfe der Auflösungstechnik neu zu gestalten, müssen die Klauseln zunächst in die Konjunktive Normalform (CNF) umgewandelt werden. In dieser Form wird jede Quantifizierung implizit: universelle Quantifizierer auf Variablen ( X Anwesend UND , …) werden einfach als verstanden weggelassen, während existenziell quantifizierte Variablen durch Skolemfunktionen ersetzt werden.

{displayStyle neg p (x) vee q (x)}

{displayStyle p (a)}

Deshalb,

{displayStyle q (a)}

Die Frage ist also, wie die Auflösungstechnik die letzte Klausel aus den ersten beiden ableitet? Die Regel ist einfach:

Finden Sie zwei Klauseln mit demselben Prädikat, in denen es in einer Klausel, jedoch nicht in der anderen, negiert wird.
Führen Sie eine Vereinigung für die beiden Prädikate durch. (Wenn die Vereinigung fehlschlägt, haben Sie eine schlechte Auswahl an Prädikaten getroffen. Gehen Sie zum vorherigen Schritt zurück und versuchen Sie es erneut.)
Wenn ungebundene Variablen, die in den einheitlichen Prädikaten gebunden waren, auch in anderen Prädikaten in den beiden Klauseln auftreten, ersetzen Sie sie auch durch ihre gebundenen Werte (Begriffe).
Verwerfen Sie die einheitlichen Prädikate und kombinieren Sie die verbleibenden aus den beiden Klauseln zu einer neuen Klausel, die ebenfalls vom “∨” -Operator verbunden ist.

Um diese Regel auf das obige Beispiel anzuwenden, finden wir das Prädikat P tritt in negierter Form auf

¬ P ( X )

in der ersten Klausel und in nicht gepflegter Form

P ( A )

in der zweiten Klausel. X ist eine ungebundene Variable, während A ist ein gebundener Wert (Term). Die Vereinigung der beiden erzeugt den Substitution

X ↦ A

Die einheitlichen Prädikate abwerfen und diese Substitution auf die verbleibenden Prädikate anwenden (gerade Q ( X ), in diesem Fall) die Schlussfolgerung:

Q ( A )

Betrachten Sie für ein anderes Beispiel die syllogistische Form

Alle Kretaner sind Inselbewohner.

Alle Inselbewohner sind Lügner.

Daher sind alle Kretaner Lügner.

Oder allgemeiner,

∀ X P ( X ) → Q ( X )

∀ X Q ( X ) → R ( X )

Daher ∀ X P ( X ) → R ( X )

In CNF werden die Vorgänger:

¬ P ( X ) ∨ Q ( X )

¬ Q ( UND ) ∨ R ( UND )

(Beachten Sie, dass die Variable in der zweiten Klausel umbenannt wurde, um deutlich zu machen, dass Variablen in verschiedenen Klauseln unterschiedlich sind.)

Jetzt vereinen Q ( X ) in der ersten Klausel mit ¬ Q ( UND ) In der zweiten Klausel bedeutet das X Und UND Werden Sie trotzdem die gleiche Variable. Wenn Sie dies in die verbleibenden Klauseln ersetzen und sie kombinieren, wird der Schluss gekommen:

¬ P ( X ) ∨ R ( X )

Factoring [ bearbeiten ]

Die von Robinson definierte Lösungsregel umfasste auch Factoring, das zwei Literale in derselben Klausel vor oder während der oben definierten Auflösung vereint. Die resultierende Inferenzregel ist eine Widerspruchsabgeschlossene, ^[6]In diesem Fall ist eine Reihe von Klauseln nur dann, wenn es eine Ableitung der leeren Klausel mit nur Auflösung gibt, die durch Berücksichtigung der Faktoren verbessert wird.

Ein Beispiel für eine unbefriedigende Klausel, für die Factoring erforderlich ist, um die leere Klausel abzuleiten, ist:

{displayStyle {begin {array} {rlcl} (1): & p (u) & lor & p (f (u)) \ (2): & lnot p (v) & lor & p (f (f (w)) \ (3): & lnot P (x) & lor & lnot p (f (x)) \ end {Array}}}

Da jede Klausel aus zwei Literalen besteht, kann es jedes mögliche Resolvent mögen. Daher kann die leere Klausel durch Lösung ohne Factoring niemals erhalten werden.
Unter Verwendung von Factoring kann es erhalten werden, z. folgendermaßen: ^[7]

{displayStyle {begin {array} {rll} (4): & p (u) lor p (f (w)) & {text {durch Auflösung (1) und (2), mit}} v = f (u) \ (5): & p (f (w)) & {text {von factoring (4), mit}} u = f (w) \ (6): & lnot p (f (f (w ‘)) & {text {durch Auflösung (5) und (3) mit}} W = W ‘, x = f (w’) \ (7): & {text {false}} & {text {durch Auflösen (5) und (6) ) mit}} w = f (w ‘) \ end {Array}}}

Nicht-Klauselungsauflösung [ bearbeiten ]

Es wurden Verallgemeinerungen der obigen Auflösungsregel entwickelt, bei denen die Ursprungsformeln nicht in klauslicher Normalform enthalten sind. ^[8]^[9]^[zehn]^[11]^[Zwölftel]^[13]

Diese Techniken sind hauptsächlich nützlich im interaktiven Theorem, was beweist, wo es wichtig ist, die menschliche Lesbarkeit von Zwischenergebnis -Formeln zu bewahren. Außerdem vermeiden sie eine kombinatorische Explosion während der Transformation zu Klausel. ^[zehn]^{: 98}Und manchmal speichern Sie Auflösungsschritte. ^[13]^{: 425}

Nichtklausalauflösung in der Aussagelogik [ bearbeiten ]

Für die Aussagenlogik Murray ^[9]^{: 18}und Manna und Waldinger ^[zehn]^{: 98}Verwenden Sie die Regel

{displayStyle {begin {array} {c} f [p] ;;;;;;;;;;; g [p] \ hline f [{textit {true}}] lor g [{textit {false}}] \ Ende {Array}}}

{displayStyle p}

$p$ bezeichnet eine willkürliche Formel,

{displayStyle f [p]}

$F[p]$ bezeichnet eine Formel, die enthält

{displayStyle p}

$p$ als Subformula und

{displayStyle f [{textit {true}}]}

${displaystyle F[{textit {true}}]}$ wird gebaut, indem er ausgetauscht wird

{displayStyle f [p]}

$F[p]$ Jedes Ereignis von

{displayStyle p}

$p$ von

{displayStyle {textit {true}}}

${textit {true}}$ ; Ebenso für

{displayStyle g}

$G$ .
Das Resolvent

{displayStyle f [{textit {true}}] lor g [{textit {false}}]}

${displaystyle F[{textit {true}}]lor G[{textit {false}}]}$ soll mit Regeln wie vereinfacht werden wie vereinfacht werden wie

{displayStyle qland {textit {true}} impliziert q}

${displaystyle qland {textit {true}}implies q}$ , usw.
Um zu verhindern, dass nutzlose triviale Resolvents erzeugt werden, wird die Regel nur dann angewendet, wenn

{displayStyle p}

$p$ hat mindestens einen “negativ” und “positiv” ^[14]Vorkommen in

{displayStyle f}

$F$ Und

{displayStyle g}

$G$ , bzw. Murray hat gezeigt, dass diese Regel abgeschlossen ist, wenn sie durch geeignete logische Transformationsregeln erweitert werden. ^[zehn]^{: 103}

Traugott verwendet die Regel

{displayStyle {begin {array} {c} f [p^{+}, p^{-}] ;;;;;;;; g [p] \ hline f [g [{textit {true}}], lnot g [{textit {false}}] \ end {array}}}

wo die Exponenten von

{displayStyle p}

$p$ Zeigen Sie die Polarität seiner Ereignisse an. Während

{displayStyle g [{textit {true}}]}

${displaystyle G[{textit {true}}]}$ Und

{displayStyle g [{textit {false}}]}

${displaystyle G[{textit {false}}]}$ werden wie zuvor gebaut, die Formel

{displayStyle f [g [{textit {true}}], lnot g [{textit {false}}]}]}

${displaystyle F[G[{textit {true}}],lnot G[{textit {false}}]]}$ wird erhalten, indem jedes positive und jedes negative Ereignis von ersetzt wird

{displayStyle p}

$p$ In

{displayStyle f}

$F$ mit

{displayStyle g [{textit {true}}]}

${displaystyle G[{textit {true}}]}$ Und

{displayStyle g [{textit {false}}]}

${displaystyle G[{textit {false}}]}$ , bzw. Ähnlich wie bei Murrays Ansatz sind angemessene Vereinfachung der Transformationen auf das Resolvent angewendet zu werden. Traugott bewies, dass seine Regel vollständig ist, vorausgesetzt

{DisplayStyle Land, lor, rightarrow, lnot}

${displaystyle land ,lor ,rightarrow ,lnot }$ sind die einzigen Verbindungen, die in Formeln verwendet werden. ^[Zwölftel]^{: 398–400}

Traugotts Entschlossenheit ist stärker als Murray. ^[Zwölftel]^{: 395}Darüber hinaus führt es keine neuen binären Junktoren ein, wodurch eine Tendenz zur klausalen Form in wiederholter Auflösung vermieden wird. Die Formeln können jedoch länger wachsen, wenn ein kleiner

{displayStyle p}

$p$ wird mehrmals durch ein größeres ersetzt

{displayStyle g [{textit {true}}]}

${displaystyle G[{textit {true}}]}$ und/oder

{displayStyle g [{textit {false}}]}

${displaystyle G[{textit {false}}]}$ . ^[Zwölftel]^{: 398}

Aussagen nicht Clausal Resolution Beispiel [ bearbeiten ]

Beispiel

{displayStyle {begin {array} {rccc} (1): & a & rightarrow & bland c \ (2): & c & rightarrow & d \ (3): & bland d & rightarrow & e \ (4): & lnot (a & rightarrow)

Die Murray -Regel kann wie folgt verwendet werden, um einen Widerspruch zu schließen: ^[15]

{displayStyle {begin {Array} {rrclccl} (5): & ({textit {true}}} rightarrow d) & lor & (arightarrow bland {textit {false}}) & implies & dlor lnot a & {mbox {from (aus (aus 1), mit}} p = c \ (6): & (bland {textit {true}} rightarrow e) & lor & ({textit {false}} lor lnot a) & implies & (Brightarrow e) lor lnot a & {mbox {von (3) und (5), mit}} p = d \ (7): & (({textit {true}}} rightarrow e) lor lnot a) & lor & (arightarrow {textit {false}} land c) & impliziert & elor lnot alor lnot a & {mbox {von (6) und (1), mit}} p = b \ (8): & (Elor lnot {textit {true}} lor lnot {textit {true}}) & lor & lnot & lnot ({textit {false}} rightarrow e) & impliziert & e & {Mbox {von (7) und (4), mit}} p = a \ (9): & lnot (arightarrow {textit {true}}) & lor & {{textit { false}} & impliziert & {textit {false}} & {mbox {from (4) und (8), mit}} p = e \ end {Array}}}

Für den gleichen Zweck kann die Traugott -Regel wie folgt verwendet werden: ^[Zwölftel]^{: 397}

{displayStyle {begin {array} {rcccl} (10): & arightarrow bland ({textit {true}} rightarrow d) & impliziert & arightarrow Bland d & {mbox {from (1) und (2), mit}}} p = c \ ((() 11). & impliziert & {textit {false}} & {mbox {von (11) und (4), mit}} p = (arightarrow e) \ end {Array}}}}

Aus einem Vergleich beider Abzüge sind die folgenden Probleme zu sehen:

Traugotts Regel kann ein schärferes Resolvent ergeben: Vergleichen (5) und (10), die sowohl auflösen (1) als auch (2) auf ${displayStyle p = c}$
Murrays Regel führte 3 neue Disjunktionsymbole vor: in (5), (6) und (7), während Traugotts Regel kein neues Symbol einführte; In diesem Sinne ähneln Traugotts Zwischenformeln dem Stil des Benutzers enger als Murray.
Aufgrund des letzteren Problems kann Traugotts Regel die Implikation der Annahme (4) mit AS nutzen ${displayStyle p}$

Nichtklausalauflösung in Logik erster Ordnung erster Ordnung [ bearbeiten ]

Für die Prädikat-Logik erster Ordnung ist die Regel von Murray verallgemeinert, um eindeutige, aber unifierbare Subformeln zu ermöglichen

{displayStyle p_ {1}}

$p_{1}$ Und

{displayStyle p_ {2}}

$p_{2}$ von

{displayStyle f}

$F$ Und

{displayStyle g}

$G$ , bzw. Wenn

{displayStyle phi}

$phi$ ist der allgemeinste Unifier von

{displayStyle p_ {1}}

$p_{1}$ Und

{displayStyle p_ {2}}

$p_{2}$ dann ist das verallgemeinerte Resolvent

{displayStyle fPhi [{textit {true}}] lor gphi [{textit {false}}]}

${displaystyle Fphi [{textit {true}}]lor Gphi [{textit {false}}]}$ . Während die Regel so gut bleibt, wenn ein besonderer Substitution mehr ist

{displayStyle phi}

$phi$ Wird verwendet, sind keine derartigen Regelanwendungen erforderlich, um Vollständigkeit zu erreichen. ^{[ Zitat benötigt ]}

Traugotts Regel ist verallgemeinert, um mehrere paarweise unterschiedliche Subformulas zu ermöglichen

{displayStyle p_ {1}, ldots, p_ {m}}

${displaystyle p_{1},ldots ,p_{m}}$ von

{displayStyle f}

$F$ Und

{displayStyle p_ {m+1}, ldots, p_ {n}}

${displaystyle p_{m+1},ldots ,p_{n}}$ von

{displayStyle g}

$G$ , so lange wie

{displayStyle p_ {1}, ldots, p_ {n}}

$p_1, ldots, p_n$ haben einen allgemeinsten Vereinigungsmittel, sagen wir

{displayStyle phi}

$phi$ . Das verallgemeinerte Resolvent wird nach der Bewerbung erhalten

{displayStyle phi}

$phi$ für die übergeordneten Formeln, sodass die Propositionalversion anwendbar wird. Traugotts Vollständigkeitserscheinung beruht auf der Annahme, dass diese vollständig allgemeine Regel verwendet wird. ^[Zwölftel]^{: 401}Es ist nicht klar, ob seine Regel vollständig bleiben würde, wenn er auf beschränkt ist

{displayStyle p_ {1} = cdots = p_ {m}}

${displaystyle p_{1}=cdots =p_{m}}$ Und

{displayStyle p_ {m+1} = cdots = p_ {n}}

${displaystyle p_{m+1}=cdots =p_{n}}$ . ^[16]

Paramodulation [ bearbeiten ]

Die Paramodulation ist eine verwandte Technik zum Argumentieren von Klauseln, bei denen das Prädikatsymbol Gleichheit ist. Es erzeugt alle “gleichen” Versionen von Klauseln, außer reflexive Identitäten. Der Paramodulationsvorgang nimmt positiv ein aus Klausel, die eine Gleichheit buchstäblich enthalten muss. Es sucht dann eine hinein Klausel mit einem Untermaterial, der sich mit einer Seite der Gleichheit vereint. Der Untermaterial wird dann durch die andere Seite der Gleichheit ersetzt. Das allgemeine Ziel der Paramodulation ist es, das System auf Atome zu reduzieren und die Größe der Begriffe beim Ersetzen zu verringern. ^[17]

Implementierungen [ bearbeiten ]

Siehe auch [ bearbeiten ]

^ Davis, Martin; Putnam, Hilary (1960). “Ein Computerverfahren zur Quantifizierungstheorie”. J. ACM . 7 (3): 201–215. doi: 10.1145/321033.321034 . S2CID 31888376 . Hier: p. 210, “III. Regel zur Beseitigung von Atomformeln”.
^ Robinson 1965
^ D.E. Knuth, Die Kunst der Computerprogrammierung 4a : Kombinatorische Algorithmen , Teil 1, p. 539
^ ^A ^B Leitsch 1997, p. 11 “Bevor wir die Inferenzmethode selbst anwenden, wandeln wir die Formeln in quantifiziererfreie Konjunktive Normalform.”
^ Wieder Enrique P.; González, Juan L.; Rubio, Fernando M. (2005). Computerlogik . ISBN 9788497321822 .
^ Russell, Stuart J.; Norvig, Peter (2009). Künstliche Intelligenz: ein moderner Ansatz (3. Aufl.). Prentice Hall. P. 350. ISBN 978-0-13-604259-4 .
^ Duffy, David A. (1991). Prinzipien des automatisierten Satzes beweisen . Wiley. ISBN 978-0-471-92784-6 . Siehe p. 77. Das Beispiel hier ist leicht modifiziert, um eine nicht triviale Faktorierungssubstitution zu demonstrieren. Zur Klarheit wird der Factoring -Schritt (5) getrennt dargestellt. In Schritt (6) die frische Variable ${displaystyle w’}$
^ Wilkins, D. (1973). Quest: Ein nicht-klausales Theorem-Providenssystem (Masterarbeit). Universität von Essex.
^ ^A ^B Murray, Neil V. (Februar 1979). Ein Beweisverfahren für die quantifiziererfreie nicht-klausale Logik erster Ordnung (Technischer Bericht). Elektrotechnik und Informatik, Universität Syracuse. 39. (Zitiert von Manna, Waldinger, 1980 als: “Ein Beweisverfahren für nicht klausale Logik erster Ordnung”, 1978)
^ ^A ^B ^C ^D Manna, Zohar; WALDINGER, Richard (Januar 1980). “Ein deduktiver Ansatz zur Programmsynthese” . ACM -Transaktionen zu Programmiersprachen und Systemen . 2 : 90–121. doi: 10.1145/357084.357090 . S2CID 14770735 .
^ Murray, N.V. (1982). “Völlig nicht klauslicher Theorem beweisen”. Künstliche Intelligenz . 18 : 67–85. doi: 10.1016/0004-3702 (82) 90011-x .
^ ^A ^B ^C ^D ^{Es ist} ^F Traugott, J. (1986). “Verschachtelte Resolution” . 8. Internationale Konferenz über automatisierten Abzug. Cade 1986 . Lncs. Vol. 230. Springer. S. 394–403. doi: 10.1007/3-540-16780-3_106 . ISBN 978-3-540-39861-5 .
^ ^A ^B Schmerl, U.R. (1988). “Lösung für Formelbäume”. Informatischer Akt . 25 (4): 425–438. doi: 10.1007/bf02737109 . S2CID 32702782 . Zusammenfassung
^ Diese Begriffe, die als “Polaritäten” bezeichnet werden, beziehen sich auf die Anzahl der oben gefundenen expliziten oder implizite Negationen ${displayStyle p}$
^ ” ${displayStyle impliziert}$
^ Hier, ” ${DisplayStyle =}$
^ Nieuwenhuis, Robert; Rubio, Alberto (2001). “7. Paramodulationsbasierte Theorem-Beweis” (PDF) . In Robinson, Alan J. A.; Voronkov, Andrei (Hrsg.). Handbuch der automatisierten Argumentation . Elsevier. S. 371–444. ISBN 978-0-08-053279-0 .

Verweise [ bearbeiten ]

Externe Links [ bearbeiten ]

after-content-x4

Auflösung (Logik) – Wikipedia wiki

Auflösung in der Aussagelogik [ bearbeiten ]

Lösungsregel [ bearbeiten ]

Eine Auflösungstechnik [ bearbeiten ]

Ein einfaches Beispiel [ bearbeiten ]

Auflösung in Logik erster Ordnung [ bearbeiten ]

Beispiel [ bearbeiten ]

Informelle Erklärung [ bearbeiten ]

Factoring [ bearbeiten ]

Nicht-Klauselungsauflösung [ bearbeiten ]

Nichtklausalauflösung in der Aussagelogik [ bearbeiten ]

Aussagen nicht Clausal Resolution Beispiel [ bearbeiten ]

Nichtklausalauflösung in Logik erster Ordnung erster Ordnung [ bearbeiten ]

Paramodulation [ bearbeiten ]

Implementierungen [ bearbeiten ]

Siehe auch [ bearbeiten ]

Verweise [ bearbeiten ]

Externe Links [ bearbeiten ]

Recent Posts

Recent Comments

Archives

Categories

Meta