In this case, we will attempt a proof by contradiction.
Remember that to use proof by contradiction to prove a conditional statement(p->q), we do the following:
- Assume the negation of q (the conclusion of the conditional statement).
- Use p and ¬q to arrive at a contradiction.
This type of proofs is valid because p->q ≡ (p^q)-> F.
p= “mn is even”
q= “m is even or n is even”
¬q = “m and n are odd”. (¬(pvq)≡¬p^¬q by the De Morgan law)
If m and n are both odd, then:
m= 2k+1, for some integer k
n=2t+1, for some integer t
mn = (2k+1) x (2t+1) = 4kt + 2k + 2t +1 = 2(2kt+k+t) + 1
Therefore, mn is odd.
Because p is true (premise) and ¬p is also true, we have a contradiction.
This completes the proof by contradiction ∎
Related posts:
- Use a direct proof to show that the sum of two even integers is even
- Use a direct proof to show that the sum of two odd integers is even
- Use a proof by contradiction to prove that the sum of an irrational number and a rational number is irrational
- Prove or disprove that the product of two irrational numbers is irrational
- Show that if n is an integer and n^3+5 is odd, then n is even using a proof by contraposition and a proof by contradiction
