2
$\begingroup$

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

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

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – user665125
    Sep 25, 2020 at 6:40
  • $\begingroup$ @user665125 You are welcome. And yes, the way without DeMorgan you suggest in your comment is also quite quick and elegant. :-) $\endgroup$ Sep 25, 2020 at 7:01

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .