Logique et ensembles Flashcards
Quelle est la négation de P => Q
P et ¬Q
Quelle est la réciproque de P => Q
Q => P
Quelle est la contraposée de P => Q
¬Q => ¬P
Quel lien y a-t-il entre une implication et sa contraposée ?
Elles sont toujours équivalentes
(Faux => Faux) est …
Vrai
(Faux => Vrai) est …
Vrai
(Vrai => Faux) est …
Faux
P => Q équivaut à …
¬P v Q
P ^ (Q v R) = …
(P ^ Q) v (P ^ R)
[Distributivité de ^ sur v]
Quelles sont les dualités de De Morgan ?
- ¬(P ^ Q) = ¬P v ¬Q
- ¬(P v Q) = ¬P ^ ¬ Q
Comment définit-on un ensemble en compréhension ?
{x ∈ E | P(x)}
Comment définir un ensemble en extension ?
{x1, …, xn}
Quand dit-on que deux ensembles sont égaux ?
Quand E ⊂ F et F ⊂ E
Autrement dit, E et F ont les mêmes éléments
Que signifie l’ensemble des parties de E ?
C’est l’ensemble de tous les ensembles inclus dans E, noté 𝒫(E)
Donner l’ensemble des parties de {0, 1}
𝒫({0, 1}) = {∅, {0}, {1}, {0, 1}}
Quel est le nombre de parties d’un ensemble à n éléments ?
2n
Deux ensembles A et B sont disjoints si on a …
A ∩ B = ∅
Pour tout ensemble A,
A \ ∅ = …
A
Pour tout ensemble A,
A \ A = …
∅
Pour tout ensemble A,
∅ \ A = …
∅
Propriété différence ensembliste :
Pour tout ensemble A,
si b ∉ A, alors …
A \ {b} = A
Soit E un ensemble
cA = …
E \ A
Donner deux propriétés de l’union et l’inclusion
- A ⊂ A∪B
- B ⊂ A∪B
Donner deux propriétés de l’intersection et de l’inclusion
- A∩B ⊂ A
- A∩B ⊂ B
Donner deux propriétés de l’inclusion
- A ⊂ A
- Si A ⊂ B et B ⊂ C, alors A ⊂ C (Transitivité)
Définir le produit cartésien de deux ensembles E et F en compréhension
E × F = {(x, y) | x ∈ E et y ∈ F}
|E × F| = …
|E||F|
Définir en compréhension
𝒫k(E) = …
{A ∈ 𝒫(E) | |A| = k}
Comment calculer le cardinal de 𝒫k(E) avec les coefficient binomiaux ?
|𝒫k(E)| = binom(k, |E|)
Dénombrement binomial de k parmi |E|