Aussagenkalküls

Aussagenkalküls bezeichnet in der Logik das formale System zur Analyse und Ableitung von Aussagenverknüpfungen. Es untersucht, wie aus einfachen Behauptungen mithilfe logischer Operatoren neue Aussagen entstehen und wie Wahrheiten formell bewertet werden.

Syntax: Die Bausteine sind propositionale Variablen wie p, q, r und die Operatoren ¬, ∧, ∨, →, ⟷. Aus diesen lassen sich durch geschachtelte Verknüpfungen gut geformte Formeln (WFFs) bilden; Klammern definieren die Struktur.

Semantik: Jedem Valuation v ordnet man jeder Variablen einen Wahrheitswert zu. Die Verknüpfungen werden durch Wahrheitswerttabellen definiert. Eine Formel ist eine Tautologie, wenn sie unter allen Belegungen wahr ist; sie ist satisfierbar, wenn es eine Belegung gibt, unter der sie wahr wird; sie ist eine Kontradiktion (Widerspruch), wenn sie unter allen Belegungen falsch ist.

Begründungssysteme: Das Kalkül kann als Hilbert-System mit axiomatischen Schemata und der Regel Modus ponens formuliert werden. Typische Axiomsschemata umfassen z. B. p → (q → p), (p → (q → r)) → ((p → q) → (p → r)) und (¬p → ¬q) → (q → p). Aus p und p → q folgt q, dies ist der Modus ponens.

Eigenschaften: Wichtige Formal-Eigenschaften sind Faithfulness (Gültigkeitssicherung) und Vollständigkeit: Soundness bedeutet, dass aus den Axiomen ableitete Formeln semantisch wahr sind; Completeness bedeutet, dass jede semantisch wahre Formel auch beweisbar ist.

Varianten und Anwendungen: Neben Hilbert-Systemen gibt es Natural Deduction, Sequent Calculus und intuitionistische Varianten. Anwendungen finden sich in Mathematik, Informatik, Verifikation von Programmen und automatisierter Beweisführung.