Théorie Des Ensembles

si 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