Wenn wir Sätze mit der Überlagerungsrechnung beweisen, beschäftigen wir uns mit drei Arten von Regeln:
Generieren von Regeln: Generieren Sie aus den Klauselpaaren A und B eine neue Klausel C, während Sie das ursprüngliche Paar beibehalten, z. B. Überlagerung im allgemeinen Fall.
Umschreibungsregeln: Aus Klausel A wird eine neue Klausel B generiert, z. B. Gleichheitsreflexivität, Gleichheitsfaktor; Die Überlagerung mit einer Einheitsgleichung kann auch als Umschreiberegel angesehen werden.
Regeln beseitigen: Löschen Sie eine Klausel, z. B. Subsumtion, Tautologie-Eliminierung.
Die Frage ist, ob wir in Bezug auf die zweite Kategorie eine strikte Umschreibung durchführen können, indem wir die ursprüngliche Klausel durch die neue ersetzen , oder ob wir sowohl die ursprüngliche als auch die neue beibehalten müssen. Im Fall der Gleichheitsreflexivität scheint es so, als könnten wir das erstere tun, aber für das Gleichheitsfaktorisieren und die Überlagerung mit einer Einheitsgleichung ist nicht sofort klar, ob dies die Vollständigkeit bewahren würde.
Gibt es eine allgemeine Möglichkeit zu wissen, was der Fall ist? Oder eine Liste, die jeweils erstellt werden muss?
quelle
Antworten:
Eine führende Implementierung des Beweises des Überlagerungskalkülsatzes ist E. In seiner Beschreibung ihrer Technologie gibt er einige grundlegende Theorien und Hintergründe unter Beweisverfahren an :
Daher kann das Wort "Umschreiben" in den tatsächlichen Implementierungen der Theorem-Beweisregeln etwas falsch sein, da die ursprünglichen Klauseln niemals "gelöscht" und immer beibehalten werden, falls sie beeinflusst oder mit späteren Ableitungen kombiniert werden können. Das Umschreiben "bewegt" "umgeschriebene" Klauseln zwischen und in beide Richtungen.P. U.
Das heißt, das Umschreiben ist im Grunde wie das Hinzufügen neuer abgeleiteter (wahrer) Klauseln zu einer Liste bekannter wahrer Klauseln, und die Bewegung zwischen und ist eine Strategie, um neue wahre Klauseln auf effiziente Weise zu finden (im Grunde genommen die "Grenze" in a zu verfolgen gemischte Tiefen- / Breitensuche, geordnet nach der Prioritätsfunktion) und ist die Menge der bekannten wahren Klauseln.P. U. P.∪ U.
Ich kenne keinen Schiedsrichter dafür, aber denke, das ist die Theorie zu all dem. Angenommen, und dann wurde "gelöscht". Es könnte immer noch möglich sein, durch andere Ableitungen und Klauseln abzuleiten . in diesem Fall hätte es keine Wirkung. Wenn es jedoch nicht auf anderen Wegen abgeleitet werden kann, kann es theoretisch dazu führen, dass ein vollständiges Problem in ein unvollständiges Problem umgewandelt wird. Ich kenne keine Referenz, die dies zeigt. Es könnte eine machbare Übung für den Leser sein, ein Beispiel zu finden.EIN⟹B. EIN B.⟹EIN
Kleingedrucktes: Stich auf diese Frage, weil andere Antworten fehlen. Ich bin auch an einer wirklich maßgeblichen Antwort auf diese Frage interessiert. Es gibt wahrscheinlich eine bessere als oben, aber dies ist die beste, die bisher nach einigen Recherchen gefunden wurde. Ich vermute, die Frage könnte besser auf math.se, mathoverflow oder TCS.se beantwortet werden. Es fiel mir auch schwer, grundlegende Beschreibungen dieser Konzepte und ohne viel Fachjargon zu finden.
quelle