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).