Nonmonotonic Reasoning in Multivalued Logics

Nonmonotonic Reasoning in Multivalued Logics
Marjon Blondeel
Gevolgtrekking of inferentie in klassieke logica is monotoon: als een conclusie
kan worden bekomen uitgaande van een verzameling feiten dan zal geen enkel
bijkomend feit deze conclusie vals maken. Menselijk redeneren heeft echter
een niet-monotone component. Conclusies zijn gebaseerd op kennis die mensen
ter beschikking hebben en indien nieuwe kennis voorhanden is kunnen eerder
gemaakte gevolgtrekkingen ongeldig worden. Bijvoorbeeld, zolang er geen aanwijzingen zijn dat het gaat regenen, blijven we bij ons besluit om te picknicken
in het park. Op basis van verschillende manieren om om te gaan met uitspraken
zoals “meestal geldt dat” en “bij gebrek aan bewijs van het tegenovergestelde”
zijn sinds de jaren 1970 meerdere niet-monotone logica’s ge¨ıntroduceerd en
bestudeerd. Twee belangrijke formalismen voor niet-monotoon redeneren zijn
autoepistemische logica en negatie-door-falen in logisch programmeren.
Answer set programmeren (ASP) is een declaratieve programmeertaal die
ons toelaat om combinatorische optimalisatieproblemen te modelleren op een
beknopte en elegante manier. Om zo’n probleem op te lossen vertalen we het
eerst naar een ASP-programma. Bepaalde modellen van het programma, de
answer sets, komen dan overeen met de oplossingen van het oorspronkelijke
probleem. De sterkte van ASP ligt in het gebruik van de negatie-door-falen
operator die toelaat om eerder gemaakte conclusies terug te trekken wanneer
nieuwe informatie beschikbaar wordt. Daarenboven is er een sterke connectie tussen ASP en autoepistemische logica: ASP-programma’s kunnen vertaald
worden naar een verzameling formules in autoepistemische logica zodat er een
1-1 verband is tussen de answer sets en de zogenaamde stabiele expansies in
autoepistemische logica.
Hoewel ASP een rijke taal biedt, leent het zich niet onmiddellijk tot het modelleren van problemen met continue domeinen. Vaag answer set programmeren
(fuzzy answer set programming, FASP) is een uitbreiding van ASP gebaseerd op
vaaglogica. Door het gebruik van een oneindig aantal waarheidswaarden biedt
FASP de mogelijkheid om continue systemen te modelleren. Omdat FASP een
relatief nieuw concept is, is er weinig gekend over de computationele complexiteit. Bovendien zijn er bijna geen technieken gekend om answer sets van FASPprogramma’s te berekenen. Tenslotte zijn verbanden met andere formalismen
van niet-monotoon redeneren met continue waarden grotendeels onbekend. In
dit proefschrift wordt op verschillende niveau’s bijgedragen aan het lopende
onderzoek rond FASP.
Een eerste richting van onderzoek is de computationele complexiteit van
FASP. In het bijzonder hebben we de complexiteit van FASP onder de Lukasiewicz
semantiek, een veelgebruikte vaaglogica, in kaart gebracht. We hebben ook de
complexiteit van onmiddellijke syntactische veralgemeningen van ASP bestudeerd
en reducties naar bestaande optimalisatietechnieken zoals bilevel linear programming aangetoond.
1
Vervolgens hebben we een combinatie van autoepistemische logica en vaaglogica ge¨ıntroduceerd. We hebben aangetoond dat deze veralgemening de relatie tussen de answer sets van ASP-programma’s en de stabiele expansies van
een overeenkomstige verzameling autoepistemische formules bewaard. Deze resultaten leiden tot een beter begrip van hoe we vage answer sets moeten interpreteren. Omdat de taal van autoepistemische vaaglogica veel expressiever is
dan de theorie¨en die we nodig hebben om de FASP-programma’s voor te stellen
kan dit een nuttige basis zijn voor het defini¨eren en vergelijken van uitbreidingen
van de basistaal van FASP.
Tenslotte hebben we modale vaaglogica’s gedefinieerd en verbanden met autoepistemische vaaglogica aangetoond. Zo hebben we bijvoorbeeld gekende verbanden tussen autoepistemische logica en verschillende klassieke modale logica systemen veralgemeend. In het bijzonder hebben we Levesque’s logica van
“only knowing” veralgemeend en hebben we aangetoond dat het verband met
autoepistemische logica bewaard blijft onder deze veralgemening. Bovendien
hebben we een correcte en volledige axiomatisatie gegeven voor deze vaaglogica.
Al deze resultaten hebben ons begrip over de complexiteit van FASP en het
verband met andere vormen van niet-monotoon rederen met continue waarheidswaarden verrijkt en uitgediept.
2

Download Report