Aussagenlogik/Elementare Einführung/Textabschnitt

Aussagen

Eine Aussage ist ein sprachliches Gebilde, das wahr oder falsch sein kann.^[1] Es ist durchaus erlaubt, dass man nicht entscheiden kann, ob die Aussage wahr oder falsch ist, weil man dazu Zusatzinformationen benötigt. Wichtig ist allein, dass die Prädikate wahr und falsch sinnvolle Prädikate des Gebildes aufgrund seiner syntaktischen und semantischen Gestalt sind.

Die Bedingung der Bedeutungsklarheit wird von natürlich-sprachlichen Aussagen selten erfüllt. Nehmen wir z.B. den Satz

Dieses Pferd ist schnell.

Einerseits haben wir keine Information, um welches Pferd es sich handelt, von dem da die Rede ist, und die Gültigkeit der Aussage hängt vermutlich davon ab, welches Pferd gemeint ist. Andererseits ist die Bedeutung von „schnell“ nicht so fest umrissen, dass, selbst wenn es klar wäre, um welches Pferd es sich handelt, vermutlich Uneinigkeit herrscht, ob es als schnell gelten soll oder nicht. Weitere alltagssprachliche Aussagen sind

Marsmenschen sind grün.

Ich fresse einen Besen.

Heinz Ngolo und Mustafa Müller sind Freunde.

In der natürlichen Sprache besteht die Möglichkeit, durch Zusatzinformationen, Kontextbezug, intersubjektive Vereinbarungen und kommunikative Bedeutungsangleichungen eine Gesprächssituation zu erzeugen, in der man über die Gültigkeit von solchen nicht scharf definierten Aussagen weitgehende Einigkeit erzielen kann. In der Logik und in der Mathematik hingegen sind diese praktischen Notlösungen nicht erlaubt, sondern die Bedeutung einer Aussage soll allein aus der Bedeutung der in ihr verwendeten Begriffe erschließbar sein, wobei diese Begriffe zuvor klar und unmissverständlich definiert worden sein müssen. Einige mathematische Aussagen (egal ob wahr oder falsch) sind

{}5>3

.

{}5<3

.

5 ist eine natürliche Zahl.

Es ist

{}7+5=13

.

Primzahlen sind ungerade.

Die minimale Darstellung eines Geldbetrages durch die Eurozahlen ist eindeutig.

Wenn man diese Aussagen versteht, und insbesondere die in ihnen verwendeten Begriffe und Symbole kennt, so sieht man, dass es sich um Aussagen handelt, die entweder wahr oder falsch sind, und zwar unabhängig davon, ob der Leser weiß, ob sie wahr oder falsch sind. Ob ein sprachliches Gebilde eine Aussage ist hängt nicht vom Wissen, ob sie wahr oder falsch ist, oder vom Aufwand ab, mit dem man durch zusätzliches Nachforschen, durch Experimente oder durch logisch-mathematisches Überlegen entscheiden könnte, ob sie wahr oder falsch ist. Bei den folgenden Beispielen handelt es sich zwar um mathematische Objekte, aber nicht um Aussagen:

5

5+11

Die Menge der Primzahlen

{}A\cap B

Eine Summe von fünf Quadraten

{}\int _{a}^{b}f(t)dt

.

Statt uns jetzt mit konkreten Aussagen auseinander zu setzen, nehmen wir im Folgenden den strukturellen Standpunkt ein, dass eine Aussage eine Aussagenvariable ${}p$ ist, die einen der beiden Wahrheitswerte wahr oder falsch annehmen kann. Zunächst interessiert uns dann, wie sich diese Wahrheitsbelegungen bei einer Konstruktion von neuen Aussagen aus alten Aussagen verhalten.

Verknüpfungen von Aussagen

Man kann aus verschiedenen Aussagen neue Aussagen bilden. Aus der Aussage

Ich fresse einen Besen

kann man die negierte Aussage

Ich fresse nicht einen Besen^[2]

machen, und aus den beiden Aussagen

Marsmenschen sind grün

und

Ich fresse einen Besen

kann man beispielsweise die folgenden neuen Aussagen basteln.

Marsmenschen sind grün und ich fresse einen Besen

Marsmenschen sind grün oder ich fresse keinen Besen

Wenn Marsmenschen grün sind, dann fresse ich einen Besen

Wenn nicht gilt, dass Marsmenschen grün sind, dann fresse ich einen Besen

Wenn Marsmenschen grün sind, dann fresse ich keinen Besen

Wenn nicht gilt, dass Marsmenschen grün sind, dann fresse ich keinen Besen

Marsmenschen sind genau dann grün, wenn ich einen Besen fresse

Hierbei werden die einzelnen Aussagen für sich genommen nicht verändert (bis auf gewisse grammatische Anpassungen), sondern lediglich in einen logischen Zusammenhang zueinander gebracht. Eine solche logische Verknüpfung ist dadurch gekennzeichnet, dass sich ihr Wahrheitsgehalt allein aus den Wahrheitsgehalten der beteiligten Aussagen und der Bedeutung der grammatischen Konjunktionen (aussagenlogisch spricht man von Junktoren) ergibt und keine weitere Information dafür erforderlich ist. Die Aussage

Marsmenschen sind grün und ich fresse keinen Besen

ist beispielsweise genau dann wahr, wenn sowohl Marsmenschen grün sind und ich keinen Besen fresse. Das ist jedenfalls die Bedeutung der logischen „und“-Verknüpfung. Eine inhaltliche Beziehung zwischen den beiden Teilaussagen ist nicht nötig.

Betrachten wir zum Vergleich eine Aussage wie

Die grünen Marsmenschen fressen Besen

Hier entsteht eine völlig neue Aussage, die lediglich einzelne Vokabeln oder Prädikate der vorgegebenen Aussagen verwendet, ihr Wahrheitsgehalt lässt sich aber keineswegs aus den Wahrheitsgehalten der vorgegebenen Aussagen erschließen.

Eine logische Verknüpfung von Aussagen liegt vor, wenn sich der Wahrheitsgehalt der Gesamtaussage aus den Wahrheitsgehalten der Teilaussagen ergibt. Die beteiligten Verknüpfungen legen dabei fest, wie sich die Wahrheitswerte der Gesamtaussage bestimmen lassen.

Aussagenvariablen und Junktoren

Um sich die Abhängigkeiten von zusammengesetzten Aussagen allein von den einzelnen Wahrheitsgehalten der beteiligten Teilaussagen und den Junktoren, nicht aber von den konkreten Aussagen und ihren Bedeutungen klarer zu machen, ist es sinnvoll, mit Aussagenvariablen zu arbeiten und die Junktoren durch Symbole zu repräsentieren. Für Aussagen schreiben wir jetzt

p,q,\ldots ,

und wir interessieren und also nicht für den Gehalt von ${}p$ , sondern lediglich für die möglichen Wahrheitswerte (oder Belegungen) von ${}p$ , die wir mit ${}w$ (wahr) oder ${}f$ (falsch) bezeichnen (gelegentlich verwendet man auch die Wahrheitswerte ${}1$ und ${}0$ ). Bei der Negation werden einfach die Wahrheitswerte vertauscht, was man mit einer einfachen Wahrheitstabelle ausdrückt:

Negation

${}p$	${}\neg p$
w	f
f	w

Bei einer konkreten Aussage gibt es in der Regel mehrere sprachliche Möglichkeiten, die Negation zu formulieren. Um die Aussage „ich fresse einen Besen“ zu negieren, ist es egal, ob man sagt:

Ich fresse nicht einen Besen.

Ich fresse keinen Besen.

Es ist nicht der Fall, dass ich einen Besen fresse.

Es trifft nicht zu, dass ich einen Besen fresse.

Die Negation wirkt auf eine einzelne Aussage, man spricht von einem einstelligen Operator. Kommen wir nun zu mehrstelligen Operatoren, die von mindestens zwei Aussagen abhängen. Bei der Verknüpfung von zwei Aussagen gibt es insgesamt vier mögliche Kombinationen der Wahrheitswerte, sodass jede logische Verknüpfung dadurch festgelegt ist, wie sie diesen vier Kombinationen einen Wahrheitswert zuordnet. Daher gibt es insgesamt ${}16$ logische Verknüpfungen, die wichtigsten sind die folgenden vier.

Die Konjunktion ist die Und-Verknüpfung. Sie ist genau dann wahr, wenn beide Teilaussagen wahr sind; sie ist also falsch, sobald nur eine der beteiligten Aussagen falsch ist. Die Wahrheitstabelle der Konjunktion sieht so aus.

Konjunktion

${}p$	${}q$	${}p\wedge q$
w	w	w
w	f	f
f	w	f
f	f	f

Die Disjunktion (oder Alternation) ist die einschließende Oder-Verknüpfung. Sie ist wahr sobald mindestens eine der Teilaussagen wahr ist, und insbesondere auch dann wahr, wenn beide Aussagen zugleich wahr sind. Sie ist nur in dem einzigen Fall falsch, dass beide Teilaussagen falsch sind. Offensichtlich sind bei einer Konjunktion und einer Disjunktion die beteiligten Teilaussagen gleichberechtigt.

Disjunktion

${}p$	${}q$	${}p\vee q$
w	w	w
w	f	w
f	w	w
f	f	f

Die Implikation ist die in der Mathematik wichtigste Verknüpfung. Mathematische Sätze haben fast immer die Gestalt einer (verschachtelten) Implikation. Der logische Gehalt einer Implikation ist, dass aus der Gültigkeit einer Voraussetzung die Gültigkeit einer Konklusion folgt.^[3] Sie wird meistens durch „Wenn ${}p$ wahr ist, dann ist auch ${}q$ wahr“ (oder kurz: Wenn ${}p$ , dann ${}q$ ) ausgedrückt. Ihre Wahrheitsbedingung ist daher, dass wenn ${}p$ mit wahr belegt ist, dann muss auch ${}q$ mit wahr belegt sein. Dies ist erfüllt, wenn ${}p$ falsch ist oder wenn ${}q$ wahr ist.^[4] Ihre Wahrheitstabelle ist daher

Implikation

${}p$	${}q$	${}p\rightarrow q$
w	w	w
w	f	f
f	w	w
f	f	w

Bei einer Implikation sind die beiden beteiligten Teilaussagen nicht gleichberechtigt, die Implikationen ${}p\rightarrow q$ und ${}q\rightarrow p$ sind verschiedene Aussagen. Eine Implikation hat also eine „Richtung“.^[5] Im allgemeinen Gebrauch und auch in der Mathematik werden Implikationen zumeist dann verwendet, wenn der Vordersatz der „Grund“ für die Konklusion ist, wenn die Implikation also einen kausalen Zusammenhang ausdrückt. Diese Interpretation spielt aber im aussagenlogischen Kontext keine Rolle.

Wenn die beiden Implikationen ${}p\rightarrow q$ und ${}q\rightarrow p$ zugleich gelten, so wird das durch „genau dann ist ${}p$ wahr, wenn ${}q$ wahr ist“ ausgedrückt. Man spricht von einer Äquivalenz der beiden Aussagen, die Wahrheitstabelle ist

Äquivalenz

${}p$	${}q$	${}p\leftrightarrow q$
w	w	w
w	f	f
f	w	f
f	f	w

Beispiele für eine mathematische Äquivalenzaussage sind:

Eine natürliche Zahl

{}n

ist genau dann gerade, wenn sie im Zehnersystem auf

{}0,2,4,6

oder

{}8

endet.

Ein Dreieck ist genau dann rechtwinklig, wenn es eine Seite gibt, deren Quadrat gleich der Summe der beiden anderen Seitenquadrate ist.

Die Hinrichtung im zweiten Beispielsatz ist dabei der Satz des Pythagoras, die Rückrichtung gilt aber auch. Achtung: In gewissen Kontexten werden Äquivalenzen als Implikationen formuliert. Dies gilt beispielsweise für Belohnungen, Bestrafungen und auch in mathematische Definitionen. Wenn man sagt: „wenn du nicht durch ${}0$ teilst, bekommst du ein Gummibärchen“, so meint man in aller Regel, dass man auch nur dann eines bekommt, aber nicht, wenn man durch ${}0$ teilt. Mathematische Definitionen wie „eine Zahl heißt gerade, wenn sie ein Vielfaches der ${}2$ ist“, sind als genau dann, wenn zu verstehen.

Unter Verwendung der Negation kann man jede logische Verknüpfung durch die angeführten Verknüpfungen ausdrücken, wobei man noch nicht mal alle braucht. Z.B. kann man die Konjunktion (und ebenso die Implikation und die Äquivalenz) auf die Disjunktion zurückführen, die Wahrheitstabelle^[6]

Konjunktion als Disjunktion

${}p$	${}q$	${}\neg (\neg p\vee \neg q)$
w	w	w
w	f	f
f	w	f
f	f	f

zeigt nämlich, dass die Wahrheitsfunktion von ${}\neg (\neg p\vee \neg q)$ mit der Wahrheitsfunktion von ${}p\wedge q$ übereinstimmt. Daher sind die beiden Ausdrücke logisch gleichwertig. Bei einem solchen nur leicht verschachtelten Ausdruck kann man die Wahrheitswerte noch einfach berechnen und damit die Wahrheitsgleichheit mit der Konjunktion feststellen. Bei komplizierteren (tiefer verschachtelten) Ausdrücken ist es sinnvoll, abhängig von den Belegungen der beteiligten Aussagenvariablen die Wahrheitswerte der Zwischenausdrücke zu berechnen. Im angegebenen Beispiel würde dies zur Tabelle

Konjunktion als Disjunktion

${}p$	${}q$	${}\neg p$	${}\neg q$	${}\neg p\vee \neg q$	${}\neg (\neg p\vee \neg q)$
w	w	f	f	f	w
w	f	f	w	w	f
f	w	w	f	w	f
f	f	w	w	w	f

führen. Natürlich kann man statt zwei auch beliebig viele Aussagenvariablen verwenden und daraus mit den Verknüpfungen neue Aussagen konstruieren. Die Wahrheitsbelegung der zusammengesetzten Aussagen lassen sich dann ebenfalls in entsprechend größeren Wahrheitstabellen darstellen.

Tautologien

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

Fußnoten

↑ Statt „wahr“ sagt man auch, dass die Aussage gilt oder dass sie richtig ist, statt „falsch“ auch, dass sie nicht gilt.
↑ Die sicherste Art, zur Negation zu kommen, ist eine Konstruktion wie „es ist nicht der Fall, dass ...“ zu verwenden. Dies ist insbesondere beim anderen Beispielsatz zu bedenken, die Aussage „Marsmenschen sind nicht grün“ kann man so verstehen, dass alle Marsmenschen nicht-grün sind, oder, dass eben nicht alle Marsmenschen grün sind, es also Ausnahmen gibt. Siehe auch den Abschnitt über Quantoren weiter unten.
↑ Genauer gesagt haben mathematische Sätze fast immer die Gestalt ${}p_{1}\wedge p_{2}\wedge \ldots \wedge p_{n}\rightarrow q$ .
↑ An die Wahrheitsbelegung einer Implikation für den Fall, wo der Vordersatz falsch ist, muss man sich etwas gewöhnen. Der Punkt ist, dass wenn man eine Implikation ${}p\rightarrow q$ beweist, dass man dann ${}p$ als wahr annimmt und davon ausgehend zeigen muss, dass auch ${}q$ wahr ist. Der Fall, dass ${}p$ falsch ist, kommt also in einem Implikationsbeweis gar nicht explizit vor. In diesem Fall gilt die Implikation, obwohl sie keine „Schlusskraft“ besitzt. Nehmen wir als Beispiel die mathematische Aussage, dass wenn eine natürliche Zahl ${}n$ durch vier teilbar ist, sie dann gerade ist. Dies ist eine wahre Aussage für alle natürlichen Zahlen, sie gilt insbesondere auch für alle Zahlen, die nicht durch vier teilbar sind. Es gibt auch jeweils für alle drei Wahrheitsbelegungen, die eine Implikation wahr machen, Beispiele von natürlichen Zahlen, die genau diese Wahrheitsbelegung repräsentieren, nicht aber für die vierte.
↑ Bei einer Implikation ${}p\rightarrow q$ sagt man auch, dass ${}p$ eine hinreichende Bedingung für ${}q$ und dass ${}q$ eine notwendige Bedingung für ${}p$ ist. Siehe dazu auch die Wahrheitstabelle zur Kontraposition weiter unten.
↑ Im Folgenden verwenden wir, um Klammern zu sparen, die Konvention, dass die Negation stärker bindet als alle mehrstelligen Junktoren, und dass die Konjunktion stärker bindet als die anderen zweistelligen Junktoren.

[1] Statt „wahr“ sagt man auch, dass die Aussage gilt oder dass sie richtig ist, statt „falsch“ auch, dass sie nicht gilt.

[2] Die sicherste Art, zur Negation zu kommen, ist eine Konstruktion wie „es ist nicht der Fall, dass ...“ zu verwenden. Dies ist insbesondere beim anderen Beispielsatz zu bedenken, die Aussage „Marsmenschen sind nicht grün“ kann man so verstehen, dass alle Marsmenschen nicht-grün sind, oder, dass eben nicht alle Marsmenschen grün sind, es also Ausnahmen gibt. Siehe auch den Abschnitt über Quantoren weiter unten.

[3] Genauer gesagt haben mathematische Sätze fast immer die Gestalt ${}p_{1}\wedge p_{2}\wedge \ldots \wedge p_{n}\rightarrow q$ .

[4] An die Wahrheitsbelegung einer Implikation für den Fall, wo der Vordersatz falsch ist, muss man sich etwas gewöhnen. Der Punkt ist, dass wenn man eine Implikation ${}p\rightarrow q$ beweist, dass man dann ${}p$ als wahr annimmt und davon ausgehend zeigen muss, dass auch ${}q$ wahr ist. Der Fall, dass ${}p$ falsch ist, kommt also in einem Implikationsbeweis gar nicht explizit vor. In diesem Fall gilt die Implikation, obwohl sie keine „Schlusskraft“ besitzt. Nehmen wir als Beispiel die mathematische Aussage, dass wenn eine natürliche Zahl ${}n$ durch vier teilbar ist, sie dann gerade ist. Dies ist eine wahre Aussage für alle natürlichen Zahlen, sie gilt insbesondere auch für alle Zahlen, die nicht durch vier teilbar sind. Es gibt auch jeweils für alle drei Wahrheitsbelegungen, die eine Implikation wahr machen, Beispiele von natürlichen Zahlen, die genau diese Wahrheitsbelegung repräsentieren, nicht aber für die vierte.

[5] Bei einer Implikation ${}p\rightarrow q$ sagt man auch, dass ${}p$ eine hinreichende Bedingung für ${}q$ und dass ${}q$ eine notwendige Bedingung für ${}p$ ist. Siehe dazu auch die Wahrheitstabelle zur Kontraposition weiter unten.

[6] Im Folgenden verwenden wir, um Klammern zu sparen, die Konvention, dass die Negation stärker bindet als alle mehrstelligen Junktoren, und dass die Konjunktion stärker bindet als die anderen zweistelligen Junktoren.

[1]

[2]

[3]

[4]

[5]

[6]