Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Sup

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientiﬁque Support de cours Logique Mathématique Cours déstiné aux étudiants de 2me année licence Informatique Préparé par Dr ADEL née AISSANOU Karima 2015/2016 1 A Zahir, Melissa et Badis............. Table des matières Table des matières 1 Introduction 4 1 Le langage du calcul propositionnel 8 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Déﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Le langage propositionnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.1 La syntaxe du langage propositionnel . . . . . . . . . . . . . . . . . 9 1.3.2 Priorité des connecteurs . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Sémantique d’un langage propositionnel . . . . . . . . . . . . . . . . . . . 10 1.4.1 Satisﬁabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.2 Satisﬁabilité d’un ensemble de formules . . . . . . . . . . . . . . . . 13 1.4.3 Tautologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.4 Conséquence logique . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.5 Théorème de substitution . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.6 Théorème de remplacement . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Système complet de connecteurs . . . . . . . . . . . . . . . . . . . . . . . . 15 1.6 Forme normale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.6.1 Obtention de Forme normale disjonctive (FND) . . . . . . . . . . . 16 1.6.2 Forme normale conjonctive (FNC) . . . . . . . . . . . . . . . . . . . 16 1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Théorie de la démonstration pour le calcul propositionnel 21 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Liste des axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 3 2.3 Les règles ou schémas de déduction . . . . . . . . . . . . . . . . . . . . . . 23 2.3.1 Règle de détachement (ou Modus Ponens) . . . . . . . . . . . . . . 23 2.3.2 Règle de substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.3 Règle S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.4 Règles I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.5 Règles II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.6 Règles III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.7 Règles IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.8 Règles V . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 Liste des théorèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.6 Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3 Le langage du calcul des prédicats du premier ordre 35 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3 Le langage des prédicats du premier ordre . . . . . . . . . . . . . . . . . . 36 3.3.1 Alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.2 Les expressions du langage . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.3 Priorité des connecteurs . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.4 Champ d’un quantiﬁcateur . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.5 Variable libre et variable liée . . . . . . . . . . . . . . . . . . . . . . 38 3.3.6 Formule close (fermée . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4 Sémantique de la logique des prédicats du premier ordre . . . . . . . . . . 38 3.4.1 Interprétation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.2 Valuation . . uploads/s3/ mi06-l2lessons-logique.pdf