Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 3



Tautologien

In der letzten Vorlesung haben wir erklärt, wie man ausgehend von einer Wahrheitsbelegung der Aussagenvariablen zu einer Interpretation einer jeden Aussage kommt. Dabei hängt der Wahrheitsgehalt im Allgemeinen von und von ab. Eine besondere Situation liegt vor, wenn der Wahrheitswert von nicht von der Belegung abhängt, also der Aussage immanent ist.


Definition  

Ein Ausdruck (zu einer Menge von Aussagenvariablen ) heißt allgemeingültig (oder eine semantische Tautologie,) wenn für jede Wahrheitsbelegung die Beziehung

gilt.

Bemerkung  

Den Wahrheitswert eines Ausdrucks unter der Interpretation zu einer Belegung kann man übersichtlich berechnen, wenn man abhängig von den Variablenwerten (für die in auftretenden Variablen) sukzessive die Werte der konstituierenden Bestandteile von berechnet. Um festzustellen, ob eine Tautologie vorliegt, legt man eine Wahrheitstabelle an, bei der die Zeilen durch die möglichen Kombinationen an -Werten der einzelnen (in vorkommenden) Variablen gegeben sind. Am übersichtlichsten wird die Tabelle, wenn man sich bei der Zeilenreihenfolge an das Dualsystem hält. Bei Variablen gibt es (neben der Kopfzeile) Zeilen.



Beispiel  

Der Ausdruck  (wir verzichten hier und im Folgenden häufig auf Klammern)

genannt Kontraposition, ist eine Tautologie (unabhängig davon, ob Aussagenvariablen oder Aussagen bezeichnen). Um dies nachzuweisen, muss man den Wahrheitswert dieses Ausdruckes bei jeder Wahrheitsbelegung berechnen, was wir mit einer Wahrheitstabelle durchführen.

Kontraposition
w w w f f w w
w f f f w f w
f w w w f w w
f f w w w w w

Dagegen ist der Ausdruck

keine Tautologie, da wir in Beispiel 2.13 eine Wahrheitsbelegung mit dem Gesamtwert angegeben haben.



Definition  

Ein Ausdruck (zu einer Menge von Aussagenvariablen ) heißt (semantische) Kontradiktion (oder Widerspruch), wenn für jede Wahrheitsbelegung die Beziehung

gilt.


Definition  

Es sei eine Menge von Aussagenvariablen und die zugehörige aussagenlogische Sprache. Eine Teilmenge heißt erfüllbar, wenn es eine Wahrheitsbelegung mit zugehöriger Interpretation derart gibt, dass für alle gilt.

Diese Sprechweise verwendet man insbesondere für einen einzelnen Ausdruck .



Lemma  

Ein Ausdruck (zu einer Menge von Aussagenvariablen )

ist genau dann eine (semantische) Tautologie, wenn nicht erfüllbar ist.

Beweis  

Wir beweisen die kontraponierte Aussage, dass genau dann keine Tautologie ist, wenn erfüllbar ist. Dass keine Tautologie vorliegt, bedeutet, dass es eine Wahrheitsbelegung derart gibt, dass

Dies bedeutet aber

was gerade die Erfüllbarkeit von besagt.



Die Folgerungsbeziehung

In gewissen Situationen interessiert man sich dafür, welche Ausdrücke aus einer bestimmten Menge von Ausdrücken, etwa einem Axiomensystem, gefolgert werden können.


Definition  

Es sei eine Menge von Variablen und die zugehörige aussagenlogische Sprache. Es sei eine Teilmenge und . Man sagt, dass aus folgt, geschrieben , wenn für jede Interpretation (gegeben durch eine Wahrheitsbelegung ) mit auch gilt.

Für die Menge aller Aussagen, die aus der Aussagenmenge folgt, schreiben wir . Tautologien sind genau die aus der leeren Ausdrucksmenge folgerbaren Aussagen. Daher schreibt man für Tautologien auch .



Ein Ableitungskalkül für die aussagenlogischen Tautologien

Wir formulieren nun einen syntaktischen Ableitungskalkül für (syntaktische) Tautologien. Dieser generiert, ausgehend von gewissen axiomatisch fixierten Grundtautologien, rekursiv eine Menge von Aussagen, die, wie wir später sehen werden, mit der Menge der allgemeingültigen Sätzen (semantische Tautologien) übereinstimmt. Wir arbeiten allein mit den logischen Symbolen , d.h. wir verzichten auf und auf . Dies reduziert die Ausdrucksstärke der Sprache nicht, da man als Abkürzung für und als Abkürzung für einführen kann. Um Klammern zu sparen verwenden wir die Konvention, dass die Negation sich auf das folgende Zeichen bezieht und dass die Konjunktion stärker bindet als die Implikation. Man könnte auch die Implikation durch definieren und eliminieren, doch dann würden die Ausdrücke sehr unübersichtlich.


Axiom  

Für eine Aussagenvariablenmenge und beliebige Ausdrücke legt man folgende (syntaktische) Tautologien axiomatisch fest.

  1. und

Man spricht häufig auch genauer von Axiomenschemata, da jedes Axiom bei unterschiedlichen Einsetzungen eine Vielzahl von Axiomen representiert. Das Kettenschlussaxiom (2) besagt die Transitivität der Implikation, Axiom (5) heißt Widerspruchsaxiom und Axiom (6) heißt Fallunterscheidungsaxiom. Diese Tautologien sind die axiomatisch fixierten Grundtautologien und fungieren als die Startglieder im rekursiven Aufbau der syntaktischen Tautologien. Um überhaupt aus diesen Axiomen weitere Tautologien generieren zu können, braucht man Ableitungsregeln. Davon gibt es lediglich eine.

Modus ponens

Aus und folgt .


Definition  

Unter einer syntaktischen Tautologie versteht man einen Ausdruck (zu einer Aussagenvariablenmenge ), den man aus den {{ Axiomlink Grundtautologien|Axiomseitenname= Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiom |Nr= |SZ= }} rekursiv mittels Modus ponens erhalten kann.

Bemerkung  

Eine Durchsicht der Grundtautologien zeigt, dass es sich jeweils auch um semantische Tautologien handelt, siehe Aufgabe 3.15. Wenn ferner und semantische Tautologien sind, so ist auch eine semantische Tautologie. D.h. die semantischen Tautologien sind unter Modus ponens abgeschlossen. Dies bedeutet insgesamt, dass syntaktische Tautologien stets semantische Tautologien sind. Diese Eigenschaft nennt man auch die Korrektheit des syntaktischen Kalküls, er leitet ausschließlich semantische Tautologien, also wahre Aussagen ab. Die umgekehrte Aussage, dass sich jede semantische Tautologie auch syntaktisch in dem angegebenen Kalkül ableiten lässt, nennt man die Vollständigkeit des Kalküls.




Weitere Tautologien und Regeln



Lemma  

Es ist

Beweis  

Es ist

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

ergibt. Wegen Axiom 3.8  (1) ist

und daher mit Modus ponens auch

Wegen Axiom 3.8  (5) ist

und damit mit Axiom 3.8  (4) auch

so dass sich

ergibt.



Lemma  

Für ist

und

Beweis  

Nach Axiom 3.8  (4) ist

und wegen Axiom 3.8  (1) ist

so dass mit Modus ponens auch

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

liefert. Wegen Axiom 3.8  (1) haben wir

also mit Modus ponens auch

Nach Axiom 3.8  (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 Lemma 3.12 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 3.16) 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.8  (3) ist

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



Lemma

Es ist

Beweis

Siehe Aufgabe 3.17.



Lemma  

Beweis  

  1. Nach Axiom 3.8  (2) ist

    und daher mit Axiom 3.8  (4) auch

    Der Vordersatz ist nach Lemma 3.12 ableitbar, also auch der Nachsatz.

  2. Nach Teil (1) ist

    und (unter Verwendung von Lemma 3.14 und Aufgabe *****)

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

    und

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

    und

    Nach Axiom 3.8  (3) ist mit der Abkürzung

    Da die beiden Teilaussagen im Vordersatz ableitbar sind, ist auch der Nachsatz ableitbar, was unter Verwendung von Axiom 3.8  (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 3.8  (6) ist

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

umformulieren. Daraus und aus (Lemma 3.11)

ergibt sich mit der Regelversion zu Lemma 3.16  (2)

und daraus durch den Kettenschluss die Behauptung.



Lemma  

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

Beweis  

  1. Sei

    und

    Nach Bemerkung 3.13 gilt auch

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

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

  2. Siehe Aufgabe 3.27.


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 (Lemma 3.11)

    ergibt sich daraus die Behauptung.

  2. Nach Axiom 3.8  (3) gilt

    und nach Axiom 3.8  (5) gilt

    Nach Lemma 3.18  (1) folgt

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

  3. Nach Axiom 3.8  (1) ist

    Nach Axiom 3.8  (5) ist

    was wir mit Axiom 3.8  (4) zu

    umformulieren können. Daraus ergibt sich

    mit der Fallunterscheidungsregel.

  4. Nach Axiom 3.8  (1) ist

    Nach Axiom 3.8  (5) ist

    was wir zu

    umformulieren können. Daraus ergibt sich

    mit der Fallunterscheidungsregel.

  5. Es ist nach Axiom 3.8  (1)

    und damit auch

    Ferner ist nach einer Variante von Axiom 3.8  (5)

    Nach Lemma 3.17 ist

    woraus sich

    ergibt. Mit der Fallunterscheidungsregel folgt die Behauptung.

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



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2016) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)