Discrete Mathematics
1
Why Are You Studying this Course
This course will develop your mathematical maturity
Discrete mathematics provides the mathematical
foundations for many computer science courses
• Data Structures
• Algorithm Analysis and Design
• Database Management Systems and Database Theory
• Compiler Construction
• Computer Security
• Digital Logic Design
• Artificial Intelligence
2
Course Information
Syllabus:
• Logic
• Sets
• Relations
• Functions.
• Combinatory: counting, permutations, combinations.
• Recursion
• Probibility
• Mathematical Induction
• Graph theory: Graphs and Trees
3
Course Information
Textbook:
• Discrete Mathematics and its Applications by Kenneth. H.
Rosen, 7th Edition
• Discrete Mathematics with Application” by Susana. 4th
edition, 2010
4
How will you master Discrete Structures
• “I hear and I forget. I see and I remember. I do and
understand” - Chinese proverb
5
Terminology
Discrete - Composed of distinct OR separable/unconnected parts.
(Opposite of continuous.)
Structures - Objects built up from simpler objects according to
some definite pattern.
6
7
Introduction
What is discrete mathematics?
• Part of mathematics devoted to the study of
discrete objects.
• Discrete means consisting of distinct or
unconnected elements.
• As computers are discrete object operating one
jumpy, discontinuous step at a time, Discrete
Math is the right framework for describing
precisely Computer Science concepts.
8
Introduction
What is discrete mathematics?
• In computer science we usually deal with finite,
discrete objects.
• For example, we cannot store a real number
(infinite precision) in a computer but can only
store bits (finite precisions).
Definition
• Discrete Mathematics is a collection of
mathematical topics that examine and use finite
or countably infinite mathematical objects.
9
Problems Solved Using DM
10
Logic – 7
11
Statement – 8a
12
Examples – 8b
13
Truth Values of Propositions –
8c
14
Examples – 9a
15
Statements & Truth Values –
9b
T
T
F
F
16
Example – 10b
17
Understanding Statements –
11c
18
Example – 11b
19
Compound Statement – 12a
20
Symbolic Representation –
13a
21
Logical Connectives – 14a
22
Examples – 14b
23
Translating from English to
Symbols – 15
24
Translating from English to
Symbols – 16a
25
Translating from English to
Symbols – 16
26
27
Translating from English to
Symbols – 17a
28
Translating from English to
Symbols – 17b
29
Negation – 19
30
Truth Table for ~p – 20
31
Conjunction – 21
32
Truth Table for p ^ q – 22
33
Disjunction – 23
34
Truth Table for p q – 15
35
Truth Table
36
Advanced versions of many Internet search engines
allow you to use some form of and, or and not to
refine the search process.
Imagine that you want to find web pages about
careers in mathematics or computer science but not
finance or marketing.
With a search engine that uses quotation marks to
enclose exact phrases and expresses and as AND,
or as OR, and not as NOT, you would write
Careers AND (mathematics OR "computer science")
AND NOT (finance OR marketing).
37
Truth Table for ~p^q - 2
38
Truth Table for ~p^q – 2a
39
Truth Table for ~p^q – 2b
40
Truth Table for ~p^q – 2c
41
~p ^ (q v~ r) – (2 - 3a)
42
~p ^ (q v~ r) – 2 - 3b
43
~p ^ (q v~ r) – 2 - 3c
44
~p ^ (q v~ r) – 2 - 3d
45
v
Truth Table for ~p (p v~ q) – 2 - 3e
46
47
Truth Table for (pvq) ^~ (p^q) – 2 - 4a
48
Truth Table for (pvq) ^~ (p^q) – 2 - 4c
49
Truth Table for (pvq) ^~ (p^q) – 2 - 4e
v v
50
Truth Table for (pvq) ^~ (p^q) – 2 -4f
51
Exclusive OR – 2 - 5
52
Symbols for Exclusive OR – 2 - 5a
53
Logical Equivalence – 2 - 6
54
Double Negation ~(~p) ≡ p – 2 - 7
55
Examples – 2 - 12
56
Example – 2 - 17c
57
Example – 2 - 17d
58
Example – 2 - 17e
59
Exercise – 2 - 19
60
Tautology – 2 - 21
61
Example – 2 - 21a
62
Contradiction – 2 - 22
63
Example – 2 - 22a
64
Exercise – 2 - 23
65
Exercise – 2 - 24
66
