Fiche de révision : Logique et théorie des ensembles

📋 Plan du Cours

1. Ensembles et opérations
2. Propositions et connecteurs logiques
3. Quantificateurs et ensembles définis
4. Méthodes de démonstration
5. Sommes, produits et factorielles
6. Cardinalités et dénombrement
7. Combinaisons et binôme

📖 1. Ensembles et opérations

🔑 Notions clés & Définitions

• Partie d’un ensemble : Ensemble dont tous les éléments appartiennent à E.
• Ensemble des parties : L’ensemble des parties de E, noté P(E), contient toutes les parties de E, tandis que ∅ désigne la partie vide de E.
• Opérations sur les parties : Pour des parties A et B de E, le complémentaire de A est $E\setminus A=\{x\in E\mid x\notin A\}$, la réunion est $A\cup B=\{x\in E\mid x\in A\ \text{ou}\ x\in B\}$, l’intersection est $A\cap B=\{x\in E\mid x\in A\ \text{et}\ x\in B\}$ et la différence est $A\setminus B=\{x\in E\mid x\in A\ \text{et}\ x\notin B\}$.
• Partition : Une famille (Aᵢ)ᵢ∈I de parties non vides de E est une partition de E si ses parties sont deux à deux disjointes et si leur réunion est E.
• Produit cartésien : Le produit cartésien E×F est l’ensemble de tous les couples (x,y) tels que x∈E et y∈F, et le couple (a,b) n’est pas l’ensemble {a,b}.

📝 Points essentiels

📌 Pour démontrer que deux parties A et B sont égales, il suffit de démontrer les deux inclusions A⊂B et B⊂A.

💡 Astuce mémo

∅ est vide, tandis que φ est la lettre grecque phi

📖 2. Propositions et connecteurs logiques

🔑 Notions clés & Définitions

• Proposition : Phrase mathématique dotée d’un sens qui est vraie ou fausse.
• Implication : L’implication A⇒B signifie que si A est vraie, alors B est vraie, et elle est équivalente à (non A) ou B.
• Équivalence : L’équivalence A⇔B est la conjonction des implications A⇒B et B⇒A ; elle signifie que A et B ont les mêmes valeurs de vérité.

★ À maîtriser

📌 Les lois de De Morgan donnent non(A ou B) équivalent à (non A) et (non B), ainsi que non(A et B) équivalent à (non A) ou (non B).

Compléments

📌 La contraposition remplace l’implication A⇒B par l’implication équivalente (non B)⇒(non A).

💡 Astuce mémo

A ⇒ B impose une condition, tandis que A ⇔ B impose deux implications

📖 3. Quantificateurs et ensembles définis

🔑 Notions clés & Définitions

• Quantificateurs : Le quantificateur ∃ signifie « il existe au moins un », ∃! signifie « il existe un unique », et ∀ signifie « quel que soit ».
• Ensemble défini par propriété : Ensemble des éléments x de E pour lesquels A(x) est vraie.

★ À maîtriser

📌 La négation de ∃x∈E, A(x) est ∀x∈E, non A(x), tandis que la négation de ∀x∈E, A(x) est ∃x∈E, non A(x).

📌 Les propositions ∃x∈E,∀y∈F,A(x,y) et ∀y∈F,∃x∈E,A(x,y) ne sont pas équivalentes.

Compléments

📌 Un objet affecté d’un quantificateur ∃ dépend de tous les objets affectés de quantificateurs ∀ qui le précèdent dans l’énoncé.

💡 Astuce mémo

∃ cherche un témoin, tandis que ∀ exige tous les cas

📖 4. Méthodes de démonstration

★ À maîtriser

• Pour démontrer une assertion A par l’absurde, on suppose A fausse et on cherche une contradiction.

• Pour démontrer A⇒B directement, on suppose A vraie et on démontre que B est vraie ; par contraposition, on démontre (non B)⇒(non A).

• Pour démontrer A⇔B, on démontre séparément les deux implications A⇒B et B⇒A.

• Pour démontrer ∀n∈N,A(n) par récurrence, on établit l’initialisation A(0), puis l’hérédité A(n)⇒A(n+1) pour tout n∈N.

Compléments

• La récurrence forte utilise l’implication [A(0) et A(1) et … et A(n)]⇒A(n+1), tandis que la récurrence à deux pas utilise [A(n) et A(n+1)]⇒A(n+2) avec A(0) et A(1) comme initialisation.

• Pour déterminer S={x∈E ; A(x)} par analyse-synthèse, on cherche d’abord une propriété plus simple B(x) nécessaire à A(x), puis on sélectionne parmi les solutions de B(x) celles qui vérifient A(x).

💡 Astuce mémo

Initialisation → hérédité → conclusion par récurrence

📖 5. Sommes, produits et factorielles

🔑 Notions clés & Définitions

• Factorielle : La factorielle vérifie 0!=1 et, pour n>0, $n!=\prod_{k=1}^{n}k$.

★ À maîtriser

📐 Formule — Pour une famille finie, $\sum_{k=1}^{n}a_k=a_1+a_2+\cdots+a_n$ et $\prod_{k=1}^{n}a_k=a_1\times a_2\times\cdots\times a_n$.

📐 Formule — Les sommes vérifient $\sum_{k=1}^{n}(a_k+b_k)=\sum_{k=1}^{n}a_k+\sum_{k=1}^{n}b_k$ et $\sum_{k=1}^{n}\lambda a_k=\lambda\sum_{k=1}^{n}a_k$.

Compléments

📐 Formule — Les produits vérifient $\prod_{k=1}^{n}(a_kb_k)=\left(\prod_{k=1}^{n}a_k\right)\left(\prod_{k=1}^{n}b_k\right)$ et $\prod_{k=1}^{n}(\lambda a_k)=\lambda^n\prod_{k=1}^{n}a_k$.

📖 6. Cardinalités et dénombrement

🔑 Notions clés & Définitions

• Cardinal : Nombre de ses éléments et appartient à N.

★ À maîtriser

📐 Formule — Pour des parties A et B d’un ensemble fini E, $Card(A\cup B)+Card(A\cap B)=Card(A)+Card(B)$.

📐 Formule — Pour des ensembles finis E et F, $Card(E\times F)=Card(E)\,Card(F)$ et $Card(P(E))=2^{Card(E)}$.

Compléments

📐 Formule — Pour des ensembles finis E et F, $Card(F(E,F))=Card(F)^{Card(E)}$ et $Card(S(E))=(Card(E))!$.

📌 Si A⊂B et B est fini, alors Card(A)=Card(B) si et seulement si A=B.

💡 Astuce mémo

Produit cartésien → multiplication des cardinalités ; parties → puissance de 2

📖 7. Combinaisons et binôme

🔑 Notions clés & Définitions

• p-combinaison : Partie de E qui possède p éléments.

★ À maîtriser

📐 Formule — Si Card(E)=n, le nombre de p-combinaisons est $\binom{n}{p}=\frac{n!}{p!(n-p)!}$ pour p∈⟦0,n⟧, et $\binom{n}{p}=0$ si p>n.

📐 Formule — Pour n≥1 et p∈⟦1,n⟧, les coefficients binomiaux vérifient $\binom{n}{p}=\binom{n-1}{p-1}+\binom{n-1}{p}$ et $\binom{n}{p}=\binom{n}{n-p}$.

📐 Formule — Pour tous a,b∈C et n∈N*, la formule du binôme de Newton est $\left(a+b\right)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k$.

Compléments

• Les coefficients binomiaux peuvent être obtenus à l’aide du triangle de Pascal, dont chaque terme intérieur est la somme des deux termes situés juste au-dessus.

💡 Astuce mémo

Pascal → coefficients binomiaux → binôme de Newton

📊 Tableaux de synthèse

Connecteurs logiques