Logique propositionnelle et quantificateurs

Quelle est la valeur de vérité de $P \Rightarrow Q$ lorsque $P$ est fausse ?

D'après la table de vérité de l'implication, $P \Rightarrow Q$ n'est fausse que lorsque $P$ est vraie et $Q$ fausse. Dès que $P$ est fausse, $P \Rightarrow Q$ est vraie, quelle que soit $Q$.

La proposition $P \vee \overline{P}$ est :

Une proposition est soit vraie soit fausse : si $P$ est vraie, $P \vee \overline{P}$ est vraie ; si $P$ est fausse, $\overline{P}$ est vraie donc $P \vee \overline{P}$ est encore vraie. C'est le principe du tiers exclu.

Vrai ou faux : la négation de "$P \wedge Q$" est "$\overline{P} \wedge \overline{Q}$".

Faux. D'après les lois de De Morgan, $\overline{P \wedge Q} = \overline{P} \vee \overline{Q}$ (et non $\wedge$). Par exemple si $P$ est vraie et $Q$ fausse, $P\wedge Q$ est fausse donc sa négation est vraie ; or $\overline P \wedge \overline Q$ est fausse (car $\overline P$ est fausse), alors que $\overline P \vee \overline Q$ est vraie.

Quelle est la contraposée de l'implication "$x > 2 \Rightarrow x^2 > 4$" (pour $x \in \mathbb{R}^+$) ?

La contraposée de $P \Rightarrow Q$ est $\overline{Q} \Rightarrow \overline{P}$. Ici $\overline{Q}$ est "$x^2 \leq 4$" et $\overline{P}$ est "$x \leq 2$", donc la contraposée est "$x^2 \leq 4 \Rightarrow x \leq 2$".

Comment se lit $\exists x \in \mathbb{R},\ x^2 = 2$ ?

Le symbole $\exists$ se lit "il existe (au moins un)". L'énoncé affirme l'existence d'un réel dont le carré vaut $2$ (par exemple $x = \sqrt{2}$), sans affirmer l'unicité.

Quelle est la négation de $\forall x \in \mathbb{R},\ x^2 \geq 0$ ?

La négation de $\forall x,\ P(x)$ est $\exists x,\ \overline{P(x)}$. Ici $\overline{P(x)}$ est "$x^2 < 0$", donc la négation est $\exists x \in \mathbb{R},\ x^2 < 0$ (qui est d'ailleurs fausse, ce qui confirme que la proposition de départ est vraie).

Vrai ou faux : $\forall x \in E,\ \exists y \in F,\ R(x,y)$ implique toujours $\exists y \in F,\ \forall x \in E,\ R(x,y)$.

Faux, c'est l'implication réciproque qui est toujours vraie. Contre-exemple : avec $R(x,y)$ : "$y>x$" sur $\mathbb{R}$, $\forall x,\exists y, y>x$ est vraie (prendre $y=x+1$) mais $\exists y,\forall x, y>x$ est fausse (aucun réel ne majore strictement tous les réels).

Quelle est la négation de "$x \geq 0 \Rightarrow x^2 \geq 1$" ?

La négation de $P \Rightarrow Q$ est $P \wedge \overline{Q}$. Ici cela donne "$x \geq 0$ et $x^2 < 1$", ce qui est cohérent : $x = 0{,}5$ vérifie bien $x\geq 0$ et $x^2 = 0{,}25 < 1$, donc l'implication de départ est fausse pour ce $x$.

Parmi les énoncés suivants sur $\mathbb{N}$, lequel est vrai ?

A est vraie : pour tout entier $n$, il existe un entier plus grand (par exemple $p=n+1$) — c'est la non-majoration de $\mathbb{N}$. B affirmerait un entier $p$ supérieur à tous les entiers, ce qui est impossible (en particulier $p \leq p$). C et D sont fausses pour des raisons analogues.

Vrai ou faux : la proposition $P \Leftrightarrow Q$ est vraie si et seulement si $P$ et $Q$ ont la même valeur de vérité.

Vrai. D'après la table de vérité, $P \Leftrightarrow Q$ est vraie dans les cas (V,V) et (F,F), c'est-à-dire exactement lorsque $P$ et $Q$ ont la même valeur de vérité.

Énoncer et nier (en justifiant chaque étape) la proposition $\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \geq N,\ |u_n - \ell| < \varepsilon$ (définition de $u_n \to \ell$).

Méthode : on parcourt l'énoncé de gauche à droite et on transforme chaque $\forall$ en $\exists$ (et inversement), puis on nie la proposition finale.

Étape 1 : $\overline{\forall \varepsilon>0,\ (\cdots)} \Leftrightarrow \exists \varepsilon>0,\ \overline{(\cdots)}$.

Étape 2 : $\overline{\exists N,\ (\cdots)} \Leftrightarrow \forall N,\ \overline{(\cdots)}$.

Étape 3 : $\overline{\forall n\geq N,\ (\cdots)} \Leftrightarrow \exists n\geq N,\ \overline{(\cdots)}$.

Étape 4 : la négation de $|u_n-\ell|<\varepsilon$ est $|u_n-\ell|\geq \varepsilon$.

Conclusion :

Soient $E$ un ensemble non vide et $R(x,y)$ une relation sur $E$. Vrai ou faux : $\exists y \in E,\ \forall x \in E,\ R(x,y)$ est strictement plus forte que $\forall x \in E,\ \exists y \in E,\ R(x,y)$ (c'est-à-dire que la première implique la seconde, sans réciproque en général).

Vrai. Si un même $y_0$ convient pour tous les $x$ (énoncé $\exists\forall$), alors en particulier pour chaque $x$ il existe (au moins) ce $y_0$ qui convient, ce qui donne l'énoncé $\forall\exists$. La réciproque est fausse en général, comme le montre l'exemple $R(x,y)$ : "$y>x$" sur $\mathbb{R}$ (voir cours, section 7).

Démontrer que $P \Rightarrow Q$ est logiquement équivalente à $\overline{P} \vee Q$, puis en déduire la formule de négation $\overline{P \Rightarrow Q} = P \wedge \overline{Q}$.

Étape 1 — équivalence par table de vérité :

Les colonnes $P\Rightarrow Q$ et $\overline{P}\vee Q$ sont identiques dans les quatre lignes, donc $P\Rightarrow Q \Leftrightarrow \overline{P}\vee Q$.

Étape 2 — négation : en niant les deux membres de cette équivalence et en appliquant la loi de De Morgan $\overline{A \vee B} = \overline{A}\wedge\overline{B}$ avec $A=\overline{P}$, $B=Q$ :

Soit $f : \mathbb{R} \to \mathbb{R}$. L'énoncé "$f$ est bornée" se traduit par $\exists M \in \mathbb{R},\ \forall x \in \mathbb{R},\ |f(x)| \leq M$. Quelle est sa négation ?

On échange $\exists M$ en $\forall M$, puis $\forall x$ en $\exists x$, et on nie l'inégalité finale ($\leq$ devient $>$) : $\forall M \in \mathbb{R},\ \exists x \in \mathbb{R},\ |f(x)| > M$. C'est bien la définition d'une fonction non bornée : pour toute borne candidate $M$, on trouve un point où $f$ la dépasse.

Vrai ou faux : pour montrer qu'une proposition de la forme $\forall x \in E,\ P(x)$ est fausse, il suffit d'exhiber un seul $x_0 \in E$ tel que $P(x_0)$ soit fausse.

Vrai. C'est le principe du contre-exemple. La négation de $\forall x\in E,\ P(x)$ est $\exists x\in E,\ \overline{P(x)}$ : il suffit donc d'exhiber un seul élément $x_0$ qui ne vérifie pas $P$ pour établir que l'énoncé universel est faux.