Page 21 - Chapter 2

 EXAMPLE 5 We add (~q) into hypothesis p 1 ∧ p 2 ∧… ∧

Is the following argument valid? p n, if the enlarged hypothesis p 1 ∧ p 2 ∧… ∧ p n
∧ (~q) implies a contradiction, then we can
If taxes are lowered, then income rises
Income rises conclude that q follows from p 1 ,p 2 , … and p n

∴ taxes are lowered
Solution:  EXAMPLE 7
Let p: taxes are lowed q: income rise Prove there is no rational number a/b
p=>q whose square is 2, namely, sqrt(2) is
(or show the truth table of
q (p=>q) ∧ q => p , and determine irrational.
∴ p whether or not it is a tautology) Solution:
Then argument is not valid , since p=>q and Let p: a, b are integers and no common

q can be both true with p being false. factors, and b is not 0
2
q: (a/b) is not 2
 Indirect Method of Proof In order to prove p => q ,
The tautology We try to find the contradiction from p ∧ ~q

(p=>q )  (~q) => (~p ) Refer to Example 7 for more details.
(An implication is equivalent to its
contrapositive)  EXAMPLE 8:

Note:
Prove or disprove the statement that if x
To proof p=>q indirectly, we assume q is 2 2
and y are real numbers, (x =y )  (x=y)
false (~q) and show that p is then false (~p)
Solution:
2 2
Since (1) =(-1) , but -1 ≠ 1, the result is
 EXAMPLE 6 false. Our example is called counterexample,

2
Let n be an integer. Prove that if n is odd, and any other counterexample would do just
then n is odd. as well.

Solution: Note:
2
Let p: n is odd , q: n is odd. If a statement claims that a property holds
To prove that (p=>q) for all objects of a certain type, then to prove

We try to prove its contrapositive ~q=>~p it, we must use steps that are valid for all
Assuming that n is even (~q), let n=2k, k is objects of that type and that do not make
2
2
2
an integer, then we have n = (2k) =4k is references to any particular object. To
even (~p). disprove such a statement, we need only
Hence, the given statement has been show one counterexample.
proved.

 The tautology
((p ⇒ q) ∧ (~q)) ⇒ ~p
If a statement p implies a false statement
q, then p must be false.

Proof by contradiction
To prove (p 1 ∧ p 2 ∧… ∧ p n) ⇒ q ,