Exercices corrigés : Logique et raisonnements (Prépa, 1re année)

1. Par définition, $Q\Rightarrow R$ est $(\neg Q)\vee R$, donc $P\Rightarrow(Q\Rightarrow R)$ est $(\neg P)\vee\big((\neg Q)\vee R\big)$. Par associativité de $\vee$, c'est $\big((\neg P)\vee(\neg Q)\big)\vee R$. Par De Morgan, $(\neg P)\vee(\neg Q)$ équivaut à $\neg(P\wedge Q)$. On obtient $\neg(P\wedge Q)\vee R$, qui est par définition $(P\wedge Q)\Rightarrow R$.

2. Non. Prenons $P$ fausse, $Q$ vraie, $R$ fausse.

• $P\Rightarrow Q$ est vraie car $P$ est fausse ; donc $(P\Rightarrow Q)\Rightarrow R$ a une prémisse vraie et une conclusion fausse : elle est fausse.
• $P\Rightarrow(Q\Rightarrow R)$ est vraie car $P$ est fausse.

Les deux assertions n'ont pas la même valeur de vérité dans ce cas, elles ne sont pas équivalentes. L'implication n'est pas associative : les parenthèses comptent.

3. $(P\Rightarrow Q)\wedge(P\Rightarrow R)$ est $\big((\neg P)\vee Q\big)\wedge\big((\neg P)\vee R\big)$. Par distributivité de $\vee$ sur $\wedge$ (appliquée avec $\neg P$ à la place de $P$), c'est $(\neg P)\vee(Q\wedge R)$, c'est-à-dire $P\Rightarrow(Q\wedge R)$.

On applique la méthode du cours : on garde l'ordre et les ensembles, on échange $\forall$ et $\exists$, on nie la propriété finale.

1. $f$ bornée : $\exists M\in\mathbb{R},\ \forall x\in\mathbb{R},\ |f(x)|\leq M$. Négation : $\forall M\in\mathbb{R},\ \exists x\in\mathbb{R},\ |f(x)|>M$. Aucun réel ne majore $|f|$ : pour tout seuil, $|f|$ le dépasse quelque part.

2. $\exists x\in\mathbb{R},\ f(x)=0$. Négation : $\forall x\in\mathbb{R},\ f(x)\neq 0$. La fonction ne s'annule jamais.

3. $\forall x\in\mathbb{R}_+,\ f(x)\geq 0$. Négation : $\exists x\in\mathbb{R}_+,\ f(x)<0$. Il existe un réel positif où $f$ est strictement négative. Écrire « $\exists x<0$ » serait une erreur : la condition $x\geq 0$ n'est pas niée.

4. $\exists N\in\mathbb{N},\ \forall n\geq N,\ u_{n+1}\geq u_n$. Négation : $\forall N\in\mathbb{N},\ \exists n\geq N,\ u_{n+1}<u_n$. Aussi loin que l'on aille, on trouve encore un rang où la suite décroît strictement.

5. $\exists T>0,\ \forall x\in\mathbb{R},\ f(x+T)=f(x)$. Négation : $\forall T>0,\ \exists x\in\mathbb{R},\ f(x+T)\neq f(x)$. Aucun réel $T>0$ n'est une période.

1. Vraie. Soit $x\in\mathbb{R}$. Le réel $y=-x$ vérifie $x+y=0$.

2. Fausse. Sa négation est $\forall y\in\mathbb{R},\ \exists x\in\mathbb{R},\ x+y\neq 0$. Soit $y\in\mathbb{R}$ ; avec $x=1-y$, on a $x+y=1\neq 0$. La négation est vraie, donc l'assertion est fausse. Comparée à 1, seul l'ordre des quantificateurs a changé.

3. Fausse. Sa négation est $\exists x\in\mathbb{R},\ \forall y\in\mathbb{R},\ xy\neq 1$. Le réel $x=0$ convient : pour tout $y$, $0\times y=0\neq 1$.

4. Vraie. Le réel $x=0$ vérifie $0\times y=0$ pour tout $y\in\mathbb{R}$.

5. Vraie. Soit $n\in\mathbb{N}$. L'entier $m=n^2+1$ vérifie $m>n^2$.

6. Fausse. Sa négation est $\forall m\in\mathbb{N},\ \exists n\in\mathbb{N},\ m\leq n^2$. Soit $m\in\mathbb{N}$, prenons $n=m$. Si $m=0$, $n^2=0\geq m$. Si $m\geq 1$, $n^2=m\cdot m\geq m$. Dans les deux cas $m\leq n^2$ : la négation est vraie.

1. Supposons par l'absurde que $\dfrac{\ln 2}{\ln 10}\in\mathbb{Q}$. Comme $1<2<10$, on a $\ln 2>0$ et $\ln 10>0$, donc ce quotient est strictement positif : on peut l'écrire $\dfrac{p}{q}$ avec $p,q\in\mathbb{N}^*$.

Alors $q\ln 2=p\ln 10$, puis, en appliquant l'exponentielle, $2^q=10^p=2^p\,5^p$. Comme $5^p>1$, on a $2^q>2^p$, donc $q>p$. En divisant par $2^p$ : $$2^{q-p}=5^p.$$ Le membre de gauche est pair car $q-p\geq 1$. Le membre de droite est impair, comme produit de nombres impairs. C'est une contradiction. Donc $\dfrac{\ln 2}{\ln 10}\notin\mathbb{Q}$.

2. Supposons par l'absurde que $\sqrt{6}\in\mathbb{Q}$. Comme $\sqrt{6}>0$, on écrit $\sqrt{6}=\dfrac{p}{q}$ avec $p,q\in\mathbb{N}^*$ et la fraction irréductible. Alors $p^2=6q^2=2(3q^2)$ est pair, donc $p$ est pair (résultat du cours) : $p=2k$ avec $k\in\mathbb{N}^*$. Il vient $4k^2=6q^2$, soit $2k^2=3q^2$. Donc $3q^2$ est pair. Si $q$ était impair, $3q^2$ serait impair comme produit d'impairs ; donc $q$ est pair. Ainsi $2$ divise $p$ et $q$, ce qui contredit l'irréductibilité. Donc $\sqrt{6}\notin\mathbb{Q}$.

3. Supposons par l'absurde que $r=\sqrt{2}+\sqrt{3}\in\mathbb{Q}$. Alors $r^2=2+2\sqrt{6}+3=5+2\sqrt{6}$, donc $$\sqrt{6}=\frac{r^2-5}{2}.$$ Ce nombre est rationnel, car $\mathbb{Q}$ est stable par produit, différence et division par $2$. Cela contredit la question 2. Donc $\sqrt{2}+\sqrt{3}\notin\mathbb{Q}$.

1. Soit $n\in\mathbb{Z}$. Les cas « $n$ pair » et « $n$ impair » recouvrent $\mathbb{Z}$.

• Si $n=2k$ avec $k\in\mathbb{Z}$ : $n^2=4k^2$, le reste est $0$.
• Si $n=2k+1$ avec $k\in\mathbb{Z}$ : $n^2=4(k^2+k)+1$, le reste est $1$.

2. Supposons par l'absurde qu'il existe $a,b,k\in\mathbb{Z}$ tels que $a^2+b^2=4k+3$. D'après la question 1, $a^2=4u+r$ et $b^2=4v+s$ avec $u,v\in\mathbb{Z}$ et $r,s\in\{0,1\}$. Alors $a^2+b^2=4(u+v)+(r+s)$ avec $0\leq r+s\leq 2<4$ : par unicité de la division euclidienne, le reste de $a^2+b^2$ par $4$ est $r+s\in\{0,1,2\}$. Or l'écriture $4k+3$ montre que ce reste vaut $3$. Contradiction.

3. $2027=4\times 506+3$. D'après la question 2, $2027$ n'est pas somme de deux carrés d'entiers.

4. Soit $n\in\mathbb{Z}$. Par division euclidienne par $3$, $n$ s'écrit $3k$, $3k+1$ ou $3k+2$ avec $k\in\mathbb{Z}$ ; ces trois cas recouvrent $\mathbb{Z}$.

• Si $n=3k$ : $3$ divise le facteur $n$.
• Si $n=3k+1$ : $2n+1=6k+3=3(2k+1)$.
• Si $n=3k+2$ : $n+1=3(k+1)$.

Dans chaque cas, l'un des facteurs est multiple de $3$, donc $n(n+1)(2n+1)$ est divisible par $3$.

1. Analyse. Soit $f$ une solution et $x\in\mathbb{R}$. La relation en $x$ et en $-x$ donne $$\begin{cases}f(x)+2f(-x)=x^2+x\\ 2f(x)+f(-x)=x^2-x\end{cases}$$ En retranchant la première ligne au double de la seconde : $3f(x)=2x^2-2x-x^2-x=x^2-3x$, donc $f(x)=\dfrac{x^2}{3}-x$. Le seul candidat est $f:x\mapsto\dfrac{x^2}{3}-x$.

Synthèse. Pour ce candidat et tout $x\in\mathbb{R}$ : $f(-x)=\dfrac{x^2}{3}+x$ et $$f(x)+2f(-x)=\frac{x^2}{3}-x+\frac{2x^2}{3}+2x=x^2+x.$$ Conclusion. L'unique solution est $x\mapsto\dfrac{x^2}{3}-x$.

2. Analyse. Soit $f$ une solution. D'après le cours, $f=g+h$ avec $g(x)=\dfrac{f(x)+f(-x)}{2}$ paire et $h(x)=\dfrac{f(x)-f(-x)}{2}$ impaire. La condition donne $g(x)=\dfrac{x^2}{2}$ pour tout $x$. Donc $f(x)=\dfrac{x^2}{2}+h(x)$ avec $h$ impaire. Aucune condition n'apparaît sur $h$.

Synthèse. Soit $h:\mathbb{R}\to\mathbb{R}$ impaire quelconque et $f(x)=\dfrac{x^2}{2}+h(x)$. Pour tout $x$ : $f(x)+f(-x)=\dfrac{x^2}{2}+\dfrac{x^2}{2}+h(x)+h(-x)=x^2$, car $h(-x)=-h(x)$.

Conclusion. Les solutions sont exactement les fonctions $x\mapsto\dfrac{x^2}{2}+h(x)$ où $h$ est une fonction impaire quelconque. Il y en a une infinité : l'analyse n'aboutit pas toujours à un candidat unique.

1. Soit $x\in\mathbb{R}$. Le réel $M=f(x)$ vérifie $f(x)\leq M$ : $A$ est vraie, quelle que soit $f$.

Si $B$ est vraie, un réel $M$ vérifie $f(x)\leq M$ pour tout $x$ ; pour chaque $x$, ce même $M$ convient dans $A$. Donc $B\Rightarrow A$.

Pour $f=\mathrm{id}$, la négation de $B$, « $\forall M\in\mathbb{R},\ \exists x\in\mathbb{R},\ f(x)>M$ », est vraie : pour $M$ donné, $x=M+1$ convient. Donc $B$ est fausse ($B$ signifie « $f$ est majorée »).

2. Négation de $(U)$ : $$\exists\varepsilon>0,\ \forall\eta>0,\ \exists (x,y)\in\mathbb{R}^2,\ |x-y|\leq\eta\ \text{et}\ |f(x)-f(y)|>\varepsilon.$$

3. Soit $f(x)=3x+1$ et $\varepsilon>0$. Posons $\eta=\dfrac{\varepsilon}{3}>0$. Soit $(x,y)\in\mathbb{R}^2$ avec $|x-y|\leq\eta$. Alors $|f(x)-f(y)|=3|x-y|\leq 3\eta=\varepsilon$. Donc $f$ vérifie $(U)$.

4. Soit $f(x)=x^2$. Montrons la négation de $(U)$ avec $\varepsilon=1$. Soit $\eta>0$. Posons $x=\dfrac{1}{\eta}$ et $y=x+\eta$. Alors $|x-y|=\eta\leq\eta$ et $$|f(y)-f(x)|=(y-x)(y+x)=\eta\left(\frac{2}{\eta}+\eta\right)=2+\eta^2>1.$$ La négation de $(U)$ est vraie : $x\mapsto x^2$ ne vérifie pas $(U)$.

5. Supposons $(U)$. Soient $x\in\mathbb{R}$ et $\varepsilon>0$. Par $(U)$, il existe $\eta>0$ tel que pour tout couple $(x',y)$ vérifiant $|x'-y|\leq\eta$, on ait $|f(x')-f(y)|\leq\varepsilon$. En particulier avec $x'=x$ : pour tout $y$ tel que $|x-y|\leq\eta$, $|f(x)-f(y)|\leq\varepsilon$. C'est $(C)$.

Pour $f(x)=x^2$ : soient $x\in\mathbb{R}$ et $\varepsilon>0$. Posons $\eta=\min\left(1,\dfrac{\varepsilon}{2|x|+1}\right)>0$. Soit $y$ tel que $|x-y|\leq\eta$. Alors $|y+x|=|(y-x)+2x|\leq|y-x|+2|x|\leq 1+2|x|$, donc $$|y^2-x^2|=|y-x|\,|y+x|\leq\eta\,(2|x|+1)\leq\varepsilon.$$ Ainsi $x\mapsto x^2$ vérifie $(C)$.

Commentaire. $(C)$ est la continuité de $f$ sur $\mathbb{R}$ : le $\eta$ peut dépendre de $x$. Dans $(U)$, le quantificateur $\forall x$ est placé après $\exists\eta$ : un même $\eta$ doit convenir pour tous les points. La fonction carré montre que $(C)\Rightarrow(U)$ est fausse : le $\eta$ construit tend vers $0$ quand $|x|$ grandit, et la question 4 prouve qu'on ne peut pas faire mieux. La propriété $(U)$ s'appelle continuité uniforme ; elle est étudiée dans le chapitre sur la continuité.

1. $96=32\times 3=2^5(2\times 1+1)$ : $(a,b)=(5,1)$. $45=2^0(2\times 22+1)$ : $(a,b)=(0,22)$.

2. Pour $n\in\mathbb{N}^*$, notons $P(n)$ : « il existe $(a,b)\in\mathbb{N}^2$ tel que $n=2^a(2b+1)$ ».

Initialisation. $1=2^0(2\times 0+1)$, donc $P(1)$ est vraie.

Hérédité. Soit $n\geq 1$ tel que $P(k)$ soit vraie pour tout $k\in\llbracket 1,n\rrbracket$.

• Si $n+1$ est impair, alors $n$ est pair, $b=\dfrac{n}{2}\in\mathbb{N}$ et $n+1=2^0(2b+1)$.
• Si $n+1$ est pair, $n+1=2m$ avec $m\in\mathbb{N}$. On a $m\geq 1$ et $m=\dfrac{n+1}{2}\leq n$ car $n\geq 1$. Par hypothèse, $P(m)$ est vraie : $m=2^a(2b+1)$ avec $(a,b)\in\mathbb{N}^2$. Alors $n+1=2^{a+1}(2b+1)$.

Dans les deux cas $P(n+1)$ est vraie.

Conclusion. Par récurrence forte, $P(n)$ est vraie pour tout $n\geq 1$. Une récurrence simple ne suffit pas : on utilise le rang $m=\frac{n+1}{2}$, qui n'est pas $n$ en général.

3. Soient $(a,b)$ et $(c,d)$ dans $\mathbb{N}^2$ tels que $2^a(2b+1)=2^c(2d+1)$. Supposons par l'absurde $a\neq c$ ; les rôles étant symétriques, on peut supposer $a<c$. En divisant par $2^a$ : $$2b+1=2^{c-a}(2d+1).$$ Le membre de gauche est impair ; celui de droite est pair car $c-a\geq 1$. Contradiction. Donc $a=c$. En divisant par $2^a$, il reste $2b+1=2d+1$, donc $b=d$.

Conclusion. Tout $n\in\mathbb{N}^*$ s'écrit de façon unique $2^a(2b+1)$ : $2^a$ est la plus grande puissance de $2$ qui divise $n$, et $2b+1$ la partie impaire de $n$.

1. $F_2=1$, $F_3=2$, $F_4=3$, $F_5=5$, $F_6=8$, $F_7=13$, $F_8=21$.

2. a) Pour $n\geq 1$, notons $P(n)$ : « $F_n\in\mathbb{N}$ et $F_n\geq 1$ ». Initialisation. $F_1=1$ et $F_2=1$ : $P(1)$ et $P(2)$ sont vraies. Hérédité. Soit $n\geq 1$ tel que $P(n)$ et $P(n+1)$ soient vraies. Alors $F_{n+2}=F_{n+1}+F_n$ est un entier, somme de deux entiers, et $F_{n+2}\geq 1+1\geq 1$. Donc $P(n+2)$. Conclusion. Par récurrence double, $P(n)$ est vraie pour tout $n\geq 1$.

b) Soit $k\geq 2$. Alors $F_{k+1}-F_k=F_{k-1}\geq 1$ d'après a), car $k-1\geq 1$. Donc $F_{k+1}>F_k$ et même $F_{k+1}\geq F_k+1$, ces nombres étant entiers. Montrons par récurrence simple $F_k\geq k-1$ pour $k\geq 2$. Pour $k=2$ : $F_2=1\geq 1$. Si $F_k\geq k-1$ pour un $k\geq 2$, alors $F_{k+1}\geq F_k+1\geq k$. Par récurrence, $F_k\geq k-1$ pour tout $k\geq 2$.

3. Pour $n\in\mathbb{N}$, notons $S(n)$ : « $\sum_{k=0}^{n}F_k=F_{n+2}-1$ ». Initialisation. $\sum_{k=0}^{0}F_k=0$ et $F_2-1=0$. Hérédité. Soit $n\in\mathbb{N}$ tel que $S(n)$ soit vraie. Alors $$\sum_{k=0}^{n+1}F_k=F_{n+2}-1+F_{n+1}=F_{n+3}-1.$$ Conclusion. Par récurrence simple, $S(n)$ est vraie pour tout $n\in\mathbb{N}$.

4. Pour $n\geq 1$, notons $C(n)$ : « $F_{n+1}F_{n-1}-F_n^2=(-1)^n$ ». Initialisation. $F_2F_0-F_1^2=0-1=-1=(-1)^1$. Hérédité. Soit $n\geq 1$ tel que $C(n)$ soit vraie. Alors, en utilisant $F_{n+1}-F_n=F_{n-1}$ (valable car $n\geq 1$) : $$\begin{aligned}F_{n+2}F_n-F_{n+1}^2&=(F_{n+1}+F_n)F_n-F_{n+1}^2=F_n^2-F_{n+1}(F_{n+1}-F_n)\\&=F_n^2-F_{n+1}F_{n-1}=-(-1)^n=(-1)^{n+1}.\end{aligned}$$ Donc $C(n+1)$ est vraie. Conclusion. Par récurrence, $C(n)$ est vraie pour tout $n\geq 1$.

5. a) $20=13+5+2=F_7+F_5+F_3$ et $33=21+8+3+1=F_8+F_6+F_4+F_2$.

b) Pour $N\geq 1$, notons $Z(N)$ : « $N$ est une somme de termes $F_k$, d'indices $k\geq 2$ deux à deux distincts ». Initialisation. $1=F_2$ : $Z(1)$ est vraie. Hérédité. Soit $n\geq 1$ tel que $Z(r)$ soit vraie pour tout $r\in\llbracket 1,n\rrbracket$. Posons $N=n+1\geq 2$ et $E=\{k\geq 2,\ F_k\leq N\}$. L'ensemble $E$ contient $2$ car $F_2=1\leq N$ ; il est majoré par $N+1$ car, d'après 2 b), $k\in E$ implique $k-1\leq F_k\leq N$. C'est une partie non vide et majorée de $\mathbb{N}$ : elle admet un plus grand élément $m$. Ainsi $F_m\leq N<F_{m+1}$.

• Si $F_m=N$, $Z(N)$ est vraie.
• Sinon, posons $r=N-F_m$. On a $r\geq 1$ et $r\leq N-1=n$ car $F_m\geq 1$. Par hypothèse de récurrence forte, $r=F_{k_1}+\dots+F_{k_s}$ avec des indices $k_i\geq 2$ deux à deux distincts. De plus $r<F_{m+1}-F_m=F_{m-1}\leq F_m$, l'inégalité $F_{m-1}\leq F_m$ venant de $F_m-F_{m-1}=F_{m-2}\geq 0$. Donc chaque $F_{k_i}\leq r<F_m$, ce qui impose $k_i\neq m$. Alors $N=F_m+F_{k_1}+\dots+F_{k_s}$ avec des indices $\geq 2$ deux à deux distincts.

Conclusion. Par récurrence forte, $Z(N)$ est vraie pour tout $N\geq 1$. La récurrence est forte car on utilise le rang $r$, inconnu à l'avance.