Aussagen- und Prädikatenlogik

Die Aussagen- und Prädikatenlogik ist, neben den Grundrechenarten, eine wichtige Grundlage der Mathematik mit der man verschiedene mathematische Zusammenhänge ausdrücken kann.

Was ist eine Aussage?

Zunächst müssen wir klären, was überhaupt eine Aussage ist. Darunter versteht man einen Satz bzw. Ausdruck, dessen Inhalt entweder als wahr (true) oder unwahr (false) entschieden werden kann. Beispiele dafür sind:

  • Heute ist Montag.
  • Der Professor erklärt nichts.
  • 2+3 != 4
  • Es regnet genau dann, wenn die Sonne scheint.

Diese Aussagen sind je nach Situation mit „Ja“ oder „Nein“ beantwortbar. Keine Aussagen sind hingegen folgende Sätze:

  • Sind alle anwesend?
  • Bitte lest weiter.
  • Ein Lügner behauptet: „Alle Lügner lügen“.

Bei diesen Beispielen handelt es sich nicht um Aussagen, da diese nicht eindeutig mit „Ja“ oder „Nein“ beantwortbar sind. Vor allem das letzte Beispiel ist interessant, denn es beschreibt einen Widerspruch und könnte ggf. in mehrwertigen Logiken (nicht nur true, false, sondern z.b. auch „vielleicht“) beantwortet werden. Da wir aber von einer zweiwertigen Logik ausgehen, ist dies keine zulässige Aussage.

Die logischen Operationen

Verschiedene Aussagen lassen sich mit Hilfe der mehrerer Operationen verknüpfen, um verkettete Aussagen zu bilden. Im folgenden wird A die erste Beispiel- und B die zweiten Beispielaussage sein.

NICHT

Die einfachste Operation ist die unitäre NICHT-Operation. Diese ist auch als „Non“ bekannt und wird mit dem \(\neg\) Symbol dargestellt. Die Funktion besteht in der Umkehrung des Wahrheitwertes einer Aussage:

A \( \neg \) A
0 1
1 0

Dies ist sehr anschaulich: (\(\neg A\))

Heute ist nicht Montag.

UND

Diese Operation trägt das Symbol \(\wedge\) und dessen Bedeutung ist trivial. Es lassen sich zwei Aussagen verknüpfen und der Wahrheitswert der Verknüpfung wird nur „wahr“ wenn beide Teilaussagen wahr sind.

 A  B  A\(\wedge\)B
 0 0 0
 0 1 0
 1 0 0
 1 1 1

Den folgenden Satz könnte man bilden: (\(A \wedge B\))

Heute ist Montag, und der Professor erklärt nichts.

ODER

Die „oder“-Operation verknüpft zwei Aussagen, dessen gemeinsamer Wahrheitswert „wahr“ annimmt, wenn mindestens eine der beiden Aussagen „wahr“ ist. Wichtig ist anzumerken, dass es sich nicht um das umgangssprachliche „entweder oder“ (xor) handelt.

A B A\(\vee\)B
0 0 0
0 1 1
1 0 1
1 1 1

Wendet man die Beispielsätze an, ergibt sich folgende Aussage: (\(A \vee B\))

Heute ist Montag, oder der Professor erklärt nichts.

Implikation

Die Implikation wird meines Wissens nicht im Schulmathe behandelt, sodass diese dem Einen oder Anderen unbekannt sein könnte. Nichtsdestotrotz ist sie in der Mathematik sehr wichtig. Eine Implikation hat die folgende Struktur: \(A \rightarrow B\). Die Aussage A ist für B hinreichend, sodass B gelten muss, wenn A gilt. Andersherum ist B notwendig für A, sodass die Ungültigkeit von B die Ungültigkeit von A nach sich zieht. Man kann also nicht von etwas Wahrem auf etwas Falsches schließen.

A B A\(\rightarrow\)B
0 0 1
0 1 1
1 0 0
1 1 1

Die Implikation lässt sich durch die Grundoperationen „oder“ und „nicht“ darstellen: \(\neg A \vee B\) ist äquivalent zu \(A\rightarrow B\).

Ein Beispielsatz kann folgendermaßen lauten:

Der Professor erklärt nichts, wenn heute Montag ist.

Äquivalenz

Die letzte in der Mathematik gebräuchliche logische Operation nennt sich Äquivalenz. Diese drückt die Gleichheit zweier Aussagen aus. Folglich ergibt sich diese Wahrheitstabelle:

A B A\(\Leftrightarrow\)B
0 0 1
0 1 0
1 0 0
1 1 1

Auch diese Operation lässt sich wieder durch Grundoperationen beschreiben: \(\neg (A \wedge B)\ \vee (A \wedge B)\) und einer der obligatorischen Beispielsatz wäre:

Heute ist Montag, genau dann wenn der Professor nichts erklärt.

Prädikatenlogik

Nachdem ihr nun die wichtigsten Operationen und deren Funktionsweise kennt, können wir zur Prädikatenlogik übergehen. Die Prädikatenlogik gibt uns zwei weitere Symbole mit denen man eine Aussage auf verschiedene „Objekte“ anwenden kann. Diese Symbole nennen wir Quantoren:

  • Allquantor \(\forall\) – Für alle x gilt P(x)
  • Existenzquantor \(\exists\) – Es existiert mindestens ein x, für das P(x) gilt

Diese Quantoren erlauben uns, eine Aussage zu verallgemeinern, in dem diese Aussage auf Objekte einer Menge angewendet wird, und die Menge so beschrieben werden kann.

Sei M die Menge aller Leser dieses Blogeintrages.
Sei V(x) das Prädikat: Der Leser x hat das Thema verstanden.

Ich könnte dann folgende Behauptung aufstellen:
\(\forall x \in M. V(x)\)

Die Formel sagt folgendes aus: Für alle Leser dieses Blogeintrags gilt, dass sie das Thema verstanden haben. Nun, ich vermute dass es schwierig werden könnte, diese Aussage zu beweisen, da bereits ein Leser, der das Thema nicht verstanden hat, genügt, um die Aussage zu widerlegen. Deswegen wäre ich besser beraten, folgende Aussage aufzustellen:
\(\exists x \in M. V(x)\)

Zur Gültigkeit dieser Aussage reicht mir ein Leser, der das Thema verstanden hat. Dies könnte man relativ leicht beweisen, wenn man mich selbst als Leser sieht (Ich nehme an, ich hätte das Thema verstanden :P)

Durchziehen einer Negation

Es existiert die Möglichkeit, dass man Negationen vor einem Quantor „durchzieht“, sodass die Negation in die Aussage verschoben wird. Bei diesem Prozess wird der Quantor vertauscht. Ein kleines Beispiel dazu:
\(\neg \forall x \in M. V(x)\)

Gesprochen: Nicht für alle Leser gilt, dass sie das Thema verstanden haben. Aha, das riecht stark nach dem Existenzquantor. Das Ergebnis des „Durchziehens“:
\(\exists x \in M. \neg V(x)\)

Gesprochen: Es existiert mindestens ein Leser, der das Thema nicht verstanden hat.

Fazit

Ich hoffe, ich konnte das Thema einigermaßen verständlich erklären. Falls nicht, dann wird das bestimmt jemand im Laufe eures Lebens euch ein weiteres Mal erklären, denn ohne die Logik könnten wir vieles in der Mathematik nicht beschreiben.

~Sebastian

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.