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 $\langle D,W\rangle$ waarbij $W$ een verzameling logische formules is waarvan bekend is dat ze gelden en D een verzameling afleidingsregels, de defaults. De formules in $W$ en in de afleidingsregels in $D$ behoren tot een bepaalde logica, zoals propositionele formules of formules uit de predicatenlogica.

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

${\frac {\mathrm {Prerequisite} :\mathrm {Justification} _{1},\dots ,\mathrm {Justification} _{n}}{\mathrm {Conclusion} }}$

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

${\frac {A(X):B(X)}{C(X)}}$

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

${\frac {A({\mathord {Jan}}):B({\mathord {Jan}})}{C({\mathord {Jan}})}}\ {\frac {A({\mathord {Piet}}):B({\mathord {Piet}})}{C({\mathord {Piet}})}}\ {\frac {A({\mathord {Klaas}}):B({\mathord {Klaas}})}{C({\mathord {Klaas}})}}$

Voorbeeld 1

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

$D=\left\{{\frac {{\mathit {Vogel}}(X):{\mathit {KanVliegen}}(X)}{{\mathit {KanVliegen}}(X)}}\right\}$

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 $\neg KanVliegen(X)$ geldt dan is deze default niet meer toepasbaar.

Stel W bestaat uit:

$W=\{{\mathit {Vogel}}({\mathit {Arend}}),{\mathit {Vogel}}({\mathit {Struisvogel}}),\neg {\mathit {KanVliegen}}({\mathit {Struisvogel}}),{\mathit {KanVliegen}}({\mathit {Uil}})\}$

De default in $D$ kan toegepast worden om te concluderen dat de ${\mathit {Arend}}$ kan vliegen want men weet dat ${\mathit {Vogel}}({\mathit {Arend}})$ geldt en de negatie van de justification ${\mathit {KanVliegen}}({\mathit {Arend}})$ zit niet in $W$. Men kan echter niet concluderen dat de ${\mathit {Struisvogel}}$ kan vliegen want de negatie van ${\mathit {KanVliegen}}({\mathit {Struisvogel}})$ zit wel in $W$. De default kan dus niet toegepast worden aangezien dit inconsistent zou zijn met wat bekend is: de default kan alleen toegepast worden als ${\mathit {Vogel}}({\mathit {Struisvogel}})$ geldt en als de huidige kennis consistent is met de propositie ${\mathit {KanVliegen}}({\mathit {Struisvogel}})$.

Over de ${\mathit {Uil}}$ kunnen geen verdere conclusies getrokken worden (zoals ${\mathit {Vogel}}(Uil)$) aangezien de default alleen toestaat om ${\mathit {KanVliegen}}({\mathit {Uil}})$ 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:

${\frac {:\neg F}{\neg F}}$

voor elke formule $F$. In de programmeertaal Prolog wordt bijvoorbeeld een 'default'-aanname gebruikt voor negatie, namelijk negatie als falen. Hierbij neemt Prolog aan dat $\neg F$ waar is als het er niet in slaagt om aan te tonen dat $F$ geldt. Dit verschilt met defaultlogica aangezien men daar $\neg F$ alleen kan concluderen als $\neg F$ 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:

d₁: Republikeinen zijn doorgaans geen pacifist.

d₂: Quakers zijn doorgaans wel pacifist.

en daarnaast is bekend dat Nixon zowel Republikein als Quaker is. De bijbehorende defaulttheorie is $\langle D,W\rangle$ met $D=\{{\frac {{\mathit {Republikein}}(X):\neg {\mathit {Pacifist}}(X)}{\neg {\mathit {Pacifist}}(X)}},{\frac {{\mathit {Quaker}}(X):{\mathit {Pacifist}}(X)}{{\mathit {Pacifist}}(X)}}\}$ en $W=\{{\mathit {Republikein}}({\mathit {Nixon}}),{\mathit {Quaker}}({\mathit {Nixon}})\}$

Aanvankelijk zijn beide defaults toepasbaar: de prerequisite van beide defaults zit in de huidige kennis $W$ en zowel ${\mathit {Pacifist}}({\mathit {Nixon}})$ als $\neg {\mathit {Pacifist}}({\mathit {Nixon}})$ (respectievelijk de negaties van de justifications van d₁ en d₂) zijn niet aanwezig in de huidige kennis $W$. Door het toepassen van een van beide regels wordt de andere regel echter niet meer toepasbaar: als men bijvoorbeeld d₁ toepast dan concludeert men $\neg {\mathit {Pacifist}}({\mathit {Nixon}})$ waardoor d₂ niet meer toepasbaar is. De default d₂ veronderstelt namelijk dat Nixon een Quaker is en dat de huidige kennis consistent is met de propositie ${\mathit {Pacifist}}({\mathit {Nixon}})$. Maar, er is al $\neg {\mathit {Pacifist}}({\mathit {Nixon}})$ afgeleid waardoor deze regel niet meer toegepast kan worden. Dezelfde redenering kan men mutatis mutandis ook houden voor het eerst toepassen van d₂ en vervolgens d₁ (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 ${\mathit {Pacifist}}({\mathit {Nixon}})$ als $\neg {\mathit {Pacifist}}({\mathit {Nixon}})$ concludeerbaar. Naast de bestaande kennis $W$ is er een feitenverzameling concludeerbaar met een van beide proposities:

$V_{1}=W\cup \{\neg {\mathit {Pacifist}}({\mathit {Nixon}})\}$

$V_{2}=W\cup \{{\mathit {Pacifist}}({\mathit {Nixon}})\}$

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

$E_{1}={\mathord {Th}}(W\cup \{\neg {\mathit {Pacifist}}({\mathit {Nixon}})\})$

$E_{2}={\mathord {Th}}(W\cup \{{\mathit {Pacifist}}({\mathit {Nixon}})\})$

waarbij ${\mathord {Th}}(S)$ de deductieve afsluiting van een verzameling $S$ 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 ${\frac {\phi :\psi }{\chi }}$ veronderstelt namelijk dat $\neg \psi$ niet geldt. Mocht men later wel $\neg \psi$ afleiden dan schendt dit de eerdere aanname dat $\psi$ 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:

$E_{i}={\mathord {Th}}(W\cup C)$

waarbij

C de conclusies bevat van de defaults die gebruikt zijn om E_i te construeren,

${\mathord {Th}}(S)$ de deductieve afsluiting van een verzameling $S$ 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 $\phi$ heeft afgeleid terwijl men ook $\neg \phi$ heeft aangenomen, voor elke formule $\phi$. 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 $\langle D,W\rangle$ met $D=\{{\frac {:A}{\neg A}}\}$ en $W=\emptyset$: de default veronderstelt dat $A$ het geval is en concludeert vervolgens $\neg A$ wat strijdig is met de eerdere aanname.

Externe link

• (en) Defeasible Reasoning, Stanford Encyclopedia of Philosophy