3
$\begingroup$

$$ (P\leftrightarrow Q) = (P\lor Q)\to(P\land Q)$$

How can I prove this equation using propositional logic laws? it would be great if someone can explain this with all steps.

$\endgroup$
  • 2
    $\begingroup$ If your question is to prove $P \iff [(P\vee Q)\implies(P\wedge Q)]$, there is a counterexample: $P$:T, $Q$:F. $\endgroup$ – The Great Seo May 6 '15 at 8:08
  • 1
    $\begingroup$ Do you mean $P\leftrightarrow\big((P\lor Q)\to(P\land Q)\big)$ or $\big(P\leftrightarrow(P\lor Q)\big)\to(P\land Q)$? $\endgroup$ – Demosthene May 6 '15 at 8:33
  • $\begingroup$ YEAH P↔((P∨Q)→(P∧Q)) $\endgroup$ – Ali May 6 '15 at 9:43
  • 1
    $\begingroup$ I MEAN I HAVE TO PROVE THAT P ↔ Q IS EQUAL TO (P∨Q)→(P∧Q)) USING LAWS $\endgroup$ – Ali May 6 '15 at 9:46
  • $\begingroup$ @Ali: Are another pair of parentheses are needed for clarity, around $P\leftrightarrow Q$? I'll add them if you will check that this edit correctly represents your meaning. $\endgroup$ – hardmath May 6 '15 at 13:04
4
$\begingroup$

$P\leftrightarrow Q$ is true whenever $P$ and $Q$ have the same truth value, i.e. when they're both false or both true. Hence: \begin{align} P\leftrightarrow Q&=(\neg P\land\neg Q)\lor (P\land Q)\\ &=\neg(P\lor Q)\lor (P\land Q)\\ &=(P\lor Q)\to(P\land Q) \end{align}

First line: this is the definition of the biconditional ($\leftrightarrow$) as a disjunction between the two cases "both $P$ and $Q$ are false" or "both $P$ and $Q$ are true".

Second line: we apply De Morgan's law to the first parenthesis, "factoring out" a negation ($\neg$). Indeed, having both $P$ and $Q$ false is the same has not having either of them true.

Third line: we move from the second to the third line by applying the definition of the implication ($\to$) as a disjunction. For a premise to logically imply a conclusion, we require the conclusion to never be false when the premise is false, or equivalenty, as in our case, that either the premise be false or the conclusion be true. Here the premise is $(P\lor Q)$ and the conclusion is $(P\land Q)$.

$\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.