Calculo de predicados

C APÍTULO 6

Cálculo de Predicados
Índice del Capítulo
6.1. Predicados y Cálculo de Predicados . . . . . . . . . . . . . . . . . . . . . 112 6.2. El cuantificador universal . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.2.1. Traslación con el operador universal . . . . . . . . . . . . . . . . . . 114 6.2.2. Distributividad con el cuantificador universal . . . . . . . . . . . . .115 6.2.3. Manipulación de rango y término con el cuantificador universal . . . 115 6.2.4. Instanciación con el cuantificador universal . . . . . . . . . . . . . . 116 6.2.5. Teoremas y el cuantificador universal . . . . . . . . . . . . . . . . . 117 6.3. El cuantificador existencial . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.3.1. Traslación en la cuantificación existencial . . . . . . . .. . . . . . . 120 6.3.2. Distributividad en la cuantificación existencial . . . . . . . . . . . . 120 6.3.3. Manipulación de rango y término con el cuantificador existencial . . 121 6.3.4. Introducción del operador existencial e intercambio . . . . . . . . . . 121 6.3.5. Testigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.4. Del lenguaje corriente al cálculo depredicados . . . . . . . . . . . . . . . 123 6.4.1. Razonamientos en matemática . . . . . . . . . . . . . . . . . . . . . 125 6.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.5.1. Ejercicios sobre cuantificación existencial . . . . . . . . . . . . . . . 128 6.5.2. Ejercicios sobre traducción entre cálculo de predicados y lenguaje corriente129

Introduciremos los conceptos referentes al Cálculo de Predicados, lo cual no es más que una extensión del Cálculo Proposicional que ya vimos en el Capítulo 3. Esta extensión nos permitirá trabajar con expresiones que usen variables de otro tipo además del tipo booleano y nos 111

112

6. C ÁLCULO

DE

P REDICADOS

6.2. E L

CUANTIFICADOR UNIVERSAL

113

conducirá a un sistema formal queabarque una mayor cantidad de expresiones y poder deductivo.

todo x que satisfaga R se satisface P ”. Vamos a repasar ahora los axiomas vistos en el capítulo anterior para el caso particular del cuantificador universal. Rango vacío (∀ i : f alse : T.i) ≡ true Rango unitario Si i no es una variable libre en la expresión N, entonces (∀ i : i = N : T.i) ≡ T.N Distributividad Como el operador ∨ esdistributivo a derecha e izquierda con respecto al operador ∧, y true es absorbente para ∨, vale (∀ i : R.i : x ∨ T.i) ≡ x ∨ (∀ i : R.i : T.i) (∀ i : R.i : T.i ∨ x) ≡ (∀ i : R.i : T.i) ∨ x (6.2) (6.3)

6.1. Predicados y Cálculo de Predicados
El Cálculo Proposicional nos permitió razonar con fórmulas construídas con variables y operadores booleanos, con lo cual nos fue posible expresar afirmaciones ofrases que pueden modelizarse utilizando expresiones de tipo booleano. El Cálculo de Predicados nos permitirá ampliar el espectro, trabajando con fórmulas de diversos tipos además del booleano. La construcción de fórmulas que veremos en este cálculo nos obliga a definir nuevas expresiones llamadas predicados. Un predicado es una aplicación de una función booleana cuyos argumentos pueden ser dediferentes tipos, es decir un predicado puede ser una función de tipo Z → B como la función par.i o Z × Z → B como la función igual(x, x − z + z) o menor(x, y + z). Los nombres de las funciones (igual, menor) son llamados símbolos de predicados. También utilizamos la notación x < y para expresar el predicado menor(x, y). Por ejemplo, la siguiente expresión x < y ∧ x = z ⇒ q(x, z + x) contiene trespredicados, x < y, x = z y q(x, x + z). Vemos que los argumentos de los predicados son en este caso, variables de tipo distinto de B o también expresiones de éstos tipos. Los argumentos de un predicado son llamados términos, por ejemplo en la fórmula anterior los términos en los predicados son x, y, z y z + x. Diremos que una fórmula del cálculo de predicados es una expresión booleana en la cual...