Übung zur Prädikaten-Logik

• Die folgende Formel E mathend000# ist erfüllbar.
  
  
  Bestimmen Sie ein Modell mit möglichst kleinem Universum.

• Geben Sie eine (kleine) erfüllbare Formel F mathend000# an, so daß jedes Modell von F mathend000# wenigstens 5 Elemente enthält.

• Beweisen Sie: Erfüllbarkeit ist bereits für Formeln ohne Funktionssymbole unentscheidbar.

  Geben Sie dazu ein Verfahren an, das aus einer beliebigen Formel F mathend000# eine Formel G mathend000# ohne Funktionssymbole erzeugt, so daß gilt: F mathend000# besitzt Modell $\iff$ mathend000# G mathend000# besitzt Modell. Hinweis: zusätzliche Relationssymbole.

  Wenden Sie das Verfahren auf die o.g. Formel E mathend000# (und das von Ihnen gefundene Modell) an.

• Beweisen Sie, daß Erfüllbarkeit und Allgemeingültigkeit entscheidbar sind für Formeln,
  • die nur nullstellige Rel.-Symbole und keine Fkt.-Symbole enthalten,
  • die nur einstellige Rel.-Symbole und keine Fkt.-Symbole enthalten.
  Hinweis: es genügt, endliche Modelle bis zu einer gewissen Größe zu betrachten.

(vgl. Uwe Schöning: Logik für Informatiker, Spektrum)