¿Cómo pruebo que esta declaración es tautológica sin usar tablas de verdad?

Question

¿Cómo pruebo que la siguiente declaración es una tautología, sin usar las tablas de la verdad? $$[¬P ∧ (P ∨ Q)] → Q$$

Sé que si asumimos $Q ≡ T$ entonces no importa cuál sea el valor de verdad de lo que está a la izquierda del operador de la implicación, la declaración será una tautología. Pero si asumimos que $Q ≡ F$ entonces podría haber dos posibilidades del resultado de la declaración: Si $\;[¬P ∧ (P ∨ Q)] ≡ T,\;$ entonces la declaración es falsa, y si $\;[¬P ∧ (P ∨ Q)] ≡ F,\;$ entonces la declaración es verdadera (según la tabla de verdad de las declaraciones de implicación: $\;T → F = F\; \text { and }\;F → F = T.)$

¿Hay alguna forma de probar $\;[¬P ∧ (P ∨ Q)] \rightarrow Q\;$ es siempre cierto sin usar tablas de verdad, en cambio, ¿puede ser probado únicamente con palabras/lógica? ¿O sólo estoy siendo tonto?

Answer 1

Como usted señala, si $Q$ es verdadera, entonces la implicación es verdadera.

Y si $Q$ es falso, tenemos que $\lnot P \land (P \lor Q) \equiv \underbrace{\underbrace{(\lnot P \land P)}_{F} \lor \underbrace{(\lnot P \land \underbrace{Q}_{F})}_{F}}_{F}$ y cualquier implicación con una premisa falsa es verdadera.

Por lo tanto, la implicación es una tautología.

Answer 2

Así que, probablemente sea una aproximación tonta a este tipo de cosas, pero odio las tablas de verdad y tomo una ruta un poco más tortuosa a través de lo que Quine llamaba "forma normal alterna". @amWhy puso el antecedente del condicional en forma normal alternante, pero poner toda la frase en esa forma da una prueba bastante clara de tautología. El inconveniente es que la forma alternante puede ser muy larga.

Así que la fórmula original es $(\neg P\wedge(P\vee Q))\to Q$ . Lo primero es eliminar los condicionales escribiendo esto como $(P\vee(\neg P\wedge\neg Q))\vee Q$ .

En una frase más complicada haríamos uso de las propiedades distributivas de la alternancia y la conjunción para asegurarnos de que tenemos una cadena de alternancias de conjunciones . En este caso, lo tenemos en un solo paso por encima: $P\vee(\neg P\wedge\neg Q)\vee Q$ . Cambiando el orden de nuestros elementos alternados y añadiendo de nuevo en paréntesis, vemos que tenemos $(P\vee Q)\vee(\neg P\wedge\neg Q)$ o $(P\vee Q)\vee\neg(P\vee Q)$ , una tautología obvia.

Lo que me gusta de la forma normal alternante es que A) la frase resultante es clara, aunque engorrosa y B) puede mostrar una tautología o inconsistencia mediante un método de evaluación extremadamente centrado en la sintaxis.

Answer 3

Para demostrar la implicación $\neg P \wedge (P \vee Q) \to Q$ asumimos que $\neg P \wedge (P \vee Q)$ y luego probar $Q$ de esta suposición.

De la conjunción $\neg P \wedge (P \vee Q)$ podemos deducir $\neg P$ y también podemos deducir $P \vee Q$ . Consideremos dos casos según los dos disyuntos de $P \vee Q$ .

1. $P$ retenciones. Entonces, a partir de $\neg P$ obtenemos una contradicción, y de una contradicción podemos inferir $Q$ .

2. $Q$ se mantiene.

En cualquier caso, hemos demostrado que $Q$ se mantiene.

Answer 4

* Uso de la prueba de tautología del algoritmo *

[P'∧(P∨Q)]→Q

Supongamos: [P'∧(P∨Q)] es verdadero y Q es falso

Supongamos que [P'∧(P∨Q)] es verdadera y Q es falso. -Si [P'∧(P∨Q)] es verdadero, entonces P' es verdadero y (P∨Q) es verdadero. -Si P' es verdadera, entonces P es falsa. -Si P es falso en (P∨Q), entonces Q es verdadera para que (P∨Q) sea verdadera.

Así que Q se contradice, dice que es falso y al mismo tiempo dice que es cierto . ¡Por ello, sabemos que esta WFF(fórmula bien formada) es una tautología!

Answer 5

Utilizando una prueba del estilo de Fitch, esta tautología se puede demostrar por contradicción. Suponga que el enunciado es falso, demuestre que esta suposición implica una contradicción y luego niegue la suposición.