QCM — Initiation à la Logique

NiveauMoyen★★

Négations, quantificateurs, tables de vérité et implication : les automatismes, sans pièges grossiers.

Négation de $ \forall x\in\R, (x>2 \imp x^2>4)$ :

Corrigé · CNier $\forall$ donne $\exists$, et $\neg(P\imp Q)\eqv P\wedge\neg Q$. La négation de $x^2>4$ est $x^2\le 4$.

L'implication $P\imp Q$ est fausse. Que peut-on affirmer avec certitude ?

Corrigé · BUne implication n'est fausse que sur l'unique ligne « $P$ vrai, $Q$ faux ».

La contraposée de « $n^2$ impair $\imp n$ impair » est :

Corrigé · DContraposée de $P\imp Q$ : $\neg Q\imp\neg P$, avec $P=$« $n^2$ impair », $Q=$« $n$ impair ».

Sur $\R$, laquelle de ces propositions est vraie ?

Corrigé · CPour $x$ donné, $y=-x$ convient. A est fausse ($y\to-\infty$), B fausse ($y<0$), D fausse ($x\cdot 0=0$).

La négation de « $a\le x<b$ » (soit $x\ge a$ et $x<b$) est :

Corrigé · ADe Morgan : $\neg\big((x\ge a)\wedge(x<b)\big)=(x<a)\vee(x\ge b)$. Attention aux bornes.

Parmi ces formules, laquelle n'est pas une tautologie ?

Corrigé · D$(P\vee Q)\imp P$ est fausse pour $P$ faux et $Q$ vrai ; les trois autres sont toujours vraies.

« $P\imp Q$ » est logiquement équivalente à :

Corrigé · A$(P\imp Q)\eqv(\neg P\vee Q)$. La réponse D est la réciproque, non équivalente.

NiveauBon★★★

Simplifications, tautologies, unicité, dénombrement et récurrence : plusieurs résultats à combiner.

Simplifier $ \neg\big(P\vee(\neg P\wedge Q)\big)$ :

Corrigé · BAbsorption : $P\vee(\neg P\wedge Q)=P\vee Q$ ; puis De Morgan : $\neg(P\vee Q)=\neg P\wedge\neg Q$.

Sur $\R$, $ \forall x, \exists y, y^2=x $ est fausse. Sa négation (vraie) s'écrit :

Corrigé · C$\neg(\forall x \exists y)=\exists x \forall y$ puis on nie. Vraie car pour $x<0$, aucun $y$ réel ne convient.

Q10

Laquelle de ces implications est une tautologie (vraie pour tous $P,Q,R$) ?

Corrigé · ATransitivité de l'implication (syllogisme). D est fausse : $(P\vee Q)\wedge\neg P$ entraîne $Q$, pas $\neg Q$.

Q11

« $P\eqv Q$ » est équivalente à :

Corrigé · D$P\eqv Q$ est vraie quand $P,Q$ ont même valeur. A et B sont le ou exclusif ; C est toujours vraie.

Q12

La négation de « $\exists! x\in E, P(x)$ » (il existe un unique $x$) est :

Corrigé · B« Exactement un » se nie en « aucun » ou « au moins deux ».

Q13

Combien existe-t-il de connecteurs binaires distincts (fonctions de vérité $\{V,F\}^2\to\{V,F\}$) ?

Corrigé · CIl y a $2^2=4$ lignes possibles, chacune donnant $V$ ou $F$ : $2^{4}=16$ fonctions (dont $\wedge,\vee,\imp,\eqv,\ldots$).

Q14

On prouve $P(0)$ et $ \forall n\ge 1, P(n)\imp P(n+1) $ (sans montrer $P(0)\imp P(1)$). Que faut-il au minimum ajouter pour conclure $\forall n\in\N, P(n)$ ?

Corrigé · BLa chaîne d'hérédité ne démarre qu'à $1$. Or $P(0)$ ne permet pas d'atteindre $P(1)$ : il faut établir la base $P(1)$.

NiveauDifficile — type concours★★★★

Niveau concours/CPGE : paradoxe du buveur, associativité de l'équivalence, négation de la définition ε–N, récurrence sans base.

Q15

Sur un ensemble $E\ne\varnothing$, la proposition $ \exists x\in E, \big(P(x)\imp \forall y\in E, P(y)\big) $ est :

Corrigé · AParadoxe du buveur. Si $\forall y P(y)$, tout $x$ convient. Sinon il existe $x_0$ avec $\neg P(x_0)$ : l'implication a un antécédent faux, donc est vraie.

Q16

Si $ \forall \varepsilon>0, |a|<\varepsilon $ (avec $a\in\R$), alors :

Corrigé · DSi $a\ne 0$, alors $|a|>0$ et le choix $\varepsilon=\tfrac{|a|}{2}$ contredit l'hypothèse. Donc $a=0$.

Q17

La négation de $ \forall\varepsilon>0, \exists N\in\N, \forall n\ge N, |u_n-\ell|<\varepsilon $ est :

Corrigé · AOn échange chaque quantificateur ($\forall\leftrightarrow\exists$) et l'on nie l'inégalité : $<$ devient $\ge$.

Q18

Parmi ces affirmations sur les connecteurs, laquelle est vraie ?

Corrigé · CVérification par table de vérité : l'équivalence est associative (et commutative), l'implication ne l'est pas.

Q19

Soit $P(n): 9\mid(10^n+1)$. On a bien $ \forall n, P(n)\imp P(n+1) $, et pourtant $P(n)$ est fausse pour tout $n$. Pourquoi ?

Corrigé · B$10^n+1\equiv 1^n+1=2 [9]$, jamais divisible par $9$. L'implication $P(n)\imp P(n+1)$ est vraie car son antécédent est toujours faux.

Q20

Laquelle de ces équivalences est fausse en général ?

Corrigé · DLa forme correcte est $\big((P\vee Q)\imp R\big)\eqv\big((P\imp R)\wedge(Q\imp R)\big)$, avec un $\wedge$ (et non un $\vee$).

Q21

Pour montrer que $ \sqrt2+\sqrt3 $ est irrationnel, la stratégie correcte et minimale est :

Corrigé · CDe $\sqrt2+\sqrt3=r$ on tire $\sqrt3=r-\sqrt2$, puis en élevant au carré $3=r^2-2r\sqrt2+2$, d'où $\sqrt2=\tfrac{r^2-1}{2r}\in\Q$ : absurde.