NewLec 3

MA1100 Basics of Mathematics
Lecture 3: More on Connectives
Yang Yue
Department of Mathematics
National University of Singapore
Aug. 21, 2006

Outline
1 If and Only If
2 Mathematical Definitions
3 Logical Rules
4 Example of Proof by Contradiction
5 Example of Proving “p ∨ q”
The bi-conditional “if and only if”
We use p ↔ q to denote the compound “p if and only if q”.
Truth table of p ↔ q:
p q p↔q
T T T
T F F
F T F
F F T
p ↔ q and (p → q) ∧ (q → p) are equivalent.

Remarks
We often use “iff” for “if and only if”.
If p ↔ q is true, then we say “p is a sufficient and

necessary condition for q”.
More Explanations on p → q
Most modifications are unsatisfactory: Consider the truth

table:
p q p→q
T T T
T F F
F T *
F F **
Setting ∗ = ∗∗ = T seems most reasonable.
Definitions
In math, definitions provide precise meaning of

mathematical objects or symbols being used.
For examples, the definition of prime number can be

written as follows: “a positive integer p is a prime number,
iff p 6= 1 and only divisors of p are 1 and p”.
(Why are definitions necessary?)
Convention: All “if” in a definition means “if and only if”.

Examples
We say that a positive integer n is a perfect square if

n = m2 for some integer m.
We say that a function f : A → B is surjective if for all y ∈ B

there is an x ∈ A such that f (x) = y .
We say that a is a root of the equation f (x) = 0 if f (a) = 0.
(All “if” actually means “if and only if”.)

Modus Ponens
Intuitively it is clear that from p → q and p we get q.
We may set it as an inference rule.
(It is called Modus Ponens.)

Rules Preserve Truth
Example
[(p → q) ∧ p] → q is a tautology.
Thus we can deduce the truth of q if we know the truth of

both p and p → q.
We leave the precise definition of logical rules to logicians.

In this course, we only require that rules preserve the truth
(which are often variations of Modus Ponens).
Examples
From p → q and q → r , we can deduce p → r .
This can be justified by showing that
[(p → q) ∧ (q → r )] → (p → r )
is a tautology.
From p ∨ q and ¬p, we can deduce q, as

[(p ∨ q) ∧ ¬p] → q is a tautology.
More Examples of Logical Arguments
Show that from p → (q → r ), ¬s ∨ p and q, we can deduce

s → r.
We need to obtain r from the assumption of s.
The argument goes:

From s and ¬s ∨ p, we get p by previous example.
From p and p → (q → r ), we get q → r .
From q → r and q, we get r .
(These arguments based skeleton forms can help us

reasoning. We leave the discussion of validity to future
courses.)
Examples of Proofs: Plan
We prove a few statements.
Some knowledge on numbers is assumed.
(we will repeat the knowledge later.)
Pay attention to the logical flow.

First Example
Example
Show that 300 000 067 110 605 737 is not a perfect square.
Let’s call the number z.

Discussion
Maybe we can use brute force, but it is too tedious.
Or maybe z is a perfect square, say t 2 , what can we say

about t? t must be odd, because ...
Thus t ends in a 1, 3, 5, 7 or 9, t 2 should ends in a

1, 9, 5, 9, 1.
Why is that? Because say t = 10m + 1, then

t 2 = 100m2 + 20m + 1, ...
Proof of Statement 1
Proof.
Suppose that the given number z is the square of some (odd)
integer, say t. Now t = 10m + r for some integer m and for
some integer r from the list 1, 3, 5, 7, 9. But then
t 2 = (10m + r )2 = 100m2 + 20mr + r 2
and so that last digit of z(= t 2 ) is the same as the last digit of
r 2 , which is, 1 or 9 or 5. But z’s final digit is a 7. Hence z
cannot be a perfect square.
Comments
Let’s take a closer look of our proof.

We begin with “Suppose that z is a square...”, that is we
assumed the contrary of what is claimed.
(One advantage in this approach is that it gives us

something to work from.)
We then deduce that, if it were a square then z would end

in a 1, a 5 or a 9, therefore contradicting the fact that z
ends in a 7.
Because of this contradiction, we have to admit that our

supposition was wrong.
Proof by Contradiction
This kind of argument – assuming what you wish to prove

is false and deducing a contradiction from this assumed
falsity – is commonly employed in mathematical proof. It is
called proof by contradiction.
Method is more important
You should learn the method, instead of the conclusion.

For example, the same method shows that no perfect
square can end in a 3, which tells us more than the
statement that “the particular number z is not a perfect
square”.
Proof by Cases
We showed that no odd integer t, when squared, can end

in a 7 by considering all five possible cases for t, namely,
t’s last digit being 1 or 3 or 5 or 7 or 9. This is an example
of proof by cases.
The logical principle behind can be described by “from
(C1 → D) ∧ (C2 → D) ∧ (C3 → D) ∧ (C4 → D) ∧ (C5 → D)
we conclude
(C1 ∨ C2 ∨ C3 ∨ C4 ∨ C5 ) → D.”
In our proof, C1 is “The integer t has final digit 1”, etc, and
D is “The integer t 2 does not end in a 7”.
Second Example
Example
Show that 3 < π < 4.
π is the ratio dc of the length, c, of the circumference of a circle
to the length of the circle’s diameter d.
Discussion
c c
We need to show that 3 < d and d < 4.
What we need are two lengths m and n, say, which can be

determined exactly and for which 3 ≤ m < dc < n ≤ 4.
What about the perimeters of squares or hexagons etc,
lying just inside and outside the circle?
Let’s calculate the perimeter of the squares.

Discussion (conti.)
Improve the inscribed square to a hexagon.

Proof.
Let C be a circle of diameter d units. Then the perimeters of
the inscribed regular hexagon and the escribed square are
3d
respectively 3d and 4d. The required ratio thus lies between d
and 4dd , i.e., 3 < π < 4.
Remarks
Sometimes an initial failure can be overcome if we modify

our first attempts.
Drawing pictures may help.

An Example for Fun
Picture can be misleading too!

Example
What’s wrong? Every triangle is isosceles (indeed equilateral).
The wrong proof:

An Example Involving “Or”
Example
Show that either 2007 is a prime or it is divisible by some
number not exceeding 45.
Understanding the Problem
Do we know what ‘prime’ and ‘divisible’ mean?
The statement does not claim that 2007 is prime nor that
2007 is divisible by some number not exceeding 45.
It only says that at least one of these alternatives holds.

Discussion
If 2007 is a prime, then the compound “... or ...” is true. So

to be sure that the statement is true, we are only left to
check that if 2007 is not a prime.
So let us suppose that 2007 is not prime. Then

2007 = mn, can m and n be both > 45?
Proof.
Either 2007 is a prime or it is not. In the former case there is
nothing more to prove. In the latter case there are integers m
and n such that 2007 = mn. If both m and n exceed 45, then
mn > 452 = 2025, which is impossible. Thus one of them must
not exceed 45.
Comments
Always make sure you understand what is being sought

before embarking on an attempt at a solution or proof.
To prove the truth of p ∨ q one possible ploy is to prove that

¬p → q is true.
(Again we use “proof by contradiction” in one step.)

NewLec 3

Uploaded by

Copyright:

Available Formats

NewLec 3

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

NewLec 3

Uploaded by

Copyright:

Available Formats

MA1100 Basics of Mathematics

Lecture 3: More on Connectives

Aug. 21, 2006

4 Example of Proof by Contradiction

We use p ↔ q to denote the compound “p if and only if q”.

p ↔ q and (p → q) ∧ (q → p) are equivalent.

We often use “iff” for “if and only if”.

If p ↔ q is true, then we say “p is a sufficient and

Most modifications are unsatisfactory: Consider the truth

In math, definitions provide precise meaning of

For examples, the definition of prime number can be

(Why are definitions necessary?)

Convention: All “if” in a definition means “if and only if”.

We say that a positive integer n is a perfect square if

We say that a function f : A → B is surjective if for all y ∈ B

We say that a is a root of the equation f (x) = 0 if f (a) = 0.

(All “if” actually means “if and only if”.)

Intuitively it is clear that from p → q and p we get q.

We may set it as an inference rule.

(It is called Modus Ponens.)

Thus we can deduce the truth of q if we know the truth of

We leave the precise definition of logical rules to logicians.

From p → q and q → r , we can deduce p → r .

This can be justified by showing that

From p ∨ q and ¬p, we can deduce q, as

Show that from p → (q → r ), ¬s ∨ p and q, we can deduce

We need to obtain r from the assumption of s.

The argument goes:

(These arguments based skeleton forms can help us

We prove a few statements.

Some knowledge on numbers is assumed.

(we will repeat the knowledge later.)

Pay attention to the logical flow.

Let’s call the number z.

Maybe we can use brute force, but it is too tedious.

Or maybe z is a perfect square, say t 2 , what can we say

Thus t ends in a 1, 3, 5, 7 or 9, t 2 should ends in a

Why is that? Because say t = 10m + 1, then

t 2 = (10m + r )2 = 100m2 + 20mr + r 2

Let’s take a closer look of our proof.

(One advantage in this approach is that it gives us

We then deduce that, if it were a square then z would end

Because of this contradiction, we have to admit that our

This kind of argument – assuming what you wish to prove

You should learn the method, instead of the conclusion.

We showed that no odd integer t, when squared, can end

The logical principle behind can be described by “from

(C1 → D) ∧ (C2 → D) ∧ (C3 → D) ∧ (C4 → D) ∧ (C5 → D)

What we need are two lengths m and n, say, which can be

Let’s calculate the perimeter of the squares.

Improve the inscribed square to a hexagon.

Sometimes an initial failure can be overcome if we modify

Drawing pictures may help.

Picture can be misleading too!

The wrong proof:

Do we know what ‘prime’ and ‘divisible’ mean?

It only says that at least one of these alternatives holds.

If 2007 is a prime, then the compound “... or ...” is true. So

So let us suppose that 2007 is not prime. Then