Spickzettel · Mathematische Grundlagen der Informatik

Relationen

Kapitel 5 — Eigenschaften, Verknüpfung, Inverse und Äquivalenzrelationen auf einen Blick.

Grundbegriffe

RelationR ⊆ A×B — eine Teilmenge des kartesischen Produkts

SchreibweiseaRb :⇔ (a,b) ∈ R

HeterogenR ⊆ A×B mit A≠B — Darstellung als bipartiter Graph

HomogenR ⊆ M×M (A=B=M) — Darstellung als Pfeildiagramm auf einer Punktmenge

→ Die vier Eigenschaften (reflexiv, symmetrisch, antisymmetrisch, transitiv) sind nur für homogene Relationen definiert — es muss ja xRx, yRx usw. überhaupt Sinn ergeben (x,y aus derselben Menge).

Die vier Eigenschaften (homogene Relationen)

Reflexiv

∀x∈M: xRx

Jedes Element steht in Relation zu sich selbst. Graph: jeder Punkt hat eine Schlaufe.

Symmetrisch

∀x,y: xRy ⇒ yRx

Pfeile kommen immer paarweise (beide Richtungen) oder gar nicht.

Antisymmetrisch

∀x,y: (xRy∧yRx) ⇒ x=y

Zwischen verschiedenen Elementen nie Pfeile in beide Richtungen (höchstens eine).

Transitiv

∀x,y,z: (xRy∧yRz) ⇒ xRz

Gibt es einen „Umweg" a→b→c, muss auch die Abkürzung a→c existieren.

Beispiele

„ist Grossvater von"

R auf der Menge aller Personen

✗ nicht reflexiv (niemand ist sein eigener Grossvater) · ✗ nicht symmetrisch · ✓ antisymmetrisch (vacuous — aRb und bRa können nie gleichzeitig gelten) · ✗ nicht transitiv (Grossvater des Grossvaters ist Ururgrossvater, nicht Grossvater)

x ≥ y auf ℕ

die „grösser-gleich"-Relation

✓ reflexiv (x≥x) · ✗ nicht symmetrisch (3≥2, aber nicht 2≥3) · ✓ antisymmetrisch (x≥y∧y≥x ⇒ x=y) · ✓ transitiv (x≥y∧y≥z ⇒ x≥z)

Verknüpfung von Relationen

Für R⊆A×B und S⊆B×C heisst die Verknüpfung S∘R ⊆ A×C:

S∘R = {(a,c) | ∃b∈B: aRb ∧ bSc}

⚠

Reihenfolge wie bei Funktionen: in S∘R wird zuerst R, dann S angewendet (von rechts nach links lesen) — nicht „erst S, dann R".

→ Beispiel: R = „arbeitet in Beruf" (Person→Beruf), S = „gehört zu Branche" (Beruf→Branche). Dann verknüpft S∘R jede Person direkt mit ihrer Branche.

Inverse Relation

R⁻¹ = {(b,a) | (a,b) ∈ R}

Alle Pfeile einfach umdrehen.

Doppelte Inverse(R⁻¹)⁻¹ = R

Symmetrisch ⇔R symmetrisch ⇔ R = R⁻¹

Äquivalenzrelation & Äquivalenzklassen

Definition Äquivalenzrelation

Eine homogene Relation, die alle drei Eigenschaften gleichzeitig erfüllt.

reflexiv ∧ symmetrisch ∧ transitiv

Definition Äquivalenzklasse [x]_R

Alle Elemente, die zu x äquivalent sind.

[x]_R = {y∈M | xRy}

Beispiel

M = {−4,−3,−2,−1,1,2,3,4}, R = {(x,y)∈M×M | x·y > 0} (gleiches Vorzeichen).

[−4]_R = {−4,−3,−2,−1} (= [−3]_R = [−2]_R = [−1]_R) · [1]_R = {1,2,3,4} (= [2]_R = [3]_R = [4]_R)

Induzierte Partition: P = { {−4,−3,−2,−1}, {1,2,3,4} }.

Äquivalenzrelation ↔ Partition

⇄

Jede Äquivalenzrelation R auf M induziert eine Partition von M (die Äquivalenzklassen). Umgekehrt induziert jede Partition P von M eine Äquivalenzrelation (xRy :⇔ x und y liegen in derselben Menge von P). Die beiden Konzepte sind zwei Seiten derselben Münze.

Tipps & Tricks

→

Eigenschaft widerlegen

Um zu zeigen, dass eine Eigenschaft nicht gilt, reicht ein einziges Gegenbeispiel (ein konkretes Paar/Tripel, das die Bedingung verletzt) — kein allgemeiner Beweis nötig.

→

Eigenschaft beweisen

Hier reicht kein Beispiel — man muss für beliebige x,y (bzw. x,y,z) aus der Definition von R zeigen, dass die Bedingung immer erfüllt ist (direkter Beweis, wie bei All-Aussagen).

→

Aus dem Graphen ablesen

Schlaufe an jedem Punkt? → reflexiv. Jeder Pfeil hat sein Gegenstück? → symmetrisch. Kein Pfeilpaar zwischen verschiedenen Punkten? → antisymmetrisch. Jeder „Umweg" hat auch die Abkürzung? → transitiv.

→

S∘R, R⁻¹, R∘R — Eigenschaften zeigen

Gehe wieder elementweise vor: sei (a,c)∈S∘R beliebig, also ∃b: aRb∧bSc — und arbeite direkt mit dieser Definition weiter, genau wie bei einem gewöhnlichen direkten Beweis.

→

Äquivalenzklassen = Partition direkt ablesen

Sobald man weiss, dass R eine Äquivalenzrelation ist, kann man die Äquivalenzklassen bestimmen, indem man einfach schaut, welche Elemente jeweils zueinander in Relation stehen — das ergibt direkt die Partition.

→

Reihenfolge bei Verknüpfungen

S∘R heisst „erst R, dann S" — wie bei Funktionen (g∘f). Bei Aufgaben zuerst notieren, welche Mengen/Relationen beteiligt sind (A→B→C), dann erst verknüpfen.