calculo de predicados

CAPTULO 5Clculo de Predicados

ndice del Captulo5.1. Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915.2. Predicados y Clculo de Predicados . . . . . . . . . . . . . . . . . . . . . 925.3. El cuantificador universal . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.4. El cuantificador existencial . . . . . . . . . . . . . . . . . . . . . . . . . . 975.5. Propiedades de las cuantificaciones universal y existencial . . . . . . . . . 1005.6. Aplicaciones del clculo de predicados . . . . . . . . . . . . . . . . . . . . 1025.7. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

5.7.1. Ejercicios de traduccin . . . . . . . . . . . . . . . . . . . . . . . . 1045.7.2. Ejercicios sobre cuantificacin universal . . . . . . . . . . . . . . . . 1055.7.3. Ejercicios sobre cuantificacin existencial . . . . . . . . . . . . . . . 1065.7.4. Ejercicios de razonamientos . . . . . . . . . . . . . . . . . . . . . . 106

Introduciremos los conceptos referentes al Clculo de Predicados, el cual es una extensin delClculo Proposicional que ya vimos en el Captulo 3. Esta extensin nos permitir trabajarcon expresiones que usen variables de otro tipo adems del tipo booleano y nos conducir a unsistema formal que abarque una mayor cantidad de expresiones y con un mayor poder deductivo.

5.1. IntroduccinSi bien el clculo proposicional nos permiti analizar cierto tipo de razonamientos y resolver

acertijos lgicos, su poder expresivo no es suficiente para comprobar la validez de algunosrazonamientos simples. Por ejemplo, consideremos el siguiente razonamiento:

Todos los hombres son mortales. Scrates es hombre. Por lo tanto, Scrates es mortal.

91

92 5. CLCULO DE PREDICADOS

Si lo formalizamos en la lgica proposicional obtendremos que tanto las premisas como laconclusin son proposiciones elementales:

p : Todos los hombres son mortales.q : Scrates es hombre.r : Scrates es mortal.

y el razonamiento sera p q r, el cual no resulta verdadero.No podremos demostrar la validez de este razonamiento usando lgica proposicional, porque

sta no depende de las relaciones entre las premisas y la conclusin, sino de relaciones entrepartes de las proposiciones elementales que intervienen. Si analizamos la estructura internas deestas proposiciones, encontramos que el razonamiento es de la forma:

Todos los A son B. C es A. Por lo tanto, C es B.

En las secciones siguientes veremos herramientas que nos permiten demostrar este tipo derazonamientos. Trataremos primero el uso de smbolos para representar partes de enunciadossimples (llamados smbolos de predicados); y luego veremos la naturaleza de expresiones talescomo Todos los As son B.

5.2. Predicados y Clculo de PredicadosEl Clculo Proposicional nos permiti razonar con frmulas construdas a partir de las con-

stantes true y false, variables y operadores booleanos, con lo cual nos fue posible expresarafirmaciones o frases que pueden modelizarse utilizando expresiones de tipo booleano.

El Clculo de Predicados nos permitir razonar sobre una clase ms extensa y expresiva deexpresiones booleanas.

Un predicado es una aplicacin de una funcin booleana cuyos argumentos pueden ser ex-presiones no boolenas. Utilizaremos predicados para expresar propiedades o relaciones entreobjetos. Los siguientes son ejemplos de predicados: par.i , igual.(x, xz+z) , menor.(x, y+z).Los nombres de las funciones (igual, menor) son llamados smbolos de predicados. Tambinutilizaremos en los predicados la notacin infija, como x < y en lugar de menor.(x, y).

Los argumentos de los predicados pueden ser expresiones de distintos tipos. Estas expre-siones son llamadas trminos, por ejemplo los trminos de los predicados dados son i, x, xz+zy y + z.

Diremos que una frmula del clculo de predicados es una expresin booleana en la cualalguna de las variables booleanas ha sido reemplazada por:

predicados.

cuantificaciones existenciales o universales (las cuales sern introducidas a continuacin).

Por ejemplo, la expresin x < y x = z q.(x, z + x) es una frmula del clculo depredicados. sta contiene tres predicados: x < y, x = z y q.(x, x + z), y los trminos: x, y, z yz + x.

5.3. EL CUANTIFICADOR UNIVERSAL 93

El clculo puro de predicados incluye los axiomas y reglas de inferencia del clculo proposi-cional y los axiomas y reglas correspondientes a las expresiones cuantificadas que veremos acontinuacin.

En este clculo los smbolos de funcin no sern interpretados (a exepcin de la igualdad=). Esto significa que se har abstraccin de su significado, y se utilizarn las reglas de la lgicapara manipularlos. Es decir, que el clculo nos permitir razonar sobre sentencias sin tener encuenta el significado de los smbolos de predicados.

5.3. El cuantificador universalLa frase para todo x se formaliza con el cuantificador universal como x. Una afirmacin

que contenga esta frase se simboliza mediante una cuantificacin universal. Por ejemplo,Para todo entero n, 2 n es par.

se escribe usando nuestra notacin para la cuantificacin universal como:

(n : n Z : par.(2 n))

donde n Z es true si y solo si n es entero, y par.n es true si y solo si n es par.En matemtica, en general se dice (2n) es par, con n entero o para cualquier entero n,

(2 n) es par. Estas afirmaciones se interpretan igual a la dada anteriormente, es decir que seformalizan en el clculo de predicados con la misma cuantificacin universal.

El formato general de una cuantificacin universal es el siguiente:

(x : R.x : T.x)

Esta expresin se lee para todo x que satisfaga R se satisface T . R y T son predicados quetoman como argumento la variable de cuantificacin x. Llamaremos a estos predicados rango ytrmino de cuantificacin, respectivamente.

A continuacin veremos algunos axiomas y teoremas que nos permitirn trabajar con cuan-tificaciones universales. Al final del captulo utilizaremos stos para demostrar razonamientoscomo el dado en la introduccin.

(5.1) Axioma. Rango true

(x : true : T.x) (x :: T.x)

Este axioma nos permite omitir el rango de una cuantificacin universal cuando ste estrue.

(5.2) Axioma. Rango unitario

(x : x = N : T.x) T.N


donde x no aparece en la expresin N . Este axioma dice que si hay un nico x posible,al que llamamos N , decir que algo vale para todos los x equivale a decir que vale paraN .

Ejemplo: Para todo entero n tal que n es 3, 2 n es par es equivalente a 2 3 espar.

(5.3) Axioma. Rango vaco

(x : false : T.x) true

Este teorema afirma que es cierto que para cualquier x que satisfaga false se satis-face T.x, para cualquier predicado T . Esta cuantificacin universal es cierta dado queningn valor que pueda tomar x satisface false. Llamaremos rango vaco a la expresinbooleana false (dado que ningn valor lo satisface).

La cuantificacin universal (x : R.x : T.x) nos dice que todos los x que satisfagan Rsatisfacen T . A esta expresin la podemos interpretar como la conjuncin de todos los T.x talque R.x es true. Por ejemplo, la expresin:

(x : 0 x < 5 : b[x] > 0)

es equivalente a

b[0] > 0 b[1] > 0 b[2] > 0 b[3] > 0 b[4] > 0

Es decir que podemos pensar a la cuantificacin universal como la generalizacin de la con-juncin. A continuacin veremos que algunas propiedades de la conjuncin pasan a la cuantifi-cacin universal.

(5.4) Axioma. Distributividad de respecto de

(x : R.x : P T.x) P (x : R.x : T.x)

donde x no aparece en P .

La conmutatividad de nos permite definir el siguiente axioma.

(5.5) Axioma. Regla del trmino

(x : R.x : T.x G.x) (x : R.x : T.x) (x : R.x : G.x)

Cuando una cuantificacin tiene como trmino otra cuantificacin diremos que los cuantifi-cadores estn anidados. La siguiente ley permite intercambiar cuantificadores anidados de lasiguiente manera:

5.3. EL CUANTIFICADOR UNIVERSAL 95

(5.6) Axioma. Intercambio de cuantificadores

(x :: ( y :: T.x.y)) ( y :: (x :: T.x.y))

Por ejemplo, usamos este axioma para afirmar que para todos los m se da que para todo n,2 (m n) es par es lo mismo que para todos los n se da que para todo m, 2 (m n) espar.

Tambin podramos expresar la frase anterior como para todo m y n, 2 (m n) es par.Utilizaremos el siguiente axioma para expresar los cuantificadores anidados mediante una solacuantificacin con varias variables:

(5.7) Axioma.

(x :: ( y :: T.x.y)) (x, y :: T.x.y)

El axioma que sigue nos permitir trasladar el rango de especificacin hacia el trmino decuantificacin:

(5.8) Axioma. Traslacin

(x : R.x : T.x) (x : : R.x T.x)

Ejemplo: Para todos los enteros n, 2 n es par es equivalente a Para todos los n, sin es entero entonces 2 n es par

A partir de este axioma se pueden demostrar los siguientes teoremas:

(5.9) Teorema. Traslacin

a) (x : R.x : P.x) (x :: R.x P.x)b) (x : R.x : P.x) (x :: R.x P.x R.x)c) (x : R.x : P.x) (x :: R.x P.x P.x)

(5.10) Teorema. Variantes de traslacin

a) (x : Q.x R.x : P.x) (x : Q.x : R.x P.x)b) (x : Q.x R.x : P.x) (x : Q.x : R.x P.x)c) (x : Q.x R : P.x) (x : Q.x : R.x P.x R.x)d) (x : Q.x R.x : P.x) (x : Q.x : R.x P.x P.x)


Probaremos (5.10a))

(x : Q.x R.x : P.x)= Traslacin 5.8

(x :: Q.x R.x P.x)= Teorema 3.64

(x :: Q.x (R.x P.x))= Traslacin 5.8

(x : Q.x : R.x P.x)

El axioma que sigue muestra que la variable de la cuantificacin puede ser reemplazada porcualquier otra variable que no sea utilizada en la expresin.

(5.11) Axioma. Cambio de variableSi y no ocurre en R.x ni en T.x entonces

(x : R.x : T.x) ( y : R.y : T.y)

La restriccin y no ocurre en R o en T asegura que y es una variable nueva.Aplicando este teorema al primer ejemplo, podemos afirmar que es lo mismo decir Para

todos los enteros n, 2n es par que decir Para todos los enteros x, 2x es par. Las variablesde cuantificacin son llamadas tambin variables bobas, dado que podemos reemplazarlas porcualquier variable, lo nico que hacen es indicar sobre qu se cuantifica.

El siguiente teorema formaliza la idea de que cuando el rango de especificacin es unadisyuncin de predicados, podemos dividir la cuantificacin en dos cuantificaciones cuyos ran-gos son cada uno de estos predicados.

(5.12) Teorema. Particin de rango

( i : R.i S.i : T.i) ( i : R.i : T.i) ( i : S.i : T.i)

Ejemplo: Para todo nmero n mayor que 3 o menor que 3, |n 3| es mayor a 3es equivalente a Para todo nmero n mayor que 3 , |n 3| es mayor a 3 y para todonmero n menor que 3, |n 3| es mayor a 3 .

Si tenemos que un predicado f.x vale para todo x, en particular debera ser cierto f.t paracualquier t arbitrario que uno tome. Esta idea se formaliza en el siguiente teorema.

(5.13) Teorema. Instanciacin

(x :: P.x) P.E

5.4. EL CUANTIFICADOR EXISTENCIAL 97

Veamos situaciones donde la regla 5.13 es de gran ayuda. Por ejemplo, supongamos quequeremos probar

B par.(i + j) B par.(i + j)2

y que vale:

(x :: par.x par.x2) (5.1)Usaremos Instanciacin 5.13 para dar la siguiente prueba:

B par(i + j)= supuesto 5.1, Instanciacin 5.13 con E = i + j

B par((i + j)2)

5.4. El cuantificador existencialOtra clase de cuantificador, necesario para expresar afirmaciones o frases del lenguage cor-

riente, es el cuantificador existencial.La frase existe un x se formaliza con este cuantificador como x. Por ejemplo, la frase

existe al menos un nmero entre 10 y 20 que es primo, la cual puede expresarse tambin comoalgn nmero entre 10 y 20 es primo, se formaliza con la siguiente cuantificacin existencial:

(x : 10 x 20 : primo.x) (5.2)donde primo.x es true si y solo si x es primo.

El formato general de una cuantificacin existencial es el siguiente:

(x : R.x : P.x) (5.3)el cual se lee existe x en el rango R que satisface P . Al igual que en la cuantificacin universal,R y T son predicados que toman como argumento la variable x, y se denominan rango y trminode cuantificacin respectivamente.

La cuantificacin existencial se puede pensar como la generalizacin de la disyuncin. Estohace que algunas propiedades de la disyuncin pasen a esta cuantificacin.

El siguiente axioma caracteriza a la cuantificacin existencial, relacionandola con la cuan-tificacin universal.

(5.14) Axioma. De Morgan Generalizado

(x : R.x : T.x) (x : R.x : T.x)

Llamamos a este axioma De Morgan Generalizado, dado que es una generalizacin dela ley de De Morgan (3.47a), (p q) p q.


El siguiente ejemplo ilustra la idea de esta generalizacin: La expresin (x : 0 x f.m)d) (x, y : x R y R : f.x < 0 0 < f.y ( z : z R : f.z = 0))

5.3 Formalizar las siguientes frases:

a) Cada uno ama a alguien.b) Alguien ama a alguien.

5.7. EJERCICIOS 105

c) Cada uno ama a cada uno.d) Nadie ama a todos.e) Alguien ama a nadie.

5.4 Formalizar las siguientes frases:

a) Puedes engaar a alguien por algn tiempo.b) Puedes engaar a todos por algn tiempo.c) No puedes engaar a todos todo el tiempo.d) No puedes engaar a alguien todo el tiempo.

5.7.2. Ejercicios sobre cuantificacin universal5.5 Suponiendo que x no ocurre en P , probar que la Distributividad de respecto de (5.4):

P (x : R.x : Q.x) (x : R.x : P Q.x) sigue directamente de la misma expresincon R.x true, es decir P (x :: Q.x) (x :: P Q.x). Lo cual significa quepodramos haber definido un axioma ms simple.

5.6 Probar que (x : R.x : P.x) (x : R.x : Q.x) (x : R.x : P.x Q.x) sigue dela misma expresin con R.x true, es decir de (x :: P.x) (x :: Q.x) (x ::P.x Q.x).

5.7 Suponiendo que x no ocurre en P , probar (x : R.x : P ) P (x :: R.x). Sug-erencia: Comenzar con el lado izquierdo aplicando Traslacin, ya que en el lado derechoR.x true.

5.8 Probar el teorema 5.33: (x : R.x : true) true.

5.9 Probar el teorema 5.34: (x : R.x : P.x Q.x) ((x : R.x : P.x) (x :R.x : Q.x)). Sugerencia: Reemplazar la expresin completa usando el teorema (3.61) y acontinuacin la Regla del Trmino.

5.10 Probar el teorema: Fortalecimiento de rango (5.29): (x : Q.x R.x : P.x) (x :Q.x : P.x). Sugerencia: Ser de utilidad el axioma de Particin de Rango.

5.11 Probar el teorema: Fortalecimiento de trmino (5.30): (x : R.x : P.x Q.x) (x :R.x : P.x). Sugerencia: Usar la Regla del Trmino.

5.12 Probar el teorema: Monotona de (): (x : R.x : Q.x P.x) ((x : R.x : Q.x) (x : R.x : P.x)). Usar (3.64) Traslacin y luego la Regla del Trmino

5.13 Probar el teorema: Instanciacin (5.13): (x :: P.x) P [x := E]. Sugerencia: La clavees renombrar la variable cuantificada usando el teorema Cambio de variable. Elegir paraello una variable que no aparezca en P.x ni en E.


5.7.3. Ejercicios sobre cuantificacin existencial5.14 Probar el teorema 5.15: Formas alternativas de De Morgan Generalizado:

a) (x : R.x : P.x) (x : R.x : P.x)b) (x : R.x : P.x) (x : R.x : P.x)c) (x : R.x : P.x) (x : R.x : P.x)

5.15 Probar el teorema 5.23: Traslacin para : (x : R.x : P.x) (x :: R.x P.x).

5.16 Probar el teorema 5.24: Traslacin para : (x : Q.x R.x : P.x) (x : Q.x :R.x P.x).

5.17 Suponiendo que x no ocurre en P , probar el teorema 5.32: Distributividad de respectode : P (x : R.x : Q.x) (x : R.x : P Q.x).

5.18 Suponiendo que x no ocurre en P , probar el teorema: (x : R.x : P ) P (x :: R.x).

5.19 Suponiendo que x no ocurre en P , probar el teorema 5.38: Distributividad de respectode : (x :: R.x) ((x : R.x : P.x Q.x) P (x : R.x : Q.x)).

5.20 Probar el teorema 5.39: (x : R.x : false) false.

5.21 Probar el teorema 5.35: Debilitamiento de rango: (x : R.x : P.x) (x : Q.x R.x :P.x).

5.22 Probar el teorema 5.36: Debilitamiento de trmino: (x : R.x : P.x) (x : R.x :P.x Q.x).

5.23 Probar el teorema 5.37: Monotona de : (x : R.x : Q.x P.x) ((x : R.x :Q.x) (x : R.x : P.x)).

5.24 Probar el teorema 5.27: Introduccin de : P.E (x :: P.x).

5.7.4. Ejercicios de razonamientos5.25 Demostrar que el siguiente razonamiento es correcto, formalizndolo mediante clculo de

predicados y demostrndolo como teorema.

Todos los ballenas son mamferos. Wally es una ballena. Por lo tanto, Wally esun mamfero.

5.26 Demostrar que los siguientes razonamientos son correctos formalizndolos mediante cl-culo de predicados y demostrndolos como teoremas.

5.7. EJERCICIOS 107

a) Los brujos son considerados individuos con poderes ocultos. Algn brujo es mago.Luego, algn mago es considerado como individuo con poderes ocultos.

b) Ningn fotgrafo pinta. Todos los que no son fotgrafos son escultores. Por lo tanto,todos los pintores son escultores.

c) Ningn feo despierta pasiones. Todos los atletas despiertan pasiones. Por lo tanto,ningn atleta es feo.

calculo de predicados

Documents