💻 computer science

Fully Evaluated Left-Sequential Logics

Dieser Beitrag führt eine Hierarchie vollständig ausgewerteter linkssequentieller Logiken ein, die von Free bis Static FEL reicht, und liefert vollständige Axiomatisierungen für ihre zweiwertigen und dreiwertigen Versionen unter Verwendung von Auswertungsbäumen als semantische Grundlage.

Ursprüngliche Autoren: Alban Ponse, Daan J. C. Staudt

Veröffentlicht 2026-05-14

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Alban Ponse, Daan J. C. Staudt

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

Stellen Sie sich vor, Sie sind ein Koch, der ein komplexes Gericht zubereitet. In der Welt der Computerlogik sind die „Zutaten" Fakten (wahr oder falsch), und die „Rezepte" sind Anweisungen, wie man sie kombiniert. Dieser Artikel stellt eine Familie von Kochstilen vor, die Vollständig Ausgewertete Links-Sequentielle Logiken (FELs) genannt werden.

Die Kernidee ist einfach: Sie müssen jedes einzelne Ingredient in der Reihenfolge von links nach rechts probieren, bevor Sie entscheiden, ob das Gericht fertig ist. Sie können keinen Schritt überspringen und nicht einfach auf halbem Weg aufhören, nur weil die erste Zutat schlecht geschmeckt hat.

Hier ist eine Aufschlüsselung der verschiedenen „Kochstile" (Logiken), die die Autoren mit alltäglichen Analogien erkunden.

1. Die Grundregel: „Links-Sequentiell"

In diesen Logiken ist die Reihenfolge wichtig. Wenn Sie ein Rezept „A dann B" haben, müssen Sie zuerst A probieren.

Der Punkt: Die Autoren verwenden einen speziellen Punkt (wie ∧•), um dies zu zeigen. Es bedeutet: „Probieren Sie zuerst die linke Seite. Sobald das erledigt ist, probieren Sie die rechte Seite."
Der Unterschied: In der normalen Logik (wie einer Standard-Wahrheitstabelle) könnten Sie anhalten, wenn der erste Teil „Falsch" ist, weil das Ganze bereits falsch ist. In diesen Logiken setzen Sie fort. Sie probieren den zweiten Teil trotzdem. Dies wird als „Vollständige Auswertung" bezeichnet.

2. Die vier Ebenen der „Kochstile"

Der Artikel präsentiert eine Hierarchie von vier Logiken, die von der chaotischsten bis zur starrsten reichen. Betrachten Sie sie als verschiedene Grade der Küchenordnung.

Ebene 1: Freie FEL (FFEL) – Der „Chaotische Probierer"

Die Ausstrahlung: Dies ist der grundlegendste, „freie" Stil.
Die Regel: Sie probieren alles in der Reihenfolge. Wenn Sie jedoch dieselbe Zutat zweimal probieren (z. B. A und dann wieder A), könnte das zweite Mal anders schmecken, weil das erste Mal die Küche verändert hat!
Die Analogie: Stellen Sie sich vor, Sie probieren eine Zitrone. Das erste Mal ist sie sauer. Aber wenn Sie sie sofort nach dem Ausdrücken erneut probieren, ist sie vielleicht nur noch eine feuchte Schale. In FFEL sind A und A nicht notwendigerweise gleich, weil das erste A möglicherweise eine „Nebenwirkung" hatte (wie das Ändern der Umgebung).
Hauptmerkmal: Es ist nur dann immun gegen Nebenwirkungen, wenn Sie versprechen, dass sich die Zutaten nicht ändern. Es ist die „schwächste" Logik, da sie die größte Unvorhersehbarkeit zulässt.

Ebene 2: Speichernde FEL (MFEL) – Der „Notizmachende Koch"

Die Ausstrahlung: Dieser Koch ist organisiert.
Die Regel: Wenn Sie eine Zutat probieren (sagen wir, A), schreiben Sie sie in ein Notizbuch. Wenn Sie später im Rezept wieder auf A stoßen, schauen Sie einfach in Ihr Notizbuch. Sie probieren es nicht erneut.
Die Analogie: Stellen Sie sich einen Sicherheitsbeamten vor, der Ausweise kontrolliert. Wenn er Ihren Ausweis am Eingang kontrolliert hat, muss er ihn am Hintereingang nicht erneut prüfen; er erinnert sich an Sie.
Hauptmerkmal: Dies entfernt die „Nebenwirkungen". Sobald ein Atom (Zutat) ausgewertet ist, ist sein Wert für den Rest des Prozesses festgelegt. Dies macht die Logik stärker und vorhersehbarer.

Ebene 3: Bedingte FEL (CℓFEL) – Das „Flexible Team"

Die Ausstrahlung: Dieses Team kann Plätze tauschen.
Die Regel: Es ist wie MFEL (Sie merken sich, was Sie probiert haben), aber jetzt können Sie die Reihenfolge der Zutaten tauschen, wenn sie unterschiedlich sind. A dann B wird genauso behandelt wie B dann A.
Die Analogie: Stellen Sie sich eine Gruppe von Freunden vor, die entscheiden, wo sie essen. Wenn Alice und Bob zwischen Pizza und Sushi entscheiden, ist es egal, wer zuerst spricht; die endgültige Entscheidung ist dieselbe.
Hauptmerkmal: Diese Logik ist äquivalent zu einer berühmten dreiwertigen Logik namens Bochvars Logik. Sie behandelt „undefinierte" Zutaten (wie ein kaputtes Ei), indem sie das ganze Gericht sofort als „kaputt" (undefiniert) behandelt.

Ebene 4: Statische FEL (SFEL) – Der „Strenge Buchhalter"

Die Ausstrahlung: Der starrste, traditionellste Stil.
Die Regel: Dies ist einfach die klassische Aussagenlogik (wie Schulmathematik), aber mit der Regel, dass Sie trotzdem alles in der Reihenfolge probieren.
Die Analogie: Dies ist der „Goldstandard". Wenn ein Rezept besagt: „Wenn das Ei schlecht ist, ist der Kuchen schlecht", stimmt diese Logik zu. Sie absorbiert das ganze Chaos.
Hauptmerkmal: Sie ist so streng, dass sie „undefinierte" Zutaten nicht verarbeiten kann. Wenn Sie versuchen, „Undefiniert" mit „Falsch" zu mischen, bricht die Mathematik zusammen (weil Undefiniert zu Falsch wird, was ein Widerspruch ist).

3. Die „Undefinierte" Zutat (U)

Die Autoren untersuchen auch, was passiert, wenn eine Zutat Undefiniert (U) ist.

In den „Freien" und „Speichernden" Stilen: Wenn Sie eine undefinierte Zutat probieren, stoppt der gesamte Prozess oder wird undefiniert. Es ist wie der Versuch, einen Kuchen mit „Geheimnis-Pulver" zu backen. Das Ergebnis ist ein „Geheimnis-Kuchen".
Die „Absorbierende" Regel: In der stärksten dreiwertigen Version (Bedingte FEL) ist die undefinierte Zutat „absorbierend". Wenn Sie Undefiniert mit irgendetwas mischen, ist das Ergebnis Undefiniert. Es ist wie ein Schwarzes Loch in Ihrem Rezept.

4. Die „Bäume" der Logik

Um zu beweisen, dass ihre Regeln funktionieren, verwenden die Autoren Auswertungsbäume.

Stellen Sie sich einen Stammbaum vor:
- Die Spitze ist die Hauptfrage.
- Die Äste sind die „Linke" (Wahr) und „Rechte" (Falsch) Pfade.
- Die Blätter am Boden sind die endgültigen Antworten (Wahr oder Falsch).
Die Innovation: In diesen Logiken zeigt der Baum den exakten Pfad, den Sie genommen haben. Wenn Sie A und dann B probiert haben, zeigt der Baum diese spezifische Reise. In der „Speichernden" Logik ist der Baum sauberer, weil er nicht zeigt, dass Sie dieselbe Zutat zweimal probiert haben.

Zusammenfassung der Leistung des Artikels

Die Autoren haben diese Kochstile nicht nur beschrieben; sie haben die Regelbücher (Axiome) für jeden einzelnen geschrieben.

Sie definierten genau, wie man Zutaten kombiniert (Gleichungen).
Sie bewiesen, dass diese Regelbücher Vollständig sind (sie decken jedes denkbare Szenario ab) und Unabhängig (keine Regel ist überflüssig; Sie können keine entfernen, ohne das System zu zerstören).
Sie verwendeten Computerwerkzeuge (Prover9 und Mace4), um ihre Mathematik zu überprüfen und sicherzustellen, dass sich kein menschlicher Fehler eingeschlichen hat.

Kurz gesagt: Dieser Artikel kartiert ein Spektrum von Logiksystemen, in denen Sie gezwungen sind, jedes einzelne Ingredient in der Reihenfolge zu probieren. Es beginnt mit einem chaotischen System, in dem Zutaten sich ändern könnten, geht über zu einem System, in dem Sie sich merken, was Sie probiert haben, dann zu einem System, in dem die Reihenfolge keine Rolle spielt, und schließlich zu einem starren System, das sich wie Standardmathematik verhält. Sie liefern die exakten mathematischen Gesetze für jeden Stil.

Technische Zusammenfassung: Vollständig Ausgewertete Linkssequenzielle Logiken

Problemstellung
Dieser Beitrag behandelt die Formalisierung und Axiomatisierung von „Vollständig Ausgewerteten Linkssequenziellen Logiken" (FELs). Im Gegensatz zu Kurzschlusslogiken (SCLs), bei denen die Auswertung anhält, sobald das Ergebnis eines zusammengesetzten Ausdrucks bestimmt ist, schreiben FELs eine Strategie der „vollständigen" oder „strikten" Auswertung vor: Jeder atomare Proposition innerhalb eines Terms wird ausgewertet, unabhängig davon, ob sein Wert für das Endergebnis strikt notwendig ist. Diese Strategie wird durch Programmierkontexte motiviert, in denen garantiert werden muss, dass Nebenwirkungen (z. B. Zustandsänderungen) für alle Atome in einem Ausdruck auftreten. Die Autoren zielen darauf ab, eine Hierarchie solcher Logiken zu definieren, die von der schwächsten (Freie FEL), die immun gegen atomare Nebenwirkungen ist, bis zur stärksten (Statische FEL) reicht, die sich als sequenzielle Version der klassischen Aussagenlogik verhält. Darüber hinaus erweitert der Beitrag diese Logiken auf eine dreiwertige Umgebung, um „Undefiniertheit" ( $U$ ) zu behandeln, ein häufiges Merkmal in Programmierung und Logik (z. B. Division durch Null).

Methodik
Die Autoren verwenden einen semantischen Rahmen, der auf Auswertungsbäumen basiert, einem Konzept, das in ihrer früheren Arbeit [19] eingeführt wurde.

Semantik: Auswertungsbäume sind binäre Bäume, bei denen innere Knoten Atome repräsentieren und Blätter Wahrheitswerte ( $T$ $T$ , $F$ $F$ oder $U$ $U$ ) darstellen. Ein Pfad von der Wurzel zu einem Blatt modelliert eine Auswertungssequenz.
- In der Freien FEL (FFEL) erhält die Baumstruktur strikt die Reihenfolge der Auswertung und erlaubt wiederholtes Auftreten desselben Atoms, was potenzielle Nebenwirkungen modelliert.
- In der Memorisierenden FEL (MFEL) wird die Semantik so verfeinert, dass kein Pfad im Baum mehrere Vorkommen desselben Atoms enthält; die Auswertung eines Atoms wird „memorisiert", wenn es erneut auftritt.
- In der Konditionalen FEL (CℓFEL) integriert die Logik die Kommutativität von Atomen und behandelt effektiv die Reihenfolge unabhängiger Atome als irrelevant.
- In der Statischen FEL (SFEL) kollabiert die Logik zu einer sequenziellen Version der Aussagenlogik, in der Absorptionsgesetze gelten.
Dreiwertige Erweiterung: Für alle Logiken außer SFEL führen die Autoren eine Konstante $U$ (undefiniert) ein. Die Semantik wird auf Bäume mit Blättern in $\{T, F, U\}$ erweitert, wobei $U$ als absorbierendes Element wirkt (z. B. $U \land_r x = U$ ).
Axiomatisierung: Der primäre methodische Beitrag ist die Herleitung vollständiger equationaler Axiomatisierungen für jede Logik. Die Autoren definieren Normalformen (z. B. FEL-Normalform, $\sigma$ -Normalformen), um die Vollständigkeit zu beweisen. Sie nutzen den Theorembeweiser Prover9, um Ableitbarkeiten zu verifizieren, und Mace4, um endliche Gegenmodelle zu generieren und die Unabhängigkeit der Axiome zu beweisen.

Hauptbeiträge und Ergebnisse

Hierarchie zweiwertiger FELs:
- Freie FEL (FFEL): Die schwächste Logik, axiomatisiert durch die Menge $EqFFEL$. Sie widerlegt Idempotenz ( $x \land_r x \neq x$ ), erfüllt jedoch Assoziativität. Sie ist die Logik der vollständigen Auswertung ohne Nebenwirkungsbeschränkungen.
- Memorisierende FEL (MFEL): Axiomatisiert durch Hinzufügen eines Axioms zu FFEL (speziell $(x \lor_r y) \land_r z = (\neg x \land_r (y \land_r z)) \lor_r (x \land_r z)$ ). Sie erzwingt, dass wiederholte Atome als identisch behandelt werden, wodurch Nebenwirkungen eliminiert werden.
- Konditionale FEL (CℓFEL $_2$ ): Axiomatisiert durch Hinzufügen der Kommutativität ( $x \land_r y = y \land_r x$ ) zu MFEL. Diese Logik ist äquivalent zur zweiwertigen Sublogik der Konditionalen Logik (Guzmán und Squier [12]).
- Statische FEL (SFEL): Die stärkste Logik, erhalten durch Hinzufügen von $x \land_r F = F$ zu CℓFEL $_2$ . Sie ist äquivalent zur Statischen Kurzschlusslogik (SSCL) und zur Standard-Aussagenlogik unter sequenzieller Auswertung.
Dreiwertige Erweiterungen (FELU):
- Die Autoren definieren dreiwertige Versionen (FFELU, MFELU, CℓFEL) durch Hinzufügen der Axiome $\neg U = U$ und $U \land_r x = U$ .
- CℓFEL (die dreiwertige Konditionale FEL) wird als äquivalent zur strengen Logik von Bochvar [8] bewiesen.
- SFEL kann nicht mit $U$ erweitert werden, da das Absorptionsgesetz $F = U \land_r F = U$ zu einem Kollaps der Wahrheitswerte führt.
Vollständigkeit und Unabhängigkeit:
- Vollständige equationale Axiomatisierungen werden für alle definierten Logiken bereitgestellt.
- Die Autoren präsentieren alternative, prägnantere Mengen unabhängiger Axiome für jede Logik (z. B. die Menge $MF$ für MFEL), die mit automatisierten Werkzeugen verifiziert wurden.
- Normalformen werden konstruiert, um zu beweisen, dass syntaktische Gleichheit von Normalformen semantischer Gleichheit von Auswertungsbäumen entspricht.

Bedeutung und Behauptungen
Der Beitrag behauptet, einen einheitlichen Rahmen zum Verständnis der vollständigen linkssequenziellen Auswertung zu liefern und die Lücke zwischen Kurzschlusslogiken und klassischer Aussagenlogik zu schließen.

Vorhersagbarkeit: Die Autoren argumentieren, dass FELs im Vergleich zu SCLs eine größere Vorhersagbarkeit bezüglich des Zustands der Umgebung (Nebenwirkungen) nach der Auswertung bieten, da garantiert wird, dass alle Atome ausgewertet werden.
Ausdrucksstärke: Der Beitrag zeigt, dass FFEL bestimmte einheitliche Auswertungsbäume nicht ausdrücken kann (z. B. Bäume, bei denen ein Atom in verschiedenen Ästen mit unterschiedlichen Ergebnissen erscheint), MFEL und stärkere Logiken dies jedoch können, wodurch die Ausdruckskraft der Logik erhöht wird.
Beziehung zu bestehender Arbeit: Die Arbeit positioniert CℓFEL innerhalb der Logik-Hierarchie und zeigt, dass sie der Logik von Bochvar und einer Sublogik der Konditionalen Logik äquivalent ist. Sie klärt zudem die Beziehung zwischen FELs und Kurzschlusslogiken (SCLs) und stellt fest, dass FEL-Verknüpfungen innerhalb von SCL-Rahmenwerken definiert werden können (und umgekehrt unter spezifischen Bedingungen), obwohl FELs eine striktere Auswertungsdisziplin erzwingen.

Der Beitrag schließt mit der Feststellung, dass diese Logiken eine robuste theoretische Grundlage für die Reasoning über Ausdrücke bieten, bei denen eine vollständige Auswertung erforderlich ist, und vollständige sowie unabhängige Axiomatisierungen liefern, die automatisches Reasoning und Verifikation erleichtern.