Remerciez-le!

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

INFO202 : Fondements mathématiques de l’Informatique Étienne KOUOKAM Année acad

INFO202 : Fondements mathématiques de l’Informatique Étienne KOUOKAM Année académique 2016-2017 Table des matières Partie I Logique 4 Chapitre 1 : Systèmes formels 6 1.1 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Ensembles récursifs et récursivement énumérables . . . . . . . . . . . 6 1.3 Systèmes formels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Déﬁnitions supplémentaires . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Résultats généraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chapitre 2 : Logique propositionnelle 10 2.1 Première approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Sémantique dans le calcul des propositions . . . . . . . . . . . . . . . 13 2.3.1 Puissance d’expression . . . . . . . . . . . . . . . . . . . . . 14 2.3.2 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Formules et interprétations . . . . . . . . . . . . . . . . . . . . . . . 15 2.5 Arbres sémantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6 Algorithme de réduction . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6.1 formes duales . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6.2 formes normales . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6.3 Algorithme de normalisation . . . . . . . . . . . . . . . . . . 20 2.6.4 Foncteur booléen associé à une formule . . . . . . . . . . . . 22 2.6.5 Formes clausales . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.6.6 Méthode de résolution de Robinson . . . . . . . . . . . . . . . 24 2.6.7 Méthode de résolution sémantique . . . . . . . . . . . . . . . . 25 2.7 Système de preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Chapitre 3 : Logique des prédicats 29 3.1 Calcul des prédicats, le point de vue formel . . . . . . . . . . . . . . 29 3.1.1 Sous-formules d’une formule . . . . . . . . . . . . . . . . . . . 31 3.1.2 Variables libres ou liées . . . . . . . . . . . . . . . . . . . . . . 31 3.1.3 Standardisation des variables . . . . . . . . . . . . . . . . . . 32 3.2 Sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Substitution et instanciation . . . . . . . . . . . . . . . . . . . . . . 34 3.3.1 Substitution d’une variable par un terme . . . . . . . . . . . . 34 3.4 Uniﬁcation (de deux formules) . . . . . . . . . . . . . . . . . . . . . . 35 Etienne KOUOKAM/INFO202 Fondements mathématiques de l’Informatique TABLE DES MATIÈRES 3 3.4.1 Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5 Algorithme d’uniﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.5.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.5.2 Règle de résolution . . . . . . . . . . . . . . . . . . . . . . . . 40 3.6 De la logique des prédicats à Prolog . . . . . . . . . . . . . . . . . . 41 3.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Partie II programmation logique 42 Chapitre 4 : Programmation Logique : Le langage Prolog 44 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2 Les éléments fondamentaux du Prolog . . . . . . . . . . . . . . . . . 44 4.2.1 Les faits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2.2 Les questions ou les requêtes . . . . . . . . . . . . . . . . . . 45 4.2.3 Les types du Prolog . . . . . . . . . . . . . . . . . . . . . . . 45 4.2.4 Variables partagées . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.5 Les règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.3 Mise en œuvre d’un programme . . . . . . . . . . . . . . . . . . . . 48 4.3.1 Le lancement de l’interprète . . . . . . . . . . . . . . . . . . . 48 4.3.2 Chargement de ﬁchiers . . . . . . . . . . . . . . . . . . . . . . 48 4.3.3 Limitation des choix . . . . . . . . . . . . . . . . . . . . . . 49 4.3.4 Position du cut . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.5 Optimisation des calculs . . . . . . . . . . . . . . . . . . . . 49 4.4 Negation as failure . . . . . . . . uploads/Philosophie/ info202-support-de-cours-kouokam.pdf