Theoretische Informatik (Vorlesung 4)

Ziele

• Vertiefend in die Inhalte der Vorlesungen gehen

Aufgabe 1

• Sei M eine Menge. Eine zweistellige Relation R ist eine Teilmenge R ⊂ MxM. Für ( x, y) ∈ R schreiben wir xRy ( x steht in Relation zu y)
• Bsp.:  <, =, > = {(x,y) ∈ NxN, x = y} = N x N
• Eine Relation heißt:
  1. reflexiv, wenn für alle x ∈ M : xRx
     1. ≤ ↔ ja
     2. = ↔ ja
     3. < ↔ nein ( da z.B.: 3 < 3 falsch ist )
  2. symmetrisch, wenn für alle x,y ∈ M: xRy → yRx
     1. ≤ ↔ nein ( da 3 = 5 aber 5 = 3 !  )
     2. = ↔ ja
     3. < ↔ nein
  3. asymmetrisch, wenn für alle x,y ∈ M: xRy → ¬(yRx)
     1. ≤ ↔ nein ( da 5 = 5 → wahr, aber ¬ ( 5 = 5 ) → falsch )
     2. = ↔ nein
     3. < ↔ ja
  4. antisymmetrisch, wenn für alle x,y ∈ M: xRy und yRx folgt: x = y
     1.  ≤ ↔ ja
     2.  = ↔ ja
     3.  < ↔ ja ( da es keine gültige Lösung für die Vorbedingung gibt → leere Menge, für diese ist es wieder wahr )
  5. transitiv, wenn für alle x,y,z ∈ M aus xRy und yRz => xRz
     1. gilt für alle Operationen

Aufgabe 2 Äquivalenzrelationen

• Sei R eine zweistellige Relation auf M. Dann heißt R eine Äquivlanzrelation, wenn R:
  1. reflexiv,
  2. symmetrisch und
  3. transitiv ist
• Beispiel: Drei Parallele Geraden im ℝ² ( Parallelität ist eine Äquivalenzrelation )

Aufgabe 3 Äquivalenzrelationen

• Sei M die Menge aller Schüler eine Schule. Ein Schüler X stehe in Relation zu Schüler Y, wenn X und Y die selbe Klassen besuchen. ( X ~ Y )

• Reflexivität:  ( X ~ X )
  • Schüler X steht in Relation zu sich selbst
• Symmetrie: X ~ Y → Y ~ X
  • Wenn X die Klasse besucht, besucht auch Y diese
• Transitivität: X ~ Y → Y ~ Z → X ~ Z
  • Wenn X die Klasse mit Y besucht und Y die Klasse mit Z, dann besucht X und Z die gleiche Klasse

Hiermit haben wir bewiesen, dass die definierte Relation eine Äquivalenzrelation ist.

Äquivalenzklasse

• [X]^~ = { y ∈ M, X~Y ) = Wenn X ein Schüler der Klasse 6c ist, dann sind [X]^~ alle Schüler der Klasse 6c. Alle Schüler einer bestimmten Eigenschaft (Schulklasse) werden in Äquivalenzklassen zusammengefasst.
• X ∈ [X]^~ ( X ist immer Teil seiner eigenen Äquivalenzklasse )
• a) Für alle x,y ∈ M mit X ~ Y gilt [X]^~ = [Y]^~
  • zz.:
    • [X]^~ ⊂ [Y]^~, [Y]^~ ⊂ [X]^~ sei z ∈ [X]^~, also gilt X ~ Z.
    • Aus der Symmetrie folgt Z ~ X. 
    • Da X ~ Y, folgt aus der Transitivität Z ~ Y.
    • Wieder aus der Symmetrie folgt Y ~ Z und damit Z ∈ [Y]^~
• b) Für alle x,y ∈ M mit x ~/~ y gilt [X]^~ ∩ [Y]^~ = Ø ( leere Menge )
  • Da X in keiner Relation zu Y steht, handelt es sich bei deren Äquivalenzklassen um 2 verschiedene Teilmengen aus M. Diese Teilmengen repräsentieren disjunkten Äquivalenzklassen und erzeugen bei der Schnittmengen-Operation die leere Menge.