2ª Edición 2ª Edición Inteligencia Artificial La primera edición de Inteligencia Artificial: Un Enfoque Modernose ha convertido en un clásico de la literatura sobre la IA. Ha sido adoptado por 600 universidades de 60 países y ha recibido elogios por ser una síntesis definitiva de este campo. Se ha dicho por ejemplo que: “La publicación de este libro de texto fue un avance importante, no sólo para la enseñanza en el campo de la IA, sino también por el punto de vista unificado que introduce. Incluso, los expertos encuentran que todos los capítulos realizan importantes incursiones en la investigación de este campo.” _Prof. Un Enfoque Moderno Thomas Dietterich (Estado de Oregón) “Es simplemente magnífico. El libro que siempre he estado esperando… es como la Biblia de la IA para la próxima década.” _Prof. Gerd Brewka (Viena) “Un logro maravilloso, un libro verdaderamente precioso.” _Prof. Selmer Bringsjord (RPI) 2ª Edición “Es un gran libro, con una profundidad y una amplitud increíbles, y muy bien escrito. Sé que todas las U I personas que lo han utilizado en sus clases han disfrutado con él.” _Prof. Haym Hirsh (Rutgers) n n “Me ha impresionado profundamente esa calidad sin precedentes al presentar el campo de la IA con t log una imagen coherente, equilibrada, extensa y profunda. Se va a convertir en el libro de texto estándar E anvi durante los próximos años.” _Prof. Wolfgang Bibel (Darmstadt) n e irr ceo “¡Es magnífico! Está bien escrito, tiene una estructura muy buena, y disfruta de toda la cobertura f l idN informativa que debería conocer todo estudiante de IA.” _Prof. Martha Pollack (Michigan) o i ifo • “Excepcional… Las descripciones son verdaderamente claras y legibles, y su estructura es excelente; q g rtMll los ejemplos son motivadores y su cobertura informativa es académica y profunda. Va a dominar su u e e e a Aue uss c“pEaelmr omp meoj áodsru lraiabcnrtoute ad lueizn aq tduieoem. d(pDisoep poaoncreu mmeroédsroi tp,o losor paardhomopriitoairs…é.”, Ep_suP ercodafes. iNq tuailesn Nibnuicleslusnsooon c s(oSemtaao mn efeol jroqdru) eq uees cnruibeismtroos l iCbhroa.r)n”i a_kP ryo yf.o, M n qR c i Drew McDermott (Yale) o co f “Un informe magistral de gran alcance en el campo de la Inteligencia Artificial que iluminará a d i nn a profesores, así como a alumnos.” _Dr. Alan Kay e eE g rn n “Este es el libro que me hizo amar la IA.” _Alumno (Indonesia) A iU o l e En la segunda edición, todos los capítulos se han reescrito de forma extensa. Se ha introducido material r t nuevo y elocuente para abarcar áreas tales como la satisfacción de las limitaciones, gráficos de t n planificaciones, agentes de Internet, inferencia de probabilística exacta, técnicas Monte Carlo de la i I cadena Marlon, filtros Kalman, métodos de aprendizaje de conjuntos, aprendizaje estadístico, modelos f de lenguajes naturales probabilísticos, robótica probabilística y aspectos éticos de la IA. i c El libro tiene un soporte variado de recursos en línea (online) incluyendo códigos fuente, figuras, i diapositivas para clase, un directorio de 800 enlaces con la IA en la Web y un grupo de debate en línea a (online). Toda esta información se encuentra disponible en: l aima.cs.berkeley.edu LibroSite es una página web asociada al libro, con una gran variedad de recursos y material adicional tanto para los profesores como para estudiantes. Apoyos a la docencia, ejercicios Russell de autocontrol, enlaces relacionados, material de investigación, etc., hacen de LibroSite el complemento académico perfecto para este libro. Norvig www.librosite.net/russell ISBN 978-84-205-4003-0 Stuart Russell Peter Norvig www.pearsoneducacion.com 9 788420 540030 INTELIGENCIA ARTIFICIAL UN ENFOQUE MODERNO Segunda edición INTELIGENCIA ARTIFICIAL UN ENFOQUE MODERNO Segunda edición Stuart J. Russell y Peter Norvig Traducción: Juan Manuel Corchado Rodríguez Facultad de Ciencias Universidad de Salamanca Fernando Martín Rubio, José Manuel Cadenas Figueredo, Luis Daniel Hernández Molinero y Enrique Paniagua Arís Facultad de Informática Universidad de Murcia Raquel Fuentetaja Pinzán y Mónica Robledo de los Santos Universidad Pontificia de Salamanca, campus Madrid Ramón Rizo Aldeguer Escuela Politécnica Superior Universidad de Alicante Revisión técnica: Juan Manuel Corchado Rodríguez Facultad de Ciencias Universidad de Salamanca Fernando Martín Rubio Facultad de Informática Universidad de Murcia Andrés Castillo Sanz y María Luisa Díez Plata Facultad de Informática Universidad Pontificia de Salamanca, campus Madrid Coordinación general de la traducción y revisión técnica: Luis Joyanes Aguilar Facultad de Informática Universidad Pontificia de Salamanca, campus Madrid Madrid • México • Santafé de Bogotá• Buenos Aires • Caracas • Lima Montevideo • San Juan • San José • Santiago • São Paulo • White Plains Datos de catalogación bibliográfica RUSSELL, S. J.; NORVIG, P. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO Segunda edición PEARSON EDUCACIÓN, S.A., Madrid, 2004 ISBN: 978-84-205-4003-0 Materia:Informática 681.3 Formato 195 (cid:1)250 Páginas: 1240 Todos los derechos reservados. Queda prohibida, salvo excepción prevista en la ley, cualquier forma de reproducción, distribución, comunicación pública y transformación de esta obra sin contar con autorización de los titulares de propiedad intelectual. La infracción de los derechos mencionados puede ser constitutiva de delito contra la propiedad intelectual (arts. 270 y sgts. Código Penal). DERECHOS RESERVADOS ©2004 por PEARSON EDUCACIÓN, S.A. Ribera del Loira, 28 28042 Madrid (España) INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO.Segunda edición RUSSELL, S. J.; NORVIG, P. ISBN: 978-84-205-4003-0 Depósito Legal: M-14511-2008 Última reimpresión: 2008 PEARSON PRENTICE HALL es un sello editorial autorizado de PEARSON EDUCACIÓN, S.A. Authorized translation from the English language edition, entitled ARTIFICIAL INTELLIGENCE: A MODERN APPROACH,2ndedition by RUSSELL, STUART; NORVIG, PETER. Published by Pearson Education, Inc, publishing as Prentice Hall. ©2003. All rights reserved. No part or this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from Pearson Education, Inc. ISBN: 0-13-790395-2 Equipo editorial: Editor: David Fayerman Aragón Técnico editorial: Ana Isabel García Borro Equipo de producción: Director: José Antonio Clares Técnico: José Antonio Hernán Diseño de cubierta: Equipo de diseño de PEARSON EDUCACIÓN, S.A. Composición: COPIBOOK, S.L. Impreso por: IMPRESO EN MÉXICO - PRINTED IN MEXICO Contenido Prólogo XIX Sobre los autores XXV 1 Introducción 1 1.1 ¿Qué es la IA? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Comportamiento humano: el enfoque de la Prueba de Turing . . . . . . . . . . . . . . . . . . 3 Pensar como un humano: el enfoque del modelo cognitivo . . . . . . . . . . . . . . . . . . . . 3 Pensamiento racional: el enfoque de las «leyes del pensamiento» . . . . . . . . . . . . . . . 4 Actuar de forma racional: el enfoque del agente racional . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Los fundamentos de la inteligencia artificial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Filosofía (desde el año 428 a.C. hasta el presente) . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Matemáticas (aproximadamente desde el año 800 al presente) . . . . . . . . . . . . . . . . . 9 Economía (desde el año 1776 hasta el presente) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Neurociencia (desde el año 1861 hasta el presente) . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Psicología (desde el año 1879 hasta el presente) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Ingeniería computacional (desde el año 1940 hasta el presente) . . . . . . . . . . . . . . . . 16 Teoría de control y cibernética (desde el año 1948 hasta el presente) . . . . . . . . . . . . 17 Lingüística (desde el año 1957 hasta el presente) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Historia de la inteligencia artificial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Génesis de la inteligencia artificial (1943-1955) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Nacimiento de la inteligencia artificial (1956) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Entusiasmo inicial, grandes esperanzas (1952-1969) . . . . . . . . . . . . . . . . . . . . . . . . . 21 Una dosis de realidad (1966-1973) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Sistemas basados en el conocimiento: ¿clave del poder? (1969-1979) . . . . . . . . . . . . 26 La IA se convierte en una industria (desde 1980 hasta el presente) . . . . . . . . . . . . . . 28 Regreso de las redes neuronales (desde 1986 hasta el presente) . . . . . . . . . . . . . . . . . 29 IA se convierte en una ciencia (desde 1987 hasta el presente) . . . . . . . . . . . . . . . . . . 29 Emergencia de los sistemas inteligentes (desde 1995 hasta el presente) . . . . . . . . . . 31 1.4 El estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.5 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Notas bibliográficas e históricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2 Agentes inteligentes 37 2.1 Agentes y su entorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2 Buen comportamiento: el concepto de racionalidad . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Medidas de rendimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Racionalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 VI CONTENIDO Omnisciencia, aprendizaje y autonomía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3 La naturaleza del entorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Especificación del entorno de trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Propiedades de los entornos de trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.4 Estructura de los agentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Programas de los agentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Agentes reactivos simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Agentes reactivos basados en modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Agentes basados en objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Agentes basados en utilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Agentes que aprenden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.5 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Notas bibliográficas e históricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3 Resolver problemas mediante búsqueda 67 3.1 Agentes resolventes-problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Problemas y soluciones bien definidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Formular los problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.2 Ejemplos de problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Problemas de juguete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Problemas del mundo real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.3 Búsqueda de soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Medir el rendimiento de la resolución del problema . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.4 Estrategias de búsqueda no informada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Búsqueda primero en anchura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Búsqueda de costo uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Búsqueda primero en profundidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Búsqueda de profundidad limitada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Búsqueda primero en profundidad con profundidad iterativa . . . . . . . . . . . . . . . . . . . 87 Búsqueda bidireccional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Comparación de las estrategias de búsqueda no informada . . . . . . . . . . . . . . . . . . . . 91 3.5 Evitar estados repetidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.6 Búsqueda con información parcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Problemas sin sensores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Problemas de contingencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.7 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Notas bibliográficas e históricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4 Búsqueda informada y exploración 107 4.1 Estrategias de búsqueda informada (heurísticas) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Búsqueda voraz primero el mejor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Búsqueda A*: minimizar el costo estimado total de la solución . . . . . . . . . . . . . . . . . 110 Búsqueda heurística con memoria acotada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Aprender a buscar mejor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.2 Funciones heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 El efecto de la precisión heurística en el rendimiento . . . . . . . . . . . . . . . . . . . . . . . . . 120 Inventar funciones heurísticas admisibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Aprendizaje de heurísticas desde la experiencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 4.3 Algoritmos de búsqueda local y problemas de optimización . . . . . . . . . . . . . . . . . . . 125 CONTENIDO VII Búsqueda de ascensión de colinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 Búsqueda de temple simulado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 Búsqueda por haz local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 4.4 Búsqueda local en espacios continuos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 4.5 Agentes de búsqueda onliney ambientes desconocidos . . . . . . . . . . . . . . . . . . . . . . . 138 Problemas de búsqueda en línea (online) .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 Agentes de búsqueda en línea (online) .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Búsqueda local en línea (online) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Aprendizaje en la búsqueda en línea (online) .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 4.6 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Notas bibliográficas e históricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 5 Problemas de satisfacción de restricciones 155 5.1 Problemas de satisfacción de restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 5.2 Búsqueda con vuelta atrás para PSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Variable y ordenamiento de valor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Propagación de la información a través de las restricciones . . . . . . . . . . . . . . . . . . . . 163 Comprobación hacia delante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Propagación de restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Manejo de restricciones especiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 Vuelta atrás inteligente: mirando hacia atrás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 5.3 Búsqueda local para problemas de satisfacción de restricciones . . . . . . . . . . . . . . . . 169 5.4 La estructura de los problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 5.5 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Notas bibliográficas e históricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 6 Búsqueda entre adversarios 181 6.1 Juegos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.2 Decisiones óptimas en juegos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Estrategias óptimas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 El algoritmo minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Decisiones óptimas en juegos multi-jugador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 6.3 Poda alfa-beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 6.4 Decisiones en tiempo real imperfectas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 Funciones de evaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 Corte de la búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 6.5 Juegos que incluyen un elemento de posibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 Evaluación de la posición en juegos con nodos de posibilidad . . . . . . . . . . . . . . . . . . 198 Complejidad del minimaxesperado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 Juegos de cartas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 6.6 Programas de juegos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 6.7 Discusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 6.8 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Notas bibliográficas e históricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 7 Agentes lógicos 217 7.1 Agentes basados en conocimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 7.2 El mundo de wumpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 VIII CONTENIDO 7.3 Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.4 Lógica proposicional: una lógica muy sencilla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 Sintaxis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 Semántica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 Una base de conocimiento sencilla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 Inferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 Equivalencia, validez y satisfacibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 7.5 Patrones de razonamiento en lógica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 Forma normal conjuntiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 Un algoritmo de resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 Completitud de la resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Encadenamiento hacia delante y hacia atrás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 7.6 Inferencia proposicional efectiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 Un algoritmo completo con backtracking(«vuelta atrás») . . . . . . . . . . . . . . . . . . . . . 248 Algoritmos de búsqueda local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Problemas duros de satisfacibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 7.7 Agentes basados en lógica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Encontrar hoyos y wumpusutilizando la inferencia lógica . . . . . . . . . . . . . . . . . . . . . 253 Guardar la pista acerca de la localización y la orientación del agente . . . . . . . . . . . . 255 Agentes basados en circuitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 Una comparación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 7.8 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 Notas bibliográficas e históricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 8 Lógica de primer orden 271 8.1 Revisión de la representación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 8.2 Sintaxis y semántica de la lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 Modelos en lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 Símbolos e interpretaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 Términos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 Sentencias atómicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Sentencias compuestas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Cuantificador universal (") . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Cuantificación existencial (∃) .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Cuantificadores anidados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Conexiones entre "y ∃ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 Igualdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 8.3 Utilizar la lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 Aserciones y peticiones en lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 El dominio del parentesco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 Números, conjuntos y listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 El mundo de wumpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 8.4 Ingeniería del conocimiento con lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . 295 El proceso de ingeniería del conocimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 El dominio de los circuitos electrónicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Identificar la tarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 Recopilar el conocimiento relevante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 Decidir el vocabulario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299