Vérité des formules

Si nous avons quelques propositions atomiques que nous composons en une formule, nous pouvons essayer de décider si la formule entière est vraie ou fausse.

Vérité d’une proposition

Précisons d’abord ce qu’est la valeur de vérité d’une proposition. Si nous avons une proposition p, nous devrions être capables de décider si elle est vraie ou fausse. Une proposition vraie aura la valeur de vérité 1 et une proposition fausse la valeur 0.

Une valuation est alors une règle e qui associe à une proposition donnée soit 0, soit 1. Quand nous écrivons e(p), nous voulons savoir si la proposition p est vraie. Si p est la proposition « deux fois deux font quatre », alors e(p) = 1, car c’est une proposition vraie. Si q est la proposition « Hugo est une fille », alors e(q) = 0, car Hugo n’est pas une fille. e est donc une fonction qui nous indique si la proposition est vraie.

Il faut ici bien comprendre que e n’est pas une fonction magique qui sait tout sur le monde. Elle se comporte comme on le lui dit. Elle ne sait pas si Hugo est un garçon ou une fille. Au début du calcul, c’est à nous de déclarer comment la fonction de valuation doit se comporter. Si nous lui disons que Hugo est une fille, elle nous renverra e(q) = 1.

Valeur de vérité des connecteurs

Pour pouvoir établir la valeur de vérité d’une formule, nous devons savoir évaluer celle des connecteurs. Autrement dit, si nous connaissons les valuations e(p) et e(q), quelle sera la valeur de vérité des formules p ∧ q, p ⇒ q, etc.

Chaque connecteur se comporte différemment et sert à autre chose, nous allons donc les étudier un par un.

Conjonction

La conjonction se note p ∧ q et se lit « p et en même temps q ». Prenons pour exemple la formule « La France se trouve en Europe occidentale et en même temps sa capitale est Paris ». Quand toute cette phrase sera-t-elle vraie ?

Le connecteur « et en même temps » nous aide déjà à déterminer la vérité. Il dit explicitement qu’il veut que les deux propositions, à gauche et à droite, soient vraies. Si les deux propositions p et q sont vraies, c’est-à-dire e(p) = 1 et e(q) = 1, alors la conjonction entière est vraie. Dans le cas contraire, où l’une des propositions est fausse ou les deux, la formule entière est fausse.

Un exemple de conjonction qui n’est pas vraie : « La Loire est un fleuve et en même temps la Loire traverse la Russie ». Il est vrai que la Loire est un fleuve, mais il n’est pas vrai qu’elle coule en Russie, donc la conjonction entière n’est pas vraie.

Le tableau suivant le présente clairement :

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

Dans les deux premières colonnes se trouvent les valeurs de vérité des propositions p et q, et dans la troisième la valeur de vérité de la formule p ∧ q.

Disjonction

La disjonction se note p ∨ q et se lit « p ou q ». Exemple : « La Russie se trouve en Europe ou en Asie. » Quand toute la phrase sera-t-elle vraie ?

Pour une disjonction, il suffit qu’au moins une des possibilités soit vraie. Le connecteur « ou » nous laisse le choix, il suffit que sa partie gauche ou sa partie droite soit vraie. La seule petite différence avec le langage courant est que le « ou » logique est vrai même quand les deux propositions sont vérifiées en même temps. Ce n’est pas toujours l’usage : dans la conversation, nous employons souvent « ou » de façon exclusive, c’est-à-dire « soit …, soit … »

Il existe à ce sujet une blague classique : une famille choisit une voiture d’occasion. Le père dit au vendeur : « nous avons décidé de prendre une voiture bleue ou rouge ». Le vendeur leur a vendu les deux voitures. C’est une illustration de la différence entre le « ou » logique et le « ou » de la conversation : le père voulait sans doute dire qu’ils choisiraient exactement une de ces voitures, tandis que le vendeur a considéré comme valable la possibilité de leur vendre les deux.

La phrase précédente sur la Russie est vraie, car les deux propositions sont vraies. La phrase « le nombre 7 est divisible par 3 ou le nombre 7 est premier » est vraie, car sept est un nombre premier. Il n’est certes pas divisible par trois, mais cela ne nous gêne plus. Table de vérité :

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

Implication

L’implication se note p ⇒ q et se lit « si p, alors q ». Un exemple d’implication est la phrase « si nous mangeons beaucoup de bonbons, alors nous aurons mal au ventre ». Quand la phrase sera-t-elle vraie ?

L’implication logique est le plus traître de tous les connecteurs et, même dans le langage courant, elle n’est souvent pas bien comprise et est confondue avec l’équivalence. Essayons de répondre à la question : la réciproque q ⇒ p est-elle vraie elle aussi ?

Nous savons que si nous mangeons beaucoup de bonbons, alors nous aurons mal au ventre. Est-il vrai aussi que si nous avons mal au ventre, alors nous avons mangé beaucoup de bonbons ? Certainement pas : nous avons pu manger tout autre chose et avoir quand même mal au ventre, ou avoir mal au ventre pour une tout autre raison. La réciproque n’est donc pas forcément vraie. Si p ⇒ q et q ⇒ p sont vraies toutes les deux, il s’agit d’une équivalence, voir plus loin.

Un autre exemple : « s’il pleut demain, alors Hugo prendra un parapluie ». Et maintenant je te dis que Hugo a pris un parapluie. La question est : a-t-il plu ce jour-là ? Beaucoup de gens ont tendance à dire que oui, évidemment, puisque Hugo a pris un parapluie alors qu’il devait pleuvoir. Mais la phrase d’origine n’est pas construite ainsi !

En réalité, Hugo a pu prendre un parapluie pour une tout autre raison dont nous n’avons aucune idée. Peut-être qu’il prend toujours un parapluie quand il va rendre visite à sa grand-mère, qui habite loin de l’arrêt de bus. Ou bien il a décidé d’acheter un nouveau parapluie et veut jeter l’ancien. Ce sont toutes des raisons légitimes pour lesquelles Hugo a pu prendre un parapluie même s’il n’a pas forcément plu.

Nous pouvons maintenant répondre à la question : quand l’implication est-elle vraie ? Quand les deux propositions sont vraies, l’implication est certainement vraie : « si 42 est un nombre entier naturel, alors il est positif ». Les deux propositions sont vraies, donc l’implication entière est vraie. Un autre exemple est l’implication « si 42 est un nombre entier naturel, alors il est négatif ». Cette implication n’est pas vraie, car à partir d’une vérité, on essaie de déduire quelque chose qui n’est pas vrai.

Restent enfin les cas où la première proposition est fausse. Dans ce cas, la vérité de la seconde proposition ne nous intéresse plus. Si l’on part d’une fausseté, on peut ensuite raconter ce que l’on veut. Ce sont des phrases du genre « si 1 est un nombre négatif, alors nous sommes le père Noël » ou « si la Terre est plate, alors le soleil est bleu ». Dans de tels cas, l’implication est automatiquement vraie, simplement parce qu’elle part d’une fausseté. Table de vérité :

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

Équivalence

L’équivalence s’écrit p ⇔ q et se lit « p si et seulement si q ». Un exemple d’équivalence est « le nombre x est divisible par deux si et seulement s’il est pair ». Quand toute la phrase sera-t-elle vraie ?

Pour une équivalence, nous attendons que les deux propositions soient en telle symbiose que soit les deux sont vraies, soit aucune ne l’est. Donc soit le nombre x est pair et en même temps divisible par deux, soit il n’est ni l’un ni l’autre. Il ne peut pas arriver que x soit pair sans être divisible par deux.

Exemple : « Louis lit un livre si et seulement s’il est aux toilettes. » Pour que l’équivalence soit satisfaite, chaque fois que Louis est aux toilettes, il doit lire un livre. Et en même temps, chaque fois qu’il lit un livre, il doit être aux toilettes. Il ne peut pas arriver qu’il lise un livre, par exemple, dans son lit.

Nous pouvons exprimer l’équivalence à l’aide de deux implications. Ainsi, p ⇔ q pourrait se réécrire p ⇒ q et en même temps q ⇒ p. Table de vérité :

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

Négation

La négation est une opération unaire, nous l’écrivons soit avec une barre $\bar{p}$, soit avec ce symbole : ¬p. La négation nie l’affirmation d’origine. Si nous avons la proposition « Léa est chanteuse », la négation nous donne la proposition « Il n’est pas vrai que Léa soit chanteuse » ou, plus brièvement, « Léa n’est pas chanteuse ». En pratique, nous pouvons toujours former la négation en plaçant « Il n’est pas vrai que… » devant la proposition.

La négation inverse la valeur de vérité, c’est-à-dire qu’elle transforme 0 en 1 et 1 en 0. Nous pouvons donc écrire ¬0 = 1 et ¬1 = 0.

Attention à certains pièges. Prenons l’affirmation « la neige est blanche ». Quelle est sa négation ? Certains pourraient penser à « la neige est noire », mais ce n’est pas vrai ! Avec la règle précédente, la négation est la proposition « il n’est pas vrai que la neige soit blanche ». Cela signifie-t-il forcément qu’elle doit être noire ? Non, elle peut être par exemple rose bonbon.

Tableau de tous les connecteurs

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

Valeur de vérité d’une formule entière

Nous savons maintenant évaluer la vérité de deux propositions reliées par un connecteur. Nous évaluons une formule entière de façon tout à fait analogue. Si nous avons la formule (p ⇒ q) ∧ r, dès que nous avons évalué la formule (p ⇒ q), par exemple à 1, nous obtenons une conjonction classique 1 ∧ r, que nous savons déjà traiter.

En appliquant successivement les connecteurs les plus simples, nous arrivons à la valeur de vérité finale de la formule entière. On utilise souvent pour cela la méthode dite de la table de vérité, décrite plus loin.

Méthode de la table de vérité

La méthode de la table de vérité s’utilise pour évaluer des formules plus compliquées. Dans les n premières colonnes, nous écrivons les n variables propositionnelles avec lesquelles travaille la formule, et dans les colonnes suivantes nous plaçons peu à peu les sous-formules que la formule contient. Un exemple rendra cela plus clair :

Prenons la formule (p ∨ q) ∧ (q ⇒ p). Au début, nous écrivons dans le tableau toutes les variables propositionnelles, c’est-à-dire p et q, et toutes les combinaisons de leurs valuations :

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

Ensuite, nous y ajoutons des colonnes pour les différentes sous-formules p ∨ q et q ⇒ p.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Maintenant, nous évaluons ces formules et complétons les colonnes avec des zéros ou des uns. Le tableau contient toutes les informations nécessaires. Nous procédons ainsi : quand nous évaluons p ∨ q à la première ligne, nous remplaçons p par 1 et q aussi par 1. Nous obtenons ainsi l’expression 1 ∨ 1. L’évaluation de cette expression donne de nouveau 1, donc nous écrivons 1 dans le tableau :

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Nous complétons ainsi peu à peu tout le tableau :

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

Il reste maintenant à évaluer la formule entière. Appelons-la par exemple φ = (p ∨ q) ∧ (q ⇒ p). Nous ajoutons au tableau une colonne avec φ et nous l’évaluons, en utilisant pour cela les deux colonnes précédentes.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

Le tableau est maintenant complet et il nous donne la valeur de vérité de la formule pour toutes les valuations possibles. Par exemple, si e(p) = 1 et en même temps e(q) = 1, alors la formule est vraie. Dans le cas où e(p) = 0 et e(q) = 1, la formule n’est pas vraie.

Remarque que nous ne pouvons pas dire que « la formule est vraie ». Cette phrase n’a pas de sens, car pour pouvoir dire que la formule est vraie, il faudrait dire dans quelle valuation elle est vraie. Nous pouvons donc dire que « la formule φ est vraie dans la valuation e₁ et n’est pas vraie dans la valuation e₂ ».

Le seul cas où l’on pourrait dire que la formule est vraie, c’est si elle est vraie dans toutes les valuations possibles. Par exemple, la formule p ∨ ¬p est vraie dans toutes les valuations, nous pouvons donc dire que la formule est vraie. De même pour le cas où une formule est fausse dans toutes les valuations.

De telles formules ont alors une désignation spéciale. Une formule qui est vraie dans toutes les valuations s’appelle une tautologie. Une formule qui n’est satisfaite dans aucune valuation s’appelle une contradiction.