CHAPITRE 1 Rappels mathématiques 1. Les entiers naturels Souvent on écrit l'ens

CHAPITRE 1 Rappels mathématiques 1. Les entiers naturels Souvent on écrit l'ensemble des entiers naturels {1, 2, 3 . . . , } en utilisant les trois points (. . .) pour exprimer que l'ensemble des entiers est un ensemble qui possède une in nité d'éléments. Cette dé nition est intuitive et facilement acceptée. Mais elle ne su t pas pour utiliser le concept de nombres entiers dans plusieurs domaines des mathématiques. Ceci revient au fait d'écrire trois points (. . .), pour exprimer la notion d'in ni, qui n'est pas, en soit, un concept mathématique. Il est donc nécessaire de donner une dé nition des entiers naturels adaptée à de nombreuses applications en mathématiques et aussi en logique. Dans la nouvelle dé nition des entiers on prend chaque entier comme un objet mathématique construit à partir de l'entier 0 (zero) et l'application S dite fonction successeur : (∀n ∈N)S : n →n + 1. Ainsi on peut construire tous les entiers naturels comme suit : 1 = S(0), 2 = S(1), 3 = S(2), . . . , n + 1 = f(n), . . . Cette manière de construire les entiers naturels amène à proposer une nouvelle dé nition des entiers naturels Définition 1.1. (1) 0 est un entier naturel (2) Si n est un entier naturel alors S(n) = (n + 1) est un entier naturel. (3) L'ensemble des entiers naturels est dé ni par les clauses (1) et (2). Cette dé nition est un exemple de dé nition par induction. La clause (1) est appelée règle de base, la clause (2) qui permet de construire un nouveau élément est appelée règle de génération. La dernière clause est appelée règle de fermeture, elle signi e que la dé nition des entiers est déterminée par les clauses (1) et (2). 1.1. Induction mathématique. Le principe d'induction mathématique est très utilisé pour démontrer des proptiétés sur les ensembles des entiers ou sur tout autre ensemble dont les éléments sont des objets mathéamtiques et qui est isomorphe à un sous ensemble de l'ensemble des entiers naturels. Il serait très utile de rappeler de façon simple le principe d'induction. Supposons que l'on souhaite démontrer une 7 8 1. RAPPELS MATHÉMATIQUES propriété P(n) pour tout n ∈N. Pour utiliser le principe d'induction dans notre démonstration nous devons suivre les étapes suivantes : (1) Montrer que la propriété P(n) est véri ée pour n = 0. (2) Montrer que P(n + 1) est véri ée si l'on admet que P(n) est véri ée. (3) On déclare que (∀n ∈N)P(n) est démontrée si nous avons montré les étapes 1) et 2). Accepter le principe de l'induction mathématique, très utilisé en mathématique, devient immédiat si on prend en considération la dé nition inductive des entiers na- turels. Soulignons que le principe d'induction n'est pas seulement utilisé pour dé- montrer des propriétés des entiers naturels mais concerne aussi les proriétés sur des ensembles dénombrables. Le principe d'induction est aussi très utilisé dans les preuves des propriétés et théorèmes en logique où souvent les dé nitions sont données sous la forme de dé nition inductive. Généralement la preuve par induction d'une propiété P(n) sur un ensemble dénombrable E est constituée de trois étapes : (1) Montrer que le plus petit élément de E, soit n0 véri e la propriété P. Ceci signi e que P(n0) est véri ée. P(n0) est la base d'induction. (2) On suppose que P(n) est véri ée, c'est l'hypothèse d'induction. (3) A partir de l'hypothèse d'induction on montre que P(n+1) est véri ée. Dans le cas où cela est montré on peut dire que : (∀n ∈E)P(n) est véri ée. On trouve souvent dans certaines démonstrations mathématiques l'utilisation du principe d'induction sous une autre forme légèrement diérente de celle décrite ci- dessus. L'hypthèse d'induction est donnée sous la forme P(m) est véri ée pout tout (m < n). Il est facile de voir que c'est une généralisation du principe d'induction décrit plus haut. Exemple 1.1. Montrer par induction que la somme des entiers 1, 3, 5, . . . , 2n −1 est égale à n2. Tout d'abord on peut réecrire cette question sous une forme qui correspond à la dé nition du principe d'induction. Soit P(n) = 1 + 2 + . . . + 2n −1 = n2. Le domaine de dé nition de P est E = {1, 3, 5, . . . , 2n −1, . . .}. Appliquer le principe d'induction pour montrer cette propriété nous amène à : (1) S'assurer que la base d'induction est véri ée, cest à dire que P(1) est vraie. Ceci donne P(1) = 1 = 12. (2) Supposer que P(n) est vraie. Ceci sgni e que P(n) = 1+3+5+. . .+2n−1 = n2. 3. DÉMONSTRATION PAR CONTRADITION 9 (3) Montrer que P(n + 1) = 1 + 3 + 5 + . . . + 2n + 1 = (n + 1)2. Pour démontrer ce résultat on part de l'hypothèse P(n) = 1+3+5+. . .+2n−1 = n2, on ajoute aux deux membres cette égalité, le nombre 2n + 1. Ceci donne : 1 + 3 + 5 + . . . + 2n −1 + 2n + 1 = n2 + 2n + 1 On obtient : 1 + 3 + 5 + . . . + 2n −1 + 2n + 1 = n2 + 2n + 1 = (n + 1)2. et donc : P(n + 1) = (n + 1)2. 2. Démonstration par contraposition La démonstration par contraposition est basée sur le principe suivant : Démontrer que la négation d'une proposition est fausse prouve que cette propo- sition est vraie. Nous verrons dans le reste de ce cours la justi cation de ce principe. Nous allons maintenant, à l'aide d'un exemple, montrer son utilisation dans la déduc- tion mathématique. Supposons que que l'on pose cette question : l'ensemble des entiers naturels pre- miers est-il ni ? Les entiers premiers sont les entiers dont l'ensemble des diviseurs se réduit à 1 et l'entier lui même. Les entiers 2, 3, 7, 11, 13, . . . sont des premiers. Pour répondre à cette question nous allons appliquer le raisonnement par con- traposition. Partant de notre intuition que l'ensemble des entiers premiers est un ensemble in ni, on supposera que cet ensemble est ni et on démontrera que cette hypothèse est fausse. Si notre hypothèse était vraie alors l'ensemble des entiers premiers s'écrirait : {2, 3, 7, 11, 13, 17, . . . , p}. Ici p est le plus grand entiers premiers. Soit Q = (2∗3∗7∗11∗13∗17∗. . .∗p)+1. Q est plus grand que p et par hypothèse Q n'est pas premier puisque p est le plus grand entier premier. Mais observons que le reste de la division de Q par tout entier premier est égal à 1. Alors Q est premier. Ceci Nouscontredit l'hypothèse qui dit que l'ensemble des entiers premiers est ni. 3. Démonstration par contradition Le principe du raisonnement par contradition est basé sur le principe suivant : Si nous arrivons à déduire une contradiction en partant d'une hypothèse donnée alors nous concluons que cette hypothèse est fausse. Plus loin, nous présenterons la justi cation d'un tel principe. Donnons un exemple d'application de ce principe pour montrer son utilisation dans les preuves mathématiques. Problème : Trouver l'ensem- ble des nombres entiers écrits à l'aide des chires 0, 1, . . . , 9 en utilisant une seule fois 10 1. RAPPELS MATHÉMATIQUES chacun de ces chires et dont la somme est égale à 100. Une première tentative nous permet de donner l'ensemble {4, 5, 6, 730, 28, 19}. Cet ensemble possède la seconde condition mais pas la première puisque 4+5+6+7+30+28+19 = 99. Une deuxième tentative nous amène à constater que l'ensemble des nombres {4, 5, 6, 7, 31, 28, 19} véri e la première condition puisque 4+5+6+7+31+28+19 = 100 ; mais ne véri e pas la deuxième condition. Le chire 1 apparait dans 19 et 31. Après d'autres tentatives infructieuses, le lecteur se convaint facilement qu'il n'ex- iste aucun ensemble de nombres véri ant les conditions de ce problème. Alors, on se trouve devant la situation de croire qu'un tel ensemble n'existe pas. Cette idée sur la solution du problème est dictée par l'expérience et l'intuition développées après plusieurs essais. Pour justi er cette nouvelle idée qu'aucune solution ne véri e les conditions du problème, on supposera qu'une telle solution existe et on déduira une contradition. Supposons que la somme de certains nombres, véri ant les conditions du problème, est égale à 100. Ces nombres constituent dix (10) formes diérentes puisque 0, 1, 2, 3, . . . , 9 sont utlisés une seule fois pour écrire ces nombres. Nous avons : 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 Chacune de ces formes représente, dans notre ensemble de nombres, solution du problème, soit une dizaine ou soit une unité. Considérons que T est la somme des formes uploads/s3/ cours-logique-formelle-partie-1.pdf

Tags
Administrationl'énoncé formule entiers propositionnelle logiquement
Documents similaires
  • 59
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager