Négation par l'échec

La négation par l'échec (en anglais NAF pour negation as failure, ou NBF pour negation by failure) est une règle d'inférence non monotone en programmation logique, utilisée pour la dérivation de à partir de l'échec de la dérivation de . C'est une caractéristique importante de la programmation logique depuis les origines de Planner et de Prolog. En Prolog, la négation par l'échec est habituellement implémentée en utilisant les fonctionnalités non logiques du langage. En Prolog pur, les littéraux de négation par l'échec (littéraux négatifs) de la forme peuvent apparaître dans le corps des clauses et peuvent être utilisés pour dériver d'autres littéraux négatifs. Par exemple, si l'on considère uniquement les quatre clauses suivantes : La négation par l'échec dérive , et . La sémantique de la négation par l'échec est restée un problème ouvert jusqu'à ce que Keith Clark montre en 1978 qu'elle était correcte par rapport à la complétion du programme logique où « seulement » et sont interprétés comme « si et seulement si », abrégé en « ssi » et noté . Par exemple, la complétion des quatre clauses précédentes est : La règle d'inférence de la négation par l'échec simule un raisonnement avec une complétion explicite, où la négation est appliquée aux deux côtés de l'équivalence et où la négation de la partie droite est distribuée sur les formules atomiques. Par exemple, pour montrer , la négation par l'échec simule un raisonnement avec les équivalences suivantes : Dans le cas non propositionnel, il faut étendre la complétion avec des axiomes d'égalité, pour formaliser l'hypothèse que des entités avec des noms différents sont elles-mêmes distinctes. La négation par l'échec simule ceci par l'échec de l'unification. Par exemple, si l'on considère uniquement les deux clauses suivantes : On dérive, avec la négation par l'échec, . La complétion du programme est : étendue avec les axiomes d'unicité des noms et de fermeture du domaine. La sémantique par complétion est étroitement liée à la notion de circonscription et à l'hypothèse du monde clos.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (8)

Séances de cours associées (1)

Négation par l'échec

Default logic

Default logic is a non-monotonic logic proposed by Raymond Reiter to formalize reasoning with default assumptions. Default logic can express facts like “by default, something is true”; by contrast, standard logic can only express that something is true or that something is false. This is a problem because reasoning often involves facts that are true in the majority of cases but not always. A classical example is: “birds typically fly”.

Sémantique des modèles stables

La sémantique des modèles stables est une sémantique déclarative en programmation logique utilisant la négation par l'échec. C'est l'une des nombreuses approches standard pour la signification de la négation dans la programmation logique, au côté de la terminaison de programme et de la sémantique bien fondée. La sémantique du modèle stable est à la base du langage de programmation déclarative Answer Set Programming (ASP).

Analyse de terminaison à l'aide de paires de dépendances

Explore l'analyse automatisée de terminaison à l'aide de paires de dépendances, couvrant les techniques classiques et modernes, les concours annuels et des outils comme AProVE.