Formel (Prädikatenlogik)

Die Menge $FO[\sigma ]$ der Formeln ist induktiv definiert:

1. Atomare Formeln: $t_1=t_2$ oder $R(t_1,\dots ,t_k)$.
2. Verknüpfungen: Sind $\phi ,\psi$ Formeln, dann auch $\mathrm{\neg }\phi ,(\phi \wedge \psi ),(\phi \vee \psi ),\dots$
3. Quantoren: Ist $\phi$ eine Formel und $x$ eine Variable, dann sind $\mathrm{\exists }x\phi$ und $\mathrm{\forall }x\phi$ Formeln.