0
$\begingroup$

I'm stuck while trying to show that $(p \land q) \to (p \lor q)$ is logically equivalent to $(p \lor ¬p) \land (q \lor \neg q)$. I know they're equivalent (they're tautologies) because they both have the same truth table but I'm not sure how to start from $(p \land q) \to (p \lor q)$ and finally get $(p \lor ¬p) \land (q \lor \neg q)$.

What I have done so far is this:

\begin{align*} (p \land q) \to (p \lor q)&\equiv\neg(p \land q) \lor (p \lor q)&\text{(Definition of $\to$)}\\ &\equiv(\neg p\lor\neg q)\lor (p \lor q)&\text{(De Morgan's Law)}\\ &\equiv(\neg p\lor\neg p)\lor (q \lor q)&\text{(Associativity and commutativity of $\lor$)}\\ \end{align*}

I don't see how to get a conjunction from there. I know I could say both disjunctions on my last step are $\mathrm{TRUE} \lor \mathrm{TRUE} \equiv \mathrm{TRUE}$ but I don't think it will leave me to get the conjunction I'm looking for, right?

I appreacite your help.

$\endgroup$
2
  • $\begingroup$ What rules of inference/replacement are you allowed to use in your proof? $\endgroup$ – Alann Rosas Apr 15 at 2:25
  • $\begingroup$ @AlannRosas Only basic equivalences. Here you can check them: postimg.cc/Z9n9565t. $\endgroup$ – Augus Apr 15 at 2:29
0
$\begingroup$

Welcome to math.SE!!

Since $p\lor\neg p\equiv\mathrm{T}$ and $q\lor\neg q\equiv\mathrm{T}$, you have \begin{align*} \mathrm{T}\lor\mathrm{T}&\equiv\mathrm{T}\\ &\equiv\mathrm{T}\land \mathrm{T}\\ &\equiv(p\lor\neg p)\land(q\lor\neg q). \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.