0
$\begingroup$

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?

enter image description here

I leave the image again without any mark

enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

There are in fact several issues with your approach. Here are few observations:

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.

So, propositional logic does not help there, but, suppose it did: in classical propositional logic, an approach different from inferential proof (where equivalences such as DeMorgan's, usually axiomatized, are used in inferential steps) is the so called "method of truth tables", where we simply compute the truth table for the statement to prove (exactly as you have done in your example, except that you don't need DeMorgan's or any other transformation/simplification, just compute the formula as given), and the statement is a theorem (is true) iff the truth table (the last column, the one corresponding to the full statement) is identically true, i.e. true everywhere.

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .