Wie beweist man bei Fitch „(P → Q)“ aus der Prämisse „(¬P ∨ Q)“?

Sie haben Recht: Der richtige Weg ist die Verwendung von Beweis durch Fälle (auch bekannt als: Eliminierung von Disjunktionen ):

1) Q --- angenommen für den Fallbeweis [a-1]

2) P → Q --- von 1) durch bedingte Einführung

3) ¬P --- angenommen für den Fallbeweis [a-2]

4) P --- angenommen [b]

5) Widerspruch !

6) Q --- von 5) durch Ex falso

7) P → Q --- von 6) durch Bedingte Einführung, Entladung [b]

und es ist geschafft.

Mit dem Editor und Checker für natürliche Deduktion im Fitch-Stil kann ich den folgenden Beweis schreiben:

Zeile 1 enthält die Prämisse.

Da wir bei Annahme von „P“ letztlich „Q“ erhalten wollen, nehme ich „P“ in Zeile 2 an, indem ich einen Unterbeweis beginne, der nach der Fitch-Notation eingerückt ist.

Um einen Widerspruch zu bekommen, beginne ich einen weiteren Unterbeweis und nehme "¬Q" in Zeile 3 an.

In Zeile 4 verwende ich die Regel des disjunktiven Syllogismus (DS). Ich habe eine Disjunktion, "¬P ∨ Q", und "¬Q". Ich kann mit dem disjunktiven Syllogismus „¬P“ schließen. Siehe für alle x: Calgary Remix , Seiten 124-5, für eine Beschreibung dieser Regel.

In Zeile 5 führe ich aufgrund der Zeilen 2 und 4 einen Widerspruch (⊥) ein.

Der Widerspruch vervollständigt einen indirekten Beweis (IP), der es mir erlaubt, den Unterbeweis zu schließen, der die Annahme "¬Q" in Zeile 6 entlädt.

In Zeile 7 führe ich eine Bedingung aus den Zeilen 2 bis 6 ein, die den Beweis vervollständigt.

Da Sie beweisen wollen, dass eine Disjunktion eine Bedingung nach sich zieht , sollte Ihre Strategie lauten: Verwenden Sie die Eliminierung der Disjunktion und in jedem Fall die bedingte Einführung , wenn Sie können.

|_ ~p v q         : premise
|  |_ ~p          : assumed case 1
|  |  |_ p        : assumption
|  |  |           : ...
|  |  |  q        : ...
|  |  p -> q      : conditional introduction (...)
|  ~p -> (p -> q) : conditional introduction (...)
|  |_ q           : assumed case 2
|  |  |_ p        : assumption
|  |  |  q        : reiteration (...)
|  |  p -> q      : conditional introduction (...)
|  q -> (p -> q)  : conditional introduction (...)
|  p -> q         : disjunction elimination (...)

Dann ist nur noch zu entscheiden, ob p in jedem der beiden Fälle q implizieren würde und wie , falls ja.

Nehmen Sie alternativ zuerst p an und verwenden Sie dann die Disjunktionselimination. [Es stellt sich oft als effizienter heraus, DE so lange wie möglich hinauszuzögern: Baue einen Berg mit zwei Gipfeln statt mit zwei Bergen.]

 |_ ~p v q      : premise
 |  |_ p        : assumption
 |  |  |_ ~p    : assumption
 |  |  |  :     : ...
 |  |  |  q     : ...
 |  |  ~p -> q  : conditional introduction
 |  |  |_ q     : assumption
 |  |  q -> q   : conditional introduction
 |  |  q        : disjunction elimination
 |  p -> q      : conditional introduction