Taal

Alfabet

1. Een verzameling C van individuele constanten.Eg. {a, b, c, d}
2. Een verzameling P van predikaatletters. Eg. {A( ), B ( ), C( )}
3. Een verzameling F van functieletters. Eg. {f₁ ,g₂ ,h₃ ,i₄}
4. Logische symbolen ¬, ∧, ∨, →, ↔, ∀ en ∃.
5. Individuele variabelen. Eg. {u, v, w, x, y, z}
6. Hulpsymbolen ) en (.

∀, Universele kwantor: 'Voor alle'
∃, Existentiële kwantor: 'Er is een'

Plaatsigheid van een predikaat: Aantal argumenten.
Notatie. P(a, b) = 2 plaatsig. oftwel P²

Bereik kwantoren: In het algemeen is het bereik van een voorkomen van een kwantor in een formule φ de subformule waarvóór die kwantor is gevoegd tijdens de constructie van φ.

Vrij en gebonden variabelen: Variabele x heet vrij als deze niet in het bereik van een kwantor ligt.

Gesloten of open formules: Een zin of gesloten formule is een formule zonder vrije variabelen. Een formule waarin vrij variabelen voorkomen, heet een open formule.

Vrij voor x in φ: Een term t heet vrij voor x in φ, als in [t / x] φ geen variabele van t in een gesubstitueerd voorkomen van t gebonden voorkomt.

Formule

Formules van de predikaatlogica worden als volgt gedefinieerd:

1. Als P^k een k-plaatsige predikaatletter is en t₁, ..., t_k zijn termen, dan is P(t₁, ..., t_k ) een formule.
2. Als φ en ψ formules zijn, dan ook ¬ψ, ( φ ∧ ψ ), ( φ ∨ ψ ), ( φ → ψ ) en ( φ ↔ ψ ).
3. Als φ een formule is en x een individuele variabele, dan zijn ∀ x φ en ∃ x φ ook formules.
4. Niets is een formule dan op grond van vorige regels.

Atomaire formule: formule in de vorm P(t₁ , ..., t_k ).

Substitutie

1. Laat t en t' termen zijn en x een variabele. Dan is [t / x] t' de term die ontstaat door elk voorkomen van x in t' te vervangen door t.
2. Laat φ een formule zijn, t een term en x een variabele. Dan is [t / x] φ de formule die ontstaat door elk vrij voorkomen van x in φ te vervangen door t. ( [t / x]φ noemt wel een instantie van φ.)