Polycopié de cours et exercices corrigés Support destiné aux étudiants de la 1è

Polycopié de cours et exercices corrigés Support destiné aux étudiants de la 1ère année PES (Professeur d’Enseignement Secondaire) informatique, Licence Mathématique et Informatique (MI) Année universitaire 2018-2019 INTRODUCTION A LA LOGIQUE MATHEMATIQUE Dr. BENKADDOUR Fatima Zohra Enseignante au département des sciences exactes E.N.S d’Oran Résumé Cet ouvrage propose une introduction à la logique mathématique accessible aux étudiants de la première année PES (Professeur d'enseignement Secondaire) à l'ENS d'Oran (E.N.S.O) ainsi qu'aux étudiants du domaine Mathématique et In- formatique (MI). Il aborde les techniques fondamentales de la logique propositionnelle dite d'ordre 0 et la logique des prédicats du premier ordre. Ce document propose une série d'exercices résolus qui conduisent l'étudiant à une connaissance approfondie des notions de base de la logique. Mots-clés : Logique propositionnelle, Logique des prédicats, PES, E.N.S.O, MI. Table des matières Résumé ii Table des matières iii Liste des gures vi Liste des tableaux vii 1 Notions de base de la logique mathématique 3 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Assertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Tautologies et antilogies . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Connecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4.1 La négation  non  ou  ¬  . . . . . . . . . . . . . . . . . 4 1.4.2 Conjonction  et  ou  ∧ . . . . . . . . . . . . . . . . . . 5 1.4.3 Disjonction  ou  ou  ∨ . . . . . . . . . . . . . . . . . . 6 1.4.4 Implication  ⇒ . . . . . . . . . . . . . . . . . . . . . . . 7 1.4.5 Équivalence  ⇔ . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Lois de Morgan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6 Les quanti cateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6.1 Le quanti cateur universel . . . . . . . . . . . . . . . . . . . 11 1.6.2 Le quanti cateur existentiel . . . . . . . . . . . . . . . . . . 12 1.6.3 Propriétés des quanti cateurs . . . . . . . . . . . . . . . . . 12 1.7 Théorie des ensembles . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7.1 Ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7.2 Élément . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.7.3 Sous-ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.7.4 Complémentaire d'un ensemble . . . . . . . . . . . . . . . . 14 1.7.5 Intersection de deux ensembles . . . . . . . . . . . . . . . . 14 1.7.6 Union de deux ensembles . . . . . . . . . . . . . . . . . . . . 15 1.8 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.8.1 Relation d'équivalence . . . . . . . . . . . . . . . . . . . . . 16 1.8.2 Relation d'ordre . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.9 Ensembles ordonnés et Treillis . . . . . . . . . . . . . . . . . . . . . 17 1.9.1 Ensembles ordonnés . . . . . . . . . . . . . . . . . . . . . . 17 iii Table des matières iv 1.9.2 Les Treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Logique propositionnelle (Ordre 0) 19 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Syntaxe (Formalisation) . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3.1 Table de vérité . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3.2 Validité et consistance . . . . . . . . . . . . . . . . . . . . . 22 2.3.3 Équivalence des formules bien formées . . . . . . . . . . . . 22 2.3.4 Conséquence logique (satisfaction) . . . . . . . . . . . . . . . 23 2.3.5 Formes normales (Normalisation) . . . . . . . . . . . . . . . 24 2.4 Théorie de la preuve (démonstration) . . . . . . . . . . . . . . . . . 25 2.4.1 Système de déduction naturelle . . . . . . . . . . . . . . . . 27 2.4.1.1 Règles d'inférence . . . . . . . . . . . . . . . . . . 28 2.4.1.2 Complétude et consistance . . . . . . . . . . . . . . 28 2.4.2 Principe de résolution de Robinson . . . . . . . . . . . . . . 28 2.4.2.1 Règle de résolution . . . . . . . . . . . . . . . . . . 29 2.4.2.2 Validité de la règle de résolution . . . . . . . . . . 30 2.4.2.3 Complétude de la méthode de résolution . . . . . . 31 2.4.2.4 Quelques stratégies . . . . . . . . . . . . . . . . . . 31 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3 Logique des prédicats (ordre 1) 37 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Prédicat . . . . . . . . . . . . . . uploads/Philosophie/ polycopie-logique-mathematique-2 1 .pdf

Tags
Philosophieformule logique table formules quanti
Documents similaires
  • 19
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager