1 · Résumé du cours
1.1 Propositions et fonctions propositionnelles
Définition — proposition
Une proposition (ou assertion) est un énoncé mathématique auquel on peut attribuer une seule valeur de vérité : vrai (V) ou faux (F).
1.1.1 La négation
Définition
La négation de \(P\), notée \(\overline P\) (ou \(\neg P\)), est vraie lorsque \(P\) est fausse, et fausse lorsque \(P\) est vraie.
\[\begin{array}{|c|c|}\hline P & \overline P\\ \hline V & F\\ \hline F & V\\ \hline\end{array}\]
Deux principes fondamentaux
Pour toute proposition \(P\) :
- \(P\) et \(\overline P\) ne peuvent être vraies en même temps — principe de non-contradiction ;
- \(P\vee\overline P\) est toujours vraie — principe du tiers exclu.
Exemples. « \(2+3=5\) » est vraie ; « \(7\) est pair » est fausse ; « \(x>1\) » n'est pas une proposition (sa vérité dépend de \(x\)) ; « Quel âge as-tu ? » non plus (ce n'est pas une affirmation).
1.1.2 Fonction propositionnelle
Définition — prédicat
Une fonction propositionnelle (ou prédicat) est un énoncé \(P(x)\) dépendant d'une variable \(x\) d'un ensemble \(E\). Pour chaque valeur fixée de \(x\), \(P(x)\) devient une proposition.
Exemple. Dans \(E=\mathbb{R}\), \(P(x):\) « \(x^2-1=0\) ». Alors \(P(1)\) est vraie, \(P(2)\) est fausse, et l'ensemble des \(x\) qui rendent \(P(x)\) vraie est \(\{-1,\,1\}\).
Proposition ou pas ?
Le test : peut-on répondre sans ambiguïté « vrai » ou « faux » ? Si oui, c'est une proposition. Un énoncé à variable libre n'est qu'une fonction propositionnelle, tant qu'on n'a pas fixé la variable ou placé un quantificateur devant.
1.2 Les quantificateurs
Définition
Pour transformer \(P(x)\) en proposition, on
quantifie la variable :
- quantificateur universel \(\forall\) (« pour tout ») : \(\forall x\in E,\ P(x)\) se lit « pour tout \(x\) de \(E\), \(P(x)\) est vraie » ;
- quantificateur existentiel \(\exists\) (« il existe ») : \(\exists x\in E,\ P(x)\) se lit « il existe au moins un \(x\) de \(E\) tel que \(P(x)\) ».
On note \(\exists!\,x\in E,\ P(x)\) pour « il existe un
unique \(x\) tel que \(P(x)\) ».
Exemples. \(\forall x\in\mathbb{R},\ x^2\ge0\) (V) ; \(\exists x\in\mathbb{R},\ x^2=2\) (V, \(x=\sqrt2\)) ; \(\forall x\in\mathbb{R},\ x^2=2\) (F, \(x=0\) ne convient pas) ; \(\exists!\,x\in\mathbb{R},\ x+3=5\) (V, seul \(x=2\)).
L'ordre des quantificateurs compte
\(\forall\) et \(\exists\) ne commutent pas. Comparez, pour \(x,y\in\mathbb{R}\) :
\[\underbrace{\forall x,\ \exists y,\ y>x}_{\text{V : }y=x+1\text{ marche}}\qquad\text{et}\qquad\underbrace{\exists y,\ \forall x,\ y>x}_{\text{F : aucun }y\text{ ne dépasse tout }x}.\]
Dans le premier, \(y\) peut dépendre de \(x\) ; dans le second, le même \(y\) devrait dépasser tous les \(x\). Lisez toujours de gauche à droite.
Domaine et portée
Le domaine \(E\) fait partie de l'énoncé : \(\exists x\in\mathbb{R},\ x^2=2\) est vraie, mais \(\exists x\in\mathbb{Q},\ x^2=2\) est fausse.
1.2.1 Négation d'une proposition quantifiée
Règle
La négation échange les quantificateurs et nie le prédicat :
\[\overline{\big(\forall x\in E,\ P(x)\big)}\;=\;\exists x\in E,\ \overline{P(x)}\]
\[\overline{\big(\exists x\in E,\ P(x)\big)}\;=\;\forall x\in E,\ \overline{P(x)}\]
Exemple. La négation de \(\forall x\in\mathbb{R},\ \exists y\in\mathbb{R},\ x+y=0\) est \(\exists x\in\mathbb{R},\ \forall y\in\mathbb{R},\ x+y\neq0\) : on échange chaque quantificateur, de gauche à droite, puis on nie la relation finale.
1.3 Opérations sur les propositions
À partir de \(P\) et \(Q\), on construit de nouvelles propositions à l'aide de connecteurs logiques, décrits par leur table de vérité.
1.3.1 Conjonction et disjonction
Définition
- la conjonction « \(P\) et \(Q\) », notée \(P\wedge Q\), est vraie uniquement quand \(P\) et \(Q\) sont vraies toutes les deux ;
- la disjonction « \(P\) ou \(Q\) », notée \(P\vee Q\), est fausse uniquement quand \(P\) et \(Q\) sont fausses toutes les deux.
\[\begin{array}{|c|c|c|c|}\hline P & Q & P\wedge Q & P\vee Q\\ \hline V & V & V & V\\ \hline V & F & F & V\\ \hline F & V & F & V\\ \hline F & F & F & F\\ \hline\end{array}\]
Le « ou » mathématique est inclusif
En français courant, « fromage ou dessert » est exclusif. En maths, le « ou » est inclusif : \(P\vee Q\) reste vraie quand \(P\) et \(Q\) le sont ensemble. Ainsi « \(x\le2\) ou \(x\ge0\) » est vraie pour tout réel.
1.3.2 L'implication
Définition
L'implication « \(P\Rightarrow Q\) » (« si \(P\) alors \(Q\) ») est fausse dans le seul cas où \(P\) est vraie et \(Q\) fausse ; vraie dans tous les autres cas.
\[\begin{array}{|c|c|c|c|}\hline P & Q & P\Rightarrow Q & Q\Rightarrow P\\ \hline V & V & V & V\\ \hline V & F & F & V\\ \hline F & V & V & F\\ \hline F & F & V & V\\ \hline\end{array}\]
« Le faux implique n'importe quoi »
Quand \(P\) est fausse, \(P\Rightarrow Q\) est vraie, quelle que soit \(Q\). Ainsi « \(2<0\Rightarrow 3=7\) » est vraie ! Une implication ne garantit rien sur \(Q\) tant que \(P\) n'est pas réalisée.
Vocabulaire de l'implication
Pour \(P\Rightarrow Q\) : la réciproque est \(Q\Rightarrow P\) ; la contraposée est \(\overline Q\Rightarrow\overline P\) ; on dit que \(P\) est suffisante pour \(Q\), et \(Q\) nécessaire pour \(P\).
Exemple. « \(x=2\Rightarrow x^2=4\) » est vraie. Sa réciproque « \(x^2=4\Rightarrow x=2\) » est fausse (\(x=-2\) est un contre-exemple), mais sa contraposée « \(x^2\neq4\Rightarrow x\neq2\) » est vraie.
1.3.3 L'équivalence
Définition
L'équivalence « \(P\Leftrightarrow Q\) » (« \(P\) si et seulement si \(Q\) ») est vraie lorsque \(P\) et \(Q\) ont la même valeur de vérité. Elle équivaut à \((P\Rightarrow Q)\wedge(Q\Rightarrow P)\).
\[\begin{array}{|c|c|c|}\hline P & Q & P\Leftrightarrow Q\\ \hline V & V & V\\ \hline V & F & F\\ \hline F & V & F\\ \hline F & F & V\\ \hline\end{array}\]
Prouver une équivalence = prouver DEUX implications
Pour établir \(P\Leftrightarrow Q\), on démontre séparément \(P\Rightarrow Q\) (sens direct) puis \(Q\Rightarrow P\) (réciproque). Oublier un sens est l'erreur classique.
1.4 Lois logiques
Définition — tautologie
Une loi logique (ou tautologie) est une proposition toujours vraie, quelles que soient les valeurs de vérité des propositions qui la composent (sa colonne finale ne contient que des V).
Les lois à connaître
Pour toutes propositions \(P,Q,R\) :
\[\overline{\overline P}\Leftrightarrow P,\qquad P\wedge Q\Leftrightarrow Q\wedge P,\qquad P\vee Q\Leftrightarrow Q\vee P\quad(\text{commutativité}),\]
\[P\wedge(Q\vee R)\Leftrightarrow(P\wedge Q)\vee(P\wedge R),\qquad P\vee(Q\wedge R)\Leftrightarrow(P\vee Q)\wedge(P\vee R)\quad(\text{distributivité}),\]
\[\overline{P\wedge Q}\Leftrightarrow\overline P\vee\overline Q,\qquad \overline{P\vee Q}\Leftrightarrow\overline P\wedge\overline Q\quad(\textbf{De Morgan}),\]
\[(P\Rightarrow Q)\Leftrightarrow(\overline P\vee Q),\qquad \overline{P\Rightarrow Q}\Leftrightarrow(P\wedge\overline Q),\]
\[(P\Rightarrow Q)\Leftrightarrow(\overline Q\Rightarrow\overline P),\qquad \big[(P\Rightarrow Q)\wedge(Q\Rightarrow R)\big]\Rightarrow(P\Rightarrow R)\quad(\text{transitivité}).\]
Vérifier la contraposition par table
\[\begin{array}{|c|c|c|c|c|c|}\hline P & Q & P\Rightarrow Q & \overline Q & \overline P & \overline Q\Rightarrow\overline P\\ \hline V & V & V & F & F & V\\ \hline V & F & F & V & F & F\\ \hline F & V & V & F & V & V\\ \hline F & F & V & V & V & V\\ \hline\end{array}\]
Les colonnes \(P\Rightarrow Q\) et \(\overline Q\Rightarrow\overline P\) sont identiques : les deux propositions sont équivalentes.
De Morgan, le réflexe pour nier
Pour nier une conjonction ou une disjonction, on échange \(\wedge\) et \(\vee\) et on nie chaque morceau. La négation de « \(x\ge0\) et \(x\le1\) » est « \(x<0\) ou \(x>1\) ». Couplé à la règle des quantificateurs, c'est l'outil universel de la négation.
1.5 Les raisonnements mathématiques
Démontrer une proposition, c'est établir qu'elle est vraie à partir des hypothèses, des définitions et des propriétés connues. Voici les principales méthodes.
1.5.1 Raisonnement direct
Méthode
Pour démontrer directement \(P\Rightarrow Q\), on suppose \(P\) vraie, puis on enchaîne des déductions justifiées jusqu'à \(Q\).
Exemple. La somme de deux rationnels est rationnelle : si \(a=\frac pq\) et \(b=\frac rs\) avec \(p,r\in\mathbb{Z}\), \(q,s\in\mathbb{N}^*\), alors \(a+b=\frac{ps+rq}{qs}\in\mathbb{Q}\).
1.5.2 Raisonnement par contre-exemple
Méthode
Pour montrer qu'une proposition « \(\forall x\in E,\ P(x)\) » est fausse, il suffit d'exhiber un seul \(x_0\) tel que \(P(x_0)\) soit fausse.
Exemple. « Tout entier naturel est somme de deux carrés » est faux : \(3\) n'est pas somme de deux carrés. L'entier \(3\) est un contre-exemple.
1.5.3 Raisonnement par contraposée
Méthode
Pour démontrer \(P\Rightarrow Q\), on peut démontrer sa contraposée \(\overline Q\Rightarrow\overline P\) (qui lui est équivalente). On y gagne quand \(\overline Q\) est plus maniable que \(P\).
Exemple. « si \(n^2\) est pair alors \(n\) est pair » : la contraposée « \(n\) impair \(\Rightarrow n^2\) impair » se prouve avec \(n=2k+1\), \(n^2=2(2k^2+2k)+1\).
1.5.4 Raisonnement par équivalences successives
Méthode
Pour résoudre une équation ou prouver une équivalence, on enchaîne des \(\Leftrightarrow\) jusqu'à un résultat évident. Chaque étape doit être réversible — sinon on n'a qu'une implication.
Exemple. \(2x-1=5\iff 2x=6\iff x=3\). Toutes les étapes sont réversibles : \(S=\{3\}\).
1.5.5 Raisonnement par disjonction des cas
Méthode
Lorsqu'une propriété se démontre différemment selon les situations, on partage l'ensemble d'étude en cas qui le recouvrent entièrement, et l'on conclut dans chaque cas.
Exemple. \(\forall n\in\mathbb{N},\ n(n+1)\) est pair : si \(n\) est pair, \(n(n+1)\) l'est ; si \(n\) est impair, \(n+1\) est pair. Dans les deux cas, \(n(n+1)\) est pair.
1.5.6 Raisonnement par l'absurde
Méthode
Pour démontrer \(P\), on suppose qu'elle est fausse (\(\overline P\) vraie) et l'on en déduit une contradiction : l'hypothèse \(\overline P\) était intenable, donc \(P\) est vraie.
Exemple — \(\sqrt2\) est irrationnel. Si \(\sqrt2=\frac pq\) irréductible, alors \(p^2=2q^2\), donc \(p\) pair (\(p=2k\)), puis \(q^2=2k^2\) donc \(q\) pair : \(p\) et \(q\) tous deux pairs contredit « \(\frac pq\) irréductible ». Donc \(\sqrt2\notin\mathbb{Q}\).
1.5.7 Raisonnement par récurrence
Principe de récurrence
Soit \(P(n)\) une propriété dépendant de \(n\in\mathbb{N}\) et \(n_0\in\mathbb{N}\). Si
- (Initialisation) \(P(n_0)\) est vraie ;
- (Hérédité) pour tout \(n\ge n_0\), \(P(n)\Rightarrow P(n+1)\),
alors \(P(n)\) est vraie
pour tout \(n\ge n_0\).
Rédiger une récurrence
- Énoncer clairement \(P(n)\) ;
- Initialisation : vérifier \(P(n_0)\) ;
- Hérédité : supposer \(P(n)\) vraie (hypothèse de récurrence) pour un \(n\ge n_0\) fixé, et en déduire \(P(n+1)\) ;
- Conclusion : \(P(n)\) est vraie pour tout \(n\ge n_0\).
Exemple : \(1+2+\dots+n=\frac{n(n+1)}2\). Init. \(n=1\) : \(1=\frac{1\cdot2}2\). Hérédité : \(\frac{n(n+1)}2+(n+1)=\frac{(n+1)(n+2)}2\).
L'initialisation n'est pas une formalité
Une propriété peut être héréditaire sans jamais être vraie : « \(P(n): 2^n\) est divisible par \(3\) » vérifie \(P(n)\Rightarrow P(n+1)\) (si \(3\mid 2^n\) alors \(3\mid 2^{n+1}=2\cdot2^n\)), pourtant \(P(0)\) est fausse et \(P(n)\) l'est pour tout \(n\). Sans initialisation, la récurrence ne prouve rien.