Exemples de logique propositionnelle

Dans cet article, nous allons voir quelques formules et leurs valuations possibles à l’aide de la méthode de la table de vérité.

Premier exemple

Essayons de trouver quand cette formule est vraie : ϕ = (p ∧ q) ∨ ¬q. Écrivons dans le tableau les variables propositionnelles p et q :

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Ajoutons ensuite au tableau la première partie de la formule : (p ∧ q), la négation ¬q, puis la formule entière :

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Calculons maintenant les valeurs de la troisième colonne, qui est une simple conjonction, et aussi celles de la négation – là, il suffit de mettre les valeurs inverses de celles de la deuxième colonne :

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Enfin, calculons les valeurs de la dernière colonne. C’est la formule entière. Dans notre tableau, nous calculons donc la disjonction « entre la troisième et la quatrième colonne ». Résultat :

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Deuxième exemple

Même énoncé, autre formule : ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Nous voyons que la formule contient les variables propositionnelles p et q et leurs négations. Nous commençons donc par construire un tableau avec les deux variables et leurs négations :

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Ajoutons ensuite les formules p ∧ ¬q et ¬p ⇒ q, que nous savons déjà évaluer facilement, car le tableau contient à la fois les valuations des propositions et celles de leurs négations. Le tableau ressemble à ceci :

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Il nous reste enfin à évaluer la formule entière, qui est l’équivalence entre les deux dernières colonnes :

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Troisième exemple

Le troisième exemple sera un peu plus compliqué : essayons avec trois variables propositionnelles, ce qui complique le calcul du tableau. La formule sera la suivante : ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Comme il y a trois variables propositionnelles, le nombre total de valuations possibles est égal à huit :

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

Ensuite, nous procédons comme dans le cas précédent : nous évaluons chaque colonne dans les huit lignes. Le tableau entier ressemblera à ceci :

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Quatrième exemple

Cet exemple n’est plus donné comme une simple formule, mais comme un problème en langage courant. Trois amis qui veulent aller à une grande fête où l’on distribuera des pizzas gratuites ne s’apprécient pas vraiment et posent leurs conditions pour y aller. Ils s’appellent Mathieu, Jules et Paul. Les règles sont les suivantes :

1. Si Mathieu y va, alors Jules y va aussi.
2. Paul vient à la fête ou, si Mathieu y vient, alors Jules n’y vient pas.
3. Paul vient si et seulement si Mathieu ne vient pas ou Jules ne vient pas.

La question est : peuvent-ils tous venir à la fête ? Sinon, qui peut y aller sans enfreindre aucune règle ?

Nous devons d’abord réécrire les propositions précédentes avec des variables propositionnelles et des formules. Notons donc M, J et P les variables propositionnelles (Mathieu, Jules, Paul), chacune signifiant une proposition du type « Mathieu ira à la fête ». La première règle peut se réécrire ainsi : M ⇒ J – « si M, alors J », c’est-à-dire « si Mathieu va à la fête, alors Jules va à la fête ».

Voici comment réécrire la deuxième règle. Elle commence par la phrase « Paul vient à la fête ou… », nous aurons donc évidemment besoin d’une disjonction. Pour l’instant, écrivons : P ∨ … La partie suivante de la phrase dit : « si Mathieu y vient, alors Jules n’y vient pas ». C’est une implication, où il faut encore utiliser une négation à droite. « Jules ne vient pas » = ¬J. L’implication entière s’écrit : M ⇒ ¬J. Nous l’ajoutons à la disjonction précédente : P ∨ (M ⇒ ¬J).

Nous réécrivons la troisième règle ainsi : nous commençons par « Paul vient si et seulement si ». Cela signifie une équivalence : P ⇔ … Ensuite nous avons « Mathieu ne vient pas ou Jules ne vient pas », que nous réécrivons ainsi : ¬M ∨ ¬J. Nous assemblons le tout : (P ⇔ (¬M ∨ ¬J)).

Mettons maintenant toutes les formules dans le tableau et calculons les valeurs :

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

La question était de savoir si les trois garçons peuvent aller à la grande fête. Nous trouvons la réponse à la première ligne. Elle correspond au cas où tous les garçons y vont – ce qui est signalé par les trois 1 des trois premières colonnes. Toutes les conditions sont-elles remplies ? La première oui (quatrième colonne), la deuxième aussi (cinquième colonne), mais la dernière non (dernière colonne), il y a un zéro. Cela signifie que, si les trois y vont, la troisième condition ne sera pas remplie.

Nous cherchons donc les lignes où il n’y a que des 1 aux positions qui représentent les conditions (c’est-à-dire les trois dernières colonnes). Un 1 signifie que la condition est remplie. Nous voyons que cela arrive dans deux cas : quand Jules et Paul y vont mais pas Mathieu, et quand seul Paul y va.

Tu peux aussi le calculer en ajoutant au tableau la formule ϕ, qui sera la conjonction des trois conditions. Elle s’écrit ainsi : ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Elle représente ce que nous voulons – que toutes les formules (toutes les conditions) soient remplies. Le tableau ressemblerait alors à ceci :

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Quelques exemples de plus sur la méthode de la table de vérité

Comme j’ai écrit un programme qui sait construire automatiquement tout le tableau à partir d’une formule donnée, je dois bien l’utiliser, et voici donc encore quelques formules résolues :

Formule : ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Table de vérité :

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formule : (a ∨ ¬a) ⇔ (b ∧ ¬b). Table de vérité :

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formule : ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Table de vérité :

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formule : ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Table de vérité :

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formule : ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Table de vérité :

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$