Propositionslogik

Propositionslogik, auch als Aussagenlogik bezeichnet, ist ein formales Teilsystem der Logik, das sich mit Wahrheitswerten einfacher Aussagen sowie mit den Verknüpfungen dieser Aussagen befasst. Eine Aussage ist eine Behauptung, die wahr oder falsch sein kann; zusammengesetzte Aussagen entstehen durch logische Verknüpfungen.

Syntax: Die Sprache verwendet Propositionsvariablen wie p, q oder r. Verknüpfungen sind Konjunktion ∧ (und), Disjunktion ∨ (oder), Negation ¬ (nicht), Implikation → (wenn... dann) und Äquivalenz ↔ (genau dann, wenn). Komplexe Formeln werden durch Klammern strukturiert.

Semantik: Für jede Belegung v ordnet man jeder Variablen p einen Wahrheitswert zu. Die Wahrheitswerte zusammengesetzter Formeln ergeben sich aus Wahrheitstafeln. Eine Formel ist eine Tautologie, wenn sie unabhängig von der Belegung wahr ist; sie ist satisfierbar, wenn es eine Belegung gibt, unter der sie wahr wird; sie ist unsatisfierbar, wenn keine solche Belegung existiert.

Inferenz: Folgerungen werden durch Regeln wie Modus Ponens nachvollzogen (aus p und p→q folgt q) oder durch formale Beweissysteme, etwa natürliche Deduktion. In der Aussagenlogik gilt Vollständigkeit: Jede semantisch gültige Formel ist auch syntaktisch beweisbar.

Anwendungen und Grenzen: Die Aussagenlogik dient der Modellierung von Boolean-Schaltungen, formeller Verifikation und automatisierter Schlussfolgerung. Sie ist decidierbar; das Erkennen von Sat­isfiability (SAT) ist NP-vollständig. Ihre Ausdrucksfähigkeit ist begrenzt; Quantorenlogik (Prädikatenlogik) erweitert sie, um über Objekte und Eigenschaften zu reden. Erweiterungen umfassen modale und temporale Logik.

Geschichte: Frühe Formen finden sich bei Boole; die formale Behandlung wurde durch Frege, Russell und Whitehead entwickelt; die Aussagenlogik bildet eine Grundlage moderner Logik und Informatik.