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.

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)\mathrm{\neg }Pb)\mathrm{\neg }\mathrm{\neg }Qc)P\wedge Qd)Q\Rightarrow Pe)P\vee \mathrm{\neg }P$
   $f)\mathrm{\neg }P\wedge Qg)\mathrm{\neg }(P\wedge Q)h)\mathrm{\neg }P\wedge \mathrm{\neg }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 ».

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.

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 $\underset{\_}{\vee }$, $\mid$ et $\Vert$ définis par :

   • $\underset{\_}{\vee }$ est le connecteur de disjonction exclusive (« OU exclusif ») : $P\underset{\_}{\vee }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) ;
   • $\Vert$ (connecteur de Pierce) est le connecteur de rejet (« NOR » ou « NON OU ») : $P\Vert 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 ?

Modèle:BDdebut 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 \mathrm{\neg }P$, $P\mapsto Vrai$ et $P\mapsto Faux$, dont voici les tables de vérité :

Valeur de $P$	Valeur de $\mathrm{\neg }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\underset{\_}{\vee }Q$	Valeur de $P\mid Q$	Valeur de $P\Vert 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 $\mathrm{\neg }$ et $\wedge$, ou encore $\mathrm{\neg }$ et $\vee$. Il suffit donc d'engendrer ces deux derniers avec $|$, puis avec $\Vert$. On a $P\mid Q=\mathrm{\neg }(P\wedge Q)$ donc $\mathrm{\neg }P=P\mid P$ et $P\wedge Q=\mathrm{\neg }(P\mid Q)$. De même, $P\Vert Q=\mathrm{\neg }(P\vee Q)$ donc $\mathrm{\neg }P=P\Vert P$ et $P\vee Q=\mathrm{\neg }(P\Vert Q)$.

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

$P$	$Q$	$P\wedge Q$	$\mathrm{\neg }P\wedge Q$	$P\wedge \mathrm{\neg }Q$	$\mathrm{\neg }P\wedge \mathrm{\neg }Q$	$P\vee Q$	$\mathrm{\neg }P\vee Q$	$P\vee \mathrm{\neg }Q$	$\mathrm{\neg }P\vee \mathrm{\neg }Q$	$P\iff Q$	$P\iff \mathrm{\neg }Q$	$P$	$\mathrm{\neg }P$	$Q$	$\mathrm{\neg }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. Modèle:BDfin

Exercice 3-5

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

   $a)\mathrm{\neg }\mathrm{\neg }P\equiv Pb)P\vee Q\equiv Q\vee Pc)\mathrm{\neg }(P\wedge Q)\equiv (\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$

   $d)(P\Rightarrow Q)\equiv (\mathrm{\neg }P)\vee Qe)(P\vee Q)\wedge (P\vee R)\equiv P\vee (Q\wedge R)$.

2. En déduire :

   $a)(P\Rightarrow Q)\equiv (\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P)b)\mathrm{\neg }(P\Rightarrow Q)\equiv P\wedge \mathrm{\neg }Q$

   $c)(Q\Rightarrow P)\wedge (\mathrm{\neg }Q\Rightarrow P)\equiv Pd)(\mathrm{\neg }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)b)(P\Rightarrow Q)\Rightarrow Rc)(P\Rightarrow Q)\vee (Q\Rightarrow P)$.

Modèle:BDdebut 1. Il suffit de comparer les colonnes correspondantes des tables suivantes :

$P$	$\mathrm{\neg }P$	$\mathrm{\neg }\mathrm{\neg }P$	$Q$	$P\vee Q$	$Q\vee P$	$P\wedge Q$	$\mathrm{\neg }(P\wedge Q)$	$\mathrm{\neg }Q$	$\mathrm{\neg }P\vee \mathrm{\neg }Q$	$P\Rightarrow Q$	$(\mathrm{\neg }P)\vee 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\vee Q$	$P\vee R$	$(P\vee Q)\wedge (P\vee R)$	$Q\wedge R$	$P\vee (Q\wedge 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 : $(\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P)\equiv (\mathrm{\neg }\mathrm{\neg }Q)\vee \mathrm{\neg }P\equiv Q\vee \mathrm{\neg }P\equiv (\mathrm{\neg }P)\vee Q\equiv (P\Rightarrow Q)$

b) En utilisant successivement d), a), c), a), on obtient : $\mathrm{\neg }(P\Rightarrow Q)\equiv \mathrm{\neg }((\mathrm{\neg }P)\vee Q)\equiv \mathrm{\neg }((\mathrm{\neg }P)\vee \mathrm{\neg }\mathrm{\neg }Q)\equiv \mathrm{\neg }\mathrm{\neg }(P\wedge \mathrm{\neg }Q)\equiv P\wedge \mathrm{\neg }Q$.

c) En utilisant successivement d), a), b), e), on obtient : $(Q\Rightarrow P)\wedge (\mathrm{\neg }Q\Rightarrow P)\equiv (\mathrm{\neg }Q\vee P)\wedge (\mathrm{\neg }\mathrm{\neg }Q\vee P)\equiv (\mathrm{\neg }Q\vee P)\wedge (Q\vee P)\equiv (P\vee \mathrm{\neg }Q)\wedge (P\vee Q)\equiv P\vee (\mathrm{\neg }Q\wedge Q)\equiv P\vee Faux\equiv P$.

d) En utilisant d) puis a), on obtient : $(\mathrm{\neg }P\Rightarrow P)\equiv (\mathrm{\neg }\mathrm{\neg }P\vee P)\equiv (P\vee P)\equiv P$.

3.

$P$	$Q$	$R$	$P\Rightarrow (Q\Rightarrow R)$	$(P\Rightarrow Q)\Rightarrow R$	$(P\Rightarrow Q)\vee (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
			$\mathrm{\neg }(P\wedge Q\wedge \mathrm{\neg }R)$	$(P\wedge \mathrm{\neg }Q)\vee 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\vee Q$ soit une tautologie et $P\wedge Q$ une contradiction ?

Exercice 3-7

On considère trois propositions $𝒜$, $ℬ$ et $𝒞$ et l'on suppose que $𝒜\iff (ℬ\wedge 𝒞)$ et $𝒞\iff (𝒜\vee \mathrm{\neg }𝒞)$. En déduire les valeurs de vérité de $𝒜$, $ℬ$ et $𝒞$. Modèle:Solution

Exercice 3-8

Déterminer les ensembles suivants :

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

Soient $a,b,k\in ℝ$ tels que $a\le b$ et $k>1$. Déterminer les réels $x$ tels que

$\mathrm{\forall }y\in [a,b](x\ge y\Rightarrow x\ge ky)$.

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 : $\mathrm{\exists }x\in E\mathrm{\neg }P(x)$

   B : $\mathrm{\exists }x\in E[P(x)\wedge \mathrm{\neg }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 : $[\mathrm{\forall }x\in EP(x)]\Rightarrow [\mathrm{\forall }x\in EQ(x)]$

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

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. $\mathrm{\forall }x\in ℝ(x>3\wedge x\le -2)$
2. $\mathrm{\exists }(x,y,z)\in {ℝ}^3(x>y+z\wedge x-y\ne y-z\wedge -1\le z\le 2)$
3. $\mathrm{\forall }a\in \mathbb{N}\mathrm{\exists }(b,c)\in \mathbb{N}\times \mathbb{N}a=bc$
4. $\mathrm{\forall }(a,b)\in \mathbb{N}\times \mathbb{N}\mathrm{\exists }c\in \mathbb{N}a=bc$
5. $\mathrm{\exists }a\in \mathbb{N}\mathrm{\forall }b\in \mathbb{N}\mathrm{\exists }c\in \mathbb{N}a=bc$
6. $\mathrm{\forall }(a,b)\in {ℝ}^{2}a<b\Rightarrow \mathrm{\exists }q\in \mathbb{Q}a<q<b$
7. La suite numérique $(u_n{)}_{n\in \mathbb{N}}$ vérifie : $\mathrm{\exists }M\in ℝ\mathrm{\forall }n\in \mathbb{N}{u}_n\le M$
8. La suite numérique $(u_n{)}_{n\in \mathbb{N}}$ vérifie : $\mathrm{\exists }M\in ℝ\mathrm{\exists }N\in \mathbb{N}\mathrm{\forall }n\in \mathbb{N}(n\ge N\Rightarrow u_n\le 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.

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\ne 0\Rightarrow 0=1$
4. $\mathrm{\exists }x(x=0\Rightarrow x=1)$
5. $\mathrm{\exists }x(x\ne 0\Rightarrow x=1)$