0
$\begingroup$

I've been working through Logical Equivalence problems, and this one seems to have gotten me stuck! Can somebody help?

I'm trying to use Logical Equivalence Laws to show the LHS is equivalent to RHS

$$(((P\land R) \rightarrow (\lnot P \lor Q)) \lor (\lnot(P \land \lnot Q)) \equiv \lnot P \lor (\lnot Q \rightarrow \lnot R)$$

$\endgroup$
3
  • $\begingroup$ What exactly is the problem? Do you need to show that this is a tautology? $\endgroup$
    – mrp
    Feb 7, 2015 at 13:36
  • $\begingroup$ @mrp - I need to show the Left Hand Side is equal to the Right Hand Side $\endgroup$
    – Mathematica
    Feb 7, 2015 at 13:37
  • $\begingroup$ For this kind of problems, just reduce each side separately by eliminating implications and equivalences and using absorption and distributivity to get as simple forms as possible before trying to make them match. Unless cunningly designed, almost all such problems will be solved easily. $\endgroup$
    – user21820
    Feb 7, 2015 at 14:40

2 Answers 2

Reset to default
1
$\begingroup$

$$\begin{align}(((P\land R) \rightarrow (\lnot P \lor Q)) \lor (\lnot(P \land \lnot Q)) & \equiv ((\lnot(P \land R) \lor (\lnot P \lor Q)) \lor (\lnot (P \land \lnot Q))\tag{1}\\ \\ &\equiv \lnot P \lor \lnot R \lor \lnot P \lor Q \lor \lnot P \lor Q\tag{2}\\\\ &\equiv \lnot P \lor \lnot R \lor Q \tag{3}\\ \\ &\equiv\lnot P \lor (R\rightarrow Q) \tag{4}\\ \\ &\equiv \lnot P \lor (\lnot Q \rightarrow \lnot R)\tag{5} \end{align}$$

$\endgroup$
3
  • $\begingroup$ How did you get from line 2 to line 3? $\endgroup$
    – Mathematica
    Feb 7, 2015 at 22:35
  • $\begingroup$ It's called simplification (some call it reiteration): $P\lor P \equiv P$ and also (not needed here) $P \land P \equiv P$. (Also, by associativity and commutativity, you can rearrange the propositions so you have the repetitions side by side. Note: I just numbered the lines. Did you mean $(2) \to (3)$? Or $(1)\to (2)$? $\endgroup$
    – amWhy
    Feb 7, 2015 at 22:49
  • $\begingroup$ Yes from (2) - (3) $\endgroup$
    – Mathematica
    Feb 7, 2015 at 23:19
0
$\begingroup$

$[[(P\land R)\implies(\neg P\lor Q)]\lor\neg(P\land\neg Q)]\equiv$

$[[\neg(P\lor R)\lor(\neg P\lor Q)]\lor(\neg P\lor Q)]\equiv$

$[[(\neg P\lor\neg R)\lor(\neg P\lor Q)]\lor(\neg P\lor Q)]\equiv$

$[(\neg P\lor (\neg R\lor Q))\lor (\neg P\lor Q)]\equiv$

$(\neg P\lor\neg R\lor Q)$ (The rest are eliminated because they are already present)$\equiv[\neg P\lor (Q\lor\neg R)]\equiv$

$[\neg P\lor (\neg(\neg Q)\implies \neg R)]\equiv$ (contraposition)

$\endgroup$

You must log in to answer this question.

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