CSM2127: Discrete Mathematics

Introduction

Presented By:
Professor Dr. Md. Rakib Hassan
Department of Computer Science and Mathematics
Email: rakib@bau.edu.bd
Textbook
❖Discrete Mathematics and Its Applications by Kenneth H.
Rosen (8th edition or later)

PROF. DR. MD. RAKIB HASSAN 2

What is Discrete Mathematics?
❖Discrete mathematics
o is the part of mathematics devoted to the study of discrete (as
opposed to continuous) objects.
❖Calculus
o deals with continuous objects and is not part of discrete
mathematics.
❖Examples of discrete objects:
o integers, steps taken by a computer program, distinct paths to
travel from point A to point B on a map along a road network, ways
to pick a winning set of numbers in a lottery.
❖A course in discrete mathematics provides
o the mathematical background needed for all subsequent courses in
computer science and for all subsequent courses in the many
branches of discrete mathematics.

PROF. DR. MD. RAKIB HASSAN 3

Kinds of Problems Solved Using Discrete
Mathematics
❖How many ways can a password be chosen following specific
rules?
❖How many valid internet addresses are there?
❖What is the probability of winning a particular lottery?
❖Is there a link between two computers in a network?
❖How can I identify spam email messages?
❖How can I encrypt a message so that no unintended recipient
can read it?
❖How can we build a circuit that adds two integers?

PROF. DR. MD. RAKIB HASSAN 4

Kinds of Problems Solved Using Discrete
Mathematics (Cont.)
❖ What is the shortest path between two cities using a transportation
system?
❖ Find the shortest tour that visits each of a group of cities only once and
then ends in the starting city.
❖ How can we represent English sentences so that a computer can reason
with them?
❖ How can we prove that there are infinitely many prime numbers?
❖ How can a list of integers be sorted so that the integers are in increasing
order?
❖ How many steps are required to do such a sorting?
❖ How can it be proved that a sorting algorithm always correctly sorts a list?

PROF. DR. MD. RAKIB HASSAN 5

Applications in Bioinformatics
❖ Graph Theory:
o Biological networks, like protein-protein interactions, can be modeled as
graphs.
o Graph algorithms help analyze these networks, identify important nodes, and
understand how information flows within them.
❖ Combinatorics:
o This branch deals with counting and arranging discrete objects.
o It's crucial for tasks like counting possible DNA sequences, analyzing gene
order variations, or finding optimal alignments between sequences.
❖ Algorithms:
o Designing efficient algorithms is vital for analyzing large biological datasets.
o Discrete mathematics provides a foundation for designing algorithms to
analyze sequences, find patterns in genetic data, and solve optimization
problems in bioinformatics.
❖ Number Theory:
o Concepts like modular arithmetic find applications in error correction for DNA
sequencing and data transmission.

PROF. DR. MD. RAKIB HASSAN 6

Goal of Discrete Mathematics
❖Mathematical Reasoning
o Ability to read, understand, and construct mathematical
arguments and proofs.
❖Combinatorial Analysis
o Techniques for counting objects of different kinds.
❖Discrete Structures
o Abstract mathematical structures that represent objects and
the relationships between them.
o Examples are sets, permutations, relations, graphs, trees, and
finite state machines.

PROF. DR. MD. RAKIB HASSAN 7

Goal of Discrete Mathematics (Cont.)
❖Algorithmic Thinking
o One way to solve many problems is to specify an algorithm.
o An algorithm is a sequence of steps that can be followed to
solve any instance of a particular problem.
❖Applications and Modeling
o Concepts from discrete mathematics have not only been
used to address problems in computing, but have been
applied to solve problems in many areas such as chemistry,
biology, linguistics, geography, business, etc.

PROF. DR. MD. RAKIB HASSAN 8

It is a Gateway Course
❖Topics in discrete mathematics will be important in many
courses that you will take in the future:
o Computer Science:
▪ Computer Architecture, Data Structures, Algorithms, Programming
Languages, Compilers, Computer Security, Databases, Artificial
Intelligence, Networking, Graphics, Game Design, Theory of
Computation, ……
o Mathematics:
▪ Logic, Set Theory, Probability, Number Theory, Abstract Algebra,
Combinatorics, Graph Theory, Game Theory, Network Optimization, …
▪ The concepts learned will also be helpful in continuous areas of mathematics.
o Other Disciplines: You may find concepts learned here useful in courses in
philosophy, economics, linguistics, and other departments.

PROF. DR. MD. RAKIB HASSAN 9

Propositions
❖A proposition is a declarative sentence that is either true or
false.
❖Examples of propositions:
a) The Moon is made of green cheese.
b) Dhaka is the capital of Bangladesh.
c) 1 week has 8 days.
d) 1+0=1
e) 0+0=2
❖Examples that are not propositions.
a) Sit down!
b) What time is it?
c) x+1=2
d) x+y=z

PROF. DR. MD. RAKIB HASSAN 10

Propositional Logic
❖Constructing Propositions
o Propositional Variables:
▪ p, q, r, s, …
o The proposition that is always true is denoted by T and the
proposition that is always false is denoted by F.
o Compound Propositions are constructed from logical
connectives and other propositions
▪ Negation ¬
▪ Conjunction ∧
▪ Disjunction ∨
▪ Implication →
▪ Biconditional

PROF. DR. MD. RAKIB HASSAN 11

Compound Propositions: Negation
❖ The negation of a proposition p is denoted by ¬p and has this
truth table:

p ¬p
T F
F T

❖Example: If p denotes “The earth is round.”, then ¬p denotes

“It is not the case that the earth is round,” or more simply “The
earth is not round.”

PROF. DR. MD. RAKIB HASSAN 12

Conjunction
❖The conjunction of propositions p and q is denoted by p ∧ q
and has this truth table:

p q p∧q
T T T
T F F
F T F
F F F

❖Example: If p denotes “I am at home.” and q denotes “It is

raining.” then p ∧q denotes “I am at home and it is raining.”

PROF. DR. MD. RAKIB HASSAN 13

Disjunction
❖The disjunction of propositions p and q is denoted by p ∨q
and has this truth table:
p q p ∨q
T T T
T F T
F T T
F F F

❖Example: If p denotes “I am at home.” and q denotes “It is

raining.” then p ∨q denotes “I am at home or it is raining.”

PROF. DR. MD. RAKIB HASSAN 14

The Connective Or in English
❖In English, “or” has two distinct meanings.
o “Inclusive Or” - In the sentence “Students who have taken CS202 or
Math120 may take this class,” we assume that students need to have
taken one of the prerequisites, but may have taken both. This is the
meaning of disjunction. For p ∨q to be true, either one or both of p and
q must be true.
o “Exclusive Or” - When reading the sentence “Soup or salad comes with
this entrée,” we do not expect to be able to get both soup and salad. This
is the meaning of Exclusive Or (Xor). In p ⊕ q , one of p and q must be
true, but not both. The truth table for ⊕ is:

p q p ⊕q
T T F
T F T
F T T
F F F

PROF. DR. MD. RAKIB HASSAN 15

Implication or Conditional Statement
❖If p and q are propositions, then p →q is a conditional
statement or implication which is read as “if p, then q ” and
has this truth table:
p q p →q
T T T
T F F
F T T
F F T
❖Example: If p denotes “I am at home.” and q denotes “It is
raining.” then p →q denotes “If I am at home, then it is
raining.”
❖In p →q,
o p is the hypothesis (antecedent or premise) and
o q is the conclusion (or consequence).

PROF. DR. MD. RAKIB HASSAN 16

Understanding Implication
❖ In p →q, there does not need to be any connection between
the antecedent or the consequent.
o The “meaning” of p →q depends only on the truth values of p and q.
❖These implications are perfectly fine, but would not be used in
ordinary English.
o “If the moon is made of green cheese, then I have more money than Bill
Gates. ”
o “If the moon is made of green cheese, then I’m on leave.”
o “If 1 + 1 = 3, then it is raining today.”

PROF. DR. MD. RAKIB HASSAN 17

Understanding Implication (Cont.)
❖One way to view the logical conditional is to think of an
obligation or contract.
o “If I am elected, then I will lower taxes.”
o “If you get 100% on the final, then you will get an A.”

❖If the politician is elected and does not lower taxes, then the
voters can say that he or she has broken the campaign pledge.
❖Something similar holds for the professor. This corresponds to
the case where p is true and q is false.

PROF. DR. MD. RAKIB HASSAN 18

Understanding Implication (Cont.)
❖“p only if q” expresses the same thing as “if p, then q”
❖Note that “p only if q” says that p cannot be true when q is not
true.
❖That is, the statement is false if p is true, but q is false.
❖When p is false, q may be either true or false, because the
statement says nothing about the truth value of q.

PROF. DR. MD. RAKIB HASSAN 19

Example
❖Suppose your professor tells you
o “You can receive an A in the course only if your score on the final is at
least 90%.”

❖Then, if you receive an A in the course, then you know that

your score on the final is at least 90%. If you do not receive an
A, you may or may not have scored at least 90% on the final.
❖Be careful not to use “q only if p” to express p → q because
this is incorrect.
❖“p is sufficient for q” is equivalent to “if p, then q,” note that “p
is sufficient for q” means if p is true, it must be the case that q
is also true. This is the same as saying that if p is true, then q is
also true.

PROF. DR. MD. RAKIB HASSAN 20

Example
❖Let p be the statement “Maria learns discrete mathematics”
and q the statement “Maria will find a good job.” Express the
statement p → q as a statement in English.
❖From the definition of conditional statements, we see that
when p is the statement “Maria learns discrete mathematics”
and q is the statement “Maria will find a good job,” p → q
represents the statement
o “If Maria learns discrete mathematics, then she will find a good job.”
❖There are many other ways to express this conditional
statement in English. Among the most natural of these are
o “Maria will find a good job when she learns discrete mathematics.”
o “For Maria to get a good job, it is sufficient for her to learn discrete
mathematics.”
o “Maria will find a good job unless she does not learn discrete
mathematics.”

PROF. DR. MD. RAKIB HASSAN 21

 Different Ways of Expressing p →q
❖ if p, then q
❖ p implies q
❖ if p, q
❖ p only if q
❖ q unless ¬p
❖ q when p
❖ q if p
❖ q whenever p
❖ p is sufficient for q
❖ q follows from p
❖ q is necessary for p
❖ a necessary condition for p is q
❖ a sufficient condition for q is p

PROF. DR. MD. RAKIB HASSAN 22

Converse, Contrapositive, and Inverse
❖From p →q we can form new conditional statements .
o q →p is the converse of p →q
o ¬q → ¬ p is the contrapositive of p →q
o ¬ p → ¬ q is the inverse of p →q

❖Example: Find the converse, inverse, and contrapositive of

“The home team wins whenever it is raining.”
❖ Solution:
o Because “q whenever p” is one of the ways to express the conditional
statement p → q, the original statement can be rewritten as
▪ “If it is raining, then the home team wins.”
o converse: If the home team wins, then it is raining.
o inverse: If it is not raining, then the home team does not win.
o contrapositive: If the home team does not win, then it is not raining.

PROF. DR. MD. RAKIB HASSAN 23

Biconditional
❖If p and q are propositions, then we can form the
biconditional proposition p q , read as “p if and only if q .”
❖The biconditional p q denotes the proposition with this
truth table:

p q p q
T T T
T F F
F T F
F F T

❖ If p denotes “I am at home.” and q denotes “It is raining.” then

p q denotes “I am at home if and only if it is raining.”

PROF. DR. MD. RAKIB HASSAN 24

Expressing the Biconditional
❖Some alternative ways “p if and only if q” is expressed
in English:
o p is necessary and sufficient for q
o if p then q , and conversely
o p iff q

PROF. DR. MD. RAKIB HASSAN 25

Truth Tables For Compound Propositions
❖Construction of a truth table:
o Rows
▪ Need a row for every possible combination of values for the atomic
propositions.
o Columns
▪ Need a column for the compound proposition (usually at far right)
▪ Need a column for the truth value of each expression that occurs in the
compound proposition as it is built up.
➢ This includes the atomic propositions

PROF. DR. MD. RAKIB HASSAN 26

Example Truth Table
❖Construct a truth table for

p q r r pq p  q → r
T T T F T F
T T F T T T
T F T F T F
T F F T T T
F T T F T F
F T F T T T
F F T F F T
F F F T F T

PROF. DR. MD. RAKIB HASSAN 27

Equivalent Propositions
❖Two propositions are equivalent if they always have the same
truth value.
❖Example: Show using a truth table that the conditional (p →q)
is equivalent to the contrapositive (¬q → ¬ p).
❖Solution:
p q ¬p ¬q p →q ¬q → ¬ p
T T F F T T
T F F T F F
F T T F T T
F F T T T T

PROF. DR. MD. RAKIB HASSAN 28

Using a Truth Table to Show Non-Equivalence
❖Example: Show using truth tables that neither the converse
nor inverse of an implication are equivalent to the implication.
❖Solution:
p q ¬p ¬q p →q ¬ p →¬ q q→p
T T F F T T T
T F F T F T T
F T T F T F F
F F T T T T T

PROF. DR. MD. RAKIB HASSAN 29

Problem
❖How many rows are there in a truth table with n propositional
variables?

Solution: 2n

❖Note that this means that with n propositional variables, we

can construct 2n distinct (i.e., not equivalent) propositions.

PROF. DR. MD. RAKIB HASSAN 30

Precedence of Logical Operators
Operator Precedence
 1
 2
 3
→ 4
 5

❖𝑝𝑞→𝑟 is equivalent to (𝑝𝑞)→𝑟

❖If the intended meaning is 𝑝(𝑞→ 𝑟), then parentheses must
be used.

PROF. DR. MD. RAKIB HASSAN 31

PROF. DR. MD. RAKIB HASSAN 32