Prädikatenlogische Formeln
Der Aussagenlogik besitzt eine lange philosophische Tradition und zudem interessante Anwendungen innerhalb der Mathematik und Informatik, reicht aber als Sprache für die Mathematik nicht aus. Die Mathematik wird heute in der ausdrucksstärkeren Prädikatenlogik erster Stufe formuliert. Ihr Formelbegriff benötigt keine Aussagenvariablen, sondern beruht auf folgenden Zeichen:
Variablensymbole x, y, z, …,
Identität =,
Funktionssymbole f, g, h, … mit bestimmten Stellenzahlen,
Relationssymbole R, S, T, … mit bestimmten Stellenzahlen,
Konstantensymbole c, d, e, …,
Junktoren ¬, ∧, ∨, ⩒, →, ↔,
Falsum und Verum ⊥, ⊤,
Quantoren ∀, ∃, ∃!,
Klammern (, ).
Der Vorrat an Funktions-, Relations- und Konstantensymbolen − die sogenannte Signatur der Sprache − ist abhängig von der zu formulierenden mathematischen Theorie. In der axiomatischen Mengenlehre wird nur ein zweistelliges Relationssymbol ∈ für die Elementbeziehung benötigt. Die Sprache mit der leeren Signatur (nur mit Identität) ist die reine Logik.
Mit Hilfe der Zeichen werden der Reihe nach Terme, Primformeln und Formeln durch folgende Schemata definiert:
(1) | Jede Variable und jede Konstante ist ein Term. |
(2) | Sind t1, …, tn Terme, und ist f ein n stelliges Funktionssymbol, so ist f(t1, …, tn) ein Term. |
(3) | ⊥ und ⊤ sind Primformeln. |
(4) | Sind t und s Terme, so ist t = s eine Primformel. |
(5) | Sind t1, …, tn Terme und ist R ein n-stelliges Relationssymbol, so ist R(t1, …, tn) eine Primformel. |
(6) | Jede Primformel ist eine Formel. |
(7) | Sind φ und ψ Formeln, so sind auch ¬ φ, (φ ∧ ψ), (φ ∨ ψ), (φ ⩒ ψ), (φ → ψ) und (φ ↔ ψ) Formeln. |
(8) | Ist φ eine Formel und x eine Variable, so sind auch ∀x φ, ∃x φ, ∃!x φ Formeln. |
In ∀x φ, ∃x φ, ∃!x φ heißt φ der Wirkungsbereich des Quantors ∀x, ∃x bzw. ∃!x. Liegt eine Variable einer Formel nicht im Wirkungsbereich eines Quantors der Formel, so heißt die Variable eine freie Variable. Andernfalls heißt sie gebunden. Wir schreiben φ(x1, …, xn), wenn alle freien Variablen von φ unter x1, …, xn vorkommen. Eine Formel ohne freie Variable heißt eine Aussage oder ein Satz.
Um Klammern zu sparen, übernehmen wir die Bindungsstärke der Junktoren aus der Aussagenlogik und legen zudem fest, dass Quantoren stärker binden als Junktoren. Damit ist zum Beispiel ∀x φ ∧ ψ zu unterscheiden von ∀x (φ ∧ ψ). In der ersten Formel ist φ der Wirkungsbereich des Allquantors ∀x, in der zweiten (φ ∧ ψ). Weiter scheiben wir ∀x, y φ statt ∀x ∀y φ. Analoges gilt für die anderen Quantoren und drei oder mehr Variable. Statt ¬(t = s) schreiben wir wie üblich auch t ≠ s.
Beispiele
Wir betrachten die Sprache mit einem einstelligen Funktionssymbol S, zwei zweistelligen Funktionssymbolen +, ·, zwei Konstantensymbolen 0, 1 und einer zweistelligen Relation <. Variablen notieren wir als n, m, k usw. Statt +(n, m), ·(n, m) und <(n, m) schreiben wir n + m, n · m und n < m. Um die eindeutige Lesbarkeit zu erhalten, verwenden wir Klammern, wobei · stärker binden soll als +.
Terme
n, m, k, 0, 1,
S(n), n + m, n + 0, 1 + m,
n + (n + m), n · m + k, n · (m + k),
S(S(n)), S(n + m), n + S(m), S(n) · (S(S(m)) + (k + k)).
Primformeln
n = m, n < n, m < k, 0 < 1, 1 < 0,
n < S(n), S(k + m) = S(S(k + m)), n · m < m + S(n),
Formeln
| S(n) = 1 ∨ ∃m S(m) = 1, | freie Variable: n |
| n < m ∨ n = m ∨ m < n, | freie Variable: n, m |
| ∃n ∀n ∀n n = k ∨ ∃m 0 = 0, | freie Variable: k |
| ∃n n = 0 ∧ ∃m k · n = 1, | freie Variable: k, n |
Aussagen
∀n, m (S(n) = S(m) → n = m),
∀n, m (S(n) = S(m) → n = 0),
∀n n + m = S(n), ∀n S(n) ≠ 0,
∀n ∃k n < k ∧ ∀n (n ≠ 0 → ∃m m < n).
Weitere Funktions-, Relations- und Konstantensymbole können wir durch Definitionen einführen. Dadurch werden die Ausdrucksmöglichkeiten der Sprache zwar prinzipiell nicht vergrößert, aber Formeln kürzer und lesbarer.
Beispiele
In der Signatur des obigen Beispiels können wir setzen:
| 2 | wird definiert als | S(1), |
| quad(n) | wird definiert als | n · n, |
| n ≤ m | wird definiert als | n < m ∨ n = m, |
| d | n | wird definiert als | ∃k d · k = n, |
| prim(n) | wird definiert als | 1 < n ∧ ∀d (d | n → d = 1 ∨ d = n). |
2 ist ein Konstantensymbol, quad ein zweistelliges Funktionssymbol, ≤, | und prim sind zwei- bzw. einstellige Relationssymbole.
Die logische Zeichenfülle lässt sich reduzieren, indem
| A ∨ B | als | ¬ (¬ A ∧ ¬ B), |
| A → B | als | ¬ A ∨ B (oder gleichwertig ¬ (A ∧ ¬ B)), |
| A ↔ B | als | (A → B) ∧ (B → A), |
| A ⩒ B | als | ¬ (A ↔ B), |
| ∃x φ | als | ¬ ∀x ¬ φ(x), |
| ∃!x φ | als | ∃x ∀y (φ(y) ↔ x = y), |
| ⊥ | als | ∃x ¬ (x = x), |
| ⊤ | als | ¬ ⊥ |
definiert wird. Es genügen also ¬, ∧ und ∀.
Wir erwähnen noch zwei Aspekte der Prädikatenlogik, die im mathematischen Alltag nützlich sind:
(1) | Prädikatenlogische Tautologien: Ersetzt man in einer aussagenlogischen Tautologie die Aussagenvariablen durch Formeln der Prädikatenlogik, so erhält man eine prädikatenlogische Tautologie. Diese Tautologien werden in der Mathematik als logische Axiome verwendet. Ein Beispiel ist die Formel ∀x (x = x) ∧ f (x) = y → f (x) = y, die aus der Formel A ∧ B → B der Aussagenlogik gewonnen wird. |
(2) | Äquivalente Ersetzung: Es gelte φ ↔ ψ. Ersetzen wir nun in einer Formel χ eine Teilformel φ durch ψ, so erhalten wir eine zu χ äquivalente Formel χ′, d. h. es gilt χ ↔ χ′. Damit können wir zum Beispiel eine Implikation φ → ψ innerhalb einer beliebig komplexen Formel stets durch ¬ φ ∨ ψ ersetzen, wenn wir dies möchten. |