$$((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p\land r)\rightarrow (q\lor s))$$ I have some problem with formula: $$(p \rightarrow q) \land (r \rightarrow s) $$ $$\equiv(\neg p \lor q) \land (\neg r \lor s)$$ $$\equiv(\neg p \land \neg r) \lor (\neg p \land s) \lor (q \land \neg r) \lor (q \land s)$$ I have to prove this implies: $$(\neg p \lor \neg r \lor q \lor s)$$

The problem is that I don't know what to do to get this?

Wolfram says this is a tautology, but I don't know how to prove it (Wolfram).

  • 1
    $\begingroup$ If you want an equivalent form, it won't be of the last form. $\endgroup$ – Thomas Andrews Jun 24 '15 at 17:15
  • $\begingroup$ They cannot be equivalent, since if $q, r,\lnot s$, then the first one is false, the second one is true. $\endgroup$ – user26486 Jun 24 '15 at 17:20
  • $\begingroup$ I edited one thing $r$ should be $\neg r$ and wolfram tells that is tautology but how proof it? $\endgroup$ – hadson172 Jun 24 '15 at 17:32
  • $\begingroup$ the standard technique that always works for proving logical tautologies is using truth tables. $\endgroup$ – supinf Jun 24 '15 at 17:40
  • $\begingroup$ For 4 combinations? On exams i have 2 minutes on this $\endgroup$ – hadson172 Jun 24 '15 at 17:41

In general, we have

$$(A\implies B)\iff(B\lor\lnot A)$$ and $$(A\land B)\implies (A\lor B)$$

Applying the first of these, we get

$$((p\implies q)\land(r\implies s))\iff((q\lor\lnot p)\land(s\lor\lnot r))$$

Applying the second, we get

$$((q\lor\lnot p)\land(s\lor\lnot r))\implies((q\lor\lnot p)\lor(s\lor\lnot r))$$


First note that $$(p\land r)\rightarrow (q\lor s)$$ $$\equiv\neg (p \land r) \lor (q\lor s)$$ $$\equiv(\neg p \lor \neg r) \lor (q\lor s)$$ $$\equiv\neg p \lor \neg r\lor q\lor s$$ $$\equiv(\neg p \lor q)\lor(\neg r\lor s)$$ $$\equiv(p \rightarrow q)\lor(r\rightarrow s)$$ Therefore $$((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p\land r)\rightarrow (q\lor s))$$ $$\equiv((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p \rightarrow q)\lor(r\rightarrow s))$$ $$\equiv\neg((p \rightarrow q) \land (r \rightarrow s))\lor ((p \rightarrow q)\lor(r\rightarrow s))$$ $$\equiv\neg(p \rightarrow q) \lor \neg(r \rightarrow s)\lor (p \rightarrow q)\lor(r\rightarrow s)$$ $$\equiv \mbox{tautology}$$


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.