Implication et équivalence/Exercices/Logique et raisonnements

Exercice 3-1

Vrai ou faux ?

1. Si $1+1=3$, alors $1+1=2$.
2. Si $1+1=2$, alors $1+1=3$.
3. Il n'est pas vrai que « $1+1=2$ si $1+1=3$ ».
4. Il n'est pas vrai que « $1+1=3$ si $1+1=2$ ».
5. $1+1=3$ si et seulement si $3+14=\pi$.
6. $-{\sqrt {2}}>0$ si et seulement si $(-{\sqrt {2}})^{2}>0^{2}$.
7. Un entier naturel est positif si et seulement si son carré est positif.

Solution

1. Vrai (pour deux raisons).
2. Faux.
3. Faux (en tant que négation de l'énoncé 1).
4. Vrai (en tant que négation de l'énoncé 2).
5. Vrai (car les deux termes sont faux).
6. Faux (car l'un est faux et l'autre vrai).
7. Vrai (car les deux termes sont vrais, quel que soit l'entier naturel considéré).

 

Exercice 3-2

1. On considère les assertions $P$ : « il pleut » et $Q$ : « je suis mouillé ». Donner des énoncées en français qui traduisent les assertions suivantes :
   $a)\;\lnot P\quad b)\;\lnot \lnot Q\quad c)\;P\land Q\quad d)\;Q\Rightarrow P\quad e)\;P\lor \lnot P$
   $f)\;\lnot P\land Q\quad g)\;\lnot (P\land Q)\quad h)\;\lnot P\land \lnot Q$.
2. Simplifiez les énoncés suivants :
   • Il n'est pas vrai que s'il pleut, il fait froid.
   • Il n'est pas vrai que « les coquelicots sont rouges si et seulement si les violettes sont bleues ».
   • Il n'est pas vrai que « les champignons ne poussent pas s'il ne fait pas soleil ».

Solution

1. a) Il ne pleut pas.

   b) Je suis mouillé.

   c) Il pleut et je suis mouillé.

   d) Si je suis mouillé alors il pleut.

   e) Vrai.

   f) Il ne pleut pas et je suis mouillé.

   g) Il ne pleut pas ou je suis sec.

   h) Il ne pleut pas et je suis sec.

2. • Il pleut et il ne fait pas froid.
   • Les coquelicots sont rouges et au moins une violette n'est pas bleue, ou les violettes sont bleues et au moins un coquelicot n'est pas rouge.
   • Il ne fait pas soleil et un champignon pousse.

 

Exercice 3-3

1. La négation de la proposition « S'il fait beau, je vais à la plage » est :

   a) S'il fait beau, je ne vais pas à la plage.

   b) S'il ne fait pas beau, je ne vais pas à la plage.

   c) S'il ne fait pas beau, je vais à la plage.

   d) Il fait beau et je ne vais pas à la plage.

2. La proposition « Les personnes qui parlent trop ne réfléchissent pas souvent » équivaut à :

   a) Les personnes qui parlent trop ne réfléchissent pas.

   b) Les personnes qui réfléchissent souvent ne parlent pas trop.

   c) Les personnes qui réfléchissent souvent parlent trop.

   d) Les personnes qui ne parlent pas trop réfléchissent souvent.

Solution

1. d), 2. b)

 

Exercice 3-4

1. Montrer qu'il y a 4 connecteurs unaires et écrire leurs tables de vérité.

2. a) Écrire les tables de vérité des trois connecteurs binaires ${\underline {\lor }}$, $\mid$ et $\|$ définis par :

   • ${\underline {\lor }}$ est le connecteur de disjonction exclusive (« OU exclusif ») : $P{\underline {\lor }}Q$ est vrai si l'on a $P$ ou $Q$ mais pas les deux à la fois ;
   • $\mid$ (barre de Sheffer) est le connecteur d’incompatibilité (« NAND » ou « NON ET ») : $P\mid Q$ signifie que $P$ exclut $Q$ (ou encore : que l'on ne peut pas avoir $P$ et $Q$ à la fois) ;
   • $\|$ (connecteur de Pierce) est le connecteur de rejet (« NOR » ou « NON OU ») : $P\|Q$ signifie que l'on n'a ni $P$, ni $Q$.

   b) Montrer que tous les connecteurs logiques usuels peuvent être définis en utilisant uniquement la barre de Sheffer, et que le connecteur de Pierce peut jouer le même rôle.

   c) Montrer qu'il y a 16 connecteurs binaires et écrire leurs tables de vérité.

3. Combien y a-t-il de connecteurs ternaires ?

Solution

1. Les connecteurs $n$-aires sont les applications de $\{Vrai,Faux\}^{n}$ dans $\{Vrai,Faux\}$. Il y en a donc $2^{(2^{n})}$.
En particulier, il y a $2^{(2^{1})}=4$ connecteurs unaires : $P\mapsto P$, $P\mapsto \lnot P$, $P\mapsto Vrai$ et $P\mapsto Faux$, dont voici les tables de vérité :

Valeur de $P$	Valeur de $\lnot P$	Valeur de $Vrai$	Valeur de $Faux$
V	F	V	F
F	V	V	F

2.

a)

Valeur de $P$	Valeur de $Q$	Valeur de $P{\underline {\lor }}Q$	Valeur de $P\mid Q$	Valeur de $P\|Q$
V	V	F	F	F
V	F	V	V	F
F	V	V	V	F
F	F	F	V	V

b) On sait que tous les connecteurs logiques peuvent s'obtenir à partir des deux connecteurs $\lnot$ et $\land$, ou encore $\lnot$ et $\lor$. Il suffit donc d'engendrer ces deux derniers avec $|$, puis avec $\|$. On a $P\mid Q=\lnot (P\land Q)$ donc $\lnot P=P\mid P$ et $P\land Q=\lnot (P\mid Q)$. De même, $P\|Q=\lnot (P\lor Q)$ donc $\lnot P=P\|P$ et $P\lor Q=\lnot (P\|Q)$.

c) Il y a $2^{(2^{2})}=16$ connecteurs binaires, dont voici les tables de vérité :

$P$	$Q$	$P\land Q$	$\lnot P\land Q$	$P\land \lnot Q$	$\lnot P\land \lnot Q$	$P\lor Q$	$\lnot P\lor Q$	$P\lor \lnot Q$	$\lnot P\lor \lnot Q$	$P\Leftrightarrow Q$	$P\Leftrightarrow \lnot Q$	$P$	$\lnot P$	$Q$	$\lnot Q$	$V$	$F$
V	V	V	F	F	F	V	V	V	F	V	F	V	F	V	F	V	F
V	F	F	F	V	F	V	F	V	V	F	V	V	F	F	V	V	F
F	V	F	V	F	F	V	V	F	V	F	V	F	V	V	F	V	F
F	F	F	F	F	V	F	V	V	V	V	F	F	V	F	V	V	F

3. Il y a $2^{(2^{3})}=256$ connecteurs ternaires.

 

Exercice 3-5

1. Vérifier à l'aide des tables de vérité les équivalences logiques suivantes :

   $a)\;\lnot \lnot P\equiv P\qquad b)\;P\lor Q\equiv Q\lor P\qquad c)\;\lnot (P\land Q)\equiv (\lnot P)\lor (\lnot Q)$

   $d)\;(P\Rightarrow Q)\equiv (\lnot P)\lor Q\qquad e)\;(P\lor Q)\land (P\lor R)\equiv P\lor (Q\land R)$.

2. En déduire :

   $a)\;(P\Rightarrow Q)\equiv (\lnot Q\Rightarrow \lnot P)\qquad b)\;\lnot (P\Rightarrow Q)\equiv P\land \lnot Q$

   $c)\;(Q\Rightarrow P)\land (\lnot Q\Rightarrow P)\equiv P\qquad d)\;(\lnot P\Rightarrow P)\equiv P$.

3. Dans chacun des cas suivants, écrire la table de vérité de l'assertion et trouver une assertion équivalente plus simple :

   $a)\;P\Rightarrow (Q\Rightarrow R)\qquad b)\;(P\Rightarrow Q)\Rightarrow R\qquad c)\;(P\Rightarrow Q)\lor (Q\Rightarrow P)$.

Solution

1. Il suffit de comparer les colonnes correspondantes des tables suivantes :

$P$	$\lnot P$	$\lnot \lnot P$	$Q$	$P\lor Q$	$Q\lor P$	$P\land Q$	$\lnot (P\land Q)$	$\lnot Q$	$\lnot P\lor \lnot Q$	$P\Rightarrow Q$	$(\lnot P)\lor Q$
V	F	V	V	V	V	V	F	F	F	V	V
V	F	V	F	V	V	F	V	V	V	F	F
F	V	F	V	V	V	F	V	F	V	V	V
F	V	F	F	F	F	F	V	V	V	V	V

$P$	$Q$	$R$	$P\lor Q$	$P\lor R$	$(P\lor Q)\land (P\lor R)$	$Q\land R$	$P\lor (Q\land R)$
V	V	V	V	V	V	V	V
V	V	F	V	V	V	F	V
V	F	V	V	V	V	F	V
V	F	F	V	V	V	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	F	F
F	F	V	F	V	F	F	F
F	F	F	F	F	F	F	F

2.

a) En utilisant successivement d), a), b), d), on obtient : $(\lnot Q\Rightarrow \lnot P)\equiv (\lnot \lnot Q)\lor \lnot P\equiv Q\lor \lnot P\equiv (\lnot P)\lor Q\equiv (P\Rightarrow Q)$

b) En utilisant successivement d), a), c), a), on obtient : $\lnot (P\Rightarrow Q)\equiv \lnot ((\lnot P)\lor Q)\equiv \lnot ((\lnot P)\lor \lnot \lnot Q)\equiv \lnot \lnot (P\land \lnot Q)\equiv P\land \lnot Q$.

c) En utilisant successivement d), a), b), e), on obtient : $(Q\Rightarrow P)\land (\lnot Q\Rightarrow P)\equiv (\lnot Q\lor P)\land (\lnot \lnot Q\lor P)\equiv (\lnot Q\lor P)\land (Q\lor P)\equiv (P\lor \lnot Q)\land (P\lor Q)\equiv P\lor (\lnot Q\land Q)\equiv P\lor Faux\equiv P$.

d) En utilisant d) puis a), on obtient : $(\lnot P\Rightarrow P)\equiv (\lnot \lnot P\lor P)\equiv (P\lor P)\equiv P$.

3.

$P$	$Q$	$R$	$P\Rightarrow (Q\Rightarrow R)$	$(P\Rightarrow Q)\Rightarrow R$	$(P\Rightarrow Q)\lor (Q\Rightarrow P)$
V	V	V	V	V	V
V	V	F	F	F	V
V	F	V	V	V	V
V	F	F	V	V	V
F	V	V	V	V	V
F	V	F	V	F	V
F	F	V	V	V	V
F	F	F	V	F	V
			$\lnot (P\land Q\land \lnot R)$	$(P\land \lnot Q)\lor R$	Vrai

 

Exercice 3-6

1. Que peut-on dire de l'assertion $P$ lorsque l'assertion « $P\Rightarrow Q$ » est vraie
   a) avec $Q$ qui est fausse ? b) avec $Q$ qui est vraie ?
2. Mêmes questions lorsque l'assertion « $Q\Rightarrow P$ » est vraie.
3. Étant donnée une assertion $P$ fixée, que peut-on dire de l'assertion $Q$ telle que $P\lor Q$ soit une tautologie et $P\land Q$ une contradiction ?

Solution

1. a) $P$ est fausse, b) Rien.
2. a) Rien, b) $P$ est vraie.
3. Par hypothèse, $(P\lor Q)\land \lnot (P\land Q)$, ce qui équivaut à $(\lnot P\Rightarrow Q)\land (Q\Rightarrow \lnot P)$, ou encore : $Q\Leftrightarrow \lnot P$.

 

Exercice 3-7

On considère trois propositions ${\mathcal {A}}$, ${\mathcal {B}}$ et ${\mathcal {C}}$ et l'on suppose que ${\mathcal {A}}\Leftrightarrow ({\mathcal {B}}\land {\mathcal {C}})$ et ${\mathcal {C}}\Leftrightarrow ({\mathcal {A}}\lor \lnot {\mathcal {C}})$. En déduire les valeurs de vérité de ${\mathcal {A}}$, ${\mathcal {B}}$ et ${\mathcal {C}}$.

Solution

De la seconde hypothèse on déduit que ${\mathcal {C}}$ est vrai et donc ${\mathcal {A}}$ aussi. De la première hypothèse on déduit alors que ${\mathcal {B}}$ est vrai.

 

Exercice 3-8

Déterminer les ensembles suivants :

• $X=\{x\in \mathbb {R} \mid x>1\Rightarrow x>5\}$,
• $Y=\{x\in \mathbb {R} \mid x>1\Rightarrow (x>2\Rightarrow x>3)\}$,
• $Z=\{x\in \mathbb {R} \mid (x>1\Rightarrow x>2)\Rightarrow x>3\}$.

Solution

• $X=\{x\in \mathbb {R} \mid x\leq 1{\rm {\ ou\ }}x>5\}=\left]-\infty ,1\right]\cup \left]5,+\infty \right[$.
• Pour tout $x\in \mathbb {R}$, $x\in Y\Leftrightarrow [(x\leq 1){\rm {\ ou\ }}(x\leq 2{\rm {\ ou\ }}x>3)]\Leftrightarrow [(x\leq 1{\rm {\ ou\ }}x\leq 2){\rm {\ ou\ }}x>3)]\Leftrightarrow [x\leq 2{\rm {\ ou\ }}x>3]$ donc $Y=\left]-\infty ,2\right]\cup \left]3,+\infty \right[$.
• Pour tout $x\in \mathbb {R}$, $x\in Z\Leftrightarrow [{\rm {non}}(x\leq 1{\rm {\ ou\ }}x>2){\rm {\ ou\ }}x>3]\Leftrightarrow [(x>1{\rm {\ et\ }}x\leq 2){\rm {\ ou\ }}x>3]$ donc $Z=\left]1,2\right]\cup \left]3,+\infty \right[$.

 

Soient $a,b,k\in \mathbb {R}$ tels que $a\leq b$ et $k>1$. Déterminer les réels $x$ tels que

$\forall y\in [a,b]\quad (x\geq y\Rightarrow x\geq ky)$.

Solution

Un réel $x$ vérifie

$\forall y\in [a,b]\quad (y>x\lor y\leq x/k)$

ou encore

$[a,b]\subset \left]-\infty ,x/k\right]\cup \left]x,+\infty \right[$

si et seulement si $\left]-\infty ,x/k\right]\cup \left]x,+\infty \right[=\mathbb {R}$ (c'est-à-dire $x/k\geq x$) ou $[a,b]\subset \left]-\infty ,x/k\right]$ ou $[a,b]\subset \left]x,+\infty \right[$.

L'ensemble des solutions $x$ est donc $\left]-\infty ,0\right]\cup \left[kb,+\infty \right[\cup \left]-\infty ,a\right[$, autrement dit :

• si $b\leq 0$ : $\mathbb {R}$ ;
• si $a\leq 0<b$ : $\left]-\infty ,0\right]\cup \left[kb,+\infty \right[$ ;
• si $a>0$ : $\left]-\infty ,a\right[\cup \left[kb,+\infty \right[$.

 

Exercice 3-9

1. Donner un exemple simple d'ensemble $E$, et de choix d'interprétation sur $E$ des prédicats $P$ et $Q$, tel que les énoncés suivants soient vrais tous les deux :

   A : $\exists x\in E\quad \lnot P(x)$

   B : $\exists x\in E\quad [P(x)\land \lnot Q(x)]$.

2. Pour tout $(E,P,Q)$ vérifiant A et B, donner (en justifiant !) la valeur de vérité de chacun des deux énoncés :

   C : $[\forall x\in E\quad P(x)]\Rightarrow [\forall x\in E\quad Q(x)]$

   D : $\forall x\in E\quad [P(x)\Rightarrow Q(x)]$.

Solution

1. $E=\{0,1\}$, $P(1)=V$, $P(0)=F$, $Q(1)=F$ (et $Q(0)$ quelconque).
2. C est vrai car $[\forall x\in E\quad P(x)]$ est faux (car il équivaut à $\lnot A$).
   D est faux car il équivaut à $\lnot B$.

 

Exercice 3-10

Dans chaque cas, écrire en langage quantifié la négation de l'assertion (on précisera, quand c'est possible, la valeur de vérité des assertions).

1. $\forall x\in \mathbb {R} \quad (x>3\land x\leq -2)$
2. $\exists (x,y,z)\in \mathbb {R} ^{3}\quad (x>y+z\land x-y\neq y-z\land -1\leq z\leq 2)$
3. $\forall a\in \mathbb {N} \quad \exists (b,c)\in \mathbb {N} \times \mathbb {N} \quad a=bc$
4. $\forall (a,b)\in \mathbb {N} \times \mathbb {N} \quad \exists c\in \mathbb {N} \quad a=bc$
5. $\exists a\in \mathbb {N} \quad \forall b\in \mathbb {N} \quad \exists c\in \mathbb {N} \quad a=bc$
6. $\forall (a,b)\in \mathbb {R} ^{2}\quad a<b\Rightarrow \exists q\in \mathbb {Q} \quad a<q<b$
7. La suite numérique $(u_{n})_{n\in \mathbb {N} }$ vérifie : $\exists M\in \mathbb {R} \quad \forall n\in \mathbb {N} \quad u_{n}\leq M$
8. La suite numérique $(u_{n})_{n\in \mathbb {N} }$ vérifie : $\exists M\in \mathbb {R} \quad \exists N\in \mathbb {N} \quad \forall n\in \mathbb {N} \quad (n\geq N\Rightarrow u_{n}\leq M)$.

Solution

1. La négation $\exists x\in \mathbb {R} \quad (x\leq 3\lor x>-2)$ est vraie, et même : $\forall x\in \mathbb {R} \quad (x\leq 3\lor x>-2)$.
2. La proposition est vraie, et même : $\forall (y,z)\in \mathbb {R} ^{2}\quad \exists x\in \mathbb {R} \quad (x>y+z\land x\neq 2y-z)$. Sa négation est $\forall (x,y,z)\in \mathbb {R} ^{3}\quad (x\leq y+z\lor x-y\neq y-z\lor -1\leq z\leq 2)$.
3. La proposition est vraie car $\forall a\in \mathbb {N} \quad a=a\times 1$. Sa négation est $\exists a\in \mathbb {N} \quad \forall (b,c)\in \mathbb {N} \times \mathbb {N} \quad a\neq bc$.
4. La négation $\exists (a,b)\in \mathbb {N} \times \mathbb {N} \quad \forall c\in \mathbb {N} \quad a\neq bc$ est vraie ($\forall c\in \mathbb {N} \quad 1\neq 0c$).
5. La proposition est vraie, et même : $\forall b\in \mathbb {N} \quad 0=b0$. Sa négation est $\forall a\in \mathbb {N} \quad \exists b\in \mathbb {N} \quad \forall c\in \mathbb {N} \quad a\neq bc$.
6. La proposition est vraie ($\mathbb {Q}$ est dense dans $\mathbb {R}$). Sa négation est $\exists (a,b)\in \mathbb {R} ^{2}\quad a<b\land \forall q\in \mathbb {Q} \quad (q\leq a\lor q\geq b)$.
7. La proposition signifie que la suite $(u_{n})_{n\in \mathbb {N} }$ est majorée. Sa négation est $\forall M\in \mathbb {R} \quad \exists n\in \mathbb {N} \quad u_{n}>M$.
8. La proposition signifie que la suite $(u_{n})_{n\in \mathbb {N} }$ est majorée à partir d'un certain rang (ce qui équivaut à : cette suite est majorée). Sa négation est $\forall M\in \mathbb {R} \quad \forall N\in \mathbb {N} \quad \exists n\in \mathbb {N} \quad (n\geq N\land u_{n}>M)$.

 

Exercice 3-11

Juger de la validité des syllogismes suivants :

1. Aucune citrouille n'est rouge, or tous les fruits sont rouges, donc certains fruits ne sont pas des citrouilles.
2. Seules les citrouilles sont orange, or certains fruits ne sont pas orange, donc certains fruits ne sont pas des citrouilles.
3. Seuls les jugements désintéressés sont des jugements libres, or tout jugement rationnel est un jugement libre, donc certains jugements rationnels sont désintéressés.
4. Qui est déchu de ses droits civiques n'est pas éligible, or certains criminels ne sont pas déchus de leurs droits civiques, donc certains criminels sont éligibles.
5. Seuls les actes explicitement interdits par la loi sont répréhensibles, or certains détournements d'argent ne sont pas explicitement interdits par la loi, donc certains détournements d'argent ne sont pas répréhensibles.

Solution

1. Valide, bien qu'affaibli (on pourrait conclure qu'aucun fruit n'est une citrouille).
2. Invalide (il faudrait remplacer, dans la prémisse majeure, « Seules les citrouilles » par « Toutes les citrouilles »).
3. Valide, bien qu'affaibli (on pourrait conclure que tous les jugements rationnels sont désintéressés).
4. Invalide (il faudrait intervertir, dans la prémisse majeure, « est » et « n'est pas »).
5. Parfaitement valide.

 

Exercice 3-12

Soient $0=\varnothing$ et $1=\{0\}$. Les énoncés suivants sont-ils vrais ou faux ? (justifier)

1. $0=1\Rightarrow 0=0$
2. $0=0\Rightarrow 0=1$
3. $0\neq 0\Rightarrow 0=1$
4. $\exists x\;(x=0\Rightarrow x=1)$
5. $\exists x\;(x\neq 0\Rightarrow x=1)$

Solution

$P\Rightarrow Q$ signifie : $P$ est faux ou $Q$ est vrai.

1. $0=1\Rightarrow 0=0$ est vrai car $0=0$ est vrai (ou encore : car $0=1$ est faux).
2. $0=0$ est vrai et $0=1$ est faux donc $0=0\Rightarrow 0=1$ est faux.
3. ($0=1$ est faux mais) $0\neq 0$ est faux donc $0\neq 0\Rightarrow 0=1$ est vrai.
4. $\exists x\;(x=0\Rightarrow x=1)$ est vrai. Pour le démontrer, il suffit de fournir un $x$ tel que $x=1$ soit vrai ou tel que $x=0$ soit faux (par exemple $x=1$, ou n'importe quel $x\neq 0$, comme $x=2$).
5. $\exists x\;(x\neq 0\Rightarrow x=1)$ est vrai. Pour le démontrer, il suffit de fournir un $x$ tel que $x=1$ soit vrai ou tel que $x\neq 0$ soit faux (on a le choix entre $x=1$ ou $x=0$).