Contrôle Continu 1

5 Février 2025

Donner la table de vérité des formules suivantes :

  1. (a∨¬b) ⇒ (¬a⇒(c∨b)).
  2. (a⇔b) ⇒ (c⇔d).
  3. (a⇒(b∧c)) ⇒ (a∨b∨¬c).
Correction
  1. Vrai pour toutes les assignations sauf a = b = c = 0.
  2. Toujours vrai sauf pour :
    • a = 0, b = 0, c = 0, d = 1,
    • a = 0, b = 0, c = 1, d = 0,
    • a = 1, b = 1, c = 0, d = 1,
    • a = 1, b = 1, c = 1, d = 0.
  3. Toujours vrai sauf pour: a = 0, b = 0, c = 0.
  1. Donner une forme normale conjonctive de la formule : ¬((x∨a)∧(y∨¬z)) ∧ (a∨(¬b∧¬x)).
  2. Donner une forme normale disjonctive de la formule : (a∧b) ⇒ ¬(c∨¬d).
Correction
  1. On applique De Morgan (deux fois successivement) :

((¬x∧¬a)∨(¬y∧z)) ∧ (a∨(¬b∧¬x)).

On développe ensuite le ∨ sur le ∧. On peut vraiment imaginer qu’on est en train de développer un polynôme de la forme suivante (NX+NA) × (NY+Z) + A × (NB+NX) où on a remplacé ∧ par + et ∨ par ×. En faisant un développement comme on fait d’habitude, on trouve : NX × NY + NX × Z + NA × NY + NA × Z + A × NB + A × NX. À la fin, on trouve donc :

(¬x∨¬y) ∧ (¬x∨z) ∧ (¬a∨¬y) ∧ (¬a∨z) ∧ (a∨¬b) ∧ (a∨¬x)

  1. On commence par écrire A ⇒ B comme ¬A ∨ B: ¬(a∧b) ∨ ¬(c∨¬d). On applique De Morgan: (¬a∨¬b) ∨ (¬c∧d). On est en DNF!

Dans cet exercice, on note ⊕ pour le ou exclusif (ie, a ⊕ b vaut vrai si a ou b est vrai mais pas les deux).

  1. Donner une forme normale conjonctive de la formule a ⇔ (b⊕c).
  2. En déduire la transformation de Tseitin de la formule (u⊕v) ⊕ (w∧z).
Correction
  1. Le plus simple ici est de le faire avec une table de vérité. On voit vite que les contre-modèles sont :
  • a = 0, b = 1, c = 0
  • a = 0, b = 0, c = 1
  • a = 1, b = 0, c = 0
  • a = 1, b = 1, c = 1

En FNC: (a∨¬b∨c) ∧ (a∨b∨¬c) ∧ (¬a∨b∨c) ∧ (¬a∨¬b∨¬c).

G r ⊕, x1 r2 ⊕, x2 r->r2 r3 ∧, x3 r->r3 u u r2->u v v r2->v w w r3->w z z r3->z

On réexprime cette fonction comme: C1 ∧ C2 ∧ C3 où

  • C1 est x1 ⇔ (x2⊕x3)
  • C2 est x2 ⇔ (u⊕v)
  • C3 est x3 ⇔ (w∧z)

On met C1, C2, C3 en FNC. On utilise la question précédente pour C1 et C2 et le cours pour C3:

  • C1 est équivalente à (x1∨¬x2∨x3) ∧ (x1∨x2∨¬x3) ∧ (¬x1∨x2∨x3) ∧ (¬x1∨¬x2∨¬x3).
  • C2 est équivalente à (x2∨¬u∨v) ∧ (x2∨u∨¬v) ∧ (¬x2∨u∨v) ∧ (¬x2∨¬u∨¬v).
  • C3 est équivalente à (x3∨¬w∨¬z) ∧ (¬x3∨w) ∧ (¬x3∨z).

Au final, la transformation de Tseitin demandée est :

(x1∨¬x2∨x3) ∧ (x1∨x2∨¬x3) ∧ (¬x1∨x2∨x3) ∧ (¬x1∨¬x2∨¬x3) ∧ (x2∨¬u∨v) ∧ (x2∨u∨¬v) ∧ (¬x2∨u∨v) ∧ (¬x2∨¬u∨¬v) ∧ (x3∨¬w∨¬z) ∧ (¬x3∨w) ∧ (¬x3∨z).

Modéliser en logique propositionnelle et résoudre le problème suivant (c’est la modélisation plus que la réponse qui est importante ici).

Alice, Bob, Carole et David sont quatre amphibiens. Les crapauds disent toujours la vérité et les grenouilles mentent toujours.

Combien y a-t-il de grenouilles ?

Correction

On note CA (resp. CB, CC et CD) la proposition atomique qui signifie “Alice (resp. Bob, Carole et David) est un crapaud”. Le fait qu’Alice soit une grenouille est naturellement équivalent à ¬CA et le fait qu’Alice dise la vérité est équivalent à CA.

On a donc :

  • Alice dit : “David et moi ne sommes pas de la même espèce” se traduit directement par CA ⇔ ((CA∧¬CD)∨(¬CA∧CD)). Cependant, on peut facilement simplifier en CA ⇔ ¬CD.
  • Bob dit : “Carole est une grenouille.” se traduit par CB ⇔ ¬CC.
  • Carole dit : “Bob est une grenouille.” se traduit par CC ⇔ ¬CB.
  • David dit : “Il y a au moins deux crapauds parmi nous” se traduit par CD ⇔ ((CA∧CB)∨(CA∧CC)∨(CA∧CD)∨(CB∧CC)∨(CB∧CD)∨(CC∧CD)).

On peut donner une table de vérité :

CA CB CC CD F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

On a deux solutions mais dans les deux cas, il y a deux grenouilles ! On peut donc conclure qu’il y a deux grenouilles.