Fiche de révision : Raisonnement et ensembles

📋 Plan du Cours

1. Propositions et valeurs de vérité
2. Connecteurs et équivalences logiques
3. Méthodes de preuve
4. Quantificateurs et preuves existentielles
5. Analyse-synthèse et récurrence
6. Notion et représentation des ensembles
7. Inclusion et constructions ensemblistes
8. Opérations et partitions

📖 1. Propositions et valeurs de vérité

🔑 Notions clés & Définitions

• Proposition : Phrase qui est vraie ou fausse, mais jamais les deux simultanément.

★ À maîtriser

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

Compléments

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

💡 Astuce mémo

Une proposition est soit vraie, soit fausse : V contre F.

📖 2. Connecteurs et équivalences logiques

🔑 Notions clés & Définitions

• Négation : Vraie lorsque p est fausse et fausse lorsque p est vraie.
• Conjonction : Vraie lorsque p et q sont toutes les deux vraies, et fausse dans tous les autres cas.
• Disjonction : Fausse lorsque p et q sont toutes les deux fausses, et vraie dans tous les autres cas.
• Implication : Fausse lorsque p est vraie et q est fausse, et vraie dans tous les autres cas.
• Équivalence : Vraie lorsque p et q ont la même valeur de vérité, et fausse sinon.
• 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 ayant la même table de vérité, ce qui se note P ≡ Q.

★ À maîtriser

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

• La contraposée de p → q est ¬q → ¬p et possède la même table de vérité que p → q.

📐 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 p \lor q$.

💡 Astuce mémo

L’implication échoue seulement quand p est vraie et q fausse ; l’équivalence exige la même valeur.

📖 3. Méthodes de preuve

★ À maîtriser

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

• Pour démontrer p ⇒ q par contraposition, on montre l’implication équivalente ¬q ⇒ ¬p en supposant ¬q vraie.

• Pour démontrer une assertion p par l’absurde, on suppose ¬p vraie et on montre que cette hypothèse entraîne une contradiction.

Compléments

• Pour démontrer une propriété dépendant de x par disjonction des cas, on sépare le raisonnement suivant toutes les valeurs possibles de x.

💡 Astuce mémo

Directe, contraposée, absurde, cas : quatre chemins pour établir une implication.

📖 4. Quantificateurs et preuves existentielles

🔑 Notions clés & Définitions

• Assertion universelle : Vraie lorsque P(x) est satisfaite par tout élément de E et fausse lorsqu’il existe au moins un contre-exemple.
• Assertion existentielle : Vraie lorsque P(x) est satisfaite par au moins un élément de E et fausse lorsqu’elle ne l’est par aucun.

★ À 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)$.

Compléments

📌 Pour montrer qu’une assertion universelle est fausse, il suffit de trouver un élément de E pour lequel la propriété est fausse ; cet élément est un contre-exemple.

• Toute assertion universelle portant sur l’ensemble vide est vraie, tandis que toute assertion existentielle portant sur l’ensemble vide est fausse.

💡 Astuce mémo

∀ demande tous les éléments ; ∃ n’en demande qu’un.

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

★ À maîtriser

• L’analyse-synthèse démontre l’existence et l’unicité d’un objet en identifiant d’abord l’objet nécessairement imposé, puis en vérifiant qu’il possède les propriétés demandées.

• La récurrence simple prouve ∀n ∈ N, P(n) par l’initialisation P(0) et l’hérédité P(n) ⇒ P(n+1).

• La récurrence forte prouve P(n+1) en supposant simultanément P(k) pour tout k ≤ n, après avoir vérifié l’initialisation.

Compléments

• Pour tout entier n ≥ 4, on peut démontrer par récurrence que 2^n < n!.

💡 Astuce mémo

Analyse → objet nécessaire ; synthèse → propriétés vérifiées ; récurrence : initialisation → hérédité.

📖 6. Notion et représentation des ensembles

🔑 Notions clés & Définitions

• Ensemble : G. Cantor, 1845-1918 — Collection d’objets appelés ses éléments, et la relation e ∈ E signifie que e appartient à E.

★ À maîtriser

📌 L’écriture en extension liste les éléments entre accolades, tandis que l’écriture en compréhension définit les éléments par une propriété, comme F = {x ∈ E : P(x)}.

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

Compléments

• Dans un ensemble, l’ordre d’écriture des éléments et leurs répétitions ne changent pas l’ensemble : {1,3,5} = {3,1,5} = {1,3,1,5,5}.

💡 Astuce mémo

Extension = éléments listés ; compréhension = propriété caractéristique.

📖 7. Inclusion et constructions ensemblistes

🔑 Notions clés & Définitions

• Inclusion : Lorsque tout élément de A est un élément de B.
• Ensemble vide : Unique ensemble n’ayant aucun élément et inclus dans tout ensemble A.
• 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

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

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

Compléments

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

💡 Astuce mémo

Vide → singleton → paire → produit cartésien → parties.

📖 8. Opérations et partitions

🔑 Notions clés & Définitions

• Intersection : Ensemble des éléments qui appartiennent à A et à B.
• Réunion : Ensemble des éléments qui appartiennent à A ou à B.
• Complémentaire : Le complémentaire de A dans E est C_E A = {x ∈ E : x ∉ A}, c’est-à-dire E \ A.
• Partition : Famille de parties non vides, deux à deux disjointes, dont la réunion couvre E.
• Différence symétrique : La différence symétrique A △ B est l’union des éléments appartenant à A mais pas à B et des éléments appartenant à B mais pas à A.
• Ensembles disjoints : Deux ensembles E et F sont disjoints lorsque E ∩ F = ∅.

📝 Points essentiels

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

💡 Astuce mémo

Intersection = et ; réunion = ou ; différence = dans A mais pas dans B.

📊 Tableaux de synthèse

Connecteurs logiques