Université Clermont Auvergne Outils Mathématiques 2

Portail AVEC mathématiques

Fiche du chapitre I
Raisonnements, Ensembles, Dénombrements

En vue d’une utilisation lors de l’examen, ne pas annoter (surligneur et encadrement autorisés)
✞ ☎
Propositions, quantificateurs, règles de logique ✆
✝

X Une proposition (ou énoncé, assertion) est une phrase mathématique dotée d’un sens.
– Une proposition peut être vraie (V) ou fausse (F).

A B A ou B A et B [non A] : négation de A
A non A V V V V [A ou B] : disjonction de A, B (« ou » inclusif)
V F V F V F [A et B] : conjonction de A, B.
F V F V V F
F F F F

X L’implication A ⇒ B signifie : « Si A est vraie alors B est vraie ».

– Elle a même valeur de vérité que [ (non A) ou B ].
– Lorsque [A ⇒ B] est vraie, A est une condition suffisante pour B et B est une condition nécessaire pour A.
X L’équivalence A ⇔ B est définie par la proposition : [ A ⇒ B et B ⇒ A ].
– A ⇔ B signifie que A et B ont mêmes valeurs de vérité, ou encore : « A est vraie si et seulement si B est vraie ».

La proposition : est équivalente à :

non(non A) A
non(A ou B) (non A) et (non B)
non(A et B) (non A) ou (non B)
A⇒B (non B) ⇒ (non A) (Contraposition)
non(A ⇒ B) A et (non B)

X Le quantificateur « ∃ » signifie « il existe » et le quantificateur « ∀ » signifie « quel que soit ».

– « il existe » est toujours synonyme de « il existe au moins un », et « il existe un unique » se note ∃!

La proposition : est équivalente à :

∃x ∈ E, ∃y ∈ F, A(x, y) ∃y ∈ F, ∃x ∈ E, A(x, y)
∀x ∈ E, ∀y ∈ F, A(x, y) ∀y ∈ F, ∀x ∈ E, A(x, y)


non ∃x ∈ E, A(x) ∀x ∈ E, (non A(x))


non ∀x ∈ E, A(x) ∃x ∈ E, (non A(x))

MAIS [∃x ∈ E, ∀y ∈ F, A(x, y)] et [∀y ∈ F, ∃x ∈ E, A(x, y)] NE SONT PAS ÉQUIVALENTES.
– Un objet affecté d’un ∃ dépend de tous les objets affectés de ∀ qui le précèdent dans l’énoncé.

X La notation {x ∈ E ; A(x)} désigne l’ensemble des x appartenant à E et tels que A(x) vraie.

1
 ✞ ☎
✝Méthodes de raisonnements ✆

Pour Démontrer : On peut utiliser un raisonnement :

• Direct : on cherche une assertion B qui est vraie et qui implique A
L’assertion A
• Par l’absurde : on suppose que A est fausse et on cherche une contradiction.
L’implication • Direct : on suppose que A est vraie et on démontre qu’alors B est vraie.
A⇒B • Par contraposition : on démontre l’implication [(non B) ⇒ (non A)].
L’équivalence
• Par double implication : on démontre les implications [A ⇒ B] et [B ⇒ A].
A ⇐⇒ B
• Par récurrence : on démontre l’initialisation et l’hérédité :
L’assertion – Initialisation : A(0) est vraie ;
[∀n ∈ N, A(n)] – Hérédité : pour tout entier n ∈ N, l’implication [A(n) ⇒ A(n + 1)] est vraie.
Le principe de récurrence permet de conclure que [∀n ∈ N, A(n)] est vraie.
Variantes du raisonnement par récurrence :
➢ Récurrence à partir d’un certain rang n0 ∈ N. Initialisation : A(n0 ) est vraie. Hérédité : pour tout n ≥ n0 ,
l’implication A(n) ⇒ A(n + 1) est vraie. Conclusion : [∀n ≥ n0 , A(n)] est vraie.
➢ Récurrence forte :
– Initialisation : A(0) est vraie ;
– Hérédité : pour tout n ∈ N, l’implication [A(0) et A(1) et . . . et A(n)] ⇒ A(n + 1) est vraie.
➢ Récurrence à deux pas :
– Initialisation : A(0) et A(1) vraies ;
– Hérédité : pour tout n ∈ N, l’implication [A(n) et A(n + 1)] ⇒ A(n + 2) est vraie.
X Pour déterminer S = {x ∈ E ; A(x)}, on peut utiliser un raisonnement par analyse-synthèse :
1. Analyse : On cherche une proposition plus simple B(x) qui est vraie lorsque A(x) est vraie.
2. Synthèse : Parmi les x satisfaisant la proposition B(x), on sélectionne ceux qui vérifient A(x).
✞ ☎
Ensembles
✝ ✆

X Une partie d’un ensemble E est un ensemble A dont tous les éléments appartiennent à E.
– On écrit x ∈ A pour « x appartient à A » et x 6∈ A signifie « x n’appartient pas à A ».
– On écrit A ⊂ B pour « A est inclus dans B ».
– ∅ désigne la partie vide de E et P(E) l’ensemble de toutes les parties de E.

X Opérations sur les parties. Soit A, B des parties d’un ensemble E.

➢ Pour obtenir l’égalité A = B, on procède souvent en démontrant les inclusions A ⊂ B et B ⊂ A.
Complémentaire : ∁E A = {x ∈ E ; x 6∈ A}



 Réunion :

A ∪ B = {x ∈ E ; x ∈ A ou x ∈ B}
Définitions :
 Intersection : A ∩ B = {x ∈ E ; x ∈ A et x ∈ B}


Différence : A \ B = {x ∈ E ; x ∈ A et x 6∈ B}

(
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Propriétés :
∁E (A ∪ B) = (∁E A) ∩ (∁E B) ∁E (A ∩ B) = (∁E A) ∪ (∁E B)
X Une famille (Ai )i∈I de parties non vides de E est une partition de E lorsque :
1. ∀i, j ∈ I, i 6= j ⇒ Ai ∩ Aj = ∅ ;
2. la réunion de toutes ces parties, notée Ai , est égale à E.
S
i∈I
X Le produit cartésien E × F désigne l’ensemble de tous les couples (x, y) où x ∈ E et y ∈ F .

2
 ✞ ☎
Applications ✆
✝

X Pour E et F deux ensembles non vide, une application f : E −→ F est un procédé qui à tout x ∈ E
associe un unique élément f (x) ∈ F .
– On note F (E, F ) l’ensemble des applications de E dans F .
– Lorsque f (x) = y on dit que y est l’image de x et que x est un antécédent de y pour la fonction f .
– L’application IdE ∈ F (E, E) (« identité de E ») est définie par IdE (x) = x pour tout x ∈ E.
– Si f ∈ F (E, F ) et g ∈ F (F, G) alors la composée g ◦ f ∈ F (E, G) est définie par (g ◦ f )(x) = g(f (x)) pour tout x ∈ E.
– Si A ⊂ E et f ∈ F (E, F ), alors la restriction f |A de f à A est définie par f |A (x) = f (x) pour tout x ∈ A.
– Si A ⊂ E, f ∈ F (E, F ) et g = f |A ∈ F (A, F ) alors on dit que f est un prolongement de g.
n 1 si x ∈ A
– La fonction indicatrice 1A ∈ F (E, R) d’une partie A de E, est définie par 1A (x) = .
0 si x 6∈ A.
On a : 1A∩B = 1A 1B , 1A∪B = 1A + 1B − 1A 1B , 1∁E A = 1 − 1A .
➢ Pour f, g ∈ F (E, F ), l’égalité f = g, signifie : [ ∀x ∈ E, f (x) = g(x)].

X Image directe
( et Image réciproque par une application f ∈ F (E, F ).
Image directe d’une partie X ⊂ E : f (X) = {y ∈ F ; ∃x ∈ X, y = f (x)}
Définitions :
Image réciproque d’une partie Y ⊂ F : f −1 (Y ) = {x ∈ E ; f (x) ∈ Y }
(
f (A ∪ B) = f (A) ∪ f (B) f (A ∩ B) ⊂ f (A) ∩ f (B) B
Propriétés :
f (C ∪ D) = f (C) ∪ f (D) f −1 (C ∩ D) = f −1 (C) ∩ f −1 (D)
−1 −1 −1


 injective lorsque :
 ∀x, x′ ∈ E, [f (x) = f (x′ )] ⇒ [x = x′ ]
X L’application f ∈ F (E, F ) est surjective lorsque : f (E) = F

bijective lorsque : elle est injective et surjective.


– [f injective ] ⇐⇒ [ ∀y ∈ F, f −1 ({y}) contient au plus un élément ]

– [f surjective ] ⇐⇒ [ ∀y ∈ F, f −1 ({y}) contient au moins un élément ] ⇐⇒ [∀y ∈ F , ∃x ∈ E, f (x) = y]
– [f bijective ] ⇐⇒ [ ∀y ∈ F, f −1 ({y}) contient exactement un élément ] ⇐⇒ [∀y ∈ F, ∃! x ∈ E, f (x) = y]
➢ Lorsque f est bijective, l’application g ∈ F (F, E) qui associe à y ∈ F l’unique x ∈ E tel que f (x) = y
s’appelle la bijection réciproque de f et elle est notée f −1 .
➢ f est bijective équivaut à : [ ∃g ∈ F (F, E), g ◦ f = IdE et f ◦ g = IdF ]. On a alors g = f −1 .

X Une permutation de E est une application bijective de E dans E.

– L’ensemble des permutations de E est noté S(E).
– Si σ, τ ∈ S(E) alors σ ◦ τ ∈ S(E) et σ −1 ∈ S(E). !
1 2 ··· n
– Si E = {1, 2, . . . , n}, on note Sn pour S(E) et on présente σ ∈ Sn sous la forme σ = .
σ(1) σ(2) · · · σ(n)
✞ ☎
Notations pour somme et produit ✆
✝

X La somme et le produit d’une famille finie {a1 , a2 , . . . , an } ⊂ R de nombres réels sont notés :
n
X n
Y
ak = a1 + a2 + · · · + an et ak = a1 × a2 × · · · × an .
k=1 k=1

Pn
+ bk ) = nk=1 ak + nk=1 bk
Pn Pn
Factorielle d’un entier naturel :
P P
k=1 (ak k=1 λak = λ k=1 ak
Qn Qn Qn Qn Qn
= λn 0! = 1 et n! = nk=1 k si n > 0.
Q
k=1 (ak bk ) = ( k=1 ak )( k=1 bk ) k=1 (λak ) k=1 ak

3
 ✞ ☎
Cardinal d’un ensemble fini, Dénombrement ✆
✝

X Le Cardinal d’un ensemble fini E est le nombre d’éléments qu’il contient : Card(E) ∈ N.
➢ Toute partie A d’un ensemble fini E est finie et Card(A) ≤ Card(E).
➢ Si A ⊂ B et B fini, alors : [Card(A) = Card(B) ⇐⇒ A = B].
Soit E, F des ensembles finis et A, B des parties de E.

Card(A ∪ B) + Card(A ∩ B) = Card(A) + Card(B) Card(A) + Card(∁E A) = Card(E)

Card(E × F ) = Card(E).Card(F ) Card(P(E)) = 2Card(E)
Card(F (E, F )) = Card(F )Card(E)


Card(S(E)) = Card(E) !

X Soit E, F deux ensembles finis et f ∈ F (E, F ). On a toujours : Card(f (E)) ≤ Card(E) et de plus :
➢ [Card(f (E)) = Card(E)] ⇐⇒ [ f injective ].
➢ [Card(f (E)) = Card(F )] ⇐⇒ [ f surjective ].
➢ Si Card(E) = Card(F ) alors : [ f injective ] ⇐⇒ [ f surjective ] ⇐⇒ [ f bijective ].

X Une p-combinaison dans un ensemble E est une partie de E de cardinal p.

➢ Si Card(E) = n, alors le nombre de p-combinaisons est :
   
n n! n
(Coefficient binomial) = si p ∈ J0, nK et = 0 si p > n.
p p!(n − p)! p

  
n−1
 
n−1
    
n n n
➢ Pour tout n ≥ 1 et tout p ∈ J1, nK : = + et = .
p p−1 p p n−p
n
➢ Les valeurs de s’obtiennent aussi à l’aide du triangle de Pascal :


p

p 0 1 2 3 4 5 6 7 8 9 10 11
n
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
9 1 9 36 84 126 126 84 36 9 1
10 1 10 45 120 210 252 210 120 45 10 1
11 1 11 55 165 330 462 462 330 165 55 11 1

➢ Les coefficients binomiaux interviennent dans la formule du binôme de Newton :

n  
n
X n
∗
∀a, b ∈ C, ∀n ∈ N , (a + b) = an−k bk .
k
k=0

4
X Un p-arrangement dans E est la donnée d’une p-combinaison d’éléments énumérés dans un ordre
donné. On le note comme un p-uplet (x1 , . . . , xp ) dont les composantes sont deux à deux distinctes.
➢ Il y a p! p-arrangements différents pour une p-combinaison donnée.
➢ Au p-arrangement (x1 , . . . , xp ) correspond l’application injective J1, pK → E, k 7→ xk .
Il y a donc autant de p-arrangements dans E que d’injections de J1, pK dans E et si Card(E) = n
alors ce nombre est  
p n! n
An = = p! .
(n − p)! p

✞ ☎
Relations d’équivalence sur un ensemble ✆
✝

Une relation binaire sur un ensemble E est une partie R de E × E. On note xRy lorsque (x, y) ∈ R.

X Une relation binaire R est une relation d’équivalence si elle satisfait les trois propriétés suivantes :
1. xRx pour tout x ∈ E (R est réflexive) ;
2. ∀x, y ∈ E, [xRy ⇒ yRx] (R est symétrique) ;
3. ∀x, y, z ∈ E, [(xRy et yRz) ⇒ xRz] (R est transitive) ;
Si R est une relation d’équivalence sur E, la classe d’équivalence de x est :
•
cl(x) = {y ∈ E ; xRy} ⊂ E (parfois notée x ou x).

cl(x) = cl(y) ⇐⇒ xRy

cl(x) 6= cl(y) ⇐⇒ cl(x) ∩ cl(y) = ∅

➢ Les classes d’équivalence distinctes de E forment une partition de E.

➢ L’ensemble des classes d’équivalences de E pour R est noté E/R et appelé ensemble quotient.
L’application q : E −→ E/R définie par q(x) = cl(x) est l’application quotient canonique.

X Une relation binaire R est une relation d’ordre si elle satisfait les trois propriétés suivantes :
1. xRx pour tout x ∈ E (R est réflexive) ;
2. ∀x, y ∈ E, [xRy et yRx ⇒ x = y] (R est antisymétrique) ;
3. ∀x, y, z ∈ E, [(xRy et yRz) ⇒ xRz] (R est transitive).