Inhaltsverzeichnis
Mathematische Grundlagen der Aussagenlogik
Die Aussagenlogik beschäftigt sich mit wahren und falschen Aussagen und ihren Verknüpfungen. Sie ist eine Grundlage bei der Erstellung von Schaltungen in der Digitaltechnik.
Aussagen
Wir betrachten die folgenden sprachlichen Gebilde:
- Jede Zahl, deren Quersumme durch 3 teilbar ist, ist selbst durch 3 teilbar.
- Die letzte Mathematikarbeit war ganz schön schwer.
- Schützt den Regenwald!
- Braune Schuhe sind wärmer als im Winter!
Bei welchem dieser sprachlichen Gebilde lässt sich eindeutig sagen, ob es wahr oder falsch ist?
Definition:
Aussagen sind sprachliche Gebilde, bei denen man entscheiden kann, ob sie wahr oder falsch sind.
Aufgabe 1
Entscheide jeweils ob, eine Aussage vorliegt. Entscheide bei einer Aussage, ob sie wahr oder falsch ist.
a) 7 ist eine durch 3 teilbare Zahl.
b) a ist ein Vielfaches von 11.
c) Halte Abstand!
d) Je höher, desto fliegt es.
e) Es gibt unendlich viele Primzahlen.
f) Jede gerade Zahl, die größer als 2 ist, lässt sich als Summe zweier Primzahlen darstellen.
Aufgabe 2 (Zusatzaufgabe)
Schreibe ein Pythonprogramm,welches für eine eingegebene Zahl testet, ob die Goldbachsche Vermutung erfüllt ist!
Einzelaussagen und zusammengesetzte Aussagen
Häufig sind Aussagen durch Bindewörter wie „und“, „oder“, „nicht“, „wenn…, dann…“ usw. zusammengesetzt. Man spricht dann von zusammengesetzten Aussagen. Sie lassen sich Teilaussagen zerlegen. Eine Aussage, die sich nicht mehr zerlegen lässt, nennt man Einzelaussage.
Beispiel:
Aussage A: Die Sonnne scheint.
Aussage B: Es ist kalt.
Aussage A und B: Die Sonne scheint und es ist kalt.
„A“ und „B“ sind für sich genommen Einzelaussagen die Aussage „A und B“ ist eine zusammengesetzte Aussage.
Manchmal sind zusammengesetzte Aussagen auf Grund der Formulierung nicht einfach erkennbar. Wir betrachten die Aussage:
Beispiel:
„Heute ist nasses, kaltes Wetter.“
Diese Aussage lässt sich auch formulieren als:
„Heute ist nasses Wetter und heute ist kaltes Wetter.“
Die ursprüngliche Aussage lässt sich also zerlegen in die Einzelaussagen
A: „Heute ist nasses Wetter.“
B: „Heute ist kaltes Wetter.“
Aufgabe 3:
Welche Aussagen stecken in den folgenden zusammengesetzten Aussagen?
a) Wer im Schulhaus keine Maske trägt, verstößt gegen die Coronaregeln.
b) Heute ist es kalt, regnerisch und stürmisch.
c) ABC ist ein rechtwinkliges, gleichschenkliges Dreieck.
d) Heute Nachmittag scheint die Sonne früher oder später.
Aussagefunktionen
Mit den genannten Bindewörtern lassen sich aus vorhandenen Aussagen neue Aussagen zusammensetzen. Deshalb nennt man diese Bindewörter Aussagefunktionen. In Aussagefunktionen wird nun festgelegt, wie der Wahrheitswert der zusammengesetzten Aussage von den Wahrheitswerten der vorgegebenen Aussagen abhängt. Dies geschieht in Form von sogenannten Wahrheitstabellen. In den Wahrheitstabellen werden die vorgegebenen Aussagen mit großen Buchstaben und die Wahrheitswerte mit den Ziffern 1 für wahr und 0 für falsch bezeichnet.
Grundlegende Aussagefunktionen
Negation (nicht)
Die Negation einer Aussage $\text{X}$ ist genau dann wahr, wenn $\text{X}$ „nicht“ wahr ist. Für „nicht $\text{X}$“ kann man auch $\overline{\text{X}}$ schreiben.
Wahrheitstabelle:
$$\begin{array}{|c|c|}\hline X & \overline{X} \\ \hline 1 & 0 \\ 0 & 1 \\ \hline \end{array}$$
Konjunktion (und)
Die Konjunktion der Aussagen $\text{X}$ und $\text{Y}$ ist genau dann wahr, wenn $\text{X}$ „und“ $\text{Y}$ wahr sind. Für „$\text{X}$ und $\text{X}$“ kann man auch $\text{X}\wedge\text{Y}$ schreiben.
Wahrheitstabelle:
$$\begin{array}{|c|c|c|}\hline X & Y & X \wedge Y \\ \hline 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \hline \end{array}$$
Disjunktion (oder)
Die Disjunktion der Aussagen $\text{X}$ und $\text{Y}$ ist genau dann wahr, wenn $\text{X}$ „oder“ $\text{Y}$ oder beide wahr sind. Für „$\text{X}$ oder $\text{X}$“ kann man auch $\text{X}\vee\text{Y}$ schreiben.
$$\begin{array}{|c|c|c|}\hline X & Y & X \vee Y \\ \hline 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ \hline \end{array}$$
Wahrheitstabellen lassen sich auch für zusammengesetzte Aussagen erstellen, z.B. $\overline{X \wedge \overline{Y}}$.
$$\begin{array}{|c|c|c|c|c|} \hline X & Y & \overline{Y} & X \wedge \overline{Y} & \overline{X \wedge \overline{Y}}\\ \hline 1 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 1\\ \hline \end{array}$$
Aufgabe 4
Gegeben sind die Aussagen
$A$: Es ist kalt.
$B$: Es schneit.
Formuliere die folgenden Aussagen in Worten:
a) $\overline{A} \vee B$
b) $A \wedge \overline{B}$
c) $\overline{A \vee B} \wedge A$
d) $\overline{A \wedge B}$
Aufgabe 5
Ermittle die Wahrheitstabellen der folgenden logischen Ausdrücke!
a) $\overline{X} \wedge \overline{Y}$
b) $X \vee \overline{Y}$
c) $\overline{X \wedge Y} \wedge X$
d) $\overline{X \vee Y}$
Weitere Aussagefunktionen
Implikation (wenn-dann)
Als Implikaton werden Aussagen der Form „Wenn $\text{X}$, dann $\text{Y}$“ oder „Aus $\text{X}$ folgt $\text{Y}$“ bezeichnet. $\text{X}$ ist dabei die Voraussetzung, $\text{Y}$ ist die Behauptung. Abgekürzt kann man für die Implikation schreiben: $\text{X} \rightarrow \text{Y}$. Aus einer wahren Voraussetzung kann nur eine wahre Behauptung folgen, deshalb steht in der ersten Zeile der Wahrheitstabelle eine 1 und in der zweiten Zeile eine 0. Aus einer falschen Voraussetzung kann sowohl eine wahre als auch eine falsche Behauptung folgen. Deshalb steht in der dritten und vierten Zeile der Wahrheitstabelle eine 1.
Wahrheitstabelle:
$$\begin{array}{|c|c|c|}\hline X & Y & X \rightarrow Y \\ \hline 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \hline \end{array}$$
Äquivalenz (genau dann, wenn)
Als Äqivalenz werden Aussagen der Form „$\text{X}$ genau dann, wenn $\text{Y}$ “ genannt. Die Äquivalenz ist genau dann wahr, wenn beide Teilaussagen wahr oder beide Teilaussagen falsch sind.
Wahrheitstabelle:
$$\begin{array}{|c|c|c|}\hline X & Y & X \leftrightarrow Y \\ \hline 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \hline \end{array}$$
In der Digitaltechnik werden häufig noch die folgenden logischen Funktionen verwendet:
Antivalenz (entweder-oder, exklusiv oder)
Genau wie bei der Disjunktion (oder) ist die Antivalenz wahr, wenn entweder $\text{X}$ oder $\text{Y}$ wahr sind, sie ist allerdings falsch, wenn $\text{X}$ und $\text{Y}$ beide wahr sind. Die Antivalenz ist die Negation der Äquivalenz. Als Symbol schreibt man $\text{X} \oplus \text{Y}$ oder $\text{X} \nleftrightarrow \text{Y}$ .
Wahrheitstabelle:
$$\begin{array}{|c|c|c|}\hline X & Y & X \nleftrightarrow Y \\ \hline 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ \hline \end{array}$$
NICHT UND (NAND)
Diese Funktion ist die Negation der Konjunktion. $\left(\overline{\text{X}\wedge\text{Y}}\right)$
Wahrheitstabelle:
$$\begin{array}{|c|c|c|}\hline X & Y & \overline{X \wedge Y} \\ \hline 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \hline \end{array}$$
NICHT ODER (NOR)
Diese Funktion ist die Negation der Disjunktion. $\left(\overline{\text{X}\vee\text{Y}}\right)$
$$\begin{array}{|c|c|c|}\hline X & Y & \overline{\text{X}\vee\text{Y}} \\ \hline 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \hline \end{array}$$
Aufgabe 6
Ermittle die Wahrheitstabellen der folgenden logischen Ausdrücke!
a) $\left((X \rightarrow Y)\wedge(\overline{X} \rightarrow Y)\right) \rightarrow X$
b) $\overline{\left((X \rightarrow Y) \rightarrow X\right) \rightarrow X}$
c) $\overline{\overline{X}\wedge\overline{Y}} \leftrightarrow (X \vee Y)$
d) $(\overline{X} \wedge \overline{Y})\rightarrow(Z \rightarrow Y)$
e) $(X \rightarrow Y)\rightarrow \left((Y \rightarrow X)\rightarrow(X \leftrightarrow Y)\right)$
Tautologien
Bei den letzten logischen Ausdrücken ergab sich für jede Kombination der Wahrheitswerte der Ausgangsaussage immer der Wahrheitswert 1. Solche Ausdrücke nennt man Tautologien.
Definition
Eine Tautologie (Identität) ist eine Aussagenverbindung, die unabhängig von den Wahrheitswerten ihrer Teilaussagen immer wahr ist.
Aufgabe 7
Weise die folgenden Tautologien nach!
a) $\overline{\overline{X}} \leftrightarrow X$
b) $(X \vee X) \leftrightarrow X$
c) $(X \wedge X) \leftrightarrow X$
d) $\overline{X \wedge Y} \leftrightarrow (\overline{X} \vee \overline{Y})$
e) $\overline{X \vee Y} \leftrightarrow (\overline{X} \wedge \overline{Y})$
f) $(X \rightarrow Y) \leftrightarrow (\overline{Y} \rightarrow \overline{X})$
Zwei Schlussregeln
Einsetzungsregel
Setzt man in eine Tautologie für eine Einzelaussage an jeder Stelle, an der Sie in der Tautologie vorkommt, eine beliebige andere Einzelaussage oder Aussageverbindung ein, so erhält man wieder eine Tautologie.
Abtrennungsregel Wenn eine wahre Aussage die Form einer Implikation hat und wenn außerdem die Voraussetzung un dieser Implikation den Wahrheitswert 1 hat, dann ist die Behauptung wahr.
Aufgabe 8 (Einsetzungsregel)
a) Zeige, dass der logische Ausdruck $(X \rightarrow Y) \leftrightarrow (\overline{X} \vee Y)$ eine Tautologie ist.
b) Setze für $X$ den Ausdruck $X \wedge Z$ ein und zeige, dass der entstehende Ausdruck eine Tautologie ist.
Anwendungen
Die Anwendungsaufgaben befinden sich in den folgenden PDF-Dateien!