Zeigen Sie die folgenden Sätze durch natürliche Deduktion und das Gesetz der ausgeschlossenen Mitte

verstehe die Zeilen 9 und 10 nicht. Was soll das heißen?

Zeile 9 ist durch 'Negation Elimination'. Aus$~q~$Und$~\lnot q~$Sie können daraus schließen$~\bot~$. Das Symbol ist die Widerspruchskonstante, auch bekannt als 'falsum' oder 'bottom'. (Aus jeder Aussage und ihrer eigenen Negation können Sie schließen, dass Sie einen Widerspruch haben). Einige Systeme nennen dies „Widerspruchseinführung“.

$$\dfrac{q\quad\lnot q}{\bot}{\lnot_\mathsf e}$$

Zeile 10 steht für „Widerspruchsbeseitigung“, auch bekannt als „ex falso quadlibet“ oder das „Prinzip der Explosion“ (oder einfach nur „Explosion“). "Alles kann aus einem Widerspruch abgeleitet werden". Also ab$\bot$wir können alles schließen, wie z$r$.

$$\dfrac{\bot}{r}{\bot_\mathsf e}$$

---

Für die zweite ist Zeile 5 eine 'Negationseinführung'. Wenn Sie einen Widerspruch unter einer angenommenen Position ableiten, können Sie diese Annahme aufheben, um die Negation dieser Position abzuleiten. Der Unterschied zwischen dieser Regel und der letzten liegt in der Erfüllung der Annahme.

$$\dfrac{\dfrac{[\varphi]^\mathrm n\\~~~\vdots}{\bot}}{\lnot \varphi}{{\lnot_\mathsf i}^\mathrm n}$$

---

Jeder LEM-Beweis kann in einen Doppelnegations-Eliminationsbeweis umgeschrieben werden und umgekehrt.
In diesem Fall können Sie tun

$$\def\fitch#1#2{~~~~\begin{array}{|l}#1\\\hline #2\end{array}}\fitch{\lnot(\lnot p\vee q)}{\fitch{\lnot p}{\lnot p\vee q\qquad\vee_\mathsf i\\\bot\qquad\lnot_\mathsf e}\\\lnot\lnot p\qquad\lnot_\mathsf i\\p\qquad\lnot\lnot_\mathsf e}\qquad\fitch{\lnot(\lnot p\vee q)}{p\vee\lnot p\qquad\textsf{LEM}\\\fitch{p}{}\\\fitch{\lnot p}{\lnot p\vee q\qquad\vee_\mathsf{i}\\\bot\qquad\lnot_\mathsf e\\p\qquad\bot_\mathsf e}\\p\qquad\vee_\mathsf e}$$

Die Entscheidung, was man verwendet, ist oft eine Wahl des Stils. Hier sieht der DNE-Beweis eleganter aus.

---

Normalerweise gibt es jedoch keinen großen Unterschied in der Komplexität. Hier ist der Rahmen für Ihren ersten Beweis, sowohl im DNE- als auch im LEM-Stil.

$$\fitch{}{\fitch{\lnot((p\to q)\lor(q\to r))}{\fitch{q}{\fitch{p}{q}\\p\to q\\(p\to q)\lor(q\to r)\\\bot\\r}\\q\to r\\(p\to q)\lor(q\to r)\\\bot}\\\lnot\lnot((p\to q)\lor(q\to r))\\(p\to q)\lor(q\to r)}\quad\fitch{}{q\lor\lnot q\\\fitch{q}{\fitch{p}{q}\\p\to q\\(p\to q)\lor(q\to r)}\\\fitch{\lnot q}{\fitch{q}{\bot\\r}\\q\to r\\(p\to q)\lor(q\to r)}\\(p\to q)\lor(q\to r)}$$

Ich denke, sie verwenden für Ihre erste Frage das Explosionsprinzip, das besagt, dass aus einem Widerspruch alles beweisbar ist. Ein Argument dafür könnte wie folgt lauten: Nehmen Sie das an$p\wedge \neg p$gilt für einen Satz$p$und nehmen Sie jeden Vorschlag an$q$. Dann,$p\rightarrow q$ist eine wahre Aussage, weil$\neg p$wahr ist (nach Annahme). Dann seit$p$stimmt auch, Modus Ponens impliziert das$q$hält auch.

Für die zweite Frage scheint es so$\bot$wird verwendet, um einen Widerspruchsbeweis zu beenden. Nämlich, wenn wir das beweisen wollen$\neg q$widerspruchsfrei wahr ist, nehmen wir das an$q$ist wahr und folgern$\bot$. Damit können wir schließen$\neg q$durch „Einführung$\neg$". In der von Ihnen angegebenen Situation, da wir es beweisen wollen$\neg\neg p$, wir nehmen an$\neg p$und ableiten$\bot$. Das nutzen wir dann$\neg\neg p\rightarrow p$um das zu schließen$p$hält.

Es gibt keine gute Regel, die notwendigerweise impliziert, dass Sie das Gesetz des ausgeschlossenen Dritten anwenden werden. Ein Grund, warum ich vielleicht darüber nachdenke, es im ersten Fall zu verwenden, aber nicht im zweiten, ist, dass wir in Ihrem ersten Beispiel etwas beweisen müssen, ohne zusätzliche Annahmen zu verwenden. Unter solchen Umständen würde die Verwendung von LEM es uns ermöglichen, einen Beweis von Fällen zu führen, in denen wir etwas annehmen dürfen, das uns helfen könnte. In Ihrem zweiten Beispiel beweisen Sie jedoch eine Implikation$A\rightarrow B$und so müssen wir das in der ersten Zeile unseres Beweises annehmen$A$ist wahr.

Der erste Beweis verwendet das Explosionsprinzip, das besagt, dass aus einem Widerspruch alles folgt. Eine alternative Möglichkeit, diesen Teil des Beweises zu schreiben, wäre wie folgt:

$(8)$Annehmen$q$
$(9)$Annehmen$\lnot r$
$(10)$Widerspruch zwischen$(7)$Und$(8)$
$(11)$Annahme schließen bei$(9)$: Widerspruch impliziert$r$(Widerspruchsbeweis)
$(12)$Annahme schließen bei$(8)$:$q$Erträge$r$So$q \to r$(Einführung der Implikation)

Dies entspricht dem Beweis, den Sie haben, erfordert jedoch einige zusätzliche Zeilen und verschachtelte Annahmen, sodass dies der Einfachheit halber häufig stattdessen durch das Explosionsprinzip motiviert ist.

Für Ihren zweiten Beweis haben Sie Recht, weil wir angenommen haben$\lnot p,$wir können schließen$\lnot p \vee q$Weil$\lnot p$als wahr angenommen wird, also der Wert von$q$ist unwichtig. Dies ist die Regel der Addition oder der Einführung einer Disjunktion, wie sie in der natürlichen Deduktion genannt würde. Das hilft, weil wir jetzt einen direkten Widerspruch zu unserer Prämisse bekommen, was uns erlaubt zu schließen$p$durch einen Widerspruchsbeweis. (oder reductio ad absurdum , wenn Sie auf Latein stehen) Im Wesentlichen, wenn$p$falsch war, müssen wir einen Widerspruch haben, also$p$muss wahr sein.

Und was den Einsatz angeht$LEM$oder nicht verwenden$LEM,$Ich würde sagen, verwenden Sie es, wenn Sie es verwenden können und es nützlich ist.

Hoffe das hilft!

Andere, insbesondere Graham Kemp, haben Ihnen hervorragende Antworten auf Ihre spezifischen Fragen gegeben. Aber wenn wir ein wenig von den Details zurücktreten, vermute ich, dass Sie wahrscheinlich mehr Hintergrund-Hausaufgaben zu dieser Art von natürlichem Abzugssystem machen müssen – insbesondere zu einem System, das die Absurditätskonstante einsetzt. (Als allgemeines Prinzip, wenn ein Lehrbuch Sie verwirrt, versuchen Sie es mit einem anderen!)

Der ausgezeichnete forallX- Text ist lebhaft, aber gut auf ND und ist frei verfügbar unter https://forallx.openlogicproject.org/forallxyyc.pdf – siehe Kapitel 15 bis 18.

Für weitere Details und viele ausgearbeitete Antworten auf online verfügbare Übungen können Sie auch kostenlos mein Intro to Formal Logic von https://www.logicmatters.net/ifl herunterladen und sich die darin enthaltenen ND-Kapitel ansehen.