19 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, 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)

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

    species island bill_len bill_dep flipper_len body_mass    sex year
1    Gentoo Biscoe     46.1     13.2         211      4500 female 2007
2    Gentoo Biscoe     50.0     16.3         230      5700   male 2007
3    Gentoo Biscoe     48.7     14.1         210      4450 female 2007
4    Gentoo Biscoe     50.0     15.2         218      5700   male 2007
5    Gentoo Biscoe     47.6     14.5         215      5400   male 2007
6    Gentoo Biscoe     46.5     13.5         210      4550 female 2007
7    Gentoo Biscoe     45.4     14.6         211      4800 female 2007
8    Gentoo Biscoe     46.7     15.3         219      5200   male 2007
9    Gentoo Biscoe     43.3     13.4         209      4400 female 2007
10   Gentoo Biscoe     46.8     15.4         215      5150   male 2007
11   Gentoo Biscoe     40.9     13.7         214      4650 female 2007
12   Gentoo Biscoe     49.0     16.1         216      5550   male 2007
13   Gentoo Biscoe     45.5     13.7         214      4650 female 2007
14   Gentoo Biscoe     48.4     14.6         213      5850   male 2007
15   Gentoo Biscoe     45.8     14.6         210      4200 female 2007
16   Gentoo Biscoe     49.3     15.7         217      5850   male 2007
17   Gentoo Biscoe     42.0     13.5         210      4150 female 2007
18   Gentoo Biscoe     49.2     15.2         221      6300   male 2007
19   Gentoo Biscoe     46.2     14.5         209      4800 female 2007
20   Gentoo Biscoe     48.7     15.1         222      5350   male 2007
21   Gentoo Biscoe     50.2     14.3         218      5700   male 2007
22   Gentoo Biscoe     45.1     14.5         215      5000 female 2007
23   Gentoo Biscoe     46.5     14.5         213      4400 female 2007
24   Gentoo Biscoe     46.3     15.8         215      5050   male 2007
25   Gentoo Biscoe     42.9     13.1         215      5000 female 2007
26   Gentoo Biscoe     46.1     15.1         215      5100   male 2007
27   Gentoo Biscoe     44.5     14.3         216      4100   <NA> 2007
28   Gentoo Biscoe     47.8     15.0         215      5650   male 2007
29   Gentoo Biscoe     48.2     14.3         210      4600 female 2007
30   Gentoo Biscoe     50.0     15.3         220      5550   male 2007
31   Gentoo Biscoe     47.3     15.3         222      5250   male 2007
32   Gentoo Biscoe     42.8     14.2         209      4700 female 2007
33   Gentoo Biscoe     45.1     14.5         207      5050 female 2007
34   Gentoo Biscoe     59.6     17.0         230      6050   male 2007
35   Gentoo Biscoe     49.1     14.8         220      5150 female 2008
36   Gentoo Biscoe     48.4     16.3         220      5400   male 2008
37   Gentoo Biscoe     42.6     13.7         213      4950 female 2008
38   Gentoo Biscoe     44.4     17.3         219      5250   male 2008
39   Gentoo Biscoe     44.0     13.6         208      4350 female 2008
40   Gentoo Biscoe     48.7     15.7         208      5350   male 2008
41   Gentoo Biscoe     42.7     13.7         208      3950 female 2008
42   Gentoo Biscoe     49.6     16.0         225      5700   male 2008
43   Gentoo Biscoe     45.3     13.7         210      4300 female 2008
44   Gentoo Biscoe     49.6     15.0         216      4750   male 2008
45   Gentoo Biscoe     50.5     15.9         222      5550   male 2008
46   Gentoo Biscoe     43.6     13.9         217      4900 female 2008
47   Gentoo Biscoe     45.5     13.9         210      4200 female 2008
48   Gentoo Biscoe     50.5     15.9         225      5400   male 2008
49   Gentoo Biscoe     44.9     13.3         213      5100 female 2008
50   Gentoo Biscoe     45.2     15.8         215      5300   male 2008
51   Gentoo Biscoe     46.6     14.2         210      4850 female 2008
52   Gentoo Biscoe     48.5     14.1         220      5300   male 2008
53   Gentoo Biscoe     45.1     14.4         210      4400 female 2008
54   Gentoo Biscoe     50.1     15.0         225      5000   male 2008
55   Gentoo Biscoe     46.5     14.4         217      4900 female 2008
56   Gentoo Biscoe     45.0     15.4         220      5050   male 2008
57   Gentoo Biscoe     43.8     13.9         208      4300 female 2008
58   Gentoo Biscoe     45.5     15.0         220      5000   male 2008
59   Gentoo Biscoe     43.2     14.5         208      4450 female 2008
60   Gentoo Biscoe     50.4     15.3         224      5550   male 2008
61   Gentoo Biscoe     45.3     13.8         208      4200 female 2008
62   Gentoo Biscoe     46.2     14.9         221      5300   male 2008
63   Gentoo Biscoe     45.7     13.9         214      4400 female 2008
64   Gentoo Biscoe     54.3     15.7         231      5650   male 2008
65   Gentoo Biscoe     45.8     14.2         219      4700 female 2008
66   Gentoo Biscoe     49.8     16.8         230      5700   male 2008
67   Gentoo Biscoe     46.2     14.4         214      4650   <NA> 2008
68   Gentoo Biscoe     49.5     16.2         229      5800   male 2008
69   Gentoo Biscoe     43.5     14.2         220      4700 female 2008
70   Gentoo Biscoe     50.7     15.0         223      5550   male 2008
71   Gentoo Biscoe     47.7     15.0         216      4750 female 2008
72   Gentoo Biscoe     46.4     15.6         221      5000   male 2008
73   Gentoo Biscoe     48.2     15.6         221      5100   male 2008
74   Gentoo Biscoe     46.5     14.8         217      5200 female 2008
75   Gentoo Biscoe     46.4     15.0         216      4700 female 2008
76   Gentoo Biscoe     48.6     16.0         230      5800   male 2008
77   Gentoo Biscoe     47.5     14.2         209      4600 female 2008
78   Gentoo Biscoe     51.1     16.3         220      6000   male 2008
79   Gentoo Biscoe     45.2     13.8         215      4750 female 2008
80   Gentoo Biscoe     45.2     16.4         223      5950   male 2008
81   Gentoo Biscoe     49.1     14.5         212      4625 female 2009
82   Gentoo Biscoe     52.5     15.6         221      5450   male 2009
83   Gentoo Biscoe     47.4     14.6         212      4725 female 2009
84   Gentoo Biscoe     50.0     15.9         224      5350   male 2009
85   Gentoo Biscoe     44.9     13.8         212      4750 female 2009
86   Gentoo Biscoe     50.8     17.3         228      5600   male 2009
87   Gentoo Biscoe     43.4     14.4         218      4600 female 2009
88   Gentoo Biscoe     51.3     14.2         218      5300   male 2009
89   Gentoo Biscoe     47.5     14.0         212      4875 female 2009
90   Gentoo Biscoe     52.1     17.0         230      5550   male 2009
91   Gentoo Biscoe     47.5     15.0         218      4950 female 2009
92   Gentoo Biscoe     52.2     17.1         228      5400   male 2009
93   Gentoo Biscoe     45.5     14.5         212      4750 female 2009
94   Gentoo Biscoe     49.5     16.1         224      5650   male 2009
95   Gentoo Biscoe     44.5     14.7         214      4850 female 2009
96   Gentoo Biscoe     50.8     15.7         226      5200   male 2009
97   Gentoo Biscoe     49.4     15.8         216      4925   male 2009
98   Gentoo Biscoe     46.9     14.6         222      4875 female 2009
99   Gentoo Biscoe     48.4     14.4         203      4625 female 2009
100  Gentoo Biscoe     51.1     16.5         225      5250   male 2009
101  Gentoo Biscoe     48.5     15.0         219      4850 female 2009
102  Gentoo Biscoe     55.9     17.0         228      5600   male 2009
103  Gentoo Biscoe     47.2     15.5         215      4975 female 2009
104  Gentoo Biscoe     49.1     15.0         228      5500   male 2009
105  Gentoo Biscoe     47.3     13.8         216      4725   <NA> 2009
106  Gentoo Biscoe     46.8     16.1         215      5500   male 2009
107  Gentoo Biscoe     41.7     14.7         210      4700 female 2009
108  Gentoo Biscoe     53.4     15.8         219      5500   male 2009
109  Gentoo Biscoe     43.3     14.0         208      4575 female 2009
110  Gentoo Biscoe     48.1     15.1         209      5500   male 2009
111  Gentoo Biscoe     50.5     15.2         216      5000 female 2009
112  Gentoo Biscoe     49.8     15.9         229      5950   male 2009
113  Gentoo Biscoe     43.5     15.2         213      4650 female 2009
114  Gentoo Biscoe     51.5     16.3         230      5500   male 2009
115  Gentoo Biscoe     46.2     14.1         217      4375 female 2009
116  Gentoo Biscoe     55.1     16.0         230      5850   male 2009
117  Gentoo Biscoe     44.5     15.7         217      4875   <NA> 2009
118  Gentoo Biscoe     48.8     16.2         222      6000   male 2009
119  Gentoo Biscoe     47.2     13.7         214      4925 female 2009
120  Gentoo Biscoe       NA       NA          NA        NA   <NA> 2009
121  Gentoo Biscoe     46.8     14.3         215      4850 female 2009
122  Gentoo Biscoe     50.4     15.7         222      5750   male 2009
123  Gentoo Biscoe     45.2     14.8         212      5200 female 2009
124  Gentoo Biscoe     49.9     16.1         213      5400   male 2009

In diesem Beispiel werden aus dem Datensatz penguins alle Beobachtungen herausgefiltert, bei denen species gleich "Gentoo" ist, das Argument species == "Gentoo" eine wahre Aussage (TRUE) ist.

19.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 11.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.

Analog gibt es seit R 4.6.0 auch den Operator %notin% der einer Negation des obigen Ausdrucks entspricht.

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

[1]  TRUE FALSE  TRUE FALSE

Praktische Anwendungen dieser Operatoren finden sich im Zusammenhang mit dem Filtern von Daten in Datentabellen in Kapitel 17.3.

19.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.

19.3 Wahrheitstabellen

Mit Hilfe einer Wahrheitstabelle können alle Wahrheitswerte, die eine (abgeleitete) Aussage haben kann gleichzeitig gezeigt werden. In Tabelle 19.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 19.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 19.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 O,{} J,{} S sowie die verknüpfte Aussage W mit

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

O	w	w	w	w	f	f	f	f
J	w	w	f	f	w	w	f	f
S	w	f	w	f	w	f	w	f
W

Gegeben sind die Aussagen P,{} X,{} U sowie die verknüpfte Aussage Q mit

Q \quad \equiv \quad \neg \left(P \wedge \neg X\right) \vee \left(X \iff U\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
X	w	w	f	f	w	w	f	f
U	w	f	w	f	w	f	w	f
Q

Gegeben sind die Aussagen T,{} V,{} H sowie die verknüpfte Aussage W mit

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

T	w	w	w	w	f	f	f	f
V	w	w	f	f	w	w	f	f
H	w	f	w	f	w	f	w	f
W

Gegeben sind die Aussagen X,{} B,{} R sowie die verknüpfte Aussage V mit

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

X	w	w	w	w	f	f	f	f
B	w	w	f	f	w	w	f	f
R	w	f	w	f	w	f	w	f
V

Gegeben sind die Aussagen H,{} I,{} V sowie die verknüpfte Aussage Q mit

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

H	w	w	w	w	f	f	f	f
I	w	w	f	f	w	w	f	f
V	w	f	w	f	w	f	w	f
Q

Gegeben sind die Aussagen D,{} L,{} O sowie die verknüpfte Aussage C mit

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

D	w	w	w	w	f	f	f	f
L	w	w	f	f	w	w	f	f
O	w	f	w	f	w	f	w	f
C

Gegeben sind die Aussagen P,{} V,{} B sowie die verknüpfte Aussage C mit

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

P	w	w	w	w	f	f	f	f
V	w	w	f	f	w	w	f	f
B	w	f	w	f	w	f	w	f
C

Gegeben sind die Aussagen F,{} K,{} Y sowie die verknüpfte Aussage D mit

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

F	w	w	w	w	f	f	f	f
K	w	w	f	f	w	w	f	f
Y	w	f	w	f	w	f	w	f
D

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

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

G	w	w	w	w	f	f	f	f
O	w	w	f	f	w	w	f	f
U	w	f	w	f	w	f	w	f
B

Gegeben sind die Aussagen M,{} N,{} X sowie die verknüpfte Aussage P mit

P \quad \equiv \quad \neg \left(M \implies \neg N\right) \vee \neg \left(\neg N \iff X\right). Bestimmen sie die Wahrheitswerte (f oder w) von P und tragen diese in die Felder ein.

M	w	w	w	w	f	f	f	f
N	w	w	f	f	w	w	f	f
X	w	f	w	f	w	f	w	f
P

Gegeben sind die Aussagen K,{} D,{} F sowie die verknüpfte Aussage O mit

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

K	w	w	w	w	f	f	f	f
D	w	w	f	f	w	w	f	f
F	w	f	w	f	w	f	w	f
O

Gegeben sind die Aussagen C,{} X,{} I sowie die verknüpfte Aussage H mit

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

C	w	w	w	w	f	f	f	f
X	w	w	f	f	w	w	f	f
I	w	f	w	f	w	f	w	f
H

19.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.

19.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:

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

Lösung

Die quadratische Gleichung hat in \mathbb{Z} zwei Lösungen: L = \{-3, 3\}.
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 teilweise 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

19.6 Quantoren

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

19.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.

19.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.

19.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 19.1, also Dreiecke und Quadrate in verschiedenen Größen und Farben.

Aufgaben, Teil 1

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

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

Lösungen

Das ist noch relativ einfach: \bigvee\limits_{x} \neg Q(x)
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)).
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*}

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.

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”

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*}

Lösungen

19.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

19.7 Übersicht Aussagenlogik

Tabelle 19.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 19.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!