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$
2
  • $\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$ Commented Aug 29, 2017 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$ Commented Aug 29, 2017 at 11:42

2 Answers 2

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
  • 1
    $\begingroup$ Thank you for correcting my initial mistake. Had to change my process to get to the right answer though $\endgroup$
    – Derpm
    Commented Aug 29, 2017 at 12:43
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$
1
  • $\begingroup$ Thanks :) Fixing my initial mistake still did not get me the answer but you pointed me in the right direction. Thanks! $\endgroup$
    – Derpm
    Commented Aug 29, 2017 at 12:43

You must log in to answer this question.

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