Calcul en logique du premier ordre

Yves Bouchard

Description

Un calcul logique, au sens large, est une méthode de résolution appliquée au traitement d’une structure propositionnelle. Les propositions constituant cette structure peuvent aussi bien être des expressions d’une langue naturelle (comme le français) que des expressions d’un langage formalisé (comme l’arithmétique), liées entre elles par une dépendance de nature fonctionnelle.
Cet ouvrage constitue une introduction à deux outils de calcul en logique du premier ordre, soit le calcul en arbres de consistance et le calcul en déduction naturelle. La première partie, centrée sur la notion de structure propositionnelle, expose les concepts, les objets et les méthodes propres à la logique propositionnelle. Dans la deuxième partie, la logique propositionnelle est étendue à la logique prédicative au moyen de la quantification et de concepts caractéristiques d’un langage du premier ordre. Les deux outils de calcul sont ensuite enrichis de manière à pouvoir traiter des fonctions propositionnelles, soit des prédicats du premier ordre.
De nombreux exemples et exercices, accompagnés de leurs solutions, aideront l’étudiant à progresser vers des calculs toujours plus complexes et à raffiner ses méthodes de calcul logique.

Sujets

• Déduction naturelle

Informations

• Publié par: Presses de l'Université du Québec
• Date de parution: 04 février 2015
• Nombre de lectures: 6
• EAN13: 9782760542105
• Langue: Français
• Poids de l'ouvrage: 4 Mo

Extrait

YVES BOUCHARD
Calcul en logique
du premier ordreCalcul en logique
du premier ordrePresses de l’Université du Québec
Le Delta I, 2875, boulevard Laurier, bureau 450, Québec (Québec) G1V 2M2
Téléphone : 418 657-4399 Télécopieur : 418 657-2096
Courriel : [e-mail] Internet : www.puq.ca
Diffusion / Distribution :
Canada Prologue inc., 1650, boulevard Lionel-Bertrand, Boisbriand (Québec) J7H 1N7
Tél. : [phone]
France AFPU-D – Association française des Presses d’université
Sodis, 128, avenue du Maréchal de Lattre de Tassigny, 77 403 Lagny, France – Tél. : [phone]
Belgique Patrimoine SPRL, avenue Milcamps 119, 1030 Bruxelles, Belgique – Tél. : [phone]
Suisse Servidis SA, Chemin des Chalets 7, 1279 Chavannes-de-Bogis, Suisse – Tél. : [phone]
La Loi sur le droit d’auteur interdit la reproduction des œuvres sans autorisation des titulaires de droits.
Or, la photocopie non autorisée – le « photocopillage » – s’est généralisée, provoquant une baisse des
ventes de livres et compromettant la rédaction et la production de nouveaux ouvrages par des
professionnels. L’objet du logo apparaissant ci-contre est d’alerter le lecteur sur la menace que représente pour
l’avenir de l’écrit le développement massif du « photocopillage ».
Membre deYVES BOUCHARD
Calcul en logique
du premier ordreCatalogage avant publication de Bibliothèque et Archives nationales
du Québec et Bibliothèque et Archives Canada
Bouchard, Yves,
1963Calcul en logique du premier ordre
Comprend des références bibliographiques et un index.
ISBN 978-2-7605-4209-9
1. Logique du premier ordre. 2. Calcul propositionnel. I. Titre.
BC128.B68 2015 160 C2014-942383-7
Les Presses de l’Université du Québec
reconnaissent l’aide financière du gouvernement du Canada
par l’entremise du Fonds du livre du Canada
et du Conseil des Arts du Canada pour leurs activités d’édition.
Elles remercient également la Société de développement
des entreprises culturelles (SODEC) pour son soutien financier.
Conception graphique
Michèle Blondeau
Mise en pages
Yves Bouchard
er trimestre 2015Dépôt légal : 1
› Bibliothèque et Archives nationales du Québec
› Archives Canada
© 2015 – Presses de l’Université du Québec
Tous droits de reproduction, de traduction et d’adaptation réservés
Imprimé au CanadaÀ Ghislaine et GuillaumeAvant-propos
Cet ouvrage présente le contenu relatif à deux outils de calcul en logique
des prédicats du premier ordre, soit le calcul en arbres de consistance et
le calcul en déduction naturelle. Dans la première partie, on retrouve les
concepts, les objets et les méthodes propres à la logique propositionnelle
(chapitres 1 à 3). L’approche de cette partie est centrée sur la notion de
structure propositionnelle. Dans la deuxième partie, la logique
propositionnelle est étendue à la logique prédicative au moyen de la quantification et
de concepts caractéristiques d’un langage du premier ordre (chapitre 4). Les
deux outils de calcul sont enrichis de manière à pouvoir traiter des fonctions
propositionnelles (chapitre 5 et 6), à savoir des prédicats du premier ordre.
Les exemples et les exercices utilisés dans chaque chapitre répondent bien
sûr au besoin d’illustration mais surtout aux impératifs liés à la progression
dans les développements plus techniques.
Tout au long de la préparation de cet ouvrage, j’ai pu bénéficier de l’aide
et de l’appui de plusieurs collègues. Je tiens en particulier à remercier Serge
Robert et André Mayers pour leurs suggestions de corrections qui m’ont
permis de réduire les défauts dans ma présentation. Je remercie également
BenoîtCôtéetGillesBeauchamp pourleuraide,notamment danslarévision
des exercices et dans l’exploration de voies inédites.
AEn ce qui concerne la typographie LT X, les arbres de consistance ontE
été réalisés à l’aide de la librairie de commandes pst-tree développée par
Timothy Van Zandt et Herbert Voß, et les déductions naturelles, au moyen
de la librairie fitch programmée par Peter Selinger.
Enfin,j’aimeraisinviterlelecteurattentifàmecommuniquertouteerreur
qui a pu échapper à mon attention ([e-mail]).Table des matières
Avant-propos ix
Introduction 1
I Logique propositionnelle 9
1 Les connecteurs logiques 11
1.1 Objets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.1 Propriétés des connecteurs . . . . . . . . . . . . . . . . 11
1.1.2 Définitions des connecteurs . . . . . . . . . . . . . . . 12
1.1.3 Relations entre les connecteurs . . . . . . . . . . . . . 18
1.1.4 Traduction de la langue naturelle . . . . . . . . . . . . 21
1.2 Méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.2.1 Tables de vérité . . . . . . . . . . . . . . . . . . . . . . 26
1.2.2 Calcul par réduction . . . . . . . . . . . . . . . . . . . 31
1.2.3 Tautologie . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.3 Solutions des exercices . . . . . . . . . . . . . . . . . . . . . . 37
2 Les arbres de consistance I 45
2.1 Forme normale disjonctive . . . . . . . . . . . . . . . . . . . . 45
2.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3 Calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.3.1 Énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.3.2 Ensemble d’énoncés . . . . . . . . . . . . . . . . . . . 63
2.3.3 Inférence . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.4 Objets et méthodes . . . . . . . . . . . . . . . . . . . . . . . . 71xii TABLE DES MATIÈRES
2.5 Sommaire des règles . . . . . . . . . . . . . . . . . . . . . . . 77
2.6 Solutions des exercices . . . . . . . . . . . . . . . . . . . . . . 78
3 La déduction naturelle I 105
3.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.2 Règles d’introduction . . . . . . . . . . . . . . . . . . . . . . . 107
3.3 Règles d’élimination . . . . . . . . . . . . . . . . . . . . . . . 113
3.4 Calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.5 Sommaire des règles . . . . . . . . . . . . . . . . . . . . . . . 141
3.6 Solutions des exercices . . . . . . . . . . . . . . . . . . . . . . 143
II Logique prédicative 159
4 La quantification 161
4.1 Prédicat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.1.1 Abstraction . . . . . . . . . . . . . . . . . . . . . . . . 163
4.2 Quantificateur . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.2.1 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.2.2 Instanciation . . . . . . . . . . . . . . . . . . . . . . . 167
4.2.3 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.3 Traduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
4.4 Propriétés des relations. . . . . . . . . . . . . . . . . . . . . . 177
4.5 Langage du premier ordre . . . . . . . . . . . . . . . . . . . . 179
4.5.1 Point de vue syntaxique . . . . . . . . . . . . . . . . . 180
4.5.2 Point de vue sémantique . . . . . . . . . . . . . . . . . 181
4.6 Solutions des exercices . . . . . . . . . . . . . . . . . . . . . . 187
5 Les arbres de consistance II 193
5.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
5.1.1 Première approche . . . . . . . . . . . . . . . . . . . . 194
5.1.2 Règles . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.2 Interprétation . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
5.3 Objets et méthodes . . . . . . . . . . . . . . . . . . . . . . . . 207
5.4 Calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
5.5 Sommaire des règles . . . . . . . . . . . . . . . . . . . . . . . 216
5.6 Solutions des exercices . . . . . . . . . . . . . . . . . . . . . . 217TABLE DES MATIÈRES xiii
6 La déduction naturelle II 237
6.1 Règles d’introduction . . . . . . . . . . . . . . . . . . . . . . . 237
6.2 Règles d’élimination . . . . . . . . . . . . . . . . . . . . . . . 240
6.3 Règles définitoires . . . . . . . . . . . . . . . . . . . . . . . . 243
6.4 Calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
6.5 Sommaire des règles . . . . . . . . . . . . . . . . . . . . . . . 260
6.6 Solutions des exercices . . . . . . . . . . . . . . . . . . . . . . 263
Bibliographie 279
Index 285Introduction
Given a number of premises, logic does
not tell us what concl