Discrete Structures

Aleena Rehman
ZUFESTM - Ziauddin University Faculty of
Engineering & Management
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.
What is discrete Structures?

• Discrete mathematics is the part of mathematics

devoted to the study of discrete objects (Kenneth H.
Rosen, 6th 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
Marks Distribution
Category Marks

Final Exam 40

Midterm Exam 20

Assignments (4) 10

Quizzes (4) 10

Presentation 20

Total Marks 100

Students must maintain at least 80% attendance to be eligible to sit for the
midterm and final exams.
Reference Books
• Discrete Mathematics and its Applications
(with Combinatorics and Graph Theory)
6th Edition, The McGraw-Hill Companies, 2007,
Kenneth H. Rosen.
• Discrete Mathematics with Applications
2nd 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
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).
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.
Examples (Propositions Cont.)

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

proposition, determine whether it is true or false.

Take two aspirins.

This is an imperative sentence not the declarative

sentence and therefore not a proposition.
Examples (Propositions Cont.)

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

proposition, determine whether it is true or false.

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.
Examples (Propositions Cont.)

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

proposition, determine whether it is true or false.

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.
Notations

• Propositions are often represented by small letters called

notations, such as p, q, r, s, etc.
• These variables represent specific statements or
sentences.
• Every proposition has a truth value, which is either :
• True (T or 1): If the statement is correct or valid.
• False (F or 0): If the statement is incorrect or invalid.
 Compound Propositions
A compound proposition is formed by combining two or more
simple propositions using logical operators like AND ( ∧), OR
(∨), NOT (¬), IMPLICATION (→), etc. These operators help
create more complex logical expressions.
Logical Operators or Connectives

1. Not 
2. And ˄
3. Or ˅
4. Exclusive or 
5. Implication 
6. Biconditional 
Compound Propositions
Negation of a proposition
Negates a proposition, meaning it changes True (T)
to False (F) and vice versa.
It is not the case that “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)
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.

Truth Table (AND)
• Binary Operator, Symbol: 

p q pq
true true true
true false false
false true false
false false false
 Disjunction (OR)

Let p and q be propositions. The disjunction of p

and q, denoted by p˅q, is the proposition “p or q”.
The disjunction p˅q is false when both p and q are
false and is true otherwise.
Examples

1. Find the disjunction of the propositions p and q,

where

p : Today is Friday.
q : It is raining today.
The disjunction is

p˅q : Today is Friday or it is raining today.

Truth Table (OR)

• Binary Operator, Symbol: 

p q pq
true true true
true false true
false true true
false false false
Exclusive OR (XOR)

Let p and q be propositions. The exclusive or

of p and q, denoted by pq, is the proposition
“pq”.
The exclusive or, p  q, is true when exactly
one of p and q is true and is false otherwise.
Examples

1. Find the exclusive or of the propositions p and q,

where

p : Atif will pass the course CSC102.

q : Atif will fail the course CSC102.
The exclusive or is

pq : Atif will pass or fail the course CSC102.

Truth Table (XOR)

• Binary Operator, Symbol: 

p q pq
true true false
true false true
false true true
false false false
Examples (OR vs XOR)
The following proposition uses the (English) connective
“or”. Determine from the context whether “or” is intended
to be used in the inclusive or exclusive sense.

1. “Nabeel has one or two brothers”.

A person cannot have both one and two brothers.
Therefore, “or” is used in the exclusive sense.
Examples (OR vs XOR)

2. To register for BSC you must have passed

the qualifying exam or be listed as an Math
major.

Presumably, if you have passed the qualifying exam and

are also listed as an Math major, you can still register for
BCS. Therefore, “or” is inclusive.
Composite Statements
Statements and operators can be combined in any
way to form new statements.

p q p q (p)(q)
true true false false false
true false false true true
false true true false true
false false true true true
Translating English to Logic

I did not buy a lottery ticket this week or I bought a lottery ticket and won
the million dollar on Friday.
Breakdown:
•"I did not buy a lottery ticket this week": This is a negation.
•If p represents "I bought a lottery ticket this week", then the negation of
this is ¬p (meaning "I did not buy a lottery ticket this week").

•"I bought a lottery ticket and won the million dollar on Friday": This
is a conjunction. If q represents "I bought a lottery ticket" and r
represents "I won the million dollar on Friday", the conjunction is q ∧ r
(meaning "I bought a lottery ticket and I won the million dollar on Friday").
Conditional Statements

A conditional statement is a type of logical proposition that

expresses an "if-then" relationship between two propositions
Conditional Statements
Implication
Let p and q be propositions. The conditional statement p 
q, is the proposition “If p, then q”.
The conditional statement p  q is false when p
is true and q is false and is true otherwise.

where p is called hypothesis, antecedent or premise.

q is called conclusion or consequence
In logic, implication refers to a type of logical relationship between two statements. It is
typically represented by the symbol → (or sometimes ⇒) and is read as:
"If p, then q" or "p implies q".
This means that whenever the statement p (the antecedent) is true, the statement q (the
consequent) must also be true for the implication to hold true.
Key Points:
•Implication is a conditional statement, often called "if-then" statements.
•It tells us that q will occur if p happens.
•It is not concerned with the truth value of q when p is false.
Implication (if - then)

• Binary Operator, Symbol: 

P Q PQ
true true true
true false false
false true true
false false true
Conditional Statements
Biconditional Statements
Let p and q be propositions. The biconditional statement
pq, is the proposition “p if and only if q”.
The biconditional (bi-implication) statement p
 q is true when p and q have same truth
values and is false otherwise.
Biconditional (if and only if)

• Binary Operator, Symbol: 

P Q PQ
true true true
true false false
false true false
false false true
 Logically Equivalent Statements
According to De Morgan's Law, Two statements are called logically
equivalent if and only if they have identical truth tables or the truth value
will always be the same.

The statements (PQ) and (P)(Q) are logically equivalent, because

(PQ)(P)(Q) is always true.
 P Q (PQ) (P)(Q) (PQ)(P)(Q)

true true false false true

true false true true true
false true true true true
false false true true true
 Tautologies
• Tautology is a statement that is always true regardless of the truth
values of the individual logical variables

• Examples:
• R(R)
 (PQ)  (P)(Q)
Contradictions
• A Contradiction is a statement that is always false regardless of
the truth values of the individual logical variables

Examples
• R(R)
 ((PQ)(P)(Q))

• The negation of any tautology is a contradiction, and

the negation of any contradiction is a tautology.
 Practice Questions

1. Identify whether the following are propositions:

1. The earth is flat
2. 5 + 2 = 9
3. Can you help me with this
4. The sky is blue or green
2. Logical form:
1. If I am studying, then I will pass the exam
2. It is not true that I am studying or I will pass the exam
3. Either I will go to the park, or I will stay home
4. If it is sunny, then I will play cricket
3. Truth Tables:
4. Translations

a.If I eat, then I will not be hungry

b.It is not true that I am both happy and tired
c.Either it rains, or I will go for a walk
d.If I complete my homework, then I will watch TV
e.I will watch TV only if I complete my homework