Theorien

Theorie einer Struktur = alle Formeln, die in dieser Struktur wahr sind.

Beispiel: Signatur $\Sigma_{F}^{}$ = {0₀, S₁, + ₂},$\Sigma_{R}^{}$ = { = ₂},

Struktur: $\mathbb {N}$ mit Null, Nachfolger, Plus, Gleichheit.

Theorie T der natürlichen Zahlen mit Addition.

Formel ($\forall$x : $\forall$y : $\forall$z : x + (y + z) = (x + y) + z) $\in$ T.

typische (algorithmische) Fragen:

• Erfüllbarkeit (gehört $\exists$-Abschluß von Formel F zu T?)
• Wahrheit (gehört geschlossene Formel F zu T?)