University of Hawaii

ICS141:
Discrete Mathematics for
Computer Science I
Dept. Information & Computer Sci., University of Hawaii

Jan Stelovsky
based on slides by Dr. Baek and Dr. Still
Originals by Dr. M. P. Frank and Dr. J.L. Gross
Provided by McGraw-Hill

ICS 141: Discrete Mathematics I – Fall 2011 7-1

 University of Hawaii

Lecture 7
Chapter 1. The Foundations
1.6 Introduction to Proofs
Chapter 2. Basic Structures
2.1 Sets

ICS 141: Discrete Mathematics I – Fall 2011 7-2

 Proof Terminology
University of Hawaii

n  A proof is a valid argument that establishes

the truth of a mathematical statement
n  Axiom (or postulate): a statement that is
assumed to be true
n  Theorem
n  A statement that has been proven to be true
n  Hypothesis, premise
n  An assumption (often unproven) defining the
structures about which we are reasoning

ICS 141: Discrete Mathematics I – Fall 2011 7-3

 More Proof Terminology
University of Hawaii

n  Lemma
n  A minor theorem used as a stepping-stone

to proving a major theorem.

n  Corollary
n  A minor theorem proved as an easy

consequence of a major theorem.

n  Conjecture
n  A statement whose truth value has not

been proven. (A conjecture may be widely

believed to be true, regardless.)
ICS 141: Discrete Mathematics I – Fall 2011 7-4
 Proof Methods
University of Hawaii

n  For proving a statement p alone

n  Proof by Contradiction (indirect proof):
Assume ¬p, and prove ¬p → F.

ICS 141: Discrete Mathematics I – Fall 2011 7-5

 Proof Methods
University of Hawaii

n  For proving implications p → q, we have:

n  Trivial proof: Prove q by itself.
n  Direct proof: Assume p is true, and prove q.
n  Indirect proof:
n  Proof by Contraposition (¬q → ¬p):
Assume ¬q, and prove ¬p.
n  Proof by Contradiction:
Assume p ∧ ¬q, and show this leads to a
contradiction. (i.e. prove (p ∧ ¬q) → F)
n  Vacuous proof: Prove ¬p by itself.

ICS 141: Discrete Mathematics I – Fall 2011 7-6

 Direct Proof Example
University of Hawaii

n  Definition: An integer n is called odd iff n=2k+1

for some integer k; n is even iff n=2k for some k.
n  Theorem: Every integer is either odd or even, but
not both.
n  This can be proven from even simpler axioms.
n  Theorem:
(For all integers n) If n is odd, then n2 is odd.
Proof:
If n is odd, then n = 2k + 1 for some integer k.
Thus, n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1.
Therefore n2 is of the form 2j + 1 (with j the integer
2k2 + 2k), thus n2 is odd. ■
ICS 141: Discrete Mathematics I – Fall 2011 7-7
 Indirect Proof Example: University of Hawaii

Proof by Contraposition
n  Theorem: (For all integers n)
If 3n + 2 is odd, then n is odd.
n  Proof:
(Contrapositive: If n is even, then 3n + 2 is even)
Suppose that the conclusion is false, i.e., that n is even.
Then n = 2k for some integer k.
Then 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).
Thus 3n + 2 is even, because it equals 2j for an integer
j = 3k + 1. So 3n + 2 is not odd.
We have shown that ¬(n is odd) → ¬(3n + 2 is odd),
thus its contrapositive (3n + 2 is odd) → (n is odd) is
also true. ■
ICS 141: Discrete Mathematics I – Fall 2011 7-8
 Vacuous Proof Example
University of Hawaii

n  Show ¬p (i.e. p is false) to prove p → q is true.

n  Theorem: (For all n) If n is both odd and even,

then n2 = n + n.
n  Proof:
The statement “n is both odd and even” is
necessarily false, since no number can be
both odd and even. So, the theorem is
vacuously true. ■

ICS 141: Discrete Mathematics I – Fall 2011 7-9

 Trivial Proof Example
University of Hawaii

n  Show q (i.e. q is true) to prove p → q is true.

n  Theorem: (For integers n) If n is the sum of

two prime numbers, then either n is odd or n
is even.
n  Proof:
Any integer n is either odd or even. So the
conclusion of the implication is true
regardless of the truth of the hypothesis.
Thus the implication is true trivially. ■

ICS 141: Discrete Mathematics I – Fall 2011 7-10

 Proof by Contradiction
University of Hawaii

n  A method for proving p.

n  Assume ¬p, and prove both q and ¬q for
some proposition q. (Can be anything!)
n  Thus ¬p → (q ∧ ¬q)
n  (q ∧ ¬q) is a trivial contradiction, equal to F
n  Thus ¬p → F, which is only true if ¬p = F
n  Thus p is true

ICS 141: Discrete Mathematics I – Fall 2011 7-11

 Rational Number
University of Hawaii

n  Definition:
The real number r is rational if there exist
integers p and q with q ≠ 0 such that r = p/q.
A real number that is not rational is called
irrational.

ICS 141: Discrete Mathematics I – Fall 2011 7-12

 Proof by Contradiction
Example
University of Hawaii

n  Theorem: 2 is irrational.

n  Proof:
n  Assume that 2 is rational. This means there are
integers x and y (y ≠ 0) with no common divisors
such that 2 = x/y.
Squaring both sides, 2 = x2/y2, so 2y2 = x2. So x2 is
even; thus x is even (see earlier).
Let x = 2k. So 2y2 = (2k)2 = 4k2. Dividing both sides
by 2, y2 = 2k2. Thus y2 is even, so y is even.
But then x and y have a common divisor, namely 2,
so we have a contradiction.
Therefore, 2 is irrational. ■
ICS 141: Discrete Mathematics I – Fall 2011 7-13
 Proof by Contradiction
University of Hawaii

n  Proving implication p → q by contradiction

n  Assume ¬q, and use the premise p to

arrive at a contradiction, i.e. (¬q ∧ p) → F

(p → q ≡ (¬q ∧ p) → F)
n  How does this relate to the proof by
contraposition?
n  Proof by Contraposition (¬q → ¬p):
Assume ¬q, and prove ¬p.

ICS 141: Discrete Mathematics I – Fall 2011 7-14

 Proof by Contradiction
Example: Implication
University of Hawaii

n  Theorem: (For all integers n)

If 3n + 2 is odd, then n is odd.
n  Proof:
Assume that the conclusion is false, i.e., that n is even,
and that 3n + 2 is odd.
Then n = 2k for some integer k and 3n + 2 = 3(2k) + 2 =
6k + 2 = 2(3k + 1). Thus 3n + 2 is even, because it
equals 2j for an integer j = 3k + 1.
This contradicts the assumption “3n + 2 is odd”.
This completes the proof by contradiction,
proving that if 3n + 2 is odd, then n is odd. ■

ICS 141: Discrete Mathematics I – Fall 2011 7-15

 Circular Reasoning
University of Hawaii

n  The fallacy of (explicitly or implicitly) assuming

the very statement you are trying to prove in the
course of its proof. Example:
n  Prove that an integer n is even, if n2 is even.
n  Attempted proof:
Assume n2 is even. Then n2 = 2k for some integer k.
Dividing both sides by n gives n = (2k)/n = 2(k/n).
So there is an integer j (namely k/n) such that n = 2j.
Therefore n is even.
n  Circular reasoning is used in this proof.
Where? Begs the question: How do
you show that j = k/n = n/2 is an integer,
ICS 141: Discrete Mathematics I – Fall 2011 without first assuming that n is even?7-16
 University of Hawaii

Chapter 2
Basic Structures:
Sets, Functions, Sequences, and Sums

ICS 141: Discrete Mathematics I – Fall 2011 7-17

 2.1 Sets
University of Hawaii

n  A set is a new type of structure, representing

an unordered collection (group) of zero or
more distinct (different) objects. The objects
are called elements or members of the set.
n  Notation: x ∈ S
n  Set theory deals with operations between,
relations among, and statements about sets.
n  Sets are ubiquitous in computer software
systems.
n  (E.g. data types Set, HashSet in java.util)
ICS 141: Discrete Mathematics I – Fall 2011 7-18
 Basic Notations for Sets
University of Hawaii

n  For sets, we’ll use variables S, T, U,…

n  We can denote a set S in writing by listing all of
its elements in curly braces:
n  {a,b,c} is the set whose elements are a, b, and c
n  Set builder notation:
n  For any statement P(x) over any domain,
{x | P(x)} is the set of all x such that P(x) is true
n  Example: {1, 2, 3, 4}
= {x | x is an integer where x > 0 and x < 5 }
= {x∈Z | x > 0 and x < 5 }
ICS 141: Discrete Mathematics I – Fall 2011 7-19
 Basic Properties of Sets
University of Hawaii

n  Sets are inherently unordered:

n  No matter what objects a, b, and c denote,

{a, b, c} = {a, c, b} = {b, a, c} =

{b, c, a} = {c, a, b} = {c, b, a}.
n  All elements are distinct (unequal);
multiple listings make no difference!
n  If a = b, then {a, b, c} = {a, c} = {b, c} =

{a, a, b, a, b, c, c, c, c}.
n  This set contains (at most) 2 elements!

ICS 141: Discrete Mathematics I – Fall 2011 7-20

 Definition of Set Equality
University of Hawaii

n  Two sets are declared to be equal if and only

if they contain exactly the same elements.
n  In particular, it does not matter how the set is
defined or denoted.
n  Example:
The set {1, 2, 3, 4}
= {x | x is an integer where x > 0 and x < 5}
= {x | x is a positive integer where x2 < 20}

ICS 141: Discrete Mathematics I – Fall 2011 7-21

 Infinite Sets
University of Hawaii

n  Conceptually, sets may be infinite

(i.e., not finite, without end, unending).
n  Symbols for some special infinite sets:
N = {0, 1, 2,…} the set of Natural numbers.
Z = {…, –2, –1, 0, 1, 2,…} the set of Zntegers.
Z+ = {1, 2, 3,…} the set of positive integers.
Q = {p/q | p,q ∈ Z, and q ≠ 0}
the set of Rational numbers.
R = the set of “Real” numbers.
n  “Blackboard Bold” or double-struck font is also
often used for these special number sets.
ICS 141: Discrete Mathematics I – Fall 2011 7-22