Logique et démonstration automatique
Informatique théorique - Introduction à la logique propositionnelle et à la logique du premier ordre (Niveau A)

L'ouvrage : niveau A (IUT - BTS - 1re cycle)

Destiné principalement aux étudiants des premiers cycles scientifiques, un livre pour leur faire découvrir la logique, renforcer leur rigueur et conforter leur aptitude à raisonner.

L'ouvrage ne nécessite pas de connaissances a priori en logique, ni en mathématiques. L'étude se concentre sur la logique classique à deux valeurs de vérité, logique qui est celle des circuits combinatoires. Sont uniquement présentés des résultats et algorithmes dont il existe une réalisation logicielle permettant de les appliquer automatiquement sur des exemples.

Dans une première partie consacrée à la logique propositionnelle sont présentés les définitions, les résultats de base, la résolution, la stratégie complète et l'algorithme
DPLL, ainsi que la déduction naturelle. Dans la seconde partie l'ensemble des notions, résultats et techniques est revisité pour la logique du premier ordre.

Enfin le livre comprend de nombreux exercices gradués avec leurs corrigés détaillés, qui permettent à chacun de tester ses connaissances et la compréhension des concepts présentés.

Les auteurs
Stéphane Devismes est maure de conférences à l'université Joseph-Fourier de Grenoble où il est responsable du module introduction à la logique, à l'antenne Drôme-Ardèche. Pascal Lafourcade est maître de conférences à l'université Joseph-Fourier de Grenoble où il est responsable du module introduction à la logique.

 Lévy est maître de conférences retraité de l'université Joseph-Fourier de Grenoble où il a enseigné la logique à tous les niveaux.

Table des matières

A Logique propositionnelle
Logique proposltionneUe
1 Syntaxe .
2 Sens des fonnules . .
3 Substitution et remplacement .
4 Fonnes Nonnales . .
5 Algèbre de Boole . .
6 Fonctions booléennes
7 Circuits ....
8 L'outil BDDC .
9 Exercices...

II Résolution proposltlonneUe 1 Résolution...................... 2 Stratégie complète . 3 Algorithme de Davis-Putnam-Logemann-Loveland 4 Transfonnation en temps linéaire d'une fonnule en produit de clauses 5 Exercices................................
III Déduction NatureUe 1 Système fonnel de la déduction naturelle. 2 Tactiques de preuve . 3 Cohérence de la déduction naturelle . 4 Complétude de la déduction naturelle 5 Outils .. 6 Exercices...............
B Logique du premier ordre
IV Logique du premier ordre 1 Syntaxe . 2 Êtrelibreoulié . . . . 3 Sens des fonnules . . . 4 Équivalences remarquables 5 Exercices.........
V Base de la démonstration automatique 1 Méthodes de Herbrand 2 Skolémisation........ 3 Unification . 4 Résolution au premier ordre 5 Exercices..........
5

7
8

Il
17
19

21
25
27
29

31

37
38
46
55
60

66

71
72

77

79
79

81

83

85

87
88
90

91
99

102

107

108

112

117

120
126

VI Déduction naturelle au premier ordre: quantificateurs, copie et égalité 129 1 Règles pour la logique du premier ordre . . . . . . . 129 2 Tactiques de preuves ... 133 3 Cohérence du système 135 4 Exercices......... 138
C Annexes 141
Corrigés 143
Bibliographie 265
Index 207