Freie Variablen und die Sätze von ℒ
Definition (freie Variablen)
Die freien Variablen einer Formel sind wie folgt festgelegt.
(i) | Die freien Variablen von x = y und x ∈ y sind x, y. |
(ii) | Die freien Variablen von ¬ φ sind die freien Variablen von φ. |
(iii) | Die freien Variablen von φ ∧ ψ, φ ∨ ψ, φ → ψ und φ ↔ ψ bestehen aus den freien Variablen von φ und den freien Variablen von ψ. |
(iv) | Die freien Variablen von ∀x φ und ∃x φ sind die freien Variablen von φ ohne die Variable x. |
Eine Variable x, die in φ in der Form ∀x oder ∃x vorkommt, heißt eine gebundene Variable von φ. Beispielsweise sind x, y, z die freien Variablen der Formel
φ = (∃u. u = y ∨ u = x) ∧ ∀x. x ∈ y → x = z.
Die gebundenen Variablen dieser Formel sind u und x. x kommt also in φ sowohl frei als auch gebunden vor. Das erste Vorkommen von x in φ ist frei, das zweite Vorkommen von x in φ ist gebunden.
Definition (Sätze/Aussagen)
Eine Formel von ℒ heißt eine Aussage oder ein Satz von ℒ, falls φ keine freien Variablen besitzt.
Definition (Generalisierung und Allabschluss einer Formel)
Sei φ eine Formel, und seien x1, …, xn Variablen (mit n ≥ 0). Dann heißt ∀x1, …, xn φ eine Generalisierung von φ. Ist ψ eine Generalisierung von φ ohne freie Variablen, so heißt ψ ein Allabschluss von φ.
Der Fall n = 0 bedeutet, dass φ selbst als eine Generalisierung von φ gilt.
Definition (die Schreibweise φ(x1, … , xn))
Seien φ eine Formel und x1, …, xn paarweise verschiedene Variablen. Wir schreiben φ(x1, …, xn), wenn die freien Variablen von φ unter x1, … , xn vorkommen.
Schreiben wir φ(x1, … , xn), so folgt nicht, dass genau x1, … , xn die freien Variablen von φ sind. Z. B. können wir die Formel φ = „∀x x = y“ schreiben als φ(x, y, z). Diese Konvention erweist sich als überaus bequem.