Prof. Dr. J. Esparza
Lehrstuhl für Grundlagen derSoftwarezuverlässigkeit und theoretische
InformatikFakultät für Informatik
Technische Universität München
http://www7.in.tum.de/um/courses/ds/ws1314
WS 20013/14
Diskrete Strukturen
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen• Mathematische und notationelle Grundlagen
– Mengen– Relationen und Abbildungen– Aussagen- und Prädikatenlogik– Beweismethoden– Wachstum von Funktionen
2
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Einführung in die Mengentheorie
– Eine Menge ist eine Struktur, die eine ungeordneteSammlung von null oder mehrerenunterscheidbaren Objekten (Elementen) beinhaltet.
– Die Mengentheorie behandelt Operationen auf Mengen, Beziehungen zwischen und Aussagen überdiesen.
– Sämtliche Inhalte der Mathematik können mittelsmengentheoretischer Aussagen definiert werden.
– Mengen sind allgegenwärtig in jeglicher Art von Softwaresystemen.
3
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Jede Ansammlung oder Klasse von Objekten, die
wir beschreiben können, stellt eine Menge dar.• Die Elemente einer Menge können selbst Mengen
sein.• Mengen, die sich selbst als Element enthalten
(oder als Element eines Elements etc.), müssensorgfältig behandelt werden:– Sei 푀 die Menge aller Mengen, die sich nicht selbst
enthalten. Dann ist 푀 Element von 푀 gdw. 푀 keinElement von 푀 ist!
• Die Lösung dieses Problems ist nicht trivial. Wir brauchen jedoch keine solche Mengen.
4
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Jede Ansammlung oder Klasse von Objekten, die
wir beschreiben können, stellt eine Menge dar.• Die Elemente einer Menge können selbst Mengen
sein.• Mengen, die sich selbst als Element enthalten
(oder als Element eines Elements etc.), müssensorgfältig behandelt werden:– Sei 푀 die Menge aller Mengen, die sich nicht selbst
enthalten. Dann ist 푀 Element von 푀 gdw. 푀 keinElement von 푀 ist!
• Die Lösung dieses Problems ist nicht trivial. Wir brauchen jedoch keine solche Mengen.
5
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Eine Menge kann extensional oder intensional
beschrieben werden:– Extensionale Beschreibung: Explizite Aufzählung der
Elementen der Menge. Möglich nur für endliche Mengen.Notation: {푎, 푏, 푐}ist die Menge, die aus den 3 Objekten푎, 푏, 푐 besteht.
– Intensionale Beschreibung: Die Menge wird beschrieben alsdiejenigen Elemente einer anderen Menge, die eineEigenschaft 푃 erfüllen.Notation: wenn 퐷 die Menge aller Deutschen ist, und 푀(푥)bezeichnet, dass 푥 in München lebt, dann beschreibt푑 ∈ 퐷 푀(푑)}die Menge aller Münchener.
6
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Eigenschaften von Mengen
– Mengen sind inhärent ungeordnet (die Reihenfolge der Elemente ist unerheblich):
• Unabhängig davon, was a, b, und c darstellen, 푎, 푏, 푐 = 푎, 푐, 푏 = 푏,푎, 푐 = 푏, 푐,푎 = 푐,푎, 푏 = {푐, 푏,푎}.
– Alle Elemente einer Menge sind unterschiedlich; mehrfache Auflistung macht keinen Unterschied.
• Wenn 푎 = 푏, dann gilt: {푎, 푏, 푐} = {푎, 푐} = {푏, 푐} = {푎,푎, 푏,푎, 푏, 푐, 푐, 푐, 푐}.
• Diese Menge enthält (höchstens) 2 Elemente.– Zwei Mengen sind genau dann gleich, wenn sie exakt die
gleichen Elemente beinhalten. 7
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Unterschied zwischen Mengen und geordneten푛-Tupeln– Ein n-Tupel bezeichnet eine geordnete Zusammen-
stellung von Objekten, im Gegensatz zu Mengen, deren Elemente keine festgelegte Reihenfolge haben.
– Ein geordnetes n-Tupel (eine Sequenz oder Liste) der Länge n wird geschrieben als (푎1,푎2, … ,푎 ).
– Beachte, dass (1, 2)(2, 1)(2, 1, 1).
8
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen
9
John Venn1834-1923
Venn-Diagramm zur grafischen Veranschaulichung der Mengenlehre
0
-1 35
7
46
81
2
9
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Spezielle Mengen
ℕ = 1,2, …ℕ = 0,1,2, …ℤ = Menge der ganzen Zahlenℚ = Menge der Brüche (rationale Zahlen)ℝ = Menge der reelen Zahlenℂ = Menge der komplexen Zahlenℤ = 0,1, … ,푛 − 1 Restklasse bei Division durch 푛푛 = {1,2, … ,푛}
10
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Bezeichnungen – Element von
– xA bezeichnet, dass 푥 Element von 퐴 ist.– xA bezeichnet, dass 푥 kein Element von 퐴 ist.– Zwei Mengen 퐴,퐵sind genau dann gleich,
geschrieben 퐴 = 퐵 wenn sie dieselben Elementeenthalten. D.h., A und B sind gleich wenn für alle Elemente 푥gilt:
푥 ∈ 퐴 gdw. 푥 ∈ 퐵 .
11
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Weitere Bezeichnungen퐵 ⊆ 퐴 퐵 ist Teilmenge von 퐴: jedes Element
von 퐵 ist auch Element von 퐴.퐵 = 퐴 퐵 ⊆ 퐴 und 퐴 ⊆ 퐵퐵 ⊈ 퐴 퐵 ⊆ 퐴 gilt nicht퐵 ⊂ 퐴 퐵 ⊆ 퐴und 퐵 ≠ 퐴
12
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Die leere Menge
– ∅ (“die leere Menge”) ist die Menge, die keineElemente enthält.
– Die leere Menge ist in jeder Menge als Teilmengeenthalten
13
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengen und Elemente
– Die Elemente einer Menge können selbst wiederMengen sein. • Beispiel:
sei 푆 = 푋 푋 ⊆ {1,2,3}}dann ist푆 = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
– Beachte, dass 1 {1} {{1}} !
14
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengenoperationen - Kardinalität u. Endlichkeit
– |퐴| (“die Kardinalität von 퐴”) ist ein Maß dafür, wieviele unterschiedliche Elemente eine Menge 퐴 hat.
– z.B. |∅| = 0
| 1,2,3 | = 3
| 푎, 푏 | = 2
| 1,2,3 , 4,5 | = 2
15
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengenoperationen - Kardinalität u. Endlichkeit
– Wenn 퐴 ∈ ℕ , dann ist 퐴 endlich. Andernfalls ist퐴 unendlich.
– Beachte (Erklärung siehe später): Unendliche Mengen können unterschiedlich „groß“ sein!
16
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengenoperationen - Die Potenzmenge
– Definition:푃 푀 : = 2푀 ∶= 푋 푋 ⊆ 푀}ist die Potenzmenge der Menge 푀.
– 푃(∅) enthält als Element genau ∅also 푃 ∅ = ∅ (≠ ∅).
17
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengenoperationen - Die Potenzmenge
Beispiel:Für 푀 = {푎, 푏, 푐,푑}ist푃(푀) = {∅, {푎}, {푏}, {푐}, {푑},
{푎, 푏}, {푎, 푐}, {푎,푑}, {푏, 푐}, {푏,푑}, {푐,푑},푎, 푏, 푐 , 푎, 푏,푑 , 푎, 푐,푑 , 푏, 푐,푑 ,
{푎, 푏, 푐,푑}}
18
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengenoperationen - Die Potenzmenge
– Es gilt: die Potenzmenge einer 푛-elementigen Mengeenthält genau 2 Elemente.Argument, warum es so ist: Sei 푀 = 푎 , … ,푎 . Um eine Menge 퐿 ∈ 푃(푀)festzulegen, haben wir fürjedes 푖 ∈ [푛]die Wahl, 푎푖 zu 퐿 hinzuzufügen oder nicht. Damit ergeben sich 2 verschiedene Möglichkeiten. Diese Möglichkeiten entsprechen genau den Elementenvon 푃(푀).
– Später in der Vorlesung werden wir einen detallierterenBeweis sehen.
19
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengenoperationen - das kartesische Produkt
– Das kartesische Produkt zweier Mengen 퐴,퐵ist die Menge퐴 × 퐵 ∶= {(푎, 푏)|푎퐴und푏퐵}d.h., eine Menge, deren Elemente 2-Tupel sind.
– z.B. 푎, 푏 × {1,2} = {(푎, 1), (푎, 2), (푏, 1), (푏, 2)}
– Für endliche Mengen 퐴,퐵gilt: |퐴 × 퐵| = |퐴| · |퐵|.
20
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengenoperationen - das kartesische Produkt
– Das kartesische Produkt ist nicht kommutativ:푎 × 푏 = 푎, 푏 푏,푎 = 푏 × {푎}.
– Das kartesische Produkt ist nicht assoziativ:
푎 × 푏 × 푐 = 푎, 푏 , 푐
≠ 푎, 푏, 푐
= 푎 × ( 푏 × {푐})
– Das kartesische Produkt lässt sich auf 푛 Mengen erweitern:퐴1 × ⋯× 퐴 : = 푎1, … , 푎 푎1 ∈ 퐴1und… und푎 ∈ 퐴 }
21
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Mengenoperationen - das kartesische Produkt
– Das kartesische Produkt 퐴 × ⋯× 퐴 mit 푛 “Kopien” von 퐴 wird mit 퐴 bezeichnet
– Konvention: 퐴 = {∅}– Die Menge ⋃ 퐴 wird mit 퐴∗ bezeichnet. – Manchmal wird 퐴 Alphabet genannt . Ein Element von 퐴∗ ist dann ein Wort. Statt 푎 , … ,푎 wird 푎 푎 …푎geschrieben.
– Die Konkatenation von zwei Wörten 푎 …푎 und 푏 … 푏 ist das Wort 푎 …푎 푏 … 푏 .
22
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Weitere Mengenoperationen퐴 ∪ 퐵 Vereinigung: 푥 푥 ∈ 퐴oder푥 ∈ 퐵}퐴 ∩퐵 Schnittmenge: 푥 푥 ∈ 퐴und푥 ∈ 퐵}– Daraus folgt: |퐴 ∪ 퐵| = |퐴| + |퐵| − |퐴 ∩ 퐵|
퐴 ∖ 퐵 Differenzmenge: 푥 푥 ∈ 퐴und푥 ∉ 퐵}Oft werden nur Teilmengen einer Menge 푈 (die Grundmenge, Domaine oder Universum) betrachtet. Dann:
퐴̅ Komplementmenge: 푥 푥 ∈ 푈und푥 ∉ 퐴}23
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Lemma: Für beliebige Mengen 퐴,퐵, und 퐶
gelten die folgenden Identitäten:퐴 ∪ 퐴 = 퐴 ∩ 퐴 = 퐴 (Idempotenz)퐴 ∪ 퐵 = 퐵 ∪ 퐴 , 퐴 ∩ 퐵 = 퐵 ∩ 퐴 (Kommutativität)퐴 ∪ 퐵 ∪ 퐶 = 퐴 ∪ 퐵 ∪ 퐶퐴 ∩ 퐵 ∩ 퐶 = 퐴 ∩ 퐵 ∩ 퐶 (Assoziativität)퐴 ∩ 퐵 ∪ 퐶 = 퐴 ∩ 퐵 ∪ (퐴 ∩ 퐶) (Distributivität)퐴 ∪ 퐵 ∩ 퐶 = 퐴 ∪ 퐵 ∩ (퐴 ∪ 퐶)퐴 ∪ ∅ = 퐴 , 퐴 ∩ ∅ = ∅
24
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Aufgabe: welche von den folgenden Identitäten
gelten?퐴 ∖ 퐵 ∪ 퐶 = 퐴 ∖ 퐵 ∪ (퐴 ∖ 퐶)퐴 ∖ 퐵 ∪ 퐶 = 퐴 ∖ 퐵 ∩ (퐴 ∖ 퐶)퐴 ∖ 퐵 ∖ 퐶 = 퐴 ∖ (퐶 ∖ 퐵)퐴 ∖ 퐵 ∖ 퐶 = 퐴 ∖ 퐵 ∪ (퐴 ∩ 퐶)퐴 ∖ 퐵 ∖ 퐶 = 퐴 ∖ 퐵 ∪ (퐴 ∪ 퐶)
25
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen
• Weitere Mengenoperationen퐴∆퐵 ∶= 퐴 ∖ 퐵 ∪ (퐵 ∖ 퐴) Symmetrische Differenz퐴 ⊎ 퐵 Disjunkte Vereinigung .
• Die beiden Mengen sind disjunkt, d.h., 퐴 ∩ 퐵 = ∅.
Eine Partition einer Menge A ist eine Zerlegung von A in paarweise disjunkte, nichtleere Teilmengen 퐴1, … ,퐴 , so dass gilt:
퐴 = 퐴1 ⊎ 퐴2 ⊎ ⋯⊎ 퐴푛
25
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Weitere Mengenoperationen
⋃ 퐴 Vereinigung der Mengen 퐴 , …퐴
⋂ 퐴 Schnitt der Mengen 퐴 , …퐴
27
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Frage:
Wie lassen sich die Mengen 퐴 ∩ 퐵 bzw. 퐴 ∪ 퐵mit ∪,∩, 퐴̅,퐵 darstellen?
• Antwort:퐴 ∩ 퐵 = 퐴̅ ∪ 퐵퐴 ∪ 퐵 = 퐴̅ ∩ 퐵
28
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Frage:
Wie lassen sich die Mengen 퐴 ∩ 퐵 bzw. 퐴 ∪ 퐵mit ∪,∩, 퐴̅,퐵 darstellen?
• Antwort:퐴 ∩ 퐵 = 퐴̅ ∪ 퐵퐴 ∪ 퐵 = 퐴̅ ∩ 퐵
29
Vorlesung Diskrete Strukturen WS 13/14Prof. Dr. J. Esparza – Institut für Informatik, TU München
Kapitel II – Grundlagen; Mengen• Darstellungen
– Häufig werden wir eine diskrete Struktur, z.B. eineZahl, durch eine andere diskrete Struktur einesanderen Typs repräsentieren.
– z.B., können wir die natürlichen Zahlen als Mengenoder sog. Bit-Strings darstellen:
• Mengen: 0≔∅, 1:={0}, 2:={0,1}, 3:={0,1,2}, …• Bit-Strings (Zeichenketten bestehend aus 0en und 1en):
0:=0, 1:=1, 2:=10, 3:=11, 4:=100, …– Im weiteren Verlauf der Vorlesung werden wir
konkrete Anwendungen solcher Repräsentationenkennenlernen. 30