💻 computer science

Fully Evaluated Left-Sequential Logics

Dit artikel introduceert een hiërarchie van volledig geëvalueerde links-sequentiële logica's die varieert van Free tot Static FEL, en biedt volledige axiomatiseringen voor hun twee- en drie-waardige versies met evaluatiebomen als semantische grondslag.

Oorspronkelijke auteurs: Alban Ponse, Daan J. C. Staudt

Gepubliceerd 2026-05-14

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Alban Ponse, Daan J. C. Staudt

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een chef bent die een complex gerecht bereidt. In de wereld van computerlogica zijn de "ingrediënten" feiten (waar of onwaar), en de "recepten" zijn instructies over hoe ze te combineren. Dit artikel introduceert een familie van kookstijlen genaamd Volledig Geëvalueerde Links-Sequentiële Logica's (FEL's).

Het kernidee is eenvoudig: Je moet elk ingrediënt één voor één, van links naar rechts, proeven voordat je besluit of het gerecht klaar is. Je kunt geen stap overslaan en je kunt niet halverwege stoppen alleen maar omdat het eerste ingrediënt slecht smaakte.

Hier volgt een uiteenzetting van de verschillende "kookstijlen" (logica's) die de auteurs verkennen, met behulp van alledaagse analogieën.

1. De Basisregel: "Links-Sequentieel"

In deze logica's is de volgorde belangrijk. Als je een recept hebt A dan B, moet je eerst A proeven.

De Punt: De auteurs gebruiken een speciale punt (zoals ∧•) om dit aan te geven. Het betekent "Proef eerst de linkerkant. Zodra dat klaar is, proef de rechterkant."
Het Verschil: In normale logica (zoals een standaard waarheidstabel) stop je misschien bij het eerste deel als dat "Onwaar" is, omdat het geheel dan al onwaar is. In deze logica's ga je door. Je proeft het tweede deel toch. Dit heet "Volledige Evaluatie".

2. De Vier Niveaus van "Kookstijlen"

Het artikel presenteert een hiërarchie van vier logica's, variërend van de meest chaotische tot de meest rigide. Denk aan hen als verschillende niveaus van keuken-discipline.

Niveau 1: Vrije FEL (FFEL) – De "Chaotische Proever"

De Sfeer: Dit is de meest basale, "vrije" stijl.
De Regel: Je proeft alles in volgorde. Echter, als je hetzelfde ingrediënt twee keer proeft (bijvoorbeeld A en dan weer A), kan de tweede keer anders smaken omdat de eerste keer de keuken heeft veranderd!
De Analogie: Stel je voor dat je een citroen proeft. De eerste keer is het zuur. Maar als je het direct na het persen opnieuw proeft, is het misschien nu alleen maar een nat schil. In FFEL zijn A en A niet noodzakelijk hetzelfde, omdat de eerste A een "bijwerking" kan hebben gehad (zoals het veranderen van de omgeving).
Kernkenmerk: Het is immuun voor bijwerkingen alleen als je belooft dat de ingrediënten niet veranderen. Het is de "zwakste" logica omdat het de meeste onvoorspelbaarheid toelaat.

Niveau 2: Memoriserende FEL (MFEL) – De "Note-Takende Chef"

De Sfeer: Deze chef is georganiseerd.
De Regel: Als je een ingrediënt proeft (zeg A), schrijf je het op in een notitieboekje. Als je later in het recept weer A tegenkomt, kijk je gewoon in je notitieboekje. Je proeft het niet opnieuw.
De Analogie: Stel je een beveiligingsagent voor die ID's controleert. Als hij je ID bij de ingang controleert, hoeft hij het niet opnieuw te controleren bij de achteruitgang; hij herinnert zich je.
Kernkenmerk: Dit verwijdert de "bijwerkingen". Zodra een atoom (ingrediënt) is geëvalueerd, is zijn waarde vastgesteld voor de rest van het proces. Dit maakt de logica sterker en voorspelbaarder.

Niveau 3: Conditionele FEL (CℓFEL) – Het "Flexibele Team"

De Sfeer: Dit team kan van plaats wisselen.
De Regel: Het is zoals MFEL (je onthoudt wat je hebt geproefd), maar nu kun je de volgorde van ingrediënten verwisselen als ze verschillend zijn. A dan B wordt hetzelfde behandeld als B dan A.
De Analogie: Stel je een groep vrienden voor die beslissen waar ze gaan eten. Als Alice en Bob kiezen tussen Pizza en Sushi, maakt het niet uit wie er eerst spreekt; de uiteindelijke beslissing is hetzelfde.
Kernkenmerk: Deze logica is equivalent aan een beroemde 3-waardige logica genaamd Bochvar's Logica. Het behandelt "ongedefinieerde" ingrediënten (zoals een gebroken ei) door het hele gerecht direct als "gebroken" (ongedefinieerd) te behandelen.

Niveau 4: Statische FEL (SFEL) – De "Strenge Boekhouder"

De Sfeer: De meest rigide, traditionele stijl.
De Regel: Dit is gewoon standaard propositielogica (zoals middelbare school wiskunde), maar met de regel dat je toch alles in volgorde proeft.
De Analogie: Dit is de "Gouden Standaard". Als je een recept hebt dat zegt "Als het ei slecht is, is de taart slecht", gaat deze logica hiermee akkoord. Het absorbeert al het chaos.
Kernkenmerk: Het is zo streng dat het geen "ongedefinieerde" ingrediënten aankan. Als je probeert "ongedefinieerd" te mengen met "onwaar", breekt de wiskunde (omdat Ongedefinieerd Onwaar wordt, wat een contradictie is).

3. Het "Ongedefinieerde" Ingrediënt (U)

De auteurs verkennen ook wat er gebeurt als een ingrediënt Ongedefinieerd (U) is.

In de "Vrije" en "Memoriserende" stijlen: Als je een ongedefinieerd ingrediënt proeft, stopt het hele proces of wordt het ongedefinieerd. Het is als proberen een taart te bakken met "mysteriepoeder". Het resultaat is "mysterytaart".
De "Absorberende" Regel: In de sterkste 3-waardige versie (Conditionele FEL) is het ongedefinieerde ingrediënt "absorberend". Als je Ongedefinieerd mengt met iets anders, is het resultaat Ongedefinieerd. Het is als een zwart gat in je recept.

4. De "Bomen" van Logica

Om te bewijzen dat hun regels werken, gebruiken de auteurs Evaluatiebomen.

Stel je een Stamboom voor:
- De top is de hoofdvraag.
- De takken zijn de "Linker" (Waar) en "Rechter" (Onwaar) paden.
- De bladeren onderaan zijn de uiteindelijke antwoorden (Waar of Onwaar).
De Innovatie: In deze logica's toont de boom het exacte pad dat je hebt bewandeld. Als je A proefde en dan B, toont de boom die specifieke reis. In "Memoriserende" logica is de boom schoner omdat het niet laat zien dat je hetzelfde ingrediënt twee keer proeft.

Samenvatting van de Prestatie van het Artikel

De auteurs hebben niet alleen deze kookstijlen beschreven; ze hebben de Regelboeken (Axioma's) voor elk van hen geschreven.

Ze hebben precies gedefinieerd hoe ingrediënten te combineren (vergelijkingen).
Ze hebben bewezen dat deze regelboeken Compleet zijn (ze dekken elk mogelijk scenario) en Onafhankelijk (geen enkele regel is overbodig; je kunt er geen verwijderen zonder het systeem te breken).
Ze hebben computertools (Prover9 en Mace4) gebruikt om hun wiskunde te controleren, zodat er geen menselijke fouten in sluipen.

In het kort: Dit artikel schetst een spectrum van logische systemen waarbij je gedwongen wordt om elk ingrediënt in volgorde te proeven. Het begint met een chaotisch systeem waarin ingrediënten kunnen veranderen, gaat over naar een systeem waarin je onthoudt wat je hebt geproefd, vervolgens naar een systeem waarin de volgorde er niet toe doet, en eindigt bij een rigide systeem dat zich gedraagt als standaard wiskunde. Ze leveren de exacte wiskundige wetten voor elke stijl.

Technische Samenvatting: Volledig Geëvalueerde Links-Sequential Logica's

Probleemstelling
Dit artikel behandelt de formalisering en axiomatisatie van "Volledig Geëvalueerde Links-Sequential Logica's" (VGSL's). In tegenstelling tot short-circuit logica's (SCL's), waarbij evaluatie stopt zodra het resultaat van een samengesteld expressie is bepaald, schrijven VGSL's een strategie van "volledige" of "strikte" evaluatie voor: elke atomaire propositie binnen een term wordt geëvalueerd, ongeacht of haar waarde strikt noodzakelijk is voor het eindresultaat. Deze strategie wordt gemotiveerd door programmeercontexten waar bijwerkingen (bijv. staatwijzigingen) gegarandeerd moeten plaatsvinden voor alle atomen in een expressie. De auteurs beogen een hiërarchie van dergelijke logica's te definiëren, variërend van de zwakste (Vrije VGSL), die immuun is voor atomaire bijwerkingen, tot de sterkste (Statische VGSL), die fungeert als een sequentiële versie van de klassieke propositielogica. Bovendien breiden de auteurs deze logica's uit naar een drie-waardige setting om "ongedefinieerdheid" ( $U$ ) te hanteren, een veelvoorkomend kenmerk in programmering en logica (bijv. deling door nul).

Methodologie
De auteurs maken gebruik van een semantisch raamwerk gebaseerd op evaluatiebomen, een concept dat in hun eerdere werk [19] is geïntroduceerd.

Semantiek: Evaluatiebomen zijn binaire bomen waarbij interne knopen atomen vertegenwoordigen en bladeren waarheidswaarden ( $T$ $T$ , $F$ $F$ , of $U$ $U$ ). Een pad van wortel tot blad modelleert een evaluatiesequentie.
- In Vrije VGSL (VVGSL) behoudt de boomstructuur strikt de volgorde van evaluatie en staat herhaalde voorkomens van hetzelfde atoom toe, waarmee potentiële bijwerkingen worden gemodelleerd.
- In Memoriserende VGSL (MVGSL) worden de semantiek verfijnd zodat geen enkel pad in de boom meerdere voorkomens van hetzelfde atoom bevat; de evaluatie van een atoom wordt "gememoriseerd" indien het opnieuw wordt aangetroffen.
- In Conditionele VGSL (CℓVGSL) wordt de commutativiteit van atomen opgenomen in de logica, waardoor de volgorde van onafhankelijke atomen effectief als irrelevant wordt behandeld.
- In Statische VGSL (SVGL) stort de logica in tot een sequentiële versie van propositielogica waar absorptiewetten gelden.
Drie-waardige Uitbreiding: Voor alle logica's behalve SVGL introduceren de auteurs een constante $U$ (ongedefinieerd). De semantiek wordt uitgebreid tot bomen met bladeren in $\{T, F, U\}$ , waarbij $U$ fungeert als een absorberend element (bijv. $U \land_r x = U$ ).
Axiomatisatie: De primaire methodologische bijdrage is de afleiding van volledige equationale axiomatisaties voor elke logica. De auteurs definiëren normaalvormen (bijv. VGSL Normaalvorm, $\sigma$ -normaalvormen) om volledigheid te bewijzen. Zij maken gebruik van het theoremabewijzer Prover9 om afleidbaarheden te verifiëren en Mace4 om eindige tegenvoorbeelden te genereren om de onafhankelijkheid van axioma's te bewijzen.

Belangrijkste Bijdragen en Resultaten

Hiërarchie van Twee-waardige VGSL's:
- Vrije VGSL (VVGSL): De zwakste logica, geaxiomatiseerd door de verzameling $EqVVGSL$. Zij weerlegt idempotentie ( $x \land_r x \neq x$ ) maar voldoet aan associativiteit. Het is de logica van volledige evaluatie zonder beperkingen inzake bijwerkingen.
- Memoriserende VGSL (MVGSL): Geaxiomatiseerd door het toevoegen van één axioma aan VVGSL (specifiek, $(x \lor_r y) \land_r z = (\neg x \land_r (y \land_r z)) \lor_r (x \land_r z)$ ). Zij dwingt af dat herhaalde atomen als identiek worden behandeld, waardoor bijwerkingen worden geëlimineerd.
- Conditionele VGSL (CℓVGSL $_2$ ): Geaxiomatiseerd door het toevoegen van commutativiteit ( $x \land_r y = y \land_r x$ ) aan MVGSL. Deze logica is equivalent aan de twee-waardige sublogica van Conditionele Logica (Guzmán en Squier [12]).
- Statische VGSL (SVGL): De sterkste logica, verkregen door $x \land_r F = F$ toe te voegen aan CℓVGSL $_2$ . Het is equivalent aan Statische Short-Circuit Logica (SSCL) en standaard propositielogica onder sequentiële evaluatie.
Drie-waardige Uitbreidingen (VGSLU):
- De auteurs definiëren drie-waardige versies (VVGSLU, MVGSLU, CℓVGSL) door axioma's $\neg U = U$ en $U \land_r x = U$ toe te voegen.
- CℓVGSL (de drie-waardige Conditionele VGSL) wordt bewezen equivalent te zijn aan Bochvar's strikte logica [8].
- SVGL kan niet worden uitgebreid met $U$ , omdat de absorptiewet $F = U \land_r F = U$ leidt tot een instorting van waarheidswaarden.
Volledigheid en Onafhankelijkheid:
- Volledige equationale axiomatisaties worden geboden voor alle gedefinieerde logica's.
- De auteurs presenteren alternatieve, beknoptere verzamelingen van onafhankelijke axioma's voor elke logica (bijv. de verzameling $MF$ voor MVGSL), geverifieerd met geautomatiseerde hulpmiddelen.
- Normaalvormen worden geconstrueerd om te bewijzen dat syntactische gelijkheid van normaalvormen overeenkomt met semantische gelijkheid van evaluatiebomen.

Betekenis en Beweringen
Het artikel beweert een unifyend raamwerk te bieden voor het begrijpen van volledige links-sequentiële evaluatie, waarmee de kloof tussen short-circuit logica's en klassieke propositielogica wordt overbrugd.

Voorspelbaarheid: De auteurs betogen dat VGSL's meer voorspelbaarheid bieden met betrekking tot de staat van de omgeving (bijwerkingen) na evaluatie in vergelijking met SCL's, aangezien alle atomen gegarandeerd worden geëvalueerd.
Expressiviteit: Het artikel demonstreert dat hoewel VVGSL bepaalde uniforme evaluatiebomen niet kan uitdrukken (bijv. bomen waar een atoom in verschillende takken voorkomt met verschillende uitkomsten), MVGSL en sterkere logica's deze wel kunnen uitdrukken, waardoor de expressieve kracht van de logica toeneemt.
Relatie tot Bestaand Werk: Het werk situeert CℓVGSL binnen de hiërarchie van logica's, waarbij wordt aangetoond dat het equivalent is aan Bochvar's logica en een sublogica van Conditionele Logica. Het verduidelijkt ook de relatie tussen VGSL's en Short-Circuit Logica's (SCL's), met de opmerking dat VGSL-connectieven binnen SCL-raamwerken kunnen worden gedefinieerd (en omgekeerd onder specifieke voorwaarden), hoewel VGSL's een strengere evaluatiediscipline afdwingen.

Het artikel concludeert dat deze logica's een robuuste theoretische basis bieden voor redeneren over expressies waar volledige evaluatie vereist is, en volledige en onafhankelijke axiomatisaties bieden die geautomatiseerd redeneren en verificatie faciliteren.