Transcript Discrete Mathematics - Lyle School of Engineering

Discrete Mathematics, Part II
CSE 2353
Fall 2007
Margaret H. Dunham
Department of Computer Science and
Engineering
Southern Methodist University
•Some slides provided by Dr. Eric Gossett; Bethel University; St. Paul,
Minnesota
•Some slides are companion slides for Discrete Mathematical
Structures: Theory and Applications by D.S. Malik and M.K. Sen
Outline









Introduction
Sets
Logic & Boolean Algebra
Proof Techniques
Counting Principles
Combinatorics
Relations,Functions
Graphs/Trees
Boolean Functions, Circuits
2
Proof Technique: Learning
Objectives

Learn various proof techniques

Direct

Indirect

Contradiction

Induction

Practice writing proofs

CS: Why study proof techniques?
3
Proof Techniques

Theorem


Statement that can be shown to be true (under certain
conditions)
Typically Stated in one of three ways

As Facts

As Implications

As Biimplications
4
Validity of Arguments


Proof: an argument or a proof of a theorem
consists of a finite sequence of statements
ending in a conclusion
Argument: a finite sequence A1 , A2 , A3 , ..., An 1 , An
of statements.


The final statement, An , is the conclusion, and
the statements A1 , A2 , A3 , ..., An 1
are the
premises of the argument.
An argument is logically valid if the statement
formula
is a tautology.
, , , ...,

A A A
1
2
3
A
n 1
A
n
5
Proof
A mathematical proof of the statement S is a
sequence of logically valid statements that connect
axioms, definitions, and other already validated
statements into a demonstration of the correctness
of S. The rules of logic and the axioms are agreed
upon ahead of time. At a minimum, the axioms
should be independent and consistent. The amount
of detail presented should be appropriate for the
intended audience.
6
Proof Techniques

Direct Proof or Proof by Direct Method





Proof of those theorems that can be expressed in the form
∀x (P(x) → Q(x)), D is the domain of discourse
Select a particular, but arbitrarily chosen, member a of the
domain D
Show that the statement P(a) → Q(a) is true. (Assume that
P(a) is true
Show that Q(a) is true
By the rule of Choose Method (Universal Generalization),
∀x (P(x) → Q(x)) is true
7
Proof Techniques

Indirect Proof



The implication P → Q is equivalent to the implication
( Q → P)
Therefore, in order to show that P → Q is true, one
can also show that the implication ( Q →  P) is true
To show that ( Q →  P) is true, assume that the
negation of Q is true and prove that the negation of P
is true
8
Proof Techniques

Proof by Contradiction



Assume that the conclusion is not true and then arrive at a
contradiction
Example: Prove that there are infinitely many prime
numbers
Proof:
 Assume there are not infinitely many prime numbers,
therefore they are listable, i.e. p1,p2,…,pn
 Consider the number q = p1p2…pn+1. q is not divisible
by any of the listed primes
 Therefore, q is a prime. However, it was not listed.
 Contradiction! Therefore, there are infinitely many
primes.
9
Proof Techniques

Proof of Biimplications



To prove a theorem of the form ∀x (P(x) ↔ Q(x )), where D is the
domain of the discourse, consider an arbitrary but fixed element
a from D. For this a, prove that the biimplication P(a) ↔ Q(a) is
true
The biimplication P ↔ Q is equivalent to (P → Q) ∧ (Q → P)
Prove that the implications P → Q and Q → P are true
 Assume that P is true and show that Q is true
 Assume that Q is true and show that P is true
10
Proof Techniques

Proof of Equivalent Statements


Consider the theorem that says that statements
P,Q and r are equivalent
Show that P → Q, Q → R and R → P


Assume P and prove Q. Then assume Q and
prove R Finally, assume R and prove P
What other methods are possible?
11
Other Proof Techniques

Vacuous

Trivial

Contrapositive

Counter Example

Divide into Cases

Constructive
12
Proof Basics
You can not prove
by example
13
Proof Strategies with Quantifiers

Existential



Constructive
 some mathematicians only accept constructive proofs
Nonconstructive
 show that denying existence leads to a contradiction
Universal


to prove false:
 one counter-example
to prove true:
 usually harder
 the choose method
14
Proofs in Computer Science


Proof of program correctness
Proofs are used to verify
approaches
15
Mathematical Induction


Assume that when a domino is knocked over,
the next domino is knocked over by it
Show that if the first domino is knocked over,
then all the dominoes will be knocked over
16
Mathematical Induction



Let P(n) denote the statement that then nth
domino is knocked over
Base Step: Show that P(1) is true
Inductive Hypothesis: Assume some P(i) is
true, i.e. the ith domino is knocked over for some
i 1

Inductive Step: Prove that P(i+1) is true, i.e.
P(i )  P(i  1)
17
Outline









Introduction
Sets
Logic & Boolean Algebra
Proof Techniques
Counting Principles
Combinatorics
Relations,Functions
Graphs/Trees
Boolean Functions, Circuits
18
Learning Objectives

Learn the basic counting
principles—multiplication and
addition

Explore the pigeonhole principle

Learn about permutations

Learn about combinations
19
Basic Counting Principles
20
Basic Counting Principles
21
Pigeonhole Principle

The pigeonhole principle is also known as the Dirichlet
drawer principle, or the shoebox principle.
22
Pigeonhole Principle
23
Permutations
24
Permutations
25
Combinations
26
Combinations
27
Generalized Permutations and
Combinations
28