Introduction à la logique
Correction des exercices

Auteur : Antoine Zimmermann

Tronc commun informatique – Mines Saint-Étienne

Ces corrections ont été rédigées par Antoine Zimmermann sur des suggestions de réponses de Gauthier Picard (anciennement Mines Saint-Étienne).

 

Table des matières

  1. Logique des propositions
    1. Exercice 1.6.1
    2. Exercice 1.6.2
    3. Exercice 1.6.3
    4. Exercice 1.6.4
    5. Exercice 1.6.5
    6. Exercice 1.6.6
    7. Exercice 1.6.7
    8. Exercice 1.6.8
  2. Logique des prédicats (du premier ordre)
    1. Exercice 2.5.1
    2. Exercice 2.5.2
    3. Exercice 2.5.3
    4. Exercice 2.5.4
    5. Exercice 2.5.5
    6. Exercice 2.5.6
    7. Exercice 2.5.7
  3. Principe de résolution
    1. Exercice 3.5.1
    2. Exercice 3.5.2
    3. Exercice 3.5.3
    4. Exercice 3.5.4
    5. Exercice 3.5.5
    6. Exercice 3.5.6

Logique des propositions

En utilisant les atomes S (le soleil brille), P (il pleut), B (il bruine), A (il y a un arc en ciel), O (il a un vent d’Ouest), E (il y a du vent d’Est), traduire dans la logique des propositions 𝓛0 les énoncés suivants :

  1. S’il pleut et que le soleil brille en même temps, alors il y a un arc en ciel,
  2. Si le vent d’ouest amène la pluie, on n’a jamais vu qu’un vent d’est soit porteur de pluie,
  3. La bruine est une forme de pluie.

Les formules suivantes peuvent modéliser les 3 phrases de l’énoncé. La phrase (b) est difficile à modéliser complètement car elle cache une relation de causalité. Si le vent d’est n’apporte pas la pluie (le vent d’est n’est pas la cause de la pluie), cela ne veut pas forcément dire qu’il ne pleut pas lorsqu’il y a un vent d’est. Mais s’il peut pleuvoir lorsqu’il y a un vent d’est, alors on ne peut rien dire sur le sujet en logique propositionnelle. En revanche, il serait faux d’écrire ((O → P) ∧ ¬(E → P)) car cela implique logiquement qu’il ne pleut pas, nécessairement. Autrement dit, cette dernière modélisation décrit un monde où il ne peut pas pleuvoir.

  1. ((S ∧ P) → A)
  2. ((O → P) ∧ (E → ¬P))
  3. (B → P)

Représenter dans le formalisme de la logique des propositions les théorèmes de géométrie suivants :

  1. Si un triangle est équilatéral alors il est isocèle.
  2. Un triangle rectangle n’est jamais équilatéral.
  3. Un carré est à la fois un parallélogramme et un rectangle.
  4. Un losange n’est ni un quadrilatère rectangle ni un triangle.
  5. Deux droites coplanaires sont soit sécantes, soit parallèles.
  6. Deux droites ne peuvent être à la fois sécantes et parallèles.

Pour cet exercice, il faut définir des propositions. Si on les définit de façon naïve, on peut aboutir à des aberrations. « être isocèle » n’est pas une affirmation. « Un triangle est isocèle » est une affirmation mais dépend de quel triangle on parle (ou bien cela signifie-t-il « l’un des triangles est isocèle » ? ou encore « il existe un triangle isocèle » ?). On considèrera donc une forme géométrique donnée et on considèrera les proposition : tequi pour « la forme est un triangle équilatéral » ; tiso pour « la forme est un triangle isocèle » ; trec pour « la forme est un triangle rectangle » ; carr pour « la forme est un carré » ; pgram pour « la forme est un parallélogramme » ; rect pour « la forme est un rectangle » ; los pour « la forme est un losange » ; qrec pour « la forme est un quadrilatère rectangle » ; tri pour « la forme est un triangle » ; cop pour « la forme est deux droites coplanaires » ; sec pour « la forme est deux droites séquantes » ; para pour « la forme est deux droites parallèles ».

  1. (tequi → tiso)
  2. (trec → ¬tequi)
  3. (carr → (pgram ∧ rect))
  4. (los → (¬qrec ∧ ¬tri))
  5. (cop → ((sec ∧ ¬para) ∨ (¬sec ∧ para)))
  6. ¬(sec ∧ para)

Dans le cas où l’on voudrait s’intéresser aux propriétés de plusieurs formes géométriques, par exemple d’un millier de triangles, pour savoir lesquelles sont de tel ou tel type, il faudrait introduire autant de formules propositionnelles qu’il y a de formes. Par exemple, pour des triangles t1, …, t1000, il faudrait écrire (tequit1 → tisot1), …, (tequit1000 → tisot1000). Chaque nouvelle forme introduite dans le système devrait être accompagnée d’une telle formule. À la place, on aimerait pouvoir écrire que « pour tout triangle t, (tequit → tisot) », mais pour être totalement général, il faudrait une infinité de formules propositionnelles. C’est pourquoi la logique propositionnelle n’est pas suffisante et qu’on introduit la logique du premier ordre dans le chapitre suivant.

Formaliser dans 𝓛0 les propositions suivantes :

  1. Si Alice et Julie viennent à Paris, Zoé viendra aussi ;
  2. Si Julie vient à Paris, Alice aussi ;
  3. Julie ou Zoé, l’une des deux au moins, viendra à Paris.

Alice viendra-t-elle à Paris ? Et Julie ? Et Zoé ?

Soient les variables propositionnelles :

  • a : « Alice vient à Paris »
  • j : « Julie vient à Paris »
  • z : « Zoé vient à Paris »

« Si Alice et Julie viennent à Paris, Zoé viendra aussi » se traduit par a ∧ j → z. « Si Julie vient à Paris, Alice aussi » se traduit par j → a. « Julie ou Zoé, l’une des deux au moins, viendra à Paris » se traduit par j ∨ z.

Les données se traduisent par la formule F = (a ∧ j → z) ∧ (j → a) ∧ (j ∨ z).

Pour savoir si Alice, Julie et Zoé viennent à Paris, nous utilisons la méthode des tables de vérité.

a j z (a ∧ j) (a ∧ j → z) (j → a) (j ∨ z) F
⊥⊥⊥⊥⊤⊤⊥⊥
⊥⊥⊤⊥⊤⊤⊤⊤
⊥⊤⊥⊥⊤⊥⊤⊥
⊥⊤⊤⊥⊤⊥⊤⊥
⊤⊥⊥⊥⊤⊤⊥⊥
⊤⊥⊤⊥⊤⊤⊤⊤
⊤⊤⊥⊤⊥⊤⊤⊥
⊤⊤⊤⊤⊤⊤⊤⊤

On peut en conclure que :

  • Il se peut qu’Alice vienne à Paris ;
  • Il se peut que Julie vienne à Paris ;
  • Il est certain que Zoé viendra à Paris.

Montrer que ((p → r) ∧ (q ↔ s) ∧ (r ↔ q) ∧ p) ⊨ s.

On utilise ici la méthode des tableaux. Cela revient à montrer que l’arbre de racine :

  • (p → r) ∧ (q ↔ s) ∧ (r ↔ q) ∧ p ∧ ¬s

est fermé.

arbre de décision de la méthode des tableaux

Montrer que :

((¬q ∨ ¬s) ∧ (p → s) ∧ (¬p → (r → (q ∧ s))) ∧ ((q ∧ ¬s) → (¬r → (q ∧ p)))) ⊨ ¬q.

On utilise ici la méthode des tableaux. Cela revient à montrer que l’arbre de racine :

  • (¬q ∨ ¬s) ∧ (p → s) ∧ (¬p → (r → (q ∧ s))) ∧ ((q ∧ ¬s) → (¬r → (q ∧ p))) ∧ ¬¬q

est fermé.

arbre de décision de la méthode des tableaux

Construire dans SF0 la preuve de ⊢ ((a → b) → ((b → c) → (a → c))).

D’après le théorème de la déduction, avoir une preuve de ⊢ ((a → b) → ((b → c) → (a → c))) revient à prouver que (a → b) ⊢ ((b → c) → (a → c)). En appliquant à nouveau le théorème de la déduction, cela revient à trouver une preuve de (a → b), (b → c) ⊢ (a → c). En faisant une dernière fois appel au théorème de la déduction, cela revient à trouver une preuve de (a → b), (b → c), a ⊢ c.

On obtient une preuve de c en posant :

  • c1 = aHypothèse
  • c2 = (a → b)Hypothèse
  • c3 = (b → c)Hypothèse
  • c4 = bModus ponens sur c1 et c2
  • c5 = cModus ponens sur c3 et c4

À proprement parler, nous ne construisons pas une preuve de ⊢ ((a → b) → ((b → c) → (a → c))) mais nous démontrons l’existence d’une telle preuve par l’équivalence énoncée par le théorème de la déduction. Si nous avions accès à une preuve constructive du théorème de la déduction, nous pourrions partir de la preuve ci-dessus pour construire la preuve du théorème considéré.

Construire dans SF0 la preuve de ⊢ (¬a → (a → b)).

D’après le théorème de la déduction, avoir une preuve de ⊢ (¬a → (a → b)) revient à prouver que ¬a ⊢ (a → b).

On obtient une preuve de (a → b) en posant :

  • c1 = ¬aHypothèse
  • c2 = (¬a → (¬b → ¬a))Axiome A1 avec A=¬a et B=¬b
  • c3 = (¬b → ¬a)Modus ponens sur c1 et c2
  • c4 = ((¬b → ¬a) → (a → b))Axiome A3 avec A=b et B=a
  • c5 = (a → b)Modus ponens sur c3 et c4

La même remarque que pour l’exercice 1.6.6 vaut pour cet exercice.

Lors de ses aventures au pays des merveilles rapportées par Lewis Carroll, Alice est souvent accompagnée par le chat de Cheshire. Ce félin énigmatique s’exprime sous la forme d’affirmations logiques qui sont toujours vraies. Alice se trouve dans un corridor dont toutes les portes à sa taille sont fermées. La seule porte ouverte est nettement trop petite pour qu’elle puisse l’emprunter. Une étagère est fixée au-dessus de cette porte. Le chat dit alors à Alice : « L’un des flacons posés sur cette étagère contient un liquide qui te permettra de prendre une taille plus adéquate. Mais attention, les autres flacons peuvent contenir un poison fatal. » Trois flacons sont effectivement posés sur l’étagère. Le premier est rouge, le second jaune, le troisième bleu. Une étiquette est collée sur chaque flacon. Alice lit l’inscription figurant sur chaque étiquette :

  • Flacon rouge : le flacon jaune contient un poison ; le bleu n’en contient pas ;
  • Flacon jaune : si le flacon rouge contient un poison, alors le bleu aussi ;
  • Flacon bleu : je ne contiens pas de poison, mais au moins l’un des deux autres si.

Nous noterons R, J et B les variables propositionnelles correspondant au fait que les flacons rouge, jaune et bleu contiennent un poison. Nous noterons IR, IJ et IB les propositions correspondant aux inscriptions sur les flacons rouge, jaune et bleu.

On résoudra les questions suivantes d’abord en utilisant une table de vérité, puis en utilisant des simplifications et règles d’équivalence des formules.

  1. Exprimez les formules IR, IJ et IB sous la forme de formules dépendant de R, J et B.
  2. Les inscriptions sur les trois flacons sont-elles compatibles ?
  3. Dans le cas où aucun des trois flacons ne contient un poison, est-ce qu’une ou plusieurs inscriptions sont fausses ?
  4. Si les trois inscriptions sont vraies, est-ce qu’un ou plusieurs flacons contiennent un poison ?
  5. Si seuls les flacons ne contenant pas un poison ont une inscription vraie, est-ce qu’un ou plusieurs flacons ne contiennent pas un poison ?

Solution de la question (a) : IR, IJ exprimés sous une forme dépendant de R, J et B :

  • IR = J ∧ ¬B
  • IJ = R → B
  • IB = ¬B ∧ (R ∨ J)

Solutions avec une table de vérité

On peut répondre aux questions (b) à (e) en utilisant une table de vérité.

R J B IR IJ IB (IR ∧ IJ) (IJ ∧ IB) (IR ∧ IB) (IR ∧ IJ ∧ IB)
1⊥⊥⊥⊥⊤⊥⊥⊥⊥⊥
2⊥⊥⊤⊥⊤⊥⊥⊥⊥⊥
3⊥⊤⊥⊤⊤⊤⊤⊤⊤⊤
4⊥⊤⊤⊥⊤⊥⊥⊥⊥⊥
5⊤⊥⊥⊥⊥⊤⊥⊥⊥⊥
6⊤⊥⊤⊥⊤⊥⊥⊥⊥⊥
7⊤⊤⊥⊤⊥⊤⊥⊥⊤⊥
8⊤⊤⊤⊥⊤⊥⊥⊥⊥⊥

Solution de la question (b) : Les inscriptions sur les trois flacons sont toutes vraies si et seulement si on se trouve dans les conditions de la ligne 3, c’est-à-dire si le flacon jaune est le seul à contenir un poison.

Solution de la question (c) : La situation où aucun flacon ne contient de poison correspond à la ligne 8 de la table. Alors les inscription IR et IB sont fausses.

Solution de la question (d) : La ligne 3 correspond à la situation où les trois inscriptions sont vraies. Dans ce cas, seul le flacon jaune contient du poison (J = ⊤).

Solution de la question (e) : Pour vérifier que si seuls les flacons ne contenant pas un poison ont une inscription vraie, un ou plusieurs flacons ne contiennent pas un poison, nous posons par hypothèse, que F = (¬R ↔ IR) ∧ (¬J ↔ IJ) ∧ (¬B ↔ IB) est vraie, or :

  • (¬R ↔ IR) est vraie aux lignes 3, 5, 6 et 8 ;
  • (¬J ↔ IJ) est vraie aux lignes 1, 2, 6 et 7 ;
  • (¬B ↔ IB) est vraie aux lignes 2, 3, 4, 5, 6, 7 et 8.

Donc F n’est vraie qu’à la ligne 6, donc seul le flacon jaune ne contient pas de poison sous cette hypothèse.

Solutions avec des équivalences

À venir…

Logique des prédicats (du premier ordre)

Traduire dans le langage des prédicats du premier ordre les phrases suivantes :

  1. Jean suit un cours.
  2. Un logicien a été champion du monde de cyclisme.
  3. Un entier naturel est pair ou impair.
  4. Un enseignant-chercheur a toujours un nouveau sujet à étudier.
  5. Dans un triangle isocèle une médiane est également hauteur.

Dans cet exercice, on peut choisir de modéliser la phrase avec plus ou moins de précision, et plusieurs choix de modélisation sont possibles. Notez que pour faciliter la compréhension du modèle, on utilise des conventions de nommage systématiques : les prédicats unaires, qui désignent généralement des classes d’entités, sont des noms communs au singulier avec une majuscule ; les prédicats binaires sont des verbes conjugués à la troisième personne du singulier et commencent par une minuscule.

  1. On définit Jean comme une constante. On définit le prédicat unaire Cours tel que Cours(x) est vrai lorsque x désigne un cours ; et le prédicat binaire suit tel que suit(x,y) est vrai lorsque x suit le cours y. Alors la phrase peut s’écrire :
    • ∃c (Cours(c) ∧ suit(Jean,c))
  2. On définit cyclisme comme une constante. On définit le prédicat unaire Logicien tel que Logicien(x) est vrai lorsque x désigne un logicien ; et le prédicat binaire estChampionDe tel que estChampionDe(x,y) est vrai lorsque x est champion dans une discipline y. Alors la phrase peut s’écrire :
    • ∃l (Logicien(l) ∧ estChampionDe(l,cyclisme))
  3. On définit le prédicat unaire EntierNaturel tel que EntierNaturel(x) est vrai lorsque x désigne un entier naturel ; le prédicat unaire Pair tel que Pair(x) est vrai lorsque x est divisible par 2 ; et le prédicat unaire Impair tel que Impair(x) est vrai lorsque x n’est divisible par 2. Alors la phrase peut s’écrire :
    • ∀n (EntierNaturel(n) → (Pair(n) ∨ Impair(n)))
    Notons qu’ici, nos connaissances nous indiquent que les nombres entiers ne peuvent pas être à la fois pairs et impairs. Il serait tentant d’ajouter explicitement ce fait dans la formule, mais ce serait modéliser quelque chose qui n’est pas décrit par la phrase.
  4. Je propose d’abord une modélisation naïve de la phrase. On définit le prédicat unaire EnseignantChercheur tel que EnseignantChercheur(x) est vrai lorsque x désigne un enseignant-chercheur ; le prédicat unaire Nouveau tel que Nouveau(x) est vrai lorsque x désigne quelque chose de nouveau ; le prédicat unaire Sujet tel que Sujet(x) est vrai lorsque x désigne un sujet d’étude ; et le prédicat binaire étudie tel que étudie(x,y) est vrai lorsque x étudie le sujet y. Alors la phrase peut s’écrire :
    • ∀ec (EnseignantChercheur(ec) → ∃s (Sujet(s) ∧ Nouveau(s) ∧ étudie(ec,s)))
    Notons que ce qui est nouveau dépend du temps (une fois le nouveau sujet étudié, il n’est plus nouveau). Or, la logique du premier ordre n’est pas bien adapté pour décrire convenablement l’évolution dans le temps d’une situation. Aussi, le fait qu’un sujet soit nouveau est relatif à la personne qui le considère. Remarquons enfin que la phrase ne dit pas qu’un enseignant-chercheur étudie à tout instant un nouveau sujet. Elle indique simplement que l’enseignant-chercheur a la possibilité d’étudier un nouveau sujet. Là encore, la notion de potentialité ne se décrit pas facilement en logique du premier ordre. On peut néanmoins affiner la formule pour tenter de tenir compte de ces trois remarques. On définit le prédicat unaire Instant tel que Instant(x) est vrai lorsque x désigne un instant, c’est-à-dire un point sur la ligne du temps. On définit le prédicat binaire estEnseignantChercheur tel que estEnseignantChercheur(x,y) est vrai lorsque x désigne un enseignant-chercheur à l’instant y. On définit le prédicat ternaire estNouveauPour tel que estNouveauPour(x,y,z) est vrai lorsque x désigne quelque chose de nouveau pour l’individu y à l’instant z ; le prédicat ternaire peutÉtudier tel que peutÉtudier(x,y,z) est vrai lorsque x a la possibilité d’étudier le sujet y à l’instant z. Alors la phrase peut s’écrire :
    • ∀ec∀t (estEnseignantChercheur(ec,t) → ∃s (Sujet(s) ∧ estNouveauPour(s,ec,t) ∧ peutÉtudier(ec,s,t)))
  5. On définit le prédicat unaire Triangle tel que Triangle(x) est vrai lorsque x désigne un triangle ; le prédicat unaire Isocèle tel que Isocèle(x) est vrai lorsque x est isocèle ; le prédicat binaire estMédianeDe tel que estMédianeDe(x,y) est vrai lorsque x est une médiane du triangle y ; le prédicat binaire estHauteurDe tel que estHauteurDe(x,y) est vrai lorsque x est une hauteur du triangle y
    • ∀t (Triangle(t) ∧ Isocèle(t) → ∃m (estMédianeDe(m,t) ∧ estHauteurDe(m,t)))
    Notons qu’il serait erroné de définir des prédicats unaires Médiane et Hauteur car cela n’a aucun sens de parler de médiane ou de hauteur indépendemment de tout triangle.

Traduire dans le langage des prédicats du premier ordre les phrases suivantes :

  1. Tous les hommes sont méchants.
  2. Seulement les hommes sont méchants.
  3. Il existe des hommes méchants.
  4. Il existe un homme qui n’est pas méchant.
  5. Il n’existe pas d’homme méchant.
  6. Il existe un homme qui aime toutes les femmes.
  7. Chaque chat connaît un chien qui le déteste.
  8. Tous les poissons, sauf les requins, sont gentils avec les enfants.
  9. Tous les oiseaux ne peuvent pas voler.
  10. Chaque personne aime quelqu’un et personne n’aime tout le monde, ou bien quelqu’un aime tout le monde et quelqu’un n’aime personne.
  11. Il y a des gens que l’on peut rouler tout le temps et quelquefois on peut rouler tout le monde, mais on ne peut pas rouler tout le monde à chaque fois.

Dans cet exercice, on aura besoin des prédicats suivants, dont la signification est sensée être claire de par le choix de leur nom, sauf exceptions détaillées entre parenthèses. On utilise les mêmes conventions que pour l’exercice 2.5.1 :

Prédicats unaires :
Homme, Méchant, Femme, Chat, Chien, Poisson, Requin, Enfant, Oiseau, Volant (quelque chose qui peut voler)
Prédicats binaires :
aime, connait, déteste, estGentilAvec, peutÊtreRoulé (vrai lorsque le premier argument peut être roulé, dans le sens de trompé/dupé, à l’instant du second argument)
  1. ∀x (Homme(x) → Méchant(x))
  2. ∀x (Méchant(x) → Homme(x))
  3. ∃x (Homme(x) ∧ Méchant(x))1
  4. ∃x (Homme(x) ∧ ¬Méchant(x))
  5. ¬∃x (Homme(x) ∧ Méchant(x))
  6. ∃x (Homme(x) ∧ ∀y (Femme(y) → aime(x,y)))
  7. ∀x (Chat(x) → >∃y (Chien(y) ∧ connait(x,y) ∧ déteste(y,x)))
  8. ∀x ((Poisson(x) ∧ ¬Requin(x)) → ∀y (Enfant(y) → estGentilAvec(x,y)))2
  9. ¬∀x (Oiseau(x) → Volant(x))
  10. ((∀x∃y aime(x,y) ∧ ¬∃x∀y aime(x,y)) ∨ (∃x∀y aime(x,y) ∧ ∃x∀y ¬aime(x,y)))
  11. (∃x∀t peutÊtreRoulé(x,t) ∧ ∃t∀x peutÊtreRoulé(x,t) ∧ ¬∀x∀t peutÊtreRoulé(x,t))

On notera que la phrase utilise un pluriel, alors que la formule ne mentionne l’existence que d’une seule entité. On pourrait penser que le pluriel peut s’écrire ∃x∃y … mais cela nindique pas que x et y désigne des choses différentes. Il faudrait pouvoir indiquer que x ≠ y mais le symbole ≠ n’appartient pas au langage de la logique du premier ordre. Une manière de s’en sortir consiste à introduire un prédicat unaire EstX et d’écrire ∃x∃y (Homme(x) ∧ Méchant(x) ∧ EstX(x) ∧ Homme(y) ∧ Méchant(y) ∧ ¬EstX(y)). Ceci impose nécessairement que x est différent de y.

La formule, telle qu’écrite, dit que « tous les poissons qui ne sont pas des requins sont gentils avec tous les enfants ». Ceci ne dit rien sur les requins. En revanche, le mot « sauf » laisse penser quil y a des exceptions (ou au moins une) parmi les requins. Par analogie, si on disait « tous les nombres entiers naturels, sauf le nombre zéro, ont un prédécesseur », on comprendrait que zéro est une exception. Cela na pas le même sens que « tous les entiers naturels non nuls ont un prédesseur », car on pourrait également dire « tous les entiers naturels non nuls ont un successeur », alors quil serait incorrect de dire « tous les nombres entiers naturels, sauf zéro, ont un successeur ». On peut modéliser lexception en ajoutant ∃x∃y (Requin(x) ∧ ¬estGentilAvec(x,y))

Traduire dans le langage des prédicats du premier ordre les phrases suivantes :

  1. Toutes les personnes qui entrent en voiture dans la faculté doivent avoir une carte ou être accompagnées par un membre du personnel.
  2. Certains étudiants entrent en voiture dans la faculté sans être accompagnés de personnes qui ne sont pas des étudiants.
  3. Aucun étudiant n’a de carte.

On peut proposer différent niveaux de précisions dans cette modélisation. Dans un premier temps, on ignore l’aspect temporel et on simplifie quelque peu la situation avec des prédicats regroupant plusieurs caractéristiques :

Prédicats unaires :
IndividuEntrantDansLaFac, PossesseurDeCarte, Étudiant, MembreDuPersonnel
Prédicats binaires :
accompagne
  1. ∀x (IndividuEntrantDansLaFac(x) → (PossesseurDeCarte(x,c) ∨ ∃p (MembreDuPersonnel(p) ∧ accompagne(p,x))))
  2. ∃x (Étudiant(x) ∧ IndividuEntrantDansLaFac(x) ∧ ¬∃y (accompagne(x,y) ∧ ¬Étudiant(y)))
  3. ∀x (Étudiant(x) → ¬PossesseurDeCarte(x))

Notons que ceci permet de conclure que certains étudiants sont membres du personnel (pouvez-vous le prouver ?). On peut affiner, toujours sans tenir compte de l’aspect temporel :

Constante :
laFaculté
Prédicats unaires :
Personne, Voiture, Carte
Prédicats binaires :
entreDans, possède, conduit
  1. ∀x∀v ((Personne(x) ∧ Voiture(v) ∧ conduit(x,v) ∧ entreDans(x,faculté)) → (∃c (Carte(c) ∧ possède(x,c)) ∨ ∃p (MembreDuPersonnel(p) ∧ accompagne(p,x))))
  2. ∃x∃v (Étudiant(x) ∧ Voiture(v) ∧ conduit(x,v) ∧ entreDans(x,faculté) ∧ ¬∃y (accompagne(x,y) ∧ ¬Étudiant(y)))
  3. ∀x (Étudiant(x) → ¬∃c (Carte(c) ∧ possède(x,c)))

Notons que ceci ne permet pas de conclure que certains étudiants sont membres du personnel (on peut construire une interprétation qui satisfait ces formules et dans laquelle aucun étudiant n’est membre du personnel). Il peut sembler surprenant qu’en affinant le modèle, on perde certaines conclusions. La raison est que dans la première des trois formules, la condition impose que x désigne une personne (car la phrase disait « toutes les personnes qui… ») alors que les deux autres formules ne parlent pas a priori de personnes ! En effet, rien dans la formule ne permet de conclure qu’un étudiant est une personne. On pourrait relâcher la contrainte de la première formule en éliminant Personne(x) (toute entité qui entre en voiture dans la faculté est soumise à la contrainte) ou bien modéliser le fait qu’un étudiant est une personne :

  1. ∀x(Étudiant(x) → Personne(x))

Enfin, on peut ajouter la dimension temporel. En effet, pour que la première formule décrire bien la réalité, il faut qu’elle soit vraie à tout instant, tandis que la seconde formule ne doit être vraie qu’à certains moments. On peut donc introduire le prédicat unaire Instant et transformer les prédicats entreDans, conduit, possède et accompagne en prédicats ternaires. Ainsi :

  1. ∀t∀x∀v ((Instant(t) ∧ Voiture(v) ∧ conduit(x,v,t) ∧ entreDans(x,faculté,t)) → (∃c (Carte(c) ∧ possède(x,c,t)) ∨ ∃p (MembreDuPersonnel(p) ∧ accompagne(p,x,t))))
  2. ∃t∃x∃v (Instant(t) ∧ Étudiant(x) ∧ Voiture(v) ∧ conduit(x,v,t) ∧ entreDans(x,faculté,t) ∧ ¬∃y (accompagne(x,y,t) ∧ ¬Étudiant(y)))
  3. ∀t∀x ((Instant(t) ∧ Étudiant(x)) → ¬∃c (Carte(c) ∧ possède(x,c,t)))

Traduire dans le langage des prédicats du premier ordre les phrases suivantes :

Une conjecture est un théorème qui ne peut être démontré par aucun mathématicien. Il existe des mathématiciens qui ne démontrent pas tous les théorèmes. Si un mathématicien démontre une conjecture alors il se trompe. Si quelqu’un démontre un théorème sans se tromper, alors ce n’est pas une conjecture.

On introduit les prédicats suivants :

Prédicats unaires :
Conjecture, Mathématicien, Théorème, EnErreur (quelqu’un qui se trompe)
Prédicats binaires :
démontre

Ainsi, les phrases peuvent se modéliser comme suit :

  1. ∀c∀m ((Conjecture(c) ∧ Mathématicien(m)) → (Théorème(c) ∧ ¬démontre(m,c)))
  2. ∃m∃t (Mathématicien(m) ∧ Théorème(t) ∧ ¬démontre(m,t))
  3. ∀m∀c ((Mathématicien(m) ∧ Conjecture(c) ∧ démontre(m,c)) → EnErreur(m))
  4. ∀x∀t ((Théorème(t) ∧ ¬EnErreur(x) ∧ démontre(x,t)) → ¬Conjecture(t))

Traduire dans le langage des prédicats du premier ordre les phrases suivantes :

Il existe des PC non connectés en réseau. Dans les grandes entreprises, tous les PC sont connectés au réseau interne. Il existe dans chaque grande entreprise au moins un PC connecté au réseau interne et relié à Internet.

On introduit les termes suivants :

Constante :
Internet
Prédicats unaires :
GrandeEntreprise, PC, Réseau
Prédicats binaires :
estConnectéÀ, possède, seTrouveDans

Ainsi, les phrases peuvent se modéliser comme suit :

  1. ∃x∀y (PC(x) ∧ (Réseau(y) → ¬estConnectéÀ(x,y)))
  2. ∀x∀y ((GrandeEntreprise(x) ∧ PC(y) ∧ Réseau(z) ∧ seTrouveDans(y,x) ∧ seTrouveDans(z,x)) → estConnectéÀ(y,z))3
  3. ∀x∀y∃z ((GrandeEntreprise(x) ∧ Réseau(y) ∧ seTrouveDans(y,x)) → (PC(z) ∧ seTrouveDans(z,x) ∧ estConnectéÀ(z,y) ∧ estConnectéÀ(z,Internet)))3

On modélise « le réseau interne d’une entreprise » comme un réseau qui se trouve dans l’entreprise.

Traduire dans le langage des prédicats du premier ordre les phrases suivantes :

Toute personne possédant un PC et un modem peut utiliser Internet. Il existe des personnes connectées en réseau, qui ne peuvent pas utiliser Internet. Nul ne possède de modem s’il ne possède pas de PC. Tout utilisateur d’Internet est soit connecté à un réseau, soit possesseur d’un PC. Il n’est pas possible d’utiliser Internet sans posséder de PC.

On introduit les termes suivants :

Constante :
Internet
Prédicats unaires :
Modem, PC, Personne, Réseau
Prédicats binaires :
estConnectéÀ, possède

Ainsi, les phrases peuvent se modéliser comme suit :

  1. ∀x∀y∀z ((Personne(x) ∧ PC(y) ∧ Modem(z) ∧ possède(x,y) ∧ possède(x,z)) → estConnectéÀ(x,Internet))4
  2. ∃x∃y ((Personne(x) ∧ Réseau(y) ∧ estConnectéÀ(x,y) ∧ ¬estConnectéÀ(x,Internet))
  3. ∀x∀y ((Modem(y) ∧ possède(x,y)) → ∃z(PC(z) ∧ possède(x,z)))
  4. ∀x (estConnectéÀ(x,Internet) → (∃y (Réseau(y) ∧ estConnectéÀ(x,y)) ∨ ∃z (PC(z) ∧ possède(x,z))))
  5. ∀x (estConnectéÀ(x,Internet) → ∃y (PC(y) ∧ possède(x,y)))

Une version simplifiée acceptable pourrait utiliser les prédicats suivants :

Prédicats unaires :
EnRéseau, PossesseurDeModem, PossesseurDePC, Internaute (peut se connecter à Internet)
  1. ∀x ((PossesseurDePC(x) ∧ PossesseurDeModem(x)) → Internaute(x))
  2. ∃xEnRéseau(x) ∧ ¬Internaute(x))
  3. ∀x (PossesseurDeModem(x) → PossesseurDePC(x))
  4. ∀x (Internaute(x) → (EnRéseau(x) ∨ PossesseurDePC(x)))
  5. ∀x (Internaute(x) → PossesseurDePC(x))

On considèrera que « peut utiliser Internet » signifie la même chose que « est connecté à Internet ».

Soient les expressions dans 𝓛1 :

  • (A1)∃z∀x∀y (F(x,y) → G(z,x))
  • (A2)∀x∀y∃z (¬F(y,z) → E(x))
  • (A3)∃z ¬E(z)
  • (C)∃x G(x,x)

Montrer, en utilisant la méthode des tableaux, que A1 ∧ A2 ∧ A3 → C est un théorème.

arbre de décision pour l’exercice 2.5.7 Arbre de décision pour l’exercice 2.5.7

Principe de résolution

Montrer, en utilisant la résolution, que la formule suivante est une tautologie :

  • ((p → r) ∧ (q ↔ s) ∧ (r ↔ q) ∧ p) → s

Il faut montrer que F = ((p → r) ∧ (q ↔ s) ∧ (r ↔ q) ∧ p) ∧ ¬s est une contradiction. Comme il sagit dune formule de logique propositionnelle, il ny a pas de variable, donc il nest pas nécessaire de mettre sous forme prénexe ni sous forme de Skolem.

On obtient la forme normale conjonctive :

  • F = ((p → r) ∧ (q ↔ s) ∧ (r ↔ q) ∧ p) ∧ ¬s
  • ≡ (p → r) ∧ (q → s) ∧ (s → q) ∧ (r → q) ∧ (q → r) ∧ p ∧ ¬s
  • ≡ (¬p ∨ r) ∧ (¬q ∨ s) ∧ (¬s ∨ q) ∧ (¬r ∨ q) ∧ (¬q ∨ r) ∧ p ∧ ¬s

Puis en forme clausale :

(C1) ¬p r
(C2) ¬q s
(C3) ¬s q
(C4) ¬r q
(C5) ¬q r
(C6) p
(C7) ¬s

On peut obtenir la clause vide grâce à la suite de clauses :

(C8) ¬q obtenue par la résolution de C2 + C7
(C9) ¬r obtenue par la résolution de C4 + C8
(C10) ¬p obtenue par la résolution de C1 + C9
(C11) ◻ obtenue par la résolution de C6 + C10

Soient les formules dans 𝓛1 :

  • (A1)∃z∀x∀y (F(x,y) → G(z,x))
  • (A2)∀x∀y∃z (¬F(y,z) → E(x))
  • (A3)∃z ¬E(z)
  • (C)∃x G(x,x)

Montrer, en utilisant le principe de résolution, que A1 ∧ A2 ∧ A3 → C est un théorème.

Il faut montrer que A1 ∧ A2 ∧ A3 ∧ ¬C est contradictoire. Mise sous forme prénexe :

  • (A1)∃z∀x∀y (F(x,y) → G(z,x))
  • (A2)∀x∀y∃z (¬F(y,z) → E(x))
  • (A3)∃z ¬E(z)
  • (¬C)∀x ¬G(x,x)

Mise sous forme de Skolem (a et b sont des constantes). À partir de maintenant, on se permet d’omettre les quantificateurs car on sait que toutes les variables sont quantifiées universellement.

  • (A1)(F(x,y) → G(a,x))
  • (A2)(¬F(y,f(x,y)) → E(x))
  • (A3)¬E(b)
  • (¬C)¬G(x,x)

Mise sous forme normale conjonctive :

  • (A1)(¬F(x,y) ∨ G(a,x))
  • (A2)(F(y,f(x,y)) ∨ E(x))
  • (A3)¬E(b)
  • (¬C)¬G(x,x)

Mise sous forme clausale et renommage des variables pour éviter des conflits lors de l’unification :

(C1) ¬F(x1,y1) G(a,x1)
(C2) F(y2,f(x2,y2) E(x2)
(C3) ¬E(b)
(C4) ¬G(x4,x4)

On applique alors la résolution de la façon suivante :

(C5) ¬F(a,y1) obtenue par la résolution de C1 + C4 [x4 ↦ a, x1 ↦ a]
(C6) E(x2) obtenue par la résolution de C2 + C5 [y2 ↦ a, y1 ↦ f(x2,a)]
(C7) ◻ obtenue par la résolution de C3 + C6 [x2 ↦ b]

Montrer en utilisant le principe de résolution que :

  • H1, H2, H3 ⊨ C

On prendra soin de mettre en valeur les étapes de mise sous forme prénexe, de Skolémisation et de mise sous FNC.

  • (H1)(∃x F(x) → ∃x G(x))
  • (H2)∀x (G(x) → ∃y H(x,y))
  • (H3)∀x∀y (H(x,y) → A(x))
  • (C)∃x (F(x) → A(x))

Il faut montrer que H1 ∧ H2 ∧ H3 ∧ ¬C est contradictoire. Mise sous forme prénexe :

  • (H1)∀x∃y (F(x) → G(y))
  • (H2)∀x∃y (G(x) → H(x,y))
  • (H3)∀x∀y (H(x,y) → A(x))
  • (¬C)∀x ¬(F(x) → A(x))

Notons qu’il faut renommer une des deux occurrences de la variable x dans la formule (H1) car elles sont quantifiées séparément. Mise sous forme de Skolem. À partir de maintenant, on se permet d’omettre les quantificateurs car on sait que toutes les variables sont quantifiées universellement.

  • (H1)(F(x) → G(f(x)))
  • (H2)(G(x) → H(x,g(x)))
  • (H3)(H(x,y) → A(x))
  • (¬C)¬(F(x) → A(x))

Notons qu’il faut introduire un symbole de fonction différent pour chaque occurrence d’un quantificateur existentiel. Mise sous forme normale conjonctive :

  • (H1)(¬F(x) ∨ G(f(x)))
  • (H2)(¬G(x) ∨ H(x,g(x)))
  • (H3)(¬H(x,y) ∨ A(x))
  • (¬C)(F(x) ∧ ¬A(x))

Mise sous forme clausale et renommage des variables pour éviter des conflits lors de l’unification :

(C1) ¬F(x1) G(f(x1))
(C2) ¬G(x2) H(x2,g(x2))
(C3) ¬H(x3,y3) A(x3)
(C4) F(x4)
(C5) ¬A(x5)

Notons qu’il y a une conjonction dans la formule (¬C), ce qui aboutit à deux clauses qu’il faut disposer sur deux lignes différentes. On applique alors la résolution de la façon suivante :

(C6) ¬H(x3,y3) (C3 + C5) [x4 ↦ x3]
(C7) ¬G(x2) (C2 + C6) [x3 ↦ x2, y3 ↦ g(x2)]
(C8) ¬F(x1) (C1 + C7) [x2 ↦ f(x1)]
(C9) ◻ (C4 + C8) [x1 ↦ x4]

Montrer en utilisant le principe de résolution que :

  • H1, H2, H3, H4, H5 ⊨ C

On prendra soin de mettre en valeur les étapes de mise sous forme prénexe, de Skolémisation et de mise sous FNC. La solution devra emprunter toutes les clauses de départ.

  • (H1)∀x∀y (M(x,x,x) ∨ B(x))
  • (H2)∀x∀y∃z ((M(x,y,z) ∧ N(x,y)) → P(y,x))
  • (H3)∃x∀y∀z∀t (¬P(y,x) ∧ (M(y,z,t) ∨ A(x,z)))
  • (H4)∀x∀y (M(x,x,x) → N(x,y))
  • (H5)∀x∀y (M(x,x,y) → ¬A(x,y))
  • (C)∃x B(x)

(x, y, z et t désignent des variables)

Il faut montrer que H1 ∧ H2 ∧ H3 ∧ H4 ∧ H5 ∧ ¬C est contradictoire. Mise sous forme prénexe :

  • (H1)∀x∀y (M(x,x,x) ∨ B(x))
  • (H2)∀x∀y∃z ((M(x,y,z) ∧ N(x,y)) → P(y,x))
  • (H3)∃x∀y∀z∀t (¬P(y,x) ∧ (M(y,z,t) ∨ A(x,z)))
  • (H4)∀x∀y (M(x,x,x) → N(x,y))
  • (H5)∀x∀y (M(x,x,y) → ¬A(x,y))
  • (¬C)∀x ¬B(x)

Mise sous forme de Skolem (a désigne une constante). À partir de maintenant, on se permet d’omettre les quantificateurs car on sait que toutes les variables sont quantifiées universellement.

  • (H1)(M(x,x,x) ∨ B(x))
  • (H2)((M(x,y,f(x,y)) ∧ N(x,y)) → P(y,x))
  • (H3)(¬P(y,a) ∧ (M(y,z,t) ∨ A(a,z)))
  • (H4)(M(x,x,x) → N(x,y))
  • (H5)(M(x,x,y) → ¬A(x,y))
  • (¬C)¬B(x)

Mise sous forme normale conjonctive :

  • (H1)(M(x,x,x) ∨ B(x))
  • (H2)(¬M(x,y,f(x,y)) ∨ ¬N(x,y) ∨ P(y,x))
  • (H3)(¬P(y,a) ∧ (M(y,z,t) ∨ A(a,z)))
  • (H4)(¬M(x,x,x) ∨ N(x,y))
  • (H5)(¬M(x,x,y) ∨ ¬A(x,y))
  • (¬C)¬B(x)

Mise sous forme clausale et renommage des variables pour éviter des conflits lors de l’unification ((H3) donne lieu à deux clauses distinctes) :

(C1) M(x1,x1,x1) B(x1)
(C2) ¬M(x2,y2,f(x2,y2)) ¬N(x2,y2) P(y2,x2)
(C3) ¬P(y3,a)
(C4) M(y4,z4,t4) A(a,z4)
(C5) ¬M(x5,x5,x5) N(x5,y5)
(C6) ¬M(x6,x6,y6) ¬A(x6,y6)
(C7) ¬B(x7)

On applique alors la résolution de la façon suivante :

(C8) M(x7,x7,x7) (C1 + C7) [x1 ↦ x7]
(C9) ¬A(x7,x7) (C6 + C8) [x6 ↦ x7, y6 ↦ x7]
(C10) M(y4,a,t4) (C4 + C9) [x7 ↦ a, z4 ↦ a]
(C11) ¬N(x2,a) P(a,x2) (C2 + C10) [y4 ↦ x2, y2 ↦ a, t4 ↦ f(x2,a)]
(C12) ¬N(a,a) (C3 + C11) [x2 ↦ a, y3 ↦ a]
(C13) ¬M(a,a,a) (C5 + C12) [x5 ↦ a, y5 ↦ a]
(C14) ◻ (C8 + C13) [x7 ↦ a]

Soient les formules suivantes dans 𝓛1. Montrer, en utilisant le principe de résolution, que H1 ∧ H2 ∧ H3 ∧ H4 → C est un théorème. La solution devra emprunter toutes les clauses de départ. x, y, z désignent des variables.

  • (H1)∀x∀y (D(x,y) → A(x,x))
  • (H2)(∀x A(x,x) → ∀x∀y B(x,y))
  • (H3)∀x∀y∀z (C(x,z) → (A(x,y) ∨ D(y,z) ∨ E(z,z)))
  • (H4)∀x∃y (C(x,y) ∧ ¬E(y,y))
  • (C)∃x B(x,x)

Il faut montrer que H1 ∧ H2 ∧ H3 ∧ H4 ∧ ¬C est contradictoire. Mise sous forme prénexe :

  • (H1)∀x∀y (D(x,y) → A(x,x))
  • (H2)∃z∀x∀y (A(z,z) → B(x,y))
  • (H3)∀x∀y∀z (C(x,z) → (A(x,y) ∨ D(y,z) ∨ E(z,z)))
  • (H4)∀x∃y (C(x,y) ∧ ¬E(y,y))
  • (¬C)∀x ¬B(x,x)

Mise sous forme de Skolem (a désigne une constante). À partir de maintenant, on se permet d’omettre les quantificateurs car on sait que toutes les variables sont quantifiées universellement.

  • (H1)(D(x,y) → A(x,x))
  • (H2)(A(a,a) → B(x,y))
  • (H3)(C(x,z) → (A(x,y) ∨ D(y,z) ∨ E(z,z)))
  • (H4)(C(x,f(x)) ∧ ¬E(f(x),f(x)))
  • (¬C)¬B(x,x)

Mise sous forme normale conjonctive :

  • (H1)(¬D(x,y) ∨ A(x,x))
  • (H2)(¬A(a,a) ∨ B(x,y))
  • (H3)(¬C(x,z) ∨ A(x,y) ∨ D(y,z) ∨ E(z,z))
  • (H4)(C(x,f(x)) ∧ ¬E(f(x),f(x)))
  • (¬C)¬B(x,x)

Mise sous forme clausale et renommage des variables pour éviter des conflits lors de l’unification ((H4) donne lieu à deux clauses distinctes) :

(C1) ¬D(x1,y1) A(x1,x1)
(C2) ¬A(a,a) B(x2,y2)
(C3) ¬C(x3,z3) A(x3,y3) D(y3,z3) E(z3,z3)
(C4) C(x4,f(x4))
(C5) ¬E(f(x5),f(x5))
(C6) ¬B(x6,x6)

On applique alors la résolution de la façon suivante :

(C7) ¬A(a,a) (C2 + C6) [x2 ↦ x6, y2 ↦ x6]
(C8) ¬D(a,y1) (C1 + C7) [x1 ↦ a]
(C9) ¬C(x3,z3) A(x3,a) E(z3,z3) (C3 + C8) [y3 ↦ a, y1 ↦ z3]
(C10) ¬C(x3,f(x5)) A(x3,a) (C5 + C9) [z3 ↦ f(x5)]
(C11) A(x3,a) (C4 + C10) [x4 ↦ x3, x5 ↦ x3]
(C12) ◻ (C7 + C11) [x3 ↦ a]

En reprenant le monde de l’exercice 2.5.3, montrer que certains étudiants sont membres du personnel.

Todo...