Formeln und Modellmengen

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

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

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

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

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?