FOL-1b
description
Transcript of FOL-1b
-
Lgica de primer orden (I)
Lorenzo Mandow, Ezequiel Lpez-Rubio y Enrique Domnguez
Depto. de Lenguajes y Ciencias de la Computacin
Universidad de Mlaga
-
Contenidos
6.1 Motivacin
6.2 Sintaxis
6.3 Semntica
-
1. Motivacin
La lgica proposicional no es concisa cuando hay muchos objetos.
Tampoco permite ciertos razonamientos. Por ejemplo:
Todos los hombres son mortales Thm
Scrates es hombre Sh
Scrates es mortal Sm
no es un argumento vlido en lgica proposicional.
-
1. Motivacin
La lgica de primer orden es ms expresiva:
Analiza la estructura de las oraciones (sujeto y predicado, o en general, predicado y objetos sobre los que predica).
Ej. Scrates es hombre
6 es divisible por 2
El sucesor de 5 es divisible por 2
Considera la posibilidad de objetos genricos (variables) y los conceptos de todo y alguno (cuantificadores)
Ej. Todos los hombres son mortales
-
Contenidos
6.1 Motivacin
6.2 Sintaxis
6.3 Semntica
-
2. Sintaxis
Los elementos sintcticos bsicos de la lgica de primer orden son: smbolos de constante, funcin y predicado. Comenzarn siempre con mayscula.
Cada funcin o predicado tiene una aridad fija.
Representaremos a las variables mediante cualquier cadena alfanumrica que empiece por minscula.
-
2. Sintaxis
S tomo
S | (SS) | (SS) | (SS) | (SS)
Esta parte es igual que en lgica proposicional, pero ahora los tomos tienen estructura
-
2. Sintaxis
Trmino Variable | Constante | Funcin (Trmino*)
tomo Predicado(Trmino*) | Trmino = Trmino
S tomo
S | (SS) | (SS) | (SS) | (SS)
por ltimo, aadimos los cuantificadores sobre variables.
-
2. Sintaxis
Trmino Variable | Constante | Funcin (Trmino*)
tomo Predicado(Trmino*) | Trmino = Trmino
S tomo
S | (SS) | (SS) | (SS) | (SS)
Variable S
Variable S
-
Contenidos
6.1 Motivacin
6.2 Sintaxis
6.3 Semntica
-
6.3 Semntica
Recordemos: En la lgica proposicional: 1. Cada proposicin puede ser verdadera o falsa. 2. Una interpretacin asigna valores de verdad a las
proposiciones atmicas 3. El valor de verdad de las proposiciones compuestas
se compone a partir de los valores de las proposiciones atmicas, siguiendo las reglas semnticas de las conectivas lgicas.
-
6.3 Semntica
En lgica de primer orden:
1. Debemos establecer un dominio de objetos del mundo real.
2. Una interpretacin establece una correspondencia entre:
1. Las constantes y los objetos del dominio. 2. Los predicados y las relaciones entre dichos objetos. 3. Las funciones y las funciones sobre dichos objetos.
-
6.3 Semntica
Cada trmino se refiere a un objeto del dominio, y su semntica viene determinada por la interpretacin.
Una expresin atmica es verdadera, si la relacin a que hace referencia el predicado es cierta entre los objetos del dominio a los que hacen referencia sus argumentos.
El valor de verdad de las expresiones compuestas mediante conectivas lgicas, se compone a partir de los valores de las expresiones atmicas (igual que en la lgica proposicional).
-
6.3 Semntica
Una frmula cuantificada universalmente x P es verdadera, si P sigue siendo verdadera tras
interpretar que x se refiere a cada uno de los objetos del dominio.
Una frmula cuantificada existencialmente x P es verdadera si P es verdadera para al menos una
interpretacin de x como un objeto del dominio.
-
6.3 Semntica
Los cuantificadores se pueden anidar. Si combinamos existenciales con universales, el orden es muy importante:
Todo el mundo ama a alguien: x y Loves(x,y)
Existe alguien que es amado por todo el mundo: y x Loves(x,y)
Reglas de De Morgan para frmulas cuantificadas:
x P x P
x P x P
-
6.3 Semntica
Usaremos el predicado de igualdad = para indicar que dos trminos se refieren al mismo objeto Si queremos expresar que el objeto al que se
refiere Father(John) y el objeto al que se refiere Henry son el mismo, escribimos:
Father(John)=Henry
Ricardo tiene al menos dos hermanos:
x,y Brother(x,Richard) Brother(y,Richard) (x=y)
-
6.3 Semntica (Ejemplo)
Dominio: El rey Ricardo Corazn de Len; su hermano menor, el
malvado rey Juan; las piernas izquierdas de Ricardo y Juan; y una corona (en total 5 objetos)
Relaciones: Hermandad={, } Sobre la cabeza={}
Funciones: Pierna izquierda={ La pierna izquierda de Ricardo, La pierna izquierda de Juan }
-
6.3 Semntica (Ejemplo) Smbolos de constante: Richard, John
Smbolos de predicado: Brother, OnHead, Person, King, Crown
Smbolo de funcin: LeftLeg
Una posible interpretacin (entre otras muchas) : Richard se refiere a Ricardo Corazn de Len y John se refiere al
malvado rey Juan
Brother se refiere a la relacin de hermandad; OnHead se refiere a la relacin sobre la cabeza; Person, King y Crown se refieren a los conjuntos de objetos que son personas, reyes y coronas, respectivamente
LeftLeg se refiere a la funcin pierna izquierda
-
6.3 Semntica (Ejemplo)
-
6.3 Semntica (Ejemplo)
Ejemplos de trminos:
Richard
LeftLeg(John)
LeftLeg(LeftLeg(Richard)) (!)
Ejemplos de tomos:
Brother(Richard,John) Person(LeftLeg(Richard))
-
6.3 Semntica (Ejemplo)
Ejemplos de frmulas compuestas con conectivas lgicas (todas ellas son verdaderas en nuestro ejemplo de modelo bajo la interpretacin considerada anteriormente): Brother(LeftLeg(Richard),John) Brother(Richard,John) Brother(John,Richard) King(Richard) King(John) King(Richard) King(John)
-
6.3 Semntica (Ejemplo)
Todos los reyes son personas: x King(x) Person(x) (correcto)
x King(x) Person(x) (error!)
El significado de la segunda expresin es:
Todos los objetos son reyes y personas
-
6.3 Semntica (Ejemplo)
El rey Juan tiene una corona sobre su cabeza : x Crown(x) OnHead(x,John) (correcto)
x Crown(x) OnHead(x,John) (error!)
El significado de la segunda expresin es:
Existe un objeto que o no es una corona o est sobre la cabeza del rey Juan