DS Lecture 1

Discrete Structures and
Quantitative Reasoning-II
(QTR-2328)
Discrete vs Continuous
• Examples of discrete Data

– Number of boys in the class.
– Number of candies in a packet.
– Number of suitcases lost by an airline.
• Examples of continuous Data

– Height of a person.
– Time in a race.
– Distance traveled by a car.
• Discrete data is a finite value
that can be counted.
• Continuous data has an infinite

number of possible values that
can be measured.
Why study Discrete Mathematics?
• It develops your mathematical thinking.
• Improves your Problem-solving ability.
• Is Important to survive in subject like: compiler design,
databases, computer security, operating system, automata
theory etc.
• Many problems can be solved using Discrete Mathematics
What is discrete Structures?
• Discrete mathematics is the part of mathematics

devoted to the study of discrete objects (Kenneth H.
Rosen, 7th edition).
• Discrete mathematics is the study of mathematical

structures that are fundamentally discrete rather
than continuous (wikipedia).
Applications of discrete mathematics
• How can a circuit that adds two integers be designed?
• How many ways are there to choose a valid password on a
computer?
• What is the shortest path between two cities using
transportation system?
• How can I encrypt a message so that no unintended recipient
can read it?
• How many valid internet addresses are there?
• How can a list of integers be sorted so that the integers are in
increasing order?
Syllabus (Topics to be covered in this course)
• Logic
• Elementary Number Theory and Methods of Proof
• Set Theory
• Relations
• Sequences and Recursion
• Mathematical Induction
• Counting
• Relations and Equivalence Relations
• Graphs
• Trees
Reference Books
• Discrete Mathematics and its Applications
(with Combinatorics and Graph Theory)
7th Edition, The McGraw-Hill Companies, 2007,
Kenneth H. Rosen.
• Discrete Mathematics with Applications
4th Edition, Thomson Learning, 1995,
Susanna S. Epp.
• Discrete Mathematics for Computer Scientists
2nd Edition, Addison-Wesley, 1999,
John Truss.
Logic
• Propositional Logic
• Logic of Compound Statements
• Propositional Equivalences
• Conditional Statements
• Logical Equivalences
• Valid and Invalid Arguments
• Applications: Digital Logic Circuits
• Predicates and Quantifiers
• Logic of Quantified Statements
Logic
Logic
Propositional Logic
Proposition: A proposition (or Statement) is a declarative
sentence (that is, a sentence that declares a
fact) that is either true or false, but not both.
Examples
1. Is the following sentence a proposition? If it is a proposition,
determine whether it is true or false.
Paris is the capital of France.
This makes a declarative statement, and hence is a
proposition. The proposition is TRUE (T).
1. Grass is
green.
2. 4 + 2 = 6
3. 4 + 2 = 7
Examples (Propositions Cont.)
2. Is the following sentence a proposition? If it is a

proposition, determine whether it is true or false.
Can Ali come with you?.
This is a question not the declarative sentence and hence
not a proposition.

Take two aspirins.
This is an imperative sentence not the declarative

sentence and therefore not a proposition.

x+ 4 > 9.
Because this is true for certain values of x (such as x =

6) and false for other values of x (such as x = 5), it is not
a proposition.

He is a college student.
Because truth or falsity of this proposition depend

on the reference for the pronoun, He. it is not a
proposition.
Compound Propositions
Notations
• The small letters are commonly used to denote the

propositional variables, that is, variables that
represent propositions, such as, p, q, r, s, ….
• The truth value of a proposition is true, denoted by T

or 1, if it is a true proposition and false, denoted by F
or 0, if it is a false proposition.
Producing new propositions from existing propositions.
Logical Operators or Connectives
1. Not 
2. And ˄
3. Or ˅
4. Exclusive or 
5. Implication 
6. Biconditional 
Negation of a proposition
Let p be a proposition. The negation of p, denoted by
 p (also denoted by ~p), is the statement
“It is not the case that p”.

The proposition  p is read as “not p”. The truth
values of the negation of p,  p, is the opposite of the
truth value of p.
Examples
1. Find the negation of the following proposition
p : Today is Friday.
The negation is
 p : It is not the case that today is Friday.
This negation can be more simply expressed by
 p : Today is not Friday.

Examples
2. Write the negation of
“6 is negative”.
The negation is
“It is not the case that 6 is negative”.

or “6 is nonnegative”.
Truth Table (NOT)
• Unary Operator, Symbol: 
p p
true false
false true
Conjunction (AND)
Definition
Let p and q be propositions. The conjunction
of p and q, denoted by p˄q, is the proposition
“p and q”.
The conjunction p˄q is true when p and q are
both true and is false otherwise.
Examples
1. Find the conjunction of the propositions p and q, where
p : Today is Friday.
q : It is raining today.
The conjunction is
p˄q : Today is Friday and it is raining today.

DS Lecture 1

Uploaded by

Copyright:

Available Formats

DS Lecture 1

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS Lecture 1

Uploaded by

Copyright:

Available Formats

Discrete Structures and

• Examples of discrete Data

• Examples of continuous Data

• Continuous data has an infinite

• Discrete mathematics is the part of mathematics

• Discrete mathematics is the study of mathematical

2. Is the following sentence a proposition? If it is a

Can Ali come with you?.

This is a question not the declarative sentence and hence

3. Is the following sentence a proposition? If it is a

Take two aspirins.

This is an imperative sentence not the declarative

4. Is the following sentence a proposition? If it is a

Because this is true for certain values of x (such as x =

5. Is the following sentence a proposition? If it is a

Because truth or falsity of this proposition depend

• The small letters are commonly used to denote the

• The truth value of a proposition is true, denoted by T

Logical Operators or Connectives

“It is not the case that p”.

This negation can be more simply expressed by

 p : Today is not Friday.

2. Write the negation of

“It is not the case that 6 is negative”.

• Unary Operator, Symbol: 

1. Find the conjunction of the propositions p and q, where

p˄q : Today is Friday and it is raining today.

You might also like