Lycée Henri-IV (PCSI) TD 01

Logique

Assertions, connecteurs, quantificateurs

Autocorrection A.
Soit a, b, c ∈ R et P, Q et R trois assertions. Écrire la négation des assertions suivantes.

(i) P et non(Q) ; (iii) ∃x ∈ [1, +∞[ : a > b + x ;

(ii) (P ⇒ Q) et R ; (iv) a = b = c.

Autocorrection B.
Écrire une assertion quantifiée traduisant le fait que tout réel positif est le carré d’un nombre réel.

Exercice 1.
Soit (un )n>0 une suite de nombres réels. Traduire à l’aide de quantificateurs chacune des assertions
suivantes. On en donnera également la négation.
(i) La suite (un )n>0 est nulle.
(ii) La suite (un )n>0 est croissante.
(iii) La suite (un )n>0 est strictement décroissante.
(iv) La suite (un )n>0 ne prend que des valeurs strictement inférieures à 2.
(v) La suite (un )n>0 ne prend que des valeurs strictement inférieures à une certaine constante.
(vi) La suite (un )n>0 est stationnaire (c’est-à-dire constante à partir d’un certain rang).
(vii) La suite (un )n>0 est bornée.
(viii) La suite (un )n>0 s’annule au moins une fois.
(ix) La suite (un )n>0 s’annule au plus une fois.

Exercice 2.
Dans cet exercice, A désigne un ensemble d’entiers naturels. Traduire à l’aide de quantificateurs
chacune des assertions suivantes. On en donnera également la négation.
(i) L’ensemble A contient tous les entiers pairs.
(ii) L’ensemble A ne contient que des entiers pairs.
(iii) L’ensemble A ne contient pas deux entiers consécutifs.
(iv) L’ensemble A est stable par somme.
(v) L’ensemble A contient exactement un élément.
(vi) L’ensemble A contient au plus un élément.
(vii) L’ensemble A contient tous les entiers à partir d’un certain rang.
(viii) L’ensemble A est infini.
(ix) L’ensemble A contient des intervalles entiers arbitrairement grands.
(x) On peut toujours trouver une puissance de 2 entre deux éléments de A.

1
 Calcul propositionnel, tables de vérité

Exercice 3.
Soit P, Q, R, H1 , H2 des assertions. Montrer à l’aide de tables de vérité que les assertions suivantes
sont toujours vraies (on dit qu’il s’agit de tautologies).

(i) (non(P) ⇒ P) ⇔ P ; (iv) [(P ⇒ Q) et (Q ⇒ P)] ⇔ (P ⇔ Q) ;

(ii) P ⇒ (Q ⇒ P) ; (v) [(H1 ⇒ P) et (H2 ⇒ P) et (H1 ou H2 )] ⇒ P ;
(iii) (P ⇒ Q) ⇔ (non(Q) ⇒ non(P)) ; (vi) (P ⇒ (Q ⇒ R)) ⇒ [(P ⇒ Q) ⇒ (P ⇒ R)].

Exercice 4. “

1. Construire à l’aide des assertions « P », « Q » et des connecteurs logiques « non » et « et » une

proposition équivalente à « P ou Q ».
2. Même question pour l’assertion « P ⇒ Q » et pour « P ⇔ Q ».

Exercice 5 (Barre de Sheffer).

Si P et Q sont deux assertions, on note P ↑ Q et on appelle barre de Sheffer de P et Q l’assertion
non(P et Q).
À l’aide des assertions P et Q et avec la barre de Sheffer comme unique connecteur logique, construire
des assertions équivalentes à

(i) non(P) ; (iii) P ou Q ; (v) P ⇔ Q.

(ii) P et Q ; (iv) P ⇒ Q ;

Logique extra-mathématique

Exercice 6 (Tâche de sélection de Wason).

Quatre cartes ont un nombre imprimé sur une de leurs faces et une lettre de l’autre côté. Elles sont

posées sur une table et montrent A B 1 2 . Quelles cartes doit-on retourner pour savoir si
les cartes respectent la règle : « au dos de chaque voyelle se trouve un nombre pair. » ?

Exercice 7. Godement, Cours d’algèbre “

À la suite d’une représentation de Pelléas et Mélisande, un journaliste hésite entre les deux rédactions
suivantes :
(i) Jamais le rôle de Mélisande n’a été si bien chanté.
(ii) Jamais si jeune cantatrice, aux si beaux cheveux, n’a si bien chanté Mélisande.
Lequel de ces compliments est le plus fort ?

Exercice 8.

Qu’est-ce que le panneau interdit ?

2
 Modes de raisonnement

Autocorrection C.
Montrer ∀x ∈ R, ∃y ∈ R : y < x.

Autocorrection D.
Soit I = [0, 1]. Montrer ∃x ∈ I : ∀y ∈ I, x 6 y.

Exercice 9.
Déterminer si chacune des assertions suivantes est vraie ou fausse (en le démontrant).

(i) 1 + 1 = 2 ⇒ 1 + 1 = 3 ; (viii) ∃!z ∈ R : cos z = 0 ;

(ii) 1 + 1 = 3 ⇒ 1 + 1 = 2 ; (ix) ∃x ∈ R : (x 6 x2 et x = e−x ) ;
(iii) 1 = 0 ⇒ ∃p, q, r ∈ Z : p3 + q3 + r3 = 114 ; (x) ∀n ∈ N, ∃m ∈ N : n + m est impair ;
(iv) ∀x ∈ R, x > 2 ⇒ x > 3 ; (xi) ∀n ∈ N, ∃m ∈ N : n m est impair ;
1 1 (xii) ∃η > 0 : ∀x ∈ R, x 6 η ⇒ x2 6 1.
(v) ∀x, y ∈ R∗ , x < y ⇒ > ;
x y (xiii) ∃η > 0 : ∀x ∈ R, |x| 6 η ⇒ x2 6 1.
(vi) ∀n ∈ N, n3 − n est pair ; (xiv) ∃η > 0 : ∀x ∈ R, |x| 6 η ⇒ x2 6 10−18 ;
√
(vii) ∃x ∈ R+ : x < x ; (xv) ∀ε > 0, ∃η > 0 : ∀x ∈ R, |x| 6 η ⇒ x2 6 ε.

Exercice 10.
Déterminer si chacune des assertions suivantes est vraie ou fausse (en le démontrant). On énoncera
la négation des assertions fausses.

(i) ∀x ∈ R, ∀y ∈ R, x + y > 0 ; (v) ∀n ∈ N, ∃m ∈ N : n + m est pair ;

(ii) ∀x ∈ R, ∃y ∈ R, x + y > 0 ; (vi) ∃n ∈ N : ∀m ∈ N, n + m est pair ;
(iii) ∃x ∈ R, ∀y ∈ R, x + y > 0 ; (vii) ∀y ∈ R∗+ , ∃x ∈ R : y = ex ;
(iv) ∃x ∈ R, ∃y ∈ R, x + y > 0 ; (viii) ∃y ∈ R∗+ : ∀x ∈ R, y = ex .

Exercice 11.
Déterminer si chacune des assertions suivantes est vraie ou fausse (en le démontrant). On énoncera
la négation des assertions fausses.

(i) ∀x ∈ R, ∀y ∈ R, xy = 0 ⇒ x = 0 ;


(iii) ∀n ∈ Z, (n > 0 ou n 6 0) ;
(ii) ∀x ∈ R, ∀y ∈ R, xy = 0 ⇒ x = 0 ; (iv) (∀n ∈ Z, n > 0) ou (∀n ∈ Z, n 6 0).

Exercice 12. “
Voici des extraits de preuves issus de livres mathématiques. Sans chercher à comprendre les démons-
tration, ni même ce dont il est question, déterminer le type de preuve employé à chaque fois.
(i) (Patrick Dehornoy, La théorie des ensembles, Calvage et Mounet, 2017).
Proposition (axiome d’infini I). Si le système ZFCfini est consistant, il ne prouve pas
l’axiome d’infini.
Démonstration. Supposons que le système ZFCfini est consistant et prouve l’axiome
d’infini. Par le théorème de complétude, ZFCfini a alors un modèle M, et, puisque
ZFfini prouve Inf, le modèle M est modèle de ZF. Mais alors la structure (Vω , ∈)M est
un modèle de ZFCfini qui ne satisfait pas Inf, ce qui contredit l’hypothèse.

3
 (ii) (Éric Amar et Étienne Matheron, Analyse complexe, Cassini, 2004)
Corollaire 4.4.5. (Ω connexe.) Si f ∈ H(Ω) n’est pas identiquement nulle, alors f n’a
qu’un nombre fini de zéros sur tout compact de Ω.
Preuve. Si f possédait une infinité de zéros sur un compact K de Ω, alors Z(f) aurait
un point d’accumulation dans K, donc dans Ω, et f serait identiquement nulle par le
principe des zéros isolés.
(iii) (Jacob Lurie, Higher Topos Theory, Princeton University Press, 2009)
Corollary [Link]. Let C be an n-category and p : K → C be a diagram. Then C/p is an
n-category.
Proof. If n 6 0, this follows easily from Examples [Link]. and [Link]. We may therefore
suppose that n > 1. [...]
(iv) (Antonio Machì, Gruppi, Springer, 2007)
1.31. Teorema. I sottogruppi di un gruppo ciclico sono ciclici.
Dim. Se il gruppo è infinito, è isomorfo a Z, e i sottogruppi di Z sono ciclici, come
visto nell’Es. 1 di 1.21. Se G è finito, la dimostrazione è analoga a quella per Z.[...]
(v) (Martin Brandenburg, Einführung in die Kategorientheorie, 2e éd., Springer, 2015).
Lemma 4.1.16 (Charakterisierung von Isomorphismen). Sei f : A → B ein Homomor-
phismus zwischen Strukturen eines Typs τ. Genau dann ist f ein Isomorphismus,
wenn die zugrunde liegende Abbildung U(f) : U(A) → U(B) von Mengen bijektiv
ist.
Beweis. Wenn f ein Isomorphismus ist, so ist nach Lemma 3.2.4 auch U(f) ein Isomor-
phismus, also bijektiv. Sei umgekehrt U(f) [...] bijektiv[...]

Démonstration des implications (dont contraposée)

Exercice 13. “
La conjecture de Goldbach forte affirme que tout nombre pair > 4 est la somme de deux nombres pre-
miers. La conjecture de Goldbach faible affirme que tout nombre impair > 7 est la somme de trois
nombres premiers.

1. Montrer que la conjecture forte implique la conjecture faible.

2. En 2013, Harald Helfgott a démontré la conjecture de Goldbach faible.
Que peut-on en déduire sur la conjecture forte ?

Exercice 14. “
Montrer l’assertion ∀x, y ∈ R, x + y > 2 ⇒ x > 1 ou y > 1.
Énoncer précisément la réciproque de cette assertion, et déterminer si elle est vraie ou fausse.

Exercice 15+ . “
Soit A, B ∈ R. Montrer que (∀ε > 0, A 6 B + ε) ⇒ A 6 B.

Exercice 16+ (Si je bois, tout le monde boit).

On considère une propriété P(x) qui dépend d’un réel x. Que penser de l’assertion suivante ?

∃x ∈ R : (P(x) =⇒ ∀y ∈ R, P(y)) .

4
 Démonstration des équivalences (dont analyse-synthèse)

Exercice 17+ .
Soit (un )n>0 une suite de nombres réels. Montrer que les assertions suivantes sont équivalentes.

(i) ∀A ∈ R, ∃n ∈ N : un > A ; (ii) ∀A ∈ R, ∃n ∈ N : un > A.

Exercice 18.
Soit f : R → R une fonction. On dit que f est strictement croissante si ∀x, y ∈ R, x < y ⇒ f(x) < f(y).
Montrer que f est strictement croissante si et seulement si
∀a, b ∈ R, a 6 b ⇔ f(a) 6 f(b).

Exercice 19+ .
Soit a, b ∈ R.
Montrer que l’assertion ∀x ∈ ]0, 1[ , ax + b > 0 est équivalente à (b > 0 et a + b > 0).

Exercice 20.
Le but de l’exercice est de déterminer toutes les fonctions f : R → R telles que
∀x, y ∈ R, x f(x) + y2 + f(xy) = f(x + y)2 − f(x)f(y). (z)

On procède par analyse et synthèse.

1. Soit f : R → R une fonction vérifiant (z).

(a) En appliquant judicieusement (z), déterminer f(0).
(b) Montrer que ∀y ∈ R, f(y)2 = y2 .
Que peut-on en déduire sur f ?
(c) Montrer que ∀x ∈ R, f(x) = x.
2. Conclure.

Exercice 21. “
Déterminer les fonctions f : R → R telles que ∀x, y ∈ R, f(xy) = f(x) + f(y).

Exercice 22+ .
Déterminer les x ∈ R tels que ∀n ∈ N, xn+2 6 xn+1 + xn .

Disjonction de cas et preuves des disjonctions

Exercice 23.
Soit n ∈ N.
Montrer qu’il existe m ∈ N tel que la somme n + m soit impaire et le produit nm soit pair.

Exercice 24.
Soit x ∈ R tel que x2 > x. Montrer que x 6 0 ou x > 1.

Exercice 25.
Montrer ∀x ∈ R, (x 6∈ Q ou ∃n ∈ N∗ : nx ∈ Z).

5
 Récurrence

Autocorrection E.
En calculant les premières valeurs, conjecturer une formule pour la somme 1 + 3 + 5 + · · · + (2n − 1)
des premiers nombres impairs, puis la démontrer par récurrence.

Autocorrection F.
On définit une suite (un )n∈N par

u0 = 0, u1 = 1, et ∀n > 0, un+2 = 5 un+1 − 6 un .

Montrer que pour tout n ∈ N, un = 3n − 2n .

Exercice 26.
Montrer que 1 + 5 + 9 + · · · + (4n − 3) = 2n2 − n.

Exercice 27 (Inégalité de Bernoulli).

Montrer ∀x > 0, ∀n ∈ N∗ , (1 + x)n > 1 + nx.

Exercice 28.
1 1 1 √
Montrer que ∀n > 1, √ + √ + · · · + √ > n.
1 2 n

Exercice 29+ .
Montrer que pour tous a, b > 0 distincts et tout n > 1, on a l’inégalité

2n−1 (an + bn ) > (a + b)n .

Exercice 30 (Majoration des nombres de Fibonacci).

On définit la suite (Fn )n∈N en posant F0 = 0 et F1 = 1 et, pour tout n ∈ N, Fn+2 = Fn + Fn+1 .
 n−1
7
1. Montrer par récurrence que ∀n ∈ N, Fn 6 .
4
2+ Optimiser : quelle est la plus petite valeur α telle que l’on ait ∀n ∈ N∗ , Fn 6 αn−1 ?

Exercice 31.
Montrer que la somme de trois cubes (d’entiers positifs) consécutifs est divisible par 9.

Exercice 32 (Équation de Pell-Fermat). “

1. Montrer que, pour tout n ∈ N, il existe des entiers naturels an et bn tels que
√ √
(3 + 2 2)n = an + bn 2.
√
2. Que dire de (3 − 2 2)n ?
3. En déduire qu’il existe une infinité de couples d’entiers (x, y) ∈ N2 tels que x2 − 2y2 = 1.

Exercice 33+ . “
Montrer que tout nombre entier > 12 peut s’écrire sous la forme 4a + 5b, pour des entiers naturels a
et b.

6
Exercice 34+ .

0. Avant de chercher à y répondre, comprendre pourquoi les deux questions suivantes ne sont
pas les mêmes. Y a-t-il un lien logique entre les deux ?
1. Pour tout entier n > 1, montrer qu’il existe a1 , . . . , an ∈ N∗ tels que a21 + · · · + a2n soit un carré
parfait.
2. Montrer qu’il existe une suite (an )n>1 d’entiers strictement positifs tels que, pour tout n ∈ N,
a21 + · · · + a2n soit un carré parfait.

Exercice 35+ . “
On suppose que sur un circuit se trouvent un certain nombre de dépôts d’essence, contenant à eux
tous juste assez d’essence pour faire un tour du circuit. Montrer qu’en partant avec un réservoir vide
d’un point bien choisi, il est possible de faire un tour du circuit sans jamais manquer d’essence.

Exercice 36.
La « preuve » suivante prétend montrer par récurrence sur n > 1 qu’étant donné n nombres réels
u1 , u2 , . . . , un ∈ R, ils sont en fait tous égaux.

Pour n ∈ N∗ , on note P(n) l’assertion

« quels que soient u1 , . . . , un ∈ R, on a u1 = u2 = · · · = un . »
Montrons ∀n ∈ N∗ , P(n) par récurrence.

Initialisation. S’il n’y a qu’un nombre u1 , il n’y a rien à montrer, ce qui montre P(1).
Hérédité. Soit n > 1 un entier tel que P(n).
Montrons P(n + 1).
Soit u1 , u2 , . . . , un , un+1 ∈ R.
D’après P(n), on a déjà u1 = u2 = · · · = un .
Par ailleurs, si l’on pose u10 = u2 , u20 = u3 , . . . , un0 = un+1 et que l’on applique P(n) à la
famille (u10 , . . . , un0 ), on obtient u10 = · · · = un−1
0
= un0 , c’est-à-dire u2 = · · · = un = un+1 .
Cela entraîne que u1 = u2 = · · · = un = un+1 , et montre donc la propriété voulue.

Le résultat est évidemment faux. Où est le problème ?

Exercice 37++ (Tous les chemins mènent à Rome).

a
Le dessin ci-contre montre un circuit de n = 5 villes vérifiant deux b
propriétés : b
b
I de chaque ville partent deux routes, étiquetées a et b ;
a a
I il existe une suite d’instructions (ici, aabb convient, par exemple)
a
qui amène de n’importe quelle ville du circuit à la ville entourée. a
b
Pour quelles valeurs de n > 3 peut-on construire un tel circuit ?
b

Exercice 38++ .
Dans un tournoi d’ordre n (au sens mathématique), n > 2 équipes s’affrontent une fois chacune.
Chaque match désigne un vainqueur (il n’y a donc pas de match nul).
1. Montrer que quelle que soit l’issue du tournoi, il sera possible de numéroter les équipes É1 , É2 , . . . , Én
de telle sorte que, pour tout 1 6 i < n, l’équipe Éi ait battu l’équipe Éi+1 (théorème de Rédei, 1934).
2. Un tournoi est dit équilibré si chaque équipe a gagné autant de matchs qu’elle en a perdu. Montrer
qu’il existe un tournoi équilibré d’ordre n si et seulement si n est impair.

7
 Petits problèmes

Exercice 39. “
Soit f : R → R une fonction. On dit que f est bornée si

∃M ∈ R : ∀x ∈ R, |f(x)| 6 M.

1. Écrire avec des quantificateurs l’assertion « f n’est pas bornée ».

2. Donner (avec démonstration) un exemple de fonction bornée et un exemple qui ne l’est pas.
3. Quelles sont les fonctions f : R → R vérifiant la propriété ∀x ∈ R, ∃M ∈ R : |f(x)| 6 M obtenue
en échangeant les deux quantificateurs ?
4. Montrer que f est bornée sur R si et seulement si ∃a, b ∈ R : ∀x ∈ R, a 6 f(x) 6 b.
5. Montrer que f est bornée sur R si et seulement si

∃C ∈ R : ∀x, y ∈ R, f(x) − f(y) 6 C.

Exercice 40+ . “
On définit les nombres de Fibonacci (Fn )n>1 par récurrence de la façon suivante :

F1 = F2 = 1 et ∀n > 1, Fn+2 = Fn+1 + Fn .

1. Calculer les nombres de Fibonacci (Fn ), pour 1 6 n 6 10.

2. Montrer que pour tout n > 1, il y a exactement Fn+1 façons de paver un échiquier de taille 2 × n
avec des dominos.
3. Démontrer l’assertion ∀n > 2, ∀m > 1, Fn+m = Fn−1 Fm + Fn Fm+1 .
4. Démontrer l’assertion ∀n > 2, F2n = Fn−1 Fn+1 + (−1)n+1 .
5. Démontrer que pour tout n > 1, on a

F1 F2 + F2 F3 + · · · + F2n−1 F2n = F22n et F1 F2 + F2 F3 + · · · + F2n F2n+1 = F22n+1 − 1.

Exercice 41++ (Buckets of fish). Hamkins, Proof and the Art of Mathematics
Le jeu de Buckets of fish est un jeu à deux joueurs. Il se joue sur une plage, avec une grande quantité
de poisson à disposition.
À tout moment du jeu, un nombre fini de (grands) seaux sont alignés sur la plage, chacun contenant
un nombre fini de poissons. Le but est de prendre le dernier poisson.
Pour ce faire, à tour de rôle, chaque joueur prend un poisson de l’un des seaux, et ajoute à tous les
seaux situés à sa gauche (s’il y en a) autant de poissons que souhaité. Par exemple, le schéma suivant
indique deux coups légaux joués successivement, à partir de la position à trois seaux de sept poissons
(ce que l’on note « 7 ë ») :

joueur 1 joueur 2
7ë 7ë 7ë 42 ë 6ë 7ë 1729 ë 1010 ë 6ë

1. Montrer que, quoi que fassent les joueurs, le jeu se termine après un nombre fini de coups.
2. Comment jouer à ce jeu de manière optimale ?