Table des Matières

1 Chapitre 1 Méthodes du raisonnement mathématique 2

1.1 Cours N 1 Éléments de logique mathématique . . . . . . . . . 2
1.1.1 Valeurs de vérité et tableau de vérité . . . . . . . 2
1.1.2 Négation d’une proposition . . . . . . . . . . . . . 3
1.1.3 Les connecteurs propositionnels . . . . . . . . . . 3
1.1.4 Tautologie et contradiction . . . . . . . . . . . . . 5
1.1.5 La réciproque et la contraposée d’une implication 6
1.1.6 Lois de Morgan . . . . . . . . . . . . . . . . . . . . . 6
1.2 Cours N 2 Les quanti…cateurs Logiques . . . . . . . . . . . . . 9
1.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Le quanti…cateur universel 8 : . . . . . . . . . . . . 9
1.2.3 Le quanti…cateur existentiel 9 : . . . . . . . . . . . 10
1.2.4 Négation des quanti…cateurs . . . . . . . . . . . . 11
1.2.5 Deux quanti…cateurs de même nature qui se
suivent: . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.6 Deux quanti…cateurs di¤érents qui se suivent: . 12
1.3 Cours N 3 Méthodes de raisonnement mathématique . . . . . 14
1.3.1 Raisonnement direct . . . . . . . . . . . . . . . . . 14
1.3.2 Raisonnement par contraposition . . . . . . . . . 14
1.3.3 Raisonnement par L’absurde . . . . . . . . . . . . 14
1.3.4 Raisonnement par contre-exemple . . . . . . . . . 15
1.3.5 Raisonnement par récurrence . . . . . . . . . . . . 16

2 Série d’exercices N 1 18

3 Correction de la série d’exercices N 1 22

1
1 Chapitre 1 Méthodes du raisonnement math-
ématique
1.1 Cours N 1 Éléments de logique mathématique

Dé…nition

On appelle p: proposition mathématique simple une phrase qu’on peut

juger "vraie" ou "fausse" sans aucune ambiguïté et de manière intemporelle;
il n y a pas une troisième possibilité.

Exemples

p: "1 2" a: "le chat est un mammifère",

q:" 0 > 3", b: "4 est un nombre impair",
r:" x est un nombre premier".

p est une proposition vraie, q une proposition fausse, r n’est pas une
proposition, nous avons besoin de plus d’informations pour pouvoir juger la
proposition r. Qu’en est-il de a et b?

1.1.1 Valeurs de vérité et tableau de vérité

On pose "vraie" =1 et "faux"=0.
1 et 0 sont les valeurs de vérité.

Le tableau de vérité contient tous les cas possibles pour une, deux ou
trois propositions.
Dans le cas d’une seule proposition le tableau de vérité contient seulement
2 cas:

p
1
0
Le nombre de possibilités dans le tableau de vérité dépend du nombre de
propositions de la manière suivante:

nb de possibilités = (2)nb de propositions

2
 Donc dans le cas de 2 propositions nous avons 4 lignes dans le tableau
et dans le cas de 3 propositions nous avons 8 lignes et ainsi de suite. Nous
verrons cela plus en détails dans la suite.

1.1.2 Négation d’une proposition

On note p le contraire logique de p, par exemple:
a :"le chat n’est pas un mammifère", qui est fausse.
b :"4 n’est pas un nombre impair", qui est vraie.
Le tableau de vérité donne:

p p
1 0
0 1
Remarque: La négation de la négation p est p.

1.1.3 Les connecteurs propositionnels

À partir des propositions simples, on construit des propositions composées,

en utilisant les connecteurs suivants:
^ et, _ ou, ) implique, , équivaut (ou est équivalent à ).

La conjonction "et":

p ^ q : "1 2 et 0 > 3". (commutatif).

Règle 1 p ^ q : est vraie si les deux sont vraies. Notre exemple est donc
faux.

La disjonction "ou" :

p _ q : "1 2 ou 0 > 3". (commutatif).

Règle 2 p _ q : est fausse si les deux sont fausses. Notre exemple est
donc vrai.

L’implication : ")" : p ) q :

"Si 1 2 alors 0 > 3". Là, p est l’hypothèse et q est la conclusion (ou
la conséquence), (non commutatif).

Règle 3 p ) q : est fausse si la première est vraie et la deuxième est

fausse. Notre exemple est donc faux.

3
 L’équivalence "," : p , q :"1 2 veut exactement dire que
0 > 3".

Nous pouvons aussi lire : "1 2 si et seulement si 0 > 3".

ou bien "1 2 est équivalent à 0 > 3". (commutatif).

Règle 4 p , q : est vraie si les deux ont la même valeur de vérité.Notre

exemple est donc faux
Voici sur le tableau de vérité un résumé des valeurs de vérité des phrases
composées:

p q p^q p_q p)q p,q

1 1 1 1 1 1
1 0 0 1 0 0
0 1 0 1 1 0
0 0 0 0 1 1

Remarques importantes : (démonstration à faire en exercice à la mai-

son)

1/ Il est important de savoir que [p ) q] , [p _ q]

2/ Il faut retenir que l’équivalence est une double implication ou bien une
implication dans les deux sens, i.e1 :

[(p , q)] , [(p ) q) ^ (q ) p)]

Exercice

On a les deux propositions p:"Les chiens aboient", q:" La caravane passe".

Traduisez les phrases suivantes:

(a) "Les chiens n’aboient pas".
(b)"Si la caravane passe alors les chiens aboient".
(c)"La caravane ne passe pas ou les chiens aboient".
(d) "Les chiens n’aboient pas et la caravane ne passe pas".

Correction
(a): p (b): q ) p (c) q _ p (d) p ^ q
1
i.e = id est expression en Latin qui signi…e "c’est à dire que" et qui s’utilise encore
couramment en mathématiques.

4
 (a) (b) (c) (d)
p q p q)p q q_p p^q
1 1 0 1 0 1 0
1 0 0 1 1 1 0
0 1 1 0 0 0 0
0 0 1 1 1 1 1

Cas de trois propositions

Exercice
Soit P, Q et R trois propositions, tracer le tableau de vérité de : P ; (P ^
Q) _ R; P ) R; Q () P

P Q R (P ^ Q) (P ^ Q) _ R P P )R Q () P
1 1 1 1 1 0 1 0
1 1 0 1 1 0 1 0
1 0 1 0 1 0 1 1
1 0 0 0 0 0 1 1
0 1 1 0 1 1 1 1
0 1 0 0 0 1 0 1
0 0 1 0 1 1 1 0
0 0 0 0 0 1 0 0

1.1.4 Tautologie et contradiction

La tautologie est une proposition qui est toujours vraie, la contradiction est
une proposition toujours fausse.

Exemple

Tracer le tableau de vérité de (p ^ p) puis de (p _ p), conclure.

p p p^p p_p
1 0 0 1
0 1 0 1
(p _ p) est une tautologie, (p ^ p) est une contradiction.

5
1.1.5 La réciproque et la contraposée d’une implication
La réciproque : On appelle réciproque de p ) q l’implication q ) p:

Exemple

P :"Je suis à Tlemcen", Q:"Je suis en Algérie".

p ) q : Si "je suis à Tlemcen" alors "je suis en Algérie", donc p ) q est
vrai.
Par contre q ) p est la proposition si "je suis en Algérie" alors "je suis à
Tlemcen", qui est fausse.

La contraposée : On appelle contraposée de p ) q l’implication

q ) p:
Dans l’exemple précédent, q ) p est la phrase : si "je ne suis pas en
Algérie" alors "je ne suis pas à Tlemcen" qui est vraie.

Remarque importante :

Il faut retenir que l’implication est équivalente à sa contraposée et non

pas à sa réciproque (preuve en TD), i.e:

(p ) q) , (q ) p)

1.1.6 Lois de Morgan

C’est les lois qui nous donnent la négation des propositions composées par
les connecteurs logiques.

Exercice

Montrer par le tableau de vérité les lois de Morgan suivantes:

1)(p ^ q) , (p _ q)

2) (p _ q) , (p ^ q)

3) (p ) q) , (p ^ q)

4) Pour trouver la négation de l’équivalence on montre d’abord que :

[(p , q)] , [(p ) q) ^ (q ) p)] : Puis on déduit (p , q):

6
 Correction

1)(p ^ q) , (p _ q)

/////// ///////
p q p^q p^q p q p_q (p ^ q) , (p _ q)
1 1 1 0 0 0 0 1
1 0 0 1 0 1 1 1
0 1 0 1 1 0 1 1
0 0 0 1 1 1 1 1

2) (p _ q) , (p ^ q)

/////// ///////
p q p_q p_q p q p^q (p _ q) , (p ^ q)
1 1 1 0 0 0 0 1
1 0 1 0 0 1 0 1
0 1 1 0 1 0 0 1
0 0 0 1 1 1 1 1

3) (p ) q) , (p ^ q)

/////// ///////
p q p)q p)q q p^q (p ) q) , (p ^ q)
1 1 1 0 0 0 1
1 0 0 1 1 1 1
0 1 1 0 0 0 1
0 0 1 0 1 0 1
Nous pouvons aussi se passer du tableau de vérité et procéder comme
suit:

(p ) q) , (p _ q)
(p ) q) , p_q
(p ) q) , p^q
(p ) q) , (p ^ q)

4) [(p , q)] , [(p ) q) ^ (q ) p)]

7
 /////// ///////
p q p,q p)q q)p (p ) q) ^ (q ) p) [(p , q)] , [(p ) q) ^ (q ) p)]
1 1 1 1 1 1 1
1 0 0 0 1 0 1
0 1 0 1 0 0 1
0 0 1 1 1 1 1

Trouver la négation de ", " :

Puisque (p , q) , [(p ) q) ^ (q ) p)] ;

alors : (p , q) , [(p ) q) ^ (q ) p)]
, (p ) q) _ (q ) p)
, (p ^ q) _ (q ^ p)
Finalement on retient que:

(p , q) , [(p ^ q) _ (q ^ p)] :

8
1.2 Cours N 2 Les quanti…cateurs Logiques
1.2.1 Introduction
Rappelons qu’un ensemble est un "espace" qui rassemble des éléments qui
ont tous une propriété commune.

Exemple
X est l’ensemble de tous les nombres pairs compris entre 1 et 11.
a) Nous pouvons le dé…nir par une liste: X = f2; 4; 6; 8; 10g .
b) Ou bien nous pouvons le dé…nir en précisant la propriété commune:
X = fx=x est pair et 1 < x < 11g.

Remarque 2 2 X; mais 12 2
= X:

Exemple introductif
On note P (x) une phrase mathématique qui dépend de x. Par exemple
P (x) : "x > 1":
Si x = 5 la proposition p(x) est vraie, si x = 0 la proposition est fausse.

Pour juger de la valeur de vérité d’une phrase mathématique qui dépend

de x, nous devons avoir plus d’informations sur ce x, quelle est sa valeur?
Ou plutôt quel est son domaine?

1.2.2 Le quanti…cateur universel 8 :

La phrase mathématique (8x 2 E; P (x)) veut dire que la proposition

mathématique P (x) est véri…ée pour TOUS les x dans E un à un, elle est
traduite par :
"Quelque soit l’élément x de E; x véri…e la proposition P (x)".
Ou bien,

"Pour tout élément x appartenant à E; x véri…e la proposition P (x)".

Ou bien,

"Pour chaque élément x dans E, x véri…e la proposition P (x)".

Si on veut montrer qu’une assertion du type (8x 2 E; P (x)) est fausse

alors il su¢ t de trouver un x 2 E tel que P (x) soit fausse.

9
 Ce x bien précis qui nous fait voir que notre proposition est fausse est
appelé un contre-exemple à l’assertion (8x 2 E; P (x)). On dit qu’on
utilise ici un raisonnement par contre-exemple.

Exemple

Montrer que l’assertion suivante (p) est fausse

p : (8x 2 R; x2 > 1):

Eh bien, un contre-exemple à la proposition (p) est x = 12 . C’est un
nombre précis qui contredit notre phrase (p), par conséquent elle est fausse.

Exemples

1) (8n 2 N; n < n + 1) vrai

2) (8n 2 N; n est pair) faux, il su¢ t de prendre n = 3
3)(8x 2 R; x 1) faux, il su¢ t de prendre x = 2
4) (8x 2 R; x2 0) vrai
Traduction de 1): "Pour tout entier naturel n dans N; n est strictement
plus petit que n + 1".

Attention: on ne mélange pas l’expression linguistique avec l’expression

mathématique, on écrit soit tout en langue, soit tout en maths, mais on ne
mélange pas les deux en même temps.

1.2.3 Le quanti…cateur existentiel 9 :

La phrase mathématique (9x 2 E= P (x)) veut dire qu’il existe au moins
un (dans le sens un ou plusieurs mais certainement au moins un)
élément x dans E; qui véri…ent la proposition P (x), elle est traduite par :
"Il existe (au moins) un élément x de E; tel que, x véri…e la proposition
P (x)".

Si nous voulons montrer qu’une assertion du type (9x 2 E= P (x)) est

vraie alors il su¢ t de trouver un x 2 E tel que P (x) soit véri…ée. Ce x
bien précis qui nous fait voir que notre proposition est vraie est un exemple
direct, nous utilisons donc ici un raisonnement direct.

Exemples

10
 1) (9n 2 N= n > n + 1) faux
2) (9n 2 N= n est pair) vrai, il su¢ t de prendre n = 2
3) (9x 2 R= x < 1) vrai, il su¢ t de prendre x = 1
4) (9n 2 N = n < 1) faux
Traduction de 1): "Il existe au moins un entier naturel n dans N tel que,
n est strictement plus grand que n + 1.

Remarque

Nous avons aussi le quanti…cateur ! : "il existe au plus". Mais il n’est

pas très utilisé en mathématiques, on préfère souvent le remplacer par une
expression linguistique.

1.2.4 Négation des quanti…cateurs

1) (8x 2 E; p(x)) , 9x 2 E=p(x):
Exemple

(8n 2 N; n < n + 1) , 9n 2 N= n n + 1:

2) (9x 2 E=p(x)) , 8x 2 E; p(x):

Exemple

(9n 2 N = n 1) , 8n 2 N ; n < 1:
Remarque
Ne pas oublier que : ( ) , (>),( ) , (<) et (=) , (6=):

1.2.5 Deux quanti…cateurs de même nature qui se suivent:

Dans ce cas, nous gardons les mêmes règles de ré‡exion et d’évaluation

logique que la section plus haute.

1)8x 2 R; 8y 2 R; x + y = y + x: vrai
2)8x 2 R; 8y 2 R; xy x + y faux, il su¢ t de prendre x = 1 et y = 0
3)9n 2 N; 9m 2 N = nm 18 vrai, il su¢ t de prendre n = m = 1
4)9n 2 N; 9m 2 N / n+m<0 faux

11
 Traduction de 1) "Quelque soit x dans R ,quelque soit y dans R; x et y
véri…ent x + y = y + x.

Traduction de 3) "Il existe n qui appartient à N, il existe aussi au moins

un m appartenant à N; tel que n:m est inférieur ou égale à 18.

1.2.6 Deux quanti…cateurs di¤érents qui se suivent:

1) Quand, dans une proposition, le "quelque soit" est suivit par "il existe",
cela veut dire que l’élément "qui doit exister" dépend de l’élément qui est
"quelconque".

Exemples

a) 8x 2 R; 9y 2 R; x y
En l’occurrence ici : y dépend de x. Notre phrase a) est vraie.
Nous devons donner le y en fonction de x pour prouver la véracité de
notre assertion.
Dans notre exemple, il su¢ t de prendre y = jxj + 1 par exemple.

Dans le cas où elle est fausse nous devons trouver un contre-exemple:

b) La phrase 8x 2 R; 9y 2 R=y = x1 est fausse, il su¢ t de prendre x = 0.

2) Quand "il existe" vient avant le "quelque soit", les choses changent...

Ici, l’élément qui "doit exister" est le même pour tous les autres éléments
qui sont "quelconques", c’est à dire que là y est …xé, et tous les x doivent
véri…er le reste de la phrase pour ce même y.

Exemples

a)9y 2 R; 8x 2 R; x y

Notre exemple veut dire qu’il y a un y …xé pour lequel tous les réels lui
sont inférieurs.
La phrase a) est donc fausse, il su¢ t de prendre x = jyj + 1.

b) 9n 2 N= 8m 2 N ; m2 n

vrai, il su¢ t de prendre n = 0:

Remarque

12
 Si on a du mal à juger la valeur de vérité d’une phrase, on essaye de voir
sa négation, surtout pour les phrases qui commencent par 9:

Exercice

Traduire les propositions suivantes, juger leur valeur de vérité puis donner
leur négation:

1) 8x 2 R; 9y 2 R= x + y > 0:
2) 9n 2 N= 8m 2 N ; m2 < n
Correction

1) 8x 2 R; 9y 2 R= x + y > 0: vrai, il su¢ t de prendre y = x+1

1)9x 2 R=8y 2 R; x + y 0
2) 9n 2 N= 8m 2 N ; m2 <n faux, on peut prendre m = n2 :
2)8n 2 N; 9m 2 N = m2 n

Traduction de 1) :

"Quelque soit x dans R, il existe un y dans R; tel que x et y véri…ent

x + y > 0.

Traduction de 2):

"Il existe au moins un entier naturel n tel que, pour tout entier naturel

m, on a m2 est strictement plus petit que n:

13
1.3 Cours N 3 Méthodes de raisonnement mathéma-
tique
1.3.1 Raisonnement direct
On veut montrer que l’assertion « P ) Q » est vraie. On suppose que P
est vraie et on montre qu’alors Q est vraie.
Exemple Montrer que si a = b ) a+b 2
= b (facile).

1.3.2 Raisonnement par contraposition

Nous avons montré par le tableau de vérité que (p ) q) , (q ) p).
La proposition (q ) p) est appelée la contraposée de la proposition
(p ) q) :
Puisqu’elles ont le même sens, au lieu de montrer (p ) q) on montre
sa contraposée (q ) p), (pour vu qu’elle soit plus simple à monter quand
même!).

Exemple

On veut montrer que : Si "n2 est impair" alors "n est impair".
p :"n2 est impair", q :"n est impair".
On veut donc montrer (p ) q) ; on va utiliser sa contraposée (q ) p):
q :"n est pair",p :"n2 est pair". q est l’hypothèse, p est la conclusion.

Si "n est pair" alors 9k 2 N=n = 2k:

) n2 = (2k)2 :
) n2 = 4k 2 = 2(2k 2 ):
) 9m (= 2k 2 ) 2 N=n2 = 2m:
) n2 est pair.
On a montré que Si "n est pair", alors "n2 est pair", qui veut exacte-
ment dire que Si "n2 est impair" alors "n est impair".

1.3.3 Raisonnement par L’absurde

Pour montrer p par l’absurde, on suppose que sa négation p est vraie. Après
quelques pas de démonstration on tombe sur une phrase qui contredit l’hypothèse
p, donc l’hypothèse p est fausse, ce qui veut dire que p est vraie:

14
 Le but: on veut montrer p:
!Hypothèse: on suppose p:
!Démonstration! contradiction avec p:
!Conclusion: p est fausse, donc p est vraie.
Exemple
p
Le but: on veut montrer p : " 2 2 = Q": p
Pour montrer p, on va utiliser son contraire p : " 2 2 Q":
!Hypothèse :
p
p : " 2 2 Q":
p
Si 2 2 Q alors
p n
9n 2 Z; 9m 2 Z = 2 = et pgcd(n; m) = 1:
m
!Démonstration:

p n
2= m
) 2m2 = n2 :
) n2 est pair, donc n est pair, (la preuve se trouve dans la section plus haut).
) 9k 2 N=n = 2k:
) n2 = 4k 2 :
) 2m2 = 4k 2 :
) m2 = 2k 2 :
) m2 est pair, donc m est pair.
) pgcd(n; m) = 2:

Donc pgcd(n; m) = 2
C’est une contradiction avec l’hypothèse pgcd(n; m) = 1!
!Conclusion:
p p
" 2 2 Q" est fausse, donc " 2 2 = Q" est vraie.

1.3.4 Raisonnement par contre-exemple

Si on veut montrer qu’une assertion du type (8x 2 E; P (x)) est vraie alors
pour chaque x de E il faut montrer que P (x) est vraie. Par contre pour
montrer que cette assertion est fausse alors il su¢ t de trouver un x 2 E tel
que P (x) soit fausse. Ce x bien précis qui nous fait voir que notre proposition
est fausse est appelé un contre-exemple à l’assertion (8x 2 E; P (x)).

Exemple

15
 Montrer que l’assertion suivante p est fausse p : (8x 2 R; x2 > 0).

Démonstration:

Un contre-exemple pour la proposition (p) est x = 0. C’est un nombre

précis qui contredit notre phrase (P), par conséquent, elle est fausse.

1.3.5 Raisonnement par récurrence

On utilise la récurrence pour montrer des énoncés comme :

8n 2 N; P (n):
On passe par 3 étapes:

1/Véri…cation :
On doit véri…er que p(0) est vraie, (p(1) si on travaille dans N ).

2/Hérédité
On suppose que p(n) est vraie et on utilise p(n) pour démontrer que
p(n + 1) est vraie aussi.

3/Conclusion:
On déduit que 8n 2 N; P (n).

Exemple
monter que 8n 2 N ; (4n 1) est divisible par 3.

1/Véri…cation :
Pour n = 1, on a p(1): (41 1) = 3; 3 est divisible par 3, donc p(1) est
vraie.

2/Hérédité :
On suppose que p(n) est vraie: (4n 1) est divisible par 3.
Donc 9k 2 N=(4n 1) = 3k ....(1).
Pour p(n + 1) :

16
 (4n+1 1) = (4: (4n ) 1):
(1) , (4n ) = 3k + 1:
= (4: (3k + 1) 1):
= 12k + 4 1:
= 12k + 3:
= 3(4k + 1):
9k 0 = (4k + 1) 2 N=(4n+1 1) = 3k 0 :
Donc (4n+1 1) est divisible par 3.
Ce qui fait que p(n + 1) est vraie.

3/Conclusion:
8n 2 N ; (4n 1) est divisible par 3.

17
2 Série d’exercices N 1

Exercice 1
Écrire sous forme de propositions composées les énoncés suivants et
donner leur négation:
1. 7 est un nombre pair et premier.
2. Le soleil ne brille pas et la terre est ronde.
3. Oran est une ville Algérienne ou 6 = 3 + 1.
4. Si Omar joue à la ‡ûte, alors il joue à la guitare.
5. x est un nombre pair veut exactement dire que x divise 2.

Exercice 2
Soit P une proposition. En dressant la table de vérité, montrer que la
proposition P ^ P est une contradiction et que la proposition P _ P est une
tautologie.
Exercice 3
Soient P , Q deux propositions quelconques.
1. Construire la table de vérité de la proposition suivante:
(P _ Q) ^ (P _ Q)

2. Montrer les équivalences suivantes:

a) (P ) Q) () (P _ Q)
b) (P ) Q) () Q ) P ( la contraposée )

Exercice 4
Soient les trois propositions suivantes: p:" Je pars", q:"Tu restes", r : "Il
n’y a personne".
Traduisez les formules logiques suivantes en Français, puis tracez leur
tableau de vérité correspondant:
(a) (p ^ q) ) r: (b) (p _ q) ) r:
Exercice 5
Sans utiliser la table de vérité...

18
 1. Montrer que les deux propositions suivantes sont équivalentes:

a) P ) (Q ^ R) _ (Q _ R)
b) P _ (Q ^ R) _ (Q _ R)

2. Juger de la valeur de vérité de la propositions suivante :

P ) Q ^ (P ^ Q) ^ R) ) (R ^ Q)

Exercice 6

Trois personnes, x, y et z sont convoquées devant un juge pour un crime

commis dans le village, voici leurs déclarations:
x déclare : "z est coupable et y est innocent".
y déclare : "Je suis innocent, mais au moins l’un des deux autres est
coupable".
z déclare : "Si x est coupable, alors y est coupable aussi".
Nous posons p, q et r les propositions suivantes (x est innocent), (y est
innocent), (z est innocent).

1. Exprimer les déclarations des trois accusés en fonction des propositions

simples p, q et r, puis donner leur tableau de vérité.

2. Supposons qu’ils sont tous innocents, qui est ce qui a menti dans sa
déclaration?

3. Supposons qu’ils ont tous dit la vérité dans leurs déclarations, qui est
innocent et qui est coupable?

4. Supposons que les innocents on dit la vérité et que les coupables ont
menti, alors qui est innocent et qui est coupable?

5. Est-il possible que les innocents ont menti et que les coupables ont dit
la vérité?

Exercice 7

Écrire à l’aide des quanti…cateurs logiques les phrases suivantes, juger

leur valeur de vérité, puis écrire leur négation.

Le carré de tout nombre réel est positif.

19
 Pour chaque réel, je peux trouver un entier relatif tel que leur produit
soit strictement plus grand que 1.

Pour tout entier naturel x, il existe un entier naturel y tel que, pour
tout entier naturel z, la relation z < x implique la relation z < x + y.

Exercice 8

1/ L’implication suivante est-elle vraie ou fausse? Donner sa négation et

sa contraposée:
8x 2 R; x < 0 ) x x2

2/ Soient les propositions suivantes:

(a)8x 2 R; 8y 2 R; x + y 0: (b)9x 2 R; 8y 2 R; y 2 > x:

Les propositions (a), (b) sont-elles vraies ou fausses? Donner leurs néga-
tions.
3/ Écrire la négation, la réciproque et la contraposée de la proposition
suivante :

8x 2 R; 9y 2 R= x 0 ) y > 2:

Exercice 9

1. Montrer par l’absurde que

a)
a b
8a; b 0; = )a=b
1+b 1+a
b) Soit n un entier naturel. Montrer que tout nombre de la
forme (4n + 3) n’est pas un carré parfait.
2. Soit f une application de R dans R; telle que f (x) = 3x + 2: Montrer
que x1 6= x2 ) f (x1 ) 6= f (x2 ):
3. Montrer que la proposition suivante est fausse:

8n 2 N ; (6n 1) est un nombre premier.

4. Montrer par récurrence que

a)8n 2 N; (4n + 6n 1) est un multiple de 9.
Pn
b)8n 2 N ; k(k + 1)(k + 2) = 14 n(n + 1)(n + 2)(n + 3):
k=1

20
 P
n
( 1)n (2n+1) 1
c) 8n 2 N ; ( 1)k k = 4
k=1

Exercice 10

1/ Montrer que tout entier impair n s’écrit sous la forme n = 4k + r avec

k 2 N et r 2 f1; 3g :
2/Montrer maintenant par contraposition que pour n 2 N on a :

Si (n2 1) n’est pas divisible par 8 alors n est pair

21
3 Correction de la série d’exercices N 1

Exercice 1

Écrire sous forme de propositions composées les énoncés suivants et

donner leur négation:

1. 7 est un nombre pair et premier.

On pose p:" 7 est un nombre pair", q:"7 est un nombre premier", on
trouve (1): p ^ q:
Donc

(1) : (p ^ q) , p _ q:

"7 n’est pas un nombre pair ou 7 n’est pas un nombre premier".

Mais comme le contraire de pair est impair et vice versa, on peut dire:
(1): "7 est un nombre impair ou 7 n’est pas un nombre premier".

2. Le soleil ne brille pas et la terre est ronde.

On pose p:" Le soleil brille ", q:"la terre est ronde", on trouve (2): p^q:
Donc

(2) : (p ^ q) , p _ q:

"Le soleil brille ou la terre n’est pas ronde".

3. Oran est une ville Algérienne ou 6 = 3 + 1.

On pose p:" Oran est une ville Algérienne ", q:"6 = 3 + 1", on trouve
(3): p _ q:
Donc

(3) : (p _ q) , p ^ q:

"Oran n’est pas une ville Algérienne et 6 6= 3 + 1".

22
 4. Si Omar joue à la ‡ûte, alors il joue à la guitare.
On pose p:" Omar joue à la ‡ûte ", q:"il joue à la guitare", on trouve
(4): p ) q:

(4) : (p ) q) , p ^ q;

"Omar joue à la ‡ûte mais il ne joue pas à la guitare".

5. x est un nombre pair veut exactement dire que x divise 2.
On pose p:" x est un nombre pair ", q:"x divise 2", on trouve (5):
p () q:

(5) :(p () q) , [(p ^ q) _ (q ^ p)] ;

[(x est un nombre pair et x ne divise pas 2) ou bien ( x divise 2 et x

n’est pas un nombre pair)].

Exercice 2

Soit P une proposition. En dressant la table de vérité, montrer que la

proposition P ^ P est une contradiction et que la proposition P _ P est une
tautologie.

p p p^p p_p
1 0 0 1
0 1 0 1

Exercice 3

Soient P , Q deux propositions quelconques.

1. Construire la table de vérité de la proposition suivante:

(P _ Q) ^ (P _ Q)

/////// ///////
p q p_q p_q p q p_q (p _ q) ^ (p _ q)
1 1 1 0 0 0 0 0
1 0 1 0 0 1 1 0
0 1 1 0 1 0 1 0
0 0 0 1 1 1 1 1

23
 2. Montrer les équivalences suivantes:
a) (P ) Q) () (P _ Q)

/////// ///////
p q p)q p_q p p_q (p ) q) , (p _ q)
1 1 1 0 0 1 1
1 0 0 0 0 0 1
0 1 1 0 1 1 1
0 0 1 1 1 1 1

b) (p ) q) () (q ) p) ( la contraposée )

/////// ///////
p q p)q p q q ) p (p ) q) , (q ) p)
1 1 1 0 0 1 1
1 0 0 0 1 0 1
0 1 1 1 0 1 1
0 0 1 1 1 1 1

Exercice 4

Soient les trois propositions suivantes: p:" Je pars", q:"Tu restes", r : "Il
n’y a personne".
Traduisez les formules logiques suivantes en Français, puis tracez leur
tableau de vérité correspondant:
(a) (p ^ q) ) r:
(a) Si je pars et que tu ne restes pas, alors il n’y a personne !

p q r q p^q (p ^ q) ) r
1 1 1 0 0 1
1 1 0 0 0 1
1 0 1 1 1 1
1 0 0 1 1 0
0 1 1 0 0 1
0 1 0 0 0 1
0 0 1 1 0 1
0 0 0 1 0 1
(b) (p _ q) ) r:

24
(b) Si je ne pars pas ou que tu ne restes pas, alors il y a quelqu’un !

p q r p q p_q r (p _ q) ) r
1 1 1 0 0 0 0 1
1 1 0 0 0 0 1 1
1 0 1 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 1 1 0 1 0 0
0 1 0 1 0 1 1 1
0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1
Exercice 5

1. Sans utiliser la table de vérité...

2. Montrer que les deux propositions suivantes sont équivalentes:

a) P ) (Q ^ R) _ (Q _ R)
b) P _ (Q ^ R) _ (Q _ R)

Nous remarquons que les deux phrases a) et b) ont un terme commun

qui est _(Q _ R) . Il su¢ t donc de montrer l’équivalence entre les deux
premiers termes : P ) (Q ^ R) et P _ (Q ^ R) :
Nous avons vu dans le cours que [A ) B] , A _ B donc P ) (Q ^ R) ,
P _ (Q ^ R) . CQFD.

3. Juger de la valeur de vérité de la propositions suivante :

P ) Q ^ (P ^ Q) ^ R ) (R ^ Q)

Cette proposition est une implication. Le seul cas où elle est fausse,
c’est quand la première est vraie et la seconde est fausse. Est-ce que
ce cas est possible?
Posons (A): P ) Q ^ (P ^ Q) ^ R ; quand est-ce que (A) est vraie?
Eh bien, (A) est une conjonction, elle est vraie si les trois propositions
P ) Q ; (P ^ Q); R sont toutes vraies en même temps.
Or, on remarque que P ) Q est en fait équivalente à P _ Q

25
 On a donc

(A) , P _ Q ^ (P ^ Q) ^ R)
, P ^ Q ^ (P ^ Q) ^ R

Nous avons donc une contradiction P ^ Q ^ (P ^ Q), elle est toujours

fausse, donc quelque soit la valeur de vérité de R, la conjonction totale
(A) est fausse. Au …nale, notre implication est toujours vraie.

Exercice 6
Trois personnes, x, y et z sont convoquées devant un juge pour un crime
commis dans le village, voici leurs déclarations:
x déclare : "z est coupable et y est innocent".
y déclare : "Je suis innocent, mais l’un des deux autres est coupable".
z déclare : "Si x est coupable, alors y est coupable aussi".
Nous posons p, q et r les propositions suivantes (x est innocent), (y est
innocent), (z est innocent).

1. Exprimer les déclarations des trois accusés en fonction des propositions

simples p, q et r, puis donner leur tableau de vérité.

x : r ^ q; y : q ^ (p _ r); z:p)q
x y z
p q r p q r r^q p_r q ^ (p _ r) p ) q
1 1 1 0 0 0 0 0 0 1
1 1 0 0 0 1 1 1 1 1
1 0 1 0 1 0 0 0 0 1
1 0 0 0 1 1 0 1 0 1
0 1 1 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1 1 0
0 0 1 1 1 0 0 1 0 1
0 0 0 1 1 1 0 1 0 1

2. Supposons qu’ils sont tous innocents, qui est ce qui a menti dans sa
déclaration?
Le cas où ils sont tous innocents correspond à la première ligne du
tableau, en examinant la valeur de vérité des déclarations on se rend
compte que x et y ont menti.

26
 3. Supposons qu’ils ont tous dit la vérité dans leurs déclarations, qui est
innocent et qui est coupable?
Le cas où ils ont tous dit la vérité correspond au cas de toutes les
déclarations vraies, ce qui est représenté par la deuxième ligne sur le
tableau, et là nous pouvons voir que x et y sont innocents mais z est
coupable.

4. Supposons que les innocents on dit la vérité et que les coupables ont
menti, alors qui est innocent et qui est coupable?
Ce cas correspond à une concordance entre les valeurs de vérité des
propositions simples et de leurs déclarations, ce qui est représenté par
l’avant dérnière ligne du tableau, ce qui donne que x et y sont coupables
et z est innocent.

5. Est-il possible que les innocents ont menti et que les coupables ont dit
la vérité?
Ce cas correspond à une discordance entre (toutes) les propositions
simples et leurs déclarations, ce qui n’est représenté dans aucun cas
dans le tableau, donc, non, il n’est pas possible que les innocents aient
menti et que les coupables aient dit la vérité.

Exercice 7

Écrire à l’aide des quanti…cateurs logiques les phrases suivantes, juger

leur valeur de vérité, puis écrire leur négation.

Le carré de tout nombre réel est positif.

8x 2 R; x2 0:

C’est vrai, négation :

9x 2 R=x2 < 0:

Pour chaque réel, je peux trouver un entier naturel tel que leur produit
soit strictement plus grand que 1.

8x 2 R; 9n 2 N=x:n > 1:

C’est faux, il su¢ t de prendre x = 0; négation :

27
 9x 2 R=8n 2 N; x:n 1:

Pour tout entier naturel x, il existe un entier naturel y tel que, pour
tout entier naturel z, la relation z < x implique la relation z < x + y.

8x 2 N; 9y 2 N=8z 2 N z < x ) z < x + y:

C’est vrai, il su¢ t de prendre y = x.

Négation :

9x 2 N=8y 2 N; 9z 2 N= (z < x) ^ (z x + y) :

Exercice 8
1/ L’implication suivante est-elle vraie ou fausse? Donner sa négation et
sa contraposée:
8x 2 R; x < 0 ) x x2
L’implication est vraie. Négation :

9x 2 R= (x < 0) ^ x > x2 :

Contraposée :

8x 2 R; x > x2 ) (x > 0)
2/ Soient les propositions suivantes:
(a)8x 2 R; 8y 2 R; x + y 0: (b)9x 2 R; 8y 2 R; y 2 > x:

Les propositions (a), (b) sont-elles vraies ou fausses? Donner leur néga-
tion.
(a) est fausse, il su¢ t de prendre x et y tous les deux positifs, par exemple
x = 1 et y = 2:

(a) : 9x 2 R; 9y 2 R; x+y >0

(b) est vraie, il su¢ t de prendre x = 1 par exemple.

(b) : 8x 2 R; 9y 2 R; y2 x:
3/ Écrire la négation, la réciproque puis la contraposée de la proposition
suivante :

28
 (p) : 8x 2 R; 9y 2 R= x 0 ) y > 2:
Négation :

(p) : 9x 2 R; 8y 2 R; (x 0) ^ y 2
Réciproque:

(R) : 8x 2 R; 9y 2 R= y > 2 ) x 0
Contraposée

(C) : 8x 2 R; 9y 2 R= y 2) x>0

Exercice 9

1. Montrer par l’absurde que

a)
a b
8a; b 0; = )a=b
1+b 1+a
L’absurde consiste à supposer le contraire de la proposition à démon-
trer et tomber sur une contradiction, supposons donc le contraire de notre
implication : rappelons que (p ) q) , p ^ q
a b
Soient a et b 0 tels que 1+b = 1+a ^ a 6= b
a b
Si 1+b = 1+a alors a + a = b + b donc a b + a2 b2 = 0 ce qui fait que:
2 2

(a b)(1 + a + b) = 0
donc soit a = b soit a + b = 1

Mais comme a 6= b (par l’hypothèse de l’absurde), la seule possibilité c’est

que a + b = 1;
ce qui est impossible puisque les deux nombres a et b sont positifs.

b) Soit n un entier naturel. Montrer que tout nombre de la

forme (4n + 3) n’est pas un carré parfait. ( n un entier naturel).

Supposons qu’il existe au moins un n 2 Z= (4n + 3) soit un carré parfait

i.e, 9a 2 N= (4n + 3) = a2

29
 (4n + 3) = a2
a2 3
)n=
4
a2 3
n=
4 4
Si a est pair, il est clair que n n’est pas naturel, si a est impair, on aura:
2
9k 2 N=a = 2k + 1 donc n = k +2k+1 4
3
4
;
k 2 k 1
Donc n = 4 + 2 2 , il est clair que n n’est pas naturel dans ce cas non
plus.
Dans les deux cas nous avons une contradiction ...

Remarque:

On aurai pu procéder sans utiliser l’absurde, il su¢ t de voir que pour

n’importe quel entier n, le reste de la division de n par 4, appelons le r, r
2 f0; 1; 2; 3g donc le reste de la division de n2 par 4 2 f0; 1g. On écrit :

n2 0 ou 1 [4]

Et comme

(4n + 3) 3 [4]
Alors (4n + 3) ne peut pas être un carré parfait.

2. Soit f une application de R dans R; telle que f (x) = 3x + 2: Montrer

que x1 6= x2 ) f (x1 ) 6= f (x2 ):
On procède par contraposée, si (p): x1 6= x2 et (q) f (x1 ) 6= f (x2 ) alors
on veut monter que p ) q:
Par la contraposé il su¢ t de montrer que q ) p
f (x1 ) = f (x2 ) ) 3x1 + 2 = 3x2 + 2 ) x1 = x2 CQFD.
3. Montrer que la proposition suivante est fausse:

8n 2 N ; (6n 1) est un nombre premier.

On procède par contre-exemple, on remarque que pour n = 6; (6n 1) =

35 qui n’est pas un nombre premier. Ce qui contredit notre proposition, d’où
sa fausseté.
4. Montrer par récurrence que

30
 a)8n 2 N; (4n + 6n 1) est un multiple de 9.
1/Véri…cation :
Pour n = 0, on a p(0): (40 + 6(0) 1) = 0; 0 est divisible par 9, donc p(0)
est vraie.
2/Hérédité
On suppose que p(n) est vraie: (4n + 6n 1) est divisible par 9.
Donc 9k 2 N=(4n + 6n 1) = 9k .....(1)
Pour p(n + 1) :

(4n+1 + 6(n + 1) 1) = (4: (4n ) + 6n + 6 1)

= (4: (9k 6n + 1) + 6n + 6 1)
= (4:9k 3:6n + 9)
= 9(4k 2n + 1)
9k 0 = (4k 2n + 1) 2 N=(4n+1 + 6n 1) = 9k 0 :
Donc (4n+1 + 6n 1) est divisible par 9.
Ce qui fait que p(n + 1) est vraie.
3/Conclusion:
8n 2 N; (4n + 6n 1) est divisible par 9.
P
n
b)8n 2 N ; k(k + 1)(k + 2) = 41 n(n + 1)(n + 2)(n + 3):
k=1
1/Véri…cation :
P
1
Pour n = 1, on a k(k+1)(k+2) = 6, et 14 n(n+1)(n+2)(n+3) = 6;donc
k=1
p(1) est vraie.
2/Hérédité
P
n
On suppose que p(n) est vraie: k(k+1)(k+2) = 41 n(n+1)(n+2)(n+3):
k=1
P
n+1
Pour p(n + 1) : k(k + 1)(k + 2) = 41 (n + 1)(n + 2)(n + 3)(n + 4)??:
k=1

P
n+1 P
n
k(k + 1)(k + 2) = k(k + 1)(k + 2) + (n + 1)(n + 2)(n + 3)
k=1 k=1
1
= 4
n(n + 1)(n + 2)(n + 3) + (n + 1)(n + 2)(n + 3)
= (n + 1)(n + 2)(n + 3) 14 n + 1
= 41 (n + 1)(n + 2)(n + 3)(n + 4)
Ce qui fait que p(n + 1) est vraie.
3/Conclusion:
Pn
8n 2 N ; k(k + 1)(k + 2) = 14 n(n + 1)(n + 2)(n + 3):
k=1

31
 P
n
( 1)n (2n+1) 1
c) 8n 2 N ; ( 1)k k = 4
k=1
1/Véri…cation :
P
1
( 1)1 (2(1)+1) 1
Pour n = 1, on a p(1): ( 1)k k = 1; et 4
= 1, donc
k=1
p(1) est vraie.
2/Hérédité
P
n
( 1)n (2n+1) 1
On suppose que p(n) est vraie: ( 1)k k = 4
.
k=1
P
n+1
( 1)n+1 (2n+3) 1
Pour p(n + 1) : ( 1)k k = 4
???
k=1

P
n+1 P
n
( 1)k k = ( 1)k k + ( 1)(n+1) (n + 1)
k=1 k=1
n
= ( 1) (2n+1)
4
1
+ ( 1)(n+1) (n + 1)
( 1)n
= 4 [(2n + 1) 4(n + 1)] 14
= 9(4k + 2n + 1)
9k 0 = (4k + 2n + 1) 2 N=(4n+1 + 6n 1) = 9k 0 :
Donc (4n+1 + 6n 1) est divisible par 9.

Ce qui fait que p(n + 1) est vraie.

3/Conclusion:
8n 2 N ; (4n + 6n 1) est divisible par 9.

Exercice 10
1/ Montrer que tout entier impair n s’écrit sous la forme n = 4k + r avec
k 2 N et r 2 f1; 3g :
Soit n un entier impair, 9s 2 N=n = 2s + 1, puisque s est un entier
naturel, il peut être pair ou impair, donc 9k 2 N=s = 2k + 1 ou bien s = 2k
(rappelons que 0 peut très bien être considérer comme un nombre et pair en
plus !).
Dans ce cas, n = 4k + r avec k 2 N et r 2 f1; 3g :
2/Montrer maintenant par contraposition que pour n 2 N on a :

Si (n2 1) n’est pas divisible par 8 alors n est pair.

Soit n 2 N ; par contraposition, nous allons monter que si n est impair

alors (n2 1) est divisible par 8.

n impair ) n = 4k + r avec k 2 N et r 2 f1; 3g

(n2 1) = 16k 2 + 8kr + r2 1 et r2 1 2 f0; 8g

32
Ce qui fait que (n2 1) = 16k 2 + 8kr ou bien (n2 1) = 16k 2 + 8kr + 8

Dans les deux cas (n2 1) est divisible par 8.

33