Saltar al contenido principal
LibreTexts Español

3.E: Lógica Simbólica y Pruebas (Ejercicios)

  • Page ID
    115882
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Template:MathJaxLevin

    3.1: Lógica Proposicional

    1

    Considera la declaración sobre una fiesta, “Si es tu cumpleaños o habrá pastel, entonces habrá pastel”.

    1. Traducir la declaración anterior en símbolos. Declarar claramente cuál es la declaración\(P\) y cuál es\(Q\text{.}\)
    2. Hacer una tabla de verdad para la declaración.
    3. Asumiendo que la afirmación es cierta, ¿qué (si acaso) puedes concluir si habrá pastel?
    4. Asumiendo que la afirmación es cierta, ¿qué (si acaso) puedes concluir si no habrá pastel?
    5. Supongamos que se enteró de que la declaración era mentira. ¿Qué puedes concluir?
    Solución
    1. \(P\text{:}\) it's your birthday; \(Q\text{:}\) there will be cake. \((P \vee Q) \imp Q\)
    2. Pista: deberías obtener tres T y una F.
    3. Sólo que habrá pastel.
    4. ¡NO es tu cumpleaños!
    5. Es tu cumpleaños, pero el pastel es mentira.

    2

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

    Solución
    \(P\) \(Q\) \((P \vee Q) \imp (P \wedge Q)\)
    \ (P\) "> T \ (Q\) "> T \ ((P\ vee Q)\ imp (P\ cuña Q)\) "> T
    \ (P\) "> T \ (Q\) "> F \ ((P\ vee Q)\ imp (P\ cuña Q)\) "> F
    \ (P\) "> F \ (Q\) "> T \ ((P\ vee Q)\ imp (P\ cuña Q)\) "> F
    \ (P\) "> F \ (Q\) "> F \ ((P\ vee Q)\ imp (P\ cuña Q)\) "> T

    3

    Hacer una tabla de verdad para la declaración\(\neg P \wedge (Q \imp P)\text{.}\) ¿De qué se puede concluir\(P\) y\(Q\) si sabe que la afirmación es cierta?

    Solución
    \(P\) \(Q\) \(\neg P \wedge (Q \imp P)\)
    \ (P\) "> T \ (Q\) "> T \ (\ neg P\ cuña (Q\ imp P)\) "> F
    \ (P\) "> T \ (Q\) "> F \ (\ neg P\ cuña (Q\ imp P)\) "> F
    \ (P\) "> F \ (Q\) "> T \ (\ neg P\ cuña (Q\ imp P)\) "> F
    \ (P\) "> F \ (Q\) "> F \ (\ neg P\ cuña (Q\ imp P)\) "> T

    Si la afirmación es verdadera, entonces ambos\(P\) and \(Q\) are false.

    4

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

    Pista

    Al igual que arriba, solo ahora necesitarás 8 filas en lugar de solo 4.

    5

    Determine si las siguientes dos declaraciones son lógicamente equivalentes:\(\neg(P \imp Q)\) y\(P \wedge \neg Q\text{.}\) Explique cómo sabe que está en lo correcto.

    Solución

    Haz una tabla de verdad para cada uno y compara. Las declaraciones son lógicamente equivalentes.

    6

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

    7

    Simplifica las siguientes declaraciones (para que la negación solo aparezca justo antes de las variables).

    1. \(\neg(P \imp \neg Q)\text{.}\)
    2. \((\neg P \vee \neg Q) \imp \neg (\neg Q \wedge R)\text{.}\)
    3. \(\neg((P \imp \neg Q) \vee \neg (R \wedge \neg R))\text{.}\)
    4. Es falso que si Sam no es un hombre entonces Chris es una mujer, y que Chris no es una mujer.
    Contestar
    1. \(P \wedge Q\text{.}\)
    2. \((\neg P \vee \neg R) \imp (Q \vee \neg R)\) or, replacing the implication with a disjunction first: \((P \wedge Q) \vee (Q \vee \neg R)\text{.}\)
    3. \((P \wedge Q) \wedge (R \wedge \neg R)\text{.}\) This is necessarily false, so it is also equivalent to \(P \wedge \neg P\text{.}\)
    4. O Sam es una mujer y Chris es un hombre, o Chris es una mujer.

    8

    Utilice las leyes de De Morgan, y cualquier otro hecho de equivalencia lógica que conozca para simplificar las siguientes afirmaciones. Muestra todos tus pasos. Tus declaraciones finales deben tener negaciones sólo aparecen directamente al lado de las variables de oración o predicados (\(P\text{,}\)\(Q\text{,}\)\(E(x)\text{,}\)etc.), y ninguna doble negación. Sería una buena idea usar solo conjunciones, disyunciones y negaciones.

    1. \(\neg((\neg P \wedge Q) \vee \neg(R \vee \neg S))\text{.}\)
    2. \(\neg((\neg P \imp \neg Q) \wedge (\neg Q \imp R))\)(cuidado con las implicaciones).

    9

    Tommy Flanagan te estaba contando lo que comió ayer por la tarde. Te dice: “Yo comí palomitas de maíz o pasas. Además, si tenía sándwiches de pepino, entonces me tomaba refresco. Pero no bebí refresco ni té”. Por supuesto sabes que Tommy es el peor mentiroso del mundo, y todo lo que dice es falso. ¿Qué comió Tommy?

    Justifica tu respuesta escribiendo todas las declaraciones de Tommy usando variables de oración (\(P, Q, R, S, T\)), tomando sus negaciones y usándolas para deducir lo que Tommy realmente comió.

    10

    Determinar si es válida la siguiente regla de deducción:

    \(P \vee Q\)
    \(\neg P\)
    \(\therefore\) \(Q\)
    Solución

    La regla de deducción es válida. Para ver esto, haz una tabla de verdad que contenga\(P \vee Q\) and \(\neg P\) (and \(P\) and \(Q\) of course). Look at the truth value of \(Q\) in each of the rows that have \(P \vee Q\) and \(\neg P\) true.

    11

    Determinar si la siguiente es una regla de deducción válida:

    \(P \imp (Q \vee R)\)
    \(\neg(P \imp Q)\)
    \(\therefore\) \(R\)

    12

    Determinar si la siguiente es una regla de deducción válida:

    \((P \wedge Q) \imp R\)
    \(\neg P \vee \neg Q\)
    \(\therefore\) \(\neg R\)

    13

    ¿Pueden encadenar implicaciones juntas? Es decir, si\(P \imp Q\) y\(Q \imp R\text{,}\) hace eso significa el ¿\(P \imp R\text{?}\)Puedes encadenar más implicaciones juntas? Averiguemos:

    1. Demostrar que la siguiente es una regla de deducción válida:
      \(P \imp Q\)
      \(Q \imp R\)
      \(\therefore\) \(P \imp R\)
    2. Demostrar que la siguiente es una regla de deducción válida para cualquier\(n \ge 2\text{:}\)
      \(P_1 \imp P_2\)
      \(P_2 \imp P_3\)
      \(\vdots\)
      \(P_{n-1} \imp P_n\)
      \(\therefore\) \(P_1 \imp P_n\text{.}\)

      Te sugiero que no te tomes la molestia de escribir una tabla de verdad de\(2^n\) fila. En su lugar, se debe utilizar la parte (a) y la inducción matemática.

    14

    También podemos simplificar las declaraciones en la lógica de predicados usando nuestras reglas para pasar negaciones sobre cuantificadores, y luego aplicar equivalencia lógica proposicional a la parte proposicional “interior”. Simplifica las declaraciones a continuación (por lo que la negación aparece solo directamente al lado de los predicados).

    1. \(\neg \exists x \forall y (\neg O(x) \vee E(y))\text{.}\)
    2. \(\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z))\text{.}\)
    3. Hay un número\(n\) para el que ningún otro número es\(n\) menor o igual a\(n\text{.}\)
    4. Es falso que por cada número\(n\) hay otros dos números que\(n\) se encuentran entre ellos.
    Solución
    1. \(\forall x \exists y (O(x) \wedge \neg E(y))\text{.}\)
    2. \(\exists x \forall y (x \ge y \vee \forall z (x \ge z \wedge y \ge z))\text{.}\)
    3. Hay un número\(n\) for which every other number is strictly greater than \(n\text{.}\)
    4. Hay un número\(n\) which is not between any other two numbers.

    15

    Supongamos\(P\) y\(Q\) son (posiblemente moleculares) declaraciones proposicionales. Demostrar eso\(P\) y\(Q\) son lógicamente equivalentes si y sólo si\(P \iff Q\) es una tautología.

    Pista

    ¿Qué significan estos conceptos en términos de tablas de verdad?

    16

    Supongamos\(P_1, P_2, \ldots, P_n\) y\(Q\) son (posiblemente moleculares) declaraciones proposicionales. Supongamos además que

    \(P_1\)
    \(P_2\)
    \(\vdots\)
    \(P_n\)
    \(\therefore\) \(Q\)

    es una regla de deducción válida. Demostrar que la declaración

    \ begin {ecuación*} (P_1\ cuña P_2\ cuña\ cdots\ cuña P_n)\ imp Q\ end {ecuación*}

    es una tautología.

    3.2: Pruebas

    1

    Consideremos la afirmación “para todos los enteros\(a\) y\(b\text{,}\) si\(a + b\) es par, entonces\(a\) y\(b\) son pares”

    1. Escribir el contrapositivo de la declaración.
    2. Escribe lo contrario de la declaración.
    3. Escribir la negación de la declaración.
    4. ¿La declaración original es verdadera o falsa? Demuestra tu respuesta.
    5. ¿Es verdadero o falso el contrapositivo de la afirmación original? Demuestra tu respuesta.
    6. ¿Es cierto o falso lo contrario de la afirmación original? Demuestra tu respuesta.
    7. ¿La negación de la declaración original es verdadera o falsa? Demuestra tu respuesta.
    Solución
    1. Para todos los enteros\(a\) and \(b\text{,}\) if \(a\) or \(b\) is not even, then \(a+b\) is not even.
    2. Para todos los enteros\(a\) and \(b\text{,}\) if \(a\) and \(b\) are even, then \(a+b\) is even.
    3. Hay números\(a\) and \(b\) such that \(a+b\) is even but \(a\) and \(b\) are not both even.
    4. Falso. Por ejemplo,\(a = 3\) and \(b = 5\text{.}\) \(a+b = 8\text{,}\) but neither \(a\) nor \(b\) are even.
    5. Falso, ya que equivale a la declaración original.
    6. Cierto. Let\(a\) and \(b\) be integers. Assume both are even. Then \(a = 2k\) and \(b = 2j\) for some integers \(k\) and \(j\text{.}\) But then \(a+b = 2k + 2j = 2(k+j)\) which is even.
    7. Es cierto, ya que la afirmación es falsa.

    2

    Considera la declaración: para todos los enteros\(n\text{,}\) si\(n\) es par entonces\(8n\) es par.

    1. Demostrar la declaración. ¿Qué tipo de prueba estás usando?
    2. ¿Es cierto lo contrario? Demostrar o desacreditar.
    Solución
    1. Prueba directa.

      Prueba

      Let\(n\) be an integer. Assume \(n\) is even. Then \(n = 2k\) for some integer \(k\text{.}\) Thus \(8n = 16k = 2(8k)\text{.}\) Therefore \(8n\) is even.

    2. Lo contrario es falso. Es decir, hay un entero\(n\) such that \(8n\) is even but \(n\) is odd. For example, consider \(n = 3\text{.}\) Then \(8n = 24\) which is even but \(n = 3\) is odd.

    3

    Tu “amigo” te ha mostrado una “prueba” que escribió para demostrar que\(1 = 3\text{.}\) Aquí está la prueba:

    Prueba

    Afirmo que Por\(1 = 3\text{.}\) supuesto que podemos hacer cualquier cosa a un lado de una ecuación siempre y cuando también lo hagamos al otro lado. Así que resta 2 de ambos lados. Esto da\(-1 = 1\text{.}\) Ahora cuadrar ambos lados, para conseguir\(1 = 1\text{.}\) Y todos estamos de acuerdo en que esto es cierto.

    ¿Qué está pasando aquí? ¿Es válido el argumento de tu amigo? Es el argumento una prueba del reclamo Explicar\(1=3\text{?}\) cuidadosamente usando lo que sabemos de la lógica. Pista: ¿Qué implicación se desprende de la prueba dada?

    4

    Supongamos que tiene una colección de sellos de 5 centavos y sellos de 8 centavos. Vimos antes que es posible hacer cualquier cantidad de franqueo superior a 27 centavos utilizando combinaciones de ambos tipos de sellos. Pero, hagamos algunas otras preguntas:

    1. ¿Qué cantidades de franqueo puedes hacer si solo usas un número par de ambos tipos de sellos? Demuestra tu respuesta.
    2. Supongamos que hiciste una cantidad par de franqueo. Demuestre que utilizó un número par de al menos uno de los tipos de sellos.
    3. Supongamos que hizo exactamente 72 centavos de franqueo. Demuestre que utilizó al menos 6 de un tipo de sello.

    5

    Supongamos que le gustaría probar la siguiente implicación:

    Para todos los números\(n\text{,}\) si\(n\) es primo entonces\(n\) es solitario.

    Escriba el principio y el final del argumento si tuviera que probar la declaración,

    1. Directamente
    2. Por contrapositivo
    3. Por contradicción

    No es necesario que proporciones detalles para las pruebas (ya que no sabes lo que significa solitario). No obstante, asegúrate de proporcionar las primeras y últimas líneas de las pruebas para que podamos ver esa estructura lógica que seguirías.

    6

    Demostrar que\(\sqrt 3\) es irracional.

    Solución

    Prueba

    Supongamos\(\sqrt{3}\) were rational. Then \(\sqrt{3} = \frac{a}{b}\) for some integers \(a\) and \(b \ne 0\text{.}\) Without loss of generality, assume \(\frac{a}{b}\) is reduced. Now

    \ comenzar {ecuación*} 3 =\ frac {a^2} {b^2}\ final {ecuación*}\ comenzar {ecuación*} b^2 3 = a^2\ final {ecuación*}

    Entonces\(a^2\) is a multiple of 3. This can only happen if \(a\) is a multiple of 3, so \(a = 3k\) for some integer \(k\text{.}\) Then we have

    \ begin {ecuación*} b^2 3 = 9k^2\ end {ecuación*}\ begin {ecuación*} b^2 = 3k^2\ end {ecuación*}

    Entonces\(b^2\) is a multiple of 3, making \(b\) a multiple of 3 as well. But this contradicts our assumption that \(\frac{a}{b}\) is in lowest terms.

    Por lo tanto,\(\sqrt{3}\) is irrational.

    7

    Considera la sentencia: para todos los enteros\(a\) y\(b\text{,}\) si\(a\) es par y\(b\) es un múltiplo de 3, entonces\(ab\) es un múltiplo de 6.

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

    8

    Demostrar la sentencia: Para todos los enteros\(n\text{,}\) si\(5n\) es impar, entonces\(n\) es impar. Exponga claramente el estilo de prueba que está utilizando.

    Solución

    Demostraremos el contrapositivo: si\(n\) is even, then \(5n\) is even.

    Prueba

    Let\(n\) be an arbitrary integer, and suppose \(n\) is even. Then \(n = 2k\) for some integer \(k\text{.}\) Thus \(5n = 5\cdot 2k = 10k = 2(5k)\text{.}\) Since \(5k\) is an integer, we see that \(5n\) must be even. This completes the proof.

    9

    Demostrar la declaración: Para todos los enteros\(a\text{,}\)\(b\text{,}\) y\(c\text{,}\) si\(a^2 + b^2 = c^2\text{,}\) entonces\(a\) o\(b\) es par.

    10

    Probar:\(x=y\) si y solo si\(xy=\dfrac{(x+y)^2}{4}\text{.}\) Nota, necesitarás probar dos “direcciones” aquí: la parte “si” y la parte “solo si”.

    11

    El juego TENZI viene con 40 dados de seis caras (cada uno numerado del 1 al 6). Supongamos que tira los 40 dados.

    1. Demostrar que habrá al menos siete dados que aterricen en el mismo número.
    2. ¿Cuántos dados tendrías que tirar antes de que te garantizaran que unos cuatro de ellos coincidirían todos o todos serían diferentes? Demuestra tu respuesta.
    Solución
    1. Este es un ejemplo del principio del encasillamiento. Podemos demostrarlo por contrapositivo.

      Prueba

      Supongamos que cada número solo subió 6 veces o menos. Entonces hay como máximo seis 1's, seis 2's, y así sucesivamente. Eso es un total de 36 dados, por lo que no debes haber rodado todos los 40 dados.

    2. Podemos tener 9 dados sin que ningún juego de cuatro o cuatro cualquiera sea todo diferente: tres 1's, tres 2's, tres 3's Demostraremos que cada vez que lances 10 dados, siempre obtendrás cuatro emparejamientos o todos siendo diferentes.

      Prueba

      Supongamos que tira 10 dados, pero que NO hay cuatro rollos coincidentes. Esto significa que como mucho, hay tres de cualquier valor dado. Si solo tuviéramos tres valores diferentes, eso serían solo 9 dados, así que debe haber 4 valores diferentes, dando 4 dados que son todos diferentes.

    12

    Demostrar que\(\log(7)\) es irracional.

    Solución

    Damos una prueba por contradicción.

    Prueba

    Supongamos, contrariamente a lo estipulado que\(\log(7)\) is rational. Then \(\log(7) = \frac{a}{b}\) with \(a\) and \(b \ne 0\) integers. By properties of logarithms, this implies

    \ begin {ecuación*} 7 = 10^ {\ frac {a} {b}}\ end {ecuación*}

    Equivalentemente,

    \ begin {ecuación*} 7^b = 10^a\ end {ecuación*}

    Pero esto es imposible ya que cualquier potencia de 7 será impar mientras que cualquier potencia de 10 será par. Por lo tanto,\(\log(7)\) is irrational.

    13

    Demostrar que no hay soluciones enteras a la ecuación\(x^2 = 4y + 3\text{.}\)

    14

    Demostrar que cada número primo mayor que 3 es uno más o uno menos que un múltiplo de 6.

    Pista
    Demostrar el contrapositivo por casos.

    15

    Para cada una de las declaraciones a continuación, diga qué método de prueba debe utilizar para probarlas. Entonces diga cómo empieza la prueba y cómo termina. Puntos de bonificación por llenar en el medio.

    1. No hay números enteros\(x\) y\(y\) tal que\(x\) es un primo mayor que 5 y\(x = 6y + 3\text{.}\)
    2. Para todos los enteros\(n\text{,}\) si\(n\) es un múltiplo de 3, entonces se\(n\) puede escribir como la suma de enteros consecutivos.
    3. Para todos los enteros\(a\) y\(b\text{,}\) si\(a^2 + b^2\) es impar, entonces\(a\) o\(b\) es impar.
    Solución
    1. Prueba por contradicción. Inicio de prueba: Supongamos, en aras de la contradicción, que hay números enteros\(x\) and \(y\) such that \(x\) is a prime greater than 5 and \(x = 6y + 3\text{.}\) End of proof: … this is a contradiction, so there are no such integers.
    2. Prueba directa. Inicio de prueba: Let\(n\) be an integer. Assume \(n\) is a multiple of 3. End of proof: Therefore \(n\) can be written as the sum of consecutive integers.
    3. Prueba por contrapositivo. Inicio de prueba: Let\(a\) and \(b\) be integers. Assume that \(a\) and \(b\) are even. End of proof: Therefore \(a^2 + b^2\) is even.

    16

    Una baraja estándar de 52 cartas consta de 4 suites (corazones, diamantes, espadas y palos) cada una conteniendo 13 valores diferentes (As, 2, 3,..., 10, J, Q, K). Si robas algún número de cartas al azar, podrías tener o no un par (dos cartas con el mismo valor) o tres cartas todas del mismo palo. No obstante, si robas suficientes cartas, tendrás la garantía de tenerlas. Para cada una de las siguientes, encuentra el menor número de cartas que necesitarías sacar para estar garantizado teniendo las cartas especificadas. Demuestra tus respuestas.

    1. Tres de una especie (por ejemplo, tres 7's).
    2. Una descarga de cinco cartas (por ejemplo, cinco corazones).
    3. Tres cartas que son todas del mismo palo o todos diferentes.

    17

    Supongamos que estás en una fiesta con 19 de tus amigos más cercanos (así incluyéndote a ti, hay 20 personas ahí). Explique por qué debe haber al menos dos personas en la fiesta que sean amigas del mismo número de personas en la fiesta. Supongamos que la amistad siempre es correspondida.

    18

    Tu amigo te ha dado su lista de 115 mejores episodios de Doctor Who (en orden de grandeza). Resulta que has visto 60 de ellos. Demuestra que hay al menos dos episodios que has visto que están exactamente a cuatro episodios de diferencia.

    19

    Supongamos que tienes un\(n\times n\) tablero de ajedrez pero tu perro se ha comido una de las casillas de esquina. ¿Aún puedes cubrir las casillas restantes con dominó? Lo que tiene que ser cierto acerca de\(n\text{?}\) Dar condiciones necesarias y suficientes (es decir, decir exactamente qué valores del\(n\) trabajo y cuáles no funcionan). Demuestra tus respuestas.

    chessboard1.svg

    20

    ¿Y si a tu\(n\times n\) tablero le faltan dos esquinas opuestas? Demuestra que no importa lo que\(n\) sea, no podrás cubrir las casillas restantes con dominó.

    chessboard2.svg


    This page titled 3.E: Lógica Simbólica y Pruebas (Ejercicios) is shared under a not declared license and was authored, remixed, and/or curated by Oscar Levin.