Introduction à la logiqueinf242.forge.imag.fr/cours1.pdf · I complétude du calcul des prédicats...

Introduction à la logique

Benjamin Wack (benjamin.wack@imag.fr)

Notes de cours parStéphane Devismes Pascal Lafourcade Michel Lévy

Université Grenoble Alpes

9 janvier 2017

B. Wack (UGA) Introduction à la logique 9 janvier 2017 1 / 45

Préambule

Organisation

12 semaines

I Cours magistral : 1h30 par semaine

I TD : 2 × 1h30 = 3h par semaine

Cette semaine

I Cours magistral : aujourd’hui ! et jeudi 13h30 comme d’habitude

I TDs : 1 TD seulement cette semaine (mardi/vendredi),2 à partir de la semaine prochaine

voir http://inf242.forge.imag.fr/

Préambule

Planning

Dates importantes

I Vacances hiver : 20-26 février

I Pré-rapport projet : du 27 février au 3 mars

I Partiels : 6-10 mars

I Vacances printemps : 17-23 avril

I Rapport de Projet : du 24 au 28 avril

I Soutenance de Projet : 2-5 mai

I Examen : du 9 au 19 mai

I Deuxième session : Semaine du 19 juin

Préambule

Evaluations

I Contrôle continu 60% : 4 interros 10%, partiel 20% et projet 30%I Examen : 40%

Projet par groupes de 3 (ou 4).

I Phase 1 : Modélisation d’un problème en logique (avec interfacelogicielle)

I Phase 2 : Utilisation d’un solveur SAT pour résoudre ce problème

I Optionnel : Programmation d’un solveur SAT

Exemples de problèmes : Takuzu, Tout noir tout blanc, Squaro,Sudoku ...

Préambule

Matériel

I Poly (à trous)

I Sujet du projet (en ligne)

Préambule

Introduction à la Logique

Logique propositionnelle

Syntaxe

Sens des formules (sémantique)

Conclusion

Préambule

Syntaxe

Conclusion

Logique

Définitions

I La logique précise ce qu’est un raisonnement correct,indépendemment du domaine d’application.

I Un raisonnement est un moyen d’obtenir une conclusion à partird’hypothèses données.

I Un raisonnement correct ne dit rien sur la vérité des hypothèses,il dit seulement que de la vérité des hypothèses, on peutdéduire la vérité de la conclusion.

Logique

Définitions

Logique

Définitions

Exemples

Exemple I

I Hypothèse I : Tous les hommes sont mortels

I Hypothèse II : Socrate est un homme

I Conclusion : Socrate est mortel

Exemple II

I Hypothèse I : Tout ce qui est rare est cher

I Hypothèse II : Un cheval bon marché est rare

I Conclusion : Un cheval bon marché est cher !

Exemples

Exemple I

I Hypothèse I : Tous les hommes sont mortels

I Hypothèse II : Socrate est un homme

I Conclusion : Socrate est mortel

Exemple II

I Conclusion : Un cheval bon marché est cher !

Ajout d’une hypothèse

Exemple III

I Hypothèse III : Tout ce qui est bon marché n’est pas cher

I Conclusion : Hypothèses contradictoires ! Car :I Hypothèse I + hypothèse II : Un cheval bon marché est cherI Hypothèse III : Un cheval bon marché n’est pas cher

Exemple III

I Hypothèse III : Tout ce qui est bon marché n’est pas cher

I Conclusion : Hypothèses contradictoires ! Car :I Hypothèse I + hypothèse II : Un cheval bon marché est cherI Hypothèse III : Un cheval bon marché n’est pas cher

Exemple III

I Hypothèse III : Tout ce qui est bon marché n’est pas cherI Conclusion : Hypothèses contradictoires ! Car :

I Hypothèse I + hypothèse II : Un cheval bon marché est cherI Hypothèse III : Un cheval bon marché n’est pas cher

Petit historique. . .

I George Boole (1815-1864)I logique symbolique : s’éloigne de la langue naturelle

I Gottlob Frege (1848-1925)I calcul propositionnel : formalisation des règles de raisonnementI théorie de la démonstration : démonstration = objet d’étude

I Bertrand Russell (1872-1970)I logicisme : programme de formalisation des mathématiquesI paradoxe dans les premiers systèmes proposés

I Kurt Gödel (1906-1978)I complétude du calcul des prédicats du premier ordreI théorème d’incomplétude des systèmes incluant N

I Alonzo Church (1903-1995)I lambda-calcul : représentation calculatoire des démonstrations

Applications

I Hardware (portes logique)I Vérification et correction des programmes :

I prouveurs COQ, PVS, Prover9, MACE, . . .I applications industrielles (Meteor, Airbus...)

I Intelligence artificielle :I système expert (MyCin), ontologie

I Programmation : PrologI intelligence artificielleI traitement de la langue

I Preuves mathématiques, Sécurité, . . .

Plan du Semestre

AUJOURD’HUI

I Logique propositionnelle

I Résolution propositionnelle

I Déduction naturelle propositionnelle

PARTIEL

I Logique du premier ordre

I Base de la démonstration automatique(« résolution au premier ordre »)

I Déduction naturelle au premier ordre

EXAMEN

Objectifs du cours

I Modéliser et formaliser un problème décrit en langage naturel.

I Comprendre un raisonnement présenté sous forme symbolique,en particulier être capable de déterminer s’il est correct.

I Démontrer, c’est-à-dire construire un raisonnement correctutilisant les règles et/ou les algorithmes de la logiquepropositionnelle et du premier ordre.

I Écrire une preuve rigoureuse, en particulier par récurrence.

Objectifs du cours

Préambule

Syntaxe

Conclusion

Définition

La logique propositionnelle est la logique sans quantificateurs.Seules opérations logiques considérées :

I ¬ (négation)

I ∧ (conjonction “et”)

I ∨ (disjonction “ou”)

I ⇒ (implication)

I ⇔ (équivalence)

Exemple : Raisonnement formel

Hypothèses :I (H1) : Si Pierre est grand, alors Jean n’est pas le fils de PierreI (H2) : Si Pierre n’est pas grand, alors Jean est le fils de PierreI (H3) : Si Jean est le fils de Pierre alors Marie est la soeur de Jean

Conclusion (C) : Marie est la soeur de Jean ou Pierre est grand.

I p : "Pierre est grand"

I j : "Jean est le fils de Pierre"

I m : "Marie est la soeur de Jean"

I (H1) : p⇒¬j

I (H2) : ¬p⇒ j

I (H3) : j⇒m

I (C) : m∨pIl s’agira de montrer que H1∧H2∧H3⇒ C :

(p⇒¬j)∧ (¬p⇒ j)∧ (j⇒m)⇒m∨p

est vraie quelque soit la valeur de vérité des propositions p, j,m.

I (H1) : p⇒¬j

I (H2) : ¬p⇒ j

I (H3) : j⇒m

(p⇒¬j)∧ (¬p⇒ j)∧ (j⇒m)⇒m∨p

I (H1) : p⇒¬j

I (H2) : ¬p⇒ j

I (H3) : j⇒m

I (C) : m∨p

Il s’agira de montrer que H1∧H2∧H3⇒ C :

(p⇒¬j)∧ (¬p⇒ j)∧ (j⇒m)⇒m∨p

I (H1) : p⇒¬j

I (H2) : ¬p⇒ j

I (H3) : j⇒m

(p⇒¬j)∧ (¬p⇒ j)∧ (j⇒m)⇒m∨p

est vraie quelque soit la valeur de vérité des propositions p, j,m.B. Wack (UGA) Introduction à la logique 9 janvier 2017 17 / 45

Syntaxe

Préambule

Syntaxe

Conclusion

Syntaxe

Vocabulaire du langage

I Les constantes : > (vrai) et ⊥ (faux)

I Les variables : par exemple x , y1

I Les parenthèses

I Les connecteurs : ¬,∨,∧,⇒,⇔

Syntaxe

Formule (stricte)

Définition 1.1.1

Une formule stricte est définie de manière inductive par :

I > et ⊥ sont des formules strictes.

I Une variable est une formule stricte.

I Si A est une formule stricte alors ¬A est une formule stricte.

I Si A et B sont des formules strictes et si ◦ est une des opérations∨,∧,⇒,⇔ alors (A◦B) est une formule stricte.

Exemple 1.1.2

(a∨ (¬b∧ c)) est une formule stricte, mais pas a∨ (¬b∧ c), ni(a∨ (¬(b)∧ c)).

Syntaxe

Formule (stricte)

Définition 1.1.1

Une formule stricte est définie de manière inductive par :

I > et ⊥ sont des formules strictes.

I Une variable est une formule stricte.

I Si A est une formule stricte alors ¬A est une formule stricte.

I Si A et B sont des formules strictes et si ◦ est une des opérations∨,∧,⇒,⇔ alors (A◦B) est une formule stricte.

Exemple 1.1.2

(a∨ (¬b∧ c)) est une formule stricte, mais pas a∨ (¬b∧ c), ni(a∨ (¬(b)∧ c)).

Syntaxe

Exemple 1.1.3

La structure de la formule (a∨ (¬b∧ c)) est mise en évidence parl’arbre suivant :

Syntaxe

Exemple 1.1.3

Syntaxe

Exemple 1.1.3

~~ !!a

Syntaxe

Exemple 1.1.3

~~ !!a ∧

Syntaxe

Exemple 1.1.3

~~ !!a ∧

��

Syntaxe

Exercice

((p∧¬(p∨q))∧¬r)

~~ ∧

��

��p ¬

��

�� p q

Syntaxe

Exercice

((p∧¬(p∨q))∧¬r)

~~ ∧

��

��p ¬

��

�� p q

Syntaxe

Taille d’une formule

Définition 1.1.10

La taille d’une formule A, notée |A|, est définie inductivement par :I |>|= 0 et |⊥|= 0.

I Si A est une variable alors |A|= 0.

I |¬A|= 1+ |A|.I |(A◦B)|= |A|+ |B|+1.

Exemple 1.1.11

|(a∨ (¬b∧ c))| =3.

Syntaxe

Définition 1.1.10

I |¬A|= 1+ |A|.I |(A◦B)|= |A|+ |B|+1.

Exemple 1.1.11

|(a∨ (¬b∧ c))| =

Syntaxe

Définition 1.1.10

I |¬A|= 1+ |A|.I |(A◦B)|= |A|+ |B|+1.

Exemple 1.1.11

|(a∨ (¬b∧ c))| =3.

Syntaxe

Premier résultat

Les formules strictes se décomposent de manière unique en leurssous-formules.

Théorème 1.1.13Toute formule A s’écrit sous une et une seule de ces formes :

I une variable,

I une constante,

I ¬B où B est une formule,

I (B ◦C) où B et C sont des formules et ◦ un connecteur binaire.

Ce qui autorise :

I la démonstration par cas

I la récurrence sur la structure des formules et non sur leur taille.

Syntaxe

Formule à priorité

Définition 1.1.14

Idem mais :

I si A et B sont des formules à priorité alors A◦B est une formule àpriorité,

I si A est une formule à priorité alors (A) est une formule à priorité.

Exemple 1.1.15

a∨¬b∧ c est une formule à priorité mais pas une formule (stricte).

Syntaxe

Règles de priorité

Définition 1.1.16

Par ordre de priorités décroissantes : ¬, ∧, ∨,⇒ et⇔.

Associativité à gauche

Pour deux connecteurs identiques A◦B ◦C = (A◦B)◦Csauf pour l’implication : A⇒ B⇒ C = A⇒ (B⇒ C)

Syntaxe

Exemples de formules à priorité

Exemple 1.1.17

I a∧b∧ c est l’abréviation de

((a∧b)∧ c)

I a∧b∨ c est l’abréviation de

((a∧b)∨ c)

I a∨b∧ c est l’abréviation de

(a∨ (b∧ c))

Syntaxe

Exemple 1.1.17

((a∧b)∧ c)

((a∧b)∨ c)

(a∨ (b∧ c))

Syntaxe

Exemple 1.1.17

((a∧b)∧ c)

((a∧b)∨ c)

(a∨ (b∧ c))

Syntaxe

Exemple 1.1.17

((a∧b)∧ c)

((a∧b)∨ c)

(a∨ (b∧ c))

Préambule

Syntaxe

Conclusion

Assignation d’une formule

Définition 1.2.1

Une assignation est une fonction qui,à chaque variable d’une formule, associe une valeur dans {0,1}.

[A]v dénote la valeur de la formule A dans l’assignation v .

Exemple : Soit v une assignation telle que v(x) = 0 et v(y) = 1.Appliquer v à x ∨ y s’écrit [x ∨ y ]v[x ∨ y ]v = 0∨1 = 1Conclusion : x ∨ y est vrai pour l’assignation v

Définition 1.2.1

Exemple : Soit v une assignation telle que v(x) = 0 et v(y) = 1.Appliquer v à x ∨ y s’écrit

[x ∨ y ]v[x ∨ y ]v = 0∨1 = 1Conclusion : x ∨ y est vrai pour l’assignation v

Définition 1.2.1

Exemple : Soit v une assignation telle que v(x) = 0 et v(y) = 1.Appliquer v à x ∨ y s’écrit [x ∨ y ]v[x ∨ y ]v =

0∨1 = 1Conclusion : x ∨ y est vrai pour l’assignation v

Définition 1.2.1

Exemple : Soit v une assignation telle que v(x) = 0 et v(y) = 1.Appliquer v à x ∨ y s’écrit [x ∨ y ]v[x ∨ y ]v = 0∨1 = 1Conclusion :

x ∨ y est vrai pour l’assignation v

Définition 1.2.1

Exemple : Soit v une assignation telle que v(x) = 0 et v(y) = 1.Appliquer v à x ∨ y s’écrit [x ∨ y ]v[x ∨ y ]v = 0∨1 = 1Conclusion : x ∨ y est vrai pour l’assignation v

Valeur d’une formule

Définition 1.2.2

Soient A, B des formules, x une variable et v une assignation.I [x]v =

I [>]v =

, [⊥]v =

I [¬A]v =

1− [A]v

I [(A∨B)]v =

max{[A]v , [B]v}

I [(A∧B)]v =

min{[A]v , [B]v}

I [(A⇒ B)]v =

si [A]v = 0 alors 1 sinon [B]v

I [(A⇔ B)]v =

si [A]v = [B]v alors 1 sinon 0

Définition 1.2.2

Soient A, B des formules, x une variable et v une assignation.

I [x]v = v(x)

I [>]v =

, [⊥]v =

I [¬A]v =

1− [A]v

I [(A∨B)]v =

max{[A]v , [B]v}

I [(A∧B)]v =

min{[A]v , [B]v}

I [(A⇒ B)]v =

I [(A⇔ B)]v =

Définition 1.2.2

I [x]v = v(x)

I [>]v = 1, [⊥]v =

I [¬A]v =

1− [A]v

I [(A∨B)]v =

max{[A]v , [B]v}

I [(A∧B)]v =

min{[A]v , [B]v}

I [(A⇒ B)]v =

I [(A⇔ B)]v =

Définition 1.2.2

I [x]v = v(x)

I [>]v = 1, [⊥]v = 0

I [¬A]v =

1− [A]v

I [(A∨B)]v =

max{[A]v , [B]v}

I [(A∧B)]v =

min{[A]v , [B]v}

I [(A⇒ B)]v =

I [(A⇔ B)]v =

Définition 1.2.2

I [x]v = v(x)

I [>]v = 1, [⊥]v = 0

I [¬A]v = 1− [A]vI [(A∨B)]v =

max{[A]v , [B]v}

I [(A∧B)]v =

min{[A]v , [B]v}

I [(A⇒ B)]v =

I [(A⇔ B)]v =

Définition 1.2.2

I [x]v = v(x)

I [>]v = 1, [⊥]v = 0

I [¬A]v = 1− [A]vI [(A∨B)]v = max{[A]v , [B]v}I [(A∧B)]v =

min{[A]v , [B]v}

I [(A⇒ B)]v =

I [(A⇔ B)]v =

Définition 1.2.2

I [x]v = v(x)

I [>]v = 1, [⊥]v = 0

I [¬A]v = 1− [A]vI [(A∨B)]v = max{[A]v , [B]v}I [(A∧B)]v = min{[A]v , [B]v}I [(A⇒ B)]v =

I [(A⇔ B)]v =

Définition 1.2.2

I [x]v = v(x)

I [>]v = 1, [⊥]v = 0

I [¬A]v = 1− [A]vI [(A∨B)]v = max{[A]v , [B]v}I [(A∧B)]v = min{[A]v , [B]v}I [(A⇒ B)]v = si [A]v = 0 alors 1 sinon [B]vI [(A⇔ B)]v =

Définition 1.2.2

I [x]v = v(x)

I [>]v = 1, [⊥]v = 0

I [¬A]v = 1− [A]vI [(A∨B)]v = max{[A]v , [B]v}I [(A∧B)]v = min{[A]v , [B]v}I [(A⇒ B)]v = si [A]v = 0 alors 1 sinon [B]vI [(A⇔ B)]v = si [A]v = [B]v alors 1 sinon 0

Table de vérité

Définition 1.2.3

Une table de vérité donne la valeur d’une formule pour chaque choixde valeurs des variables de A.

I une ligne de la table de vérité = une assignation

I une colonne = toutes les valeurs d’une formule.

Tables de base

On associe à chaque formule une valeur : 0 (faux) ou 1 (vrai).La constante > vaut 1 et la constante ⊥ vaut 0.

Table 1.1 (table de vérité des connecteurs)

x y ¬x x ∨ y x ∧ y x ⇒ y x ⇔ y0 0 1 0 0 1 10 1 1 1 0 1 01 0 0 1 0 0 01 1 0 1 1 1 1

Exemple :

Exemple 1.2.4

Donner la table de vérité des formules suivantes.

x y x ⇒ y ¬x ¬x ∨ y (x ⇒ y)⇔ (¬x ∨ y) x ∨¬y0 0

1 1 1 1 1

1 1 1 1 0

0 0 0 1 1

1 0 1 1 1

Exemple :

Exemple 1.2.4

x y x ⇒ y ¬x ¬x ∨ y (x ⇒ y)⇔ (¬x ∨ y) x ∨¬y0 0 1 1

0 1 1 1

1 0 0 0

1 1 1 0

Exemple :

Exemple 1.2.4

x y x ⇒ y ¬x ¬x ∨ y (x ⇒ y)⇔ (¬x ∨ y) x ∨¬y0 0 1 1 1

0 1 1 1 1

1 0 0 0 0

1 1 1 0 1

Exemple :

Exemple 1.2.4

x y x ⇒ y ¬x ¬x ∨ y (x ⇒ y)⇔ (¬x ∨ y) x ∨¬y0 0 1 1 1 1

0 1 1 1 1 1

1 0 0 0 0 1

1 1 1 0 1 1

Exemple :

Exemple 1.2.4

x y x ⇒ y ¬x ¬x ∨ y (x ⇒ y)⇔ (¬x ∨ y) x ∨¬y0 0 1 1 1 1 10 1 1 1 1 1 01 0 0 0 0 1 11 1 1 0 1 1 1

Formules équivalentes

Définition 1.2.5

Deux formules A et B sont équivalentes (noté A≡ B ou simplementA = B) si elles ont la même valeur pour toute assignation.

Exemple 1.2.6

x ⇒ y ≡ ¬x ∨ y

Remarque :Le connecteur logique⇔ ne signifie pas A≡ B.

Définition 1.2.5

Exemple 1.2.6

x ⇒ y ≡ ¬x ∨ y

Définition 1.2.5

Exemple 1.2.6

x ⇒ y ≡ ¬x ∨ y

Valide, tautologie (1/2)

Définition 1.2.8

I Une formule est valide si elle a la valeur 1 pour toute assignation.

I Aussi appelée une tautologie.

I Noté |= A.

Exemple 1.2.9

I (x ⇒ y)⇔ (¬x ∨ y) est valide ;

I x ⇒ y n’est pas valide car

elle est fausse pour x = 1 et y = 0.

Définition 1.2.8

I Une formule est valide si elle a la valeur 1 pour toute assignation.

I Aussi appelée une tautologie.

I Noté |= A.

Exemple 1.2.9

I (x ⇒ y)⇔ (¬x ∨ y) est valide ;

I x ⇒ y n’est pas valide car

elle est fausse pour x = 1 et y = 0.

Propriété 1.2.10

Les formules A et B sont équivalentes (A≡ B)si et seulement sila formule A⇔ B est valide.

Cf table de vérité de⇔.

Modèle d’une formule

Définition 1.2.11

Une assignation v qui donne la valeur 1 à une formule est un modèlede cette formule.

On dit aussi que v satisfait A ou v rend A vraie.

Exemple 1.2.12

Un modèle de x ⇒ y est :

x = 1,y = 1 (il y en a d’autres).

Par contre x = 1,y = 0 n’est pas un modèle de x ⇒ y .

Définition 1.2.11

Exemple 1.2.12

Définition 1.2.11

Exemple 1.2.12

Modèle d’un ensemble de formules

Définition 1.2.13

v est un modèle de l’ensemble {A1, . . . ,An}si et seulement sielle est un modèle de chacune de ces formules.

Exemple 1.2.14

Un modèle de {a⇒ b,b⇒ c} est :

a = 0,b = 0 (et c quelconque).

Définition 1.2.13

Exemple 1.2.14

Définition 1.2.13

Exemple 1.2.14

Propriété d’un modèle d’un ensemble de formules

Propriété 1.2.15

v est un modèle de {A1, . . . ,An}si et seulement siv est un modèle de A1∧ . . .∧An.

Exemple 1.2.16

L’ensemble de formules {a⇒ b,b⇒ c}et la formule (a⇒ b)∧ (b⇒ c)ont les mêmes modèles.

Propriété d’un modèle d’un ensemble de formules

Propriété 1.2.15

v est un modèle de {A1, . . . ,An}si et seulement siv est un modèle de A1∧ . . .∧An.

Exemple 1.2.16

L’ensemble de formules {a⇒ b,b⇒ c}et la formule (a⇒ b)∧ (b⇒ c)ont les mêmes modèles.

Contre-modèle

Définition 1.2.17

Une assignation v qui donne la valeur 0 à A est un contre-modèle de A.

On dit que v ne satisfait pas A ou que v rend la formule fausse.

Exemple 1.2.18

Un contre-modèle de x ⇒ y est :

x = 1,y = 0.

Contre-modèle

Définition 1.2.17

Exemple 1.2.18

x = 1,y = 0.

Contre-modèle

Définition 1.2.17

Exemple 1.2.18

x = 1,y = 0.

Formule satisfaisable

Définition 1.2.20

Un (ensemble de) formule(s) est satisfaisable s’il admet un modèle.

Définition 1.2.21

Un (ensemble de) formule(s) est insatisfaisable s’il n’est pas satisfaisable.

Exemple 1.2.22

x ∧¬x est insatisfaisable, mais x ⇒ y est satisfaisable.

Attentioninsatisfaisable = 0 modèle satisfaisable = 1 modèle ou plusinvalide = 1 contre-modèle ou plus valide = 0 contre-modèle

Définition 1.2.20

Définition 1.2.21

Exemple 1.2.22

Définition 1.2.20

Définition 1.2.21

Exemple 1.2.22

Conclusion

Préambule

Syntaxe

Conclusion

Aujourd’hui

I Pourquoi définir et utiliser la logique formelle ?I Formules de logique propositionnelle :

I 1 variable = 1 proposition (une information) vraie ou fausseI 5 connecteurs pour articuler ces propositions

I Sens des formules :I assignation = choix d’une valeur de vérité pour chaque variableI une formule peut être vraie pour 0, 1, plusieurs ou toutes les

assignations

Conclusion

La prochaine fois

Exercice : étudier “Pierre, Jean et Marie” à l’aide des tables de vérité.

I Équivalences remarquables

I Substitutions et remplacements

I Formes normales

Conclusion

Devise d’Oxford

The more I study, the more I knowThe more I know, the more I forgetThe more I forget, the less I know

Introduction à la logiqueinf242.forge.imag.fr/cours1.pdf · I complétude du calcul des prédicats...

Documents

presentation 2008 DES Interdisciplinartitelalic.paris-sorbonne.fr/PUBLICATIONS/2008/presentation_2008_DES_… · (Calcul des propositions Calcul des prédicats) + Symboles adjoints

Prédicats prédéfinis Prédicats de type : Le type d un terme peut être une variable, une constante (atome, nombre), une structure. Un terme de type variable

Les classes de prédicats: classes sémantiques d’adjectifs Àngels Catena angels.catena@uab.es

Programmation logique Logique des prédicats du premier ordre

Cours d'algorithmique 11 / Intranet 1 9 janvier 2006 Cours dAlgorithmique N P - complétude

La logique des prédicats

Programmation et Logique - LIPNfouquere/ENSEIGNEMENT/LEE/LIC_P13.pdf · Programmation et Logique ... Logique des prédicats du premier ordre : • Prédicats dont les arguments sont

TROIS PETITES ÉTUDES SUR LES PRÉDICATS DE COMMUNICATION VERBAUX ET NOMINAUX

1 Logique du premier ordre (Logique de prédicats) Chap. 8

Prolog - recherche.enac.frrecherche.enac.fr/~brisset/cours/prolog/prolog.pdf · Programmation logique avec contraintes [12] ... Les prédicats vont jouer le rôle de procédures

DI - CHECK-LISTS COMPLÉTUDE D’UNE DEMANDE DE PERMIS

Prédicats prédéfinies Prédicats de type : Le type d un terme peut être une variable, une constante (atome, nombre), une structure. Un terme de type variable

IFT-66975 Contourner la NP-complétude. Que faire face à la NP-complétude? Pour une application précise, je veux trouver la plus grande clique possible

Cours de Logique - Logique des propositions et logique des prédicats

Analyse sémantique des prédicats de communication

IFT-66975 Complexité despace L, NL, PSPACE P-complétude et NC

LOGIQUE CM LP1 PROLOG - cours, examens · Chapitre III — Logique des Prédicats du 1er ordre (LP1) UFR Sciences et Techniques Licence S&T 2°année. 2 ... Calcul des prédicats

Du Calcul des prédicats vers Prolog

IFT-66975 Complexité et NP-complétude

Logique des prédicats - Damien Nouveldamien.nouvels.net/cours/automates/cours.pdf · 2014-11-23 · Histoire et déﬁnitions Propositions vs prédicats Avantages et inconvénients