Show that the boolean formulas $[(p ∧ ¬q) ∨ q] ∧ [(¬q ∧ p) ∨ r] and (p ∧ ¬q) ∨ (r ∧ q)$ are equivalent.

Question

So far I got this:

$[(p ∧ ¬q) ∨ q] ∧ [(¬q ∧ p) ∨ r]$:

• $p∧ T ∧ [(¬q∧p) ∨ r]$
• $p∧ [(p∧¬q) ∨ r]$
• $p \lor r$

$(p ∧ ¬q) ∨ (r ∧ q):$

• $(p ∧ ¬q) ∨ (q ∧ r)$

• $(p ∧( ¬q ∨ q)∧ r$

• $p ∧ T ∧ r$

• $p ∧ r$

Answer 1

You're not doing this right. You can't just move parentheses around like you do.

For example, for the first one, you go from $(p \land \neg q) \lor q$ to $p \land \top$, but that must mean you went from $(p \land \neg q) \lor q$ to $p \land (\neg q \lor q)$ .... which is not right:

In general, $(p \land q) \lor r$ is not equivalent to $p \land (q \lor r)$

You are similarly moving parentheses for the second expression in a way that is not allowed. Think about it: what if this was an algebraic expression using numbers? It would be like going from $(3 + 4) \cdot (5+6)$ to $3 + 4 \cdot 5 + 6$ ... that's clearly not something you can do!