3.8: Cuantificadores

Como vimos en la Sección 3.6, si\(p(n)\) es una proposición sobre un universo\(U\text{,}\) su conjunto de verdad\(T_p\) es igual a un subconjunto de U. En muchos casos, como cuando\(p(n)\) es una ecuación, estamos más preocupados por si\(T_p\) está vacío o no. En otros casos, podría interesarnos si\(T_p=U\text{;}\) eso es, si\(p(n)\) es una tautología. Dado que las condiciones\(T_p\neq \emptyset\) y\(T_p=U\) son tantas veces un problema, tenemos un sistema especial de notación para ellas.

Cuantificador Existencial

Definición \(\PageIndex{1}\): The Existential Quantifier

Si\(p(n)\) es una proposición terminada\(U\) con comúnmente\(T_p\neq \emptyset\text{,}\) decimos “Existe una\(n\) en\(U\) tal que\(p(n)\) (es verdad)”. Esto lo abreviamos con los símbolos\((\exists n)_U(p(n))\text{.}\) El símbolo\(\exists\) se llama el cuantificador existencial. Si el contexto es claro,\(U\) se deja caer la mención de:\((\exists n)(p(n))\text{.}\)

Ejemplo\(\PageIndex{1}\): Some Examples of Existential Quantifiers

1. \((\exists k)_{\mathbb{Z}}(k ^2- k - 12 = 0)\)es otra forma de decir que hay un entero que resuelve la ecuación\(k^2 - k - 12 = 0\text{.}\) El hecho de que existan dos de esos enteros no afecta en modo alguno la verdad de esta proposición.
2. \((\exists k)_{\mathbb{Z}}(3k=102)\)simplemente afirma que 102 es un múltiplo de 3, lo cual es cierto. Por otra parte,\((\exists k)_{\mathbb{Z}}(3k=100)\) afirma que 100 es un múltiplo de 3, que es falso.
3. \((\exists x)_{\mathbb{R}}(x^2 + 1 = 0)\)es falso ya que el conjunto de soluciones de la ecuación\(x^2+ 1 = 0\) en los números reales está vacío. Es común escribir\((\nexists x)_{\mathbb{R}}(x^2 + 1 = 0)\) en este caso.

Hay una gran variedad de formas en las que puedes escribir una proposición con un cuantificador existencial. La tabla\(\PageIndex{1}\) contiene una lista de diferentes variaciones que podrían ser utilizadas tanto para los cuantificadores existenciales como universales.

Cuantificador Universal

Definición \(\PageIndex{2}\): The Universal Quantifier

Si\(p(n)\) es una proposición terminada\(U\), comúnmente\(T_p=U\text{,}\) decimos “Para todos\(n\) en\(U\text{,}\)\(p(n)\) (es cierto)”. Abreviamos esto con los símbolos\((\forall n)_U(p(n))\text{.}\) El símbolo\(\forall\) se llama el cuantificador universal. Si el contexto es claro,\(U\) se deja caer la mención de:\((\forall n)(p(n))\text{.}\)

Ejemplo\(\PageIndex{2}\): Some Universal Quantifiers

1. Podemos decir que el cuadrado de cada número real no es negativo simbólicamente con un cuantificador universal:\((\forall x) _{\mathbb{R}}(x ^2 \geq 0)\text{.}\)
2. \((\forall n) _{\mathbb{Z}} (n + 0 = 0 + n =n)\)dice que la suma de cero y cualquier entero\(n\) es\(n\text{.}\) Este hecho se llama la propiedad de identidad de cero para la suma.

Tabla\(\PageIndex{1}\): Variaciones Notacionales con Expresiones Cuantificadoras

Cuantificador Universal	Cuantificador Existencial
\((\forall n)_U(p(n))\)	\((\exists n)_U(p(n))\)
\((\forall n\in U)(p(n))\)	\((\exists n\in U)(p(n))\)
\(\forall n\in U, p(n)\)	\(\exists n\in U \textrm{ such that } p(n)\)
\(p(n), \forall n \in U\)	\(p(n)\)es cierto para algunos\(n \in U\)
\(p(n)\)es cierto para todos\(n \in U\)

3.8.3: Negación de Proposiciones Cuantificadas

Cuando se niega una proposición cuantificada, los cuantificadores existencial y universal se complementan entre sí.

Ejemplo\(\PageIndex{3}\): Negation of an Existential Quantifier

Sobre el universo de los animales, definir\(F(x)\text{:}\)\(x\) es un pez y\(W(x)\text{:}\)\(x\) vive en el agua. Sabemos que la proposición no siempre\(W(x) \rightarrow F(x)\) es cierta. En otras palabras,\((\forall x)(W(x) \rightarrow F(x))\) es falso. Otra forma de afirmar este hecho es que existe un animal que vive en el agua y no es un pez; es decir,

\ begin {ecuation*}\ begin {split}\ neg (\ forall x) (W (x)\ a F (x)) &\ Leftrightarrow (\ existe x) (\ neg (W (x)\ fila derecha F (x))\\ &\ Leftrightarrow (\ existe x) (W (x)\ tierra\ neg F (x))\ end {split}\ text {.} \ end {ecuación*}

Obsérvese que la negación de una proposición universalmente cuantificada es una proposición existencialmente cuantificada. Además, cuando negas una proposición cuantificada existencialmente, obtienes una proposición universalmente cuantificada. Simbólicamente,

Tabla\(\PageIndex{2}\): Negación de expresiones cuantificadas

\(\neg ((\forall n)_U(p(n)) )\Leftrightarrow (\exists n)_U (\neg p(n))\)

\(\neg ((\exists n)_U(p(n)) )\Leftrightarrow (\forall n)_U (\neg p(n))\)

Ejemplo\(\PageIndex{4}\): More Negations of Quantified Expressions

1. Los antiguos griegos descubrieron por primera vez que\(\sqrt{2}\) es un número irracional; es decir, no\(\sqrt{2}\) es un número racional. \(\neg ((\exists r)_{\mathbb{Q}}(r^2 = 2))\)y\((\forall r)_{\mathbb{Q}} (r^2\neq 2)\) ambos afirman simbólicamente este hecho.
2. \(\neg ((\forall n)_{\mathbb{P}}(n ^2- n + 41 \textrm{ is prime}))\)es equivalente a\((\exists n)_{\mathbb{P}} (n^2 - n + 41 \textrm{ is composite})\text{.}\) Ellos son ambos verdaderos o ambos falsos.

Cuantificadores múltiples

Si una proposición tiene más de una variable, entonces puedes cuantificarla más de una vez. Por ejemplo,\(p(x, y):x^2 - y^2 = (x + y)(x - y)\) es una tautología sobre el conjunto de todos los pares de números reales porque es cierto para cada par\((x, y)\) en\(\mathbb{R} \times \mathbb{R}\text{.}\) Otra forma de ver esta proposición es como una proposición con dos variables. La aseveración de que\(p(x,y)\) es una tautología podría cuantificarse como\((\forall x)_{\mathbb{R}} ((\forall y) _{\mathbb{R}}(p(x, y)))\) o\((\forall y)_{\mathbb{R}} ((\forall x) _{\mathbb{R}}(p(x, y)))\)

En general, se pueden organizar múltiples cuantificadores universales en cualquier orden sin cambiar lógicamente el significado de la propuesta resultante. Lo mismo es cierto para múltiples cuantificadores existenciales. Por ejemplo,\(p(x, y) : x + y = 4 \textrm{ and } x - y = 2\) es una proposición sobre\(\mathbb{R} \times \mathbb{R}\text{.}\)\((\exists x)_{\mathbb{R}} ((\exists y) _{\mathbb{R}} (x + y = 4 \textrm{ and } x - y = 2))\) y\((\exists y)_{\mathbb{R}}\textrm{ } ((\exists x) _{\mathbb{R}} (x + y = 4 \textrm{ and } x - y = 2))\) son equivalentes. Una proposición con múltiples cuantificadores existenciales como éste dice que existen valores simultáneos para las variables cuantificadas que hacen que la proposición sea verdadera. Un ejemplo similar es\(q(x, y) : 2x - y = 2 \textrm{ and }4x - 2y = 5\text{,}\) que siempre es falso; y los siguientes son todos equivalentes:

\ begin {ecuación*}\ begin {split}\ neg ((\ existe x) _ {\ mathbb {R}} ((\ existe y) _ {\ mathbb {R}} (q (x, y)))) &\ Leftrightarrow\ neg (\ existe y) _ {\ mathbb {R}} ((\ existe x) _ {\ mathbb {R} (q (x, y)))\\ &\ Leftrightarrow (\ forall y) _ {\ mathbb {R}} (\ neg ((\ existe x) _ {\ mathbb {R}} (q (x, y))))\\ &\ Leftrightarrow ((\ forall y) _ {\ mathbb {R}} ((\ forall x) _ {\ mathbb {R}} (\ neg q (x, y)))\\ &\ Leftrightarrow ((\ forall x) _ {\ mathbb {R}} ((\ forall y) _ {\ mathbb {R}} (\ neg q (x, y)))\ end {split}\ end {ecuación*}

Cuando se mezclan cuantificadores existenciales y universales, el orden no puede intercambiarse sin cambiar posiblemente el sentido de la proposición. Por ejemplo, dejemos\(\mathbb{R}^+\) ser los números reales positivos,\(x : (\forall a)_{\mathbb{R}^+} ((\exists b)_{\mathbb{R}^+} (a b = 1))\) y\(y : (\exists b)_{\mathbb{R}^+} ((\forall a)_{\mathbb{R}^+}(a b = 1))\) tener diferentes valores lógicos;\(x\) es verdadero, mientras que\(y\) es falso.

Consejos para la Lectura de Proposiciones Multicuantificadas. Es comprensible que encontraras proposiciones como\(x\) difíciles de leer. El truco para descifrar estas expresiones es “pelar” un cuantificador de la proposición tal como despegarías las capas de una cebolla (¡pero los cuantificadores no deberían hacerte llorar!). Dado que el cuantificador más exterior en\(x\) es universal,\(x\) dice que eso\(z(a) : (\exists b)_{\mathbb{R}^+}(a b = 1)\) es cierto para cada valor que\(a\) pueda asumir. Ahora tómese el tiempo para seleccionar un valor para\(a\text{,}\) como 6. Por el valor que seleccionamos, obtenemos\(z(6) : (\exists b)_{\mathbb{R}^+}(6b = 1)\text{,}\) lo que obviamente es cierto ya que\(6b = 1\) tiene una solución en los números reales positivos. Obtendremos ese mismo valor de verdad sin importar qué número real positivo escojamos por\(a\text{;}\) lo tanto,\(z(a)\) es una tautología sobre\(\mathbb{R}^+\) y estamos justificados al decir que eso\(x\) es cierto. La clave para entender proposiciones como\(x\) por tu cuenta es experimentar con valores reales para las variables más externas como hicimos anteriormente.

Ahora considera\(y\text{.}\) Para ver que\(y\) es falso, desprendemos el cuantificador externo. Al tratarse de un cuantificador existencial, lo único que\(y\) dice es que algún número real positivo hace\(w(b)\):\((\forall a) _{\mathbb{R}^+} (a b = 1)\) verdadero. Elige algunos valores de\(b\) para ver si puedes encontrar uno que haga\(w(b)\) realidad. Por ejemplo, si elegimos\(b = 2\text{,}\) obtenemos\((\forall a) _{\mathbb{R}^+}(2a = 1)\text{,}\) cuál es falso, ya que casi siempre\(2a\) es diferente de 1. Deberías ser capaz de convencerte de que ningún valor de\(b\) hará\(w(b)\) realidad. Por lo tanto,\(y\) es falso.

Otra forma de convencerte de que\(y\) es falso es convencerte de que\(\neg y\) es verdad:

\ begin {ecuación*}\ begin {split}\ neg ((\ existe b) _ {\ mathbb {R} ^+} ((\ forall a) _ {\ mathbb {R} ^+} (a b = 1))) &\ Leftrightarrow (\ forall b) _ {\ mathbb {R} ^+}\ neg ((\ forall a) _ {\ mathbb {R} ^+} (a b = 1))\\ &\ Leftrightarrow (\ forall b) _ {\ mathbb {R} ^+} ((\ existe a) _ {\ mathbb {R} ^+} (a b\ neq 1))\ end {split}\ end {ecuación*}

En palabras, para cada valor de\(b\text{,}\) hay un valor para\(a\) que hace\(a b \neq 1\text{.}\) Uno tal valor es\(a=\frac{1}{b}+1\text{.}\) Por lo tanto,\(\neg y\) es cierto.

Ejercicios

Ejercicio\(\PageIndex{1}\)

Dejar\(C(x)\) ser “\(x\)es de sangre fría”, dejar\(F(x)\) ser “\(x\)es un pez”, y dejar\(S(x)\) ser “\(x\)vive en el mar”.

1. Traducir en una fórmula: Cada pez es de sangre fría.
2. Traducir al inglés:\((\exists x)(S(x) \land \neg F(x))\text{.}\)
3. Traducir al inglés:\((\forall x)(F(x) \rightarrow S(x))\text{.}\)

Responder

1. \(\displaystyle (\forall x)(F(x)\to C(x))\)
2. Hay objetos en el mar que no son peces.
3. Todos los peces viven en el mar.

Ejercicio\(\PageIndex{2}\)

Let\(M(x)\) be “\(x\)es un mamífero”, deja\(A(x)\) ser “\(x\)es un animal”, y dejar\(W(x)\) ser “\(x\)es de sangre caliente”.

1. Traduzca en una fórmula: Cada mamífero es de sangre caliente.
2. Traducir al inglés:\((\exists x)(A(x) \land (\neg M(x)))\text{.}\)

Ejercicio\(\PageIndex{3}\)

Sobre el universo de los libros, definir las proposiciones\(B(x)\text{:}\)\(x\) tiene una portada azul,\(M(x)\text{:}\)\(x\) es un libro de matemáticas,\(U(x)\text{:}\)\(x\) se publica en Estados Unidos, y\(R(x, y)\): La bibliografía de\(x\) incluye\(y\text{.}\)

Traducir en palabras:

1. \((\exists x)(\neg B(x))\text{.}\)
2. \((\forall x)(M(x) \land U(x) \rightarrow B(x))\text{.}\)
3. \((\exists x)(M(x) \land \neg B(x))\text{.}\)
4. \((\exists y)((\forall x)(M(x)\to R(x,y)))\text{.}\)
5. Expresar usando cuantificadores: Cada libro con portada azul es un libro de matemáticas.
6. Expresar usando cuantificadores: Hay libros de matemáticas que se publican fuera de Estados Unidos.
7. Expresar usando cuantificadores: No todos los libros tienen bibliografías.

Responder

1. Hay un libro con una portada que no es azul.
2. Cada libro de matemáticas que se publica en Estados Unidos tiene una portada azul.
3. Existe un libro de matemáticas con una portada que no es azul.
4. Existe un libro que aparece en la bibliografía de cada libro de matemáticas.
5. \(\displaystyle (\forall x)(B(x)\to M(x))\)
6. \(\displaystyle (\exists x)(M(x)\land \neg U(x))\)
7. \(\displaystyle (\exists x)((\forall y)(\neg R(x,y))\)

Ejercicio\(\PageIndex{4}\)

Que el universo del discurso,\(U\text{,}\) sea el conjunto de todas las personas, y que\(M(x, y)\) sea “\(x\)es la madre de\(y\text{.}\)”

¿Cuál de las siguientes es una afirmación verdadera? Traducirlo al inglés.

1. \(\displaystyle (\exists x)_U((\forall y)_U(M(x,y)))\)
2. \(\displaystyle (\forall y)_U((\exists x)_U(M(x,y)))\)
3. Traducir la siguiente declaración en notación lógica utilizando cuantificadores y la proposición\(M(x, y)\): “Todo el mundo tiene una abuela materna”.

Ejercicio\(\PageIndex{5}\)

Traduzca a sus propias palabras e indique si es verdadero o falso que\((\exists u) _{\mathbb{Z}} (4 u^2 -9 = 0)\text{.}\)

Responder

La ecuación\(4u^2-9=0\) tiene una solución en los enteros. (Falso)

Ejercicio\(\PageIndex{6}\)

Usa cuantificadores para decir que\(\sqrt{3}\) es un número irracional.

Pista

Tu respuesta dependerá de tu elección de un universo

Ejercicio\(\PageIndex{7}\)

¿Qué dicen las siguientes proposiciones, dónde\(U\) está el conjunto de poderes de ¿\(\{1,2,\dots , 9\}\text{?}\)Cuál de estas proposiciones son ciertas?

1. \((\forall A)_U \lvert A \rvert \neq \lvert A^c \rvert\text{.}\)
2. \((\exists A)_U(\exists B)_U (\lvert A \rvert =5, \lvert B \rvert=5, \textrm{ and } A\cap B=\emptyset )\text{.}\)
3. \((\forall A)_U(\forall B)_U (A-B=B^c-A^c)\text{.}\)

Responder

1. Cada subconjunto de\(U\) has a cardinality different from its complement. (True)
2. Hay un par de subconjuntos disjuntos de\(U\) ambos que tienen cardinalidad 5. (Falso)
3. \(A-B=B^c-A^c\)es una tautología. (Verdadero)

Ejercicio\(\PageIndex{8}\)

Utilice cuantificadores para indicar que para cada entero positivo, hay un entero positivo más grande.

Ejercicio\(\PageIndex{9}\)

Utilice cuantificadores para afirmar que la suma de dos números racionales cualesquiera es racional.

Responder

\((\forall a)_{\mathbb{Q}}(\forall b)_{\mathbb{Q}}\)(\(a+b\)es un número racional.)

Ejercicio\(\PageIndex{10}\)

Sobre el universo de los números reales, use cuantificadores para decir que la ecuación\(a + x = b\) tiene una solución para todos los valores de\(a\) y\(b\text{.}\)

Pista

Necesitarás tres cuantificadores.

Ejercicio\(\PageIndex{11}\)

Dejar\(n\) ser un entero positivo. Describir usando cuantificadores:

1. \(\displaystyle x \in \underset{k=1}{\overset{n}{\cup }}A_k\)
2. \(\displaystyle x \in \underset{k=1}{\overset{n}{\cap }}A_k\)

Responder

Let\(I=\{1,2,3,\ldots ,n\}\)

1. \(\displaystyle (\exists x)_I\left(x\in A_i\right)\)
2. \(\displaystyle (\forall x)_I\left(x\in A_i\right)\)

Ejercicio\(\PageIndex{12}\)

Demuéstralo\((\exists x)(\forall y)(p(x, y)) \Rightarrow (\forall y)(\exists x)(p(x, y))\text{,}\) pero que lo contrario no es cierto.