Formeln und Modellmengen

Idee: logische Verknüpfungen ⇒ passende Operationen auf (kodierten) Modellmengen

• Mod(False) = ∅, Mod(¬F) = ...
• Mod(F₁∧F₂) = Mod(F₁)∩Mod(F₂)
• Mod(∃x_i.F) = proj_i(Mod(F))

  Projektion entlang i-ter Komponente: proj_i : $\mathbb {N}$^k→$\mathbb {N}$^k-1 :

  (x₁,…, x_k) $\mapsto$ (x₁,…, x_i-1, x_x+1,…, x_k)

zu zeigen ist, daß sich diese Operationen effektiv realisieren lassen (wobei Ein- und Ausgabe durch endl. Automaten dargestellt werden)

Ü: warum werden andere Verknüpfungen nicht benötigt?