TP 3 : Modélisation II

Systèmes Logiques

15 Janvier 2025

  1. Écrire sous forme normale conjonctive (FNC) les formules suivantes :
    1. a ⇔ (b∨c)
    2. a ⇔ (b∧c)
    3. a ⇔ (b⇒c)
Correction

1.a. On peut soit faire la table de vérité, soit développer le calcul. On va développer.

a ⇔ (b∨c)
 ≡ (a⇒(b∨c)) ∧ ((b∨c)⇒a)
 ≡ (¬a∨(b∨c)) ∧ (¬(b∨c)∨a) en récrivant p ⇒ q en ¬p ∨ q
 ≡ (¬a∨b∨c) ∧ (¬b∧¬c) ∨ a) en appliquant De Morgan
 ≡ (¬a∨b∨c) ∧ (¬b∨a) ∧ (¬c∨a) en développant le ∨ sur le ∧.

1.b. On développe encore :

a ⇔ (b∧c)
 ≡ (a⇒(b∧c)) ∧ ((b∧c)⇒a)
 ≡ (¬a∨(b∧c)) ∧ (¬(b∧c)∨a) en récrivant p ⇒ q en ¬p ∨ q
 ≡ (¬a∨(b∧c)) ∧ ((¬b∨¬c)∨a) en appliquant De Morgan
 ≡ (¬a∨b) ∧ (¬a∨c) ∧ (¬b∨¬c∨a) en développant

1.c. On observe

a ⇔ (b⇒c)
 ≡ a ⇔ (¬b∨c)

On peut donc reprendre l’identité 1.a. et remplacer b par ¬b dedans ! On trouve donc

a ⇔ (b⇒c)
 ≡ (¬a∨¬b∨c) ∧ (b∨a) ∧ (¬c∨a) en utilisant ¬¬b ≡ b

  1. En déduire la transformation de Tseitin des formules suivantes :
    1. ((a∨b)⇒(¬c∨¬b)) ⇒ (a∧¬c).
    2. ((a∧b)⇒(c∨¬a)) ∨ (¬a∧(b⇒c)).
Correction

2.a. On commence par mettre sous forme arborescente pour clarifier les dépendances entre les connecteurs et on introduit une nouvelle variable pour chaque connecteur.

g N0 ⇒, x1 N1 ⇒, x2 N0->N1 N10 ∧,x5 N0->N10 N2 ∨,x3 N1->N2 N5 ∨,x4 N1->N5 N3 a N2->N3 N4 b N2->N4 N6 ¬ N5->N6 N8 ¬ N5->N8 N7 c N6->N7 N9 b N8->N9 N11 a N10->N11 N12 ¬ N10->N12 N13 c N12->N13

On exprime les valeurs des variables x en fonction de leur entrées :

  • x1 ⇔ (x2⇒x5)
  • x2 ⇔ (x3⇒x4)
  • x3 ⇔ (a∨b)
  • x4 ⇔ (¬b∨¬c)
  • x5 ⇔ (a∧¬c)

On applique ensuite les identités de la question précédentes pour mettre chaque équivalence ci-dessus sous FNC.

  • En remplaçant a, b, c dans 1.c. par x1, x2, x5, on trouve que la première équivalence est (¬x1∨¬x2∨x5) ∧ (x2∨x1) ∧ (¬x5∨x1).
  • De même (¬x2∨¬x3∨x4) ∧ (x3∨x2) ∧ (¬x4∨x2).
  • De même mais en appliquant 1.a. : (¬x3∨a∨b) ∧ (¬a∨x3) ∧ (¬b∨x3)
  • De même (¬x4∨¬b∨¬c) ∧ (b∨x4) ∧ (c∨x4)
  • De même en utilisant 1.b: (¬x5∨a) ∧ (¬x5∨¬c) ∧ (¬a∨c∨x5)

À la fin, on met tout ensemble :

(¬x1∨¬x2∨x5) ∧ (x2∨x1) ∧ (¬x5∨x1) ∧ (¬x2∨¬x3∨x4) ∧ (x3∨x2) ∧ (¬x4∨x2) ∧ (¬x3∨a∨b) ∧ (¬a∨x3) ∧ (¬b∨x3) ∧ (¬x4∨¬b∨¬c) ∧ (b∨x4) ∧ (c∨x4) ∧ (¬x5∨a) ∧ (¬x5∨¬c) ∧ (¬a∨c∨x5).

2.b. On fait pareil.

g N0 ∨, x1 N1 ⇒, x2 N0->N1 N9 ∧,x5 N0->N9 N2 ∧,x3 N1->N2 N5 ∨,x4 N1->N5 N3 a N2->N3 N4 b N2->N4 N6 c N5->N6 N7 ¬ N5->N7 N8 a N7->N8 N10 ¬ N9->N10 N12 ⇒,x6 N9->N12 N11 a N10->N11 N13 b N12->N13 N14 c N12->N14
  • x1 ⇔ (x2∨x5) soit (¬x1∨x2∨x5) ∧ (¬x2∨x5) ∧ (¬x5∨x2)
  • x2 ⇔ (x3⇒x4) soit (¬x2∨¬x3∨x4) ∧ (x3∨x2) ∧ (¬x4∨x2)
  • x3 ⇔ (a∧b) soit (¬x3∨a) ∧ (¬x3∨b) ∧ (¬a∨¬b∨x3)
  • x4 ⇔ (c∨¬a) soit (¬x4∨c∨¬a) ∧ (¬c∨¬a) ∧ (a∨c)
  • x5 ⇔ (¬a∧x6) soit (¬x5∨¬a) ∧ (¬x5∨x6) ∧ (a∨¬x6∨x5)
  • x6 ⇔ (b⇒c) soit (¬x6∨¬b∨c) ∧ (b∨x6) ∧ (¬c∨x6).

On prend la conjonction de toutes ces FNC pour trouver :

(¬x1∨x2∨x5) ∧ (¬x2∨x5) ∧ (¬x5∨x2) ∧ (¬x2∨¬x3∨x4) ∧ (x3∨x2) ∧ (¬x4∨x2) ∧ (¬x3∨a) ∧ (¬x3∨b) ∧ (¬a∨¬b∨x3) ∧ (¬x4∨c∨¬a) ∧ (¬c∨¬a) ∧ (a∨c) ∧ (¬x5∨¬a) ∧ (¬x5∨x6) ∧ (a∨¬x6∨x5) ∧ (¬x6∨¬b∨c) ∧ (b∨x6) ∧ (¬c∨x6).

Modéliser en logique propositionnelle des problèmes suivants pour trouver la solution (on peut bien sûr trouver la solution sans forcément modéliser mais ce n’est pas le but de cet exercice).

  1. Il y a trois personnes Alice, Bob et Carole. L’une d’elle est honnête et dit toujours la vérité. L’une est malhonnête et ment toujours. Une autre enfin est normale et peut dire la vérité ou mentir.
    1. Alice dit : “Carole est malhonnête”.
    2. Bob dit : “Alice est honnête”.
    3. Carole dit : “Je suis normale”.

Déterminez qui est honnête, malhonnête et normal.

Correction

On va utiliser neuf propositions atomiques :

  • NA (resp. NB, NC) est vraie si et seulement si Alice (resp Bob, Carole) est normale.
  • HA (resp. HB, HC) est vraie si et seulement si Alice (resp Bob, Carole) est honnête.
  • MA (resp. MB, MC) est vraie si et seulement si Alice (resp Bob, Carole) est malhonnête.

On commence par exprimer que chaque personne est soit normale, soit honnête, soit malhonnête :

  • Pour Alice : NA ∨ HA ∨ MA
  • Pour Bob : NB ∨ HB ∨ MB
  • Pour Carole : NC ∨ HC ∨ MC

On exprime qu’Alice ne peut être qu’une chose à la fois :

  • NA ⇒ (¬HA∧¬MA)
  • HA ⇒ (¬NA∧¬MA)
  • MA ⇒ (¬NA∧¬HA)

On fait de même pour Bob et Carole :

  • NB ⇒ (¬HB∧¬MB)
  • HB ⇒ (¬NB∧¬MB)
  • MB ⇒ (¬NB∧¬HB)
  • NC ⇒ (¬HC∧¬MC)
  • HC ⇒ (¬NC∧¬MC)
  • MC ⇒ (¬NC∧¬HC)

On va, pour simplifier la modélisation (on n’en a pas forcément besoin), introduire la proposition VN pour “la personne normale dit la vérité”. Le fait qu’une personne (par exemple Alice) dise la vérité est donc équivalent à HA ∨ (VN∧NA), c’est-à-dire, soit la personne est honnête, soit elle est normale et la personne normale dit la vérité.

On peut maintenant exprimer les contraintes du sujet :

  1. Alice dit : “Carole est malhonnête” : (HA∨(VN∧NA)) ⇔ MC (ie Alice dit la vérité si et seulement si Carole est malhonnête).
  2. Bob dit : “Alice est honnête” : (HB∨(VN∧NB)) ⇔ HA
  3. Carole dit : “Je suis normale”. (HC∨(VN∧NC)) ⇔ NC

On considère comme modélisation la conjonction de toutes ces formules. On trouve qu’il n’y a qu’une seul modèle : HA = 1, NB = 1, MC = 1, VN = 1 et les autres variables à 0. En d’autres mots, Alice est honnête, Bob est normal, Carole est malhonnête et la personne normale dit la vérité.

  1. Trois boîtes sont disposées devant vous, chacune a une inscription. Une seule de ces inscriptions est vraie.
    1. On lit sur la boîte 1 : “L’or n’est pas ici”.
    2. On lit sur la boîte 2 : “L’or n’est pas ici”.
    3. On lit sur la boîte 3 : “L’or est dans la boîte 2”.

Où se trouve l’or ?

Correction

On va utiliser une variable propositionnelle O1 pour dire que l’or est dans la boîte 1 (O2, O3 de même) et B1 pour dire que la boîte 1 dit la vérité (B2, B3 de même).

  1. B1 ⇔ ¬O1
  2. B2 ⇔ ¬O2
  3. B3 ⇔ O2

On ajoute le fait qu’une seule boîte dit la vérité : (B1∨B2∨B3) ∧ (B1⇒(¬B2∧¬B3)) ∧ (B2⇒(¬B1∧¬B3)) ∧ (B3⇒(¬B1∧¬B2)).

Et que l’or ne se trouve que dans une seule boîte : (O1∨O2∨O3) ∧ (O1⇒(¬O2∧¬O3)) ∧ (O2⇒(¬O1∧¬O3)) ∧ (O3⇒(¬O1∧¬O2)).

On peut résoudre cette formule par analyse de cas :

  • si on met B3 à vrai, alors on propage que B1 et B2 sont à faux et que O2 est à vrai. Dans ce cas, O1 est à vrai, mais dans ce cas, on a un conflit car O1 et O2 sont à vrai.

  • si on met B3 à faux, on propage et on trouve que O2 est à faux et donc que B2 est vrai. Cela implique que B1 est faux et donc que O1 est vrai. On a qu’une valeur pour O3 dans ce cas, faux.

Soit G = (V,E) un graphe. Soit D ⊆ V. On dit que v ∈ V est dominé par D si et seulement si v ∈ D ou bien il existe w ∈ D tel que {v, w} ∈ E. En d’autres mot, soit v est dans D, soit v est connecté à un élément de D. Un dominant D de G est un sous ensemble de V tel que pour tout sommet v ∈ V, v est dominé par D.

  1. Écrire une formule FG en FNC dont les modèles sont en bijection avec les dominants de G.
Correction

On introduit une proposition atomique dv pour chaque sommet v ∈ V, ie X = {xv ∣ v ∈ V}. On va considérer qu’une interprétation ω : X → {0, 1} décrit un sous-ensemble Vω ⊆ V de sommet défini par Vω = ω−1(1). On va écrire une formule en FNC qui sera satisfaite par une interprétation ω si et seulement si Vω est un dominant. On note N(v) = {w ∈ V ∣ {v, w} ∈ E}, c’est-à-dire, l’ensemble des voisins de v dans le graphe G.

Considérons, pour chaque v ∈ V, la clause Cv définie par (xv∨⋁w ∈ N(v)xw). On peut se rendre compte que si ω est une interprétation, alors ω ⊨ Cv si et seulement si v est dominé par Vω.

On définit donc FG ≡ ⋀v ∈ VCv. On a donc bien que si ω ⊨ FG, alors pour tout v ∈ V, v est dominé par Vω et donc, Vω est bien un dominant. Inversement, si D est un dominant, soit ωD : X → {0, 1} définit par ωD(v) = 1 si v ∈ D et ωD(v) = 0 sinon. Soit v ∈ V. Comme D est un dominant, v est dominé par D donc ωD ⊨ Cv. Donc ωD ⊨ Cv pour tout v ∈ V, c’est-à-dire ωD ⊨ FG, donc on a bien une bijection entre les modèles de FG et les dominants de G.