2.4: Introducción a la Cuantificación

En esta sección y en la siguiente, introducimos la lógica de primer orden, también denominada lógica predicada, lógica cuantificacional y cálculo de predicado de primer orden. La frase “x > 0” no es en sí misma una proposición porque su valor de verdad depende de x. En este caso, decimos que x es una variable libre. Una oración con al menos una variable libre se denomina predicado (o oración abierta). Para convertir un predicado en una proposición, debemos sustituir valores por cada variable libre o “cuantificar” las variables libres. Utilizaremos notación como\(P (x)\) y\(Q(a,b)\) para representar predicados con variables libres x y a, b, respectivamente. Las letras “P” y “Q” que usamos en la oración anterior no son especiales; podemos usar cualquier letra o símbolo que queramos. Por ejemplo, cada una de las siguientes representa un predicado con las variables libres indicadas.

• S (x) B “x2 − 4 = 0”
• L (a, b) B “a < b”
• F (x, y) B “x es amigo de y”

Tenga en cuenta que usamos comillas arriba para eliminar alguna ambigüedad. ¿Qué significaría S (x) = x ² − 4 = 0? Parece que S (x) es igual a 0, pero en realidad queremos que S (x) represente la oración completa “x ² − 4 = 0”. Además, observe que el orden en el que utilizamos las variables libres podría importar. Por ejemplo, compare L (a, b) con L (b, a).

Una manera de hacer proposiciones a partir de predicados es asignando valores específicos a las variables libres. Es decir, si P (x) es un predicado y x0 es un valor específico para x, entonces P (x0) es ahora una proposición que es verdadera o falsa.

Problema 2.58. Considere S (x) y L (a, b) como se definió anteriormente. Determine los valores de verdad de S (0), S (−2), L (2,1) y L (−3, −2). ¿L (2, b) es una proposición o un predicado?

Además de sustituir valores específicos por variables libres en un predicado, también podemos hacer una afirmación sobre qué valores de las variables libres se aplican al predicado.

Problema 2.59. Ambas frases siguientes son proposiciones. Decidir si cada uno es verdadero o falso. ¿Qué se necesitaría para justificar tus respuestas?

(a) Para todos x ∈ R, x ² − 4 = 0.

(b) Existe x ∈ R tal que x ² − 4 = 0.

Definición 2.60. “Para todos” es el cuantificador universal y “existe.. tal que” es el cuantificador existencial.

En matemáticas, las frases “para todos”, “para cualquiera”, “para cada” y “para cada” se pueden usar indistintamente (aunque puedan transmitir significados ligeramente diferentes en lenguaje coloquial). Podemos sustituir “existe.. tal que” con frases como “para algunos” (posiblemente con algún ajuste de la redacción de la oración). Es importante señalar que el cuantificador existencial está haciendo una afirmación sobre “al menos uno”, no “exactamente uno”.

Se dice que las variables que se cuantifican con un cuantificador universal o existencial están ligadas. Para ser una proposición, todas las variables de un predicado deben estar vinculadas.

Debemos tener cuidado de especificar la colección de valores aceptables para las variables libres. Considera la frase “Para todos x, x > 0.” ¿Esta frase es verdadera o falsa? La respuesta depende de a qué conjunto se aplique el cuantificador universal. Ciertamente, la sentencia es falsa si la aplicamos para todos x ∈ Z. Sin embargo, la oración es verdadera para todos x ∈ N. El contexto puede resolver ambigüedades, pero de lo contrario, debemos escribir claramente: “Para todos x ∈ Z, x > 0” o “Para todos x ∈ N, x > 0”. La colección de valores pretendidos para una variable se denomina universo del discurso.

Problema 2.61. Supongamos que nuestro universo de discurso es el conjunto de enteros.

(a) Proporcionar un ejemplo de un predicado P (x) tal que “Para todos x, P (x)” sea verdadero.

(b) Proporcionar un ejemplo de un predicado Q (x) tal que “Para todos x, Q (x)” es falso mientras que “Existe x tal que Q (x)” es verdadero.

Si un predicado tiene más de una variable libre, entonces podemos construir proposiciones cuantificando cada variable. Sin embargo, ¡el orden de los cuantificadores es sumamente importante!

Problema 2.62. Sea P (x, y) un predicado con variables libres x e y en un universo de discurso U. Una forma de cuantificar las variables es “Para todos x ∈ U, existe y ∈ U tal que P (x, y)”. ¿De qué otra manera se pueden cuantificar las variables?

El siguiente problema ilustra que al menos algunas de las posibilidades que descubriste en el problema anterior no son equivalentes entre sí.

Problema 2.63. Supongamos que el universo del discurso es el conjunto de personas y considera que el predicado M (x, y) B “x está casado con y”. Podemos interpretar la afirmación formal “Para todos x, existe y tal que M (x, y)” significa “Todo el mundo está casado con alguien”. Interpretar de manera similar el significado de cada una de las siguientes afirmaciones.

(a) Para todos x, existe y tal que M (x, y).

(b) Existe y tal que para todos x, M (x, y).

(c) Para todos x, para todos y, M (x, y).

(d) Existe x tal que existe y tal que M (x, y).

Problema 2.64. Supongamos que el universo del discurso es el conjunto de números reales y considera el predicado F (x, y) B “x = y ²”. Interpretar el significado de cada una de las siguientes afirmaciones.

(a) Existe x tal que existe y tal que F (x, y).

(b) Existe y tal que existe x tal que F (x, y).

(c) Para todos y, para todos x, F (x, y).

Hay un par de puntos clave a tener en cuenta sobre la cuantificación. Para ser una proposición, todas las variables deben ser cuantificadas. Esto puede suceder de al menos dos maneras:

• Las variables están explícitamente unidas por cuantificadores en la misma oración.
• Las variables están implícitamente unidas por oraciones anteriores o por contexto. Declaraciones de la forma “Let x =...” y “Supongamos x ∈...” vinculan la variable x y eliminan la ambigüedad.

Además, el orden de la cuantificación es importante. Invertir el orden de los cuantificadores puede cambiar sustancialmente el significado de una proposición.

Cuantificación y conectivos lógicos (“y”, “o”, “Si., entonces..”, y “no”) permiten declaraciones matemáticas complejas. Por ejemplo, si f es una función mientras que c y L son números reales, entonces la definición formal de lim _{x →c} f (x) = L, que puede haber encontrado en el cálculo, es:

Para todos ε > 0, existe δ > 0 tal que para todos x, si 0 < |x − c| < δ, entonces |f (x) − L| < ε.

Para estudiar la naturaleza abstracta de los enunciados matemáticos complicados, es útil adoptar alguna notación.

Definición 2.65. Se denota el cuantificador universal “para todos”\(∀\), y el cuantificador existencial “existe. tal que” se denota. tal que”\(∃\).

Usando nuestras abreviaturas para los conectivos lógicos y cuantificadores, podemos representar simbólicamente proposiciones matemáticas. Por ejemplo, la proposición (verdadera) “Existe x ∈ R tal que x2 −1 = 0” se convierte en “(x ∈ R) (x2 −1 = 0)”, mientras que la proposición (false) “Para todos x ∈ N, existe y ∈ N tal que y < x” se convierte en “(∀x ∈ N) (y ∈ N) (y < x).”

Problema 2.66. Convierte las siguientes proposiciones en sentencias usando solo símbolos lógicos y matemáticos. Supongamos que el universo del discurso es el conjunto de números reales.

(a) Existe x tal que x ² + 1 es mayor que cero.

(b) Existe un número natural n tal que n ² = 36.

(c) Por cada x, x ² es mayor o igual a cero.

Problema 2.67. Expresar la definición formal de un límite (dada anteriormente Definición 2.65) en símbolos lógicos y matemáticos.

Si miras de cerca, muchos de los teoremas que nos hemos encontrado hasta este punto eran de la forma A (x) =⇒ B (x), donde A (x) y B (x) son predicados. Por ejemplo, considere

Teorema 2.2, que establece, “Si n es un entero par, entonces n2 es un entero par”. En este caso, “n es un entero par” y “n2 es un entero par” son ambos predicados. Entonces, sería razonable suponer que toda la declaración del teorema es un predicado. Sin embargo, es una práctica estándar interpretar la oración A (x) =⇒ B (x) para significar (∀x) (A (x) =⇒ B (x)) (donde el universo del discurso para x necesita ser aclarado). También podemos reordenar tales declaraciones para “ocultar” la implicación. En particular, (∀x) (A (x) =⇒ B (x)) tiene el mismo significado que (∀x ∈ U0) B (x), donde U0 es la colección de ítems del universo del discurso U que hace verdadera A (x). Por ejemplo, podríamos reescribir la declaración del Teorema 2.2 como “Por cada entero par n, n ² es par”.

Problema 2.68. Reword Teorema 2.7 para que se lea explícitamente como una declaración universalmente cuantificada. Comparar con Problema 2.47.

Problema 2.69. Encuentra al menos otras dos instancias de declaraciones del teorema que aparecieron anteriormente en el libro y están escritas en la forma A (x) =⇒ B (x). Reescribir cada uno de manera equivalente que haga explícito al cuantificador universal mientras posiblemente suprime la implicación.

Problema 2.70. Consideremos la proposición “Si ε > 0, entonces existe N ∈ N tal que 1/N < ε.” Supongamos que el universo del discurso es el conjunto R.

a) Expresar el enunciado en símbolos lógicos y matemáticos. ¿Es verdad la afirmación?

b) Invierta el orden de los cuantificadores para obtener una nueva declaración. ¿Cambia el significado? Si es así, ¿cómo? ¿Es cierta la nueva afirmación?

La expresión simbólica (∀x) (∀y) se puede abreviar\(∀x,y\) siempre que x e y sean elementos del mismo universo.

Problema 2.71. Expresar la proposición “Para todos x, y ∈ R con x < y, existe m ∈ R tal que x < m < y” usando símbolos lógicos y matemáticos.

Problema 2.72. Reescribe cada una de las siguientes proposiciones en palabras y determina si la proposición es verdadera o falsa.

(a) (∀n ∈ N) (n ² ≥ 5)

(b) (n ∈ N) (n ² − 1 = 0)

(c) (N ∈ N) (∀n > N) (\(\dfrac{1}{n}\)< 0.01)

(d) (∀m, n ∈ Z) ((2|m 2|n) =⇒ 2| (m + n))

(e) (∀x ∈ N) (y ∈ N) (x − 2y = 0)

(f) (x ∈ N) (∀y ∈ N) (y ≤ x)

Problema 2.73. Considera la proposición (∀x) (y) (xy = 1).

(a) Dar un ejemplo de un universo de discurso donde esta proposición sea cierta.

b) Dar un ejemplo de un universo de discurso donde esta proposición sea falsa.

Para abrir el apetito por la siguiente sección, considere cómo podría probar una verdadera proposición de la forma “Para todos x.”. Si una proposición es falsa, entonces su negación es verdadera. ¿Cómo iba a negar una declaración que involucre cuantificadores?