Théorie Des Ensembles
Commentaires Composés : Théorie Des Ensembles. Rechercher de 53 000+ Dissertation Gratuites et Mémoiressi et seulement si P est vraie et Q est fausse. - si P est vraie alors Q est vraie - il suffit que P soit vraie pour que Q soit vraie - il est nécessaire (il faut) que Q soit vraie pour que P soit vraie P ⇒ Q est équivalent à
¬P ∨ Q ¬P ∨ Q
V F V V
P V V F F
Q V F V F
P ⇒ Q V F V V
¬P
F F V V
Exemple : P ⇒ P est toujours vraie. P ⇒ Q : si ABCD est un carré alors ABCD est un parallélogramme P : ABCD est un carré Q : ABCD est un parallélogramme il suffit que P soit vraie pour que Q soit vraie Il suffit que ABCD soit un carré pour que ABCD soit un parallélogramme il est nécessaire (il faut) que Q soit vraie pour que P soit vraie il est nécessaire (il faut) que ABCD soit un parallélogramme pour que ABCD soit un carré mais ce n’est pas suffisant.
Réciproque
La réciproque de P ⇒ Q est Q ⇒ P ATTENTION : P ⇒ Q n’est pas équivalent à Q ⇒ P
Cours 1 AC
2/7
A 2008
MT18 Contraposée
La contraposée de P ⇒ Q est : P ⇒ Q est équivalent à
¬Q ⇒ ¬P
¬Q ⇒ ¬P ¬Q
F V F V
P V V F F
Q V F V F
P ⇒ Q V F V V
¬P
F F V V
¬Q ⇒ ¬P
V F V V
Négation
La négation d’une implication n’est pas une implication ¬ (P ⇒ Q) ⇔ ¬ ( ¬ P ∨ Q) ⇔ (P ∧
¬Q )
1.3.4. Connecteur « équivalent »
Si P ⇒ Q et Q ⇒ P, on dit que P est équivalente à Q et on note P ⇔ Q P ⇔ Q est vraie si et seulement si P et Q sont vraies ou fausses, simultanément. - P est vraie si et seulement si (ssi) Q est vraie - il faut et il suffit que Q soit vraie pour que P soit vraie - P est une condition nécessaire et suffisante (CNS) pour que Q soit vraie P ⇒ Q et Q ⇒ P est équivalent à P ⇔ Q
P V V F F
Q V F V F
P ⇒ Q V F V V
Q ⇒ P V V F V
P ⇔ Q V F F V
Exemple : P ⇔ P est toujours vraie.
1.3.5. Théorème
On appelle théorème une proposition logique toujours vraie.
1.3.6. Propriétés
Négation ¬(¬ P) ⇔ P ¬ ( P ∨ Q) ⇔ ( ¬ P ∧ ¬ Q) ¬ ( P ∧ Q) ⇔ ( ¬ P ∨ ¬ Q) Associativité ( P ∨ Q) ∨ R ⇔ (P ∨ (Q ∨ R)) ( P ∧ Q) ∧ R ⇔ (P ∧ (Q ∧ R)) non (non P) ⇔ P non (P ou Q) ⇔ (non P et non Q) non ( P et Q) ⇔ (non P ou non Q) (P ou Q) ou R ⇔ (P ou (Q ou R) (P et Q) et R ⇔ (P et (Q et R)
Cours 1 AC
3/7
A 2008
MT18
Distributivité ( P ∨ Q) ∧ R ⇔ (P ∧ R) ∨ (Q ∧ R) ( P ∧ Q) ∨ R ⇔ (P ∨ R) ∧ (Q ∨ R) Transitivité ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R) (P ou Q) et R ⇔ (P et R) ou (Q et R) (P et Q) ou R ⇔ (P ou R) et (Q ou R) (P ⇒ Q) et (Q ⇒ R) ⇒ (P ⇒ R)
2. Quantificateurs 2.1. Deux quantificateurs
Une proposition logique peut dépendre d’une variable appartenant à un ensemble donné.
⇒ x3 + 1 > 1 signifie « pour tout x ∈ * , on a x 3 + 1 > 1 ». + On introduit le quantificateur ∀ qui signifie « pour tout » ou « quel que soit ». * 3 L’exemple précédent devient : ∀ x ∈ + ⇒ x + 1 > 1
* +
Par exemple, x ∈
A l’inverse, une proposition peut être vraie que pour certains éléments d’un ensemble. On introduit le quantificateur ∃ qui signifie « il existe ». Le symbole / signifie « tel que ». / se place après ∃ . S’il y a plusieurs ∃ dans une proposition, / se place après le dernier ∃ . Remarque : ∃! signifie « il existe un unique élément » Exemples :
∃x ∈ / 3x + 2 > 1 signifie « il existe au moins un réel tel 3x+2 > 1 » x=0 ∀x ∈ / 3x + 2 > 1 signifie « tous les réels vérifient 3x+2 > 1 » x = – 1
Vrai Faux
2.2. Négation d’une phrase quantifiée
La négation de ∀ est ∃ La négation de ∃ est ∀
¬ ( ∀ x, P(x) ) ⇔ ( ∃ x / ¬ P(x) ) ¬ ( ∃ x, P(x) ) ⇔ ( ∀ x / ¬ P(x) )
2.3. Propriété
On ne peut pas modifier l’ordre des quantificateurs sans changer le sens de la proposition. Exemple : ∀x ∈ , ∃y ∈ / x ≤ y signifie « tout entier est majoré par un autre entier » VRAI car ℕ est infini.
On modifie l’ordre des quantificateurs : ∃y ∈ / ∀x ∈ les autres » FAUX (il n’y a pas de borne supérieure).
, x ≤ y signifie « il existe un entier supérieur ou égal à tous
2.4. Exemples
Les propositions suivantes sont-elles vraies ? Quelle est la négation de celles qui sont fausses ? a) ∀x ∈ , x ≥ 1 b)
∃x ∈ / x ∈ * c) ∀x ∈ + , ln( x) = 1 d) ∀x ∈ , ∃n ∈ / n ≤ x < n + 1 e) ∃n ∈ / ∀x ∈ , n ≤ x < n + 1
3. Théorie des ensembles 3.1. Définitions
Un ensemble est une collection d’objets qui présentent une ou plusieurs propriétés communes. Exemple : l’ensemble des étudiants de MT18. est l’ensemble des nombres rationnels. Les éléments d’un ensemble sont écrits entre accolades, les uns derrière les autres séparés par des virgules. Ensemble des nombres pairs {0 , 2 , 4 , … } Soient E, A des ensembles
Cours 1 AC
4/7
A 2008
x ∈ A signifie « x est un élément de A » ou « x appartient à A ». On désigne par ∅ l’ensemble vide qui n’a aucun élément. DESSIN
Si A est fini le cardinal de A, Card(A) ou Exemple : A = { 1, 2, 5, 10} Card (A) = 4 E = { n ∈ N ⇔ n² < 0 } donc E = ∅ #A, désigne le nombre d’éléments de A.
MT18
3.2. Inclusion
Définition : On dit que A est inclus dans B, noté A ⊂ B si la proposition suivante est vraie : ( x∈ A ) ⇒ ( x ∈ B ) A est alors un sous ensemble ou une partie de B. DESSIN On dit que A = B ssi A ⊂ B et B ⊂ A Exemple :
⊂
⊂
⊂
⊂
3.3. Opération sur les ensembles 3.3.1. Réunion
Définition : Soient A et B deux ensembles. La réunion de A et B, noté A ∪ B, est l’ensemble des éléments appartenant à A ou à B : ( x ∈ A ∪ B) ⇔ ( x ∈ A) ou ( x ∈ B) Exemple : DESSIN
=
∪ {− n, n ∈ }
3.3.2. Intersection
Définition : Soient A et B deux ensembles. L’intersection de A et B, noté A ∩ B, est l’ensemble des éléments appartenant à A et à B : ( x ∈ A ∩ B) ⇔ ( x ∈ A) et ( x ∈ B) Exemple :
∩ =
+
∩ =
∩{x ∈ / Im(x) ≠ 0} =∅
DESSIN
3.3.3. Complémentaire
Définition : Soient A et E deux ensembles avec A ⊂ E. Le complémentaire de A dans E, noté
E
A ou A ou
c
A ( s’il n’y a pas de risque de confusion au niveau de l’ensemble E), est l’ensemble des éléments de E n’appartenant pas à A :
( x∈
E
A ) ⇔ ( x ∈ E) et ( x ∉ A)
Cours 1 AC
5/7
...