Fiche de révision : Expression mathématique et logique

📋 Plan du Cours

1. Propositions et opérations logiques
2. Méthodes de raisonnement
3. Ensembles et opérations ensemblistes
4. Quantificateurs et relations
5. Récurrence et formules combinatoires
6. Logique propositionnelle et quantificateurs
7. Méthodes de démonstration arithmétique
8. Opérations sur les ensembles
9. Relations et classes d’équivalence
10. Fonctions indicatrices et produits

📖 1. Propositions et opérations logiques

🔑 Notions clés & Définitions

• Proposition : Énoncé sur des objets auquel on peut attribuer l’une des deux valeurs de vérité, vraie ou fausse, selon le principe du tiers exclu.
• Négation : Proposition qui est vraie si P est fausse et fausse si P est vraie.
• Disjonction : Vraie si au moins l’une des deux propositions est vraie et fausse si les deux propositions sont fausses.
• Conjonction : Vraie si les deux propositions sont vraies et fausse si au moins l’une des deux propositions est fausse.
• Implication logique : Fausse dans le seul cas où P est vraie et Q est fausse ; elle est vraie si P est fausse ou si P et Q sont vraies.

★ À maîtriser

📌 L’implication P ⇒ Q est équivalente à (non P) ou Q, et sa négation est équivalente à P et (non Q).

📌 L’équivalence P ⇔ Q est vraie lorsque P et Q ont la même valeur logique et équivaut à P ⇒ Q et Q ⇒ P.

Compléments

• Les axiomes sont des vérités premières qui ne se déduisent pas d’autres propositions vraies et dont on ne peut déduire simultanément une proposition vraie et fausse.

💡 Astuce mémo

Le « ou » accepte les deux propositions, tandis que le « et » exige les deux.

📖 2. Méthodes de raisonnement

★ À maîtriser

• Pour démontrer P ⇒ Q par contraposée, on démontre l’implication équivalente non Q ⇒ non P.

• Pour démontrer une proposition R par l’absurde, on suppose R fausse puis on déduit une contradiction.

Compléments

• Si n est un entier impair, alors son chiffre des unités est impair ; par contraposée, si le chiffre des unités est pair, alors n est pair.

• Pour montrer qu’il n’existe pas de plus petit réel strictement positif, supposer qu’un tel réel a existe conduit à 0 < a/2 < a, ce qui est contradictoire.

💡 Astuce mémo

Contraposée : hypothèse fausse de la conclusion → conclusion fausse de l’hypothèse ; absurde : hypothèse contraire → contradiction.

📖 3. Ensembles et opérations ensemblistes

🔑 Notions clés & Définitions

• Ensemble : Collection d’objets appelés éléments, telle que pour tout objet x une seule des propositions x ∈ E ou x ∉ E est vraie.
• Sous-ensemble : Ensemble tel que tout élément de A appartient à E.
• Complémentaire : Ensemble des éléments de E qui n’appartiennent pas à A.
• Fonction indicatrice : Vaut 1 si x ∈ A et 0 si x ∉ A.
• Produit cartésien : Constitué des couples (x,y) tels que x ∈ E et y ∈ F.

📝 Points essentiels

• L’ensemble vide, noté ∅, ne contient aucun élément et est inclus dans tout ensemble E.

📌 L’intersection A ∩ B contient les éléments appartenant à A et à B, tandis que l’union A ∪ B contient les éléments appartenant à A ou à B.

📐 Formule — Pour un ensemble fini E de cardinal n, le nombre de ses parties vérifie $\operatorname{card}(\mathcal P(E))=2^n$.

💡 Astuce mémo

Intersection = « et » ; union = « ou » ; complémentaire = négation.

📖 4. Quantificateurs et relations

🔑 Notions clés & Définitions

• Proposition dépendant d’une variable : Une proposition dépendant d’une variable x se note P(x), et l’ensemble des éléments de E qui vérifient P se note A_P = {x ∈ E, P(x)}.
• Quantificateur universel : Signifie que P(x) est vraie pour tout élément x de E.
• Quantificateur existentiel : Signifie qu’il existe au moins un élément x de E pour lequel P(x) est vraie, tandis que ∃! indique l’existence d’un unique élément.
• Relation d’équivalence : Relation réflexive, symétrique et transitive.

★ À maîtriser

📌 Deux quantificateurs de même nature consécutifs peuvent être échangés, mais ∃x∀y n’a pas le même sens que ∀y∃x.

📌 La négation de ∀x ∈ E, P(x) est ∃a ∈ E, non P(a), et la négation de ∃a ∈ E, Q(a) est ∀x ∈ E, non Q(x).

Compléments

• Une relation dans E est une partie de E × E, et x et y sont liés par cette relation R lorsque (x,y) ∈ R.

💡 Astuce mémo

∀ exige tous les éléments, ∃ n’en exige qu’un ; l’ordre ∃x∀y diffère de ∀y∃x.

📖 5. Récurrence et formules combinatoires

★ À maîtriser

📐 Formule — La formule du binôme de Newton est $(a+b)^n=\sum_{p=0}^{n}\binom{n}{p}a^{n-p}b^p$, avec $\binom{n}{p}=\frac{n!}{p!(n-p)!}$ et $\binom{n+1}{p+1}=\binom{n}{p}+\binom{n}{p+1}$.

• Un raisonnement par récurrence comporte l’initialisation, qui consiste à montrer que la proposition est vraie au premier rang, puis l’hérédité, qui consiste à montrer que sa vérité au rang n entraîne sa vérité au rang n+1.

Compléments

📐 Formule — Pour tout entier naturel n, $1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2=\frac{n^2(n+1)^2}{4}$.

• L’ensemble des parties de $E=\{1{,}2{,}3\}$ est composé de ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} et E, soit 8 parties.

💡 Astuce mémo

Initialisation → hérédité → conclusion

📖 6. Logique propositionnelle et quantificateurs

📝 Points essentiels

• La négation de $P\Rightarrow Q$ est $P\land\neg Q$, tandis que la contraposée de $P\Rightarrow Q$ est $\neg Q\Rightarrow\neg P$.

• La négation de $\forall x\in E,\ P(x)$ est $\exists x\in E,\ \neg P(x)$, et la négation de $\exists x\in E,\ P(x)$ est $\forall x\in E,\ \neg P(x)$.

• La proposition $\forall x\in E,\ \exists y\in F,\ R(x,y)$ autorise un y dépendant de x, alors que $\exists y\in F,\ \forall x\in E,\ R(x,y)$ exige un même y pour tous les x.

• La négation de $P\lor Q$ est $\neg P\land\neg Q$, et la négation de $P\land Q$ est $\neg P\lor\neg Q$.

• La proposition $\exists x\,(P(x)\land Q(x))$ implique $\exists a\,P(a)\land\exists b\,Q(b)$, mais la réciproque est fausse car les témoins a et b peuvent être différents.

💡 Astuce mémo

∀x∃y permet un y dépendant de x, tandis que ∃y∀x impose un même y

📖 7. Méthodes de démonstration arithmétique

★ À maîtriser

📌 Pour tout entier n, 3n est pair si et seulement si n est pair.

📌 Si n est un entier impair, alors n^2 est impair ; réciproquement, si n^2 est pair, alors n est pair.

Compléments

📐 Formule — Pour tous réels a<b, le réel $c=a+\frac{b-a}{2}$ vérifie a<c<b.

• Si n est un entier relatif, alors $12n^2-36n+25$ est un entier positif.

💡 Astuce mémo

Directe, contraposée, absurde, récurrence

📖 8. Opérations sur les ensembles

🔑 Notions clés & Définitions

• Différence symétrique : La différence symétrique de A et B est $A\Delta B=(A\setminus B)\cup(B\setminus A)$.

★ À maîtriser

📌 Les opérations sur les ensembles traduisent les connecteurs logiques : l’union correspond à « ou », l’intersection à « et » et le complémentaire à « non ».

Compléments

📐 Formule — Pour des parties A, B, C et D adaptées, $(A\times C)\cap(B\times D)=(A\cap B)\times(C\cap D)$, mais l’égalité analogue avec l’union n’est pas toujours vraie.

📐 Formule — Pour toute partie A d’un ensemble E, $\mathbf{1}_{A^c}=1-\mathbf{1}_A$ et $\mathbf{1}_{A\cap B}=\mathbf{1}_A\mathbf{1}_B$.

💡 Astuce mémo

Union = ou ; intersection = et ; complémentaire = non

📖 9. Relations et classes d’équivalence

🔑 Notions clés & Définitions

• Classe d’équivalence : La classe d’équivalence d’un élément a pour une relation d’équivalence R est $\hat a=\{x\in E\mid xRa\}$.

★ À maîtriser

📌 Les classes d’équivalence d’une relation d’équivalence forment une partition de E : elles sont deux à deux disjointes et leur réunion est E.

Compléments

• Sur $E=\mathbb Z\times\mathbb Z^*$, la relation définie par $(p,q)R(p',q')\iff pq'=p'q$ est une relation d’équivalence dont le quotient est l’ensemble des nombres rationnels.

💡 Astuce mémo

Relation d’équivalence → classes disjointes → partition

📖 10. Fonctions indicatrices et produits

★ À maîtriser

📐 Formule — Pour des parties A d’un ensemble E et B d’un ensemble F, la fonction indicatrice du produit cartésien vérifie $\mathbf{1}_{A\times B}(x,y)=\mathbf{1}_A(x)\mathbf{1}_B(y)$.

Compléments

📐 Formule — Pour des parties A et B, la fonction indicatrice de leur différence symétrique vérifie $\mathbf{1}_{A\Delta B}=\mathbf{1}_A+\mathbf{1}_B-2\mathbf{1}_A\mathbf{1}_B$.

📐 Formule — Si C⊂A et D⊂B, alors $(A\times B)\setminus(C\times D)=((A\setminus C)\times B)\cup(C\times(B\setminus D))$.

📊 Tableaux de synthèse

Opérations logiques fondamentales