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

Übungsblatt 10

Abgabe in der 11. Semesterwoche

10.1 Formulieren Sie in der für die Graphentheorie verwendeten Sprache 1. Ordnung folgende Eigenschaft von Graphen: "G ist 3-regulär, d.h. alle vorkommenden Grade sind 3.

10.2 Betrachten Sie die Formel B: "$ x A(x) ® " x A(x)" in der für Graphen verwendeten Sprache. Zeigen sie, daß, unabhängig vom genauen Aussehen der Formel A(x), jeder Graph mit nur einer Ecke ein Modell für die Aussage B ist. Geben Sie je ein Beispiel für die Formel A(x) für die B in jedem Graphen gilt, bzw. nicht in jedem Graphen gilt.

10.3 Für welche der folgenden Formeln ist der Graph G=(V,Adj) mit V={1,2,3,4,5,6,7} und Adj={(1,2), (2,1), (2,3), (3,2), (3,4), (4,3), (2,5), (5,2), (3,5), (5,3), (5,6), (6,5), (6,7), (7,6)} ein Modell:
a) $ x $ y " z (z = x Ú (z = y Ú (Adj x z Ù Adj y z))
b) $ x " y (Ø (x = y) ® (Adj x y Ú $ z (Adj x z Ù Adj y z)))
c) $ x $ y ((Ø (x = y) Ù Adj x y) Ù " z (Ø(z = y) ® Ø(Adj x z)))

10.4 "F" stehe für eine binäre Verknüpfung, "R" stehe für eine binäre Relation, "C" stehe für eine Konstante. Welche Vorkommen der Variablen x, y, und z in folgender Formel sind frei, welche gebunden?
" z ($ y R F z F x y c Ù " x C = F z F x x).


zum Extrablatt
Juni 2000