Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université Clermont Auvergne Outils Mathématiques 2 Portail AVEC mathématiques

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, quantiﬁcateurs, règles de logique ✓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 non A V F F V A B A ou B A et B V V V V V F V F F V V F F F F F [non A] : négation de A [A ou B] : disjonction de A, B (« ou » inclusif) [A et B] : conjonction de A, B. ✓L’implication A ⇒B signiﬁe : « 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 suﬃsante pour B et B est une condition nécessaire pour A. ✓L’équivalence A ⇔B est déﬁnie par la proposition : [ A ⇒B et B ⇒A ]. – A ⇔B signiﬁe 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) non(A ⇒B) A et (non B) (Contraposition) ✓Le quantiﬁcateur « ∃» signiﬁe « il existe » et le quantiﬁcateur « ∀» signiﬁe « 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 aﬀecté d’un ∃dépend de tous les objets aﬀectés de ∀qui le précèdent dans l’énoncé. ✓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 : L’assertion A • Direct : on cherche une assertion B qui est vraie et qui implique A • Par l’absurde : on suppose que A est fausse et on cherche une contradiction. L’implication A ⇒B • Direct : on suppose que A est vraie et on démontre qu’alors B est vraie. • Par contraposition : on démontre l’implication [(non B) ⇒(non A)]. L’équivalence A ⇐ ⇒B • Par double implication : on démontre les implications [A ⇒B] et [B ⇒A]. L’assertion [∀n ∈N, A(n)] • Par récurrence : on démontre l’initialisation et l’hérédité : – Initialisation : A(0) est vraie ; – 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. ✓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ériﬁent A(x). ✞ ✝ ☎ ✆ Ensembles ✓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 ̸∈A signiﬁe « 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. ✓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. Déﬁnitions :          Complémentaire : ∁EA = {x ∈E ; x ̸∈A} Réunion : A ∪B = {x ∈E ; x ∈A ou x ∈B} Intersection : A ∩B = {x ∈E ; x ∈A et x ∈B} Diﬀérence : A \ B = {x ∈E ; x ∈A et x ̸∈B} Propriétés : ( A ∩(B ∪C) = (A ∩B) ∪(A ∩C) A ∪(B ∩C) = (A ∪B) ∩(A ∪C) ∁E(A ∪B) = (∁EA) ∩(∁EB) ∁E(A ∩B) = (∁EA) ∪(∁EB) ✓Une famille (Ai)i∈I de parties non vides de E est une partition de E lorsque : 1. ∀i, j ∈I, i ̸= j ⇒Ai ∩Aj = ∅; 2. la réunion de toutes ces parties, notée S i∈I Ai, est égale à E. ✓Le produit cartésien E × F désigne l’ensemble de tous les couples (x, y) où x ∈E et y ∈F. 2 ✞ ✝ ☎ ✆ Applications ✓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éﬁnie 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éﬁnie 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éﬁnie 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. – La fonction indicatrice 1A ∈F(E, R) d’une partie A de E, est déﬁnie par 1A(x) = n 1 si x ∈A 0 si x ̸∈A. . On a : 1A∩B = 1A 1B, 1A∪B = 1A + 1B − 1A 1B, 1∁EA = 1 − 1A. ➢Pour f, g ∈F(E, F), l’égalité f = g, signiﬁe : [ ∀x ∈E, f(x) = g(x)]. ✓Image directe et Image réciproque par une application f ∈F(E, F). Déﬁnitions : ( Image directe d’une partie X ⊂E : f(X) = {y ∈F ; ∃x ∈X, y = f(x)} Image réciproque d’une partie Y ⊂F : f −1(Y ) = {x ∈E ; f(x) ∈Y } Propriétés : ( f(A ∪B) = f(A) ∪f(B) f(A ∩B) ⊂f(A) ∩f(B) B f −1(C ∪D) = f −1(C) ∪f −1(D) f −1(C ∩D) = f −1(C) ∩f −1(D) ✓L’application f ∈F(E, F) est      injective lorsque : ∀x, x′ ∈E, [f(x) = f(x′)] ⇒[x = x′] 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. ✓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). – Si E = {1, 2, . . ., n}, on note Sn pour S(E) et on présente σ ∈Sn sous la forme σ = 1 2 · · · n σ(1) σ(2) · · · σ(n) ! . ✞ ✝ ☎ ✆ Notations pour somme et produit ✓La uploads/Philosophie/ fiche-1-avec-maths.pdf