Was bisher geschah

Was bisher geschah
Modellierung von
I
Aussagen durch Logiken
I
Daten durch Mengen, Folgen, Sprachen
I
Zusammenhängen und Eigenschaften durch Relationen
I
I
I
I
I
Definition, Beispiele
Operationen auf Relationen:
inverse Relation, Verkettung, Einschränkung, Projektionen
Eigenschaften binärer Relationen R ⊆ M 2
reflexive, symmetrische, transitive Hüllen
spezielle binäre Relationen auf einer Menge:
Halbordungen, Äquivalenzrelationen
136
Totale Ordnungen
Jede Halbordnung R ⊆ M 2 mit
∀(a, b) ∈ M 2 ((a, b) ∈ R ∨ (b, a) ∈ R)
(alternativ)
heißt totale (lineare) Halbordnung.
(alle Elemente miteinander vergleichbar)
Beispiele:
I
R ⊆ ({a, b, c})2 mit
R = {(a, a), (a, b), (a, c), (c, b), (b, b), (c, c)}
I
≤⊆
I
R ⊆ ( Menge aller AMB-Studenten )2 mit
(p, q) ∈ R gdw. (Matrikelnr. von p) ≤ (Matrikelnr. von q)
I
alphabetische Ordnung der Wörter im Wörterbuch
N2 (≤ ⊆ Z2, ≤ ⊆ R2)
137
Totale Ordnungen
häufige Aufgabe: Sortieren von Elementen
z.B. Menge von Wörtern aus A∗ : {ab, ε, a, ac, abc, c}
Präfix-Relation v A∗ × A∗ mit
∀(u, v ) ∈ A∗ × A∗ ((u v v ) ↔ ∃v 0 ∈ A∗ (u ◦ v 0 = v ))
ist reflexiv,transitiv, antisymmetrisch, also eine Halbordnung
Gilt ∀(u, v ) ∈ (A∗ × A∗ ) : ((u v v ) ∨ (v v u)) ?
nein, z.B. für A = {a, b, c}, u = ab, v = ac gilt ab 6v ac und
ac 6v ab
v ist also keine totale Ordnung auf A∗
Sortieren lassen sich nur Elemente aus totalen Ordnungen
totale Ordnungen auf A∗ ?
138
Ordnungen auf A∗
ohne Ordnung auf dem Alphabet A:
Präfix-, Postfix-, Infix-Relation auf A∗ sind
Halbordnungen, nicht total (linear)
bei gegebener totaler Ordnung < auf dem Alphabet A:
lexikographische Ordnung auf A∗ :
∀u, v ∈ A∗ : u ≤lex v gdw.
1. u v v oder
2. ∃w ∈ A∗ ∃a, b ∈ A : a < b ∧ wa v u ∧ wb v v
quasi-lexikographische Ordnung auf A∗ :
∀u, v ∈ A∗ : u ≤qlex v gdw.
1. |u| < |v | oder
2. |u| = |v | ∧ u ≤lex v
Beispiele: für A = {a, b} mit a < b
I ab v aba, ab ≤lex aba, ab ≤qlex aba
I abab 6v abba, aber abab ≤lex abba und abab ≤qlex abba,
I aaa ≤lex ab, aber aaa 6≤qlex ab
I ab 6≤lex aaba, aber ab ≤qlex aaba
139
Funktionen (Wiederholung)
Funktion: spezielle Relation mit Richtung
Relation f ⊆ A× B heißtgenau dann partielle Funktion,
wenn ∀a ∈ A : π2 f |{a} ≤ 1
Relation f ⊆ A× B heißtgenau dann (totale) Funktion,
wenn ∀a ∈ A : π2 f |{a} = 1
Beispiele:
I
Abbildung aller HTWK-Studenten auf ihren Geburtstag
ist totale Funktion
I
Abbildung von Geburtstag auf Studenten
ist keine Funktion
I
f ⊆
I
I
I
I
Z2 mit f = {(x, x 2) | x ∈ Z} ist (totale) Funktion
f 0 ⊆ Z2 mit f = {(x 2 , x) | x ∈ Z} ist keine Funktion
g ⊆ N2 mit g = {(x 2 , x) | x ∈ N} ist partielle Funktion
g ⊆ N2 mit g = {(x 2 , x) | x ∈ N} ist partielle Funktion
k ⊆ R2 mit h = {(sin x, x) | x ∈ R} ist keine Funktion
140
Definition von Funktionen
Funktion f : A → B wird definiert durch Angabe von:
Typ (Signatur):
Definitionsbereich : Menge A
Wertebereich : Menge B
Werte Zuordnung f
extensional z.B. f = {a 7→ 1, b 7→ 0}
(statt f = {(a, 1), (b, 0)})
intensional z.B. ∀x ∈ : f (x) = x 2
Syntax
Semantik
N
Graph von f : Relation f ⊆ A × B = {(x, f (x)) | x ∈ A}
141
Mehrstellige Funktionen auf einer Menge
A = B n : Funktion f : B n → B heißt auch
n-stellige Funktion auf B
Achtung: n-stellige Funktionen auf B sind
(n + 1)-stellige Relationen auf B.
Beispiel: f : × → mit
∀(x, y ) ∈ 2 : f (x, y ) = 2x + y
N
A=
B0
N N N
= {ε}:
Nullstellige Funktionen f : B 0 → B heißen auch
Konstanten f ∈ B.
Beispiel: c : 0 → mit c = 3
N
N
142
Abgeleitete Funktionen
Für Funktion f : A → B heißt
f (A) = π2 (f ) ⊆ B Bild von f ,
f (M) = π2 (f |M ) ⊆ B für M ⊆ A Bild von M unter f ,
f (a) = π2 f |{a} ∈ B für a ∈ A Bild von a unter f ,
f −1 (N) = π2 f −1 |N ⊆ A für N ⊆ B Urbild von N unter f ,
f −1 (b) = π2 f −1 |{b} ⊆ A für b ∈ B Urbild von b unter f ,
Für jede (totale) Funktion f : A → B gilt f −1 (B) = A
143
Eigenschaften von Funktionen (Wiederholung)
Funktion f : A → B heißt
injektiv , falls für alle b ∈ B gilt f −1 (b) ≤ 1,
surjektiv , falls für alle b ∈ B gilt f −1 (b) ≥ 1,
bijektiv , falls für alle b ∈ B gilt f −1 (b) = 1,
Eine Funktion ist genau dann bijektiv,
wenn sie injektiv und surjektiv ist.
Beispiele:
N → N mit ∀x ∈ N : f (x) = x 2 ist injektiv, nicht surjektiv
I f : Z → Z mit ∀x ∈ Z : f (x) = x 2 ist weder injektiv noch
I
f :
surjektiv
I
R
f : ≥0 →
surjektiv
R≥0 mit ∀x ∈ R≥0 : f (x) = x 2 ist injektiv und
144
Mengen von Funktionen
Menge aller (totalen) Funktionen von A nach B:
B A = {f : A → B} = {f ⊆ A × B | ∀a ∈ A : π2 f |{a} = 1}
Beispiel: {0, 1}{p,q,r } = {W : {p, q, r } → {0, 1}}
Für alle endlichen Mengen A, B gilt B A = |B||A| .
( Es existieren |B||A| verschiedene Funktionen von A nach B.)
Beispiele:
I
|{0, 1}||{p,q,r }| = 23 = 8 Funktionen W : {p, q, r } → {0, 1}
I
3|A| Funktionen f : A → {rot, grün, blau}
I
4|A| Funktionen f : A → {1, 2, 3, 4}
I
4|A| Funktionen f : A → {0, 1}2
145
Funktionen auf Anfangsstücken von
Funktion f : I → B mit I = {0, . . . , n} ⊂
N
N
Beispiel:
f : {0, . . . , 4} → B, wobei ∀n ∈ {0, 1, . . . , 4} : f (n) = 7n + 2
f (0) = 2, f (1) = 9, f (2) = 16, f (3) = 23, f (4) = 30
alternative Darstellung:
f0 = 2, f1 = 9, f2 = 16, f3 = 23, f4 = 30
Folge f = [2, 9, 6, 23, 30] =(7n + 2)i∈{0,...,4}
Jede Funktion f : I → B mit I = {0, . . . , n} repräsentiert
eine eindeutig definierte Folge (f (i))i∈I ∈ B ∗
Jede Folge (ai )i∈I ∈ B ∗ repräsentiert
eine eindeutig definierte Funktion a : I → B mit a(i) = ai
146
Funktionen nach {0, 1}
Für endliche Mengen A und B
I
I
(Anzahl)
A0
nullstellige Funktionen f :
→ {0, 1}
f0 = 0, f1 = 1 (Konstanten)
0
2|A | = 21 = 2
2|A|
einstellige Funktionen f : A → {0, 1}
Beispiel: für A = {a, b}
f00 = {a 7→ 0, b 7→ 0}
f01 = {a 7→ 0, b 7→ 1}
f10 = {a 7→ 1, b 7→ 0}
f11 = {a 7→ 1, b 7→ 1}
mögliche Urbilder der 1:
−1
−1
−1
−1
f00
(1) = ∅, f01
(1) = {b}, f10
(1) = {a}, f11
(1) = {a, b}
für
beliebige
Menge
A:
−1
f (1) ∈ A | f ∈ 2A = 2A (Potenzmenge von A)
I
zweistellige Funktionen f : A × B → {0, 1}
2(|A||B|)
147
Charakteristische Funktion einer Menge
Menge A definiert für jede Teilmenge B ⊆ A die
charakteristische Funktion χB : A → {0, 1} mit
(
1 falls x ∈ B
∀x ∈ A : χB (x) =
0 sonst
Beispiel: für A = {a, b, c, d} und B = {a, d} ⊆ A gilt
χB : A → {0, 1} mit χB = {a 7→ 1, b 7→ 0, c 7→ 0, d 7→ 1}
(χB ordnet jedem x ∈ A den Wahrheitswert der Aussage x ∈ B zu.)
Umgekehrt definiert jede Funktion f : A → {0, 1} eine Teilmenge
f −1 (1) ⊆ A
Für endliche Mengen A = {a1 , . . . , an } und
beliebige feste Anordnung [a1 , . . . , an ]
lässt sich jede Teilmenge B ⊆ A durch das eindeutige
Binärwort b1 . . . bn ∈ {0, 1}n mit bi = χB (ai ) repräsentieren.
148
Multimengen (Vielfachmengen, Bags)
zur Beschreibung von Elementen mit Vielfachheit
Beispiele:
I Bibliothek mit mehreren Exemplaren von Büchern
I Vorrat an Münzen
I Rommé-Blatt
Teilmenge A einer Menge U (Universum)
als charakteristische Funktion von A bzgl. U:
χA : U → {0, 1} mit
∀x ∈ U : χA (x) = |A ∩ {x}|
N
Multimenge A über Menge U: Funktion A : U →
alternative Darstellungen von Multimengen:
z.B. für U = {a, b, c, d} und A : U → mit
A(a) = 3, A(b) = 3, A(c) = 0, A(d) = 1 durch
I {a 7→ 3, b 7→ 3, c 7→ 0, d 7→ 1} (Reihenfolge egal)
I {a, b, a, b, d, b, a} (Reihenfolge egal)
I als Relation A ⊆ U × ( \ 0) mit {(a, 3), (b, 3), (d, 1)}
N
N
149

Download Report