0
$\begingroup$

Use the laws of logic to show the following: $$(a) \quad(p\rightarrow r)\vee (q\rightarrow r) \equiv (p\wedge q)\rightarrow r$$ $$(b) \quad [\neg q\wedge (p\rightarrow q)]\rightarrow \neg p\quad \text{is a tautology}$$

I don't understand which laws to use where. I can't seem to change anything that works. Any help would be appreciated.

Thanks.

$\endgroup$
  • $\begingroup$ Posting images is acceptable only if there is no other way to ask a question. Otherwise, you should type the question down if you want any answers. $\endgroup$ – 5xum Aug 17 '15 at 13:40
  • $\begingroup$ Welcome to MathSE! I edited your post to include the equations directly in your question. Please do not post links to images if it is easily possible to write your question using LaTeX, see this guide: (meta.math.stackexchange.com/questions/5020/…). $\endgroup$ – Hirshy Aug 17 '15 at 13:45
  • $\begingroup$ My apologies. Any help would be appreciated. $\endgroup$ – Heelloppp Aug 17 '15 at 13:46
0
$\begingroup$

Hint: using $a\rightarrow b\equiv \neg a\vee b$, De Morgan's law and that $\vee$ is associative we get for the RHS of $(a)$: $$(p\wedge q)\rightarrow r \equiv \neg (p\wedge q)\vee r \equiv (\neg p \vee \neg q) \vee r \equiv \neg p \vee \neg q \vee r.$$

Now notice that $$\neg p \vee \neg q \vee r \equiv \neg p \vee r \vee \neg q \vee r$$ and use that $\vee$ is also commutative.

Something similar will work for $(b)$.

$\endgroup$
  • $\begingroup$ Hi, thanks for the help. I didn't think of changing the right side. I'm just confused as to how ¬p∨¬q∨r≡¬p∨¬p∨¬q∨r is correct? Where did the extra -p come from? Don't i need two rs not two ps? $\endgroup$ – Heelloppp Aug 17 '15 at 14:19
  • $\begingroup$ Of course, I meant to add $r$ not $\neg p$, $\endgroup$ – Hirshy Aug 17 '15 at 14:23
  • $\begingroup$ Ah, is that because the (¬p∨¬q)∨r is expanded by the r? If so, what law is that? $\endgroup$ – Heelloppp Aug 17 '15 at 14:25
  • $\begingroup$ No, it is not expaned. It's just that $x\wedge x \equiv x \equiv x\vee x$ (idempotent laws). $\endgroup$ – Hirshy Aug 17 '15 at 14:29
  • $\begingroup$ Hmm, i don't understand how ¬p∨¬q∨r≡¬p∨r∨¬q∨r another r is added here. Apart from that i am fine. $\endgroup$ – Heelloppp Aug 17 '15 at 14:32

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.