Théorie des ensembles Flashcards
Def: Prédicat
Expression impliquant des variables libres
Déf: Variable libre
Variable pour laquelle on ne connaît pas de valeur
Expression booléenne atomique
Expression de type verbe sujet complément qui ne peut pas être subdivisée en d’autres expressions booléennes.
Contraposition de (p => q)
(¬q => ¬p)
Définition de l’implication (p => q)
¬p ∨ q
Satisfiabilité : Une instance du problème SAT consiste..
..en une équation booléenne contenant des
variables libres. Une telle instance est dite satisfiable lorsqu’il existe une assignation de variables telle que l’équation est évaluée à vrai.
Une instance est insatifiable..
..lorsqu’aucune assignation assignation de variables ne permet à son expression booléenne d’être vraie.
Déf : Forme normale conjonctive
est une conjonction de clauses (ensemble de clauses associées par des ET)
Déf : Littéral
désigne une variable booléenne ou la négation d’une variable booléenne.
Déf : Clause
est une disjonction (OU) de littéraux
Déf : Ensemble
Collection d’éléments non ordonnée et sans répétition. (si il y a des répétitions on les ignore)
Lorsqu’on définit un ensemble en listant tous ces éléments on le définit par…
extension
S:= { f(x) | R(x) } se lit …
S est l’ensemble des f(x) TELS QUE R(x).
Cardinalité d’un ensemble, noté |S|
est le nombre d’éléments de l’ensemble S
(∀x ∈ T | P(x)) est la version abrégée de
(∀x | x ∈ T => P(x))
Le quantificateur universel s’écrit …
∀
Le quantificateur existentiel s’écrit …
∃
(∃x ∈ T | P(x)) est la version abrégée de
(∃x | x ∈ T ∧ P(x))
Loi de De Morgan généralisées aux quantificateurs
¬(∀x ∈ T | P(x)) <=> …
(∃x ∈ T | ¬P(x))
Loi de De Morgan généralisées aux quantificateurs
¬(∃x ∈ T | P(x)) <=> …
(∀x ∈ T | ¬P(x))
Def : T ⊆ S
( ∀e | e ∈ T => e ∈ S )
Def : T ⊂ S
T ⊆ S ∧ (∃e ∈ S ∧ e ∉ T)
T ⊈ S
¬(T ⊆ S)
T ⊄ S
¬(T ⊂ S)
Inclusion : Particularité de Ø
Ø est inclus dans tous les ensembles, car dans
( ∀e | e ∈ Ø => e ∈ S ), e ∈ Ø est faux donc l’implication est vraie.
Ensemble puissance de l’ensemble S : 𝒫(S)
{ E | E ⊆ S }
contient tous les sous-ensembles possibles de S
Particularité de 𝒫(Ø)
n’est pas Ø, c’est un ensemble qui contient Ø comme unique élément. Donc |𝒫(Ø)| = 1
Priorités des opérateurs ensemblistes (priorité élevée en haut)
c \ ∩ ∪ ⊆ ⊂ ∈ = Opérateurs booléens
Ensemble :
1ere Loi de De Morgan ( S ∩ T ) ᶜ
Sᶜ ∪ Tᶜ
Ensemble :
2e Loi de De Morgan ( S ∪ T )ᶜ
Sᶜ ∩ Tᶜ
(Sᶜ)ᶜ =
S
S ∪ Sᶜ =
U
S ∩ Sᶜ =
Ø
S \ Ø =
S
S \ T =
S ∩ Tᶜ
Antisémétrie : S = T <=>
S ⊆ T ∧ T ⊆ S
Réécriture de l’inclusion
S ⊆ T <=>
S ⊂ T ∨ S = T
Réécriture de l’inclusion stricte
S ⊂ T <=>
S ⊆ T ∨ T ≠ S
n-uplet
liste ordonnée de n éléments
Produit cartésien
S x T = {(a;b) | a ∈ S ∧ b ∈ T}
C’est à dire toutes les paires possibles entre les éléments de S et de T.
Sⁿ
Produit cartésien de S, n fois
Def: Relation
- Associe des éléments de 2 ensembles.
- Sous ensemble d’un produit cartésien de ces 2 ensembles.
a 𝓡 b signifie
(a,b) ∈ 𝓡
Def : Ensemble de départ
C’est S dans SxT
Def : L’ensemble d’arrivée
C’est T dans SxT
Def: Le domaine d’une relation
Ensemble des points de l’ensemble de départ impliqués dans la relation.
Soit 𝓡 ⊆ S xT
Dom(𝓡) = (a ∈ S | (∃b ∈ T | a 𝓡 b ) )
Def: Image d’une relation
Ensemble des points de l’ensemble d’arrivée impliqués dans la relation.
Soit 𝓡 ⊆ S x T
Im(𝓡) = (b ∈ T | (∃a ∈ S | a 𝓡 b ) )
Def: Composition de relation
Soit S, T et U trois ensembles et 𝓡 ⊆ S x T et L ⊆ T x U de relations binaires.
𝓡 o L = { (a,c) ∈ SxU | (∃b ∈ T | (a,b) ∈ 𝓡 ∧ (b,c) ∈ L)}
JPM : Une Jointure en fait.
Def: Relation Identité
Les éléments sont en relation avec eux mêmes.
{(s,s) ∈ S²}
Def : Clôture d’une relation
𝓡+ = …
𝓡* = …
𝓡+ = 𝓡¹ ∪ 𝓡² ∪ 𝓡³ ∪... 𝓡* = 𝓡⁰ ∪ 𝓡¹ ∪ 𝓡² ∪ 𝓡³ ∪...
Def: 𝓡 est réflexif
(∀ a ∈ S | a 𝓡 a)
ou encore
𝐈s ⊆ 𝓡
Tous les a ont une boucle vers eux mêmes.
Def: 𝓡 est irréflexif
(∀ a ∈ S | ¬(a 𝓡 a))
ou encore
𝐈s ∩ 𝓡 = Ø
Aucun a admet une boucle vers lui même.
Def: 𝓡 est symétrique
(∀ a ∈ S, b ∈ S | a 𝓡 b => b 𝓡 a )
ou encore
𝓡⁻¹ = 𝓡
Pour chaque relations “aller” a vers b, il y a aussi un “retour” b vers a.
Def: 𝓡 est Asymétrique
(∀ a ∈ S, b ∈ S | a 𝓡 b => ¬(b 𝓡 a) )
ou encore
𝓡⁻¹ ∩ 𝓡 = Ø
Pour chaque relation “aller” a vers b, il y a JAMAIS un “retour” b vers a. Et même pas de boucle d’un élément vers lui même.
Def: 𝓡 est ANTIsymétrique
(∀ a ∈ S, b ∈ S | a 𝓡 b ∧ b 𝓡 a => a = b )
ou encore
𝓡⁻¹ ∩ 𝓡 ⊆ 𝐈s
Asymtrique mais qui admet les relation d’éléments avec eux mêmes (boucle).
Autrement dit : Le seul moyen pour que 2 éléments aient une relation symétrique c’est qu’ils soient le même élément!
Def: 𝓡 est transitif
(∀ a ∈ S, b ∈ S, c ∈ S | a 𝓡 b ∧ b 𝓡 c => a 𝓡 c )
ou encore
𝓡² ⊆ 𝓡
Particularité de |ℕ|
|ℕ| est la plus petite cardinalité infinie.
T.1.5.11. Soit A un ensemble infini, alors |A| >= |ℕ|
{0, 1}^ℕ est-il dénombrable ?
Corollaire 1.6.3.
{0, 1}^ℕ est un ensemble non dénombrable.
Car |{0, 1}^ℕ| > |ℕ|
Pour tout ensemble A,
|P(A)| ? |A|
|P(A)| > |A| (T. Cantor)
|{0, 1}^ℕ| ? |P(ℕ)|
|{0, 1}^ℕ| = |P(ℕ)|
Proposition 1.6.2
Si |A| ≤ |N| on peut conplure
que A est dénombrable
Si |A| > |N| on peut conclure
que A est NON dénombrable
[Dénombralité]
Soit A et B, deux ensembles dénombrables (finis ou infinis)
A U B est …
A x B est …
A ∪ B est dénombrable,
A × B est dénombrable.
De plus,
L’union d’un nombre dénombrable d’ensembles dénombrables est dénombrable.
Propriétés des relations d’équivalence
- Transitivité
- Réflexivité
- Symétrie
Propriétés des ordres partiels
- Transitivité
- Réflexivité
- AntiSymétrie
Propriétés des ordres partiels stricts
- Transitivité
- Irréflexivité
- ASymétrie
