Fiche de révision : Raisonnement logique et ensembles

📋 Plan du Cours

1. Propositions et connecteurs logiques
2. Équivalences logiques et lois
3. Méthodes de démonstration
4. Quantificateurs et contre-exemples
5. Analyse-synthèse et récurrence
6. Appartenance et construction des ensembles
7. Inclusion et opérations ensemblistes
8. Produits et parties d’un ensemble
9. Partitions d’un ensemble

📖 1. Propositions et connecteurs logiques

🔑 Notions clés & Définitions

• Proposition : Assertion qui est vraie ou fausse, mais jamais les deux simultanément.
• Négation : Proposition vraie lorsque p est fausse et fausse lorsque p est vraie.
• Conjonction : Proposition vraie lorsque p et q sont toutes deux vraies, et fausse dans les autres cas.
• Disjonction : Proposition fausse lorsque p et q sont toutes deux fausses, et vraie dans les autres cas.
• Implication : Proposition fausse lorsque p est vraie et q est fausse, et vraie dans les autres cas.
• Équivalence : Proposition vraie lorsque p et q ont la même valeur de vérité, et fausse sinon.

📝 Points essentiels

📌 Dans l’implication p → q, p est l’hypothèse et q est la conclusion ; p est une condition suffisante pour q, et q une condition nécessaire pour p.

📌 La réciproque de p → q est q → p, tandis que sa contraposée est ¬q → ¬p.

💡 Astuce mémo

L’implication échoue seulement pour V → F, contrairement à la conjonction, vraie seulement pour V ∧ V.

📖 2. Équivalences logiques et lois

🔑 Notions clés & Définitions

• Tautologie : Proposition toujours vraie, quelles que soient les valeurs de vérité de ses variables.
• Contradiction : Proposition toujours fausse, quelles que soient les valeurs de vérité de ses variables.
• Équivalence logique : Deux propositions composées P et Q sont logiquement équivalentes, noté P ≡ Q, lorsqu’elles ont la même table de vérité.

★ À maîtriser

📌 Les lois de De Morgan donnent ¬(p ∧ q) ≡ ¬p ∨ ¬q et ¬(p ∨ q) ≡ ¬p ∧ ¬q.

📌 Une implication p → q est logiquement équivalente à ¬p ∨ q et à sa contraposée ¬q → ¬p.

Compléments

📌 L’équivalence p ↔ q a la même table de vérité que la conjonction (p → q) ∧ (q → p).

📌 Une proposition P est une tautologie si et seulement si sa négation ¬P est une contradiction.

📖 3. Méthodes de démonstration

★ À maîtriser

• Pour prouver directement p ⇒ q, on suppose p vraie puis on démontre que q est vraie.

• Pour prouver p ⇒ q par contraposition, on suppose ¬q vraie et on démontre ¬p.

• Pour prouver une assertion p par l’absurde, on suppose ¬p et on en déduit une contradiction, par exemple une proposition de la forme q ∧ ¬q.

Compléments

• Une preuve par disjonction des cas établit une propriété en séparant le raisonnement suivant les valeurs possibles de la variable.

💡 Astuce mémo

Directe : p vers q ; contraposition : non-q vers non-p ; absurde : supposer p et non-q.

📖 4. Quantificateurs et contre-exemples

🔑 Notions clés & Définitions

• Assertion universelle : Assertion vraie si P(x) est satisfaite par tout élément de E, et fausse si au moins un élément ne la satisfait pas.
• Assertion existentielle : Assertion vraie si P(x) est satisfaite par au moins un élément de E, et fausse si aucun élément ne la satisfait.
• Contre-exemple : Un contre-exemple est un élément x d’un ensemble E pour lequel P(x) n’est pas satisfaite ; il suffit à montrer que ∀x ∈ E, P(x) est fausse.

★ À maîtriser

📌 La négation de ∀x ∈ E, P(x) est équivalente à ∃x ∈ E, ¬P(x), et la négation de ∃x ∈ E, P(x) est équivalente à ∀x ∈ E, ¬P(x).

Compléments

• La variable affectée par un quantificateur est muette et peut être remplacée par une autre lettre sans signification déjà attribuée.

📌 Les assertions ∀x ∈ ∅, P(x) sont vraies, tandis que les assertions ∃x ∈ ∅, P(x) sont fausses.

💡 Astuce mémo

Pour réfuter un « pour tout », un contre-exemple suffit ; pour établir un « il existe », un témoin suffit.

📖 5. Analyse-synthèse et récurrence

★ À maîtriser

• Le raisonnement par analyse-synthèse démontre l’existence et l’unicité d’un objet en établissant d’abord les conditions nécessaires qu’il doit vérifier, puis en vérifiant qu’un objet déterminé satisfait les propriétés voulues.

• Pour démontrer ∀n ∈ ℕ, P(n) par récurrence simple, on vérifie P(0), puis on démontre que P(n) entraîne P(n + 1) pour tout n ∈ ℕ.

• La récurrence forte démontre P(n + 1) à partir de la vérification de tous les cas P(k) pour k ≤ n, après une initialisation.

Compléments

• Pour établir par récurrence forte une propriété pour tout n ≥ b, l’initialisation peut porter sur P(b), P(b + 1), …, P(b + j), puis l’hérédité traite les n ≥ b + j.

📖 6. Appartenance et construction des ensembles

🔑 Notions clés & Définitions

• Ensemble : Collection d’objets appelés ses éléments.

★ À maîtriser

• La relation d’appartenance relie un objet à un ensemble et se note e ∈ E lorsque e appartient à E, ou e ∉ E lorsqu’il n’y appartient pas.

📌 Un ensemble peut être décrit en extension en énumérant ses éléments, ou en compréhension en indiquant une propriété vérifiée par ses éléments.

Compléments

• Dans un ensemble donné en extension, l’ordre des éléments et leurs répétitions ne changent pas l’ensemble.

• Le paradoxe de Russell montre qu’on ne peut pas former l’ensemble de tous les ensembles x tels que x ∉ x.

📌 Le schéma de séparation affirme que, pour tout ensemble A et toute propriété P, les éléments de A qui vérifient P forment l’ensemble {a ∈ A : P(a)}.

📖 7. Inclusion et opérations ensemblistes

🔑 Notions clés & Définitions

• Inclusion : A est inclus dans B, noté A ⊆ B, si tout élément de A est un élément de B.
• Partie propre : Partie de E distincte de E.
• Ensemble vide : Unique ensemble qui ne possède aucun élément.
• Disjonction : Deux ensembles E et F sont disjoints lorsque E ∩ F = ∅.

📝 Points essentiels

📌 L’inclusion est réflexive, antisymétrique et transitive : A ⊆ A ; si A ⊆ B et B ⊆ A, alors A = B ; si A ⊆ B et B ⊆ C, alors A ⊆ C.

💡 Astuce mémo

L’intersection garde les éléments communs ; la réunion garde ceux de l’un ou l’autre ensemble.

📖 8. Produits et parties d’un ensemble

🔑 Notions clés & Définitions

• Produit cartésien : Ensemble des couples (a, b) tels que a ∈ A et b ∈ B.
• Ensemble des parties : Ensemble dont les éléments sont exactement les parties de E.

★ À maîtriser

📌 Pour des ensembles finis A et B, le cardinal de leur produit cartésien vérifie $|A × B| = |A| × |B|$.

📌 Si E est un ensemble fini de cardinal n, alors le cardinal de son ensemble des parties est $|P(E)| = 2^n$.

Compléments

📌 Pour tout ensemble E, E × ∅ = ∅ × E = ∅ ; si E et F sont non vides, alors E × F n’est pas vide.

• Pour tout ensemble E, l’ensemble vide ∅ et E lui-même appartiennent à P(E).

📖 9. Partitions d’un ensemble

🔑 Notions clés & Définitions

• Complémentaire : Ensemble des x ∈ E tels que x ∉ A.
• Intersection : Ensemble des éléments qui appartiennent à la fois à A et à B.
• Réunion : Ensemble des éléments qui appartiennent à A ou à B.
• Différence ensembliste : Ensemble des éléments qui appartiennent à A et n’appartiennent pas à B.
• Différence symétrique : Union de A \ B et de B \ A.

★ À maîtriser

📌 Les lois de De Morgan pour les parties de E sont A ∪ B = A ∩ B et A ∩ B = A ∪ B, où les barres désignent les complémentaires dans E.

Compléments

📌 L’intersection et la réunion sont commutatives, associatives et distributives l’une par rapport à l’autre.

📌 Pour toute partie A d’un ensemble E, le complémentaire de A dans E est égal à E \ A.

💡 Astuce mémo

Visualiser une partition comme un ensemble découpé en blocs non vides, disjoints et couvrant tout l’ensemble.