CHAPITRE 1

LOGIQUE

La logique permet de modéliser et d’étudier le raisonnement mathématique.

1.1 Définitions
Proposition : On appelle proposition un énoncé ou une expression pouvant être vrai ou faux. On associe
à toute proposition une valeur de vérité V (vrai) ou F( faux).

Exemple 1 :

• Alger est une ville côtière. (V)

• Le triangle rectangle possède un angle droit. (V)

• 3 + 5 = 0.(F )

• x, y deux réels, x est plus grand que y. (Ceci n’est pas une proposition, il s’agit d’un énoncé)

 Axiome : On appelle axiome toute proposition considérée comme évidente, admise vraie sans démons-
tration.

Exemple 2 : Axiome d’Euclide : il affirme que par un point donné passe une unique parallèle à une droite
donnée.

 Théorème : On appelle théorème toute proposition que l’on démontre vraie.

 Corollaire : Un corollaire est une conséquence directe d’un théorème.

 Lemme : On appelle lemme toute proposition vraie préparatoire à l’établissement d’un théorème de plus
grande importance.

1.2 Connecteurs logiques

Les connecteurs logiques permettent de définir d’autres propositions à partir d’une ou plusieurs propositions
initiales. Soient P et Q deux propositions, on définit par :

0) Négation : La négation d’une proposition P est la proposition, notée P̄ , qui est vraie lorsque P est fausse
et fausse sinon.

1
 CH. 1 LOGIQUE

Exemple 3 :
P : 3 est un nombre pair (F ), P̄ : 3 n’est pas un nombre pair (V).

0)

0)

Conjonction : La conjonction des deux propositions P et Q est la proposition (P et Q), notée (P ∧ Q),
qui est vraie si P et Q sont toutes les deux vraies en même temps. Elle est fausse sinon. On résume ceci dans
la table de vérité suivante :

P Q P∧Q
V V V
V F F
F V F
F F F
Exemple 4 : 2 divise 9 et 136 est un multiple de 17. (F)
Disjonction : La disjonction des deux propositions P et Q est la proposition (P ou Q), notée (P ∨ Q), qui
est vraie si au moins l’une des deux propositions est vraie. Elle est fausse sinon. On résume ceci dans la table
P Q P∨Q
V V V
de vérité suivante : V F V Exemple 5. 2 divise 9 ou 136 est un multiple de 17.(V ) - Implication : La
F V V
F F F
proposition P implique Q, notée (P ⇒ Q), est la proposition qui est fausse lorsque P est vraie et Q est fausse.
P Q P ⇒Q
V V V
Elle est vraie sinon. En d’autres termes, il s’agit de la proposition (P̄ ∨ Q). V F F
F V V
F F V
√
Exemple 6. 2 × 2 = 6 ⇒ 3 = 1. (V) (SiP est fausse alors P ⇒ Q est toujours vraie) Remarque. À partir
de l’implication (P ⇒ Q), on définit : - L’implication (Q ⇒ P ), appelée réciproque de l’implication (P ⇒ Q). -
L’implication (Q̄ ⇒ P ), appelée contraposée de l’implication (P ⇒ Q). - La négation (P ⇒ Q) est la proposition
(P ∧ Q̄). Exemple 7. Soit l’implication suivante : n2 est pair ) ⇒ (n est pair). 1. Sa téciproque est : (n est
pair ) ⇒ n2 est pair ). 2. Sa contraposée est : (n est impair ) ⇒ n2 est impair). 3. Sa négation est : n2 est
pair ) et (n est impair). - Équivalence : La proposition P équivalent à Q, notée (P ⇔ Q), est la proposition
qui est vraie lorsque P et Q sont toutes les deux vraies ou toutes les deux fausses. Elle est fausse sinon. En
P Q P ⇔Q
V V V
d’autres termes, il s’agit de la proposition (P ⇒ Q) ∧ (Q ⇒ P ). V F F Exemple 8. Soit x ∈ R. On
F V F
F F V
a l’équivalence suivante : 2x − 2 = 0 ⇔ x = 1 (l’implication et sa réciproque sont toutes les deux vraies).
Remarque. Dans la pratique mathématique, nous ne nous intéresserons qu’aux propositions vraies. C’est √ à
dire, on écrira P ⇔ Q ou P ⇒ Q uniquement lorsque celles ci seront vraies. Exemple 9. 1. 0 ≤ x ≤ 64 ⇒ x ≤
8.(V ) 2. Soient x, y ∈ R. On a l’équivalence suivante : x2 +y 2 = 0 ⇔ x = y = 0.(V ) Proposition. Soient P, Q deux
propositions. Nous avons les équivalences (vraies) suivantes : 1. P ⇔ P̄ , 2.(P ∧ Q) ⇔ P̄ ∨ Q̄, 3.(P ∨ Q) ⇔
P̄ ∧ Q̄, 4. (P ⇒ Q) ⇔ (Q̄ ⇒ P̄ )

3) Quantificateurs Soit P (x) une proposition dépendant d’un élément x d’un ensemble E. On écrit -
∀x ∈ E, P (x) : lorsque la proposition P est vraie pour tous les éléments x ∈ E. ∀, qui se lit quelque soit
ou pour tout, est appelé quantificateur universel. - ∃x ∈ E, P (x) : lorsqu’il existe au moins un élément x de
l’ensemble E pour lequel la proposition P est vraie. ∃, qui se lit il existe au moins un, est appelé quantificateur
existentiel. - ∃!x ∈ E, P (x) : lorsqu’il existe un unique élément x de l’ensemble E pour lequel la proposition
P est vraie. Il y a conjointement existence et unicité de l’élément x vérifiant la proposition P . Exemple 10. 1.
∀x ∈ 0, +∞ , x2 ≥ 0(V ) 2. ∀x ∈ R, x2 ≥ 4(F̄ ) 3. ∃n ∈ N, n2 − n > n(V )(n = 3, n = 10, n = 100) 4.
∃x ∈ R, x2 = −4(F ) (aucun téel au carté ne donnera un nombre négatif). 5. ∃!n ∈ N, n2 − n > n(F ) Néga-
tion de propositions dépendant
 dequantificateurs

- La négation
  de (∀x ∈

E, P (x)) est (∃x ∈ E, P (x)). Exemple
11. La négation de ∀x ∈ 1, +∞ , x2 ≥ 1 est ∃x ∈ 1, +∞ , x2 < 1 . - La négation de (∃x ∈ E, P (x)) est
(∀x ∈ E, P (x)). Exemple 12. La négation de ∃n ≥ 0, n3 − n est multiple de 3) est ∀n ≥ 0, n3 − n n’est pas
multiple de 3 ). Remarque. - On peut trouver des propositions dépendant de deux quantificateurs. Par exemple :

2
 1.2 Connecteurs logiques

∀x ∈ R, ∃y > 0, x + y > 10 - L’ordre des quantificateurs est très important. Prenons l’exemple des deux propo-
sitions suivantes :

∀x ∈ R, ∃y ∈ R, y > x et ∃x ∈ R, ∀y ∈ R, y > x
La première est vraie et la seconde est fausse. En effet, dans la première on peut toujours trouver un nombre
supérieur à un nombre réel donné car R n’est pas borné. Tandis que pour la seconde, on ne peut pas trouver
un réel inférieur à tous les autres car R n’a pas de borne inférieure. 4) Modes de raisonnement Voici quelques
méthodes de raisonnement : 4.1 Raisonnement direct On veut montrer que la proposition P ⇒ Q est vraie.
Ce raisonnement consiste à supposer que P est vraie et montrer que Q est vraie. Exemple 13. Soient a, b ≥ 0.
a b a b
Montrons que si 1+b = 1+a alors a = b On suppose que 1+b = 1+a alors a(1 + a) = b(1 + b) donc a + a2 = b + b2
2 2
d’où a − b = b − a. Cela conduit à (a − b)(a + b) = −(a − b) c’est à dire (a − b)(1 + a + b) = 0 ainsi a = b ou
a + b = −1. Comme a, b ≥ 0 alors leur somme ne peut être négative. Par conséquent, on conclut que a = b. 3
4.2 Contraposée Le raisonnement par contraposée est basé sur l’équivalence suivante : (P ⇒ Q) ⇔ (Q̄ ⇒ P̄ ).
Donc si l’on souhaite montrer P ⇒ Q, il suffit de montrer Q̄ ⇒ P̄ Exemple 14. Soit n ∈ N. Montrons que si
n2 est pair alors n est pair. Écrivons d’abord la contraposée : Si n n’est pas pair alors n2 n’est pas pair. On
suppose que n n’est pas pair. On veut montrer que n2 n’est pas pair. Comme n n’est pas pair, il est impair et
donc il existe k ∈ N tel que n = 2k + 1. Alors

n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2l + 1 avec l = 2k 2 + 2k ∈ N

Et donc n2 est impair.

Par conséquent, par contraposition, ceci est équivalent a. si n2 est pair alors n est pair. 4.3 Absurde Le raison-
nement par l’absurde pour montrer qu’une proposition P est vraie repose sur le principe suivant : On suppose
que P̄ est vraie et on cherche une contradiction. Ainsi si P̄ est fausse, cela veut dire que P doit etre vraie.
Exemple 15. Montrons la proposition suivante : 0 n’a pas d’inverse dans R. Raisonnons par l’absurde c’est à
dire supposons que 0 admette un inverse dans R. Alors ∃x0 ∈ R : 0 = x10 ⇒ 0.x0 = 1 ⇒ 0 = 1. Ce qui est
absurde, ainsi 0 n’a pas d’inverse dans R 4.4 Contre-exemple Ce mode de démonstration sert à montrer qu’une
proposition de la forme : Pour tout x dans E, P (x) est fausse. Pour cela, il suffit de montrer que sa négation
est vraie, c’est à dire que : Il existe x dans E, P (x) est vraie. Exemple 16. Montrons que la proposition suivante
∀x ∈ R, x2 + 1 = 0 est fausse. Il suffit de montrer que sa négation est vraie, c’est à dire : ∃x ∈ R, x2 + 1 6= 0
est vraie. En effet, pour x = 1 on aura x2 + 1 = 2 6= 0 ce qui est vtai. Ainsi la proposition ∀x ∈ Rx2 + 1 = 0
est fausse. 4.5 Récurrence Le principe de récurrence permet de montrer qu’une proposition P (n), dépendant de
n, est vraie pour tout n ∈ N. La démonstration par récurrence se déroule en trois étapes : L’initialisation : on
montre que P (0) est vraie. L’hérédité : On suppose que P (n) est vraie pour n ≥ 0 donné et on démontre que
l’assertion au rang suivant P (n + 1) est vraie. La conclusion : On rappelle que le principe de récurrence P (n)
est vraie pour tout n ∈ N. Remarque. Si on doit montrer qu’une proposition est vraie pour tout n ≥ n0 alors
on commence l’initialisation au rang n0 . Exemple 17. Montrons que : ∀n ∈ N, 2n > n. Pour n ≥ 0, notons P (n)
lassertion suivante : 2n > n. On va montrer par récurtence que P (n) est vtaie pour tout n ≥ 0. Initialisation :
Pour n = 0 on a 20 = 1 > 0 donc P (0) est vraie.
Initialisation : Pour n = 0 on a 20 = 1 > 0 donc P (0) est vraie. Hérédité : Fixons n ≥ 1. Supposons que P (n)
est vraie et montrons que P (n + 1) est vraie.

2n+1 = 2 · 2n
= 2n + 2n
> n + 2n car 2n > n
> n + 1 car 2n ≥ 1

Donc P (n + 1) est vraie. Conclusion : par le principe de técurtence P (n) est vraie pour tout n ≥ 0, c’est à dire
2n > n ∀n ≥ 0.