MPSI · Logique et raisonnements

Connecteurs logiques et tables de vérité

Palier 0Palier 1Palier 1+Palier 2

Les assertions sont les briques du langage mathématique ; il faut maintenant le ciment. À partir d'assertions existantes, on en fabrique de nouvelles : « il ne pleut pas », « il pleut et il fait froid », « s'il pleut alors la route est mouillée ». Les opérations qui assemblent ainsi les assertions s'appellent les connecteurs logiques — et toute démonstration, du lycée aux concours, n'est qu'un enchaînement contrôlé de ces connecteurs.

Les cinq connecteurs

Question

La vérité de « P\mathcal{P} et Q\mathcal{Q} » devrait se déduire mécaniquement de celles de P\mathcal{P} et de Q\mathcal{Q}, sans réfléchir au contenu des énoncés. Comment définir précisément cette mécanique — et pour quels assemblages ?

Définition 1 : Connecteurs logiques

Soient P\mathcal{P} et Q\mathcal{Q} deux assertions.

  1. On appelle négation de P\mathcal{P}, et on note ¬P\neg \mathcal{P} ou P‾\overline{\mathcal{P}} ou NON P\mathcal{P}, la proposition qui est vraie si P\mathcal{P} est fausse, et fausse si P\mathcal{P} est vraie.
  2. On appelle conjonction de P\mathcal{P} et Q\mathcal{Q}, et on note « P\mathcal{P} et Q\mathcal{Q} » ou « P∧Q\mathcal{P} \wedge \mathcal{Q} », la proposition qui est vraie seulement si les propositions P\mathcal{P} et Q\mathcal{Q} sont vraies.
  3. On appelle disjonction de P\mathcal{P} et Q\mathcal{Q}, et on note « P\mathcal{P} ou Q\mathcal{Q} » ou « P∨Q\mathcal{P} \vee \mathcal{Q} », la proposition qui est vraie si au moins l'une des propositions P\mathcal{P} ou Q\mathcal{Q} est vraie.
  4. On appelle équivalence de P\mathcal{P} et Q\mathcal{Q} la proposition, notée P⇔Q\mathcal{P} \Leftrightarrow \mathcal{Q}, qui est vraie seulement si P\mathcal{P} et Q\mathcal{Q} ont la même valeur de vérité.
  5. On appelle implication de Q\mathcal{Q} par P\mathcal{P} la proposition, notée P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}, qui est fausse seulement si P\mathcal{P} est vraie et Q\mathcal{Q} est fausse.

Ces définitions se résument en tables de vérité — la carte d'identité de chaque connecteur :

P\mathcal{P}¬P\neg \mathcal{P}
VF
FV
P\mathcal{P}Q\mathcal{Q}P\mathcal{P} et Q\mathcal{Q}P\mathcal{P} ou Q\mathcal{Q}P⇔Q\mathcal{P} \Leftrightarrow \mathcal{Q}P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}
VVVVVV
VFFVFF
FVFVFV
FFFFVV

Remarque :

Le « ou » mathématique est inclusif : « P\mathcal{P} ou Q\mathcal{Q} » est vraie aussi quand les deux le sont. Rien à voir avec le « ou » du menu du restaurant (fromage ou dessert), qui est exclusif.

Exemple :

  1. « 2∉Q\sqrt{2} \notin \mathbb{Q} et 1+1=31 + 1 = 3 » est une assertion fausse.
  2. « 2∉Q\sqrt{2} \notin \mathbb{Q} ou 1+1=31 + 1 = 3 » est une assertion vraie.
  3. « 22 est pair et 22 est premier » est une assertion vraie — le « ou » l'aurait été aussi. Pourquoi ?

Test 1 : Le « ou » du restaurant

La proposition « 4≥44 \geq 4 ou 4≤44 \leq 4 » est fausse, car les deux membres sont vrais en même temps.

L'implication, connecteur roi

Question

D'après la table, l'implication P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} est vraie dès que P\mathcal{P} est fausse — quel que soit Q\mathcal{Q}. Pourquoi ce choix, qui semble étrange, est-il le bon ?

Remarque :

L'implication ne dit rien de la vérité de ses deux membres : elle interdit seulement une configuration, « P\mathcal{P} vraie et Q\mathcal{Q} fausse ». Ainsi :

  1. « 1+1=3⇒0=51 + 1 = 3 \Rightarrow 0 = 5 » est une assertion vraie : sa prémisse est fausse, la configuration interdite ne se produit pas. Le faux implique n'importe quoi.
  2. Comprendre P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} comme une promesse : « chaque fois que P\mathcal{P} se réalise, Q\mathcal{Q} se réalise aussi ». Une promesse n'est rompue que si P\mathcal{P} a lieu sans Q\mathcal{Q} ; si P\mathcal{P} n'a jamais lieu, la promesse est tenue à vide.
  3. C'est ce choix qui rend vraie l'assertion « ∀ x∈R:x>2⇒x2>4\forall\, x \in \mathbb{R} : x > 2 \Rightarrow x^2 > 4 » : pour x=0x = 0, la prémisse est fausse et l'implication est vraie, comme il se doit — on ne veut pas qu'un xx hors sujet la mette en défaut.

Remarque :

  1. Si P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}, on dit que P\mathcal{P} est une condition suffisante pour que Q\mathcal{Q} soit vraie, et que Q\mathcal{Q} est une condition nécessaire pour que P\mathcal{P} soit vraie.
  2. Si P\mathcal{P} et P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} sont vraies, alors Q\mathcal{Q} est vraie.
  3. Si P⇔Q\mathcal{P} \Leftrightarrow \mathcal{Q}, on dit que P\mathcal{P} est une condition nécessaire et suffisante pour Q\mathcal{Q}. On dit aussi que P\mathcal{P} est vraie si et seulement si Q\mathcal{Q} est vraie.

Vocabulaire :

La proposition Q⇒P\mathcal{Q} \Rightarrow \mathcal{P} est appelée la réciproque de P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}. Une implication peut être vraie et sa réciproque fausse : « x>2⇒x2>4x > 2 \Rightarrow x^2 > 4 » est vraie pour tout réel xx, sa réciproque ne l'est pas (x=−3x = -3).

Rédaction :

Le symbole ⇒\Rightarrow dans une copie — trois règles strictes :

  1. ⇒\Rightarrow et ⇔\Leftrightarrow sont des connecteurs : ils vivent à l'intérieur d'un énoncé que l'on cite ou que l'on veut démontrer (« Montrons que x≥2⇒x2≥4x \geq 2 \Rightarrow x^2 \geq 4 »).
  2. On n'écrit jamais ⇒\Rightarrow comme mot de liaison entre deux étapes d'un raisonnement. Les liaisons s'écrivent en français : donc, ainsi, d'où, or, par suite.
  3. Ne pas confondre : « P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} » est une assertion qui ne dit rien sur la vérité de P\mathcal{P} ; « on a P\mathcal{P}, donc Q\mathcal{Q} » affirme que P\mathcal{P} est vraie et en déduit Q\mathcal{Q}. Écrire l'une pour l'autre est une faute de sens, pas seulement de style.
À bannir dans une rédactionÀ écrire
x≥2⇒x2≥4⇒x2+1≥5x \geq 2 \Rightarrow x^2 \geq 4 \Rightarrow x^2 + 1 \geq 5On a x≥2x \geq 2, donc x2≥4x^2 \geq 4, d'où x2+1≥5x^2 + 1 \geq 5.
On a nn pair ⇒\Rightarrow n2n^2 pairOn a nn pair, donc n2n^2 est pair.

Test 2 : ⇒ n'affirme rien

Écrire « nn est pair ⇒\Rightarrow n2n^2 est pair » affirme que nn est pair.

Rédaction :

Traduire le vocabulaire des énoncés — chaque tournure française cache une implication et un sens :

PhraseÉcriture logique
Si P\mathcal{P} alors Q\mathcal{Q}P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}
P\mathcal{P} seulement si Q\mathcal{Q}P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}
Il suffit que P\mathcal{P} pour que Q\mathcal{Q}P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}
Il faut que Q\mathcal{Q} pour que P\mathcal{P}P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}
P\mathcal{P} si et seulement si Q\mathcal{Q}P⇔Q\mathcal{P} \Leftrightarrow \mathcal{Q}

Le piège est « il faut » : il faut que Q\mathcal{Q} désigne la condition nécessaire, donc la conclusion de l'implication, pas sa prémisse.

Test 3 : Confirmer la conclusion

Si P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} est vraie et si Q\mathcal{Q} est vraie, alors P\mathcal{P} est vraie.

Test 4 : Prémisse fausse

L'assertion « ∀ n∈N:n≥1 et n≤0⇒n=7\forall\, n \in \mathbb{N} : n \geq 1 \text{ et } n \leq 0 \Rightarrow n = 7 » est vraie.

Règles de calcul sur les connecteurs

Question

Peut-on calculer avec les connecteurs comme on calcule avec ++ et ×\times — c'est-à-dire disposer de règles pour transformer un énoncé composé en un énoncé équivalent plus maniable ?

Proposition 1

Soient P\mathcal{P} et Q\mathcal{Q} deux propositions. Alors :

  1. P\mathcal{P} et ¬P\neg \mathcal{P} est fausse ;
  2. P\mathcal{P} ou ¬P\neg \mathcal{P} est vraie ;
  3. ((P⇒Q) et (Q⇒P))⇔(P⇔Q)\big((\mathcal{P} \Rightarrow \mathcal{Q}) \text{ et } (\mathcal{Q} \Rightarrow \mathcal{P})\big) \Leftrightarrow (\mathcal{P} \Leftrightarrow \mathcal{Q}) ;
  4. ¬(P et Q)⇔(¬P ou ¬Q)\neg(\mathcal{P} \text{ et } \mathcal{Q}) \Leftrightarrow (\neg \mathcal{P} \text{ ou } \neg \mathcal{Q}) ;
  5. ¬(P ou Q)⇔(¬P et ¬Q)\neg(\mathcal{P} \text{ ou } \mathcal{Q}) \Leftrightarrow (\neg \mathcal{P} \text{ et } \neg \mathcal{Q}) ;
  6. ¬(P⇒Q)⇔(P et ¬Q)\neg(\mathcal{P} \Rightarrow \mathcal{Q}) \Leftrightarrow (\mathcal{P} \text{ et } \neg \mathcal{Q}) ;
  7. (P⇒Q)⇔(¬P ou Q)(\mathcal{P} \Rightarrow \mathcal{Q}) \Leftrightarrow (\neg \mathcal{P} \text{ ou } \mathcal{Q}).

Démonstration :

Chaque équivalence se vérifie par table de vérité : deux propositions sont équivalentes si et seulement si leurs colonnes coïncident sur toutes les lignes.

Points 1 et 2. Si P\mathcal{P} est vraie, ¬P\neg\mathcal{P} est fausse, et inversement : dans les deux cas, la conjonction « P\mathcal{P} et ¬P\neg\mathcal{P} » a un membre faux (elle est fausse) et la disjonction « P\mathcal{P} ou ¬P\neg\mathcal{P} » a un membre vrai (elle est vraie).

Points 4 et 5 (lois de De Morgan). Dressons la table du point 4 :

P\mathcal{P}Q\mathcal{Q}P\mathcal{P} et Q\mathcal{Q}¬(P\neg(\mathcal{P} et Q)\mathcal{Q})¬P\neg\mathcal{P} ou ¬Q\neg\mathcal{Q}
VVVFF
VFFVV
FVFVV
FFFVV

Les deux dernières colonnes coïncident. Le point 5 se vérifie par la même méthode.

Points 6 et 7. Dressons la table commune :

P\mathcal{P}Q\mathcal{Q}P⇒Q\mathcal{P} \Rightarrow \mathcal{Q}P\mathcal{P} et ¬Q\neg\mathcal{Q}¬P\neg\mathcal{P} ou Q\mathcal{Q}
VVVFV
VFFVF
FVVFV
FFVFV

La quatrième colonne est la négation ligne à ligne de la troisième (point 6), et la cinquième lui est identique (point 7).

Point 3. La proposition P⇔Q\mathcal{P} \Leftrightarrow \mathcal{Q} est vraie exactement sur les lignes où P\mathcal{P} et Q\mathcal{Q} ont même valeur (lignes 1 et 4). Sur ces lignes, P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} et Q⇒P\mathcal{Q} \Rightarrow \mathcal{P} sont toutes deux vraies, donc leur conjonction aussi. Sur les lignes 2 et 3, l'une des deux implications est fausse (celle dont la prémisse est le membre vrai), donc la conjonction est fausse. Les colonnes coïncident.

Remarque :

Deux lectures à retenir de cette proposition :

  1. Points 4, 5, 6 : ce sont les règles de négation. Nier un « et » donne un « ou » (et réciproquement), nier une implication donne « la prémisse et le contraire de la conclusion » — surtout pas une autre implication. Elles préparent la négation des énoncés quantifiés, objet de la prochaine leçon.
  2. Point 3 : pour démontrer une équivalence, on démontre les deux implications séparément. C'est la structure de la quasi-totalité des démonstrations d'équivalence que tu rédigeras cette année.

Exemple :

La négation de « ff est paire et ff est croissante » est « ff n'est pas paire ou ff n'est pas croissante » — c'est le point 4. Que devient le connecteur si l'on nie plutôt « ff est paire ou ff est croissante » ?

Test 5 : De Morgan

La négation de « P\mathcal{P} et Q\mathcal{Q} » est « ¬P\neg\mathcal{P} et ¬Q\neg\mathcal{Q} ».

Test 6 : Nier une implication

La négation de « P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} » est « P⇒¬Q\mathcal{P} \Rightarrow \neg\mathcal{Q} ».

Rédaction :

Nier un énoncé composé, mécaniquement :

  1. Repérer le connecteur principal (le dernier appliqué).
  2. Appliquer la règle correspondante : « et » devient « ou », « ou » devient « et », « P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} » devient « P\mathcal{P} et ¬Q\neg\mathcal{Q} ».
  3. Recommencer sur chaque sous-énoncé, jusqu'à ce que les négations ne portent plus que sur des énoncés simples.
  4. Terminer en traduisant les négations simples : ¬(x≤a)\neg(x \leq a) devient x>ax > a, ¬(x∈A)\neg(x \in A) devient x∉Ax \notin A, etc.

Exercice 1 : Calculs de négations

Écrire, sous forme d'un énoncé sans symbole ¬\neg, la négation de chacune des propositions suivantes portant sur un réel xx :

  1. « x≥0x \geq 0 et x≤1x \leq 1 » ;
  2. « x<−1x < -1 ou x>1x > 1 » ;
  3. « x≥2⇒x2≥4x \geq 2 \Rightarrow x^2 \geq 4 ».
Solution :(cliquer pour afficher)

1. Par la loi de De Morgan (point 4) : ¬(x≥0 et x≤1)⇔(¬(x≥0) ou ¬(x≤1))⇔(x<0 ou x>1)\neg(x \geq 0 \text{ et } x \leq 1) \Leftrightarrow (\neg(x \geq 0) \text{ ou } \neg(x \leq 1)) \Leftrightarrow (x < 0 \text{ ou } x > 1).

Géométriquement : le contraire d'appartenir à [0,1][0, 1] est d'être en dehors, d'un côté ou de l'autre.

2. Par la loi de De Morgan (point 5) : ¬(x<−1 ou x>1)⇔(x≥−1 et x≤1)\neg(x < -1 \text{ ou } x > 1) \Leftrightarrow (x \geq -1 \text{ et } x \leq 1), c'est-à-dire x∈[−1,1]x \in [-1, 1].

3. Par le point 6 : ¬(x≥2⇒x2≥4)⇔(x≥2 et x2<4)\neg(x \geq 2 \Rightarrow x^2 \geq 4) \Leftrightarrow (x \geq 2 \text{ et } x^2 < 4).

Remarque au passage : cette dernière proposition est fausse pour tout réel xx — ce qui confirme que l'implication de départ est vraie pour tout réel xx.

Exercice 2 : Le « ou exclusif »

Pour deux propositions P\mathcal{P} et Q\mathcal{Q}, on définit le « ou exclusif » comme la proposition R\mathcal{R} : « (P ou Q)(\mathcal{P} \text{ ou } \mathcal{Q}) et ¬(P et Q)\neg(\mathcal{P} \text{ et } \mathcal{Q}) ».

  1. Dresser la table de vérité de R\mathcal{R}.
  2. Montrer que R⇔¬(P⇔Q)\mathcal{R} \Leftrightarrow \neg(\mathcal{P} \Leftrightarrow \mathcal{Q}).
Solution :(cliquer pour afficher)

1. Calculons colonne par colonne :

P\mathcal{P}Q\mathcal{Q}P\mathcal{P} ou Q\mathcal{Q}¬(P\neg(\mathcal{P} et Q)\mathcal{Q})R\mathcal{R}
VVVFF
VFVVV
FVVVV
FFFVF

R\mathcal{R} est vraie exactement quand une et une seule des deux propositions est vraie : c'est bien le « fromage ou dessert ».

2. La proposition P⇔Q\mathcal{P} \Leftrightarrow \mathcal{Q} est vraie sur les lignes 1 et 4 (mêmes valeurs de vérité), donc ¬(P⇔Q)\neg(\mathcal{P} \Leftrightarrow \mathcal{Q}) est vraie sur les lignes 2 et 3 — exactement les lignes où R\mathcal{R} est vraie. Les deux colonnes coïncident sur les quatre lignes, d'où l'équivalence.

Exercice 3 : Vrai ou faux, avec la table

Les propositions suivantes sont-elles vraies pour toutes assertions P\mathcal{P}, Q\mathcal{Q}, R\mathcal{R} ?

  1. (P⇒Q) ou (Q⇒P)\big(\mathcal{P} \Rightarrow \mathcal{Q}\big) \text{ ou } \big(\mathcal{Q} \Rightarrow \mathcal{P}\big) ;
  2. ((P⇒Q) et (Q⇒R))⇒(P⇒R)\big((\mathcal{P} \Rightarrow \mathcal{Q}) \text{ et } (\mathcal{Q} \Rightarrow \mathcal{R})\big) \Rightarrow (\mathcal{P} \Rightarrow \mathcal{R}).
Solution :(cliquer pour afficher)

1. Vraie. D'après le point 7, elle équivaut à (¬P ou Q) ou (¬Q ou P)(\neg\mathcal{P} \text{ ou } \mathcal{Q}) \text{ ou } (\neg\mathcal{Q} \text{ ou } \mathcal{P}). Or parmi Q\mathcal{Q} et ¬Q\neg\mathcal{Q}, l'une des deux est vraie (point 2) : la grande disjonction contient toujours un membre vrai, elle est donc vraie. Surprenant en langage courant — mais rappelle-toi qu'une implication à prémisse fausse est vraie.

2. Vraie — c'est la transitivité de l'implication, que tu utilises à chaque enchaînement « donc ». Supposons la prémisse vraie : P⇒Q\mathcal{P} \Rightarrow \mathcal{Q} et Q⇒R\mathcal{Q} \Rightarrow \mathcal{R} sont vraies. Montrons P⇒R\mathcal{P} \Rightarrow \mathcal{R} : si P\mathcal{P} est fausse, c'est acquis ; si P\mathcal{P} est vraie, alors Q\mathcal{Q} est vraie (première implication), puis R\mathcal{R} est vraie (seconde implication). Dans tous les cas P⇒R\mathcal{P} \Rightarrow \mathcal{R} est vraie, donc l'implication globale est vraie.