# Logic behind contrapositive proofs that involves De Morgan's Laws

Suppose $$a,b\in\mathbb{Z}$$. If both $$ab$$ and $$a+b$$ are even, then both $$a$$ and $$b$$ are even

Proof by contrapositive.

Propositions:

• $$P$$: $$ab$$ is even
• $$Q$$: $$a+b$$ is even
• $$R$$: $$a$$ is even
• $$S$$: $$b$$ is even

Then logically we have $$(P\land Q)\implies (R\land S)$$.

We have to negate $$R\land S$$, so $$\neg(R\land S)$$, by De Morgan's Laws we have $$\neg R \lor \neg S$$

And we have to get not $$P\land Q$$, which is $$\neg P \lor \neg Q$$

Then we have $$(\neg R \lor \neg S)\implies(\neg P \lor \neg Q)$$

Which places in a truth table would be the right ones to evaluate this?

My answer is that the first 3 rows are the ones we have to evaluate. My reasoning is:

• First we have to force $$(\neg R \lor \neg S)$$ to be true
• Second we have to prove all different combination that makes $$(\neg R \lor \neg S)\implies(\neg P \lor \neg Q)$$ true (marked in blue brackets)
• Finally, since we have 3 equal combinations we decide to choose only the first 3 rows.

Is my reasoning correct?

I leave the image again without any mark

The statement you want to prove is one of arithmetic, and should rather be formalized in first-order logic (you need predicates, aka propositional functions, indeed already to define $${\operatorname {even}}$$), since the structure of $$a$$ and $$b$$, as well as the specific definitions of $$+$$, $$\times$$ and $${\operatorname {even}}$$ matter. It is in fact a statement that is not purely logical, you need arithmetic facts (previous theorems) to prove it, e.g. that the product of two integers is even iff at least one of the operands is even.
Indeed, $$(P \land Q) \to (R \land S)$$ is not a theorem, as you do not get "V" (true) in all places in the truth table, so it is not a tautology. Which, given it is not difficult to see that the statement in question is in fact true in arithmetic, confirms that propositional logic, at least the formalization you have attempted, is not adequate to represent the problem.