Raisonnements

Sommaire

En mathématiques, lorsqu'on est confronté à une question ou à un problème, le premier travail à faire est de déterminer la nature de ce travail. S'agit-il de:

Ce cours est consacré au langage et au raisonnement en mathématiques. Son objectif essentiel est de donner tout son sens à une proposition écrite avec des symboles mathématiques et d'apprendre à les utiliser avec précision (et non comme des abréviations).

Langage mathématique

Dans cette partie, nous définissons une proposition, sa négation, les connecteurs, les quantificateurs et donnons diverses propriétés.

Contenu.

Raisonnements

Un raisonnement mathématique est un processus permettant d'établir, à partir de propositions vraies, de nouvelles propositions, de nouveaux résultats en utilisant des principes logiques. Dans cette partie, nous étudions différents types de raisonnement.

Contenu.

Bibliographie


Langage mathématique

Expressions mathématiques

Le langage mathématique est formé d'expressions mathématiques, qui sont des assemblages de signes qui obéissent à certaines règles.

L'assemblage « y » n'est pas une expression mathématique, car le signe est un signe qui ne s'utilise qu'entre deux éléments (par exemple deux réels). Par contre, « y2 », ou « yx », ou « si y2, alors y 24 » sont des expressions mathématiques.
Définition. On classe les expressions mathématiques en deux grandes catégories.
Définition. On dit que deux expressions mathématiques sont synonymes si

Dans le cas des propositions, on dit souvent équivalentes au lieu de synonymes.

Des exemples sont à la page suivante.

Exemples d'expressions mathématiques

Considérons les expressions suivantes. Ce sont toutes des expressions mathématiques au sens donné ici , et dans chacune d'elles la variable x désigne un nombre réel.

  1. {xx 2=1}
  2. x 2=1
  3. x 3=1 ou x 3=1
  4. {1;1}
  5. x=1 ou x=1
  6. pour tout réel x, si x 2=1 alors x=1 ou x=1

Les expressions 1 et 4 sont des termes (qui désignent ici des ensembles), les expressions 2, 3 , 5 et 6 sont des propositions.

Les deux termes 1 et 4 sont synonymes car ils désignent exactement le même objet.
Les propositions 2, 3 et 5 sont équivalentes, elles sont vraies exactement pour les mêmes valeurs (1 et -1) substituées à la variable x, et fausses pour les autres.
La proposition 6 est une proposition vraie, nous y reviendrons plus loin.

Ces exemples nous montrent que dans la constitution d'expressions mathématiques, termes et propositions peuvent être imbriqués : pour constituer le terme {xx 2=1}, on a utilisé la proposition x 2=1.

Assertions ou Propositions

Définition. Une assertion, appelée encore proposition, est un énoncé dont on peut dire, avec certitude, s'il est vrai ou faux (sa valeur de vérité). En particulier tous les termes qui la composent doivent être soigneusement définis pour qu'il n'y ait pas d'ambiguité et que l'assertion soit "complète".
Exemples.

Cependant, tous les exemples qui précèdent et qui sont pris dans le langage courant peuvent être sujets à caution, comme on le verra dans certains exemples qui suivent. Ils servent ici à faire le passage avec les mathématiques.
Par ailleurs, en mathématiques, on fait souvent ce qu'on appelle des abus de langage.

Une différence entre le langage courant et les mathématiques est la suivante : tout ce qui n'est pas "vrai" (au sens de la logique) ne doit pas être utilisé dans un raisonnement. Il n'y a donc pas de sous-entendu comme on le fait fréquemment dans la vie courante. Par exemple, l'affirmationLes filles de ce cours sont excellentes ne dit, ni ne prétend rien sur le niveau des garçons, comparativement. Le français peut faire, là, d'autres suppositions !!..

Exercice. Assertion complète ou incomplète

Connecteurs : NON, ET et OU

Les connecteurs permettent de composer de nouvelles assertions. La valeur de vérité de l'assertion obtenue s'exprime, à l'aide d'une table de vérité, en fonction des valeurs de vérité de celles qui la constituent. On définit dans cette page les connecteurs NON, ET et OU.

Définitions. Soient 𝒫 et 𝒬 des assertions. Les assertions NON 𝒫 (ou négation de 𝒫), 𝒫 ET 𝒬 (conjonction de 𝒫 et 𝒬, noté aussi 𝒫𝒬) et 𝒫 OU 𝒬 (disjonction de 𝒫 et 𝒬, noté aussi 𝒫𝒬) ont pour tables de vérité :
𝒫 𝒬 NON 𝒫 𝒫 ET 𝒬 𝒫 OU 𝒬
V V F V V
V F F F V
F V V F V
F F V F F

Remarques.

  1. (NON 𝒫) est vraie si 𝒫 est fausse, et fausse si 𝒫 est vraie.
  2. A l'aide d'une table de vérité, on montre : NON (NON 𝒫) est équivalente à 𝒫. Les deux propositions ont la même valeur de vérité.
  3. La logique classique respecte la règle du tiers exclu : Une assertion 𝒫 est soit vraie, soit fausse.
  4. L'assertion 𝒫 ET 𝒬 est vraie si et seulement si les deux assertions 𝒫 et 𝒬 sont vraies.
  5. L'assertion 𝒫 OU 𝒬 est fausse si et seulement si les deux assertions 𝒫 et 𝒬 sont fausses.

Exemples.
  1. La négation de « x2» est : « x<2».
  2. La proposition «10 est divisible par 3, ou 10 est pair » est vraie car l'une des deux propositions qui la compose est vraie.
  3. La proposition « x est divisible par 3, et x est pair» n'est vraie que si les deux propositions sont simultanément vraies, c'est-à-dire lorsque x est un multiple de 6.
  4. La proposition « x est divisible par 3, ou x est pair» n'est fausse que lorsque l'une et l'autre des deux propositions sont fausses, c'est-à-dire lorsque x est un nombre impair non multiple de 3.
Exercices.

Déterminer la table de vérité d'une proposition.

  1. Deux propositions avec NON, ET, OU
  2. Trois propositions avec ET, OU

Reconnaître la table de vérité d'une proposition.

  1. Deux propositions avec NON, ET, OU
  2. Trois propositions avec ET, OU

Implication, équivalence

Définition. Soient 𝒫 et 𝒬 des assertions. L'assertion 𝒫𝒬 (qui se lit 𝒫 implique 𝒬 ) a la table de vérité suivante.
𝒫 𝒬 𝒫 Rightarrow 𝒬
V V V
V F F
F V V
F F V
Remarque. Soit 𝒫 une proposition fausse, alors, quelle que soit la valeur de vérité de la proposition 𝒬 (vraie ou fausse), l'implication 𝒫 Rightarrow 𝒬 est vraie...
Propriété. L'assertion 𝒫𝒬 est équivalente à l'assertion (NON 𝒫) OU 𝒬.

Preuve. Il suffit de comparer les tables de vérité des deux assertions.

Définition. L'assertion 𝒫𝒬 (qui se lit 𝒫 est équivalente à 𝒬) est l'assertion [ (𝒫𝒬) ET ( 𝒬𝒫)]

L'assertion " 𝒫 est équivalent à 𝒬" est vraie si et seulement si les deux assertions sont soit simultanément vraies, soit simultanément fausses.

Exercices.

Déterminer la table de vérité d'une proposition.

  1. Implication et négation de propositions
  2. Trois propositions avec implication, ET, OU

Reconnaître la table de vérité d'une proposition.

  1. Implication et négation de propositions
  2. Trois propositions avec implication, ET, OU

Négation d'une assertion utilisant un connecteur

Propriétés. Soient 𝒫 et 𝒬 des assertions.

Ces propriétés se démontrent à l'aide de tables de vérité.

Exemple 1. Dans la table ci-dessous, on lit, dans les trois colonnes de gauche, les valeurs de 𝒫, 𝒬 et [ 𝒫 ET 𝒬] et, dans les trois de droite, celles de [NON 𝒫], [NON 𝒬] et [NON 𝒫 OU NON 𝒬]. En considérant les deux colonnes du milieu, on constate que [NON 𝒫 OU NON 𝒬] est bien la négation de [ 𝒫 ET 𝒬].

𝒫 𝒬 𝒫 et 𝒬 NON 𝒫 OU NON 𝒬 NON 𝒫 NON 𝒬
V V V F F F
V F F V F V
F V F V V F
F F F V V V

On en déduit facilement que la négation de [ 𝒫 OU 𝒬] est [NON 𝒫 ET NON 𝒬].

Exemple 2. Dans la table ci-dessous, on démontre que [ 𝒫 ET NON 𝒬] est la négation de [ 𝒫𝒬] qui est définie comme [NON 𝒫 OU 𝒬].

𝒫 𝒬 NON 𝒫 NON 𝒬 𝒫𝒬 𝒫 ET NON 𝒬
V V F F V F
V F F V F V
F V V F V F
F F V V V F

On notera que la négation d'une implication n'est pas une implication !


Exemples.
Exercices. Soient 𝒫, 𝒬 et des assertions. Donner la négation des assertions suivantes :
  1. 𝒫 OU 𝒬 OU

    (NON 𝒫 ) ET (NON 𝒬) ET (NON )

  2. (x 2=1)[(x=1)OU(x=1)]

    (x 2=1) ET (x1) ET (x1)

Condition nécessaire, condition suffisante.

Définitions. Soient 𝒫 et 𝒬 des assertions.

Remarque: Les cinq énoncés suivants ont la même signification.

  1. 𝒫𝒬
  2. Pour que 𝒫 soit vraie, il faut que 𝒬 soit vraie.
  3. Pour que 𝒬 soit vraie, il suffit que 𝒫 soit vraie.
  4. 𝒬 est une condition nécessaire pour avoir 𝒫.
  5. 𝒫 est une condition suffisante pour avoir 𝒬.
Exercice. Condition nécessaire ou condition suffisante .

Négation d'une assertion utilisant des quantificateurs

Propriétés. Soit A un ensemble et P(x) une expression dépendant d'un variable x
Règle pratique : Si, dans une proposition figurent des quantificateurs et une proposition 𝒫, alors dans la négation de cette proposition, le quantificateur , (resp. ) se transforme en (resp. ) , et la proposition 𝒫 devient (NON 𝒫)

Exemple 1. La négation de «x,x est multiple de 4 » est «x,x n'est pas multiple de 4 » .

Exemple 2. La négation de «xX,x<3» est «xX,x3» .

Exemple 3. Écrire à l'aide de quantificateurs les phrases suivantes (avec des variables prenant leurs valeurs dans l'ensemble G des guichets et dans l'ensemble J des jours)

𝒫 : tous les guichets sont fermés certains jours.
𝒬 : certains jours tous les guichets sont fermés.

Puis écrire leur négation en langage courant et avec des quantificateurs.

Solution

( 𝒫) : Tous les guichets sont fermés certains jours.

gG,jJ, g est fermé le jour j

( 𝒬) : Certains jours tous les guichets sont fermés.

jJ,gG, g est fermé le jour j

(non 𝒫 ) : Certains guichets sont ouverts tous les jours.

gG,jJ, g est ouvert le jour j

(non 𝒬 ) : Tous les jours, un guichet (au moins) est ouvert.

jJ,gG, g est ouvert le jour j

Vous pouvez remarquer que c'est plutôt plus simple mathématiquement :

  • on remplace par ,
  • on remplace par
  • et on remplace l'assertion g est fermé par sa négation qui est ici l'assertion g est ouvert

Exercices.

  1. Le langage courant utilise souvent des quantificateurs. Essayer de les détecter et donner la négation des assertions qui les utilisent dans l'exercice suivant : Négation de propositions dans le langage courant
  2. Un quantificateur 1
  3. Un quantificateur 2
  4. Un quantificateur et un connecteur
  5. Un quantificateur et une implication
  6. Négation de proposition avec deux quantificateurs

Contraposée et réciproque

Définition. Soient 𝒫 et 𝒬 des assertions.
Propriété : Une implication et sa contraposée ont les mêmes valeurs de vérité. Les assertions [𝒫𝒬] et [NON 𝒬NON 𝒫] sont logiquement équivalentes.

Démonstration. D'une part, 𝒫𝒬 est par définition la proposition [NON 𝒫 OU 𝒬]. Et d'autre part, [NON 𝒬NON 𝒫] est la proposition : [NON(NON 𝒬) OU NON 𝒫], c'est à dire : [𝒬 OU NON 𝒫]. C'est bien la même chose.

Dans certains cas, la propriété contraposée peut être sensiblement plus facile à démontrer que la propriété elle-même ; c'est le raisonnement par contraposée .

Exercice.
Démontrer l'équivalence entre 𝒫𝒬 et [NON𝒬NON𝒫] en utilisant des tables de vérité .
Attention à ne pas confondre la contraposée d'une implication avec sa réciproque.

Exemples.
  1. Considérons la propriété : « si n est divisible par 4, alors il est pair » (Proposition vraie)
    • Sa contraposée est : si n est impair, alors, il n'est pas divisible par 4. (Proposition aussi vraie que la première)
    • Sa réciproque est : si n est pair, alors, il est divisible par 4. (Proposition fausse...)
  2. Donnons un exemple en langage courant : S'il pleut, le sol est mouillé.
    • Sa contraposée est : si le sol n'est pas mouillé, il ne pleut pas énoncée plus couramment : Si le sol est sec, il ne pleut pas. Ces deux implications sont vraies et équivalentes.
    • La réciproque de la première est si le sol est mouillé, il pleut.
      Et cette implication est fausse, car le sol peut être mouillé par le passage du camion municipal de nettoyage ou bien par de la neige qui a fondu.
Exercices.
  1. contraposées et réciproques dans le langage courant.
  2. contraposées et réciproques en mathématiques.
Attention quand même aux pièges de la vie courante !

Contraposée et réciproque : pièges de la vie courante

En fait dans la vie courante on confond très souvent (à tort) contraposée et réciproque, en induisant des sous-entendus qui n’existent pas. Par exemple, si l'on vous dit :

Si tu es sage ce matin, tu auras du chocolat cet après-midi

[Notons tout de suite, et c'est important, que cela ne dit rien de ce qui se passera si l'on n'a pas été sage le matin....]

la contraposée est

Si tu n'as pas de chocolat cet après-midi, tu n'as pas été sage ce matin

et la réciproque

Si tu as du chocolat cet après-midi, tu as été sage ce matin.


Enfin, la contraposée de la réciproque est

Si tu n'es pas sage ce matin, tu n'auras pas de chocolat cet après-midi.


Ce qui n'est pas équivalent à la première phrase. Mais c'est en général cette dernière affirmation qui est dans la tête de celui qui prononce la première (en appliquant des principes d'éducation positive !)

Raisonnements

Raisonnement par implication

Deux règles fondamentales fondent les raisonnements :

Principe de déduction. Si 𝒫 est vraie et si 𝒫𝒬 est vraie, alors l'assertion 𝒬 est vraie.
Exercice 1. Démontrer l'implication : x 2=xx=x.
Exemple 2. Soit ABC un triangle dont les cotés de ABC ont pour mesure : AB=4, AC=3 et BC=5. C'est l'assertion 𝒫.
L'assertion 𝒬 est : le triangle est rectangle.
La réciproque du théorème de Pythagore nous indique que si dans un triangle: AB 2+AC 2=BC 2, alors ce triangle est un triangle rectangle. ( 𝒫𝒬 )
Conclusion : l'assertion 𝒬 est vraie : ABC est un triangle rectangle
Exemple 3.

Considérons une fonction f définie sur .
On note 𝒫 l'assertion : f est dérivable sur .
On note 𝒬 l'assertion : f est continue sur .
L'assertion 𝒫𝒬 est le théorème : Toute fonction dérivable sur est continue sur .

Conclusion : la fonction f est continue sur .

Remarque : Dans la pratique, on est souvent conduit à utiliser plusieurs fois de suite la règle, on a ainsi :
Si 𝒫 est vraie, si 𝒫𝒬 vraie, si 𝒬 est vraie, alors est vraie


Raisonnement par équivalence

Première méthode pour prouver une équivalence :

En s'appuyant sur la définition de l'équivalence de deux propositions , on énonce la règle suivante.

Règle 2. Pour démontrer qu'une proposition 𝒜 est vraie, on peut établir que 𝒜 est équivalente à une autre proposition , connue comme vraie.

Plus généralement, pour démontrer que 𝒫𝒬, on peut aussi établir ainsi une suite d'équivalence entre la première propriété 𝒫 et la propriété 𝒬, On aura ainsi :

𝒫𝒫 1𝒫 2.....𝒫 n𝒬

On utilise souvent cette règle pour :

Remarque : Il convient d'être très prudent dans l'établissement des équivalences successives.

Exemple d'erreur :

On veut résoudre dans , l'équation : x+1=2x+6. Pour que cette équation ait un sens, x doit vérifier : 2x+60 et x+10. On verra plus loin, que si cette équation a des solutions, l'une des inégalités est automatiquement vérifiée.

"Solution fausse" : "On élève au carré les deux membres", on obtient l'équation du second degré x 2+4x5=0, que l'on résout, ce qui conduit à deux solutions -5 et 1. Si l'on vérifie dans l'équation, on voit que -5 ne convient pas... Que s'est-il passé ? Réponse : on n'a pas raisonné par équivalence !!

La bonne solution impose de formuler le problème avec l'équivalence suivante, en n'oubliant pas les deux conditions :

x+1=2x+6{(x+1) 2=2x+6 x+10 2x+60

La deuxième condition 2x+60 est inutile, car comme 2x+6 est égal à un carré (première ligne), elle est satisfaite.

x+1=2x+6{(x+1) 2=2x+6 x+10{x 2+4x5=0 x+10

Et on résout le système, sans oublier l'inéquation, ce qui conduit alors au résultat correct : L'équation n'a qu'une seule solution qui vaut 1.

Raisonnement par équivalence en deux temps.

Deuxième méthode pour prouver une équivalence :

Règle : On démontre la proposition 𝒫𝒬 en prouvant successivement les deux implications 𝒫𝒬 et 𝒬𝒫.
Exemple 1. Soit z un nombre complexe. Montrons qu'il est réel si et seulement s'il est égal à son conjugué.

Sens direct : Si z est un nombre complexe, il existe a et b réels tels que z=a+ib. Son conjugué est z ¯ =aib. Si z est réel, sa partie imaginaire est nulle et donc b=0. Ainsi z=a et z ¯ =a. L'égalité z=z ¯ est démontrée.

Réciproquement : Si z=z ¯ , a+ib=aib. On a ainsi 2b=0, puis b=0, et donc z=a qui est donc un nombre réel.

L'équivalence est maintenant démontrée.

Exemple 2. Montrer que : (a+b) 2=a 2+b 2 si et seulement a=0 ou b=0.

Sens direct : En développant l'expression, on trouve 2ab=0, et donc a=0 ou b=0.

Réciproquement : En remplaçant a et b par 0 dans l'expression, on vérifie que les deux membres valent tous les deux zéro, d'où l'égalité.

L'équivalence est maintenant démontrée.

Raisonnement par contraposition

On a vu, dans le paragraphe précédent Contraposée et réciproque , qu'une implication et sa contraposée sont équivalentes.

Règle 3. Pour démontrer une implication, il suffit de démontrer sa contraposée.

En d'autres termes, pour démontrer une implication, on peut le faire soit directement, soit en démontrant sa contraposée. En effet, la propriété contraposée peut être sensiblement plus facile à démontrer que la propriété elle-même, comme le montre le cas suivant.

Exemples.
  1. Pour démontrer que l'implication portant sur des nombres réels :

    ab0[a0 et b0]

    est vraie, il est équivalent, et beaucoup plus simple, de vérifier que la contraposée :

    [a=0 ou b=0][ab=0]

    est vraie, ce qui est évident.

  2. Démontrer la proposition : n, n 2 impair n impair.

    Pour démontrer cette implication, il est plus simple de démontrer la contraposée : n , n pair n 2 pair.
    Ce qui ne présente aucune difficulté. Si n est pair, il existe n tel que n=2p. On obtient n 2=(2p) 2=4p 2 donc le nombre n 2 est pair.
Exercice 1.
Démontrer la proposition : Soit x[ε + *,x<ε][x=0]
Exercice 2.
Démontrer la proposition : n, [ si n 21 n'est pas divisible par 8, alors n est pair].

Raisonnement par l'absurde

Le raisonnement par l'absurde consiste à supposer comme hypothèse la négation de ce que l'on veut démontrer, puis, par des déductions logiques utilisant cette hypothèse, à aboutir à une contradiction ou une absurdité.
Le raisonnement par l'absurde pour démontrer la proposition 𝒫 peut donc se formaliser ainsi :
Si [(NON𝒫)𝒬] est vraie et si 𝒬 est une proposition fausse, alors on peut affirmer que 𝒫 est vraie.
En effet : Si [(NON𝒫)𝒬] (qui est équivalent à [𝒫OU𝒬]) est vraie, avec 𝒬 fausse, c'est que 𝒫 est vraie.
Exemple : On veut démontrer que 2 n'est pas un rationnel. Pour cela, on va supposer que 2 est rationnel. Il existe donc deux entiers naturels p et q, premiers entre eux tels que : 2=pq .
De l'équation p 2=2q 2, on déduit que p et q sont pairs:
En effet p 2 est pair donc p également (ceci découle du fait que la contraposée : p impair p 2 impair est vraie, (voir page précédente où cela a été démontré pour les nombres pairs)).
Si p est pair, il existe k tel que p=2k. L'équation p 2=2q 2 devient 4k 2=2q 2, soit 2k 2=q 2. Donc q 2 est pair et en reprenant le même chose que ci dessus, q est pair. p et q sont donc tous les deux pairs.
Ce qui est en contradiction avec le choix de p et q qu'on a fait (premiers entre eux). D'où la contradiction, ce qui démontre que 2 est un irrationnel.
Exercice.
Montrer qu'il existe une infinité de nombres premiers.
Aide. Supposons qu'il existe un nombre FINI de nombres premiers p 1,p 2,....,p n. On suggère de s'intéresser au nombre N=p 1p 2....p n+1 et au théorème de décomposition de tout entier naturel n2 en produit de nombres premiers, pour faire apparaître une contradiction.

Un raisonnement par l'absurde pour montrer une implication peut parfois être remplacé par un raisonnement par contraposition. Par exemple,

Mais si 𝒫 ne nous a pas servi, on a en fait démontré : NON(𝒬)NON(𝒫) et donc 𝒫𝒬 par contraposition.


Raisonnement par disjonction des cas

Règle. Pour montrer une propriété par disjonction des cas, on la prouve dans le nombre fini des cas couvrant toutes les situations possibles. On traite ces cas les uns après les autres.
Exemple 1. Montrer que par disjonction des cas que : nn(n+1)2 est un entier naturel.
Deux cas seulement sont possibles: soit n est pair, soit il est impair.
  1. Si n est pair, il existe p dans tel que n=2p et n(n+1)2=2p(2p+1)2=p(2p+1) qui est un entier naturel.
  2. Si n est impair, il existe p dans tel que n=2p+1 et n(n+1)2=(2p+1)(2p+2)2=(2p+1)(p+1) qui est un entier naturel.
Exemple 2. Montrer qu'il existe deux irrationnels a et b tels que a b soit rationnel.

Raisonner selon que 2 2 est rationnel ou non.

Solution
Rappelons que 2 est irrationnel. Soit 2 2 est rationnel, soit il ne l'est pas et alors il est irrationnel.
  • Si 2 2 est rationnel, on a fini. Les nombres a= 2 et b= 2 conviennent.
  • Sinon les nombres a=2 2 et b=2 sont irrationnels et a b vaut 2.

Exercice 1. Démontrer que pour tout entier naturel n, les nombres entiers n 2+3n et n(7n+1) sont pairs.

Exercice 2. Disjonction de cas et table de vérité.
Comparer, à l'aide d'une table de vérité, les assertions [(𝒫OU𝒬)] et [ (𝒫) ET (𝒬)].

Méthode par exhaustion

Un raisonnement par disjonction des cas vise à établir le même résultat dans tous les cas rencontrés. Il existe une autre catégorie de problèmes où l'on traite les diverses situations se produisant, mais qui conduisent à des réponses non nécessairement identiques. Dans ce cas, on parlera plutôt de méthode par exhaustion ou méthode exhaustive.

Exemple. Trois frères Alfred, Bernard et Claude ont des crayons de couleur différente bleu, rouge et vert. De plus, les assertions suivantes sont vraies :

  1. Si le crayon d'Alfred est vert, alors le crayon de Bernard est bleu.
  2. Si le crayon d'Alfred est bleu, alors le crayon de Bernard est rouge.
  3. Si le crayon de Bernard n'est pas vert, alors le crayon de Claude est bleu.
  4. Si le crayon de Claude est rouge, alors le crayon d'Alfred est bleu.

Que peut-on conclure sur la couleur respective des crayons d'Alfred, Bernard et Claude? Y a-t-il plusieurs possibilités ?

Aide. Faites l'hypothèse que le crayon d'Alfred est vert et voyez ce qu'on peut en déduire. Si vous en déduisez que le crayon d'un autre est à la fois de deux couleurs différentes ou que deux des frères ont des crayons de même couleur, c'est que cela n'est pas possible. Faites alors une autre hypothèse.

Solution. Le crayon d'Alfred est rouge, celui de Bernard est vert et celui de Claude est bleu.

Exercice. Un scénario de Lewis Caroll
Considérons le problème suivant sachant que chacune des assertions suivantes est vraie :

  1. Ou le malfaiteur est venu en voiture, ou le témoin s'est trompé ;
  2. Si le malfaiteur a un complice, alors il est venu en voiture ;
  3. Le malfaiteur n'avait pas de complice et n'avait pas la clé ou bien le malfaiteur avait un complice et avait la clé ;
  4. Le malfaiteur avait la clé.

Que peut-on en conclure ? Si on remplace la dernière par le malfaiteur n'avait pas la clé, peut-on conclure ?

Raisonnement par analyse-synthèse

Le raisonnement par analyse-synthèse s'utilise souvent dans la recherche d'un ensemble d'éléments vérifiant une propriété 𝒫. On l'utilise également lorsqu'on ne fait pas de raisonnement par équivalence, dans le but d'arriver au même résultat.

Le principe est le suivant:

  1. Dans la partie analyse, on cherche les conditions nécessaires que doivent vérifier les éléments satisfaisant 𝒫.
  2. Dans la partie synthèse, on s'assure que les éléments satisfaisant les conditions nécessaires obtenues dans la partie analyse vérifient bien 𝒫.
Exemple.
Démontrer qu'il existe un unique couple (f,g) de fonctions définies sur à valeur dans vérifiant les conditions :
  1. f est une fonction paire (Rappel : f est paire si xf(x)=f(x) )
  2. g est une fonction impaire (Rappel : g est impaire si xg(x)=g(x) )
  3. x,e x=f(x)+g(x)

Analyse : On suppose qu'un tel couple (f,g) existe. Alors, pour tout x, on a :

𝒮{e x=f(x)+g(x) e x=f(x)+g(x)=f(x)g(x)

En résolvant le système 𝒮, on obtient les (uniques) solutions :

f(x)=e x+e x2 et g(x)=e xe x2

Synthèse : Il reste à vérifier que ces solutions vérifient bien les trois conditions imposées: f paire, g impaire et x,e x=f(x)+g(x), ce qui ne présente aucune difficulté et que nous laissons à faire au lecteur.

Conclusion : On a ainsi trouvé un couple (f,g), avec f paire et g impaire et vérifiant x,e x=f(x)+g(x) et ce couple est unique.

Raisonnement par récurrence

Principe de récurrence

Raisonnement par récurrence : On souhaite démontrer une assertion 𝒫(n), pour tout entier naturel n, ou pour des entiers naturels n supérieurs à un entier naturel n 0 .
Il faut d'abord bien l'énoncer... Ensuite, on suit la démarche suivante en trois étapes:
Principe de récurrence:
  1. On montre qu'il existe un entier n 0 tel que 𝒫(n 0) soit vraie.
    C'est l'initialisation en n 0.
  2. On montre ensuite que l'assertion : 𝒫(n)𝒫(n+1) est vraie pour nn 0.
    L'assertion 𝒫(n) est dite alors héréditaire pour nn 0.
    Dans la pratique, on nomme "hypothèse de récurrence" la proposition 𝒫(n) que l'on suppose vraie pour un entier nn 0 puis on démontre que 𝒫(n+1) est vrai.
  3. On énonce la conclusion : Par récurrence, on montre ainsi que la proposition 𝒫(n) est vraie pour tout entier nn 0.

Soyez particulièrement attentifs à la rédaction d'un tel raisonnement.

Exemple : Montrer que la somme des n premiers entiers vaut : S n=1+2+3+...+n=n(n+1)2

  1. Initialisation. S 1 somme des nombres de 1 à 1 vaut : S 1=1=1(2)2. C'est juste.
  2. Hérédité. Soit n1 tel que S n=n(n+1)2. Montrons que : S n+1=(n+1)(n+2)2
  3. S n+1=(1+2+3+...+n)+(n+1)=S n+(n+1)=n(n+1)2+(n+1)= (n+1)(n2+1)= (n+1)n+22=(n+1)(n+2)2.
    C'est bien ce que l'on cherchait.
  4. Conclusion : la propriété est vérifiée, pour tout n.

Exercice : Montrer que la somme des carrés des n premiers entiers naturels vaut : T n=1 2+2 2+3 2+...+n 2=n(n+1)(2n+1)6

Un autre exemple

D'autres exercices

Raisonnement par récurrence : un exemple

Donnons une version imagée du principe de récurence (à propos récurrence vient de courir en arrière).
Mettons 543 dominos sur une table, verticalement et proches les uns des autres. Je désire montrer que, si je fais tomber le premier domino sur le second, les 543 dominos tombent.

Propriété 𝒫(n) : n2,n543 les n premiers dominos sont tombés.

  1. D'une part 𝒫(2) est vraie car si je fais tomber moi-même le premier domino sur le second, celui-ci tombe, et les deux premiers sont tombés.
  2. D'autre part, l'assertion 𝒫(n)𝒫(n+1) est vraie.
    En effet si le n-ième est tombé, il est tombé sur le (n+1)-ième qui tombe à son tour, alors les n+1 dominos premiers sont donc tombés.
  3. L'initialisation et l'hérédité sont prouvées, et par récurrence on a prouvé la proposition 𝒫(n), pour n compris entre 2 et 543.

Dans le détail du principe de récurrence :
Comme 𝒫(2) et (𝒫(2)𝒫(3)) sont vraies, 𝒫(3) est vraie.
Comme 𝒫(3) ) et [ 𝒫(3)𝒫(4)] sont vraies, 𝒫(4) est vraie.
.........................
Comme 𝒫(542) et [ 𝒫(542)𝒫(543)] sont vraies, 𝒫(543) est vraie et les 543 dominos sont tombés.

Conclusion : "Si je fais tomber le premier domino sur le second, les 543 dominos tombent".

Remarquons que si j'avais fait tomber le premier domino de l'autre côté, l'implication 𝒫(n)𝒫(n+1) serait toujours vraie, en revanche 𝒫(2) ne le serait pas... Donc 𝒫(543) ne serait pas vraie (en tout cas sans autre hypothèse et si votre animal préféré arrive, je ne réponds plus de rien).

Récurrence : Exercices

Exercice 1:
À partir de quel rang les quatre propriétés suivantes sont-elles héréditaires? ?
Peut-on les initialiser, et à partir de quel rang ?

Dans les cas suivants, l'assertion 𝒫(n) est-elle héréditaire pour tout entier naturel n ? Les propositions 𝒫(0),𝒫(1),𝒫(2) sont-elles vraies ? La proposition 𝒫(n) est-elle vraie pour tout entier naturel n ? La proposition 𝒫(876) est-elle vraie ?

  1. 𝒫(n): n+1<n
  2. 𝒫(n): n 3n 2
  3. 𝒫(n): 10 n(1) n est divisible par 11
  4. 𝒫(n): 10 n+1 est divisible par 9

Exercice 2: Montrez l'inégalité: 2 n>n 2. Que pensez-vous de l'énoncé ? Précisez-le et proposez un énoncé correct. Démontrez-le.

Indication : On s’apercevra que l'initialisation ne peut commencer qu'a partir de n=6, et on prouvera qu'en revanche l'hérédité débute à n=2.

Une récurrence fausse

Il arrive que l'on fasse une mauvaise hypothèse de récurrence, que la propriété soit fausse pour le n 0 choisi, ou que la preuve de l'hérédité ne soit pas valide pour tout n. Trouvez l'erreur dans cette "démonstration" de l'assertion

Tous les crayons de couleur d'une même boîte sont de même couleur.

"Pseudo-démonstration".
  1. Si la boîte ne contient qu'un seul crayon, tous les crayons de la boîte sont de même couleur. La propriété est donc initialisée.
  2. Prenons comme hypothèse de récurrence :
    Tous les crayons d'une boîte de k crayons sont de même couleur.
    Prenons une boîte de crayons contenant k+1 crayons. Enlevons le crayon A, par exemple. Par hypothèse de récurrence, les k crayons de couleur qui restent ont la même couleur.
    Remettons A et enlevons un autre, B. Par hypothèse de récurrence, les k crayons de couleur qui restent ont la même couleur que A. Et, d'après ce qui précède, ils ont aussi la même couleur que B.
    Donc les k+1 crayons de couleur sont tous de la même couleur. L'hérédité est donc "prouvée"
  3. Conclusion : Tous les crayons de couleur d'une même boîte sont de la même couleur.
Bien évidemment, il se trouve une erreur quelque part... Trouvez-la !

Récurrence double

Parfois l'hérédité se démontre non pas uniquement par rapport au rang précédent, mais par rapport aux deux précédents. On parle alors de récurrence double. La démarche doit alors être légèrement modifiée.
On souhaite démontrer une assertion 𝒫(n) pour des entiers naturels n supérieurs à un entier naturel n 0.
Règle:
  1. Initialisation en n 0, on montre que 𝒫(n 0) et 𝒫(n 0+1) sont vraies.
  2. On montre ensuite que l'assertion : [ 𝒫(n) et 𝒫(n+1)]𝒫(n+2), est vraie pour nn 0.
    L'assertion 𝒫(n) est alors héréditaire pour nn 0.
  3. Conclusion: par le principe de récurrence, on a montré que 𝒫(n) est vraie, pour tout entier nn 0.
Exemple. On considère la suite dite de "Fibonacci", définie par :

u 0=1,u 1=1 et n,u n+1=u n+u n1

Montrer que l'inégalité suivante est vraie :

nu n(74) n

  1. Les deux inégalités suivantes sont vraies : u 0=(74) 0=174, et u 1=(74) 1=7474.
  2. Soit n *, vérifiant les deux inégalités :
    u n(74) n et u n1(74) n1.
    Alors : u n+1=u n+u n1(74) n+(74) n1
    u n+1(74) n1(74+1)(74) n1(4416)(74) n1(4916)(74) n+1
  3. Par le principe de récurrence, le résultat est ainsi démontré, pour tout n dans
Exercice. Soit x *, tel que x+1x.
  1. Montrer par une récurrence double que, n,x n+(1x) n
  2. Question annexe : trouver un réel x, non entier, vérifiant l'hypothèse.

Bibliographie

  1. F. Liret et D. Martinais, Mathématiques pour le DEUG, Algèbre 1ère Année (Dunod), chapitre 1
  2. A. Auzimour et F. Petit, Travaux dirigés d'algèbre (Vuibert)
  3. A. Denmat et F. Héaulme, Algèbre générale (Dunod), td 1

une introduction aux raisonnements.
: reasoning,math_symbols,quantifier, implication, contraposition, truth_table, recurrence, CFAI,interactive math, server side interactivity

The most recent version

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.