Sei ein zweistelliges Relationssymbol in Infixnotation. Betrachten Sie den FO()-Satz
ϕ = ∀x1∀x2∃x3
(x3 x1 ∧ x3 x2
) ∧ ∀x4
(x4 x1 ∧ x4 x2
) → x4 x3
und die Struktur A = (A,
A ) mit A = {0, 1, 2} und
A = {(0, 0),(0, 1),(0, 2),(1, 2)}.
(a) Geben Sie eine zu ϕ äquivalente Formel ϕ
0
in Negationsnormalform an.
(b) Zeigen Sie A 6 ϕ, indem Sie eine Gewinnstrategie des Falsifizierers im Spiel zur Startposition (ϕ
0
,(a1
, a2
, a3
, a4
))
angeben, wobei a1
, . . . , a4 ∈ A beliebig sind. (Tipp: Es kann hilfreich sein, wenn Sie sich zunächst klar machen,
warum A kein Modell von ϕ ist, etwa indem Sie A als gerichteten Graphen zeichnen.)
