∀ Mathe 1 PrepDiskrete Mathematik · Folien 1–3

Ordnungen, Hasse & Hüllen

ca. 20 min0 / 5 Übungen

Ordnungen vergleichen Dinge („kleiner gleich“, „teilt“, „Teilmenge von“). Du lernst, sie als Hasse-Diagramm zu zeichnen und eine Relation durch Hüllenbildung zu ergänzen.

Definition · OrdnungsrelationDef. 1.39, Folien 3 S. 16
R ist eine (Halb-)Ordnung, wenn R reflexiv, antisymmetrisch und transitiv ist. Beispiele: ≤ auf ℕ, ⊆ auf ℘(M), Teilbarkeit | auf ℕ (Bsp. 1.42). Linear heißt sie, wenn je zwei Elemente vergleichbar sind (Def. 1.43).
Äquivalenz vs. Ordnung
Beide sind reflexiv und transitiv. Der Unterschied: Äquivalenz ist symmetrisch („gleich“ geht in beide Richtungen), Ordnung ist antisymmetrisch(„kleiner“ geht nur in eine Richtung, außer bei Gleichheit).

Hasse-Diagramm

Definition · Hasse-DiagrammFolien 3 S. 21–22
Der Graph einer Ordnung, vereinfacht: Schlingen weglassen, alle Pfeile weglassen, die aus der Transitivität folgen, kleinere Elemente nach unten. Übrig bleiben die Linien zwischen „direkten Nachbarn“.
Woran erkenne ich eine Hasse-Kante?
a—b ist eine Kante, wenn a < b und nichts dazwischen liegt. Bei Teilbarkeit auf allen Teilern einer Zahl: genau dann, wenn b/a eine Primzahl ist.
Die drei Vereinfachungsschritte aus Folien 3 S. 21. Eigene Animation der KI.
✏️ Übung · Hasse-Diagramm zeichnenmittel
Zeichne das Hasse-Diagramm der Teilbarkeit auf den Teilern von 30.
12356101530
Zwei Zahlen nacheinander anklicken: Linie an/aus. Die Zahlen stehen schon in der richtigen Höhe.
✏️ Übung · Unregelmäßigerknifflig
Und hier: Teilbarkeit auf {2, 3, 4, 8, 9, 12, 24}. Achtung, das sind nicht alle Teiler einer Zahl, die Primzahl-Regel gilt hier nicht!
234891224
Zwei Zahlen nacheinander anklicken: Linie an/aus. Die Zahlen stehen schon in der richtigen Höhe.
✏️ Übung · Linear oder nicht?leicht
≤ auf ℤ ist eine lineare Ordnung.
⊆ auf ℘({1, 2}) ist eine lineare Ordnung.
Teilbarkeit auf {1, 2, 4, 8} ist eine lineare Ordnung.
Teilbarkeit | auf ℤ ist eine Ordnungsrelation.

Hüllen

Definition · HüllenDef. 1.45–1.47, Folien 3 S. 23–35
Reflexive Hülle R′: alle Schlingen ergänzen. Transitive Hülle R⁺: für jeden Pfeilweg a → … → b den direkten Pfeil a → b ergänzen. R* = R⁺ ∪ R′: die kleinste reflexive, transitive Relation, die R enthält.
Transitive Hülle ohne Fehler
Für jeden Knoten einzeln: Welche Knoten erreiche ich, wenn ich den Pfeilen folge (auch über mehrere Schritte)? Zu jedem davon gehört ein direkter Pfeil. Wenn ein Weg zurück zum Start führt (a → b → a), gehört auch die Schlinge (a, a) dazu, das wird am häufigsten vergessen.
Ein Läufer folgt den Pfeilen und ergänzt jede fehlende Abkürzung. Eigene Animation der KI zu Def. 1.46.
abc
R = {(a, b), (b, c), (c, a)}: Von jedem Knoten erreicht man alle, auch sich selbst. Also R⁺ = A × A (Folien 3 S. 29).
✏️ Übung · Transitive Hüllemittel
Ergänze möglichst wenige Pfeile, sodass die Relation transitiv wird.
abcd
✗ reflexiv
(a, a) fehlt.
✓ irreflexiv
Keine einzige Schlinge.
✗ symmetrisch
(a, b) ∈ R, aber (b, a) ∉ R.
✗ antisymmetrisch
(b, c) und (c, b) sind beide drin, obwohl b ≠ c.
✗ transitiv
(a, b) und (b, c) sind drin, aber (a, c) fehlt.
Knoten anklicken, dann Zielknoten: Pfeil an/aus. Neue Pfeile sind farbig.
R = {(a, b), (b, c), (c, b), (c, d)}
✏️ Übung · Ordnung erzeugenmittel
Ergänze möglichst wenige Pfeile, sodass eine Ordnungsrelation entsteht (reflexiv und transitiv; antisymmetrisch ist sie dann von selbst, weil es keine Kreise gibt).
1234
✗ reflexiv
(1, 1) fehlt.
✓ irreflexiv
Keine einzige Schlinge.
✗ symmetrisch
(1, 2) ∈ R, aber (2, 1) ∉ R.
✓ antisymmetrisch
Zwischen zwei verschiedenen Elementen nie Hin- und Rückpfeil.
✗ transitiv
(1, 2) und (2, 3) sind drin, aber (1, 3) fehlt.
Knoten anklicken, dann Zielknoten: Pfeil an/aus. Neue Pfeile sind farbig.
R = {(1, 2), (1, 4), (2, 3)}