💻 computer science

The TPTP Format for Interpretations

Dieses Papier führt das TPTP-Format zur Darstellung tarskischer, Herbrand- und Kripke-Interpretationen ein und beschreibt es im Detail, wobei es dessen Syntax, Semantik, Verifizierung und Tool-Unterstützung abdeckt, um die Angemessenheit für verschiedene Anwendungen sicherzustellen.

Ursprüngliche Autoren: Geoff Sutcliffe, Alexander Steen, Pascal Fontaine, Lydia Kondylidou

Veröffentlicht 2026-06-02

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Geoff Sutcliffe, Alexander Steen, Pascal Fontaine, Lydia Kondylidou

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Das „Was wäre wenn“-Szenario finden

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, ein Rätsel zu lösen. Sie haben einen Satz von Regeln (Axiome) und eine Theorie (eine Vermutung) darüber, was passiert ist. Normalerweise ist es Ihre Aufgabe zu beweisen, dass die Theorie basierend auf den Regeln wahr sein muss.

Aber manchmal wollen Sie beweisen, dass die Theorie falsch ist. Um das zu tun, müssen Sie ein spezifisches Szenario finden – ein „Gegenbeispiel“ –, in dem die Regeln zwar gelten, aber Ihre Theorie jedoch zusammenbricht. In der Welt der Computerlogik wird dieses Szenario als Interpretation oder Modell bezeichnet.

Lange Zeit konnten Computer diese „falschen“ Szenarien zwar finden, behielten die Ergebnisse aber für sich. Sie sagten lediglich: „Ich habe ein Gegenbeispiel gefunden!“, ohne Ihnen jedoch zu zeigen, wie es aussah. Das war so, als würde ein Detektiv sagen: „Der Butler war es nicht“, aber sich weigern zu zeigen, wo sein Alibi liegt.

Dieses Paper führt eine neue, standardisierte Methode ein, mit der Computer diese Szenarien aufschreiben können, damit Menschen und andere Computer sie lesen, prüfen und verstehen können. Es ist wie die Erstellung eines universellen „Bauplans“ für diese alternativen Realitäten.

Die drei Arten von Bauplänen

Das Paper erklärt, dass es drei Hauptwege gibt, um diese Szenarien zu konstruieren, und das neue Format deckt alle drei ab:

1. Die endliche Welt (Tarskische Interpretationen)
Stellen Sie sich einen kleinen, geschlossenen Raum mit einer bestimmten Anzahl von Personen und Objekten vor.

Die Analogie: Denken Sie an ein Brettspiel wie Cluedo. Sie haben einen festen Satz an Charakteren (Colonel Mustard, Mrs. Peacock), einen festen Satz an Räumen und einen festen Satz an Waffen.
Das Format: Der Computer schreibt eine Liste: „In dieser Welt gibt es genau 4 Personen. Colonel Mustard ist in der Bibliothek. Der Kerzenständer ist in der Küche.“ Er listet jede einzelne Verbindung explizit auf.
Warum es wichtig ist: Dies ist ideal, um zu prüfen, ob ein System mit einer kleinen, überschaubaren Anzahl von Elementen funktioniert.

2. Die unendliche Welt (Unendliche Interpretationen)
Stellen Sie sich nun eine Welt vor, die niemals endet, wie die Zahlengerade (1, 2, 3, 4... für immer).

Die Analogy: Man kann keine unendliche Liste von Zahlen aufschreiben. Stattdessen schreibt man ein Rezept oder eine Regel: „Beginne bei Null. Um die nächste Zahl zu erhalten, addiere eins.“
Das Format: Der Computer listet nicht jede Zahl auf. Stattdessen schreibt er eine Regel wie: „Für jede Zahl $X$ ist die nächste Person $X+1$ .“ Er verwendet mathematische Formeln, um die unendliche Menge zu beschreiben.
Warum es wichtig ist: Dies ist notwendig, wenn man mit Dingen wie Zeit, Geld oder Daten arbeitet, die ohne Limit wachsen können.

3. Das Multiversum (Kripke-Interpretationen)
Manchmal ändern sich die Regeln, je nachdem, wo man sich befindet oder wann man nachsieht.

Die Analogy: Denken Sie an ein „Du entscheidest selbst“-Buch oder einen Multiversum-Film. In einem Raum (Welt A) regnet es. Im nächsten Raum (Welt B) scheint die Sonne. Die Charaktere können in jedem Raum unterschiedlich sein oder dieselben bleiben. Es gibt Türen, die diese Räume verbinden (Erreichbarkeit).
Das Format: Der Computer schreibt eine Karte aller Räume, welche Türen offen stehen und wie das Wetter in jedem Raum ist. Er sagt: „In Welt 1 regnet es. In Welt 2 scheint die Sonne. Man kann von Welt 1 nach Welt 2 gehen, aber nicht zurück.“
Warum es wichtig ist: Dies ist entscheidend für Dinge wie Sicherheitsprotokolle oder KI-Schlussfolgerungen, bei denen die Wahrheit vom Kontext abhängt.

Das „Rezept“ für das Format

Das Paper beschreibt detailliert, wie man diese Baupläne unter Verwendung einer spezifischen Sprache namens TPTP erstellt. Betrachten Sie TPTP als eine universelle Programmiersprache für Logik.

Die Zutaten: Das Format erfordert die Definition des „Domain“ (wer ist im Raum), der „Mappings“ (wer macht was) und der „Regeln“ (was ist wahr oder falsch).
Die Flexibilität: Das Format ist intelligent. Es kann grobkörnig sein (ein großer, unstrukturierter Textabschnitt, der die ganze Welt beschreibt) oder feinkörnig (eine detaillierte Tabelle, die jede einzelne Person und jedes Objekt aufschlüsselt).
Der „Herbrand“-Spezialfall: Manchmal besteht die „Welt“ nur aus einer Liste von Wörtern und Sätzen, die der Computer selbst generiert hat. Das Paper nennt dies „Herbrand-Interpretationen“. Es ist wie ein Wörterbuch, in dem die Definitionen vollständig aus den Wörtern des Wörterbuchs selbst aufgebaut sind.

Warum brauchen wir das? (Das „Vertrau mir“-Problem)

Das Paper argumentiert, dass es nicht ausreicht, eine Lösung nur zu finden; wir müssen sie auch verifizieren.

Der alte Weg: Ein Computer sagt: „Ich habe einen Fehler gefunden!“ Sie müssen dem Computer vertrauen. Wenn der Computer einen Fehler gemacht hat, sitzen Sie fest.
Der neue Weg: Der Computer überreicht Ihnen den Bauplan (die Interpretation). Sie (oder ein anderer Computer) können den Bauplan lesen und die Mathematik überprüfen.
- Können Sie es lesen? Ja, das Format ist so konzipiert, dass es für Menschen lesbar ist.
- Können Sie es prüfen? Ja, Sie können einen einfachen Test durchführen, um zu sehen, ob der Bauplan tatsächlich die Regeln erfüllt.
- Ist es nützlich? Ja, denn wenn Sie einen Fehler finden, zeigt Ihnen der Bauplan genau, wo der Fehler liegt (z. B. „John ist in der Küche, aber die Regeln besagen, dass er in der Bibliothek sein sollte“).

Das „Werkzeugset“

Das Paper erwähnt, dass bereits Werkzeuge existieren, die dabei helfen:

Visualisierer: Stellen Sie sich eine 3D-Karte vor, bei der Sie auf eine „Welt“ klicken können, um die darin befindlichen Charaktere zu sehen. Das Paper erwähnt ein Tool namens „Interactive Interpretation Viewer“ (IIV), das genau dies für endliche Welten tut.
Verifizierer: Werkzeuge, die den Bauplan und die ursprünglichen Regeln nehmen und automatisch prüfen, ob diese übereinstimmen.

Zusammenfassung

Kurz gesagt geht es in diesem Paper darum, die Art und Weise zu standardisieren, wie Computer ihre „Was wäre wenn“-Szenarien teilen.

Früher fanden Computer Gegenbeispiele, hielten sie aber in einer Blackbox verborgen. Jetzt können sie sie in einer klaren, standardisierten „Bauplan“-Sprache aufschreiben. Dies ermöglicht es Menschen, den Bauplan zu betrachten, zu verstehen, warum ein System fehlgeschlagen ist, und zu verifizieren, dass der Computer keinen Fehler gemacht hat. Es verwandelt einen „Vertrau mir“-Moment in einen „Zeig es mir“-Moment.

Technische Zusammenfassung: Das TPTP-Format für Interpretationen

Problemstellung
Die automatisierte Theorembeweisung (Automated Theorem Proving, ATP) hat sich historisch auf die Ableitung von Theoremen aus Axiomen konzentriert. Das Widerlegen von Vermutungen durch das Finden von Gegenmodellen (Interpretationen, die Axiome erfüllen, aber die Vermutung falsifizieren) ist jedoch ein entscheidender Aspekt der ATP und essenziell für Anwendungen wie die formale Verifikation, Konsistenzprüfung und Operationsforschung. Während die TPTP-Welt schon lange ein Format für endliche Tarskische Interpretationen unterstützt, war das bestehende Format unzureichend für:

Die Darstellung von Interpretationen mit unendlichen Domänen.
Die Darstellung von Kripke-Interpretationen (verwendet in nicht-klassischen Logiken wie der Modallogik).
Die Bereitstellung einer vereinheitlichten, standardisierten Darstellung für Herbrand-Interpretationen und Sättigungen.

Das Fehlen einer standardisierten Darstellung für diese vielfältigen Interpretationstypen behindert die Fähigkeit, Modelle zu verifizieren, Gegenbeispiele zu analysieren und die Modellfindung in breitere Reasoning-Pipelines zu integrieren.

Methodik
Die Autoren haben ein neues TPTP-Format für Interpretationen entwickelt, das auf dem Prinzip basiert, dass Interpretationen als Formeln dargestellt werden sollten, die in der TPTP-Sprache selbst geschrieben sind. Dieser Ansatz nutzt die bestehende TPTP-Syntax (unterstützt CNF, FOF, TFF, THF usw.) und die annotierte Formelstruktur sprache(name, rolle, formel, quelle, nützliche_info).

Die Methodologie umfasst:

Definition der interpretation-Rolle: Eine neue Formelrolle wird eingeführt, um Interpretations-Formeln von Problem-Axiomen oder Vermutungen zu unterscheiden.
Strukturierung Tarskscher Interpretationen: Das Format definiert Interpretationen als Konjunktionen von Domänenspezifikationen und Symbolabbildungen.
- Endliche Domänen: Spezifiziert über universell quantifizierte Disjunktionen von Gleichheiten (Aufzählung von Elementen) und Unterschiedsbeschränkungen (unter Verwendung von $distinct oder doppelt angeführten Termen).
- Unendliche Domänen: Spezifiziert über Existenzquantifizierung, um unendliche Disjunktionen zu erfassen (z. B. Peano-Zahlen) oder durch definierte Typen (z. B. $int).
- Typ-Handhabung: Für typisierte Logiken (TFF, THF) verwendet das Format „Typ-Promotions-Bijektionen“, um Domänenelemente (die unterschiedliche interne Typen haben können) auf die Typen des Problems abzubilden, um Typisierungssicherheit zu gewährleisten.
- Herbrand-Interpretationen: Dargestellt unter Verwendung von interpretation-herbrand-Subrollen, oft unter Nutzung von Prädikatdefinitionen über Term-Algebren oder Sättigungen.
Strukturierung von Kripke-Interpretationen: Das Format erweitert die Tarskische Interpretation durch das Hinzufügen einer Ebene von „Welten“. Es führt definierte Symbole ein: $world (Typ), $accessible_world` (Relation), `$ local_world (Konstante) und $in_world (Prädikat). Eine Kripke-Interpretation ist eine Konjunktion, die die Menge der Welten, die Erreichbarkeitsrelation und die Tarskische Interpretation innerhalb jeder Welt spezifiziert.
Granularität und Modularität: Das Format unterstützt die Aufteilung von Interpretationen in mehrere Formeln mittels Subrollen (z. B. interpretation-domains, interpretation-mappings) auf mittlerer und feiner Granularität, um Zuständigkeiten zu trennen oder kompakte Darstellungen durch Quantifizierung zu ermöglichen.
Verifikation: Die Autoren skizzieren eine Verifikationsmethodik, bei der die Interpretations-Formeln als Axiome behandelt werden und die ursprünglichen Problem-Formeln als Vermutungen (oder negierte Vermutungen). Wenn die Problem-Formeln aus den Interpretations-Formeln bewiesen werden können, ist die Interpretation als gültiges Modell verifiziert.

Wesentliche Beiträge

Vereinheitlichte Syntax: Ein einziges, erweiterbares TPTP-Format, das in der Lage ist, Tarskische (endliche und unendliche), Herbrand- und Kripke-Interpretationen darzustellen.
Unterstützung unendlicher Domänen: Mechanismen zur Darstellung unendlicher Domänen unter Verwendung von Term-Algebren (z. B. Peano-Zahlen) oder eingebauten Typen (z. B. Ganzzahlen), wodurch die bisherige Beschränkung auf endliche Modelle überwunden wird.
Kripke-Modell-Repräsentation: Eine formale Spezifikation zur Darstellung von Modallogik-Gegenmodellen, einschließlich Weltstrukturen und Erreichbarkeitsrelationen, innerhalb des TPTP-Frameworks.
Verifikations-Framework: Eine konkrete Methode zur Verifikation von Modellen durch Reduktion der Aufgabe auf Theorembeweisung, wodurch sichergestellt wird, dass die Ausgabe eines Modellfinders nicht bloß vertrauenswürdig, sondern verifizierbar ist.
Tooling und Visualisierung: Identifikation von Werkzeugen, die das Format unterstützen, einschließlich des AGMV-Modellverifiers und des Interactive Interpretation Viewer (IIV), der die Visualisierung endlicher Tarskischer und Kripke-Modelle ermöglicht.

Ergebnisse und Fähigkeiten
Das Paper präsentiert keine neuen experimentellen Daten oder Benchmarks, sondern definiert die Spezifikation und demonstriert deren Nutzen durch zahlreiche Beispiele (bereitgestellt in den Anhängen). Diese Beispiele illustrieren:

Die Darstellung endlicher Gegenmodelle für untypisierte (FOF) und typisierte (TFF, THF) Probleme.
Die Darstellung unendlicher Modelle sowohl unter Verwendung von Term-Domänen als auch definierter Typen.
Die Darstellung von Kripke-Modellen für nicht-klassische Logiken (NXF).
Die Fähigkeit, diese Darstellungen für bessere Lesbarkeit und Modularität aufzuspalten und zu komprimieren.
Die erfolgreiche Konstruktion von Verifikationsproblemen, die durch vertrauenswürdige ATP-Systeme entlastet werden können.

Bedeutung und Ansprüche
Die Autoren behaupten, dass diese Arbeit sicherstellt, dass das TPTP-Repräsentationsformat den vielfältigen Bedürfnissen der ATP-Community gerecht wird. Die Bedeutung liegt im Übergang vom „Black Box“-Modellfinden hin zu einer transparenten, verifizierbaren und analysierbaren Modellrepräsentation.

Das Paper beansprucht bescheiden, dass das Format die notwendigen Eigenschaften für die Interpretation darstellt:

Auswertbarkeit: Formeln können in Bezug auf die Interpretation ausgewertet werden.
Traktabilität: Die Auswertung ist für endliche Interpretationen handhabbar; unendliche Interpretationen können intransitiv sein, sind aber repräsentierbar.
Verifizierbarkeit: Modelle können verifiziert werden, indem geprüft wird, ob die Problem-Formeln aus den Interpretations-Formeln folgen.
Verständlichkeit: Das Format ist darauf ausgelegt, menschenlesbar zu sein, obwohl die Autoren anmerken, dass komplexe Repräsentationen (wie Sättigungen oder unendliche Domänen) für Menschen weiterhin schwierig zu erfassen sein können.

Die Arbeit dient als Fundament für ATP-Systeme, um reichere, vielfältigere Modelle auszugeben, was ein besseres Debugging in der Verifikation und eine tiefere Analyse in der Logikforschung erleichtert. Die Autoren merken an, dass das Format derzeit implementiert wird, mit Plänen, es zukünftig auf weitere nicht-klassische Sprachen auszuweiten.