Logique : propositions, implication et négation

Propositions

Une proposition est un énoncé dont on peut dire s'il est vrai ou faux, même si on n'a pas encore tranché. « $2 + 2 = 4$ » est une proposition vraie ; « $7$ est pair » est une proposition fausse ; « Quelle heure est-il ? » n'en est pas une, c'est une question ; « Ferme la porte ! » non plus, c'est un ordre.

On note souvent $P$, $Q$ les propositions, V ou F leurs valeurs.

Attention au piège. Une proposition fausse reste une proposition. « $7$ est pair » se classe, elle a simplement la valeur F. Ce qui ne se classe pas, ce sont les questions, les ordres, les phrases ouvertes comme « $x$ est pair » tant que $x$ n'est pas fixé.

Et, ou, non

On combine les propositions :

• conjonction $P \land Q$ (« $P$ et $Q$ ») : vraie seulement si les deux le sont
• disjonction $P \lor Q$ (« $P$ ou $Q$ ») : vraie dès qu'au moins l'une l'est (le « ou » inclusif)
• négation $\neg P$ : inverse la valeur de $P$

Nier deux fois revient au départ : $\neg(\neg P) \Leftrightarrow P$.

Nier un « et », c'est un « ou » de négations : loi de De Morgan :

De même, $\neg(P \lor Q) \Leftrightarrow \neg P \land \neg Q$.

Exemple. Nier « $n$ est pair et multiple de $3$ », c'est dire « $n$ est impair ou $n$ n'est pas multiple de $3$ ».

Attention au piège. « Tous les chats ne sont pas gris » n'est pas « aucun chat n'est gris ». Nier « tout $x$ vérifie $P$ », c'est « il existe un $x$ qui ne vérifie pas $P$ », pas « aucun $x$ ne vérifie $P$ ».

Implication et équivalence

$P \Rightarrow Q$ se lit « $P$ implique $Q$ » : chaque fois que $P$ est vraie, $Q$ l'est aussi. Cette implication n'est fausse que si $P$ est vraie et $Q$ fausse. Quand $P$ est fausse, $P \Rightarrow Q$ est vraie, que $Q$ le soit ou non.

Exemple. « $n$ est multiple de $4$ $\Rightarrow$ $n$ est pair » est vraie. La réciproque « $n$ est pair $\Rightarrow$ $n$ est multiple de $4$ » est fausse : $6$ est pair, pas multiple de $4$.

$P \Leftrightarrow Q$ (« $P$ équivaut à $Q$ ») signifie les deux implications à la fois : $P$ et $Q$ ont toujours la même valeur.

Un contrôle utile. Pour montrer $P \Rightarrow Q$, on suppose $P$ vraie et on en déduit $Q$. Un exemple où $P$ est vraie et $Q$ fausse suffit à réfuter l'implication.

Ce que cette leçon prépare. Le raisonnement par récurrence s'appuie sur une implication $P(n) \Rightarrow P(n+1)$. Sans savoir ce que vaut cette flèche, l'initialisation et l'hérédité n'ont pas de statut.