Aussagenlogik (auch Aussagenkalkül) ist der einfachste Zweig der formalen Logik. Sie untersucht Aussagen – Sätze, die eindeutig wahr oder falsch sein können – und wie man sie durch Junktoren zu komplexen Formeln verknüpft. Sie ist die Grundlage fast aller digitalen Systeme: von Schaltkreisen über Programmverifikation bis zur Künstlichen Intelligenz.
Aussagen und Wahrheitswerte
Eine atomare Aussage ist ein einfacher Behauptungssatz wie „Es regnet" oder „n ist gerade". Jede Aussage hat genau einen Wahrheitswert: wahr oder falsch. Aus atomaren Aussagen baut man mit Junktoren zusammengesetzte Formeln, deren Wahrheitswert sich systematisch aus den Teilwerten ergibt.
Die wichtigsten Junktoren
- Negation (NICHT, ¬): kehrt den Wahrheitswert um.
- Konjunktion (UND, ∧): wahr nur, wenn beide Teilaussagen wahr sind.
- Disjunktion (ODER, ∨): wahr, wenn mindestens eine Teilaussage wahr ist.
- Implikation (→): „wenn A, dann B" – falsch nur, wenn A wahr und B falsch ist.
- Äquivalenz (↔): wahr, wenn beide Teilaussagen denselben Wahrheitswert haben.
Wahrheitstafeln und Typen von Formeln
Eine Wahrheitstafel listet für jede mögliche Belegung der Variablen den Wert der Formel auf. Danach klassifiziert man Formeln: Eine Tautologie ist unter jeder Belegung wahr (z.B. A ∨ ¬A), eine Kontradiktion nie wahr (A ∧ ¬A). Eine Formel heißt erfüllbar, wenn es mindestens eine Belegung gibt, unter der sie wahr wird – genau diese Frage stellt das Satisfiability-Problem (SAT).
Normalformen
Jede aussagenlogische Formel lässt sich äquivalent in Normalformen umformen: die disjunktive Normalform (DNF, ODER von UND-Termen) und die konjunktive Normalform (KNF, UND von ODER-Klauseln). Die KNF ist praktisch besonders wichtig, weil SAT-Solver Formeln in KNF verarbeiten.
Bedeutung für die Informatik
Die Aussagenlogik steckt in digitalen Schaltungen, in Datenbank-Abfragesprachen und in regelbasierten Systemen. Das Erfüllbarkeitsproblem der Aussagenlogik war das erste nachgewiesene NP-vollständige Problem; praktische Solver lösen es heute trotzdem für riesige Formeln. Ob dafür ein schneller allgemeiner Algorithmus existieren kann, ist die offene P-vs-NP-Frage. Verwandte Grundlagen: Algorithmus, Backtracking (Basis der DPLL-Solver) und die Reduktion als Werkzeug der Komplexitätstheorie.