Grundbegri e der Informatik - hookrace.net fileAquivalenzrelationen Kongruenzrelationen Halbordnungen Aquivalenzrelationen 1 Aquivalenzrelationen De nition Aquivalenzrelation von Nerode

Grundbegriffe der InformatikTutorium 1 - 14. Sitzung

Dennis Felsing

[email protected]

http://www.stud.uni-karlsruhe.de/~ubcqr/2010w/tut gbi/

2011-02-07

Aquivalenzrelationen Kongruenzrelationen Halbordnungen

Aquivalenzrelationen

1 AquivalenzrelationenDefinitionAquivalenzrelation von NerodeAquivalenzklassen und Faktormengen

2 Kongruenzrelationen

3 Halbordnungen

Dennis Felsing Grundbegriffe der Informatik 2/28



Definitionen

Sei R≡ ⊆ M ×M.

Reflexiv : ∀x ∈ M : x ≡ x

Symmetrisch : ∀x , y ∈ M : x ≡ y ⇒ y ≡ x

Transitiv : ∀x , y , z ∈ M : x ≡ y ∧ y ≡ z ⇒ x ≡ z

Aquivalenzrelation : reflexive, transitive und symmetrischeRelation

Beispiele

Gleichheitsrelation R= ⊆ R× R ist eine Aquivalenzrelation.

{(a, a), (a, b), (b, b), (b, c), (c , c)} ⊆ {a, b, c} × {a, b, c} istreflexiv, nicht symmetrisch und nicht transitiv.

R≤ ⊆ R× R ist reflexiv, transitiv und nicht symmetrisch.

R< ⊆ R×R ist transitiv, nicht symmetrisch und nicht reflexiv.Dennis Felsing Grundbegriffe der Informatik 3/28



Definitionen

Sei R ⊆ M ×M.

Reflexiv : ∀x ∈ M : (x , x) ∈ R

Symmetrisch : ∀x , y ∈ M : (x , y) ∈ R ⇒ (y , x) ∈ R

Transitiv : ∀x , y , z ∈ M : xRy ∧ yRz ⇒ xRz

Aquivalenzrelation : reflexive, transitive und symmetrischeRelation

Beispiele

xVy ⇔ x ist Vorfahre von y. V ist transitiv, nicht symmetrischund nicht reflexiv.

x♥y ⇔ x liebt y. ♥ ist nicht symmetrisch, nicht transitiv undnicht reflexiv.

R ⊆ {} × {} ist eine Aquivalenzrelation.




Definitionen

Reflexiv : ∀x ∈ M : (x , x) ∈ R

Symmetrisch : ∀x , y ∈ M : (x , y) ∈ R ⇒ (y , x) ∈ R

Transitiv : ∀x , y , z ∈ M : xRy ∧ yRz ⇒ xRz

Aquivalenzrelation : reflexiv, transitiv und symmetrisch

Ubertragung auf Graphen

Reflexiv : Schlingen an allen Knoten

Symmetrisch : Zu jedem Pfeil hin auch der zuruck

Transitiv : Wenn ein Pfad von x nach y existiert, dann aucheine direkte Kante

Aquivalenzrelation: Klumpen, die alle miteinander verbundensind, aber nach außen keine Verbindungen haben




Kongruenz modulo n

Sei n ∈ N+. Zwei Zahlen x , y ∈ Z heißen kongruent modulo n,wenn x − y durch n teilbar, also ganzzahliges Vielfaches von n ist.Dann schreibt man x ≡ y(mod n).

Reflexivitat : x − x = 0 Vielfaches von n X

Symmetrie : Sei x − y Vielfaches von n. Dann ist auchy − x = −(x − y) Vielfaches von n. X

Transitivitat : Seien x − y = k1n und y − z = k2n mit k1, k2 ∈ Z.Dann ist x − z = (x − y) + (y − z) = (k1 + k2)nVielfaches von n. X

⇒ Kongruenz modulo n ist eine Aquivalenzrelation



Aquivalenzrelation von Nerode

Definition

Fur alle w1,w2 ∈ A∗ istw1 ≡L w2 ⇔

(∀w ∈ A∗ : w1w ∈ L⇔ w2w ∈ L

)Was bedeutet das, wenn w1 ≡L w2?Fur alle Worter die man an w1 und w2 anhangen kann sindentweder beide entstehenden Worter in der Sprache L oder beidenicht.Wenn fur ein Suffix w gelten wurde, dass w1w ∈ L, aber w2w 6∈ L(oder umgekehrt), so sind w1,w2 nicht Nerode-aquivalent.



Aquivalenzklassen und Faktormengen

Defintionen

Aquivalenzklasse von x: [x ]≡ = {y ∈ M | x ≡ y}Faktormenge oder Faserung von M nach ≡:

M/≡ = {[x ]≡ | x ∈ M}



Aquivalenzklassen

Behauptung

x ≡ y ⇒ [x ] = [y ]

Beweis

”⊆“: Sei z ∈ [x ]. Es gilt also x ≡ z . Aufgrund der

Symmetrie gilt auch z ≡ x .Mit x ≡ y und Transitivitat folgt z ≡ y .Also y ≡ z und somit z ∈ [y ].⇒ [x ] ⊆ [y ]

”⊇“: Analog mit x und y vertauscht. �



Aquivalenzklassen

Behauptung

Wenn z ∈ [x ] und z ∈ [y ], dann [x ] = [y ].

Beweis

Wenn z ∈ [x ] und z ∈ [y ], dann x ≡ z und y ≡ z .Aufgrund der Symmetrie folgt x ≡ z und z ≡ y .Aus der Transitivitat folgt x ≡ y .Wie wir eben bewiesen haben, gilt nun [x ] = [y ]. �



Faktormengen

Wir wollen die Faktormenge von Z fur Kongruenz modulo 5bestimmen.Es gibt nur diese funf Aquivalenzklassen:Z/≡5

= Z5 = {[0], [1], [2], [3], [4]}



Faktormengen

Bestimme die Faktormenge der Nerode-Relation zur SpracheL =< aba∗ >.{[ε], [a], [ab], [b]}



Kongruenzrelationen

1 Aquivalenzrelationen

2 KongruenzrelationenDefinitionenArithmetik modulo n

3 Halbordnungen



Vertraglichkeit von Relationen mit Operatoren

Definition

Seien ≡ eine Aquivalenzrelation auf einer Menge M, f : M → Meine Funktion und � eine binare Operation.

≡ und f sind vertraglich :⇔∀x1, x2 ∈ M : x1 ≡ x2 ⇔ f (x1) ≡ f (x2)

≡ und � sind vertraglich :⇔∀x1, x2, y1, y2 ∈ M : x1 ≡ x2 ∧ y1 ≡ y2 ⇔ x1 � y1 ≡ x2 � y2

Aquivalenzrelation, die mit allen interessierenden Funktionenund Operationen vertraglich ist, nennt manKongruenzrelationen.



Modulo und Addition

Behauptung

≡ mod n ist mit + auf den ganzen Zahlen Z vertraglich

Beweis

Seien x1 ≡ x2 mod n und y1 ≡ y2 mod n, also∃k ∈ Z : x1 − x2 = k · n und ∃m ∈ Z : y1 − y2 = m · n.Somit folgt(x1 + y1)− (x2 + y2) = (x1 − x2) + (y1 − y2) = n · (k + m).Also (x1 + y1) ≡ (x2 + y2) mod n. �



Modulo und Multiplikation

Behauptung

≡ modn ist mit · auf den ganzen Zahlen Z vertraglich

Beweis

x1 · y1 = (x2 + k · n) · (y2 + m · n) = x2 · y2 + (x2m + ky2 + km) · nx1 · y1 − x2 · y2 ist somit ganzzahliges Vielfaches von n �



Rechnen mit Aquivalenzklassen

Wir betrachten Kongruenz modulo 5:

[3] + [4] =[3 + 4] = [7] = [2]

[2] + [3] =[2 + 3] = [5] = [0]

[2] + [3] =[7] + [−12] = [−5] = [0]

[2] · [3] =[2 · 3] = [6] = [1]

Wann ist [x ] · [y ] = [0]?Wenn bereits [x ] = [0] oder [y ] = [0], da 5eine Primzahl ist.



Rechnen mit Aquivalenzklassen

Es ergeben sich die folgenden Ergebnisse fur Z/5Z:+ [0] [1] [2] [3] [4]

[0] [0] [1] [2] [3] [4][1] [1] [2] [3] [4] [0][2] [2] [3] [4] [0] [1][3] [3] [4] [0] [1] [2][4] [4] [0] [1] [2] [3]

· [0] [1] [2] [3] [4]

[0] [0] [0] [0] [0] [0][1] [0] [1] [2] [3] [4][2] [0] [2] [4] [1] [3][3] [0] [3] [1] [4] [2][4] [0] [4] [3] [2] [1]



Halbordnungen

1 Aquivalenzrelationen

2 Kongruenzrelationen

3 HalbordnungenDefinitionBeispieleHasse-Diagramm



Halbordnungen

Definitionen

Antisymmetrisch: ∀x , y ∈ M : x v y ∧ y v x ⇒ x = y

Halbordnung: reflexive, transitive, antisymmetrische Relation



Halbordnung auf Alphabeten

Behauptung

Die Relation vp auf A∗ mit v vp w ⇔ ∃u : vu = w ist eineHalbordnung.

Beweis

Reflexivitat :Fur alle w ∈ A∗ gilt wε = w

Transitivitat :Seien w1 vp w2 und w2 vp w3. Dann ex. u1, u2 mitw1u1 = w2 und w2u2 = w3. Alsow1(u1u2) = (w1u1)u2 = w2u2 = w3 ⇒ w1 vp w3

Antisymmetrie :Seien w1 vp w2 und w2 vp w1. Dann ex. u1 undu2 mit w1u1 = w2 und w2u2 = w1. Alsow1u1u2 = w2u2 = w1. Somit muss| u1 |=| u2 |= 0⇒ u1 = u2 = ε⇒ w1 = w2

�



Weitere Relation

Frage

Ist v mit w1 v w2 ⇔| w1 |≤| w2 | eine Halbordnung?

Losung

Nein, Antisymmetrie ist verletzt. Zum Beispiel gilt uber {a, b} dassaaa v bbb und bbb v aaa, aber aaa 6= bbb.



Inklusion

Frage

Ist ⊆ auf der Potenzmenge 2M der Menge M eine Halbordnung?

Definition

Die Potenzmenge 2M einer Menge M ist die Menge allerTeilmengen dieser Menge.



Inklusion

Losung

Reflexivitat :Fur jede Teilmenge T der Menge M gilt: T ⊆ T ,denn jede Menge ist ihre eigene Teilmenge

Transitivitat :Sind alle Elemente von T1 in T2 und alle Elementevon T2 in T3, so sind auch alle Elemente von T1 inT3. Also gilt T1 ⊆ T2 ∧ T2 ⊆ T3 ⇒ T1 ⊆ T3.

Antisymmetrie :Gilt fur zwei Teilmengen T1,T2, dass T1 ⊆ T2

und T2 ⊆ T1, so ist T1 = T2, denn beide Mengenenthalten die Elemente der jeweils anderen Menge.



Hasse-Diagramm

Jede Relation ist als Graph darstellbar. Bei Halbordnungen wirddas aber ziemlich unubersichtlich. Beim Hasse-Diagramm HR zurRelation R werden alle reflexiven und transitiven Kantenweggelassen.



Uberblick

1 AquivalenzrelationenDefinitionAquivalenzrelation von NerodeAquivalenzklassen und Faktormengen

2 KongruenzrelationenDefinitionenArithmetik modulo n

3 HalbordnungenDefinitionBeispieleHasse-Diagramm



Klausur

Wichtig

Die Klausur findet am 1. Marz um 17:00 statt.

Was ist vor der Klausur sinnvoll?

Anmeldung im Studienportal uberprufen!

Skript aktiv lesen (Markieren, Notizen, Zusammenfassung, ...)

Ubungsblatter wiederholen, insbesondere rot angestrichenes

Alte Klausuren losen

Bei Problemen Tutor E-Mail schreiben




Documents

Grundbegri e der Informatik - hookrace.net fileAquivalenzrelationen Kongruenzrelationen Halbordnungen Aquivalenzrelationen 1 Aquivalenzrelationen De nition Aquivalenzrelation von Nerode