Relationen
10.10.2012 (Nachmittags)
geordnetes Paar (a,b) ist ein Konstrukt bei dem a an erster Stelle steht und b an zweiter Stelle steht.
(a,b) = {{a,b},{a}
Kartesisches Produkt
A x B = {(a,b) : a ∈ A ⋀ b ∈ B}
A={rot, grün, gelb}
B={Apfel, Banane, Kirsche, Pflaume}
AxB: hat 12 Elemente
Eine Teilmenge R⊆AxB nennen wir Relation. Wir schreiben aRb wenn (a,b) ∈R ist.
Darstellung
zum Beispiel abstrakt durch Eigenschaften
R= {(a,b)∈AxB| b hat typischerweise Farbe a}
Bei der Darstellung als Tabelle schreiben wir eine 1 wenn (a,b) ∈ R ist und 0 sonst
//Tabelle
Bei der Darstellung als Graph, zeichnen wir für jedes Element einen Punkt. Und verbinden zwei Punkte (a,b) wenn aRb gilt, mit einem Pfeil.
//Graph
R ⊆ A x A heißt Identitätsrelation geschrieben Ida oder Ia manchmal nur I (wenn klar ist, welche Menge A gemeint ist) <=> R = {(a,b) ∈ A x A | a = b}
Sei R⊆AxB irgendeine Relation, so ist:
- R^(-1) die Inverse Relation definiert durch
- R^(-1) = { (b,a) ∈ B x A | (a,b)∈R}
Die Verkettung von zwei Relationen R1 ⊆ A x B und R2 ⊆ B x C is definiert durch
R2 ○ R1 = {(a, c) ∈ AxC | ∃b∈B (a,b)∈R1 ⋂ (b,c) ∈ R2}}
Der Kringel "○" ist das Symbol für die Verkettung, auch Komposition genannt.
Sei R1 die Relation = {(a,b) ∈ FarbenxFrüchte | b hat nach Meinung des Dozenten typischerweise Farbe a}
R1^(-1) = {(b,a) ∈ Früchte x Farben | "b hat ........... Farbe a"}
R1○R1^(-1) ⊆ Früchte x Früchte
Apfel | Banane | Kirsche | Pflaume
rot 1 | 0 | 1 | 0
grün 1 | 0 | 0 | 0
gelb 1 | 1 | 0 | 0
R1 ○ R1^(-1) | Apfel | Banane | Kirsche | Pflaume
Apfel | | | |
Banane | | | |
Kirsche | | | |
Pflaume | | | |
A=B=C=R f(x) =x+1
g(x) = x²
f g
Frucht ------> Farben ------> {gekauft, nicht gekauft}
f:(Frucht) = meist vorkommende Farbe
g:(Farbe)
g( f(Frucht))
=g(Farbe)=gekauft oder nicht gekauf (aka to be or not to be)
g ○ f ⊆ Frucht x {gekauft, nicht gekauft}
Äquivalenzrelationen
R⊆AxA ist eine Äquivalenzrelation
<=>
(1) ∀a∈A: aRa Reflexivität
(2) ∀a,b∈A: aRb <=> bRa Symmetrie
(3) ∀a,b,c∈A: aRb⋀bRc => aRc Transitivität
Ganz nett als Hintergrundwissen hierzu:
Beispiel: A = {1,2,3,4,5}
\ 1 2 3 4 5
1 1 0 1 0 1
2 0 1 0 1 0
3 1 0 1 0 1
4 0 1 0 1 0
5 1 0 1 0 1
(3,1)⋀(1,5) => (3,5) Transitivität
☇ Nehmen wir an, dass (2,3) in R ist
(2,3)⋀(3,1) => (2,1) ☇
(4,3)⋀(3,1) => (4,1) ☇
(2,5)⋀(5,1) => (2,1) ☇
nächstes Beispiel
A={Menschen}
a ~ b <=> a und b haben die selbe Haarfarbe.
Ist diese Relation reflexiv? JA!
Ist sie symmetrisch? JA!
Transitivität? JA!
Wenn a und b die selbe Haarfabe haben und b und c , na(?) dann aber wohl auch a und c.
Folgt Reflexivität aus Transitivität und Symmetrie?
falscher Beweis:
aRb ⋀ bRa
folgt aus Symmetrie und aus Transitivität folgt aRa
Suchen Gegenbeispiel welches transitiv, symmetrisch aber nich reflexiv ist.
A={1,2}
R|1|2
1|0|0
2|0|0
(Merke: eine Implikation ist immer wahr, wenn die Vorraussetzung falsch ist)
Diese Relation erfüllt das Gewünschte.
A=Z und ~ sei so definiert:
a~b <=> a-b gerade ist
zZ ~ und Äquivalentrelation
∀a∈Z a-a ist gerade
0 ist gerade
∀a,b∈Z a-b gerade
=b-a gerade
(a-b) ist gerade => ∃l: (a-b)=2*l
=>(b-a)=2*(-l)=>(b-a) gerade
Wenn wir zeigen wollen, dass a genau dann, wenn b gilt, reicht es folgende zwei Implikationen zu zeigen:
A=>B und B=>A
A↔B≡(A→B)⋀(B→A)
Transitivität
(a-b) sie gerade und (b-c auch).
=> ∃k,l: (a-b)=2*k
(b-c)=2*l
(a-c)=2(k+l)
Nachtrag Relationen
Wir definieren die Verkettung von Relationen R ⊆ A x B und S ⊆ B x C als R ○ S = {(a,c)∈A x C: ∃b∈B aRb ⋀ bSc}
Siehe Beispiel Zeile 42ff + Graphen
Äquivalenzrelationen II
R|a|b|c|d|e
a|1|0|1|1|0
b|0|1|0|0|0
c|1|0|1|1|0
d|1|0|1|1|0
e|0|0|0|0|1
Sei {A1,A2,A3} eine Partition von der Menge
3
A= UAi
i=1
(d.h. Ai⋂Aj =∅ <=> i≠j)
a~b <=> ∃i{1, 2, 3}: a,b ∈A
Zeigen sie ~ ist eine Äquivalenzrelation.
A1=Steinobst={Kirschen,Pflaumen}
A2=Beeren={Erdbeere,Blaubeere}
A3=Zitrusfrüchte={Zitrone,Limette}
~ |Ki| PF| ERD| BLA| ZI| LI
KI |1 | 1| 0 | 0 | |
PF |1 | 1| 0 | 0 | |
ERD|0 | 0| 1 | 1 | |
BLA|0 | 0| 1 | 1 | |
ZI | | | | | 1 | 1
LI | | | | | 1 | 1
a ~ b <=> (a,b) ∈ ~
Reflexivität
Sei a∈A. Wir müssen zeigen:
∃i: a∈Ai (das gilt)
Symmetrie
Seien a,b∈A. Wir müssen zeigen a~b <=> b~a
a~b <=> ∃i : a,b∈Ai <=> ∃i: b,a∈Ai
<=> b~a
Transitivität
seien a,b,c∈A
a~b ⋀b~c =>a~c
Wir nehmen an die Vorraussetzung gilt.
Def. ∃i: a,b∈Ai
und ∃j:b,c∈Aj
Es reicht zu zeigen i=j
☇ Sei i≠j => b∈Ai⋂Aj
=>Ai⋂Aj≠∅ => i=j ☇
|N={0,1,2,.....} Möglich: Addieren,Multiplizieren
~⊆(|Nx|N)x(|Nx|N)
a-b=c-0
(a,b)~(c,d)
<=>a-b=c-d
<=>a+d=c+b <- Unsere Definition
Wir wollen zeigen ~ ist eine Äquivalenzrelation.
(1) Reflexivität: (a,b)∈|Nx|N
gilt(a,b)~(a,b)?
a+b=a+b (JA)
(2)Symmetrie: Sei(a,b) und (c,d) ∈|Nx|N
zZ: (a,b)~(c,d)
<=>(c,d)~(a,b)
Beweis:
(a,b)~(c,d)
<=> a+d=c+b (Definition anwenden)
<=> c+b=a+d
<=> (c,d)~(a,b) (Definition anwenden)
(3) Transitivität:
Sei (x,y), (x',y'),(x",y") ∈ (|Nx|N)x(|Nx|N)
Wir setzen voraus, dass:
(x,y)~(x',y') und (x',y')~(x",y") gilt
Wir müssen zeigen: (x,y)~(x",y")
Def: x+y'=x'+y und x'+y"=x"+y'
Wir addieren beide Gleichungen: x+y'+x'+y"=x'+y+x"+y'
=>x+y"=y+x"
=>(x,y)~(x",y") (Definition)
Übung:
(11,7)~(4,0)~(5,1)~(28,24)~........
Äquivalenzklassen:
Sei R ⊆AxA eine Äquivalenzrelation und a∈A so definieren wir die Äquivalenzklasse [a]R als die Menge {x∈A|xRa}
Lemma: Sein a,b∈A und R eine Äquivalenzrelation dann gilt:
[a]r ⋂[b]R= ∅
<=> ¬(aRb)
Beweis:
g.Z.Z. [a]R ⋂[b]R ≠ ∅
<=> aRb
"=>": Sei x ∈ [a]R ⋂ [b]R
Nach Definition gilt xRa und xRb
=> (aRx) ⋀(xRb)
=> aRb (Transitivität)
"<=": Sei aRb
=> a ∈ [b]R wir wissen aber auch a ∈ [a]R
=> a ∈ [a]R ⋂ [B]R ≠ ∅ :-)
Satz: Sei R eine Äquivalenzrelation, dann bildet die Menge der Äquivalenzklassen eine Partition
P = {[a]R | a ∈ A} :-)
S ist ein Repräsentantensystem von der Partition P gdw. ("genau dann, wenn") S aus jeder MEnge von P genau ein Element enthält
wir müssen das alles nicht verstehen. alles metal geht nach hause. Alles klar! :)
sehr schwer isses ja nun doch nicht
Übung:
0. A ⋃ B = {x | xa ⋃ xb}
1. (Ā ⋂ B)\C = {x | 0 } = (¬xa ⋂ xb) ⋂ ¬xc)} = ∅
2. A\(B\C) = {x | xa ⋂ ¬(xb⋂¬xc)}
3. (C ⋂ B) ∪ (B ⋂ A)∪(!C) = { x | ((xc⋂xb)⋃(xb⋂xa))⋃(¬xc) }
_________
4. (A ⋂ B ⋂ C) = { x | ¬(xa⋂xb⋂xc)}
Umkehrung: Stellen Sie die folgende Menge nur mit Hilfe von A, B, C und der Mengenoperationen dar.
5. { x | ¬xa ∪ (¬xa ⋂ xb)} = !A ∪ (!A ⋂ B) = !A
6. {x|xa ∪ xb)⋂(xa ∪ !xb) = (A ∪ B)⋂(A ∪ !B) = A⋃(B⋂!B) = A
7. {x|xa ⋂(xb ∪ xc)} = A ⋂ (B ∪ C)
Sonderzeichen: ∈, ∉, ≡, ∀, ∃, ∅, ⋂, ⋃, ⋀ , ⋁, ¬, →, ↔, ☇, √, ∤, |, ≥, ≤, ≠, ∪, ⊂, ⊃, ⊆, ⊇, ○, Ā, Ē, Ū, Ō