🔢 mathematics

Completeness of Tableau Calculi for Two-Dimensional Hybrid Logics

Dit artikel presenteert een geluid en compleet tableaukalkulus voor twee-dimensionale hybride productlogica en hybride afhankelijke productlogica, waarbij een speciale regel wordt toegevoegd die de geldigheid behoudt, hoewel beide systemen niet garanderen dat ze termineren.

Oorspronkelijke auteurs: Yuki Nishimura

Gepubliceerd 2026-03-17

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yuki Nishimura

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 enorme, complexe stad probeert te begrijpen. In deze stad zijn er twee soorten wegen: horizontale wegen (zoals straten) en verticale wegen (zoals trappen of liften).

Dit artikel van Yuki Nishimura gaat over een heel speciaal soort "logica" (een manier om te redeneren) die helpt om te begrijpen wat er gebeurt in zo'n stad, maar dan met een extra twist: we kunnen niet alleen zeggen "er is een huis hier", maar we kunnen ook specifieke huizen bij naam noemen en zeggen "in dat specifieke huis, op die specifieke verdieping, gebeurt X".

Hier is een simpele uitleg van wat de auteur doet, vertaald in alledaags taalgebruik:

1. De Basis: De "Hybride" Stad

Normale logica (modal logic) is als een kaart waar je alleen kunt zeggen: "Vanaf hier kun je naar een ander punt gaan." Maar het kan niet zeggen waar je precies bent.

De auteur gebruikt Hybride Logica. Dit is als een kaart met naamplaatjes op de straten en verdiepingen.

Naamplaatjes (Nominals): Stel je voor dat elke straat een naam heeft (bijv. "Straat 1") en elke verdieping ook (bijv. "Verdieping A").
De Operator (@): Dit is als een vinger die wijst. Als je zegt @Straat1, bedoel je "precies op Straat 1, waar je ook bent".

2. Het Probleem: Twee Dimensies die Samenwerken

De auteur kijkt naar een stad met twee dimensies:

Tijd (of horizontale beweging).
Ruimte (of verticale beweging).

In de HPL (Hybrid Product Logic) werken deze twee dimensies onafhankelijk van elkaar. Het is alsof je in een flatgebouw bent: je kunt naar een andere verdieping gaan (verticaal) of naar een andere kamer op dezelfde verdieping (horizontaal). De lift werkt altijd hetzelfde, ongeacht op welke verdieping je bent.

Het doel van het artikel: De auteur wil een Tableau Calculus bouwen.

Wat is dat? Denk aan een recept voor een detective. Je begint met een verdenking (een formule) en probeert stap voor stap te bewijzen of het waar is of niet. Als je een tegenstrijdigheid vindt (bijv. "Het regent" én "Het regent niet"), dan is je verdenking onwaar.
De auteur maakt een recept dat werkt voor deze tweedimensionale steden. Hij bewijst dat zijn recept correct is (je komt nooit tot een verkeerde conclusie) en compleet is (als iets waar is, kan je recept het ook vinden).

3. De Uitdaging: De Lift die Verandert (HdPL)

Dan komt het interessante deel: HdPL (Hybrid Dependent Product Logic).
Stel je voor dat de lift in je gebouw niet altijd hetzelfde doet.

Op de 1e verdieping gaat de lift alleen naar de 2e verdieping.
Op de 10e verdieping gaat de lift alleen naar de 11e en 12e.
De beweging in de ene richting (verticaal) hangt nu af van waar je bent in de andere richting (horizontaal).

De auteur past zijn detective-recept aan voor deze situatie. Hij voegt een speciale regel toe om te voorkomen dat de lift op de verkeerde manier beweegt. Hij bewijst dat dit nieuwe recept ook werkt voor deze "afhankelijke" steden.

4. Een Speciale Regel: "Aflopende" Steden

In sectie 6.4 introduceert hij een extra eigenschap: "Decreasing" (Aflopend).
Dit is als een tijdlijn. Stel je voor dat hoe ouder je wordt, hoe meer je herinneringen hebt. Alles wat waar was in het verleden, is ook waar in het heden (of andersom, afhankelijk van hoe je het bekijkt).
De auteur voegt een extra regel toe aan zijn recept die zorgt dat de logica rekening houdt met deze "aflopende" tijd. Hij laat zien dat je dit kunt doen zonder het hele recept te breken.

5. Het Grote Nadeel: De Oneindige Loop

Er is één groot probleem met al deze recepten: ze stoppen niet altijd.

Het probleem: Soms blijft de detective rondlopen in een cirkel. Hij zegt: "Ga naar kamer 1, dan kamer 2, dan weer kamer 1, dan kamer 2..." en dat kan oneindig doorgaan.
De gevolgen: Omdat het recept oneindig kan doorgaan, kunnen computers het niet altijd gebruiken om snel een antwoord te geven (dit heet "decidability"). De auteur geeft toe: "Ja, mijn recept is perfect om te bewijzen of iets waar is, maar het is niet altijd efficiënt om te stoppen."

Samenvatting in Metaforen

De Stad: Een wereld met tijd en ruimte.
Naamplaatjes: Specifieke adressen in die wereld.
Het Tableau Calculus: Een stap-voor-stap detective-verhaal om te zien of een verhaal klopt.
HPL: Een stad waar de regels voor tijd en ruimte los van elkaar staan.
HdPL: Een stad waar de regels voor tijd veranderen afhankelijk van waar je bent in de ruimte.
De Loop: De detective die in een cirkel blijft rennen en nooit thuiskomt.

Conclusie:
Yuki Nishimura heeft een krachtig nieuw gereedschap (een tableau calculus) ontworpen om complexe, tweedimensionale werelden te analyseren. Hij heeft bewezen dat het werkt voor zowel onafhankelijke als afhankelijke werelden. Het enige wat nog ontbreekt, is een manier om te zorgen dat de detective niet oneindig blijft rondlopen, zodat computers het sneller kunnen gebruiken.

Probleemstelling

Hybride logica is een uitbreiding van de modale logica die "nominalen" (proposities die waar zijn in precies één mogelijke wereld) en een "satisfaction operator" (@) introduceert. Dit maakt het mogelijk om globale beschrijvingen van modellen te geven, in plaats van alleen lokale.
Het artikel richt zich op Hybrid Product Logic (HPL), een many-dimensional uitbreiding waarbij twee onafhankelijke dimensies (bijvoorbeeld tijd en ruimte) worden gecombineerd. Hoewel er Hilbert-systemen en sequent-calculi voor HPL bestaan, ontbreekt er een tableau calculus (een bewijssysteem dat werkt via het uitbreiden van takken van een boom) voor deze logica.
Daarnaast wordt er gekeken naar Hybrid Dependent Product Logic (HdPL), waarbij de toegang tot de tweede dimensie afhankelijk is van de positie in de eerste dimensie. De uitdaging ligt in het construeren van een bewijsstelsel dat zowel geluid (sound) als volledig (complete) is, terwijl de complexiteit en terminatie (eindigheid van het bewijsproces) in acht worden genomen.

Methodologie

De auteur hanteert de methode van geïnternaliseerde tableau calculi (internalized tableau calculus), gebaseerd op eerdere werken voor één-dimensionale hybride logica (zoals Blackburn et al.).

Semantiek:
- HPL: Gebaseerd op product Kripke-modellen $M = (W_1 \times W_2, R_h, R_v, V)$ . De relaties $R_h$ (horizontaal) en $R_v$ (verticaal) werken onafhankelijk van elkaar.
- HdPL: Gebaseerd op afhankelijke product-modellen (d-product), waarbij de verticale relatie $R_v$ afhangt van het punt in de horizontale dimensie ( $R_2(x)$ ).
Tableau Constructie:
- In plaats van voorvoegsels (prefixes) te gebruiken zoals in standaard modale logica, worden labels geïntegreerd in de formules zelf. Een formule $(x, y) : \phi$ wordt geschreven als @i@aϕ, waarbij i en a de nominaal zijn die respectievelijk de eerste en tweede dimensie aanduiden.
- Er worden specifieke regels gedefinieerd voor de modale operatoren ( $\diamond_1, \diamond_2$ ), de satisfaction operator (@), en de nominalen.
- Voor HdPL worden de regels voor de tweede dimensie aangepast ( $\diamond^d_2$ ) om de afhankelijkheid van de eerste dimensie te modelleren. Er wordt een nieuw concept ingevoerd: accessibility formulas (toegankelijkheidsformules), die restricties opleggen aan wanneer regels kunnen worden toegepast om correctheid te garanderen.
Bewijstechnieken:
- Geluidheid (Soundness): Bewezen door aan te tonen dat als een tableau gesloten is, de wortelformule geldig is. Dit gebeurt via een "faithful model" constructie: als een tak open blijft, kan er een model worden geconstrueerd dat aan alle formules in die tak voldoet.
- Volledigheid (Completeness): Bewezen door aan te tonen dat als een formule niet bewijsbaar is, er een open, verzadigde (saturated) tak bestaat. Uit deze tak wordt een kanoniek model geconstrueerd (met behulp van "urfathers" van nominalen) waarin de formule niet geldt.

Belangrijkste Bijdragen

Constructie van Tableau Calculi:
- De auteur presenteert de eerste sound en complete tableau calculus voor HPL (twee dimensies, onafhankelijk).
- Er wordt een aangepaste tableau calculus ontwikkeld voor HdPL (afhankelijke dimensies), inclusief specifieke regels om de afhankelijkheid van de toegangspunten te handhaven.
Behandeling van Afhankelijkheid en "Decreasing" Eigenschappen:
- Voor HdPL wordt een speciale regel [Dec] geïntroduceerd om de eigenschap "decreasing" (afnemend) te modelleren. Dit komt overeen met de eigenschap dat als een relatie in de toekomst bestaat, deze ook in het verleden moet bestaan (relevant voor logica's zoals $T \times W$ ).
- Er wordt bewezen dat de tableau calculus met deze regel sound en volledig is voor de klasse van "decreasing" d-product frames.
Directe Bewijzen van Volledigheid:
- In tegenstelling tot eerdere werken (zoals Sano's sequent calculus) die volledigheid indirect bewezen door equivalentie met Hilbert-systemen, bewijst Nishimura de volledigheid direct door een tegenvoorbeeldmodel te construeren uit een open tableau. Dit maakt het systeem krachtiger voor het genereren van counterexamples.

Resultaten

Soundness en Completeness: De tableau calculi voor zowel HPL als HdPL (inclusief de variant met de [Dec] regel) zijn bewezen sound en volledig voor hun respectievelijke klassen van Kripke-modellen.
Geen Terminatie: Een cruciaal resultaat is dat de voorgestelde tableau calculi geen terminatie-eigenschap hebben. Er wordt een voorbeeld gegeven (een oneindige tak) waarbij de regels herhaaldelijk nieuwe nominalen genereren zonder dat de boom eindigt.
- Dit impliceert dat de beslisbaarheid (decidability) van HPL en HdPL via deze specifieke tableau-methode een open probleem blijft.
Uitbreidbaarheid: De methode kan worden uitgebreid naar $n$ -dimensionale logica's ( $n \geq 3$ ), maar aangezien product-modale logica's met meer dan 3 dimensies onbeslisbaar zijn, zal de terminatieproblematiek daar nog ernstiger zijn.

Betekenis en Toekomstperspectief

Dit artikel vult een belangrijke lacune in de literatuur over hybride logica door een direct werkend bewijssysteem (tableau) te bieden voor multidimensionale scenario's. De directe constructie van counterexamples is een significant voordeel voor automatische redenering en model-checking.

De belangrijkste beperking is het gebrek aan terminatie. De auteur suggereert dat loop-checking (het detecteren van "tweeling"-nominalen die dezelfde rol spelen) een mogelijke oplossing zou kunnen zijn om een eindig bewijsstelsel te creëren. Verder wordt er gewezen op de mogelijkheid om de logica te verrijken met andere hybride operatoren (zoals $E$ en $\downarrow$ ) en axioma's voor S4, hoewel dit de complexiteit en het probleem van terminatie waarschijnlijk zal vergroten.

Samenvattend biedt dit werk een solide theoretische basis voor het redeneren over complexe, multidimensionale systemen met hybride logica, maar benadrukt het ook de inherente moeilijkheden bij het garanderen van eindige bewijzen in deze context.