Aussagen/Tautologien/Elementare Einführung/Textabschnitt

Bei Einzelaussagen und zusammengesetzten Aussagen ist jeder Wahrheitswert erlaubt, und die Wahrheitswerte bei den verknüpften Aussagen ergeben sich aus den Einzelbelegungen über die Wahrheitsregeln, die die Junktoren auszeichnen. Abhängig von den Belegungen können somit alle Aussagen wahr oder falsch sein. Besonders interessant sind aber solche Aussagen, die unabhängig von den Einzelbelegungen stets wahr sind. Solche Aussagen nennt man Tautologien (oder allgemeingültig). Sie sind für die Mathematik vor allem deshalb wichtig, weil sie erlaubten Schlussweisen entsprechen, wie sie in Beweisen häufig vorkommen. Wenn man beispielsweise schon die beiden Aussagen ${}p$ und ${}p\rightarrow q$ bewiesen hat, wobei hier ${}p$ und ${}q$ für konkrete Aussagen stehen, so kann man daraus auf die Gültigkeit von ${}q$ schließen. Die zugrunde liegende aussagenlogische Tautologie ist

$(p\wedge (p\rightarrow q))\rightarrow q.$

Wie gesagt, eine Tautologie ist durch den konstanten Wahrheitswert wahr gekennzeichnet. Der Nachweis, dass eine gegebene Aussage eine Tautologie ist, verläuft am einfachsten über eine Wahrheitstabelle.

Ableitungsregel (Modus ponens)
${}p$ ${}q$ ${}p\rightarrow q$ ${}p\wedge (p\rightarrow q)$ ${}(p\wedge (p\rightarrow q))\rightarrow q$ w w w w w w f f f w f w w f w f f w f w

Doppelnegation
${}p$ ${}\neg p$ ${}\neg (\neg p)$ ${}p\leftrightarrow \neg (\neg p)$ w f w w f w f w

Tertium non datur
${}p$ ${}\neg p$ ${}p\vee \neg p$ w f w f w w

Die Regel Tertium non datur geht auf Aristoteles zurück und besagt, dass eine Aussage (entweder) wahr oder falsch ist und es keine dritte Möglichkeit gibt. Die obige Regel drückt formal gesehen nur aus, dass mindestens ein Wahrheitswert gelten muss, die Regel davor sagt, dass ${}p$ wahr zugleich ${}\neg p$ wahr ausschließt, was man auch den Satz vom Widerspruch nennt (zusammenfassend spricht man auch vom Bivalenzprinzip). Die Gültigkeit dieser Regeln ist bei vielen umgangssprachlichen Aussagen fragwürdig, im Rahmen der Aussagenlogik und der Mathematik haben sie aber uneingeschränkt Gültigkeit, was wiederum damit zusammenhängt, dass in diesen Gebieten nur solche Aussagen erlaubt sind, denen ein eindeutiger Wahrheitswert zukommt. Als Beweisprinzip schlägt sich dieses logische Prinzip als Beweis durch Fallunterscheidung nieder, wobei die folgende Tautologie dieses Beweisprinzip noch deutlicher ausdrückt.

Fallunterscheidung
${}p$ ${}q$ ${}p\rightarrow q$ ${}\neg p$ ${}\neg p\rightarrow q$ ${}(p\rightarrow q)\wedge (\neg p\rightarrow q)$ ${}((p\rightarrow q)\wedge (\neg p\rightarrow q))\rightarrow q$ w w w f w w w w f f f w f w f w w w w w w f f w w f f w

Bei der Fallunterscheidung will man ${}q$ beweisen, und man beweist es dann einerseits (Fall 1) unter der zusätzlichen Annahme ${}p$ und andererseits (Fall 2) unter der zusätzlichen Annahme ${}\neg p$. Man muss dabei zweimal was machen, der Vorteil ist aber, dass die zusätzlichen Annahmen zusätzliche Methoden und Techniken erlauben.

Die Kontraposition wird häufig in Beweisen verwendet, ohne dass dies immer explizit gemacht wird. In einem Beweis nimmt man einen pragmatischen Standpunkt ein, und manchmal ist es einfacher, von ${}\neg q$ nach ${}\neg p$ zu gelangen als von ${}p$ nach ${}q$.

Kontraposition
${}p$ ${}q$ ${}p\rightarrow q$ ${}\neg p$ ${}\neg q$ ${}\neg q\rightarrow \neg p$ ${}(p\rightarrow q)\leftrightarrow (\neg q\rightarrow \neg p)$ 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

Die Widerspruchsregel ist auch ein häufiges Argumentationsmuster. Man zeigt, dass aus einer Aussage ${}p$ ein Widerspruch, oft von der Form ${}q\wedge \neg q$, folgt, und schließt daraus, dass ${}p$ nicht gelten kann, also ${}\neg p$ gelten muss.

Widerspruchsregel
${}p$ ${}q$ ${}p\rightarrow q$ ${}p\rightarrow \neg q$ ${}(p\rightarrow q)\wedge (p\rightarrow \neg q)$ ${}\neg p$ ${}(p\rightarrow q)\wedge (p\rightarrow \neg q)\rightarrow \neg p$ w w w f f f w w f f w f f w f w w w w w w f f w w w w w