Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Mathématique Pour Informaticiens > Théorie des ensembles > Flashcards

Théorie des ensembles Flashcards

1
Q

Def: Prédicat

A

Expression impliquant des variables libres

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Déf: Variable libre

A

Variable pour laquelle on ne connaît pas de valeur

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Expression booléenne atomique

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Contraposition de (p => q)

A

(¬q => ¬p)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

¬p ∨ q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Une instance est insatifiable..

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Déf : Forme normale conjonctive

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Déf : Littéral

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Déf : Clause

A

est une disjonction (OU) de littéraux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Déf : Ensemble

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

extension

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Le quantificateur universel s’écrit …

A

∀

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Le quantificateur existentiel s’écrit …

A

∃

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Def : T ⊆ S

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Def : T ⊂ S

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

T ⊈ S

A

¬(T ⊆ S)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

T ⊄ S

A

¬(T ⊂ S)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Inclusion : Particularité de Ø

A

Ø est inclus dans tous les ensembles, car dans

( ∀e | e ∈ Ø => e ∈ S ), e ∈ Ø est faux donc l’implication est vraie.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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

A

{ E | E ⊆ S }

contient tous les sous-ensembles possibles de S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Particularité de 𝒫(Ø)

A

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

28
Q

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

A 
c
\
∩ ∪
⊆ ⊂
∈ =
Opérateurs booléens
29
Q

Ensemble :

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

A

Sᶜ ∪ Tᶜ

30
Q

Ensemble :

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

A

Sᶜ ∩ Tᶜ

31
Q

(Sᶜ)ᶜ =

A

S

32
Q

S ∪ Sᶜ =

A

U

33
Q

S ∩ Sᶜ =

A

Ø

34
Q

S \ Ø =

A

S

35
Q

S \ T =

A

S ∩ Tᶜ

36
Q

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

A

S ⊆ T ∧ T ⊆ S

37
Q

Réécriture de l’inclusion

S ⊆ T <=>

A

S ⊂ T ∨ S = T

38
Q

Réécriture de l’inclusion stricte

S ⊂ T <=>

A

S ⊆ T ∨ T ≠ S

39
Q

n-uplet

A

liste ordonnée de n éléments

40
Q

Produit cartésien

A

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.

41
Q

Sⁿ

A

Produit cartésien de S, n fois

42
Q

Def: Relation

A
  • Associe des éléments de 2 ensembles.

- Sous ensemble d’un produit cartésien de ces 2 ensembles.

43
Q

a 𝓡 b signifie

A

(a,b) ∈ 𝓡

44
Q

Def : Ensemble de départ

A

C’est S dans SxT

45
Q

Def : L’ensemble d’arrivée

A

C’est T dans SxT

46
Q

Def: Le domaine d’une relation

A

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

47
Q

Def: Image d’une relation

A

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

48
Q

Def: Composition de relation

A

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.

49
Q

Def: Relation Identité

A

Les éléments sont en relation avec eux mêmes.

{(s,s) ∈ S²}

50
Q

Def : Clôture d’une relation
𝓡+ = …
𝓡* = …

A 
𝓡+ = 𝓡¹ ∪  𝓡² ∪  𝓡³ ∪...
𝓡* = 𝓡⁰ ∪ 𝓡¹ ∪  𝓡² ∪  𝓡³ ∪...
51
Q

Def: 𝓡 est réflexif

A

(∀ a ∈ S | a 𝓡 a)

ou encore
𝐈s ⊆ 𝓡

Tous les a ont une boucle vers eux mêmes.

52
Q

Def: 𝓡 est irréflexif

A

(∀ a ∈ S | ¬(a 𝓡 a))

ou encore
𝐈s ∩ 𝓡 = Ø

Aucun a admet une boucle vers lui même.

53
Q

Def: 𝓡 est symétrique

A

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

54
Q

Def: 𝓡 est Asymétrique

A

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

55
Q

Def: 𝓡 est ANTIsymétrique

A

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

56
Q

Def: 𝓡 est transitif

A

(∀ a ∈ S, b ∈ S, c ∈ S | a 𝓡 b ∧ b 𝓡 c => a 𝓡 c )

ou encore

𝓡² ⊆ 𝓡

57
Q

Particularité de |ℕ|

A

|ℕ| est la plus petite cardinalité infinie.

T.1.5.11. Soit A un ensemble infini, alors |A| >= |ℕ|

58
Q

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

A

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

Car |{0, 1}^ℕ| > |ℕ|

59
Q

Pour tout ensemble A,

|P(A)| ? |A|

A

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

60
Q

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

A

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

Proposition 1.6.2

61
Q

Si |A| ≤ |N| on peut conplure

A

que A est dénombrable

62
Q

Si |A| > |N| on peut conclure

A

que A est NON dénombrable

63
Q

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

A U B est …
A x B est …

A

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.

64
Q

Propriétés des relations d’équivalence

A
  • Transitivité
  • Réflexivité
  • Symétrie
65
Q

Propriétés des ordres partiels

A
  • Transitivité
  • Réflexivité
  • AntiSymétrie
66
Q

Propriétés des ordres partiels stricts

A
  • Transitivité
  • Irréflexivité
  • ASymétrie

Mathématique Pour Informaticiens (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions