Proofing Techniques

 

• In order to show that an existential statement is true: give an example to prove it.
• In order to show that a universal statement is false: give a counter-example to prove it.

When we try to find a proof based on logical deductions, the above techniques may be a bit complicated. in such cases, a technique called proof by contradiction can be useful. In order to show that a statement is true, assume the opposite and show that it leads to a false conclusion.

Let’s solve some numericals based on proof by contradiction.

1. Use the method of proof by contradiction to show that 200 is not a perfect square.

Let us assume that 200 is a perfect square. So, n*n=200 where n is a positive integer.

We know that, 14*14=196 and 15*15=225. So, based on this we can deduce that 14<n

So, we conclude that 200 is not a perfect square.

2. Prove that, for all natural numbers n, n*n+7n+12 is an even number.

Let us assume that for all natural numbers n, n*n+7n+12 is not an even number. So, it is an odd number.

If we take n=1, result is 20 i.e. even number. Similarly for n=2, result is 30 i.e. even number and so on. So, it is not an odd number.

So, we conclude that n*n+7n+12 is an even number.

3.State whether for all natural numbers n, 7n+2 is a perfect square is true or false.

For n=1, result is 9 i.e. a perfect square. Similarly for  n=2, result is 16 i.e. a perfect square. When n=3, the result is 23 i.e. not a perfect square. So, the statement is false.

So, we conclude that n=3 is the counter example for 7n+2.

The Logical Framework

Exercise  3.1

To determine the corresponding truth values for the statement (p ^ q) v r.

Proof:
p      q      r       p ^ q      (p ^ q) v r

T       T     T         T              T
T       T     F         T              T
T       F     T         F              T
T       F     F         F              F
F       T     T         F              T
F       T     F         F              F
F       F     T         F              T
F       F     F         F              F

Exercise  3.2

By constructing the truth tables , show that ~ (p ^ q) and (~p) v (~q) are logically equivalent.

Proof:

p        q     ~p     ~q        (p^q)       ~ (p ^ q)         (~p) v (~q)

T         T       F      F          T                 F                  F
T         F       F      T          F                 T                  T
F         T       T      F          F                 T                  T
F         F       T      T          F                 T                  T

Hence proven   ~ (p ^ q)  and  (~p) v (~q) are logically equivalent.

Exercise  3.3

Construct the truth table for the statement (~p) v q, and deduce the it is logically equivalent to p -> q.

Proof:

p         q       ~p      (~p) v q     p -> q

T        T        F           T             T
T        F        F           F              F
F        T        T           T             T
F        F        T           T             T

The corresponding truth values are determined for the statement (~p) v q and also it is proven to be logically equivalent to p -> q.

Exercise 3.4

Verify explicitly that the truth table for (p=>q) ^(q=>p) is the same as the one for  p <==> q.

Proof:

p       q       p=>q      q=>p          (p=>q)^(q=>p)          p<==>q

T      T          T            T                      T                             T
T      F          F            F                       F                             F
F      T          T            F                       F                             F
F      F          T            T                       T                             T

Hence proven, the truth table for (p=>q) ^ (q=>p) is the same as the one for  p <==> q.

Exercise 3.5

Write down the contrapositive forms of the statements :

* if n is a multiple of 7 then n is not a multiple of 3.
Solution  :
If n is a multiple of 3 then n is not a multiple of 7.

*if n is a multiple of 12 then n is a multiple of 4.
Solution :
If n is not a multiple of 4 then n is not a multiple of 12.

Exercise 3.6

Determine the truth values of the following statement.

“For every pair of natural numbers x and y such that  x > 2y there is a natural number z such that
x > z > y”
Solution :
If  x and y are a pair of natural numbers such that x  > 2y. Since y is a natural number, 2y is also a  natural number.
Then x (2y+1) or larger is to satisfy the condition
x >2y  so 2y+1.

Therefore we conclude,
Let : x = 2y + 1,
z = 2y
So y  <  2y and  2y  <  2y+1 , y  <  z  <  x
So proven  x < z < y .