¿Cómo puedo demostrar que $[(p \to\neg q) \wedge q] \to \neg p$ ¿es una tautología?

Question

Demostrar que $[(p \to\neg q) \wedge q] \to \neg p$ es una tautología Leyes de la lógica

Intenté demostrarlo usando la tabla de verdad pero no produjo una tautología.

Este es mi trabajo hasta ahora: $$ [(p \to \neg q) \wedge q] \to \neg p\\ [(\lnot p \vee \lnot q) \wedge q] \lnot p\\ \lnot [(\lnot p \vee \lnot q) \wedge q] \vee \lnot p\\ [\lnot (\lnot p \vee \lnot q) \vee \lnot q] \vee \lnot p\\ [(p q) \vee \lnot q ] \vee \lnot p\\ $$

¿Puede alguien ayudarme?

Answer 1

En primer lugar, pido disculpas por el formato de esto, ¡no tengo ni idea de cómo hacer una tabla! Espero que siga siendo lo suficientemente claro.

$$ \begin{array}{cccc|cc|c} p & q & ¬p & ¬q & (p\rightarrow ¬q) & (p\rightarrow¬q)∧q & (p\rightarrow¬q)∧q\rightarrow¬p\\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{array} $$

Y por eso es una tautología. Alternativamente, si esto es de un curso de lógica formal, vas a querer mostrar $\vDash ((p\rightarrow ¬q)∧q)\rightarrow ¬p)$ , lo que debería ser bastante sencillo al menos para la lógica proposicional. Sin embargo, no he hecho nada de lógica en un buen tiempo, así que no me gustaría tratar de intentar eso de la parte superior de mi cabeza. O si estás tan lejos, podrías hacer una prueba formal usando NNO para asemejarse a una prueba por contradicción y luego usar el teorema de completitud para transferirlo.

Answer 2

Espero que esto te ayude:

Si $[(p \to\neg q) \wedge q] \Rightarrow \neg p$ entonces $[(p \to\neg q) \wedge q] \to \neg p$ es un tautología .

$$ \begin{array}{c|cc} 1 & (p \to\neg q) \wedge q\\ \hline 2 & p \to\neg q &\hspace{1cm}\text{1. Simplification}\\ 3 & q &\hspace{1cm}\text{1. Simplification}\\ 4 & \neg\neg q \to\neg p &\hspace{1cm}\text{2. Contrapositive}\\ 5 & \neg \neg q &\hspace{1cm}\text{3. Double negation}\\ \hline 6 & \neg p &\hspace{1cm}\text{4. & 5. Modus Ponens}\\ \end{array} $$

Ahora vemos que $[(p \to\neg q) \wedge q] \Rightarrow \neg p $ . Por lo tanto, $[(p \to\neg q) \wedge q] \to \neg p $ es un tautología .

Answer 3

Llame a $r = [(p \to ¬q) \wedge q]$ y utilizar primero el hecho de que $[a \to b] = [\neg a \vee b]$ por cada $a$ y $b$ y luego el hecho de que $[(a \vee b) \wedge c] = [(a \wedge c) \vee (b \wedge c)]$ por cada $a$ , $b$ y $c$ .

Esto da como resultado $r = [(\neg p \vee \neg q) \wedge q] = [(\neg p \wedge q) \vee (\neg q \wedge q)] = (\neg p \wedge q)$ desde $(\neg q \wedge q) = 0$ y $[a \vee 0] = a$ por cada $a$ . Así, se pide que se demuestre que $[(\neg p \wedge q) → \neg p]$ es siempre verdadera, lo cual es efectivamente una tautología.

Answer 4

Esto es una tautología, prueba sencilla por Isomorfismo de Curry-Howard es la siguiente: $$\lambda (a,q).\ \lambda p.\ a\ p\ q$$

Una prueba más implicada por el razonamiento:

Sólo hay una posibilidad de que la fórmula sea falsa: $$[(p → ¬q) ∧ q] → ¬p$$

• necesitamos $p$ sea verdadera (por el lado derecho de la implicación),
• y $q$ ser verdad (por la conjunción).

Sin embargo, en este escenario $p \to \neg q$ es falsa, por lo que la conjunción es falsa y la fórmula completa es verdadera, por lo que es una tautología.

¡Salud!

Answer 5

Esto se hizo con Fitch. Suponga que la afirmación que quiere demostrar es falsa. Demuestre que esta suposición implica una contradicción. A partir de aquí puedes rechazar la suposición original, demostrando que el enunciado es verdadero. El enunciado es una tautología porque se puede demostrar sin ninguna premisa; es verdadero en virtud de sus conectivos funcionales verdaderos.