3. Logique propositionnelle
3.1 Propositions et connecteurs
Une proposition élémentaire, notée p, q, r, etc., possède exactement une valeur : vraie ou fausse. Des formules composées sont construites avec les connecteurs suivants.
| Forme | Lecture | Condition de vérité |
|---|---|---|
¬p |
non p |
vraie lorsque p est fausse |
p ∧ q |
p et q |
vraie seulement si les deux sont vraies |
p ∨ q |
p ou q inclusif |
vraie si au moins une des deux est vraie |
p → q |
si p, alors q |
fausse seulement lorsque p est vraie et q fausse |
p ↔ q |
p si et seulement si q |
vraie lorsque p et q ont la même valeur |
L'implication ne dit pas que l'antécédent cause le conséquent. Sa définition vérifonctionnelle est p → q ≡ ¬p ∨ q.
La convention standard de priorité est ¬, puis ∧, ∨, →, ↔. Le cours affiche ∨ avant ∧, ce qui est inhabituel et contredit la convention générale. Pour toute formule mixte, utiliser des parenthèses explicites.
3.2 Tables de vérité
Pour n variables, une table complète possède 2^n lignes. On calcule les sous-formules de l'intérieur vers l'extérieur. La colonne finale permet de déterminer si la formule est :
- tautologique : toujours vraie;
- contradictoire : toujours fausse;
- seulement satisfiable : vraie dans certaines interprétations;
- équivalente à une autre : colonnes finales identiques.
La vidéo Exo7 rappelle qu'un contre-exemple suffit pour réfuter une affirmation universelle, tandis qu'un témoin suffit pour établir une affirmation existentielle.
3.3 Équivalences essentielles
Les équivalences suivantes servent à transformer des formules sans changer leur sens :
- implication :
p → q ≡ ¬p ∨ q; - implication à antécédent nié :
¬p → q ≡ p ∨ q; - contraposition :
p → q ≡ ¬q → ¬p; - double négation :
¬¬p ≡ p; - idempotence :
p ∧ p ≡ petp ∨ p ≡ p; - commutativité :
p ∧ q ≡ q ∧ p,p ∨ q ≡ q ∨ p; - associativité :
p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r, et de même pour∨; - distributivité :
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r); - distributivité duale :
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r); - De Morgan :
¬(p ∧ q) ≡ ¬p ∨ ¬qet¬(p ∨ q) ≡ ¬p ∧ ¬q.
Une équivalence peut être vérifiée en comparant les colonnes finales d'une table de vérité.