Chapitre 1 - Eléments de Logique et de Théorie des Ensembles PDF

CHAPITRE 1 ELÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES 1.1 Eléments de logique 1.1.1 Définitions et propriétés Définition 1.1.1 Une proposition (ou assertion) est un énoncé mathématique (ou non) qui est soit vrai, soit faux. On dit alo...

CHAPITRE 1 ELÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES 1.1 Eléments de logique 1.1.1 Définitions et propriétés Définition 1.1.1 Une proposition (ou assertion) est un énoncé mathématique (ou non) qui est soit vrai, soit faux. On dit alors qu’une proposition P ne prend que deux valeurs de vérité : V (vraie) ou P F (fausse). Une table de vérité consigne ces deux valeurs : V F Exemple 1.1.1 1. (32 > 8) est une proposition vraie. 2. " Tout entier impair est premier " est une proposition fausse : 9 est impair mais non premier. Une proposition qui est toujours vraie est appelée une tautologie. La négation d’une proposition P est la proposition notée (non P ) et définie par : P non P V F F V La négation d’une proposition P est également notée ¬P ou P.. Connecteurs logiques : A partir de deux ou plusieurs propositions, on en construit d’autres en utilisant les connecteurs logiques. Dans ce qui suit, P et Q sont deux propo- sitions quelconques. 1 CHAPITRE 1. ELÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES 1. Conjonction - disjonction : Les connecteurs "et" (conjonction) et "ou" (disjonction) sont définis par la table de vérité suivante : P Q P et Q P ou Q V V V V V F F V F V F V F F F F 2. Implication - équivalence : Les connecteurs "⇒" (implication) et "⇔" (équivalence) sont définis par la table de vérité suivante : P Q P ⇒Q P ⇔Q V V V V V F F F F V V F F F V V Notons que deux propositions sont équivalentes si elles ont les mêmes valeurs de vérité, c’est-à-dire si elles sont toutes les deux vraies ou toutes les deux fausses et que l’on a : (P ⇔ Q) ⇔ ((P ⇒ Q) et (Q ⇒ P )) Autres notations : Le connecteur "et" se note aussi "∧". Le connecteur "ou" se note "∨". Définition 1.1.2 Soient P et Q deux propositions. La contraposée de (P ⇒ Q) est la proposition (non Q ⇒ non P ). La réciproque de (P ⇒ Q) est la proposition (Q ⇒ Q). Les principales propriétés des connecteurs logiques sont regroupées dans la proposition suivante : Proposition 1.1.1 Soient P, Q et R trois propositions. On a alors : 1. (P ∧ P ) ⇔ P 2. (P ∨ P ) ⇔ P 3. (P ∧ Q) ⇔ (Q ∧ P ) 4. (P ∨ Q) ⇔ (Q ∨ P ) 5. (P ⇒ Q) ⇔ ((nonQ) ⇒ (nonP )) 6. (P ⇒ Q) ⇔ ((nonP ) ou Q)) 7. (P ∨ (nonP )) est toujours vraie 8. (P ∧ (nonP )) est toujours fausse 9. P ∧ (Q ∧ R) ⇔ (P ∧ Q) ∧ R 10. P ∨ (Q ∨ R) ⇔ (P ∨ Q) ∨ R 11. P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R) 12. P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R) 13. non(P ∧ Q) ⇔ (nonP ) ∨ (nonQ) 14. non(P ∨ Q) ⇔ (nonP ) ∧ (nonQ) Remarque 1.1.1 a) La propriété 5 de la proposition ci-dessus exprime le principe de contraposi- tion. b) Les propriétés 13 et 14 s’appellent les lois de De Morgan. La démonstration de la proposition précédente se fait en dressant la table de vérité pour chacune des propriétés énoncées ( à faire à titre d’exercice ). Page 2 sur 6 1.1. ELÉMENTS DE LOGIQUE CHAPITRE 1. ELÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES 1.1.2 Ensembles - Quantificateurs Définition 1.1.3 Un ensemble E est une collection d’objets appelés éléments de E. Si x est un élément de E, on écrit x ∈ E. Sinon, x ∈ / E. Soi P(.) une propriété dépendant d’une ou plusieurs variables d’un ensemble E. On définit alors les propositions suivantes : - (∀x ∈ E, P(x)) : pour tout x ∈ E ; on a P(x). - (∃x ∈ E, P(x)) : il existe au moins un élément x de E tel que l’on ait P(x). - (∃!x ∈ E, P(x)) : il existe un unique élément x de E tel que l’on ait P(x). Les symboles " ∀ " et " ∃ " s’appellent respectivement le quantificateur universel et le quantificateur existentiel. Exemple 1.1.2 a) Pour x réel, on pose P(x) : ”x2 ≥ 1”. Alors : - la proposition (∀x ∈ [1, +∞[, P(x)) est vraie, alors que la proposition (∀x ∈ R, P(x)) est fausse. b) Pour x, y réels, on pose P(x, y) : ”x2 + y ≥ 1”. Alors : - la proposition (∀x ∈ R, ∀y ∈ R, P(x, y)) est fausse, alors que la proposition (∃x ∈ R, ∃y ∈ R, P(x, y)) est vraie. Exercice : La proposition : (∀x ∈ R, ∃y ∈ Z, x ≥ y) est-elle vraie ? Justifier la réponse. — L’ordre des quantificateurs : l’ordre des quantificateurs est important comme le montre l’exemple suivant : soit la proposition : ∀x ∈ R, ∃y ∈ R, y > x. Cette proposition est vraie puisque pour tout réel x, on peut prendre y = x + 1 (par exemple) vérifiant ainsi y > x. Inversons maintenant les quantificateurs : ∃x ∈ R, ∀y ∈ R, y > x. Cette proposi- tion cette fois est fausse car on ne peut trouver un réel inférieur à tous les autres. Toutefois, on peut permuter deux quantifacteurs qui se suivent et de même nature. — Négation d’une phrase quantifiée : pour nier une phrase quantifiée, on utilise la proposition suivante ( en conservant les mêmes noations que précedemment) : Proposition 1.1.2 On a : 1. non (∀x ∈ E, P(x)) ⇔ (∃x ∈ E; non(P(x))). 2. non (∃x ∈ E, P(x)) ⇔ (∀x ∈ E; non(P(x))). Page 3 sur 6 1.1. ELÉMENTS DE LOGIQUE CHAPITRE 1. ELÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES 1.1.3 Quelques méthodes de raisonnement 1. Démonstration par contraposition : Si P et Q sont deux propositions, montrer la proposition (P ⇒ Q) revient à montrer (¬Q ⇒ ¬P ), d’après le principe de contraposition. Exemple 1.1.3 Soit n ∈ N. Montrons que (n2 pair ⇒ n pair). Pour ce faire, on prouve la contra- posée, c’est-à-dire : (n impair ⇒ n2 impair). En effet, si n est impair, il existe k ∈ N tel que n = 2k + 1 et donc n2 = 2(2k 2 + 2k) + 1 ce qui montre que n2 est impair. 2. Raisonnement par l’absurde : On veut démontrer qu’une proposition P est vraie. On suppose (non P ) et on déduit une contradiction, c’est-à-dire une pro- position Q telle que (Q et non Q) soit vraie. On conclut alors que P est vraie. Remarquons que ce principe est basé sur la tautologie suivante :
(¬P ⇒ Q) ∧ (¬P ⇒ ¬Q) ⇒ P Exemple 1.1.4 √ Montrons par l’absurde la proposition (P ) : 2 est irrationnel. On suppose (non √ P ), c’est-à-dire que 2 est rationnel : il existe donc p ∈ Z ∗ et q ∈ N premiers √ p entre eux tels que 2 =. D’où p2 = 2q 2. Par conséquent, p est pair et donc il q existe k ∈ Z tel que p = 2k de sorte que p2 = 4k 2 = 2q 2 , soit q 2 = 2k 2. Ainsi, q √ pair et ceci contredit le fait que p et q sont premiers entre eux. Il en résulte que est 2∈ / Q. 3. Raisonnement par récurrence : -Récurrence simple : Soit P(n) une propriété dépendant d’un entier naturel n, et soit n0 ∈ N. Alors, on a la proposition suivante : Proposition 1.1.3 On suppose que : a) P(n0 ) est vraie b) ∀n ≥ n0 , (P(n) ⇒ P(n + 1)). Alors P(n) est vraie pour tout n ≥ n0. Exemple 1.1.5 Montrons par récurrence la proposition : ∀n ∈ N, 2n > n. On note P(n) la propriété ”2n > n” On a d’abord P(0) est vraie puisque 20 > 0. Supposons maintenant que P(n) vraie pour un certain entier n ≥ 1 et montrons alors que P(n + 1) est vraie. On a 2n+1 = 22n > 2n ≥ n + 1 ce qui prouve que P(n + 1) est vraie. Par conséquent, P(n) est vraie pour tout entier naturel n. Page 4 sur 6 1.1. ELÉMENTS DE LOGIQUE CHAPITRE 1. ELÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES -Récurrence forte : Avec les mêmes notations, on a la proposition suivante : Proposition 1.1.4 On suppose que : a) P(n0 ) est vraie
b) ∀n ≥ n0 , [ P(n0 ) ∧ P(n0 + 1) ∧... P(n) ⇒ P(n + 1)]. Alors P(n) est vraie pour tout n ≥ n0. Exemple 1.1.6 Soit (un ) la suite réelle définie par : u0 = 1 et un+1 = nk=0 uk. Montrons par récurrence P forte la proposition : ∀n ∈ N∗ , un = 2n−1. Notons P(n) : un = 2n−1. On a P(1) est vraie ∗ 0
puisque u1 = 1 = 2. Soit maintenant n ∈ N tel que P(1) ∧ P(2) ∧... P(n). On a alors 2n − 1 un+1 = nk=0 uk = 1 + 1 + 2 +... + 2n−1 = 1 + = 2n de sorte que P(n + 1) est P 2−1 vraie. Par la proposition précédente, on a P(n) pour tout n ∈ N∗. 1.2 Ensembles a) Définitions et notations : Dans ce qui suit, E et F sont deux ensembles. Définition 1.2.1 On dit que E est une partie de F ( ou E inclus dans F , ou E sous-ensemble de F ), et on note E ⊂ F , si tout élément de E est élément de F. On a alors : E ⊂ F ⇔ ∀x ∈ E, x ∈ F. On dit que E et F sont égaux et on note E = F s’ils ont les mêmes éléments et on a donc : E = F ⇔ E ⊂ F et F ⊂ E. On note ∅ l’unique ensemble ne contenant aucun élément. Remarquons que ∅ et E sont des parties de E. On note P(E) l’ensemble des parties de E. On a par suite : A ∈ P(E) ⇔ A ⊂ E. Exemple 1.2.1 1. On a P(∅) = {∅} et P(P(∅)) = {∅, {∅}}. 2. Si E = {a}, alors P(E) = {∅, {a}}. Page 5 sur 6 1.2. ENSEMBLES CHAPITRE 1. ELÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES Définition 1.2.2 Soient A et B deux parties d’un ensemble E. On définit : 1. La réunion de A et B, notée A ∪ B, par A ∪ B = {x ∈ E/ x ∈ A ou x ∈ B}. 2. L’intersection de A et B, notée A∩B, par A∩B = {x ∈ E/ x ∈ A et x ∈ B}. 3. La différence de A et B, notée A \ B par A \ B = {x ∈ E/ x ∈ A et x ∈ / B}. 4. Le complémentaire de A dans E, noté A ou CEA , par A = E \ A. 5. La différence symétrique de A et B, notée A∆B, par A∆B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B). b) Propriétés : Pour toutes parties A et B d’un ensemble E, on a : 1. A ∪ ∅ = A 2. A ∪ A = E 3. A ∩ CEA = ∅ 4.A ∩ ∅ = ∅ 5. A ∪ B = B ∪ A 6. A ∩ B = B ∩ A 7. A ∩ (B ∩ C) = (A ∩ B) ∩ C 8. A ∪ (B ∪ C) = (A ∪ B) ∪ C 9. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 10. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (A∪B) (A∩B) 11. CE = CEA ∩ CEB 12. CE = CEA ∪ CEB Exercice : Soient A et B deux parties d’un ensemble E. Vérifier que A ∩ B = ∅ ⇔ A ⊂ B. c) Produit cartésien : Soient E et F deux ensembles. On définit le produit cartésien de E et F , noté E × F , par : E × F = {(x, y)/ x ∈ E et y ∈ F } En outre, on a : ∀(x, y) ∈ E × F, ∀(x0 , y 0 ) ∈ E × F, (x, y) = (x0 , y 0 ) ⇔ x = x0 et y = y 0. Exemple 1.2.2 1) Si E = {1, 2} et F = {3, 4}, alors E × F = {(1, 3), (1, 4), (2, 3), (2, 4)}. 2) On vérifie que pour tout ensemble E, ∅ × E = E × ∅ = ∅. Soient n ≥ 3 et E1 , E2 ,... , En n ensembles. On note E1 × E2... × En = {(x1 , x2 ,... , xn ), ∀i ∈ {1,... , n}, xi ∈ Ei } et on a : ∀(x1 ,... , xn ) ∈ E1 × E2... × En , ∀(x01 ,... , x0n ) ∈ E1 × E2... × En , (x1 ,... , xn ) = (x01 ,... , x0n ) ⇔ ∀i ∈ {1,... , n}, xi = x0i. (x1 ,... , xn ) ∈ E1 × E2... × En s’appelle un n-uplet de E1 × E2... × En. Si E1 = E2 =... = En = E, on note E1 × E2... × En = E n. Page 6 sur 6 1.2. ENSEMBLES