Rym Guibadj, Fabien Teytaud - LISICguibadj/IA1/cours3.pdfLa constante R renvoie a Richard` La constante J renvoie a Jean` Le predicat F renvoie´ a la relation de fraternit` e´ Rym

Introduction Syntaxe Semantique inference

Logique des predicats

Rym Guibadj, Fabien Teytaud

LISIC, ULCO, EILCO

Rym Guibadj, Fabien Teytaud (LISIC, ULCO, EILCO) Logique des predicats 1 / 49


Motivation

Pour resoudre des problemes complexes qui demandent desconnaissances d’un expert, nous avons besoin d’un langagepermettant de :

representer les connaissances d’un expert facilement.faire des deductions logiques avec ces connaissances.

la logique du premier ordrebase de plusieurs formalismes de representation des connaissanceset du raisonnement deductif utilise entre autres par les systemesexperts.



Motivation

Exemples de raisonnement deductif :

Deduire la maladie du patient et le traitement approprie, a partirde :

Symptomes d’un patient.Regles de causalite entre les symptomes et les pathologies.Regles de causalite sur les traitements.

Diagnostiquer le probleme d’un vehicule a partir de :Symptomes d’un vehicule.Regles de causalite pour la mecanique auto.



Schema d’un systeme expert



Motivation

Execution de taches a l’aide d’un agent :on specifier a l’agent le but a atteindre : robot qui doit transporterdes objets d’un endroit a un autre.la liste des operations a faire pour accomplir le but n’est pas codeed’avance : l’agent utilise un planificateur pour determiner lesactions a prendre.

Une formulation sous forme de logique permet a un systemeunique de faire plusieurs taches differentes (suffit de changer lebut).



Introduction

Peut on modeliser les situations suivantes en logiquepropositionnelle :

certains etudiants assistent a tous les coursaucun etudiant n’assiste a un cours non interessantdans toute salle d’examen, il y a un etudiant qui, s’il echoue,alors tout le monde echoue

Avec la logique des propositions, on peutrepresenter l’information,deduire / inferer de nouvelles connaissances.

Mais on ne peut pasgeneraliserutiliser des relations



Introduction

La logique des propositionssuppose que le monde contient des faits

La logique des predicatssuppose (comme le langage courant) que le monde contient :

Des objets : Gens, maisons, nombres, . . .Des relations : Freres, plus grand que, . . .Des fonctions : Le pere de, le meilleur ami de, la deuxiememi-temps de, . . .



Syntaxe

ConstantesMichel, 2, ULCO, . . .

Relations (predicats)vrai, >, . . .

Fonctions√. . ., pere, . . .

Variablesx,y, . . .

Connecteurs⇒, ⇔, ∨, ∧, ¬

Egalite (entre termes)=

Quantificateurs∀, ∃



Formules atomiques

Formule atomiquepredicat(terme1, . . . , termen)

TermesConstanteVariableFonction(terme1, . . . , termen)

ExemplesFrere(Paul, Etienne)Marie(pere(Michel),mere(Sophie))



Formules complexes

DefinitionConstruites a partir des formules atomiquesAjouts de connecteurs

ExempleFreres(John,Richard)⇒ Freres(Richard, John)



Verite en logique des predicats

Les formules sont vraies par rapport a un modele et uneinterpretation.Le modele contient au moins un objet (element du domaine) etdes relations entre eux.L’interpretation specifie les associations entre :

les symboles de constantes → les objetsles predicats → les relationsles fonctions → les relations fonctionnelles

Une formule atomique predicat(terme1,. . .,termen) est vraie dans unmodele donne, si la relation a laquelle renvoie le predicat s’appliqueaux objets auxquels renvoient les arguments.



Quantification universelle

∀ <variables> <formule>“Tous les etudiants de Calais aiment l’intelligence artificielle” :∀ x Etudiant(x,Calais)⇒ Aime(x,IA).∀ x P ssi P est vrai avec x pouvant etre tous les objets du modele.Reecriture possible avec un ensemble de conjonction(Etudiant(Albert,Calais)⇒ Aime(Albert,IA) ∧(Etudiant(Bertrand,Calais)⇒ Aime(Bertrand,IA) ∧. . .



Quantification existentielle

∃ <variables> <formule>“Il existe au moins un etudiant de Calais qui aime l’intelligenceartificielle” :∃ x Etudiant(x,Calais) ∧ Aime(x,IA).∃ x P ssi P est vrai avec x pouvant etre (au moins) un objet dumodele.Reecriture possible avec un ensemble de disjonction(Etudiant(Albert,Calais) ∧ Aime(Albert,IA) ∨(Etudiant(Bertrand,Calais) ∧ Aime(Bertrand,IA) ∨. . .



Attention

⇒ est le connecteur principal avec ∀Une erreur courante est d’utiliser ∧∀ x Etudiant(x,Calais) ∧ intelligent(x) signifie :”tous les etudiants sont a Calais et tous les etudiants sontintelligents”

∧ est le connecteur principal avec ∃Une erreur courante est d’utiliser ⇒∃ x Etudiant(x,Calais) ⇒ intelligent(x) est vrai :s’il existe quelqu’un qui n’est pas etudiant a Calais



Proprietes des quantificateurs

Equivalence∀ x ∀ y est equivalent a ∀ y ∀ x∃ x ∃ y est equivalent a ∃ y ∃ xAttention : ∀ x ∃ y n’est pas equivalent a ∃ y ∀ x

∃ y ∀ x Etudie(x,y) : ”il existe un module etudie de tous”∀ x ∃ y Etudie(x,y) :”tout le monde suit un module (pour toutetudiant, il existe un module au quel il est inscrit)”



Proprietes des quantificateurs

Equivalence∀ x ∀ y est equivalent a ∀ y ∀ x∃ x ∃ y est equivalent a ∃ y ∃ xAttention : ∀ x ∃ y n’est pas equivalent a ∃ y ∀ x

∃ y ∀ x Etudie(x,y) : ”il existe un module etudie de tous”∀ x ∃ y Etudie(x,y) :”tout le monde suit un module (pour toutetudiant, il existe un module au quel il est inscrit)”

Dualite∀ x Aime(x,les glaces) est equivalent a ¬ ∃ x ¬ Aime(x, lesglaces)∃ x Aime(x,les epinards) est equivalent a ¬ ∀ x ¬ Aime(x, lesepinards)



Notion d’egalite

terme1 = terme2 est vrai dans une interpretation ssi terme1 etterme2 renvoient au meme objetExemple :

Pere ( Richard ) = Henri est vrai ssi la fonction Pere appliquee al’objet Richard renvoie Henri

Definition de Freres en fonction de Parent :



Notion d’egalite

terme1 = terme2 est vrai dans une interpretation ssi terme1 etterme2 renvoient au meme objetExemple :

Pere ( Richard ) = Henri est vrai ssi la fonction Pere appliquee al’objet Richard renvoie Henri

Definition de Freres en fonction de Parent :∀ x,y Freres(x,y) ⇔ ( ¬ (x=y) ∧ ∃ m,p ¬ (m=p) ∧ Parent (m,x) ∧Parent (p,x) ∧ Parent (m,y) ∧ Parent (p,y))



Modelisation d’expressions courantes

ExemplesC(x) : x est un client , F(x) : x est francais, V(x) : x est vegetarien,E(x) : x est un employe

Tous les clients sont francais :Quelques clients ne sont pas vegetariens :Aucun employe n’est un client :Tous les employes sont vegetariens :





Tous les clients sont francais : ∀x ,C(x)→ F (x)

Quelques clients ne sont pas vegetariens :∃x ,C(x) ∧ ¬V (x)

Aucun employe n’est un client : ∀x ,E(x)→ ¬C(x)

Tous les employes sont vegetariens : ∀x ,E(x)→ V (x)





Tous les clients sont francais : ∀x ,C(x)→ F (x)

Quelques clients ne sont pas vegetariens :∃x ,C(x) ∧ ¬V (x)

Aucun employe n’est un client : ∀x ,E(x)→ ¬C(x)

Tous les employes sont vegetariens : ∀x ,E(x)→ V (x)

NotesTous les A sont B : ∀x ,A(x)→ B(x)

Seuls les A sont B : ∀x ,B(x)→ A(x)

Aucun A n’est B : ∀x ,A(x)→ ¬B(x)

Quelques A sont B : ∃x ,A(x) ∧ B(x)



Variables libres et liees 1/3Idee

Soit la formule : ∃x y < x

La portee du quantificateur ∃ est y < x

Seule la variable x fait l’objet de la quantification, elle est dite liee

y ne fait pas l’objet de la quantification, et est dite libre

DefinitionUne occurrence d’une variable x dans une formule atomique est libre

Si une occurrence x est libre (resp. liee) dans une formule A alors elleest libre (resp. liee) dans A → B, A ⇔ B, A ∧ B, A ∨ B, ¬A, ∀yA, et ∃yAsi y 6= x

Formule closeUne formule est close lorsque toutes les occurrences des variables qui yfigurent sont liees



Variables libres et liees 2/3

F1 : Q(a, f (x))

Formule atomique comportant une occurrence de x, x est donclibre.

F2 : ∀z Q(a, f (x))

F2 = ∀z F1, comme z 6= x , le fait que x soit libre dans F1 entraineque x est libre dans F2.

F3 : ∀x ∀y Q(x , y)→ ∃z P(z)

F3 est une formule close (x et y liees par ∀ et z liee a ∃).

F4 : Q(b,b)→ ∀x (P(x) ∨ ∃x Q(x , y))

y est libre.∀x ne peut lier qu’une variable libre c’est a dire x dans P(x).L’occurrence de x dans Q(x , y) est elle liee par ∃x .Donc les deux variables x sont liees (mais differemment).



Variables libres et liees 3/3

RemarquesUne variable liee ne possede pas d’identite propre et peut etreremplacee par n’importe quel autre nom de variable quin’apparaıt pas dans la formule.∀x A(x) est identique a ∀y A(y)

Pour eviter les ambiguıtes, mieux vaut utiliser des noms devariables differents.

ExempleSoit F : x < y → ∀x (x = y ∨ ∃y y < x)

Les variables x , y sont a la fois libres et liees. Il vaut mieuxrenommer les occurrences :F : x < y → ∀z (z = y ∨ ∃t t < z)



Semantique

But de la semantiqueDonner un sens a une formule de la logique des predicats etdecider ensuite si elle est vraie ou fausse.Il faut indiquer :

A quoi referent les objets (constantes, variables et termes) de laformule.A quoi renvoient les symboles de predicats et de fonctions de laformule.

Plusieurs etapesIl faut decider du modele (le langage).L’interpretation (la realisation) du langage.La valuation (trouver la valeur de verite).



Semantique : interpretation

Soit “Richard est le frere Jean”

Le modele (domaine) :RichardJeanLa relation de fraternite

Interpretation :La constante R renvoie a RichardLa constante J renvoie a JeanLe predicat F renvoie a la relation de fraternite



Exemple d’interpretation

Soit la formule :∀x(A(x) ∧ B(f (x), a)), definie sur le domaine ∆ = {4, 5}.

A et B sont des predicats, f est une fonction, x une variable et a une constante.

Voici une premiere interpretation I1

I1c [a] = 4.

I1f [f](4) = 5, I1

f [f](5) = 4.

I1p [A](4) = V, I1

p [A](5) = F.

I1p [B](4,4) = V, I1

p [B](5,4) = V.

Voici une seconde interpretation I2

I2c [a] = 5.

I2f [f](4) = 5, I2

f [f](5) = 4.

I2p [A](4) = F, I2

p [A](5) = V.

I2p [B](4,5) = V, I2

p [B](5,5) = F.



Valuation

Comme dans la logique des propositions, les formules ont une valeurde verite qui dependent de l’interpretation choisie. Cette valeur deverite est etablie comme suit :

La valeur de verite d’une formule atomique est la valeur de veritedu predicat selon l’interpretation I.La valeur de verite d’une formule contenant des variablesquantifiees est :

si F = ∃x G, la valeur de F sera vraie si la valeur de G selon I estvraie pour au moins une valeur de x ∈ ∆, sinon la valeur de F estfausse.si F = ∀x G, la valeur de F sera vraie si la valeur de G selon I estvraie pour toutes les valeurs de x ∈ ∆, sinon la valeur de F estfausse.

La valeur de verite d’une formule non atomique construite apartir de formules atomiques, est calculee au moyen des tablesde verite des connecteurs.



Exemple de valuation

Soit l’exemple precedent : ∀x (A(x) ∧ B(f (x),a)), definie sur ledomaine ∆ = {4,5} avec l’interpretation I1 :

I1c [a] = 4.I1

f [f](4) = 5, I1f [f](5) = 4.

I1p [A](4) = V, I1

p [A](5) = F.

I1p [B](4,4) = V, I1

p [B](5,4) = V.

Apres valuation, on obtient la table de verite suivante :





I1c [a] = 4.I1

f [f](4) = 5, I1f [f](5) = 4.

I1p [A](4) = V, I1

p [A](5) = F.

I1p [B](4,4) = V, I1

p [B](5,4) = V.


x A(x) f (x) B(f (x),a) A(x) ∧ B(f (x),a)

4 V 5 V V5 F 4 V F





I1c [a] = 4.I1

f [f](4) = 5, I1f [f](5) = 4.

I1p [A](4) = V, I1

p [A](5) = F.

I1p [B](4,4) = V, I1

p [B](5,4) = V.


x A(x) f (x) B(f (x),a) A(x) ∧ B(f (x),a)

4 V 5 V V5 F 4 V F

∀ x (A(x) ∧ B(f (x), a)) : Faux



Validite et satisfiabilite

Formule satisfiableUne formule vraie pour au moins une interpretation du modele

Formule valideUne formule vraie pour toutes les interpretations possibles du modele

ExempleSoit la formule ∀x A(x) ∨ ∃y A(y) sur ∆ = {1,2} Elle possede 4interpretations possibles :



Validite et satisfiabilite

Formule satisfiableUne formule vraie pour au moins une interpretation du modele

Formule valideUne formule vraie pour toutes les interpretations possibles du modele

ExempleSoit la formule ∀x A(x) ∨ ∃y A(y) sur ∆ = {1,2} Elle possede 4interpretations possibles :

I1p [A](1) = V , I1

p [A](2) = V

I2p [A](1) = V , I2

p [A](2) = F

I3p [A](1) = F , I3

p [A](2) = V

I4p [A](1) = F , I4

p [A](2) = F



Exemple de satisfiabilite

x y A(x) A(y) ∀ x A(x) ∃ y A(y) ∀ x A(x) ∨ ∃ y A(y)



Exemple de satisfiabilitex y A(x) A(y) ∀ x A(x) ∃ y A(y) ∀ x A(x) ∨ ∃ y A(y)

I1

1 1 V V

V V V1 2 V V2 1 V V2 2 V V

I2

1 1 V V

F V V1 2 V F2 1 F V2 2 F F

I3

1 1 F F

F V V1 2 F V2 1 V F2 2 V V

I4

1 1 F F

F F F1 2 F F2 1 F F2 2 F F



Substitution 1/2

DefinitionSubstituer une variable xi par un terme ti avec xi 6= ti .On note :

θ = {x1/t1, . . . , xn/tn}sub(θ, t) : appliquer la substitution θ au terme t

Exemplet = g(x , y , f (x , y))

θ = {x/a, y/f (x ,a)} : substituer les variables x et y par a etf (x , y).



Substitution 1/2





t ′ = Sub(θ, t) = g(a, f(x,a),f(a,f(x,a)))

Si on applique une deuxieme fois la meme substitution :



Substitution 1/2





t ′ = Sub(θ, t) = g(a, f(x,a),f(a,f(x,a)))

Si on applique une deuxieme fois la meme substitution :t ′′ = Sub(θ, t ′) = g(a,f(a,a), f(a,f(a,a)))



Substitution 2/2

Remarque 1Le terme t peut contenir des variables qui peuvent se retrouverquantifiees (liees) une fois la substitution faite. Il faut dans ce casfaire attention et renommer les variables de sorte a ce que toutes lesvariables de t restent libres dans F .

Remarque 2Il ne faut pas confondre ces substitutions avec les interpretations. Lasubstitution remplace syntaxiquement une variable par un terme pourproduire un nouvel enonce, alors qu’une interpretation faitcorrespondre une variable a un objet du domaine.



UnificationDefinition

Deux formules sont unifiables s’il existe une substitution desvariables qui les rendent identiques.Unifier deux formules : les rendre identiques en leur appliquantune substitution.

ExemplesPeut on unifier F1 : A(x ,g(b, x)) et F2 : A(a,g(y ,b)) ?

θ = {x/a, y/b}Sub(θ, F1) = A(a, g(b, a))Sub(θ, F2) = A(a, g(b, b))F1 et F2 ne sont pas unifiables.

Peut on unifier F3 : A(x ,a, z) et F4 : A(c,a, y)) ?θ = {x/c, y/z}Sub(θ, F3) = A(c, a, z)Sub(θ, F4) = A(c, a, z)F3 et F4 sont unifiables.



Principe de resolutionDefinitionComme pour la logique des propositions, on peut appliquer laresolution pour deduire des enonces a partir de faits.

Pour la logique des propositionsA partir de (p1 ∨ . . . ∨ pm),(q1 ∨ . . . ∨ qn), si pi = ¬qj , on deduit :(p1 ∨ . . . ∨ pi−1 ∨ pi+1 ∨ . . . ∨ pm ∨ q1 ∨ . . . ∨ qj−1 ∨ qj+1 ∨ . . . ∨ qn)

Pour la logique des predicatsA partir de (p1 ∨ . . . ∨ pm),(q1 ∨ . . . ∨ qn), si pi et ¬qj sont unifiablespar θ on deduit :(p1 ∨ . . . ∨ pi−1 ∨ pi+1 ∨ . . . ∨ pm ∨ q1 ∨ . . . ∨ qj−1 ∨ qj+1 ∨ . . . ∨ qn)

ExempleF1 = Animal(x) ∨ Aimer(g(x), x)

F2 = ¬Aimer(u, v) ∨ ¬Tuer(u, v)

Avec θ = {u/g(x), v/x} on unifie F1 et F2,et on deduit Animal(x) ∨ ¬Tuer(g(x), x)



Forme normale conjonctive

Pour faire une resolution les formules doivent etre en CNF.

Transformation en CNF1 Elimination des implications et des equivalences2 Reecrire en forme prenexe (mettre les quantificateurs en debut)3 Skolemisation (suppression du ∃)4 Suppression des quantificateurs universels (∀)5 Distribution de ∨ sur ∧

∀x(∀y Animal(y)⇒ Aimer(x , y))⇒ (∃y Aimer(y , x))



1. Elimination des implications

Comme en logique propositionnelle : P ⇒ Q ≡ ¬P ∨Q

∀x(∀yAnimal(y)⇒Aimer(x , y))⇒ (∃yAimer(y , x))

∀x(∀y¬Animal(y)∨Aimer(x , y))⇒ (∃yAimer(y , x))

∀x(∀y¬Animal(y) ∨ Aimer(x , y))⇒(∃yAimer(y , x))

∀x(∃yAnimal(y) ∧ ¬Aimer(x , y))∨(∃yAimer(y , x))



2. Mettre sous forme prenexe

DefinitionUne forme prenexe est une formule de la forme Q1x1 . . .QdxdM avecQi un quantificateur et M une formule sans quantificateur. Pour celaon utilise les equivalences suivantes :

¬∀p ≡ ∃x¬p.¬∃p ≡ ∀x¬p.(∀xA) ∨ B ≡ ∀x(A ∨ B) ssi x n’est pas liee dans B.(∃xA) ∨ B ≡ ∃x(A ∨ B) ssi x n’est pas liee dans B.(∀xA) ∧ B ≡ ∀x(A ∧ B) ssi x n’est pas liee dans B.(∃xA) ∧ B ≡ ∃x(A ∧ B) ssi x n’est pas liee dans B.

Si x est liee dans B alors il faut renommer x avec une substitution.



2. Mettre sous forme prenexe

∀x(∃yAnimal(y) ∧ ¬Aimer(x , y)) ∨ (∃yAimer(y , x))

∀x(∃yAnimal(y) ∧ ¬Aimer(x , y)) ∨ (∃zAimer(z, x))

∀x(∃yAnimal(y) ∧ ¬Aimer(x , y)) ∨ (∃zAimer(z, x))

∀x∃y∃z(Animal(y) ∧ ¬Aimer(x , y)) ∨ Aimer(z, x)



3. Skolemisation

DefinitionIl s’agit de supprimer les quantificateurs existentiels en les remplacantavec une constante ou un terme qui ne sont pas dans le domaine.Il y a deux possibilites :

∃x∀yA(x , y) devient ∀yA(a, y) (remplace par la constante a).∀y∃xA(x , y) devient ∀yA(f (y), y) (remplace par le terme f (y). fest appele fonction de Skolem).

Attention les deux formules ne sont pas equivalentes, mais si ondeduit G de la premiere alors on peut la deduire de la seconde.



3. Skolemisation

∀x∃y∃z(Animal(y) ∧ ¬Aimer(x , y)) ∨ Aimer(z, x)

∀x∃y(Animal(y) ∧ ¬Aimer(x , y)) ∨ Aimer(g(x), x)

∀x∃y(Animal(y) ∧ ¬Aimer(x , y)) ∨ Aimer(g(x), x)

∀x(Animal(f (x)) ∧ ¬Aimer(x , f (x))) ∨ Aimer(g(x), x)



4. Suppression des quantificateurs universels

Comme toutes les variables sont maintenant universellementquantifiees on peut supprimer les ∀ (ils deviennent implicites).

∀x(Animal(f (x)) ∧ ¬Aimer(x , f (x))) ∨ Aimer(g(x), x)

(Animal(f (x)) ∧ ¬Aimer(x , f (x))) ∨ Aimer(g(x), x)



5. Distribution de ∨ sur ∧

Comme pour la logique des propositions :(P ∧Q) ∨ R ≡ (P ∨ R) ∧ (Q ∨ R)

(Animal(f (x)) ∧ ¬Aimer(x , f (x))) ∨ Aimer(g(x), x)

(Animal(f (x)) ∨ Aimer(g(x), x)) ∧ (¬Aimer(x , f (x)) ∨Aimer(g(x), x))

La formule est en CNF. Elle comporte deux clauses :(Animal(f (x)) ∨ Aimer(g(x), x))

(¬Aimer(x , f (x)) ∨ Aimer(g(x), x))



Exemple

FaitsLes personnes qui ont la grippe A doivent prendre du TamifluLes personnes qui ont de la fievre et qui toussent ont la grippe ACeux qui ont une temperature superieure a 38˚ ont de la fievrePierre tousse et a une temperature superieure a 38˚

Peut-on deduire quePierre doit prendre du Tamiflu



Exemple 1Faits

Pour tout crime, il y a quelqu’un qui l’a commis.Seuls les malhonnetes commettent des crimes.Ne sont arretes que les gens malhonnetes.Les gens malhonnetes arretes ne commettent pas de crimes.Il y a des crimes.

QuestionIl y a des gens malhonnetes non arretes.

Codage en predicatsx est un crime : Crime(x).x a commis y : Commis(x,y).x est malhonnete : Malhonnete(x).x est arrete : Arrete(x).



Exemple 1

FaitsPour tout crime, il y a quelqu’un qui l’a commis.Seuls les malhonnetes commettent des crimes.Ne sont arretes que les gens malhonnetes.Les gens malhonnetes arretes ne commettent pas de crimes.Il y a des crimes.



Exemple 1

FaitsPour tout crime, il y a quelqu’un qui l’a commis.∀x(Crime(x)⇒ ∃yCommis(y , x)). (F1)Seuls les malhonnetes commettent des crimes.Ne sont arretes que les gens malhonnetes.Les gens malhonnetes arretes ne commettent pas de crimes.Il y a des crimes.



Exemple 1

FaitsPour tout crime, il y a quelqu’un qui l’a commis.∀x(Crime(x)⇒ ∃yCommis(y , x)). (F1)Seuls les malhonnetes commettent des crimes.∀x , y(Crime(x) ∧ Commis(y , x)⇒ Malhonnete(y)). (F2)Ne sont arretes que les gens malhonnetes.Les gens malhonnetes arretes ne commettent pas de crimes.Il y a des crimes.



Exemple 1

FaitsPour tout crime, il y a quelqu’un qui l’a commis.∀x(Crime(x)⇒ ∃yCommis(y , x)). (F1)Seuls les malhonnetes commettent des crimes.∀x , y(Crime(x) ∧ Commis(y , x)⇒ Malhonnete(y)). (F2)Ne sont arretes que les gens malhonnetes.∀x(Arrete(x)⇒ Malhonnete(x)). (F3)Les gens malhonnetes arretes ne commettent pas de crimes.Il y a des crimes.



Exemple 1

FaitsPour tout crime, il y a quelqu’un qui l’a commis.∀x(Crime(x)⇒ ∃yCommis(y , x)). (F1)Seuls les malhonnetes commettent des crimes.∀x , y(Crime(x) ∧ Commis(y , x)⇒ Malhonnete(y)). (F2)Ne sont arretes que les gens malhonnetes.∀x(Arrete(x)⇒ Malhonnete(x)). (F3)Les gens malhonnetes arretes ne commettent pas de crimes.∀x , y(Malhonnete(x) ∧ Arrete(x) ∧ Crime(y)⇒ ¬Commis(x , y)).(F4)Il y a des crimes.



Exemple 1

FaitsPour tout crime, il y a quelqu’un qui l’a commis.∀x(Crime(x)⇒ ∃yCommis(y , x)). (F1)Seuls les malhonnetes commettent des crimes.∀x , y(Crime(x) ∧ Commis(y , x)⇒ Malhonnete(y)). (F2)Ne sont arretes que les gens malhonnetes.∀x(Arrete(x)⇒ Malhonnete(x)). (F3)Les gens malhonnetes arretes ne commettent pas de crimes.∀x , y(Malhonnete(x) ∧ Arrete(x) ∧ Crime(y)⇒ ¬Commis(x , y)).(F4)Il y a des crimes.∃x(Crime(x)). (F5)



Exemple 1

ButIl y a des gens malhonnetes non arretes.

On cherche a montrer{F1,F2,F3,F4,F5,¬Q} |= ∅



Exemple 1

ButIl y a des gens malhonnetes non arretes.∃x(Malhonnete(x) ∧ ¬Arrete(x)), (Q).∀x(¬(Malhonnete(x) ∧ ¬Arrete(x))), (¬Q).

On cherche a montrer{F1,F2,F3,F4,F5,¬Q} |= ∅



Exemple 1

Traduction en CNFPour tout crime, il y a quelqu’un qui l’a commis.∀x(¬Crime(x) ∨ ∃yCommis(y , x)). (F1)∀x∃y(¬Crime(x) ∨ Commis(y , x)).∀x(¬Crime(x) ∨ Commis(f (x), x)).¬Crime(x) ∨ Commis(f (x), x). (F1)



Exemple 1

Traduction en CNFSeuls les malhonnetes commettent des crimes.∀x , y(Crime(x) ∧ Commis(y , x)⇒ Malhonnete(y)). (F2)∀x , y(¬(Crime(x) ∧ Commis(y , x)) ∨Malhonnete(y)).(¬Crime(x) ∨ ¬Commis(y , x) ∨Malhonnete(y)). (F2)



Exemple 1

Traduction en CNFNe sont arretes que les gens malhonnetes.∀x(Arrete(x)⇒ Malhonnete(x)). (F3)∀x(¬Arrete(x) ∨Malhonnete(x)).¬Arrete(x) ∨Malhonnete(x). (F3).



Exemple 1

Traduction en CNFLes gens malhonnetes arretes ne commettent pas de crimes.∀x , y(Malhonnete(x) ∧ Arrete(x) ∧ Crime(y)⇒ ¬Commis(x , y)).(F4)∀x , y(¬(Malhonnete(x)∧Arrete(x)∧Crime(y))∨¬Commis(x , y)).∀x , y(¬Malhonnete(x) ∨ ¬Arrete(x) ∨ ¬Crime(y) ∨¬Commis(x , y)).

x , y(¬Malhonnete(x) ∨ ¬Arrete(x) ∨ ¬Crime(y) ∨ ¬Commis(x , y)).(F4).



Exemple 1

Traduction en CNFIl y a des crimes.∃x(Crime(x)). (F5).(Crime(C1)). (F5).



Exemple 1

Traduction en CNFIl y a des gens malhonnetes non arretes.∀x(¬(Malhonnete(x) ∧ ¬Arrete(x))), ¬(Q)

∀x(¬Malhonnete(x) ∨ Arrete(x))

¬Malhonnete(x) ∨ Arrete(x), (¬Q)



Exemple 1

¬Crime(x) ∨ Commis(f (x), x). (F1)¬Crime(x) ∨ ¬Commis(y , x) ∨Malhonnete(y). (F2)¬Arrete(x) ∨Malhonnete(x). (F3)¬Malhonnete(x) ∨ ¬Arrete(x) ∨ ¬Crime(y) ∨ ¬Commis(x , y).(F4)Crime(C1). (F5)¬Malhonnete(x) ∨ Arrete(x). (¬Q)


Documents

Rym Guibadj, Fabien Teytaud - LISICguibadj/IA1/cours3.pdfLa constante R renvoie a Richard` La constante J renvoie a Jean` Le predicat F renvoie´ a la relation de fraternit` e´ Rym