1

Absorption:

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

Reduction:

$$P \land (\neg P \lor Q) = P \land Q$$

Starting with,

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

[Application of Absorption on $\neg P \land (\neg P \lor Q)$, by letting $P= \neg P, Q=Q$ and by commutation on $(R \lor \neg Q)].$

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

[Application of Absorption on $R \land (R \lor \neg Q$), by letting $P=R, Q=\neg Q$]

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

[Using the rule of Reduction on $\neg P \land (P \lor \neg Q)$, by letting $P = \neg P,Q= \neg Q]$

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

[Using the rule of Reduction on $R \land (\neg R \lor Q)$, by letting P=R,Q=Q]

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

tree_traversal
  • 93

1 Answers1

2

First, you need some parentheses, since you have one of those $X \land Y \lor Z$ constructions. So:

$[\color{red}(\neg P \land (\neg P \lor Q)\land (P\lor \neg Q)\color{red})\lor \color{red}(\neg P \land (\neg R \lor Q)\land (R\lor \neg Q)\color{red})]\lor [R \land (\neg P \lor Q)\land (P \lor \neg Q)\land R \land (\neg R \lor Q)\land (R \lor \neg Q)]$

Likewise, seeing where this problem comes from, one of the $\land$'s of the right square bracketed term should be a $\lor$, and so you likewise get:

$[(\neg P \land (\neg P \lor Q)\land (P\lor \neg Q))\lor (\neg P \land (\neg R \lor Q)\land (R\lor \neg Q))]\lor [\color{red}(R \land (\neg P \lor Q)\land (P \lor \neg Q)\color{red})\color{red}\lor \color{red}(R \land (\neg R \lor Q)\land (R \lor \neg Q)\color{red})]$

Because you were missing parentheses, I actually intially misread your statements, and concluded that you had applied the rules incorrectly, but as it turns out you did apply them correctly!

Here is what it looks like with proper parentheses in place. First, the $\neg P$ term absorbs the $(\neg P \lor Q)$ term, resulting in:

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

Likewise, the $R$ completely gets rid of the $(R \lor \neg Q)$:

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

Now, Reduction using the $\neg P$:

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

And finally, Reduction using the $R$:

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

Good job! ... just make sure parentheses fully disambiguate everything

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • @tree_traversal Oh I see ... I got confused because you have a problem with the parentheses so I misread ... this is exactly why you always need to put parentheses where needed! – Bram28 Feb 03 '19 at 17:46
  • Reading through your new edit to see if it clarified my question – tree_traversal Feb 03 '19 at 17:47
  • 1
    @tree_traversal I'll just show how to do it properly because of the parentheses issue ... gimme a sec ... – Bram28 Feb 03 '19 at 17:47
  • Thanks. I still had questions after your edit. Looking forward to seeing the steps. – tree_traversal Feb 03 '19 at 17:48
  • OK, one quick question, actually ... is the right side supposed to be $[(R \land (\neg P \lor Q)\land (P \lor \neg Q)) \color{red}\lor (R \land (\neg R \lor Q)\land (R \lor \neg Q)]$? – Bram28 Feb 03 '19 at 17:50
  • Problem comes from https://math.stackexchange.com/questions/3092595/assistance-in-completing-the-proof-p-→-q∧q-→-r-is-equivalent-to-p-→-r∧ – tree_traversal Feb 03 '19 at 17:51
  • 1
    @tree_traversal OK, so yes, that $\land$ should be a $\lor$ ... that makes a lot more sense ... OK, will work with that! – Bram28 Feb 03 '19 at 17:55
  • Thanks for the response. I am a bit confused. It looks like I did the 2 absorptions and 2 reductions as you did? For instance, using the rule of Reduction on $\neg P \land (P \lor \neg Q)$, by letting $P = \neg P,Q= \neg Q$ (substituting those into the actual rule) I got: $[( \neg P \land \neg Q)\lor \neg P \land (\neg R \lor Q)\land (R \lor \neg Q)]\lor [R \land (\neg P \lor Q)\land (P \lor \neg Q)\land R \land(\neg R \lor Q)]$. Which looks to be the same thing you got. – tree_traversal Feb 03 '19 at 18:08
  • 1
    @tree_traversal Yes, I believe you know how to apply them correctly ... it was because of the missing parentheses that I read your statements differently. Again, it is crucial that you have those parentheses in place :) – Bram28 Feb 03 '19 at 18:10
  • Ah, I see! So, just for clarification.. I did the applications correctly? – tree_traversal Feb 03 '19 at 18:10
  • 1
    @tree_traversal Yes, now that I know how you intended the parentheses, you did that all correctly! But I recommend you go back and those parentheses .... – Bram28 Feb 03 '19 at 18:17
  • 1
    Sweet, thanks. Could you edit the answer "No. Now,.." comment to something where it is clear (to whomever may read this in the future) that it is correct, but I was making confusing use of parentheses? Anyway, thanks again. Accepting your answer. – tree_traversal Feb 03 '19 at 18:19
  • 1
    @tree_traversal Yes, I will do that! – Bram28 Feb 03 '19 at 18:23