Foundations of Deep Neural Networks

School of Computation, Information and Technology

Technische Universität München

Hinweise zur Personalisierung:

• Ihre Prüfung wird bei der Anwesenheitskontrolle durch Aufkleben eines Codes persona-
Esolution lisiert.
• Dieser enthält lediglich eine fortlaufende Nummer, welche auch auf der Anwesenheits-
Sticker mit SRID hier einkleben
liste neben dem Unterschriftenfeld vermerkt ist.
• Diese wird als Pseudonym verwendet, um eine eindeutige Zuordnung Ihrer Prüfung zu
ermöglichen.

g
Diskrete Strukturen

la
Klausur: IN0015 / Endterm Datum: Montag, 16. Februar 2026
Prüfer: Prof. Dr. Stefanie Jegelka Uhrzeit: 17:00 – 19:00
Yongkuan Zhang, [Link].

ch
rs
vo
Bearbeitungshinweise
• Diese Klausur umfasst 28 Seiten mit insgesamt 10 Aufgaben.
Bitte kontrollieren Sie jetzt, dass Sie eine vollständige Angabe erhalten haben.

• Die Gesamtpunktzahl in dieser Klausur beträgt 40 Punkte.

gs

• Das Heraustrennen von Seiten aus der Prüfung ist untersagt.

• Als Hilfsmittel sind zugelassen:
– ein nicht-programmierbarer Taschenrechner
n

– ein analoges Wörterbuch Deutsch ↔ Muttersprache ohne Anmerkungen

– ein handgeschriebenes DIN A4 Blatt (beidseitig beschrieben, keine Kopien, Ausdrucke,
su

etc.)
• Es werden nur solche Ergebnisse gewertet, bei denen der Lösungsweg erkennbar ist. Auch Text-
aufgaben sind grundsätzlich zu begründen, sofern es in der jeweiligen Teilaufgabe nicht ausdrücklich
anders vermerkt ist.
• Schreiben Sie weder mit roter / grüner Farbe noch mit Bleistift.
Lö

• Schalten Sie alle mitgeführten elektronischen Geräte vollständig aus, verstauen Sie diese in Ihrer
Tasche und verschließen Sie diese.

Hörsaal verlassen von bis / Vorzeitige Abgabe um

– Seite 1 / 28 –
 Aufgabe 1 (4 Punkte)

0 a) Tragen Sie in die folgende Tabelle den Wahrheitswert ({0, 1}) der gegebenen Formel samt ihrer Teilformeln
ein.
1
Die Spalten zu atomaren Teilformeln müssen nicht ausgefüllt werden.
2 Sollte sich der Wahrheitswert einer nicht atomaren Teilformel für eine gegebene minimale Belegung bereits
eindeutig aus dem Wahrheitswert ihrer linken Teilformel ergeben, so muss die rechte Teilformel nicht ausge-
3
wertet werden. Nur in diesem Fall dürfen die zugehörigen Tabellenfelder leer gelassen werden, ansonsten
4 muss ein Wahrheitswert ({0, 1}) angegeben werden.

g
u x z ((z ⊕ ¬ u) ↔ (¬ x → (z ∧ u)))

la
1 1 0 1 0 0
0 0 0
0 1 1 1 0 0

ch
0 0 1
1 1 1 0 1 (0)
0 1 0
0 1 0 0 1 (0)
0 1 1
0 0 1 0 0
1

1
0

0
0

1
1

0
rs0

0
1

0
1

0
1

1
1

(0)
vo
1 1 0
1 0 1 0 1 (1)
1 1 1

b) Gegeben ist die folgende aussagenlogische Formel in KNF als Klauselmenge:

gs

G = {{p, q}, {p, r}, {p, ¬s}}

Stellen Sie die Wahrheitswertverteilung von G mittels des folgenden KV-Diagramms dar.

s
n

0 0 0 0
su

0 0 0 1
r
1 1 1 1
p
1 1 1 1
Lö

Tragen Sie dazu in jedes Feld den zugehörigen Wahrheitswert ({0,1}) ein.

– Seite 2 / 28 –
c) Gegeben ist das folgende KV-Diagramm, wobei ein graues Feld für wahr steht:

g
w

la
Geben Sie eine Formel in KNF als Klauselmenge mit höchstens 3 Klauseln an, welche den durch das
KV-Diagramm vorgegebenen Wahrheitswerteverlauf besitzt.
Solution sketch :

ch
{{q, t, ¬w}, {¬q, t, ¬y}, {¬t, y}}

rs
d) Überführen Sie die aussagenlogische Formel

H = ((q ∨ p) → (s ↔ (q → r)))

mittels semantischer Äquivalenzen in eine Formel in DNF entsprechend des Verfahrens aus der Vorlesung.
vo
• Nach Überführen in die Standardbasis {∧, ∨, ¬}:
Solution sketch :

(¬(q ∨ p) ∨ ((s ∧ (¬q ∨ r)) ∨ ¬(s ∨ (¬q ∨ r))))

n gs
su

• Nach Überführen in Negationsnormalform (¬ nur noch vor atomaren Formeln):

Lö

Solution sketch :

((¬q ∧ ¬p) ∨ ((s ∧ (¬q ∨ r)) ∨ (¬s ∧ (q ∧ ¬r))))

– Seite 3 / 28 –
 • Nach Überführen in disjunktive Normalform (DNF):
Solution sketch :

((¬q ∧ ¬p) ∨ (((s ∧ ¬q) ∨ (s ∧ r)) ∨ (¬s ∧ (q ∧ ¬r))))

g
la
ch
rs
vo
n gs
su

Variante: 1.1
Lö

– Seite 4 / 28 –
Aufgabe 2 (5 Punkte)

Geben Sie zu jeder Frage auch eine Begründung (z.B. ein Gegenbeispiel) an. Antworten bei denen 0
nur “Ja” oder “Nein” stehen, werden mit 0 Punkten gewertet!
Zulässig sind einzig Verweise auf die Vorlesungsunterlagen aus diesem Semester. Insbesondere müssen 1
nicht in der Vorlesung behandelte Ergebnisse bewiesen werden.
2
Anmerkung : (1, 1, 13 , 2, 22 ) steht für die Gradsequenz (1, 1, 1, 2, 2) und gibt an, dass es 3 Knoten von Grad 1
sowie 2 Knoten von Grad 2 gibt. 3
a) Zeigen oder widerlegen Sie: Jeder Graph G = (V, E), in dem jeder Knoten mindestens Knotengrad
|V | 4
2 − 1 hat, besitzt einen Hamiltonkreis.
5

g
Solution sketch :

la
Nein, zum Beispiel Graph mit Gradsequenz (1, 1, 1, 1) erfüllt diese
Bedingung, ist aber nicht zusammenhängend.

ch
rs
vo
gs

b) Sei G ein planarer Graph mit der Gradsequenz (2, 2, 2, 2, 2, 2, 27 , 3, 3, 3, 34 ) und 5 inneren Flächen in einer
planaren Einbettung. Bestimmen Sie die Anzahl der Zusammenhangskomponenten von G.

Solution sketch :
n

|E| = 13, |V | = 11, |F | = 6, k = |F | − |E| + |V | − 1 = 3

su
Lö

– Seite 5 / 28 –
 c) Besitzt jeder einfache Graph mit der Gradsequenz (2, 3, 3, 3, 34 , 4) eine Knotenfärbung mit maximal 4
Farben?

Solution sketch :

√ √
χ(G) ≤ 0.5 + 0.25 + i di = 0.5 + 18.25 ≈ 4, 77.
P

⇒ χ(G) ≤ 4.

g
la
ch
rs
d) Ist jeder einfache Graph mit Gradsequenz (1, 1, 2, 2, 2) ein Baum?
vo
Solution sketch :

Die Gradsequenz enthält zwei Knoten vom Grad 1 und erfüllt mit
gs

|V | = 5 und |E| = 4 auch |E| = |V | − 1, kann daher als Baum

realisiert werden; allerdings z.B. auch als ein Pfad der Länge 1
und ein einfacher Kreis der Länge 3, was kein Baum ist, da nicht
n

zusammenhängend.
su
Lö

– Seite 6 / 28 –
e) Gibt es einen einfachen Graphen mit der Gradsequenz (4, 4, 5, 5, 5, 54 , 6), der planar ist?

Solution sketch :

Die Gradsequenz erfüllt nicht |E| = 17 ≤ 3|V | − 6 = [Link] Gradse-

quenz ist zwar realisierbar, aber kein einfacher Graph mit dieser
Gradsequenz ist planar,da |E| = 17 > 3|V | − 6 = 15.

g
la
ch
Variante: 2.1
rs
vo
n gs
su
Lö

– Seite 7 / 28 –
 Aufgabe 3 (4 Punkte)

0 Im Folgenden wird stets (i) eine kurze Begründung und (ii) das Ergebnis als arithmetischer Term unter
Verwendung der in der Vorlesung behandelten kombinatorischen Koeffizienten erwartet.
1 Beachten Sie:
2 • Es reicht, die gesuchten Werte als arithmetische Terme unter Verwendung der in der Vorlesung
behandelten kombinatorischen Zählkoeffizienten anzugeben. Die Terme müssen soweit wie möglich
3
vereinfacht und ausführlich begründet werden.
4 Ein numerischer Wert wird nicht erwartet.
• Zulässig sind einzig Verweise auf die Vorlesungsunterlagen aus diesem Semester. Insbesondere

g
müssen nicht in der Vorlesung behandelte Ergebnisse bewiesen werden.
• Soweit nicht explizit anders angegeben, müssen bei den Verteilungsproblemen stets alle Objekte

la
verteilt werden.
a) Wie viele Möglichkeiten gibt es, 9 Aufgaben auf 12 Personen zu verteilen, wenn sowohl Aufgaben als
auch Personen unterscheidbar sind, jede Person aber höchstens eine Aufgabe zugewiesen bekommen

ch
soll?
Solution sketch :

m = 9 Ziehungen aus n = 12 ohne Zurücklegen unter Beachtung

der Reihenfolge:
rs
nm = 129 = 79833600
vo
n gs

b) Wie viele Möglichkeiten gibt es, 7 Aufgaben auf 3 Personen zu verteilen, wenn weder Aufgaben noch
Personen unterscheidbar sind, jede Person aber mindestens eine Aufgabe zugewiesen bekommen soll?
su

Solution sketch :

Ungeordnete Partition von 7 Elementen (Personen) auf 3 Mengen

(Räume):
Lö

Pm,n = P7,3 = 4

– Seite 8 / 28 –
  
c) Bestimmen Sie die Anzahl der durch 17, 23 oder 37 teilbaren Zahlen in 105 .
Solution sketch :

Sei Vn,d = dZ ∩ [n] die Menge der Vielfachen von d in [n]. Es

gilt |Vn,d | = ⌊n/d⌋ und Vn,d1 ∩ Vn,d2 = Vn,kgV(d1 ,d2 ) . Anwenden der
Siebformel ergibt |V100000,17 ∪ V100000,23 ∪ V100000,37 | = 12407.

g
la
ch
surj.
d) Bestimmen Sie {(f −1 (1), . . . , f −1 (5)) | f : [10] −−→ [5]} .
Solution sketch :

rs
Anzahl surjektiver Funktionen von [m] = [10] nach [n] = [5]:
vo
(n!) · Sm,n = (5!) · S10,5 = 5103000

Alternativ: Geordnete Partition von 10 Elementen auf 5 Mengen:

gs

(n!) · Sm,n = (5!) · S10,5 = 5103000

.
n
su

Variante: 3.1
Lö

– Seite 9 / 28 –
 Aufgabe 4 (4 Punkte)

0 Gegeben sind die folgenden beiden Relationen R und S über der Grundmenge [5] sowohl in graphischer
Darstellung als auch als Tabelle:
1

2
R S
3
2 2
4

g
3 3

la
1 1

ch
4 4

5 5

(s,t)
1
2
3
1
0
0
0
2
0
0
0
3
0
1
0
4
0
0
0
5
0
1
1
rs (s,t)
1
2
3
1
0
0
0
2
0
0
0
3
0
1
0
4
0
1
0
5
1
0
0
vo
4 0 0 0 0 1 4 0 1 1 0 0
5 1 0 0 0 0 5 1 0 0 0 0

a) Zeichnen Sie den Graphen zur Relation R∗ in die folgende Vorlage ein:
gs

2
n

3
su

1
Lö

4
(s,t) 1 2 3 4 5
1 1 0 0 0 0
5 2 1 1 1 0 1
3 1 0 1 0 1
4 1 0 0 1 1
5 1 0 0 0 1

b) Sei Y die bzgl. ⊆ kleinste partielle Ordnung mit R ⊆ Y .

Bestimmen Sie das Hasse-Diagramm von Y und stellen Sie dieses wieder graphisch dar:

– Seite 10 / 28 –
 2

g
(s,t) 1 2 3 4 5
1 0 0 0 0 0
5 2 0 0 1 0 0

la
3 0 0 0 0 1
4 0 0 0 0 1
5 1 0 0 0 0

ch
Geben Sie weiterhin alle minimalen und alle maximalen Elemente bzgl. Y an:

• Minimale Elemente: 2, 4
• Maximale Elemente: 1

rs
c) Bestimmen Sie die Äquivalenzklassen der bzgl. ⊆ größten Äquivalenzrelation T1 mit T1 ⊆ S ∗ .
Solution sketch :
vo
{{1, 5}, {2, 4}, {3}}

Bestimmen Sie ebenfalls die Äquivalenzklassen der bzgl. ⊆ kleinsten Äquivalenzrelation T2 mit S ⊆ T2 .
Solution sketch :
gs

{{1, 5}, {2, 3, 4}}

n

Variante: 4.1
su
Lö

– Seite 11 / 28 –
 Aufgabe 5 (2 Punkte)

0 a)

1
H 5 H
2 F F
D 2 1 D
4 3
G G
A A 6
C C
B 7 B

g
E E

la
Bestimmen Sie die Reihenfolge u1 , u2 , . . . , un in welcher die Breitensuche (Breadth-first, BFS), beginnend
im Knoten G, die Knoten des oben links gezeigten Graphen zu einem Spannbaum hinzufügt. Falls für den
Algorithmus mehrere Knoten zur Auswahl stehen sollte, wählen Sie den Knoten mit der lexikographisch
niedrigsten Bezeichnung (also z.B. A vor B vor C usw.).

ch
Zeichnen Sie den resultierenden Spannbaum in die obige rechte Vorlage und beschriften Sie die Kanten
bzgl. der Reihenfolge in der sie zum Spannbaum hinzugefügt werden. Mit anderen Worten, beschriften Sie
die Kante {ui , ui+1 } mit dem Index i.
b)

G
F
D
H
rs G
F
61
D
2
H
7
vo
A 4 A 3
C C
B B
5

E E
gs

Bestimmen Sie die Reihenfolge u1 , u2 , . . . , un in welcher die Tiefensuche (Depth-first, DFS), beginnend
im Knoten G, die Knoten des oben links gezeigten Graphen zu einem Spannbaum hinzufügt. Falls für den
Algorithmus mehrere Knoten zur Auswahl stehen, wählen Sie den Knoten mit der lexikographisch niedrigsten
Bezeichnung (also z.B. A vor B vor C usw.).
Zeichnen Sie den resultierenden Spannbaum in die obige rechte Vorlage und beschriften Sie die Kanten
n

bzgl. der Reihenfolge in der sie zum Spannbaum hinzugefügt werden. Mit anderen Worten, beschriften Sie
die Kante {ui , ui+1 } mit dem Index i.
Variante: 5.1
su
Lö

– Seite 12 / 28 –
Aufgabe 6 (5 Punkte)

Bei den folgenden Teilaufgaben wird stets eine kurze Begründung (z.B. ausführliche Rechnung unter Angabe 0
der verwendeten Resultate) und, soweit zutreffend, der konkrete numerische Wert erwartet. Der numerische
Wert alleine reicht jedoch nicht als Antwort! 1
Die folgende Liste an Primzahlen könnte hilfreich sein:
2
11, 19, 23, 29, 43 3

a) Wir betrachten die multiplikative Gruppe (Z∗N , ·N , 1) modulo N = 989. 4

Bestimmen Sie das multiplikative Inverse von a = 890 modulo N = 989 mittels des erweiterten Euklidischen
5
Algorithmus.

g
Verwenden Sie hierfür die vorgegebene Tabelle:

la
a b ⌊b/a⌋ α β
890 989 1 -10 9

ch
99 890 8 9 -1
98 99 1 -1 1
1 98 - 1 0

rs
Geben Sie nun das multiplikative Inverse a−1 in Z∗N an:
Solution sketch :
vo
a−1 = 979

b) Werten Sie den folgenden Term schrittweise aus:

gs

(8820)6554 + (8812)6556 mod 551

Hinweis : 551 ist keine Primzahl.

Solution sketch :
n

551 = 29 · 19, φ(551) = 504

su

8820 mod 551 = 4, 8812 mod 551 = 547, 6554 mod 504 = 2, 6556 mod
504 = 4
(8820)6554 + (8812)6556 ≡551 (8820 mod 551)6554 mod 504 + (8812 mod 551)6556 mod 504
Lö

≡551 (4)2 + (547)4

≡551 272

– Seite 13 / 28 –
 c) Bestimmen Sie alle Lösungen x, y ∈ Z11 des folgenden linearen Gleichungssystems modulo der Primzahl
p = 11:
2x + 9y ≡11 5
4x + 10y ≡11 6
Sie müssen Ihren Rechenweg angeben, lediglich die Angabe des Ergebnisses wird mit 0 Punkten bewertet!
Hinweis : (Z∗11 , ·11 , 1) wird von 2 erzeugt, wobei ⟨2⟩ = {2, 4, 8, 5, 10, 9, 7, 3, 6, 1} gilt.
(⟨g⟩ ist nach aufsteigendem Exponenten aufgezählt.)
Solution sketch :

x = 3, y = 6.

g
la
ch
rs
vo
n gs
su

Variante: 6.2
Lö

– Seite 14 / 28 –
Aufgabe 7 (4 Punkte)

Gegeben ist die folgende aussagenlogische Formel F in den Variablen q, u, x in Klauselmengendarstellung: 0

{{q, u, ¬x}, {q, ¬u, ¬x}, {¬q, u}, {¬q, ¬u}, {u, x}, {¬u, x}} 1

Protokollieren Sie den Verlauf des DPLL-Algorithmus angewandt auf F entsprechend den Übungen als 2
Graph über den betrachteten Klauselmengen:
3
• Kennzeichnen Sie jede Kante mit der angewandten Regel und dem verwendeten Literal (OLR
4
vor PLR vor Fallunterscheidung).

• Sollten für eine Regel mehrere Literale in Frage kommen, dann muss das Literal mit der lexikographisch

g
niedrigsten Variable gewählt werden; sollte die Wahl nicht eindeutig sein, dann muss das positive
Literal gewählt werden

la
(d.h. 1. q, 2. ¬q, 3. u, 4. ¬u, 5. x, 6. ¬x).

Solution sketch :

ch
(0) {{q, u, ¬x}, {q, ¬u, ¬x}, {¬q, u}, {¬q, ¬u}, {u, x}, {¬u, x}}

Case q Case ¬q

(1) {{u}, {¬u}, {u, x}, {¬u, x}}

OLR {u}
rs (3) {{u, ¬x}, {¬u, ¬x}, {u, x}, {¬u, x}}

Case u Case ¬u
vo
(2) {{}, {x}} (4) {{¬x}, {x}} (6) {{¬x}, {x}}

OLR {x} OLR {x}

gs

(5) {{}} (7) {{}}

n
su
Lö

Variante: 7.1

– Seite 15 / 28 –
 Aufgabe 8 (4 Punkte)

0 Die ehemals unsterblichen Fibonacci-Kaninchen sind krank: sie sterben mittlerweile nach drei Jahren.
Das Wachstum der Kaninchen-Population wird jetzt durch
1
Dn = Dn−1 + Dn−2 − Dn−3
2
für alle n ≥ 2 beschrieben, wobei immer noch D1 := 1 und Dn := 0 für n ≤ 0 gelten soll.
3
a) Stellen Sie nun eine Vermutung dafür auf, wie man Dn durch einen möglichst einfachen arithmetischen
4 Term t(n) in der Variable n für n ≥ 0 beschreiben kann.
Erinnerung : ⌈x⌉ und ⌊x⌋ runden ein beliebiges x ∈ R auf die nächstgrößere bzw. -kleinere Ganzzahl.

g
Hinweis : Bestimmen Sie zuerst Dn für n ∈ {0, . . . , 8}.
Solution sketch :

la
t(n) = ⌈n/2⌉

ch
rs
b) Beweisen Sie Ihre Behauptung aus (a) mittels Induktion.
Solution sketch :
vo
I.B.: Wie in (a) berechnet:
!
D0 = 0 = ⌈0/2⌉
gs

!
D1 = 1 = ⌈1/2⌉
!
D2 = 1 = ⌈2/2⌉.
I.S.: Sei n ≥ 3
n

• I.A.: Für alle k ∈ {0, . . . , n − 1} gilt Dk = ⌈k/2⌉.

su

• [Link].: Für alle k ∈ {0, . . . , n} gilt Dk = ⌈k/2⌉.

• Beweis [Link].:
Lö

Dn = Dn−1 + Dn−2 − Dn−3

Da n ≥ 3 gilt n − 3 ≥ 0, womit die I.A. anwendbar ist:
Dn = ⌈(n − 1)/2⌉ + ⌈(n − 2)/2⌉ − ⌈(n − 3)/2⌉
Da ⌈(n − 1)/2⌉ − ⌈(n − 3)/2⌉ = 1 und ⌈(n − 2)/2⌉ + 1 = ⌈n/2⌉,
folgt die Indunktionsbehauptung.
Variante: 8.2

– Seite 16 / 28 –
Aufgabe 9 (5 Punkte)

Wir betrachten im Folgenden ausschließlich einfache Graphen G = (V, E). Mit anderen Worten, wir nehmen 0
an, dass E ⊆ V2 := {{u, v} ⊆ V | u ̸= v}.

Für G = (V, E) ist Aut(G) die Menge aller Graphautomorphismen von G. 1

Aut(G) definiert eine Untergruppe der symmetrischen Gruppe (SV , ◦, IdV ) bzgl. V , wobei SV die Menge 2
aller Permutationen von V bezeichnet.
Wie in der Vorlesung bezeichnen wir S[n] kurz mit Sn . 3
Begründen Sie kurz Ihre Antwort.
4
[n]


a) Es gilt z.B., dass Aut(Kn ) = Sn wobei Kn := ([n], 2 ) den vollständigen Graphen darstellt.
5

g
Geben Sie ein weiteres Beispiel für einen Graphen G = ([n], E) mit Aut(G) = Sn an.
Solution sketch :

la
G = ([n], ∅).

ch
rs
vo
gs

V


b) Für einen Graphen G = (V, E) definieren wir den Komplementgraphen als G := (V, 2 \ E).
Zeigen Sie, dass Aut(G) = Aut(G).

Solution sketch :
n

Sei. α ∈ Sn . Nach der Definition von Aut(G) und da (F ↔ G) ≡

su

(¬F ↔ ¬G).
α ∈ Aut(G) GDW. für alle u, v ∈ V : {u, v} ∈ E gdw. {α(u), α(v)} ∈ E
Lö

GDW. für alle u, v ∈ V : {u, v} ̸∈ E gdw. {α(u), α(v)} ̸∈ E

GDW für alle u, v ∈ V : {u, v} ∈ (V × V ) \ E gdw. {α(u), α(v)} ∈
(V × V ) \ E
GDW. α ∈ Aut(G).

– Seite 17 / 28 –
 c) Definieren Sie zwei Graphen G1 = (V1 , E1 ) und G2 = (V2 , E2 ) mit |V1 | = ̸ |V2 |, für welche trotzdem
Aut(G1 ) ∼
= Aut(G2 ) gilt. (d. h. es existiert eine Bijektion φ : Aut(G1 ) → Aut(G2 ), die die Gruppenoperation
erhält.)
Solution sketch :

P2 , P3 : Für beide Graphen ist die Gruppe der Automorphismen

isomorph zu (Z2 , +2 , 0) da wir entweder die beiden Enden fixieren
oder aufeinander abbilden können. Alternativ: P1 und ein weiterer

g
starrer Graph (Lösung aus Aufgabe d)).

la
ch
rs
d) Definieren Sie einen Graphen G = (V, E) mit |V | > 1 und |Aut(G)| = 1.

Solution sketch :
vo
Ein zentraler Knoten der jeweils mit P1 , P2 und P3 verbunden ist.
n gs
su
Lö

– Seite 18 / 28 –
e) Sei G = (Z, {{i, i + 1} | i ∈ Z}). Bestimmen Sie ein Erzeugendensystem von Aut(G).
Solution sketch :

Jeder Automorphismus α wird zuerst durch die Wahl von α(0) ∈ Z

und dann durch α(1) ∈ {α(0) − 1, α(0) + 1} bestimmt.
Sei σ(i) := i + 1 die Funktion, die die Zahlengerade eine Posi-
tion nach rechts verschiebt und ρ(i) := −i die Funktion, die die

g
Zahlengerade um 0 spiegelt.

la
Somit α = ρj ◦ σ i für i := α(0) und j := 1 if α(1) = i − 1 sonst j := 0.

ch
Variante: 9.1
rs
vo
n gs
su
Lö

– Seite 19 / 28 –
 Aufgabe 10 (3 Punkte)

0
a) Wir betrachten den gerichteten Graphen G = (V, E) ohne Mehrfachkanten, wobei |V | = |N| und daher V
1 eine abzählbar unendliche Menge ist.
2 • Ist dann die Menge der Kanten von G, also E, ebenfalls abzählbar?
3 • Ist die Menge aller Relationen {R | R ⊆ V × V } abzählbar?
Begründen Sie ihre Antwort. Sie dürfen Ergebnisse aus der Vorlesung benutzen.
Solution sketch :

g
(a) Ja, E ist abzählbar. Da |V | = |N|, gibt es eine Bijektion f :

la
V → N. Da E ⊆ V × V gilt, ist |E| ≤ |V × V |. Außerdem ist
V × V abzählbar, z.B. über die Injektion

ch
g : V × V → N × N, g(u, v) = (f (u), f (v)),
(und damit sogar eine Bijektion g −1 (a, b) = (f −1 (a), f −1 (b))).
rs
Nach Vorlesung gilt |N×N| = |N|, also ist V ×V abzählbar. Damit
ist auch E als Teilmenge einer abzählbaren Menge abzählbar.
vo
(b) Nein, die Menge aller Relationen ist nicht abzählbar. Die
Menge aller Relationen ist genau die Potenzmenge von V × V ,
gs

also P(V ×V ). Aus (a) folgt |V ×V | = |N| (also abzählbar unend-

lich), somit gibt es eine Bijektion β : N → V × V . Dann induziert
n

β eine Bijektion zwischen P(V ×V ) und P(N). Nach Cantor (Dia-

su

gonalargument) ist P(N) überabzählbar, also ist auch P(V × V )

(und damit die Menge aller Relationen) überabzählbar.

Punkte (1P): (a) 0.5P: E ⊆ V × V und V × V abzählbar; (b) 0.5P:

Lö

P(V × V ) ∼ P(N) und Cantor.

– Seite 20 / 28 –
b) Zeigen Sie durch das Angeben einer geeigneten Bijektion, dass |N0 | = |3Z| = |{3z | z ∈ Z}|. Begründen
Sie kurz ihre Antwort.
Solution sketch :

Zunächst gilt 3Z = {3z | z ∈ Z} per Definition.

Es bleibt |N0 | = |3Z| zu zeigen. Dazu genügen Bijektionen:

(a) N0 ∼ Z über 

g


n/2, n gerade,




ψ : N0 → Z, ψ(n) = 

la

−(n + 1)/2, n ungerade.




(b) Z ∼ 3Z über

ch
θ : Z → 3Z, θ(z) = 3z,
mit Inverser θ−1 (3z) = z.

rs
Damit folgt N0 ∼ Z ∼ 3Z und somit |N0 | = |3Z|.
Punkte (1P): 0.5P für eine korrekte Bijektion N0 ↔ Z; 0.5P für
vo
Z ↔ 3Z und Schlussfolgerung.
n gs
su
Lö

– Seite 21 / 28 –
 c) Zeigen Sie, dass jede beliebige abzählbar unendliche Menge M in eine Partition von 2 abzählbar
unendlich großen Mengen aufgeteilt werden kann.
Solution sketch :

Da M abzählbar unendlich ist, existiert eine Bijektion f : N0 → M .

Definiere
M0 := {f (2n) | n ∈ N0 }, M1 := {f (2n + 1) | n ∈ N0 }.

g
Dann gilt M0 ∩ M1 = ∅ und M0 ∪ M1 = M . Außerdem sind M0 und

la
M1 jeweils abzählbar unendlich über die Bijektionen n 7→ f (2n)
bzw. n 7→ f (2n + 1). Also ist M = M0 ⊎ M1 eine Partition in zwei

ch
abzählbar unendliche Mengen.
Punkte (1P): 0.5P für Konstruktion M0 , M1 ; 0.5P für Nachweis:

rs
disjunkt, Vereinigung ist M , beide abzählbar unendlich.
vo
gs

Variante: 10.1
n
su
Lö

– Seite 22 / 28 –
Zusätzlicher Platz für Lösungen. Markieren Sie deutlich die Zuordnung zur jeweiligen Teilaufgabe.
Vergessen Sie nicht, ungültige Lösungen zu streichen.

g
la
ch
rs
vo
n gs
su
Lö

– Seite 23 / 28 –
 g
la
ch
rs
vo
ngs
su
Lö

– Seite 24 / 28 –
 g
la
ch
rs
vo
ngs
su
Lö

– Seite 25 / 28 –
 g
la
ch
rs
vo
ngs
su
Lö

– Seite 26 / 28 –
 g
la
ch
rs
vo
ngs
su
Lö

– Seite 27 / 28 –
 g
la
ch
rs
vo
ngs
su
Lö

– Seite 28 / 28 –