Université Félix Houphouet Boigny / UFR - MI /

2021 - 2022/ L1 TC

Fiche de TD - Éléments de Logique mathématique

Exercice 0.1

En notant P et Q les affirmations suivantes :

P : Jean est fort en Maths.
Q : Jean est fort en Chimie.

Représenter les affirmations suivantes sous forme symbolique, à l’aide des lettres P et Q
et des connecteurs usuels.
1) Jean est fort en Maths mais faible en Chimie.
2) Jean est fort en Math ou il est à la fois fort en chimie et faible en Maths.
3) Jean n’est fort ni en Math ni en Chimie.
4) Jean est fort en Maths s’il est fort en Chimie.

Exercice 0.2
1) P, Q et R étant des propositions données, construire les tables de vérité des formes pro-
positionnelles suivantes (où P est la négation de P ) :

(i) P ⇒ (P ∨ Q)

(ii) P ⇒ (Q ∨ R)

(iii) P ∨ Q

(iv) (P ∧ Q) ⇒ Q

(v) P ∨ Q ∧ R.
 2

2) Une tautologie est une proposition intrinsèquement vraie. Par exemple, soit P est une
proposition. La connection P ∨ P est une tautologie. Soient P, Q, R des propositions. On
considère les deux propositions suivantes

[(P ⇒ Q) ∨ (Q ⇒ R)] ⇒ (P ⇒ R) (1)

(P ⇒ Q) ⇒ [(P ∨ R)) ⇒ (Q ∨ R)] (2)

(a) Sans utiliser de table de vérité, montrer que la proposition (1) est une tautologie.
(b) Vérifier si la proposition (2) est une tautologie.

Exercice 0.3
En notant P, Q et R les 3 affirmations suivantes :

P : Pierre fait des Maths

Q : Pierre fait de la chimie

R : Pierre fait de l’Anglais

représenter les affirmations qui suivent sous forme symbolique, à l’aide des lettres P, Q,
R et des connecteurs usuels.

1) Pierre fait des Maths et de l’Anglais mais pas de Chimie.

2) Pierre fait des Maths et de la Chimie mais pas à la fois de la chimie et de l’Anglais.

3) Il est faux que Pierre fasse de l’Anglais sans faire de Maths.

4) Il est faux que Pierre ne fasse pas des Maths et fasse quand même de la Chimie.

5) Il est faux que Pierre fasse de l’Anglais sans faire de Maths.

6) Pierre ne fait ni Anglais ni Chimie mais il fait des Maths.

Exercice 1
1) étant donnés deux entiers a et b, on considère les duex propositions :
Q : a et b sont touts les deux pairs
Q : a et b sont de parités différentes. Que signifient les implications suivantes et lesquelles
sont vraies pour les valeurs de a et b ? t

P ⇒ Q, Q ⇒ P, P ⇒ Q, Q ⇒ P, P ⇒ Q, Q ⇒ P, P ⇒ Q, Q ⇒P

Exercice 2
Ecrire les implications ou équivalences correctes :
 3

a) [∀ x ∈ E, p(x) et q(x)]...........[∀ x ∈ E, p(x)] et [∀ x ∈ E, q(x)]

b) [∃ x ∈ E, p(x) et q(x)]...........[∃ x ∈ E, p(x)] et [∃ x ∈ E, q(x)]

c) [∀ x ∈ E, p(x) ou q(x)]...........[∀ x ∈ E, p(x)] ou [∀ x ∈ E, q(x)]

d) [∃ x ∈ E, p(x) ou q(x)]..........[∃ x ∈ E, p(x)] ou [∃ x ∈ E, q(x)].

Exercice 3

Soit (x, y) ∈ R × R. Ecrire les négations des propositions suivantes :

1) 1 ≤ x < y

2) x y = 0

3) x2 = 1 ⇒ x=1
0 0 0
4) ∀ x ∈ E, ∀ x ∈ E, x 6= x ⇒ f (x) 6= f (x )

5) ∀ ε > 0, ∃ η > 0, ∀ x ∈]a, b[, |x − x0 | < η ⇒ |f (x) − f (x0 )| < ε

6) ∀ a ∈ Z, ∀ b ∈ N∗ , ∃ q ∈ Z, a = b q + r et 0 ≤ r < b.

Exercice 4

VRAI ou FAUX ?

1) P, Q étant des propositions, La négation de (P ⇒ Q) est (Q ⇒ P )

2) soit f : E −→ F une application.

(∀ x, y ∈ E, f (x) = f (y) ⇒ x = y) ⇔ (∀ x, y ∈ E, x = y ou f (x) = f (y)

3) Si f : E −→ F et g : F −→ E sont des applications bijectives, on a

(f ◦ g)−1 = f −1 ◦ g −1

4) Soient f : E −→ F une application et A ⊆ E.

∀ x ∈ E, f (x) ∈ f (A) ⇒ x ∈ A

Exercice 5
 4

P, Q, R, S étant 4 propositions, on désigne par A la proposition : (P ∨ Q) ∧ (R ∨ S) et

par B la proposition : (P ∧ Q) ∨ (R ∧ S)

1) Déterminer une autre proposition équivalente à A et une autre proposition équivenlente

à B.

2) x et y étant des nombres réels, en utilisant les résultats de la question précédente, résoudre
le système (S) suivant : 
(x − 1)(y − 2) = 0
(x − 2)(y − 3) = 0
3) x et y étant des nombres réels, en utilisant les résultats de la question précédente, résoudre
l’équation (E) suivante :

|(x − 3)(y − 2)| + |(x − 1)(y − 4)| = 0

Exercice 6

Soient P et Q deux propositions. On note P ↑ Q la proposition e(P ∧ Q).

↑ s’appelle la barre de Sheffer.

1) Exprimer eP, P ∧ Q, P ∨ Q à l’aide de P, Q et du seul connecteur ↑.

2) Exprimer de même P ⇒ Q et P ⇔ Q.

Exercice 7
Ecrire à l’aide de quantificateurs les propositions suivantes et donner les valeurs de vérité.

1) Le carré de tout réel est positif.

2) Certains réels sont strictement supérieurs à leur carré.

3) Aucun entier n’est supérieur à tous les autres.

4) Tous les réels ne sont pas des quotients d’entiers.

5) Il existe un entier multiple de tous les autres.

6) Entre deux réels distincts, il existe un rationnel.

7) Etant donné trois réels, il y en a au moins deux de même signe.

Exercice 8
 5

1) Démontrer par récurrence les propositions suivantes :

Pn
a)∀ n ∈ N, k=0 2k = 2n+1 − 1
Pn n (n+1) (2n+1)
b) ∀ n ∈ N, k=0 k2 = 6

2) Démontrer par récurrence que

∀ n ∈ N \ {0, 1, 2, 3}, n2 ≤ 2n
Exercice 9

Démontrer que pour tout n ∈ N,

1) n3 − n est divisible par 6,

2) n5 − n est divisible par 30,

3) Soit 4 divise n2 , soit 4 divise n2 − 1.

Ensembles, Applications

Exercice 10

Soient A, B et C des parties quelconques d’un ensemble E. On note A le complémentaire

de A dans E Simplifier les ensembles suivants :

1) X = (A ∩ B) ∪ (A ∩ B),

2) Y = (A ∪ B) ∩ (A ∪ B),

3) Z = A ∩ B ∩ (A ∩ B),

4) U = [A ∩ (B ∪ C)] ∩ [(B ∩ C) ∪ C],

5) V = (A ∩ B) ∪ (A ∩ C) ∪ [(A ∪ B) ∩ (A ∪ C)].

Exercice 11

Soient A, B, C des ensembles ; Montrer que :

1) A ∪ B = A ∩ C ⇒ B ⊂ A ⊂ C,
 6

2) A ∩ B ⊂ A ∩ C et A ∪ B ⊂ A ∪ C ⇒ B ⊂ C.

Exercice 12
Soient A, B, C des parties d’un ensemble E.

I) Ecrire en utilisant ∀, ∃ les assertions suivantes.

(a) A = ∅

(b) A ∩ B 6= ∅

(c) A ∪ B = ∅

II) Dire si les propositions suivantes sont vraies. (Justifier vos réponses !)

1) A ⊆ B ⇔ A∪B =B;

2) A ⊆ B ⇔ A∪B =E;

3) A ⊆ B ∩ A ⇒ B⊆A

4) A ∪ B ⊆ A ⇒ A ⊆ B.

5) A ⊆ B ∩ C ⇒ A⊆B et A ⊆ C

6) A ⊆ B ∪ C ⇒ A⊆B ou A ⊆ C.

7) A ⊆ B ∩ C ⇒ A⊆B ou A ⊆ C.

8) A ⊆ B ∪ C ⇒ A⊆B et A ⊆ C.

9) B ∩ C ⊆ A ⇒ B ⊆ A et C ⊆ A.

Exercice 13
On appelle différence symétrique de deux sous-ensembles A et B de E le sous ensemble noté
A∆B suivant :
A∆B = (A \ B) ∪ (B \ A)
1) Montrer que A∆B = (A ∪ B) \ (A ∩ B)
2) Déterminer A∆∅, A∆E, A∆A, A∆A où A est une partie de E et A sont complémentaire
dans E.
3) Montrer que A∆B = ∅ ⇔ A = B.
 7

4) Soient A, B, C des parties de E. Montrer que

(A∆B)∆C = A∆(B∆C)
Exercice 14

a) Indiquer si la famille d’ensemble (An )n∈N partitionne E dans chaque cas suivan :

1) ∀ n ∈ N, An = {n, n + 2} et E = N,

2) ∀ n ∈ N, An = {2 n, 2 n + 1} et E = N,

3) ∀ n ∈ N, An = [2 n, 2 n + 1[ et E = R∗+ ,

4) ∀ n ∈ N∗ , An = [ n+1
1
, n1 [ et E =]0, 1[.

b) Pour tout n ∈ N∗ , on pose Bn =] n1 , n + 1]. Caractériser de manière explicite les ensembles

suivants : \ [
C= Bn , D= Bn
n∈N∗ n=∈N∗

Exercice 15

Soit P l’ensemble de tous les pays du monde et V l’ensemble de toutes les villes du monde.
On note G l’ensemble de tous les gens qui ont vécu jusqu’à aujourd’hui. Soit I l’ensemble de
tous les Ivoiriens.

Soit c : P −→ V l’application qui associe à p ∈ P la ville capitale de p.

Soit m : G −→ G l’application qui associe à g ∈ G la mère de g.

Soit h : R × R −→ R définie par h(x, y) = 2 x + 5 y + 1.

1) Déterminer si ces applications sont injectives, surjectives, bijectives.

2) Quelle est l’image directe c(P ) de P par c ?

3) Quelle est l’image directe de G par m ?

4) Quelle est l’image directe de I par m ?

5) Quelle est l’image directe de R × R par h ?

Exercice 16
 8

1) On considère l’application f : R × R −→ R × R définie par f (x, y) = (x, x y − y 3 ).

L’application f est elle injective ? Est elle surjective ?

2) Soit h l’application de R × R vers R × R définie par

h(x, y) = (2 x + y − 1, −3 x + 2 y + 2)

démontrer que h est une bijection et déterminer sa bijection réciproque h−1 .

Exercice 17

1
soit f : R −→ R la fonction définie par x 7−→ f (x) = x2 +1
.

Déterminer les ensembles suivants :

f ([−2, 1], f ([0, 3]), f −1 ([−1, 1]), f −1 ([ 51 , 21 ].

Exercice 18

Pour tout entier n ∈ N∗ , on pose An = [ n+1

1
, n1 [.
2x
On considère l’application f : R −→ R définie par f (x) = .
1 + x2
a) Vérifier si la famille de parties (An )n∈N∗ partitionne l’ensemble E =]0, 1[.

b) L’application f est-elle injective ? Est elle surjective ? Justifier les réponses !

c) Déterminer f (An ) pour tout n ∈ N∗ .

d) On pose I = [ 41 , 1]. Déterminer f −1 (I).

e) Montrer que f (R) = [−1, 1]. La famille (f (An ))n∈N∗ est-elle une partition de [−1, 1] ?

Exercice 19

Soient E un ensemble et A, B deux parties de E. Soit f l’application de P(E) vers P(E) ×

P(E) définie par f (X) = (X ∪ A, X ∪ B), ∀ X ∈ P(E).
Montrer que
f injective ⇔ A ∩ B = ∅
Exercice 20

1) Déterminer toutes les applications f de N vers N telles que

∀ m, n ∈ N, f (m + n) = f (m) + f (n)
 9

2) Déterminer toutes les applications g de N vers N telles que

∀ m, n ∈ N, g(m + n) = g(m) g(n)
3) Déterminer toutes les applications injectives h de N vers N telles que
∀ n ∈ N, h(n) ≤ n
4) Soit E un ensemble fini.

a) Montrer que toute application injective de E dans E est une bijection.

b) Montrer que toute application surjective de E sur E est une bijection.

Exercices 22
Soit f : E −→ E une application
Montrer que

a) f injective ⇔ ∀ A ∈ P(E), A = f −1 (f (A)).

b) f surjective ⇔ ∀ B ∈ P(F ), f (f −1 (B)) = B.

0 0 0
c) f injective ⇔ ∀ A, A ∈ P(E), f (A ∩ A ) = f (A) ∩ f (A ).

Relations d’équivalence - Relations d’ordre

Exercice 23
On considère l’ensemble E = {∗, , 4, ♦} et les relations binaires suivantes :
R = {(∗, ∗), (4, 4), ( , )}, S = {(∗, ∗), (4, 4), (♦, ♦), (♦, ), (4, ♦), (∗, ♦)}

Etudier les relations binaires R et S (réflexivité, symétrie, antisymétrie, transitivité).

Exercice 24

On considère les deux relations R, ∆ suivantes :

a) E = R,
∀ x, y ∈ R, xRy ⇔ cos2 x + sin2 y = 1.

b) E = N,
∀ x, y ∈ N, x∆y ⇔ ∃ p, q ∈ N∗ , y = p xq .

1) Pour chacune de ces relations, étudier la réflexivité, la symétrie, l’antisymétrie et la tran-

sitivité.
 10

2) La relation ∆ est-elle une relation d’ordre totale ? Justifier la réponse.

Exercice 25 : Relation de congruence modulo n sur Z.

Soit n ∈ N. Sur Z, on considère la relation R définie comme suit : pour tous a et b éléments
de Z, on a
a R b si b − a ∈ nZ
(i)- Montrer que la relation R est une relation d’équivalence.

(ii)- Montrer que la relation R a exactement n classes d’équivalences si n 6= 0,.

(iii)- Montrer que la relation R est compatible à la fois avec + et ×.

(iv)- Décrire les classes d’équivalence dans les cas suivants : n = 0, n = 1, n = 2, n =

3, n = 4, n = 7.

Exercice 26
Sur Z on considère la relation R définie comme suit : Pour tous a et b éléments de Z, on a

a R b si b2 − a2 ∈ 6 Z

(i)- Montrer que R est une relation d’équivalence.

(ii)- Déterminer les classes d’équivalence.

Exercice 27

On munit l’ensemble R×R de la relation binaire notée ∆, définie par : pour tout (x, y) ∈ R×R
et (a, b) ∈ R × R,

(x, y) ∆(a, b) ⇔ x < a ou (x = a et y ≤ b).

Démontrer que la relation ∆ est une relation d’ordre total sur R × R.