PDF de programación - 2013 Temas de “Programación lógica e I.A.

Temas de “Programación lógica e I.A.”

José A. Alonso Jiménez

Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 21 de febrero de 2013

Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain
de Creative Commons.

Se permite:

copiar, distribuir y comunicar públicamente la obra

hacer obras derivadas

Bajo las condiciones siguientes:

Reconocimiento. Debe reconocer los créditos de la obra de la manera espe-
cificada por el autor.

No comercial. No puede utilizar esta obra para fines comerciales.

Compartir bajo la misma licencia. Si altera o transforma esta obra, o genera
una obra derivada, sólo puede distribuir la obra generada bajo una licencia
idéntica a ésta.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licen-
cia de esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular
de los derechos de autor.

Esto es un resumen del texto legal (la licencia completa). Para ver una copia de esta
licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie una
carta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Índice general

1. El sistema deductivo de Prolog

2. Introducción a la programación lógica con Prolog

3. Programación con Prolog

4. Resolución de problemas de espacios de estados

5. Procesamiento del lenguaje natural

6. Ingeniería del conocimiento y metaintérpretes

7. Razonamiento por defecto y razonamiento abductivo

8. Programación lógica con restricciones

9. Formalización en Prolog de la lógica proposicional

10. Programación lógica y aprendizaje automático

Bibliografía

5

21

55

77

103

133

165

177

193

219

261

3

4

Índice general

Capítulo 1

El sistema deductivo de Prolog

5

6

Capítulo 1. El sistema deductivo de Prolog

PDTema1:ElsistemadeductivodePrologProgramaciónlógica(2008–09)Tema1:ElsistemadeductivodePrologJoséA.AlonsoJiménezGrupodeLógicaComputacionalDepartamentodeCienciasdelaComputacióneI.A.UniversidaddeSevilla1/27PDTema1:ElsistemadeductivodeProlog1.IntroducciónObjetivosdelcursoDeclarativovs.imperativoHistoriadelaprogramaciónlógica2.DeducciónPrologDeducciónPrologenlógicaproposicionalDeducciónPrologenlógicarelacionalDeducciónPrologenlógicafuncional2/27 Programación lógica e I.A.

7

PDTema1:ElsistemadeductivodePrologIntroducciónObjetivosdelcursoTema1:ElsistemadeductivodeProlog1.IntroducciónObjetivosdelcursoDeclarativovs.imperativoHistoriadelaprogramaciónlógica2.DeducciónProlog3/27PDTema1:ElsistemadeductivodePrologIntroducciónObjetivosdelcursoObjetivosdelcursoILógicacomo:IsistemadeespecificaciónyIlenguajedeprogramaciónIPrincipios:IProgramas=TeoríasIEjecución=BúsquedadepruebasIProgramación=ModelizaciónIProlog=ProgramminginLogicIRelacionesconotroscampos:IInteligenciaartificialISistemasbasadosenelconocimientoIProcesamientodellenguajenatural4/27 8

Capítulo 1. El sistema deductivo de Prolog

PDTema1:ElsistemadeductivodePrologIntroducciónDeclarativovs.imperativoTema1:ElsistemadeductivodeProlog1.IntroducciónObjetivosdelcursoDeclarativovs.imperativoHistoriadelaprogramaciónlógica2.DeducciónProlog5/27PDTema1:ElsistemadeductivodePrologIntroducciónDeclarativovs.imperativoDeclarativovs.imperativoIParadigmasIImperativo:SedescribecómoresolverelproblemaIDeclarativo:SedescribequéeselproblemaIProgramasIImperativo:UnasucesióndeinstruccionesIDeclarativo:UnconjuntodesentenciasILenguajesIImperativo:Pascal,C,FortranIDeclarativo:Prolog,Lisppuro,ML,HaskellIVentajasIImperativo:ProgramasrápidosyespecializadosIDeclarativo:Programasgenerales,cortosylegibles6/27 Programación lógica e I.A.

9

PDTema1:ElsistemadeductivodePrologIntroducciónHistoriadelaprogramaciónlógicaTema1:ElsistemadeductivodeProlog1.IntroducciónObjetivosdelcursoDeclarativovs.imperativoHistoriadelaprogramaciónlógica2.DeducciónProlog7/27PDTema1:ElsistemadeductivodePrologIntroducciónHistoriadelaprogramaciónlógicaHistoriadelaprogramaciónlógicaI1960:DemostraciónautomáticadeteoremasI1965:Resoluciónyunificación(Robinson)I1969:QA3,obtenciónderespuesta(Green)I1972:ImplementacióndeProlog(Colmerauer)I1974:Programaciónlógica(Kowalski)I1977:PrologdeEdimburgo(Warren)I1981:ProyectojaponésdeQuintaGeneraciónI1986:ProgramaciónlógicaconrestriccionesI1995:EstándarISOdeProlog8/27 10

Capítulo 1. El sistema deductivo de Prolog

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicaproposicionalTema1:ElsistemadeductivodeProlog1.Introducción2.DeducciónPrologDeducciónPrologenlógicaproposicionalDeducciónPrologenlógicarelacionalDeducciónPrologenlógicafuncional9/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicaproposicionalDeducciónPrologenlógicaproposicionalIBasedeconocimientoyobjetivo:IBasedeconocimiento:IRegla1:Siunanimalesunguladoytienerayasnegras,entoncesesunacebra.IRegla2:Siunanimalrumiayesmamífero,entoncesesungulado.IRegla3:Siunanimalesmamíferoytienepezuñas,entoncesesungulado.IHecho1:Elanimalesmamífero.IHecho2:Elanimaltienepezuñas.IHecho3:Elanimaltienerayasnegras.IObjetivo:Demostrarapartirdelabasedeconocimientosqueelanimalesunacebra.10/27 Programación lógica e I.A.

11

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicaproposicionalDeducciónPrologenlógicaproposicionalIPrograma:es_cebra:-es_ungulado,tiene_rayas_negras.%R1es_ungulado:-rumia,es_mamífero.%R2es_ungulado:-es_mamífero,tiene_pezuñas.%R3es_mamífero.%H1tiene_pezuñas.%H2tiene_rayas_negras.%H3ISesión:>plWelcometoSWI-Prolog(Multi-threaded,Version5.6.20)Copyright(c)1990-2006UniversityofAmsterdam.?-[animales].Yes?-es_cebra.Yes11/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicaproposicionalDeducciónPrologenlógicaproposicionalIÁrboldededucción:12/27 12

Capítulo 1. El sistema deductivo de Prolog

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicaproposicionalDeducciónPrologenlógicaproposicionalIDemostraciónporresoluciónSLD:13/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicarelacionalTema1:ElsistemadeductivodeProlog1.Introducción2.DeducciónPrologDeducciónPrologenlógicaproposicionalDeducciónPrologenlógicarelacionalDeducciónPrologenlógicafuncional14/27 Programación lógica e I.A.

13

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicarelacionalDeducciónPrologenlógicarelacionalIBasedeconocimiento:IHechos1-4:6y12sondivisiblespor2ypor3.IHecho5:4esdivisiblepor2.IRegla1:Losnúmerosdivisiblespor2ypor3sondivisiblespor6.IPrograma:divide(2,6).%Hecho1divide(2,4).%Hecho2divide(2,12).%Hecho3divide(3,6).%Hecho4divide(3,12).%Hecho5divide(6,X):-divide(2,X),divide(3,X).%Regla115/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicarelacionalDeducciónPrologenlógicarelacionalISímbolos:IConstantes:2,3,4,6,12IRelaciónbinaria:divideIVariable:XIInterpretacionesdelaRegla1:Idivide(6,X):-divide(2,X),divide(3,X).IInterpretacióndeclarativa:(∀X)[divide(2,X)∧divide(3,X)→divide(6,X)]IInterpretaciónprocedimental.IConsulta:¿Cuálessonlosmúltiplosde6??-divide(6,X).X=6;X=12;No16/27 14

Capítulo 1. El sistema deductivo de Prolog

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicarelacionalDeducciónPrologenlógicarelacionalIÁrboldededucción:IComentarios:IUnificación.ICálculoderespuestas.IRespuestasmúltiples.17/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalTema1:ElsistemadeductivodeProlog1.Introducción2.DeducciónPrologDeducciónPrologenlógicaproposicionalDeducciónPrologenlógicarelacionalDeducciónPrologenlógicafuncional18/27 Programación lógica e I.A.

15

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalDeducciónPrologenlógicafuncionalIRepresentacióndelosnúmerosnaturales:0,s(0),s(s(0)),...IDefinicióndelasuma:0+Y=Ys(X)+Y=s(X+Y)IProgramasuma(0,Y,Y).%R1suma(s(X),Y,s(Z)):-suma(X,Y,Z).%R2IConsulta:¿Cuáleslasumades(0)ys(s(0))??-suma(s(0),s(s(0)),X).X=s(s(s(0)))Yes19/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalDeducciónPrologenlógicafuncionalIÁrboldededucción:20/27 16

Capítulo 1. El sistema deductivo de Prolog

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalDeducciónPrologenlógicafuncionalIConsulta:I¿Cuáleslarestades(s(s(0)))ys(s(0))?ISesión:?-suma(X,s(s(0)),s(s(s(0)))).X=s(0);No21/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalDeducciónPrologenlógicafuncionalIÁrboldededucción:22/27 Programación lógica e I.A.

17

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalDeducciónPrologenlógicafuncionalIConsulta:IPregunta:¿CuálessonlassolucionesdelaecuaciónX+Y=s(s(0))?ISesión:?-suma(X,Y,s(s(0))).X=0Y=s(s(0));X=s(0)Y=s(0);X=s(s(0))Y=0;No23/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalDeducciónPrologenlógicafuncionalIÁrboldededucción:24/27 18

Capítulo 1. El sistema deductivo de Prolog

PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalDeducciónPrologenlógicafuncionalIConsulta:IPregunta:resolverelsistemadeecuaciones1+X=YX+Y=1ISesión:?-suma(s(0),X,Y),suma(X,Y,s(0)).X=0Y=s(0);No25/27PDTema1:ElsistemadeductivodePrologDeducciónPrologDeducciónPrologenlógicafuncionalDeducciónPrologenlógicafuncionalIÁrboldededucción:26/27 Programación lógica e I.A.

19

PDTema1:ElsistemadeductivodePrologBibliografíaBibliografía1.J.A.Alonso(2006)IntroducciónalaprogramaciónlógicaconProlog.ICap.0:“Introducción”.2.I.Bratko(1990)PrologProgrammingforArtificialIntelligence(2nded.)ICap.1:“AnoverviewofProlog”.ICap.2:“SyntaxandmeaningofPrologprograms”.3.W.F.ClocksinyC.S.Mellish(1994)ProgramminginProlog(FourthEdition).ICap.1:“Tutorialintroduction”.ICap.2:“Acloserlook”.27/27 20

Capítulo 1. El sistema deductivo de Prolog

Capítulo 2

Introducción a la programación lógica
con Prolog

21

22

Capítulo 2.

Introducción a la programación lógica con Prolog

PDTema2:PrologProgramaciónlógica(2008–09)Tema2:PrologJoséA.Alon