Fiche résumé : Logique et raisonnements (Prépa, 1re année)

Ce chapitre fixe le langage dans lequel toutes les mathématiques de prépa sont écrites : assertions, connecteurs, quantificateurs, et la façon correcte de les nier. Il donne aussi les schémas de démonstration (contraposée, absurde, analyse-synthèse, récurrences) qui servent ensuite dans tous les chapitres.

Table de vérité : $P\Rightarrow Q$ n'est fausse que si $P$ est vraie et $Q$ fausse ; $P\Rightarrow Q$ équivaut à $(\neg P)\vee Q$.
De Morgan : $\neg(P\wedge Q)\equiv\neg P\vee\neg Q$ et $\neg(P\vee Q)\equiv\neg P\wedge\neg Q$.
Négation d'une implication : $\neg(P\Rightarrow Q)\equiv P\wedge\neg Q$.
Contraposée : $P\Rightarrow Q$ équivaut à $\neg Q\Rightarrow\neg P$. La réciproque $Q\Rightarrow P$ n'est pas équivalente.
Équivalence : $P\Leftrightarrow Q$ signifie $(P\Rightarrow Q)\wedge(Q\Rightarrow P)$. Si $P\Rightarrow Q$ : $P$ condition suffisante, $Q$ condition nécessaire.
Négation des quantificateurs : $\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)$.
Ordre : on ne permute jamais un $\forall$ et un $\exists$. En niant, on garde l'ordre et les ensembles ($\forall\varepsilon>0$ devient $\exists\varepsilon>0$).
Prouver $\forall x\in E,\ P(x)$ : « Soit $x\in E$ », puis preuve générale. Prouver $\exists$ : exhiber un élément. Réfuter un $\forall$ : un contre-exemple.
Contraposée : on suppose $\neg Q$, on aboutit à $\neg P$. Absurde : on suppose $\neg R$, on aboutit à une contradiction.
Disjonction de cas : les cas doivent recouvrir tout l'ensemble.
Analyse-synthèse : analyse = conditions nécessaires (unicité) ; synthèse = vérification (existence) ; conclusion.
Récurrence simple : $P(n_0)$ et $\forall n\geq n_0,\ P(n)\Rightarrow P(n+1)$.
Récurrence double : $P(n_0)$, $P(n_0+1)$ et $\forall n\geq n_0,\ (P(n)\wedge P(n+1))\Rightarrow P(n+2)$.
Récurrence forte : $P(n_0)$ et $\forall n\geq n_0$, $\big(\forall k\in\llbracket n_0,n\rrbracket,\ P(k)\big)\Rightarrow P(n+1)$.
Résultats types : $n^2$ pair $\Rightarrow n$ pair ; $\sqrt{2}\notin\mathbb{Q}$ ; infinité des nombres premiers ; toute fonction $\mathbb{R}\to\mathbb{R}$ est, de façon unique, somme d'une paire $\frac{f(x)+f(-x)}{2}$ et d'une impaire $\frac{f(x)-f(-x)}{2}$ ; tout entier $n\geq 2$ est produit de nombres premiers.