Logical Equivalence for $p \lor q$

Question

I have to prove that

$$p \vee q \equiv (p\wedge q) \vee (\neg p\wedge q) \vee (p\wedge \neg q)$$

Based on the truth table, they are equivalent, but I couldn't figure out how to use logic statements to prove they are equivalent. I have tried many ways but they all go weird.

$(p\wedge q) \vee (\neg p\wedge q) \vee (p\wedge \neg q)$

$\equiv (p\wedge q) \vee ((\neg p\wedge q)\vee p) \wedge ((\neg p\wedge q)\vee \neg q)$

$\equiv (p\wedge q) \vee ((T \wedge (q\vee p)) \wedge (T\wedge \neg(p \wedge q))$

$\equiv (p\wedge q) \vee (q\vee p) \wedge \neg(p \wedge q)$

I couldn't figure out what I'm supposed to from this point. Did I do anything wrong? Thanks

Answer 1

Using the basic logical equivalences listed here, you can easily prove that $p \lor q$ is equivalent to $(p∧q)∨(¬p∧q)∨(p∧¬q)$.

\begin{align} & \quad \ (p∧q)∨(¬p∧q)∨(p∧¬q) \\ \text{(commutativity)}\quad &\equiv (p \land q) \lor (p \land\lnot q) \lor (\lnot p \land q) \\ \text{(distributivity of $\land$ over $\lor$)} \quad & \equiv (p \land (q \lor \lnot q)) \lor (\lnot p \land q) \\ \text{(negation law)} \quad &\equiv (p \land \top) \lor (\lnot p \land q) \\ \text{(identity law)} \quad &\equiv p \lor (\lnot p \land q) \\ \text{(distributivity of $\lor$ over $\land$)}\quad &\equiv (p \lor \lnot p) \land (p \lor q) \\ \text{(negation law)}\quad &\equiv \top \land (p \lor q) \\ \text{(identity law)}\quad &\equiv p \lor q \end{align} where $\top$ stands for a tautology, i.e. a formula that is always true. In the first two lines, the use of the associativity law is left implicit.

Answer 2

To prove $p \vee q \equiv (p\wedge q) \vee (\neg p\wedge q) \vee (p\wedge \neg q)$, let's start from RHS as follows.

$(p\wedge q) \vee (\neg p\wedge q) \vee (p\wedge \neg q)$

$\equiv q \wedge (p\vee \neg p) \vee (p\wedge \neg q)$

$\equiv (q \wedge \text{T}) \vee (p\wedge \neg q)$

$\equiv q \vee (p\wedge \neg q)$

$\equiv (q \vee p)\wedge(q\vee \neg q)$

$\equiv (q \vee p)\wedge \text{T}$

$\equiv (q \vee p)$

Q.E.D.

Answer 3

For better readability I use $+$ for "or", $\cdot$ for "and" and $()'$ for negation.

So, you have \begin{eqnarray*} pq + p'q+pq' & = & (p+p')q+pq' \\ & = & q + pq' \\ & \stackrel{DeMorgan}{=} & (q'(p'+q))' \\ & \stackrel{qq' = F}{=} & (q'p')' \\ & = & p+q \end{eqnarray*}