Notions de logique
Table des matières
Propositions et connecteurs logiques
Propositions
Définition
-
Tout énoncé mathématique qui a un sens et qui est soit vrai, soit faux, est une proposition (ou assertion). Une proposition est notée généralement \(p\), \(q\), \(r\), \(\dots\)
-
On désigne par \(1\) ou \(\mathrm{V}\) la valeur de vérité d’une proposition vraie, et par \(0\) ou \(\mathrm{F}\) celle d’une proposition fausse.
-
Une proposition est soit vraie, soit fausse, et ne peut être à la fois vraie et fausse.
-
Une table de vérité est un tableau qui donne la valeur de vérité d’une proposition \(p\) construite à partir d’autres propositions \(q, r, \dots\), en fonction des valeurs de vérité de ces dernières.
Exemple
Pour chacune des phrases suivantes :
-
Dire si c’est une proposition. Justifier.
-
Si c’est une proposition, donner sa valeur de vérité.
-
\(\sqrt{16}+\sqrt{9}=7\).
-
Quelle est la solution de \(x^{2}=4\) ?
-
\(\sqrt{2}+\sqrt{6}\leq \sqrt{8}\).
-
Ferme la porte !
-
\(\cos\!\left(\dfrac{\pi}{6}\right)=\dfrac{\sqrt{3}}{2}\).
-
\(\sqrt{3}-\sqrt{2}=1\).
Application
On considère les propositions suivantes :
-
\(p\) : \(\sqrt{2}\in\mathbb{N}\).
-
\(q\) : \(7\) est un nombre premier.
-
\(r\) : \(114\,516\) est un multiple de \(3\).
-
Donner la valeur de vérité de \(p\), \(q\) et \(r\).
-
Construire la table de vérité associée au triplet \((p, q, r)\). Combien de combinaisons obtient-on ?
Les connecteurs logiques
Proposition
Soient \(p\) et \(q\) deux propositions. On définit cinq connecteurs logiques :
-
Négation : la proposition « non \(p\) », notée \(\overline{p}\) (ou \(\neg p\)), est vraie si \(p\) est fausse, et fausse si \(p\) est vraie.
-
Conjonction : la proposition « \(p\) et \(q\) », notée \(p\wedge q\), est vraie si \(p\) et \(q\) sont toutes les deux vraies, et fausse sinon.
-
Disjonction : la proposition « \(p\) ou \(q\) », notée \(p\vee q\), est vraie si au moins l’une des deux propositions est vraie, et fausse sinon.
-
Implication : la proposition « \(p\Rightarrow q\) », qui se lit « \(p\) implique \(q\) » ou « si \(p\) alors \(q\) », n’est fausse que lorsque \(p\) est vraie et \(q\) est fausse. La proposition \(q\Rightarrow p\) s’appelle l’implication réciproque de \(p\Rightarrow q\).
-
Équivalence : la proposition « \(p\Leftrightarrow q\) », qui se lit « \(p\) équivaut à \(q\) » ou « \(p\) si et seulement si \(q\) », est vraie lorsque \(p\) et \(q\) ont la même valeur de vérité (toutes deux vraies, ou toutes deux fausses).
Tables de vérité.
| \(p\) | \(q\) | \(\overline{p}\) | \(p\wedge q\) | \(p\vee q\) | \(p\Rightarrow q\) | \(p\Leftrightarrow q\) |
|---|---|---|---|---|---|---|
| V | V | F | V | V | V | V |
| V | F | F | F | V | F | F |
| F | V | V | F | V | V | F |
| F | F | V | F | F | V | V |
Exemple
Donner la valeur de vérité de chacune des propositions suivantes.
-
\(36\) est pair et multiple de \(3\).
-
\(69\) est impair ou multiple de \(3\).
-
\(\sqrt{2}\in\mathbb{Q} \Rightarrow \pi^{2}<10\).
-
\(\sqrt{100}=10 \Leftrightarrow x^{2}-8x+15=0\) admet \(5\) comme unique solution.
-
\(0\) est impair ou \(\sqrt{25+16}=5+4\).
-
\(5+5=11 \Leftrightarrow 3<2\).
Application
-
Soient \(p\) et \(q\) deux propositions. À l’aide d’une table de vérité, montrer que :
\[(p\Rightarrow q) \Leftrightarrow (\overline{p}\vee q).\] -
En déduire la valeur de vérité de la proposition :
\[(\sqrt{2}\in\mathbb{Z}) \Rightarrow (\sqrt{2}>1).\]
Proposition
Soient \(p\) et \(q\) deux propositions.
-
\(\overline{p\wedge q} \Leftrightarrow (\overline{p}\vee \overline{q})\).
-
\(\overline{p\vee q} \Leftrightarrow (\overline{p}\wedge \overline{q})\).
-
\((p\Leftrightarrow q) \Leftrightarrow \big[(p\Rightarrow q)\wedge (q\Rightarrow p)\big]\).
-
\((p\wedge \overline{p})\) est toujours fausse ; \((p\vee \overline{p})\) est toujours vraie.
Exercice
-
Démontrer la première loi de De Morgan à l’aide d’une table de vérité.
-
Soient \(a, b\in\mathbb{R}\) et \(m, n\in\mathbb{N}\). Donner la négation de chacune des propositions :
-
\(u\) : « \(a^{2}+b^{2}=(a+b)^{2}-2ab\) et \((a+b)^{2}-2ab=\dfrac{(a+b)^{2}+(a-b)^{2}}{2}\) ».
-
\(v\) : « \(mn=m+n\) ou \(mn>m+n\) ».
-
Les quantificateurs
Fonction propositionnelle
Définition
On appelle fonction propositionnelle sur un ensemble \(E\) tout énoncé mathématique contenant une ou plusieurs variables appartenant à \(E\) et qui devient une proposition à chaque fois qu’on remplace la (ou les) variable(s) par un (ou des) élément(s) de \(E\). On la note généralement \(A(x)\), \(A(x,y)\), \(\dots\)
Exemple
On considère les fonctions propositionnelles suivantes :
-
\(A(x) : x^{2}\geq x\) où \(x\in\mathbb{R}\) ;
-
\(B(n) : n^{2}+n+1\) est premier, où \(n\in\mathbb{N}\) ;
-
\(C(x,y) : x+y=xy\) où \((x,y)\in\mathbb{R}^{2}\).
-
Donner la valeur de vérité de \(A(2)\) et de \(A\!\left(\dfrac{1}{2}\right)\).
-
Donner la valeur de vérité de \(B(0)\), \(B(1)\), \(B(4)\).
-
Trouver un couple \((x,y)\in\mathbb{R}^{2}\) tel que \(C(x,y)\) soit vraie, et un couple tel qu’elle soit fausse.
Application
Soit \(A(x) : \dfrac{x-1}{2}=\dfrac{x+1}{3}\) où \(x\in\mathbb{R}\).
-
Existe-t-il une valeur de \(x\) pour laquelle \(A(x)\) est vraie ? Si oui, la déterminer.
-
Combien de telles valeurs existe-t-il ?
Quantificateurs et négation
Soit \(A(x)\) une fonction propositionnelle définie sur un ensemble \(E\). On pose : \(A=\{x\in E\,/\, A(x) \text{ est vraie}\}\).
Proposition
-
Quantificateur universel. Si \(A=E\), on dit que tous les éléments de \(E\) vérifient \(A(x)\) et l’on écrit :
\[(\forall x\in E),\ A(x).\]
Le symbole \(\forall\) se lit « pour tout » ou « quel que soit ». -
Quantificateur existentiel. Si \(A\neq \emptyset\), on dit qu’il existe au moins un élément de \(E\) vérifiant \(A(x)\) et l’on écrit :
\[(\exists x\in E),\ A(x).\]
Le symbole \(\exists\) se lit « il existe (au moins) ». Le symbole \(\exists !\) se lit « il existe un unique ». -
Négation. On a les deux règles fondamentales suivantes :
\[\overline{(\forall x\in E,\ A(x))} \Leftrightarrow (\exists x\in E,\ \overline{A(x)}) \qquad \text{et} \qquad \overline{(\exists x\in E,\ A(x))} \Leftrightarrow (\forall x\in E,\ \overline{A(x)}).\] -
Permutation. On peut permuter deux quantificateurs de même nature (\(\forall \forall\) ou \(\exists \exists\)). En revanche, \((\forall y)(\exists x)\,p(x,y)\) et \((\exists x)(\forall y)\,p(x,y)\) ne sont pas équivalentes : dans la première, \(x\) peut dépendre de \(y\) ; dans la seconde, \(x\) est fixé indépendamment de \(y\).
Exemple
Pour chacune des propositions suivantes :
-
donner sa valeur de vérité ;
-
écrire sa négation.
-
\((\forall x\in\mathbb{R}),\ x^{2}\geq 1\).
-
\((\forall n\in\mathbb{N}),\ n(n+1)\) est divisible par \(2\).
-
\((\exists x\in\mathbb{R}),\ x^{2}+1=0\).
-
\((\exists !\, x\in\mathbb{R}),\ x^{2}-6x+9=0\).
-
\((\forall x\in\mathbb{R})(\exists y\in\mathbb{R}),\ y<-x\).
-
\((\exists x\in\mathbb{R})(\forall y\in\mathbb{R}),\ y<-x\).
Application
-
Écrire à l’aide des quantificateurs :
-
Pour tout entier naturel \(n\), il existe un entier naturel \(k\) tel que \(n\leq k\).
-
Le carré de tout réel est positif.
-
\(f\) est une fonction numérique définie sur \(\mathbb{R}\) et constante.
-
-
Donner la négation de :
-
\((\forall x\in\mathbb{R}),\ x\geq 2 \Rightarrow x^{2}\geq 4\).
-
\((\forall a, b\in\mathbb{R}),\ (a^{2}+b^{2}\geq ab \text{ ou } a^{2}+1\neq a)\).
-
Exercice
Montrer que :
\[(\forall x\in\mathbb{R})(\exists y\in\,]-\infty;1[),\ 3x^{2}y - x + y = 0.\]
Lois logiques et méthodes de raisonnement
Définition
Une loi logique est une proposition construite à partir d’autres propositions liées par des connecteurs et qui est vraie indépendamment des valeurs de vérité de ses composantes.
Remarque
Schéma récapitulatif des méthodes de raisonnement. Pour démontrer une proposition mathématique, on dispose des techniques suivantes :
Raisonnement par déduction
Proposition
Le raisonnement par déduction consiste à appliquer la loi logique du modus ponens :
\[\big( p \wedge (p\Rightarrow q) \big) \Rightarrow q.\]
En d’autres termes, si \(p\) est vraie et si l’implication \(p\Rightarrow q\) est vraie, alors \(q\) est vraie.
Exemple
Démontrer par déduction les implications suivantes :
-
\(\forall x, y\in\mathbb{R},\ (0<x<2 \text{ et } 0<y<2) \Rightarrow \dfrac{1}{x}+\dfrac{1}{y}>1\).
-
\(\forall x\in\mathbb{R}^{+},\ \dfrac{1}{1+\sqrt{x}}=1-\sqrt{x} \Rightarrow x=0\).
Application
Montrer que pour tous réels \(a\) et \(b\) :
\[a^{2}+b^{2}=1 \Rightarrow |a+b|\leq \sqrt{2}.\]
(Indication : remarquer que \((a+b)^{2}\leq 2(a^{2}+b^{2})\).)
Exercice
-
Montrer que \(\forall (a, b)\in\mathbb{R}^{2},\ a^{2}+b^{2}=0 \Rightarrow a=b=0\).
-
Soient \(x, y\in\mathbb{R}^{+}\). Montrer que \(x+y+2=2\sqrt{x}+2\sqrt{y} \Rightarrow x=y=1\).
Raisonnement par contraposée
Proposition
L’implication \(\overline{q}\Rightarrow \overline{p}\) s’appelle la contraposée de l’implication \(p\Rightarrow q\), et l’on a :
\[(p\Rightarrow q) \Leftrightarrow (\overline{q}\Rightarrow \overline{p}).\]
Pour démontrer \(p\Rightarrow q\), il suffit donc de démontrer sa contraposée \(\overline{q}\Rightarrow \overline{p}\).
Exemple
Démontrer en utilisant la contraposée :
-
\(\forall x\in\mathbb{R}^{+},\ x\neq 4 \Rightarrow \sqrt{x}-1\neq \dfrac{x}{4}\).
-
\(\forall n\in\mathbb{N},\ n^{2}\text{ pair} \Rightarrow n\text{ pair}\).
Application
Soient \(x, y\in\mathbb{R}\). Montrer par contraposée que :
\[(x+1)(y-1)\neq (x-1)(y+1) \;\Longrightarrow\; x\neq y.\]
Exercice
-
Montrer que pour tout \(n\in\mathbb{N}\) : \(n^{2}\) est divisible par \(5 \Rightarrow n\) est divisible par \(5\).
-
Soit \(x, y\in\mathbb{R}\). Montrer que :
\[xy\neq 1 \text{ et } x\neq y \Rightarrow \dfrac{x}{x^{2}+x+1}\neq\dfrac{y}{y^{2}+y+1}.\]
Raisonnement par équivalence
Proposition
Pour montrer qu’une équivalence \(p\Leftrightarrow q\) est vraie, on peut :
-
soit établir une chaîne d’équivalences \(p\Leftrightarrow \cdots \Leftrightarrow q\) à l’aide de propriétés et d’opérations mathématiques ;
-
soit montrer que les deux implications \(p\Rightarrow q\) et \(q\Rightarrow p\) sont toutes les deux vraies.
Exemple
Démontrer les équivalences suivantes :
-
\(\forall x\in\mathbb{R},\ |x-1|<\dfrac{1}{2} \Leftrightarrow \dfrac{2}{5}<\dfrac{1}{x+1}<\dfrac{2}{3}\).
-
\(\forall (a, b)\in\mathbb{R}^{2},\ (a+b)^{2}=a^{2}+b^{2} \Leftrightarrow ab=0\).
Application
Soient \(a, b\in\mathbb{R}^{+}\). Montrer que :
\[a+b=0 \Leftrightarrow a=b=0.\]
Exercice
-
Montrer que \(\forall x\in[1;+\infty[,\ \dfrac{\sqrt{x-1}}{x}\leq \dfrac{1}{2}\).
-
Montrer que \(\forall x, y\in\mathbb{R},\ |x|+|y|=|x+y| \Leftrightarrow xy\geq 0\).
Raisonnement par disjonction des cas
Proposition
Pour montrer qu’une proposition du type \(\forall x\in E,\ p(x)\) est vraie, il suffit de partitionner \(E\) en plusieurs sous-ensembles et de montrer que \(p(x)\) est vraie sur chacun de ces sous-ensembles.
Exemple
Démontrer par disjonction des cas :
-
\(\forall x\in\mathbb{R},\ |x-1|\leq x^{2}-x+1\).
-
\(\forall x\in\mathbb{R},\ \sqrt{x^{2}+1}+x>0\).
Application
Soit \(x\in\mathbb{R}\). Montrer que :
\[|x|+|x-1|\geq 1.\]
Préciser pour quelles valeurs de \(x\) l’égalité a lieu.
Exercice
-
Montrer que \(n(n+1)(n+2)\) est multiple de \(3\) pour tout \(n\in\mathbb{N}\).
-
Résoudre dans \(\mathbb{R}\) l’équation \(x^{2}-|x-2|+5=0\).
Raisonnement par l’absurde
Proposition
Pour démontrer qu’une proposition \(p\) est vraie, on suppose qu’elle est fausse (c’est-à-dire que \(\overline{p}\) est vraie) et l’on cherche à aboutir à une contradiction avec un résultat connu ou avec une hypothèse.
Exemple
Démontrer par l’absurde :
-
Soit \(n\in\mathbb{N}\). On pose \(A=\dfrac{n+3}{n+5}\). Montrer que \(A\neq 1\).
-
Soit \(ABC\) un triangle et \(a>0\) tels que \(BC=3a\), \(CA=2a\) et \(AB=4a\). Montrer que \(ABC\) n’est pas un triangle rectangle.
Application
Montrer que \(\sqrt{2}\notin \mathbb{Q}\).
(Indication : supposer \(\sqrt{2}=\dfrac{p}{q}\) avec \(\mathrm{pgcd}(p,q)=1\), élever au carré et étudier la parité.)
Exercice
-
Soient \(a, b\in\mathbb{Q}\). Montrer que \(a-\sqrt{2}\,b=0 \Rightarrow a=b=0\).
-
Montrer que \(\forall n\in\mathbb{N}^{*},\ \sqrt{\dfrac{n}{n+1}}\notin\mathbb{Q}\).
Raisonnement par contre-exemple
Proposition
Pour montrer qu’une proposition de type \((\forall x\in E),\ p(x)\) est fausse, il suffit de trouver un élément \(x\) de \(E\) pour lequel \(p(x)\) est fausse. Un tel élément s’appelle un contre-exemple.
Exemple
Pour chaque proposition, donner sa valeur de vérité et fournir un contre-exemple si elle est fausse.
-
\(\forall x\in\mathbb{R},\ x^{2}+x-2=0\).
-
\(\forall x\in[-1;1],\ x^{2}\geq x\).
-
\(\forall (a, b)\in\mathbb{R}^{2},\ \sqrt{a^{2}+b^{2}}=a+b\).
Application
Étudier la valeur de vérité des propositions suivantes ; en cas de fausseté, donner un contre-exemple.
-
Tous les nombres premiers sont impairs.
-
\(\forall n\in\mathbb{N},\ n^{2}+n+1\) est premier.
-
\(\forall x, y\in\mathbb{R},\ \cos(x+y)=\cos(x)+\cos(y)\).
Exercice
Étudier la valeur de vérité des propositions suivantes ; en cas de fausseté, donner un contre-exemple.
-
Tous les nombres impairs sont premiers.
-
\(\forall x, y\in\mathbb{R},\ 2x+4y=5\).
-
\(\forall x\in\mathbb{R}, \exists y\in\mathbb{R} : x^{2}-xy+y^{2}=0\).
Raisonnement par récurrence
Proposition
Soit \(p(n)\) une fonction propositionnelle définie sur \(\mathbb{N}\) et \(n_{0}\in\mathbb{N}\). Pour démontrer que la proposition \((\forall n\geq n_{0}),\ p(n)\) est vraie, on procède en trois étapes :
-
Initialisation : on vérifie que \(p(n_{0})\) est vraie.
-
Hérédité : on suppose que \(p(n)\) est vraie pour un certain \(n\geq n_{0}\) (hypothèse de récurrence), et l’on démontre que \(p(n+1)\) est alors vraie.
-
Conclusion : d’après le principe de récurrence, \(p(n)\) est vraie pour tout \(n\geq n_{0}\).
Exemple
Démontrer par récurrence :
-
\(\forall n\in\mathbb{N}^{*},\ \displaystyle\sum_{k=1}^{n}k = \dfrac{n(n+1)}{2}\).
-
Soit \(a\in\mathbb{R}^{+}\). Montrer que \(\forall n\in\mathbb{N},\ (1+a)^{n}\geq 1+na\).
-
\(\forall n\in\mathbb{N},\ 7\) divise \(2^{3n+2}-4\).
Application
Démontrer par récurrence que :
\[\forall n\in\mathbb{N}^{*},\ \displaystyle\sum_{k=1}^{n}k^{2}=\dfrac{n(n+1)(2n+1)}{6}.\]
Exercice
Démontrer par récurrence :
-
\(\forall n\in\mathbb{N}^{*},\ 3^{1}+3^{2}+\cdots+3^{n}=\dfrac{3^{n+1}-3}{2}\).
-
\(\forall n\in\mathbb{N},\ 1+3+\cdots+(2n+1)=(n+1)^{2}\).
-
\(\forall n\in\mathbb{N},\ 3^{n}\geq 2n+1\).
-
\(\forall n\in\mathbb{N}^{*},\ \dfrac{1}{1\times 2}+\dfrac{1}{2\times 3}+\cdots+\dfrac{1}{n(n+1)}=\dfrac{n}{n+1}\).