¿Cómo debo proceder en probar esta tautología?

Question

Sé que la siguiente es una tautología porque lo he comprobado en su tabla de verdad. Ahora estoy tratando de demostrar que es una tautología por el uso de las reglas de la lógica, que es más difícil. ¿Cómo debo proceder?

$(p\land(p\implies q))\implies q$

$(p\land(\lnot p \lor q))\implies q$

$(p\land \lnot p) \lor (p\land q) \implies q$ Este paso es donde estoy pegado en. Sé que $(p\land \lnot p)$ es falso. Así que me parece que el valor de verdad de todo a la izquierda de la $\implies$ operador depende del valor de verdad de $(p\land q)$ Así que lo que quiero hacer es esto:

FALSOS $\lor (p\land q) \implies q$ que se reduce a

$(p\land q) \implies q$

Es mi pensamiento correcto? Si es así, entonces quiero reescribir $(p\land q) \implies q$

$\lnot(p \land q) \lor (p \land q)$ mediante el uso de la identidad de $p\implies q \equiv \lnot p \lor q$ Estoy en el camino correcto?

Answer 1

Utilice la ley de Morgan en $\neg(p\land q)$ cerca del final. Esto debería darte una disyunción que fácilmente puede considerarse como tautológica de la ley del medio excluido. Además, recuerde que $(p\land q)\implies q\equiv \neg(p\land q)\lor q$, no $\neg(p\land q)\lor(p\land q)$de % de % como escribió.

Answer 2

$$\begin{align} (p\land(p\rightarrow q))\rightarrow q &\Longleftrightarrow (p\land(\neg p\lor q))\rightarrow q\ &\Longleftrightarrow ((p\land \neg p)\lor (p\land q))\rightarrow q\ &\Longleftrightarrow (F\lor (p\land q))\rightarrow q & \text{Negation law}\ &\Longleftrightarrow \neg(F\lor (p\land q))\lor q\ &\Longleftrightarrow (T\land \neg(p\land q))\lor q \ &\Longleftrightarrow (T\land(\neg p\lor \neg q))\lor q &\text{DeMorgan's law}\ &\Longleftrightarrow (\neg p\lor \neg q)\lor q &\text{Domination law}\ &\Longleftrightarrow \neg p\lor (\neg q\lor q) \ &\Longleftrightarrow \neg p\lor T\ &\Longleftrightarrow T\ \end {Alinee el} $$

Answer 3

Su razonamiento es correcto hasta ahora. Me parece ya equivale a $a\to b$ $\lnot a\lor b$, $(p\land q)\to q$ es equivalente a $\lnot(p\land q)\lor q$, que es diferente de lo que usted escribió en la última línea. Para continuar, creo que va a utilizar que $\lnot(p\land q)$ es equivalente a $\lnot p\lor \lnot q$.

Answer 4

Utilizando la notación de deducción natural

Modus ponens: $$\backslash!!!!!{A}$$ $$\overline{B}$$ $% $ $\overline{A\to B}$de la asunción $A$ puede deducir $B$ y $A\to B$ es deducible.

Ley de la conjunción: $$A\wedge B$$ $$\overline{\qquad A \qquad}$ $ y $$A\wedge B$$ $% $ $\overline{\qquad B \qquad}$y $A\wedge B$, entonces ambos $A$ y $B$ también.

Para probar la declaración usando ND, empezar por romper la primera implicación - y usted pronto averiguar qué hacer. (Si hay alguna duda solo pregunte).