Mostrar mediante el uso de leyes de conectividad lógica que $(P \to Q) \land (Q \to R) $ es equivalente a $(P \to R) \land [(P \iff Q) \lor (R \iff Q)]$

Question

Tengo problemas con un problema en el libro del que me estoy estudiando. Dice lo siguiente:

Muestra que $(P \to Q) \land (Q \to R) $ es equivalente a $(P \to R)$ $ \land [(P \iff Q) \lor (R \iff Q)]$ mediante el uso de conexiones lógicas

Hasta ahora he dedicado mucho tiempo a este problema, y ahora les pido un consejo o una solución para resolverlo. Este es uno de los métodos que he utilizado. Señala cualquier defecto que haya hecho.

$(P \to Q) \land (Q \to R) $

(Ley condicional)

$( \neg P \lor Q) \land ( \neg Q \lor R) \Rightarrow $

(Derecho distributivo)

$[( \neg P \land \neg Q)] \lor [Q \land ( \neg Q \lor R)] \Rightarrow $

(Derecho distributivo)

$[( \neg P \land \neg Q) \lor (R \land \neg P)] \lor [(Q \land \neg Q) \lor (R \land Q)] \Rightarrow $

Contradicción

$[( \neg P \land \neg Q) \lor (R \land \neg P)] \lor [(Contradiction) \lor (R \land Q)] \Rightarrow $

(Ley de Contradicción)

$[( \neg P \land \neg Q) \lor (R \land \neg P)] \lor [ (R \land Q)] \Rightarrow $

Típicamente alrededor del paso cinco me quedo atascado o me confundo porque el problema se complica. Sé que podrías demostrarlo usando las tablas de verdad. Sin embargo, el problema dice que hay que usar las conexiones lógicas. Mis preguntas son: ¿Estoy en el camino correcto para resolver este problema? ¿Cometí algún error? ¿Qué consejos/pistas me darías en mi camino para resolver este problema?

Edita Algunos de ustedes quieren que haga una lista de las leyes. Aquí están:

Las leyes de DeMorgan

$ \neg (P \land Q) \equiv \neg P \lor \neg Q$

$ \neg (P \lor Q) \equiv \neg P \land \neg Q$

Leyes conmutativas

$P \lor Q \equiv Q \lor P$

$Q \lor P \equiv P \lor Q$

Leyes asociativas

$P \land (Q \land R) \equiv (P \land Q) \land R $

$(P \land Q) \land R \equiv P \land (Q \land R) $

Leyes idemotécnicas

$P \land P \equiv P$

$P \lor P \equiv P$

Leyes de distribución

$P \land (Q \lor R) \equiv (P \land Q ) \lor (P \land R)$

$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$

Leyes de absorción

$P \lor (P \land Q) \equiv P$

$P \land (P \lor Q) \equiv P$

Leyes de tautología

$P \land (tautology) \equiv P$

$P \lor (tautology) \equiv (tautology)$

Leyes de Contradicción

$P \land (contradiction) \equiv (contradiction)$

$P \lor (contradiction) \equiv P$

Leyes condicionales

$P \to Q \equiv \neg P \lor Q$

$P \to Q \equiv \neg (P \land \neg Q)$

Answer 1

Lo que queremos probar es una conjunción, así que basta con probar cada conjunción por separado y luego pegarlas al final. Este problema probablemente sería más fácil y más intuitivo usando prueba por contradicción, pero después de hablar con el preguntador, proporcionaré una prueba directa.

$$ \begin {array}{lr} 1. & (P \rightarrow Q) \wedge (Q \rightarrow R) & \text {Premise} \\ 2. & P \rightarrow Q & \text {Simplification, 1} \\ 3. & Q \rightarrow R & \text {Simplification, 1} \\ 4. & \neg {P} \vee Q & \text {Conditional Law, 2} \\ 5. & \neg {Q} \vee R & \text {Conditional Law, 3} \\ 6. & Q \vee \neg {Q} & \text {Tautology} \\ 7. & \neg {P} \vee R & \text {Constructive Dilemma, 4,5,6} \\ 8. & P \rightarrow R & \text {Conditional Law, 7} \\ 9. & (P \rightarrow Q) \vee (Q \rightarrow R) & \text {Addition, 2} \\ 10. & (Q \rightarrow P) \vee (Q \rightarrow R) & \text {Addition, 3} \\ 11. & (P \rightarrow Q) \vee (R \rightarrow Q) & \text {Addition, 2} \\ 12. & Q \vee \neg {Q} & \text {Tautology} \\ 13. & (Q \vee \neg {Q}) \vee (P \vee \neg {R}) & \text {Addidition, 12} \\ 14. & ( \neg {Q} \vee P) \vee ( \neg {R} \vee Q) & \text {Associative Law, 13} \\ 15. & (Q \rightarrow P) \vee (R \rightarrow Q) & \text {Conditional Law, 14} \\ 16. & \big ((P \rightarrow Q) \vee (Q \rightarrow R) \big ) \wedge \big ((Q \rightarrow P) \vee (Q \rightarrow R) \big ) & \text {Conjunction, 9,10} \\ 17. & \big ((P \rightarrow Q) \vee (R \rightarrow Q) \big ) \wedge \big ((Q \rightarrow P) \vee (R \rightarrow Q) \big ) & \text {Conjunction, 11,15} \\ 18. & \big ((P \rightarrow Q) \wedge (Q \rightarrow P) \big ) \vee (Q \rightarrow R) & \text {Distributive Law, 16} \\ 19. & \big ((P \rightarrow Q) \wedge (Q \rightarrow P) \big ) \vee (R \rightarrow Q) & \text {Distributive Law, 17} \\ 20. & \Big ( \big ((P \rightarrow Q) \wedge (Q \rightarrow P) \big ) \vee (Q \rightarrow R) \Big ) \wedge & \\ & \Big ( \big ((P \rightarrow Q) \wedge (Q \rightarrow P) \big ) \vee (R \rightarrow Q) \Big ) & \text {Conjunction, 18,19} \\ 21. & \big ((P \rightarrow Q) \wedge (Q \rightarrow P) \big ) \vee \big ((Q \rightarrow R) \wedge (R \rightarrow Q) \big ) & \text {Distributive Law, 20} \\ 22. & (P \equiv Q) \vee (Q \equiv R) & \text {Definition of Biconditional, 21} \\ \therefore & (P \rightarrow R) \wedge \big ((P \equiv Q) \vee (Q \equiv R) \big ) & \text {Conjunction, 8,22} \end {array}$$

Como desee.

Answer 2

Yo uso Notación polaca .

Por distribución tenemos 1.

1. KCprAEpqErq = AKCprEpqKCprErq.

Supongamos que KCprEpq. Entonces, por dos eliminaciones de conjunción tenemos Cpr y Epq. Supongamos que p. Entonces, por desprendimiento, tenemos r. También, por desprendimiento tenemos q (si tenemos "p" y "Epq", entonces "q" también). Por introducción condicional, tenemos Cpq. A continuación supongamos q. Como también tenemos Epq, podemos entonces "invertir el desprendimiento" p. Como tenemos tanto p como Cpr, podemos entonces desprender r. Por introducción condicional, tenemos Cqr. Así, por introducción de conjunción tenemos KCpqCqr. Así, KCprEpq produce KCpqCqr.

Ahora supongamos que KCprErq. Entonces, por dos eliminaciones de conjunción tenemos Cpr y Erq. Supongamos que p. Entonces como tenemos Cpr también, podemos separar r. Como tenemos Erq también, podemos separar q. Por lo tanto, Cpq. Luego supongamos q. Entonces como tenemos Erq, podemos separar r. Así, por introducción condicional tenemos Cqr. Así, por introducción de conjunción obtenemos KCpqCqr.

Dado que ambos casos conducen a KCpqCqr, AKCprEpqKCprErq implica KCpqCqr.

Supongamos que KCpqCqr. Entonces por dos eliminaciones de conjunción tenemos Cpq y Cqr. Suponga p. Suponga p otra vez. Entonces como también tenemos Cpq, obtenemos q. Como tenemos q y Cqr, obtenemos r. Descargando la primera p obtenemos Cpr. Ahora todavía tenemos Cpq en juego. Así que, por el desprendimiento y la primera p supuesta, obtenemos q. Existe una ley que dice $ \vdash $ CpCqEpq. Así que, así por dos destacamentos obtenemos Epq. Por la introducción de la disyunción obtenemos la AEpqErq. Por introducción de conjunción tenemos entonces KCprAEpqErq. Ahora descargando la primera p tenemos CpKCprAEpqErq.

Supongamos que Np. Todavía tenemos Cpq y Cqr. Como existe una ley que dice CNpCpr, y tenemos Np, obtenemos Cpr por separación. Supongamos que Nq. Existe una ley que dice $ \vdash $ CNpCNqEpq. Así que, de esa ley, Np, y Nq obtenemos Epq. Por la introducción de la disyunción tenemos entonces AEpqErq. Así, por introducción de conjunción tenemos KCprAEpqErq. Descargando Nq, tenemos CNqKCprAEpqErq. Supongamos que q. Como tenemos Cqr, por desprendimiento tenemos r. Como tenemos una ley que dice $ \vdash $ CrCqErq, por dos destacamentos pasamos a Erq. Por introducción de la disyunción tenemos AEpqErq. Por introducción de conjunción obtenemos KCprAEpqErq. Descargando q tenemos CqKCprAEpqErq. Ahora, tenemos AqNq. En consecuencia, mediante AqNq, CqKCprAEpqErq y CNqKCprAEpqErq obtenemos KCprAEpqErq por eliminación de la disyunción en el ámbito de la hipótesis Np. Así, descargando Np obtenemos CNpKCprAEpqErq.

Ahora, tenemos ApNp, CpKCprAEpqErq, y CNpKCprAEpqErq. Así, por eliminación de la disyunción obtenemos KCprAEpqErq. Todavía tenemos KCpqCqr en su lugar, y así por introducción condicional obtenemos CKCpqCqrKCprAEpqEqr.

Ya que teníamos CKCprAEpqEqrKCpqCqr arriba, ahora inferimos EKCpqCqrKCprAEpqEqr.

Answer 3

Aquí hay una respuesta más completa usando sólo equivalencias:

Reduzco cada una de las dos expresiones tanto como sea posible.

(Todas estas son equivalencias. Usaré libremente las leyes conmutativas/asociativas en lo que sigue para no tener en cuenta el orden y dejar caer el exceso de paréntesis).

1. $(P \rightarrow Q) \land (Q \rightarrow R)$

2. $( \lnot P \lor Q) \land ( \lnot Q \lor R)$ (def. de $ \rightarrow $ )

3. $[ \lnot P \land ( \lnot Q \lor R)] \lor [Q \land ( \lnot Q \lor R)]$ (distribuir)

4. $( \lnot P \land \lnot Q) \lor ( \lnot P \land R) \lor (Q \land R)$ (distribuya y tautología [se salteó algunos intermediarios])

Ahora para el otro lado:

1. $(P \rightarrow R) \land [(P \leftrightarrow Q) \lor (Q \leftrightarrow R)]$

2. $( \lnot P \lor R) \land [(P \land Q) \lor ( \lnot P \land \lnot Q) \lor (R \land Q) \lor ( \lnot R \land \lnot Q)]$ (ver el lema abajo)

3. $( \lnot P \land P \land Q) \lor ( \lnot P \land \lnot P \land Q) \lor ( \lnot P \land R \land Q) \lor ( \lnot P \land \lnot R \land \lnot Q) \lor (R \land P \land Q) \lor (R \land \lnot P \land \lnot Q) \lor (R \land R \land Q) \lor (R \land \lnot R \land \lnot Q)$ (distribuir)

4. $( \lnot P \land Q) \lor ( \lnot P \land R \land Q) \lor ( \lnot P \land \lnot R \land \lnot Q) \lor (R \land P \land Q) \lor (R \land \lnot P \land \lnot Q) \lor (R \land Q)$ (tautología e identencia)

5. $(R \land Q) \lor [( \lnot P \land R \land Q) \lor ( \lnot P \land R \land \lnot Q)] \lor [( \lnot P \land \lnot Q \land R) \lor ( \lnot P \land \lnot Q \land \lnot R)]$ (comm/assoc para reacomodar, idempotente para duplicar $( \lnot P \land R \land \lnot Q)$ y la absorción para deshacerse de $(R \land P \land Q)$ )

6. $(R \land Q) \lor ( \lnot P \land R) \lor ( \lnot P \land \lnot Q)$ (distribución y tautología)

Ahora la nota 4 de arriba es la misma que la 6 de abajo, según las leyes de la comunicación.

El Lemma mencionado anteriormente: $A \leftrightarrow B$ es equivalente a $(A \land B) \lor ( \lnot A \land \lnot B)$ . Mostrando esto: Es $(A \rightarrow B) \land (B \rightarrow A)$ que es equivalente a $( \lnot A \lor B) \land (A \lor \lnot B)$ que, distribuyéndose dos veces, equivale a $( \lnot A \land A) \lor ( \lnot A \land \lnot B) \lor (B \land A) \lor (B \land \lnot B)$ que es $( \lnot A \land \lnot B) \lor (B \land A)$ por las leyes de la tautología.