Could provide some further detail about this step in a proof

Question

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

For the equivalence above, I am not sure how we get from the left-hand side to the right-hand side. Could anyone provide some working (preferably including logic laws used)? Would be much appreciated!

Answer 1

Your step implicitly uses two logic laws:

1. commutativity of $\lor$ (i.e. $A \lor B \equiv B \lor A$), and
2. associativity of $\lor$ (i.e. $A \lor (B \lor C) \equiv (A \lor B) \lor C$).

More precisely:

\begin{align} & \quad \ ((P \land \lnot Q) \lor (Q \land \lnot R)) \lor (\lnot P \lor R) \\ &\equiv \big(((P \land \lnot Q) \lor (Q \land \lnot R)) \lor \lnot P \big) \lor R & &\text{associativity} \\ &\equiv \big(\lnot P \lor ((P \land \lnot Q) \lor (Q \land \lnot R)) \big) \lor R &&\text{commutativity} \\ &\equiv \big((\lnot P \lor (P \land \lnot Q)) \lor (Q \land \lnot R) \big) \lor R & &\text{associativity} \\ &\equiv (\lnot P \lor (P \land \lnot Q)) \lor ((Q \land \lnot R) \lor R) & &\text{associativity} \\ &\equiv (\lnot P \lor (P \land \lnot Q)) \lor (R \lor (Q \land \lnot R)) & &\text{commutativity} \end{align}

Answer 2

$\begin{align*} & \quad ((P \land \lnot Q) \lor (Q \land \lnot R)) \lor (\lnot P \lor R) \\ &\equiv (P \land \lnot Q) \lor (Q \land \lnot R)\lor (\lnot P \lor R) \text{ (removing parentheses by associativity of $\lor$)} \\ &\equiv (P \land \lnot Q) \lor (Q \land \lnot R)\lor \lnot P \lor R \text{ (removing parentheses by associativity of $\lor$)}\\ &\equiv \lnot P \lor (P \land \lnot Q) \lor R \lor (Q \land \lnot R) \text{ (commutativity of $\lor$)} \\ &\equiv (\lnot P \lor (P \land \lnot Q)) \lor (R \lor (Q \land \lnot R)) \text{ (associativity of $\lor$)} \end{align*}$