Logique formelle/Exercices/Quantificateurs et connecteurs logiques

Exercice 1-1

Pour quels ensembles $E$ l'implication suivante est-elle vraie quels que soient les prédicats $P$ et $Q$ ?

$\left[\forall x\in E\quad (P(x)\lor Q(x))\right]\Rightarrow \left[(\forall x\in E\quad P(x))\lor (\forall x\in E\quad Q(x))\right]$

Solution

Si $E=\varnothing$, l'implication est trivialement vraie car $\forall x\in \varnothing \quad \dots$ est toujours vrai et $\mathrm {VRAI} \Rightarrow \left[\mathrm {VRAI} \lor \mathrm {VRAI} \right]$ aussi.

Si $E=\{a\}$, l'implication est encore vraie, car elle se traduit par $\left[P(a)\lor Q(a)\right]\Rightarrow \left[P(a)\lor Q(a)\right]$.

Si $E$ a au moins deux éléments $a\neq b$, l'implication est fausse par exemple pour $P(x)\equiv (x=a)$ et $Q(x)\equiv (x\neq a)$.

Remarque : en revanche, l'implication réciproque, elle, est toujours vraie.

Moralité : $\forall$ et $\lor$ ne commutent pas. Cela n'a rien d'étonnant car $\forall$ est en quelque sorte un $\land$ infini, or le $\land$ usuel lui-même ne commute pas avec $\lor$.

 

Exercice 1-2

Soient $(E,\leq )$ et $(F,\preceq )$ deux ensembles ordonnés et $f:E\to F$ une application.

1. Traduire formellement : « $f$ n'est pas strictement croissante ». (Attention : on ne suppose pas que les ordres $\leq$ et $\preceq$ sont totaux.)
2. Traduire formellement : « $f$ est croissante ».
3. En déduire (formellement) que si $f$ est croissante et non strictement croissante, alors il existe $a,b\in E$ tels que $a<b$ et $f$ est constante sur l'ensemble $[a,b]:=\{x\in E\mid a\leq x\leq b\}$.

Solution

1. $\exists a,b\in E\quad \left(a<b\land f(a)\nprec f(b)\right)$.
2. $\forall x,y\in E\quad \left(x\leq y\Rightarrow f(x)\preceq f(y)\right)$.
3. Comme $f$ n'est pas strictement croissante, il existe $a,b\in E$ tels que $a<b$ et $f(a)\nprec f(b)$. Comme $f$ est croissante, $f(a)\preceq f(b)$. Donc $f(a)=f(b)$.
   Par croissance de $f$, on en déduit : $\forall x\in \left[a,b\right]\quad f(a)\preceq f(x)\preceq f(b)=f(a)$ donc (par antisymétrie de $\preceq$) $\forall x\in \left[a,b\right]\quad f(x)=f(a)$.

 

Voir aussi

« TD : Exercices de logique », sur Université d'Angers, L3SEN