Lógica de Predicados Lectura M3 PDF

Preview

Summary

Lógica de Predicados_Lectura_M3.pdf...

Description

Módulo 3 Unidad 3 Lógica de Predicados

Materia: Lógica Simbólica Profesor: Marcelo Smrekar

Introducción George Boole (Lincoln, Reino Unido, 1815-Ballintemple, actual Irlanda, 1864) Matemático británico. Procedía de una familia venida a menos y tuvo que desestimar la idea de convertirse en monje al verse obligado a mantener a sus padres. A los dieciséis años enseñaba Matemáticas en un colegio privado y más tarde fundó uno propio. A los veinticuatro años, tras la publicación de su primer escrito, pudo ingresar en Cambridge, pero desestimó la oferta, de nuevo a causa de sus deberes respecto a su familia. En 1849 le nombraron profesor de Matemáticas del Queen’s College, en Cork, donde permaneció el resto de su vida. El gran descubrimiento de Boole fue aplicar una serie de símbolos a operaciones lógicas y hacer que estos símbolos y operaciones –por elección cuidadosa – tuvieran la misma estructura lógica que el álgebra convencional. En el álgebra de Boole, los símbolos podían manipularse según reglas fijas que producirían resultados lógicos. En 1854 publicó Investigación sobre las leyes del pensamiento, libro que trataba por completo de la lógica simbólica y su álgebra. La influencia de esta lógica matemática sobre las matemáticas modernas tendría una evolución lenta: si en un primer momento no parecía más que un intrincado juego de palabras, más adelante se vio que era de lo más útil, y hasta completamente indispensable para conseguir la matemática lógica. Biografías y vidas: George Boole http://www.biografiasyvidas.com/biografia/b/boole.htm (Visita: marzo de 2011)

Si profundizamos en el estudio de la lógica, notaremos, más temprano que tarde que los métodos empleados en la lógica de proposiciones y que han sido mencionados en las lecturas de los módulos anteriores, no resultan suficientes para estudiar algunos razonamientos. Por ejemplo, en el siguiente razonamiento: Todos los Argentinos son sudamericanos. Todos los Cordobeses son Argentinos. Entonces, todos los Cordobeses son Argentinos. No es posible decidir sobre la validez del razonamiento con los métodos que conocemos, puesto que no es posible determinar el valor de verdad de la última proposición sólo como consecuencia de los valores de verdad de las proposiciones anteriores. Expresando simbólicamente las premisas y la conclusión de la inferencia, tendríamos: p= Todos los Argentinos son sudamericanos. q= Todos los Cordobeses son Argentinos.

Lógica Simbólica – Marcelo Smrekar | 2

(p A q) —>r= Entonces, todos los Cordobeses son sudamericanos. El razonamiento mencionado es intuitivamente válido, sin embargo, esta fórmula "p" y "q" implica "r" es inválida porque no tenemos información sobre la veracidad de ―r‖ salvo que expresamente determinemos una relación entre ―p‖ y ―q‖. Debemos recordar en este punto que las tautologías que definimos en lecturas anteriores indicaban la veracidad de la proposición compuesta como consecuencia de las proposiciones simples que la componían. Ejemplo, ―p entonces q‖ y también ―p‖, entonces ―q‖ y vemos que ninguna otra proposición (como en este caso ―r‖) estaba involucrada. En el caso del ejemplo mencionado de los gentilicios (si bien sabemos sobradamente que todos los cordobeses son sudamericanos) en rigor, no podemos afirmar que r sea verdadero con los valores de verdad de ―p‖ y de ―q‖. Es decir que es posible hacer verdaderas las premisas y falsa la conclusión. Examinando atentamente la estructura del razonamiento llegamos a la evidencia de que su validez depende no sólo de las relaciones existentes entre sus proposiciones, sino también de las relaciones existentes entre los elementos de sus proposiciones, elementos conocidos tradicionalmente con el nombre de términos. De este nuevo tipo de razonamiento, basado en el análisis de la estructura interna de las proposiciones simpl es, se ocupa ésta, la Lógica llamada Lógica de los Predicados. De hecho, son semejantes los predicados del lenguaje coloquial y los predicados de la Lógica. Palabras (adjetivos) que denotan propiedades o cualidades como 'frío', 'lento', 'azul', 'Argentino', etc.,son predicados gramaticales y también predicados lógicos de una posición, de un argumento, o de un ―elemento‖ (se refieren a un solo nombre como 'Juan es lento'. Sin embargo, la diferencia se produce con términos como 'Córdoba', 'caballo' u otros que son sustantivos comunes. En gramática estos sustantivos son sujetos pero en lógica en ningún caso lo son, sino que son predicados. La situación se acentúa más con palabras como 'hermano' o 'cuñado', que el lenguaje de la lógica de predicados interpreta como predicados de dos posiciones (elementos) o predicados que relacionan a dos elementos como, por ejemplo, 'Pedro es hermano de Miguel' o 'María es cuñada de Julia'. En estos casos, de manera general, los predicados son: '... hermano de../,'... cuñado de../, etc.

3.1- Función Proposicional: Definición. La Lógica de Predicados distingue también dos clases de términos: los que representan individuos (gramaticalmente "sujetos" y para la Lógica ―argumentos‖) y los que representan propiedades (gramaticalmente "predicados" y para la Lógica serán también predicados). En ese sentido entonces, los llamaremos argumentos y predicados respectivamente. Por ejemplo: Felipe corre. Es una proposición con un argumento (Felipe) y un predicado (corre). El predicado adjetiva al argumento y es considerado por la Lógica de

Lógica Simbólica – Marcelo Smrekar | 3

Predicados como una característica del mismo. A estas proposiciones las llamaremos del tipo predicativas. A un argumento determinado lo simbolizaremos con las primeras letras del abecedario (a, b, c) y podremos indicar por ejemplo ―a corre‖ destacando que el sujeto particular a está corriendo. Es posible también, que el argumento no esté específicamente determinado. En este caso el argumento se simboliza con un indicador de que puede ser cualquier elemento. Para representar un argumento indefinido utilizaremos las últimas letras del abecedario (x, y, z) y llamaremos al argumento indeterminado ―variable‖ ya que podremos utilizar cualquier elemento particular para incorporar en el argumento reemplazándolo por la variable. En ese caso, diremos que ―evaluamos‖ la variable por el argumento particular. A los predicados, en general los simbolizaremos con letras mayúsculas tales como F, G, H y de esta manera F(a) Indica que al argumento específico a le corresponde el argumento F. En el caso que el argumento fuera ―Felipe‖ y el predicado fuera ―corre‖ F(a) simboliza ―Felipe corre‖

Definición Diremos que una entidad es una función proposicional si utiliza una variable como argumento. A las funciones proposicionales las simbolizaremos utilizando los mismos símbolos que para las proposiciones. Así F(x), G(z), H(y) son funciones proposicionales.

3.2- Cuantificadores lógicos: Cuantificador universal, cuantificador existencial. La Lógica de Predicados, es comúnmente llamada también Lógica de ―cuantificadores‖ por lo que procederemos a definir ese concepto. Si notamos que una función proposicional puede ser evaluada por uno, varios, o todos los elementos a al vez, estaremos pensando intuitivamente en los cuantificadores. Es decir que de acuerdo a la cantidad de elementos que el sujeto determine, las proposiciones predicativas pueden clasificarse en: a) Singulares: cuando el sujeto es un solo elemento. Ejemplo: Ricardo es Ingeniero. b) Universales: cuando el sujeto es una totalidad de elementos. Ejemplo: Todos los geómetras son matemáticos.

Lógica Simbólica – Marcelo Smrekar | 4

c) Particulares: cuando el sujeto es una parcialidad de individuos. Ejemplo: Algunos Ingenieros son Cordobeses. La cantidad de elementos que el sujeto resume en estas proposiciones introduce nuevos elementos, que llamaremos cuantificadores y que están representados por los términos "todos" y "algunos". Estos nuevos elementos determinan cuantitativamente a sus argumentos.

Cuantificador universal. En el caso en el que el argumento resuma a ―todos‖ los elementos del universo, utilizaremos el símbolo  e indicaremos ―para todo‖ elemento. Por otra parte, a este símbolo lo llamaremos cuantificador universal. Además a la expresión x le daremos el significado ―para todo x‖ o ―para todo valor de x‖ y a la expresión x /F(x) le daremos el significado ―para todo valor de x corresponde el predicado F. De esta forma, si x representa a los geómetras y F es ―ser matemático‖ entonces la expresión x , F(x) significa ―Todos los geómetras son matemáticos‖ o más específicamente ―Para todo geómetra se da, que el mismo es matemático‖ o de otra forma ―para todo geómetra, el geómetra es matemático‖

Cuantificador existencial. En el caso en el que el argumento resuma a ―algunos‖ elementos del universo, entendiendo a alguno como al menos uno, utilizaremos el símbolo  para indicar que existe al menos un elemento al cual es posible asignarle el predicado. A este símbolo lo llamaremos cuantificador Existencial. Además a la expresión x le daremos el significado ―existe x‖ o ―existe al menos un valor de x‖ y a la expresión x /F(x) le daremos el significado ―existe al menos un valor de x al que le corresponde el predicado F‖ o y de otra forma ―existe x tal que a x le corresponde F‖. De esta forma, si x representa a los ingenieros y G es ―ser Cordobés‖ entonces la expresión x /G(x) significa ―Algunos Ingenieros son Cordobeses.‖ o más específicamente ―Existe al menos un ingeniero que es cordobés‖ o lo mismo ―Existe al menos un ingeniero, tal que ese ingeniero es cordobés‖. Note que esta expresión puede ser cierta o falsa, para que sea cierta, sólo hay que encontrar un ingeniero que sea cordobés, para que sea falsa, no es posible que haya ni siquiera uno.

Sintaxis de la Lógica de Predicados. A manera de resumen veremos que los símbolos que introduce la Lógica de Predicados son: • Variables individuales: éstas representan elementos o individuos indeterminados del universo. Se emplean para mencionarlas las últimas letras minúsculas del alfabeto: x, y z etc. • Constantes individuales: éstas representan a los individuos determinados del universo. Se emplean para mencionarlas las primeras letras minúsculas del alfabeto: a, b, c etc.

Lógica Simbólica – Marcelo Smrekar | 5

• Variables predicativas: éstas representan predicados que no están determinados. Se usan las letras mayúsculas: F, G, H, etc. para mencionarlas • Cuantificadores: éstos hacen referencia a la totalidad de los elementos del universo o a la existencia de al menos uno de los elementos del mismo. De acuerdo a ello, los cuantificadores son dos, específicamente:

  cuantificador universal  cuantificador existencial Los símbolos  y  son los que llamamos cuantificadores. En el espacio inmediato a los cuantificadores dentro del paréntesis se colocan o bien variables individuales como (x ) o ( x ) y entonces estamos refiriéndonos a la Lógica de Predicados de primer orden; o bien, variables predicativas como (F ) o ( G ) y en ese caso nos estaremos refiriendo a la Lógica de Predicados de segundo orden. Es objetivo de esta materia, estudiar la Lógica de Predicados de primer orden solamente, por lo que dejaremos las cuestiones relativas a la Lógica de Predicados de segundo orden para aquel estudiante que quiera profundizar en ese campo. La Lógica de Predicados que aquí desarrollaremos es, entonces, de primer orden, pues los cuantificadores sólo contienen variables individuales. Veremos ahora algunas reglas para la formación de proposiciones que involucren funciones (a estas proposiciones con funciones las llamaremos fórmulas) para asegurarnos que se encuentren bien formadas:

Regla 1: Cada variable predicativa seguida de una o más constantes individuales es una proposición simple. Ejemplos: a)

F(a)

b)

G(ab)

c)

H(abc)

Regla 2. Cada proposición simple afectada al menos por un conectivo es una proposición compuesta tal y como la vimos en el módulo 1. Ejemplos: a)

F(a) ^ G(b)

b)

F(a) => (G(b) v H(c))

c)

F(a) v G(b) v H(c)

Regla 3: Cada variable predicativa seguida de una o más variables individuales es una función proposicional simple. Ejemplos: a)

F(x)

Lógica Simbólica – Marcelo Smrekar | 6

b)

G(xy)

c)

H(xyz)

Regla 4. Cada función proposicional simple afectada al menos por un operador es una función proposicional compuesta. Ejemplos: a)

F(x) ^ G(y)

b)

F(x)=> (G(y) v H(z))

c)

F(x) v G(y) v H(z)

Regla 5. Son variables libres las variables que no son afectadas por algún cuantificador. Ejemplos: a)

F(x)

b)

(F(x)=>G(y)) v H(z)

c)

F(x) v G(y) v H(z)

Regla 6. Son variables ligadas las variables afectadas por algún cuantificador. Ejemplos: a)

x /F(x)

b)

( x ) ^ ( y ) / (F(x) ^ G(y))

c)

( x ) ^ ( y ) ^ ( z ) / [(F(x)=>G(y)) v H(z)]

Regla 7. Son fórmulas cerradas las fórmulas que no contienen variables libres. Ejemplos: a)

x /F(x)

b)

( x ) ^ ( y ) / (F(x) ^ G(y))

c)

( x ) ^ ( y ) ^ ( z ) / [(F(x)=>G(y)) v H(z)]

Regla 8. Son fórmulas abiertas las fórmulas que contienen al menos una variable libre. Ejemplos: a)

F(x)

b)

F(x) ^ [( y ) ^ ( z ) / (G(y) v H(z))]

c)

( x ) ^ ( y ) / [(F(x)=>G(y)) v H(z)]

Regla 9. Si cuantificamos las variables libres de una función proposicional obtenemos una proposición. Ejemplos: a) F(x):

( x ), F(x)

Lógica Simbólica – Marcelo Smrekar | 7

b) ( x )^( y )^(z )[(F(x)=>G(y))vH(z)]

F(x)=>G(y))vH(z):

( x ) ^ ( y )^ ( z )

c) [F(x)^G(y)^H(z)]:

/

[F(x)^G(y)^H(z)] Regla 10. Si sustituimos las variables libres de una función proposicional por constantes individuales obtenemos una proposición. Ejemplos: a)

Dado F(x) y a por x se tiene: F(a)

b)

Dado G(xy), a por x y b por y se tiene: G(ab)

c)

Dado H(xyz), a por x, b por y, c por z se tiene: H(abc)

Regla 11. Son fórmulas predicativas monádicas las que contienen una sola variable individual. Ejemplos: a)

F(x)

b)

F(y) ^ G(y)

c)

[(F(z)=>G(z)) v H(z)]

Regla 12. Son fórmulas predicativas poliádicas las que contienen dos o más variables individuales. Ejemplos: a)

F(xy)

b)

(F(x) ^ G(y))

c)

[(F(x) => G(y)) v H(z)]

Regla 13. En la Lógica de Predicados de primer orden se cuantifican sólo las variables individuales. Ejemplos: a)

x /F(x)

b)

( x ) ^ ( y ) / (F(x) ^ G(y))

c)

( x ) ^ ( y ) ^ ( z ) / [(F(x)=>G(y)) v H(z)]

Regla 14. En la lógica de predicados de segundo orden se cuantifican también las variables predicativas. Ejemplos: a)

F ^ x /F(x)

b)

( G ) ^ ( x ) ^ ( y ) / (F(x) ^ G(y))

c)

( x ) ^ ( y ) ^ ( H ) ^ ( z ) / [(F(x)=>G(y)) v H(z)]

Lógica Simbólica – Marcelo Smrekar | 8

Formalizaciones Formalizaciones de proposiciones singulares Una proposición con predicado de las que llamamos predicativas se simboliza funcionalmente invirtiendo el orden de sus elementos y, como vimos en apartados anteriores, se usa cualquier letra mayúscula para los predicados y cualquier letra minúscula para las constantes individuales. Ejemplos: a)

Jorge es Arquitecto: A(j)

b)

Jorge y Ernesto no son Biólogos: ¬B(j) ^ ¬B(e)

c)

Es falso que Jorge y Ernesto sean Biólogos: ¬ (B(j) ^ B(e))

d)

Jorge y Ernesto son hermanos: H(j,e)

e)

Resistencia es la capital del Chaco: C(r)

f)

Rosario está entre Córdoba y Buenos aires: E(rcb)

Como todas estas fórmulas, son funciones evaluadas en valores determinados, es decir constantes, desde la a hasta la f, representan proposiciones. Lo que sostenemos es que sus argumentos o sujetos están simbolizados por letras que ya significan individuos determinados, consecuentemente se pueden calificar de verdaderas o falsas y en debido a eso, son proposiciones. Formalización de funciones proposicionales Las expresiones siguientes 'x es inteligente' e 'y es sabio', que se simbolizan 'I(x)' y 'S(y)' respectivamente, son funciones proposicionales. Es decir que no son proposiciones ya que sus argumentos están representados por variables que significan individuos indeterminados, de manera que no pueden ser calificadas de verdaderas ni de falsas.

3.3- Proposiciones categóricas. Una función proposicional expresa simbólicamente el caso general de una proposición individual. Al evaluarla, y convertirla en proposición, podemos reemplazar la variable por valores constantes particulares o cuantificadores. Así se tiene que de la proposición: O(x)

: x es obispo

A la que en principio no le podemos determinar el valor de verdad puesto que no sabemos qué valores va a tomar x, al cuantificarlas las convertimos en proposiciones. Por ejemplo

Lógica Simbólica – Marcelo Smrekar | 9

x / O(x) : algunos x son obispos x , O(x) : todos los x son obispos Como podemos ver, si el universo es el conjunto de las personas de Córdoba, entonces la primera es verdadera (entiendo que algún obispo cordobés hay) y la segunda es falsa (puesto que yo soy cordobés y de ninguna manera soy obispo). Debido a que las proposiciones que surgen al cuantificar una función, tanto con el cuantificador universal como con el existencial (y a las que llamaremos categóricas), pueden ser tanto afirmativas como negativas, tenemos que su expresión simbólica se puede resumir de acuerdo a lo que se ve en el cuadro siguiente y considerando las cuatro opciones correspondientes: Proposiciones

Fórmulas

Todo x miente

x M(x)

Ningún x miente

x ¬ M(x)

Algún x miente

x M(x)

Algún x no miente

x ¬ M(x)

Universales afirmativas. Las proposiciones categóricas universales afirmativas son aquellas funciones proposicionales cuantificadas con el cuantificador universal y que afirman el predicado de la función. De esta forma tenemos que: Todos los griegos son patriotas Lo que tenemos aquí es que ―Para todo x‖, ―x es griego‖, entonces ―x es patriota‖, que podemos simbolizar como x , G(x) => P(x).

Universales negativas. Las proposiciones categóricas universales negativas son aquellas funciones proposicionales cuantificadas con el cuantificador universal y que niegan el predicado de la función. De esta forma tenemos que: Ningún griego es patriota. Lo que tenemos aquí es que ―Para todo x‖, ―x es griego‖, entonces ―x no es patriota‖, que podemos simbolizar como x , G(x) => ¬P(x). Es interesante notar que las universales negativas no son la negación de las universales afirmativas (¿por qué? Medite sobre ello)

Lógica Simbólica – Marcelo Smrekar | 10

Particulares afirmativas. Las proposiciones categóricas particulares afirmativas son aquellas funciones proposicionales cuantificadas con el cuantificador existencial y que afirman el predicado de la función. De esta forma tenemos que: Algunos griegos son patriotas Lo que tenemos aquí es que ―Existe al menos un x‖ tal que ―x es griego‖ y ―x es patriota‖, que podemos simbolizar como x / G(x) ^ P(x).

Particulares negativas. Las proposiciones categóricas particulares negativas son aquellas funciones proposicionales cuantificadas con el cua...