Théorie des ensembles

Question 1

Def: Prédicat

Answer 1

Expression impliquant des variables libres

Question 2

Déf: Variable libre

Answer 2

Variable pour laquelle on ne connaît pas de valeur

Question 3

Expression booléenne atomique

Answer 3

Expression de type verbe sujet complément qui ne peut pas être subdivisée en d’autres expressions booléennes.

Question 4

Contraposition de (p => q)

Answer 4

(¬q => ¬p)

Question 5

Définition de l’implication (p => q)

Answer 5

¬p ∨ q

Question 6

Satisfiabilité : Une instance du problème SAT consiste..

Answer 6

..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.

Question 7

Une instance est insatifiable..

Answer 7

..lorsqu’aucune assignation assignation de variables ne permet à son expression booléenne d’être vraie.

Question 8

Déf : Forme normale conjonctive

Answer 8

est une conjonction de clauses (ensemble de clauses associées par des ET)

Question 9

Déf : Littéral

Answer 9

désigne une variable booléenne ou la négation d’une variable booléenne.

Question 10

Déf : Clause

Answer 10

est une disjonction (OU) de littéraux

Question 11

Déf : Ensemble

Answer 11

Collection d’éléments non ordonnée et sans répétition. (si il y a des répétitions on les ignore)

Question 12

Lorsqu’on définit un ensemble en listant tous ces éléments on le définit par…

Answer 12

extension

Question 13

S:= { f(x) | R(x) } se lit …

Answer 13

S est l’ensemble des f(x) TELS QUE R(x).

Question 14

Cardinalité d’un ensemble, noté |S|

Answer 14

est le nombre d’éléments de l’ensemble S

Question 15

(∀x ∈ T | P(x)) est la version abrégée de

Answer 15

(∀x | x ∈ T => P(x))

Question 16

Le quantificateur universel s’écrit …

Answer 16

∀

Question 17

Le quantificateur existentiel s’écrit …

Answer 17

∃

Question 18

(∃x ∈ T | P(x)) est la version abrégée de

Answer 18

(∃x | x ∈ T ∧ P(x))

Question 19

Loi de De Morgan généralisées aux quantificateurs

¬(∀x ∈ T | P(x)) <=> …

Answer 19

(∃x ∈ T | ¬P(x))

Question 20

Loi de De Morgan généralisées aux quantificateurs

¬(∃x ∈ T | P(x)) <=> …

Answer 20

(∀x ∈ T | ¬P(x))

Question 21

Def : T ⊆ S

Answer 21

( ∀e | e ∈ T => e ∈ S )

Question 22

Def : T ⊂ S

Answer 22

T ⊆ S ∧ (∃e ∈ S ∧ e ∉ T)

Question 23

T ⊈ S

Answer 23

¬(T ⊆ S)

Question 24

T ⊄ S

Answer 24

¬(T ⊂ S)

Question 25

Inclusion : Particularité de Ø

Answer 25

Ø est inclus dans tous les ensembles, car dans | ( ∀e | e ∈ Ø => e ∈ S ), e ∈ Ø est faux donc l'implication est vraie.

Question 26

Ensemble puissance de l'ensemble S : 𝒫(S)

Answer 26

{ E | E ⊆ S } contient tous les sous-ensembles possibles de S

Question 27

Particularité de 𝒫(Ø)

Answer 27

n'est pas Ø, c'est un ensemble qui contient Ø comme unique élément. Donc |𝒫(Ø)| = 1

Question 28

Priorités des opérateurs ensemblistes (priorité élevée en haut)

Answer 28

``` c \ ∩ ∪ ⊆ ⊂ ∈ = Opérateurs booléens ```

Question 29

Ensemble : | 1ere Loi de De Morgan ( S ∩ T ) ᶜ

Answer 29

Sᶜ ∪ Tᶜ

Question 30

Ensemble : | 2e Loi de De Morgan ( S ∪ T )ᶜ

Answer 30

Sᶜ ∩ Tᶜ

Question 31

(Sᶜ)ᶜ =

Answer 31

S

Question 32

S ∪ Sᶜ =

Answer 32

U

Question 33

S ∩ Sᶜ =

Answer 33

Ø

Question 34

S \ Ø =

Answer 34

S

Question 35

S \ T =

Answer 35

S ∩ Tᶜ

Question 36

Antisémétrie : S = T <=>

Answer 36

S ⊆ T ∧ T ⊆ S

Question 37

Réécriture de l'inclusion | S ⊆ T <=>

Answer 37

S ⊂ T ∨ S = T

Question 38

Réécriture de l'inclusion stricte | S ⊂ T <=>

Answer 38

S ⊆ T ∨ T ≠ S

Question 39

n-uplet

Answer 39

liste ordonnée de n éléments

Question 40

Produit cartésien

Answer 40

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.

Question 41

Sⁿ

Answer 41

Produit cartésien de S, n fois

Question 42

Def: Relation

Answer 42

- Associe des éléments de 2 ensembles. | - Sous ensemble d'un produit cartésien de ces 2 ensembles.

Question 43

a 𝓡 b signifie

Answer 43

(a,b) ∈ 𝓡

Question 44

Def : Ensemble de départ

Answer 44

C'est S dans SxT

Question 45

Def : L'ensemble d'arrivée

Answer 45

C'est T dans SxT

Question 46

Def: Le domaine d'une relation

Answer 46

Ensemble des points de l'ensemble de départ impliqués dans la relation. Soit 𝓡 ⊆ S xT Dom(𝓡) = (a ∈ S | (∃b ∈ T | a 𝓡 b ) )

Question 47

Def: Image d'une relation

Answer 47

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 ) )

Question 48

Def: Composition de relation

Answer 48

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.

Question 49

Def: Relation Identité

Answer 49

Les éléments sont en relation avec eux mêmes. | {(s,s) ∈ S²}

Question 50

Def : Clôture d'une relation 𝓡+ = ... 𝓡* = ...

Answer 50

``` 𝓡+ = 𝓡¹ ∪ 𝓡² ∪ 𝓡³ ∪... 𝓡* = 𝓡⁰ ∪ 𝓡¹ ∪ 𝓡² ∪ 𝓡³ ∪... ```

Question 51

Def: 𝓡 est réflexif

Answer 51

(∀ a ∈ S | a 𝓡 a) ou encore 𝐈s ⊆ 𝓡 Tous les a ont une boucle vers eux mêmes.

Question 52

Def: 𝓡 est irréflexif

Answer 52

(∀ a ∈ S | ¬(a 𝓡 a)) ou encore 𝐈s ∩ 𝓡 = Ø Aucun a admet une boucle vers lui même.

Question 53

Def: 𝓡 est symétrique

Answer 53

(∀ 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.

Question 54

Def: 𝓡 est Asymétrique

Answer 54

(∀ 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.

Question 55

Def: 𝓡 est ANTIsymétrique

Answer 55

(∀ 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!

Question 56

Def: 𝓡 est transitif

Answer 56

(∀ a ∈ S, b ∈ S, c ∈ S | a 𝓡 b ∧ b 𝓡 c => a 𝓡 c ) ou encore 𝓡² ⊆ 𝓡

Question 57

Particularité de |ℕ|

Answer 57

|ℕ| est la plus petite cardinalité infinie. T.1.5.11. Soit A un ensemble infini, alors |A| >= |ℕ|

Question 58

{0, 1}^ℕ est-il dénombrable ?

Answer 58

Corollaire 1.6.3. {0, 1}^ℕ est un ensemble non dénombrable. Car |{0, 1}^ℕ| > |ℕ|

Question 59

Pour tout ensemble A, | |P(A)| ? |A|

Answer 59

|P(A)| > |A| (T. Cantor)

Question 60

|{0, 1}^ℕ| ? |P(ℕ)|

Answer 60

|{0, 1}^ℕ| = |P(ℕ)| | Proposition 1.6.2

Question 61

Si |A| ≤ |N| on peut conplure

Answer 61

que A est dénombrable

Question 62

Si |A| > |N| on peut conclure

Answer 62

que A est NON dénombrable

Question 63

[Dénombralité] Soit A et B, deux ensembles dénombrables (finis ou infinis) A U B est ... A x B est ...

Answer 63

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.

Question 64

Propriétés des relations d’équivalence

Answer 64

- Transitivité - Réflexivité - Symétrie

Question 65

Propriétés des ordres partiels

Answer 65

- Transitivité - Réflexivité - AntiSymétrie

Question 66

Propriétés des ordres partiels stricts

Answer 66

- Transitivité - Irréflexivité - ASymétrie