Propositions logiques (et, ou, non) et quantificateurs

Une proposition est une phrase qui est soit vraie, soit fausse ; avec « non », « et », « ou », on en fabrique de nouvelles dont on calcule la vérité, et avec « pour tout » et « il existe », on parle de toute une famille d'objets à la fois.

Objectifs

Reconnaître une proposition et donner sa valeur de vérité.
Construire et utiliser les tables de vérité de la négation, de la conjonction (et) et de la disjonction (ou).
Appliquer les lois de De Morgan pour nier une phrase avec « et » ou « ou ».
Lire et écrire des propositions avec les quantificateurs \(\forall\) et \(\exists\).
Écrire correctement la négation d'une proposition quantifiée.

1. Propositions et valeur de vérité

« \(7\) est un nombre premier » : proposition vraie.
« \(2 + 3 = 6\) » : proposition fausse.
« Ouagadougou est la capitale du Burkina Faso » : proposition vraie.
« Ferme la fenêtre ! » ou « Quelle heure est-il ? » : ce ne sont pas des propositions (on ne peut pas dire vrai ou faux).
« \(x > 3\) » : ce n'est pas une proposition tant qu'on ne connaît pas \(x\) ; c'est une proposition dépendant de \(x\), notée \(P(x)\). Par exemple \(P(5)\) est vraie et \(P(1)\) est fausse.

Laquelle de ces phrases est une proposition ?

Résous l'équation \(2x = 4\).
Est-ce que \(9\) est pair ?
\(9\) est un nombre pair.

La phrase 3 affirme quelque chose qu'on peut juger : elle est fausse, mais c'est bien une proposition. Un ordre ou une question n'en sont pas.

2. Les connecteurs « non », « et », « ou »

La négation : non \(P\)

La négation de \(P\), notée \(\text{non}\,P\) ou \(\overline{P}\), est vraie quand \(P\) est fausse, et fausse quand \(P\) est vraie.

\(P\)	\(\overline{P}\)
V	F
F	V

Exemple : la négation de « \(x > 3\) » est « \(x \leq 3\) » (et non « \(x < 3\) »).

La conjonction : \(P\) et \(Q\)

« \(P\) et \(Q\) », noté \(P \wedge Q\), est vraie seulement quand les deux sont vraies.

La disjonction : \(P\) ou \(Q\)

« \(P\) ou \(Q\) », noté \(P \vee Q\), est vraie quand au moins une des deux est vraie. En mathématiques, le « ou » est inclusif : il est vrai aussi quand les deux sont vraies.

\(P\)	\(Q\)	\(P \wedge Q\)	\(P \vee Q\)
V	V	V	V
V	F	F	V
F	V	F	V
F	F	F	F

« P et Q » n'est vraie que dans la zone commune aux deux cercles : les deux conditions sont réunies.

« P ou Q » est vraie dans toute la zone colorée : il suffit d'être dans l'un des cercles, et la zone commune compte aussi.

Exemple résolu : valeurs de vérité

Soit \(P\) : « \(12\) est divisible par \(3\) » et \(Q\) : « \(12\) est divisible par \(5\) ». Donne la valeur de vérité de \(\overline{Q}\), \(P \wedge Q\) et \(P \vee Q\).

Voir la solution

\(P\) est vraie (\(12 = 3 \times 4\)) et \(Q\) est fausse (\(12\) n'est pas un multiple de \(5\)). Donc \(\overline{Q}\) est vraie ; \(P \wedge Q\) est fausse (\(Q\) est fausse) ; \(P \vee Q\) est vraie (\(P\) est vraie).

\(P\) : « \(4\) est pair » et \(Q\) : « \(4\) est un carré ». Que vaut \(P \vee Q\) ?

Fausse, car on ne peut pas avoir les deux
Vraie
On ne peut pas savoir

\(P\) et \(Q\) sont vraies (\(4 = 2^2\)). Le « ou » mathématique est inclusif : \(P \vee Q\) est vraie.

3. Nier « et » et « ou » : les lois de De Morgan

Exemple résolu : vérifier une loi par une table de vérité

On écrit les quatre cas possibles pour \(P\) et \(Q\), puis on calcule \(P \wedge Q\) et sa négation.

On calcule \(\overline{P}\), \(\overline{Q}\), puis \(\overline{P} \vee \overline{Q}\).

\(P\)	\(Q\)	\(\overline{P \wedge Q}\)	\(\overline{P}\)	\(\overline{Q}\)	\(\overline{P} \vee \overline{Q}\)
V	V	F	F	F	F
V	F	V	F	V	V
F	V	V	V	F	V
F	F	V	V	V	V

Les colonnes \(\overline{P \wedge Q}\) et \(\overline{P} \vee \overline{Q}\) sont identiques dans les quatre cas : les deux propositions sont équivalentes.

Exemple résolu : nier une condition sur \(x\)

Écris la négation de « \(x > 2\) et \(x < 5\) ».

Voir la solution

On nie chaque morceau et on remplace « et » par « ou » : « \(x \leq 2\) ou \(x \geq 5\) ». Autrement dit, \(x\) n'est pas dans l'intervalle \(]2 ; 5[\).

Quelle est la négation de « Kofi parle anglais ou Kofi parle espagnol » ?

Kofi ne parle pas anglais et Kofi ne parle pas espagnol.
Kofi ne parle pas anglais ou Kofi ne parle pas espagnol.
Kofi parle anglais et espagnol.

D'après De Morgan, \(\overline{P \vee Q} \iff \overline{P} \wedge \overline{Q}\) : Kofi ne parle aucune des deux langues.

4. Les quantificateurs \(\forall\) et \(\exists\)

\(\forall x \in \mathbb{R},\ x^2 \geq 0\) : vraie (un carré est toujours positif ou nul).
\(\exists x \in \mathbb{R},\ x^2 = 2\) : vraie (prendre \(x = \sqrt{2}\)).
\(\forall x \in \mathbb{R},\ x^2 > 0\) : fausse, car pour \(x = 0\), \(x^2 = 0\). Le nombre \(0\) est un contre-exemple.
\(\exists n \in \mathbb{N},\ 2n + 1 = 8\) : fausse, car \(2n + 1 = 8\) donne \(n = \dfrac{7}{2}\), qui n'est pas entier.

Négation d'une proposition quantifiée

Exemple résolu

Écris la négation de : \(\forall x \in \mathbb{R},\ x^2 + 1 > 2x\), puis dis laquelle des deux est vraie.

On remplace \(\forall\) par \(\exists\) et on nie « \(x^2 + 1 > 2x\) » en « \(x^2 + 1 \leq 2x\) » : \[\exists x \in \mathbb{R},\ x^2 + 1 \leq 2x.\]

On remarque que \(x^2 + 1 - 2x = (x - 1)^2\).

Pour \(x = 1\) : \((1-1)^2 = 0\), donc \(x^2 + 1 = 2x\). La négation est vraie (avec \(x = 1\)), donc la proposition de départ est fausse.

Quelle est la négation de « \(\exists x \in \mathbb{R},\ x^2 < 0\) » ?

\(\exists x \in \mathbb{R},\ x^2 \geq 0\)
\(\forall x \in \mathbb{R},\ x^2 < 0\)
\(\forall x \in \mathbb{R},\ x^2 \geq 0\)

On échange \(\exists\) en \(\forall\) et on nie \(x^2 < 0\) en \(x^2 \geq 0\). Cette négation est d'ailleurs vraie.

Pour démontrer que « \(\forall n \in \mathbb{N},\ n^2 + n + 41\) est premier » est fausse, que suffit-il de faire ?

Vérifier que c'est vrai pour \(n = 0, 1, 2\)
Trouver une seule valeur de \(n\) pour laquelle le nombre n'est pas premier
Montrer que c'est faux pour tous les \(n\)

Un contre-exemple suffit. Par exemple, pour \(n = 41\) : \(41^2 + 41 + 41 = 41 \times 43\), qui n'est pas premier.

Erreurs fréquentes

Nier « \(x > 3\) » en « \(x < 3\) » : on oublie le cas \(x = 3\). La bonne négation est « \(x \leq 3\) ».
Nier « \(P\) et \(Q\) » en « \(\overline{P}\) et \(\overline{Q}\) » : il faut changer « et » en « ou ».
Croire que le « ou » mathématique exclut le cas où les deux sont vraies.
Nier un « pour tout » en un autre « pour tout » : la négation de « tous » est « au moins un ne… pas ».
Penser que quelques exemples démontrent un « pour tout ».
Échanger l'ordre de \(\forall\) et \(\exists\) sans réfléchir.

Récapitulatif

flowchart LR
A[Proposition V ou F] --> B[non]
A --> C[et : les deux vraies]
A --> D[ou : au moins une vraie]
A --> E[Pour tout et Il existe]
E --> F[Negation : echanger et nier]

Une proposition est soit vraie, soit fausse.
\(P \wedge Q\) vraie si les deux sont vraies ; \(P \vee Q\) vraie si au moins une est vraie (ou inclusif).
De Morgan : \(\overline{P \wedge Q} \iff \overline{P} \vee \overline{Q}\) et \(\overline{P \vee Q} \iff \overline{P} \wedge \overline{Q}\).
Négation d'une proposition quantifiée : \(\forall\) devient \(\exists\), \(\exists\) devient \(\forall\), et la propriété est niée.

Cartes mémo

Proposition

Énoncé dont on peut dire sans ambiguïté s'il est vrai ou faux.

\(P \wedge Q\) (et)

Vraie uniquement quand \(P\) et \(Q\) sont toutes les deux vraies.

\(P \vee Q\) (ou)

Vraie dès qu'au moins une des deux est vraie (ou inclusif).

Lois de De Morgan

\(\overline{P \wedge Q} \iff \overline{P} \vee \overline{Q}\) et \(\overline{P \vee Q} \iff \overline{P} \wedge \overline{Q}\)

\(\forall\) et \(\exists\)

« Pour tout » (chaque élément) et « il existe » (au moins un élément).

Nier une proposition quantifiée

\(\overline{\forall x,\ P(x)} \iff \exists x,\ \overline{P(x)}\) : on échange les quantificateurs et on nie la propriété.