Logique pour l'informatique et pour l'intelligence artificielle

Ricardo Caferra

Description

La logique, qu'elle soit propositionnelle, du premier ordre ou non classique, joue un rôle capital dans l'informatique et plus particulièrement dans l'intelligence artificielle.
Conçu dans un but d'autoformation, Logique pour l'informatique et pour l'intelligence artificielle donne les bases conceptuelles et les techniques nécessaires à la bonne utilisation d'outils tels que les démonstrateurs automatiques ou assistés.
Il analyse les méthodes des tableaux sémantiques, de Davis et Putnam, de résolution ainsi que les concepts d'unification et de subsomption. La méthode de traduction est privilégiée pour les logiques non classiques.
Les exemples ont été choisis de façon à guider la conception d'abstractions pertinentes pour des classes de problèmes. Les digressions et remarques permettent d'approfondir certains sujets et de découvrir des liens avec d'autres domaines d'étude. Les nombreux exercices corrigés apportent un complément indispensable à la bonne compréhension et à l'assimilation des notions.
1. Introduction. 2. Un peu de réflexion avant la formalisation. 3. La logique propositionnelle (LP ou CP). 4 Les termes du premier ordre. 5. Logique du premier ordre ou logique des prédicats (L1O (LP1,. CP1)). 6. Fondements de programmation en logique. 7. L'intelligence et l'intelligence artificielle. 8. L'inférence. 9. La spécification des problèmes et les langages de la logique. 10. Les logiques (dites) non classiques. 11. La connaissance et la logique : quelques notions. 12. CORRIGÉS.

Sujets

• Informatique
• Intelligence artificielle

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 23 décembre 2010
• Nombre de lectures: 81
• EAN13: 9782746241114
• Langue: Français
• Poids de l'ouvrage: 4 Mo

Extrait

Logique pour l’informatique et pour l’intelligence artificielle



































© LAVOISIER, 2011
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN 978-2-7462-2600-5
ISSN 1242-7691


Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une part,
que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.


Printed and bound in England by Antony Rowe Ltd, Chippenham, January 2011.





Logique pour l’informatique et

pour l’intelligence artificielle












Ricardo Caferra













Collection dirigée par Jean-Charles Pomerol





BANATRE Michel et al. – Informatique diffuse, 2007.
BARTHELEMY Pierre, ROLLAND Robert et VERON Pascal – Cryptographie, 2005.
CARDON Alain – La complexité organisée : systèmes adaptatifs, 2004.
CHRISMENT Claude et al. – Bases de données relationnelles, 2008.
FOURNIER Jean-Claude – Théorie des graphes et applications, 2005.
GUILLOT Philippe – Courbes elliptiques : une présentation élémentaire pour la
cryptographie, 2010.
PARIS Stéphane – Le multimédia et la compression, 2009.
PARIS Stéphane – Le multimédia, 2009.
PIERSON Jacky – La biométrie, 2007.
POLI Alain et GUILLOT Philippe – Algèbre, confidentialité et intégrité en
multimédia, 2009.
POLI Alain et GUILLOT Philippe – Algèbre et protection de l’information, 2005.
VARRETTE Sébastien et BERNARD Nicolas – Programmation avancée en C
avec exercices corrigés, 2006.
VERDRET Philippe – De Perl à Java : programmation des expressions régulières,
2004.
Table des mati`eres
1 Introduction 11
1.1 La logique, les fondements de l’informatique et les applications de la
logique `a l’informatique.......................... 11
1.2 Utilit´e de la logique pour le m´etier d’ing´enieurinformaticien ..... 13
2Unpeuder´eflexion avant la formalisation 17
2.1 Qu’est-cequelalogique?......................... 17
2.1.1 Lalogiqueetlesparadoxes.................... 17
2.1.2 Les paradoxes et la th´eoriedesensembles............ 19
2.1.3 Lesxes dans l’arithm´etique et dans la th´eorie des
ensembles .............................. 22
2.1.4 Surlesformalismesetdesnotionsbienconnues ........ 24
2.1.5 Revenons `alad´efinition de logique ............... 31
2.1.6 Quelques r´eflexions sur la et l’informatique ...... 38
2.2 Des r´ep`ereshistoriques .......................... 39
3 La logique propositionnelle (LP ou CP) 45
3.1 Syntaxe et s´emantique 46
3.2 La m´ethode des tableaux s´emantiques.................. 60
3.3 Syst`emesformels ............................. 70
3.4 Un syst`emeformelpourlaLP(CP)................... 83
3.5 La m´ethodedeDavisetPutnam..................... 95
3.6 Les arbres s´emantiquesdanslaLP 99
3.7 La m´ethode de r´esolutiondanslaLP103
3.7.1 Probl`emes, strat´egies et ´enonc´es.................111
3.7.2 Strat´egies111
3.8 LesclausesdeHorn............................114
3.9 La logique propositionnelle d’un point de vue alg´ebrique .......115
4 Les termes du premier ordre 121
4.1 Filtrage et unification . . .........................121
4.2 Termes du premier ordre, substitution, unification ...........1256 Logique pour l’informatique et pour l’intelligence artificielle
5 Logique du premier ordre ou logique des pr´edicats (L1O (LP1,
CP1)) 131
5.1 Syntaxe ..................................133
5.2 S´emantique ................................136
5.2.1 Les notions de v´erit´e et satisfaction ...............138
5.2.2 Unevariante:lesstructuresmultisortes ............148
5.2.3 Les th´eories et leurs mod`eles...................150
5.3 Les tableaux s´emantiquesdanslaL1O .................151
5.4 L’unification dans la m´ethode des tableaux s´emantiques........163
5.5 Vers une proc´edure de semi-d´ecisionpourlaL1O ...........166
5.5.1 Transformation en forme normale pr´enexe166
5.5.2 FormenormaledeSkolem ....................172
5.6 Les arbres s´emantiquesdanslaL1O...................180
5.7 La m´ethode de r´esolutiondanslaL1O .................183
5.8 Une classe d´ecidable:laclassemonadique ...............193
5.8.1 Quelques classes d´ecidables196
5.9 Les limites : le (premier) th´eor`eme d’incompl´etude de G¨odel .....196
6 Fondements de programmation en logique 201
6.1 Sp´ecificationetprogrammation .....................201
6.2 Vers un langage de programmation en logique .............206
6.3 Programmation en logique : exemples..................209
6.3.1 Agir sur le contrˆole : la coupure (cut) / ...........214
6.3.2 La n´egation par ´echec(NPE)217
6.4 Calculabilit´eetclausesdeHorn224
7 L’intelligence et l’intelligence artificielle 227
7.1 Les syst`emes intelligents : l’intelligence artificielle (IA) ........227
7.2 Quelles approches pour ´etudier l’IA? ..................231
7.3 Vers une d´efinition op´erationnelle de l’intelligence ...........231
7.3.1 Le jeu d’imitation propos´eparTuring..............231
7.4 Peut-on identifier l’intelligence humaine et celle des machines? ....233
7.4.1 Argument de la chambre chinoise ................234
7.5 Un peu d’histoire .............................236
7.6 Quelques th`emes incontest´esdel’IA...................238
8 L’inf´erence 241
8.1 L’inf´erence d´eductive ...........................241
8.2 Unconceptimportant:lasubso(u)mptionentreclauses........248
8.3 L’abduction ................................254
8.3.1 D´ecouverte de th´eories explicatives ...............255
8.4 L’inf´erence inductive ...........................258
8.5 La g´en´eralisation : g´en´eration d’hypoth`eses inductives.........263Table des matières 7
8.5.1 G´en´eralisation `a partir d’exemples et contre-exemples.....267
9Lasp´ecification des probl`emes et les langages de la logique 269
9.1 L’´egalit´e ..................................269
9.1.1 Quand l’utilise-t-on? .......................270
9.1.2 Quelques questions sur l’´egalit´e .................270
9.1.3 1. Pourquoi a-t-on besoin de l’´egalit´e? .............270
9.1.4 2. Qu’est-ce que l’´egalit´e? ....................270
9.1.5 3. Comment raisonner avec l’´egalit´e? ..............272
9.1.6 En sp´ecifiant sans l’´egalit´e ....................273
9.1.7 En axiomatisant l’´egalit´e.....................274
9.1.8 Ajoutant la d´efinition de = et utilisant la m´ethode de r´esolution274
9.1.9 En ajoutant `alam´ethode des tableaux des r`egles sp´ecialis´ees . 275
9.1.10 En ajoutant `alar´esolution des r`egles sp´ecialis´ees .......278
9.2 Lescontraintes ..............................284
9.3 La logique du second ordre (L2O) : quelques notions .........296
9.3.1 Syntaxe et s´emantique ......................299
10 Les logiques (dites) non classiques 303
10.1 Les logiques polyvalentes ou multivalu´ees
(many-valued logics) ...........................303
10.1.1 Comment raisonner avec les logiques p-valu´ees? ........309
10.2 Les concepts inexacts : la logique floue (fuzzy logic) ..........312
10.2.1 Inf´erencedanslalogiquefloue ..................322
10.2.2 La m´ethodedeHerbrandenLF .................324
10.3 Leslogiquesmodales326
10.3.1 Vers une s´emantique .......................328
10.3.2 Commentraisonneravecleslogiquesmodales?.........332
10.4 Quelques ´el´ementsdelogiquetemporelle ................342
10.4.1 Op´erateurs temporels et s´emantique...............345
10.4.2 Unelogiquetemporelle ......................347
10.4.3 Commentraisonneravecleslogiquestemporelles?.......348
10.4.4 Un exemple de logique propositionnelle du temps lin´eaire et
discret : PTL (aussi appel´eePLTL) ..............351
11 La connaissance et la logique : quelques notions 355
11.1 Qu’est-cequelaconnaissance? .....................356
11.2 Connaissanceetlogiquemodale359
11.2.1 Nouveaux op´erateursmodaux ..................360
11.2.2 Exemples d’application......................361
´12 CORRIGES 365AVANT-PROPOS
Cesnotessontler´esultat d’une conception de la transmission des connaissances
et de plusieurs ann´ees d’exp´erience d’enseignement `a l’INP Grenoble (Ensimag).
Silatabledemati`eress’interpr`etetroplitt´eralement,l’entrepriseestirr´ealisable:
les th`emes ´etudi´es dans les diff´erents chapitres ont donn´e lieu `a la publication, par
de nombreux auteurs, de milliers de pages (livres, monographies, articles, livres et
`articles de vulgarisation, etc.) certaines de la plus haute teneur scientifique. A ceci
doit s’ajouter toute l’information accessible via internet.
Lebutdecesnotes,suremenˆ tambitieuxmaisavecl’espoirden’ˆetrepasd´em´esur´e,
est d’essayer de donner une vue qui se veut unifi´ee des concepts et des techniques
utiles dans beaucoup de domaines bien identifi´es de l’informatique et de
l’intelligence artificielle dans leurs maturit´es actuelle. Il est difficile de trouver ces diff´erents
sujets r´eunis dans un mˆeme document. Ces concepts et techniques devraient aussi
permettre au lecteur d’aller plus loin.
La rigueur conceptuelle est toujours privil´egi´ee par rapport a` la rigueur formelle.
Cette approche est indispensable pour la transmission des savoirs dans le monde
moderne,particuli`erementdanscertainsdomaines,ou`lesdiplˆom´esdevrontcontinuer
`aacqu´erir des connaissances tout au long de leur vie professionnelle.
La m´ethode de pr´esentation pour tous les sujets est toujours la mˆeme :
description informelle du sujet `a´