Was bisher geschah

Was bisher geschah
Modellierung von
Aussagen durch Logiken
klassische Aussagenlogik
klassische Prädikatenlogik
Daten durch
Mengen
Folgen
Sprachen
Zusammenhängen und Eigenschaften durch Relationen
Definition
Beispiele
Operationen auf Relationen:
inverse Relation
Verkettung von Relationen
Projektionen, Einschränkung
Eigenschaften binärer Relationen auf einer Menge
106
Hüllen binärer Relationen
R ∪ IM heißt reflexive Hülle von R ⊆ M 2
(mit Identität IM = {(x, x) | x ∈ M})
R ∪ R −1 heißt symmetrische Hülle von R ⊆ M 2
(mit inverser Relation R −1 = {(y , x) | (x, y ) ∈ R})
Wiederholung: Verkettung ◦ der Relationen R ⊆ M 2 und S ⊆ M 2
R ◦ S = {(x, z) ∈ M 2 | ∃y ∈ M : (x, y ) ∈ R ∧ (y , z) ∈ S}
Iterierte Verkettung von R ⊆ M 2 mit sich selbst:
R
R0
= IM
n+1
= Rn ◦ R
R+
=
◆
Rn ⊆ M 2
transitive Hülle
n∈ \{0}
R∗
=
n∈
◆
Rn ⊆ M 2
reflexiv-transitive Hülle
107
Beispiel
R ⊆ ({a, b, c})2
mit
R = {(a, b), (b, c)}
R −1 = {(b, a), (c, b)}
R ∪ R −1 = {(a, b), (b, c), (b, a), (c, b)}
(symmetrische Hülle)
R 0 = {(a, a), (b, b), (c, c)}
R ∪ R 0 = {(a, b), (b, c), (a, a), (b, b), (c, c)}
(reflexive Hülle)
R 2 = {(a, c)}
R 3 = ∅ (= R n
R
+
2
für beliebige n ≥ 3)
3
= R ∪ R ∪ R ∪ · · · = {(a, b), (b, c), (a, c)}
(transitive Hülle)
R
∗
0
+
= R ∪ R = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)}
(reflexiv-transitive Hülle)
108
Modellierungsbeispiel
Lineares Solitaire mit
Menge der Spielzustände Q = {0, 1}6 ,
Startzustand 011110 ∈ Q,
Übergangsrelation T ∈ Q 2 mit


 (011110, 100110) , (011110, 011001) 
(100110, 100001) , (011001, 100001)
T =


(100110, 101000) , (011001, 000101)
Hüllen der Übergangsrelation enthalten
zusätzliche Möglichkeiten für Spielzüge:
reflexive Hülle T ∪ IQ
Aussetzen
−1
„Rückwärts“-Züge
symmetrische Hülle T ∪ T
+
transitive Hülle T
mehrere Züge auf einmal (aber wenigstens einen)
reflexiv-transitive Hülle T ∗
beliebig viele Züge auf einmal (Aussetzen erlaubt)
109
Quasiordnungen
Jede reflexive und transitive Relation R ⊆ M 2 heißt
Quasiordnung.
Beispiele:
R ⊆ {a, b, c}2 mit
R = {(a, a), (a, b), (b, b), (b, c), (a, c), (c, c)}
T ⊆ (Menge aller Personen)2 mit
(p, q) ∈ T gdw. p höchstens so alt ist wie q
S⊆
❩2 mit S = {(a, b) ∈ ❩2 | |a| ≥ |b|}
110
Äquivalenzrelationen
Jede reflexive, transitive und symmetrische Relation R ⊆ M 2
heißt Äquivalenzrelation.
Beispiele:
R ⊆ {a, b, c}2 mit R = {(a, a), (a, b), (b, a), (b, b), (c, c)}
Relation „haben dieselbe Farbe“ für Skatkarten
R ⊆ ({♦, ♥, ♠, ♣} × ({7, 8, 9, 10} ∪ {B, D, K , A}))2 mit
R = {((f1 , w1 ), (f2 , w2 )) | f1 = f2 }
Relation „sind im selben Studiengang“ für Studenten
R ⊆ A∗ mit R = {(u, v ) ∈ (A∗ )2 | |u| = |v |} (gleiche Länge)
Gleichmächtigkeit von Mengen: (A, B) ∈ R gdw. |A| = |B|
Ähnlichkeit von Dreiecken
für jede Menge M: IM ⊆ M 2 mit IM = {(x, x) | x ∈ M}
111
Äquivalenzklassen
Zu jeder Äquivalenzrelation R ⊆ M 2 heißen
zwei Elemente a ∈ M und b ∈ M genau dann äquivalent
bzgl. R, wenn (a, b) ∈ R
die Menge aller zu a ∈ M äquivalenten Elemente aus M
[a]R = {x ∈ M | (a, x) ∈ R}
Äquivalenzklasse von a bzgl. R
Beispiele:
Äquivalenzklassen bzgl. der Äquivalenzrelation
R ⊆ {a, b, c}2 mit R = {(a, a), (a, b), (b, a), (b, b), (c, c)}:
[a]R = {a, b} = [b]R und [c]R = {c}
Äquivalenzklassen bzgl. der Äquivalenzrelation
„haben dieselbe Farbe“ für Skatkarten:
K♦ , K♥ , K♠ , K♣ (siehe Übungsaufgabe 5.1.a)
[(♦, B)]R = K♦ = {(♦, w) | w ∈ {7, 8, 9, 10, B, D, K , A}}
112
Äquivalenzrelationen und disjunkte Zerlegungen
1. Jede Äquivalenzrelation R ⊆ M 2 definiert eine disjunkte
Zerlegung von M in die Menge aller Äquivalenzklassen
{[a]R | a ∈ M}
2. Jede (disjunkte) Zerlegung P = {Mi | i ∈ I} einer Menge M
definiert eine Äquivalenzrelation
RP ⊆ M 2
mit
RP = {(a, b) | ∃i ∈ I : {a, b} ⊆ Mi }
Beispiele:
Relation R ⊆ {a, b, c}2 mit
R = {(a, a), (a, b), (b, a), (b, b), (c, c)}
definiert Zerlegung {[a]R , [b]R , [c]R } = {{a, b}, {c}}
der Menge {a, b, c}
Zerlegung F = {K♦ , K♥ , K♠ , K♣ } der Menge aller Skatkarten
definiert die Relation RF (haben dieselbe Farbe)
◆ ◆
◆
Zerlegung P = {3 , 3 + 1, 3 + 2}
definiert die Relation RP = {(m, n) ∈
◆2 | 3|(m − n)}
113
Halbordnungen
Jede reflexive, transitive und antisymmetrische Relation
R ⊆ M 2 heißt Halbordnung.
a ∈ M und b ∈ M heißen genau dann vergleichbar bzgl. R,
wenn (a, b) ∈ R oder (b, a) ∈ R
Beispiele:
R ⊆ {a, b, c, d}2 mit
R = {(a, a), (a, b), (a, c), (a, d), (b, b), (b, d), (c, c), (d, d)}
≤⊆
◆2 (≤ ⊆ ❩2, ≤ ⊆ ❘2)
R ⊆ ( Menge aller AMB-Studenten )2 mit
(p, q) ∈ R gdw. (Matrikelnr. von p) ≤ (Matrikelnr. von q)
⊆ ({a, b}∗ )2
◆
❩
Teilerrelation | ⊆ 2 mit a|b gdw. ∃n ∈ | an = b
(Warum ist | ⊆ 2 keine Halbordnung?)
❩
Teilmengenrelation ⊆ auf 2{a,b,c}
114
Hasse-Diagramme von Halbordnungen
(für Halbordnungen auf endlichen Mengen)
graphische Darstellung der Relation mit folgenden
Konventionen:
Pfeilspitzen weglassen,
stattdessen optische Ausrichtung (nach oben)
reflexive Kanten (Schlingen) weglassen
transitive Kanten weglassen
Beispiele (Tafel):
Halbordnung ⊆ auf 2{a,b,c} ,
≤ auf {0, . . . , 6},
Teiler-Halbordnung | auf {0, . . . , 6}
115
Totale Ordnungen
Jede Halbordnung R ⊆ M 2 mit
∀(a, b) ∈ M 2 ((a, b) ∈ R ∨ (b, a) ∈ R)
heißt totale (lineare) Halbordnung.
(alle Elemente miteinander vergleichbar)
Beispiele:
R ⊆ ({a, b, c})2 mit
R = {(a, a), (a, b), (a, c), (c, b), (b, b), (c, c)}
≤⊆
◆2 (≤ ⊆ ❩2, ≤ ⊆ ❘2)
R ⊆ ( Menge aller AMB-Studenten )2 mit
(p, q) ∈ R gdw. (Matrikelnr. von p) ≤ (Matrikelnr. von q)
alphabetische Ordnung der Wörter im Wörterbuch
116

Download Report