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