18  Aussagenlogik

Die Aussagenlogik beschäftigt sich mit Aussagen und deren Verknüpfungen (Junktoren). Dabei sind Aussagen immer entweder wahr oder falsch. Sowohl in der Mathematik als auch beim Programmieren oder im täglichen Leben spielen logische Überlegungen und damit die Aussagenlogik eine wichtige Rolle.

Beispiel 1: (Tägliches Leben: Lügende Politiker entlarven)

In einer Rede hört man von einem Politiker die folgenden vier Aussagen:

• ,,Die Vollbeschäftigung wird erhalten oder die Steuern dürfen nicht erhöht werden.’’
• ,,Wenn sich Politiker um die Bevölkerung kümmern, müssen die Steuern angehoben werden.’’
• ,,Die Politiker kümmern sich um die Bevölkerung oder die Vollbeschäftigung kann nicht erhalten werden.’’
• ,,Es stimmt nicht, dass die Erhaltung der Vollbeschäftigung eine Steuererhöhung zur Folge haben muss.’’

Frage: Hat sich der Politiker widersprochen? Das heißt kann es Wahrheitswerte (wahr oder falsch) für alle Aussagen geben, so dass er sich nicht widerspricht oder sagt er vielleicht sogar immer die Wahrheit egal welche Wahrheitswerte seine Aussagen haben?

Problem: Verknüpfungen der Aussagen verhältnismäßig komplex, so dass man die obige Frage nicht ohne weiteres beantworten kann!

Lösung: Formalisieren des Problems und Aussagen in mathematischer Form formulieren.

Wir werden die Lösung am Ende des Kapitels zeigen.

Beispiel 2: (Mathematik: direkter Beweis)

In der Mathematik gibt es verschiedene Formen der Beweisführung: die vollständige Induktion, den Beweis durch Widerspruch und den direkten Beweis.

Die folgende Aufgabe soll mit Hilfe eines direkten Beweises geführt werden. Die Idee ist aus einer Aussage A durch Umformungen eine Aussage B zu folgern, deren Wahrheitswert bekannt ist. Formal könnte man das schreiben als

\begin{align*} A \implies C_1 \implies C_2 \implies \cdots \implies C_n \implies B, \end{align*}

wobei alle C_i Zwischenschritte sind.

Konkretes Beispiel

Man zeige, dass für alle a, b \in \mathbb{R} gilt:

\begin{align*} a^2 + b^2 \ge 2ab \end{align*}

Beweis:

\begin{align*} a^2 + b^2 \ge 2ab \quad \implies \quad a^2 - 2ab + b^2 \ge 0 \quad \implies \quad (a-b)^2 \ge 0 \end{align*}

Damit ist man fertig, da Quadrate in den reellen Zahlen nie negativ sind, während man dem ursprünglichen Ausdruck nicht unbedingt ansieht ob er für alle a, b wahr ist.

Weitere Beweismethoden sind die vollständige Induktion und Beweis durch Widerspruch.

Beispiel 3: (Informatik)

In Data Science oder der Informatik benötigt wir Wahrheitswerte an mehreren Stellen:

Ein Beispiel sind Abbruchbedingungen bei Schleifen:

i <- 1
while(i<5){
  cat(paste("i hat aktuell den Wert", i, "\n"))
  i <- i+1
}

i hat aktuell den Wert 1 
i hat aktuell den Wert 2 
i hat aktuell den Wert 3 
i hat aktuell den Wert 4 

Die while() Schleife wird solange ausgeführt wie der Term i<5 eine wahre Aussage ist.

Beispiel 4: (Datenanalyse)

library(pacman)
p_load(tidyverse, palmerpenguins)

penguins |> filter(species == "Adelie")

# A tibble: 152 × 8
   species island    bill_length_mm bill_depth_mm flipper_length_mm body_mass_g
   <fct>   <fct>              <dbl>         <dbl>             <int>       <int>
 1 Adelie  Torgersen           39.1          18.7               181        3750
 2 Adelie  Torgersen           39.5          17.4               186        3800
 3 Adelie  Torgersen           40.3          18                 195        3250
 4 Adelie  Torgersen           NA            NA                  NA          NA
 5 Adelie  Torgersen           36.7          19.3               193        3450
 6 Adelie  Torgersen           39.3          20.6               190        3650
 7 Adelie  Torgersen           38.9          17.8               181        3625
 8 Adelie  Torgersen           39.2          19.6               195        4675
 9 Adelie  Torgersen           34.1          18.1               193        3475
10 Adelie  Torgersen           42            20.2               190        4250
# ℹ 142 more rows
# ℹ 2 more variables: sex <fct>, year <int>

In diesem Beispiel werden aus dem Datensatz penguins alle Beobachtungen herausgefiltert, bei denen species gleich "Adelie" ist, das Argument species == "Adelie" also TRUE ist.

18.1 Aussagen und Wahrheitswerte

Wir wollen in diesem Kapitel die Grundlagen für die Aussagenlogik definieren und einige kleine Beispiele dazu zeigen. Am Ende des Kapitel lösen wir Beispiel 1: Lügende Poliker entlarven mit Hilfe der Aussagenlogik auf.

Definition: Aussage / Wahrheitswerte

Eine Aussage ist ein grammatischer Satz, der objektiv nach wahr (w) oder falsch (f) klassifiziert werden kann. Man nennt die Wörter wahr und falsch die Wahrheitswerte.

Aussagen sind damit nie

• wahr und gleichzeitig falsch,
• weder wahr noch falsch.

Beispiele:

• 2 + 3 = 6 ist eine falsche Aussage, 2\cdot 4 = 8 ist eine wahre Aussage.
• Sätze wie “Sonnenblumen sind schön” (nicht objektiv) oder “Dieser Satz ist falsch.” (semantisches Paradox) sind keine Aussagen, da sie nicht objektiv als wahr oder falsch klassifiziert werden können.

Bemerkungen:

• In der R werden die Wahrheitswerte mit TRUE oder T beziehungsweise FALSE oder F gekennzeichnet. Oft entstehen solche logische Vektoren aus Vergleichen (z.B. zweier Vektoren).

# Beispiel 1:
1:6 > 3

[1] FALSE FALSE FALSE  TRUE  TRUE  TRUE

Im ersten Beispiel vergleichen wir, ob die ganzen Zahlen von 1 bis 6 größer als 3 sind. Das Ergebnis ist ein sogenannter logischer Vektor (siehe Kapitel 5.4.1).

# Beispiel 2:
c("Adam", "Bert", "Carl", "Doro") %in% c("Bert", "Cale", "Doro", "Emil", "Fido")

[1] FALSE  TRUE FALSE  TRUE

Mit dem Operator %in% wird überprüft, ob sich die Einträge aus dem ersten Vektor im zweiten befinden. Ist ein Eintrag TRUE, so kommt der jeweilige Eintrag im zweiten Vektor vor. Eine praktische Anwendungen im Zusammenhang mit dem Filtern von Daten in Datentabellen finden sich im Kapitel 8.3.

18.2 Junktoren

Junktoren sind logische Operatoren in der Aussagenlogik.

• Negation: \neg A (oder auch \overline{A})
  liest man nicht A. Die Negation kehrt den Wahrheitswert einer Aussage um, das heißt ist A wahr, so ist \neg A falsch und umgekeht.

Die Negation ist ein einstelliger Operator, da sie nur einen Wahrheitswert benötigt. Die folgenden Junktoren sind alle zweistellige Operatoren, da sie zwei Wahrheitswerte benötigen.

• Konjunktion: A \wedge B
  liest man A und B und ist genau dann wahr, wenn A und B beide wahr sind.

• Disjunktion: A \vee B
  liest man A oder B und ist genau dann falsch, wenn sowohl A als auch B falsch sind.

• Implikation: A \implies B
  liest man aus A folgt B oder A impliziert B oder B ist notwendig für A oder A ist hinreichend für B ist nur genau dann falsch, wenn A wahr und B falsch ist.

• Äquivalenz: A \iff B
  liest man A ist äquivalent zu B- Die Aussage A ist wahr genau dann, wenn Aussage B wahr ist. Gleichwertig kann man auch sagen: Wenn Aussage A wahr ist, so auch B, und wenn B wahr ist, so auch A.

18.3 Wahrheitstabellen

Mit Hilfe einer Wahrheitstabelle können alle Wahrheitswerte, die eine (abgeleitete) Aussage haben kann gleichzeitig gezeigt werden. In Tabelle 18.1 sieht man die im vorherigen Kapitel definierten Aussagen A und B, sowie die definierten Verknüpfungen. Für n verknüpfte Aussagen gibt es 2^n mögliche wahr/falsch-Kombinationen. Also für zwei Aussagen sind das 2^2 = 4 verschiedene Möglichkeiten, die alle in der Wahrheitstabelle zu sehen sind.

Tabelle 18.1: Übersicht zur Negation, Konjunktion, Disjunktion, Implikation und Äquivalenz zweier Aussagen.

A	B	\neg A	\neg B	A \wedge B	A \vee B	A \implies B	A \iff B
w	w	f	f	w	w	w	w
w	f	f	w	f	w	f	f
f	w	w	f	f	w	w	f
f	f	w	w	f	f	w	w

• Tautologie:
  Eine Tautologie ist eine Aussage, die unabhängig von den Wahrheitswerten immer wahr ist. Ein Beispiel hierfür wäre die Aussage: ,,Es regnet oder es regnet nicht’’.

• Kontradiktion: ist das Gegenteil einer Tautologie und unabhängig der Wahrheitswerte immer falsch. Ein Beispiel ist die Aussage ,,Es regnet und es regnet nicht’’.

Die Wahrheitstabellen können auf beliebige Kombinationen von Aussagen erweitert werden und sind ein praktisches Werkzeug um logische Verknüpfungen zu untersuchen. Ein interessantes Beispiel ist die Kontraposition. Dabei iist zu erwähnen, dass nicht nur das Ergebnis in der Tabelle zu sehen ist, sondern auch die Zwischenschritte, wie man das Ergebnis erhalten hat (hier: das explizite Aufschreiben der Negationen \neg A und \neg B).

Beispiel: Kontraposition

Die folgende Wahrheitstabelle zeigt, dass Implikation A \implies B und ihrer Kontraposition \neg B \implies \neg A die gleichen Wahrheitswerte haben. Mathematisch schreibt man

\begin{align*} (A \implies B) \equiv (\neg B \implies \neg A), \end{align*}

wobei \equiv die Bedeutung ist identisch zu hat und auch so gelesen wird.

Tabelle 18.2: Wahrheitstabelle für die Kontraposition

A	B	\neg A	\neg B	A \implies B	\neg B \implies \neg A
w	w	f	f	w	w
w	f	f	w	f	f
f	w	w	f	w	w
f	f	w	w	w	w

Nimmt man zum Beispiel die beiden Aussagen A: ,,Es regnet.’’ und B: ,,Die Erde ist nass.’‘, dann ist die Implikation: ,,Wenn es regnet, dann ist die Erde nass.’‘. Eine dazu identische Aussage ist nun nicht: ,,Wenn es nicht regnet, dann ist die Erde nicht nass.’‘, das wäre im Allgemeinen falsch, schließlich kann sie auch aufgrund anderer Gründe nass sein, wenn dort zum Beispiel eine Wasserschlacht stattgefunden hat oder weil der Nachbar sein Auto geputzt hat. Eine äquivalente Aussage ist ,,Wenn die Erde nicht nass ist, dann regnet es nicht.’’

Aufgaben: Wahrheitstabellen

Zeigen Sie mit Hilfe einer Wahrheitstabelle, dass

• \neg(\neg A) \equiv A gilt,
• A \vee \neg A eine Tautologie ist,
• A \wedge \neg A eine Kontradiktion ist und
• die beiden Regeln von de Morgan gelten:

\begin{align*} \neg(A \wedge B) \equiv (\neg A \vee \neg B) \quad \text{und} \quad \neg(A \vee B) \equiv (\neg A \wedge \neg B). \end{align*}

• Zeigen Sie mit Hilfe einer Wahrheitstabelle, dass die Äquivalenz der Implikation in beide Richtungen entspricht:

\begin{align*} (A \iff B) \equiv (A \implies B) \wedge (B \implies A) \end{align*}

Lösungen

Die ersten drei können wir leicht in einer einzigen Tabelle machen:

A	\neg A	\neg (\neg A)	A \vee \neg A	A \vee \neg A
w	f	w	w	f
f	w	f	w	f

Für die beiden de Morgan Regel gibt es zwei Aussagen A und B, die jeweils wahr oder falsch sein könnten, daher gibt es 2^2 = 4 Möglichkeiten diese zu kombinieren und man muss alle Möglichkeiten betrachten.

A	B	\neg A	\neg B	A \wedge B	\neg(A \wedge B)	\neg A \vee \neg B
w	w	f	f	w	f	f
w	f	f	w	f	w	w
f	w	w	f	f	w	w
f	f	w	w	f	w	w

und komplett analog:

A	B	\neg A	\neg B	A \vee B	\neg(A \vee B)	\neg A \wedge \neg B
w	w	f	f	w	f	f
w	f	f	w	w	f	f
f	w	w	f	w	f	f
f	f	w	w	f	w	w

Man sieht, dass jeweils die letzten beiden Spalten gleich sind.

A	B	A \implies B	B \implies A	A \iff B	(A \implies B) \wedge (B \implies A)
w	w	w	w	w	w
w	f	f	w	f	f
f	w	w	f	f	f
f	f	w	w	w	w

Selbsttest: Wahrheitstabelle

Gegeben sind die Aussagen R,{} O,{} X sowie die verknüpfte Aussage H mit

H \quad \equiv \quad \left(R \iff O\right) \vee \left(\neg O \wedge X\right). Bestimmen sie die Wahrheitswerte (f oder w) von H und tragen diese in die Felder ein.

R	w	w	w	w	f	f	f	f
O	w	w	f	f	w	w	f	f
X	w	f	w	f	w	f	w	f
H

Gegeben sind die Aussagen B,{} S,{} G sowie die verknüpfte Aussage O mit

O \quad \equiv \quad \neg \left(B \vee S\right) \implies \neg \left(S \iff G\right). Bestimmen sie die Wahrheitswerte (f oder w) von O und tragen diese in die Felder ein.

B	w	w	w	w	f	f	f	f
S	w	w	f	f	w	w	f	f
G	w	f	w	f	w	f	w	f
O

Gegeben sind die Aussagen L,{} Z,{} P sowie die verknüpfte Aussage Q mit

Q \quad \equiv \quad \left(L \wedge Z\right) \vee \neg \left(Z \implies P\right). Bestimmen sie die Wahrheitswerte (f oder w) von Q und tragen diese in die Felder ein.

L	w	w	w	w	f	f	f	f
Z	w	w	f	f	w	w	f	f
P	w	f	w	f	w	f	w	f
Q

Gegeben sind die Aussagen T,{} H,{} C sowie die verknüpfte Aussage O mit

O \quad \equiv \quad \neg \left(T \vee \neg H\right) \wedge \left(\neg H \implies C\right). Bestimmen sie die Wahrheitswerte (f oder w) von O und tragen diese in die Felder ein.

T	w	w	w	w	f	f	f	f
H	w	w	f	f	w	w	f	f
C	w	f	w	f	w	f	w	f
O

Gegeben sind die Aussagen Z,{} R,{} M sowie die verknüpfte Aussage W mit

W \quad \equiv \quad \neg \left(Z \vee \neg R\right) \iff \neg \left(\neg R \wedge M\right). Bestimmen sie die Wahrheitswerte (f oder w) von W und tragen diese in die Felder ein.

Z	w	w	w	w	f	f	f	f
R	w	w	f	f	w	w	f	f
M	w	f	w	f	w	f	w	f
W

Gegeben sind die Aussagen R,{} U,{} K sowie die verknüpfte Aussage O mit

O \quad \equiv \quad \neg \left(R \implies \neg U\right) \vee \neg \left(U \iff K\right). Bestimmen sie die Wahrheitswerte (f oder w) von O und tragen diese in die Felder ein.

R	w	w	w	w	f	f	f	f
U	w	w	f	f	w	w	f	f
K	w	f	w	f	w	f	w	f
O

Gegeben sind die Aussagen P,{} W,{} J sowie die verknüpfte Aussage Q mit

Q \quad \equiv \quad \neg \left(P \wedge W\right) \iff \neg \left(W \vee J\right). Bestimmen sie die Wahrheitswerte (f oder w) von Q und tragen diese in die Felder ein.

P	w	w	w	w	f	f	f	f
W	w	w	f	f	w	w	f	f
J	w	f	w	f	w	f	w	f
Q

Gegeben sind die Aussagen R,{} E,{} C sowie die verknüpfte Aussage T mit

T \quad \equiv \quad \left(R \vee E\right) \implies \neg \left(E \iff C\right). Bestimmen sie die Wahrheitswerte (f oder w) von T und tragen diese in die Felder ein.

R	w	w	w	w	f	f	f	f
E	w	w	f	f	w	w	f	f
C	w	f	w	f	w	f	w	f
T

Gegeben sind die Aussagen J,{} T,{} I sowie die verknüpfte Aussage U mit

U \quad \equiv \quad \left(J \vee \neg T\right) \wedge \left(T \implies I\right). Bestimmen sie die Wahrheitswerte (f oder w) von U und tragen diese in die Felder ein.

J	w	w	w	w	f	f	f	f
T	w	w	f	f	w	w	f	f
I	w	f	w	f	w	f	w	f
U

Gegeben sind die Aussagen Y,{} H,{} V sowie die verknüpfte Aussage L mit

L \quad \equiv \quad \left(Y \vee H\right) \implies \left(H \iff V\right). Bestimmen sie die Wahrheitswerte (f oder w) von L und tragen diese in die Felder ein.

Y	w	w	w	w	f	f	f	f
H	w	w	f	f	w	w	f	f
V	w	f	w	f	w	f	w	f
L

Gegeben sind die Aussagen S,{} K,{} N sowie die verknüpfte Aussage U mit

U \quad \equiv \quad \left(S \iff \neg K\right) \wedge \left(\neg K \implies N\right). Bestimmen sie die Wahrheitswerte (f oder w) von U und tragen diese in die Felder ein.

S	w	w	w	w	f	f	f	f
K	w	w	f	f	w	w	f	f
N	w	f	w	f	w	f	w	f
U

Gegeben sind die Aussagen B,{} V,{} G sowie die verknüpfte Aussage T mit

T \quad \equiv \quad \left(B \vee V\right) \wedge \left(\neg V \iff G\right). Bestimmen sie die Wahrheitswerte (f oder w) von T und tragen diese in die Felder ein.

B	w	w	w	w	f	f	f	f
V	w	w	f	f	w	w	f	f
G	w	f	w	f	w	f	w	f
T

18.4 Rechenregeln

Um sicherer mit den Verknüpfungen umzugehen, ist es notwendig einige Rechenregeln zu kennen.

• Konjunktion und Disjunktion sind kommutativ:

\begin{align*} A\wedge B \equiv B \wedge A \qquad \text{und} \qquad A\vee B \equiv B \vee A \end{align*}

• Konjunktion und Disjunktion sind assoziativ:

\begin{align*} (A \wedge B) \wedge C \equiv A \wedge (B \wedge C) \qquad \text{und} \qquad (A \vee B) \vee C \equiv A \vee (B \vee C) \end{align*}

• Distributivgesetze:

\begin{align*} A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C) \quad \text{und} \quad A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C) \end{align*}

Das Distributivgesetz gibt an, wie Konjunktion und Disjunktion zu behandeln sind, wenn diese gemeinsam in einem Ausdruck auftauchen. Dies ist analog zu Multiplikation und Addition bei den reellen Zahlen: a\cdot (b+c) = a\cdot b + a\cdot c.

• Absorptionsgesetze:

\begin{align*} A \vee (A \wedge B) \equiv A \quad \text{und} \quad A \wedge (A \vee B) \equiv A \end{align*}

• Neutralitätsgesetze:

\begin{align*} A \wedge A \equiv A \quad \text{und} \quad A \vee 0 \equiv A \end{align*}

• Dualität:

Jede Formel hat eine duale Formel, die man erhält, wenn man gleichzeitig

• wahr mit falsch vertauscht und
• \wedge mit \vee vertauscht.

Zum Beispiel:

A	B	A \wedge B		A	B	A \vee B
w	w	w		f	f	f
w	f	f		f	w	w
f	w	f		w	f	w
f	f	f		w	w	w

Aufgaben:

Überlegen Sie sich mit Hilfe einer Wahrheitstablle, warum die Regel A \vee (A \wedge B) \equiv A (oder alternativ die Regel A \wedge (A \vee B) \equiv A) Absorptionsgesetz heißt.

18.5 Aussageformen

Definition: Aussageform, Variable und Grundmenge

Eine Aussageform ist ein grammatischer Satz, an dem ein durch Zeichen (meist Buchstaben) gekennzeichnete Leerstelle auftritt. Das an der Leerstelle auftretende Zeichen heißt Variable, und steht für ein Element aus einer Grundmenge.

Beispiel:

Der Ausdruck A: 2m + 1 = 5 mit m \in \mathbb{N} ist offenbar keine Aussage im Sinne der Definition einer Aussage, da A keinen Wahrheitswert hat. Es handelt sich um eine Aussageform. Erst A(m) wird je nach m zu einer wahren oder falschen Aussage.

• A ist die Aussageform,
• m ist die Variable und
• \mathbb{N} = \{1, 2, \cdots\} die Grundmenge

Setzen wir nun ein Element aus der Grundmenge ein, so wird aus der Aussageform eine Aussage.

• A(1): 2\cdot 1 + 1 = 5 ist das Gleiche wie 3 = 5 ist eine falsche Aussage
• A(2): 2\cdot 2 + 1 = 5 ist das Gleiche wie 5 = 5 ist eine wahre Aussage

Definition: Lösung

Elemente der Grundmenge, die die Aussageform zu einer wahren Aussage machen, nennt man Lösungen der Aussageform. Alle Lösungen der Aussageform aus der Grundmenge nennt man die Lösungsmenge der Aussageform.

Im obigen Beispiel ist L = \{2\} die Lösungsmenge der Aussageform A.

Definition: Erfüllbarkeit, Kontradiktion, Tautologie

Man nennt eine Aussageform

• erfüllbar, wenn die Lösungsmenge nicht die leere Menge ist,
• eine Kontradiktion, wenn die Aussageform nicht erfüllbar ist und
• eine Tautologie, wenn jedes Element der Grundmenge die Aussageform erfüllt.

Aufgabe:

1. Wie lautet die Lösungsmenge der Ausageform B:\, k^2 = 9, mit k \in \mathbb{Z}?
2. Was liefert der Ausdruck (-3:3)^2 == 4 ?

Lösung

1. Die quadratische Gleichung hat in \mathbb{Z} zwei Lösungen: L = \{-3, 3\}.
2. Gibt man dies in die Konsole ein, so ergibt sich

(-3:3)^2 == 4

[1] FALSE  TRUE FALSE FALSE FALSE  TRUE FALSE

Um das Ergebnis zu verstehen, kann man den obigen Ausdruck nur teileweise ausführen, zum Beispiel:

(-3:3)

[1] -3 -2 -1  0  1  2  3

(-3:3)^2

[1] 9 4 1 0 1 4 9

18.6 Quantoren

Für Aussageformen gibt es neben den Junktoren auch noch die Quantoren. Diese machen aus einer Aussageform eine Aussage.

18.6.1 Existenzquantor \exists, \bigvee

Schreibweise und Aussprache:

Er wird mit der Variablen aus der Grundmenge geschrieben \exists x, \bigvee\limits_{x} und man liest

• für mindestens ein x gilt…
• es gibt mindestens ein x für das gilt…
• es existiert mindestens ein x für das gilt…

Wahrheitswerte:

Wie bereits erwähnt machen die Quantoren aus einer Aussageform eine Aussage. Der Ausdruck \exists x A(x) ist eine Aussage und genau dann wahr, wenn mindestens ein Element der Grundmenge die Aussageform zu einer wahren Aussage macht, ansonsten ist die Aussage falsch.

Beispiel:

Gegeben ist die Aussageform A: 2n + 1 = 5 und n \in \mathbb{N} sei eine natürliche Zahl, dann heißt \exists n A(n) oder etwas ausführlicher \exists n\in \mathbb{N} A(n):

Es gibt mindestens eine Zahl n aus der Grundmenge \mathbb{N}, so dass A(n) eine wahre Aussage ist.

Dies ist offenbar eine wahre Aussage, da die Aussage für n = 2 wahr ist. Es gibt einen Zusammenhang zur Disjunktion \vee, was auch die Schreibweise des Existenzquantors erklärt:

\begin{align*} \exists n A(n) = \bigwedge_{n} A(n) \; \equiv \; A(1) \wedge A(2) \wedge A(3) \wedge \cdots \end{align*}

Der Unterschied besteht darin, dass auch (überabzählbar) unendliche Grundmengen mit dem Quantoren behandelt werden können, während die Schreibweise mit Hilfe der Junktoren dies nicht zulässt.

18.6.2 Allquantor \forall, \bigwedge

Schreibweise und Aussprache:

Er wird mit der Variablen aus der Grundmenge geschrieben \forall x, \bigwedge\limits_{x} und man liest

• für alle x gilt …
• für jedes x gilt …

Wahrheitswerte

Der Ausdruck \forall x A(x) ist eine Aussage und genau dann wahr, wenn alle Element der Grundmenge die Aussageform zu einer wahren Aussage machen, ansonsten ist die Aussage falsch.

Beispiel

Gegeben ist die Aussageform A: 2n + 1 = 5 und n \in \mathbb{N} sei eine natürliche Zahl, dann heißt \forall n A(n) (oder etwas ausführlicher \bigwedge\limits_{n\in \mathbb{N}} A(n)):

Für alle (Zahlen) n aus der Grundmenge \mathbb{N} ist A(n) eine wahre Aussage.

Dies ist eine falsche Aussage, da die Aussage nur für n = 2 wahr ist. Auch hier gibt es wieder einen Zusammenhang zu den Junktoren, hier allerdings zur Konjunktion \vee:

\begin{align*} \forall n A(n) = \bigvee_{n} A(n) \; \equiv \; A(1) \vee A(2) \vee A(3) \vee \cdots \end{align*}

Wie auch schon beim Existenzquantor können bei der Quantorenschreibweise Grundmengen mit unendlichen vielen Elementen behandelt werden.

18.6.3 Satzformeln

Beispiel (Implikation):

Gibt man die beiden folgenden Aussageformen vor:

• A(x): x ist ein Säugetier und
• B(x): x ist ein Hund.

Schauen wir uns folgende Aussage(!) an: \bigwedge\limits_x (B(x) \implies A(x)).

Nur die Implikation B(x) \implies A(x) bedeutet: Wenn das Tier x ein Hund ist, dann ist das Tier x ein Säugetier.

Wie ändert sich das nun durch den Allquantor? Die kurze Antwort ist

Alle Hunde sind Säugetiere.

Wir könnten den gleichen Sachverhalt auch noch komplizierter formulieren und die Elemente x aus der Grundmenge in den Satz einbauen, aber das trägt nicht wirklich zum Verständnis bei.

Beispiel (Konjunktion, Disjunktion, Implikation und Äquivalenz)

Sehen wir uns nun die folgenden Aussageformen an

• Q(x): x ist ein Quadrat,
• K(x): x ist klein,
• G(x): x ist grün,
• L(x,y) x liegt links von y.

Die Grundmenge sind die Objekte in Abbildung 18.1, also Dreiecke und Quadrate in verschiedenen Größen und Farben.

Abbildung 18.1: Grafik zum Beispiel

Aufgaben, Teil 1

Zuerst formulieren wir ein paar Aussagen und bringen diese in eine mathematische Form:

1. Es gibt Objekte, die keine Quadrate sind.
2. Es gibt grüne Quadrate.
3. Alle großen Quadrate sind grün.
4. Es gibt große und kleine Quadrate.
5. Alle großen Objekte liegen links von den kleinen Objekten.
6. Dann und nur dann wenn ein Objekt klein ist, ist es kein grünes Quadrat.
7. Es ist nicht richtig, dass alle Quadrate groß sind.

Lösungen

1. Das ist noch relativ einfach: \bigvee\limits_{x} \neg Q(x)

2. Nun haben wir eine zusätzliche Bedingung, diese können wir mit Hilfe der Konjunktion hinzufügen: \bigvee\limits_{x} (Q(x) \wedge G(x)).

3. Analog zum vorherigen Fall geht es um große Quadrate (Konjunktion). Allerdings benötigen wir nun den Allquantor, da es um alle großen Quadrate geht und wir haben eine Folgerung, nämlich dass diese grün sind:

\begin{align*} \bigwedge\limits_{x} \Big(Q(x) \wedge \neg K(x) \implies G(x)\Big) \end{align*}

4. Bei diesem Satz muss man ein wenig aufpassen, denn wir haben haben zwei verschiedene Existenzaussagen gekoppelt.

\begin{align*} \left(\bigvee\limits_{x} \Big(Q(x) \wedge \neg K(x)\Big)\right) \wedge \left(\bigvee\limits_{y} \Big(Q(y) \wedge K(y)\Big)\right) \end{align*}

Wie man die Variablen nennt spielt keine Rolle. Daher kann man diese im zweiten Ausdruck auch y nennen, um diese klar vom linken Term abzugrenzen.

5. Hier haben wir nun zum ersten Mal die Aussageform L(x, y) Hier ist die Reihenfolge der vorkommenden Variablen x und y wichtig! Desweiteren benötigen wir auch zwei Quantoren, da alle Objekte betrachtet werden müssen.

\begin{align*} \bigwedge\limits_{y} \Big( \bigwedge\limits_{x} L(x, y) \wedge \neg K(x) \Big) \implies K(y) \end{align*}

Um den Ausdruck besser zu verstehen, zerlegt man diesen. So kann der Ausdruck \Big( \bigwedge\limits_{x} L(x, y) \wedge \neg K(x) \Big) gelesen werden als

“Alle nicht-kleinen Objekte liegen links von y”

6. Die Formulierung Dann und nur dann zeigt an, dass es sich um eine Äquivalenz zweier Aussagen handelt. Damit ergibt sich:

\begin{align*} \bigwedge\limits_{x} \Big(K(x) \iff \big(Q(x) \wedge \neg G(x)\big)\Big) \end{align*}

Aufgaben, Teil 2:

In einem zweiten Schritt können wir uns nun überlegen, ob diese Aussagen wahr oder falsch sind.

Lösungen

Offensich sind 1. bis 5. wahr. Einzig 6. ist nicht direkt klar. Sehen wir es uns das genauer an. Die Äquivalenz heißt Implikation in beide Richtungen. Die Richtung “wenn ein Objekt klein ist, dann ist es kein grünes Quadrat” stimmt. Die andere Richtung “wenn ein Objekt kein grünes Quadrat ist, dann ist es klein” ist aber falsch, da es auch ein Dreieck sein kann. Daher ist die Aussage falsch.

Aufgaben, Teil 3:

In einem letzten Teil kann man nun den umgekehrten Weg gehen und sich für gegebene Aussagen die Bedeutung überlegen und welchen Wahrheitswert diese haben:

\begin{align*} \bigwedge\limits_{x} \Big(\neg Q(x) \implies \neg K(x) \Big) \end{align*}

\begin{align*} \bigvee\limits_{x} \Big(Q(x) \vee \neg G(x) \Big) \end{align*}

\begin{align*} \bigvee\limits_{x} \Big(Q(x) \vee \neg G(x) \Big) \end{align*}

Lösungen

18.6.4 Quantoren in R

In R gibt es zwei Funktionen mit denen wir herausfinden können, ob in einem logischen Vektor mindestens einer (any()) oder alle (all()) Werte den Wahrheitswert TRUE haben.

any(..., na.rm = FALSE)

überprüft, ob in einem logischen Vektoren mindestens ein Eintrag TRUE ist. Die Ausgabe ist ein logischer Vektor der Länge 1, der TRUE ist, falls es mindestens einen Eintrag TRUE gibt, sost FALSE

all(..., na.rm = TRUE)

überprüft, ob in einem logischen Vektor alle Einträge TRUEsind. Die Ausgabe ist wieder ein logischer Vektor der Länge 1. Sollten alle Einträge in dem Vektor TRUE sein, so ist die Ausgabe TRUE, sonst FALSE.

x1 <- c(TRUE, TRUE)
x2 <- c(TRUE, FALSE)
x3 <- c(FALSE, FALSE)
y  <- c(TRUE, NA)

any(x2)

[1] TRUE

any(x1, x2, x3)

[1] TRUE

any(x3)

[1] FALSE

any(y)

[1] TRUE

any(y, na.rm = TRUE)

[1] TRUE

all(x1)

[1] TRUE

all(x2)

[1] FALSE

all(y)

[1] NA

all(y, na.rm = TRUE)

[1] TRUE

18.7 Übersicht Aussagenlogik

Tabelle 18.3: Übersicht Aussagenlogik, # gibt die Anzahl der Argumente an.

Name	Ausprägung	R	#	Anwendung	Aussprache
Wahrheitswert	wahr, w	TRUE, T	0		wahr
	falsch, f	FALSE, F	0		falsch
Negation (NOT)	\neg	!	1	\neg A	nicht A
Konjunktion (AND)	\wedge	&	2	A \wedge B	A und B
Disjunktion (OR)	\vee	|	2	A \vee B	A oder B
Implikation	\implies		2	A \implies B	A impliziert B
					wenn A dann B
					A ist hinreichend für B
					B ist notwendig für A
Äquivalenz	\iff		2	A \iff B	A äquivalent B
					A gilt genau dann wenn B gilt
					A notw. und hinr. für B
Allaussage	\forall, \bigwedge	all()	1	\forall x, \bigwedge_x	für alle x
					für jedes x
Existenzaussage	\exists, \bigvee	any()	1	\exists x, \bigvee_x	es existiert mind. ein x

Auflösung: Lügende Politiker

Zu guter Letzt wollen wir das Einstiegsbeispiel auflösen. Dazu müssen wir die Sätze des Politikers in Aussagen übersetzen.

• ,,Die Vollbeschäftigung wird erhalten oder die Steuern dürfen nicht erhöht werden.’’
• ,,Wenn sich Politiker um die Bevölkerung kümmern, müssen die Steuern angehoben werden.’’
• ,,Die Politiker kümmern sich um die Bevölkerung oder die Vollbeschäftigung kann nicht erhalten werden.’’
• ,,Es stimmt nicht, dass die Erhaltung der Vollbeschäftigung eine Steuererhöhung zur Folge haben muss.’’

In den Sätzen des Politikers kommen 3 Aussagen vor (über deren Wahrheitswert wir erstmal nichts wissen):

• V: Vollbeschäftigung erhalten,
• S: Steuern erhöhen,
• P: Politiker kümmern sich.

Diese können jeweils wahr oder falsch sein, womit wir insgesamt 2^3 = 8 verschiedene Möglichkeiten betrachten müssen.

Übersetzt man die Sätze des Politikers in mathematische Ausssagen, so ergibt sich:

• A_1: \, V \vee \neg S
• A_2: \, P \implies S
• A_3: \, P \vee \neg V
• A_4: \, \neg(V \implies S)

Wir erzeugen nun eine Wahrheitstabelle mit allen acht Möglichkeiten. Die Schritte, wie man zu den Wahrheitsweren der Spalten A_1 bis A_4 kommt, haben wir aus Platzgründen weggelassen. Es ist allerdings eine gute Übung sich diese zu überlegen.

Tabelle 18.4: Lösung der einleitenden Aufgabe (Lügende Politiker entlarven) mit Hilfe einer Wahrheitstabelle

V	P	S	A_1	A_2	A_3	A_4	\bigwedge A_i
w	w	w	w	w	w	f	f
w	w	f	w	f	w	w	f
w	f	w	w	w	f	f	f
w	f	f	w	w	f	w	f
f	w	w	f	w	w	f	f
f	w	f	w	f	w	f	f
f	f	w	f	w	w	f	f
f	f	f	w	w	w	f	f

Die letzte Spalte Dies bedeutet, dass es vollkommen egal ist welche Wahrheitswerte die einzelnen Aussagen (V, P, S) haben, der Politiker kann in keinem der Fälle die Wahrheit sagen!