getting rid of implication

Question

I'm supposed to show that

$[(P \implies Q) \land P] \implies Q$ is a tautology.

I used the conditional law $$(P \implies Q) \iff \lnot(P \land \lnot Q)$$ to change this to: $$[(\lnot P \lor Q) \land P] \implies Q.$$

I've reduced this (using the distributive law) to: $$(P\land Q) \implies Q.$$

Is there another law to rid of this implication?

If not, how would I show this is a tautology?

Thank you

score 4 · Accepted Answer · answered Oct 09 '13 at 19:25

4

Hint: Use the conditional law again.

answered Oct 09 '13 at 19:25

Cameron Buie

102,994

But it's (P∧Q) not just P – muros Oct 09 '13 at 19:27
That's true, but it's no problem. The conditional law simply says that $$(A\implies B)\equiv(\neg A\vee B),$$ yes? (The actual choice of letters isn't important, just the idea.) Apply this to the case $A=P\wedge Q$ and $B=Q.$ – Cameron Buie Oct 09 '13 at 19:29
oh.. I suppose it will be ¬(P∨Q)vQ. Thanks – muros Oct 09 '13 at 19:30
Not quite. It will be $\neg(P\wedge Q)\vee Q$, instead. Can you see what to do next? – Cameron Buie Oct 09 '13 at 19:30

score 2 · Answer 2 · answered Oct 09 '13 at 19:30

2

You have $(P \land Q ) \to Q$, which becomes $\lnot(P \land Q) \lor Q$.

Using De Morgan's law, we have $\lnot(P \land Q) = (\lnot P) \lor (\lnot Q)$, so the above becomes $(\lnot P) \lor (\lnot Q) \lor Q) = (\lnot Q) \lor Q$, which is a tautology.

answered Oct 09 '13 at 19:30

copper.hat

172,524

score 0 · Answer 3 · answered Dec 29 '18 at 13:56

$[(P \implies Q) \land P] \implies Q$ is a tautology.

Because $(P \implies Q) \equiv (\lnot P \lor Q)$

$[(\lnot P \lor Q) \land P] \implies Q$

$(\lnot P \land P) \lor (Q \land P) \implies Q$

Because $(\lnot P \land P)$ always false, then

$(Q \land P) \implies Q$

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

$\lnot Q \lor \lnot P \lor Q$

getting rid of implication

3 Answers3