Logique par défaut - Default logic

La logique par défaut est une logique non monotone proposée par Raymond Reiter pour formaliser le raisonnement avec des hypothèses par défaut.

La logique par défaut peut exprimer des faits tels que «par défaut, quelque chose est vrai»; en revanche, la logique standard ne peut qu'exprimer que quelque chose est vrai ou que quelque chose est faux. C'est un problème car le raisonnement implique souvent des faits qui sont vrais dans la majorité des cas, mais pas toujours. Un exemple classique est: «les oiseaux volent généralement». Cette règle peut être exprimée en logique standard soit par «tous les oiseaux volent», ce qui est incompatible avec le fait que les manchots ne volent pas, soit par «tous les oiseaux qui ne sont pas des pingouins et non des autruches et ... volent», ce qui exige tout exceptions à la règle à spécifier. La logique par défaut vise à formaliser des règles d'inférence comme celle-ci sans mentionner explicitement toutes leurs exceptions.

Syntaxe de la logique par défaut

Une théorie par défaut est une paire . W est un ensemble de formules logiques, appelées théorie d'arrière-plan , qui formalisent les faits connus avec certitude. D est un ensemble de règles par défaut , chacune étant de la forme: ${\ displaystyle \ langle W, D \ rangle}$

${\ displaystyle {\ frac {\ mathrm {Prérequis: Justification} _ {1}, \ dots, \ mathrm {Justification} _ {n}} {\ mathrm {Conclusion}}}}$

Selon cette valeur par défaut, si nous pensons que le prérequis est vrai, et que chacun est conforme à nos croyances actuelles, nous sommes amenés à croire que la conclusion est vraie. ${\ displaystyle \ mathrm {Justification} _ {n}}$

Les formules logiques dans W et toutes les formules par défaut étaient à l'origine supposées être des formules logiques du premier ordre , mais elles peuvent potentiellement être des formules dans une logique formelle arbitraire. Le cas où ce sont des formules en logique propositionnelle est l'un des plus étudiés.

Exemples

La règle par défaut «les oiseaux volent généralement» est formalisée par la valeur par défaut suivante:

${\ displaystyle D = \ left \ {{\ frac {\ mathrm {Bird} (X): \ mathrm {Flies} (X)} {\ mathrm {Flies} (X)}} \ right \}}$

Cette règle signifie que "si X est un oiseau et que l'on peut supposer qu'il vole, alors nous pouvons conclure qu'il vole". Une théorie de base contenant quelques faits sur les oiseaux est la suivante:

${\ displaystyle W = \ {\ mathrm {Oiseau} (\ mathrm {Condor}), \ mathrm {Oiseau} (\ mathrm {Pingouin}), \ neg \ mathrm {Mouches} (\ mathrm {Pingouin}), \ mathrm {Mouches} (\ mathrm {Abeille}) \}}$ .

Selon cette règle par défaut, un condor vole car la précondition Bird (Condor) est vraie et la justification Flies (Condor) n'est pas incompatible avec ce qui est actuellement connu. Au contraire, Bird (Penguin) ne permet pas de conclure Flies (Penguin) : même si la condition préalable du défaut Bird (Penguin) est vraie, la justification Flies (Penguin) est incompatible avec ce que l'on sait. De cette théorie d'arrière-plan et de cette valeur par défaut, Bird (Bee) ne peut pas être conclu car la règle par défaut permet uniquement de dériver Flies ( X ) de Bird ( X ) , mais pas l'inverse. Dériver les antécédents d'une règle d'inférence à partir des conséquences est une forme d'explication des conséquences et est le but du raisonnement abductif .

Une hypothèse par défaut courante est que ce qui n'est pas connu pour être vrai est considéré comme faux. Ceci est connu comme l' Assomption fermé du monde , et est formalisée dans la logique par défaut en utilisant une valeur par défaut comme celui ci - dessous pour tous les faits F .

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

Par exemple, le langage informatique Prolog utilise une sorte d'hypothèse par défaut lorsqu'il s'agit de négation: si un atome négatif ne peut être prouvé comme étant vrai, alors il est supposé être faux. Notez, cependant, que Prolog utilise la soi-disant négation comme échec : lorsque l'interpréteur doit évaluer l'atome , il essaie de prouver que F est vrai, et conclut que c'est vrai s'il échoue. Dans la logique par défaut, au contraire, une valeur par défaut ayant pour justification ne peut être appliquée que si elle est cohérente avec les connaissances actuelles. ${\ displaystyle \ neg F}$${\ displaystyle \ neg F}$${\ displaystyle \ neg F}$${\ displaystyle \ neg F}$

Restrictions

Une valeur par défaut est catégorique ou sans prérequis si elle n'a pas de prérequis (ou, de manière équivalente, son prérequis est tautologique ). Un défaut est normal s'il a une seule justification équivalente à sa conclusion. Une valeur par défaut est supra normale si elle est à la fois catégorique et normale. Un défaut est semi-normal si toutes ses justifications entraînent sa conclusion. Une théorie par défaut est appelée catégorique, normale, supra normale ou semi-normale si toutes les valeurs par défaut qu'elle contient sont respectivement catégoriques, normales, supra normales ou semi-normales.

Sémantique de la logique par défaut

Une règle par défaut peut être appliquée à une théorie si sa condition préalable est impliquée par la théorie et si ses justifications sont toutes cohérentes avec la théorie. L'application d'une règle par défaut conduit à ajouter sa conséquence à la théorie. D'autres règles par défaut peuvent alors être appliquées à la théorie résultante. Lorsque la théorie est telle qu'aucun autre défaut ne peut être appliqué, la théorie est appelée une extension de la théorie par défaut. Les règles par défaut peuvent être appliquées dans un ordre différent, ce qui peut conduire à des extensions différentes. L' exemple du diamant Nixon est une théorie par défaut avec deux extensions:

${\ displaystyle \ left \ langle \ left \ {{\ frac {\ mathrm {Républicain} (X): \ neg \ mathrm {Pacifiste} (X)} {\ neg \ mathrm {Pacifiste} (X)}}, { \ frac {\ mathrm {Quaker} (X): \ mathrm {Pacifiste} (X)} {\ mathrm {Pacifiste} (X)}} \ right \}, \ left \ {\ mathrm {Républicain} (\ mathrm { Nixon}), \ mathrm {Quaker} (\ mathrm {Nixon}) \ right \} \ right \ rangle}$

Puisque Nixon est à la fois républicain et quaker , les deux valeurs par défaut peuvent être appliquées. Cependant, l'application du premier défaut conduit à la conclusion que Nixon n'est pas un pacifiste, ce qui rend le second défaut non applicable. De la même manière, en appliquant la deuxième valeur par défaut, nous obtenons que Nixon est un pacifiste, rendant ainsi la première valeur par défaut non applicable. Cette théorie par défaut particulière a donc deux extensions, l'une dans laquelle Pacifist (Nixon) est vrai, et l'autre dans laquelle Pacifist (Nixon) est faux.

La sémantique originale de la logique par défaut était basée sur le point fixe d'une fonction. Ce qui suit est une définition algorithmique équivalente. Si une valeur par défaut contient des formules avec des variables libres, elle est considérée comme représentant l'ensemble de toutes les valeurs par défaut obtenues en donnant une valeur à toutes ces variables. Un défaut est applicable à une théorie propositionnelle T si et toutes les théories sont cohérentes. L'application de ce défaut à T conduit à la théorie . Une extension peut être générée en appliquant l'algorithme suivant: ${\ displaystyle {\ frac {\ alpha: \ beta _ {1}, \ ldots, \ beta _ {n}} {\ gamma}}}$${\ displaystyle T \ models \ alpha}$${\ displaystyle T \ cup \ {\ beta _ {i} \}}$${\ displaystyle T \ cup \ {\ gamma \}}$

T = W         /* current theory */
A = 0         /* set of defaults applied so far */
 
              /* apply a sequence of defaults */
while there is a default d that is not in A and is applicable to T
    add the consequence of d to T
    add d to A
 
              /* final consistency check */
if 
    for every default d in A
        T is consistent with all justifications of d
then
    output T

Cet algorithme n'est pas déterministe , car plusieurs valeurs par défaut peuvent alternativement être appliquées à une théorie T donnée . Dans l'exemple du diamant Nixon, l'application de la première valeur par défaut conduit à une théorie à laquelle la seconde valeur par défaut ne peut pas être appliquée et vice versa. En conséquence, deux extensions sont générées: une dans laquelle Nixon est un pacifiste et une dans laquelle Nixon n'est pas un pacifiste.

Le contrôle final de cohérence des justifications de tous les défauts qui ont été appliqués implique que certaines théories n'ont pas d'extensions. En particulier, cela se produit chaque fois que cette vérification échoue pour chaque séquence possible de valeurs par défaut applicables. La théorie par défaut suivante n'a pas d'extension:

${\ displaystyle \ left \ langle \ left \ {{\ frac {: A (b)} {\ neg A (b)}} \ right \}, \ emptyset \ right \ rangle}$

Puisqu'il est cohérent avec la théorie de base, la valeur par défaut peut être appliquée, conduisant ainsi à la conclusion qui est fausse. Ce résultat mine cependant l'hypothèse qui a été faite pour appliquer le premier défaut. Par conséquent, cette théorie n'a pas d'extensions. ${\ displaystyle A (b)}$${\ displaystyle A (b)}$

Dans une théorie par défaut normale, toutes les valeurs par défaut sont normales: chaque valeur par défaut a la forme . Une théorie par défaut normale est garantie d'avoir au moins une extension. De plus, les extensions d'une théorie normale des défauts sont incompatibles entre elles, c'est-à-dire incompatibles les unes avec les autres. ${\ displaystyle {\ frac {\ phi: \ psi} {\ psi}}}$

Engagement

Une théorie par défaut peut avoir zéro, une ou plusieurs extensions. L'implication d'une formule à partir d'une théorie par défaut peut être définie de deux manières:

Sceptique

une formule est impliquée par une théorie par défaut si elle est impliquée par toutes ses extensions;

Crédule

une formule est impliquée par une théorie par défaut si elle est impliquée par au moins une de ses extensions.

Ainsi, la théorie de l'exemple du diamant Nixon a deux extensions, l'une dans laquelle Nixon est un pacifiste et l'autre dans laquelle il n'est pas un pacifiste. Par conséquent, ni Pacifiste (Nixon) ni ¬Pacifiste (Nixon) ne sont impliqués de manière sceptique, alors que les deux sont impliqués de manière crédule. Comme le montre cet exemple, les conséquences crédules d'une théorie par défaut peuvent être incompatibles les unes avec les autres.

Règles d'inférence par défaut alternatives

Les règles d'inférence alternatives suivantes pour la logique par défaut sont toutes basées sur la même syntaxe que le système d'origine.

Justifié

diffère de l'original en ce qu'un défaut n'est pas appliqué si de ce fait l'ensemble T devient incompatible avec une justification d'un défaut appliqué;

Concis

un défaut n'est appliqué que si sa conséquence n'est pas déjà impliquée par T (la définition exacte est plus compliquée que celle-ci; ce n'est que l'idée principale derrière elle);

Contraint

une valeur par défaut n'est appliquée que si l'ensemble composé de la théorie d'arrière-plan, des justifications de toutes les valeurs par défaut appliquées et des conséquences de toutes les valeurs par défaut appliquées (y compris celle-ci) est cohérente;

Rationnel

similaire à la logique par défaut contrainte, mais la conséquence de l'ajout par défaut n'est pas prise en compte dans le contrôle de cohérence;

Prudent

les valeurs par défaut qui peuvent être appliquées mais qui sont en conflit les unes avec les autres (comme celles de l'exemple du diamant Nixon) ne sont pas appliquées.

Les versions justifiées et contraintes de la règle d'inférence attribuent au moins une extension à chaque théorie par défaut.

Variantes de la logique par défaut

Les variantes suivantes de la logique par défaut diffèrent de l'original sur la syntaxe et la sémantique.

Variantes assertionnelles

Une assertion est une paire composée d'une formule et d'un ensemble de formules. Une telle paire indique que p est vrai alors que les formules ont été supposées cohérentes pour prouver que p est vrai. Une théorie assertionnelle par défaut est composée d'une théorie assertionnelle (un ensemble de formules assertionnelles) appelée théorie d'arrière-plan et d'un ensemble de valeurs par défaut définies comme dans la syntaxe originale. Chaque fois qu'un défaut est appliqué à une théorie assertionnelle, la paire composée de sa conséquence et de son ensemble de justifications est ajoutée à la théorie. La sémantique suivante utilise des théories assertionnelles: ${\ displaystyle \ langle p: \ {r_ {1}, \ ldots, r_ {n} \} \ rangle}$${\ displaystyle r_ {1}, \ ldots, r_ {n}}$

• Logique par défaut cumulative
• Engagement envers la logique par défaut des hypothèses
• Logique quasi-par défaut

Extensions faibles

plutôt que de vérifier si les conditions préalables sont valides dans la théorie composée de la théorie d'arrière-plan et des conséquences des valeurs par défaut appliquées, les conditions préalables sont vérifiées pour la validité dans l'extension qui sera générée; en d'autres termes, l'algorithme de génération d'extensions commence par deviner une théorie et l'utiliser à la place de la théorie d'arrière-plan; ce qui résulte du processus de génération d'extensions n'est en fait une extension que si elle est équivalente à la théorie devinée au départ. Cette variante de la logique par défaut est liée en principe à la logique autoépistémique , où une théorie a le modèle dans lequel x est vrai simplement parce que, en supposant vrai, la formule soutient l'hypothèse initiale. ${\ displaystyle \ Box x \ rightarrow x}$${\ displaystyle \ Box x}$${\ displaystyle \ Box x \ rightarrow x}$

Logique par défaut disjonctive

la conséquence d'une valeur par défaut est un ensemble de formules au lieu d'une seule formule. Chaque fois que la valeur par défaut est appliquée, au moins une de ses conséquences est choisie de manière non déterministe et rendue vraie.

Priorités sur les défauts

la priorité relative des valeurs par défaut peut être explicitement spécifiée; parmi les valeurs par défaut applicables à une théorie, une seule des plus préférées peut être appliquée. Certaines sémantiques de la logique par défaut n'exigent pas que les priorités soient explicitement spécifiées; plutôt, des valeurs par défaut plus spécifiques (celles qui sont applicables dans moins de cas) sont préférées à des valeurs moins spécifiques.

Variante statistique

une valeur statistique par défaut est une valeur par défaut avec une limite supérieure attachée à sa fréquence d'erreur; en d'autres termes, la valeur par défaut est supposée être une règle d'inférence incorrecte dans au plus cette fraction de fois où elle est appliquée.

Traductions

Les théories par défaut peuvent être traduites en théories dans d'autres logiques et vice versa. Les conditions suivantes sur les traductions ont été prises en compte:

Conséquences-Préservation

les théories originale et traduite ont les mêmes conséquences (propositionnelles);

Fidèle

cette condition n'a de sens que lors de la traduction entre deux variantes de logique par défaut ou entre une logique par défaut et une logique dans laquelle un concept similaire à l'extension existe, par exemple des modèles en logique modale ; une traduction est fidèle s'il existe une correspondance (typiquement, une bijection) entre les extensions (ou modèles) des théories d'origine et traduites;

Modulaire

une traduction d'une logique par défaut à une autre logique est modulaire si les valeurs par défaut et la théorie de base peuvent être traduites séparément; de plus, l'ajout de formules à la théorie d'arrière-plan ne conduit qu'à ajouter les nouvelles formules au résultat de la traduction;

Même alphabet

les théories originales et traduites sont construites sur le même alphabet;

Polynôme

le temps d'exécution de la traduction ou la taille de la théorie générée doivent être polynomiaux de la taille de la théorie originale.

Les traductions doivent généralement être fidèles ou au moins préserver les conséquences, tandis que les conditions de modularité et du même alphabet sont parfois ignorées.

La traductibilité entre la logique propositionnelle par défaut et les logiques suivantes a été étudiée:

• logique propositionnelle classique;
• logique autoépistémique;
• logique propositionnelle par défaut limitée aux théories semi-normales;
• sémantique alternative de la logique par défaut;
• circonscription.

Les traductions existent ou non selon les conditions imposées. Les traductions de la logique propositionnelle par défaut à la logique propositionnelle classique ne peuvent pas toujours générer une théorie propositionnelle de taille polynomiale, à moins que la hiérarchie polynomiale ne s'effondre. Des traductions en logique autoépistémique existent ou non selon que la modularité ou l'utilisation du même alphabet est requise.

Complexité

La complexité de calcul des problèmes suivants concernant la logique par défaut est connue:

Existence d'extensions

décider si une théorie par défaut propositionnelle a au moins une extension est -complete; ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Implication sceptique

décider si une théorie propositionnelle par défaut implique sceptiquement une formule propositionnelle est -complète; ${\ displaystyle \ Pi _ {2} ^ {P}}$

Implication crédule

décider si une théorie propositionnelle par défaut implique de façon crédule une formule propositionnelle est -complète; ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Vérification de l'extension

décider si une formule propositionnelle équivaut à une extension d'une théorie propositionnelle par défaut est -complet; ${\ displaystyle \ Delta _ {2} ^ {P [\ log]}}$

Vérification du modèle

décider si une interprétation propositionnelle est un modèle d'extension d'une théorie propositionnelle par défaut est -complet. ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Implémentations

Quatre systèmes mettant en œuvre des logiques par défaut sont DeReS , XRay , GADeL et Catala .

Voir également

• Programmation du jeu de réponses
• Logique défaisable
• Logique non monotone

Les références

• G. Antoniou (1999). Un tutoriel sur les logiques par défaut. ACM Computing Surveys , 31 (4): 337-359.
• M. Cadoli, FM Donini, P. Liberatore et M. Schaerf (2000). Efficacité spatiale des formalismes de représentation des connaissances propositionnelles . Journal of Artificial Intelligence Research , 13: 1-31.
• P. Cholewinski, V. Marek et M. Truszczynski (1996). Système de raisonnement par défaut DeReS. Dans les actes de la cinquième conférence internationale sur les principes de la représentation et du raisonnement des connaissances (KR'96) , pages 518-528.
• J. Delgrande et T. Schaub (2003). Sur la relation entre la logique par défaut de Reiter et ses variantes (majeures). Dans Septième Conférence européenne sur les approches symboliques et quantitatives du raisonnement avec incertitude (ECSQARU 2003) , pages 452-463.
• JP Delgrande, T. Schaub et WK Jackson (1994). Approches alternatives de la logique par défaut. Intelligence artificielle , 70: 167-237.
• G. Gottlob (1992). Résultats de complexité pour les logiques non monotones. Journal of Logic and Computation , 2: 397-425.
• G. Gottlob (1995). Traduire la logique par défaut en logique autoépistémique standard . Journal de l'ACM , 42: 711-740.
• T. Imielinski (1987). Résultats sur la traduction des valeurs par défaut en circonscription. Intelligence artificielle , 32: 131-146.
• T. Janhunen (1998). Sur l'intertranslatabilité des logiques autoépistémiques, de défaut et de priorité, et de la circonscription parallèle . In Proceedings of the Sixth European Workshop on Logics in Artificial Intelligence (JELIA'98) , pages 216-232.
• T. Janhunen (2003). Évaluer l'effet de la semi-normalité sur l'expressivité des défauts. Intelligence artificielle , 144: 233-250.
• SE Kyburg et CM. Teng (2006). Inférence logique et statistique non monotone. Computational Intelligence , 22 (1): 26-51.
• P. Liberatore et M. Schaerf (1998). La complexité de la vérification du modèle pour les logiques par défaut propositionnelles. Dans Actes de la treizième conférence européenne sur l'intelligence artificielle (ECAI'98) , pages 18–22.
• W. Lukaszewicz (1988). Considérations sur la logique par défaut: une approche alternative. Intelligence computationnelle , 4 (1): 1-16.
• W. Marek et M. Truszczynski (1993). Logiques non monotones: raisonnement dépendant du contexte . Springer.
• A. Mikitiuk et M. Truszczynski (1995). Logiques par défaut contraintes et rationnelles . Dans les actes de la quatorzième conférence internationale conjointe sur l'intelligence artificielle (IJCAI'95) , pages 1509-1517.
• P. Nicolas, F. Saubion et I. Stéphan (2001). Heuristique pour un système de raisonnement logique par défaut . Journal international sur les outils d'intelligence artificielle , 10 (4): 503-523.
• R. Reiter (1980). Une logique de raisonnement par défaut. Intelligence artificielle , 13: 81-132.
• T. Schaub, S. Brüning et P. Nicolas (1996). XRay: un prouveur de théorème de technologie prologue pour le raisonnement par défaut: une description du système. Dans Actes de la treizième conférence internationale sur la déduction automatisée (CADE'96) , pages 293-297.
• G. Wheeler (2004). Une logique par défaut limitée par les ressources. In Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR-04) , Whistler, Colombie-Britannique, 416-422.
• G. Wheeler et C. Damasio (2004). Une mise en œuvre de la logique statistique par défaut . In Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004) , LNCS Series, Springer, pages 121-133.

Liens externes

• Schmidt, Charles F. RCI.Rutgers.edu , Logique par défaut. Récupéré le 10 août 2004.
• Ramsay, Allan (1999). UMIST.ac.uk , logique par défaut. Récupéré le 10 août 2004.
• Stanford.edu , Raisonnement défaisable, Stanford Encyclopedia of Philosophy .