Logique Mathématique Calculabilité et Calcul des prédicats

Cet ouvrage est un recueil d’exercices corrigés, destiné principalement aux étudiants en informatique (LMD et Ingénieurs). C’est le fruit d’une expérience de plusieurs années d’enseignement durant lesquelles nous avons essayé de déceler les difficultés rencontrées par les étudiants pour l’assimilation des connaissances liées au domaine de la logique mathématique en général. En effet, le contenu de la documentation liée à ce domaine est beaucoup plus théorique que pratique, chose qui répulse un peu nos étudiants. Pour cela, nous avons adopté une démarche qui vise à simplifier le niveau d’abstraction pour faciliter la mise en pratique des concepts théoriques. Nous avons voulu, par une alternance de rappel de cours et d’exercices corrigés, de répondre à un besoin pédagogique : celui de mettre rapidement en pratique les connaissances théoriques acquises. Notre principal objectif n’est pas uniquement de présenter les solutions des exercices. L’idée est d’aider l’étudiant à comprendre en détail la démarche suivie pour résoudre chacun des exercices sélectionnés avec soins afin de développer sa capacité de raisonnement pour répondre à d’autres problématiques. L’ouvrage présente deux parties, chacune contient trois chapitres. Tous les chapitres sont organisés de la même façon : un bref rappel des principales notions théoriques suivi d’une série d’exercices avec leurs corrigés détaillés. Ceci pour que le lecteur puisse consulter ce livre comme un aide-mémoire. Cependant, nous recommandons vivement aux lecteurs intéressés par les détails théoriques (définitions et démonstrations rigoureuses) de consulter les ouvrages cités en référence en l’occurrence l’ouvrage : Logique Mathématique et Calculabilité de Pr. M. Mezghiche. La première partie «Calculabilité» traite les trois formalismes utilisés pour caractériser les fonctions dites calculables. Chacun des trois chapitres de cette partie est dédié à un formalisme particulier à savoir : les fonctions récursives (chapitre 1), les machines de Turing (chapitre2) et le lambda calcul (chapitre 3). La seconde partie «Calcul des prédicats» traite les différents concepts liés au calcul des prédicats (Logique du premier ordre). Elle se décline aussi en trois chapitres complémentaires. Chacun traite un aspect particulier. Le chapitre 4, est dédié au volet «syntaxe» : formules bien formées, formalisation des énoncés, variables libres et liées. Le chapitre 5, concerne le volet «sémantique» : les interprétations, satisfiabilité et valeurs de vérité des formules, la validité. Le chapitre 6, traite l’aspect «démonstration» en abordant la méthode de résolution et les concepts qui vont avec (forme normale prénexe, skolémisation, domaine de Herbrand). Nous espérons que cet ouvrage soit d’une grande utilité pour les étudiants pour qu’ils puissent mieux apprécier et appréhender le domaine de la logique mathématique.