TP 1 : Formules propositionnelles

Systèmes Logiques

08 Janvier 2025

Vrai ou faux :

  1. Si F est valide alors F est satisfiable.
  2. Si F est satisfiable alors ¬F n’est pas satisfiable.
  3. Si F est contradictoire alors ¬F est valide.
  4. Si F est satisfiable alors G ⇒ F est satisfiable.
Correction
  1. Vrai.
  2. Faux, si F est valide, ce n’est pas possible.
  3. Vrai.
  4. Vrai, n’importe quel modèle de F sera un modèle de G ⇒ F. En effet, soit ce modèle est un modèle de G et alors c’est bien un modèle de F et de G donc de G ⇒ F. Ou c’est un contre-modèle de G, et dans ce cas, l’implication est vrai car la prémisse est fausse !

Dire si les formules suivantes sont des formules valides. Si non, justifiez en donnant un contre-modèle.

  1. (x∨y∨¬z) ⇒ (y∧(¬x∨¬z))
  2. (x∧¬x) ⇒ ((y∨z)∧x)
  3. x ⇒ ((y∧z)⇒(y∨z)).
Correction
  1. Non, en considérant x = 1, y = 0, z = 0. La partie gauche de l’implication est vérifiée mais pas la partie droite en raison du fait que y = 0.
  2. Oui car x ∧ ¬x est une contradiction, l’implication est donc toujours vérifiée.
  3. Oui car ((y∧z)⇒(y∨z)) est valide.

Dessinez sous forme arborescente et donner les tables de vérités des formules suivantes.

  1. (x∧y∧z) ⇒ (¬x∨¬y∨¬z).
  2. (x∧y∧z) ∨ ((x∧¬z)∨(y∧¬z)).
  3. ((x∨y)⇒(¬z)) ⇒ (z∨y).
Correction
  1. (x∧y∧z) ⇒ (¬x∨¬y∨¬z).
    x y z ⟦F⟧(ω)
    0 0 0 1
    0 0 1 1
    0 1 0 1
    0 1 1 1
    1 0 0 1
    1 0 1 1
    1 1 0 1
    1 1 1 0
  2. (x∧y∧z) ∨ ((x∧¬z)∨(y∧¬z)).
    x y z ⟦F⟧(ω)
    0 0 0 0
    0 0 1 0
    0 1 0 1
    0 1 1 0
    1 0 0 1
    1 0 1 0
    1 1 0 1
    1 1 1 1
  3. ((x∨y)⇒(¬z)) ⇒ (z∨y).
    x y z ⟦F⟧(ω)
    0 0 0 0
    0 0 1 1
    0 1 0 1
    0 1 1 1
    1 0 0 0
    1 0 1 1
    1 1 0 1
    1 1 1 1

Soit F, G, H des formules propositionnelles.

  1. Les formules de De Morgan affirment que :

Vérifiez leur véracité.

  1. Vérifiez aussi les identités suivantes :

À quoi ces identités vous font-elles penser ?

Correction

Pour vérifier une identité, il suffit de vérifier que la sémantique de chaque formule est la même en fonction des sémantiques de chaque formule (qui sont dans {0, 1}). On peut donc le faire via une table de vérité :

F G ¬(F∧G) ¬F ∨ ¬G
0 0 1 1
0 1 1 1
1 0 1 1
1 1 0 0
F G ¬(F∨G) ¬F ∧ ¬G
0 0 0 1
0 1 0 0
1 0 0 0
1 1 0 0
F G H F ∧ (G∨H) (F∧G) ∨ (F∧H)
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 0 0
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1
F G H F ∨ (G∧H) (F∨G) ∧ (F∨H)
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1

Prouver que l’ensemble de connecteur { ⊕ } n’est pas fonctionnellement complet mais que {⊕,∧,1} est fonctionnellement complet (où 1 est une constante qui s’évalue toujours à vrai).

Correction

Soit p une proposition atomique et f la fonction booléenne sur {0, 1}{p} qui vaut tout le temps 1. On montrer qu’on ne peut pas l’écrire avec ⊕ seulement. En effet, soit F une formule booléenne ne contenant que l’opérateur ⊕ et la proposition atomique p. On montre que ⟦F⟧(⋅) ne peut pas être la fonction booléenne constante égale à 1. En effet, ⟦F⟧(ω) où ω = {p ↦ 0} est forcément égal à 0. On peut le prouver par induction sur le nombre de connecteur ⊕ dans la formule. S’il n’y a aucun connecteur ⊕, alors F est la formule p et ⟦F⟧(ω) = 0 par définition. Sinon, F = F1 ⊕ F2 et F1 et F2 ont strictement moins de connecteurs ⊕ que F. Or ⟦F⟧(ω) = |⟦F1⟧(ω)−⟦F2⟧(ω)| par définition, et ⟦F1⟧(ω) = 0 et ⟦F2⟧(ω) = 0 par induction. Donc ⟦F⟧(ω) = 0.

On observe que la même preuve fonctionne pour le système de connecteur {⊕, ∧ }.

Pour montrer la complétude de {⊕,∧,1}, on montre que F ∨ G et ¬F peuvent être réécrit seulement avec ces connecteurs. Ainsi ¬F est logiquement équivalent à F ⊕ 1. De plus, F ∨ G est logiquement équivalent à ¬(¬F∧¬G) par la question précédente. Et donc à 1 ⊕ ((1⊕F)∧(1⊕G)).