Exercices corrigés – Quantificateurs et connecteurs logiques
Exercice 1 : Quantificateurs et Propositions Logiques
Soit la proposition : \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R} : x^2 + y^2 = 1\). Déterminez si cette proposition est vraie ou fausse. Justifiez votre réponse.
Écrivez la négation de la proposition suivante en utilisant les quantificateurs : \(\exists x \in \mathbb{N}, \forall y \in \mathbb{N} : x > y\)
Considérez l’ensemble \(A = \{1, 2, 3, 4\}\). Évaluez la valeur de vérité de : \(\forall x \in A, \exists y \in A : x + y = 5\)
Transformez la phrase suivante en expression logique avec quantificateurs : « Pour tout nombre réel positif, il existe un nombre réel plus petit que lui ».
Démontrez que les propositions \(\forall x \exists y P(x,y)\) et \(\exists y \forall x P(x,y)\) ne sont pas logiquement équivalentes.
Solution
La proposition \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R} : x^2 + y^2 = 1\) est vraie. En effet, pour tout réel \(x\), on peut trouver un réel \(y\) tel que \(x^2 + y^2 = 1\). Par exemple, si on choisit \(y = \sqrt{1 – x^2}\) (ou \(y = -\sqrt{1 – x^2}\)), on a bien \(x^2 + (\sqrt{1 – x^2})^2 = x^2 + 1 – x^2 = 1\). Donc, pour tout \(x\), il existe un \(y\) qui satisfait l’équation.
La négation de la proposition \(\exists x \in \mathbb{N}, \forall y \in \mathbb{N} : x > y\) est \(\forall x \in \mathbb{N}, \exists y \in \mathbb{N} : x \leq y\). En d’autres termes, pour tout entier naturel \(x\), il existe un entier naturel \(y\) tel que \(x\) soit inférieur ou égal à \(y\).
Pour l’ensemble \(A = \{1, 2, 3, 4\}\), la proposition \(\forall x \in A, \exists y \in A : x + y = 5\) est vraie. On peut vérifier pour chaque \(x\) dans \(A\):
– Si \(x = 1\), on peut choisir \(y = 4\) car \(1 + 4 = 5\).
– Si \(x = 2\), on peut choisir \(y = 3\) car \(2 + 3 = 5\).
– Si \(x = 3\), on peut choisir \(y = 2\) car \(3 + 2 = 5\).
– Si \(x = 4\), on peut choisir \(y = 1\) car \(4 + 1 = 5\).
Comme on trouve un \(y\) pour chaque \(x\), la proposition est vraie.
La phrase « Pour tout nombre réel positif, il existe un nombre réel plus petit que lui » peut être exprimée comme : \(\forall x \in \mathbb{R}^+, \exists y \in \mathbb{R} : y < x\). Ici, \(\mathbb{R}^+\) représente l'ensemble des nombres réels positifs.
Pour démontrer que les propositions \(\forall x \exists y P(x,y)\) et \(\exists y \forall x P(x,y)\) ne sont pas logiquement équivalentes, considérons un exemple concret. Soit \(P(x, y)\) la proposition « x est ami avec y » dans un ensemble de personnes.
– La proposition \(\forall x \exists y P(x,y)\) signifie « Pour toute personne \(x\), il existe une personne \(y\) telle que \(x\) est ami avec \(y\). Cela signifie que chacun a au moins un ami.
– La proposition \(\exists y \forall x P(x,y)\) signifie « Il existe une personne \(y\) telle que pour toute personne \(x\), \(y\) est ami avec \(x\). Cela signifie qu’il existe une personne qui est amie avec tout le monde.
Il est clair que ces deux propositions ne sont pas équivalentes. La première ne dit rien sur l’existence d’une personne qui est amie avec tout le monde, tandis que la seconde implique que la personne \(y\) est amie avec tout le monde, ce qui est beaucoup plus fort. Par conséquent, \(\forall x \exists y P(x,y)\) et \(\exists y \forall x P(x,y)\) ne sont pas logiquement équivalentes.
Exercice 2 : Connecteurs Logiques et Tables de Vérité
Construisez la table de vérité de l’expression : \((p \rightarrow q) \wedge (\neg p \vee q)\)
Montrez que les expressions \(p \rightarrow q\) et \(\neg p \vee q\) sont logiquement équivalentes.
Soit \(p\), \(q\) et \(r\) trois propositions. Démontrez que : \((p \wedge q) \rightarrow r \equiv p \rightarrow (q \rightarrow r)\)
Déterminez si la formule suivante est une tautologie : \((p \rightarrow q) \rightarrow ((q \rightarrow r) \rightarrow (p \rightarrow r))\)
Solution
Voici la table de vérité de l’expression \((p \rightarrow q) \wedge (\neg p \vee q)\) :
\[
\begin{array}{|c|c|c|c|c|c|}
\hline
p & q & \neg p & p \rightarrow q & \neg p \vee q & (p \rightarrow q) \wedge (\neg p \vee q) \\
\hline
V & V & F & V & V & V \\
\hline
V & F & F & F & F & F \\
\hline
F & V & V & V & V & V \\
\hline
F & F & V & V & V & V \\
\hline
\end{array}
\]
On observe que l’expression est vraie dans tous les cas sauf lorsque \(p\) est vrai et \(q\) est faux.
Pour montrer que \(p \rightarrow q\) et \(\neg p \vee q\) sont logiquement équivalentes, on peut utiliser leur table de vérité :
\[
\begin{array}{|c|c|c|c|c|}
\hline
p & q & \neg p & p \rightarrow q & \neg p \vee q \\
\hline
V & V & F & V & V \\
\hline
V & F & F & F & F \\
\hline
F & V & V & V & V \\
\hline
F & F & V & V & V \\
\hline
\end{array}
\]
Comme les colonnes de \(p \rightarrow q\) et \(\neg p \vee q\) sont identiques, les deux expressions sont logiquement équivalentes.
Pour démontrer que \((p \wedge q) \rightarrow r \equiv p \rightarrow (q \rightarrow r)\), on peut utiliser une table de vérité :
\[
\begin{array}{|c|c|c|c|c|c|c|}
\hline
p & q & r & p \wedge q & (p \wedge q) \rightarrow r & q \rightarrow r & p \rightarrow (q \rightarrow r) \\
\hline
V & V & V & V & V & V & V \\
\hline
V & V & F & V & F & F & F \\
\hline
V & F & V & F & V & V & V \\
\hline
V & F & F & F & V & V & V \\
\hline
F & V & V & F & V & V & V \\
\hline
F & V & F & F & V & F & V \\
\hline
F & F & V & F & V & V & V \\
\hline
F & F & F & F & V & V & V \\
\hline
\end{array}
\]
Les colonnes \((p \wedge q) \rightarrow r\) et \(p \rightarrow (q \rightarrow r)\) sont identiques, donc les deux expressions sont équivalentes.
Pour simplifier l’expression \((p \vee q) \wedge (p \vee \neg q) \wedge (\neg p \vee q)\), on peut procéder comme suit :
– On remarque que \((p \vee q) \wedge (p \vee \neg q)\) est équivalent à \(p\) car :
– Si \(p\) est vrai, \(p \vee q\) et \(p \vee \neg q\) sont tous les deux vrais, donc leur intersection est vraie.
– Si \(p\) est faux, alors soit \(q\) est vrai, soit \(\neg q\) est vrai. Dans le premier cas, \(p \vee q\) est faux et dans le second, \(p \vee \neg q\) est faux. Dans les deux cas, leur intersection est fausse.
– Donc, l’expression devient \(p \wedge (\neg p \vee q)\).
– On remarque que \(p \wedge (\neg p \vee q)\) est équivalent à \(p \wedge q\) car :
– Si \(p\) est faux, \(p \wedge (\neg p \vee q)\) est faux.
– Si \(p\) est vrai, alors \(p \wedge (\neg p \vee q)\) est équivalent à \(p \wedge q\).
– Donc, l’expression simplifiée est \(p \wedge q\).
Pour déterminer si la formule \((p \rightarrow q) \rightarrow ((q \rightarrow r) \rightarrow (p \rightarrow r))\) est une tautologie, on peut utiliser une table de vérité :
\[
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
p & q & r & p \rightarrow q & q \rightarrow r & p \rightarrow r & (q \rightarrow r) \rightarrow (p \rightarrow r) & (p \rightarrow q) \rightarrow ((q \rightarrow r) \rightarrow (p \rightarrow r)) \\
\hline
V & V & V & V & V & V & V & V \\
\hline
V & V & F & V & F & F & V & V \\
\hline
V & F & V & F & V & V & V & V \\
\hline
V & F & F & F & V & F & F & V \\
\hline
F & V & V & V & V & V & V & V \\
\hline
F & V & F & V & F & V & V & V \\
\hline
F & F & V & V & V & V & V & V \\
\hline
F & F & F & V & V & V & V & V \\
\hline
\end{array}
\]
Toutes les valeurs de la dernière colonne sont vraies, donc la formule est une tautologie. Cette tautologie est un principe important de la logique appelé « syllogisme ».
Exercice 3 : Logique du Premier Ordre
Formalisez en logique du premier ordre : « Tous les nombres premiers supérieurs à 2 sont impairs ».
Soit \(P(x)\) : « x est pair » et \(Q(x)\) : « x est divisible par 4 ». Exprimez en logique du premier ordre : « Tout nombre pair n’est pas nécessairement divisible par 4 ».
Donnez la négation de : \(\forall x \in \mathbb{R}, (x > 0 \rightarrow \exists y \in \mathbb{R} : y^2 = x)\)
Soient \(P(x,y)\) : « x aime y » et \(Q(x)\) : « x est heureux ». Formalisez : « Toute personne qui aime quelqu’un est heureuse ».
Prouvez que \(\forall x (P(x) \vee Q(x)) \not\equiv (\forall x P(x)) \vee (\forall x Q(x))\)
Solution
La formalisation en logique du premier ordre de « Tous les nombres premiers supérieurs à 2 sont impairs » est :
\[\forall x \in \mathbb{N}, (\text{estPremier}(x) \wedge x > 2) \rightarrow \text{estImpair}(x)\]
où \(\text{estPremier}(x)\) est une proposition qui est vraie si et seulement si \(x\) est un nombre premier, et \(\text{estImpair}(x)\) est une proposition qui est vraie si et seulement si \(x\) est impair.
Si \(P(x)\) : « x est pair » et \(Q(x)\) : « x est divisible par 4 », l’expression « Tout nombre pair n’est pas nécessairement divisible par 4 » peut être formalisée comme :
\[\forall x \in \mathbb{N}, P(x) \nrightarrow Q(x)\]
ou, de manière équivalente, en utilisant la négation de l’implication :
\[\exists x \in \mathbb{N}, P(x) \wedge \neg Q(x)\]
Cela signifie qu’il existe au moins un nombre pair qui n’est pas divisible par 4.
La négation de \(\forall x \in \mathbb{R}, (x > 0 \rightarrow \exists y \in \mathbb{R} : y^2 = x)\) est :
\[\exists x \in \mathbb{R}, \neg (x > 0 \rightarrow \exists y \in \mathbb{R} : y^2 = x)\]
En utilisant la règle de négation de l’implication (\(\neg (p \rightarrow q) \equiv p \wedge \neg q\)), on obtient :
\[\exists x \in \mathbb{R}, (x > 0 \wedge \forall y \in \mathbb{R}, y^2 \neq x)\]
Cela signifie qu’il existe un nombre réel strictement positif qui n’est pas le carré d’aucun nombre réel.
Si \(P(x,y)\) : « x aime y » et \(Q(x)\) : « x est heureux », la phrase « Toute personne qui aime quelqu’un est heureuse » peut être formalisée comme :
\[\forall x, (\exists y, P(x,y)) \rightarrow Q(x)\]
Cela signifie que pour toute personne \(x\), si \(x\) aime quelqu’un (\(y\)), alors \(x\) est heureux.
Pour prouver que \(\forall x (P(x) \vee Q(x)) \not\equiv (\forall x P(x)) \vee (\forall x Q(x))\), on peut utiliser un contre-exemple. Soit l’ensemble \(A = \{1, 2\}\), et définissons \(P(x)\) et \(Q(x)\) comme suit :
\[
\begin{array}{|c|c|c|}
\hline
x & P(x) & Q(x) \\
\hline
1 & Vrai & Faux \\
\hline
2 & Faux & Vrai \\
\hline
\end{array}
\]
Vérifions les deux expressions :
– \(\forall x \in A, (P(x) \vee Q(x))\) est vrai car :
– Pour \(x = 1\), \(P(1) \vee Q(1)\) est vrai (\(Vrai \vee Faux\)).
– Pour \(x = 2\), \(P(2) \vee Q(2)\) est vrai (\(Faux \vee Vrai\)).
– \((\forall x \in A, P(x)) \vee (\forall x \in A, Q(x))\) est faux car :
– \(\forall x \in A, P(x)\) est faux car \(P(2)\) est faux.
– \(\forall x \in A, Q(x)\) est faux car \(Q(1)\) est faux.
– Donc, \(Faux \vee Faux\) est faux.
Comme l’une des expressions est vraie et l’autre fausse, elles ne sont pas équivalentes. On a donc bien prouvé que \(\forall x (P(x) \vee Q(x)) \not\equiv (\forall x P(x)) \vee (\forall x Q(x))\).
Exercice 4 : Preuves et Réfutations
Prouvez par contradiction que \(\sqrt{2}\) est irrationnel en utilisant la logique des prédicats.
Démontrez que si \(\forall x (P(x) \rightarrow Q(x))\) et \(\exists x P(x)\) sont vrais, alors \(\exists x Q(x)\) est vrai.
Soit \(R\) une relation binaire sur un ensemble \(E\). Exprimez la transitivité de \(R\) en utilisant les quantificateurs.
Prouvez que \(\forall x \exists y P(x,y)\) n’implique pas \(\exists y \forall x P(x,y)\) en construisant un contre-exemple.
Démontrez que \(\forall x (P(x) \wedge Q(x)) \equiv (\forall x P(x)) \wedge (\forall x Q(x))\)
Solution
Pour prouver par contradiction que \(\sqrt{2}\) est irrationnel, supposons le contraire, c’est-à-dire que \(\sqrt{2}\) est rationnel. Alors, il existe deux entiers naturels \(a\) et \(b\) (avec \(b \neq 0\)) tels que \(\sqrt{2} = \frac{a}{b}\) et \(a\) et \(b\) sont premiers entre eux (c’est-à-dire que leur seul diviseur commun est 1). En élevant les deux côtés de l’équation au carré, on obtient \(2 = \frac{a^2}{b^2}\), ce qui implique \(a^2 = 2b^2\). Cela signifie que \(a^2\) est pair, et donc \(a\) est pair (puisque le carré d’un nombre impair est impair). Si \(a\) est pair, on peut écrire \(a = 2k\) pour un certain entier naturel \(k\). En substituant dans l’équation \(a^2 = 2b^2\), on obtient \(4k^2 = 2b^2\), ce qui simplifie en \(2k^2 = b^2\). Cela montre que \(b^2\) est pair, et donc \(b\) est pair. Maintenant, nous avons prouvé que \(a\) et \(b\) sont tous les deux pairs, ce qui contredit notre hypothèse initiale que \(a\) et \(b\) sont premiers entre eux. Par conséquent, notre supposition que \(\sqrt{2}\) est rationnel est fausse, et donc \(\sqrt{2}\) est irrationnel.
Soit \(x_0\) un élément de l’ensemble pour lequel \(P(x_0)\) est vrai (tel qu’assuré par \(\exists x P(x)\)). Puisque \(\forall x (P(x) \rightarrow Q(x))\) est vrai, cela implique que pour tout \(x\), si \(P(x)\) est vrai, alors \(Q(x)\) est vrai. En particulier, pour \(x = x_0\), \(P(x_0)\) étant vrai, \(Q(x_0)\) doit également être vrai. Par conséquent, il existe un élément \(x_0\) (à savoir le même \(x_0\) que ci-dessus) tel que \(Q(x_0)\) est vrai, ce qui prouve que \(\exists x Q(x)\) est vrai.
La transitivité de la relation binaire \(R\) sur l’ensemble \(E\) peut être exprimée comme suit : \(\forall x \in E, \forall y \in E, \forall z \in E, (R(x,y) \wedge R(y,z)) \rightarrow R(x,z)\). Cela signifie que pour tous éléments \(x\), \(y\) et \(z\) de l’ensemble \(E\), si \(x\) est en relation avec \(y\) et \(y\) est en relation avec \(z\), alors \(x\) est en relation avec \(z\).
Pour montrer que \(\forall x \exists y P(x,y)\) n’implique pas \(\exists y \forall x P(x,y)\), considérons l’ensemble des entiers naturels \(\mathbb{N}\) et définissons la propriété \(P(x,y)\) comme « x est plus petit que y ». Pour tout entier naturel \(x\), il existe un entier naturel \(y\) (par exemple, \(y = x + 1\)) tel que \(P(x,y)\) est vrai (car \(x\) est plus petit que \(x + 1\)). Donc, \(\forall x \exists y P(x,y)\) est vrai. Cependant, il n’existe pas un seul entier naturel \(y\) qui soit plus grand que tous les entiers naturels \(x\). Donc, \(\exists y \forall x P(x,y)\) est faux. Cela prouve que \(\forall x \exists y P(x,y)\) n’implique pas \(\exists y \forall x P(x,y)\).
Pour prouver que \(\forall x (P(x) \wedge Q(x)) \equiv (\forall x P(x)) \wedge (\forall x Q(x))\), nous allons montrer que les deux expressions ont la même valeur de vérité dans tous les cas.
**Sens direct** : Supposons que \(\forall x (P(x) \wedge Q(x))\) est vrai. Cela signifie que pour tout \(x\), \(P(x)\) et \(Q(x)\) sont tous les deux vrais. Donc, \(\forall x P(x)\) est vrai et \(\forall x Q(x)\) est vrai. Par conséquent, \((\forall x P(x)) \wedge (\forall x Q(x))\) est vrai.
**Sens inverse** : Supposons que \((\forall x P(x)) \wedge (\forall x Q(x))\) est vrai. Cela signifie que \(\forall x P(x)\) est vrai et \(\forall x Q(x)\) est vrai. Donc, pour tout \(x\), \(P(x)\) est vrai et \(Q(x)\) est vrai. Par conséquent, pour tout \(x\), \(P(x) \wedge Q(x)\) est vrai, ce qui implique que \(\forall x (P(x) \wedge Q(x))\) est vrai.
Comme les deux sens sont prouvés, nous avons montré que \(\forall x (P(x) \wedge Q(x)) \equiv (\forall x P(x)) \wedge (\forall x Q(x))\).
Exercice 5 : Applications Avancées
Soit \(f : \mathbb{R} \rightarrow \mathbb{R}\) une fonction. Exprimez la continuité de \(f\) en \(a\) en utilisant les quantificateurs.
Formalisez le principe de récurrence mathématique en utilisant la logique du premier ordre.
Exprimez l’unicité d’un élément neutre dans un groupe en utilisant les quantificateurs.
Démontrez que dans un ensemble ordonné, si \(\forall x \exists y (x < y)\), alors l'ensemble est infini.
Soit \(R\) une relation d’équivalence sur un ensemble \(E\). Exprimez la propriété de partition des classes d’équivalence en utilisant les quantificateurs.
Solution
La continuité de la fonction \(f\) en un point \(a \in \mathbb{R}\) peut être exprimée en utilisant les quantificateurs comme suit :
\[\forall \epsilon > 0, \exists \delta > 0, \forall x \in \mathbb{R}, |x – a| < \delta \rightarrow |f(x) - f(a)| < \epsilon\]
Cela signifie que pour tout \(\epsilon\) strictement positif, il existe un \(\delta\) strictement positif tel que pour tout \(x\) réel, si la distance entre \(x\) et \(a\) est inférieure à \(\delta\), alors la distance entre \(f(x)\) et \(f(a)\) est inférieure à \(\epsilon\).
Le principe de récurrence mathématique peut être formalisé en logique du premier ordre comme suit :
\[\forall P \subset \mathbb{N}, (0 \in P \wedge \forall n \in \mathbb{N}, n \in P \rightarrow n+1 \in P) \rightarrow P = \mathbb{N}\]
Cela signifie que pour tout sous-ensemble \(P\) de l’ensemble des entiers naturels \(\mathbb{N}\), si \(0\) appartient à \(P\) et pour tout \(n\) appartenant à \(\mathbb{N}\), si \(n\) appartient à \(P\) alors \(n+1\) appartient à \(P\), alors \(P\) est égal à l’ensemble des entiers naturels \(\mathbb{N}\).
L’unicité d’un élément neutre \(e\) dans un groupe peut être exprimée en utilisant les quantificateurs comme suit :
\[(\exists e \in G, \forall x \in G, ex = xe = x) \wedge (\forall e’, e » \in G, (\forall x \in G, e’x = xe’ = x \wedge e »x = xe » = x) \rightarrow e’ = e »)\]
Cela signifie qu’il existe un élément \(e\) dans le groupe \(G\) tel que pour tout élément \(x\) de \(G\), la multiplication de \(e\) par \(x\) (à gauche ou à droite) donne \(x\), et de plus, si deux éléments \(e’\) et \(e »\) de \(G\) ont cette propriété, alors \(e’\) est égal à \(e »\).
Pour démontrer qu’un ensemble ordonné \(E\) est infini si \(\forall x \exists y (x < y)\), supposons que \(E\) est fini. Un ensemble fini a un plus grand élément, notons-le \(M\). Par hypothèse, pour tout \(x\) dans \(E\), il existe \(y\) dans \(E\) tel que \(x < y\). En particulier, pour \(x = M\), il existe \(y\) dans \(E\) tel que \(M < y\). Mais cela contredit la définition de \(M\) comme étant le plus grand élément. Donc, notre supposition que \(E\) est fini est fausse, et donc \(E\) est infini.
La propriété de partition des classes d’équivalence d’une relation d’équivalence \(R\) sur un ensemble \(E\) peut être exprimée en utilisant les quantificateurs comme suit :
\[\forall x \in E, \exists! y \in E, xRy \wedge (\forall z \in E, (zRx \vee zRy) \rightarrow z = x \vee z = y)\]
Cela signifie que pour tout élément \(x\) de \(E\), il existe un unique élément \(y\) de \(E\) tel que \(x\) est en relation avec \(y\) par \(R\), et de plus, pour tout élément \(z\) de \(E\), si \(z\) est en relation avec \(x\) ou \(z\) est en relation avec \(y\), alors \(z\) est soit égal à \(x\), soit égal à \(y\). Cela garantit que les classes d’équivalence forment une partition de \(E\), c’est-à-dire que chaque élément de \(E\) appartient à une unique classe d’équivalence et que l’union de toutes les classes d’équivalence est égale à \(E\).
