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$ Commented Apr 15, 2021 at 2:25
  • $\begingroup$ @AlannRosas Only basic equivalences. Here you can check them: postimg.cc/Z9n9565t. $\endgroup$
    – Augus
    Commented Apr 15, 2021 at 2:29

1 Answer 1

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$

You must log in to answer this question.

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