Résumé de cours : bases de la logique
Une proposition (ou assertion) est un énoncé mathématique qui a une et une seule valeur : vrai ou faux.
La négation de la proposition $P$ est la proposition qui est vraie si et seulement si $P$ est fausse. Elle est notée $\textrm{non }P$.
Si $P$ et $Q$ sont deux propositions, $P$ et $Q$ est la proposition qui est vraie si et seulement si $P$ et $Q$ sont toutes les deux vraies.
Si $P$ et $Q$ sont deux propositions, $P$ ou $Q$ est la proposition qui est vraie si et seulement si au moins une des deux propositions $P$ ou $Q$ est vraie.
Les opérateurs non, et, ou, sont reliés par les formules suivantes : $$\textrm{non }(P\textrm{ et }Q)=(\textrm{non }P)\textrm{ ou }(\textrm{non }Q).$$ $$\textrm{non }(P\textrm{ ou }Q)=(\textrm{non }P)\textrm{ et }(\textrm{non }Q).$$
L'implication $P\implies Q$ est la proposition $\textrm{non }P\textrm{ ou }Q$. Pour démontrer $P\implies Q$, on suppose que $P$ est vraie et on démontre que $Q$ est vraie. La négation de la proposition $P\implies Q$ est donc la proposition $P\textrm{ et non }Q$.
On dit que les proposition $P$ et $Q$ sont équivalentes lorsque l'on a à la fois $P\implies Q$ et $Q\implies P$ qui sont vraies. On note alors $P\iff Q$.
La contraposée de la proposition $P\implies Q$ est la proposition $\textrm{non }Q\implies \textrm{non }P$. Les deux propositions $P\implies Q$ et $\textrm{non }Q\implies \textrm{non }P$ sont équivalentes. L'une est vraie si et seulement si l'autre est vraie.
Le quantificateur pour tout ou quel que soit est noté $\forall$. La proposition $\forall x\in E,\ P(x)$ est vraie lorsque, pour tout $x\in E$, la proposition $P(x)$ est vraie.
Le quantificateur il existe (au moins un) est noté $\exists$. La proposition $\exists x\in E,\ P(x)$ est vraie lorsqu'il existe au moins un $x\in E$ telle que la proposition $P(x)$ soit vraie.
Le quantificateur il existe un unique est noté $\exists!$. La proposition $\exists! x\in E,\ P(x)$ est vraie lorsqu'il existe un unique $x\in E$ telle que la proposition $P(x)$ soit vraie.
La négation de $\forall x\in E,\ P(x)$ est $\exists x\in E,\ \textrm{non }P(x)$. La négation de $\exists x\in E,\ P(x)$ est $\forall x\in E,\ \textrm{non }P(x)$.
Lorsque $P\implies Q$, on dit que $P$ est une condition suffisante à $Q$, et que $Q$ est une condition nécessaire à $P$.
- On raisonne par double implication : on suppose d'abord que $P$ est vraie, et on démontre que $Q$ est vraie. Ensuite, on suppose que $Q$ est vraie, et on démontre que $P$ est vraie.
- On passe de $P$ à $Q$ en utilisant uniquement des équivalences. C'est une méthode souvent déconseillée, car il faut faire très attention à ce que chaque enchaînement logique de la démonstration est bien une équivalence.
- commencer cette phase par la phrase : ``supposons que, pour tout $n\in\mathbb N$, $P(n)$ est vraie et prouvons $P(n+1)$''. Si $P(n)$ est vraie pour tout entier $n$, il n'y a plus rien à prouver!
- commencer cette phase par la phrase : ``supposons qu'il existe un $n\in\mathbb N$ tel que $P(n)$ est vraie et prouvons $P(n+1)$. L'erreur est plus subtile. Le principe de récurrence s'écrit formellement $$\big (P(0) \textrm{ vraie ET }(\forall n\in \mathbb N\ P(n)\implies P(n+1)\big)\implies \forall n\in\mathbb N, P(n)\textrm{ vraie.}$$ La dernière rédaction serait correcte si le principe de récurrence s'écrivait $$\big (P(0) \textrm{ vraie ET }(\exists n\in \mathbb N\ P(n)\implies P(n+1)\big)\implies \forall n\in\mathbb N, P(n)\textrm{ vraie.}$$ ce qui est faux.
- initialisation : prouver que $P(0)$ et $\mathcal P(1)$ sont vraies.
- hérédité : prouver que, pour tout entier $n$, si $P(n)$ et $P(n+1)$ sont vraies, alors $P(n+2)$ est vraie.
- initialisation : prouver que $P(0)$ est vraie.
- hérédité : prouver que, pour tout entier $n$, si $P(0),P(1),\dots,P(n)$ sont toutes vraies, alors $P(n+1)$ est vraie.
- L'analyse. On suppose que $x$ est solution du problème, et on trouve un certain nombre de conditions nécessaires satisfaites par $x$.
- La synthèse. On vérifie que les conditions obtenues à l'issue de la phase d'analyse sont en fait également suffisantes pour que $x$ soit solution du problème.