Klausur zur Vorlesung ”Diskrete Strukturen“ SS 92

Aufgabe 1. 5 Punkte Bestimmen Sie die kleinste natürliche Zahl n, für die 13 | n + 4, 11 | n − 3 und 7 | n + 2 gilt.

Aufgabe 2. 2+2 Punkte (a) Wieviele nicht-isomorphe abelsche Gruppen der Ordnung 180 mit zwei (oder weniger) Erzeugern gibt es? Begründen Sie Ihre Antwort!

(b) Wieviele nicht-isomorphe abelsche Gruppen der Ordnung 180 mit drei (oder weniger) Erzeugern gibt es? Begründen Sie Ihre Antwort!

Aufgabe 3. 3 Punkte Es sei I ⊆ Z_{2}[x] das von x^{3} +x^{2} +1 und x^{2} +x+1 erzeugte Ideal in Z_{2}[x]. Zeigen Sie, daß I = Z_{2}[x] gilt.

Aufgabe 4. 3+6 Punkte (a) Es seien zwei Polynome f = x^{5} + x^{4} + x^{3} + 1 und g = x^{4} + x^{2} + 1 aus Z_{2}[x] gegeben. Bestimmen Sie einen größten gemeinsamen Teiler d von f und g sowie Polynome u und v aus Z_{2}[x], für die d = u ∗ f + v ∗ g gilt.

(b) Es sei K ein Körper, f und g zwei Polynome aus K[x] mit ∂f > ∂g und d ∈ ggT (f, g). Der erweiterte Euklidische Algorithmus liefert Polynome u und v aus K[x] mit d = u ∗ f + v ∗ g. Zeigen Sie, daß für das Polynom u die Abschätzung ∂u ≤ ∂g − ∂d gilt. ∂h bezeichne dabei den Grad eines Polynoms h. ANLEITUNG: Zeigen Sie zuerst, daß ∂x_{i+1} < ∂x_{i+2} und ∂r_{i} + ∂x_{i+1} = ∂g für i ≥ 0 im erweiterten Euklidischen Algorithmus (bei Startwerten r_{0} = g und r_{−1} = f) gilt.

Aufgabe 5. 1+3 Punkte (a) Es sei φ die Eulersche φ-Funktion. Berechnen Sie φ(81), φ(25) und φ(2025).

(b) Zeigen Sie: Aus n | m folgt φ(n) | φ(m).

Aufgabe 6. 4 Punkte Bestimmen Sie die ganzzahligen Lösungen x ∈ V_{3×1}(Z) der Gleichung

( \begin{matrix}2 & 4 & 2 \\ 4 & 6 & 4 \\ 6 & 8 & 12 \\ 4 & 6 & 4 \end{matrix} ) x = ( \begin{matrix}4 \\ 4 \\ 10 \\ 4 \end{matrix} ) .

Aufgabe 7. 3 Punkte

Es sei P die Pyramide . Es sei M die Menge der Ecken, Kanten und Flächen sowie P und ∅. Dann ist (M, ⊆) eine verbandsgeordnete Menge. Bestimmen Sie die Eulercharakteristik des zugehörigen Verbandes.

Aufgabe 8. 3 Punkte Es sei M = {a, b, c, d, e} und ≤ = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, e), (d, e)} gegeben. Es sei g : M → N eine Gewichtsfunktion. Bestimmen Sie aus den summierten Gewichten f(x) = ∑_{d≤x} g(d) mittels Möbiusinversion die ursprüngliche Gewichtsfunktion g. Dabei ist f gegeben durch f(a) = 1, f(b) = 2, f(c) = 4, f(d) = 6 und f(e) = 12.

Aufgabe 9. 2 Punkte Es sei O ein regelmäßiger Oktaeder. Es sei M die Menge der Ecken, Kanten und Flächen sowie O und ∅. Dann ist (M, ⊆) eine verbandsgeordnete Menge. Ist der zugehörige Verband ein Boolescher Verband?

Aufgabe 10. 2+8 Punkte (a) Es sei A eine freie Boolesche Algebra mit freiem Erzeugendensystem {x_{1}, x_{2}, x_{3}}. Bestimmen Sie die disjunktive Normalform des Elementes (x_{1} + x_{2} + x_{3}) · (x_{1} + \overline{x_{2}} + \overline{x_{3}}).

(b) Es sei B eine Boolesche Algebra mit freiem Erzeugendensystem \{x_{1}, …, x_{n}\}. Für ϵ ∈ \underline{2}^{n} = \{0, 1\}^{n} sei q_{ϵ} definiert als x_{1}^{ϵ_{1}} + … + x_{n}^{ϵ_{n}}. Für eine Teilemenge I von \underline{2}^{n} sei w_{I} definiert als ∏_{ϵ∈I} q_{ϵ}. Bestimmen Sie für w_{I} die disjunktive Normalform. HINWEISE: DeMorgansche Regeln. Was ist \overline{w_{I}}?.

Aufgabe 11. 2+2+2+4 Punkte Es sei A die Klasse der abelschen Gruppen.

(a) Gibt es für Z ˙+Z ein A–freies Erzeugendensystem? Wenn ja, geben Sie eins an.

Es sei M = {(3, 11, 3, 19), (4, 13, 6, 23), (2, 4, 6, 8)} ⊂ V_{1×4}(Z). Weiter sei U die von M erzeugte Untergruppe.

(b) Zeigen Sie, daß M kein A–freies Erzeugendensystem für U ist.

(c) Gibt es ein A-freies Erzeugendensystem für U? Wenn ja, geben Sie es an!

(d) Ist die Faktorgruppe V_{1×4}(Z)/U A-frei? Begründen Sie Ihr Antwort!

Aufgabe 12. 3+2 Punkte Das Ideal I = (x^{3} +x^{2} +1)Q[x] von Q[x] kann als Q[X]–Teilmodul und als Q–Teilmodul von Q[X] aufgefaßt werden. Entsprechend ist Q[X]/I ein Q[x]– oder Q–Modul.

(a) Bestimmen Sie eine Basis für Q[X]/I als Q–Modul.

(b) Bestimmen Sie ein unverkürzbares Erzeugendensystem für Q[X]/I als Q[x]–Modul.

Aufgabe 13. 3+2 Punkte

(a) Bestimmen Sie das Minimalpolynom von ( \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} ) ∈ V_{3×3}(Q).

(b) Es sei s ein Element aus den reellen Zahlen R mit s^{2} = 2 und a = 1 + s. Bestimmen Sie das Minimalpolynom von a über Q.