Notes de Cours : LOGIQUE MATHÉMATIQUE Par Pr. Mohamed MEZGHICHE Table des matiè

Notes de Cours : LOGIQUE MATHÉMATIQUE Par Pr. Mohamed MEZGHICHE Table des matières partie 1. LOGIQUE 5 Chapitre 1. Rappels mathématiques 7 1. Les entiers naturels 7 2. Démonstration par contraposition 9 3. Démonstration par contradition 9 Chapitre 2. Calcul propositionnel 11 1. Préliminaires 11 2. Syntaxe de la logique propositionnelle 14 3. Sémantique de la logique propositionnelle 14 4. Théorème de remplacement 15 5. Forme normale conjonctive d'un énoncé 17 6. Ensemble complet de connecteurs 19 7. Exercices. 21 Chapitre 3. CALCUL PROPOSITIONNEL FORMEL 23 1. Système déductif pour le calcul propositionnel 23 2. Adéquation et complétude du CPF. 28 3. Méthode de Davis Putnam pour le calcul propositionnel. 31 4. Calcul des Séquents 33 5. Exercices. 35 Chapitre 4. Calcul des Prédicalts du premier ordre. 37 1. Langage du calcul des prédicats. 37 2. Notion de variables libres et de variables liées 38 3. Interprétation 39 4. Satisfaction, Valeurs de vérité 39 5. Exercices. 41 6. Calcul des prédicats formalisé 42 7. Forme normale prénexe d'une formule 49 8. Exercices 50 3 4 TABLE DES MATIÈRES 9. Solémisation, Résolution 51 10. Exercices 59 Première partie LOGIQUE 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 uploads/Philosophie/ 01-logique-mathematique.pdf

Tags
Philosophieformule calcul formules alors l'ensemble
Documents similaires
  • 42
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager