Prof. Dr. B.

Steffen

Andrej Dudenhefner – Markus Frohme – Gerrit Nolte – Oliver Rüthing – Jonas Schürmann

Übungen zur Vorlesung

Mathematik für Informatik 1
Wintersemester 2021/22
Übungsblatt 7

Für die Abgabe der Bearbeitungen stehen den Übungsgruppen Briefkästen im Verbindungsflur
Erdgeschoss OH 14 - OH 12 zu zur Verfügung.
Die den einzelnen Übungsgruppen zugeteilten Briefkästen sind durch die Gruppennummer ge-
kennzeichnet. Sie sind ferner mit dem Namen der Veranstaltung sowie Zeit und Ort der Übung
kenntlich gemacht.
Bitte werfen Sie Ihre Bearbeitungen in den Ihrer Übungsgruppe zugeteilten Briefkasten bis zur
unten aufgeführten Abgabefrist ein!
Schreiben Sie unbedingt immer Ihren vollständigen Namen, Ihre Matrikelnummer
und Ihre Gruppennummer auf Ihre Abgaben!

Abgabefrist: 3.12.2021, 16:00 Uhr

Aufgabe 7.1 Verbände (1+1+1 Punkte)

1. Wir betrachten die Menge M =df {1, 2, 3, 5, 6, 10, 15, 30}. Zeichen Sie das Hasse-Diagramm
von (M, |), wobei | wie üblich die Teilbarkeitsrelation auf natürlichen Zahlen sei.

Lösung:

30

6 10 15

2 3 5

2. Sei M wie in Teil 1 und A = {2, 5, 10}. Geben Sie - sofern vohanden - an:
Minimale, maximale, kleinste und größte Elemente von A sowie Infimum und Supremum von
A.
Prof. Dr. B. Steffen

Lösung: 2 und 5 sind minimale Elemente von A. Ein kleinstes Element von A existiert
hingegen nicht. Das Infimum von A ist 1.
Größtes Element von A und damit gleichzeitig einziges maximales Element sowie Supremum
ist 10.

3. Geben Sie eine Menge M ⊆ N an, so dass (M, |) kein Verband ist.

Lösung: Betrachte M =df {2, 3}. Dann besitzen die Elemente 2 und 3 keine untere Schranke
in M und somit auch kein Infimum.

Aufgabe 7.2 Distributive Verbände (1+1+2 Punkte)

Gegeben sei der durch das folgende Hasse-Diagramm festgelegte Verband:

d e

a b c

1. Ist dieser Verband distributiv? Begründen Sie Ihre Antwort.

Lösung: Dieser Verband ist nicht distributiv:

Es ist d u (a t c) = d u 1 = d und (d u a) t (d u c) = a t 0 = a, so dass Distributivität nicht
gegeben ist.

2. Bestimmen Sie alle Elemente des Verbandes, zu denen ein komplementäres Element existiert.
Bilden diese Elemente einen Unterverband von V ? Hierbei ist ein Unterverband S von V eine
Teilmenge S ⊆ V , für die die folgende Abschlusseigenschaft gilt:

∀ x, y ∈ S. x u y ∈ S ∧ x t y ∈ S.

Begründen Sie Ihre Antwort.

Lösung: In dem Verband sind die folgenden Elemente komplementär:

0 ↔ 1, a ↔ e, a ↔ c und d ↔ c.
Die Menge S =df {0, 1, a, c, d, e} bildet aber keinen Unterverband, da für d, e ∈ S deren
V -Infimum, nämlich b, nicht in S enthalten ist und damit die Abgeschlossenheit verletzt ist.

3. Zeigen Sie:
In einem distributiven Verband bildet die Menge der Elemente, zu denen es ein komplemen-
täres Element gibt, einen Unterverband.

Lösung: Sei S die Menge der Elemente von V , die ein komplementäres Element besitzen.
Wir müssen zeigen: sind a und b zwei beliebige Elemente von S, dann gilt a u b ∈ S und
a t b ∈ S.
Prof. Dr. B. Steffen

Es seien also a, b ∈ S. Die komplementären Elemente ā und b̄ sind dann ebenfalls Elemente
von S.
Es gilt
Distr. Komm.,Ass.
(a u b) u (ā t b̄) = ((a u b) u ā) t ((a u b) u b̄) = (b u (a u ā)) t (a u (b u b̄))
Kompl. Extrem. Idemp.
= (b u 0) t (a u 0) = 0t0 = 0
und
Komm. Distr.
(a u b) t (ā t b̄) = (ā t b̄) t (a u b) = ((ā t b̄) t a) u ((ā t b̄) t b)
Komm.,Ass. Kompl.
= (b̄ t (a t ā)) u (ā t (b t b̄)) = (b̄ t 1) u (a t 1)
Extrem. Idemp.
= 1u1 = 1

Dabei wurde das von Booleschen Verbänden bekannte Gesetz der Extremalität verwendet,
dessen Beweis sich hier überträgt. Wir erhalten also, dass a u b das komplementäre Element
ā t b̄ besitzt und folglich Element von S ist.
Das Komplement für a t b ergibt sich analog als ā u b̄.

Aufgabe 7.3 Verbandshomomorphismen (1+2+2 Punkte)

Gegeben seien die folgenden drei Verbände:
• (V1 , v1 ) =df (N∪{∞}, ≤): Die linear geordneten natürlichen Zahlen mit zusätzlichem größten
Element ∞.
• (V2 , v2 ) =df (N, |): Die natürlichen Zahlen mit Teilbarkeitsbeziehung
• (V3 , v3 ) =df (P(N), ⊆): Der Potenzmengenverband der natürlichen Zahlen
Betrachten Sie die Funktionen:
0 falls n = ∞
(
1. f : V1 → V2 mit f (n) =df
n sonst
2. g : V2 → V3 mit g(n) =df {m ∈ N | m|n}

falls M unendlich
(
∞
3. h : V3 → V1 mit h(M ) =df
|M | sonst
Welche der Funktionen sind Ordnungs-, t- oder u-Homomorphismen? Begründen Sie Ihre Antwor-
ten.

Lösung:
1. f ist kein Ordnungshomomorphismus. Es ist 2 v1 3, aber 2 6v2 3, da 2 kein Teiler von 3 ist.
Damit ist f gemäß Satz 7.20 auch kein t- oder u-Homomorphismus.
2. • g ist ein u-Homomorphismus, denn es gilt für beliebige n, m ∈ N:

g(n u2 m) = g(ggT (n, m))

= {k ∈ N | k|ggT (n, m)}
= {k ∈ N | k|n ∧ k|m}
= {k ∈ N | k|n} ∩ {k ∈ N | k|m}
= g(n) ∩ g(m)
= g(n) u3 g(m)
Prof. Dr. B. Steffen

• g ist kein t-Homomorphismus, denn es gilt

g(2 t2 3) = g(kgV (2, 3)) = g(6) = {1, 2, 3, 6}

6= {1, 2, 3} = {1, 2} ∪ {1, 3} = g(2) ∪ g(3)
= g(2) t3 g(3).

• Damit ist g gemäß Satz 7.20 ein Ordnungshomomorphismus.

3. • h ist ein Ordnungshomomorphismus. Sei A, B ∈ P(N) mit A v3 B, also A ⊆ B.

– Falls B unendlich ist, gilt h(B) = ∞ und damit h(A) ≤ h(B) für beliebige A. Somit
auch h(A) v1 h(B).
– Falls B endlich ist, muss auch A endlich sein. Dann gilt B = A ∪ (B \ A) und
da diese beiden Mengen endlich und disjunkt sind |B| = |A| + |B \ A|. D.h.
∃k ∈ N. |B| = |A| + k. Damit gilt |A| ≤ |B| also auch h(A) v1 h(B).
• h ist kein u-Homomorphismus. Es gilt

h({1} u3 {2}) = h({1} ∩ {2}) = h(∅) = |∅| = 0

6= 1 = min{1, 1} = min{h({1}), h({2})}
= h({1}) u1 h({2})

• g ist kein t-Homomorphismus. Es gilt

h({1} t3 {2}) = h({1} ∪ {2}) = h({1, 2}) = |{1, 2}| = 2

6= 1 = max{1, 1} = max{h({1}), h({2})}
= h({1}) t1 h({2})

Aufgabe 7.4 Verbandshomomorphismen (Bonusaufgabe: 2+3 Punkte)

Sei f : A → B eine beliebige Funktion. Offensichtlich induziert f eine Funktion f : P(A) → P(B)
durch:1
f (X) =df {f (a) | a ∈ X}

1. Beweisen Sie:
∀ X, Y ∈ P(A). f (X ∪ Y ) = f (X) ∪ f (Y )

Lösung: Seien X und Y Teilmengen von A. Es gilt:

f (X ∪ Y ) = {f (z) | z ∈ X ∪ Y }
= {f (z) | z ∈ X ∨ z ∈ Y }
= {f (z) | z ∈ X } ∪ {f (z) | z ∈ Y }
= f (X) ∪ f (Y ) .
1
Wie in der Mathematik üblich verwenden wir f in überladener Weise auch für diese Funktion.
Prof. Dr. B. Steffen

2. Beweisen Sie:

f : A → B injektiv ⇔ ∀ X, Y ∈ P(A). f (X ∩ Y ) = f (X) ∩ f (Y )

Lösung: ⇒: Sei f injektiv und X, Y ⊆ A. Offensichtlich gilt f (X ∩Y ) ⊆ f (X)∩f (Y ). Deshalb

bleibt nur die andere Inklusion f (X) ∩ f (Y ) ⊆ f (X ∩ Y ) zu zeigen. Sei b ∈ f (X) ∩ f (Y ).
Dann existieren x ∈ X, y ∈ Y mit f (x) = f (y) = b. Weil f injektiv ist, folgt x = y und somit
x ∈ X ∩ Y . Also gilt b ∈ f (X ∩ Y ).

⇐: Es gelte ∀ X, Y ⊆ A. f (X ∩ Y ) = f (X) ∩ f (Y ). Sei weiter a1 , a2 ∈ A. Dann gilt:

f (a1 ) = f (a2 ) ⇒ f ({a1 }) = f ({a2 }) ⇒ f ({a1 }) ∩ f ({a2 }) 6= ∅

V or.
⇒ f ({a1 } ∩ {a2 }) 6= ∅ ⇒ {a1 } ∩ {a2 } =
6 ∅
⇒ a1 = a2