Formalisation pour la programmation
CC1 logique propositionnelle

Mardi 21 septembre 2021, 15 h 30 – 16 h 15

Le livret de cours ainsi que les notes personnelles sont autorisés. Vous avez 45 minutes. Les étudiants composant à distance doivent envoyer une photo ou un scan de leur travail à antoine.zimmermann@emse.fr et christopher.leturc@emse.fr.

Hortense pense à son examen de logique du lendemain et émet ces réflexions :

  1. si je révise bien pour l’examen, je le réussirai ;
  2. mais s’il y a une erreur dans l’énoncé, alors je le raterai.
  3. Hortense décide malgré tout de bien réviser pour l’examen

(a) Modéliser en logique propositionnelle les 3 assertions ci-dessus, en précisant bien quelle affirmation correspond à chaque proposition.

(b) Ensuite, en utilisant la méthode des tableaux, montrer que, selon le raisonnement d’Hortense, l’examen ne comportera pas d’erreur d’énoncé.

On définit les propositions suivantes :

  • Révise : « Hortense révise bien pour l’examen »
  • Réussit : « Hortense réussit son examen »
  • Erreur : « L’examen contient une erreur »

Alors, on modélise la situation comme suit :

  1. (Révise → Réussit)
  2. (Erreur → ¬Réussit)
  3. Révise

On cherche à montrer que si la situation modélisée précédemment est vraie, alors l’examen ne comporte pas d’erreur, c’est-à-dire que ((a) ∧ (b) ∧ (c)) ⊨ ¬Erreur. Ceci est équivalent à démontrer que la formule ((a) ∧ (b) ∧ (c) ∧ ¬¬Erreur) est une contradiction. Voici l’arbre de la méthode des tableaux :

arbre de décision
Figure 1 : Arbre dont toutes les branches sont fermées, démontrant la contradiction

On considère la formule suivante : (¬((p → q) ∧ (q ↔ r)) → (¬q ∨ ¬r))

(a) Construire une table de vérité, puis (b) montrer si la formule est une contradiction, une tautologie, ou bien simplement satisfiable.

On pourra poser : F1 = ((p → q) ∧ (q ↔ r)) et F2 = (¬q ∨ ¬r) et remplir la table selon ce modèle à recopier :

p q r (p → q) (q ↔ r) F1 ¬F1 F2 (¬F1 → F2)
 
 
 

(a) Table de vérité :

p q r (p → q) (q ↔ r) F1 ¬F1 F2 (¬F1 → F2)
⊥ ⊥ ⊥ ⊤ ⊤ ⊤ ⊥ ⊤ ⊤
⊥ ⊥ ⊤ ⊤ ⊥ ⊥ ⊤ ⊤ ⊤
⊥ ⊤ ⊥ ⊤ ⊥ ⊥ ⊤ ⊤ ⊤
⊥ ⊤ ⊤ ⊤ ⊤ ⊤ ⊥ ⊥ ⊤
⊤ ⊥ ⊥ ⊥ ⊤ ⊥ ⊤ ⊤ ⊤
⊤ ⊥ ⊤ ⊥ ⊥ ⊥ ⊤ ⊤ ⊤
⊤ ⊤ ⊥ ⊤ ⊥ ⊥ ⊤ ⊤ ⊤
⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊥ ⊥ ⊤

(b) La formule est une tautologie car toutes les valeurs de la dernière colonne sont vraies.

On considère un réseau social comprenant 3 personnes : Xavier, Yves et Zahia. Une personne peut en connaitre une autre mais ce n’est pas forcément réciproque. On définit les symboles de propositions suivants pour modéliser la situation :

  • xy : Xavier connait Yves ;
  • xz : Xavier connait Zahia ;
  • yx : Yves connait Xavier ;
  • yz : Yves connait Zahia ;
  • zx : Zahia connait Xavier ; et
  • zy : Zahia connait Yves.

Nous savons par ailleurs que :

  1. si Yves connait Xavier, alors il connait aussi Zahia ;
  2. Zahia connait au moins un des deux autres ;
  3. Il y a au moins deux des trois personnes qui ne se connaissent pas du tout l’un(e) l’autre.

(a) Exprimer en logique propositionnelle les phrases ci-dessus avec les propositions {xy, xz, yx, yz, zx, zy}.

(b) Donner une interprétation qui satisfait nos connaissances et selon laquelle Xavier connait les 2 autres ; puis une autre interprétation satisfaisant nos connaissances où Yves connait les 2 autres ; enfin une interprétation satisfaisant nos connaissances et telle que Zahia connaisse les 2 autres.

Pour gagner du temps, on peut décrire une interprétation en ne listant que les propositions interprétées comme vraies.

(c) Une des trois personnes peut-elle ne pas être connue des 2 autres, tout en ne les connaissant pas non plus (c’est-à-dire, peut-il y avoir un individu isolé socialement) ? Justifier.

  1. En logique propositionnelle, les affirmations sont :
    1. (yx → yz)
    2. (zx ∨ zy)
    3. ((¬xy ∧ ¬yx) ∨ (¬xz ∧ ¬zx) ∨ (¬yz ∧ ¬zy))
  2. On propose les interprétations suivantes :

    • L’interprétation I : {xy ↦ ⊤, xz ↦ ⊤, yx ↦ ⊥, yz ↦ ⊥, zx ↦ ⊤, zy ↦ ⊥} (c’est-à-dire, l’interprétation I telle que I(xy) = I(xz) = I(zx) = ⊤ et I(yx) = I(yz) = I(zy) = ⊥) satisfait les formules et vérifie le fait que Xavier connaisse les 2 autres. On peut visualiser une interprétation avec un graphe où les sommets désignent des personnes et les arcs indiquent une connaissance.

      Premier cas, première interprétation
      Figure 2 : Cas où Xavier connait les 2 autres

    • L’interprétation I : {xy ↦ ⊥, xz ↦ ⊥, yx ↦ ⊤, yz ↦ ⊤, zx ↦ ⊥, zy ↦ ⊤} (c’est-à-dire, l’interprétation I telle que I(yx) = I(yz) = I(zy) = ⊤ et I(xy) = I(xz) = I(zx) = ⊥) satisfait les formules et vérifie le fait que Yves connaisse les 2 autres. On pourrait aussi choisir I(xy) = ⊤, sans changer le reste, et satisfaire les contraintes. Sous forme de graphes :

      Deuxième cas, première interprétation Deuxième cas, seconde interprétation
      Figure 3 : Cas où Yves connait les 2 autres

    • L’interprétation I : {xy ↦ ⊥, xz ↦ ⊥, yx ↦ ⊥, yz ↦ ⊥, zx ↦ ⊤, zy ↦ ⊤} (c’est-à-dire, l’interprétation I telle que I(zx) = I(zy) = I(zx) = ⊤ et I(xy) = I(xz) = I(yx) = I(yz) = ⊥) satisfait les formules et vérifie le fait que Zahia connaisse les 2 autres. On pourrait aussi choisir I(xz) = ⊤, et/ou I(yz) = ⊤, sans changer le reste, et satisfaire les contraintes. Sous forme de graphes :

      Troisième cas, première interprétation Troisième cas, deuxième interprétation Troisième cas, troisième interprétation Troisième cas, quatrième interprétation
      Figure 3 : Cas où Zahia connait les 2 autres

  3. Xavier ou Yves peuvent être isolés socialement. En effet, l’interprétation I : {xy ↦ ⊥, xz ↦ ⊥, yx ↦ ⊥, yz ↦ ⊥, zx ↦ ⊤, zy ↦ ⊥} satisfait les contraintes, de même que l’interprétation I : {xy ↦ ⊥, xz ↦ ⊤, yx ↦ ⊥, yz ↦ ⊥, zx ↦ ⊤, zy ↦ ⊥}, ou I : {xy ↦ ⊥, xz ↦ ⊥, yx ↦ ⊥, yz ↦ ⊥, zx ↦ ⊥, zy ↦ ⊤}, ou I : {xy ↦ ⊥, xz ↦ ⊥, yx ↦ ⊥, yz ↦ ⊤, zx ↦ ⊥, zy ↦ ⊤}. Sous forme de graphes :

    Xavier isolé, première interprétation Xavier isolé, seconde interprétation Yves isolé, première interprétation Yves isolé, seconde interprétation
    Figure 4 : Cas où un individu est isolé socialement