Story Transcript
Lógica de Predicados En las últimas décadas, ha aumentado considerablemente el interés de la informática por la aplicación de la lógica a la programación. De hecho, ha aparecido un nuevo paradigma de programación, la programación declarativa, cuyos fundamentos teóricos se basan en los desarrollos de la lógica de predicados que pretendían alcanzar sistemas de demostración automática de teoremas. El instrumento fundamental de comunicación humana es el lenguaje, formado por frases de tipo interrogativo, imperativo y declarativo. Estas últimas constituyen el elemento básico de descripción de conocimiento. La lógica de predicados estudia frases declarativas con mayor grado de detalle, considerando la estructura interna de las proposiciones. Se toma como elemento básico los objetos y las relaciones entre dichos objetos. Es decir, se distingue: -Que se afirma (predicado o relación) -De quién se afirma (objeto) Definición 1. El alfabeto de la lógica de predicados esta formado por los siguientes conjuntos de símbolos:
Conjunto de símbolos de Variables (Var): esta formado por las últimas letras del alfabeto minúsculas. También se utilizan subíndices, por ejemplo: x, y, z, z1, y1, xn, yn Var .
Conjunto de símbolos constantes (Cons): primeras letras del alfabeto minúsculas (con subíndices), por ejemplo a, b, c, a1, b1, an, bn Cons.
Conjunto de letras de función (func): Esta formado por las letras f, g, h, también se pueden incluir subíndices para diferenciar distintas funciones f1, g1, h1, fn, gn Func.
En algunos casos se indica la aridad mediante superíndice. Así por ejemplo f 2 Func será una función con dos argumentos.
Conjunto de letras de predicados (Pred): Se representan mediante letras mayúsculas, P, Q, R Pred
Como en el caso de las funciones, se puede representar la aridad mediante un superíndice, por ejemplo: P3 Pred será un predicado con tres argumentos.
La aridad de una función o de un predicado se define como el numero de argumentos que tiene.
Símbolos de conectivas: ┐ Negación Conectiva y Conectiva o Implicación Doble implicación o equivalencia, si y solo si. Cuantificadores: Cuantificador universal Cuantificador existencial Signos de puntuación: Paréntesis ( ) y coma. 1
Definición 2. Un término es una cadena de símbolos utilizada para representar objetos siguiendo las siguientes reglas: - Toda variable o constante individual es un término. -
Si t1, t2, tn son términos y fn es una función de aridad n entonces fn(t1, t2, tn) es un término.
-
Todos los términos posibles se generan aplicando únicamente las dos reglas anteriores.
Definición 3. Un átomo es una cadena de símbolos de la forma: Pn(t1, t2, ,tn) Donde Pn es un predicado de aridad n y t1, t2, …, tn son términos. Definición 4. Dado un alfabeto de lógica de predicados, se puede definir el conjunto de formulas bien formadas (fbf) cuyos elementos siguen las reglas:
Todo átomo es una fórmula bien formada ( se denomina formula atómica)
Si A y B son formulas bien formadas entonces: (A) (B) ┐A ┐B A B A B A B A B
son fórmulas bien formadas
Si A es una formula bien formada y x una variable entonces x(A) y x(A) serán fórmulas bien formadas.
Ejemplo: la frase “Todos los estudiantes de informática son listos” podría formalizarse empleando los predicados: I(x) = “x estudia informática” y L(x)= “x es listo” como:
Definición 5. En una expresión del tipo xA, xA, la variable x es conocida como variable de cuantificación, a la fórmula A como ámbito o recorrido de la cuantificación. Definición 6. En una formula bien formada A, una variable está ligada si está en el ámbito de un cuantificador que la tiene como variable de cuantificación. Una variable está libre si no está ligada. Ejemplo: en la expresión
x P(x, f(x, y) ámbito
La variable x aparece en el ámbito del cuantificador universal que además la tiene como variable de cuantificación, por tanto, la variable x está ligada. 2
La variable y también está en el ámbito del cuantificador universal, pero éste no la tiene como variable de cuantificación, por lo tanto, es una variable libre. Definición 7. Se dice que una fórmula bien formada es una fórmula cerrada si todas sus variables están ligadas. Con las definiciones anteriores podrían aparecer problemas si una variable aparece cuantificada dos veces. Por ejemplo, en la fórmula x (P(x) xQ(x)), la x está sometida a dos cuantificadores. Para evitar confusiones. En la definición de fórmula bien formada, se establece una restricción en el tercer punto quedaría: “Si A es una fbf y x una variable libre en A entonces xA y xA serán fórmulas bien formadas” Se denomina lógica de predicados de orden Cero a la lógica de predicados en la que se trabaja con predicados de aridad cero (serán proposiciones Verdaderas o Falsas, de ahí que también se le conozca como lógica de proposiciones o enunciados). Puesto que no se utilizan constantes, variables, funciones ni cuantificadores su estudio es sencillo. Sin embargo, existen estructuras deductivas que la lógica de proposiciones no puede formalizar de forma adecuada, por ejemplo: “Todos los informáticos son listos, Juan es informático, luego Juan es listo” En la lógica de predicados de Primer Orden se permite la cuantificación de variables. De esa forma, el razonamiento anterior se formalizaría: (x(Informático (x) Listo(x) ) Informático(Juan)) listo (Juan) En este caso, si se puede comprobar la validez de esa fórmula, sin embargo se impone la limitación de no poder cuantificar mas que variables, con lo cual existe un amplio conjunto de fases que se quedan fuera del ámbito de la lógica de primer orden. Ejemplo 1: La frase “Algunas relaciones entre pares de alumnos de la clase son simétricas” se formalizaría: Rx y (R(x, y) R(y, x)) Ejemplo 2: Una frase de la fórmula “Existe una función f tal que para cualquier x existe una y de forma que f(x)=y” se debería formalizar incluyendo un cuantificador existencial sobre las funciones: fxy= (f(x)=y) En los ejemplos anteriores aparecen fórmulas con cuantificadores aplicados a variables de predicado y función, suponiendo la existencia de dominios predicados y de funciones. La lógica que permite ese tipo de cuantificación se conoce como lógica de predicados de segundo orden.
3
Interpretación: Es un mecanismo que permitirá asignar un valor verdadero (v) o falso (f) a una formula. Para ello es necesario dar un significado a cada uno de los símbolos que aparecen en la fórmula. Las conectivas y los cuantificadores tienen un significado fijo, mientras que el significado de las constantes, símbolos de función y símbolos de predicado puede variar.
En una interpretación, se define un dominio de discurso sobre el cual varían las variables, se asignan valores a las constantes y se definen los símbolos de función y de predicados de forma particular. Se necesita, por tanto, asignar un valor concreto a cada símbolo de la fórmula en un dominio determinado. Definición 8. Una interpretación de una fórmula F consiste es: - Un conjunto no vacío D, llamado Dominio de la interpretación -
Asociar a cada letra de constante c f un elemento del dominio c’ D.
-
Asignar a cada letra de función f de aridad n una aplicación fI de la forma DxDx…xDD.
-
Asignar a cada letra de predicado P de aridad n una aplicación P’ de la forma DxDx…xD v,f.
Definición 9. Una interpretación I de una fórmula F es un modelo para F si VI(F)=V. Definición 10. Una fórmula F es válida si y solo si toda interpretación I es un modelo de F. Definición 11. Una fórmula F es satisfacible si existe alguna interpretación I que sea un modelo de F. Definición 12. Una fórmula F es insatisfacible o contradicción si no existe una interpretación I que sea un modelo de F.
Todas las fórmulas
Satisfacibles Insatisfacibles Válidas
4
Ejercicio: Dada la fórmula F=xy (P(x,y) Q(f(x))) Q(g(a, b, f(y))), una interpretación I para la fórmula sería: Dominio: D=1, 2, 3 Constantes: a=1, b=3 Funciones: f(x)= 4-x g(x, y, z)= [(x+y+z)MOD 3]+1 Predicados: P(x, y)= “xy” Q(x)=”x=2 OR x=3” Para calcular el valor de la fórmula para esa interpretación se chequeará si para todo x existe un y que cumpla ( P(x,y) Q(f(x))) Q(g(a, b, f(y))). Se comienza por x=1: a) Se busca un y, escogiendo, por ejemplo, y=1. Se evalúa la fórmula y el valor que se obtiene es F(falso). x=1, y=1, a=1 y b=3
se sustituyen estos valores en la fórmula (P(x,y) Q(f(x))) Q(g(a, b, f(y))) ( P(1,1) Q(f(1))) Q(g(1, 3, f(1))) Se calcula la función f con x=1 f(x)= 4-x; f(1) = 4-1 da como resultado 3.
Se calcula el predicado P(x, y)= “xy”
P(1,1)= “11” el resultado es verdadero V.
En la formula se sustituyen los valores obtenidos: ( v Q(3)) Q(g(1, 3, 3)) Ahora se calcula la función g y el predicado Q. g(x, y, z)= [(x+y+z)MOD 3]+1 g(1, 3, 3)= [(1+3+3)MOD 3]+1
Q(x)=”x=2 OR x=3” Q(3)=”x=2 OR x=3” =verdadero v
[7 MOD 3]+1 = 1+1 = 2 Se sustituyen los resultados: ( v v) Q(2) Para el predicado Q(2)= el resultado es v verdadero, pero como esta negado el predicado entonces es Falso. Resolviendo el paréntesis (v v) = v Quedaría: vf su resultado es F falso. Puesto que para y=1 es resultado es falso, no se cumple, entonces se busca un nuevo valor de y. Para y=2 se tiene: x=1, y=2, a=1 y b=3 (P(1,2) Q(f(1))) Q(g(1, 3, f(3))) El resultado da verdadero v. (modelo) Como ya en encontró un valor de y donde la formula da verdadero, se continua con el siguiente valor del dominio. 5
Para x=2, y=1, a=1 y b=3 Sustituyendo valores, en la formula el resultado es Verdadero. (Modelo) Como el valor era verdadero entonces se continúa con el siguiente valor del dominio. Para x=3, y=1, a=1 y b=3 Sustituyendo valores, en la formula el resultado es Verdadero. (Modelo) Ya se checo todo el dominio, por lo tanto se concluye que: La fórmula es satisfacible para ese dominio.
6