Introduction Application of Discrete Structure

Discrete structures/mathematics has special relevance to

computer science.
Apart from computer sc. Discrete Structure have
application in many diverse areas.
Computer is a binary machine and all the algorithms in
computer science are based on binary digits 0 and 1. We
therefore can say computer is inherently is DISCRETE. Example:
Management Science
Discrete Structures/Mathematics
Network Analysis
BSCS (3 Credit Hour) Social decision making
Lecture # 01 Finance

Reasons to study discrete Mathematics. Course Objective

Mathematical Maturity essential to study any scientific Express statements with the precision of formal logic.
discipline.
Analyze arguments to test their validity. Prove a formula using mathematical induction.
Prerequisite of number of advance courses i.e.
Apply the basic properties and operations related to sets. Prove statements using direct and indirect methods.
Data Structures
Algorithm Analysis
Apply to sets the basic properties and operations related Illustrate the basic definitions of graph theory and
Theory of Automata
to relations and functions. properties of graphs.
Computer Theory

Define terms recursively.

The kind of problem solved using Discrete

Structure Course: Recommended Books: Main Topics:
How many ways are there to choose a valid password? 1) Discrete Mathematics and its application by 1) Logic
Kenneth H. Rosen, 7th edition. 2) Sets & Operations on sets
Is there a path connecting two computers in a network? 3) Relations & Their Properties
2) Discrete Mathematics with applications by 4) Functions
How can a circuit that adds two integers be designed? Susanna S. Epp. 5) Sequences & Series
6) Recurrence Relations
How many valid internet addresses are there? 3) Discrete Mathematics by Ross and Wright 7) Mathematical Induction
8) Methods of Proof
How can we encrypt credit card information on the web? 9) Combinatorics
10) Probability
What is the probability of winning a lottery? 11) Graphs and Trees
 What is Discrete mathematics /
Marks Distribution structures? Example:
Assignments (10 %) The word discrete is essentially the opposite of
Quizzes (10 %) continuous, discontinuous or segregated.
Midterm Exam (30 %) Discrete Continuous
During the 8th week. Definition:
Duration: 1.5 hour.
Will cover all material covered during the first seven weeks. “Discrete Mathematics/Structure concerns
Final Exam (50 %) processes that consist of a sequence of individual steps.”
During the 16th week.
Will cover whole of the course with a slight emphasis on the
material cover after the midterm exam.
Duration: 3 hour

Example: Odometer Logic

Set of Integers: Logic rules and principles is to distinguish an argument is
• • • • • • valid or invalid.
-3 -2 -1 0 1 2
Def:
Set of Real Numbers: “Logic is the study of the principles and methods that
distinguishes between a valid and an invalid argument.”
• • • • • • •
-3 -2 -1 0 1 2 3

PROPOSITION Examples: NOT Propositions

A statement/proposition is a declarative sentence which is Statement Truth Value Close the door.
either TRUE or FALSE but not both.

A statement is also referred to as Proposition. Grass is green. x is greater than 2.

Example: 4+2=6
2+2 = 4
4+2=7 He is very rich (though is a declarative statement but we
It is Sunday today
There are four fingers in a hand. don’t know about pronoun he)
If a proposition is true, we say that it has a truth value of
"true”.
If a proposition is false, its truth value is "false".
The truth values “true” and “false” are, respectively,
denoted by the letters T and F. 
 UNDERSTANDING STATEMENTS
Rule: Example:
If the sentence is preceded by other sentences that x=1 x + 2 is positive.
make the pronoun or variable reference clear, then the x>2 May I come in?
sentence is a statement. x > 2 is a statement with truth-value FALSE. Logic is interesting.
It is hot today.
Example -1 > 0
Bill Gates is an American x + y = 12
He is very rich
He is very rich is a statement with truth-value TRUE.

COMPOUND STATEMENT SYMBOLIC REPRESENTATION LOGICAL CONNECTIVES

Def: Statements are symbolically represented by letters such CONNECTIV MEANING SYMBOL CALLED
“Simple statements could be used to build a compound as p, q, r,...
statement.” Negation not ~ Tilde
EXAMPLES: Conjunction and ∧ Hat
Examples:
Disjunction or ∨ Vel
“3 + 2 = 5” and “Lahore is a city in Pakistan” p = “Islamabad is the capital of Pakistan”
Conditional if…then… → Arrow
“The grass is green” or “ It is hot today” q = “17 is divisible by 3”
“Discrete Structure is not difficult to me”   Biconditional if and only ↔ Double
if arrow

AND, OR, NOT are called LOGICAL CONNECTIVES.

TRANSLATING FROM ENGLISH TO

EXAMPLES: SYMBOLS: EXAMPLE:
p = “Islamabad is the capital of Pakistan” Let p = “It is hot”, and q = “It is sunny” Let h = “Ali is healthy”
q = “17 is divisible by 3”   w = “Ali is wealthy”
SENTENCE SYMBOLIC FORM s = “Ali is wise”
p ∧ q = “Islamabad is the capital of Pakistan and 17 is It is not hot.
divisible by 3” It is hot and sunny. SENTENCE SYMBOLIC FORM
p ∨ q = “Islamabad is the capital of Pakistan or 17 is It is hot or sunny. Ali is healthy and wealthy but not wise.
divisible by 3” It is not hot but sunny. Ali is not wealthy but he is healthy and wise.
~p = “It is not the case that Islamabad is the capital It is neither hot nor sunny. Ali is neither healthy, wealthy nor wise.
of Pakistan” or simply “Islamabad is not the capital of
Pakistan”
 TRANSLATING FROM SYMBOLS TO
ENGLISH TRUTH TABLE NEGATION (~)
Let m = “Ali is good in Mathematics” A convenient method for analyzing a compound If p is a statement variable, then negation of p, “not p”,
c = “Ali is a Computer Science student” statement is to make a truth table for it. is denoted as “~p”

SYMBOLIC FORM STATEMENTS A truth table specifies the truth value of a compound It has opposite truth value from p i.e.,
~c proposition for all possible truth values of its constituent if p is true, ~p is false; if p is false, ~p is true.
propositions.
c∨m
m ∧ ~c

TRUTH TABLE FOR ~p CONJUCTION (∧) TRUTH TABLE FOR (p ∧ q)

If p and q are statements, then the conjunction of p and
q is “p and q”, denoted as “p ∧ q”. p q p∧q
p ~p
T T T
T F It is true when, and only when, both p and q are true. If T F F
either p or q is false, or if both are false, p ∧ q is false. F T F
F T
F F F

DISJUNCTION (∨) TRUTH TABLE FOR (p ∨ q)

If p & q are statements, then the disjunction of p and q
is “p or q”, denoted as “p ∨ q”. p q p∨
q
It is true when at least one of p or q is true and is false T T T
only when both p and q are false. T F T
F T T
F F F