# Logical Equivalence for $p \lor q$

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

• @AdityaDwivedi - In fact, the last two brackets don't evaluate to a tautology. Sep 25, 2020 at 4:52

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.

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.

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*}$$

• Appreciate the help. It's different from what I learned but it seems easier to read. Maybe it would be faster if q+pq' = (q+p)(q+q') = p+q. Sep 25, 2020 at 6:40
• @user665125 You are welcome. And yes, the way without DeMorgan you suggest in your comment is also quite quick and elegant. :-) Sep 25, 2020 at 7:01