1
Download Lógica de primer orden
Document related concepts
Transcript
PROGRAMACIÓN
LÓGICA
LÓGICA DE PRIMER ORDEN
Juan Juárez Fuentes
Introducción
Lógica de primer orden
La lógica proposicional es uno de los lenguajes de
representación más sencillos, que permite mostrar las
cuestiones fundamentales.
Sin embargo, su ontología es muy limitada, y abarca sólo
aquellos mundos constituidos por hechos.
La lógica de primer orden tiene alcances ontológicos más
amplios. Considera el mundo constituido por objetos y
propiedades que los distingan.
Introducción
Lógica de primer orden
Entre estos objetos hay varios tipos de relaciones, algunas de
las cuales son las funciones.
Ejemplos
Objetos: gente, casas, números, teorías, Ronald McDonald,
colores, juegos de béisbol, guerras, siglos, …
Relaciones: hermano de, mayor que, dentro de, parte de, de
color, sucedió luego de, es el dueño de, …
Propiedades: rojo, redondo, de varios pisos, falso, lo mejor,
…
Funciones: padre de, mejor amigo de, tercer tiempo de, uno
más que, …
Introducción
Lógica de primer orden
“Uno más dos es igual a tres”
Objetos: uno, dos, tres, uno más dos.
Relación: es igual a
Función: más
“Los cuadros cercanos a la pintura brillan”
Objetos: cuadros, pintura
Propiedad: brilla
Relación: cercanía
“El malvado rey Juan gobernó Inglaterra en 1200”
Objetos: Juan, Inglaterra, 1200
Relación: gobernó
Propiedades: malvado, rey
Sintaxis y semántica
Términos
En la lógica proposicional, cada expresión es una oración, que
representa un hecho. En la lógica de primer orden hay
oraciones, pero también términos que representan objetos.
Los signos que representan constantes, las variables y los
signos de funciones sirven todos para construir términos; los
cuantificadores y los signos de predicados sirven para
construir oraciones.
Sintaxis y semántica
Términos (2)
Un término es una expresión lógica que se refiere un objeto.
Los signos de constante son términos.
A veces es más práctico utilizar una expresión para referirse a
un objeto, por ejemplo, en vez de LaPiernaIzquierdaDeJuan es
más práctico usar PiernaIzquierdaDe(Juan)
Sintaxis y semántica
Elementos
Signos de constantes: A, B, C, Juan…
Signos de predicado: Redondo, Hermano…
Ejemplo, Hermano hace referencia al conjunto de tuplas
{<Rey Juan, Ricardo Corazón de León> <Ricardo Corazón
de León, rey Juan>}
Signos de funciones: Coseno, PadreDe, PiernaIzquierdaDe…
Son relaciones en las que un objeto está relacionado
justamente con otro objeto.
Sintaxis y semántica
Oraciones atómicas
Los términos y signos de predicado se combinan para formar
oraciones atómicas, mediante las que se afirman hechos.
Una oración atómica está formada por un signo de predicado y
por una lista de términos entre paréntesis, ejemplo
Hermano (Ricardo, Juan)
Casado (PadreDe (Ricardo), MadreDe (Juan))
Se dice que una oración atómica es verdadera si la relación a la
que alude el signo de predicado es válida para los objetos a los
que aluden los argumentos.
Sintaxis y semántica
Oraciones complejas
Mediante los conectores lógicos se pueden construir oraciones
más complicadas, como en cálculo proposicional, ejemplo:
Hermano (Ricardo, Juan) ∧ Hermano
(Juan, Ricardo)
Mayor (Juan, 30) ∨ Menor (Juan, 30)
Mayor (Juan, 30) ⇒ ¬Menor (Juan, 30)
¬Hermano (Robin, Juan)
Sintaxis y semántica
Cuantificadores
Los cuantificadores permiten expresar propiedades de grupos
completos de objetos en vez de enumerarlos por sus nombres.
La lógica de primer orden contiene dos cuantificadores
estándar, denominados universales y existenciales.
Sintaxis y semántica
Cuantificación universal (∀)
Facilita la expresión de reglas generales, ejemplo: en vez de
decir “Mancha es un gato” y “Mancha es un mamífero” se usa:
∀x Gato (x) ⇒ Mamífero (x)
Lo cual equivale a:
Gato (Mancha) ⇒ Mamífero (Mancha) ∧ Gato (Rebeca) ⇒
Mamífero (Rebeca) ∧ Gato (Félix) ⇒ Mamífero (Félix) ∧ Gato
(Juan) ⇒ Mamífero (Juan) ∧ …
Sintaxis y semántica
Cuantificación universal (∀)
Por lo tanto la primera expresión será valida si y sólo si todas
estas últimas son también verdaderas, es decir, si P es
verdadera para todos los objetos x del universo. Por lo tanto, a
∀ se le conoce como cuantificador universal.
Cuando un término no tiene variables se le conoce como
término de base.
Sintaxis y semántica
Cuantificación existencial (∃)
Con ella podemos hacer afirmaciones sobre cualquier objeto
del universo sin tener que nombrarlo, ejemplo, si queremos
decir que Mancha tiene un hermano que es un gato:
∃x
Hermano (x, Mancha) ∧ Gato (x)
En general, ∃x P es verdadero si P es verdadero para cierto
objeto del universo.
Sintaxis y semántica
Cuantificación existencial (∃)
∃x Hermano (x, Mancha) ∧ Gato (x) equivale a las oraciones:
(Hermano (Mancha, Mancha) ∧ Gato (Mancha))
∨ (Hermano (Rebeca, Mancha) ∧ Gato (Rebeca))
∨ (Hermano (Félix, Mancha) ∧ Gato (Félix))
∨ (Hermano (Ricardo, Mancha) ∧ Gato (Ricardo))
∨…
Así como ⇒ es el conector natural para ∀, ∧ es el conector
natural para ∃.
Sintaxis y semántica
Cuantificadores anidados
“Para toda x y toda y, si x es el padre de y, entonces y es el hijo
de x”
∀x,y Padre (x,y) ⇒ Hijo (y,x)
“Para toda x y toda y, si x es hermano de y, entonces y es
hermano de x”
∀x,y Hermano (x,y) ⇒ Hermano (y,x)
Sintaxis y semántica
Cuantificadores anidados (2)
“Todas las personas aman a alguien”
∀x ∃y Aman (x,y)
“Siempre hay alguien a quien todos aman”
∃y ∀x Aman (x,y)
Sintaxis y semántica
Fórmula bien formada
Una oración como ∀x P (y), en la que y carece de cuantificador,
es incorrecta.
El término fórmula bien configurada o fbc se emplea para
calificar oraciones en las que todas sus variables se han
introducido adecuadamente.
También se puede decir formula bien formada o fbf.
Sintaxis y semántica
Relaciones entre ∀ y ∃
Ambos cuantificadores están estrechamente relacionados
entre sí mediante la negación.
“A todos les desagradan las espinacas” ≡ “No hay alguien a
quien le gusten las espinacas”
∀x ¬LeGustan(x, espinacas) ≡ ¬∃x LeGustan (x, espinacas)
“A todos les gusta el helado” ≡ “No hay alguien a quien no le
guste el helado”
∀x LeGusta(x, helado) ≡ ¬∃x ¬LeGusta (x, helado)
Sintaxis y semántica
Relaciones entre ∀ y ∃
Puesto que ∀ es una conjunción de objetos del universo y ∃ es
su disyunción, es natural que obedezcan las leyes de De
Morgan:
∀x ¬P ≡ ¬∃x P
¬∀x P ≡ ∃x ¬P
∀x P ≡ ¬∃x ¬P
∃x P ≡ ¬∀x ¬P
¬P ∧ ¬Q ≡ ¬(P ∨ Q)
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
P ∧Q ≡ ¬ (¬P ∨ ¬Q)
P ∨Q ≡ ¬ (¬P ∧ ¬Q)
Sintaxis y semántica
Igualdad
Para formular aseveraciones en las que los dos términos se
refieren a un mismo objeto se utiliza el símbolo de igualdad:
Padre(Juan) = Enrique
El signo de igualdad sirve para describir las propiedades de
una función determinada o se puede emplear en la negación
para insistir en que dos términos no son el mismo objeto:
∃x,y Hermano(Mancha, x) ∧ Hermano(Mancha, y) ∧ ¬(x=y)
Extensiones en la Notación
Lógica de orden superior
El nombre lógica de primer orden se basa en el hecho de que
con ella se cuantifican objetos (las entidades de primer orden
que en realidad existen en el mundo), aunque no permiten
cuantificar las relaciones o funciones que existen entre dichos
objetos.
Mediante la lógica de orden superior es posible cuantificar
relaciones y funciones al igual que objetos.
∀x,y (x=y) ⇔ (∀p p(x) ⇔ p(y))
∀f,g (f=g) ⇔ (∀x f(x) ⇔ g(x))
Extensiones en la Notación
Operador λ
Expresiones funcionales y de predicado usando el operador λ.
El operador λ se usa para convertir términos en funciones,
especificando sus argumentos:
λx,y x2 - y2
Esta expresión se aplica a los argumentos para producir un
término lógico de la misma manera que lo haría una función
común:
(λx,y x2 - y2) (25,24) = 252 – 242 = 49
Extensiones en la Notación
El cuantificador de unicidad ∃!
Se utiliza para afirmar la existencia de un objeto específico que
satisface determinado predicado.
“Existe un solo rey”
∃! Rey(x)
“Todo país tiene exactamente un gobernante””
∀ c País(c) ⇒ ∃! r Gobernante(r, c)
Extensiones en la Notación
El operador de unicidad ι
Se utiliza para representar directamente el objeto específico,
ejemplo:
“El único gobernante de Libertania está muerto”
Muerto (ι r Gobernante(r, Libertania))
Que es una abreviatura de
∃! r Gobernante (r, Libertania) ∧ Muerto (r)
Uso de una lógica de primer orden
Dominio
En la representación del conocimiento, un dominio es un
fragmento del mundo acerca del que deseamos expresar un
determinado conocimiento.
Uso de una lógica de primer orden
Dominio (2)
El dominio del parentesco
En este dominio están presentes hechos tales como:
Y reglas como:
“Isabel es la madre de Carlos” y “Carlos es el padre de
Guillermo”
“Si x es la madre de y y y es padre de z, entonces x es la
abuela de z”
Los objetos de este dominio son personas.
Uso de una lógica de primer orden
Dominio (3)
El dominio del parentesco
Entre las propiedades que poseen están el género y las
relaciones que guardan entre sí son las de padres,
hermanos, esposos, etc.
Por lo tanto, hay dos predicados unarios: Hombre y Mujer.
La mayoría de las relaciones de parentesco serán
predicados binarios:
Progenitor, Hijo, Hermano, Hermana, Progenie, Hijo, Hija,
Esposo, Esposa, Cónyuge, Abuelo, Nieto, Primo, Tía,
Tío.
Para Madre y Padre se usarán funciones, puesto que todo
mundo cuenta con ellos desde un punto de vista biológico.
Uso de una lógica de primer orden
Dominio (4)
El dominio del parentesco
La madre de alguien es su progenitor femenino:
El esposo de alguien es su cónyuge masculino
∀m,c Madre(m,c) ⇔ Mujer(m) ∧ Progenitor(m,c)
∀w,h Esposo(h,w) ⇔ Hombre(h) ∧ Cónyuge(h,w)
Masculino y femenino son categorías disyuntas:
∀x Hombre(x) ⇔ ¬Mujer(x)
Uso de una lógica de primer orden
Dominio (5)
El dominio del parentesco
Progenitor y progenie son relaciones inversas:
∀p,c Progenitor(p,c) ⇔ Progenie(c,p)
Un(a) abuelo(a) es progenitor del progenitor de alguien:
∀g,c Abuelo_a(g,c) ⇔ ∃p Progenitor(g,p) ∧
Progenitor(p,c)
Un hermano es otro de los hijos de los progenitores de
alguien:
∀x,y Hermanos(x,y) ⇔ x ≠ y ∧ ∃p Progenitor(p,x) ∧
Progenitor(p,y)
Uso de una lógica de primer orden
Axiomas, definiciones y teoremas
Los matemáticos crean axiomas para capturar los hechos
básicos acerca de un dominio, para definir otros conceptos en
función de tales hechos básicos y para utilizar los axiomas y
las definiciones para demostrar teoremas.
¿Cómo saber si se han postulado una cantidad suficiente de
axiomas de tal manera que un dominio quede completamente
especificado? Postulando un conjunto de predicados básicos
en función de los cuales se pueden definir los demás.
¿Y si tenemos demasiadas oraciones? Revisar cuáles
oraciones no son necesarias y se pueden inferir con otras
oraciones.
Uso de una lógica de primer orden
Axiomas, definiciones y teoremas
Sin embargo, hay axiomas independientes, que son aquellos
que no se pueden obtener a partir de otros axiomas.
Un axioma como ∀x,y P(x,y) ≡… se conoce como definición de
P, porque sirve para definir exactamente para qué objetos P se
cumple y para cuáles no.
Uso de una lógica de primer orden
El dominio de los conjuntos
En este dominio, ConjuntoVacío es una constante, Miembro y
Subconjunto son predicados; Intersección, Unión y Adyunción
o Incorporación son funciones. Conjunto es un predicado
únicamente válido en los conjuntos.
Los ocho axiomas siguientes estipulan que:
Los únicos conjuntos son el conjunto vacío y aquellos que
resultan de incorporar algo a un conjunto
∀s Conjunto(s) ⇔ (s = ConjuntoVacio) ∨ (∃x,s2
Conjunto(s2) ∧ s=Adyunto(x, s2))
Uso de una lógica de primer orden
El dominio de los conjuntos
El conjunto vacío es aquel que no tiene incorporado ningún
elemento.
¬∃x,s Adyunto(x, s) = ConjuntoVacío
La adyunción de un elemento que ya esté en el conjunto no
produce efecto alguno.
∀x,s Miembro(x,s) ⇔ s = Adyunto(x,s)
Los únicos miembros de un conjunto son los elementos que ya
fueron incorporados a dicho conjunto.
∀x,s Miembro(x) ⇔ ∃y,s2 (s=Adjunto(y, s2) ∧ (x=y ∨
Miembro(x,s2)))
Uso de una lógica de primer orden
El dominio de los conjuntos
Un conjunto es subconjunto de otro si y sólo si todos los
miembros del primer conjunto son miembros del segundo
conjunto.
∀s1,s2 Subconjunto(s1,s2) ⇔ (∀x Miembro(x, s1) ⇒ Miembro(x,
s2)))
Dos conjuntos son iguales si y sólo si cada uno de ellos es
subconjunto del otro.
∀s1,s2 (s1 = s2) ⇔ (Subconjunto(s1,s2) ∧ Miembro(s2, s1)))
Uso de una lógica de primer orden
El dominio de los conjuntos
Un objeto es miembro de la intersección de dos conjuntos si y
sólo si es también miembro de cada uno de los conjuntos.
∀x,s1,s2 Miembro (x, Intersección(s1,s2)) ⇔ Miembro (x,s1) ∧
Miembro (x,s2)
Un objeto es miembro de la unión de dos conjuntos si y sólo si
es también miembro de uno de los dos conjuntos
∀x,s1,s2 Miembro (x, Unión(s1,s2)) ⇔ Miembro (x,s1) ∨
Miembro (x,s2)
Uso de una lógica de primer orden
Notaciones
Notaciones especiales para conjuntos, listas y aritmética
∅ = Conjunto vacío
{x} = Adjunto(x, Conjunto vacío)
{x,y} = Adjunto(x, Adjunto(y, Conjunto vacío)
{x,y|s} =Adjunto (x, Adjunto(y,s))
r ∪ s = Unión(r,s)
r ∩ s = Intersección (r,s)
x∈ s = Miembro(x,s)
r ⊆ s = Subconjunto(r,s)
[] = Nada
[x] = Cons(x, Nada)
[x,y] =Cons(x, Cons(y,
Nada))
[x,y|l] =Cons(x, Cons(y, l))
Uso de una lógica de primer orden
Preguntas o consultas
Cómo formular preguntas y obtener respuestas
Para añadirle oraciones a la base de conocimientos BC,
diríamos:
Decir(BC, (∀m,c Madre(m,c) ⇔ Mujer(m) ∧
Progenitor(m,c)))
Decir(BC, (Mujer(Maxi) ∧ Progenitor(Maxi,Mancha) ∧
Progenitor(Mancha,Botas)))
Y luego podríamos preguntar
Preguntar(BC, Abuelo_a(Maxi, Botas))
Uso de una lógica de primer orden
Preguntas o consultas (2)
Cómo formular preguntas y obtener respuestas
Las oraciones añadidas al utilizar DECIR se llaman
aseveraciones.
A las preguntas formuladas mediante PREGUNTAR se les
conoce como consultas u objetivos.
También se pueden hacer preguntas básicamente
cuantificadas como:
Preguntar(BC,∃x Hijo(x,Mancha))
Las preguntas del tipo “¿Existe una x tal que…?” se
resuelve proporcionando esa x, mediante una sustitución o
lista de enlace.
Caso de aplicación
Agentes lógicos para el mundo de wumpus
Se consideran tres arquitecturas:
Agentes reflejos
Agentes basados en modelos
Agentes basados en metas
Lo primero que se debe hacer es definir la interfaz entre el
agente y el ambiente.
Percepción([Hedor, Brisa, Resplandor, Nada],5)
La acción del agente debe ser una de las siguientes:
Vuelta(Derecha), Vuelta(Izquierda), Adelante, Disparar,
Tomar, Soltar, Saltar
Caso de aplicación
Agentes lógicos para el mundo de wumpus
(2)
Para decidir cuál es la mejor, la función HACER-CONSULTASOBRE-ACCION crea una consulta tal como
∃a Acción(a,5)
Caso de aplicación
Un agente reflejo simple
El más sencillo de los agentes funciona mediante reglas que
conectan directamente percepciones y acciones. Tales reglas
se parecen a los reflejos o a los instintos, ejemplo:
∀s,b,u,c,t Percepción([s,b,Resplandor,u,c],t) ⇒
Acción(Tomar,t)
La relación entre percepción y acción puede estar regulada por
reglas de percepción, mediante las cuales se elabora una
abstracción de la entrada perceptual inmediata y se le
convierte en formas más útiles.
∀b,g,u,c,t Percepción([Hedor,b,g,u,c],t) ⇒ Hedor(t)
∀s,g,u,c,t Percepción([s,Brisa,g,u,c],t) ⇒ Brisa(t)
∀s,b,u,c,t Percepción([s,b,Resplandor,u,c],t) ⇒ EnOro(t)
…
Caso de aplicación
Un agente reflejo simple (2)
De esta forma, se puede establecer una conexión entre los
predicados anteriores y las posibles acciones:
∀t , EnOro(t) ⇒ Acción(Tomar, t)
Caso de aplicación
Un agente reflejo simple (3)
Limitaciones de los agentes reflejos simples
El mundo del wumpus es difícil para los simples agentes
reflejos.
La acción Saltar permite ver el porqué. Un agente reflejo
puro no sabe con seguridad cuándo saltar, puesto que ni
tener el oro ni estar en el cuadro inicial son parte de su
percepción.
También son incapaces de evitar los ciclos infinitos.
Caso de aplicación
Cómo representar los cambios en el mundo
Cualquier sistema que tome sus decisiones basándose en
percepciones anteriores puede ser reelaborado para que en
vez de tales percepciones utilice un conjunto de oraciones que
se refieran al estado actual del mundo.
Las reglas que describen la manera como cambia (o no
cambia) el mundo se conocen como reglas diacrónicas, del
griego “a través del tiempo”.
Caso de aplicación
Cómo representar los cambios en el mundo
(2)
Una manera de manejar el cambio es sustituir oraciones en la
BC. La inconveniencia es que pierde todo conocimiento acerca
del pasado.
Otra es que el agente pueda explorar estados del pasado y
posibles estados del futuro, donde cada uno se representa
mediante una BC diferente
En principio, representar situaciones y acciones no es distinto
que representar objetos más concretos como los gatos y los
reyes, o relaciones concretas como el hermanazgo.
Caso de aplicación
Cómo representar los cambios en el mundo
(3)
Cálculo de situaciones
Es el nombre dado para una manera particular de describir
el cambio en la lógica de primer orden.
Concibe al mundo como una secuencia de situaciones,
cada una de las cuales es como una “instantánea” del
estado del mundo.
Las situaciones se generan mediante acciones desde
situaciones anteriores.
Caso de aplicación
Cómo representar los cambios en el mundo
(4)
Cálculo de situaciones
Para hacer esto, se proporciona al predicado
correspondiente un argumento de situación adicional. Por
ejemplo, en vez de usar En(Agente, ubicación), tendríamos
En(Agente, [1,1],S0 ∧ Agente, [1,2],S1)
Caso de aplicación
Cómo representar los cambios en el mundo
(5)
Cálculo de situaciones
Para representar cómo cambia el mundo de una situación a
otra se emplea la función resultado:
Resultado (HaciaAdelante,S0) =S1
Resultado (DarVuelta(ALaDerecha, S1) =S2
Resultado (HaciaAdelante,S2) =S3
Caso de aplicación
Cómo representar los cambios en el mundo
(6)
Cálculo de situaciones
También se cuenta con:
Axiomas de efecto, para definir el efecto que produce el
realizar alguna acción.
Axiomas de cuadro, para describir cómo el mundo
permanece igual
Axiomas de estado sucesor, para definir cuando un
predicado es válido después de una acción siempre y
cuando sea verdadero o lo siga siendo, y falso en
cualquier otro caso.
Caso de aplicación
Hacia un agente basado en metas
Una vez encontrado el oro, las políticas deben modificarse
radicalmente. El objetivo ahora es regresar al cuadro de partida
a la brevedad posible. Lo que ahora desearíamos es inferir que
el agente tiene como meta encontrarse en la ubicación [1,1].
Caso de aplicación
Hacia un agente basado en metas (2)
Lo anterior se puede lograr de tres maneras por lo menos:
Inferencia
Búsqueda
Planificación
Bibliografía
Genesereth, Michael and Kao, Eric. Introduction to logic.
Morgan \& Claypool Publishers. 2013.
David Barker-Plummer, Jon Barwise, and John Etchemendy.
CSLI Publications, Stanford, CA, USA, 2nd edition.
Armin Biere, Marijn J. H. Heule, Hans van Maaren, and Toby
Walsh, editors. Handbook of Satisfiability, volume 185 of
Frontiers in Artificial Intelligence and Applications. IOS Press,
Lansdale, PA, USA, February 2009.
Hans K. Buning and T. Letterman. Propositional Logic:
Deduction and Algorithms. Cambridge University Press, New
York, NY, USA, 1999.
Bibliografía (2)
Chin-Liang Chang and Richard C. Lee. Symbolic Logic and
MechanicalTheorem Proving (Computer Science Classics). Academic
Press, Salt Lake City, UT, USA, May 1973.
Herbert B. Enderton. A Mathematical Introduction to Logic. Academic
Press, Salt Lake City, UT, USA, 2nd edition, 2001.
Timothy Hinrichs and Michael Genesereth. Herbrand logic. Technical
Report LG-2006-02, Stanford University, Stanford, CA, USA, 2006.
http://logic.stanford.edu/reports/LG-2006-02.pdf.
John Alan Robinson and Andrei Voronkov, editors. Handbook of
Automated Reasoning (in 2 volumes). MIT Press, Cambridge, MA,
USA, 2001.
