Fiche de révision : Raisonnement et ensembles

📋 Plan du Cours

1. Propositions et valeurs de vérité
2. Connecteurs et tables de vérité
3. Équivalences et lois logiques
4. Méthodes de démonstration
5. Quantificateurs et contre-exemples
6. Notion et construction des ensembles
7. Inclusion et opérations ensemblistes
8. Partitions et produits d’ensembles

📖 1. Propositions et valeurs de vérité

🔑 Notions clés & Définitions

• Proposition : Phrase qui est vraie ou fausse, l’un des deux mais pas les deux simultanément.

★ À maîtriser

• La valeur de vérité d’une proposition vraie est V et celle d’une proposition fausse est F.

Compléments

• Les assertions « Paris est la capitale de la France » et « 1 + 2 = 3 » sont vraies, tandis que « 2 > 4 » est fausse.

💡 Astuce mémo

V s’oppose à F : une proposition est vraie ou fausse, jamais les deux

📖 2. Connecteurs et tables de vérité

🔑 Notions clés & Définitions

• Négation : Est vraie lorsque p est fausse et fausse lorsque p est vraie.
• Conjonction : Est vraie lorsque p et q sont toutes les deux vraies et fausse dans tous les autres cas.
• Disjonction : Est fausse lorsque p et q sont toutes les deux fausses et vraie dans tous les autres cas.
• Implication : Est fausse lorsque p est vraie et q est fausse, et vraie dans tous les autres cas.
• Équivalence : Est vraie lorsque p et q ont la même valeur de vérité et fausse sinon.

💡 Astuce mémo

¬ transforme, ∧ réunit, ∨ élargit, → conditionne, ↔ équilibre

📖 3. Équivalences et lois logiques

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

★ À maîtriser

📌 Deux propositions composées P et Q sont logiquement équivalentes, notées P ≡ Q, lorsqu’elles ont la même table de vérité.

📐 Formule — Les lois de De Morgan donnent $\neg(p \land q) \equiv \neg p \lor \neg q$ et $\neg(p \lor q) \equiv \neg p \land \neg q$.

Compléments

📐 Formule — L’implication vérifie $p \to q \equiv \neg q \to \neg p$ et $p \to q \equiv \neg p \lor q$.

💡 Astuce mémo

Même table de vérité → équivalence logique

📖 4. Méthodes de démonstration

★ À maîtriser

• Pour réaliser une preuve directe de p ⇒ q, on suppose p vraie et on 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 vraie et on montre que cette hypothèse conduit à une contradiction.

• L’analyse-synthèse démontre l’existence et l’unicité d’un objet en déduisant d’abord les conditions nécessaires, puis en vérifiant que l’objet obtenu possède les propriétés voulues.

Compléments

• La preuve par disjonction des cas démontre une propriété en séparant le raisonnement suivant toutes les valeurs possibles de la variable.

💡 Astuce mémo

Directe, contraposée, absurde, cas par cas, analyse-synthèse

📖 5. Quantificateurs et contre-exemples

🔑 Notions clés & Définitions

• Quantificateur universel : Le quantificateur ∀ se lit « pour tout » et l’assertion ∀x ∈ E, P(x) est vraie lorsque P(x) est satisfaite par tout élément de E.
• Quantificateur existentiel : Le quantificateur ∃ se lit « il existe » et l’assertion ∃x ∈ E, P(x) est vraie lorsque P(x) est satisfaite par au moins un élément de E.

★ À maîtriser

📐 Formule — Les négations des quantificateurs vérifient $\neg(\forall x \in E, P(x)) \equiv \exists x \in E, \neg P(x)$ et $\neg(\exists x \in E, P(x)) \equiv \forall x \in E, \neg P(x)$.

📌 Pour montrer qu’une assertion universelle est fausse, il suffit de trouver un élément de E qui ne satisfait pas la propriété, appelé contre-exemple.

Compléments

• Toute assertion universelle ∀x ∈ ∅, P(x) est vraie, tandis que toute assertion existentielle ∃x ∈ ∅, P(x) est fausse.

💡 Astuce mémo

Universel : un contre-exemple suffit ; existentiel : un exemple suffit

📖 6. Notion et construction des ensembles

🔑 Notions clés & Définitions

• Ensemble : G. Cantor, 1845-1918 — Collection d’objets appelés ses éléments, et l’appartenance d’un objet e à un ensemble E se note e ∈ E.

★ À maîtriser

📌 L’écriture en extension décrit un ensemble en listant ses éléments entre accolades, tandis que l’écriture en compréhension le décrit par une propriété sous la forme F = {x ∈ E : P(x)}.

📌 Dans un ensemble, l’ordre des éléments et leurs répétitions ne comptent pas, ainsi {1, 3, 5} = {3, 1, 5} = {1, 3, 1, 5, 5}.

Compléments

• Le schéma de séparation forme, à partir d’un ensemble A et d’une propriété P, l’ensemble {a ∈ A : P(a)}.

💡 Astuce mémo

Extension : éléments listés ; compréhension : propriété vérifiée

📖 7. Inclusion et opérations ensemblistes

🔑 Notions clés & Définitions

• Inclusion : Lorsque tout élément de A est un élément de B.
• Opérations ensemblistes : Pour des parties A et B de E, le complémentaire est C_E A = {x ∈ E : x ∉ A}, l’intersection est A ∩ B = {x ∈ E : x ∈ A et x ∈ B}, la réunion est A ∪ B = {x ∈ E : x ∈ A ou x ∈ B}, la différence est A \ B = {x ∈ E : x ∈ A et x ∉ B}, et la différence symétrique est A Δ B = (A \ B) ∪ (B \ A).

★ À maîtriser

📌 L’inclusion est réflexive, antisymétrique et transitive : A ⊆ A, [(A ⊆ B) ∧ (B ⊆ A)] ⇒ A = B, et [(A ⊆ B) ∧ (B ⊆ C)] ⇒ A ⊆ C.

Compléments

📐 Formule — Les lois de De Morgan pour les ensembles sont $\overline{A \cup B}=\overline{A}\cap\overline{B}$ et $\overline{A \cap B}=\overline{A}\cup\overline{B}$.

💡 Astuce mémo

Complément, intersection, réunion, différence, différence symétrique

📖 8. Partitions et produits d’ensembles

🔑 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 toutes les parties de E.
• Partition : Une partition de E est une famille de parties non vides, deux à deux disjointes, dont la réunion couvre E.
• Ensembles disjoints : Deux ensembles E et F sont disjoints lorsque E ∩ F = ∅.

📝 Points essentiels

📐 Formule — Si A et B sont finis, le cardinal du produit cartésien vérifie $|A \times B|=|A|\times|B|$.

📐 Formule — Si E est un ensemble fini de cardinal n, alors le cardinal de son ensemble des parties vérifie $|P(E)|=2^n$.

📊 Tableaux de synthèse

Quantificateurs et réfutation