Defaultlogica
Defaultlogica is een niet-monotone logica ontwikkeld door Raymond Reiter waarmee men kan redeneren over gangbare aannames, zoals vogels die doorgaans kunnen vliegen. Men gebruikt hierbij een default, een regel waarvan men aanneemt dat deze wel zal gelden in de meeste situaties. Zo kunnen vogels gewoonlijk vliegen maar er zijn vogelsoorten (bijvoorbeeld pinguïns en struisvogels) die niet kunnen vliegen. Ook kunnen er andere oorzaken zijn, zoals gebroken vleugels. Defaultlogica biedt een manier om deze vorm van redeneren te formaliseren.

Overzicht
Een theorie in defaultlogica bestaat uit een tupel  waarbij  een verzameling logische formules is waarvan bekend is dat ze gelden en D een verzameling afleidingsregels, de defaults. De formules in  en in de afleidingsregels in  behoren tot een bepaalde logica, zoals propositionele formules of formules uit de predicatenlogica.

Elk van de defaults heeft de volgende vorm (met Engelstalige terminologie):

Deze defaults kunnen gelezen worden als: als de Prerequisite geldt en deze is consistent elk van de Justificationi dan kan men de Conclusion concluderen. Formeel betekent dit dat geen van de negaties van de Justificationi afleidbaar mag zijn. In de predicatenlogica geeft de bovenstaande vorm een schema voor verscheidene defaultregels. Stel een default heeft de volgende vorm:

Het is niet mogelijk te kwantificeren over  (aangezien een default een afleidingsregel is en geen propositie in de objecttaal) maar men kan wel constanten invullen voor ; zo kan het bovenstaande schema resulteren in de volgende defaultregels:

Voorbeeld 1
Het voorbeeld met vogels die doorgaans kunnen vliegen wordt genoteerd met behulp van de volgende default:

Dit kan gelezen worden als: als X een vogel is en we kunnen aannemen dat X kan vliegen, dan kan X vliegen. Anders gezegd: als X een vogel is en onze kennis is consistent met het idee dat X kan vliegen, dan kan X vliegen. Als men echter kan afleiden dat  geldt dan is deze default niet meer toepasbaar.

Stel W bestaat uit:

De default in  kan toegepast worden om te concluderen dat de  kan vliegen want men weet dat  geldt en de negatie van de justification  zit niet in . Men kan echter niet concluderen dat de  kan vliegen want de negatie van  zit wel in . De default kan dus niet toegepast worden aangezien dit inconsistent zou zijn met wat bekend is: de default kan alleen toegepast worden als  geldt en als de huidige kennis consistent is met de propositie .

Over de  kunnen geen verdere conclusies getrokken worden (zoals ) aangezien de default alleen toestaat om  te concluderen onder bepaalde voorwaarden en niet andersom. Het afleiden van een antecedent op basis van een consequent wordt abductief redeneren genoemd.

Voorbeeld 2
De aanname van een gesloten wereld kan in defaultlogica als volgt geformaliseerd worden:

voor elke formule . In de programmeertaal Prolog wordt bijvoorbeeld een 'default'-aanname gebruikt voor negatie, namelijk negatie als falen. Hierbij neemt Prolog aan dat  waar is als het er niet in slaagt om aan te tonen dat  geldt. Dit verschilt met defaultlogica aangezien men daar  alleen kan concluderen als  consistent is met de huidige kennis.

Voorbeeld 3
Een bekend voorbeeld in niet-monotone logica gaat over president Richard Nixon. De volgende defaults worden hierbij gebruikt:
d1: Republikeinen zijn doorgaans geen pacifist.
d2: Quakers zijn doorgaans wel pacifist.

en daarnaast is bekend dat Nixon zowel Republikein als Quaker is. De bijbehorende defaulttheorie is  met  en 

Aanvankelijk zijn beide defaults toepasbaar: de prerequisite van beide defaults zit in de huidige kennis  en zowel  als  (respectievelijk de negaties van de justifications van d1 en d2) zijn niet aanwezig in de huidige kennis . Door het toepassen van een van beide regels wordt de andere regel echter niet meer toepasbaar: als men bijvoorbeeld d1 toepast dan concludeert men  waardoor d2 niet meer toepasbaar is. De default d2 veronderstelt namelijk dat Nixon een Quaker is en dat de huidige kennis consistent is met de propositie . Maar, er is al  afgeleid waardoor deze regel niet meer toegepast kan worden. Dezelfde redenering kan men mutatis mutandis ook houden voor het eerst toepassen van d2 en vervolgens d1 (wat ook niet mogelijk is).

Zoals dit voorbeeld illustreert kunnen defaults elkaar blokkeren. Ook is het mogelijk dat een default een eerdere default schendt door een conclusie te trekken waarvan een eerdere default aannam dat die niet gold. Het voorbeeld maakt ook duidelijk dat een defaulttheorie meerdere 'interpretaties' kan hebben: afhankelijk van de volgorde waarin men defaults toepast concludeert men andere feiten. Op basis van deze defaulttheorie is namelijk zowel  als  concludeerbaar. Naast de bestaande kennis  is er een feitenverzameling concludeerbaar met een van beide proposities:

Daarnaast kan men proposities afleiden die logischerwijs volgen uit deze verzamelingen (op basis van de afleidingsregels van propositielogica en predicatenlogica). Uit  en  volgt bijvoorbeeld ook  en . Om de uiteindelijke feitenverzameling die men kan afleiden uit een gegeven defaulttheorie te noteren, gebruikt men de deductieve afsluiting van een verzameling proposities:

waarbij  de deductieve afsluiting van een verzameling  aanduidt.

Semantiek
Het Nixon-voorbeeld geeft aan dat er meerdere feitenverzamelingen zijn die men kan concluderen op basis van een defaulttheorie. Formeel zegt men dat de defaulttheorie meerdere extensies (Engels: extension) heeft. Een extensie wordt verkregen door een reeks defaults toe te passen op de defaulttheorie totdat er geen default meer toepasbaar is: als de verkregen feitenverzameling consistent is met de gemaakte aannames dan heeft men een extensie, in het andere geval (bij inconsistentie) leidt de reeks niet tot een extensie van de defaulttheorie. Het toepassen van  veronderstelt namelijk dat  niet geldt. Mocht men later wel  afleiden dan schendt dit de eerdere aanname dat  geldt. De afgeleide feitenverzameling mag dus geen propositie bevatten waarvan men bij het toepassen van een default heeft aangenomen dat die niet geldt. Op basis hiervan kan men ook inzien dat de afgeleide feitenverzameling zelf consistent moet zijn. Uit een inconsistente feitenverzameling volgt namelijk elke propositie, inclusief de aannames die men heeft moeten maken om een default toe te passen.

Definitie
Formeel heeft een extensie van een defaulttheorie de volgende vorm:

waarbij
C de conclusies bevat van de defaults die gebruikt zijn om Ei te construeren,
 de deductieve afsluiting van een verzameling  aanduidt.

De reeks defaults dient zodanig te zijn dat er geen enkele default meer toegepast kan worden. Elke default wordt hooguit 1 keer toegepast aangezien het meerdere keren toepassen van een default geen zin heeft (de conclusie is immers al toegevoegd en dus leidt het opnieuw toepassen niet tot meer kennis).

Terminologie
Een reeks toegepaste defaults noemt men een proces (Engels: process). Een proces is gesloten (Engels: closed) als er geen defaults meer toepasbaar zijn. Een proces is succesvol (Engels: successful) als men nooit  heeft afgeleid terwijl men ook  heeft aangenomen, voor elke formule . Een proces is gefaald (Engels: failed) als het niet succesvol is.

Voorbeeld
Een defaulttheorie kan nul of meer extensies hebben. Een voorbeeld van een defaulttheorie met nul extensies is  met  en : de default veronderstelt dat  het geval is en concludeert vervolgens  wat strijdig is met de eerdere aanname.

Externe link
 Defeasible Reasoning, Stanford Encyclopedia of Philosophy

Logica
Logisch programmeren