3.6: Ejercicios

EJERCICIO 3.1. Probar las leyes de Morgan, (3.3) y (3.4). (Pista: Hay cuatro posibles asignaciones de valores de verdad 0 y 1 a las dos afirmaciones\(P\) y\(Q\). Para cada una de esas tareas, evalúe los valores de verdad de los lados izquierdo y derecho de (3.3) y demuestre que siempre son los mismos).

EJERCICIO 3.2. Demostrar que las declaraciones compuestas\(P\) y\(Q\) son proposicionalmente equivalentes iff\(P \Longleftrightarrow Q\).

EJERCICIO 3.3. Dar un ejemplo de una declaración condicional verdadera en la que la consecuencia es falsa. EJERCICIO 3.4. Si\(P, Q\) y\(R\) son declaraciones, probar que son ciertas las siguientes:
a)\(P \wedge \neg P \Rightarrow Q\)
b)\([(P \Rightarrow Q) \wedge(Q \Rightarrow R)] \Rightarrow(P \Rightarrow R)\)
c)\([P \Rightarrow(Q \wedge \neg Q)] \Rightarrow \neg P\)
d)\([P \wedge(P \Rightarrow Q)] \Rightarrow Q\)
e) \(P \Rightarrow(Q \vee \neg Q)\).

EJERCICIO 3.5. Dejar\(P\) y\(Q\) ser declaraciones. Demostrar que hay declaraciones usando solamente\(P, Q, \neg\) y\(\wedge\) que son proposicionalmente equivalentes a
a)\(P \wedge Q\)
b)\(P \vee Q\)
c)\(P \Rightarrow Q\).

Demostrar que hay declaraciones usando solamente\(P, Q, \neg\) y\(\vee\) que son equivalentes a lo anterior.

EJERCICIO 3.6. Demostrar las leyes distributivas para la lógica proposicional: Si\(P, Q\) y\(R\) son declaraciones, entonces
a)\(P \vee(Q \wedge R) \equiv(P \vee Q) \wedge(P \vee R)\)
b)\(P \wedge(Q \vee R) \equiv(P \wedge Q) \vee(P \wedge R)\).

EJERCICIO 3.7. Demostrar la ley distributiva para conjuntos: Si\(X, Y\) y\(Z\) son conjuntos, entonces
a)\(X \cup(Y \cap Z)=(X \cup Y) \cap(X \cup Z)\)
b)\(X \cap(Y \cup Z)=(X \cap Y) \cup(X \cap Z)\).

EJERCICIO 3.8. Dejar conjuntos\(X, Y\) y\(Z\) ser conjuntos característicos de fórmulas\(P(x), Q(x)\) y\(R(x)\) respectivamente. Para cada región posible del diagrama de Venn\(X, Y\) y\(Z\) dar una fórmula compuesta (con fórmulas atómicas\(P, Q\) y\(R\)) que tiene esa región como su conjunto característico.

EJERCICIO 3.9. Escribe una fórmula en una variable que defina los enteros pares.

EJERCICIO 3.10. Escribe una fórmula que defina cuadrados perfectos. EJERCICIO 3.11. Escribe una fórmula en dos variables que defina los puntos en los\(\mathbb{R}^{2}\) que tengan distancia 1 del punto\((\pi, e)\).

EJERCICIO 3.12. ¿Se puede escribir una fórmula en una variable usando solo suma, multiplicación, exponenciación, enteros e igualdad, para definir el conjunto de todas las raíces de un polinomio dado con coeficientes enteros? ¿Qué tal el conjunto de raíces de todos los polinomios con coeficientes enteros?

EJERCICIO 3.13. ¿Cuáles de las siguientes afirmaciones son ciertas?
a)\((\forall x \in \mathbb{R}) x+1>x\)
b)\((\forall x \in \mathbb{Z}) x^{2}>x\)
c)\((\exists x \in \mathbb{Z})(\forall y \in \mathbb{Z}) x \leq y\)
d)\((\forall y \in \mathbb{Z})(\exists x \in \mathbb{Z}) x \leq y\)
e)\((\forall \varepsilon>0)(\exists \delta>0)(\forall x \in \mathbb{R})[0<|x-1|<\delta] \Rightarrow\left[\left|x^{2}-1\right|<\varepsilon\right]\).

EJERCICIO 3.14. ¿Cuál es la negación de cada afirmación en el Ejercicio 3.13? ¿Cuál de las negaciones es verdad?

EJERCICIO 3.15. Dejar\(a, L \in \mathbb{R}\) y\(f\) ser una función real. Demostrar que las declaraciones\[(\forall \varepsilon>0)(\exists \delta>0)(\forall x \in \operatorname{Dom}(f))[0<|x-a|<\delta] \Rightarrow[|f(x)-L|<\varepsilon]\] y no\[(\exists \delta>0)(\forall \varepsilon>0)(\forall x \in \operatorname{Dom}(f))[0<|x-a|<\delta] \Rightarrow[|f(x)-L|<\varepsilon]\] son equivalentes. ¿Qué afirmación es consecuencia de la otra?

EJERCICIO 3.16. Dejar\(P(x, y)\) ser una fórmula en dos variables. Demostrar que en general no\((\forall x)(\exists y) P(x, y)\) necesita ser equivalente a\((\exists y)(\forall x) P(x, y)\). Demostrar que\((\forall x)(\forall y) P(x, y)\) es equivalente a\((\forall y)(\forall x) P(x, y)\). ¿Qué pasa\((\exists x)(\exists y) P(x, y)\) y\((\exists y)(\exists x) P(x, y)\)?

EJERCICIO 3.17. Considera las siguientes afirmaciones. Anote lo contrapositivo y lo contrario a cada uno.

(i) Todos los hombres son mortales.

(ii) Me refiero a lo que digo. (iii) Toda función continua en el intervalo\([0,1]\) alcanza su máximo

(iv) La suma de los ángulos de un triángulo es\(180^{\circ}\).

EJERCICIO 3.18. Demostrar que un número es divisible por 4 si y sólo si sus dos últimos dígitos lo son.

EJERCICIO 3.19. Demostrar que un número es divisible por 8 si sus últimos tres dígitos son.

EJERCICIO 3.20. Demostrar que un número es divisible\(2^{n}\) por si sus últimos\(n\) dígitos son.

EJERCICIO 3.21. Supongamos que\(m\) es un número con la propiedad de que cualquier número natural es\(m\) divisible por si sus últimos tres dígitos son. ¿De qué dice esto\(m\)? Demuestra tu aseveración.

EJERCICIO 3.22. Demostrar que un entero es divisible por 11 si la suma de los dígitos colocados extrañamente menos la suma de los dígitos colocados uniformemente es divisible por 11. (Entonces\(11 \mid 823493\) iff 11 divide\((2+4+3)-(8+3+9)\).)

EJERCICIO 3.23. Mostrar que cada intervalo contiene números racionales e irracionales.

EJERCICIO 3.24. Demostrar que\(\sqrt{3}\) es irracional.

EJERCICIO 3.25. Demostrar que\(\sqrt{10}\) es irracional.

EJERCICIO 3.26. Demostrar que la raíz cuadrada de cualquier número natural es un número entero o irracional.

EJERCICIO 3.27. Demostrar que existen números irracionales\(x\) y\(y\) entonces eso\(x^{y}\) es racional. (Pista: considerar\(\sqrt{2}^{\sqrt{2}}\) y\(\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}\).)

EJERCICIO 3.28. Demostrar o desmentir la siguiente aseveración: Cualesquiera 4 puntos en el plano, ninguno de los cuales tres son colineales, se encuentran en un círculo.

EJERCICIO 3.29. Demostrar que hay un número infinito de primos. EJERCICIO 3.30. Para\(k=0,1,2\), deja\(P_{k}\) ser el conjunto de números primos que son congruentes con\(k \bmod 3\). Por el Ejercicio 3.29,\(P_{0} \cup P_{1} \cup P_{2}\) es infinito. ¿Se puede decir cuáles de los conjuntos\(P_{0}, P_{1}\) y\(P_{2}\) son infinitos?

(Comentario: Para dos de los tres conjuntos, este problema no es demasiado difícil. Para el tercero, es sumamente difícil, y es un caso especial de un célebre teorema de Dirichlet. Ver\(e . g\). [8] para un tratamiento del teorema de Dirichlet.)

EJERCICIO 3.31. Que los puntos en\(\mathbb{R}^{2}\) sean de color rojo, verde y azul. Demostrar que o bien hay dos puntos del mismo color a una distancia 1 de distancia, o bien hay un triángulo equilátero de longitud lateral\(\sqrt{3}\) todos cuyos vértices son del mismo color.

EJERCICIO 3.32. Demostrar que\[e=\sum_{n=0}^{\infty} \frac{1}{n !}\] es irracional. (Pista: Argumenta por contradicción. Asumir\(e=\frac{p}{q}\), y multiplicar ambos lados por\(q !\) Reorganizar la ecuación para obtener un entero igual a una suma infinita de números racionales que converge a un número en\((0,1)\).)