Proving conjunction of two implications Let $p, q, r, s$ be propositions. I am supposed to prove the following statement.
$(p \Rightarrow q \ \ \land \ \ r \Rightarrow s) \Rightarrow (p \land r \Rightarrow q \land s) \land (p \lor r \Rightarrow q \lor s)$
Would it be true if I show this statement is a tautology with a truth table and so this implication is always true? If it is not true how can I show this implication or is there any better way for this?
Thanks in advance for any help.
 A: As Shubham Johri mentions in a comment, yes, you can test the validity of the formula through a truth table, but it would be a huge, nightmarish one.
So, when is an implication false? When the antecedent, in this case $(p\rightarrow q)\wedge (r\rightarrow s)$, is true, but the consequent, here $\Big((p\wedge r)\rightarrow(q\wedge s)\Big)\wedge\Big((p\vee r)\rightarrow(q\vee s)\Big)$, is false.
When is a conjunction true and when is it false? When, respectively, both statements are simultaneously true, and when any of the two is false, meaning in our case that $p\rightarrow q$ and $r\rightarrow s$ are true, but either $(p\wedge r)\rightarrow(q\wedge s)$ or $(p\vee r)\rightarrow(q\vee s)$ is false.

*

*If $(p\wedge r)\rightarrow(q\wedge s)$ is false, $p\wedge r$ is true but $q\wedge s$ is false, meaning $p$ and $r$ are true, while $q$ or $s$ is false; either way, we got a contradiction, since $p$, $r$, $p\rightarrow q$ and $r\rightarrow s$ being true imply (by Modus Ponens), that BOTH $q$ and $s$ must be true.


*If $(p\vee r)\rightarrow(q\vee s)$ is false, $p\vee r$ is true and $q\vee s$ is false, meaning $p$ or $r$ is true, while both $q$ and $s$ are false. Again, we reach a contradiction regardless of the case, since if $p$ is true, given $p\rightarrow q$ is true one finds $q$ is true; and if $r$ is true, given $r\rightarrow s$ is also true one derives $s$ is true.
Since, by assuming the formula is not a tautology, we reached a contradiction, we must reach the conclusion that the original formula is, in fact, a tautology.
