Die zehn Schlussfolgerungen des Natural Deduction Systems beweisen die Gesetze von DeMorgan .
Die Regeln des natürlichen Abzugs
Verneinung Einführung:
{(P → Q), (P → ¬Q)} ⊢ ¬P
Verneinung-Beseitigung:
{(¬P → Q), (¬P → ¬Q)} ⊢ P
Und Einführung:
{P, Q} ⊢ P ʌ Q
Und Beseitigung:
P ʌ Q ⊢ {P, Q}
Oder Einführung:
P ⊢ {(P ∨ Q),(Q ∨ P)}
Oder Beseitigung:
{(P ∨ Q), (P → R), (Q → R)} ⊢ R
Iff Einführung:
{(P → Q), (Q → P)} ⊢ (P ≡ Q)
Iff-Eliminierung:
(P ≡ Q) ⊢ {(P → Q), (Q → P)}
Wenn Einführung:
(P ⊢ Q) ⊢ (P → Q)
Wenn Beseitigung:
{(P → Q), P} ⊢ Q
Beweisstruktur
Jede Aussage in Ihrem Beweis muss das Ergebnis einer der zehn Regeln sein, die auf einige zuvor abgeleitete Sätze (keine zirkuläre Logik) oder eine Annahme (nachfolgend beschrieben) angewendet wurden. Jede Regel wirkt auf einige Sätze auf der linken Seite des ⊢
Operators (logische Konsequenz) und erzeugt eine beliebige Anzahl von Sätzen auf der rechten Seite. Die If-Einführung unterscheidet sich geringfügig von den übrigen Operatoren (im Folgenden ausführlich beschrieben). Es wirkt sich auf eine Anweisung aus, die die logische Konsequenz einer anderen ist.
Beispiel 1
Sie haben folgende Aussagen:
{(P → R), Q}
Sie können And Introduction verwenden, um Folgendes zu erstellen:
(P → R) ʌ Q
Beispiel 2
Sie haben folgende Aussagen:
{(P → R), P}
Sie können If Elimination verwenden, um Folgendes zu machen:
R
Beispiel 3
Sie haben folgende Aussagen:
(P ʌ Q)
Sie können And Elimination verwenden, um Folgendes zu machen:
P
oder machen:
Q
Mariä Himmelfahrt
Sie können jederzeit eine von Ihnen gewünschte Aussage treffen. Jede Aussage, die aus diesen Annahmen abgeleitet wird, ist "abhängig" von ihnen. Aussagen werden auch von den Annahmen abhängen, auf die sich ihre übergeordneten Aussagen stützen. Die einzige Möglichkeit, Annahmen zu beseitigen, ist die If-Einführung. Bei If-Einführung beginnen Sie mit einer Aussage Q
, die auf einer Aussage beruht, P
und enden mit (P → Q)
. Die neue Anweisung ist darauf angewiesen , jede Annahme Q
auf verlässt sich außer für Annahme P
. Ihre endgültige Aussage sollte sich auf keine Annahmen stützen.
Besonderheiten und Wertung
Sie konstruieren einen Beweis für jedes der beiden Gesetze von DeMorgan, indem Sie nur die 10 Folgerungen des Natural Deduction Calculus verwenden.
Die zwei Regeln sind:
¬(P ∨ Q) ≡ ¬P ʌ ¬Q
¬(P ʌ Q) ≡ ¬P ∨ ¬Q
Ihre Punktzahl ergibt sich aus der Anzahl der verwendeten Schlussfolgerungen und der Anzahl der getroffenen Annahmen. Ihre endgültige Aussage sollte sich nicht auf irgendwelche Annahmen stützen (dh sollte ein Theorem sein).
Sie können Ihren Proof nach Belieben formatieren.
Sie können jedes Lemma kostenlos von einem Proof auf einen anderen übertragen.
Beispiel Beweis
Ich werde das beweisen (P and not(P)) implies Q
(Jeder Aufzählungspunkt ist +1 Punkt)
Annehmen
not (Q)
Annehmen
(P and not(P))
Verwenden und Elim
(P and not(P))
ableiten{P, not(P)}
Verwenden Sie und Einführung auf
P
undnot(Q)
abzuleiten(P and not(Q))
Verwenden Sie And Elim für die gerade abgeleitete Aussage
P
Der neue P
Satz unterscheidet sich von dem anderen, den wir früher herleiten. Es ist nämlich auf die Annahmen angewiesen not(Q)
und (P and not(P))
. Während die ursprüngliche Aussage war nur auf (P and not(P))
. Dies ermöglicht uns Folgendes:
Wenn Einführung auf
P
Einführungnot(Q) implies P
(immer noch abhängig von der(P and not(P))
Annahme)Verwenden Sie und Einführung auf
not(P)
undnot(Q)
(ab Schritt 3), um abzuleiten(not(P) and not(Q))
Verwenden Sie und Elim auf die soeben abgeleitete Aussage zu machen
not(P)
(jetzt abhängig vonnot(Q)
)Wenn Einführung auf die neue
not(P)
Einführungnot(Q) implies not(P)
Wir werden nun die Negation Beseitigung auf verwenden
not(Q) implies not(P)
undnot(Q) implies P
herzuleitenQ
Dies Q
hängt nur von der Annahme ab (P and not(P))
, mit der wir den Beweis beenden können
- Wenn Einführung auf
Q
abzuleiten(P and not(P)) implies Q
Dieser Beweis ergibt insgesamt 11 Punkte.
quelle
⊢
(das Symbol wird für mich auch nicht auf Mobilgeräten gerendert).(P ⊢ (Q ⊢ R)) ⊢ (Q ⊢ (P ⊢ R))
(in diesem Fall¬Q ⊢ ((P ʌ ¬P) ⊢ P)
zu(P ʌ ¬P) ⊢ (¬Q ⊢ P)
verwendet wurde).(assume (P/\~P); P,~P by and-elim; (assume ~Q; P by assumption; ~P by assumption); ~Q->P by impl-intro; ~Q->~P by impl-intro; Q by neg-elim); P/\~P->Q by impl-intro
um eine Punktzahl von 9 zu bekommen?Antworten:
Prüfungsergebnis: 81
Jede Linie sollte 1 Punkt wert sein. Die Gesetze von De Morgan finden sich in den Aussagen (3) und (6). Beschriftungen in Klammern kennzeichnen die vorherigen Aussagen, von denen eine Zeile abhängt, wenn sie nicht unmittelbar vorangehen.
quelle
Prüfungsergebnis: 59
Erläuterung
Ich werde eine baumähnliche Struktur für den Beweis verwenden, da ich diesen Stil gut lesbar finde. Jede Zeile wird mit der Anzahl der verwendeten Regeln beschriftet. Beispiel: Das "Beispiel 1" in der Challenge würde als dieser Baum dargestellt (von unten nach oben):
Man beachte die unbekannten Zählungen A, B und auch die Annahme Γ - das ist also kein Theorem. Um zu demonstrieren, wie ein Theorem zu beweisen ist, nehmen wir A an und verwenden eine Or-Einführung wie folgt:
Dies hängt immer noch von der Annahme A ab, aber wir können einen Satz ableiten, indem wir eine If-Einführung anwenden:
So konnten wir den Satz ⊢ A → ( A ∨ B ) in insgesamt 3 Schritten ableiten (1 Annahme & 2 angewandte Regeln).
Damit können wir ein paar neue Regeln beweisen, die uns helfen, DeMorgans Gesetze zu beweisen.
Zusätzliche Regeln
Leiten wir zunächst das Explosionsprinzip ab und bezeichnen es in weiteren Beweisen mit PE :
Daraus leiten wir eine andere Form ab: A ⊢ ¬ A → X - wir nennen es CPE :
Wir werden einen weiteren benötigen, bei dem der negierte Term (¬) eine Annahme ist, und ihn als CPE bezeichnen - :
Aus den beiden soeben abgeleiteten Regeln ( CPE und CPE - ) können wir eine wichtige Regel Double Negation ableiten :
Das nächste was zu tun ist, ist etwas wie Modus Tollens zu beweisen - daher MT :
Lemmas
Lemma A
Lemma A1
Wir brauchen zwei Mal die folgende Regel:
Lemma A
Indem wir das gerade bewiesene Lemma zweimal instanziieren, können wir eine Richtung einer Äquivalenz zeigen, die wir für den endgültigen Beweis benötigen:
Lemma B
Um eine andere Richtung aufzuzeigen, müssen wir zwei Mal ziemlich repetitive Sachen machen (für beide Argumente A und B in ( A ∨ B )) - das bedeutet, dass ich hier möglicherweise den Beweis weiter spielen könnte.
Lemma B1 '
Lemma B1
Lemma B2 '
Lemma B2
Lemma B
Schließlich die Schlussfolgerung von B1 und B2 :
Tatsächlicher Beweis
Sobald wir diese beiden Aussagen bewiesen haben:
Wir können die erste Äquivalenz (¬ ( A ∨ B ) ≡ ¬ A ʌ ¬ B ) wie folgt beweisen :
Und mit der gerade bewiesenen Regel zusammen mit Iff-Elimination können wir auch die zweite Äquivalenz beweisen:
Ich bin mir nicht sicher, ob das stimmt. Wenn ich es richtig gemacht habe, lass es mich wissen, wenn etwas nicht stimmt.
Erläuterung
Quelle
Wenn jemand die Tex-Quelle haben möchte (braucht mathpartir ):
quelle
P
undQ
würden Sie seine Schritte separat in der Endsumme zählen müssen. (Mit anderen Worten, das Beweissystem erlaubt es nicht direkt, "Lemmata zweiter Ordnung" wie "für alle Sätze A und BA/\B -> B/\A
" zu beweisen und dann beideP/\(Q/\R) -> (Q/\R)/\P
und zu beweisen(P/\Q)/\R -> R/\(P/\Q)
.)Prüfungsergebnis: 65
Die Gesetze von de Morgan lauten Linie 30 und Linie 65.
(Ich habe keine besonderen Anstrengungen unternommen, um Golf zu spielen, zum Beispiel um zu sehen, ob es einige wiederholte Beweise gibt, die zu Beginn abstrahiert werden könnten.)
quelle