Prädikatenlogik

Prädikatenlogik, auch Prädikatenlogik erster Stufe oder einfach Erstordnungslogik genannt, ist ein formales System der Logik, das die Aussagenlogik um Quantifizierer, Variablen, Prädikate und Funktionssymbole erweitert. Sie ermöglicht Aussagen über Objekte, deren Eigenschaften und Beziehungen untereinander und bildet damit die Grundlage vieler mathematischer und informatischer Theorien.

Die Syntax umfasst Variablen, Konstanten, Funktionssymbole und Prädikatsymbole mit festgelegter Arität. Aus Termen bilden sich atomare Formeln wie P(t1,…,tn), die durch logische Verbindungssymbole (¬, ∧, ∨, →) zu komplexen Formeln kombiniert werden. Die Quantoren ∀ (für alle) und ∃ (exists) erlauben Aussagen über Elemente der Domäne. Formeln ohne freie Variablen nennt man Sätze bzw. Aussagenlogikformeln.

Die Semantik beruht auf Interpretationen, die einer Domäne D und die Symbole entsprechend zuordnen: Funktionssymbole als echte Funktionen auf D, Prädikatensymbole als Relationen auf D. Die Wahrheit einer Formel wird relativ zur Interpretation bestimmt: atomare Formeln gelten als wahr, wenn die zugeordneten Kriterien erfüllt sind; ∀x φ bedeutet, dass φ für jedes Element der Domäne gilt, ∃x φ, dass es mindestens ein Element gibt, für welches φ wahr ist. Eine Interpretation, in der eine Formel wahr ist, heißt Modell der Formel.

Prädikatenlogik ist deutlich ausdrucksstärker als die Aussagenlogik und bildet die Grundlage für Mathematik, Informatik und formale Verifikationen. Sie umfasst wichtige meta-logische Ergebnisse wie die Vollständigkeit (Gödel) und Kompaktheit, sowie die Tatsache, dass Allgemeine Prädikatenlogik unentscheidbar ist. Anwendungen reichen von der Formalisierung mathematischer Theorien bis zur Semantik von Programmiersprachen und Datenbanken.