$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Ressources mathématiques > Documents pour la math sup >
Accéder à mon compte > Accéder à ma feuille d'exercices >

Résumé de cours : bases de la logique

Propositions
  • 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.
  • $$\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.
  • 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$.
Quantificateurs
  • Le quantificateur pour tout ou quel que soit est noté $\forall x$. 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)$.
Conditions nécessaires, conditions suffisantes
    Lorsque $P\implies Q$, on dit que $P$ est une condition suffisante à $Q$, et que $Q$ est une condition nécessaire à $P$.
Méthodes de raisonnement
  • par implication : pour prouver que $P\implies Q$, on suppose que $P$ est vraie et on utilise différentes propriétés déjà connues pour établir que $Q$ est vraie.
  • par double implication / par équivalence : Pour démontrer que $P\iff Q$, il y a deux méthodes standard :
    • 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.
  • par contraposée : pour démontrer que $P\implies Q$, il suffit de démontrer la contraposée de cette proposition, c'est-à-dire $\textrm{non }Q\implies\textrm{non }P$.
  • par l'absurde : pour démontrer que $P\implies Q$, on peut supposer que $P$ et $\textrm{non }Q$ sont toutes les deux vraies, et obtenir une contradiction; pour démontrer que $P$ est vraie, on peut supposer que $\textrm{non }P$ est vraie et obtenir une contradiction.
  • par récurrence : Le raisonnement par récurrence est utilisé pour démontrer des propriétés qui dépendent d'un entier $n$. Il est basé sur le principe suivant :
    Théorème (principe de récurrence) : Soit $P(n)$ une propriété concernant un entier naturel $n$. On suppose que $P(0)$ est vraie et que, pour tout entier naturel $k$, si $P(k)$ est vraie, alors $P(k + 1)$ est vraie. Alors la propriété $P(n)$ est vraie pour tout entier naturel $n$.

    Pour bien rédiger une démonstration par récurrence, il est nécessaire de faire apparaitre clairement les 4 étapes : définir précisément quelle est la propriété $ P(n)$ que l'on souhaite démontrer, écrire la phase d'initialisation, la phase d'hérédité, puis la conclusion. Il existe deux erreurs fréquentes de rédaction de la phase d'hérédité.
    • 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.
    Pour ne pas faire d'erreurs, je vous conseille de toujours commencer la phase d'hérédité par : ``Soit $n\in\mathbb N$ tel que $P(n)$ est vraie'' ou alors ``Supposons que $P(n)$ est vraie pour un certain $n\in\mathbb N$''.
  • par récurrence double : si on veut prouver qu'une proposition $P(n)$ dépendant de l'entier naturel $n$ est vraie pour tout entier $n$, on peut procéder de la façon suivante :
    • 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.
  • par récurrence forte : si on veut prouver qu'une proposition $P(n)$ dépendant de l'entier naturel $n$ est vraie pour tout entier $n$, on peut procéder de la façon suivante :
    • 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.
  • par disjonction de cas : le raisonnement par disjonction de cas s'utilise quand on veut démontrer une propriété $P$ dépendant d'un paramètre $x$ appartenant à un ensemble $E$, et que la justification dépend de la valeur de $x$. On écrit alors $E=E_1\cup\dots\cup E_n$, et on sépare les raisonnements suivant que $x\in E_1$, $x\in E_2,\dots$. On emploie fréquemment ce raisonnement pour résoudre des (in)équations avec des valeurs absolues (le raisonnement dépend du signe de la quantité à l'intérieur de la valeur absolue), démontrer des propriétés en arithmétique (on sépare le raisonnement suivant la parité de certains entiers, leur congruence modulo $n$...), résoudre des problèmes de géométrie (disjonction selon la position relative de deux objets géométriques).
  • par analyse/synthèse : le raisonnement par analyse/synthèse, qu'on pourrait aussi appeler raisonnement par condition nécessaire/condition suffisante, est un raisonnement que l'on emploie souvent lorsqu'on cherche toutes les solutions d'un problème donné. Il comporte deux phases :
    • 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.