Propositions et connecteurs logiques
Proposition et fonction propositionnelle
• Une proposition (ou assertion) est un énoncé mathématique qui a un sens logique et auquel on peut attribuer une et une seule valeur de vérité : soit vrai (noté V ou 1), soit faux (noté F ou 0).
• Une fonction propositionnelle (ou prédicat) est un énoncé contenant une ou plusieurs variables appartenant à un ensemble $E$. Elle devient une proposition dont on peut déterminer la valeur de vérité chaque fois que l'on remplace les variables par des éléments spécifiques de $E$.
Déterminer la valeur de vérité de chacune des propositions suivantes :
- $P : -6 \in \mathbb{N}$
- $Q : 1 < 3$
- $R : 1 + 1 = 0$
- $S : 2 \times 3 = 7$
L'énoncé $p(x) : \text{« } x \in \mathbb{R} \text{ ; } 2x + 1 = 0 \text{ »}$ est une fonction propositionnelle.
- Pour $x = -\frac{1}{2}$, la proposition $p\left(-\frac{1}{2}\right)$ est vraie.
- Pour $x = 0$, la proposition $p(0)$ est fausse.
Les connecteurs logiques
La négation d’une proposition
La négation d'une proposition $P$ est la proposition, notée $\text{non}(P)$ ou $\overline{P}$, qui est vraie si $P$ est fausse, et fausse si $P$ est vraie.
La conjonction (Le connecteur ET)
La conjonction de deux propositions $P$ et $Q$ est la proposition, notée $P \land Q$ (ou $P \text{ et } Q$), qui est vraie uniquement lorsque $P$ et $Q$ sont simultanément vraies.
La disjonction (Le connecteur OU)
La disjonction de deux propositions $P$ et $Q$ est la proposition, notée $P \lor Q$ (ou $P \text{ ou } Q$), qui est vraie si au moins l'une des deux propositions est vraie.
L’implication
L'implication de $Q$ par $P$ est la proposition, notée $P \implies Q$, qui est fausse uniquement lorsque $P$ est vraie et $Q$ est fausse.
La proposition $P \implies Q$ est logiquement équivalente à l'expression $\overline{P} \lor Q$.
L’équivalence
L'équivalence de deux propositions $P$ et $Q$ est la proposition, notée $P \iff Q$, qui est vraie lorsque $P$ et $Q$ ont la même valeur de vérité.
La proposition $P \iff Q$ est équivalente à la conjonction des deux implications : $(P \implies Q) \land (Q \implies P)$.
Lois logiques et règles de De Morgan
Quelles que soient les propositions $P$, $Q$ et $R$, les équivalences suivantes sont toujours vraies :
- $\overline{P \land Q} \iff \overline{P} \lor \overline{Q}$
- $\overline{P \lor Q} \iff \overline{P} \land \overline{Q}$
- Distributivité : $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$
- Distributivité : $P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$
Les quantificateurs
Quantificateur universel et existentiel
Soit $P(x)$ une fonction propositionnelle définie sur un ensemble $E$.
- Le quantificateur universel ($\forall$) : L'énoncé $\forall x \in E \,;\, P(x)$ signifie que la propriété $P(x)$ est vraie pour tous les éléments $x$ de $E$.
- Le quantificateur existentiel ($\exists$) : L'énoncé $\exists x \in E \,;\, P(x)$ signifie qu'il existe au moins un élément $x$ de $E$ pour lequel la propriété $P(x)$ est vraie.
- Le quantificateur d'unicité ($\exists!$) : L'énoncé $\exists! x \in E \,;\, P(x)$ signifie qu'il existe un unique élément $x$ de $E$ vérifiant la propriété $P(x)$.
Exprimer à l'aide des quantificateurs logiques les énoncés suivants :
- Pour tout nombre réel $x$, son carré est supérieur ou égal à zéro.
- Il existe un entier relatif $n$ tel que $n^2 – 2 = 0$.
- Tout entier naturel est inférieur ou égal à son carré.
Négation des quantificateurs
- La négation de l'assertion $\Big(\forall x \in E \,;\, P(x)\Big)$ est la proposition $\Big(\exists x \in E \,;\, \overline{P(x)}\Big)$.
- La négation de l'assertion $\Big(\exists x \in E \,;\, P(x)\Big)$ est la proposition $\Big(\forall x \in E \,;\, \overline{P(x)}\Big)$.
Écrire la négation des propositions suivantes puis préciser leur valeur de vérité :
- $A : (\forall x \in \mathbb{R}) \,;\, x^2 – x \ge 0$
- $B : (\exists x \in \mathbb{R}) \,;\, x^2 + 1 = 0$
- $C : (\forall x \in \mathbb{R}^+) \,;\, \sqrt{x} \ge 0$
Les types de raisonnements mathématiques
Raisonnement par contre-exemple
Pour prouver qu'une proposition de la forme $\forall x \in E \,;\, P(x)$ est fausse, il suffit de trouver un exemple $x_0 \in E$ tel que $P(x_0)$ soit fausse. Cet élément $x_0$ est appelé un contre-exemple.
Montrer que la proposition suivante est fausse :
\[ (\forall x \in \mathbb{R}) \,;\, x^2 > x \]
Raisonnement par contraposition
La règle de contraposition repose sur la loi logique selon laquelle l'implication $(P \implies Q)$ est équivalente à sa contraposée $(\overline{Q} \implies \overline{P})$.
\[ (P \implies Q) \iff (\overline{Q} \implies \overline{P}) \]
Soit $n \in \mathbb{N}$. En utilisant un raisonnement par contraposition, démontrer que :
\[ \text{Si } n^2 \text{ est impair, alors } n \text{ est impair.} \]
Raisonnement par l’absurde
Pour démontrer qu'une proposition $P$ est vraie, on suppose que sa négation $\overline{P}$ est vraie, puis on effectue des déductions logiques jusqu'à aboutir à une contradiction avec les hypothèses ou avec une propriété mathématique universellement établie.
Montrer par l'absurde que pour tout réel $x \in \mathbb{R}$ :
\[ \sqrt{x^2 + 1} + x > 0 \]
\textit{Hint : Supposer qu'il existe un réel $x$ tel que $\sqrt{x^2 + 1} + x \le 0$}
Raisonnement par disjonction des cas
Lorsque l'on veut démontrer une propriété $P(x)$ pour tout $x$ appartenant à un ensemble $E$, on peut partitionner $E$ en plusieurs sous-ensembles disjoints et valider séparément la propriété dans chacun de ces sous-ensembles (par exemple, étudier le cas où $x \ge 0$ et le cas où $x < 0$).
Démontrer que pour tout réel $x \in \mathbb{R}$ :
\[ |x – 1| \le x^2 – x + 1 \]
Solution :
- Premier cas : $x \ge 1$. Alors $|x-1| = x-1$. L'inéquation devient $x-1 \le x^2-x+1 \iff x^2-2x+2 \ge 0$. Le discriminant vaut $\Delta = -4 < 0$, donc l'expression est toujours strictement positive. Le cas est vérifié.
- Deuxième cas : $x < 1$. Alors $|x-1| = -(x-1) = -x+1$. L'inéquation s'écrit $-x+1 \le x^2-x+1 \iff x^2 \ge 0$, ce qui est toujours vrai pour tout réel $x$.
Raisonnement par équivalences successives
Pour démontrer qu'une proposition $P$ est vraie, on peut établir une chaîne d'équivalences successives reliant $P$ à une proposition $Q$ reconnue comme vraie :
\[ P \iff Q_1 \iff Q_2 \iff \dots \iff Q \]
Puisque la dernière proposition $Q$ est vraie, on en déduit que $P$ est vraie.
Montrer que pour tout réel positif $x \in \mathbb{R}^+$ :
\[ \sqrt{\frac{x^2 + 3x + 1}{5}} \ge \sqrt{x} \]
Raisonnement par récurrence
[Principe de récurrence]
Soit $P(n)$ une fonction propositionnelle définie sur l'ensemble des entiers naturels $\mathbb{N}$.
Pour prouver que $P(n)$ est vraie pour tout entier $n \ge n_0$, on effectue les trois étapes suivantes :
- Initialisation : On montre que la proposition est vraie pour le premier terme $n = n_0$.
- Hérédité : On suppose qu'il existe un entier fixé $n \ge n_0$ tel que $P(n)$ soit vraie (l'hypothèse de récurrence), et on démontre sous cette condition que $P(n+1)$ est vraie.
- Conclusion : La propriété $P(n)$ est déclarée vraie pour tout entier supérieur ou égal à $n_0$.
Montrer par récurrence que pour tout entier naturel $n \in \mathbb{N}$ :
\[ 2^n > n \]