Lycée Louis-Le-Grand, Paris Pour le 10/09/2021

MP2I – Mathématiques
A. Troesch

DM no 1 : Révision, modes de raisonnement

Exercice 1 – (Systèmes complets de connecteurs)

Un ensemble S de connecteurs logiques est dit complet si toute formule propositionnelle est équivalente à une formule
pouvant s’écrire uniquement à l’aide de ces connecteurs. Ainsi, par construction-même, t , ^, _, ùñu est un système
complet de connecteurs.
On dit qu’il est complet minimal si quel que soit le connecteur qu’on enlève du système, le système obtenu n’est plus
complet.

1. Exprimer A ùñ B à l’aide des connecteurs , ^, _. Le système complet t , ^, _, ùñu est-il minimal ?

2. Justifier que t , ^, _u est un système complet non minimal.
3. (a) Justifier que toute formule ne faisant intervenir que le connecteur _ est satisfaite par la distribution de
vérité prenant la valeur V pour toute variable propositionnelle.
On pourra raisonner par récurrence sur le nombre de symboles de connecteur de la formule.
(b) En déduire que le système t , _u est un système complet minimal de connecteurs.
(c) Démontrer que même que t , ^u est un système complet minimal de connecteurs.
4. On définit deux connecteurs logiques, appelés barres de Sheffer, et correspondant au NON-ET (NAND) et
NON-OU (NOR) par :
A^ | B “ pA ^ Bq et A_ | B “ pA _ Bq
(a) Donner une formule simple équivalente à A ^
| A et à A _
| A.
(b) Montrer que t ^
| u et t _
| u sont deux systèmes complets de connecteurs.
Il est assez remarquable de pouvoir écrire toutes les formules de la logique propositionnelle avec un seul connecteur !
Évidemment, en pratique, ce serait très compliqué à lire !

Exercice 2 – (Autour de la suite de Fibonacci)

On définit la suite de Fibonacci pFn qnPN par :

F0 “ 0, F1 “ 1, @n ě 2, Fn “ Fn´1 ` Fn´2 .

1. Calculer les 10 premiers termes de la suite de Fibonacci.

2. Montrer que pFn qnPN est croissante, et que pour tout n P N, Fn ě n ´ 1. Quelle est la limite de pFn qnPN ?
3. Montrer les relations suivantes :
ÿn
(a) @n ě 1, Fk2 “ Fn Fn`1 .
k“1
(b) @n ě 1, Fn pFn´1 ` Fn`1 q “ F2n et Fn2 ` Fn`1
2
“ F2n`1 .
ÿn
(c) @n ě 0, Fk “ Fn`2 ´ 1.
k“0
n´1
ÿ
(d) @n ě 1, F2k`1 “ F2n .
k“0
ÿn
(e) @n ě 0, F2k “ F2n`1 ´ 1.
k“0
p ˆ ˙
ÿ p
(f) @n ě 0, @p ě 0, Fn`k “ Fn`2p .
k“0
k
(g) @n ě 1, Fn2 “ Fn´1 Fn`1 ` p´1qn`1 .
(h) @m ě 0, @n ě 1, Fm`n “ Fm`1 Fn ` Fm Fn´1 .

1
 n n´i
ÿ ÿ ˆn ´ i˙ˆn ´ j ˙
˚
(i) @n ě 0, “ F2n`2 .
i“0 j“0
j i
(On pourra essayer de trouver une relation similaire pour F2n`3 ; cette relation peut se deviner lors des
tentatives pour prouver le caractère héréditaire de la formule à montrer)
4. Montrer que pour tout n P N, Fn`1 est égal au nombre de façon de placer bout-à-bout des carrés de côté 1 et
des dominos 1 ˆ 2 de sorte à former une rangée de longueur n (les carrés sont deux-à-deux indiscernables, ainsi
que les dominos).
Si vous le souhaitez, vous pouvez essayer de retrouver à l’aide de cette interprétation combinatoire les formules de
la question précédente (comptez certains ensembles de configurations de deux façons différentes ; pour savoir quelles
configurations rechercher, s’aider du côté simple de l’identité ; pour obtenir une somme, trier suivant un certain critère).
3 3
˚
5. Montrer que pour tout n, Fn`2 ` Fn`1 ´ Fn3 est un nombre de Fibonacci (on calculera cette expression pour
des petites valeurs de n, et on comparera avec les valeurs de la question 1, afin de trouver une conjecture).
˚
6. (Théorème de Zeckendorf, ou décomposition de n dans la base de Fibonacci)
Montrer que tout entier n ě 0 s’écrit de manière unique comme une somme de nombres de Fibonacci non nuls,
distincts et non consécutifs d’indices supérieurs ou égaux à 2 (commencez par trouver les plus grands termes
de la décomposition).
˚
7. Application : un jeu d’allumettes.
Deux joueurs tirent à tour de rôle des allumettes d’une boîte, avec les règles suivantes :
‚ Chaque joueur tire à chaque fois au moins une allumette.
‚ Le premier joueur ne retire pas la totalité des allumettes au premier tour.
‚ Un joueur tire au plus deux fois le nombre d’allumettes tirées par le joueur précédent.
‚ Le joueur qui retire la dernière allumette a gagné.
Montrer que si le nombre initial d’allumettes n’est pas un nombre de Fibonacci, la stratégie consistant à
tirer autant d’allumettes que le plus petit terme de la décomposition dans la base de Fibonacci du nombre
d’allumettes restantes peut être menée jusqu’au bout et constitue une stratégie gagnante pour le joueur 1.
Que dire du cas où le nombre initial d’allumettes est un nombre de Fibonacci ?

Problème – (Définitions et démonstrations par induction structurelle)

Soit E un ensemble non vide. Soit m P N˚ et pour tout i P v1, mw, ki P N˚ , et fi : E ki ÝÑ E. Soit F0 Ă E.
On rappelle que le sous-ensemble F de E défini par induction structurelle à partir de F0 et des fonctions f1 , . . . , fm
est le plus petit ensemble au sens de l’inclusion tel que F0 Ă F et stable par chacun des fi :

@i P v1, mw , @px1 , . . . , xki q P F ki , fi px1 , . . . , xki q P F.

Autrement dit, pour tout autre ensemble H vérifiant ces propriétés, F Ă H.

1. Existence de F , et description par le haut
Soit M “ tG Ă E | F0 Ă G et G stable par chacun des fi u.
(a) Montrer que M est non vide.
č
(b) Soit F “ G. Montrer que F est stable par les fi , et que F0 Ă F .
GPM
(c) Montrer que F est bien l’ensemble défini par induction structurelle à partir de F0 et des fi .
2. Description par le bas de F
Soit pour tout n P N,
m
ď
Fn`1 “ Fn Y fi pFnki q.
i“1

Ainsi, Fn`1 est obtenu en rajoutant à Fn l’ensemble des éléments pouvant s’obtenir des éléments de Fn en
appliquant l’une des fonctions fi .
(a) Justifier que pour tout n P N, Fn est bien défini, et Fn Ă F .
ď
(b) Montrer que F “ Fn .
nPN
Ainsi, F peut se construire « par le bas », en rajoutant petit à petit tous les éléments qu’on peut construire avec
les règles de construction données.
3. Principe d’induction structurelle
Soit P une propriété définie sur un sous-ensemble G de E tel que F Ă G. On suppose que :
‚ @x P F0 , Ppxq
‚ @i P v1, mw , @px1 , . . . , xki q P F ki , Ppx1 q ^ ¨ ¨ ¨ ^ Ppxki q ùñ Ppfi px1 , . . . , xki qq.

2
 Ainsi, P est vraie sur les éléments initiaux, et stable par les contructions fi .
(a) En considérant V “ tx P F | Ppxq est vraieu, montrer à l’aide de la propriété de minimalité de F que Ppxq
est vraie pour tout x P F .
(b) Retrouver ce résultat en utilisant la description par le bas de F .
4. Exemple : les formules de la logique propositionnelle
Soit V un ensemble fini (les variables propositionnelles P , Q, R...) et E l’ensemble de tous les mots (c’est-à-dire
juxtaposition de lettres) que l’on peut former avec les variables propositionnelles et les symboles p, q, ^, _, ,
ùñ et ðñ. On définit les fonctions suivantes, à une ou deux variables dans E :

f1 pF q “ F f2 pF, Gq “ pF _ Gq f3 pF, Gq “ pF ^ Gq f4 pF, Gq “ pF ùñ Gq f5 pF, Gq “ pF ðñ Gq.

L’ensemble F des formules propositionnelles est l’ensemble défini par induction structurelle à partir de l’en-
semble de base V et des fonctions f1 , f2 , f3 , f4 et f5 .
(a) Montrer qu’une formule de F a toujours autant de parenthèses ouvrantes que de parenthèses fermantes.
(b) On appelle segment initial d’un mot m “ m1 m2 . . . mk un mot m1 m2 . . . mi , i P v1, kw (il s’agit donc du
début du mot m, contenant au moins une lettre). Un segment initial de m est dit propre s’il est différent de
m lui-même.
i. Montrer par principe d’induction structurelle que si F est une formule commençant par une parenthèse
ouvrante, et F 1 un segment initial propre de F , alors, si opF 1 q et f pF 1 q désignent le nombre de parenthèses
ouvrantes et fermantes respectivement de F 1 , on a opF 1 q ą f pF 1 q.
ii. En déduire que si F est une formule, un segment initial propre de F ne peut pas être une formule.
(c) (Théorème de lecture unique d’une formule)
Montrer que pour toute formule F , un et un seul des trois cas suivants se présente :
(i) F P V
(ii) il existe une unique formule G telle que F “ G
(iii) il existe un unique connecteur logique γ et un unique couple pG, Hq de formules telles que F “ pGγHq.