The Maths Tailor

1.1. Définition et négation

Définition —Proposition

On appelle proposition un énoncé mathématique qui peut être vrai ou faux.

Exemple

Deux propositions simples.

« $1 + 1 = 2$ » est une proposition vraie.
« $7$ est un entier pair» est une proposition fausse.

Définition —Négation

A une proposition

P

, on peut associer sa négation notée non

P

qui est vraie si

P

est fausse et fausse si

P

est vraie.

1.2. Conjonction et disjonction

Définition —Conjonction

A deux propositions

P

et

Q

, on peut associer la conjonction de

P

et

Q

notée

P

et

Q

qui est

vraie si les deux propositions $P$ et $Q$ sont vraies;
fausse si l'une au moins des deux propositions $P$ ou $Q$ est fausse.

Exemple

Soit

ABCD

un rectangle. La proposition
«l'angle

\widehat{ABC}

est droit et les diagonales

[AC]

et

[BD]

se coupent en leur milieu»
est vraie.
Soit

ABC

un triangle. La proposition
«

AB > AC + BC

et

\widehat{ABC} + \widehat{CAB} + \widehat{BCA} = \pi

»
est fausse.

Définition —Disjonction

A deux propositions

P

et

Q

, on peut associer la disjonction

P

ou

Q

qui est

vraie si l'une au moins des deux propositions $P$ ou $Q$ est vraie;
fausse si les deux propositions $P$ et $Q$ sont fausses.

Remarque

Le «ou» considéré ici est un «ou» non exclusif. La proposition

P

ou

Q

est vraie si l'une au moins des deux propositions

P

ou

Q

est vraie et non si exactement une des propositions est vraie.

Exemple

Soit

ABC

un triangle. La proposition
«

AB > AC + BC

ou

\widehat{ABC} + \widehat{CAB} + \widehat{BCA} = \pi

»
est vraie.

1.3. Implication et équivalence

Définition —Implication

A deux propositions

P

et

Q

, on peut associer la proposition

P \implies Q

qui est

vraie si $P$ est fausse ou si $P$ et $Q$ sont vraies;
fausse si $P$ est vraie et $Q$ fausse.

Remarque

Si

P

et

P \implies Q

sont vraies, alors nécessairement

Q

est vraie.

Remarque

L'implication

Q \implies P

s'appelle la réciproque de l'implication

P \implies Q

. Si une implication est vraie, sa réciproque n'est pas forcément vraie.

Exemple

Soient

a

et

b

deux réels. Alors

a=b \implies a^2 = b^2

est vraie mais

a^2 = b^2 \implies a=b

est fausse en général.

Définition —Équivalence

A deux propositions

P

et

Q

, on peut associer la proposition

P \iff Q

qui est

vraie si $P$ et $Q$ sont vraies ou si $P$ et $Q$ sont fausses;
fausse sinon.

Exemple

Soient

a

et

b

deux réels. Alors

a=b \iff e^a=e^b

.

1.4. Formule propositionnelle

Définition —Formule propositionnelle

On appelle formule propositionnelle une combinaison de propositions logiques et de connecteurs logiques.

Définition —Tautologie

Une formule propositionnelle est appelée une tautologie si elle est vraie quelques soient les valeurs de vérité des propositions logiques qui la composent.

Exemple

Si

P

est une proposition logique,

P

ou (non

P

) est une tautologie.

Encadré —Notation 1.1

Si

F

et

G

sont des formules propositionnelles, on notera

F \equiv G

si la proposition

F \iff G

est une tautologie.

Proposition —Reformulations

Soient

P

et

Q

des propositions logiques.

$(P \implies Q) \equiv ((\text{non } P) \text{ ou } Q)$ .
$(P \iff Q) \equiv ((P \implies Q) \text{ et } (Q \implies P))$ .
$(P \text{ ou } Q) \equiv ((\text{non } P) \implies Q)$ .

Démonstration

Par la Notation 1.1, montrer

F \equiv G

revient à montrer que

F \iff G

est une tautologie, c'est-à-dire vraie pour toutes valeurs de vérité des propositions qui la composent (Définition 1.8). On procède donc par tables de vérité pour chacune des trois identités.

Première identité :

(P \implies Q) \equiv ((\text{non } P) \text{ ou } Q)

.

On dresse la table de vérité des deux formules en parcourant les 4 cas possibles :

\begin{array}{|c|c|c|c|c|} P & Q & P \implies Q & \text{non } P & (\text{non } P) \text{ ou } Q \\ \text{V} & \text{V} & \text{V} & \text{F} & \text{V} \\ \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{F} & \text{F} & \text{V} & \text{V} & \text{V} \\ \end{array}

Les colonnes

P \implies Q

et

(\text{non } P) \text{ ou } Q

sont identiques (d'après la Définition 1.5 pour l'implication et la Définition 1.2 et 1.4 pour les colonnes de droite). Donc

(P \implies Q) \iff ((\text{non } P) \text{ ou } Q)

est vraie dans tous les cas : c'est une tautologie.

Deuxième identité :

(P \iff Q) \equiv ((P \implies Q) \text{ et } (Q \implies P))

.

On dresse la table de vérité :

\begin{array}{|c|c|c|c|c|c|} P & Q & P \iff Q & P \implies Q & Q \implies P & (P \implies Q) \text{ et } (Q \implies P) \\ \text{V} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{V} & \text{F} & \text{F} & \text{F} & \text{V} & \text{F} \\ \text{F} & \text{V} & \text{F} & \text{V} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \end{array}

Les colonnes

P \iff Q

et

(P \implies Q) \text{ et } (Q \implies P)

sont identiques (d'après la Définition 1.6 pour l'équivalence, la Définition 1.5 pour les deux implications, et la Définition 1.3 pour la conjonction). Donc la formule est une tautologie.

Troisième identité :

(P \text{ ou } Q) \equiv ((\text{non } P) \implies Q)

.

On dresse la table de vérité :

\begin{array}{|c|c|c|c|c|} P & Q & P \text{ ou } Q & \text{non } P & (\text{non } P) \implies Q \\ \text{V} & \text{V} & \text{V} & \text{F} & \text{V} \\ \text{V} & \text{F} & \text{V} & \text{F} & \text{V} \\ \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{F} & \text{F} & \text{F} & \text{V} & \text{F} \\ \end{array}

Les colonnes

P \text{ ou } Q

et

(\text{non } P) \implies Q

sont identiques (d'après la Définition 1.4 pour la disjonction, la Définition 1.2 pour la négation, et la Définition 1.5 pour l'implication). Donc la formule est une tautologie.

Les trois identités étant vérifiées par tables de vérité exhaustives, la proposition est démontrée.

Application

Soient

P

et

Q

des propositions logiques. Montrer que

(P \text{ et } (P \implies Q)) \implies Q

est une tautologie.

Correction

On veut montrer que

(P \text{ et } (P \implies Q)) \implies Q

est une tautologie, c'est-à-dire vraie pour toutes valeurs de vérité de

P

et

Q

(d'après la Définition 1.8).

On dresse la table de vérité :

\begin{array}{|c|c|c|c|c|} P & Q & P \implies Q & P \text{ et } (P \implies Q) & (P \text{ et } (P \implies Q)) \implies Q \\ \text{V} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{V} & \text{F} & \text{F} & \text{F} & \text{V} \\ \text{F} & \text{V} & \text{V} & \text{F} & \text{V} \\ \text{F} & \text{F} & \text{V} & \text{F} & \text{V} \\ \end{array}

Les valeurs de chaque colonne sont calculées d'après les Définitions 1.5 (implication), 1.3 (conjonction) et 1.5 à nouveau (implication extérieure). La dernière colonne est vraie dans tous les cas :

(P \text{ et } (P \implies Q)) \implies Q

est donc une tautologie.

□

1.5. Conditions nécessaires et/ou suffisantes

Remarque —Conditions nécessaires et conditions suffisantes

Soient

P

et

Q

deux propositions.

On dit que $Q$ est une condition nécessaire pour avoir $P$ si, dès que $P$ est vraie alors nécessairement forcément $Q$ est vraie. Autrement dit, $P \implies Q$ est vraie.
On dit que $Q$ est une condition suffisante pour avoir $P$ s'il suffit que $Q$ soit vraie pour que $P$ soit vraie. Autrement dit, $Q \implies P$ est vraie.
On dit que $Q$ est une condition nécessaire et suffisante pour avoir $P$ quand $P$ est vraie si et seulement si $Q$ est vraie. Autrement dit, $P \iff Q$ est vraie.

Application

Soit

x \in \mathbb{R}

. La proposition «

x \ge 1

» est-elle une condition nécessaire de la proposition «

x^2+x+2 \ge 3

» ? Même question avec suffisante.

Correction

Soient

P

la proposition «

x \ge 1

» et

Q

la proposition «

x^2 + x + 2 \ge 3

», c'est-à-dire «

x^2 + x - 1 \ge 0

».

$P$ est-elle une condition nécessaire de $Q$ ? Cela revient à se demander si

Q \implies P

est vraie (d'après la définition des conditions nécessaires). Or

x = -2

vérifie

(-2)^2 + (-2) + 2 = 4 - 2 + 2 = 4 \ge 3

(donc

Q

est vraie) mais

-2 < 1

(donc

P

est fausse). Ainsi

Q \implies P

est fausse dans ce cas.

P

n'est pas une condition nécessaire de

Q

.

$P$ est-elle une condition suffisante de $Q$ ? Cela revient à se demander si

P \implies Q

est vraie. Supposons

x \ge 1

. Alors

x^2 \ge x \ge 1

et

x \ge 1

, donc

x^2 + x + 2 \ge 1 + 1 + 2 = 4 \ge 3

. Ainsi

Q

est vraie dès que

P

est vraie :

P \implies Q

est vraie.

P

est une condition suffisante de

Q

.

□

1.6. Règles de calcul propositionnel

Proposition —Distributivité

Soient

P

,

Q

et

R

trois propositions logiques. Alors on a :

$((P \text{ ou } Q) \text{ et } R) \equiv ((P \text{ et } R) \text{ ou } (Q \text{ et } R))$
$((P \text{ et } Q) \text{ ou } R) \equiv ((P \text{ ou } R) \text{ et } (Q \text{ ou } R))$

Démonstration

Par la Notation 1.1, montrer

F \equiv G

revient à montrer que

F \iff G

est une tautologie (Définition 1.8). On procède par tables de vérité à trois variables

P

,

Q

,

R

: il y a

2^3 = 8

cas possibles.

Première identité :

((P \text{ ou } Q) \text{ et } R) \equiv ((P \text{ et } R) \text{ ou } (Q \text{ et } R))

.

\begin{array}{|c|c|c|c|c|c|c|c|} P & Q & R & P \text{ ou } Q & (P \text{ ou } Q) \text{ et } R & P \text{ et } R & Q \text{ et } R & (P \text{ et } R) \text{ ou } (Q \text{ et } R) \\ \text{V} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{V} & \text{V} & \text{F} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{V} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} & \text{F} & \text{V} \\ \text{V} & \text{F} & \text{F} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{V} & \text{V} & \text{V} & \text{V} & \text{F} & \text{V} & \text{V} \\ \text{F} & \text{V} & \text{F} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{F} & \text{F} & \text{F} & \text{F} & \text{F} & \text{F} \\ \end{array}

Les colonnes 5 et 8 sont identiques dans tous les cas (chaque cellule est calculée d'après les Définitions 1.3 et 1.4 de la conjonction et de la disjonction). La formule est donc une tautologie.

Deuxième identité :

((P \text{ et } Q) \text{ ou } R) \equiv ((P \text{ ou } R) \text{ et } (Q \text{ ou } R))

.

\begin{array}{|c|c|c|c|c|c|c|c|} P & Q & R & P \text{ et } Q & (P \text{ et } Q) \text{ ou } R & P \text{ ou } R & Q \text{ ou } R & (P \text{ ou } R) \text{ et } (Q \text{ ou } R) \\ \text{V} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{V} & \text{V} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{V} & \text{F} & \text{V} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{V} & \text{F} & \text{F} & \text{F} & \text{F} & \text{V} & \text{F} & \text{F} \\ \text{F} & \text{V} & \text{V} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{F} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} & \text{V} & \text{F} \\ \text{F} & \text{F} & \text{V} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \text{F} & \text{F} & \text{F} & \text{F} & \text{F} & \text{F} & \text{F} & \text{F} \\ \end{array}

Les colonnes 5 et 8 sont identiques dans tous les cas. La formule est donc une tautologie.

Les deux identités de distributivité étant vérifiées exhaustivement, la proposition est démontrée.

Remarque

On dit que la conjonction (resp. la disjonction) est distributive sur la disjonction (resp. conjonction).

Exemple

\begin{cases} x^2 = 1 \\ y = -3 \end{cases} \iff \begin{cases} x = 1 \text{ ou } x = -1 \\ y = -3 \end{cases} \iff \left( \begin{cases} x = 1 \\ y = -3 \end{cases} \text{ ou } \begin{cases} x = -1 \\ y = -3 \end{cases} \right)

Proposition —Négation

Soient

P

et

Q

deux propositions logiques. Alors on a :

$\text{non}(P \text{ et } Q) \equiv ((\text{non } P) \text{ ou } (\text{non } Q))$
$\text{non}(P \text{ ou } Q) \equiv ((\text{non } P) \text{ et } (\text{non } Q))$
$\text{non}(P \implies Q) \equiv (P \text{ et } (\text{non } Q))$

Démonstration

Par la Notation 1.1, il s'agit dans chaque cas de montrer que la formule

F \iff G

est une tautologie (Définition 1.8). On traite les deux premières identités par tables de vérité, et la troisième en utilisant la Proposition 1.1.

Première identité (première loi de De Morgan) :

\text{non}(P \text{ et } Q) \equiv ((\text{non } P) \text{ ou } (\text{non } Q))

.

\begin{array}{|c|c|c|c|c|c|c|} P & Q & P \text{ et } Q & \text{non}(P \text{ et } Q) & \text{non } P & \text{non } Q & (\text{non } P) \text{ ou } (\text{non } Q) \\ \text{V} & \text{V} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{V} & \text{F} & \text{F} & \text{V} & \text{F} & \text{V} & \text{V} \\ \text{F} & \text{V} & \text{F} & \text{V} & \text{V} & \text{F} & \text{V} \\ \text{F} & \text{F} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \end{array}

Les colonnes 4 et 7 sont identiques dans les 4 cas (d'après la Définition 1.3 pour la conjonction, la Définition 1.2 pour la négation, et la Définition 1.4 pour la disjonction). La formule est une tautologie.

Deuxième identité (deuxième loi de De Morgan) :

\text{non}(P \text{ ou } Q) \equiv ((\text{non } P) \text{ et } (\text{non } Q))

.

\begin{array}{|c|c|c|c|c|c|c|} P & Q & P \text{ ou } Q & \text{non}(P \text{ ou } Q) & \text{non } P & \text{non } Q & (\text{non } P) \text{ et } (\text{non } Q) \\ \text{V} & \text{V} & \text{V} & \text{F} & \text{F} & \text{F} & \text{F} \\ \text{V} & \text{F} & \text{V} & \text{F} & \text{F} & \text{V} & \text{F} \\ \text{F} & \text{V} & \text{V} & \text{F} & \text{V} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{F} & \text{V} & \text{V} & \text{V} & \text{V} \\ \end{array}

Les colonnes 4 et 7 sont identiques dans les 4 cas. La formule est une tautologie.

Troisième identité :

\text{non}(P \implies Q) \equiv (P \text{ et } (\text{non } Q))

.

D'après la Proposition 1.1 (première reformulation), on a

P \implies Q \equiv (\text{non } P) \text{ ou } Q

. Autrement dit,

(P \implies Q) \iff ((\text{non } P) \text{ ou } Q)

est une tautologie. En particulier, pour toutes valeurs de vérité de

P

et

Q

, les formules

P \implies Q

et

(\text{non } P) \text{ ou } Q

ont la même valeur de vérité, donc leurs négations aussi. Ainsi :

\text{non}(P \implies Q) \equiv \text{non}((\text{non } P) \text{ ou } Q).

Or, d'après la deuxième identité démontrée ci-dessus (appliquée à

\text{non } P

à la place de

P

et

Q

à la place de

Q

) :

\text{non}((\text{non } P) \text{ ou } Q) \equiv (\text{non}(\text{non } P)) \text{ et } (\text{non } Q).

Enfin, d'après la Définition 1.2 de la négation,

\text{non}(\text{non } P)

a la même valeur de vérité que

P

(la double négation redonne la proposition initiale), donc :

\text{non}((\text{non } P)) \text{ et } (\text{non } Q) \equiv P \text{ et } (\text{non } Q).

En enchaînant les trois équivalences, on obtient bien

\text{non}(P \implies Q) \equiv P \text{ et } (\text{non } Q)

.

Exemple

La négation de la proposition

-1 \le x \le 2

est

x < -1

ou

x > 2

.

Exemple

Soient

P

la proposition «Il y a de la fumée» et

Q

la proposition «Il y a du feu». Le célèbre proverbe «Il n'y a pas de fumée sans feu» se traduit par

P \implies Q

. Sa négation est «Il y a de la fumée et il n'y a pas de feu» qui se traduit par

P

et (non

Q

).

1.7. En pratique

Méthode —Montrer qu'une implication est vraie

Pour montrer que

P \implies Q

est vraie, il suffit de montrer que si

P

est vraie, alors

Q

est vraie.
Remarque. La notation logique

P \implies Q

correspond en français à la phrase «si

P

alors

Q

».

Attention

L'implication

P \implies Q

peut être vraie sans que

P

et

Q

ne soient forcément vraies.
Quand on vous demande de montrer que l'implication

P \implies Q

est vraie, il ne s'agit nullement de prouver que

P

ou

Q

sont vraies mais que si

P

est vraie, alors

Q

est vraie.

Méthode —Montrer qu'une équivalence est vraie

Pour montrer que

P \iff Q

est vraie, il suffit de montrer que si

P

est vraie, alors

Q

est vraie et que si

Q

est vraie, alors

P

est vraie.
Remarque. La notation logique

P \iff Q

correspond en français à la phrase «

P

si et seulement si

Q

».

Attention

L'équivalence

P \iff Q

peut être vraie sans que

P

et

Q

ne soient forcément vraies.
Quand on vous demande de montrer que l'équivalence

P \iff Q

est vraie, il ne s'agit nullement de prouver que

P

ou

Q

sont vraies mais que

P

est vraie si et seulement si

Q

est vraie.
En pratique, dans une rédaction, on n'emploiera jamais les symboles

\implies

et

\iff

. Le seul endroit où le symbole

\iff

est toléré, c'est dans les résolutions d'équations ou d'inéquations.
On préférera l'emploi de mots de français : conjonctions de coordination (mais, ou, et, donc, or, ni, car), conjonctions de subordination (parce que, si, puisque, ...) ou adverbes (ainsi, cependant, ...).

Raisonnements

1. Propositions logiques

1.1. Définition et négation

1.2. Conjonction et disjonction

1.3. Implication et équivalence

1.4. Formule propositionnelle

1.5. Conditions nécessaires et/ou suffisantes

1.6. Règles de calcul propositionnel

1.7. En pratique