Une formule de la logique propositionnelle est une suite de symboles pouvant contenir :
Des lettres pour les variables propositionnelles : souvent, p, q, ….
Des connecteurs logiques :
La conjonction “et” : ∧
La disjonction “ou” : ∨
La flèche/implication “implique” (ou “si … alors …”) : →
La négation “non” : ¬
Des parenthèses
Des constantes propositionnelles : ⊤ (Vrai) et ⊥ (Faux)
Une variable ou une constante est une formule correcte
Si F est une formule correcte, alors ¬F est une formule correcte
Si F1 et F2 sont des formules correctes, alors (F1 ∧ F2), (F1 ∨ F2), (F1 → F2) sont des formules correctes
p est une formule correcte, donc ¬p aussi
¬p est une formule correcte, q aussi, donc (¬p ∨ q) est une formule correcte
(¬p ∨ q) est une formule correcte, donc (¬p ∨ q) → (¬p ∨ q) aussi.
p et q sont des formules correctes, donc (p ∧ q) aussi, et ¬(p ∧ q) également.
Pour savoir si la formule (¬p ∧ (q → p ∧ r)) est correcte, il faut vérifier qu’elle est bien parenthésée et la décomposer avec toutes ses sous-formules :
la formule est une conjonction (∧), avec ¬p et (t → ∧ r) comme sous-formules
¬p est correcte (car p est une formule correcte)
(q → p ∧ r) n’est pas correcte (il manque les parenthèses).
Donc la formule du début n’est pas correcte
Dès qu’il y a un connecteur binaire (→,∧,∨), il y a une sous-formule à gauche et une sous-formule à droite du connecteur, et des parenthèses autour.
Il est autorisé de ne pas mettre les parenthèses les plus extérieures. C’est-à-dire que si la formule est correcte et qu’elle commence et termine par une parenthèse, on peut les enlever.
(p ∧ (q ∨ (p → ¬r))) peut être réécrit comme ça : p ∧ (q ∨ (p → ¬r))
¬(p ∧ q) ne peut pas être réécrit comme ça : ¬p ∧ q.
Pour évaluer les valeurs de vérité que peut avoir une formule, on commence par regarder les connecteurs qui la composent, et les variables propositionnelles (p, q, …) qui s’y trouvent. Pour toutes ces variables, on va considérer les cas où elles sont vraies ou fausses.
Attention, une variable a toujours la même valeur de vérité dans une formule. Par exemple, pour une formule comme p → ((p ∨ ¬p) ∧ p), on n’aura que deux cas à étudier : quand p est vrai, et quand p est faux.
Pour écrire la table de vérité, on commencera donc par la colonne correspondant aux deux possibilités pour p :
| p | … |
|---|---|
| V | … |
| F | … |
Quand une formule contient plusieurs variables, il y a plus de possibilités à étudier. Avec trois variables p, q, r par exemple, il faut considérer le cas où elles sont toutes vraies, toutes fausses, et les cas intermédiaires. Autrement dit
| p | q | r | … |
|---|---|---|---|
| V | V | V | … |
| V | V | F | … |
| V | F | V | … |
| V | F | F | … |
| F | V | V | … |
| F | V | F | … |
| F | F | V | … |
| F | F | F | … |
En effet, pour chaque variable, il y a deux possibilités. Pour chacune des ces possibilités, il faut regarder les possibilités des autres variables, etc… Le nombre de lignes correspond donc à “2 possibilités pour p” × “2 possibilités pour q” × “2 possibilités pour r” = 8.
En général, si la formule contient n variables propositionnelles différentes, la table de vérité aura 2n lignes.
Si ⊥ ou ⊤ apparaît dans la formule, il ne faut pas ajouter de ligne, comme ce sont des constantes, il n’y a qu’une seule possibilité : ⊥ est forcément faux, et ⊤ est forcément vrai.
Pour savoir quelles colonnes mettre dans notre table de vérité, il faut découper la formule et identifier son connecteur principal. (Ici il faut faire très attention aux parenthèses !)
Si la formule est – par exemple – une conjonction F1 ∧ F2, il faut préparer une colonne pour F1 et une pour F2. Ensuite, pour toutes les formules récupérées ainsi, je refais la même chose, jusqu’à tomber sur les variables p, q, … (qui ont déjà leur colonne, on ne les recopie pas).
(p ∧ (¬q ∨ (r → (p ∧ q))))
(les sous-formules identifiées sont en rouge)
La formule est une conjonction, avec p et (¬q ∨ (r → (p ∧ q))) pour sous-formules. Comme p est une variable, je ne dois regarder que l’autre sous formule, pour laquelle je devrai faire une colonne (après).
(¬q ∨ (r → (p ∧ q))) est une disjonction, qui a pour sous-formules ¬q et (r → (p ∧ q)), je continue à décomposer.
¬q est une négation qui a pour sous-formule uniquement q.
(r → (p ∧ q)) est une implication qui a deux sous-formules : r et (p ∧ q).
les deux sous-formules de (p ∧ q) sont p et q
On peut maintenant préparer les colonnes de la table de vérité : on regarde les sous formules, et on les écrit. D’abord les variables propositionnelles, puis les sous-formules (en rouge ci-dessus) en partant de la fin dans l’ordre où on les a écrites, et enfin on inscrit la formule entière :
| p | q | r | (p ∧ q) | (r → (p ∧ q)) | ¬q | (¬q ∨ (r → (p ∧ q))) | (p ∧ (¬q ∨ (r → (p ∧ q)))) |
|---|---|---|---|---|---|---|---|
| … | … | … | … | … | … | … |
Il y a une raison : on va calculer (dans chaque ligne) la valeur de vérité de chaque formule, en fonction de ses sous-formules. Avec l’ordre comme dans l’exemple ci-dessous, remarquez que si on calcule de gauche à droite, à chaque fois que l’on regardera une sous-formule, elle sera à gauche, donc on l’aura déjà calculée. On commence avec les variables propositionnelles, comme vu à la section sur les lignes, et on finira par la formule principale.
Pour compléter la table, il faut connaître par cœur les règles pour chaque connecteur, elles sont rappelées ci-dessous.
| F1 | F2 | F1 ∧ F2 |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Une conjonction est vraie si les deux sous-formules sont vraies. Dans tous les autres cas elle est fausse.
| F1 | F2 | F1 ∨ F2 |
|---|---|---|
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
Une disjonction est fausse si les deux sous-formules sont fausses. Dans tous les autres cas elle est vraie.
| F1 | F2 | F1 → F2 |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Une implication est fausse si une formule vraie implique une formule fausse. Dans tous les autres cas elle est vraie.
| F | ¬F |
|---|---|
| V | F |
| F | V |
La négation inverse la vérité de sa sous formule.
On prend la formule suivante : (¬q ∨ (r → (p ∧ q))) (qui apparaissait dans l’exemple précédent), et l’on prépare les lignes et les colonnes de la table, comme on l’a expliqué un peu plus haut.
Si vous pensez avoir compris, essayez de remplir la table avant de lire la suite !
| p | q | r | (p ∧ q) | (r → (p ∧ q)) | ¬q | (¬q ∨ (r → (p ∧ q))) |
|---|---|---|---|---|---|---|
| V | V | V | ||||
| V | V | F | ||||
| V | F | V | ||||
| V | F | F | ||||
| F | V | V | ||||
| F | V | F | ||||
| F | F | V | ||||
| F | F | F |
Pour la première colonne à remplir, on applique la table de la conjonction (donnée plus haut). On ne regarde donc que les valeurs de p et q (parfois il y a des doublons, c’est normal !).
On obtient donc la table suivante.
| p | q | r | (p ∧ q) | (r → (p ∧ q)) | ¬q | (¬q ∨ (r → (p ∧ q))) |
|---|---|---|---|---|---|---|
| V | V | V | V | |||
| V | V | F | V | |||
| V | F | V | F | |||
| V | F | F | F | |||
| F | V | V | F | |||
| F | V | F | F | |||
| F | F | V | F | |||
| F | F | F | F |
(en effet, on a mis les lignes à vrai dans les cas où p et q sont vrais, et faux ailleurs).
Pour la suite, on va remplir la deuxième colonne : c’est une implication avec deux sous-formules. On regarde donc deux colonnes : celle de r, et celle de (p ∧ q) (que l’on vient de remplir). C’est (p ∧ q) qui va jouer le rôle de F2 dans la table de l’implication. On utilise ensuite la table de l’implication.
| p | q | r | (p ∧ q) | (r → (p ∧ q)) | ¬q | (¬q ∨ (r → (p ∧ q))) |
|---|---|---|---|---|---|---|
| V | V | V | V | V | ||
| V | V | F | V | V | ||
| V | F | V | F | F | ||
| V | F | F | F | V | ||
| F | V | V | F | F | ||
| F | V | F | F | V | ||
| F | F | V | F | F | ||
| F | F | F | F | V |
(en effet, on a mis les lignes à faux quand r est vrai et p ∧ q est faux, et vrai dans les autres lignes.)
Pour la colonne suivante, il suffit de regarder les valeurs de q, et de mettre la valeur inverse, car on applique la table de la négation :
| p | q | r | (p ∧ q) | (r → (p ∧ q)) | ¬q | (¬q ∨ (r → (p ∧ q))) |
|---|---|---|---|---|---|---|
| V | V | V | V | V | F | |
| V | V | F | V | V | F | |
| V | F | V | F | F | V | |
| V | F | F | F | V | V | |
| F | V | V | F | F | F | |
| F | V | F | F | V | F | |
| F | F | V | F | F | V | |
| F | F | F | F | V | V |
Pour finir avec la dernière colonne, on utilise la table de la disjonction, et on va pour cela regarder les colonnes des deux sous formules : ¬q et (r → (p ∧ q). On va mettre à Faux les lignes où les deux colonnes sont à Faux, et toutes les autres à Vrai.
| p | q | r | (p ∧ q) | (r → (p ∧ q)) | ¬q | (¬q ∨ (r → (p ∧ q))) |
|---|---|---|---|---|---|---|
| V | V | V | V | V | F | V |
| V | V | F | V | V | F | V |
| V | F | V | F | F | V | V |
| V | F | F | F | V | V | V |
| F | V | V | F | F | F | F |
| F | V | F | F | V | F | V |
| F | F | V | F | F | V | V |
| F | F | F | F | V | V | V |
Et c’est terminé, on peut voir que la formule est presque toujours vraie, elle est seulement fausse quand p est vrai, et q et r sont faux.
Pour vous entraîner, essayez de refaire des tables avec des formules que vous avez écrites, ou des formules que vous pouvez trouver dans les TD, dans le cours, ou ailleurs sur internet (par exemple https://fr.wikipedia.org/wiki/Calcul_des_propositions)