Propositions et connecteurs logiques

Toutes les mathématiques reposent sur un geste : démontrer. Pas convaincre, pas illustrer, démontrer. Et démontrer suppose un langage où chaque phrase est soit vraie, soit fausse, sans zone grise. Ce langage, c’est la logique propositionnelle. C’est le tout premier outil à poser avant d’écrire la moindre démonstration sérieuse.

À la fin de ce chapitre tu sauras répondre à trois questions : qu’est-ce qu’un énoncé qu’on a le droit d’appeler vrai ou faux, comment combiner de tels énoncés avec « non », « et », « ou », « si… alors », et pourquoi l’implication a un comportement qui surprend tout le monde la première fois.

L’enquête : raisonner juste

Imagine un détective sur une scène de crime. Il ne dispose que de faits, dont chacun est soit vrai, soit faux : « la fenêtre était verrouillée », « le suspect était en ville », « l’alarme s’est déclenchée ». À partir de ces faits, il enchaîne des déductions : si la fenêtre était verrouillée et l’alarme ne s’est pas déclenchée, alors l’intrus avait une clé.

Tout le raisonnement tient dans ces petits mots de liaison : non, et, ou, si… alors. La logique propositionnelle, c’est exactement ça, mais rendue assez précise pour qu’une machine puisse la vérifier. Le détective travaille à l’intuition. Nous, on va poser les règles noir sur blanc.

Qu’est-ce qu’une proposition

Une proposition Proposition Énoncé mathématique dont on peut dire sans ambiguïté s'il est vrai ou s'il est faux, sans troisième possibilité. Ce principe, appelé bivalence, est le point de départ de toute la logique propositionnelle. est un énoncé dont on peut dire sans ambiguïté s’il est vrai ou faux. C’est tout, mais c’est strict.

• « 2 + 2 = 4 » est une proposition (vraie).
• « 7 est un nombre pair » est une proposition (fausse).
• « Quelle heure est-il ? » n’est pas une proposition : une question n’est ni vraie ni fausse.
• « $x > 3$ » n’est pas une proposition tant que $x$ n’est pas fixé : sa valeur de vérité dépend de $x$. On en fera une vraie proposition au chapitre 2 grâce aux quantificateurs.

Le principe qui dit qu’une proposition est soit vraie, soit fausse, sans troisième possibilité, s’appelle la bivalence. On note traditionnellement le vrai $V$ (ou $1$) et le faux $F$ (ou $0$). On désigne les propositions par des lettres : $P$, $Q$, $R$.

Joue avec une table de vérité

Avant toute théorie, manipule. Le tableau ci-dessous est une table de vérité Table de vérité Tableau qui donne la valeur de vérité d'une formule logique pour chacune des combinaisons possibles des valeurs de ses variables. Pour n variables, elle comporte 2ⁿ lignes. : il donne la valeur de deux formules pour chaque combinaison possible de $P$ et $Q$. Bascule les valeurs de $P$ et $Q$ avec les boutons : la ligne correspondante se surligne. Ta mission : trouve la seule ligne où $P \land Q$ vaut $V$, puis la seule ligne où $P \lor Q$ vaut $F$.

Tu viens de rencontrer deux connecteurs : $\land$ (et) et $\lor$ (ou). Formalisons-les, avec leur petit frère $\lnot$ (non).

Les trois premiers connecteurs : non, et, ou

Un connecteur logique Connecteur logique Symbole qui combine une ou deux propositions pour en former une nouvelle. Les cinq connecteurs de base sont la négation (¬), la conjonction (∧), la disjonction (∨), l'implication (⇒) et l'équivalence (⇔). est un symbole qui fabrique une nouvelle proposition à partir d’une ou deux propositions. On définit chacun par sa table de vérité, qui est sa définition complète : rien de caché.

La négation : ¬

La négation inverse la valeur de vérité. $\lnot P$ se lit « non $P$ » et vaut $V$ exactement quand $P$ vaut $F$.

$P$	$\lnot P$
V	F
F	V

La conjonction : ∧

$P \land Q$ se lit « $P$ et $Q$ ». Elle vaut $V$ uniquement quand les deux sont vraies en même temps.

$P$	$Q$	$P \land Q$
V	V	V
V	F	F
F	V	F
F	F	F

La disjonction : ∨

$P \lor Q$ se lit « $P$ ou $Q$ ». Attention au piège : c’est le ou inclusif. Il vaut $V$ dès qu’au moins une des deux est vraie, y compris si les deux le sont.

$P$	$Q$	$P \lor Q$
V	V	V
V	F	V
F	V	V
F	F	F

L’implication, le connecteur qui piège

Voici le connecteur le plus important des mathématiques, et le plus contre-intuitif. L’ implication Implication Connecteur « si... alors... », noté ⇒. La proposition P ⇒ Q est fausse dans un seul cas : quand P est vraie et Q est fausse. En particulier, une implication dont la prémisse est fausse est toujours vraie. $P \Rightarrow Q$ se lit « si $P$ alors $Q$ ». Comme le neurone se lit de trois façons, l’implication aussi, et il faut connaître les trois :

si P alors Q | P suffit pour Q | Q est nécessaire pour P

Sa table de vérité réserve une surprise : $P \Rightarrow Q$ n’est fausse que dans un seul cas, celui où $P$ est vraie mais $Q$ fausse.

$P$	$Q$	$P \Rightarrow Q$
V	V	V
V	F	F
F	V	V
F	F	V

Les deux dernières lignes choquent : quand $P$ est fausse, $P \Rightarrow Q$ est vraie quoi qu’il arrive. On dit qu’une implication à prémisse fausse est vraie par vacuité.

L’implication cache une seconde surprise, plus utile encore : elle se réécrit sans le symbole $\Rightarrow$. Compare ci-dessous $P \Rightarrow Q$ et $\lnot P \lor Q$. Active « Tout afficher » : les deux colonnes sont identiques.

Cette réécriture $P \Rightarrow Q \equiv \lnot P \lor Q$ est un outil qu’on utilisera sans cesse pour manipuler les implications dans les démonstrations.

L’équivalence, les tautologies et les contradictions

Quand deux propositions ont la même valeur de vérité dans tous les cas, on dit qu’elles sont en équivalence logique Équivalence logique Relation entre deux propositions qui ont la même valeur de vérité dans tous les cas possibles. Le connecteur associé, noté ⇔, se lit « si et seulement si » et équivaut à une double implication. . Le connecteur $P \Leftrightarrow Q$ se lit « $P$ si et seulement si $Q$ ». Il vaut $V$ exactement quand $P$ et $Q$ ont la même valeur.

$P$	$Q$	$P \Leftrightarrow Q$
V	V	V
V	F	F
F	V	F
F	F	V

Deux familles de propositions méritent un nom :

• Une tautologie Tautologie Proposition qui est vraie quelles que soient les valeurs de vérité de ses composantes. Exemple : P ∨ ¬P (principe du tiers exclu). Son opposée est la contradiction, toujours fausse. est vraie quelles que soient les valeurs de ses variables. L’exemple roi est le tiers exclu : $P \lor \lnot P$. Soit $P$ est vraie, soit $\lnot P$ l’est, jamais les deux, jamais aucune.
• Une contradiction est toujours fausse. L’exemple roi est $P \land \lnot P$ : une proposition ne peut pas être vraie et fausse à la fois (principe de non-contradiction).

Les lois de De Morgan

Comment nie-t-on un « et » ? Comment nie-t-on un « ou » ? La réponse, ce sont les deux lois de De Morgan, parmi les plus utilisées de toutes les mathématiques :

¬(P ∧ Q) ≡ ¬P ∨ ¬Q ¬(P ∨ Q) ≡ ¬P ∧ ¬Q

En clair : nier « les deux » revient à dire « au moins l’un des deux est faux » ; nier « au moins l’un » revient à dire « les deux sont faux ». Vérifie la première loi toi-même ci-dessous, colonne contre colonne.

Voici le tableau récapitulatif des cinq connecteurs. Garde-le sous les yeux : c’est ta carte du chapitre.

Symbole	Nom	Lecture	Vrai quand…
$\lnot$	négation	non P	$P$ est faux
$\land$	conjonction	P et Q	$P$ et $Q$ sont vrais tous les deux
$\lor$	disjonction	P ou Q	au moins un des deux est vrai
$\Rightarrow$	implication	si P alors Q	sauf si $P$ vrai et $Q$ faux
$\Leftrightarrow$	équivalence	P si et seulement si Q	$P$ et $Q$ ont la même valeur

Toute formule est un arbre

Une formule logique n’est pas une suite de symboles à plat : c’est une structure emboîtée, un arbre. Les connecteurs sont les nœuds, les variables sont les feuilles. Voici l’arbre de $(P \land Q) \Rightarrow R$ :

Cet arbre dicte l’ordre d’évaluation : on calcule d’abord les feuilles, puis on remonte. Il dicte aussi la priorité des connecteurs, exactement comme la multiplication passe avant l’addition. La convention, du plus prioritaire au moins prioritaire : $\lnot$, puis $\land$, puis $\lor$, puis $\Rightarrow$, puis $\Leftrightarrow$. Ainsi $\lnot P \lor Q$ se lit $(\lnot P) \lor Q$, et non $\lnot (P \lor Q)$. En cas de doute, les parenthèses tranchent.

Une histoire : de Boole aux circuits

L’idée que le raisonnement puisse devenir du calcul est récente à l’échelle des mathématiques.

Année	Événement
1847	George Boole publie une algèbre où le vrai et le faux se calculent comme des nombres. La logique devient mathématique.
1879	Gottlob Frege invente une notation pour les quantificateurs et fonde la logique moderne. On en récolte les fruits au chapitre 2.
1937	Claude Shannon montre dans son mémoire de master que les circuits à interrupteurs réalisent exactement l’algèbre de Boole. Naissance de l’électronique numérique.

En une phrase

La logique propositionnelle est un petit calcul exact : des propositions, vraies ou fausses, se combinent par cinq connecteurs, et la valeur de n’importe quelle formule se lit mécaniquement dans sa table de vérité.

Vers le chapitre 2

On a soigneusement évité « $x > 3$ » en disant que ce n’était pas une proposition. C’est gênant : les mathématiques sont pleines d’énoncés qui dépendent d’une variable. Pour les rendre vrais ou faux, il faut dire « pour tout $x$ » ou « il existe un $x$ ». Ce sont les quantificateurs $\forall$ et $\exists$, le sujet du chapitre 2.

Exercices

Prends une feuille et un crayon. Les corrigés sont juste en dessous, regarde-les seulement après avoir essayé.

Exercice 1 : reconnaître une équivalence

Dresser la table de vérité de $(P \Rightarrow Q) \land (Q \Rightarrow P)$, puis comparer avec $P \Leftrightarrow Q$. Que constate-t-on ?

Exercice 2 : nier une implication

Montrer, par une table de vérité, que $\lnot(P \Rightarrow Q)$ est équivalente à $P \land \lnot Q$. Cette identité est précieuse : elle dit ce qu’il faut exhiber pour réfuter un « si… alors ».

Sources

• Boole, G. (1854). An Investigation of the Laws of Thought. Walton and Maberly. Archive.org
• Frege, G. (1879). Begriffsschrift. Louis Nebert.
• Shannon, C. E. (1938). « A Symbolic Analysis of Relay and Switching Circuits. » Transactions of the AIEE 57(12), 713-723. DOI 10.1109/T-AIEE.1938.5057767

Pour aller plus loin

• Cori, R. & Lascar, D. (2003). Logique mathématique, tome 1. Dunod. Une référence française rigoureuse.
• David, R., Nour, K. & Raffalli, C. (2003). Introduction à la logique : théorie de la démonstration. Dunod.
• Velleman, D. J. (2019). How to Prove It. Cambridge University Press. Excellent pour passer de la logique aux démonstrations.