DISKRETE MATHEMATIK
Dr. E. Prisner, Dr. J. Sustal,
Dr. W. Preuß, S. Fröhlich,
Sommersemester 2000

S.1 Gegeben sind zwei Ordnungsrelationen R und S auf der Menge M={a,b,c,d,e,f}.
R = {(a,a), (a,d), (a,e), (a,f), (b,b), (b,c), (b,d), (b,e), (b,f), (c,c), (c,e), (c,f), (d,d), (d,e), (d,f), (e,e), (f,f) },
S = {(a,a), (a,c), (a,d), (a,e), (a,f), (b,b), (b,c), (b,e), (c,c), (c,e), (d,d), (d,f), (e,e), (f,f) }.

• (a) Bilden Sie den Durchschnitt R S und zeichnen Sie die Hasse-Diagramme von R, S, und R S
• (b) liegen (a,c), (a,f) in R ° S?

S.2 Eine Aussageform F habe den folgenden Werteverlauf

a	b	c	F(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Geben Sie die entsprechenden kanonischen Normalformen an (DNF, KNF).

S.3 Eine Äquivalenzrelation R partitioniert die komplexe Ebene C in 4 Klassen (Quadranten):

• K₁ --- alle komplexen Zahlen im 1. Quadrant,
• K₂ --- alle komplexen Zahlen im 2. Quadrant,
• K₃ --- alle komplexen Zahlen im 3. Quadrant,
• K₄ --- alle komplexen Zahlen im 4. Quadrant,

S.4 Zeigen Sie, daß es keinen endlichen Graphen gibt, bei dem alle Eckengrade verschieden sind. Gibt es einen solchen unendlichen Graphen? Gibt es einen Graphen mit 10 Ecken, bei dem alle Grade bis auf zwei verschieden sind?

S.5 Lösen Sie die Rekursionsgleichung u_n+2 = 6 u_n+1 - 8 u_n, u₀ =0, u₁ = 4.

S.6 Wie groß ist die Anzahl der surjektiven Abbildungen f aus {1,2,3,4,5} nach {6,7,8}?

S.7 Es seien folgende Prämissen gegeben:

• p q
• r s
• (q r) (p t)
• s p

S.8 Beschreiben Sie die Modelle folgender Theorien (etwa für die Sprache mit einer binären Relation, aber das spielt keine Rolle):

• (a) { x y z ( x = z y = z)},
• (b) { x y x = y},
• (c) x y z ( x = z x = y)},