Course description
Some applications
Discrete mathematics I
Introduction
Huynh Tuong Nguyen
Faculty of Computer Science and Engineering
Ho Chi Minh City University of Technology

February 22, 2012
Discrete Math 1 N. Huynh Tuong Introduction 1/18
Course description
Some applications
1
Course description
Course outline
Document
2
Some applications
Discrete Math 1 N. Huynh Tuong Introduction 2/18
Course description
Some applications
Course outline
Document
Context
Global
4 principal chapters on 42 hours for courses & exercises.
5 Labs (10%), 1 Assignment (10%)
2 evaluations: mid-exam (MCQ + 60 minutes - 30%) + final
exam (writing - 120 minutes - 50%)
Aims
The content of this subject is mainly a great part of logic, set

theory and graph theory.
This is the mathematical base for many topics of Computational
Science
Discrete Math 1 N. Huynh Tuong Introduction 3/18
Course description
Some applications
Course outline
Document
Subjects in general discrete mathematics course
☞ Logic
☞ Set theory
☞ Number theory
☞ Combinatorics: enumerative combinatorics,
graph theory
☞ Algorithmics
☞ Information theory
☞ Complexity theory
☞ Probability theory
☞ Proof
☞ Counting and Relations
Discrete Math 1 N. Huynh Tuong Introduction 4/18
Course description
Some applications
Course outline
Document
Topics relational to discrete mathematics
1
Theoretical computer science
2
Information theory

3
Logic
4
Set theory
5
Combinatorics
6
Graph theory
7
Probability
8
Number theory
9
Algebra
10
Calculus of finite differences, discrete calculus or discrete analysis
11
Geometry
12
Topology
13
Oper at ions research: scheduling
14
Game theory, decision theory, utility theory, social choice theory
15
Discretization
16
Discrete analogues of continuous mathematics
17
. . .

Discrete Math 1 N. Huynh Tuong Introduction 5/18
Course description
Some applications
Course outline
Document
Context
Course outline
Proof methods
modular arithmetic over int egers .
induction, contradiction.
Set theory
relations, functions, cardinalities, relation, equivalence equation, partial
order
combinatorics: counting, principles of sum, multiplication, division,
inclusion and exclusion.
Graph theory
directed, undirected, isomorphism
Weighted graphs, algorithm for finding shortest paths
Trees: features, binary trees, minimu m spanning trees in conn ect ed and
weighted graphs
Probabilistics Modelling
introd u ct ory random variables.
Discrete Math 1 N. Huynh Tuong Introduction 6/18
Course description
Some applications
Course outline
Document
Document
Book
Discrete mathematics and applications - K e n n et h H. Rosen. (Vietna mese

translation - NXB KHKT 1997)
Discrete mathematics - Richard Johnsonbaugh, Willey, 1997
Discrete mathematics with algorithms - Micheal O. Albertson & Joan P.
Hutchinson, Willey, 1998
Discrete Math 1 N. Huynh Tuong Introduction 7/18
Course description
Some applications
Application
it concerns a wide range of disciplines in various areas: science, t ech nology,
business and commerce.
applied mathematicians are engaged in the creation, st u d y and application of
advanced mathematical methods relevant to specific problems.
applied mathematics has assumed a much broader meaning and embraces such
diverse fields as communication theory, optimization, game theory and
numerical analysis.
today there is a remarkable variety of applications of mathematics in industry
and government, such as materials processing, design, medical diagnosis,
development of financial products, network management, weather prediction,
etc.
Discrete Math 1 N. Huynh Tuong Introduction 8/18
Course description
Some applications
Application
it concerns a wide range of disciplines in various areas: science, t ech nology,
business and commerce.
applied mathematicians are engaged in the creation, st u d y and application of
advanced mathematical methods relevant to specific problems.
applied mathematics has assumed a much broader meaning and embraces such
diverse fields as communication theory, optimization, game theory and
numerical analysis.

today there is a remarkable variety of applications of mathematics in industry
and government, such as materials processing, design, medical diagnosis,
development of financial products, network management, weather prediction,
etc.
Engineers use technology, mathematics
and scientific knowledge to solve
practical problems. (wikipedia.org)
Science
Technology
Engineering
Discrete Math 1 N. Huynh Tuong Introduction 8/18
Course description
Some applications
Computing of algorithm complexity
Know results
Size Approximating of computational time
n O( log n) O( n) O( n log n) O( n
2
) O( 2
n
) O( n!)
10 3.10
−9
s 10
−8
s 3.10
−8
s 10
−7
s 10

−6
s 3.10
−3
s
10
2
7.10
−9
s 10
−7
s 7.10
−7
s 10
−5
s 4.10
13
y *
10
3
10
−8
s 10
−6
s 10
−5
s 10
−3
s * *
10
4

1, 3.10
−8
s 10
−5
s 10
−4
s 10
−1
s * *
10
5
1, 7.10
−8
s 10
−4
s 2.10
−3
s 10s * *
10
6
2.10
−8
s 10
−3
s 2.10
−2
s 17m * *
Discrete Math 1 N. Huynh Tuong Introduction 9/18
Course description
Some applications

Mathematical model
Solver
Simplex, GLPK
CPLEX, MPL
Excel, Mathlab, et c.
Discrete Math 1 N. Huynh Tuong Introduction 10/18
Course description
Some applications
Mathematical model
Solver
Simplex, GLPK
CPLEX, MPL
Excel, Mathlab, et c.
Discrete Math 1 N. Huynh Tuong Introduction 10/18
Course description
Some applications
Mathematical model
Exercise
A bookseller A buys books from two publishers B , and C.
Publisher B offers a package of 5 mysteries and 5 romance novels
for $50, and publisher C offers a package of 5 mysteries and 10
romance novels for $150. The bookseller A wants to buy at least
2,500 mysteries and 3,500 romance novels, and he has promised C
(who has influence on the Senate Textbook Committee) that at
least 25% of the total number of books he purchases will come
from publisher C.
Question. How many packages should A order from each publisher
in order to minimize his cost and satisfy C ? What will the novels
cost him?
Discrete Math 1 N. Huynh Tuong Introduction 11/18

Course description
Some applications
Mathematical model
Solution
Let x be the number of packages from Publisher B, and let y be
the number of packages from C.
Problem: Minimize
C = 50x + 150y subject to
5x + 5y ≥ 2.500
5x + 10y ≥ 3.500
x − 4.5y ≤ 0
x ≥ 0, y ≥ 0
Answer: Buy 484 packages from Publisher B and 108 from C for a
total cost of $40.400.
Discrete Math 1 N. Huynh Tuong Introduction 12/18
Course description
Some applications
Graph
Shortest path pr ob le m
Min cut and maximum flow
Vehicle Routing Problem
Discrete Math 1 N. Huynh Tuong Introduction 13/18
Course description
Some applications
Graph
Shortest path pr ob le m
Min cut and maximum flow
Vehicle Routing Problem
Discrete Math 1 N. Huynh Tuong Introduction 13/18
Course description

Some applications
Scheduling
Discrete Math 1 N. Huynh Tuong Introduction 14/18
Course description
Some applications
Scheduling
Exercise
Problem 1||T
max
.
Given 8 jobs with processing times and due dates as follows:
Job J
1
J
2
J
3
J
4
J
5
J
6
J
7
J
8
p
i
1 2 2 3 3 4 4 3

d
i
25 16 19 7 18 22 27 8
Let C
i
be comple tio n time of job J
i
and let T
i
= max(0, C
i
− d
i
) its tardiness.
Question. How to minimize T
max
= max
i
T
i
? What is the minimum value of
T
max
?
Discrete Math 1 N. Huynh Tuong Introduction 15/18
Course description
Some applications
Timetabling
Example
In the bipartite graph below, the vertices P

1
, . . . , P
6
represent workers and
edges J
1
, . . . , J
6
of jobs. A n edge connects a worker with a job if the worker
has the necess ary qualifications to occupy this job. Here, all the e d ge s have an
unit weight 1 , mean that P
i
has the skill(competence) to operate J
j
if there is
an edge between P
i
and J
j
.
Discrete Math 1 N. Huynh Tuong Introduction 16/18
Course description
Some applications
Timetabling
Example
In the bipartite graph below, the vertices P
1
, . . . , P
6
represent workers and

edges J
1
, . . . , J
6
of jobs. A n edge connects a worker with a job if the worker
has the necess ary qualifications to occupy this job. Here, all the e d ge s have an
unit weight 1 , mean that P
i
has the skill(competence) to operate J
j
if there is
an edge between P
i
and J
j
.
P
1
P
2
P
3
P
4
P
5
P
6
J
1

J
2
J
3
J
4
J
5
J
6
Discrete Math 1 N. Huynh Tuong Introduction 16/18
Course description
Some applications
Game and simulation
Sally Salon Game
Discrete Math 1 N. Huynh Tuong Introduction 17/18
Course description
Some applications
Probabilistics Modelling
Calculating of Pi
Using a Monte-Carlo method to determine an approximate value of
π :
randomly draw a great number of points in a square of side 2, and
determine the ratio C /N where N is the total number of points,
and C the numb e r of points whose distance to the center of the
square is ≤ 1).
Discrete Math 1 N. Huynh Tuong Introduction 18/18
Logics
Tran Vinh Tan
Contents

Propositional Logic
1.1
Chapter 1
Logics
Discrete Mathematics I on 13 March 2012
Tran Vinh Tan
Faculty of Computer Science and Engineering
University of Technology - VNUHCM
Logics
Tran Vinh Tan
Contents
Propositional Logic
1.2
Contents
1 Propositional Logic
Logics
Tran Vinh Tan
Contents
Propositional Logic
1.3
Logic
Definition (Averroes)
The tool for distinguishing between the true and the false.
Definition (Penguin Encyclopedia)
The formal systematic study of the principles of valid inference
and correct reasoning.
Definition (Discrete Mathematics - Rosen)
Rules of logic are used to distinguish between valid and invalid
mathematical arguments.