3.S: Lógica Simbólica y Pruebas (Resumen)

Template:MathJaxLevin

Hemos considerado la lógica tanto como su propia subdisciplina de las matemáticas, como un medio para ayudarnos a comprender mejor y escribir pruebas. En cualquiera de los dos puntos de vista, notamos que las declaraciones matemáticas tienen una forma lógica particular, y analizarla puede ayudar a darle sentido a la declaración.

En el nivel más básico, una sentencia podría combinar declaraciones más simples usando conectivas lógicas. A menudo hacemos uso de variables, y cuantificamos sobre esas variables. Cómo resolver la verdad o falsedad de una afirmación basada en estos conectivos y cuantificadores es de lo que se trata la lógica. A partir de esto, podemos decidir si dos declaraciones son lógicamente equivalentes o si una o más afirmaciones (lógicamente) implican otra.

Al escribir pruebas (en cualquier área de las matemáticas) nuestro objetivo es explicar por qué una afirmación matemática es cierta. Por lo tanto, es vital que nuestro argumento implique la verdad de la afirmación. Para estar seguros de ello, primero debemos saber qué significa que la afirmación sea cierta, así como asegurar que las declaraciones que conforman la prueba impliquen correctamente la conclusión. Se requiere una comprensión firme de la lógica para verificar si una prueba es correcta.

Hay, sin embargo, otra razón por la que entender la lógica puede ser útil. Comprender la estructura lógica de una declaración a menudo da pistas sobre cómo escribir una prueba de la declaración.

Esto no quiere decir que escribir pruebas sea siempre sencillo. Consideremos nuevamente la conjetura de Goldbach:

Cada número par mayor a 2 se puede escribir como la suma de dos primos.

Aquí no vamos a intentar probar la afirmación, pero al menos podemos decir cómo podría ser una prueba, con base en la forma lógica de la declaración. Quizás deberíamos escribir la declaración de una manera equivalente que resalta mejor los cuantificadores y conectivos:

Para todos los enteros\(n\text{,}\) si\(n\) es par y mayor que 2, entonces existe enteros\(p\) y\(q\) tal que\(p\) y\(q\) son primos y\(n = p+q\text{.}\)

¿Cómo sería una prueba directa? Dado que la sentencia comienza con un cuantificador universal, comenzaríamos por, “Let\(n\) be an arbitary integer”. El resto de la declaración es una implicación. En una prueba directa asumimos la parte “si”, por lo que la siguiente línea sería, “Asumir\(n\) es mayor que 2 y es par”. No tengo idea de lo que viene después, pero eventualmente, necesitaríamos encontrar dos números primos\(p\) y\(q\) (dependiendo de\(n\)) y explicar cómo sabemos eso\(n = p+q\text{.}\)

O tal vez intentamos una prueba por contradicción. Para ello, primero asumimos la negación de la declaración que queremos probar. ¿Cuál es la negación? Por lo que hemos estudiado deberíamos poder ver que es,

Hay un entero\(n\) tal que\(n\) es par y mayor que\(2\text{,}\) pero para todos los enteros\(p\) y\(q\text{,}\) cualquiera\(p\) o no\(q\) es primo o\(n \ne p+q\text{.}\)

¿Podría ser cierta esta afirmación? Una prueba por contradicción comenzaría asumiendo que lo era y finalmente concluiría con una contradicción, demostrando que nuestra asunción de la verdad era incorrecta. Y si puedes encontrar tal contradicción, habrás demostrado ser el problema abierto más famoso de las matemáticas. Buena suerte.

Revisión del Capítulo

1

Completa una tabla de verdad para la declaración\(\neg P \imp (Q \wedge R)\text{.}\)

Solución

\(P\)	\(Q\)	\(R\)	\(\neg P \imp (Q \wedge R)\)
\ (P\) "> T	\ (Q\) "> T	\ (R\) "> T	\ (\ neg P\ imp (Q\ cuña R)\) "> T
\ (P\) "> T	\ (Q\) "> T	\ (R\) "> F	\ (\ neg P\ imp (Q\ cuña R)\) "> T
\ (P\) "> T	\ (Q\) "> F	\ (R\) "> T	\ (\ neg P\ imp (Q\ cuña R)\) "> T
\ (P\) "> T	\ (Q\) "> F	\ (R\) "> F	\ (\ neg P\ imp (Q\ cuña R)\) "> T
\ (P\) "> F	\ (Q\) "> T	\ (R\) "> T	\ (\ neg P\ imp (Q\ cuña R)\) "> T
\ (P\) "> F	\ (Q\) "> T	\ (R\) "> F	\ (\ neg P\ imp (Q\ cuña R)\) "> F
\ (P\) "> F	\ (Q\) "> F	\ (R\) "> T	\ (\ neg P\ imp (Q\ cuña R)\) "> F
\ (P\) "> F	\ (Q\) "> F	\ (R\) "> F	\ (\ neg P\ imp (Q\ cuña R)\) "> F

2

Supongamos que sabes que la afirmación “si Peter no es alto, entonces Quincy es gordo y Robert es flaco” es falsa. ¿Qué, si acaso, puedes concluir sobre Peter y Robert si sabes que Quincy es realmente gordo? Explique (puede hacer referencia al problema\(\PageIndex{1}\)).

Solución

Peter no es alto y Robert no es flaco. Debes estar en la fila 6 en la tabla de verdad anterior.

3

¿Son las declaraciones\(P \imp (Q \vee R)\) y\((P \imp Q) \vee (P \imp R)\) lógicamente equivalentes? Explica tu respuesta.

Solución

Sí. Para ver esto, haga una tabla de verdad para cada enunciado y compare.

4

¿Es válida la siguiente regla de deducción? Explique.

	\(P \imp Q\)
	\(P\imp R\)
\(\therefore\)	\(P \imp (Q \wedge R)\text{.}\)

Solución

Haga una tabla de verdad que incluya las tres declaraciones en el argumento:

\(P\)	\(Q\)	\(R\)	\(P \imp Q\)	\(P \imp R\)	\(P \imp (Q \wedge R)\)
\ (P\)” style="vertical-align:middle; "> T	\ (Q\)” style="vertical-align:middle; "> T	\ (R\)” style="vertical-align:middle; "> T	\ (P\ imp Q\)” style="vertical-align:middle; "> T	\ (P\ imp R\)” style="vertical-align:middle; "> T	\ (P\ imp (Q\ cuña R)\)” style="vertical-align:middle; "> T
\ (P\)” style="vertical-align:middle; "> T	\ (Q\)” style="vertical-align:middle; "> T	\ (R\)” style="vertical-align:middle; "> F	\ (P\ imp Q\)” style="vertical-align:middle; "> T	\ (P\ imp R\)” style="vertical-align:middle; "> F	\ (P\ imp (Q\ cuña R)\)” style="vertical-align:middle; "> F
\ (P\)” style="vertical-align:middle; "> T	\ (Q\)” style="vertical-align:middle; "> F	\ (R\)” style="vertical-align:middle; "> T	\ (P\ imp Q\)” style="vertical-align:middle; "> F	\ (P\ imp R\)” style="vertical-align:middle; "> T	\ (P\ imp (Q\ cuña R)\)” style="vertical-align:middle; "> F
\ (P\)” style="vertical-align:middle; "> T	\ (Q\)” style="vertical-align:middle; "> F	\ (R\)” style="vertical-align:middle; "> F	\ (P\ imp Q\)” style="vertical-align:middle; "> F	\ (P\ imp R\)” style="vertical-align:middle; "> F	\ (P\ imp (Q\ cuña R)\)” style="vertical-align:middle; "> F
\ (P\)” style="vertical-align:middle; "> F	\ (Q\)” style="vertical-align:middle; "> T	\ (R\)” style="vertical-align:middle; "> T	\ (P\ imp Q\)” style="vertical-align:middle; "> T	\ (P\ imp R\)” style="vertical-align:middle; "> T	\ (P\ imp (Q\ cuña R)\)” style="vertical-align:middle; "> T
\ (P\)” style="vertical-align:middle; "> F	\ (Q\)” style="vertical-align:middle; "> T	\ (R\)” style="vertical-align:middle; "> F	\ (P\ imp Q\)” style="vertical-align:middle; "> T	\ (P\ imp R\)” style="vertical-align:middle; "> T	\ (P\ imp (Q\ cuña R)\)” style="vertical-align:middle; "> T
\ (P\)” style="vertical-align:middle; "> F	\ (Q\)” style="vertical-align:middle; "> F	\ (R\)” style="vertical-align:middle; "> T	\ (P\ imp Q\)” style="vertical-align:middle; "> T	\ (P\ imp R\)” style="vertical-align:middle; "> T	\ (P\ imp (Q\ cuña R)\)” style="vertical-align:middle; "> T
\ (P\)” style="vertical-align:middle; "> F	\ (Q\)” style="vertical-align:middle; "> F	\ (R\)” style="vertical-align:middle; "> F	\ (P\ imp Q\)” style="vertical-align:middle; "> T	\ (P\ imp R\)” style="vertical-align:middle; "> T	\ (P\ imp (Q\ cuña R)\)” style="vertical-align:middle; "> T

Observe que en cada fila para la que tanto\(P \imp Q\) and \(P \imp R\) is true, so is \(P \imp (Q \wedge R)\text{.}\) Therefore, whenever the premises of the argument are true, so is the conclusion. In other words, the deduction rule is valid.

5

Escribir la negación, conversar y contrapositivo para cada una de las declaraciones a continuación.

1. Si se apaga la alimentación, entonces la comida se echará a perder.
2. Si la puerta está cerrada, entonces la luz está apagada.
3. \(\forall x (x \lt 1 \imp x^2 \lt 1)\text{.}\)
4. Para todos los números naturales\(n\text{,}\) si\(n\) es primo, entonces\(n\) es solitario.
5. Para todas las funciones\(f\text{,}\) si\(f\) es diferenciable, entonces\(f\) es continuo.
6. Para todos los enteros\(a\) y\(b\text{,}\) si\(a\cdot b\) es par, entonces\(a\) y\(b\) son pares.
7. Por cada entero\(x\) y cada entero\(y\) hay un entero\(n\) tal que si\(x > 0\) entonces\(nx > y\text{.}\)
8. Para todos los números reales\(x\) y\(y\text{,}\) si\(xy = 0\) entonces\(x = 0\) o\(y = 0\text{.}\)
9. Por cada alumno en Matemáticas 228, si no entiende las implicaciones, entonces reprobarán el examen.

Solución

1. Converse: Si la comida se estropea, entonces se apagó la energía.

   Contrapositivo: Si la comida no se echa a perder, entonces la energía no se apagó.

2. Converse: Si la luz está apagada entonces la puerta está cerrada.

   Contrapositivo: Si la luz está encendida entonces la puerta está abierta.

3. Conversar:\(\forall x( x^2 \lt 1 \imp x \lt 1)\)

   Contrapositivo:\(\forall x (x^2 \ge 1 \imp x \ge 1)\text{.}\)

4. Converse: Para todos los números naturales\(n\text{,}\) if \(n\) is solitary, then \(n\) is prime.

   Contrapositivo: Para todos los números naturales\(n\text{,}\) if \(n\) is not solitary then \(n\) is not prime.

5. Converse: Para todas las funciones\(f\text{,}\) if \(f\) is continuous then \(f\) is differentiable.

   Contrapositivo: Para todas las funciones\(f\text{,}\) if \(f\) is not continuous then \(f\) is not differentiable.

6. Converse: Para todos los enteros\(a\) and \(b\text{,}\) if \(a\) and \(b\) are even then \(ab\) is even.

   Contrapositivo: Para todos los enteros\(a\) and \(b\text{,}\) if \(a\) or \(b\) is odd, then \(ab\) is odd.

7. Converse: Por cada entero\(x\) and every integer \(y\) there is an integer \(n\) such that if \(nx > y\) then \(x > 0\text{.}\)

   Contrapositivo: Por cada entero\(x\) and every integer \(y\) there is an integer \(n\) such that if \(nx \le y\) then \(x \le 0\text{.}\)

8. Converse: Para todos los números reales\(x\) and \(y\text{,}\) if \(x = 0\) or \(y = 0\) then \(xy = 0\)

   Contrapositivo: Para todos los números reales\(x\) and \(y\text{,}\) if \(x \ne 0\) and \(y \ne 0\) then \(xy \ne 0\text{.}\)

9. Converse: Por cada alumno en Matemáticas 228, si reprueban el examen, entonces no entendieron las implicaciones.

   Contrapositivo: Por cada alumno en Matemáticas 228, si aprueba el examen, entonces entendió implicaciones.

6

Considere la sentencia: para todos los enteros\(n\text{,}\) si\(n\) es par y\(n \le 7\) luego\(n\) es negativo o\(n \in \{0,2,4,6\}\text{.}\)

1. ¿Es verdad la afirmación? Explique por qué.
2. Escribir la negación de la declaración. ¿Es verdad? Explique.
3. Indicar el contrapositivo de la declaración. ¿Es verdad? Explique.
4. Declarar lo contrario de la declaración. ¿Es verdad? Explique.

Solución

1. El enunciado es cierto. Si\(n\) is an even integer less than or equal to 7, then the only way it could not be negative is if \(n\) was equal to 0, 2, 4, or 6.
2. Hay un entero\(n\) such that \(n\) is even and \(n \le 7\) but \(n\) is not negative and \(n \not\in \{0,2,4,6\}\text{.}\) This is false, since the original statement is true.
3. Para todos los enteros\(n\text{,}\) if \(n\) is not negative and \(n \not\in\{0,2,4,6\}\) then \(n\) is odd or \(n > 7\text{.}\) This is true, since the contrapositive is equivalent to the original statement (which is true).
4. Para todos los enteros\(n\text{,}\) if \(n\) is negative or \(n \in \{0,2,4,6\}\) then \(n\) is even and \(n \le 7\text{.}\) This is false. \(n = -3\) is a counterexample.

7

Considera la declaración:\(\forall x (\forall y (x + y = y) \imp \forall z (x\cdot z = 0))\text{.}\)

1. Explique en palabras lo que dice la declaración. ¿Es cierta esta afirmación? Asegúrate de exponer lo que estás tomando como ser el universo del discurso.
2. Escribe lo contrario de la declaración, tanto en palabras como en símbolos. ¿Es cierto lo contrario?
3. Escribir el contrapositivo de la declaración, tanto en palabras como en símbolos. ¿Es cierto lo contrapositivo?
4. Escribir la negación de la declaración, tanto en palabras como en símbolos. ¿Es verdad la negación?

Solución

1. Para cualquier número\(x\text{,}\) if it is the case that adding any number to \(x\) gives that number back, then multiplying any number by \(x\) will give 0. This is true (of the integers or the reals). The “if” part only holds if \(x = 0\text{,}\) and in that case, anything times \(x\) will be 0.
2. Lo contrario en palabras es esto: para cualquier número\(x\text{,}\) if everything times \(x\) is zero, then everything added to \(x\) gives itself. Or in symbols: \(\forall x (\forall z (x \cdot z = 0) \imp \forall y (x + y = y))\text{.}\) The converse is true: the only number which when multiplied by any other number gives 0 is \(x = 0\text{.}\) And if \(x = 0\text{,}\) then \(x + y = y\text{.}\)
3. El contrapositivo en palabras es: para cualquier número\(x\text{,}\) if there is some number which when multiplied by \(x\) does not give zero, then there is some number which when added to \(x\) does not give that number. In symbols: \(\forall x (\exists z (x\cdot z \ne 0) \imp \exists y (x + y \ne y))\text{.}\) We know the contrapositive must be true because the original implication is true.
4. La negación: hay un número\(x\) such that any number added to \(x\) gives the number back again, but there is a number you can multiply \(x\) by and not get 0. In symbols: \(\exists x (\forall y (x + y = y) \wedge \exists z (x \cdot z \ne 0))\text{.}\) Of course since the original implication is true, the negation is false.

8

Escriba cada una de las siguientes declaraciones en la forma, “si..., entonces...” Cuidado, algunas de las afirmaciones pueden ser falsas (lo cual está bien para los efectos de esta pregunta).

1. Para bajar de peso, debes hacer ejercicio.
2. Para bajar de peso, todo lo que necesitas hacer es hacer ejercicio.
3. Todo americano es patriótico.
4. Eres patriótico sólo si eres estadounidense.
5. El conjunto de números racionales es un subconjunto de los números reales.
6. Un número es primo si no es par.
7. O los Broncos ganarán el Super Bowl, o no jugarán en el Super Bowl.

Solución

1. Si has perdido peso, entonces has hecho ejercicio.
2. Si haces ejercicio, entonces perderás peso.
3. Si eres estadounidense, entonces eres patriótico.
4. Si eres patriótico, entonces eres estadounidense.
5. Si un número es racional, entonces es real.
6. Si un número no es par, entonces es primo. (O el contrapositivo: si un número no es primo, entonces es par).
7. Si los Broncos no ganan el Super Bowl, entonces no jugaron en el Super Bowl. Alternativamente, si los Broncos juegan en el Super Bowl, entonces ganarán el Super Bowl.

9

Simplifica lo siguiente.

1. \(\neg (\neg (P \wedge \neg Q) \imp \neg(\neg R \vee \neg(P \imp R)))\text{.}\)
2. \(\neg \exists x \neg \forall y \neg \exists z (z = x + y \imp \exists w (x - y = w))\text{.}\)

Solución

1. \((\neg P \vee Q) \wedge (\neg R \vee (P \wedge \neg R))\text{.}\)
2. \(\forall x \forall y \forall z (z = x+y \wedge \forall w (x-y \ne w))\text{.}\)

10

Considera la sentencia: para todos los enteros\(n\text{,}\) si\(n\) es impar, entonces\(7n\) es impar.

1. Demostrar la declaración. ¿Qué tipo de prueba estás usando?
2. Demostrar lo contrario. ¿Qué tipo de prueba estás usando?

Solución

1. Prueba directa.

   Prueba

   Let\(n\) be an integer. Assume \(n\) is odd. So \(n = 2k+1\) for some integer \(k\text{.}\) Then

   \ begin {ecuación*} 7n = 7 (2k+1) = 14k + 7 = 2 (7k +3) + 1. \ end {ecuación*}

   Desde\(7k + 3\) is an integer, we see that \(7n\) is odd.

2. Lo contrario es: para todos los enteros\(n\text{,}\) if \(7n\) is odd, then \(n\) is odd. We will prove this by contrapositive.

   Prueba

   Let\(n\) be an integer. Assume \(n\) is not odd. Then \(n = 2k\) for some integer \(k\text{.}\) So \(7n = 14k = 2(7k)\) which is to say \(7n\) is even. Therefore \(7n\) is not odd.

11

Supongamos que rompes tu alcancía y recoges un puñado de 22 monedas (centavos, cinco centavos, monedas de diez centavos y cuartos).

1. Demuestra que debes tener al menos 6 monedas de una sola denominación.
2. Supongamos que tiene un número impar de centavos. Demuestra que debes tener un número impar de al menos uno de los otros tipos de monedas.
3. ¿Cuántas monedas necesitarías sacar para estar seguro de que tenías 4 monedas que eran todas iguales o 4 monedas que eran todas diferentes? Demuestra tu respuesta.

Solución

1. Supongamos que solo tenías 5 monedas de cada denominación. Esto significa que tienes 5 centavos, 5 monedas de cinco centavos, 5 centavos y 5 cuartos. Se trata de un total de 20 monedas. Pero tienes más de 20 monedas, por lo que debes tener más de 5 de al menos un tipo.
2. Pero esto dice que el número de centavos también es par (es 2 veces un entero). Así hemos establecido el contrapositivo del enunciado, “Si tienes un número impar de centavos entonces tienes un número impar de al menos otro tipo de moneda”.

3. Necesitas 10 monedas. Podrías tener 3 centavos, 3 nickels y 3 dimes. La décima moneda debe ser un cuarto, dándote 4 monedas que son todas diferentes, o bien un 4to centavo, níquel o moneda de diez centavos. Para probarlo, suponga que no tienes 4 monedas que sean todas iguales o todas diferentes. En particular, esto dice que solo tienes 3 tipos de monedas, y cada uno de esos tipos solo puede contener 3 monedas, para un total de 9 monedas, que es menos de 10.

12

Te encuentras con cuatro trolls jugando bridge. Declaran:

• Troll 1: Todos los trolls aquí ven al menos una brasa.
• Troll 2: Veo por lo menos un troll que ve sólo los knaves.
• Troll 3: Algunos trolls tienen miedo de las cabras.
• Troll 4: Todos los trolls tienen miedo de las cabras.

¿Hay trolls que no le tengan miedo a las cabras? Recordemos, claro, que todos los trolls son o bien caballeros (que siempre dicen la verdad) o brillos (que siempre mienten).