Exercices corrigés - Bases de la logique - propositions - quantificateurs

Il faut retourner la carte 8 et la carte verte :

• inutile de retourner la carte 5, on n'a pas de contraintes sur les cartes ayant un chiffre impair sur une face;
• il faut retourner la carte 8, pour vérifier que la couleur sur l'autre face est bleue;
• inutile de retourner la carte bleue, une carte ayant un chiffre pair ou impair sur une face peut être bleue sur l'autre face;
• il faut retourner la carte verte : si le chiffre inscrit sur l'autre face était pair, la règle serait fausse.

On va dresser les tables de vérité de ces deux propositions et démontrer que leurs résultats sont identiques. $$ \begin{array}{c|c|c|c|c} A&B&C&B\textrm{ OU }C&A\textrm{ ET }(B\textrm{ OU }C)\\ 0&0&0&0&0\\ 0&0&1&1&0\\ 0&1&0&1&0\\ 0&1&1&1&0\\ 1&0&0&0&0\\ 1&0&1&1&1\\ 1&1&0&1&1\\ 1&1&1&1&1\\ \end{array} $$ $$\begin{array}{c|c|c|c|c} A&B&C&A\textrm{ ET }B&A\textrm{ ET }C&(A\textrm{ ET }B)\textrm{ OU }(A\textrm{ ET }C)\\ 0&0&0&0&0&0\\ 0&0&1&0&0&0\\ 0&1&0&0&0&0\\ 0&1&1&0&0&0\\ 1&0&0&0&0&0\\ 1&0&1&0&1&1\\ 1&1&0&1&0&1\\ 1&1&1&1&1&1\\ \end{array} $$ La lecture de ces deux tables de vérité nous dit bien que les deux propositions sont équivalentes.

1. On va commencer par réaliser la table de vérité de l'opérateur NAND : $$\begin{array}{c|c|c|c} A&B&A\textrm{ ET }B&A\textrm{ NAND }B\\ 0&0&0&1\\ 0&1&0&1\\ 1&0&0&1\\ 1&1&1&0 \end{array}$$ On prouve ensuite que l'opérateur NON peut être défini à l'aide de NAND. Pour cela, on remarque que $A\textrm{ NAND }A=\textrm{NON }A$ à l'aide de la table de vérité ci-dessus. On en déduit alors que l'opérateur ET peut s'exprimer à l'aide de NAND. En effet, \begin{eqnarray*} A\textrm{ ET }B&=&\textrm{NON}(A\textrm{ NAND }B)\\ &=&(A\textrm{ NAND }B)\textrm{ NAND }(A\textrm{ NAND }B). \end{eqnarray*} Puisqu'on peut exprimer l'opérateur OU à l'aide des opérateurs ET et NON, on peut retrouver aussi l'opérateur OU uniquement à l'aide de NAND. En effet, on a $$A\textrm{ OU }B=\textrm{NON}(\textrm{NON }A\textrm{ ET NON }B).$$ Remplaçant les NON et le ET par leur formule à l'aide de NAND, on exprimera OU à l'aide de NAND uniquement. On peut aussi remarquer, à l'aide d'une table de vérité, que $$A\textrm{ OU }B=(A\textrm{ NAND }A)\textrm{ NAND }(B\textrm{ NAND }B).$$
2. La méthode est similaire. La table de vérité est cette fois $$\begin{array}{c|c|c|c} A&B&A\textrm{ OU }B&A\textrm{ NOR }B\\ 0&0&0&1\\ 0&1&1&0\\ 1&0&1&0\\ 1&1&1&0 \end{array}$$ On remarque ensuite que $A\textrm{ NOR }A=\textrm{NON }A$ à l'aide de la table de vérité ci-dessus. On en déduit alors que l'opérateur OU peut s'exprimer à l'aide de NOR. En effet, \begin{eqnarray*} A\textrm{ OU }B&=&\textrm{NON}(A\textrm{ NOR }B)\\ &=&(A\textrm{ NOR }B)\textrm{ NOR }(A\textrm{ NOR }B). \end{eqnarray*} Finalement, on a aussi $$A\textrm{ ET }B=(A\textrm{ NOR }A)\textrm{ NOR }(B\textrm{ NOR }B).$$

Il suffit d'établir les tables de vérité de ces deux propositions et de vérifier qu'elles sont identiques. On a d'une part $$ \begin{array}{c|c|c|c} P&Q&P\implies Q&\textrm{NON }P\implies Q\\ 0&0&1&0\\ 0&1&1&0\\ 1&0&0&1\\ 1&1&1&0\\ \end{array} $$ et d'autre part $$ \begin{array}{c|c|c|c} P&Q&\textrm{ NON Q}&P\textrm{ ET NON } Q\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&1&1\\ 1&1&0&0\\ \end{array} $$ Les deux propositions sont bien équivalentes!

La méthode est de remplacer les symboles $\implies$ and $\iff$ par leur équivalent avec les symboles $\vee,\wedge,\lnot$, d'utiliser les lois de Morgan $\lnot (A \vee B)=\lnot A\wedge \lnot B$ et $\lnot (A \wedge B)=\lnot A\vee \lnot B$, et d'utiliser la distributivité de $\wedge$ par rapport à $\vee$.

1. $(\lnot p \wedge q) \implies r$ est la même chose que $\lnot( \lnot p \wedge q) \vee r$. On enlève le non externe, et on trouve $(p \vee \lnot q) \vee r$ soit $p \vee \lnot q \vee r$. C'est une forme normale à la fois disjonctive et conjonctive.
2. On enlève le $\implies$ et on trouve donc $\lnot(p \vee \lnot q) \wedge (\lnot s \vee t)$. On enlève ensuite le non et on trouve $\lnot p \wedge q \wedge (\lnot s \vee t)$. Cette formule est déjà sous forme conjonctive. Pour la mettre sous forme disjonctive, il faut utiliser la distributivité, et on trouve : $$(\lnot p \wedge q \wedge \lnot s) \vee (\lnot p \wedge q \wedge t).$$
3. On enlève le non externe et on trouve $(\lnot p \vee \lnot q) \wedge (p \vee q)$. C'est une forme normale conjonctive. Pour obtenir une forme normale disjonctive, il faut encore développer par distributivité du et par rapport au ou. On trouve $$(\lnot p \wedge p) \vee (\lnot p \wedge q) \vee (\lnot q \wedge p) \vee (\lnot q \wedge q).$$ On peut encore simplifier, car $(\lnot p \wedge p)$ est toujours faux et n'intervient pas dans la disjonction. Finalement, on trouve $(\lnot p \wedge q) \vee (\lnot q \wedge p)$.

Notons $p=$"il pleut", $q=$"Abel a un parapluie" et $r=$"Béatrice a un parapluie". L'énoncé nous dit que $p\implies q$ et que $p\iff r$.

1. Dans cette situation, on nous dit que $q$ est vraie. On ne peut rien conclure.
2. non $q$ est vraie. Or, on sait (contraposée de $p\implies q$) que (non $q\implies$ non $p$). Donc il ne pleut pas.
3. $r$ est vraie, et $r$ équivaut à $p$. Donc il pleut et Abel a son parapluie.
4. non $r$ est vraie et non $r$ équivaut à non $p$ donc il ne pleut pas.
5. non $p$ est vraie et non $p$ équivaut à non $r$ donc Béatrice se promène sans parapluie.
6. $p$ est vraie or $p\implies q$ et $p\iff r$ donc Abel et Béatrice ont tous deux leur parapluie.

Notons $A$ la proposition "$6|n$" et $B$ la proposition "$n$ est pair". Alors $A\implies B$. En effet, si $6|n$, alors il existe un entier $k$ tels que $n=6\times k$ et donc $n=2\times (3k)$ est pair. En revanche, la réciproque est fausse. En effet, $4$ est pair mais $6$ ne divise pas 4. On en déduit que

1. $6|n$ n'est pas une condition nécessaire à ce que $n$ soit pair ($4$ est un contre-exemple).
2. $6|n$ est une condition suffisante à ce que $n$ soit pair.

1. Avoir passé l'examen.
2. Les points $A,B$ et $C$ sont alignés.
3. $ABCD$ est un parallélogramme.

Les trois conditions précédentes sont des conditions nécessaires mais non suffisantes (pourquoi?). On peut en imaginer bien d'autres...

1. Avoir plus que $12$ en moyenne.
2. $A$ est le milieu de $[BC]$.
3. Les diagonales de $ABCD$ ont même longueur et se coupent en leur milieu.

Les deux premières conditions sont des conditions suffisantes, mais non nécessaires (pourquoi?). En revanche, la troisième condition est une condition nécessaire et suffisante.

Notons $P$ la proposition "Avoir son examen" et $Q$ la proposition "Travailler régulièrement". Nous allons écrire les propositions sous la forme $P\implies Q$ ou $Q\implies P$.

1. La proposition est clairement $Q\implies P$.
2. La proposition est $P\implies Q$.
3. La proposition est $\bar Q\implies \bar P$. C'est une proposition équivalente à sa contraposée, $P\implies Q$.
4. Même signification que 2., $P\implies Q$.
5. Cette fois, on a $Q\implies P$.
6. La proposition est $\bar Q\implies \bar P$, qui est équivalente à $P\implies Q$.
7. Cette fois, on a $\bar P\implies \bar Q$, qui est équivalente à $Q\implies P$.
8. Tout simplement, $Q\implies P$.
9. C'est la même chose que 2, à savoir $P\implies Q$.

Les propositions 1, 5, 7 et 8 sont donc équivalentes, et les proposition 2, 3, 4, 6 et 9 le sont également.

Construisons la table de vérité de $(A\implies B)\implies C$ : $$\begin{array}{c|c|c|c|c} A&B&A\implies B&C&(A\implies B)\implies C\\ 0&0&1&0&0\\ 0&1&1&0&0\\ 1&0&0&0&1\\ 1&1&1&0&0\\ 0&0&1&1&1\\ 0&1&1&1&1\\ 1&0&0&1&1\\ 1&1&1&1&1\\ \end{array}$$ Les valeurs de vérité de $A$, $B$ et $C$ qui sont possibles correspondent aux valeurs des lignes 3,5,6,7,8, celles pour laquelle $(A\implies B)\implies C$ est vrai. On en déduit alors que :

• On ne peut pas être sûr que $A$ est suffisant à $B$. Par exemple, dans la troisième ligne, $A$ est vrai, $B$ est faux, et pourtant $(A\implies B)\implies C$ est vrai. Symétriquement, on ne peut pas être sûr que $B$ est nécessaire à $A$.
• De même, on ne peut pas être sûr que $A$ est suffisant à $C$ (ligne 3), que $B$ est suffisant à $A$ (ligne 6), que $C$ est suffisant à $A$ (ligne 5), que $C$ est suffisant à $B$ (ligne 5).
• En revanche si $B$ est vrai, et puisque $(A\implies B)\implies C$ est vrai , on ne peut être que dans les lignes 6 ou 8 de la table de vérité, pour lesquelles $C$ est automatiquement vrai. Dès que $B$ est vrai, alors $C$ est vrai. Autrement dit, $B$ est une condition suffisante pour que $C$ soit vrai. Symétriquement, $C$ est une condition nécessaire pour que $B$ soit vrai.

1. Cette propositions est fausse, car 2 ne divise pas 167.
2. Cette proposition est vraie, car 136 est un multiple de 17.
3. Cette proposition est fausse, car $x$ devrait être simultanément égal à -1 et à -2.
4. Cette proposition est vraie car $(\exists x\in\mathbb R,\ x+1=0)$ est vraie (il suffit de prendre $x=-1$) et de la même façon $(\exists x\in\mathbb R,\ x+2=0)$ est vraie (il suffit de prendre $x=-2$).
5. Cette proposition est vraie, par exemple car il s'agit de la négation de la proposition 3, qui est fausse.
6. Cette assertion est fausse. Si on considère $x$ n'importe quel réel non nul, alors le choix de $y=1$ et de $z=2x$ fait que $z$ est différent de $xy$.
7. Cette assertion est fausse. Prenons n'importe quel $y$ dans $\mathbb R^*$. On voudrait trouver $x$ dans $\mathbb R^*$ tel que, pour tout $z$ dans $\mathbb R^*$, on ait $z=xy$. Bien sûr, ce n'est pas possible, car le $x$ que l'on choisit devrait convenir à toute valeur de $z$, ce qui n'est pas possible car il suffit de considérer un $z$ différent de $xy$.
8. Cette assertion est vraie, car on peut choisir $x$ une fois $y$ et $z$ fixés. On choisit alors $x=z/y$.
9. L'assertion est vraie, il suffit de prendre $a=0$ (convient pour toute valeur de $\veps>0$).
10. Cette assertion est "évidemment" vraie car elle est plus faible que la précédente (on peut choisir $a$ après $\veps>0$).

En appliquant les règles usuelles, les négations sont respectivement :

1. $\forall x\in \mathbb R,\ \exists y\in\mathbb R,\ x+y< 0$ ;
2. $\exists x\in \mathbb R,\ \exists y\in\mathbb R,\ x+y<0$ ;
3. $\forall x\in \mathbb R,\ \forall y\in\mathbb R,\ x+y<0$ ;
4. $\exists x\in\mathbb R,\ \forall y\in\mathbb R,\ x+y<0$.

On remarque ensuite que

1. La proposition 1 est fausse. En effet, quelque soit le $x$ choisi, je peux trouver $y$, par exemple $y=-x-1,$ tel que $x+y<0$ (on vient donc de prouver que la négation de 1 est vraie).
2. La proposition 2 est fausse. On peut prendre le contre-exemple $x=y=-1$.
3. La proposition 3 est vraie. On peut choisir $x=y=1$.
4. La proposition 4 est vraie. Si je considère n'importe quel $x\in\mathbb R,$ il suffit de prendre $y=-x+1$ pour que $x+y=1\geq 0.$

1. $\exists x\in\mathbb R,\ f(x)=0$.
2. $\exists M>0,\ \forall A>0,\ \exists x\geq A,\ f(x)\leq M$.
3. $\exists x\in\mathbb R,\ f(x)>0\textrm{ et }x>0$.
4. $\exists \veps>0,\ \forall \eta>0,\ \exists (x,y)\in I^2, |x-y|\leq \eta\textrm{ et } |f(x)-f(y)|>\veps$.

On sépare en 4 cas :

1. $x\geq 2$. Alors, pour tout $y\in[0,1]$, les propositions $x\geq y$ et $x\geq 2y$ sont vraies. D'après la table de vérité de l'implication, l'assertion est vraie.
2. $x<0$. Alors, pour tout $y\in [0,1]$, les propositions $x\geq y$ et $x\geq 2y$ sont fausses. D'après la table de vérité de l'implication, l'assertion est vraie.
3. $x\in]0,2[$. On peut alors trouver un réel $y\in[0,1]$ tel que $2y>x$ et $x\geq y$. En effet, $x/2\in ]0,1[$ et il suffit de choisir $x/2<y<\min(1,x)$. Dans ce cas, $x\geq y$ est vraie et $x\geq 2y$ est fausse. L'assertion est fausse.
4. Si $x=0$, alors les assertions $x\geq y$ et $x\geq 2y$ sont ou bien simultanément fausses (lorsque $y\in]0,1]$), ou bien simultanément vraies. L'assertion est donc vraie.