Ein auf Widerlegung basierendes Beweisverfahren, das logische Formeln in einen Baum einfacher Komponenten (ein Tableau oder Truth-Tree) zerlegt, um Erfüllbarkeit zu prüfen; ein geschlossenes Tableau (alle Äste widersprüchlich) zeigt die Unerfüllbarkeit der Wurzelformel.

Prinzip

Systematische Anwendung von Zerlegungsregeln, die die semantischen Bedingungen der Verknüpfungen und Quantoren widerspiegeln, wobei Äste erweitert werden, bis sie sich durch Widerspruch schließen oder offen als Erfüllungszeugnis verbleiben.

Demonstration

Um ¬(A ∧ B) zu prüfen, setzt man dessen Negation an die Wurzel, wendet Negations- und Konjunktionszerlegung an und erzeugt Äste; wenn jeder Ast eine Formel und deren Negation enthält, schließt das Tableau und zeigt die Gültigkeit der Ausgangsaussage.

Fehlanwendung

Zu frühes Abbrechen der Erweiterung, falsche Anwendung von Verzweigungsregeln oder fehlerhafte Instanziation von Quantoren (besonders Universalen) kann offene Äste hinterlassen, die fälschlich Erfüllbarkeit suggerieren, oder unzulässige Schließungen erzeugen.

Konsequenz

Richtig ausgeführt liefern Tableaus aus offenen Ästen Gegenmodelle und aus geschlossenen Tableaus kompakte Widerlegungen, was sie praktisch für automatisches Schließen und zur Extraktion diagnostischer Gegenbeispiele macht.

Umkehrung

Die Umkehr ist ein System, das syntaktische Herleitungen (z. B. Hilbert oder natürliche Deduktion) aufbaut, statt semantische Gegenmodelle zu suchen; Tableaus betonen die Modellsuche gegenüber syntaktischer Herleitung.

Abgrenzung

Am besten für Aussagenlogik und Prädikatenlogik ersten Grades; für erste Stufe-Tableaus sind Strategien mit freien Variablen oder Skolemisierung nötig, um Zeugen darzustellen, und ohne Schranken kann die Suche nicht terminieren.

Semantische Spannung

Spannung besteht gegenüber Resolution und axiomatischen Kalkülen: Tableaus sind modellorientiert und erzeugen tendenziell Gegenmodelle, während Resolution auf Klauselwiderlegung durch Unifikation und Erzeugung von Resolventen fokussiert.

Synthese

Semantische Tableaux sind eine baumbasierte Entscheidungs- und Suchmethode, die Formeln durch semantische Regeln zerlegt; die Schließungsmuster der Äste entscheiden über Erfüllbarkeit und liefern explizite Gegenmodelle oder Widerlegungen.