Logica e predicados PDF

Preview

Summary

Download Logica e predicados PDF

Description

LOGICA DE PREDICADOS SINTAXIS. SEMANTICA.REPRESENTACIÓN Los enunciados sobre el mundo que en Lógica de Proposiciones eran tan monolíticos como p o q ahora en Lógica de Predicados tienen estructura interna, como en Px o en Ray: un predicado que enuncia algo sobre uno o más términos. Se incorporan además al lenguaje dos cuantificadores ('para todo' y 'existe'), que permiten declarar de golpe propiedades que cumplen los estados de nuestro sistema, no importa cuántos sean (o incluso si hay un número infinito de ellos). Este bloque (Lenguaje de la Lógica de Predicados) presenta la sintaxis de este lenguaje, su semántica y ejemplos de uso del lenguaje. Sintaxis y semántica. El lengua de la lógica de Predicados La sintaxis de la Lógica de Predicados se basa en fórmulas atómicas compuestas cada una de un predicado que afirma algo sobre 'unos sujetos' (sus términos). Para precisar 'estos sujetos' (cada término) se pueden utilizar constantes, variables o funciones. Estas fórmulas atómicas se pueden componer en fórmulas más complejas (mediante conectivas) y/o se les puede anteponer un cuantificador. Esta sección presenta la sintaxis y la semántica de la Lógica de Predicados en tres etapas: 

Predicados sólo con constantes en sus términos



Predicados que además pueden usar variables en sus términos (y ser objeto de cuantificación)



Predicados que además pueden usar funciones en sus términos. Y la presentación de una relación especial entre términos: la identidad.

Predicados sólo con constantes en los términos Predicados monádicos con constantes en los términos En lógica proposicional tenemos las proposiciones, mientras en predicados, nos aporta estructura, información sobre un elemento. Necesitamos ampliar nuestro vocabulario, como proposiciones  añadimos propiedades y el elemento, sujeto o término del que es la propiedad (Pa, P siendo la propiedad y a el elemento o sujeto).

A efectos sintácticos, los árboles quedarían de otra manera, donde estaría el fin, la proposiciones se enuncia la propiedad y al término al que se refiere.

En Lógica de Predicados, las fórmulas atómicas tienen estructura interna. Cada una de ellas se compone de un predicado y de sus términos correspondientes: Pt1…tn. Intuitivamente, un predicado afirma algo sobre sus términos. Y la declaración de cada predicado afecta siempre al mismo número de términos; es decir, un mismo predicado P no puede aparecer en el mismo discurso unas veces como Pt1t2 (con dos términos) y otras como Pt1t2t3 (con tres). Para construir sintácticamente esos términos se dispondrá de constantes, variables y funciones que calculan términos. Primera aproximación: predicados monádicos con una constante en su único término En la aproximación más simple a este lenguaje empezamos considerando fórmulas atómicas formadas con: 1. nombres de predicados monádicos como P o Q, que enuncian una propiedad sobre un único término 2. nombres de términos constantes, como a o b. Estas fórmulas atómicas son del tipo Pa o Qa y se acabarán interpretando como "a tiene la propiedad P" o "a tiene la propiedad Q". Fórmulas más complejas se generan mediante el uso de conectivas; así se produce, por ejemplo: (Pa∧¬Qb)→Qa. A la hora de interpretar, necesitamos el contexto, el universo. En este universo damos una interpretación de los componentes de nuestra formula y realizamos el Diagrama de Ben. Según esta interpretación le damos unos valores y vemos si cumplen las propiedades.

1. Construcción de interpretaciones Evaluar una fórmula como (Qa→¬Pb) respecto a una interpretación requiere fijar cómo se evalúan sus fórmulas atómicas (respecto a esa interpretación). Para ello se requiere:

1. Fijar un universo, es decir, precisar el 'conjunto total' de elementos que se considera en esta interpretación I: por ejemplo UI={1,2,3}. 2. Para cada predicado monádico, fijar el conjunto de elementos del universo que lo representa, por ejemplo: Q I={1,3},PI={1,2}. 3. Fijar qué elementos (aI,bI)del universo representan a los términos a y b de la fórmula, por ejemplo: aI=2,bI=1. Notación. El mismo predicado monádico Q puede ser representado en la interpretación I1 por un conjunto como Q I1={1} y en la interpretación I2 por un conjunto como Q I2={1,2}. En los ejemplos con una sola interpretación se usará como nombre del conjunto el mismo que el del predicado monádico: Q={1,2} en vez de QI={1,2}. Lo mismo haremos con el elemento que representa a la constante: a=3. Independencia en la elección. El conjunto que representa Q puede ser cualquier subconjunto del universo: desde el conjunto vacío (sin elementos) hasta el propio universo (con todos sus elementos), o alguno 'intermedio'. Para cualquier otro predicado monádico, como P, se puede escoger cualquiera de esas opciones, coincida o no con el conjunto que se escogió para Q. Lo mismo ocurre al escoger qué elementos representan a las constantes Q=a, b, pueden coincidir o no en el elemento que las representa en el universo. Por último, en una fórmula como (Pa→Qa) el elemento que se escoge en un interpretación para representar la constante a debe ser el mismo para sus dos apariciones. Incluso la fórmula más simple en Lógica de Predicados (p.ej. Qa) admite infinitas interpretaciones posibles. Basta considerar que se pueden ir escogiendo, ilimitadamente, universos cada vez con más elementos (o incluso universos infinitos). Este hecho surge inevitablemente de la semántica, de la forma en que se ha definido cómo se interpreta una fórmula en Lógica de Predicados. No ocurría así en Lógica de Proposiciones y esta característica de este nuevo sistema lógico tendrá consecuencias en los cálculos posibles para decidir cuestiones como la insatisfacibilidad o la consecuencia en Lógica de Predicados. 2. Satisfacción de una fórmula (monádica) atómica La interpretación I satisface (⊨) la fórmula Qa sí y sólo si el elemento del universo que representa a esa constante pertenece (∈) al conjunto en el universo que representa al predicado Q: I⊨Qa ↔ aI∈ QI. Así, una interpretación I donde Q={1,3}, a=2 no satisface la fórmula Qa; formalmente: I⊭ QaI. Por contra, una interpretación I con Q={1,3},a=3, satisface la fórmula Qa: formalmente I⊨Q. Notación. El símbolo ⊨ se usa tanto para expresar I⊨Qa ("la interpretación satisface la fórmula") como X,Y⊨Z ("Z es consecuencia de las fórmulas X e Y"). El significado concreto se aprecia fácilmente en cada caso, conforme el componente izquierdo de la expresión sea una interpretación o no. Para calcular si una interpretación I satisface una fórmula compuesta como (Pa→¬Qb) basta evaluar el valor de verdad de cada fórmula atómica ('si la interpretación la satisface o no') y luego propagar esos valores a través de la conectivas proposicionales como es usual. Es decir, si I⊨Pa y I⊨Qb

entonces esa misma interpretación I no satisface el condicional porque hace verdadero el antecedente pero falso el consecuente. 3. Ejemplos: Usamos sólo dos predicados y dos términos o sujetos de un universo.. P_, Q_, a, b. Para la interpretación de la imagen, resultan falsas y verdaderas: -

Pa Pa Pa Pa

∧ Qb: FALSA ∨ ¬Qb: FALSA → Qb: VERDADERA ↔ Qb: FALSA

Podemos encontrar infinitas interpretaciones:

Predicados poliádicos con constantes en los términos No sólo se puede expresar una propiedad de un elemento, si no, también, podemos establecer una relación en la que un predico pueda llevar más de un término o sujeto. Tal que P_ (Pa), R_ _ (Rab), M _ _ _(Sacd).

Entonces en el árbol, añadimos al predicado tantos hijos como argumentos tenga. Normalmente se trabaja con predicados monádicos y diádicos (2 argumentos o sujetos). Entonces ahora no trabajamos con una propiedad sobre un término, si no una relación. Para interpretar un predicado Rab, necesitamos relaciones, que a través del diagrama de Ben se representa con una flecha que indica la relación, va por pares. En la interpretación en la izquierda resulta verdadera. Hay que tener en cuenta la dirección de la flecha. Si a=b=3, asumir que un elemento está relacionado consigo mismo, también necesitamos una flecha para indicar esa relación. No por ser el mismo se establece esa relación. Igual que un predicado monádico como (Pa) enunciaba algo sobre un término, un predicado diádico (Rab) enuncia algo sobre dos términos y en general un predicado n-ádico (Ma1…an) enuncia algo en conjunto sobre n términos. Durante el curso trabajaremos especialmente con predicados monádicos y diádicos. Semántica (de predicados diádicos) Un predicado diádico como Rab se interpreta escogiendo una relación determinada en un universo dado y comprobando si el elemento que representa a y el que representa b se encuentran en esa relación en el universo. Así, la misma 'fórmula abstracta' Rab se puede interpretar como el enunciado "Es mayor(5,4)" en el universo de los números naturales o "Es Padre(pepe, juan)" en un cierto universo de personas. Formalmente, una relación binaria en un universo es también un conjunto: en concreto, el conjunto de pares de elementos del universo que se consideran relacionados. Por ejemplo, sobre U={1,2,3}, una posible relación es el conjunto M={(1,1),(1,2),(3,2)}. Obsérvese que en M está el par (1,2) pero no el par (2,1): "1 está relacionado con 2" pero "2 no está relacionado con 1". I satisface Rab sí y sólo si el par de elementos del universo (a I,bI) pertenece al conjunto de pares de elementos que definen la relación R I que representa al predicado diádico R: I ⊨Rab↔(aI,bI)∈RI.

Las flechas en el diagrama de Ben, tiene que diferenciarse entre ambos predicados. Predicados con variables en sus términos y con cuantificadores Sintaxis Se presentan nuevos símbolos en el lenguaje de predicados: cuantificadores ⩝_ (para todo), ∃_ (existe), también un nuevo conjunto de variables (x, y, z…) que completan el símbolo de cuantificadores. Las variables van a jugar el mismo papel que las constantes. Pero los términos no pueden ir con los cuantificadores. Las reglas sintácticas:

Por ejemplo: ⩝x ((Pa → Rxb) ∨ Qz), ∃z ((Pa → Rxb) ∨ Qz), ⩝x (∃z ((Pa → Rxb) ∨ Qz)). Hasta este punto se han rellenado los términos de un predicado (p.ej. Rab) con constantes. Ahora se amplía el alfabeto de forma que también se puedan situar variables en los términos (p.ej. Rxy). Es decir, el alfabeto provee por separado de un conjunto de constantes y de otro de variables. Cuando los ejemplo requieran pocos términos usaremos {a,b,c,…} como términos constantes y {…,x,y,z} para las variables. O bien {c1,c2,c3,…} y {x1,x2,x3,…} si se requieren muchos más. Así, todo término puede ser complementado bien por una constante o por una variable. Todas estas fórmulas son fórmulas atómicas de Lógica de Predicados: Rab, Rxa, Rcy, Ryx… o bien Rc1c2,Rx1c1,Rc3x2,Rx2x1… Los cuantificadores son dos, que se usarán para construir enunciados como: - ∀x: "todos los elementos del universo cumplen (...)" - ∃x:"existe al menos un elemento que cumple (...)" Los símbolos ∀ (para todo) y ∃ (existe) van siempre seguidos de una variable escogida en cada caso. Nunca una constante completa un cuantificador. Un ejemplo de cuantificador correctamente completado es el que aparece en la fórmula ∃x (Px), que puede leerse como "existe al menos un x tal que ese x tiene la propiedad P".

Recordamos que en este curso se viene abreviando como 'fórmula' lo que en otros textos se denomina 'fórmula bien formada' o 'fórmula correcta'. El siguiente conjunto de reglas producen casi todas las fórmulas de Lógica de Predicados (a falta de las reglas que introducen la identidad y funciones en los términos, que se verán en el próximo capítulo). 1. Fórmula (atómica): todo predicado n-ádico Mt1…tn con sus términos correctamente formados es una fórmula; donde un término está correctamente formado si: - el término consta de una constante - el término consta de una variable 2. Conectivas: - sí X es una fórmula entonces (¬X) también lo es - sí X,Y son fórmulas entonces también lo son (X∧Y),(X∨Y),(X→Y) y (X↔Y) 3. Si X es una fórmula entonces también lo son tanto ∀vX como ∃vX, cualquiera que sea la variable usada en ∀v y ∃v. Ejemplos de fórmulas de Lógica de Predicados En la siguiente secuencias de fórmulas cada una de ellas, salvo las atómicas, se genera a partir de una o dos fórmulas previas en la secuencia:

El árbol sintáctico de la última fórmula tiene por conectiva principal, superior, una conjunción. Y este nodo raíz tiene dos nodos hijos inmediatos: un cuantificador ∀z y un predicado Px. Variables libres y ligadas: tenemos que aclarar que el ámbito de un cuantificador es todo lo que hay a su derecha y entre paréntesis. Cuando se genera una fórmula del tipo ∀xF a partir de una fórmula previa F, de esta fórmula F se dice que es el ámbito de ese cuantificador. Así, en ∀z¬(Raz→¬∃xPx) el ámbito del cuantificador es: - ∃x es Px - ∀z es ¬ (Raz→¬∃xPx) Son variables ligadas o cuantificadas aquellas que se ven afectadas por un cuantificador, están dentro del ámbito, y ese cuantificador tiene que tener la misma variable. Las variables libres son aquellas variables dentro de un predicado a las que ningún cuantificador las afecta, es decir, no se encuentran dentro del ámbito del cuantificador. Es importante la distinción a la hora de la semántica.

Semántica Las variables se tienen que estudiar para todos y cada uno de los elementos de nuestro universo. No es como un término o una constante que se le asigna un elemento de nuestro universo. Entonces hay que hacer todas las

interpretaciones donde la variable en cada interpretación será un elemento diferente de nuestro universo. Para interpretar una fórmula como Qax se requiere lo mismo para la constante que para la variable libre. Es decir, hay que construir una interpretación donde: 

Se fija un universo y los pares de elementos relacionados por Q en esa interpretación, así como el elemento que representa a la constante 'a',



Se fija qué elemento del universo representa a la variable libre 'x'

Por ejemplo, la siguiente interpretación I1 satisface Qax: I1:U={1,2,3}, Q={(1,1),(1,2),(2,1),(3,1)}, a=3, x=1. Como ejemplos adicionales, si se considera una interpretación I2 exactamente igual a la anterior salvo que ahora x=2 resulta que I2 no satisface Qax. Tampoco I3 si es idéntica a la anterior salvo que ahora x=3. (En cada interpretación a la variable x se le asigna un elemento diferente del universo, mientras que la constante a se mantiene igual, a=3). Se puede observar que en los tres ejemplos anteriores simplemente se ha hecho transitar a la variable 'x' por todos los valores que puede tomar del universo, evaluando en cada caso si esa interpretación satisface o no la fórmula. En este apartado, este proceso no es más que una forma de generar ejemplos distintos. En el apartado siguiente, sobre cómo interpretar los cuantificadores, este recorrido de asignaciones de la variable será conceptualmente necesario. La variable libre en Qax se puede convertir en variable ligada en la fórmula ∃x Qax o en ∀x Qax. Y estas tres expresiones declaran enunciados distintos: 1. Qax: 'a' está relacionado con 'x' por la relación Q. 2. ∃x Qax: existe (al menos) un 'x' tal que 'a' está relacionado con ese 'x' por Q 3. ∀x Qax: todos (cada uno de los 'x' del universo) cumplen que 'a' está relacionado por Q con él Partamos de una misma interpretación aplicable a las tres fórmulas anteriores: I: U={1,2,3,4}, Q={(1,1),(1,2),(2,1),(3,1)}, a=3. 1. Qax: a la interpretación anterior es necesario completarla con una asignación precisa de un elemento para 'x'. Si x=1x=1x=1 entonces satisface la fórmula 2. ∃x Qax: ya no es preciso asignar explícitamente un elemento concreto para 'x' porque se consideran todas las opciones posibles para 'x' como elemento del universo. La interpretación III anterior satisface ∃x Qax si existe al menos una asignación a 'x' (aquí, x=1x=1x=1) que satisface Qax. 3. ∀x Qax: ya no es preciso asignar explícitamente un elemento concreto para 'x' porque se consideran todas las opciones posibles para 'x' como elemento del universo. La interpretación III anterior satisfaría ∀x Qax si todas las asignaciones a 'x' en ese universo satisfacen Qax. Como a=3 en esa interpretación y el universo consta de 4 elementos, esto requeriría que en Q estuvieran todos los

posibles pares que empiezan por 3: (3,1),(3,2),(3,3)(3,4) Como esto no ocurre en la interpretación I, ésta no satisface la fórmula ∀x Qax. Predicados con funciones en sus términos. Identidad entre términos Funciones en los términos La referenciación indirecta que permiten las funciones. Cada predicado, cuando se interpreta, enuncia algo sobre sus términos. Hasta este punto la referencia a esos términos se producía de forma directa, como en Qax, que en un universo de personas se podría leer como " la persona 'a' quiere a la persona 'x' ". Pero, en ese mismo universo de personas, es usual también referirse a "la madre de Juan" o incluso a "la madre de la madre de Juan". De forma abstracta, esto es un ejemplo de función f(x) con un argumento: se facilita un valor para ese argumento (Juan) y la función devuelve la persona que 'es madre (juan)'. O se facilita como argumento la persona que 'es madre(juan)' y la función devuelve la persona 'es madre (es madre(juan))'. Es decir, de forma más abstracta, se calcula el elemento resultante de f(f(x)). Hay funciones del tipo g(x, y) tales que, para obtener el elemento resultante al que se refieren hay que facilitar el valor de dos argumentos. Esto ocurre en un universo de puntos geográficos, para referirse al 'punto intermedio entre Calatayud y Mérida'. O en el universo de números naturales para referirse al 'número que es suma de 3 y de 5'. Sintaxis. En este punto ampliamos la sintaxis que venimos utilizando para permitir esa referencia indirecta a elementos: 

Nuestro lenguaje dispone de predicados n-adicos (Rt1t2…tn) que declaran algo sobre sus términos. Usualmente manejaremos sólo predicados monádicos o diádicos



Cada uno de estos términos puede ser rellenado por una constante, una variable o una función h(x1,x2,…,xm). Usualmente emplearemos sólo funciones con uno o dos argumentos.



Esos argumentos de las funciones requieren a su vez 'ser rellenados con' constantes, variables o con referencias a elementos escritas en forma de función.

De esta forma, si Q es un predicado diádico, f(x) es una función con un argumento y g(x,y) es una función con dos argumentos, todos estas fórmulas atómicas son sintácticamente correctas: 

Qab, Qax, Qxy



Qaf(x), Qxf(x), Qxf(b)



Qf(x)f(b), Qag(b,c), Qf(x)g(x,b)



Qaf(f(b)), Qag(f(x),b)

Semántica. Todas las fórmulas anteriores, del tipo Qt1t2 se pueden interpretar como "alguien1 quiere a alguien2". O también como "algo1 es mayor que algo2",

entre otras muchas opciones. Cualquier interpretación concreta tiene que facilitar exactamente qué o quién (en el universo) es cada término, por mucho que se haya referenciado de forma muy indirecta. Por ejemplo, la siguiente interpretación III facilita toda la información necesaria como para evaluar si satisface o no cada una de las fórmulas Qt1 t2 que expusimos en el listado previo: 

universo U={1,2,3}, donde Q={(1,1),(1,2),(3,2)}



valores para las constantes a=1,b=2,c=1,x=3,y=2.



¿qué/quién es aquí el f de algo, f(t))? f(1)=2, f(2)=2, f(3)=1.



¿qué/quién es aquí g(t1,t2)? -

y

variables

libres

referenciadas:

g(1,1)=2, g(1,2)=2, g(1,3)=1 g(2,1)=3, g(2,2)=2, g(2,3)=2 g(3,1)=1, g(3,2)=1, g(3,3)=2

En esta interpretación Qag(f(x),b) resulta ser Q1g(f(3),2) resolviendo las constantes y variables, que a su vez es Q1g(1,2) resolviendo la función 'f' y finalmente se concreta como Q12 resolviendo la función 'g'. Y el par (1,2) sí que se declara en la interpretación entre los relacionados por Q, luego la interpretación satisface Qag(f(x),b). La relación de identidad entre dos términos Sintaxis. La relación de identidad afirma ...