Apuntes de L´ogica Matem´atica 2. L´ogica de Predicados

Francisco Jos´e Gonz´alez Guti´errez C´adiz, Abril de 2005

Universidad de C´ adiz

Departamento de Matem´ aticas

ii

Lecci´ on 2

L´ ogica de Predicados Contenido 2.1

2.2

2.3

2.1

Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.1.1

Predicado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.1.2

Universo del Discurso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.1.3

Predicados y Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

2.2.1

Cuantificador Universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

2.2.2

Valor de Verdad del Cuantificador Universal . . . . . . . . . . . . . . . . . . . .

37

2.2.3

Cuantificador Existencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

2.2.4

Valor de Verdad del Cuantificador Existencial . . . . . . . . . . . . . . . . . . .

37

2.2.5

Alcance de un Cuantificador

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

C´ alculo de Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

2.3.1

Implicaci´ on L´ ogica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

2.3.2

Equivalencia L´ ogica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

2.3.3

Leyes de De Morgan Generalizadas . . . . . . . . . . . . . . . . . . . . . . . . .

46

2.3.4

Regla general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

2.3.5

Proposiciones al Alcance de un Cuantificador . . . . . . . . . . . . . . . . . . .

49

2.3.6

Predicados al Alcance de un Cuantificador . . . . . . . . . . . . . . . . . . . . .

52

2.3.7

Asociatividad y Distributividad . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

Definiciones

Cualquier teor´ıa cient´ıfica aspira a enunciar leyes, postulados, definiciones, teoremas, etc... con una validez m´as o menos universal y, en cualquier caso, bien precisada. A menudo interesa afirmar que todos los individuos de un cierto campo tienen la propiedad p o que algunos la tienen. El c´alculo proposicional no es suficientemente fuerte para hacer todas las afirmaciones que se necesitan en matem´aticas. Por ejemplo, afirmaciones como “x = 5” ´o “x > y” no son proposiciones ya que no son necesariamente verdaderas o falsas. Sin embargo, asignando valores concretos a las variables x e y, las afirmaciones anteriores son susceptibles de ser verdaderas o falsas, es decir, se convierten en proposiciones. En castellano tambi´en ocurren situaciones similares, por ejemplo, 27

Universidad de C´ adiz

Departamento de Matem´ aticas Ella es alta y rubia. El vive en el campo.

Ella, ´el y el campo se utilizan como variables, x es alta y rubia. x vive en y

2.1.1

Predicado

Es una afirmaci´ on que expresa una propiedad de un objeto o una relaci´ on entre objetos. Estas afirmaciones se hacen verdaderas o falsas cuando se reemplazan las variables (objetos) por valores espec´ıficos. Ejemplo 2.1 La afirmaci´ on “p(x) : x es alta y rubia” es un predicado que expresa la propiedad del objeto x de ser “alta y rubia”. Si sustituimos la variable x por un valor determinado, por ejemplo Laura, entonces el predicado se transforma en la proposici´on “Laura es alta y rubia” que podr´a ser verdadera o falsa. El predicado “q(x) : x vive en y” expresa una relaci´on entre los objetos x e y. Si sustituimos x  por Pedro e y por Madrid, obtendremos la proposici´on “Pedro vive en Madrid”. Ejemplo 2.2 Los predicados se usan frecuentemente en sentencias de control en lenguajes de programaci´on de alto nivel. Por ejemplo, la sentencia Si x > 5, entonces z := y incluye el predicado “x > 5”. Cuando se ejecuta la sentencia, el valor de verdad de la afirmaci´on “x > 5” se determina usando el valor que tenga la variable x en ese momento. El predicado se convierte en una proposici´on cuyo valor verdadero es verdad o falso.  Ejemplo 2.3

2.1.2

El predicado “p(x, y) : x + y > 5” tiene dos variables.

Universo del Discurso

Llamaremos de esta forma al conjunto al cual pertenecen los valores que puedan tomar las variables. Lo notaremos por U y lo nombraremos por conjunto universal o, simplemente, universo. Debe contener, al menos, un elemento. Ejemplo 2.4 En una posible evaluaci´ on del predicado “p(x) : x > 5”, elegir´ıamos probablemente un conjunto num´erico, por ejemplo los n´ umeros enteros, como universo del discurso. No tendr´ıa sentido elegir el conjunto de los colores del arco iris ya que podr´ıamos encontrarnos con situaciones tales como “azul > 5”. 

2.1.3

Predicados y Proposiciones

Si p(x1 , x2 , . . . , xn ) es un predicado constante con n variables y asignamos los valores c1 , c2 , . . . , cn a cada una de ellas, el resultado es la proposici´ on p(c1 , c2 , . . . , cn ). Para transformar un predicado en proposici´on, cada variable del predicado debe estar “ligada”. 28

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

Ejemplo 2.5 Consideremos el predicado p(x, y) : x + y = 5 en el universo de los n´ umeros enteros. En principio las variables x e y pueden tomar cualquier valor entero, es decir est´an “libres”. Si asignamos a x el valor 2 y a la y el valor 3, entonces el predicado p(x, y) se transforma en la proposici´ on p(2, 3) : 2 + 3 = 5 que es verdad. Si hubi´eramos asignado los valores 1 y 2 a las variables x e y, respectivamente, entonces resultar´ıa la proposici´ on p(1, 2) : 1 + 2 = 5 que es falsa. En ambos casos, las variables x e y han pasado de estar libres a estar ligadas. Hemos ligado las variables asign´andoles unos valores determinados del universo del discurso.  Ejemplo 2.6 Las variables enteras x e y tienen los valores iniciales 3 y 8, respectivamente. Determinar los valores de x e y despu´es de la ejecuci´ on de cada una de las proposiciones siguientes. (El valor de x despu´es de la ejecuci´ on de (a) se convierte en el valor de x para la proposici´on del apartado (b) y as´ı sucesivamente). (La operaci´ on Div devuelve la parte entera de un cociente; por ejemplo, 8 Div 4=2 y 9 Div 2=4). (a) Si y − x = 5, entonces x = x − 2; (b) Si [(2y = x) y (x Div 4 = 1)], entonces x = 4y − 3; (c) Si [(x < 8) ´ o (y Div 2 = 2)], entonces x = 2y, de lo contrario y = 2x; (d) Si [(x < 20) y (x Div 6 = 1)], entonces y = y − x − 5; (e) Si [(x = 2y) ´ o (x Div 2 = 5)], entonces y = y + 2; (f) Si [(x Div 3 = 3) e (y Div 3 6= 1)] entonces y = x; (g) Si yx 6= 35, entonces x = 3y + 7; Soluci´on Los valores iniciales son x:=3, y:=8 (a) y − x = 5 −→ x := x − 2; y − x = 8 − 3 = 5, es decir la hip´ otesis es verdadera. Consecuentemente se sigue la conclusi´on y x := x − 2 = 3 − 2 = 1. Los nuevos valores de x e y son, por tanto, x:=1, y:=8 (b) (2y = x) ∧ (x Div 4 = 1) −→ x := 4y − 3; 2y = x es falsa y x Div 4 tambi´en (1 Div 4 = 0), luego (2y = x) ∧ (x Div 4) es falsa y, consecuentemente, no se sigue la conclusi´on. Los valores de x e y siguen siendo los mismos que en el apartado anterior. (c) (x < 8) ∨ (y Div 2 = 2) −→ x := 2y, de lo contrario y := 2x; x < 8 es verdadera y y Div 2 = 2 es falsa (8 Div 2 = 4) luego (x < 8) ∨ (y Div 2 = 2) es verdad y, consecuentemente, se sigue la primera de las dos conclusiones, de aqu´ı que los nuevos valores de x e y sean x:=16, y:=8 29

Universidad de C´ adiz

Departamento de Matem´ aticas

(d) (x < 20) ∧ (x Div 6 = 1) −→ y := y − x − 5; x < 20 es verdad y x Div 2 = 5 es falsa, luego (x < 20) ∧ (x Div 6 = 1) es falsa y, consecuentemente, no se sigue la conclusi´on, es decir, los valores de x e y no var´ıan. (e) (x = 2y) ∨ (x Div 2 = 5) −→ y := y + 2; x = 2y es verdad y x Div 2 = 5 es falsa, luego la hip´otesis, (x = 2y) ∨ (x Div 2 = 5) es verdadera y, consecuentemente, y := y + 2 = 8 + 2 = 10. Los nuevos valores de x e y son, por tanto, x:=16, y:=10 (f) (x Div 3 = 3) ∧ (y Div 3 6= 1) −→ y := x; x Div 3 = 3 es falsa e y Div 3 6= 1 es verdadera, por lo tanto la hip´otesis (x Div 3 = 3) ∧ (y Div 3 6= 1) es falsa y los valores de x e y no cambian. (g) yx 6= 35 =⇒ x := 3y + 7; Como yx = 10 · 16 = 160 6= 35, la hip´otesis es verdadera de aqu´ı que se siga la conclusi´on y x := 3y + 7 = 3 · 10 + 7 = 37. Los valores finales de x e y son, por tanto, x:=37, y:=10  Nota 2.1 En los lenguajes de programaci´on, aparecen estructuras de decisi´on del tipo “Si...Entonces”. En este contexto, el condicional “si p entonces q” significa que se ejecutar´a q u ´nicamente en caso de que p sea verdadera. Si p es falsa, el control pasa a la siguiente instrucci´on del programa.  Ejemplo 2.7 Para cada segmento de programa contenido en los apartados siguientes, determinar el n´ umero de veces que se ejecuta la sentencia x := x + 1 (a)

y := 1 Si y < 2 ´ o y > 0 entonces x := x + 1 de lo contrario x := x + 2

(b)

y := 2 Si (y < 0 e y > 1) ´ o y = 3 entonces x := x + 1 de lo contrario x := x + 2

(c)

y := 1 Hacer mientras y < 3 Comienzo x := x + 1 30

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

y := y + 1 Fin (d)

y := 1 Hacer mientras (y > 0 e y < 3) ´ oy=3 Comienzo x := x + 1 y := y + 1 Fin

(e)

y := 1 Hacer mientras y > 0 e y < 4 Comienzo Si y < 2 entonces y := y + 1 de lo contrario y := y + 2 x := x + 1 Fin

Soluci´on (a) Sean p(y) : y < 2 q(y) : y > 0 Otra forma de escribir el segmento de programa propuesto ser´ıa y:=1 Si p(y) ∨ q(y) es verdad entonces x := x + 1 Si p(y) ∨ q(y) es falso entonces x := x + 2 Como el valor de y es 1, ambos predicados se convierten en proposiciones verdaderas, por lo tanto p(y) ∨ q(y) es verdad y la sentencia x := x + 1 se ejecuta una vez. (b) Sean p(y) : y < 0 q(y) : y > 1 r(y) : y = 3 Otra forma de escribir el segmento de programa propuesto ser´ıa: y := 2 Si [p(y) ∧ q(y)] ∨ r(y) es verdad entonces x := x + 1 Si [p(y) ∧ q(y)] ∨ r(y) es falso entonces x := x + 2 31

Universidad de C´ adiz

Departamento de Matem´ aticas

Pues bien, para que [p(y) ∧ q(y)] ∨ r(y) sea una proposici´on verdadera, bastar´a con que lo sea una de las dos. Como el valor de y es 2, r(y) ser´a una proposici´on falsa, de aqu´ı que tenga que ser verdad la conjunci´ on p(y) ∧ q(y) para lo cual lo tendr´an que serlo ambas, lo cual es imposible ya que cuando p(y) sea verdad, q(y) ser´ a falsa y viceversa. Consecuentemente, la sentencia x := x + 1 no se ejecuta ninguna vez. (c) Sea p(y) : y < 3. Entonces, el segmento de programa propuesto ser´a y := 1 Hacer mientras p(y) sea verdad Comienzo x := x + 1 y := y + 1 Fin El predicado p(y) ser´ a una proposici´on verdadera para aquellos valores de y que sean estrictamente menores que 3 y dado que el valor inicial de y es 1 y aumenta en una unidad (y := y + 1) cada vez que se ejecutan las sentencias entre comienzo y fin, la sentencia x := x + 1 se ejecutar´a dos veces. (d) Sean p(y) : y > 0 q(y) : y < 3 r(y) : y = 3 Utilizando notaci´ on l´ ogica, el segmento de programa propuesto se escribir´a: y := 1 Hacer mientras [p(y) ∧ q(y)] ∨ r(y) sea verdad Comienzo x := x + 1 y := y + 1 Fin Pues bien, los valores de y que hacen del predicado [p(y) ∧ q(y)] ∨ r(y) una proposici´on verdadera ser´an aquellos que conviertan en proposiciones verdaderas, al menos, a uno de los dos predicados, [p(y) ∧ q(y)] ´ o r(x). Los valores de la variable y que hacen de p(y) ∧ q(y) una proposici´on verdadera son aquellos que hacen proposiciones verdaderas a los dos predicados p(y) y q(y), es decir y > 0 e y < 3, o lo que es igual y = 1 ´ o y = 2. Para que el predicado r(y) sea una proposici´on verdadera, la variable y ha de valer 3. Consecuentemente, [p(y) ∧ q(y)] ∨ r(y) es verdad para y =1∨y =2∨y =3 Dado que el valor inicial de y es 1 y aumenta en una unidad cada vez que se ejecuta comienzo...fin, la sentencia x := x + 1 se ejecutar´ a tres veces. (e) Sean p(y) : y > 0 q(y) : y < 4 r(y) : y < 2 Podemos escribir el segmento de programa en la forma: 32

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

y := 1 Hacer mientras p(y) ∧ q(y) sea verdad Comienzo Si r(y) es verdad entonces y := y + 1 Si ¬r(y) es verdad entonces y := y + 2 x := x + 1 Fin El primer y el segundo condicional entre comienzo y fin se ejecutar´an para los valores de la variable y que hagan de los predicados p(y) ∧ q(y) ∧ r(y) y p(y) ∧ q(y) ∧ ¬r(y), respectivamente, proposiciones verdaderas. Pues bien, p(y) ∧ q(y) ∧ r(y) : (y > 0) ∧ (y < 4) ∧ (y < 2) es decir, p(y) ∧ q(y) ∧ r(y) : y = 1 y p(y) ∧ q(y) ∧ ¬r(y) : (y > 0) ∧ (y < 4) ∧ (y > 2) o sea, p(y) ∧ q(y) ∧ ¬r(y) : (y = 2) ∨ (y = 3) Como el valor inicial es y = 1, se ejecutar´a el primer condicional y el valor de y ser´a 2. La segunda vez se ejecutar´ a el segundo condicional, la sentencia x := x + 1 y la variable y toma el valor 4 que ya no verifica la condici´ on inicial, con lo que el programa termina. Consecuentemente, la sentencia x := x + 1 se ejecuta una vez. Ejemplo 2.8

¿Cu´ antas veces se imprime el valor de x en el siguiente programa?

x := 10 y := 1 Hacer mientras y 6 7 Comienzo z := 1 Hacer mientras z 6 y + 3 Comienzo Si [(x > 8) ´ o ((y > 5) y (z < 10))] entonces imprimir x z := z + 1 Fin x := x − 1 y := y + 1 Fin Soluci´on Sean p(y) : y 6 7 33



Universidad de C´ adiz

Departamento de Matem´ aticas

q(z, y) : z 6 y + 3 r(x) : x > 8 s(y) : y > 5 t(z) : z < 10 los predicados cuyas variables son x, y, z perteneciendo las tres al universo de los enteros positivos. Utilizando estos predicados, el programa podr´a escribirse en la forma: x := 10 y := 1 Hacer mientras p(y) sea verdad Comienzo z := 1 Hacer mientras q(z, y) sea verdad Comienzo Si [r(x) ∨ (s(y) ∧ t(z))] es verdad entonces imprimir x z := z + 1 Fin x := x − 1 y := y + 1 Fin La variable x se imprimir´ a para los valores de x, y, z que hagan que el predicado [p(y) ∧ q(z, y)] ∧ [r(x) ∨ (s(y) ∧ t(z))] sea una proposici´ on verdadera. Aplicando la distributividad de ∧ respecto de ∨, obtendremos [p(y) ∧ q(z, y) ∧ r(x)] ∨ [p(y) ∧ q(z, y) ∧ s(y) ∧ t(z)] que ser´a una proposici´ on verdadera para los valores de las variables que hagan verdadera, al menos, a una de las dos. Pues bien, p(y) ∧ q(z, y) ∧ r(x) ser´ a verdad u ´nicamente para aquellos valores de x, y, z que hagan de los tres predicados, tres proposiciones verdaderas. Si observamos los valores iniciales de las tres variables, p(y) ser´a verdad siete veces y por cada una de ellas, q(z, y) ser´ a verdad y + 3 veces. Sin embargo, la variable x s´olo puede tomar dos valores. En efecto, como su valor inicial es 10, tendremos x := 10 ∧ r(x) : x > 8 de donde resulta que r(x) : (x = 9) ∨ (x = 10) Por lo tanto, p(y) ∧ q(z, y) ∧ r(x) ⇐⇒ [p(y) ∧ q(z, y) ∧ (x = 10)] ∨ [p(y) ∧ q(z, y) ∧ (x = 9)] Ahora bien, para x = 10 y para x = 9, la variable y toma los valores 1 y 2, respectivamente, luego p(y) ∧ q(z, y) ∧ r(x) ⇐⇒ [p(1) ∧ q(z, 1) ∧ (x = 10)] ∨ [p(2) ∧ q(z, 2) ∧ (x = 9)] Como p(1) : 1 6 7 y p(2) : 2 6 7 son verdad siempre, las dos proposiciones entre corchetes ser´an verdad cuando lo sean q(z, 1) y q(z, 2), respectivamente. Resumiendo p(y) ∧ q(z, y) ∧ r(x) ⇐⇒ q(z, 1) ∨ q(z, 2) ⇐⇒ (z 6 4) ∨ (z 6 5) 34

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

Por otra parte, p(y) ∧ q(z, y) ∧ s(y) ∧ t(z) al igual que la anterior, ser´a verdad u ´nicamente para los valores de las variables que hagan de los cuatro predicados, cuatro proposiciones verdaderas. Ahora bien, observemos lo siguiente: p(y) ∧ s(y) ⇐⇒ (y 6 7) ∧ (y > 5) ⇐⇒ (y = 6) ∨ (y = 7) luego, p(y) ∧ q(z, y) ∧ s(y) ∧ t(z) ⇐⇒

[(y = 6) ∧ q(z, y) ∧ t(z)] ∨ [(y = 7) ∧ q(z, y) ∧ t(z)]

⇐⇒

[q(z, 6) ∧ t(z)] ∨ [q(z, 7) ∧ t(z)]

⇐⇒

[q(z, 6) ∧ (z < 10)] ∨ [q(z, 7) ∧ (z < 10)]

⇐⇒

[(z 6 9) ∧ (z < 10)] ∨ [(z 6 10) ∧ (z < 10)]

⇐⇒

(z 6 9) ∨ (z 6 9)

En definitiva, [p(y) ∧ q(z, y) ∧ r(x)] ∨ [p(y) ∧ q(z, y) ∧ s(y) ∧ t(z)] =⇒ (z 6 4) ∨ (z 6 5) ∨ (z 6 9) ∨ (z 6 9) Luego x se imprime un total de veintisiete veces.

2.2



Cuantificadores

Otra forma de ligar las variables individuales es cuantificarlas.

2.2.1

Cuantificador Universal

Si p(x) es un predicado cuya variable es x, entonces la afirmaci´ on “para todo x, p(x)” es una proposici´ on en la cual se dice que la variable x est´ a universalmente cuantificada. La frase “para todo” se simboliza con ∀, s´ımbolo que recibe el nombre de “cuantificador universal”. As´ı pues, “para todo x, p(x)” se escribe “ ∀x, p(x)”. El s´ımbolo ∀x puede interpretarse tambi´en como “para cada x”, “para cualquier x” y “para x arbitrario”. Ejemplo 2.9 En el universo del discurso de los n´ umeros enteros, la proposici´on “todo n´ umero es  estrictamente menor que el siguiente” puede escribirse en la forma ∀x, x < x + 1. Ejemplo 2.10 Sean p(x, y, z) : xy = z, q(x, y) : x = y y r(x, y) : x > y y sea el universo del discurso U , el conjunto de los n´ umeros enteros. Transcribir las siguientes proposiciones a notaci´on l´ogica. (a) Si y = 1, entonces xy = x para cualquier x. (b) Si xy 6= 0, entonces x 6= 0 e y 6= 0. (c) Si xy = 0, entonces x = 0 ´ o y = 0. (d) 3x = 6 si, y s´ olo si x = 2. (e) No existe soluci´ on para x2 = y, a menos que y > 0. (f) x < z es una condici´ on necesaria para que x < y e y < z. 35

Universidad de C´ adiz

Departamento de Matem´ aticas

(g) x 6 y e y 6 x es una condici´ on suficiente para que y = x. (h) Si x < y y z < 0, entonces xz > yz. (i) No es cierto que x = y y x < y. (j) Si x < y, entonces para alg´ un z tal que z < 0, xz > yz. (k) Existe un x tal que para cada y y z, es xy = xz. Soluci´on (a) Si y = 1, entonces xy = x para cualquier x. ∀y [q(y, 1) −→ ∀x, p(x, y, x)] (b) Si xy 6= 0, entonces x 6= 0 e y 6= 0. ∀x, ∀y [¬p(x, y, 0) −→ ¬q(x, 0) ∧ ¬q(0, y)] (c) Si xy = 0, entonces x = 0 ´ o y = 0. ∀x, ∀y [p(x, y, 0) −→ q(x, 0) ∨ q(0, y)] (d) 3x = 6 si, y s´ olo si x = 2. ∀x [p(3, x, 6) ←→ q(x, 2)] (e) No existe soluci´ on para x2 = y, a menos que y > 0. ∀y [r(0, y) −→ ¬∃x : p(x, x, y)] (f) x < z es una condici´ on necesaria para que x < y e y < z. ∀x, ∀y, ∀z [r(y, x) ∧ r(z, y) −→ r(z, x)] (g) x 6 y e y 6 x es una condici´ on suficiente para que y = x. ∀x, ∀y [¬r(x, y) ∧ ¬r(y, x) −→ q(x, y)] (h) Si x < y y z < 0, entonces xz > yz. ∀x, ∀y, ∀z [r(y, x) ∧ r(0, z) −→ ∀u, ∀v (p(x, z, u) ∧ p(y, z, v)) −→ r(u, v)] (i) No es cierto que x = y y x < y. ∀x, ∀y [¬q(x, y) ∧ r(y, x)] (j) Si x < y, entonces para alg´ un z tal que z < 0, xz > yz. ∀x, ∀y [r(y, x) −→ ∃z : (r(0, z) ∧ ∀u, ∀v (p(x, z, u) ∧ p(y, z, v) −→ r(u, v)))] (k) Existe un x tal que para cada y y z, es xy = xz. ∃x : [∀y, ∀z, ∀u, ∀v (p(x, y, u) ∧ p(x, z, v) −→ q(u, v))]  36

L´ ogica Matem´ atica

2.2.2

Francisco Jos´e Gonz´ alez Guti´errez

Valor de Verdad del Cuantificador Universal

Sea p(x) un predicado cuya variable x toma valores en un universo del discurso U . ∀x, p(x) es verdad si el predicado p(x) es una proposici´ on verdadera para todos los valores de x en el universo U . ∀x, p(x) es falsa si hay, al menos, un valor de x en U para el cual el predicado p(x) sea una proposici´ on falsa. Ejemplo 2.11 afirmaciones:

Estudiar en el universo de los n´ umeros enteros, el valor de verdad de las siguientes

(a) ∀x, x < x + 1 (b) ∀x, x = 5 Soluci´on (a) ∀x, x < x + 1 El predicado p(x) : x < x + 1 es una proposici´on verdadera si sustituimos x por cualquier n´ umero entero, luego la proposici´ on cuantificada ∀x, x < x + 1 es verdad. (b) ∀x, x = 5 Esta proposici´ on dice que “todos los n´ umeros enteros son iguales a 5”. Pues bien, el predicado p(x) : x = 5 es una proposici´ on falsa, por ejemplo, para x = 1, luego la proposici´on cuantificada ∀x, x = 5 es falsa. 

2.2.3

Cuantificador Existencial

Si p(x) es un predicado cuya variable es x, entonces la afirmaci´ on “existe un x tal que p(x)” es una proposici´ on en la que diremos que la variable x est´ a existencialmente cuantificada. La frase “existe [al menos]” se simboliza con ∃, s´ımbolo que recibe el nombre de cuantificador existencial. Por tanto, “existe un x, tal que p(x)” se escribe “∃x : p(x)” y puede leerse tambi´en como “para alg´ un x, p(x)” o “existe, al menos, un x, tal que p(x)”.

2.2.4

Valor de Verdad del Cuantificador Existencial

Sea p(x) un predicado de variable x que toma valores en un universo del discurso U . ∃x : p(x) es verdadera, si el predicado p(x) es una proposici´ on verdadera para, al menos, uno de los valores de x en U . ∃x : p(x) es falsa, si el predicado p(x) es una proposici´ on falsa para todos los valores de x en U . Nota 2.2

Un cuadro resumen de los valores de verdad de los cuantificadores podr´ıa ser el siguiente:

∀x, p(x)

Verdad p(x) es verdad para cada x

Falso p(x) es falsa para, al menos, un x

∃x : p(x)

p(x) es verdad para, al menos, un x

p(x) es falsa para todos los valores de x

37

Universidad de C´ adiz Ejemplo 2.12 siguientes:

Departamento de Matem´ aticas

Estudiar en el conjunto de los n´ umeros enteros, el valor de verdad de las afirmaciones

(a) ∃x : x < x + 1 (b) ∃x : x = 5 (c) ∃x : x = x + 1 Soluci´on (a) ∃x : x < x + 1 La proposici´ on es “existe, al menos, un entero que es menor que el siguiente”. El predicado p(x) : x < x + 1 es una proposici´on verdadera para cualquier entero x, por tanto, la proposici´ on cuantificada es verdad. (b) ∃x : x = 5 La traducci´ on de la proposici´ on al lenguaje ordinario es “existe, al menos, un entero igual a 5”. El predicado p(x) : x = 5 es una proposici´on verdadera cuando x toma el valor 5, luego la proposici´ on cuantificada es verdad. (c) ∃x : x = x + 1 La proposici´ on es “existe, al menos, un n´ umero entero que es igual al siguiente” El predicado p(x) : x = x + 1 es una proposici´on falsa para cualquier n´ umero entero x, por tanto la proposici´ on cuantificada es falsa. 

2.2.5

Alcance de un Cuantificador

En una expresi´ on ∀x [p(x) . . .] o ∃x : [p(x) . . .], la porci´ on de la expresi´ on a la que se aplica ∀x ´ o ∃x se llama alcance del cuantificador y se indicar´ a entre corchetes a menos que sea evidente. Ejemplo 2.13 En cada una de las expresiones simb´olicas siguientes, describir el alcance de cada cuantificador y decir que variables est´ an ligadas y cu´ales est´an libres. (a) ∀x [p(x) ∧ ∃y : (t(x, y) ∧ r(x))] (b) ¬∃x : [p(x) ∧ ∃y : (t(x, y) ∨ r(z))] (c) ¬∃x : [p(x) ∧ ∃y : (t(x, y) ∨ r(y))] Soluci´on (a) El alcance de ∀ es toda la f´ ormula. El alcance de ∃ es la f´ormula (t(x, y) ∧ r(x)). La variable x est´a ligada por el cuantificador ∀ y la y por el ∃, luego no hay variables libres. (b) El alcance de ¬∃ es el resto de la f´ ormula y el alcance de ∃ es t(x, y) ∨ r(z). La variable z est´a libre, pero x e y est´ an ligadas por el cuantificador ∃. (c) Los alcances son los mismos que en (b). La y en r(y) est´a libre, pero en t(x, y) est´a ligada.



Ejemplo 2.14 Consideremos el universo de los n´ umeros enteros y sea p(x, y, z) el predicado x − y = z. Transcribir las siguientes afirmaciones a notaci´on l´ogica. 38

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

(a) Para cada x e y, existe alg´ un z tal que x − y = z. (b) Para cada x e y, existe alg´ un z tal que x − z = y. (c) Existe un x tal que para todo y, y − x = y. (d) Cuando el 0 se resta de cualquier entero, el resultado es el entero original. (e) 3 restado de 5 da 2. Soluci´on (a) Para cada x e y, existe alg´ un z tal que x − y = z. ∀x [∀y(∃z : p(x, y, z))] (b) Para cada x e y, existe alg´ un z tal que x − z = y. ∀x [∀y(∃z : p(x, z, y))] (c) Existe un x tal que para todo y, y − x = y. ∃x : [∀y, p(y, x, y)] (d) Cuando el 0 se resta de cualquier entero, el resultado es el entero original. ∀x, p(x, 0, x) (e) 3 restado de 5 da 2. p(5, 3, 2)  Ejemplo 2.15 Sean p(x, y, z), q(x, y, z) y r(x, y) los predicados “x + y = z”, “x · y = z” y “x < y”, respectivamente. Expresar en el universo de los n´ umeros enteros no negativos las afirmaciones siguientes: (a) Para cada x e y, existe un z tal que x + y = z. (b) Ning´ un x es menor que cero. (c) Para todo x es x + 0 = x. (d) Para todo x, x · y = y para todo y. (e) Existe un x tal que x · y = y para cada y. Soluci´on (a) ∀x [∀y(∃z : p(x, y, z))] (b) ∀x [¬r(x, 0)] o bien, ¬∃x : r(x, 0) (c) ∀x, p(x, 0, x) (d) ∀x [∀y, q(x, y, y)] (e) ∃x : [∀y, q(x, y, y)]

 39

Universidad de C´ adiz

Departamento de Matem´ aticas

Ejemplo 2.16 Determinar cu´ ales de las siguientes proposiciones cuantificadas son verdad si el universo es el conjunto de los n´ umeros enteros. (a) ∀x [∃y : (x · y = 0)] (b) ∃y : [∀x (x · y = 1)] (c) ∃y : [∀x (x · y = x)] Soluci´on (a) ∀x [∃y : (x · y = 0)] “Dado cualquier n´ umero entero, existe otro tal que el producto de ambos es cero” La proposici´ on ∃y : x · y = 0 es verdad para cualquier entero x ya que bastar´ıa tomar y = 0. Por lo tanto, ∀x [∃y : (x · y = 0)] es una proposici´ on verdadera. (b) ∃y : [∀x (x · y = 1)] “Puede encontrarse un n´ umero entero tal que su producto por cualquier entero sea 1” La proposici´ on ∀x, x · y = 1 es falsa ya que bastar´ıa tomar x 6= 1 para que x · y 6= 1 cualquiera que sea el y que se elija. Por lo tanto, la proposici´ on ∃y : [∀x (x · y = 1)] es falsa. (c) ∃y : [∀x (x · y = x)] “Existe, al menos, un n´ umero entero tal que al multiplicarlo por cualquier entero lo deja igual”. La proposici´ on ∀x, x · y = x ser´a verdadera o falsa dependiendo del y que elijamos. En particular, si tomamos y = 1, la proposici´ on ∀x, x · y = x es verdad para todos los enteros. Consecuentemente, ∃y : [∀x (x · y = x)] es una proposici´ on verdadera.



Nota 2.3 Una afirmaci´ on con variables cuantificadas se puede expresar mediante las proposiciones que se obtienen asignando valores a las variables de los predicados que ocurren en la afirmaci´on. − Si el universo del discurso es finito esta relaci´on puede hacerse expl´ıcita. Por ejemplo, supongamos que el universo consiste en los enteros 1,2,3 y 4, entonces la proposici´on: ∀x, p(x) equivale a la proposici´ on p(1) ∧ p(2) ∧ p(3) ∧ p(4) y la proposici´ on ∃x : p(x) es equivalente a la p(1) ∨ p(2) ∨ p(3) ∨ p(4) 40

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

− Si el universo del discurso es infinito una proposici´on con cuantificadores no puede representarse siempre por un n´ umero finito de conjunciones o disyunciones de proposiciones sin cuantificadores. Sin embargo, podemos extender el concepto y a veces es conveniente expresar una afirmaci´on universal o existencialmente cuantificada como una conjunci´on o disyunci´on infinita, respectivamente. Por ejemplo, consideremos como universo del discurso el conjunto de los n´ umeros enteros no negativos y sea p(x) el predicado “x > 4”. Entonces, la proposici´on, ∀x, p(x) puede interpretarse como la conjunci´on infinita p(0) ∧ p(1) ∧ p(2) ∧ p(3) ∧ p(4) ∧ · · · la cual es falsa ya que, por ejemplo, p(0) es falsa. Asimismo, la proposici´ on ∃x : p(x) puede interpretarse como la disyunci´on infinita p(0) ∨ p(1) ∨ p(2) ∨ p(3) ∨ p(4) ∨ · · · la cual es verdad, ya que al menos uno de los operandos, por ejemplo p(5), es verdad.



Ejemplo 2.17 Sea el universo del discurso U = {0, 1}. Encontrar conjunciones y disyunciones finitas de proposiciones que no usen cuantificadores y que sean equivalentes a las siguientes: (a) ∀x, p(0, x) (b) ∀x [∀y, p(x, y)] (c) ∀x [∃y : p(x, y)] (d) ∃x : [∀y, p(x, y)] (e) ∃y [∃x : p(x, y)] Soluci´on (a) ∀x, p(0, x) La forma equivalente pedida es p(0, 0) ∧ p(0, 1) (b) La proposici´ on cuantificada ∀x [∀y (p(x, y))] puede expandirse en la forma: [∀y, p(0, y)] ∧ [∀y, p(1, y)] la cual puede interpretarse como [p(0, 0) ∧ p(0, 1)] ∧ [p(1, 0) ∧ p(1, 1)] que por la asociatividad de ∧ equivale a p(0, 0) ∧ p(0, 1) ∧ p(1, 0) ∧ p(1, 1) (c) Expandimos la proposici´ on ∀x [∃y : p(x, y)] a [∃y : p(0, y)] ∧ [∃y : p(1, y)] 41

Universidad de C´ adiz

Departamento de Matem´ aticas

la cual equivale a [p(0, 0) ∨ p(0, 1)[ ∧ [p(1, 0) ∨ p(1, 1)] y aplicando la distributividad de ∧ respecto de ∨, [(p(0, 0) ∨ p(0, 1)) ∧ p(1, 0)] ∨ [(p(0, 0) ∨ p(0, 1)) ∧ p(1, 1)] es decir, (p(0, 0) ∧ p(1, 0)) ∨ (p(0, 1) ∧ p(1, 0)) ∨ (p(0, 0) ∧ p(1, 1)) ∨ (p(0, 1) ∧ p(1, 1)) (d) ∃x : [∀y, p(x, y)] se expande en la forma: [∀y, p(0, y)] ∨ [∀y, p(1, y)] la cual equivale a la proposici´ on [p(0, 0) ∧ p(0, 1)] ∨ [p(1, 0) ∧ p(1, 1)] y por la distributividad de ∨ respecto de ∧, [(p(0, 0) ∧ p(0, 1)) ∨ p(1, 0)] ∧ [(p(0, 0) ∧ p(0, 1)) ∨ p(1, 1)] es decir, (p(0, 0) ∨ p(0, 1)) ∧ (p(0, 1) ∨ p(1, 0)) ∧ (p(0, 0) ∨ p(1, 1)) ∧ (p(0, 1) ∨ p(1, 1)) (e) La proposici´ on con cuantificadores ∃y [∃x : p(x, y)] puede expandirse a: [∃x : p(x, 0)] ∨ [∃x : p(x, 1)] que es equivalente a la proposici´ on, p(0, 0) ∨ p(1, 0) ∨ p(0, 1) ∨ p(1, 1)  En el ejemplo siguiente veremos como el orden en que se ligan las variables es vital y puede afectar profundamente el significado de una afirmaci´on. Ejemplo 2.18 siguientes:

Si el universo del discurso es el conjunto de las personas casadas, evaluar las afirmaciones

(a) ∀x [∃y : (x est´ a casada con y)] (b) ∃y : [∀x (x est´ a casada con y)] Si el universo es el conjunto de los n´ umeros enteros, evaluar: (c) ∀x [∃y : (x + y = 0)] (d) ∃y : [∀x (x + y = 0)] Soluci´on Los cuantificadores se eval´ uan de izquierda a derecha. 42

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

(a) ∀x [∃y : (x est´ a casada con y)] La transcripci´ on de la proposici´ on es “para cada persona que elijamos en el universo del discurso, existe otra que est´ a casada con ella”. Pues bien, dada una persona cualquiera x, la proposici´on ∃y : x est´a casada con y es verdadera, por lo tanto, ∀x [∃y : (x est´a casada con y)] es verdad. (b) ∃y : [∀x (x est´ a casada con y)] La transcripci´ on es “Existe una persona y del universo del discurso tal que todas las dem´as est´an casadas con ella”. Pues bien, la proposici´ on ∀x(x est´a casada con y) es falsa para cualquier y que tomemos en el universo, por tanto, ∃y : [∀x (x est´a casada con y)] es una proposici´ on falsa. (c) ∀x [∃y : (x + y = 0)] “Dado cualquier n´ umero entero, existe otro tal que la suma de ambos es cero”. Pues bien, dado cualquier n´ umero entero x, la proposici´on ∃y : x + y = 0 es verdad ya que siempre puede encontrarse otro entero y que cumpla la ecuaci´on x+y = 0 (bastar´ıa tomar y = −x). Por lo tanto la proposici´on ∀x [∃y : (x + y = 0)] es verdad. (d) ∃y : [∀x (x + y = 0)] “Existe, al menos, un n´ umero entero y tal que su suma con cualquier otro n´ umero entero es cero”. La proposici´ on ∀x, x + y = 0 es falsa para todos los y del universo del discurso. En efecto, bastar´ıa tomar un x 6= 0 y x 6= −y para que x + y 6= 0. Por lo tanto, ∃y : [∀x (x + y = 0)] es una proposici´ on falsa. Obs´ervese que las dos parejas de proposiciones se diferencian u ´nicamente en el orden de los cuantificadores  universal y existencial y, sin embargo, sus valores de verdad son distintos. Nota 2.4 Cuando se asignan valores a las variables de un predicado para transformarla en una proposici´on, los valores de verdad de ´esta pueden cambiar dependiendo del universo del discurso que se elija. Por ejemplo, la proposici´ on “∀x, x es negativo” ser´a verdad si el universo del discurso son los n´ umeros enteros negativos y falsa si son los enteros positivos. En el ejemplo siguiente buscamos universos que hagan que determinadas proposiciones sean verdaderas.  Ejemplo 2.19 Especificar un universo del discurso para el cual las proposiciones siguientes sean verdad. Elegir el universo como un conjunto de n´ umeros enteros tan grande como sea posible. 43

Universidad de C´ adiz

Departamento de Matem´ aticas

(a) ∀x, x > 0 (b) ∀x, x = 3 (c) ∀x [∃y : (x + y = 248)] (d) ∃y : [∀ (x, x + y < 0)] Soluci´on (a) La proposici´ on ∀x, x > 0 significa que x sea mayor que cero, cualquiera que sea x, luego U es el conjunto de los enteros positivos. (b) ∀x, x = 3, significa que cualquiera que sea x, valga 3, luego U es el subconjunto de los enteros formado u ´nicamente por el 3. (c) ∀x [∃y (: x + y = 248)]. El universo del discurso que hace que esta proposici´on sea verdad es el conjunto de los enteros, ya que dado cualquier entero x, bastar´ıa tomar y = 248 − x para que la proposici´ on ∃y : x + y = 248 fuese verdad. (d) ∃y : [∀x (x + y < 0)]. El universo que hace verdadera esta proposici´on es el de los enteros negativos,  ya que fijando un y en ´el la proposici´on ∀x(x + y < 0) es verdad.

2.3

C´ alculo de Predicados

La versi´on de la l´ ogica que trata con proposiciones cuantificadas se llama l´ ogica de predicados. La introducci´on de cuantificadores no s´ olo ampl´ıa la fuerza expresiva de las proposiciones que se pueden construir, sino que tambi´en permite elaborar principios l´ogicos que explican el razonamiento seguido en casi todas las demostraciones matem´ aticas. Una transcripci´ on cuidadosa de los desarrollos matem´aticos incluyen, a menudo, cuantificadores, predicados y operadores l´ ogicos. Ejemplo 2.20

Consideremos como universo del discurso el conjunto de los n´ umeros enteros y sean

p(x) : x es no negativo. q(x) : x es par. r(x) : x es impar. s(x) : x es primo. Expresar en notaci´ on l´ ogica las siguientes afirmaciones: (a) Existe un entero par. (b) Todo n´ umero entero es par o impar. (c) Todos los n´ umeros primos son no negativos. (d) El u ´nico n´ umero primo par es el 2. (e) No todos los enteros son pares. (f) No todos los primos son impares. (g) Si un entero no es impar, entonces es par. 44

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

Soluci´on (a) Existe un entero par. ∃x : q(x) (b) Todo n´ umero entero es par o impar. ∀x [q(x) ∨ r(x)] (c) Todos los n´ umeros primos son no negativos. ∀x [s(x) −→ p(x)] (d) El u ´nico n´ umero primo par es el 2. ∀x [s(x) ∧ q(x) −→ x = 2] (e) No todos los enteros son pares. ¬ [∀x, q(x)] (f) No todos los primos son impares. ¬∀x, [s(x) −→ r(x)] (g) Si un entero no es impar, entonces es par. ∀x [¬r(x) −→ q(x)] Obs´ervese que en el ejemplo anterior, los cuantificadores est´an al comienzo de cada afirmaci´on. Sin embargo, no siempre es as´ı, los cuantificadores pueden ir en cualquier parte y su situaci´on es importante. Ejemplo 2.21 Consideremos en el universo de los n´ umeros enteros el predicado p(x, y, z) : xy = z. Transcribir a notaci´ on l´ ogica las afirmaciones siguientes: (a) Si x = 0, entonces xy = x para todos los valores de y. (b) Si xy = x para cada y, entonces x = 0. (c) Si xy 6= x para alg´ un x, entonces x 6= 0. Soluci´on Sea p(x, y, z) : xy = z, entonces (a) Si x = 0, entonces xy = x para todos los valores de y. ∀x [x = 0 −→ ∀y, p(x, y, x)] (b) Si xy = x para cada y, entonces x = 0. ∀x [∀y (p(x, y, x) −→ x = 0)] (c) Si xy 6= x para alg´ un x, entonces x 6= 0. ∃x : [¬p(x, y, x) −→ x 6= 0] 45

Universidad de C´ adiz

Departamento de Matem´ aticas

La proposici´on (b) afirma que si xy = x para todos los valores de y, entonces x vale cero. Si en su lugar escribimos ∀x [∀y (p(x, y, x) −→ x = 0)] la transcripci´ on no es correcta, ya que en tal caso estar´ıamos afirmando que si xy = x, entonces x = 0 para cada x y para cada y, lo cual es falso ya que, por ejemplo, tomando x = y = 1, tendremos que xy = x y, sin embargo, x no es cero. Por tanto, el lugar en el que se coloca el cuantificador es fundamental.  Los ejemplos anteriores ilustran la gran variedad de formas en las que pueden hacerse afirmaciones que contengan predicados, cuantificadores y operadores l´ogicos. Nota 2.5 El valor de verdad de una proposici´on compuesta depende, generalmente, del conjunto universal donde las variables ligadas est´ an cuantificadas. Sin embargo, existen ejemplos importantes donde el valor de verdad no depende ni del universo del discurso ni de los valores que las variables tomen en el mismo.

2.3.1

Implicaci´ on L´ ogica

Sean A1 y A2 dos afirmaciones que contienen predicados. Diremos que A1 implica l´ ogicamente A2 si para cualquier universo del discurso que elijamos y para cualquier valor de las variables en el mismo, A2 es verdad cuando A1 lo sea.

2.3.2

Equivalencia L´ ogica

Sean A1 y A2 dos afirmaciones que contienen predicados. Diremos que A1 equivale l´ ogicamente a A2 si para cualquier universo del discurso que elijamos y para cualquier valor de las variables en el mismo, A1 y A2 tienen los mismos valores de verdad. Obs´ervese que las definiciones son an´ alogas a las dadas para la implicaci´on y equivalencia l´ogica de proposiciones. Ahora se exige que las condiciones se verifiquen para cualquier universo del discurso y cualquier valor de las variables en el mismo.

2.3.3

Leyes de De Morgan Generalizadas

Constituyen una clase importante de equivalencias l´ ogicas y son las siguientes: 1. ¬∀x, p(x) ⇐⇒ ∃x : ¬p(x) 2. ¬∃x : p(x) ⇐⇒ ∀x, ¬p(x) 3. ∀x, p(x) ⇐⇒ ¬∃x : ¬p(x) 4. ∃x : p(x) ⇐⇒ ¬∀x, ¬p(x) Demostraci´on Sea U un universo del discurso arbitrario, p(x) un predicado cualquiera, y x cualquiera de U . Veamos que en todos los casos las dos proposiciones tienen los mismos valores de verdad. 1. ¬∀x, p(x) ⇐⇒ ∃x : ¬p(x) Si ¬∀x, p(x) es verdad, entonces ∀x, p(x) es falso, luego existe, al menos, un x en U para el cual p(x) es falso, o lo que es igual para el que ¬p(x) es verdad, es decir ∃x : ¬p(x) es verdad. 46

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

Si ¬∀x, p(x) es falso, entonces ∀x, p(x) es verdad, luego p(x) es verdad para cualquier valor de x y ¬p(x) falso. Por lo tanto, ∃x : ¬p(x) es falso. 2. ¬∃x : p(x) ⇐⇒ ∀x, ¬p(x) Si ¬∃x : p(x) es verdad, entonces ∃x : p(x) es falso, luego p(x) es falso para todos los valores de x, es decir ¬p(x) es verdad para cualquier x de U y, consecuentemente, ∀x, ¬p(x) es verdad. Si ¬∃x : p(x) es falso, entonces ∃x : p(x) es verdad, luego p(x) es verdad para alg´ un valor de x, de aqu´ı que exista un x para el cual ¬p(x) es falso y, por lo tanto, ∀x, ¬p(x) es falso. 3. ∀x, p(x) ⇐⇒ ¬∃x : ¬p(x) Si ∀x, p(x) es verdad, entonces p(x) es verdad para cualquier x o lo que es igual ¬p(x) es falso para todo x de U , es decir ∃x : ¬p(x) es falso y, por tanto, ¬∃x : ¬p(x) es verdad. Si ∀x, p(x) es falso, entonces hay, al menos, un valor de x para el cual p(x) es falso o para el que ¬p(x) es verdad, es decir ∃x : ¬p(x) es verdad y, consecuentemente, ¬∃x : ¬p(x) es falso. 4. ∃x : p(x) ⇐⇒ ¬∀x, ¬p(x) Si ∃x : p(x) es verdad, entonces p(x) es verdad para alg´ un valor de x en U , luego existe un x en U para el cual ¬p(x) es falso, es decir, ∀x, ¬p(x) es falso y, consecuentemente, ¬∀x, ¬p(x) es verdad. Si ∃x : p(x) es falso, entonces p(x) es falsa para todos los valores de x en U , es decir ¬p(x) es verdad, luego ∀x, ¬p(x) es verdad y, por lo tanto, ¬∀x¬p(x) es falso. Tenemos, pues, que cada una de las proposiciones anteriores son verdaderas independientemente del conjunto universal que elijamos y las variables de predicado que utilicemos, por lo tanto de acuerdo con la definici´on, son l´ ogicamente equivalentes.  Nota 2.6 Obs´ervese que seg´ un lo que acabamos de probar, la equivalencia 1. es cierta para cualquier predicado luego ser´ a cierto para ¬p(x). Entonces, ¬∀x, ¬p(x) ⇐⇒ ∃x : ¬¬p(x) y si sustituimos ¬¬p(x) por p(x), resulta ¬∀x, ¬p(x) ⇐⇒ ∃x : p(x) que es la cuarta ley de De Morgan, de la cual, negando ambos miembros, y en virtud de la equivalencia l´ogica entre una proposici´ on y su contrarrec´ıproca, obtenemos, ¬¬∀x, ¬p(x) ⇐⇒ ¬∃x : p(x) es decir, ∀x, ¬p(x) ⇐⇒ ¬∃x : p(x) que es la segunda ley de De Morgan. Si ahora se la aplicamos a ¬p(x), obtendremos ∀x, ¬¬p(x) ⇐⇒ ¬∃x : ¬p(x) o sea, ∀x, p(x) ⇐⇒ ¬∃x : ¬p(x) que es la tercera ley de De Morgan.



Nota 2.7 Las leyes de De Morgan generalizadas pueden utilizarse repetidamente para negar cualquier proposici´on con cuantificadores. Por ejemplo, podemos utilizarlas para negar la proposici´on ∃w : [∀x (∃y : (∃z : p(w, x, y, z)))] 47

Universidad de C´ adiz

Departamento de Matem´ aticas

En efecto, ¬∃w : [∀x (∃y : (∃z : p(w, x, y, z)))] ⇐⇒

∀w [¬∀x(∃y : (∃z : p(w, x, y, z)))]

{Segunda ley}

⇐⇒

∀w [∃x : (¬∃y : (∃z : p(w, x, y, z)] {Primera ley}

⇐⇒

∀w [∃x : (∀y(¬∃z : p(w, x, y, z)))]

{Segunda ley}

⇐⇒

∀w [∃x : (∀y(∀z, ¬p(w, x, y, z)))]

{Segunda ley} 

2.3.4

Regla general

La negaci´ on de una proposici´ on con cuantif icadores es l´ ogicamente equivalente a la proposici´ on que se obtiene sustituyendo cada ∀ por ∃, cada ∃ por ∀ y reemplazando el predicado por su negaci´ on. Ejemplo 2.22

Construir la negaci´ on de la proposici´on ∀x [∀y (∃z : x < z < y)]

Soluci´on De acuerdo con la regla general, la negaci´ on de la proposici´on anterior es: ∃x : [∃y : (∀z, ¬(x < z < y))] si ahora aplicamos las leyes de De Morgan del c´alculo proposicional a la proposici´on ¬(x < z < y), tendremos ¬(x < z < y) ⇐⇒ ¬ [(x < z) ∧ (z < y)] ⇐⇒

¬(x < z) ∨ ¬(z < y)

⇐⇒

x>z∨z >y

Por tanto, la negaci´ on de ∀x [∀y(∃z : (x < z < y))] es l´ogicamente equivalente a ∃x : [∃y : (∀z, x > z ∨ z > y)]  Ejemplo 2.23 nadores”.

Negar la afirmaci´ on “todas las empresas fabrican alg´ un componente de todos los orde-

Soluci´on Sean los predicados p(x, y): la empresa x produce el componente y y q(y, z): y es un componente del ordenador z La afirmaci´on propuesta escrita en lenguaje simb´olico ser´ıa ∀x [∀z(∃y : (p(x, y) ∧ p(y, z)))] y su negaci´on, de acuerdo con la regla general ser´a: ∃x : [∃z : (∀y : ¬(p(x, y) ∧ q(y, z)))] 48

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

la cual, a su vez, es l´ ogicamente equivalente a ∃x : [∃z : (∀y : ¬p(x, y) ∨ ¬q(y, z))] que podemos escribir en forma de condicional sin m´as que utilizar la implicaci´on l´ogica conocida como implicaci´ on, ∃x : [∃z : (∀y : p(x, y) −→ ¬q(y, z))] cuya interpretaci´ on es “pueden encontrarse una empresa y un ordenador tales que si un componente cualquiera est´ a fabricado por la empresa, entonces no pertenece al ordenador”. Obs´ervese que tambi´en pod´ıamos haber escrito ∃x : [∃z : (∀y : q(y, z) −→ ¬p(x, y))] cuya interpretaci´ on es “pueden encontrarse una empresa y un ordenador tales que si un componente cualquiera pertenece al ordenador, entonces no est´ a fabricado por la empresa”. Obs´ervese tambi´en que otra forma equivalente de la negaci´on es ∃x : [∃z : (¬∃y : p(x, y) ∧ q(y, z))] cuya interpretaci´ on es “existen una empresa y un ordenador tales que la empresa no fabrica ning´ un componente del ordenador” o tambi´en “existen una empresa y un ordenador tales que el ordenador no tiene ning´ un componente fabricado por la empresa.”  Ahora estudiaremos de que forma afectan a los cuantificadores lo conectores l´ogicos conjunci´on y disyunci´on.

2.3.5

Proposiciones al Alcance de un Cuantificador

Si una proposici´ on est´ a dentro del alcance de un cuantificador mediante una conjunci´ on o una disyunci´ on, entonces puede situarse fuera del alcance del mismo. (a) ∀x [p(x) ∨ q] ⇐⇒ [∀x, p(x)] ∨ q (b) ∃x : [p(x) ∨ q] ⇐⇒ [∃x : p(x)] ∨ q (c) ∃x : [p(x) ∧ q] ⇐⇒ [∃x : p(x)] ∧ q (d) ∀x [p(x) ∧ q] ⇐⇒ [∀x, p(x)] ∧ q Demostraci´on Supondremos que U es un universo del discurso arbitrario, p(x) cualquier predicado, x un elemento cualquiera de U y q una proposici´ on cualquiera. 49

Universidad de C´ adiz

Departamento de Matem´ aticas

(a) ∀x [p(x) ∨ q] ⇐⇒ [∀x, p(x)] ∨ q. Veamos que ambas proposiciones tienen los mismos valores de verdad. Si ∀x [p(x) ∨ q] es verdad, entonces p(x) ∨ q es verdad para todos los valores de x en U luego una de las dos proposiciones ha ser verdad para todo x. − Si p(x) es verdad para todos los valores de x en U , entonces ∀x, p(x) es verdad y, consecuentemente [∀x, p(x)] ∨ q es verdad. − Si q es verdad, entonces [∀x, p(x)] ∨ q es verdad. luego en ambos casos, [∀x, p(x)] ∨ q es verdad. Si ∀x [p(x) ∨ q] es falso, entonces existe al menos un x para el cual p(x) ∨ q es falso de aqu´ı que p(x) sea falso para ese x y q tambi´en, luego [∀x, p(x)] es falso, q es falso y, consecuentemente, [∀x, p(x)] ∨ q es falso. (b) ∃x : [p(x) ∨ q] ⇐⇒ [∃x : p(x)] ∨ q. Veamos si ambas proposiciones tienen los mismos valores de verdad. Si ∃x : p(x) ∨ q es verdad, entonces existe un x, para el cual p(x) ∨ q es verdad, luego una de las dos proposiciones ha de ser verdad. − Si p(x) es verdad para alg´ un x, entonces ∃x : p(x) es verdad y, consecuentemente, [∃x : p(x)]∨q tambi´en lo es. − Si q es verdad, entonces [∃x : p(x)] ∨ q tambi´en lo es. es decir, en cualquier caso [∃x : p(x)] ∨ q es verdad. Si ∃x : [p(x) ∨ q] es falso, entonces p(x) ∨ q es falso para todos los valores de x, luego p(x) es falso para cualquier x de U y q tambi´en, es decir ∃x : p(x) es falso y q falso, luego [∃x : p(x)] ∨ q es falso. (c) ∃x : [p(x) ∧ q] ⇐⇒ [∃x : p(x)] ∧ q. Si ∃x : [p(x) ∧ q] es verdad, entonces p(x) ∧ q es verdad para alg´ un valor de la variable x, luego p(x) y q han de ser verdad para este x de aqu´ı que ∃x : p(x) sea verdad y q tambi´en y, consecuentemente, [∃x : p(x)] ∧ q es verdad. Si [∃x : p(x) ∧ q] es falso, entonces p(x)∧q es falso para todos los valores de la variable x, luego p(x) y q han de ser, ambos, falsos para todos esos valores, de aqu´ı que ∃x : p(x) sea falso y q tambi´en. Consecuentemente, [∃x : p(x)] ∧ q es falso. Tambi´en podemos probarlo de otra forma. En efecto, en el apartado (a) hemos visto que ∀x [p(x) ∨ q] ⇐⇒ [∀x, p(x)] ∨ q de aqu´ı que sustituyendo los predicados por sus negaciones, tengamos ∀x [¬p(x) ∨ ¬q] ⇐⇒ [∀x, ¬p(x)] ∨ ¬q y negando ambos miembros, ¬∀x [¬p(x) ∨ ¬q] ⇐⇒ ¬ [(∀x, ¬(p(x)) ∨ ¬q] y aplicando las leyes de De Morgan en el segundo miembro ¬∀x [¬p(x) ∨ ¬q] ⇐⇒ [¬∀x, ¬p(x)] ∧ q y por las leyes de De Morgan generalizadas, ∃x : ¬ [¬(p(x) ∨ ¬q] ⇐⇒ [∃x : ¬¬p(x)] ∧ q es decir, ∃x : [¬¬p(x) ∧ ¬¬q] ⇐⇒ [∃x : p(x)] ∧ q y, consecuentemente, ∃x : [p(x) ∧ q] ⇐⇒ [∃x : p(x)] ∧ q 50

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

(d) ∀x [p(x) ∧ q] ⇐⇒ [∀x, p(x)] ∧ q. Si ∀x(p(x) ∧ q) es verdad, entonces p(x) ∧ q es verdad para todos los valores de x en U de aqu´ı que p(x) y q sean, ambos, verdad para cualquier x. Por lo tanto, ∀x, p(x) es verdad y q tambi´en y, consecuentemente, [∀x, p(x)] ∧ q es verdad. Si ∀x [p(x) ∧ q] es falso, entonces hay alg´ un valor de la variable x para el cual p(x) ∧ q es falso, de aqu´ı que una de las dos proposiciones sea falsa. − Si p(x) es falsa para alg´ un valor de la variable x, entonces ∀x, p(x) es falsa y, consecuentemente, [∀x, p(x)] ∧ q ser´ a falsa, independientemente del valor de verdad de q. − Si q es falsa, entonces [∀x, p(x)] ∧ q es falsa. Al igual que el apartado anterior, lo probaremos de otra forma. En efecto, en el apartado (b) vimos que ∃x : [p(x) ∨ q] ⇐⇒ [∃x : p(x)] ∨ q luego si sustituimos cada proposici´ on por su negaci´on, tendremos ∃x : [¬p(x) ∨ ¬q] ⇐⇒ [∃x : ¬p(x)] ∨ ¬q y negando ambos miembros, ¬∃x : [¬p(x) ∨ ¬q] ⇐⇒ ¬ [(∃x : ¬p(x)) ∨ ¬q] es decir, ¬∃x : [¬p(x) ∨ ¬q] ⇐⇒ [¬∃x : ¬p(x)] ∧ q de aqu´ı que, por las Leyes de De Morgan generalizadas, tengamos ∀x, ¬ [¬p(x) ∨ ¬q] ⇐⇒ [∀x, ¬¬p(x)] ∧ q o sea, ∀x [¬¬p(x) ∧ ¬¬q] ⇐⇒ [∀x, p(x)] ∧ q y, consecuentemente, ∀x [p(x) ∧ q] ⇐⇒ [∀x, p(x)] ∧ q  Ejemplo 2.24

Probar las siguientes equivalencias:

(a) ∀x [p −→ q(x)] ⇐⇒ p −→ [∀x, q(x)] (b) [∀x, p(x)] −→ q ⇐⇒ ∃x : [p(x) −→ q] Soluci´on (a) ∀x [p −→ q(x)] ⇐⇒ p −→ [∀x, q(x)] En efecto, ∀x [p −→ q(x)] ⇐⇒

∀x [¬p ∨ q(x)]

{Implicaci´on}

⇐⇒

∀x [q(x) ∨ ¬p]

{Conmutatividad de ∨}

⇐⇒

[∀x, q(x)] ∨ ¬p

{2.3.5 (a)}

⇐⇒

¬p ∨ [∀x, q(x)]

{Conmutatividad de ∨}

⇐⇒

p −→ [∀x, q(x)] {Implicaci´on} 51

Universidad de C´ adiz

Departamento de Matem´ aticas

(b) [∀x, p(x) −→ q] ⇐⇒ ∃x : [p(x) −→ q] En efecto, [∀x, p(x)] −→ q

⇐⇒

[¬∀x, p(x)] ∨ q

{Implicaci´on}

⇐⇒

[∃x : ¬p(x)] ∨ q

{Leyes de De Morgan}

⇐⇒

∃x : [¬p(x) ∨ q]

{2.3.5 (a)}

⇐⇒

∃x : [p(x) −→ q] {Implicaci´on} 

2.3.6

Predicados al Alcance de un Cuantificador

Los predicados con variables no ligadas por un cuantificador que est´en dentro del alcance del mismo mediante una conjunci´ on o una disyunci´ on pueden situarse fuera del alcance del cuantificador. (a) ∀x [p(x) ∨ q(y)] ⇐⇒ [∀x, p(x)] ∨ q(y) (b) ∀x [p(x) ∧ q(y)] ⇐⇒ [∀x, p(x)] ∧ q(y) (c) ∃x : [p(x) ∨ q(y)] ⇐⇒ [∃x : p(x)] ∨ q(y) (d) ∃x : [p(x) ∧ q(y)] ⇐⇒ [∃x : p(x)] ∧ q(y) Demostraci´on La demostraci´ on es id´entica a la hecha en la proposici´on anterior.

2.3.7



Asociatividad y Distributividad

(a) ∀x [p(x) ∧ q(x)] ⇐⇒ [∀x, p(x)] ∧ [∀x, q(x)] (b) ∃x : [p(x) ∧ q(x)] =⇒ [∃x : p(x)] ∧ [∃x : q(x)] (c) ∃x : [p(x) ∨ q(x)] ⇐⇒ [∃x : p(x)] ∨ [∃x : q(x)] (d) [∀x, p(x)] ∨ [∀x, q(x)] =⇒ ∀x, [p(x) ∨ q(x)] Demostraci´on Sea U un universo del discurso cualquiera y p(x), q(x) dos predicados arbitrarios, siendo x cualquier elemento de U (a) ∀x [p(x) ∧ q(x)] ⇐⇒ [∀x, p(x)] ∧ [∀x, q(x)] Veamos que ambas proposiciones tienen los mismos valores de verdad. Si ∀x [p(x) ∧ q(x)] es verdad, entonces p(x) ∧ q(x) es verdad para todos los valores de x en U , luego p(x) y q(x) son, ambas, verdad para cualquier x de U , es decir ∀x, p(x) es verdad y ∀x, q(x) tambi´en, luego [∀x, p(x)] ∧ [∀x, q(x)] es verdad. Por otra parte, si ∀x [p(x) ∧ q(x)] es falso, entonces existe, al menos, un valor de x en U para el cual p(x) ∧ q(x) es falsa luego una de las dos ha de ser falsa. − Si p(x) es falsa para alg´ un valor de x, entonces ∀x, p(x) es falsa y, consecuentemente, la proposici´ on [∀x, p(x)] ∧ [∀x, q(x)] es falsa. − Si q(x) es falsa, el razonamiento es id´entico al anterior. Por lo tanto, en ambos casos, la proposici´on es falsa. 52

L´ ogica Matem´ atica

Francisco Jos´e Gonz´ alez Guti´errez

La relaci´ on anterior suele enunciarse informalmente diciendo que “el cuantificador universal es distributivo respecto del conectivo l´ ogico conjunci´ on.” (b) ∃x : [p(x) ∧ q(x)] =⇒ [∃x : p(x)] ∧ [∃x : q(x)] Veamos que si la primera de las proposiciones es verdad, entonces la segunda tambi´en lo es. En efecto si ∃x : [p(x) ∧ q(x)] es verdad, entonces p(x) ∧ q(x) es verdad para alg´ un x en U , luego p(x) y q(x) son verdad, ambas, para ´ese x, de aqu´ı que ∃x : p(x) sea verdad y ∃x : q(x) tambi´en y, consecuentemente, [∃x : p(x)] ∧ [∃x : q(x)] es verdad. Veamos que, sin embargo, no se da la equivalencia l´ogica como en el apartado anterior. En efecto, la afirmaci´ on ∃x : [p(x) ∧ q(x)] nos dice que existe un valor de x en el universo para el cual p(x) y q(x) son, ambas, verdad. Por otra parte, [∃x : p(x)] ∧ [∃x : q(x)] afirma que existe un valor de x en el universo tal que p(x) es verdad y que existe un valor de x para el cual es verdad q(x). Veamos un contraejemplo que pone de manifiesto lo que decimos. Supongamos que U es el conjunto de los n´ umeros enteros y sea p(x) : x es un n´ umero par y q(x) : x es un n´ umero impar. Entonces, “existe, al menos, un n´ umero entero par y existe, al menos, un n´ umero entero impar”, luego [∃x : p(x)] ∧ [∃x : q(x)] es una proposici´ on verdadera, en tanto que “existe, al menos, un n´ umero entero que es, al mismo tiempo, par e impar”, es decir, ∃x : [p(x) ∧ q(x)] es una proposici´ on falsa, luego no se verifica la implicaci´on contraria. (c) ∃x : [p(x) ∨ q(x)] ⇐⇒ [∃x : p(x)] ∨ [∃x : q(x)] Veamos que si la segunda es falsa, entonces la primera tambi´en lo es (equivale a probar que si la primera es verdad, la segunda tambi´en). En efecto, si [∃x : p(x)] ∨ [∃x : q(x)] es falsa, entonces ∃x : p(x) es falsa y ∃x : q(x) tambi´en, luego p(x) y q(x) son, ambas, falsas para todos los valores de x en U , de aqu´ı que para cualquier valor de x, p(x) ∨ q(x) sea falsa y, consecuentemente, ∃x : [p(x) ∨ q(x)] es una proposici´ on falsa. Por otra parte, si ∃x : [p(x) ∨ q(x)] es falsa, entonces p(x) ∨ q(x) es falsa para todos los valores de x en U , luego p(x) es falsa y q(x) es falsa para cualquier x, de aqu´ı que ∃x : p(x) sea falsa, ∃x : q(x) tambi´en y, consecuentemente, [∃x : p(x)] ∨ [∃x : q(x)] sea una proposici´on falsa. Veamos otra forma de demostrar lo mismo. En el apartado (a), hemos visto que ∀x [p(x) ∧ q(x)] ⇐⇒ [∀x, p(x)] ∧ [∀x, q(x)] siendo cierto este resultado para cualquier predicado, luego tambi´en lo ser´a para sus negaciones, es decir, ∀x [¬p(x) ∧ ¬q(x)] ⇐⇒ [∀x, ¬p(x)] ∧ [∀x, ¬q(x)] negando ahora ambos miembros, resulta ¬∀x [¬p(x) ∧ ¬q(x)] ⇐⇒ ¬ [(∀x, ¬p(x)) ∧ (∀x, ¬q(x))] as´ı pues, ∃x : ¬([¬p(x) ∧ ¬q(x)]] ⇐⇒ [¬∀x, ¬p(x)] ∨ [¬∀x, ¬q(x)] es decir, ∃x : [¬¬p(x) ∨ ¬¬q(x)] ⇐⇒ [∃x : ¬¬p(x)] ∨ [∃x : ¬¬q(x)] de aqu´ı que ∃x : [p(x) ∨ q(x)] ⇐⇒ [∃x : p(x)] ∨ (∃x : q(x)] La relaci´ on anterior suele enunciarse informalmente diciendo que “el cuantificador existencial es distributivo respecto del conectivo l´ ogico disyunci´ on” 53

Universidad de C´ adiz

Departamento de Matem´ aticas

(d) [∀x, p(x)] ∨ [∀x, q(x)] =⇒ ∀x, [p(x) ∨ q(x)] En efecto, si [∀x, p(x)] ∨ [∀x, q(x)] es verdad, entonces una de las dos proposiciones ha de ser verdad. Si ∀x, p(x) es verdad, p(x) ha de ser verdad para todos los valores de x, luego p(x) ∨ q(x) es verdad y, consecuentemente, ∀x [p(x) ∨ q(x)] es verdad. Si ∀x, q(x) es verdad, se razona exactamente igual. Otra forma de demostrar lo mismo es la siguiente: en el apartado (b) vimos que ∃x : [p(x) ∧ q(x)] =⇒ [∃x : p(x)] ∧ [∃x : q(x)] Si ahora sustituimos los predicados por sus negaciones, ∃x : [¬p(x) ∧ ¬q(x)] =⇒ [∃x : ¬p(x)] ∧ [∃x : ¬q(x)] negamos ambos miembros, y aplicamos la “contrarrec´ıproca”, resulta ¬ [∃x : ¬p(x)] ∧ [∃x : ¬q(x)] =⇒ ¬∃x : [¬p(x) ∧ ¬q(x)] luego, [¬∃x : ¬p(x)] ∨ [¬∃x : ¬q(x)] =⇒ ∀x¬ [¬p(x) ∧ ¬q(x)] es decir, [∀x, ¬¬p(x)] ∨ [∀x, ¬¬q(x)] =⇒ ∀x [¬¬p(x) ∨ ¬¬q(x)] de donde se sigue que [∀x, p(x)] ∨ [∀x, q(x)] =⇒ ∀x [p(x) ∨ q(x)] Por razones an´ alogas a las del apartado (b) no se da la equivalencia l´ogica.

54