Source: http://docplayer.es/1549210-Logica-de-predicados-de-primer-orden.html
Timestamp: 2018-05-25 00:12:44+00:00

Document:
Lógica de Predicados de Primer Orden - PDF
Download "Lógica de Predicados de Primer Orden"
Valentín Venegas Salazar
1 Lógica de Predicados de Primer Orden La lógica proposicional puede ser no apropiada para expresar ciertos tipos de conocimiento. Por ejemplo: Algunas manzanas son rojas Esta afirmación no se refiere específicamente a ningún conjunto de manzanas, solo está diciendo que existe un conjunto de manzanas que son rojas. cómo podríamos representar esta afirmación en LP? La LP también puede puede ser no apropiada para modelar cierto tipo de razonamiento. Veamos el siguiente razonamiento correcto: Juan ayuda a todas las personas que gustan de la lógica. A Juan es persona y le gusta la lógica. Juan ayuda a Juan Jorge Baier Aranda, PUC << Atrás 111
2 En estos ejemplos hemos visto que la LP no permite referirse en forma sencilla a todos los elementos de un dominio. Más aún, si los elementos del dominio son infinitos, simplemente no puede expresar conocimiento acerca de todos los individuos. La LP tampoco es capaz de representar propiedades de objetos, solo proposiciones. La lógica de primer orden (LPO) soluciona estos problemas en este sentido: Permite hacer cuantificación sobre los objetos de un dominio. Ej: Todos los perros son animales, Algunos sapos lloran. Permite representar propiedades a través de relaciones y funciones. Un lenguaje L de la lógica de predicados esta compuesto por los siguientes elementos: Un conjunto C, finito o enumerable, de constantes para designar objetos. Ej: {C 1, C 2,..., C n,...}, Jorge Baier Aranda, PUC << Atrás 112
3 Para evitar confusiones, usaremos siempre mayúsculas para denotar los símbolos constantes. Un conjunto F, de símbolos de función. Ejemplo: {f, g, h,...}. A cada función se le asocia una aridad, que es un número natural y que corresponde a la cantidad de argumentos de la función. Un conjunto P finito o infinito enumerable de símbolos para predicados {P, Q, R, S,...}, que se utilizan para designar propiedades de objetos. A éstos también se les asocia una aridad positiva. Los tres conjuntos anteriores, se agrupan normalmente en un solo conjunto de símbolos S = P, F, C. En el que se ubican primero los predicados, luego las funciones y finalmente las constantes. En nuestro ejemplo, S = P, Q, R, S,..., f, g, h,..., C 1, C 2,... Jorge Baier Aranda, PUC << Atrás 113
4 Además de estos elementos un lenguaje de primer está compuesto de fórmulas que pueden contener los siguientes elementos: 1.,,,, : conectivos lógicos usuales. 2. =: un predicado especial para la igualdad. 3., : cuantificadores existencial y universal. 4. x 1, x 2,...: conjunto enumerable de variables, el cual informalmente podríamos llamar por x, z, u, etc. 5. (,,, ): símbolos de puntuación. Aún nos falta definir cómo se forman exactamente las fórmulas. Veamos ahora un pequeño adelanto: Sea S = A, GL, padre, Maria, P edro, Andres, Juan. símbolos, donde Un conjunto de GL, de aridad 1 tal que GL(x) es verdadero ssi a x le gusta la lógica. A, de aridad 2 es tal que A(x, y) es verdadero exactamente cuando x ayuda a y. Además, la función padre(x) representa al padre del objeto x. Jorge Baier Aranda, PUC << Atrás 114
5 Qué creen que expresan las siguientes fórmulas? y(gl(y) A(Juan, y)) xa(x, Juan) GL(Juan) y(a(juan, y) x(a(x, y))) y, z(a(juan, y) z = padre(y) x(a(z, x))) Aparte de especificar cómo se escriben las fórmulas debemos darle una semántica. Notemos que los lenguajes de primer orden hablan de objetos, propiedades y funciones. Estos elementos del lenguaje deben tener una contra parte, en cierto dominio real (dominio de discurso). Es posible usar el meta-lenguaje matemático para describir el dominio de discurso a través de estructuras. Veremos esto más adelante... Jorge Baier Aranda, PUC << Atrás 115
6 Sintaxis de LPOP Ahora definiremos formalmente la sintaxis de LPOP. Partiremos con la definición de qué es un término. Definición 14. Sea L un lenguaje de primer orden construido a partir de un conjunto S de símbolos. Un término se forma a partir de la aplicación sucesiva de las siguientes reglas. 1. Toda constante de S es un término. 2. Toda variable es un término. 3. Si f es una función de aridad n (f S) y t 1, t 2,..., t n son términos entonces f(t 1, t 2,..., t n ) es un término. En nuestro ejemplo anterior, los siguientes son términos x 1, y, Juan, padre(padre(juan)) Usando esto como base podemos definir una fórmula Jorge Baier Aranda, PUC << Atrás 116
7 Definición 15. Una fórmula se obtiene, solamente, mediante una aplicación finita de las siguientes reglas: 1. Si t 1 y t 2 son términos, entonces t 1 = t 2 es una fórmula. 2. Si P es un símbolo de predicado n-ario y t 1,..., t n son términos, entonces P (t 1, t 2,..., t n ) es una fórmula. 3. Si ϕ y ψ son fórmulas, entonces ϕ y (ϕ ψ) son fórmulas ( es un conectivo binario). 4. Si φ es una fórmula y x es una variable, entonces xφ y xφ también son fórmulas. El lenguaje de primer orden de todas las fórmulas que se generan a partir de un conjunto de símbolos S se anota como L(S). Continuando con nuestro ejemplo, las siguientes son fórmulas del lenguaje: x(a(x, z) A(x, padre(u))), x ya(x, y), (*) x(a(y, Juan) y(gl(y) A(y, x))), ya(x, y). (**) Jorge Baier Aranda, PUC << Atrás 117
8 La fórmula (*) se acostumbra a escribir como xya(x, y) En la fórmula (**) la variable x no está afectada por ningún cuantificador. En este caso decimos que x es una variable libre. Además, las relaciones binarias también se pueden anotar con notación infija. De esta manera A(x, y) se escribe como xay. Definición 16. Una fórmula del lenguaje ϕ es una oración. Si no tiene variables libres. Jorge Baier Aranda, PUC << Atrás 118
9 Otro Ejemplo de LPOP Supongamos el siguiente conjunto de símbolos S = <, >, s, +, 0, 1, Podemos escribir el siguiente conjunto de fórmulas: x 0 < s(x) xyz((x < y y < z) x < y) x x + 1 = s(x) xy s(x) + y = x + s(y) x x + 0 = x De qué dominio real están hablando estas fórmulas? Si pensamos que estas fórmulas están hablando acerca de los naturales y que s(x) representa al sucesor del natural x, entonces, estas fórmulas están describiendo propiedades de la desigualdad y de la suma. Jorge Baier Aranda, PUC << Atrás 119
10 Estructuras El dominio de discurso lo describiremos como una estructura. Una estructura es un conjunto formado por: Un conjunto A no vacío de objetos. Si estamos hablando de los naturales, este conjunto es N Un conjunto R A de relaciones. Una relación R A sobre A es n-aria si R A A n. Estas son las relaciones que cumplen los elementos del dominio. En el caso de los naturales, podríamos escoger la relación < N N N o la relación primo N N Un conjunto F A de funciones. Una función n-aria f A recibe elementos del dominio y retorna un elemento del dominio, es decir f A : A n A. En el caso de los naturales, podríamos escoger la multiplicación ( N) y la suma (+ N ) Un conjunto de constantes distinguidas. C A puede denotar una constante en el conjunto A. Obviamente, C A A. En el caso de los naturales podríamos elegir a 0 N y a 1 N. Jorge Baier Aranda, PUC << Atrás 120
11 Definición 17. Una estructura se anota formalmente como una tupla E = A, R A,..., f A,..., C A,..., en la cual A es un conjunto y R A, f A y C A son, respectivamente, una relación, una función y una constante sobre A con las características descritas anteriormente. Jorge Baier Aranda, PUC << Atrás 121
12 Por ejemplo, una estructura sobre los naturales puede ser la siguiente: N = N, < N, primo N, + N, N, 0 N, 1 N Si un lenguaje L de primer orden habla acerca de cierta estructura, entonces el conjunto de símbolos S utilizados por el lenguaje debe ser compatible con los elementos de la estructura. Por ejemplo, el conjunto de símbolos es compatible con la estructura S = R,..., f,..., C E = A, R A,..., f A,..., C A cuando hay una correspondencia exacta entre los elementos y sus símbolos (incluyendo las aridades). En este caso decimos que Jorge Baier Aranda, PUC << Atrás 122
13 R es interpretado por R A f es interpretado por f A, y C es interpretado por C A. Los siguientes son ejemplos de estructuras compatibles: S = <, primo, +,, 0, 1 y N 1 = N, < N, primo N, + N, N, 0 N, 1 N S = <, primo, +,, {0, 1} y N 2 = N, < N, impar N, + N, N, 1 N, 0 N Nótese que en el segundo ejemplo no existe una correspondencia natural entre los símbolos utilizados y las propiedades que representan. Este fenómeno siempre ocurre en lógica simbólica. Siempre debemos recordar que los símbolos son solamente símbolos. Bajo este esquema en el cual la realidad es representada mediante símbolos nos preocupa ahora saber cuándo una fórmula es verdadera. Por ejemplo, qué significa la siguiente fórmula x (primo(x) primo(x + 2)) Jorge Baier Aranda, PUC << Atrás 123
14 cuando la interpretamos con N 1? qué significa cuando la interpretamos con N 2? bajo qué interpretación esta fórmula es verdadera? es N 2 la única estructura que hace a la fórmula verdadera? podemos escribir un conjunto de fórmulas que sea hecho verdadero sólo por un a interpretación dada por la estructura N 2 y por ninguna otra? Si queremos usar la lógica de primer orden para razonar acerca de lo que ocurre en el mundo, deberemos ser capaces de describir lógicamente el mundo sin que exista la posibilidad a que las teorías sean verdaderas en estructuras que no tienen nada que ver con el mundo que estamos modelando. Más adelante veremos que esto puede ser no trivial... De lo que sí debiéramos estar seguros es que para ser capaces de modelar dominios en forma lógica deberemos entender claramente cuándo una fórmula es verdadera en una cierta estructura. Antes de esto, refinaremos nuestro concepto de interpretación. Jorge Baier Aranda, PUC << Atrás 124
15 Interpretación de Términos Hasta el momento, tenemos una idea más o menos clara de cómo se interpretan las relaciones y funciones. La pregunta es cómo interpretamos un término? Debemos dar una respuesta para los tres tipos de términos: constantes, variables, f(t 1, t 2,..., t n ), donde t 1,..., t n son términos. Al menos para el caso de las constantes debería ser bastante claro... Sin embargo, necesitamos dar una interpretación a las variables. variable, qué objeto del dominio le corresponde? Si x es una Necesitamos una función de asignación, que asigne valores a las variables. Jorge Baier Aranda, PUC << Atrás 125
16 Sea S = { R,..., f,..., C,... } un conjunto de símbolos. Si llamamos V ar(l(s)) al conjunto de variables de un lenguaje de primer orden, entonces β es una función de asignación tal que β : V ar(l(s)) A. Formalmente, sea un conjunto de símbolos y S = R,..., f,..., C,... E = A, R A,..., f A,..., C A una estructura compatible y β una función de asignación, entonces una interpretación es un par I = E, β, definida por: 1. I(C) := C A. 2. I(x) := β(x), con x V ar(l(s)). 3. I(f(t 1,..., t n )) := f A (I(t 1 ),..., I(t n )), con x V ar(l(s)). Jorge Baier Aranda, PUC << Atrás 126
17 Valor de Verdad de Fórmulas Tal como en el caso proposicional, nos interesa saber cuándo una fórmula es verdadera. En LP, definimos cuando una fórmula era verdadera dada una asignación de valor de verdad para cada una de las variables proposicionales del lenguaje. Es decir, definimos cuándo σ = ϕ. En lógica de primer orden no hay valuaciones, sino interpretaciones, por lo tanto nos preocupamos de definir cuándo una fórmula es verdadera bajo una interpretación: I = ϕ (ϕ L(S)). Deberemos definir esto en forma inductiva para todas las fórmulas posibles del lenguaje. Definición 18. Sea L(S) un lenguaje de primer orden y ϕ L(S). Entonces: Jorge Baier Aranda, PUC << Atrás 127
18 1. Si ϕ es de la forma t = s entonces I = ϕ ssi I(t) = I(s) 2. Si ϕ es de la forma R(t 1,..., t n ) entonces I = ϕ ssi (I(t 1 ),..., I(t n )) R A 3. Si ϕ es de la forma ψ entonces I = ϕ ssi no se cumple que I = ψ 4. Si ϕ es de la forma ψ χ entonces I = ϕ ssi I = ψ y I = χ 5. Si ϕ es de la forma ψ χ entonces I = ϕ ssi I = ψ o I = χ Jorge Baier Aranda, PUC << Atrás 128
19 6. Si ϕ es de la forma ψ χ entonces 7. Si ϕ es de la forma ψ χ entonces 8. Si ϕ es de la forma x ψ entonces I = ϕ ssi I = χ o no se cumple que I = ψ I = ϕ ssi I = ψ exactamente cuando I = χ I = ϕ ssi I x a = ψ con a A Aquí, la notación I x a implica reemplazar la asignación de valor de x por el objeto a en la función de asignación β. 9. Si ϕ es de la forma x ψ entonces I = ϕ ssi I x a = ψ para todo a A Definición 19. Una fórmula ϕ de L(S) es satisfacible si existe una interpretación I = E, β tal que I = ϕ Jorge Baier Aranda, PUC << Atrás 129
20 Definición 20. Una fórmula ϕ de L(S) es válida en la estructura E (compatible con S) si ésta es hecha verdadera bajo cualquier asignación β. E = ϕ ssi E, β = ϕ para todo β Definición 21. Sea I una interpretación que hace verdadera a una fórmula ϕ L(P ). Entonces se dice que I es un modelo para esta fórmula. Definición 22. Sea Σ un conjunto de fórmulas en un lenguaje de primer orden L(S), decimos que I = Σ ssi I = ϕ para todo ϕ Σ Definición 23. [Consecuencia Lógica] Sea Σ un conjunto de oraciones en L(S) y ϕ es una oración en L(S). Entonces ϕ es consecuencia lógica de Σ ssi, I = Σ entonces I = ϕ Jorge Baier Aranda, PUC << Atrás 130
21 Otro Ejemplo Supongamos las siguientes situaciones en el dominio de los bloques: C B A D Podríamos usar la estructura B = U, {Sobre U }, {A, B, C, D, M} para modelar este dominio, donde: U = {A, B, C, D, M}. Sobre U = {(A, M), (B, A), (C, B), (D, M)} La interpretación I = B, β, para un β arbitrario es modelo del siguiente conjunto de fórmulas sobre S = {{Sobre}, {B A, B B, B C, B D, M}} Jorge Baier Aranda, PUC << Atrás 131
22 x (Sobre(x, M) x = B A x = B D ) Sobre(B B, B A ) Sobre(B C, B B ) Si consideramos, ahora, una relación binaria extra ArribaDe, tal que ArribaDe(x, y) es verdadera si y sólo si el objeto x está arriba de y, y agregamos el siguiente axioma: xy (ArribaDe(x, y) Sobre(x, y) Sobre(x, z) ArribaDe(z, y)) La interpretación, adecuadamente modificada, seguiría siendo modelo de la teoría. Una pregunta natural a hacerse es: tiene esta teoría otro modelo? La respuesta es SÍ, y muchos más... Jorge Baier Aranda, PUC << Atrás 132
23 C B C Mostramos sólo dos de ellos: A D C B E A D Hay algún problema con la teoría? La respuesta a esta pregunta dependerá de qué es lo que queremos hacer con ella. Jorge Baier Aranda, PUC << Atrás 133
24 Si esta representa hechos válidos, entonces es suficiente. Si queremos hacer deducción o razonar acerca de los hechos que son verdaderos en este dominio o no, necesitamos una mejor teoría. Dicha teoría debe forzar a que todas los modelos de esta representen el mundo que se quiere representar. Un arreglo para esta teoría es el siguiente: x(sobre(x, M) x = B A x = B D ), x(sobre(x, B A ) x = B B ), x(sobre(x, B B ) x = B C ), x Sobre(x, B C ), x Sobre(x, B D ). Recordemos, además, que una interpretación podría asignar a un objeto del dominio dos símbolos de constante distintos del lenguaje. Por ejemplo, el objeto Jorge Baier Aranda, PUC << Atrás 134
25 A podría estar designado por B A y B B teniendo un modelo. al mismo tiempo y la teoría seguiría Esta distinción se hace agregando axiomas de nombres únicos. Los axiomas para este caso son varios. A continuación veremos algunos: M B A, M B B M B C, M B D, B A B B,B A B C, B A B D,... Lo que estamos logrando con esto es que cualquier modelo de la teoría tenga propiedades con la misma extensión para cada uno de sus predicados. Una condición suficiente para asegurar es que la teoría sea definicional, es decir, que defina por completo la extensión de los predicados. Esto se traduce en que para todo predicado n-ario P de la teoría exista un axioma que establece que x (P (x) ϕ), Jorge Baier Aranda, PUC << Atrás 135
26 donde ϕ es una fórmula que no tiene variables libres y x es una tupla de n variables. x(sobre(x, y) (y = M (x = B A x = B D )) (y = B A x = B B ) (y = B B x = B C )). y que hay axiomas de nombres únicos para objetos del dominio. Usando la semántica ya definida, podemos demostrar que la siguiente fórmula es consecuencia lógica de nuestra teoría. x Sobre(x, x) En efecto podemos demostrarlo por contradicción Supongamos que hay un objeto z tal que Sobre(z, z), del axioma de definición de Sobre se tiene que Jorge Baier Aranda, PUC << Atrás 136
27 (z = M (z = B A z = B D )) (z = B A z = B B ) (z = B B z = B C ) Que evidentemente contradice a los axiomas de nombres únicos, por lo que no puede existir tal z y luego x Sobre(x, x). La demostración que acabamos de hacer ha sido posible porque tenemos un conocimiento certero sobre los modelos de la teoría. Sería ideal que, tal como en el caso de LP, en LPOP tuviéramos un sistema formal deductivo, mediante el cual no requiramos evidencia expĺıcita de las estructuras que lo modelan. A continuación, veremos un sistema deductivo para lógica de primer orden. Jorge Baier Aranda, PUC << Atrás 137
28 Un sistema deductivo para Lógica de Primer Orden Al igual que en LP, en LPO existen fórmulas que son siempre verdaderas. A partir de estas fórmulas, podremos construir un sistema deductivo, con el cual se podrán derivar fórmulas correctas. Por ejemplo, las siguientes fórmulas son universalmente válidas: = P (x) (Q(x) P (x)), Esta fórmula es una instancia de una tautología de LP. En general, con cualquier instancia de tautología podremos obtener una fórmula universalmente. En particular, a partir del esquema de axiomas de Hilbert, podemos obtener: (P (x) (Q(y) R(z))) ((P (x) Q(y)) (P (x) R(z))) Sin embargo, instanciaciones de estos esquemas de axiomas no son suficientes para realizar todo el razonamiento de primer orden. Jorge Baier Aranda, PUC << Atrás 138
29 Veamos ahora algunas fórmulas universalmente válidas que involucran cuantificación: ( x P (x) P (C)), (P (y) x P (x)), ( y P (y) x P (x)), ( x P (x) x P (x)). Las siguientes fórmulas, sin embargo, no lo son: ( x P (x) x P (x)), x (P (x) P (C)), ( x P (x) y P (y)) Jorge Baier Aranda, PUC << Atrás 139
30 El sistema deductivo Un sistema deductivo de Hilbert para LPO consta de: Esquemas axiomáticos Reglas de deducción. Los esquemas axiomáticos para LPO son los de LP, más axiomas para la cuantificación universal 4 : 1. ϕ (ψ ϕ). 2. (ϕ (ψ χ)) ((ϕ ψ) (ϕ χ)) 3. ( ϕ ψ) (( ϕ ψ) ϕ). 4. xϕ(x) ϕ(t) 5. ϕ(t) xϕ(x) 6. xϕ(x) x ϕ(x). 4 Aquí t denota un término arbitrario, en particular puede ser una variable o una constante Jorge Baier Aranda, PUC << Atrás 140
31 Además, debemos agregar los siguientes axiomas para igualdad: x (x = x) x (x = y y = x) x (x = y y = z x = z) Para todo predicado n-ario P y función m-aria f 5 : xy P (x) x = y P (y), xy x = y f(x) = f(y). Las reglas de deducción son las siguientes: 1. Modus Ponens, igual que en LP 5 Aquí x representa a una tupla de variables. ϕ ψ, ϕ ψ Jorge Baier Aranda, PUC << Atrás 141
32 2. Regla de Generalización. Cuando y no aparece libre en ϕ ϕ ψ(y) ϕ x ψ(x) Nótese que ϕ puede ser una fórmula siempre válida, con lo que la regla de generalización: ψ(y) x ψ(x) es un caso particular de la anterior. Una demostración formal de una fórmula ϕ a partir de un conjunto de fórmulas Σ es una secuencia de fórmulas φ 1, φ 2,..., φ n donde φ n = ϕ y, para todo 1 i n, φ i Σ, o φ i es un axioma lógico, o φ i se obtiene de una regla de deducción a partir de fórmulas φ k y φ j (k < j < i) Cuando ϕ se obtiene de una demostración formal a partir de Σ, decimos que Σ ϕ. Jorge Baier Aranda, PUC << Atrás 142
33 Ejercicio: Demuestre que { x (P (x) Q(x)), x P (x)} x Q(x) 1. x (P (x) Q(x)) (de Σ) 2. (P (p) Q(p)). (esquema de axioma 4 en 1) 3. x P (x) (de Σ) 4. P (p). (esquema de axioma 4 en 3) 5. Q(p). (modus ponens entre 2 y 4) 6. x Q(x) (generalización de 5) Jorge Baier Aranda, PUC << Atrás 143
34 Propiedades del Sistema Deductivo Cabe preguntarnos ahora, qué propiedades tiene este sistema deductivo. Veremos que, afortunadamente, muchas de las propiedades que se tenían en LP, también se cumplen en LPO. Teorema 2. [de Corrección] Sea Σ un conjunto de oraciones y ϕ una oración, entonces si Σ ϕ entonces Σ = ϕ La demostración de este teorema es idéntica a la de LP, puesto que los esquemas de axiomas y reglas de deducción siempre preservan la verdad. Teorema 3. [de Compleción de Gödel] Sea Σ un conjunto de oraciones y ϕ una oración, entonces si Σ = ϕ entonces Σ ϕ Teorema 4. [de Compacidad o Finitud] Sea Σ es un conjunto de oraciones y Jorge Baier Aranda, PUC << Atrás 144
35 ϕ es una oración, entonces Σ es satisfacible ssi todo subconjunto finito de Σ lo es Jorge Baier Aranda, PUC << Atrás 145
36 Fórmulas Prenex Es una forma normal de fórmulas de primer orden. Una fórmula prenex sólo tiene cuantificadores al comienzo de ésta. Por ejemplo: es una fórmula prenex. xy z (P (x, y) R(x, y, z)) Formalmente, una fórmula prenex se escribe como Q 1 x 1 Q 2 x 2... Q n x n Ψ, donde Q i (1 i n) representa algún cuantificador ( o ) y donde Ψ no tiene cuantificadores. Teorema 5. Sea ϕ una fórmula arbitraria de L(S). Entonces existe una fórmula prenex ψ equivalente. Jorge Baier Aranda, PUC << Atrás 146
37 Antes de demostrar este teorema, veamos algunos ejemplos: la fórmula es equivalente a y equivalente a x (P (x) y Q(x, y)) x y (P (x) Q(x, y)) P (x) y R(y) y (P (x) R(y)) cómo podemos hacer esto en general? Jorge Baier Aranda, PUC << Atrás 147
38 Es posible demostrar que si ϕ y ψ son fórmulas y x es una variable que no aparece en ψ o está cuantificada en ψ, entonces las siguientes fórmulas son equivalentes: 1. Qx ϕ y Qx ϕ 2. (Qx ϕ) ψ y Qx (ϕ ψ) 3. ψ (Qx ϕ) y Qx (ψ ϕ) donde Q representa a algún cuantificador ( o ), Q representa al cuantificador complementario 6 representado por Q y representa a o. Qué pasa si ψ tiene a x como una variable libre? fórmula equivalente a: Ejemplo: Encuentre una x P (x) y Q(y, z) P (x, y) en este caso no podemos aplicar directamente la transformación, deberemos renombrar la variable libre x y luego aplicar la regla. 6 El cuantificador complementario de es y vice versa. Jorge Baier Aranda, PUC << Atrás 148
39 Renombrando x por u e y por v obtenemos: y luego x(p (x) y Q(y, z) P (u, v)) que es equivalente a x( y (P (x) Q(y, z) P (u, v))) x y (P (x) Q(y, z) P (u, v)) El teorema se demuestra justificando que la aplicación de las transformaciones de arriba son suficientes para llevar cualquier fórmula a forma normal prenex. Jorge Baier Aranda, PUC << Atrás 149
40 Resolución de Primer Orden Tal como en LP, nos interesa encontrar un algoritmo implementable que permita hacer demostraciones de teoremas de primer orden en forma automática. En 1965, J.A. Robinson descubrió un método de resolución para primer orden. El método es bastante parecido al de resolución de LP. Jorge Baier Aranda, PUC << Atrás 150
41 Supongamos que tenemos las siguientes dos cláusulas de primer orden: P (x) Q(y, z) R(x, f(w)) y la cláusula S(y) P (u) Observemos que: Las variables en ambas cláusulas aparecen como libres. Buscamos encontrar una correspondencia entre resolución y consecuencia lógica por lo cual supondremos que todas las fórmulas están impĺıcitamente cuantificadas universalmente (no queremos variables libres). Dado que la primera fórmula se cumple para todo x, podríamos inferir que, en particular, se cumple para un objeto cualquiera C. Si lo mismo decimos acerca de la segunda cláusula tendremos que, se cumple que P (C) Q(y, z) R(C, f(w)) y la cláusula S(y) P (C) Jorge Baier Aranda, PUC << Atrás 151
42 Dada tal sustitución, podemos utilizar la regla de resolución que ya conocemos y generar la siguiente cláusula: Por qué? S(y) Q(y, z) R(C, f(w)) El proceso de asignar un valor a una variable, reemplazándola en toda la forma se llama sustitución. Si θ = {x/b, y/f(a)} y ϕ es una fórmula, entonces ϕθ corresponde a la misma fórmula con todas las ocurrencias de x reemplazadas por b y todas las ocurrencias de y reemplazadas por f(a). Formalmente, una sustitución es una función parcialmente definida θ : V ar T (S), donde T (S) es el conjunto de términos de un conjunto de símbolos S. Una sustitución que hace que dos fórmulas atómicas se hagan iguales se conoce como unificador. Ejemplo: Jorge Baier Aranda, PUC << Atrás 152
43 La sustitución θ = {x/f(a), y/g(u), z/a} es un unificador para los literales 7 : porque L 1 θ L 2 θ. L 1 R(x, g(u)) L 1 R(f(z), y) El sentido de igualdad ( ) usado aquí es meramente sintáctico y quiere decir que las expresiones son iguales caracter a caracter. Si θ es unificador, se usa para expresar el conjunto {E 1, E 2,..., E n }θ {E 1 θ, E 2 θ,..., E n θ} Dos literales que unifican, pueden ser hechos unificar por muchas sustituciones. En nuestro ejemplo anterior, todas las siguientes sustituciones son unificadores 7 Tal como en LP, un literal es una fórmula atómica o la negación de una. Jorge Baier Aranda, PUC << Atrás 153
44 de L 1 y L 2 : θ 1 = {x/f(a), y/g(u), z/a} θ 2 = {x/f(z), y/g(u)} θ 3 = {x/f(f(b)), y/g(a), z/f(b), u/a} De todos los unificadores posibles siempre existe al menos uno que es el menos restrictivo, en el sentido que es el que menos restringe futuras unificaciones. Este tipo de unificador se conoce como unificador más general (UMG). Un UMG asigna la menor cantidad de sustituciones posibles. Formalmente, un UMG θ de el conjunto de expresiones E es tal que cualquier otro unificador θ de E se puede obtener primero mediante la aplicación de θ y después de alguna otra sustitución τ. Es decir, Eθ = Eθτ Jorge Baier Aranda, PUC << Atrás 154
45 En nuestro ejemplo, θ 2 es el unificador más general. De hecho, si E = {R(x, g(u)), R(f(z), y)}, Eθ 1 = (Eθ 2 ){z/a} Eθ 3 = (Eθ 2 ){z/f(b), u/a} Ahora estamos listos para formalizar una regla de resolución: Sean l 1 l 2... l n y l 1 l 2... l m cláusulas de primer orden. La regla de resolución es aplicable si existen l i (1 i n) y l k (1 k m) tales que l iθ y l k θ son uno la negación del otro (literales complementarios). En este caso, la regla de resolución es la siguiente: l 1 l 2... l n l 1 l 2... l m i {1,...,n} {j} l iθ i {1,...,m} {k} l i θ Hasta el momento, tenemos un método de resolución sirve para fórmulas de primer orden cuantificadas universalmente. Jorge Baier Aranda, PUC << Atrás 155
46 qué podemos hacer cuando queremos demostrar un hecho a partir de un conjunto de formulas con cuantificadores existenciales? La respuesta está en transformar una fórmula con cuantificadores varios a una que sólo tenga cuantificadores universales. Esto se puede hacer mediante skolemización. Jorge Baier Aranda, PUC << Atrás 156
47 Skolemización La skolemización (por Toraf Skolem) tiene por objeto transformar una fórmula a otra equivalente en forma normal prenex. Consideremos la siguiente fórmula: x P (x) Siempre podremos reemplazar la fórmula anterior por donde C es una constante. P (C), Pero, cómo podemos transformar x y R(x, y)?. x R(x, C) por qué? Claramente, no nos sirve Sea ϕ una fórmula prenex, tal que x 1... x k x ϕ Jorge Baier Aranda, PUC << Atrás 157
48 es una oración. La transformación de skolem le asocia a esta fórmula: x 1... x k ϕ(x/f(x 1,..., x k )) donde ϕ(x/f(x 1,..., x k )) corresponde a la sustitución de x por f(x 1,..., x k ) en ϕ. f se conoce como una constante de Skolem, y es una constante nueva, que no debe tener ocurrencias en ϕ. Para la regla anterior, en caso que k = 0, se obtiene la fórmula x ϕ la que se reemplaza por ϕ(x/c) donde C es una constante nueva. Ejemplos: 1. x y z S(x, y, z) se transforma en x y S(x, y, f(x, y)). Jorge Baier Aranda, PUC << Atrás 158
49 2. se transforma en x y z u (P (x, y) Q(y, z) R(u)) x z (P (x, f(x)) Q(f(x), z) R(g(x, z))) Teorema 6. Sea Σ L(S) un conjunto de oraciones en forma normal prenex y sea Σ un conjunto formado a partir de sucesivas aplicaciones de la transformación de Skolem. Entonces Σ tiene un modelo si y solo si Σ también lo tiene. La demostración del teorema pasa por demostrar que x 1... x k x ϕ x 1... x k ϕ(x/f(x 1,..., x k )) Jorge Baier Aranda, PUC << Atrás 159
UBA Facultad de Ciencias Económicas Lógica Algunos conceptos sobre Prolog
UBA Facultad de Ciencias Económicas Lógica Algunos conceptos sobre Prolog Autor: Carlos Lombardi carlombardi@gmail.com Índice Algunos conceptos sobre Prolog... 1 Índice... 1 Capítulo 1 Lógica para sistemas...

References: Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución