Notions en logique

I. Logique

1) Proposition

définition
Une proposition (Assertion) est une phrase soit vraie, soit fausse, pas les deux en même temps et se note souvent P, Q, R …

Exemples

• « Il pleut. »
• « Je suis plus grand que toi. »
• « 2 + 2 = 4 »
• « 2 × 3 = 7 »

remarque
Soit P une proposition

• Si P est vraie, on dit alors que la valeur de vérité de P est « Vrai » et se note « V »
• Si P est fausse, on dit alors que la valeur de vérité de P est « faux » et se note « F ».

Table de vérité

2) Opérations sur les propositions

Si P est une assertion et Q est une autre assertion, nous allons définir de nouvelles assertions construites à partir de P et de Q.

a) Négation

définition

La négation de la proposition P est la proposition « non P » ou $\overline{P}$ ou $\neg P$ est vraie si P est fausse, et fausse si P est vraie.

P	V	F
non P	F	V

Table de vérité de $\overline{P}$

Symbole	Négation
=	≠
≤	>
≥	<
∈	∉

b) conjonction, disjonction, implication et équivalence

• La conjonction notée $P \text{ et } Q$ ou $P \land Q$ de deux assertions P et Q est une assertion qui est vraie si et seulement si P et Q sont toutes les deux vraies.
• La disjonction notée $P \text{ ou } Q$ ou $P \lor Q$ de deux assertions P et Q est une assertion qui est vraie si P ou Q (ou les deux) est vraie.
• L’implication notée $P \implies Q$ est l’assertion $P$ implique $Q$.
  L’implication est fausse si et seulement si P est vraie et Q est fausse.

remarque

Si P est fausse (c-à-d $\bar{P}$ est vraie), alors l’assertion $P \implies Q$ est toujours vraie.

• L’équivalence est définie par :
  $P \iff Q$ est l’assertion $(P \implies Q)$ et $(Q \implies P)$.

Exemples

• $0 \le x \le 25 \Longrightarrow \sqrt{x} \le 5$ est vraie.
• $x \in ]-\infty, -4[ \implies x^2+3x-4 > 0$ est vraie.
• $\sin(\theta)=0 \implies \theta = 0$ est fausse.
• $2+2=5 \implies \sqrt{2} = 2$ est vraie ! Eh oui, si $P$ est fausse alors l’assertion $P \implies Q$ est toujours vraie.
• Pour $x,x' \in \mathbb{R}$, l’équivalence $x \cdot x' = 0 \iff (x = 0 \text{ ou } x' = 0)$ est vraie.
• Voici une équivalence toujours fausse : $P \iff \text{non}(P)$.

3) Proposition: Lois de Morgan

1. $\text{non}(P \text{ et } Q) \iff (\text{non } P) \text{ ou } (\text{non } Q)$
2. $\text{non}(P \text{ ou } Q) \iff (\text{non } P) \text{ et } (\text{non } Q)$

Proposition

Soient $P, Q, R$ trois assertions. Nous avons les équivalences (vraies) suivantes :

1. $P \iff \text{ non}(\text{non}(P))$
2. $(P \text{ et } Q) \iff (Q \text{ et } P)$
3. $(P \text{ ou } Q) \iff (Q \text{ ou } P)$
4. $(P \text{ et } (Q \text{ ou } R)) \iff (P \text{ et } Q) \text{ ou } (P \text{ et } R)$
5. $(P \text{ ou } (Q \text{ et } R)) \iff (P \text{ ou } Q) \text{ et } (P \text{ ou } R)$
6. $P \implies Q \iff \text{non}(Q) \implies \text{non}(P)$

4) Fonction propositionnelle

définition

Une assertion P qui dépend d’un paramètre ou plusieurs s’appelle fonction propositionnelle.

remarque

Si P dépend d’un paramètre x, on a l’assertion $P(x)$ qui est vraie ou fausse selon la valeur de $x$.

Exemples

• $P(x): x \in \mathbb{R}$, $x^2 \ge 1$ est une fonction propositionnelle.
• $Q(x,y): x,y \in \mathbb{R}$, $x^2 + y^2 = 4$ est une fonction propositionnelle.

$P(2)$ et $Q(2,2)$ sont vraies, tandis que $P(0)$ et $Q(1,2)$ sont fausses.

5) Les quantificateurs

a) Le quantificateur $\forall$ : pour tout

L’assertion : $\forall x \in E \quad P(x)$ est vraie lorsque les assertions $P(x)$ sont vraies pour tous les éléments $x$ de l’ensemble $E$.

Exemples

• $\forall x \in [1,+\infty[ \quad (x^2 \ge 1)$ est vraie.
• $\forall x \in \mathbb{R} \quad (x^2 \ge 1)$ est fausse (voir si $x = \frac{1}{2}$).
• $\forall n \in \mathbb{N} \quad n(n+1) \text{ est divisible par } 2$ est vraie.

b) Le quantificateur $\exists$ : il existe

L’assertion : $\exists x \in E \quad P(x)$ est vraie lorsque l’on peut trouver au moins un $x$ de $E$ pour lequel $P(x)$ est vraie.

Exemples

• $\exists x \in \mathbb{R} \quad (x(x-1) < 0)$ est vraie (par exemple $x = \frac{1}{2}$ vérifie bien la propriété).
• $\exists n \in \mathbb{N} \quad n^2 - n > n$ est vraie.
• $\exists x \in \mathbb{R} \quad (x^2 = -1)$ est fausse (aucun réel au carré ne donnera un nombre négatif).

c) La négation des quantificateurs

• La négation de $\forall x \in E \quad P(x)$ est $\exists x \in E \quad \overline{P(x)}$.
• La négation de $\exists x \in E \quad P(x)$ est $\forall x \in E \quad \overline{P(x)}$.

Exemples

• La négation de $\forall x \in [1,+\infty[ \quad (x^2 \ge 1)$ est $\exists x \in [1,+\infty[ \quad (x^2 < 1)$.
• La négation de $\exists z \in \mathbb{R} \quad (z^2 + z + 1 = 0)$ est $\forall z \in \mathbb{R} \quad (z^2 + z + 1 \neq 0)$.
• La négation de $\forall x \in \mathbb{R} \quad (x + 1 \in \mathbb{Z})$ est $\exists x \in \mathbb{R} \quad (x + 1 \notin \mathbb{Z})$.

remarque

• L’ordre des quantificateurs est très important. Par exemple, $\forall x \in \mathbb{N}, \exists y \in \mathbb{N}, (x < y)$ est vrai, tandis que $\exists y \in \mathbb{N}, \forall x \in \mathbb{N}, (x < y)$ est faux.

II. Raisonnements

1) Raisonnement direct

On veut montrer que l’assertion $P \implies Q$ est vraie.
On suppose que $P$ est vraie et on montre qu’alors $Q$ est vraie.

Exemple

Montrer que : $n \in \mathbb{N}$ est pair $\implies n^2$ est pair.

Solution

Supposons que $n$ est pair et montrons que $n^2$ est pair.

On a que $n$ est pair, donc $\exists p \in \mathbb{N}$ tel que : $n = 2p$.

Donc $n^2 = (2p)^2 = 4p^2 = 2 \times 2p^2 = 2k$ avec $k = 2p^2 \in \mathbb{N}$.

Et par suite, $n^2$ est pair.

D’où : $n \in \mathbb{N}$ est pair $\implies n^2$ est pair.

2) Raisonnement par disjonction des cas

Si l’on souhaite vérifier une assertion $P(x)$ pour tous les $x$ dans un ensemble $E$, on montre l’assertion pour les $x$ dans une partie $A$ de $E$, puis pour les $x$ n’appartenant pas à $A$.

C’est la méthode de disjonction ou du cas par cas.

Exemple

Montrer que pour tout $x \in \mathbb{R}$, $|x-1| \le x^2 - x + 1$.

Preuve

Soit $x \in \mathbb{R}$. Nous distinguons deux cas.

• Premier cas : $x \ge 1$.

Alors $|x-1| = x-1$.

Calculons alors $x^2 - x + 1 - |x-1|$.

Ainsi, $x^2 - x + 1 - |x-1| \ge 0$ et donc $x^2 - x + 1 \ge |x-1|$.

• Deuxième cas : $x < 1$.

Alors $|x-1| = -(x-1)$.
Nous obtenons :

Et donc, $x^2 - x + 1 \ge |x-1|$.

• Conclusion :

Dans tous les cas, $|x-1| \le x^2 - x + 1$.

3) Contraposée

Le raisonnement par contraposition est basé sur l’équivalence suivante :

L’assertion $P \implies Q$ est équivalente à $\text{non}(Q) \implies \text{non}(P)$.

Donc, si l’on souhaite montrer l’assertion $P \implies Q$, on montre en fait que si $\text{non}(Q)$ est vraie, alors $\text{non}(P)$ est vraie.

Exemple

Soit $n \in \mathbb{N}$. Montrer que si $n^2$ est pair alors $n$ est pair.

Solution

Nous supposons que $n$ n’est pas pair. Nous voulons montrer qu’alors $n^2$ n’est pas pair.
Comme $n$ n’est pas pair, il est impair et donc il existe $k \in \mathbb{N}$ tel que $n = 2k + 1$.
Alors,

Et donc $n^2$ est impair.

Conclusion : Nous avons montré que si $n$ est impair alors $n^2$ est impair.

Par contraposition, ceci est équivalent à :

si $n^2$ est pair alors $n$ est pair.

4) Absurde

Le raisonnement par l’absurde

pour montrer $P \implies Q$ repose sur le principe suivant :
on suppose à la fois que $P$ est vraie et que $Q$ est fausse et on cherche une contradiction.
Ainsi, si $P$ est vraie, alors $Q$ doit être vraie et donc $P \implies Q$ est vraie.

Exemple

Soient $a, b \ge 0$. Montrer que si $\frac{a}{1+b} = \frac{b}{1+a}$, alors $a = b$.

Solution

Nous raisonnons par l’absurde en supposant que $\frac{a}{1+b} = \frac{b}{1+a}$ et $a \neq b$.

Comme $\frac{a}{1+b} = \frac{b}{1+a}$,

alors $a(1+a) = b(1+b)$.

Donc $a + a^2 = b + b^2$ d’où $a^2 - b^2 = b - a$.

Cela conduit à $(a - b)(a + b) = -(a - b)$.

Comme $a \neq b$, alors $a - b \neq 0$ et donc en divisant par $a - b$, on obtient $a + b = -1$.

La somme des deux nombres positifs $a$ et $b$ ne peut être négative.

Nous obtenons une contradiction.

Conclusion : Si $\frac{a}{1+b} = \frac{b}{1+a}$, alors $a = b$.

5) Raisonnement par équivalence

Le raisonnement par équivalence repose sur le principe suivant : pour montrer que $P$ est vrai, on montre que $P \iff Q$ est vrai et $Q$ est vrai, donc on déduit que $P$ est vrai.

Exemple

Montrer que : $\forall(x, y) \in \mathbb{R}^2 \quad 2\sqrt{x^2 + xy + y^2} \ge |x - y|$

Solution

Soit $x, y \in \mathbb{R}$, on a :

On sait que $(x + y)^2 \ge 0$ $\hspace{1cm}(vrai).$

Donc, $\forall(x, y) \in \mathbb{R}^2 \quad 2\sqrt{x^2 + xy + y^2} \ge |x - y|$.

6) Récurrence

Soit $n_0 \in \mathbb{N}~~$ fixé.

Le principe de récurrence permet de montrer qu’une fonction propositionnelle $P(n)$, dépendant de $n$, est vraie pour tout $n \ge n_0$.

La démonstration par récurrence se déroule en trois étapes :

• Initialisation : on prouve que $P(n_0)$ est vraie.
• Hérédité : on suppose $n \ge n_0$ donné avec $P(n)$ vraie, et on démontre alors que l’assertion $P(n+1)$ au rang suivant est vraie.
• Conclusion : on rappelle que par le principe de récurrence, $P(n)$ est vraie pour tout $n \ge n_0$.

Exemple

Montrer que pour tout $n \in \mathbb{N}$, $2^n > n$.

Solution

Pour $n \ge 0$, notons $P(n)$ l’assertion suivante : $2^n > n$.

Nous allons démontrer par récurrence que $P(n)$ est vraie pour tout $n \ge 0$.

• Initialisation :
  Pour $n = 0$, nous avons $2^0 = 1 > 0$. Donc $P(0)$ est vraie.

• Hérédité :
  Fixons $n \ge 0$. Supposons que $P(n)$ soit vraie. Nous allons montrer que $P(n+1)$ est vraie.

  $$2^{n+1} = 2^n \cdot 2^1 = 2 \cdot 2^n = 2^n + 2^n > n + 2^n$$
  $$~\quad \text{ car par } P(n), \text{ nous savons } 2^n > n,$$
  $$> n + 1 \quad \text{car } 2^n \ge 1.$$

  Donc $P(n+1)$ est vraie.

• Conclusion :
  Par le principe de récurrence, $P(n)$ est vraie pour tout $n \ge 0$, c’est-à-dire $2^n > n$ pour tout $n \ge 0$.

III. Exercices

Voir la série des exercices sur le lien :

Exercices logique