4.1: Predicados y Cuantificadores
- Page ID
- 118169
A menudo dejamos que las variables representen objetos matemáticos arbitrarios. Sin embargo, como hemos visto, las variables de objeto o variables libres (a diferencia de las variables de instrucción) conducen a problemas en la lógica. Por ejemplo, la frase “\(f\)es una función diferenciable” sólo puede determinarse como verdadera o falsa cuando\(f\) representa una función específica.
En esta sección, tratamos estos problemas cuantificando tales variables libres: limitándonos a discutir si las “declaraciones” que involucran una o más variables libres son siempre/ a veces/nunca verdaderas para objetos del tipo representado por las variables libres.
una declaración cuyo valor de verdad depende de una o más variables libres
una declaración de predicado\(A\) cuyo valor de verdad depende de la variable libre\(x\)
una declaración predicada\(A\) cuyo valor de verdad depende de las variables libres\(x\) y\(y\)
- Let\(A(f)\) representar la frase “\(f\)es diferenciable”, una declaración de predicado en una variable libre\(f\text{.}\)
- Let\(B(m,n)\) representar la frase “\(m\)es mayor que\(n\)”, una declaración de predicado en dos variables libres\(m\) y\(n\text{.}\)
Un predicado no es una declaración lógica a menos que todas sus variables representen objetos específicos.
el tipo de objeto que representa una variable en un predicado
En Ejemplo\(\PageIndex{1}\), el dominio de la variable\(f\) podría ser “funciones de una sola variable real”, y los dominios de las variables\(m\) y\(n\) podrían ser ambos “números naturales” (es decir, números enteros, no negativos).
Por lo general, el dominio de una variable en un predicado es implícito y se puede determinar a partir del contexto de la sentencia. No obstante, si queremos hacer explícito el dominio podemos predefinirlo a la variable. Por ejemplo,
\ begin {reunir*} A (f) =\ text {“function} f\ text {es diferenciable”,}\\ B (m, n) =\ text {“integer} m\ text {es mayor que entero} n\ text {”.} \ end {reunir*}
Podemos convertir un predicado en una declaración lógica siendo más específicos sobre qué objetos en sus dominios representan las variables. Sin embargo, muchas veces no queremos ser demasiado específicos (o de lo contrario normalmente no necesitaríamos variables).
Las siguientes frases son afirmaciones lógicas, porque se puede determinar su valor de verdad.
- “Cada función\(f\) es diferenciable”.
- “Existe un entero\(m\) que\(2\) divide”.
La primera declaración es falsa; por ejemplo, la función no\(f(x) = \vert x \vert\) es diferenciable en\(x=0\text{.}\) La segunda declaración es verdadera; esta afirmación básicamente dice que incluso existen enteros.
los fragmentos de oración “para cada” y “existe” cuantifican si un predicado debe aplicarse a todos o sólo algunos de los objetos en el dominio de una de sus variables.
el cuantificador “para cada”
símbolo para el cuantificador universal
el cuantificador “existe”
símbolo para el cuantificador existencial
Como antes, vamos a\(A(f)\) representar el predicado “\(f\)es diferenciable”. Entonces la afirmación\((\forall f ) A(f)\) es falsa, porque no todas las funciones son diferenciables. No obstante, la afirmación\((\exists f) A(f)\) es cierta —por ejemplo, los polinomios son diferenciables.
Para que una afirmación cuantificada existencialmente sea cierta, no es necesario que haya un solo objeto en el dominio implícito que satisfaga las condiciones del predicado —podría haber muchos de esos objetos. Entonces, así como siempre debes leer una disyunción\(p \lor q\) como “p o q o ambos”, siempre debes leer una declaración cuantificada existencialmente\((\exists x) A(x)\) como “existe al menos una\(x\) tal que\(A(x)\) sea verdadera”.
Las declaraciones matemáticas a menudo involucran varias variables cuantificadas.
Dejar\(B(m,n)\) representar “\(m\)divide\(n\)”, donde\(m\) y\(n\) son números enteros positivos. ¿Cuáles de las siguientes afirmaciones son ciertas?
- \(\displaystyle (\forall m)(\forall n)B(m,n) \)
- \(\displaystyle (\exists m)(\exists n)B(m,n) \)
- \(\displaystyle (\forall m)(\exists n)B(m,n) \)
- \(\displaystyle (\exists m)(\forall n)B(m,n) \)
- \(\displaystyle (\forall n)(\exists m)B(m,n) \)
- \(\displaystyle (\exists n)(\forall m)B(m,n) \)
Solución
- Esta afirmación dice “por cada\(m\) y por cada\(n\text{,}\)\(m\) divide\(n\text{.}\)” Un ejemplo de valores para\(m\) y\(n\) con\(m\) no dividir\(n\) (como\(m=3\) y\(n=2\)) es suficiente para demostrar que no siempre es cierto que un número\(m\) divide otro número\(n\text{.}\)
- Esta afirmación dice “existe\(m\) tal que existe\(n\) tal que se\(m\) divide\(n\text{.}\)” Para demostrar que esta afirmación es cierta, tenemos que mostrar explícitamente que al menos un par de valores para\(m\) y\(n\) existe dando un ejemplo (como\(m = n = 2\)).
- Esta afirmación dice “por cada que\(m\) existe un\(n\) tal que\(m\) divide\(n\text{.}\)” Para demostrar que esta afirmación es cierta, tenemos que aportar, por cada valor posible de\(m\text{,}\) un valor de\(n\) que funcione. Cuando\(m=1\text{,}\) tenemos ejemplo\(n=1\text{.}\) Cuando\(m=2\text{,}\) tenemos ejemplo\(n=2\text{.}\) Cuando\(m=3\text{,}\) tenemos ejemplo\(n=3\text{.}\) De igual manera, para cada valor de\(m\text{,}\) podemos\(n\) elegir ser el mismo valor\(m\) que como ejemplo.
- Nota
-
Si el dominio para\(m\) e\(n\) incluido\(0\text{,}\) entonces esta tercera declaración sería realmente falsa, como lo demuestra el ejemplo\(m = 0\text{.}\)
- Esta afirmación dice “existe\(m\) tal que por cada que\(n\) tenemos\(m\) divide\(n\text{.}\)” Esto es cierto, ya que el ejemplo\(m = 1\text{,}\) que divide cada número\(n\text{,}\) demuestra la existencia de este especial\(m\) (aunque es el único ejemplo posible).
- Esta afirmación dice “por cada\(n\) existe un\(m\) modo que\(m\) divide\(n\text{.}\)” De manera similar a la justificación de la Declaración 3, por cada valor posible de\(n\) necesitamos dar un ejemplo para\(m\) que\(m\) divida\(n\text{,}\) pero esta vez es la \(n\)eso es arbitrario y el\(m\) que va a ser el ejemplo. Pero nuevamente, cada número positivo se divide, así que siempre podríamos\(m\) tomar\(n\) como el mismo valor que nuestro ejemplo para demostrar que tal\(m\) existe. (O, en realidad siempre podríamos elegir\(m=1\) como ejemplo para cada valor diferente de\(n\text{.}\))
- Esta afirmación dice “existe\(n\) tal que por cada que\(m\) tenemos\(m\) divisiones\(n\text{.}\)” Sin embargo, no hay un número positivo que sea divisible por todos los demás números positivos.
Si bien el orden de dos cuantificadores del mismo tipo no importa (razón por la cual no consideramos las declaraciones con cuantificadores en el orden\((\forall n)(\forall m)\) y\((\exists n)(\exists m)\) en Ejemplo Trabajado\(\PageIndex{5}\) anterior), ¡el orden de un par “mixto” de cuantificadores importa! Esto se demuestra por la Declaración 3 y la Declaración 6 en el Ejemplo Trabajado\(\PageIndex{5}\) —ambas declaraciones involucran a\(\forall m\) y a\(\exists n\text{,}\) pero en órdenes opuestas. Dado que una de estas dos afirmaciones es verdadera y una falsa, obviamente no pueden ser la misma afirmación.
Aún más, el orden de un par “mixto” de cuantificadores implica una dependencia de la segunda variable cuantificada de la primera.
- Si la afirmación\((\forall x)(\exists y) A(x,y)\) es verdadera, significa que, correspondiente a todos y cada uno de los objetos\(x\) en el dominio apropiado, existirá al menos un ejemplo de un objeto\(y\) en el dominio apropiado para que\(A(x,y)\) sea cierto. Pero el ejemplo correspondiente\(y\) podría ser diferente para diferentes ejemplos del objeto\(x\text{.}\)
- Si la afirmación\((\exists y)(\forall x) A(x,y)\) es verdadera, significa que hay al menos un objeto de ejemplo “especial”\(y\) que disfruta de la propiedad que\(A(x,y)\) será verdadera para todos y cada uno de los objetos\(x\) en el dominio apropiado.
Supongamos que\(A(x,y)\) es una sentencia predicado, donde\(x\) y\(y\) son variables que solo pueden tomar los valores\(0\text{,}\)\(1\text{,}\) o Supongamos\(2\text{.}\) además que se sabe que\(A(x,y)\) es cierto en las instancias específicas
\ begin {ecuación*} A (0,1), A (1,0), A (1,1), A (1,2), A (2,2)\ texto {.} \ end {ecuación*}
- \((\forall x)(\exists y) A(x,y)\)La declaración es verdadera porque para cada valor de\(x\) podemos exhibir al menos un valor\(y\) para el cual\(A(x,y)\) es verdadero:
- cuando\(x=0\text{,}\) sabemos que\(A(0,y)\) es cierto para al menos uno\(y\) (por ejemplo,\(y = 1\));
- cuando\(x=1\text{,}\) sabemos que\(A(1,y)\) es cierto para al menos uno\(y\) (por ejemplo,\(y = 1\)); y
- cuando\(x=2\text{,}\) sabemos que\(A(2,y)\) es cierto para al menos uno\(y\) (por ejemplo,\(y = 2\)).
- \((\exists x)(\forall y) A(x,y)\)La afirmación es verdadera porque podemos exhibir al menos un valor “especial” de\(x\) para el cual\(A(x,y)\) es cierto para todos y cada uno de los valores de\(y\text{.}\) En particular, vemos que porque\(x=1\) tenemos\(A(1,y)\) verdad para cada uno de\(y = 0,1,2\text{.}\)
Observación\(\PageIndex{7}\)
Dependiendo de los requisitos gramaticales o del estilo personal, el cuantificador “para cada” podría expresarse como “para todos” o simplemente “cada” o “todos”. El cuantificador “existe” también puede expresarse como “algunos” o “hay al menos uno”, pero recuerde que la realidad de la situación podría ser “más de uno”.
A los matemáticos les gusta usar “cualquiera” o “para cualquiera” en lugar de “cada” o “para cada”.
Demostrar que\(n+1\) es un número impar para cualquier número par\(n\text{.}\)
Solución. 1 (Incorrecta)
Dice que probar\(n+1\) es impar para cualquier número par\(n\text{,}\) así que elegiré mi número par favorito\(n = 8\text{.}\) Entonces obviamente\(8+1 = 9\) es impar.
Solución. 2 (Correcto)
La declaración del problema es realmente pedir probar que cada número par tiene la propiedad de que el número posterior es impar. Así que vamos\(n\) a representar un número par arbitrario pero no especificado. Entonces\(n\) es divisible por\(2\text{,}\) lo que hay algún número\(m\) tal que\(n = 2m\text{.}\) Ahora, no\(n+1 = 2m+1\) es divisible por\(2\text{,}\) ya que no\((2m+1)/2 = m + \dfrac{1}{2} \) es un número entero. Por lo tanto,\(n+1\) debe ser extraño.
Practicaremos declaraciones de prueba que involucren predicados universalmente cuantificados en el Capítulo 6.