2

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.

Rodrigo de Azevedo
  • 1
Derpm
  • 69
  • 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. – Mauro ALLEGRANZA Aug 29 '17 at 11:40
  • In order to succeed, you have to apply correct transformations ending with T (or some equivalent, like e.g. $p \lor \lnot p$). – Mauro ALLEGRANZA Aug 29 '17 at 11:42

2 Answers2

2

You've made a mistake:

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

Shaun
  • 44,997
  • 1
    Thank you for correcting my initial mistake. Had to change my process to get to the right answer though – Derpm Aug 29 '17 at 12:43
1

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.

Graham Kemp
  • 129,094
  • Thanks :) Fixing my initial mistake still did not get me the answer but you pointed me in the right direction. Thanks! – Derpm Aug 29 '17 at 12:43