Prove $(p \rightarrow q) \land (r \rightarrow s) \implies ( \neg p \lor \neg r \lor q \lor s)$

$$((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).

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