Discrete Mathematics

離散數學
Lecture 01
September 13, 2006
洪國寶
 Outline
• Course information
• Overview of Discrete Mathematics
• Logic (chapter 1 (§1.1))
1.1)

2006/9/14 2
 Course information (1/3)
• Textbook
Discrete Mathematics and its Applications,
5th Edition, Kenneth H. Rosen, McGraw-
Hill, Inc., New York, 2003

http://www.mhhe.com/math/advmath/rosen/r5/

歐亞書局
2006/9/14 3
 Course information (2/3)
• Grading (Tentative)
Quizzes 30%
Midterm exam 30%
Final exam 30%
Class participation 10%

2006/9/14 4
 Course information (3/3)
• The problems of the quizzes and exams are
all from examples and exercises of the
textbook.

2006/9/14 5
 Outline
• Course information
• Overview of Discrete Mathematics
• Logic (chapter 1 (§1.1))
1.1)

2006/9/14 6
Overview of Discrete Mathematics

• What is Discrete Mathematics?

• What is Mathematics, really?
– It’s not just about numbers!
– Mathematics is much more than that:
Mathematics is the study of any and all
absolutely certain truths about any and all
perfectly well-defined concepts.
Overview of Discrete Mathematics

Mathematics is the study of any and all

absolutely certain truths about any and all
perfectly well-defined concepts.
• But, the concepts can relate to numbers,
symbols, visual patterns, or anything!
Overview of Discrete Mathematics

• What is Discrete Mathematics?

– The study of discrete, mathematical objects
and structures.
Overview of Discrete Mathematics

• What are “discrete structures” anyway?

– “Discrete” - Composed of distinct, separable
parts. (Opposite of continuous.)
discrete:continuous :: digital:analog
– “Structures” - objects built up from simpler
objects according to a definite pattern.
 Discrete Structures We’ll Study

• Propositions • Proofs
• Predicates • Summations
• Sets • Permutations
• (Discrete) Functions • Combinations
• Orders of Growth • Relations
• Algorithms • Graphs
• Integers • Trees
 Relationships Between Structures

• “→” :≡ “Can be defined in terms of”

Groups Programs Proofs
Operators Trees
Complex numbers Propositions
Graphs
Real numbers Strings
Integers Functions
Natural Matrices
numbers Relations
Sequences
Infinite Bits n-tuples Vectors
ordinals
Sets
2006/9/14 12
 Some Notations We’ll Learn

¬p p∧q p⊕q p→q p⇔q ∀x P ( x)

∃x P( x) {a1 , L , an } Z , N , R ∴ {x | P( x)} x∉S
n
∅ S ⊆T |S| A∪ B A IA i
i =1
n
f :A→ B f −1 ( x) f og x  ∑
α
aα
∈S
∏a
i =1
i

O, Ω, Θ min, max a /| b gcd, lcm mod a ≡ b (mod m)

n
( a k L a0 ) b [aij ] AT ⋅B
AΟ A[ n ]  
r
C (n; n1 ,L , nm ) p( E | F ) R∗ ∆ [a ]R deg + (v)
 Why Study Discrete Math?

• The basis of all of digital information

processing: Discrete manipulations of
discrete structures represented in memory.
• It’s the basic language and conceptual
foundation of all of computer science.
• Discrete concepts are also widely used
throughout math, science, engineering,
economics, biology, etc., …
• A generally useful tool for rational thought!
 Uses for Discrete Math in
Computer Science
• Algorithms & data • Database management
structures systems
• Programming • Computer security
language compilers & • Error correction codes
interpreters. • Graphics & animation
• Computer networks algorithms, game
• Operating systems engines
• Computer architecture • Just about everything!
 Goals of a Discrete Math Course

• Teach students how to think mathematically

• Five important themes
- mathematical reasoning
- combinatorial analysis
- discrete structures
- algorithmic thinking
- applications and modeling
 Five Important Themes
- mathematical reasoning
to read, comprehend, and construct mathematical arguments

- combinatorial analysis
the ability to count or enumerate objects

- discrete structures
to work with discrete structures, which are the abstract mathematical
structures used to represent discrete objects and relationships between these
objects

- algorithmic thinking
the specification of the algorithm, the verification that it works properly, and
the analysis of the computer memory and time required to perform it

- applications and modeling

 Course Objectives
• Upon completion of this course, the student
should be able to:
– Check the validity of simple logical arguments.
– Creatively construct simple valid logical arguments.
– Describe the definitions and properties of a variety of
specific types discrete structures.
– Correctly read, write and analyze various types of
structures using standard notations.
 Course Outline (1/11)
• 1 The Foundations: Logic, Sets, and
Functions
– 1.1 Logic
– 1.2 Propositional Equivalences
– 1.3 Predicates and Quantifiers
– 1.4 Nested Quantifiers
– 1.5 Methods of proof
– 1.6 Sets
– 1.7 Set Operations
– 1.8 Functions

2006/9/14 19
 Course Outline (2/11)
• 2 The Fundamentals: Algorithms,
the Integers, and Matrices
– 2.1 Algorithms
– 2.2 The Growth of Functions
– 2.3 Complexity of Algorithms
– 2.4 The Integers and Division
– 2.5 Integers and Algorithms
– 2.6 Applications of Number Theory
– 2.7 Matrices

2006/9/14 20
 Course Outline (3/11)
• 3 Mathematical Reasoning,
Induction, and Recursion
– 3.1 Art and Strategy of Proof
– 3.2 Sequences and Sums
– 3.3 Mathematical Induction
– 3.4 Recursive Definitions and
Structural Definition
– 3.5 Recursive Algorithms
– 3.6 Program Correctness

2006/9/14 21
 Course Outline (4/11)
• 4 Counting
– 4.1 The Basics of Counting
– 4.2 The Pigeonhole Principle
– 4.3 Permutations and Combinations
– 4.4 Binomial Coefficients
– 4.5 Generalized Permutations and
Combinations
– 4.6 Generating Permutations and
Combinations

2006/9/14 22
 Course Outline (5/11)

• 5 Discrete Probability
– 5.1 An Introduction to Discrete
Probability
– 5.2 Probability Theory
– 5.3 Expected Value and
Variance

2006/9/14 23
 Course Outline (6/11)
• 6 Advanced Counting Techniques
– 6.1 Recurrence Relations
– 6.2 Solving Recurrence Relations
– 6.3 Divide-and-Conquer Relations
– 6.4 Generating Functions
– 6.5 Inclusion-Exclusion
– 6.6 Applications of Inclusion-Exclusion

2006/9/14 24
 Course Outline (7/11)
• 7 Relations
– 7.1 Relations and Their Properties
– 7.2 n-ary Relations and Their
Applications
– 7.3 Representing Relations
– 7.4 Closures of Relations
– 7.5 Equivalence Relations
– 7.6 Partial Orderings

2006/9/14 25
 Course Outline (8/11)
• 8 Graphs
– 8.1 Introduction to Graphs
– 8.2 Graph Terminology
– 8.3 Representing Graphs and Graph
Isomorphism
– 8.4 Connectivity
– 8.5 Euler and Hamilton Paths
– 8.6 Shortest Path Problems
– 8.7 Planar Graphs
– 8.8 Graph Coloring

2006/9/14 26
 Course Outline (9/11)
• 9 Trees
– 9.1 Introduction to Trees
– 9.2 Applications of Trees
– 9.3 Tree Traversal
– 9.4 Spanning Trees
– 9.5 Minimum Spanning Trees

2006/9/14 27
 Course Outline (10/11)
• 10 Boolean Algebra
– 10.1 Boolean Functions
– 10.2 Representing Boolean Functions
– 10.3 Logic Gates
– 10.4 Minimization of Circuits

2006/9/14 28
 Course Outline (11/11)
• 11 Modeling Computation
– 11.1 Languages and Grammars
– 11.2 Finite-State Machines with Output
– 11.3 Finite-State Machines with No Output
– 11.4 Language Recognition
– 11.5 Turing Machines

2006/9/14 29
 Some Advice
• Take note
• Read in advance
• Do exercises
• Take advantages of the web resources
– http://www.mhhe.com/math/advmath/rosen/r5/
– MIT 6.042 Mathematics for Computer Science
http://theory.lcs.mit.edu/classes/6.042/fall06/

2006/9/14 30
2006/9/14 31
 Outline
• Course information
• Overview of Discrete Mathematics
• Logic (chapter 1 (§1.1))
1.1)

2006/9/14 32
 Logic (1/2)
Mathematical Logic is a tool for working with
complicated compound statements. It includes:
• A language for expressing them.
• A concise notation for writing them.
• A methodology for reasoning about their truth or
falsity.
• It is the foundation for expressing formal proofs
in all branches of mathematics.

2006/9/14 33
 Logic (2/2)
• Propositional logic (§1.1-1.2):
– Basic definitions. (§1.1)
– Equivalence rules & derivations. (§1.2)
• Predicate logic (§1.3-1.4)
– Predicates.
– Quantified predicate expressions.
– Equivalences & derivations.

2006/9/14 34
 Topic #1 – Propositional Logic

Propositional Logic (§1.1)

Propositional Logic is the logic of compound
statements built from simpler statements
using so-called Boolean connectives.
Some applications in computer science:
• Design of digital electronic circuits.
• Expressing conditions in programs.
• Queries to databases & search engines.

2006/9/14 35
 Topic #1 – Propositional Logic

Definition of a Proposition
A proposition (p, q, r, …) is simply a
statement (i.e., a declarative sentence) with
a definite meaning, having a truth value
that’s either true (T) or false (F), but not
both.
(However, you might not know the actual
truth value, and it might be situation-
dependent.)

2006/9/14 36
 Topic #1 – Propositional Logic

Examples of Propositions
• “It is raining.” (In a given situation.)
• “Toronto is the capital of Canada.”
• “2 + 2 = 3”
But, the following are NOT propositions:
• “What time is it?” (interrogative, question)
• “La la la la la.” (meaningless interjection)
• “Just do it!” (imperative, command)
• “x+1=2” (neither true nor false)
• “1 + 2” (expression with a non-true/false value)

2006/9/14 37
 Topic #1.0 – Propositional Logic: Operators

Operators / Connectives
An operator or connective combines one or
more operand expressions into a larger
expression. (E.g., “+” in numeric exprs.)
Unary operators take 1 operand (e.g., −3);
binary operators take 2 operands (eg 3 × 4).
Propositional or Boolean operators operate
on propositions or truth values instead of on
numbers.
2006/9/14 38
 Some Popular Boolean Operators

Formal Name Nickname Arity Symbol

Negation operator NOT Unary ¬
Conjunction operator AND Binary ∧
Disjunction operator OR Binary ∨
Exclusive-OR operator XOR Binary ⊕
Implication operator IMPLIES Binary →
Biconditional operator IFF Binary ↔

2006/9/14 39
 Topic #1.0 – Propositional Logic: Operators

The Negation Operator

The unary negation operator “¬” (NOT)
transforms a prop. into its logical negation.
E.g. If p = “Today is Friday.”
then ¬p = “Today is not Friday.”
Truth table for NOT: p ¬p
T :≡ True; F :≡ False T F
“:≡” means “is defined as” F T
Operand Result
column column
2006/9/14 40
 Topic #1.0 – Propositional Logic: Operators

The Conjunction Operator

• The binary conjunction operator “∧”
(AND) combines two propositions to form
their logical conjunction. ∧ND
• Example 4. If p=“Today is Friday.” and
q=“It is raining today.”, then p∧q=“Today
is Friday and it is raining today.”
Remember: “∧” points up like an “A”, and it means “∧ND”

2006/9/14 41
 Topic #1.0 – Propositional Logic: Operators

Conjunction Truth Table

Operand columns
• Note that a p q p∧q
conjunction
p1 ∧ p2 ∧ … ∧ pn F F F
of n propositions F T F
will have 2n rows T F F
in its truth table. T T T
• Also: ¬ and ∧ operations together are sufficient to express
any Boolean truth table! (They are functionally complete.)

2006/9/14 42
 Topic #1.0 – Propositional Logic: Operators

The Disjunction Operator

• The binary disjunction operator “∨” (OR)
combines two propositions to form their
logical disjunction.
• Example 5.
p=“Today is Friday.”
q=“It is raining today.”
p∨q=“Today is Friday or it is raining today.”
Meaning is like “and/or” in English.
2006/9/14 43
 Topic #1.0 – Propositional Logic: Operators

Disjunction Truth Table

• Note that p∨q means p q p∨q
that p is true, or q is
true, or both are true!
F F F
Note
F T T difference
• So, this operation is
T F T from AND
also called inclusive or,
because it includes the
T T T
possibility that both p and q are true.
• “¬” and “∨” together are also universal.
2006/9/14 44
 Topic #1.0 – Propositional Logic: Operators

The Exclusive Or Operator

The binary exclusive-or operator “⊕” (XOR)
combines two propositions to form their
logical “exclusive or”.
p = “I will earn an A in this course,”
q = “I will drop this course,”
p ⊕ q = “I will either earn an A for this
course, or I will drop it (but not both!)”

2006/9/14 45
 Topic #1.0 – Propositional Logic: Operators

Exclusive-Or Truth Table

• Note that p⊕q means p q p⊕q
that p is true, or q is
true, but not both!
F F F
F T T
• This operation is
T F T
called exclusive or,
because it excludes the
T T F Note
difference
from OR.
possibility that both p and q are true.
• “¬” and “⊕” together are not universal.
2006/9/14 46
 Topic #1.0 – Propositional Logic: Operators

The Implication Operator

hypothesis conclusion
The implication p → q states that p implies q.
I.e., If p is true, then q is true; but if p is not
true, then q could be either true or false.
E.g., let p = “You study hard.”
q = “You will get a good grade.”
p → q = “If you study hard, then you will get
a good grade.” (else, it could go either way)

2006/9/14 47
 Topic #1.0 – Propositional Logic: Operators

Implication Truth Table

• p → q is false only when p q p→q
p is true but q is not true. F F T
• p → q does not say F T T The
that p causes q! T F F only
False
• p → q does not require T T T case!
that p or q are ever true!
• E.g. “(1=0) → pigs can fly” is TRUE!

2006/9/14 48
 Topic #1.0 – Propositional Logic: Operators

English Phrases Meaning p → q

• “p implies q” • “p only if q”
• “if p, then q” • “p is sufficient for q”
• “if p, q” • “q is necessary for p”
• “when p, q” • “q follows from p”
• “whenever p, q” • “q is implied by p”
• “q if p” We will see some equivalent
logic expressions later.
• “q when p”
• “q whenever p”
2006/9/14 49
 Topic #1.0 – Propositional Logic: Operators

Converse, Inverse, Contrapositive

Some terminology, for an implication p → q:

• Its converse is: q → p.
• Its inverse is: ¬p → ¬q.
• Its contrapositive: ¬q → ¬ p.
• One of these three has the same meaning
(same truth table) as p → q. Can you figure
out which?

2006/9/14 50
 Topic #1.0 – Propositional Logic: Operators

The biconditional operator

• The biconditional p ↔ q states that p is true if and
only if (IFF) q is true.
• Example 8. (p. 9)
p = “You can take the flight.”
q = “You buy a ticket.”
p ↔ q = “You can take the flight if and only if
you buy a ticket.”

2006/9/14 51
 Topic #1.0 – Propositional Logic: Operators

Biconditional Truth Table

• p ↔ q means that p and q p q p ↔q
have the same truth value.
F F T
• Note this truth table is the
exact opposite of ⊕’s!
F T F
– p ↔ q means ¬(p ⊕ q) T F F
• p ↔ q does not imply T T T
p and q are true, or cause each other.

2006/9/14 52
 Topic #1.0 – Propositional Logic: Operators

Nested Propositional Expressions

• Use parentheses to group sub-expressions:
“I just saw my old friend, and either he’s
grown or I’ve shrunk.” = f ∧ (g ∨ s)
– (f ∧ g) ∨ s would mean something different
– f ∧ g ∨ s would be ambiguous
• By convention, “¬” takes precedence over
both “∧” and “∨”.
– ¬s ∧ f means (¬s) ∧ f , not ¬ (s ∧ f)
2006/9/14 53
 Precedence of Logical Operators
Operator Precedence
¬ 1
∧ 2
∨ 3
→ 4
↔ 5

2006/9/14 54
 Topic #1.0 – Propositional Logic: Operators

Boolean Operations Summary

• We have seen 1 unary operator (out of the 4
possible) and 5 binary operators (out of the
16 possible). Their truth tables are below.
p q ¬p p∧q p∨q p⊕q p→q p↔q
F F T F F F T T
F T T F T T T F
T F F F T T F F
T T F T T F T T
2006/9/14 55
 Topic #1.0 – Propositional Logic: Operators

Some Alternative Notations

Name: not and or xor implies iff

Propositional logic: ¬ ∧ ∨ ⊕ → ↔
Boolean algebra: p pq + ⊕
C/C++/Java (wordwise): ! && || != ==
C/C++/Java (bitwise): ~ & | ^
Logic gates:

2006/9/14 56
 Translating English Sentences
• Example 9.

2006/9/14 57
 System Specifications
• Propositional expressions are consistent if
there is an assignment of truth values to the
variables in the expressions that makes all
the expressions true.
• Example 12.

2006/9/14 58
 Logic puzzles
• Puzzles that can be solved using logical
reasoning are known as logic puzzles.
• Example 15.

2006/9/14 59
 Topic #2 – Bits

Bits and Bit Operations

• Why propositional logic can be applied in
the design of digital circuit?

2006/9/14 60
 Topic #2 – Bits

Bits and Bit Operations

• A bit is a binary (base 2) digit: 0 or 1.
• Bits may be used to represent truth values.
• By convention:
0 represents “false”; 1 represents “true”.
• Boolean algebra is like ordinary algebra
except that variables stand for bits, + means
“or”, and multiplication means “and”.
– See chapter 10 for more details.

2006/9/14 61
 Topic #2 – Bits

Bit Strings
• A Bit string is a sequence of zero or more bits.
The length of this string is the number of bits in
the string.
– More on sequences in §3.2.
• By convention, bit strings are written left to right:
e.g. the first bit of “1001101010” is 1.
• When a bit string represents a base-2 number, by
convention the first bit is the most significant bit.
Ex. 11012=8+4+1=13.

2006/9/14 62
 Topic #2 – Bits

Bitwise Operations
• Boolean operations can be extended to
operate on bit strings as well as single bits.
• E.g.:
01 1011 0110
11 0001 1101
11 1011 1111 Bit-wise OR
01 0001 0100 Bit-wise AND
10 1010 1011 Bit-wise XOR
2006/9/14 63
 End of §1.1
You have learned about: • Atomic vs. compound
• Propositions: What propositions.
they are. • Alternative notations.
• Propositional logic • Bits and bit-strings.
operators’ • Next section: §1.2
– Symbolic notations. – Propositional
– English equivalents. equivalences.
– Logical meaning. – How to prove them.
– Truth tables.

2006/9/14 64