Aussagenlogik/Syntaktische Tautologien/Ableitungen und Regeln/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Lemma  

Es ist

Beweis  

Es ist

nach Axiom  (6), woraus sich nach Axiom  (4) mit Modus Pones auch

ergibt. Wegen Axiom  (1) ist

und daher mit Modus ponens auch

Wegen Axiom  (5) ist

und damit mit Axiom  (4) auch

so dass sich

ergibt.




Lemma  

Für ist

und

Beweis  

Nach Axiom  (4) ist

und wegen Axiom  (1) ist

so dass mit Modus ponens auch

gilt. Für die andere Behauptung gehen wir von Fakt aus, was

liefert. Wegen Axiom  (1) haben wir

also mit Modus ponens auch

Nach Axiom  (4) ist

woraus sich nach dem bisher Bewiesenen

ergibt.


Bemerkung  

Die aussagenlogischen Axiome der Form führen zu entsprechenden Schlussregeln, d.h. Vorschriften, wie man aus (schon etablierten) syntaktischen Tautologien neue Tautologien erhält. Wir gehen unter diesem Gesichtspunkt die Axiome durch.

Aus folgt .

Dies ergibt sich aus der Voraussetzung aus und dem Modus ponens.

Aus folgt (und ebenso ).

Dies ergibt sich aus nach Fakt und der Voraussetzung mittels Modus ponens. Umgekehrt gilt die sogenannte Konjunktionsregel, d.h. aus und folgt auch . Dies ergibt sich aus

(was aus den Axiomen folgt, siehe Aufgabe) aus den Voraussetzungen durch eine zweifache Anwendung des Modus ponens.

Aus und ergibt sich . Diese Regel heißt Kettenschlussregel. Nach der obigen abgeleiteten Konjunktionsregel folgt aus den Voraussetzungen direkt und daraus und dem Kettenschlussaxiom mit dem Modus ponens .




Lemma  

Es ist

Beweis  

Nach Axiom  (3) ist

Die beiden Bestandteile des Vordersatzes gelten nach Fakt, so dass auch ihre Konjunktion ableitbar ist. Daher ist auch der Nachsatz ableitbar.



Lemma

Es ist

Beweis

Siehe Aufgabe.




Lemma  

Beweis  

  1. Nach Axiom  (2) ist

    und daher mit Axiom  (4) auch

    Der Vordersatz ist nach Fakt ableitbar, also auch der Nachsatz.

  2. Nach Teil (1) ist

    und (unter Verwendung von Fakt und Aufgabe)

    Daher gilt auch (nach der Regelversion zu Teil (1))

    und

    bzw. unter Verwendung von Axiom  (4) und der Assoziativität der Konjunktion

    und

    Nach Axiom  (3) ist mit der Abkürzung

    Da die beiden Teilaussagen im Vordersatz ableitbar sind, ist auch der Nachsatz ableitbar, was unter Verwendung von Axiom  (4) zur Behauptung umformulierbar ist.


Die folgende Aussage gibt eine „interne Version“ des Modus ponens, der ja nach Definition eine Schlussregel ist.



Lemma  

Es ist

Beweis  

Nach Axiom  (6) ist

und Axiom  (5) kann man wegen Axiom  (4) zu

umformulieren. Daraus und aus (Fakt)

ergibt sich mit der Regelversion zu Fakt  (2)

und daraus durch den Kettenschluss die Behauptung.




Lemma  

  1. Aus und folgt .
  2. Aus und ergibt sich .

Beweis  

  1. Sei

    und

    Nach Bemerkung gilt auch

    und daraus ergibt sich mit Axiom  (3), der Konjunktionsregel und dem Modus ponens

    Mittels des Kettenschlusses ergibt sich daraus und aus Axiom  (2) die Behauptung.

  2. Siehe Aufgabe.


Die folgenden Tautologien machen wichtige Aussagen über das Negationszeichen. Die Tautologie (2) ist eine wichtige Variante der Widerspruchstautologie und die in (5) und (6) ausgedrückte Äquivalenz heißt Kontraposition.



Lemma  

Beweis  

  1. Die Fallunterscheidungstautologie liefert

    Aus (Fakt)

    ergibt sich daraus die Behauptung.

  2. Nach Axiom  (3) gilt

    und nach Axiom  (5) gilt

    Nach Fakt  (1) folgt

    woraus nach Teil (1) die Behauptung mit der Kettenschlussregel folgt.

  3. Nach Axiom  (1) ist

    Nach Axiom  (5) ist

    was wir mit Axiom  (4) zu

    umformulieren können. Daraus ergibt sich

    mit der Fallunterscheidungsregel.

  4. Nach Axiom  (1) ist

    Nach Axiom  (5) ist

    was wir zu

    umformulieren können. Daraus ergibt sich

    mit der Fallunterscheidungsregel.

  5. Es ist nach Axiom  (1)

    und damit auch

    Ferner ist nach einer Variante von Axiom  (5)

    Nach Fakt ist

    woraus sich

    ergibt. Mit der Fallunterscheidungsregel folgt die Behauptung.

  6. Dies folgt aus (3), (4) und (5).