Logique Mathématique Exam

Cet examen de logique mathématique évalue les compétences en syntaxe formelle, en raisonnement logique, en résolution par principe de résolution, ainsi qu'en modélisation et déduction dans le cadre de la logique des prédicats.

Exercice 1

Il s'agit de déterminer, pour chaque expression donnée, si elle est une formule du langage L = {X, F, R} défini par :

• X : ensemble des variables
• R : ensemble des relations avec P unaire et R binaire
• F : ensemble des fonctions avec f unaire, g binaire et c constante

Pour chaque expression correcte, préciser si c’est un terme, une formule atomique ou une formule bien formée, et pour chaque occurrence de variable, dire si elle est liée ou libre.

Les expressions données sont (certaines sont incomplètes dans le texte, mais nous traitons celles lisibles) :

• b) P(x)
• e) P(R(x,y))
• d) (y x R) (x f x P) (∀ ∧ ∃) (expression partielle)
• f) (y x g) (x y g R) (expression partielle)
• g) (c y g x f R) (expression partielle)

Nous analysons celles clairement identifiables :

b) P(x)

Analyse :

• P est un symbole de relation unaire (prédicat unaire).
• x est une variable.
• P(x) est donc une formule atomique (relation appliquée à un terme).
• x est une variable libre car aucune quantification ne la lie.

Conclusion : P(x) est une formule atomique avec x libre.

e) P(R(x,y))

Analyse :

• R est un symbole de relation binaire, donc R(x,y) est une formule atomique.
• Or, P est un prédicat unaire qui doit s’appliquer à un terme, pas à une formule.
• R(x,y) n’est pas un terme mais une formule, donc P(R(x,y)) n’est pas syntaxiquement correct.

Conclusion : P(R(x,y)) n’est pas une formule de L.

Expressions partielles (d, f, g)

Les expressions sont incomplètes et brouillées dans le texte, ce qui empêche une analyse précise. Il n’est donc pas possible de conclure sur leur validité syntaxique ni leur classification.

Exercice 2

On doit prouver, par le principe de résolution, que John aime les chips, à partir des assertions :

• John aime toutes les sortes de nourriture.
• Tout ce que quelqu'un mange et qui ne le tue pas est de la nourriture.
• Bill mange des chips et cela ne l’a pas tué.

Constantes : John, Bill, Chips

Prédicats :

• A(x,y) : x aime y
• M(x,y) : x mange y
• T(x,y) : x tue y
• N(x) : x est de la nourriture

Étape 1 : Traduction en logique des prédicats

• John aime toutes les sortes de nourriture :

∀y (N(y) → A(John,y))

• Tout ce que quelqu'un mange et qui ne le tue pas est de la nourriture :

∀x ∀y ((M(x,y) ∧ ¬T(x,y)) → N(y))

• Bill mange des chips et cela ne l’a pas tué :

M(Bill,Chips) ∧ ¬T(Bill,Chips)

Étape 2 : Objectif

Montrer que John aime les chips :

A(John,Chips)

Étape 3 : Mise en forme pour résolution

Nous transformons les formules en forme normale conjonctive (FNC) et en clauses :

• ∀y (¬N(y) ∨ A(John,y)) → clause : ¬N(y) ∨ A(John,y)
• ∀x ∀y (¬M(x,y) ∨ T(x,y) ∨ N(y)) → clause : ¬M(x,y) ∨ T(x,y) ∨ N(y)
• M(Bill,Chips)
• ¬T(Bill,Chips)

Étape 4 : Ajout de la négation de la conclusion

Pour prouver A(John,Chips), on ajoute ¬A(John,Chips) et on cherche une contradiction.

Étape 5 : Résolution

• Clause 1 : ¬N(y) ∨ A(John,y)
• Clause 2 : ¬M(x,y) ∨ T(x,y) ∨ N(y)
• Clause 3 : M(Bill,Chips)
• Clause 4 : ¬T(Bill,Chips)
• Clause 5 : ¬A(John,Chips) (négation de la conclusion)

Substitution : y = Chips, x = Bill

• De la clause 3 et 4, on a M(Bill,Chips) et ¬T(Bill,Chips)
• Clause 2 devient : ¬M(Bill,Chips) ∨ T(Bill,Chips) ∨ N(Chips)
• En substituant M(Bill,Chips) vrai et ¬T(Bill,Chips) vrai, la clause 2 réduit à N(Chips)
• Clause 1 avec y=Chips : ¬N(Chips) ∨ A(John,Chips)
• Or, on a N(Chips) vrai, donc ¬N(Chips) faux, donc A(John,Chips) doit être vrai.
• Mais on a la négation ¬A(John,Chips) (clause 5), contradiction.

Conclusion : Par résolution, on prouve que John aime les chips.

Exercice 3

Il s'agit d'analyser les affirmations contradictoires de trois juges (Nikolaï, Omar, Peter) face à trois candidates (Laetitia, Patricia, Surya) pour déterminer si elles sont qualifiées, en utilisant la logique propositionnelle.

1 — Cas de Laetitia

Affirmations :

• Nikolaï : "L'un de nous au moins va vous mentir."
• Omar : "Vous êtes qualifiée, toutes mes félicitations !"
• Peter : "Nikolaï a dit la vérité."

Laetitia conclut qu'elle est qualifiée. Vérifions si cette conclusion est cohérente.

Analyse

Posons Q : Laetitia est qualifiée.

Posons V(x) : x dit la vérité.

• Nikolaï : "Au moins un de nous ment" → ¬(V(Nikolaï) ∧ V(Omar) ∧ V(Peter)) → au moins un est faux.
• Omar : "Vous êtes qualifiée" → Q
• Peter : "Nikolaï a dit la vérité" → V(Nikolaï)

Peter affirme que Nikolaï dit la vérité, donc V(Peter) → V(Nikolaï).

Si Nikolaï dit la vérité, alors au moins un ment, ce qui est vrai puisque il y a au moins un menteur.

Supposons que Omar dit la vérité (V(Omar)) alors Q est vrai (Laetitia est qualifiée).

Peter dit que Nikolaï dit la vérité, donc V(Peter) → V(Nikolaï).

Si tous trois disaient la vérité, cela contredirait Nikolaï (qui dit qu'au moins un ment). Donc au moins un ment.

Si Omar ment, alors Q est faux (Laetitia non qualifiée), ce qui contredirait la joie de Laetitia.

Conclusion : Laetitia est qualifiée, et il y a au moins un menteur parmi les juges.

Conclusion : Laetitia a raison d’affirmer qu’elle est qualifiée, mais au moins un juge ment.

2 — Cas de Patricia

Affirmations :

• Nikolaï : "Désolé, vous n'êtes pas qualifiée."
• Omar : "Ne l'écoutez pas, Nikolaï ne dit jamais la vérité."
• Peter : "Je ne sais pas si vous devez croire Omar ! En effet, deux d'entre nous, au moins, vous mentent!"

Patricia croit Nikolaï et repart déçue. Vérifions la cohérence.

Analyse

Posons Q : Patricia est qualifiée.

• Nikolaï : ¬Q
• Omar : "Nikolaï ne dit jamais la vérité" → ¬V(Nikolaï)
• Peter : "Au moins deux d'entre nous mentent" → au moins deux menteurs parmi Nikolaï, Omar, Peter.

Si Nikolaï dit la vérité (V(Nikolaï)), alors Omar ment (car il dit que Nikolaï ment toujours). Mais Peter dit qu'il y a au moins deux menteurs.

Si Nikolaï ment (¬V(Nikolaï)), alors Omar dit la vérité (car il dit que Nikolaï ment toujours). Peter affirme qu'il y a au moins deux menteurs, or si Nikolaï ment et Omar dit la vérité, il faudrait que Peter mente aussi pour avoir deux menteurs.

Patricia croit Nikolaï (donc ¬Q), mais Omar dit que Nikolaï ment toujours (donc Q). Il y a contradiction.

Conclusion : Patricia n’est pas qualifiée (¬Q) si on croit Nikolaï, mais les juges ne sont pas tous cohérents. Peter indique qu’au moins deux juges mentent, ce qui est compatible avec cette situation. Patricia peut être réconfortée par le fait que la logique des juges est incohérente, ce qui relativise son échec.

3 — Cas de Surya

Affirmations :

• Nikolaï : "Peter vous dira la vérité."
• Omar : "Si vous êtes qualifiée, c'est que Nikolaï vous a menti !"
• Peter : "Omar dit la vérité. En tous cas, je vous félicite, vous êtes qualifiée."

Surya est confuse. Trouvons la conclusion logique.

Analyse

Posons Q : Surya est qualifiée.

• Nikolaï : V(Peter)
• Omar : Q → ¬V(Nikolaï)
• Peter : V(Omar) ∧ Q

Peter affirme que Omar dit la vérité et que Surya est qualifiée.

Si Peter dit la vérité, alors Omar dit la vérité et Q est vrai.

Si Omar dit la vérité, alors Q → ¬V(Nikolaï), donc si Q vrai, Nikolaï ment.

Or Nikolaï affirme que Peter dit la vérité, donc si Nikolaï ment, Peter ment, contradiction avec hypothèse.

Il y a donc une contradiction si Q est vrai.

Si Q est faux, alors Omar ment, donc Peter ment (car Peter dit que Omar dit la vérité), donc Nikolaï dit la vérité (car Peter ment). Mais Nikolaï dit que Peter dit la vérité, ce qui est faux si Peter ment. Contradiction.

On obtient un paradoxe, donc aucune des hypothèses ne peut être vraie sans contradiction.

Conclusion : Les affirmations sont contradictoires, il est impossible de conclure de façon certaine si Surya est qualifiée ou non.

Exercice 4

Jean a été tué mardi. Les suspects sont luc, paul, alain, bernard, louis. On doit :

1. Écrire les connaissances en logique des prédicats.
2. Déterminer qui a tué Jean mardi.

1 — Formalisation des connaissances

Prédicats :

• Alibi(x, jour) : x a un alibi pour le jour donné
• Douteux(x) : x est douteux
• DésireTuer(x, Jean) : x désire tuer Jean
• IntérêtTuer(x, Jean) : x a intérêt à tuer Jean
• Héritier(x, Jean) : x est héritier de Jean
• DoitArgent(x, Jean) : x doit de l’argent à Jean
• AvuCommisCrime(x) : Jean a vu x commettre un crime
• PossèdeArme(x) : x possède une arme
• Assassin(x) : x est l’assassin de Jean

Règles :

• Un alibi donné par quelqu’un de douteux n’est pas pris en compte :

∀x ∀y (Alibi(x,y) ∧ ¬Douteux(donneur) → AlibiValide(x,y))

Mais on ne connaît pas explicitement les donneurs d’alibi, on suppose que si alibi donné par douteux, il est invalide.

• Quelqu’un peut désirer tuer Jean s’il a intérêt ou s’il désire se venger :

∀x (DésireTuer(x,Jean) ↔ (IntérêtTuer(x,Jean) ∨ DésireVengeance(x,Jean)))

• Quelqu’un a intérêt à tuer Jean s’il est héritier, ou s’il lui doit de l’argent, ou si Jean l’a surpris en train de commettre un crime :

∀x (IntérêtTuer(x,Jean) ↔ (Héritier(x,Jean) ∨ DoitArgent(x,Jean) ∨ AvuCommisCrime(x)))

• L’assassin est quelqu’un qui peut désirer tuer Jean, qui possède une arme et qui n’a pas d’alibi valide pour mardi :

∀x (Assassin(x) ↔ (DésireTuer(x,Jean) ∧ PossèdeArme(x) ∧ ¬AlibiValide(x,mardi)))

Faits :

• Alibi(luc,mardi) donné par bernard
• Alibi(paul,mardi) donné par bernard
• Alibi(louis,mardi) donné par luc
• Alibi(alain,jeudi) donné par luc
• Douteux(alain)
• DésireVengeance(paul,Jean)
• DésireVengeance(luc,Jean)
• Héritier(bernard,Jean)
• Héritier(Jean,louis)
• DoitArgent(louis,Jean)
• DoitArgent(luc,Jean)
• AvuCommisCrime(alain)
• PossèdeArme(luc)
• PossèdeArme(louis)
• PossèdeArme(alain)

2 — Détermination de l’assassin

Étape 1 : Valider les alibis

• Alibi(luc,mardi) donné par bernard. Bernard est-il douteux ? Non (pas indiqué).
• Alibi(paul,mardi) donné par bernard. Même raisonnement.
• Alibi(louis,mardi) donné par luc. Luc douteux ? Non indiqué.
• Alibi(alain,jeudi) donné par luc. Jour différent (jeudi), donc pas pertinent pour mardi.

Donc :

• AlibiValide(luc,mardi) = vrai
• AlibiValide(paul,mardi) = vrai
• AlibiValide(louis,mardi) = vrai
• AlibiValide(alain,mardi) = faux (pas d’alibi mardi)

Étape 2 : Désir de tuer Jean

• DésireVengeance(paul,Jean) vrai → DésireTuer(paul,Jean) vrai
• DésireVengeance(luc,Jean) vrai → DésireTuer(luc,Jean) vrai
• IntérêtTuer(bernard,Jean) car héritier → DésireTuer(bernard,Jean) vrai
• IntérêtTuer(louis,Jean) car doit de l’argent → DésireTuer(louis,Jean) vrai
• IntérêtTuer(alain,Jean) car Jean a vu alain commettre un crime → DésireTuer(alain,Jean) vrai

Étape 3 : Possession d’arme

• PossèdeArme(luc) vrai
• PossèdeArme(louis) vrai
• PossèdeArme(alain) vrai
• PossèdeArme(paul) non indiqué (donc faux)
• PossèdeArme(bernard) non indiqué (faux)

Étape 4 : Alibi valide mardi

• luc : alibi valide mardi
• paul : alibi valide mardi
• louis : alibi valide mardi
• alain : pas d’alibi mardi
• bernard : pas d’alibi mardi (non mentionné)

Étape 5 : Conditions pour être assassin :

DésireTuer(x,Jean) ∧ PossèdeArme(x) ∧ ¬AlibiValide(x,mardi)

• luc : désire tuer (oui), possède arme (oui), alibi valide (oui) → exclu
• paul : désire tuer (oui), possède arme (non), alibi valide (oui) → exclu
• louis : désire tuer (oui), possède arme (oui), alibi valide (oui) → exclu
• alain : désire tuer (oui), possède arme (oui), alibi valide (non) → suspect
• bernard : désire tuer (oui), possède arme (non), alibi valide (non) → exclu

Conclusion : Seul alain satisfait toutes les conditions pour être l’assassin de Jean mardi.

Méthode

Ce sujet récompense :

• La rigueur dans l’analyse syntaxique des formules et la distinction claire entre termes, formules atomiques et formules bien formées, ainsi que la compréhension des variables libres et liées.
• La maîtrise de la traduction des énoncés en logique des prédicats, notamment la capacité à formaliser correctement les assertions et à manipuler la forme normale conjonctive pour appliquer la résolution.
• La capacité à raisonner logiquement dans des situations complexes, notamment en logique propositionnelle, en analysant la cohérence des affirmations contradictoires et en déduisant des conclusions valides ou en identifiant des paradoxes.
• La modélisation précise des connaissances dans un contexte d’enquête, en respectant les règles données et en appliquant les définitions pour déduire des conclusions sur les suspects.

Les erreurs pénalisées sont notamment :

• Confusion entre termes et formules, ou mauvaise identification des variables libres et liées.
• Traduction incorrecte ou incomplète des énoncés en logique formelle.
• Omissions dans les étapes de résolution ou absence de justification des déductions.
• Conclusions hâtives sans vérification de la cohérence des hypothèses.