Notions de logique – exercices corrigés 1Bac

Une proposition est un énoncé qui a un sens et qui peut être vrai ou faux (mais pas les deux en même temps).

Ses deux valeurs de vérité possibles sont :

• V (vrai) ou 1
• F (faux) ou 0

Exemple : « \(-2 \in \mathbb{N}\) » est une proposition fausse.
« \(\forall x \in \mathbb{R}, x^2 \ge 0\) » est une proposition vraie.

Une fonction propositionnelle est une expression contenant une ou plusieurs variables appartenant à des ensembles déterminés.

Si on remplace les variables par des éléments de ces ensembles, elle devient une proposition (vraie ou fausse).

Exemple tiré du cours : \(T : x \in \mathbb{R} ; x^2 – 1 = 0\)

• Pour \(x = 1\) ou \(x = -1\), \(T\) devient une proposition vraie.
• Pour les autres valeurs de \(\mathbb{R}\), \(T\) devient une proposition fausse.

Soient \(P\) et \(Q\) deux propositions :

• Conjonction : \(P \land Q\) (\(P\) et \(Q\)) est vraie si et seulement si \(P\) et \(Q\) sont toutes les deux vraies.
• Disjonction : \(P \lor Q\) (\(P\) ou \(Q\)) est fausse si et seulement si \(P\) et \(Q\) sont toutes les deux fausses.

Pour toutes propositions \(P\) et \(Q\) :

En français :

• La négation de « P et Q » est « non P ou non Q ».
• La négation de « P ou Q » est « non P et non Q ».

L’implication \(P \Rightarrow Q\) est fausse uniquement lorsque \(P\) est vraie et \(Q\) est fausse. Dans tous les autres cas, elle est vraie.

• Quantificateur universel \(\forall\) : « pour tout » ou « quel que soit »
  La proposition \((\forall x \in E) : P(x)\) est vraie lorsque \(P(x)\) est vraie pour tout \(x\) de \(E\).
• Quantificateur existentiel \(\exists\) : « il existe au moins un »
  La proposition \((\exists x \in E) : P(x)\) est vraie lorsqu’il existe au moins un \(x\) dans \(E\) tel que \(P(x)\) soit vraie.
• Quantificateur d’unicité \(\exists!\) : « il existe un unique »
  La proposition \(\exists! x \in E; P(x)\) est vraie s’il existe un seul \(x\) dans \(E\) tel que \(P(x)\) soit vraie.

Exemples :

• \((\forall x \in \mathbb{R}) : x^2 \ge 0\) est une proposition vraie.
• \((\exists x \in \mathbb{R}) : 3x + 6 = 0\) est une proposition vraie (car \(x = -2\) convient).
• \(\exists! x \in \mathbb{R} ; x^2 – 1 = 0\) est une proposition fausse (car deux solutions : 1 et -1).

Négation des quantificateurs :

L’équivalence de deux propositions \(P\) et \(Q\), notée \(P \Leftrightarrow Q\), est définie par :

Table de vérité :

Exemple : \((x^2 + y^2 = 2xy) \Leftrightarrow (x = y)\) est une équivalence vraie.

Principe : Si \(P\) et \((P \Rightarrow Q)\) sont vraies, alors \(Q\) est vraie.

C’est le principe du modus ponens (syllogisme).

Exemple tiré du cours : Pour montrer que \(\forall x \in \mathbb{R}_+^* : x + \frac{1}{x} \ge 2\), on utilise :

• On a \((\sqrt{x} – \frac{1}{\sqrt{x}})^2 \ge 0\) (proposition vraie)
• \((\sqrt{x} – \frac{1}{\sqrt{x}})^2 \ge 0 \Rightarrow x + \frac{1}{x} \ge 2\)
• Donc \(x + \frac{1}{x} \ge 2\) est vraie.

Principe : On établit l’équivalence \(P \Leftrightarrow Q\) à l’aide d’une chaîne d’équivalences successives.

On transforme \(P\) en \(Q\) en passant par des propositions intermédiaires \(P \Leftrightarrow P_1 \Leftrightarrow P_2 \Leftrightarrow \cdots \Leftrightarrow Q\).

Exemple tiré du cours : Pour montrer \(x + y + 13 = 4\sqrt{x} + 6\sqrt{y} \Leftrightarrow x = 4 \text{ et } y = 9\) :

Principe : Pour montrer que \((\forall x \in E) : P(x)\) est vraie, on montre que \(P(x)\) est vraie pour une partie \(A\) de \(E\), puis que \(P(x)\) est vraie pour les \(x\) n’appartenant pas à \(A\).

Exemple tiré du cours : Pour montrer que \(\forall n \in \mathbb{N}\), \(n^2 + n + 1\) est impair :

• Cas 1 : \(n\) pair (\(n = 2k\)) → \(n^2 + n + 1 = 2(2k^2 + k) + 1\) (impair)
• Cas 2 : \(n\) impair (\(n = 2k + 1\)) → \(n^2 + n + 1 = 2(2k^2 + 3k + 1) + 1\) (impair)
• Conclusion : Dans tous les cas, \(n^2 + n + 1\) est impair.

Principe : Pour montrer que \(P \Rightarrow Q\) est vraie, on montre sa contraposée \(\overline{Q} \Rightarrow \overline{P}\) qui lui est logiquement équivalente.

Exemple tiré du cours : Pour montrer \((x \neq 0) \Rightarrow (\sqrt{x+1} \neq 1 + \frac{x}{2})\) :

• On montre sa contraposée : \((\sqrt{x+1} = 1 + \frac{x}{2}) \Rightarrow (x = 0)\)

Principe : Pour montrer qu’une proposition \(P\) est vraie, on suppose que \(P\) est fausse (c’est-à-dire \(\overline{P}\) vraie) et on montre que cela conduit à une contradiction (une proposition toujours fausse).

Exemple tiré du cours : Montrer que \(\forall x \in \mathbb{R} – \{\frac{2}{3}\} : \frac{4x+1}{3x-2} \neq \frac{4}{3}\) :

• On suppose qu’il existe \(x\) tel que \(\frac{4x+1}{3x-2} = \frac{4}{3}\)
• Alors \(3(4x+1) = 4(3x-2) \Rightarrow 12x + 3 = 12x – 8 \Rightarrow 3 = 8\) (contradiction)
• Donc l’hypothèse est fausse, la proposition initiale est vraie.

Principe : Soit \(n \in \mathbb{N}\) et \(n_0\) un entier naturel fixé. Pour montrer que la proposition \((\forall n \ge n_0) : P(n)\) est vraie, on montre :

1. Initialisation : \(P(n_0)\) est vraie.
2. Hérédité : \((\forall n \ge n_0) : (P(n) \Rightarrow P(n+1))\) est vraie.

Exemple tiré du cours : Montrer que \(\forall n \in \mathbb{N}^* : 7^n – 2^n\) est divisible par 5 :

• Initialisation : Pour \(n = 1\), \(7^1 – 2^1 = 5\) divisible par 5.
• Hérédité : Si \(7^n – 2^n = 5k\), alors \(7^{n+1} – 2^{n+1} = 5(7k + 2^n)\) divisible par 5.
• Conclusion : La propriété est vraie pour tout \(n \in \mathbb{N}^*\).

Principe : Pour montrer qu’une proposition universelle \((\forall x \in E) : P(x)\) est fausse, il suffit de trouver un contre-exemple, c’est-à-dire un élément \(a \in E\) tel que \(P(a)\) soit fausse.

Cela revient à montrer que sa négation \((\exists x \in E) : \overline{P(x)}\) est vraie.

Exemple tiré du cours : La proposition \((\forall x \in \mathbb{R}) : \sqrt{x^2} = x\) est fausse car pour \(x = -1\) :

• \(\sqrt{(-1)^2} = \sqrt{1} = 1 \neq -1\)
• Donc \(x = -1\) est un contre-exemple.

Remarque : La bonne propriété est \((\forall x \in \mathbb{R}) : \sqrt{x^2} = |x|\).