Diskrete Mathematik 1

Berner Fachhochschule - Technik und Informatik

Fachbereich Informatik
Dr. W. Businger
Dr. V. Bigler-Maillart
HS 2019/20
Diese Seite ist leer.
Inhaltsverzeichnis
1 Aussagenlogik 1
1.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Die Konjunktion A ^ B . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Die Disjunktion A _ B . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Die Negation ¬A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Zusammengesetzte Aussagen . . . . . . . . . . . . . . . . . . . . . . . . 3
1.6 Disjunktive Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.7 Tautologien und Kontradiktionen . . . . . . . . . . . . . . . . . . . . . . 5
1.8 Logische Äquivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.9 Die Implikation oder Subjunktion . . . . . . . . . . . . . . . . . . . . . . 7
1.10 Äquivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.11 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.12 Syntax und Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Fortsetzung der Logik 12

2.1 Aussageformen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Quantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Beweistechniken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Mengenlehre 17
3.1 Mengen und Elemente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Teilmengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Vereinigung, Durchschnitt und Komplement . . . . . . . . . . . . . . . . 19
3.4 Mengenalgebra, Dualität . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Mengensystem, Potenzmenge, Partition . . . . . . . . . . . . . . . . . . 22
3.6 Geordnete Paare, n-Tupel und Produktmengen . . . . . . . . . . . . . . 23
3.7 Endliche Mengen, Ein- und Ausschlussformel . . . . . . . . . . . . . . . 24

4 Begri↵ der Funktion (Abbildung) 26

4.1 Definition einer Funktion (Abbildung) . . . . . . . . . . . . . . . . . . . 26
4.2 Graph einer Funktion (Abbildung) . . . . . . . . . . . . . . . . . . . . . 28
4.3 Injektive, surjektive und bijektive Funktionen . . . . . . . . . . . . . . . 29
4.4 Verkettung oder Hintereinanderausführung von Funktionen . . . . . . . 32
4.5 Umkehrfunktion (inverse Abbildung) . . . . . . . . . . . . . . . . . . . . 32

5 Mengenlehre (Fortsetzung) 37
5.1 Mächtigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6 Die natürlichen Zahlen 40

6.1 Die Axiome von Peano . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.2 Das Prinzip der vollständigen Induktion . . . . . . . . . . . . . . . . . . 40
6.3 Starke Induktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.4 Fakultäten, Binomialkoeffizienten und Binomischer Lehrsatz . . . . . . . 47
6.5 Die Primzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.6 Der grösste gemeinsame Teiler (ggT) und der euklidische Algorithmus . 53
6.6.1 Ganzzahlige Division mit Rest . . . . . . . . . . . . . . . . . . . 53
6.6.2 Der euklidische Algorithmus . . . . . . . . . . . . . . . . . . . . . 54
6.6.3 Anzahl Schritte im euklidischen Algorithmus . . . . . . . . . . . 55
6.6.4 Eine Folgerung aus dem euklidischen Algorithmus . . . . . . . . 57

i
 6.6.5 Das kleinste gemeinsame Vielfache (kgV) . . . . . . . . . . . . . 58
6.7 Die ganzen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.7.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.7.2 Die Kongruenzrelation . . . . . . . . . . . . . . . . . . . . . . . . 59
6.8 Lineare diophantische Gleichungen . . . . . . . . . . . . . . . . . . . . . 63
6.9 Der chinesische Restsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

7 Kryptologie 68
7.1 Der kleine Fermatsche Satz . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.2 Eulersche Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.3 RSA-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.4 Schnelles Potenzieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.5 Sicherheit des RSA-Verfahrens . . . . . . . . . . . . . . . . . . . . . . . 74
7.6 Erzeugung von Primzahlen . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.7 Digitale Unterschriften . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7.8 Wahl des ö↵entlichen Schlüssels e . . . . . . . . . . . . . . . . . . . . . . 79

8 Relationen 80
8.1 Relationen auf einer Menge A . . . . . . . . . . . . . . . . . . . . . . . . 80
8.2 Eigenschaften von Relationen . . . . . . . . . . . . . . . . . . . . . . . . 81
8.3 Äquivalenzrelationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.4 Ordnungsrelationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.5 Topologisches Sortieren . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.6 Relationen von einer Menge A nach einer Menge B . . . . . . . . . . . . 89

Stichwortverzeichnis 91

ii
1 Aussagenlogik
1.1 Einführung
Unter einer Aussage verstehen wir in der Aussagenlogik ein sprachliches Gebilde, das
entweder wahr (richtig) oder falsch ist. Die Wahrheit oder die Falschheit einer Aussage
wird als ihr Wahrheitswert bezeichnet. Da es nur zwei Möglichkeiten gibt, nennt man
die Aussagenlogik zweiwertig.

Beispiel 1 Wir wollen untersuchen, welche der folgenden sprachlichen Gebilde Aus-
sagen (im mathematischen Sinne) sind; im Falle einer Aussage wollen wir ihren Wahr-
heitswert bestimmen.

(a) 3 ist eine Primzahl“

”
(b) Es gibt keine gerade Primzahl“
”
(c) Was für ein hübsches Kind!“
”
(d) 5+13=9“
”
(e) Es gibt unendlich viele Primzahlen“
”
(f ) Es gibt unendlich viele Primzahlzwillinge“ (dies ist eine Aussage von der man
”
bis heute nicht weiss, ob sie richtig oder falsch ist)
(g) Jede gerade natürliche Zahl, die grösser als 2 ist, lässt sich als Summe zweier
”
Primzahlen darstellen“ (dies ist die sogenannte Goldbachsche1 Vermutung, die
bis heute weder bewiesen noch widerlegt wurde)
(h) Welche Farbe besitzt dieses Auto ?“
”
(i) Am 3. März 1549 regnete es in Zürich“
”
(j) Diese Aussage ist falsch.“
”
Die Lösung wird im Unterricht erarbeitet. 3

Wir können Aussagen durch logische Operationen miteinander verknüpfen und erhalten
so zusammengesetzte Aussagen. Wie wir sehen werden, hängt der Wahrheitswert einer
zusammengesetzten Aussagen nur von den Wahrheitswerten der Teilaussagen und der
Art der Verknüpfung ab.

1.2 Die Konjunktion A ^ B

Zwei Aussagen A und B können durch das Wort und“ zu einer neuen Aussage A ^ B
”
verknüpft werden. Diese neue Aussage heisst Konjunktion von A und B. Der Wahr-
heitswert von A ^ B wird durch die folgende Tabelle definiert, die man als Wahrheits-
tabelle bezeichnet:

A B A^B
w w w
w f f
f w f
f f f
1
Christian von Goldbach (1690-1764): preussischer Jurist und Mathematiker

1
Aus dieser Tabelle entnehmen wir, dass die zusammengesetzte Aussage A ^ B genau
dann wahr ist, wenn die beiden Teilaussagen A und B beide wahr sind.
Beispiel 2 Bestimmen Sie die Wahrheitswerte der folgenden Aussagen:
(a) 3 > 2 ^ 1 > 3“
”
(b) 2 ist eine Primzahl und 3 ist ein Teiler von 29’751.“
”
Die Lösung wird im Unterricht erarbeitet. 3

1.3 Die Disjunktion A _ B

Zwei Aussagen A und B können wir durch das Wort oder“ zu einer neuen Aussage A_B
”
verknüpfen. Diese neue Aussage heisst Disjunktion von A und B. Der Wahrheitswert
von A _ B wird durch die folgende Wahrheitstabelle definiert
A B A_B
w w w
w f w
f w w
f f f
Die Aussage A _ B ist also genau dann falsch, wenn beide Teilaussagen A und B falsch
sind.
In der Umgangssprache verwendet man oder“ häufig im Sinne von entweder
” ”
oder“. Beispielsweise sagt man: Ich werde an der Fachhochschule Nordwestschweiz
”
in Brug/Windisch oder an der Berner Fachhochschule - Technik und Informatik in Bi-
el studieren.“ In der Mathematik hingegen wird das Wort oder“ stets im Sinne von
”
und/oder“ verwendet. Dies bedeutet eben, dass die Aussage A _ B auch dann wahr
”
ist, wenn beide Teilaussagen A und B wahr sind. Die Aussage Das Dreieck ABC ist
”
rechtwinklig oder gleichschenklig“ ist also auch richtig, wenn das Dreieck rechtwinklig
und gleichschenklig ist.
Es gibt jedoch auch in der Umgangssprache Beispiele, wo oder“ im mathematischen
”
Sinne von und/oder“ verwendet wird. Als Beispiel möge die Aussage Es ist verboten
” ”
zu rauchen oder auf den Boden zu spucken“ dienen.
Beispiel 3 Geben Sie die Wahrheitstabelle von entweder oder“ an. Das exklusive oder
”
wird oft mit XOR (eXclusive OR) bezeichnet. Wir verwenden als Verknüpfungszeichen
.
Die Lösung wird im Unterricht erarbeitet. 3

1.4 Die Negation ¬A

Für eine beliebige Aussage A ist es möglich, ihre Negation zu bilden, indem wir es ist
”
falsch, dass. . .“ vor A schreiben oder indem wir in A das Wort nicht“ einfügen. Sym-
”
bolisch schreibt man: ¬A . Der Wahrheitswert von ¬A ist durch die folgende Wahrheits-
tabelle definiert:
A ¬A
w f
f w
Falls also A wahr ist, so ist ¬A falsch, und falls A falsch ist, so ist ¬A wahr.

2
1.5 Zusammengesetzte Aussagen
Mit Hilfe der Verknüpfungssymbole ^, _, ¬ können wir bereits sehr komplexe Aussagen
aufbauen. Wie wir bereits erwähnt haben, hängt der Wahrheitswert der zusammenge-
setzten Aussage nur von den Wahrheitswerten der Teilaussagen und der verwendeten
Verknüpfungen ab. Wir werden oft die Teilaussagen A, B, C, . . . als Variablen ansehen,
die die Werte w bzw. f annehmen. Der Wahrheitswert der zusammengesetzten Aussage
ist dann eine Funktion dieser Variablen, was wir durch die Notation P (A, B, C, . . .)
ausdrücken.

Um eine zusammengesetzte Aussage studieren zu können, müssen wir ihre Wahrheits-

tabelle herleiten. Betrachten wir beispielsweise die Aussage ¬(A ^ ¬B). Die Wahrheits-
tabelle dieser Aussage lautet:
A B ¬B A ^ ¬B ¬(A ^ ¬B)
w w f f w
w f w w f
f w f f w
f f w f w
Beachten Sie, dass die ersten Kolonnen für die Teilaussagen A und B reserviert sind.
Die Tabelle muss soviele Zeilen enthalten wie es Kombinationen von w und f bezüglich
dieser Teilaussagen gibt. Im Fall von zwei Teilaussagen gibt es o↵enbar 4 Kombinatio-
nen.

Beispiel 4 (a) Wie viele Zeilen besitzt die Wahrheitstabelle der zusammengesetzten
Aussage P (A1 , A2 , . . . , An ) ?
(b) Wie viele verschiedene Wahrheitstabellen sind möglich für n verschiedene Teil-
aussagen?
Die Lösung wird im Unterricht erarbeitet. 3

Beispiel 5 Bestimmen Sie die Wahrheitstabelle der zusammengesetzten Aussage

A ^ (B _ ¬C) .

Die Lösung wird im Unterricht erarbeitet. 3

1.6 Disjunktive Normalform

Nachdem wir die Wahrheitstabelle eine zusammengesetzten Aussage herleiten können,
wenden wir uns nun dem umgekehrten Problem zu. Gegeben ist eine Wahrheitstabelle,
gesucht eine zusammengesetzte Aussage, deren Wahrheitstabelle gleich der vorgebenen
Tabelle ist. Dazu definieren wir:

Definition 1 Seien m, n 2 N . Eine zusammengesetze Aussage P (A1 , . . . , An ) der

Form
P1 (A1 , . . . , An ) _ P2 (A1 , . . . , An ) _ . . . _ Pm (A1 , . . . , An )
heisst disjunktive Normalform, wenn jede Teilaussage Pi (A1 , . . . , An ) nur aus Kon-
junktionen der Aussagen Ai oder ihrer Negationen besteht. In diesen Teilaussagen

3
müssen nicht alle Variablen Ai vorkommen. Es darf auch nur eine einzige Variable
oder ihre Negation vorkommen. Falls in jeder Teilaussage entweder jede Variable oder
ihre Negation genau einmal vorkommt spricht man von der kanonischen disjunkti-
ven Normalform.

Beispiel 6 Welche der folgenden zusammengesetzten Aussagen sind disjunktive Nor-

malformen?
(a) A _ (¬B ^ D) _ ¬C _ (A ^ B)
(b) A _ B _ C _ ¬D
(c) A ^ B ^ C ^ ¬(A ^ D)
(d) A ^ ¬B ^ ¬A ^ ¬¬C

Die Lösung wird im Unterricht erarbeitet. 3

Zu einer beliebigen Wahrheitstabelle, in der mindestens eine Zeile wahr ist, lässt
sich eine kanonische disjunktive Normalform finden. Dazu gehen wir wie folgt vor:
(1) Für jede Zeile der Wahrheitstabelle, die wahr ist, bilden wir die Konjunktion aller
Teilaussagen, deren Wahrheitswert in dieser Zeile wahr ist, und der Negationen
aller Teilaussagen, deren Wahrheitswert in dieser Zeile falsch ist.
(2) Die so erhaltenen Konjunktionen verbinden wir schliesslich durch Disjunktionen.

Beispiel 7 Konstruieren Sie mit der obigen Methode die kanonische disjunktive Nor-
malform, die zur folgenden Wahrheitstabelle gehört:
A B C P (A, B, C)
w w w f
w w f w
w f w w
w f f f
f w w w
f w f f
f f w f
f f f f

Die Lösung wird im Unterricht erarbeitet. 3

Beispiel 8 Finden Sie eine zusammengesetzte Aussage, die zu folgender Wahrheitsta-

belle gehört:
A B C P (A, B, C)
w w w w
w w f w
w f w f
w f f w
f w w f
f w f f
f f w w
f f f f
Die Lösung wird im Unterricht erarbeitet. 3

4
Für Wahrheitstabellen, die in allen Zeilen falsch sind, kann das obige Verfahren nicht
angewendet werden. Aber in diesem Fall ist es einfach eine zusammengesetzte Aussage
zu finden, deren Wahrheitswert stets f“ ist. Falls es beispielsweise 3 Teilaussagen A, B
”
und C gibt, so kann man die zusammengesetzte Aussage

(A ^ ¬A) ^ (B ^ ¬B) ^ (C ^ ¬C)

verwenden. Damit haben wir den folgenden Satz bewiesen:

Satz 1 Mit Hilfe der Junktoren ^, _ und ¬ lässt sich für jede Wahrheitstabelle eine
zusammengesetzte Aussage finden, die ihr entspricht.

1.7 Tautologien und Kontradiktionen

Es gibt zusammengesetzte Aussagen P (A, B, . . .), die in der letzten Kolonne der Wahr-
heitstabelle nur den Wert w besitzen, das heisst, sie sind wahr unabhängig von den
Wahrheitswerten ihrer Variablen. Solche Aussagen werden Tautologien genannt. Ein
Beispiel für eine Tautologie ist die Aussage A _ ¬A, deren Wahrheitstabelle gegeben ist
durch
A ¬A A _ ¬A
w f w
f w w

Analog existieren zusammengesetzte Aussagen P (A, B, . . .), die in der letzten Kolonne
ihrer Wahrheitstabelle nur den Wert f besitzen, das heisst, sie sind falsch unabhängig
von den Wahrheitswerten ihrer Variablen. Solche Aussagen werden Kontradiktionen
genannt. Ein Beispiel einer Kontradiktion ist die Aussage A ^ ¬A, deren Wahrheitsta-
belle gegeben ist durch

A ¬A A ^ ¬A
w f f
f w f

Beispiel 9 Bestimmen Sie die Wahrheitstabelle der Aussage (A ^ B) _ ¬(A ^ B).

Die Lösung wird im Unterricht erarbeitet. 3

Satz 2 (Substitutionsprinzip) Falls P (A1 , A2 , . . .) eine Tautologie ist, dann ist

P (P1 , P2 , . . .) für beliebige Aussagen P1 , P2 , . . . ebenfalls eine Tautologie.

1.8 Logische Äquivalenz

Zwei zusammengesetzte Aussagen P (A, B, . . .) und Q(A, B, . . .) heissen logisch äqui-
valent, wenn sie die gleichen Wahrheitstabellen besitzen. In diesem Fall schreiben wir

P (A, B, . . .) ⌘ Q(A, B, . . .) .

Beispiel 10 Zeigen Sie, dass die beiden zusammengesetzten Aussagen ¬(A ^ B) und
¬A _ ¬B logisch äquivalent sind.
Die Lösung wird im Unterricht erarbeitet. 3

5
Eine logische Äquivalenz zwischen zwei Aussagen ist nichts anderes als ein logisches
Gesetz. Die nachfolgende Tabelle enthält die wichtigsten Gesetze der Aussagenlogik. In
dieser Tabelle steht T für eine Tautologie (ist immer true“) und F für eine Kontra-
”
diktion (ist immer false“).
”
Wir können diese Gesetze sehr einfach beweisen, indem wir zeigen, dass die Wahr-
heitstabellen der beiden Aussagen links und rechts vom ⌘ Zeichen identisch sind.

Gesetze der Aussagenlogik

Idempotenz
1a) A ^ A ⌘ A 1b) A _ A ⌘ A
Assoziativgesetz
2a) (A ^ B) ^ C ⌘ A ^ (B ^ C) 2b) (A _ B) _ C ⌘ A _ (B _ C)
Kommutativgesetz
3a) A ^ B ⌘ B ^ A 3b) A _ B ⌘ B _ A
Distributivgesetz
4a) A ^ (B _ C) ⌘ (A ^ B) _ (A ^ C) 4b) A _ (B ^ C) ⌘ (A _ B) ^ (A _ C)
Identitätsgesetz
5a) A ^ F ⌘ F 5b) A _ T ⌘ T
6a) A ^ T ⌘ A 6b) A _ F ⌘ A
Gesetz der doppelten Verneinung
7) ¬(¬A) ⌘ A
Komplemente
8a) A ^ ¬A ⌘ F 8b) A _ ¬A ⌘ T
9a) ¬T ⌘ F 9b) ¬F ⌘ T
Gesetz von de Morgan
10a) ¬(A ^ B) ⌘ ¬A _ ¬B 10b) ¬(A _ B) ⌘ ¬A ^ ¬B

Beispiel 11 Beweisen Sie das Gesetz 4a) und das Gesetz 10b).
Die Lösung wird im Unterricht erarbeitet. 3

Beispiel 12 Verneinen Sie die folgenden Aussagen:

(a) Die Rose ist rot und wohlriechend“.
”
(b) Heute gehe ich ins Kino oder ich lese ein Buch“
”
(c) 3 > 2“
”
(d) 3 > 2 und 1 < 0“
”
Die Lösung wird im Unterricht erarbeitet. 3

Beispiel 13 Wenden Sie die Gesetze von de Morgan an, um die folgenden Aussagen
zu vereinfachen:
(a) Es ist nicht wahr, dass seine Mutter eine Engländerin und sein Vater ein Franzose
”
ist.“
(b) Es ist nicht wahr, dass sie Maschinentechnik aber nicht Informatik studiert“
”
(c) Es ist nicht wahr, dass die Computer schneller werden und ihre Preise abneh-
”
men.“

6
 (d) Es ist nicht wahr, dass es nicht kalt ist oder regnet.“
”
Die Lösung wird im Unterricht erarbeitet. 3

Beispiel 14 Beweisen Sie die folgenden Gesetze:

A ^ (A _ B) ⌘ A
A _ (A ^ B) ⌘ A
A ^ (¬A _ B) ⌘ A^B
A _ (¬A ^ B) ⌘ A_B

Diese Gesetze heissen Absorptionsgesetze.

Die Lösung wird im Unterricht erarbeitet. 3

Die Gesetze der Aussagenlogik gestatten uns logische Ausdrücke umzuformen und ins-
besondere zu vereinfachen. Dazu ein Beispiel:

Beispiel 15 Vereinfachen Sie die folgenden Ausdrücke:

(a) (A ^ ¬B) _ (A ^ B)
(b) (A _ ¬B) ^ (¬A _ ¬B)
(c) (A ^ (¬(¬A _ B))) _ (A ^ B)

Die Lösung wird im Unterricht erarbeitet. 3

1.9 Die Implikation oder Subjunktion

Viele Aussagen, besonders in der Mathematik, besitzen die Form: Wenn A, dann B.
Solche Aussagen heissen Implikationen und werden mit der Schreibweise

A)B

bezeichnet. Manchmal verwendet man einen längeren Pfeil =) . Die Implikation A )

B wird oft so gelesen:

(a) Wenn A dann B“

”
(b) Aus A folgt B“
”
(c) A impliziert B“
”
(d) B ist notwendig für A“
”
(e) A ist hinreichend für B“
”
Betrachten wir ein Beispiel. Seien A und B die Aussagen Es hat Nebel.“ bzw. Die
” ”
Sicht ist schlecht.“. Dann können wir die Aussage A ) B auf die folgenden, völlig
gleichwertigen Arten wiedergeben:

(a) Wenn es Nebel hat, dann ist die Sicht schlecht.“

”
(b) Aus der Tatsache, dass es Nebel hat, folgt schlechte Sicht.“
”

7
 (c) Die Tatsache, dass es Nebel hat, impliziert, dass die Sicht schlecht ist.“
”
(d) Notwendig dafür, dass es Nebel hat, ist schlechte Sicht.“
”
(d) Hinreichend dafür, dass die Sicht schlecht ist, ist Nebel.“
”
Wir werden später noch Beispiele aus der Mathematik antre↵en.

Die Wahrheitstabelle von A ) B lautet:

A B A)B
w w w
w f f
f w w
f f w

Beispiel 16 Bestimmen Sie die Wahrheitstabelle von ¬A _ B.

Die Lösung wird im Unterricht erarbeitet. 3

Beachten Sie, dass die Implikation A ) B nur dann falsch ist, wenn der erste Teil
A wahr ist und der zweite Teil B falsch ist. Im Fall, wo A falsch ist, ist die Aussage
A ) B wahr, unabhängig vom Wahrheitswert von B. Die Aussagen

Falls das Quadrat ein Kreis ist, dann ist der Schnee rot“ (1)
”
und
Falls der Hund ein Huhn ist, dann ist der Schnee weiss“ (2)
”
sind folglich richtige Aussagen.
Um zu zeigen, dass die Aussage A ) B wahr ist, genügt es also zu zeigen, dass die
Wahrheit von A die Wahrheit von B nach sich zieht.
In der Umgangssprache verwendet man die beiden Implikationen (1) und (2) nicht,
denn es existiert überhaupt kein Zusammenhang zwischen der Hypothese und der
Schlussfolgerung. In der Logik ist der Begri↵ der Implikation viel weiter gefasst. Es
braucht insbesondere keinen kausalen Zusammenhang (Ursache und Wirkung) zwischen
der Hypothese und der Schlussfolgerung.

Betrachten wir die Implikation A ) B und die beiden andern Implikationen, die A
und B enthalten:
B ) A, ¬B ) ¬A
Diese beiden Aussagen heissen Umkehrung bzw. Kontraposition der Aussage A )
B. Die Wahrheitstabellen dieser 3 Aussagen lauten:
Implikation Umkehrung Kontraposition
A B A)B B)A ¬B ) ¬A
w w w w w
w f f w f
f w w f w
f f w w w
Beachten Sie, dass eine Implikation und ihre Umkehrung nicht logisch äquivalent sind.
Dies bedeutet, dass aus der Richtigkeit der Aussage A ) B im allgemeinen nicht
auf die Richtigkeit der Aussage B ) A geschlossen werden kann. Hingegen sind eine
Implikation und ihre Kontraposition logisch äquivalent.

8
Satz 3 Eine Implikation A ) B und ihre Kontraposition ¬B ) ¬A sind logisch
äquivalent.

Betrachten wir ein Beispiel: seien A und B die Aussagen Es regnet“ und Die
” ”
Strasse ist nass“. Wir haben die drei Aussagen

(a) Implikation: A ) B ( Wenn es regnet, dann ist die Strasse nass“)

”
(b) Umkehrung: B ) A ( Wenn die Strasse nass ist, dann regnet es“)
”
(c) Kontraposition: ¬B ) ¬A ( Wenn die Strasse nicht nass ist, dann regnet es
”
nicht“)

Die Implikation und ihre Kontraposition, die logisch äquivalent ist, sind wahr. Die
Umkehrung der Implikation hingegen kann falsch sein, da die Strasse auch nass sein
kann, wenn es nicht regnet (jemand könnte die Strasse abspritzen).

1.10 Äquivalenz
Falls A die Aussage B impliziert und B die Aussage A, so schreiben wir

A () B .

Gemäss Definition gilt

A () B ⌘ (A ) B) ^ (B ) A).

Die Aussage A () B heisst Äquivalenz. Es existieren die folgenden Sprechweisen für

A () B :

(a) Die Aussagen A und B sind äquivalent“

”
(b) A genau dann wenn B“
”
(c) A dann und nur dann wenn B“
”
(d) A ist notwendig und hinreichend für B“
”
Aus der Definition ergibt sich die folgende Wahrheitstabelle:
A B A () B
w w w
w f f
f w f
f f w
Die Aussage A () B ist wahr, wenn A und B die gleichen Wahrheitswerte besitzen
und falsch in den übrigen Fällen. Um zu zeigen, dass eine Äquivalenz richtig ist, genügt
es zu zeigen, dass aus der Wahrheit von A die Wahrheit von B und aus der Wahrheit
von B die Wahrheit von A folgen.

1.11 Anwendung
In diesem Abschnitt betrachten wir ein Beispiel aus der Medizin [11]:

Beispiel 17 Von zwei leicht verwechselbaren Infektionskrankheiten X und Y ist be-

kannt, dass dabei zwei Symptome S und T auftreten können, die mit der Krankheit
folgendermassen verknüpft sind:

9
 (i) Wenn ein Patient an der Krankheit X leidet, aber nicht an Y , so muss bei ihm
das Syptom T auftreten.

(ii) Wenn bei einem Patienten mindestens eines der beiden Symptome auftritt, so
leidet er mindestens an einer der beiden Krankheiten.

(iii) Tritt das Symptom S nicht auf, so liegt die Krankheit Y nicht vor.

(iv) Wenn ein Patient an Y , aber nicht an X leidet, so tritt das Symptom T nicht
auf.

(a) Formalisieren Sie die Bedingungen (i) bis (iv) und stellen Sie eine vollständige
Wahrheitstabelle für die Konjunktion der Bedingungen (i)-(iv) auf.

(b) Führen Sie bei der Konjunktion der Bedingungen (i)-(iv) eine Termumformung
durch und überprüfen Sie damit das Ergebnis in (a).

(c) Welche Diagnose kann einem Patienten gegeben werden, der

(c1) beide Symptome (c2) nur Symptom T (c3) nur Symptom S

(c4) keines der beiden Symptome

aufweist?

Die Aufgabe wird im Unterricht gelöst. 3

1.12 Syntax und Semantik

In diesem Abschnitt werden wir zuerst erklären, was eine wohlgeformte Formel ist. Wir
werden für den Begri↵ wohlgeformte logische Formel die Abkürzung WFF (well-formed
formula) verwenden.
Wir geben zuerst eine Übersicht über die verwendeten Zeichen:
(1) Aussagenvariablen: A, B, C, . . .
(2) Verknüpfungszeichen (Junktoren): ¬, ^, _, ), ()
(3) Klammern: ( , ) und [ , ]
Die Bildungsregeln für WFF lauten folgendermassen:
(1) Die Aussagenvariablen sind WFF.
(2) Falls P eine WFF ist, dann ist auch ¬P eine WFF.
(3) Falls P und Q WFF sind, dann sind auch

(P ^ Q), (P _ Q), (P ) Q) und (P () Q)

WFF.
Wir lassen überflüssige Klammern weg, insbesondere die äusseren Klammern. Weiter
soll ¬ stärker binden als alle andern Junktoren und die Junktoren ^ und _ sollen stärker
binden als ) und () .

Beispiel 18 Welche der folgenden Ausdrücke sind WFF?

10
 (a) A^
(b) A ^ ¬(A ) B)
(c) A ) B ^ ¬
(d) (A ) B) () ¬(A ) ¬B)
(e) A ) B¬A
(f) A ^ B () B _ C
(g) A ^ B _ C

Die Lösung wird im Unterricht erarbeitet. 3

Der korrekte Aufbau von Formeln ist der syntaktische Teil der Aussagenlogik.
Der semantische Teil der Aussagenlogik ist die Belegung der Aussagenvariablen mit
Wahrheitswerten. Wir sprechen von Realisationen. Diesen Aspekt haben wir bereits
ausführlich in den vorhergehenden Abschnitten behandelt.

11
2 Fortsetzung der Logik
2.1 Aussageformen
Definition 2 Wir bezeichnen mit einer Aussageform (prédicat en français) einen
Satz, welcher eine endliche Zahl von Variablen enthält, und der zu einer Aussage im
Sinne der Aussagenlogik wird, wenn wir für die Variablen Werte aus vorgebenen Mengen
(den Definitionsbereichen) einsetzen.

Im Folgenden verwenden wir die üblichen Bezeichnungen für Zahlenmengen.

• Menge der natürlichen Zahlen: N := {1, 2, 3, 4, . . .} .

• Menge der ganzen Zahlen: Z := {. . . , 3 2 1, 0, 1, 2, 3, . . .} .
• Menge der rationalen Zahlen: Q := { pq : p, q 2 Z ^ q 6= 0} .
• Menge der reellen Zahlen: R .

Wir betrachten einige Beispiele für Aussageformen:

(a) Sei x 2 R . Die Gleichung

2x 5=x+8

ist eine Aussageform mit der Variable x . Der Definitionsbereich ist R . Wenn wir
für x eine reelle Zahl einsetzen, erhalten wir eine falsche oder wahre Aussage.
(b) Sei n 2 N . Wir betrachten die Aussageform

3|n (3 ist ein Teiler von n) .

Diese Aussageform wird zu einer wahren Aussage, wenn wir für n z.B. den Wert
9 einsetzen.
(c) Seien n, m 2 N . Wir betrachten die Aussageform

n|m (n ist ein Teiler von m) .

Diese Aussageform enthält zwei Variablen. Wir erhalten eine wahre Aussage, wenn
wir beispielsweise für n die Zahl 6 und für m die Zahl 12 einsetzen.

Eine Aussageform mit der Variablen x werden wir durch P (x) abkürzen. Wenn die
Aussageform die Variablen x, y und n enthält, dann schreiben wir P (x, y, n) .

Beispiel 19 (a) Sei P (x) die Aussageform x2 + 4x + 3 = 0 . Was sind die Wahrheits-
werte von P ( 3) sowie von P (0) ?
(b) Sei Q(x, y, z) die Aussageform x2 + y 2 = z 2 . Bestimmen Sie die Wahrheitswerte
von Q(5, 12, 13) sowie von Q(3, 5, 7) .
Die Lösung wird im Unterricht erarbeitet. 3

12
2.2 Quantoren
In den obigen Beispielen haben wir aus den Aussageformen eine Aussage erhalten,
indem wir für die Variablen Werte eingesetzt haben. Eine andere Möglichkeit, um zu
einer Aussage zu kommen, besteht darin Quantoren anzufügen. Das Symbol 8 steht
für für alle. Es handelt sich um ein auf den Kopf gestelltes A und soll an Allaussage
erinnern. Den Satz Alle Menschen sind sterblich schreibt man so:

8x 2 M : (x ist sterblich) .

Hier bezeichnet M die Menge der Menschen.

Definition 3 Sei P (x) eine Aussageform mit dem Definitionsbereich D . Eine All-
aussage ist eine Aussage der Form

8x 2 D : P (x) . (3)

In Worten: Für alle x aus D gilt P (x) . Eine Allaussage ist wahr, genau dann, wenn
P (x) wahr ist für jedes x 2 D . Sie ist falsch, wenn es mindestens ein x 2 D gibt, wofür
P (x) falsch ist. Ein solches x ist ein Gegenbeispiel für die Allaussage.

Beispiel 20 (a) Sei D = {1, 2, 3, 4, 5} . Wir betrachten die Aussage

8x 2 D : (x2 x) .

Zeigen Sie, dass diese Aussage wahr ist.

(b) Bestimmen Sie den Wahrheitswert der folgenden Aussage:

8x 2 R : (x2 > x) .

Die Lösung wird im Unterricht erarbeitet. 3

Das Symbol 9 steht für es existiert oder es gibt. Die Wendung es existiert wird
in der Mathematik stets im Sinne von es existiert mindestens ein verwendet. Es kann
sich also auch um 2 oder mehr Elemente handeln.
Die Aussage Es gibt eine gerade Primzahl würde man so schreiben:

9p 2 P : (p ist gerade) .

Hier bezeichnet P die Menge der Primzahlen.

Definition 4 Sei Q(x) eine Aussageform mit Definitionsbereich D . Eine Existenz-

aussage ist eine Aussage von der Form

9x 2 D : P (x) .

In Worten: es gibt (mindestens) ein x aus D , so dass P (x) wahr ist oder es gibt
(mindestens) ein x aus D mit der Eigenschaft P (x).

Wir haben oben bereits festgehalten, dass die Aussage 9x 2 D : P (x) bedeutet, dass
es mindestens ein Element aus D mit der Eigenschaft P (x) gibt. Es kann also auch
mehrere oder sogar unendlich viele geben. Wenn man ausdrücken will, dass es genau
ein Element in D mit der Eigenschaft P (x) gibt, dann schreibt man nach 9 ein Aus-
rufungszeichen, also:
9! x 2 D : P (x)

13
Beispiel 21 Bestimmen Sie die Wahrheitswerte der folgenden Aussagen:

(a) 9m 2 Z : (m2 = m)
(b) 9n 2 N : (n2 + 2n 3 = 0)

Die Lösung wird im Unterricht erarbeitet. 3

Wir interessieren uns jetzt für die Verneinung von Existenz- und Allaussagen. Wir
interessieren uns für die Verneinung der Aussage Einige Fische können fliegen. Viele
Leute denken, dass die Verneinung dieser Aussage folgendermassen lautet: Einige Fische
können nicht fliegen. Das ist aber falsch; es ist ja nicht richtig, dass einige Fische fliegen
können. Das bedeutet also, dass alle Fische nicht fliegen können.
Die Aussage Einige Fische können fliegen ist eine Existenzaussage: Es gibt fliegende
Fische. Die Verneinung einer Existenzaussage ist eine Allaussage:

Satz 4 Die Negation einer Existenzaussage

9x 2 D : P (x)

ist logisch äquivalent zu

8x 2 D : ¬P (x) .
Also:
¬(9x 2 D : P (x)) ⌘ 8x 2 D : ¬P (x)

Wir betrachten jetzt die Allaussage Alle Primzahlen sind ungerade. Die Verneinung
dieser Aussage ist natürlich nicht Alle Primzahlen sind gerade. Wenn es nicht wahr ist,
dass alle Primzahlen ungerade sind, dann bedeutet dies, dass es mindestens eine gerade
Primzahl gibt. Die Verneinung ist also eine Existenzaussage:

Satz 5 Die Negation einer Allaussage

8x 2 D : P (x)

ist logisch äquivalent zu

9x 2 D : ¬P (x) .
Also:
¬(8x 2 D : P (x)) ⌘ 9x 2 D : ¬P (x) .

Beispiel 22 Bestimmen Sie die Verneinung der folgenden Aussagen:

(a) Für jedes rechtwinklige Dreieck mit den Katheten a und b und der Hypotenuse c
gilt:
a 2 + b2 = c 2

(b) 8x 2 R \ {0} : (x > x1 ) .

(c) 9x 2 Q : (x2 = 2) .

Die Lösung wird im Unterricht erarbeitet. 3

14
Die Quantoren 8 und 9 können natürlich auch mehrmals in einer Formel vorkommen.
Wir betrachten einige Beispiele:
(a) Wir betrachten die Aussage:
8x 2 R 9y 2 R : (x < y)
Für jedes x 2 R existiert ein y 2 R , wofür gilt x < y . Diese Aussage ist o↵en-
sichtlich wahr.
(b) Wir betrachten die Verneinung der vorhergehenden Aussage. Diese lautet: es gibt
ein x 2 R , so dass für alle y 2 R gilt x y . Geschrieben mit unseren Quantoren:
9x 2 R 8y 2 R : ¬(x < y)
bzw.
9x 2 R 8y 2 R : (x y) .
(c) Dieses Beispiel zeigt, dass die Reihenfolge der Quantifikatoren eine Rolle spielt.
Falls man im Beispiel (a) die beiden Quantifikatoren vertauscht, erhält man die
Aussage:
9x 2 R 8y 2 R : (x < y) .
Es gibt ein x 2 R , so dass für alle y 2 R gilt x < y . Diese Aussage o↵ensichtlich
falsch.
Die folgende Zusammenstellung fasst alle Möglichkeiten für zwei Quantoren zusam-
men (aus Platzgründen lassen wir die Definitionsbereiche weg):
Aussage Wann wahr? Wann falsch?
8x8y P (x, y) P (x, y) ist wahr für jedes x Es existiert ein x und ein y ,
8y8x P (x, y) und jedes y . wofür P (x, y) falsch ist.
8x9yP (x, y) Für jedes x existiert ein Ex existiert ein x , so dass
y , so dass P (x, y) wahr ist. P (x, y) falsch ist für jedes y .
9x8yP (x, y) Es existiert ein x , so dass Für jedes x existiert ein y ,
P (x, y) für alle y wahr ist. so dass P (x, y) falsch ist.
9x9yP (x, y) Es existiert ein x und ein y , so dass Für jedes x und für jedes y
9y9xP (x, y) P (x, y) wahr ist. ist P (x, y) falsch.
Natürlich können die Quantoren 8 und 9 mit den Junktoren der Aussagenlogik
kombiniert werden.
Betrachten wir einige weitere Beispiele aus der Mathematik:
(a) 9x 2 R : (x2 2x + 15 = 0 ^ x > 0)
(b) Wir bezeichnen mit P die Menge der Primzahlen:
8n 2 N : (n 2 P ) n ungerade _ n = 2)

(c) 8x 2 R : (x(x + 1) > 0 () x > 0 _ x < 1)

Beispiel 23 Bestimmen Sie den Wahrheitswert der folgenden Aussagen. Untersuchen
Sie, ob die Umkehrung richtig ist.
(a) 8x 2 R : (x > 0 ) x2 > x)
(b) 8x 2 R : (x > 1 ) x2 > x)
(c) 8z 2 Z : (6|z ) 3|z)
(d) 8x 2 R : (x = 1 ) x6 = 1)
Die Lösung wird im Unterricht erarbeitet. 3

15
Beispiel 24 Bestimmen Sie den Wahrheitswert der folgenden Aussagen.

(a) 8x, y 2 R : [(x = 0 ^ y = 0) () x2 + y 2 = 0] .

(b) 8x 2 R : (x3 = 8 () x = 2) .
(c) 8x 2 R : (x4 = 1 () x = 1) .
(d) 8x 2 R : (2(x 5) = (x 5)x () 2 = x) .

Die Lösung wird im Unterricht erarbeitet. 3

Insbesondere wird der Doppelpfeil () zwischen Gleichungen und Ungleichungen

verwendet, um auszudrücken, dass die Lösungsmenge gleich ist.

2.3 Beweistechniken
Im Kapitel über die Aussagenlogik haben wir gesehen, dass die Implikation logisch
äquivalent zu ihrer Kontraposition ist:

A ) B ⌘ ¬B ) ¬A

Beim Beweis einer Aussage A ! B lohnt es sich manchmal zu überlegen, ob die Kon-
traposition nicht einfacher zu beweisen ist. Man spricht dann von einem indirekten
Beweis. Wir betrachten ein Beispiel:

Beispiel 25 Beweisen Sie die folgende Aussage:

8n 2 N : (n2 ist gerade ) n ist gerade)

Die Lösung wird im Unterricht erarbeitet. 3

Ein weiteres wichtiges Beweisprinzip ist der Beweis durch Widerspruch. Ange-
nommen wir möchten die Aussage A beweisen. Wir machen die Hypothese:

Hypothese: ¬A

Wir nehmen also die Negation von dem, das wir beweisen möchten, als richtig an.
Ausgehend von ¬A versuchen wir durch korrekte Schlussfolgerungen die Negation
einer wahren Aussage B abzuleiten. Wir haben dann einen Widerspruch erzeugt. Da

¬A ) ¬B

wahr ist (wir haben korrekte Schlussfolgerungen vorgenommen) und ¬B falsch ist, muss
¬A falsch sein. Damit haben wir A bewiesen. Wir betrachten zwei Beispiele:

Beispiel 26 Sei a eine rationale und b eine irrationale Zahl. Dann ist a + b irrational.
Die Lösung wird im Unterricht erarbeitet. 3

p
Beispiel 27 Beweisen Sie, dass 2 eine irrationale Zahl ist, das heisst, dass es keine
rationale Zahl r gibt mit r2 = 2 .
Die Lösung wird im Unterricht erarbeitet. 3

16