Lehrstuhl II für Mathematik Aachen, den 23.06.2000 der RWTH Aachen Prof. Dr. L. Volkmann

1. Übungsscheinklausur Diskrete Strukturen SS 2000

1) (4 Punkte)

Für welche m, n ∈ ℕ mit ggT (m, n) = 1 gilt (m + n)|mn ?

2) (4 Punkte)

Man bestimme alle ungeraden Zahlen n ≥ 3 mit

2 · (n − 2)! + ( \begin{matrix}n \\ 2 \end{matrix} ) − 2 ≡ 0 (mod n)

3) (4 Punkte)

Für welche n ∈ ℕ läßt sich die Folge 1, 2^{2}, 3^{2}, …, n^{2} durch einen Graphen realisieren?

4) (4 Punkte)

Es sei G ein bipartiter Graph mit der Bipartition A, B. Man zeige: Ist |A| = |B| ≥ 2, und gilt für alle S ⊆ A mit S ≠ ∅, A die Ungleichung

|S| + 1 ≤ |N(S, G)|,

so gehört jede Kante von G zu einem perfekten Matching.

5) (4 Punkte)

Sei n ∈ ℕ mit n ≥ 3 und N_{n} = {1, 2, …, n}.

a) Wieviele Teilmengen A ⊆ N_{n} gibt es, so daß {1, 2} ⊈ A gilt? Ist die Anzahl dieser Teilmengen durch 3 teilbar?

b) Wieviele (n − 2)-elementige Teilmengen A ⊆ N_{n} gibt es, so daß {1, 2} ⊈ A gilt? Gibt es mehr oder weniger als 2n solcher Teilmengen?

2. Übungsscheinklausur Diskrete Strukturen SS 2000

Name:  Vorname:  Matr.Nr.:
Bestanden: ja ( ) nein ( ) 1) 2) 3) 4) 5)  Σ
Punkte:  ( ) ( ) ( ) ( ) ( ) ( )

1) (4 Punkte)

Zeigen Sie, dass für alle m, n ∈ ℕ gilt:

m + n ≤ ggT(m, n) + kgV(m, n)

Für welche m, n gilt Gleichheit?

2) (4 Punkte)

Es sei p eine Primzahl. Man bestimme alle Restklassen [x] = [x]_{p} modulo p mit

[x][x] = [1].

3) (4 Punkte)

Sei G ein p-partiter Graph, p ≥ 2, mit der Partition E_{1}, E_{2}, …, E_{p} und sei |E_{1}| ≤ |E_{2}| ≤ … ≤ |E_{p}|. Zeigen Sie:

a) Falls für jede Menge S ⊆ E_{p} die Ungleichung |S| ≤ |N(S, G)| gilt, so existiert ein Matching M von G mit |M| = |E_{p}|.

b) Aus (p − 1)|E_{p}| ≤ |N(E_{p}, G)| folgt |E_{1}| = |E_{2}| = … = |E_{p}|.

4) (4 Punkte)

Es sei G ein schlichter und r-regulärer Graph gerader Ordnung n ≥ 4. Man zeige, dass G oder sein Komplementärgraph Ḡ Hamiltonsch ist.

5) (4 Punkte)

Es sei A = {0, 1, 2} und k ∈ ℕ. Wieviele geordnete k-Tupel (a_{1}, a_{2}, …, a_{k}) ∈ A^{k} existieren, die genau t-mal die eins enthalten für 0 ≤ t ≤ k ?

Lehrstuhl II für Mathematik Prof. Dr. L. Volkmann SS 2000

1. Übung Diskrete Strukturen

Themen: Zahlentheorie

Aufgabe 1. Ist n ∈ ℕ, so zeige man:

a) 3|(n^{3} + 2n) b) 5|(n^{5} + 4n)

c) 5|(n^{4} − 1) ⇔ 5 ∤ n

Aufgabe 2. Ist p ≥ 5 eine Primzahl, so gilt 24|(p^{2} − 1).

Aufgabe 3. Es sei f_{1} = f_{2} = 1 und f_{n} = f_{n−1} + f_{n−2} für n ≥ 3 (Fibonacci-Folge). Für n ∈ ℕ zeige man:

ggT (f_{n}, f_{n+1}) = 1

Aufgabe 4. Sei n ∈ ℕ mit n ≥ 2. Man zeige, daß unter n ganzen Zahlen a_{i} mit 2 ≤ a_{i} ≤ 2n − 1 ein Paar a_{s}, a_{t} existiert mit ggT (a_{s}, a_{t}) = 1.

Aufgabe 5. Es sei a = p_{1}p_{2} … p_{n} das Produkt der ersten n Primzahlen. Man zeige: Ist a = dd′ mit 1 < d′ − d < (p_{n} + 2)^{2}, so ist d′ − d eine Primzahl mit d′ − d > p_{n}.

Aufgabe 6. Man zeige: Das Quadrat einer ungeraden Zahl läßt bei Division durch 8 den Rest 1.

Aufgabe 7.

a) Man zeige: Jede ungerade Zahl n ≥ 3 läßt sich als Differenz von zwei aufeinanderfolgenden Quadratzahlen darstellen.

b) Man zeige: Eine ungerade Zahl n ≥ 3 ist genau dann eine Primzahl, wenn sie nur eine Darstellung als Differenz von zwei Quadratzahlen besitzt.

2. Übung Diskrete Strukturen

Themen: Zahlentheorie

Aufgabe 1. Es seien a, b, c ∈ ℤ. Zeigen Sie:

a) Gilt a|c und b|c mit ggT(a, b) = 1, so gilt (ab)|c;

b) ggT(a + b, a − b) ≥ ggT(a, b);

c) Sind a, b > 0, so gilt ggT(a, b)| kgV(a, b).

Aufgabe 2. Es sei m ∈ ℕ, m ≥ 2. Wieviele Primzahlen existieren in dem abgeschlossenen Intervall [m! + 2, m! + m]?

Aufgabe 3. Beweisen Sie den Quersummentest für 3 und 9: Es sei A = a_{n}10^{n} + a_{n−1}10^{n−1} + … + a_{1}10 + a_{0} und S = a_{0} + a_{1} + … + a_{n} mit 0 ≤ a_{i} ≤ 9. Dann gilt

a) A ≡ S (mod 3), und b) A ≡ S (mod 9).

Aufgabe 4. Es sei n ∈ ℕ und p eine Primzahl mit n < p ≤ 2n. Zeigen Sie, daß gilt

\binom{2n}{n} ≡ 0 (mod p),

aber

\binom{2n}{n} ≢ 0 (mod p^{2}).

Aufgabe 5. Sind die folgenden Gleichungen mit x, y ∈ ℤ lösbar? Wenn ja, bestimmen Sie eine Lösung.

a) 481x + 299y = 13; b) 301x + 129y = 27; c) 297x + 189y = 23.

Aufgabe 6. Es seien a, b ∈ ℤ und p eine Primzahl. Zeigen Sie (a + b)^{p} ≡ a^{p} + b^{p} (mod p)

a) über den Binomischen Lehrsatz, b) über den kleinen Satz von Fermat.

Aufgabe 7. Es sei p eine Primzahl. Zeigen Sie:

a) Gilt p ≡ 3 (mod 4), so existiert kein n ∈ ℤ mit p|(n^{2} + 1).

b) Gilt p ≡ 1 (mod 4), so existieren solche n.

Aufgabe 8. Zeigen Sie, daß n und n + 2, mit n ≥ 2 ungerade, genau dann Primzahlen sind (sog. Primzahlzwilling), wenn gilt

4((n − 1)! + 1) + n ≡ 0 (mod n(n + 2)).

Information: Die Termine für die Diskussionsstunden sind:

Herr Christoph Schmitz, Mi. 12.25-13.55 Uhr, SG 23;
Frau Isabel Ribeiro  Mi. 15.45-17.15 Uhr, SG 23.

Die Diskussionsstunden beginnen am 03.05.2000. Die Termine für Sprechstunden sind:

Frau Miranca Fischermann, nach Vereinbarung, SG 21a;
Herr Arne Hoffmann,  Do. 10.00-11.00 Uhr, Raum 218 Hauptgebäude.

Die Übungsblätter gibt es auch im Internet auf der Seite www.math2.rwth–aachen.de.

3. Übung Diskrete Strukturen

Aufgabe 1. Sei G ein schlichter, zusammenhängender und nicht vollständiger Graph der Ordnung ≥ 3. Man zeige, daß es 3 verschiedene Ecken a, b, c ∈ E(G) gibt mit ab, bc ∈ K(G) aber ac ∉ K(G).

Aufgabe 2. Sei G ein schlichter Graph ohne Kreise der Länge 3. Man zeige: m(G) ≤ (\frac{n(G)}{2})^{2}.

Aufgabe 3. Beweisen oder widerlegen Sie den folgenden Satz: Seien G ein schlichter Graph, a, b ∈ E(G) mit a ≠ b und C ein Kreis in G durch a und b minimaler Länge. Seien W_{1} und W_{2} die Wege von a nach b mit K(W_{1}) ∪ K(W_{2}) = K(C). Dann gilt: d(a, b) = min{L(W_{1}), L(W_{2})}.

Aufgabe 4. Sei G ein zusammenhängender Graph der Ordnung ≥ 2. Man zeige:

a) κ(G − a) ≤ d(a, G) für jede Ecke a aus G.

b) Ist d(a, G) gerade für jede Ecke a aus G, so gilt 2κ(G − a) ≤ d(a, G) für jede Ecke a.

Aufgabe 5. Sei G ein schlichter Graph mit κ = κ(G) vollständigen Komponenten und sei n(G) ≡ r (mod κ) mit 0 ≤ r < κ. Man zeige:

m(G) ≥ \frac{1}{2κ}(n − r)(n + r − κ).

Aufgabe 6. Sei G ein schlichter Graph der Ordnung n, q ∈ ℕ mit 2 ≤ q ≤ n und δ(G) ≥ ⌊\frac{n}{q}⌋. Man zeige, daß κ(G) ≤ q − 1.

Aufgabe 7. Sei G ein schlichter, zusammenhängender Graph der Ordnung n mit δ(G) ≥ 2. Besitzt G eine Brücke, so zeige man: 2m(G) ≤ (n − 3)(n − 4) + 8.

Aufgabe 8. Untersuchen Sie, welche der Folgen als Gradsequenzen realisierbar sind, und welche sich sogar durch schlichte Graphen realisieren lassen.

a) 1, 2, 2, 3, 3, 3, 5, 7 b) 1, 2, 3, …, n

c) 1, 1, 2, 3, …, n − 1 (n ≥ 2) d) 1, 1, 2, 4, …, 2^{n−3}, 2^{n−2} (n ≥ 2)

Aufgabe 9. Sei G ein schlichter, zusammenhängender Graph und seien alle Kreise in G kantendisjunkt (G heißt dann Kaktusgraph). Zeigen Sie: Sind a und b zwei beliebige Ecken aus G mit d_{G}(a, b) = dm(G), so gilt max{d(a, G), d(b, G)} ≤ 2.

Aufgabe 10. Sei G ein schlichter, zusammenhängender Graph mit dm(G) ≥ 3. Zeigen Sie: dm(G) ≤ n(G) − 2δ(G) + 1.

Aufgabe 11. Sei G ein schlichter, zusammenhängender Graph mit n(G) = 2p, p ∈ ℕ, welcher p paarweise nicht inzidente Brücken enthält (d.h., die Brücken bilden ein perfektes Matching von G). Zeigen Sie:

m(G) ≤ \binom{p+1}{2}.

Geben Sie für allgemeines p ein Beispiel mit m(G) = \binom{p+1}{2} an.

4. Übung Diskrete Strukturen

Aufgabe 1. Sei G ein Graph und x ∈ E(G) beliebig mit d(x, G) ≥ 1. Zeigen Sie, daß ein maximales Matching M existiert mit x ∈ E(M).

Aufgabe 2. Sei G ein schlichter Graph und a, b ∈ E(G) nicht adjazent. Zeigen Sie:

a) Ist M ein maximales Matching von G mit a, b ∉ E(M), so gilt für jede Kante k = cd ∈ M: m_{G}({a, b}, {c, d}) ≤ 2.

b) Gilt d(a, G) + d(b, G) ≥ n(G) − 1, so besitzt G genau dann ein perfektes Matching, wenn G + ab ein perfektes Matching besitzt.

Aufgabe 3. Sei G ein schlichter, bipartiter Graph mit Bipartition A, B. Zeigen Sie, daß ein Matching M von G existiert mit |M| ≥ min{|A|, |B|, 2δ(G)}.

Aufgabe 4. Sei G ein schlichter, bipartiter Graph mit Bipartition A, B. Zeigen Sie, daß folgende Aussagen äquivalent sind:

a) Es existiert eine Menge W = {P_{a}|a ∈ A} bestehend aus |A| eckendisjunkten Wegen P_{a} der Länge zwei, so daß d(a, P_{a}) = 2 für jede Ecke a ∈ A.

b) Für alle Teilmengen S ⊆ A gilt |N(S, G)| ≥ 2|S|.

Aufgabe 5. Seien x_{1}, x_{2}, …, x_{n} die Ecken eines n-Turnieres T_{n}. Beweisen Sie:

a) Σ_{i=1}^{p}d^{+}(x_{i}, T_{n}) ≥ \binom{p}{2} für alle 1 ≤ p ≤ n.

b) Ist T_{n} stark zusammenhängend mit n ≥ 3, so gilt Σ_{i=1}^{p}d^{+}(x_{i}, T_{n}) ≥ \binom{p}{2} + 1 für alle 1 ≤ p ≤ n − 1.

Aufgabe 6. Es sei T ein Turnier mit n(T) ≥ 4. Zeigen Sie:

a) Es existieren höchstens 3 Ecken x mit d^{+}(x, T) = 1.

b) Ist T stark zusammenhängend, so gibt es höchstens 2 Ecken x mit d^{+}(x, T) = 1.

Aufgabe 7. Sei T ein p-reguläres Turnier (d^{+}(x, T) = d^{−}(x, T) = p für jedes x ∈ E(T)) mit n(T) ≥ 5. Zeigen Sie, daß jeder Bogen von T auf einem orientierten Kreis der Länge 3 und auf einem orientierten Kreis der Länge 4 liegt.

Aufgabe 8. Sei T_{n} ein stark zusammenhängendes Turnier mit n ≥ 3. Zeigen Sie, daß T_{n} mindestens n − 2 verschiedene 3-Kreise enthält.

Aufgabe 9. Sei T ein Baum mit Δ(T) ≥ 2, p ∈ ℕ mit 2 ≤ p ≤ Δ(T) und E_{p} = {x ∈ E(T) | d(x, T) ≥ p}. Ist der von E_{p} induzierte Teilgraph T [E_{p}] ein Nullgraph, so zeigen Sie |N(E_{p}, T)| ≥ (p − 1)|E_{p}| + 1.

Aufgabe 10. \underline{Definition:} Der Potenzgraph G^{2} eines schlichten Graphen G besteht aus der Eckenmenge E(G), und zwei verschiedene Ecken a und b sind genau dann adjazent in G^{2}, wenn d_{G}(a, b) ≤ 2 gilt.

a) Zeigen Sie, daß für einen schlichten Graphen G mit n(G) ≥ 3 der Potenzgraph G^{2} keine Brücke enthält.

b) Zeigen Sie, daß für einen Baum T mit gerader Ordnung n(T) der Potenzgraph T^{2} ein perfektes Matching besitzt.

(Folglich gilt b) auch für beliebigen schlichten Graphen G.)

Aufgabe 11. Sei G ein zusammenhängender Graph und a ∈ E(G) beliebig aber fest gewählt. Zeigen Sie, daß es ein Gerüst T von G gibt mit d(a, T) = κ(G − a).

5. Übung Diskrete Strukturen

Aufgabe 1. Es sei k eine Kante des vollständigen Graphen K_{n}. Für welche n ≥ 3 ist der Graph K_{n} − k semi-Eulersch?

Aufgabe 2. Sei G ein Eulerscher Graph. Beweisen Sie, daß ein Kreis C in G existiert mit n(C) > ⌈\frac{n(G)−1}{μ(G)}⌉.

Aufgabe 3. Sei q ≥ 2 eine natürliche Zahl und G ein schlichter (2q+1)-regulärer Graph der Ordnung n(G) ≤ 4q + 1. Zeigen Sie, daß G einen Eulerschen Faktor G′ mit δ(G′) > 2 besitzt.

Aufgabe 4. Sei G ein vollständig p-partiter Graph mit der Partition E_{1}, E_{2}, …, E_{p}, p ≥ 2 und mit n(G) ≥ 3. Ist D eine stark zusammenhängende Orientierung von G, so zeigen Sie, daß jede Ecke a ∈ E(D) in D auf einem orientierten Kreis der Länge 3 oder 4 liegt.

Aufgabe 5. Seien r_{3} ≥ r_{2} ≥ r_{1} ≥ 2 natürliche Zahlen mit r_{3} = r_{1} + r_{2} und G = K_{r_{1},r_{2},r_{3}} − PM ein 3-partiter Graph, wobei PM ein perfektes Matching des vollständig 3-partiten Graphen K_{r_{1},r_{2},r_{3}} ist. Zeigen Sie, daß G Hamiltonsch ist.

Aufgabe 6. Sei G ein schlichter, bipartiter Graph mit Bipartition A, B, wobei |A| = |B| = n ist. Erfüllen die nicht adjazenten Ecken a ∈ A und b ∈ B die Bedingung d(a, G) + d(b, G) ≥ n + 1, so zeigen Sie, daß G genau dann Hamiltonsch ist, wenn G + ab Hamiltonsch ist.

Aufgabe 7. Ist G ein schlichter planarer Graph der Ordnung n ≥ 11, so zeigen Sie, daß der Komplementärgraph \overline{G} nicht planar ist.

Aufgabe 8. Ist G ein schlichter, planarer Graph mit δ(G) ≥ 3, so zeigen Sie:

a) τ_{5} + 2τ_{4} + 3τ_{3} ≥ 12 + Σ_{i=7}^{Δ(G)}(i − 6)τ_{i}.

b) Es existieren mindestens 4 Ecken vom Grad kleiner oder gleich 5.

c) Ist die Taillenweite t(G) ≥ 4, so gilt τ_{3} ≥ 8.

Aufgabe 9. Sei G eine zusammenhängende, nicht triviale Landkarte ohne Brücken. Zeigen Sie: Ist G 2-färbbar, so ist G Eulersch.

Aufgabe 10. Es sei W die Menge aller Worte aus 0 und 1, d.h. w ∈ W ⇔ w = (w_{1}, …, w_{n}) mit w_{i} ∈ {0, 1}, n ≥ 1. |w| = n heißt dann auch Länge von w.

a) Wieviele Worte w ∈ W mit 1 ≤ |w| ≤ n gibt es?

b) Wieviele Palindrome der Länge n gibt es, d.h. w ∈ W mit (w_{1}, …, w_{n}) = (w_{n}, …, w_{1}).

c) Für zwei Worte u, v ∈ W der Länge n definieren wir die AND-Verknüpfung wie folgt: w = (u AND v) :⇔ w_{i} = u_{i} · v_{i} für alle 1 ≤ i ≤ n. Wieviele Möglichkeiten existieren, ein Wort w ∈ W der Länge n als AND-Verknüpfung zweier anderer Worte darzustellen?

Aufgabe 11. Gegeben sei eine Permutation f von {1, …, n}. Eine Inversion von f ist ein Paar i, j mit i < j aber f(i) > f(j). Mit I_{n,k} bezeichnen wir die Anzahl der Permutationen von {1, …, n} mit genau k Inversionen. Zeigen Sie:

a) I_{n,0} = 1;

b) I_{n,k} = I_{n,\binom{n}{2}−k} für k = 0, …, \binom{n}{2};

c) I_{n,k} = I_{n−1,k} + I_{n,k−1} für k < n. Gilt dies auch für k = n?

6. Übung Diskrete Strukturen

Aufgabe 1. Es sei f_{n,0} = 1 und f_{n,k}, für k ≥ 1, die Anzahl aller Untermengen der Größe k von {1, …, n}, welche kein Paar aufeinanderfolgender Zahlen enthalten. Zeigen Sie:

a) f_{n,k} = \binom{n−k+1}{k};

b) ∑_{k=0}^{n} f_{n,k} = f_{n+2},

wobei f_{n} die n-te Fibonacci-Zahl ist (vgl. Übung 1: f_{0} = 0, f_{1} = 1 und f_{n} = f_{n−1} + f_{n−2}).

Aufgabe 2. Für n ∈ ℕ sei M_{n} = {(F_{1}, F_{2}, F_{3})}, wobei die Mengen F_{i} folgenden Bedingungen genügen:

i) F_{1} ∪ F_{2} ∪ F_{3} = {1, 2, …, n} mit F_{i} ∩ F_{j} = ∅ für i ≠ j.

ii) min F_{1} ≤ min F_{2} ≤ min F_{3}, wobei wir min F_{i} := n + 1 setzen, wenn F_{i} = ∅.

Bestimmen Sie |M_{n}|.

Aufgabe 3. Beweisen Sie folgende geschlossene Darstellung für die Stirling-Zahlen 1. Art:

s_{n,k} = (n − 1)! ∑_{1≤i_{1}<...<i_{k−1}≤n−1} \frac{1}{i_{1}i_{2} ⋯ i_{k−1}} = ∑_{1≤i_{1}<...<i_{n−k}≤n−1} i_{1}i_{2} ⋯ i_{n−k}.

Aufgabe 4. Es sei S_{0} = 1 und S_{n}, für n ≥ 1, die Anzahl der Abbildungen f : {1, …, n} → {1, …, n} mit der Eigenschaft, daß f mit dem Wert i auch alle Werte j mit 1 ≤ j ≤ i annimmt. Zeigen Sie für n ∈ ℕ :

a) S_{n} = ∑_{k=1}^{n} \binom{n}{k}S_{n−k};

b) S_{n} = ∑_{k=1}^{n} k!S_{n,k},

dabei sind S_{n,k} die Stirling-Zahlen 2. Art.

Aufgabe 5. Zeigen Sie, daß die Anzahl der Zahlpartitionen einer Zahl n ∈ ℕ, deren Summanden alle nicht durch 3 teilbar sind, gleich derjenigen Anzahl ist, in denen kein Summand mehr als zweimal erscheint.

Aufgabe 6. Die Zahl n ∈ ℕ besitze r verschiedene Primfaktoren. Zeigen Sie: φ(n) ≥ \frac{n}{r+1}.

Aufgabe 7. Es sei n ∈ ℕ mit φ(n)|(n − 1). Zeigen Sie:

a) Es ex. keine Primzahl p mit p^{2}|n.

b) Ist n keine Primzahl, so besitzt n mindestens 3 verschiedene Primfaktoren.

Aufgabe 8. Für x ∈ ℝ mit x > 0 bezeichnet π(x) die Anzahl der Primzahlen ≤ x. Zeigen Sie, daß für alle k ∈ ℕ gilt:

\frac{π(x)}{x} ≤ \frac{φ(k)}{k} + \frac{2k}{x} .

7. Übung Diskrete Strukturen

Aufgabe 1.

a) Bestimmen Sie die erzeugende Funktion der Folge a_{0} = 1, a_{n} = 2 für alle n > 0.

b) Bestimmen Sie die erzeugende Funktion und die exponentiell erzeugende Funktion von der Folge a_{n} = 2^{n} + 5^{n}.

Aufgabe 2. Gegeben sei die rekursive Folge a_{n} = 2a_{n−1} −a_{n−2}, für n ≥ 2, und a_{0} = 0, a_{1} = 1. Bestimmen Sie a_{n} mit Hilfe einer erzeugenden Funktion.

Aufgabe 3. Bestimmen Sie die Anzahl aller 0/1–Worte der Länge n (vgl. Übung 5, A.9), in denen niemals zwei Nullen hintereinander vorkommen.

Aufgabe 4. Kehren wir noch einmal zu den Funktionen aus Übung 6, Aufgabe 4 zurück: S_{n} sei die Anzahl der Funktionen von {1, …, n} → {1, …, n}, die mit dem Wert i auch jeden Wert j ≤ i annehmen. Zeigen Sie mit Hilfe einer exponentiell erzeugenden Funktion:

S_{n} = ∑_{k≥0} \frac{k^{n}}{2^{k+1}} .

Hinweis: 2S_{n} = ∑_{k=0}^{n} \binom{n}{k}S_{n−k} für n ≥ 1.

Aufgabe 5. Zeigen Sie folgende Gleichheit:

∑_{n≥1} \frac{|μ(n)|}{n^{s}} = ∏_{p}(1 + p^{−s}) = \frac{ζ(s)}{ζ(2s)},

wobei p alle Primzahlen durchläuft.

Aufgabe 6. Gegeben sei eine Halbordnung (H, ⪯). Ein Filter F ist eine Menge F ⊂ H mit der Eigenschaft: x ∈ F und y ⪰ x, dann gilt auch y ∈ F. Ferner ist ∅ ein Filter. Zeigen Sie, daß es in (H, ⪯) genauso viele Filter wie Antiketten gibt.

Information:

Zu der Vordiplomklausur am 20.09.2000 werden in der vorlesungsfreien Zeit an folgenden Tagen zusätzliche Diskussionsstunden für die Diskreten Strukturen angeboten:

Dienstag, 12.09.00, bis Freitag, 15.09.00, jeweils 10.00–11.30 Uhr im SG 23.