Mostrando una afirmación condicional es una tautología sin usar una tabla de verdad.

Question

Quería demostrar que [(pq)(qr)](pr) es una tautología sin utilizar una tabla de verdad. Hasta ahora esto es lo que tengo:

[(pq)(qr)] (pr)

\=> ¬[(¬p v q) (¬q v r)] v (¬pvr) (equivalencia lógica)

\=> [¬(¬p v q) v ¬(¬qvr)] v (¬pvr) (ley de De Morgan)

\=> [(p ¬q) v (q¬r)] v (¬pvr) (ley de De Morgan)

No logro entender qué sigue después de este paso. ¿Alguien puede ayudarme?

Answer 1

Expande la expresión $(p \wedge \neg q) \vee (q \wedge \neg r)$ distribuyendo el $\vee$ sobre el $\wedge$: \begin{align*} &(p \wedge \neg q) \vee (q \wedge \neg r) \\ &[(p \wedge \neg q) \vee q] \wedge [(p \wedge \neg q) \vee \neg r] \\ &[(p \vee q) \wedge (\neg q \vee q)] \wedge [(p \vee \neg r) \wedge (\neg q \vee \neg r)] \\ &[(p \vee q) \wedge \top] \wedge [(p \vee \neg r) \wedge (\neg q \vee \neg r)] \\ &(p \vee q) \wedge [(p \vee \neg r) \wedge (\neg q \vee \neg r)]. \end{align*} Ahora en total tenemos $\{(p \vee q) \wedge [(p \vee \neg r) \wedge (\neg q \vee \neg r)]\}\vee (\neg p \vee r)$. Si distribuimos el $\vee$ sobre el $\wedge$, obtenemos $[(p \vee q) \vee (\neg p \vee r)]\wedge\{[(p \vee \neg r) \wedge (\neg q \vee \neg r)]\vee (\neg p \vee r)\}$. Enfocándonos en la primera mitad, puedes manipular $(p \vee q) \vee (\neg p \vee r)$ para obtener $\top$ reorganizando paréntesis para obtener $(p \vee \neg p) \vee (q \vee r)$ (te dejo eso a ti).

Entonces nos queda $[(p \vee \neg r) \wedge (\neg q \vee \neg r)] \vee (\neg p \vee r)$. Nuevamente distribuyamos el $\vee$ sobre el $\wedge$: \begin{align*} &[(p \vee \neg r) \vee (\neg p \vee r)] \wedge [(\neg q \vee \neg r) \vee (\neg p \vee r)]. \end{align*} Nuevamente ambas partes de esto pueden ser manipuladas para obtener $\top$.

Answer 2

No puedo entender qué sigue después de este paso. ¿Alguien puede ayudarme?

Sí.

$$\begin{align}\vdots\quad\\\iff&~\big((p \land \lnot q) \lor (q\land\lnot r)\big) \lor (\lnot p\lor r) \\[1ex]\iff &~\big(\lnot p\lor (p\land \lnot q)\big)\lor \big(r\lor (\lnot r\land q)\big)&\quad\textsf{(Conmutación y Asociación)}\\\vdots\quad\end{align}$$

Answer 3

Puedes usar la Doble Distribución para obtener $$[(p \lor q)\land(q \lor \lnot q)\land(\lnot q \lor \lnot r)\land(p \lor \lnot r)]\lor (\lnot p \lor r)$$ $q \lor \lnot q$ es una tautología, por lo que esto se convierte en $$[(p \lor q)\land(\lnot q \lor \lnot r)\land(p \lor \lnot r)]\lor (\lnot p \lor r)$$ lo cual, por distribución, es $$[(p \lor q)\land[\lnot r\land(p \lor \lnot q)]]\lor (\lnot p \lor r)$$ La asociación nos da $$[\lnot r \land [(p \lor q)\land(p \lor \lnot q)]]\lor (\lnot p \lor r)$$ Distribuyendo nuevamente obtenemos $$[\lnot r \land [p \lor(q \land \lnot q)]]\lor (\lnot p \lor r)$$ $q \land \lnot q$ es una contradicción, por lo que esto se convierte en $$(\lnot r \land p)\lor (\lnot p \lor r)$$ Lo cual, por la Ley de De Morgan, es $$(\lnot r \land p)\lor \lnot(\lnot r \land p)$$ Lo cual es una tautología.

Answer 4

Nota que

$ [(p \land \neg q) \lor (q\land \neg r)] \lor (\neg p\lor r)$

es una gran disyunción, por lo que puedes eliminar paréntesis:

$ (p \land \neg q) \lor (q\land \neg r) \lor \neg p\lor r$

Ahora, si tienes:

Reducción

$p \lor (\neg p \land q) \equiv p \lor q$

entonces puedes aplicar eso:

$ (p \land \neg q) \lor (q\land \neg r) \lor \neg p\lor r \equiv$

$\neg q \lor q \lor \neg p \lor r \equiv$

$\top \lor \neg p \lor r \equiv$

$\top$

Pero si no tienes Reducción:

$ (p \land \neg q) \lor (q\land \neg r) \lor \neg p \lor r \equiv$

$((p \lor \neg p) \land (\neg q \lor \neg p)) \lor ((q \lor r) \land (\neg r \lor r)) \equiv$

$(\top \land (\neg q \lor \neg p)) \lor ((q \lor r) \land \top) \equiv$

$\neg q \lor \neg p \lor q \lor r$

$\top \lor \neg p \lor r \equiv$

$\top$