0
$\begingroup$

Prove

$\neg ((P\land Q)\lor \neg (P\land T)\lor (Q\land T)) \equiv P \land \lnot Q \land T$

Using only De Morgans Laws and the Distribution Laws. I managed to get the left hand side to reduce to the form:

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

I'm sure I'm missing an obvious step. Can someone point me in the right direction?

$\endgroup$
  • 1
    $\begingroup$ Just so you know, I fixed a typo in your answer where you had $\sim P$ when it should have been $\sim Q$. $\endgroup$ – Noble Mushtak May 12 '16 at 19:18
  • $\begingroup$ Oh, sorry. Thanks for fixing it. $\endgroup$ – James Paterson May 12 '16 at 19:20
1
$\begingroup$

Hint:

  1. Distribute out the $\sim Q$ from the two disjunctions that have it.
  2. Use an absorption law to finish the proof.
$\endgroup$
  • $\begingroup$ Distributing gets me $(\lnot Q \lor (\lnot P \land \lnot T))\land P \land T$. It's clear to see that this can simplify down to the target by eye, but I'm not sure if I can use rules that they haven't shown me. $\endgroup$ – James Paterson May 12 '16 at 19:23
  • 2
    $\begingroup$ If you can't use an absorption law, then just prove the absorption law. As you said, we have: $$(\sim Q \vee (\sim P \wedge \sim T)) \wedge (P \wedge T)$$ Distribute $P \wedge T$ over the disjunction: $$(\sim Q \wedge P \wedge T) \vee (\sim P \wedge \sim T \wedge P \wedge T)$$ The latter expression in this disjunction is clearly false by the Law of Contradiction, so we can remove it from the disjunction by the Law of Identity, leaving us with: $$\sim Q \wedge P \wedge T$$ $\endgroup$ – Noble Mushtak May 12 '16 at 20:02
1
$\begingroup$

Try to use the fact conjunction distributes over disjunction, i.e.: $$(A \vee B) \wedge C = (A \wedge C) \vee (B \wedge C).$$ So try and distribute $(\neg Q \vee \neg T) \wedge P \wedge T$ over $\neg Q \vee \neg P$. Then one of the two propositions in the resulting disjunction is never true, so you can eliminate it. Then you use the distributive law once more and you obtain the result by eliminating once more.

$\endgroup$
  • $\begingroup$ Distributing gives me $(\lnot Q \lor (\lnot P \land \lnot T))\land P \land T$. Should I just argue that $(\lnot P \land \lnot T)$ cannot be true as well as $P \land T$, or is there a more mathematical way of doing it? $\endgroup$ – James Paterson May 12 '16 at 19:32
  • $\begingroup$ Distributing gives me $$(\neg P \wedge P \wedge T \wedge (\neg Q \vee \neg T)) \vee (\neg Q \wedge P \wedge T \wedge (\neg Q \vee \neg T)).$$ I used the distribution law with $A = \neg Q$, $B = \neg P$ and $C=P \wedge T \wedge (\neg Q \vee \neg T)$ (sorry for some switching of symbols where commutativity allowes me to). $\endgroup$ – M. Van May 12 '16 at 19:41

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.