2
$\begingroup$

Prove that $$[\neg p \land (p \lor q)] \to q$$ is TRUE using logic laws.

Here is how I solved it:

Starting with
$[\neg p \land (p \lor q)] \to q$
An understood logical equivalence
$[\neg \neg p \land \neg(p \lor q)] \lor q$
Double negation
$[p \land \neg(p \lor q)] \lor q)$
De Morgan's law
$[ p \land (\neg p \land \neg q)] \lor q$
Associative law
$[(p \land \neg p) \land \neg q] \lor q$
Negation law
$(F \land \neg q) \lor q$
Identity law
$F \lor q$
$ q $

The problem is that to my understanding, this doesn't necessarily prove the statement to be true, and I am not sure where I have gone wrong.

$\endgroup$
  • $\begingroup$ Having corrected the mistake, your argument does not prove that the formula is a tautology (i.e. always TRUE). With your approach you have showed that the formula is equiv to $q$ and this is not always true. $\endgroup$ – Mauro ALLEGRANZA Aug 29 '17 at 11:40
  • $\begingroup$ In order to succeed, you have to apply correct transformations ending with T (or some equivalent, like e.g. $p \lor \lnot p$). $\endgroup$ – Mauro ALLEGRANZA Aug 29 '17 at 11:42
1
$\begingroup$

I'd start by distribution, since $\neg p\wedge(p\vee q)$ equivates to $(\neg p\wedge p)\vee (\neg p\wedge q)$, which simplifies through complementation and identity, to $(\neg p\wedge q)$.   (Sometimes accepted as a single step, "complementary absorption".)

Then you can apply implication equivalence, and deMorgan's rule to begin simplifying the whole expression down to the truth constant.

$\endgroup$
  • $\begingroup$ Thanks :) Fixing my initial mistake still did not get me the answer but you pointed me in the right direction. Thanks! $\endgroup$ – Derpm Aug 29 '17 at 12:43
2
$\begingroup$

You've made a mistake:

$$(\neg p \land (p \lor q))\to q$$ is $$(\neg \neg p \lor \neg(p \lor q)) \lor q.$$

$\endgroup$
  • 1
    $\begingroup$ Thank you for correcting my initial mistake. Had to change my process to get to the right answer though $\endgroup$ – Derpm Aug 29 '17 at 12:43

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.