FULL NOTES

OF
DISCRETE MATHEMATICS
BCA-3 SEM
SEC –A

PREPARED BY:
Mr. GAURAV SRIVASTAVA
Mathematical Logic
Lecture-1

2
 Discrete Mathematics
Introduction

 The term Discrete Mathematics is a

combination of two words.
1. Discrete 2. Mathematics
Example:
1.Number of students in your class?
Particular Value
2. Heights of students in your class?
Continuous Value
3
 Discrete Mathematics
Introduction
3.Today is Wednesday.

• True or False

• Yes or No
1,0

In Computer Science:
 Discrete is called as Digital.
 Continuous is called as Analog. 4
 Discrete Mathematics
Introduction
 Discrete object is something that is
countable.
 Example of Discrete object:
1. People, chair & table.
2. Natural number.
3. Rational Number.
Example of Non-Discrete object:
 The Real Numbers.
•
5
What is Discrete Mathematics ?
Definition
 Discrete Mathematics is not the name of
a branch of mathematics ,like-Number
theory, Algebra & Calculus etc. Rather,
it's a description of a set of branches of
math that all have one common property
that they are „discrete‟rather than continuous.
 Discrete Mathematics is the study of discrete
objects.
6
 Why study Discrete Mathematics?
 It develops your mathematical thinking/ logic
making.
 It improves your problem solving ability.
 If you are computer science student, then no
need to go anywhere else because Discrete
Mathematics is for you.
Discrete Mathematics is important to survive
in subjects like :Compiler design, database,
computer security, operating system &
automata theory etc.
7
Why study Discrete Mathematics ?
Many problems can be solve using
discrete mathematics.
 For Example:
1. Sorting the list of integers.
2. Finding the shortest path from your home
to your‟s friends home.
3. Drawing a graph with 2 conditions:
(i) You are not allowed to lift your pen.
(ii) You are not allowed to repeat edges.

8
 Why study Discrete Mathematics ?
4.How many different combination of passwords
are possible with just eight alphanumeric
characters.
5. Encrypt a message & deliver it to your friend
and you don‟t want anybody to read that
message except your friend.

9
Discrete Vs Continuous
 The whole world of mathematics is
divided into two realms:
1. Discrete 2. Continuous
Discrete Objects Continuous Objects
1. Discrete object is something that is Continuous object is something that
countable. is not countable.
2. Natural Numbers are discrete. Real Numbers are continuous
3. For Example : 1,2,3,4,5,……. For Example; 0.001 ,0.0001,0.1001 &
so on
4. Consider a function Y=X ; Consider functio Y= X ;
X,Y belongs to Natural Number X,Y belongs to Real Numbers.
5. Digital Clock is discrete in nature. Analog clock is continuous in nature.
- There is no continous time - In analog clock- hour , minute and
- Transition from one time to second hands move smoothly over
another time.
- 10:42:57 10:42:58 10
1.1 Propositional Logic
Introduction
A proposition is a declarative sentence (a
sentence that declares a fact) that is either
true or false, but not both.
Are the following sentences propositions?
Toronto is the capital of Canada. (Yes)
Read this carefully. (No)
1+2=3 (Yes)
x+1=2 (No)
What time is it? (No)

11
1.1 Propositional Logic

Propositional Logic – the area of logic that

deals with propositions
Propositional Variables – variables that
represent propositions: p, q, r, s
E.g. Proposition p – “Today is Friday.”
Truth values – T, F

12
1.1 Propositional Logic
DEFINITION 1
Let p be a proposition. The negation of p, denoted by ¬p, is the statement
“It is not the case that p.”
The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p
is the opposite of the truth value of p.

 Examples
 Find the negation of the proposition “Today is Friday.” and
express this in simple English.
Solution: The negation is “It is not the case that today is Friday.”
In simple English, “Today is not Friday.” or “It is not
Friday today.”
 Find the negation of the proposition “At least 10 inches of rain
fell today in Miami.” and express this in simple English.
Solution: The negation is “It is not the case that at least 10 inches
of rain fell today in Miami.”
In simple English, “Less than 10 inches of rain fell today
13

in Miami.”
1.1 Propositional Logic
 Note: Always assume fixed times, fixed places, and particular people
unless otherwise noted.
 Truth table: The Truth Table for the
Negation of a Proposition.
p ¬p
T F
F T

 Logical operators are used to form new propositions from two or more
existing propositions. The logical operators are also called
connectives.

14
1.1 Propositional Logic
DEFINITION 2
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
both p and q are true and is false otherwise.

 Examples
 Find the conjunction of the propositions p and q where p is the
proposition “Today is Friday.” and q is the proposition “It is
raining today.”, and the truth value of the conjunction.
Solution: The conjunction is the proposition “Today is Friday and it
is raining today.” The proposition is true on rainy Fridays.

15
1.1 Propositional Logic
DEFINITION 3
Let p and q be propositions. The disjunction of p and q, denoted by p ν
q, is the proposition “p or q”. The conjunction p ν q is false when both
p and q are false and is true otherwise.

 Note:
inclusive or : The disjunction is true when at least one of the two
propositions is true.
 E.g. “Students who have taken calculus or computer science can take
this class.” – those who take one or both classes.
exclusive or : The disjunction is true only when one of the
proposition is true.
 E.g. “Students who have taken calculus or computer science, but not
both, can take this class.” – only those who take one of them.
 Definition 3 uses inclusive or.
16
1.1 Propositional Logic
DEFINITION 4
Let p and q be propositions. The exclusive or of p and q, denoted by p  q,
is the proposition that is true when exactly one of p and q is true and is
false otherwise. 

The Truth Table for The Truth Table for The Truth Table for the
the Conjunction of the Disjunction of Exclusive Or (XOR) of
Two Propositions. Two Propositions. Two Propositions.
p q pΛq p q pνq p q p q
T T T T T T T T F
T F F T F T T F T
F T F F T T F T T
F F F F F F F F F
17
Discrete Mathematics
Lecture-2

18
1.1 Propositional Logic
Conditional Statements
DEFINITION 5
Let p and q be propositions. The conditional statement p → q, is the
proposition “if p, then q.” The conditional statement is false when p is
true and q is false, and true otherwise. In the conditional
 statement p
→ q, p is called the hypothesis (or antecedent or premise) and q is
called the conclusion (or consequence).
 A conditional statement is also called an implication.
 Example: “If I am elected, then I will lower taxes.” p→q
implication:
elected, lower taxes. T T |T
not elected, lower taxes. F T |T
not elected, not lower taxes. F F |T
elected, not lower taxes. T F |F

19
1.1 Propositional Logic
 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.
Solution: Any of the following -
“If Maria learns discrete mathematics, then she will find a
good job.
“Maria will find a good job when she learns discrete
mathematics.”
“For Maria to get a good job, it is sufficient for her to
learn discrete mathematics.”
“Maria will find a good job unless she does not learn
discrete mathematics.”
20
1.1 Propositional Logic
 Types of conditional/ Implication statements
 Converse Implication
 Definition : The statement q=> p is called converse implication of
the statement of p=> q
 Contrapositive Implication
 Definition : The statement ~ q => ~ p is called contrapositive of
the statement p= > q .
 Inverse Implication:
 Defintion : The statement ~ p => ~ q is called inverse
implication of the statement p => q

21
 Example:
Let p: It rains
q: The crops will grow.
Write down the converse ,inverse and contrapositive of the given
statements:
Solution : p=> q It rains then the crops will grow .
q=> p If the crops grow , then there has been rain.
~q=> ~p If the crops do not grow then there has been no rain.
~p => ~q If it does not rain then the crops will not grow.

22
1.1 Propositional Logic
DEFINITION 6
Let p and q be propositions. The biconditional statement p ↔ q is the
proposition “p if and only if q.” The biconditional statement p ↔ q is
true when p and q have the same truth values, and is false otherwise.
Biconditional statements are also called bi-implications.

 p ↔ q has the same truth value as (p → q) Λ (q → p)

 “if and only if” can be expressed by “iff”
 Example:
 Let p be the statement “You can take the flight” and let q be the
statement “You buy a ticket.” Then p ↔ q is the statement
“You can take the flight if and only if you buy a ticket.”
Implication:
If you buy a ticket you can take the flight.
If you don‟t buy a ticket you cannot take the flight. 23
1.1 Propositional Logic

The Truth Table for the

Biconditional p ↔ q.
p q p↔ q
T T T
T F F
F T F
F F T

24
Discrete Mathematics
Lecture-3

25
1.1 Propositional Logic
Truth Tables of Compound Propositions
 We can use connectives to build up complicated compound
propositions involving any number of propositional variables, then
use truth tables to determine the truth value of these compound
propositions.
 Example: Construct the truth table of the compound proposition
(p ν ¬q) → (p Λ q).

The Truth Table of (p ν ¬q) → (p Λ q).

p q ¬q p ν ¬q pΛq (p ν ¬q) → (p Λ q)

T T F T T T
T F T T F F
F T F F F T
F F T T F F 26
1.1 Propositional Logic
Precedence of Logical Operators
 We can use parentheses to specify the order in which logical
operators in a compound proposition are to be applied.
 To reduce the number of parentheses, the precedence order is
defined for logical operators.

Precedence of Logical Operators. E.g. ¬p Λ q = (¬p ) Λ q

Operator Precedence p Λ q ν r = (p Λ q ) ν r
¬ 1 p ν q Λ r = p ν (q Λ r)
Λ 2
ν 3
→ 4
↔ 5
27
1.1 Propositional Logic
Translating English Sentences
 English (and every other human language) is often ambiguous.
Translating sentences into compound statements removes the
ambiguity.
 Example: How can this English sentence be translated into a logical
expression?
“You cannot ride the roller coaster if you are under 4 feet
tall unless you are older than 16 years old.”
Solution: Let q, r, and s represent “You can ride the roller coaster,”
“You are under 4 feet tall,” and “You are older than
16 years old.” The sentence can be translated into:
(r Λ ¬ s) → ¬q.

28
1.1 Propositional Logic
 Example: How can this English sentence be translated into a logical
expression?
“You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”
Solution: Let a, c, and f represent “You can access the Internet from
campus,” “You are a computer science major,” and “You are
a freshman.” The sentence can be translated into:
a → (c ν ¬f).

29
1.1 Propositional Logic
Logic and Bit Operations
 Computers represent information using bits.
 A bit is a symbol with two possible values, 0 and 1.
 By convention, 1 represents T (true) and 0 represents F (false).
 A variable is called a Boolean variable if its value is either true or
false.
 Bit operation – replace true by 1 and false by 0 in logical
operations.

Table for the Bit Operators OR, AND, and XOR.

x y xνy x Λy x  y
0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 0 30
1.1 Propositional Logic
DEFINITION 7
A bit string is a sequence of zero or more bits. The length of this string
is the number of bits in the string.

 Example: Find the bitwise OR, bitwise AND, and bitwise XOR of the
bit string 01 1011 0110 and 11 0001 1101.
Solution:
01 1011 0110
11 0001 1101
-------------------
11 1011 1111 bitwise OR
01 0001 0100 bitwise AND
10 1010 1011 bitwise XOR

31
Discrete Mathematics
Lecture-4

32
1.2 Propositional Equivalences
Introduction
DEFINITION 1
A compound proposition that is always true, no matter what the truth
values of the propositions that occurs in it, is called a tautology. A
compound proposition that is always false is called a contradiction. A
compound proposition that is neither a tautology or a contradiction is
called a contingency.

Examples of a Tautology and a Contradiction.

p ¬p p ν ¬p p Λ ¬p

T F T F
F T T F

33
1.2 Propositional Equivalences
Logical Equivalences
DEFINITION 2
The compound propositions p and q are called logically equivalent if p ↔
q is a tautology. The notation p ≡ q denotes that p and q are logically
equivalent.

 Compound propositions that have the same truth values in all

possible cases are called logically equivalent.
 Example: Show that ¬p ν q and p → q are logically equivalent.

Truth Tables for ¬p ν q and p → q .

p q ¬p ¬p ν q p→q
T T F T T
T F F F F
F T T T T
34
F F T T T
 Logical Equivalence
 Commutative laws: p  q = q  p, p  q = q  p
 Associative laws: (p  q)  r = p  (q  r),
(p  q)  r = p  (q  r)
 Distributive laws: p  (q  r) = (p  q)  (p  r)
p  (q  r) = (p  q)  (p  r)
 Identity laws: p  t = p, p  c = p
 Negation laws: p  ~p = t, p  ~p = c
 Double negative law: ~(~p) = p
 Idempotent laws: p  p = p, p  p = p
 De Morgan‟s laws: ~(p  q) = ~p  ~q,
~(p  q) = ~p  ~q
 Universal bound laws: p  t = t, p  c = c
 Absorption laws: p  (p  q) = p, p  (p  q) = p
 Negation of t and c: ~t = c, ~c = t
De Morgan’s Laws
(1) ~(p  q) = ~p  ~q,
(2) ~(p  q) = ~p  ~q

The negation of an and statement is logically

equivalent to the or statement in which each
component is negated.
The negation of an or statement is logically equivalent
to the and statement in which each component is
negated.
 1.2 Propositional Equivalences
Constructing New Logical Equivalences
 Example: Show that ¬(p → q ) and p Λ ¬q are logically equivalent.
Solution:
¬(p → q ) ≡ ¬(¬p ν q) by example on slide 21
≡ ¬(¬p) Λ ¬q by the second De Morgan law
≡ p Λ ¬q by the double negation law
 Example: Show that (p Λ q) → (p ν q) is a tautology.
Solution: To show that this statement is a tautology, we will use logical
equivalences to demonstrate that it is logically equivalent to T.
(p Λ q) → (p ν q) ≡ ¬(p Λ q) ν (p ν q) by example on slide 21
≡ (¬ p ν ¬q) ν (p ν q) by the first De Morgan law
≡ (¬ p ν p) ν (¬ q ν q) by the associative and
communicative law for disjunction
≡TνT
≡T 37

 Note: The above examples can also be done using truth tables.
FUNCTIONALLY COMPLETE
SET OF
CONNECTIVES
Functionally Complete

• A set of logical operators is called

functionally complete if every
compound proposition is logically
equivalent to a compound
proposition involving only this
set of logical operators.
• , , and  form a functionally
complete set of operators.
Are (p(pq)) and (p  q)
equivalent?
(p(pq))
 p  (pq) DeMorgan
p  (pq) DeMorgan
p  (pq) Double Negation
(pp)(p q) Distribution
(pp)(p q) Commutative
F (p q) And Contradiction
 (p q)  F Commutative
 (p q) Identity
Are (p(pq))and (p  q)
equivalent?
• Even though both are expressed with
only , , and , it is still hard to tell
without doing a proof.
• What we need is a unique
representation of a compound
proposition that uses , , and .
• This unique representation is called
the Disjunctive Normal Form.
Example: Can we show that just  and  form a set
of functionally complete operands?
It is sufficient to show that p q can be written in
terms of  and . Then using DNF, we can write
every compound proposition in terms of  and .

(p  q)
 (p  q) Double negation (2)
 (pq ) DeMorgan
Example: Find an expression equivalent to
p  q that uses only conjunctions and
negations.
p q pq
How many minterms in the DNF?
T T T
T F F
F T T
F F T

The DNF of p  q is (pq)  (p q)  (p q).

Then, applying DeMorgan’s Law, we get that this is
equivalent to
[(pq)  (p q)  (p q)].
 Example: Now can we write an equivalent
statement to p  q that uses only disjunctions
and negations?
pq
 [(pq)  (p q)  (p q)] From Before
[(pq)  (pq)  (p  q)] DeMorgan
[(pq)  (pq)  (pq)] Doub. Neg.
[(pq)  (pq)  (pq)] DeMorgan
NORMAL FORMS
Normal Forms
 Normal forms are standard forms, sometimes

Discussion #10
called canonical or accepted forms.
 A logical expression is said to be in disjunctive
normal form (DNF) if it is written as a disjunction,

Chapter 1, Section 5
in which all terms are conjunctions of literals.
 Similarly, a logical expression is said to be in
conjunctive normal form (CNF) if it is written as a
conjunction of disjunctions of literals.

2/19
Normal Forms
The method to transform any two
logical expressions P and Q to some
Standard forms of expression P‟ and Q‟
such that a simple comparison of P‟
and Q‟, show whether P and Q are
equivalent (P≈Q). The standards forms
are called “Normal Forms” OR
“Canonical forms” .
Some Terminology
Elementary Product : In an logical
expressions, a product of the variables
and their negations is called an
“elementary product”.
For Example: Let P and Q be two atomic
variables Then ~Pꓥ Q,~Qꓥ P, Pꓥ ~Q and
Q ꓥ ~P are elementary product.
Elementary Sum : In an logical
expressions, a sum of the variables
and their negations is called an
“elementary sum”.
For Example: Let P and Q be two
atomic variables Then ~PVQ,~QVP,
PV~Q and Q V~P are elementary
product.
Types of Normal Forms

1. Disjunctive NormalForms(DNF).

2. Conjunctive Normal Forms(CNF).

 Disjunctive Normal Form (DNF)
Definition 1:
A logical expression is said to be in disjunctive
normal form if it is the sum of elementary
products.
Definition 2:
A logical expression is said to be in disjunctive
normal form if it is written as a disjunction, in
which all terms are conjunctions of literals.
Definition 3 : A disjunction of conjunctions where
every variable or its negation is represented once in
each conjunction (a minterm).Each minterm appears
only once
 DNF
 Disjunctive Normal Form (DNF)
( ..  ..  .. )  ( ..  ..  .. )  …  ( ..  .. )

Discussion #10
Term Literal, i.e. P or P

Chapter 1, Section 5
EXAMPLE:
1. PV(Q∧R) ,PV(~Q ∧R) ,(P  Q)  (P  Q)
and P  (Q  R) are in disjunctive
normal form.
2. P∧(QVR) are not in disjunctive
normal form. 8/19
Disjunctive Normal Form

Example: DNF of pq is

(pq)(pq).

(pq)  (pq)
Truth Table

p q pq (pq)  (pq)

T T F F
T F T T
F T T T
F F F F
Method to construct DNF
• Construct a truth table for the
proposition.
• Use the rows of the truth table where
the proposition is True to construct
minterms
• If the variable is true, use the
propositional variable in the minterm
• If a variable is false, use the negation of
the variable in the minterm
• Connect the minterms with „‟s.
Example: How to find the DNF of (p q)r
p q r (p q) r (p q)r
T T T T F F
T T F T T T
T F T T F F
T F F T T T
F T T T F F
F T F T T T
F F T F F T
F F F F T T
There are five sets of input that make the statement
true. Therefore there are five minterms.
p q r (p q) r (p q)r
T T T T F F
T T F T T T
T F T T F F
T F F T T T
F T T T F F
F T F T T T
F F T F F T
F F F F T T
From the truth table we can set up the DNF
(p q)r  (pqr)  (pqr) 
(pqr)  (pqr)  (pqr)
DNF Expression Generation

Discussion #10
P Q R  The only definition of
 is the truth table
T T T F
T T F T (P  Q  R)
(P  Q  R)

Chapter 1, Section 5
T F T T
T F F F
minterms
F T T F
F T F F
F F T T (P  Q  R)
F F F F

14/19
  (P  Q  R)  (P  Q  R)  (P  Q  R)
DNF and CNF
 Disjunctive Normal Form (DNF)
( ..  ..  .. )  ( ..  ..  .. )  …  ( ..  .. )

Discussion #10
Term Literal, i.e. P or P
Examples: (P  Q)  (P  Q)

Chapter 1, Section 5
P  (Q  R)

• Conjunctive Normal Form (CNF)

( ..  ..  .. )  ( ..  ..  .. )  …  ( ..  .. )
Examples: (P  Q)  (P  Q)
P  (Q  R)
15/19
Logical Operators

 - Disjunction Do we need all these?

 - Conjunction
 - Negation
 - Implication pq  p  q
 - Exclusive or (p  q)  (p  q)
 - Biconditional p  q 
(pq)  (qp) 
(p  q)  (q  p)
Functionally Complete

• A set of logical operators is called

functionally complete if every
compound proposition is logically
equivalent to a compound
proposition involving only this
set of logical operators.
• , , and  form a functionally
complete set of operators.
Are (p(pq)) and (p  q)
equivalent?
(p(pq))
 p  (pq) DeMorgan
p  (pq) DeMorgan
p  (pq) Double Negation
(pp)(p q) Distribution
(pp)(p q) Commutative
F (p q) And Contradiction
 (p q)  F Commutative
 (p q) Identity
Are (p(pq))and (p  q)
equivalent?
• Even though both are expressed with
only , , and , it is still hard to tell
without doing a proof.
• What we need is a unique
representation of a compound
proposition that uses , , and .
• This unique representation is called
the Disjunctive Normal Form.
Disjunctive Normal Form
• A disjunction of conjunctions where every
variable or its negation is represented once in
each conjunction (a minterm)
• each minterm appears only once
Example: DNF of pq is
(pq)(pq).

(pq)  (pq)
Truth Table

p q pq (pq)  (pq)

T T F F
T F T T
F T T T
F F F F
Method to construct DNF
• Construct a truth table for the
proposition.
• Use the rows of the truth table where
the proposition is True to construct
minterms
• If the variable is true, use the
propositional variable in the minterm
• If a variable is false, use the negation of
the variable in the minterm
• Connect the minterms with „‟s.
Example: How to find the DNF of (p q)r
p q r (p q) r (p q)r
T T T T F F
T T F T T T
T F T T F F
T F F T T T
F T T T F F
F T F T T T
F F T F F T
F F F F T T
There are five sets of input that make the statement
true. Therefore there are five minterms.
p q r (p q) r (p q)r
T T T T F F
T T F T T T
T F T T F F
T F F T T T
F T T T F F
F T F T T T
F F T F F T
F F F F T T
From the truth table we can set up the DNF
(p q)r  (pqr)  (pqr) 
(pqr)  (pqr)  (pqr)
Example: Can we show that just  and  form a set
of functionally complete operands?
It is sufficient to show that p q can be written in
terms of  and . Then using DNF, we can write
every compound proposition in terms of  and .

(p  q)
 (p  q) Double negation (2)
 (pq ) DeMorgan
Example: Find an expression equivalent to
p  q that uses only conjunctions and
negations.
p q pq
How many minterms in the DNF?
T T T
T F F
F T T
F F T

The DNF of p  q is (pq)  (p q)  (p q).

Then, applying DeMorgan’s Law, we get that this is
equivalent to
[(pq)  (p q)  (p q)].
 Example: Now can we write an equivalent
statement to p  q that uses only disjunctions
and negations?
pq
 [(pq)  (p q)  (p q)] From Before
[(pq)  (pq)  (p  q)] DeMorgan
[(pq)  (pq)  (pq)] Doub. Neg.
[(pq)  (pq)  (pq)] DeMorgan
Converting Expressions to DNF or
CNF

Discussion #10
The following procedure converts an expression to DNF or CNF:
1. Remove all  and .

Chapter 1, Section 5
2. Move  inside. (Use De Morgan’s law.)
3. Use distributive laws to get proper form.
Simplify as you go. (e.g. double-neg., idemp., comm., assoc.)

28/19
 CNF Conversion Example
( ..  ..  .. )  ( ..  ..  .. )  …  ( ..  .. )

((P  Q)  R  (P  Q))
 ((P  Q)  R  (P  Q))

Discussion #10
impl.
 (P  Q)  R  (P  Q) deM.
 (P  Q)  R  (P  Q) deM.
(DNF)  (P  Q)  R  (P  Q) double neg.

Chapter 1, Section 5
 ((P  R)  (Q  R))  (P  Q) distr.
 ((P  R)  (P  Q))  distr.
((Q  R)  (P  Q))
 (((P  R)  P)  ((P  R)  Q))  distr.
(((Q  R)  P)  ((Q  R)  Q))
 (P  R)  (P  R  Q)  (Q  R) assoc. comm. idemp.
29/19
 CNF Conversion Example
( ..  ..  .. )  ( ..  ..  .. )  …  ( ..  .. )

((P  Q)  R  (P  Q))
 ((P  Q)  R  (P  Q))

Discussion #10
impl.
 (P  Q)  R  (P  Q) deM.
 (P  Q)  R  (P  Q) deM.
(DNF)  (P  Q)  R  (P  Q) double neg.

Chapter 1, Section 5
 ((P  R)  (Q  R))  (P  Q) distr.
 ((P  R)  (P  Q))  distr.
((Q  R) CNF  (P  Q))
 (((P
Using thecommutative
R)  P) and  R)  Q)) 
((Pidempotent distr.
laws on the previous step and then the
(((Q  R)  P)  ((Q  R)  Q))
distributive law, we obtain this formula
 as  R)
(Pthe  (P  normal
conjunctive R  Q)form. (Q  R) assoc. comm. idemp.
30/19
 CNF Conversion Example
( ..  ..  .. )  ( ..  ..  .. )  …  ( ..  .. )
(P  R)  (P  R  Q)
((P  Q)  R  (P  Q))
 (Q  R)
 ((P  Q)  R  (P  Q))

Discussion #10
impl.
 (P  R)  (P  R  Q)
 (P  Q)  R  (P  Q)  (F  Q deM.
R) - ident.
 (P  Q)  R  (P  Q) (P  R)  ((PdeM.  F)
(DNF)  (P  Q)  R  (P  Q)  (Q  R))
double neg. distr.

Chapter 1, Section 5
- comm.,
 (P  R)  (Fdistr.
 ((P  R)  (Q  R))  (P  Q)
 ((P  R)  (P  Q))   (Q  R)) - dominat.
distr.
((Q  R)  (P  Q))  (P  R)  (Q  R) - ident.
 (((P  R)  P)  ((P  R)  Q))  distr.
(((Q  R)  P)  ((Q  R)  Q))
 (P  R)  (P  R  Q)  (Q  R) assoc. comm. idemp.
31/19
DNF Expression Generation

Discussion #10
P Q R  The only definition of
 is the truth table
T T T F
T T F T (P  Q  R)
(P  Q  R)

Chapter 1, Section 5
T F T T
T F F F
minterms
F T T F
F T F F
F F T T (P  Q  R)
F F F F

32/19
  (P  Q  R)  (P  Q  R)  (P  Q  R)
CNF Expression Generation
1. Find .
2.
3.
Find the DNF of .
}
Form a
Then, use De Morgan’s law to get the conjunction of

Discussion #10
CNF of  (i.e. ()  ) max terms

P Q   max terms

Chapter 1, Section 5
T T T F
T F F T (P  Q) (P  Q)
F T T F
F F F T (P  Q) (P  Q)

  (P  Q)  (P  Q) DNF of 

  f  ((P  Q)  (P  Q))
 (P  Q)  (P  Q) De Morgan’s 33/19

 (P  Q)  (P  Q) De Morgan’s, double neg.

 Valid Arguments in Propositional Logic

1
Argument

• An argument in propositional logic is a sequence of propositions. All

but the final proposition in the argument are called premises and the
final proposition is called the conclusion.

Premises ⇒ Conclusion
Example:
“If you have a current password, then you can log onto the network.”
“You have a current password.” 𝑝→𝑞
𝑝
Therefore, ----------------
“You can log onto the network.” ∴𝑞

2
• An argument is valid if the truth of all its premises implies that the
conclusion is true.

• An argument form in propositional logic is a sequence of compound

propositions involving propositional variables.
• An argument form is valid if no matter which particular propositions
are substituted for the propositional variables in its premises, the
conclusion is true if the premises are all true.
• The conclusion is true if the premises are all true.

3
Example:
• Either team A or Team B will win the match
• Team B lost
• Therefore Team A won
----------------------------------------------
The general form of this argument is:
Either P or Q
Not P
Therefore Q
(P ∨ Q) ∧ ┐P→Q , or

4
 Rules of Inference for Propositional Logic

• We can always use a truth table to show that an argument form is

valid. We do this by showing that whenever the premises are true,
the conclusion must also be true.

5
Checking the validity of an Argument form
• Step 1: Construct truth table for the premises and conclusion.
• Step 2: Find the rows in which all the premises are true(critical rows).
• Step 3: Check conclusion of all critical rows.
a) If in each critical rows the conclusion is true then the argument is
valid.
b) If there is a row in which conclusion is false then the argument form
is invalid.

6
Example:
Determine whether the following argument is valid or invalid
P q ¬𝒑 𝒑→𝒒 ┐q
𝑃→𝑞 T T F T F Formal
¬𝑝 T F F F T
∴ ¬𝑞
F T T T F
F F T T T

Solution
put all premises true:
p→q=T Informal
┐p = T, then p = F
Now, put q = T. So, we still have p → q = T, but q = T, Then ┐q = F.
The conclusion is False whereas all premises are true, Therefor, the argument is invalid.

7
Example : Determine whether the following argument is valid or invalid
(Hint: use informal method) 𝑝→𝑞
𝑞→ 𝑝→𝑟
𝑝
∴𝑟
Solution:
put all premises true: (p → q) = T
q → (p → r) = T
p=T
.........................................
Since p = T and (p → q) = T, then q = T
Now, since q = T and q → (p → r) = T then Q := (p → r) = T
We have p = T and (p → r) = T then r must be true. Therefore r = T and
the argument is valid.

8
Exercise:
Determine whether the following argument is valid or invalid:

𝑝 → ¬𝑟
𝑟 → (𝑝 → 𝑞)
𝑟→𝑝
∴ ¬𝑝 → ¬𝑞

9
Methods of Proof
Discrete Mathematics
SLOT-6

1
 PROOF
Proof: valid arguments that establish the
truth of a mathematical statement
Argument: a sequence of statements that
end with a conclusion
Valid: the conclusion or final statement of
the argument must follow the truth of
proceeding statements or premise of the
argument

2
 Argument and inference
• An argument is valid if and only if it is
impossible for all the premises to be true
and the conclusion to be false
• Rules of inference: use them to deduce
(construct) new statements from statements
that we already have
• Basic tools for establishing the truth of
statements

3
 The purpose of rules of inference
• We use rules of inference to construct valid
arguments.

• A valid argument is one in which it is not

possible for the conclusion to be false if the
premises are true.

• The argument is valid iff the truth of all

premises implies the conclusion is true

4
 Rules of inference for propositional logic
• Can always use truth table to show an
argument form is valid
• For an argument form with 10
propositional variables, the truth table
requires 210 rows

5
 Inference Rules - General Form
• Inference Rule –
• Pattern establishing that if we know that a set of
hypotheses are all true, then a certain related
conclusion statement is true.
• Hypothesis 1
Hypothesis 2 …
 conclusion “” means “therefore”

6
 Inference Rules & Implications

Each logical inference rule corresponds to an

implication that is a tautology.
Hypothesis 1 Inference rule
Hypothesis 2 …
 conclusion
Corresponding tautology:
((Hypoth. 1)  (Hypoth. 2)  …)  conclusion

7
 How to determine the validity of
argument?
The argument form with premises
p1 , p2 ,, pn and conclusion is valid when

( p1  p2    pn )is
aq is a tautology

8
 Modus Ponens
Consider (p  (p→q)) → q

p q p→q p(p→q)) (p(p→q)) → q

p
T T T T T pq
T F F F T q
F T T F T
F F T F T

9
 Modus Ponens example
Assume you are given the following two
statements:
p
 “you are in this class”
 “if you are in this class, you will get a grade” pq
q
Let p = “you are in this class”
Let q = “you will get a grade”

By Modus Ponens, you can conclude that you

will get a grade

10
 Modus Tollens
Assume that we know: ¬q and p → q
 Recall that p → q = ¬q → ¬p
Thus, we know ¬q and ¬q → ¬p
We can conclude ¬p
q
pq
 p

11
 Modus Tollens example
Assume you are given the following two
statements:
q
 “you will not get a grade”
 “if you are in this class, you will get a grade” pq
 p
Let p = “you are in this class”
Let q = “you will get a grade”

By Modus Tollens, you can conclude that you

are not in this class

12
 Addition & Simplification
Addition: If you know
that p is true, then p  q p
will ALWAYS be true pq

Simplification: If p  q is
true, then p will pq
ALWAYS be true p

13
 Example of proof
Example 6 of Rosen, section 1.5
We have the hypotheses:
 “It is not sunny this afternoon and it ¬p  q
p is colder than yesterday”
q  “We will go swimming only if it is r→p
sunny”
r
 “If we do not go swimming, then we ¬r → s
s will take a canoe trip”
t  “If we take a canoe trip, then we will s→t
be home by sunset”
Does this imply that “we will be t
home by sunset”?
14
 Example of proof
1. ¬p  q 1st hypothesis
2. ¬p Simplification using step 1
3. r→p 2nd hypothesis
4. ¬r Modus tollens using steps 2 & 3
5. ¬r → s 3rd hypothesis
6. s Modus ponens using steps 4 & 5
7. s→t 4th hypothesis
8. t Modus ponens using steps 6 & 7
p q
pq pq pq
p q  p 15
 More rules of inference
Conjunction: if p and q are true p
separately, then pq is true q
pq pq
Disjunctive syllogism: If pq is
true, and p is false, then q must p
be true q
pq
Resolution: If pq is true, and p  r
¬pr is true, then qr must be true
q  r
pq
Hypothetical syllogism: If p→q is qr
true, and q→r is true, then p→r
must be true pr
16
 Example of proof
question 4
Given the hypotheses:
 “If it does not rain or if it is not (¬r  ¬f) →
foggy, then the sailing race will (s  l)
be held and the lifesaving
demonstration will go on”
 “If the sailing race is held, then s→t
the trophy will be awarded”
 “The trophy was not awarded” ¬t
r
Can you conclude: “It rained”? 17
 Example of proof
1. ¬t 3rd hypothesis
2. s→t 2nd hypothesis
3. ¬s Modus tollens using steps 2 & 3
4. (¬r¬f)→(sl) 1st hypothesis
5. ¬(sl)→¬(¬r¬f) Contrapositive of step 4
6. (¬s¬l)→(rf) DeMorgan’s law and double negation law
7. ¬s¬l Addition from step 3
8. rf Modus ponens using steps 6 & 7
9. r Simplification using step 8
p q
pq p pq pq
q pq p  p 18
19
 Example
 “It is not sunny this
afternoon and it is colder
than yesterday” p  q 1)p  q hypothesis
 “We will go swimming 2)p simplication using (1)
only if it is sunny” r  p 3)r  p hypothesis
 “If we do not go 4)r modus tollens using (2) and (3)
swimming, then we will 5)r  s hypothesis
take a canoe trip” r  s 6) s modus ponens using (4)
 “If we take a canoe trip, 7) s  t hypothesis
then we will be home by 8)t modus ponens using (6) and (7)
sunset”
s t

Can we concludet
“We will be home by sunset”?
20
 Example
 “If you send me an email
message, then I will finish
1) p  q hypothesis
my program” pq 2)q  p contrapositive of (1)
 “If you do not send me an 3)p  r hypothesis
email message, then I will 4)  q  r hypotheical syllogism using (2) and (3)
go to sleep early” p  r 5)r  s hypothesis
 “If I go to sleep early, then 6)  q  s hypothetical syllogism using (4) and (5)
I will wake up feeling
refreshed”
rs

 “If I do not finish writing

the program, then I will
wake up feeling
refreshed” q  s
21
 WRITE SHORT NOTES ON CONSISTENCY OF PREMISES

A set of formulas A1 ,A2 ,A3,……..Am is

said to be consistent if their conjunction
has a truth value T for some assignment of
the truth values of the atomic variables
appearing A1,A2,……Am .
If for every assignment of the truth values to
the atomic variables at least one of the
formulas A1,A2,A3,……Am is false, so that
their conjunction is identically false , then the
formulas A1,A2,…….,Am are called
inconsistent. 22
WRITE SHORT NOTES ON CONSISTENCY OF PREMISES CONTD..

Alternatively, a set of formula A1,A2,……Am is

inconsistent if their conjunction implies a
contradiction, that is ,
A1∧ A2∧ A3………∧ Am → B∧ B’,where B is
any formula . It may be noted BꓥB’, is a
contradiction and it is necessary and sufficient
for the implication that A1 ∧ A2 ∧ ……..Am is
contradiction.
This notion of inconsistency is used in a
procedure called proof by contradiction or
reduction and absurd or indirect method of
proof .
23
 University of Hawaii

Predicates
and
Quantifiers
 Previously Concept…
 In predicate logic, a predicate is modeled as a
proposional function P(·) from subjects to
propositions.
 P(x): “x is a prime number” (x: any subject)
 P(3): “3 is a prime number.” (proposition!)

 Propositional functions of any number of

arguments, each of which may take any
grammatical role that a noun can take
 P(x,y,z): “x gave y the grade z”
 P(Mike,Mary,A): “Mike gave Mary the grade A.”
4-
2
 L

Universe of Discourse (U.D.) University of Hawaii

o
g

 The power of distinguishing subjects from

predicates is that it lets you state things about
many objects at once.
 e.g., let P(x) = “x + 1  x”. We can then say,
“For any number x, P(x) is true” instead of
(0 + 1  0)  (1 + 1  1)  (2 + 1  2)  ...

 The collection of values that a variable x can

take is called x’s universe of discourse or
the domain of discourse (often just referred
to as the domain).
 Log

Quantifier Expressions
University
of Hawaii

 Quantifiers provide a notation that allows us

to quantify (count) how many objects in the
universe of discourse satisfy the given
predicate.
 “” is the FORLL or universal quantifier.
x P(x) means for all x in the domain, P(x).
 “” is the XISTS or existential quantifier.
x P(x) means there exists an x in the domain
(that is, 1 or more) such that P(x).
 Lo

The Universal Quantifier 

g
Univer
sity of
Hawaii

 x P(x): For all x in the domain, P(x).

 x P(x) is
 true if P(x) is true for every x in D (D: domain

of discourse)
 false if P(x) is false for at least one x in D

 For every real number x, x  0 TRUE

2

 For every real number x, x2 – 1  0 FALSE

 A counterexample to the statement x P(x) is a

value x in the domain D that makes P(x) false
 What is the truth value of x P(x) when the
domain is empty? TRUE
 L

The Universal Quantifier 

o
g
Univ
ersit

 If all the elements in the domain can be listed as x1, y of

Haw
aii

x2,…, xn then, x P(x) is the same as the

conjunction:
P(x1)  P(x2)  ···  P(xn)
 Example: Let the domain of x be parking spaces at
UH. Let P(x) be the statement “x is full.” Then the
universal quantification of P(x), x P(x), is the
proposition:
 “All parking spaces at UH are full.”
 or “Every parking space at UH is full.”
 or “For each parking space at UH, that space is full.”
 The Existential Quantifier 
 x P(x): There exists an x in the domain (that
is, 1 or more) such that P(x).
 x P(x) is
 true if P(x) is true for at least one x in the
domain
 false if P(x) is false for every x in the domain

 What is the truth value of x P(x) when the

domain is empty? FALSE
 If all the elements in the domain can be listed as
x1, x2,…, xn then, x P(x) is the same as the
disjunction:
P(x1)  P(x2)  ···  P(xn)
 The Existential Quantifier 
 Example:
Let the domain of x be parking spaces at
UH. Let P(x) be the statement “x is full.”
Then the existential quantification of P(x),
x P(x), is the proposition:
 “Some parking spaces at UH are full.”
 or “There is a parking space at UH that is
full.”
 or “At least one parking space at UH is full.”
Quantifiers and First Order
Logic ( Another Definition)
• Predicate or Propositional Function

01/01/2022
• Let x be a variable and D be a set; P(x) is a sentence
• Then P(x) is called a predicate or propositional
function with respect to the set D if for each value of x
in D, P(x) is a statement; i.e., P(x) is true or false
• Moreover, D is called the domain (universe) of
discourse and x is called the free variable
Quantifiers and First Order Logic
( Another Definition)
• Universal Quantifier

01/01/2022
• Let P(x) be a predicate and let D be the domain of
the discourse. The universal quantification of P(x) is
the statement:
• For all x, P(x) or
• For every x, P(x)
• The symbol is read as “for all and every”
•
x, P ( x) or x  D, P( x)
• Two-place predicate: x, y, P( x, y )
Quantifiers and First Order Logic
( Another Definition)
• Existential Quantifier

01/01/2022
• Let P(x) be a predicate and let D be the universe of
discourse. The existential quantification of P(x) is the
statement:
• There exists x, P(x)
• The symbol is read as “there exists”
• x  D, P( x) or x, P( x)
• Bound Variable
• The variable appearing in: x, P ( xor) x, P( x)
Quantifiers and First Order Logic
• Negation of Predicates (DeMorgan’s Laws)

01/01/2022
• x, P ( x )  x, P ( x )
• Example:
• If P(x) is the statement “x has won a race” where the
domain of discourse is all runners, then the universal
quantification of P(x) is x, P ( x ), i.e., every runner
has won a race. The negation of this statement is “it is
not the case that every runner has won a race.
Therefore there exists at least one runner who has not
won a race. Therefore: x, P ( x )
•
x, P( x)  x, P( x)
 L

Free and Bound Variables

o
g
Univ
ersit
y of
Haw

 An expression like P(x) is said to have a freeaii

variable x (meaning, x is undefined).

 A quantifier (either  or ) operates on an

expression having one or more free variables,
and binds one or more of those variables, to
produce an expression having one or more
bound variables.
 Example of Binding
 P(x,y) has 2 free variables, x and y.
• bound variable . [Which is which?]
 x P(x,y) has 1 free variable , and one
 “P(x), where x = 3” is another way to bind x.
 An expression with zero free variables is a bona-fide (actual)
proposition.
 An expression with one or more free variables is not
a proposition:

• e.g. x P(x,y) = Q(y)

Scope of a Variable in an Expression(or Bound
Varaible & free variable ) Some Example Extra
• The parentheses or brackets are used wisely to identify the
scope of the variable.
– (x) ((y)[P(x,y) V Q(x,y)]  R(x))
• Scope of (y) is P(x,y) V Q(x,y) while the scope of
(x) is the entire expression
– (x)S(x) V (y)R(y)
• Scope of (x) is S(x) while the scope of (y) is R(y)
– (x)[P(x,y)  (y) Q(x,y)]
• Scope of variable y is not defined for P(x,y) hence y
is called a free variable. Such expressions might not
have a truth value at all.
• P(x): x > 0; P(y)^ P(5), P(y) V P(5).

– What is the truth of the wff (x)(A(x) Λ (y)[B(x,y) 

C(y)]) ,
where A(x) is “x > 0” , B(x, y) is “x > y”, C(y) is “y  0”,
and x is
the domain of positive integers and y is the domain
of all integers?
 Quantifiers with Restricted Domain
 Sometimes the universe of discourse is
restricted within the quantification, e.g.,

 x0 P(x) is shorthand for

“For all x that are greater than zero, P(x).”
= x (x  0  P(x))
 x0 P(x) is shorthand for
“There is an x greater than zero such that
P(x).”
= x (x  0  P(x))
 Translating from English
 Express the statement “Every student in this
class has studied calculus” using predicates
and quantifiers.
 Let C(x) be the statement: “x has

studied calculus.”
 If domain for x consists of the students in

this class, then

 it can be translated as x C(x)

or
 If domain for x consists of all people
 Let S(x) be the predicate: “x is in this class”
 Translation: x (S(x)  C(x))
 Translating from English
 Express the statement “Some students in this
class has visited Mexico” using predicates and
quantifiers.
 Let M(x) be the statement: “x has visited

Mexico”
 If domain for x consists of the students in this

class, then
it can be translated as x M(x)

or
 If domain for x consists of all people

 Let S(x) be the statement: “x is in this class”

 Then, the translation is x (S(x)  M(x))

 Translating from English
University
of Hawaii

 Express the statement “Every student in this

class has visited either Canada or Mexico”
using predicates and quantifiers.
 Let C(x) be the statement: “x has visited
Canada” and M(x) be the statement: “x has
visited Mexico”
 If domain for x consists of the students in
this class, then
 it can be translated as x (C(x)  M(x))
Class Exercises
• Using predicate symbols and appropriate quantifiers,
write the symbolic form of the following English
statement:
– D(x) is “x is a day”; M is “Monday”; T is “Tuesday”.
– S(x) is “x is sunny”; R(x) is “x is rainy”.
– Some days are sunny and rainy
– It is always a sunny day only if it is a rainy day
– It rained both Monday and Tuesday
– Every day that is rainy is not sunny
Answers
• D(x) is “x is a day”; M is “Monday”; T is “Tuesday”.
• S(x) is “x is sunny”; R(x) is “x is rainy”.

• Some days are sunny and rainy

– (x) S(x) Λ R(x) Λ D(x)
• It is always a sunny day only if it is a rainy day
– (x) [S(x) Λ D(x)  R(x) Λ D(x)]
• It rained both Monday and Tuesday
– R(M) Λ R(T)
• Every day that is rainy is not sunny
– (x) [R(X) Λ D(x)  S’(x)]
 Negations of Quantifiers
University
of Hawaii

 x P(x): “Every student in the class has taken

a course in calculus” (P(x): “x has taken a
course in calculus”)
 “Not every student in the class … calculus”

x P(x)  x P(x)

 Consider x P(x): “There is a student in the
class who has taken a course in calculus”
 “There is no student in the class who has

taken a course in calculus”

x P(x)  x P(x)
 Negations of Quantifiers
 Definitions of quantifiers: If the domain = {a, b, c,…}
 x P(x)  P(a)  P(b)  P(c)  ∙∙∙

 x P(x)  P(a)  P(b)  P(c)  ∙∙∙

 From those, we can prove the laws:

 x P(x)  (P(a)  P(b)  P(c)  ∙∙∙ )

 P(a)  P(b)  P(c)  ∙∙∙

 x P(x)
 x P(x)  (P(a)  P(b)  P(c)  ∙∙∙ )

 P(a)  P(b)  P(c)  ∙∙∙

 x P(x)
 Which propositional equivalence law was used to
prove this?
Negations of Quantifiers

Theorem:
 Generalized De Morgan's laws for logic
1. x P(x)  x P(x)
2. x P(x)  x P(x)
Negations: Examples
 What are the negations of the statements
x (x2  x) and x (x2 = 2)?
 x (x2  x)  x (x  x)  x (x2  x)
2

 x (x = 2)  x (x = 2)  x (x2  2)

2 2

 Show that x(P(x)  Q(x)) and

x(P(x)  Q(x)) are logically equivalent.
 x(P(x)  Q(x))  x (P(x)  Q(x))
 x (P(x)  Q(x))
 x (P(x)  Q(x))
Inference with quantified statements

Instantiation:
c is one particular
member
of the domain

Generalization:
for an arbitrary member
c
Example
• “Everyone in this discrete mathematics has taken a course in
computer science” and “Marla is a student in this class” imply
“Marla has taken a course in computer science”

1.x(d ( x)  c( x)) premise

2.d ( Marla)  c( Marla) universal instantiation from (1)
3.d ( Marla) premise
4.c( Marla) modus ponens from (2) and (3)
27
Example
• “A student in this class has not read the book”, and
“Everyone in this class passed the first exam” imply
“Someone who passed the first exam has not read the
book”
1.x(c( x)  b( x)) premise
2.c(a )  b(a ) existential instantiation from (1)
3.c(a ) simpliciation from (2)
4.x(c( x)  p ( x) premise
5.c(a )  p (a ) universal instantiation from (4)
6. p ( a ) modus ponens from (3) and (5)
7.b(a ) simplication from (2)
8. p ( a )   b ( a ) conjunction of (6) and (7)
9.x( p ( x)  b( x)) existential generalization form (8)
Universal modus ponens
• Use universal instantiation and modus ponens to derive new
rule
x( p ( x)  q ( x))
p (a ), where a is a particular element in the domain
 q(a)
• Assume “For all positive integers n, if n is greater than 4, then
n2 is less than 2n” is true. Show 1002<2100
Universal modus tollens
• Combine universal modus tollens and universal instantiation

x( p ( x)  q ( x))
q (a ), where a is a particular element in the domain
 p ( a )
Proof Methods
• Proving pq
• Direct proof: Assume p is true, and prove q.
• Indirect proof: Assume q, and prove p.
• Trivial proof: Prove q true.
• Vacuous proof: Prove p is true.
• Proving p
• Proof by contradiction: Prove p (r  r)
(r  r is a contradiction); therefore p must be false.
• Prove (a  b)  p
• Proof by cases: prove (a p) and (b p).
• More …
Direct Proof Example
• Definition: An integer n is called odd iff n=2k+1
for some integer k; n is even iff n=2k for some k.
• Axiom: Every integer is either odd or even.
• Theorem: (For all numbers n) If n is an odd
integer, then n2 is an odd integer.
• Proof: If n is odd, then n = 2k+1 for some integer
k. Thus, n2 = (2k+1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k)
+ 1. Therefore n2 is of the form 2j + 1 (with j the
integer 2k2 + 2k), thus n2 is odd. □
 Another Example

• Definition: A real number r is rational if there exist

integers p and q ≠ 0, with no common factors

33
other than 1 (i.e., gcd(p,q)=1), such that r=p/q. A
real number that is not rational is called irrational.
Indirect Proof
• Proving pq
• Indirect proof: Assume q, and prove p.

34
Indirect Proof Example
• Theorem: (For all integers n)
If 3n+2 is odd, then n is odd.
• Proof: Suppose that the conclusion is false, i.e.,

35
that n is even. Then n=2k for some integer k.
Then 3n+2 = 3(2k)+2 = 6k+2 = 2(3k+1). Thus
3n+2 is even, because it equals 2j for integer j =
3k+1. So 3n+2 is not odd. We have shown that
¬(n is odd)→¬(3n+2 is odd), thus its contra-
positive (3n+2 is odd) → (n is odd) is also true.
□
PROOF BY COUNTER
EXAMPLE &
MATHEMATICAL
INDUCTION
 CONTENTS
• PROOF BY COUNTER EXAMPLE
• MATHEMATICAL INDUCTION
 STRONG
INDUCTION
• 2ND PRINCIPLE OF MATHEMATICAL INDUCTION.
• USES DIFFERENT INDUCTIVE STEP THAN FIRST PRINCIPLE.
• STEPS
1. BASIC STEP : { SHOW P(0) IS TRUE }

2. INDUCTIVE HYPOTHESIS :
ASSUME P(K) IS TRUE FOR ALL NO ≤ K ≤ N.

3. INDUCTIVE STEP :
SHOW BASED ON ASSUMPTION THAT P(K+1) IS
TRUE.
3
8
EXAMPLE

3
9
SET THEORY
 Sets
 Definition: Well-defined collection of distinct objects
 Members or Elements: part of the collection
 Roster Method: Description of a set by listing the
elements, enclosed with braces
 Examples:
 Vowels = {a,e,i,o,u}

 Primary colors = {red, blue, yellow}

 Membership examples
 “a belongs to the set of Vowels” is written as:
a  Vowels
 “j does not belong to the set of Vowels:
j  Vowels

01/01/2022
 Basic notations for sets
For sets, we’ll use variables S, T, U, …
 We can denote a set S in writing by
listing all of its elements in curly
braces:
 {a, b, c} is the set of whatever 3 objects
are denoted by a, b, c.
 Set builder notation: For any
proposition P(x) over any universe of
discourse, {x|P(x)} is the set of all x
such that P(x).
e.g., {x | x is an integer where x>0
and x<5 }
3
 Sets
 Set-builder method

 A = { x | x  S, P(x) } or A = { x  S | P(x) }

 A is the set of all elements x of S, such that x

satisfies the property P

 Example: If X = {2,4,6,8,10}, then in set-builder

notation, X can be described as

 X = {n  Z | n is even and 2  n  10}

 In roaster form , each element can be explicitly

defined . For Example: V={ a,e,i,o,u} set of vowel.

01/01/2022
 Sets
 Standard Symbols which denote sets of numbers
 N : The set of all natural numbers (i.e.,all positive integers)
 Z : The set of all integers
 Z+ : The set of all positive integers
 Z* : The set of all nonzero integers
 E : The set of all even integers
 Q : The set of all rational numbers
 Q* : The set of all nonzero rational numbers
 Q+ : The set of all positive rational numbers
 R : The set of all real numbers
 R* : The set of all nonzero real numbers
 R+ : The set of all positive real numbers
 C : The set of all complex numbers
 C* : The set of all nonzero complex numbers

01/01/2022
 Sets
 Subsets

 “X is a subset of Y” is written as X  Y

 “X is not a subset of Y” is written as X Y

 Example:

 X = {a,e,i,o,u}, Y = {a, i, u} and

Z= {b,c,d,f,g}

 Y  X, since every element of Y is an element of X

 Y Z, since a  Y, but a  Z

01/01/2022
Sets
 Superset
 X and Y are sets. If X  Y, then “X is contained in
Y” or “Y contains X” or Y is a superset of X,
written Y  X
 Proper Subset
 X and Y are sets. X is a proper subset of Y if X 
Y and there exists at least one element in Y that
is not in X. This is written X  Y.
 Example:
 X = {a,e,i,o,u}, Y = {a,e,i,o,u,y}

 X  Y , since y  Y, but y  X

01/01/2022
Sets

 Set Equality
 X and Y are sets. They are said to be equal if every
element of X is an element of Y and every element of Y is
an element of X, i.e. X  Y and Y  X
 Examples:

 {1,2,3} = {2,3,1}

 X = {red, blue, yellow} and Y = {c | c is a primary

color} Therefore, X=Y
 Empty (Null) Set
 A Set is Empty (Null) if it contains no elements.

 The Empty Set is written as 

 The Empty Set is a subset of every set

01/01/2022
Sets

 Finite and Infinite Sets

 X is a set. If there exists a nonnegative integer n such
that X has n elements, then X is called a finite set with n
elements.
 If a set is not finite, then it is an infinite set.
 Examples:
 Y = {1,2,3} is a finite set
 P = {red, blue, yellow} is a finite set
 E , the set of all even integers, is an infinite set
  , the Empty Set, is a finite set with 0 elements

01/01/2022
Sets
 Cardinality of Sets
 Let S be a finite set with n distinct elements,
where n ≥ 0. Then |S| = n , where the
cardinality (number of elements) of S is n
 Example:
 If P = {red, blue, yellow}, then |P| = 3
 Singleton
 A set with only one element is a singleton
 Example:

 H = { 4 }, |H| = 1, H is a singleton

01/01/2022
Sets
 Power Set
 For any set X ,the power set of X ,written P(X),is
the set of all subsets of X
 Example:
 If X = {red, blue, yellow}, then P(X) = {  ,
{red}, {blue}, {yellow}, {red,blue}, {red,
yellow}, {blue, yellow}, {red, blue, yellow} }

 Universal Set
 An arbitrarily chosen, but fixed set

01/01/2022
 Sets
 Venn Diagrams
 Abstract visualization
of a Universal set, U
as a rectangle, with all
subsets of U shown as
circles.
 Shaded portion
represents the
corresponding set
 Example:
 In Figure 1, Set X,
shaded, is a subset
of the Universal set,
U

01/01/2022
 Set Operations and Venn
Diagrams
 Union of Sets

Example: If X = {1,2,3,4,5} and Y = {5,6,7,8,9}, then

XUY = {1,2,3,4,5,6,7,8,9}

01/01/2022
 Sets
 Intersection of Sets

Example: If X = {1,2,3,4,5} and Y = {5,6,7,8,9}, then X ∩ Y = {5}

01/01/2022
 Sets
 Disjoint Sets

Example: If X = {1,2,3,4,} and Y = {6,7,8,9}, then X ∩ Y = 

01/01/2022
 Sets
 Difference

• Example: If X = {a,b,c,d} and Y =

{c,d,e,f}, then X – Y = {a,b} and Y – X =
{e,f}

01/01/2022
 Sets

 Complement

The complement of a set X with respect to a universal set U,

denoted by X , is defined to be X = {x |x  U, but x  X}

Example: If U = {a,b,c,d,e,f} and X = {c,d,e,f}, then X = {a,b}

01/01/2022
 Sets

01/01/2022
Sets
 Ordered Pair
 X and Y are sets. If x  X and y  Y, then an
ordered pair is written (x,y)
 Order of elements is important. (x,y) is not
necessarily equal to (y,x)
 Cartesian Product
 The Cartesian product of two sets X and Y ,written X
× Y ,is the set
 X × Y ={(x,y)|x ∈ X , y ∈ Y}
 For any set X, X ×  =  =  × X
 Example:
 X = {a,b}, Y = {c,d}
 X × Y = {(a,c), (a,d), (b,c), (b,d)}
 Y × X = {(c,a), (d,a), (c,b), (d,b)}

01/01/2022
01/01/2022
Relations
 Binary Relations

• a relation between elements of two sets is a

subset of their Cartesian product (of ordered
pairs).
• Note the difference between a relation and a
function: in a relation, each a ∈ A can map to
multiple elements in B. Thus, relations are
generalizations of functions.
• If an ordered pair (a, b) ∈ R then we say that a
is related to b. We may also use the notation
aRb.
Relations
Relations (Graph View)
Relations (on a set)
Reflexivity
Symmetry I
Symmetry II
Symmetric Relations
Transitivity
Transitivity
Combining Relations
Composition and Powers
Power Examples
Equivalence Relations
Equivalence Classes I
Equivalence Classes II
Partitions I
Partitions II
Matrix Interpretation
Equivalence Relations (Example-I)
Equivalence Relations (Example-II)
Equivalence Relations (Example-III)
Equivalence Relations (Example-IV)
Equivalence Relations (Example-IV)
What is a Graph?
Definition − A graph (denoted as G=(V,E)) consists of a non-empty set of vertices or nodes V
and a set of edges E.

Example − Let us consider, a Graph is G=(V,E)

where V={a,b,c,d} and E={{a,b},{a,c},{b,c},{c,d}}

Degree of a Vertex − The degree of a vertex V of a graph G (denoted by deg (V)) is the number
of edges incident with the vertex V.

Vertex Degree Even / Odd

a 2 even
b 2 even
c 3 odd
d 1 odd

Even and Odd Vertex − If the degree of a vertex is even, the vertex is called an even vertex and
if the degree of a vertex is odd, the vertex is called an odd vertex.

Degree of a Graph − The degree of a graph is the largest vertex degree of that graph. For the
above graph the degree of the graph is 3.

The Handshaking Lemma − In a graph, the sum of all the degrees of all the vertices is equal to
twice the number of edges.

Types of Graphs
There are different types of graphs, which we will learn in the following section.

Null Graph
A null graph has no edges. The null graph of n

vertices is denoted by Nn

Simple Graph

A graph is called simple graph/strict graph if the graph is undirected and does not contain any
loops or multiple edges.

Multi-Graph

If in a graph multiple edges between the same set of vertices are allowed, it is called Multigraph.
In other words, it is a graph having at least one loop or multiple edges.
Directed and Undirected Graph

A graph G=(V,E)

is called a directed graph if the edge set is made of ordered vertex pair and a graph is called
undirected if the edge set is made of unordered vertex pair.

Connected and Disconnected Graph

A graph is connected if any two vertices of the graph are connected by a path; while a graph is
disconnected if at least two vertices of the graph are not connected by a path. If a graph G is
disconnected, then every maximal connected subgraph of G

is called a connected component of the graph G

.
Regular Graph

A graph is regular if all the vertices of the graph have the same degree. In a regular graph G of
degree r

, the degree of each vertex of G

is r.

Complete Graph

A graph is called complete graph if every two vertices pair are joined by exactly one edge. The
complete graph with n vertices is denoted by Kn
Cycle Graph

If a graph consists of a single cycle, it is called cycle graph. The cycle graph with n vertices is
denoted by Cn

Bipartite Graph

If the vertex-set of a graph G can be split into two disjoint sets, V1

and V2, in such a way that each edge in the graph joins a vertex in V1 to a vertex in V2, and there
are no edges in G that connect two vertices in V1 or two vertices in V2, then the graph G

is called a bipartite graph.

Complete Bipartite Graph

A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to
every single vertex in the second set. The complete bipartite graph is denoted by Kx,y

where the graph G contains x vertices in the first set and y

vertices in the second set.

Representation of Graphs
There are mainly two ways to represent a graph −

 Adjacency Matrix
 Adjacency List

Adjacency Matrix
An Adjacency Matrix A[V][V]

is a 2D array of size V×V where V is the number of vertices in a undirected graph. If there is an
edge between Vx to Vy then the value of A[Vx][Vy]=1 and A[Vy][Vx]=1, otherwise the value
will be zero. And for a directed graph, if there is an edge between Vx to Vy, then the value of
A[Vx][Vy]=1
, otherwise the value will be zero.

Adjacency Matrix of an Undirected Graph

Let us consider the following undirected graph and construct the adjacency matrix −

Adjacency matrix of the above undirected graph will be −

a b c d
a 0 1 1 0
b 1 0 1 0
c 1 1 0 1
d 0 0 1 0

Adjacency Matrix of a Directed Graph

Let us consider the following directed graph and construct its adjacency matrix −
Adjacency matrix of the above directed graph will be −

a b c d
a 0 1 1 0
b 0 0 1 0
c 0 0 0 1
d 0 0 0 0

Adjacency List

In adjacency list, an array (A[V])

of linked lists is used to represent the graph G with V number of vertices. An entry A[Vx]
represents the linked list of vertices adjacent to the Vx−th

vertex. The adjacency list of the undirected graph is as shown in the figure below −
Planar vs. Non-planar graph
Planar graph − A graph G

is called a planar graph if it can be drawn in a plane without any edges crossed. If we draw graph
in the plane without edge crossing, it is called embedding the graph in the plane.

Non-planar graph − A graph is non-planar if it cannot be drawn in a plane without graph edges
crossing.

Isomorphism
If two graphs G and H contain the same number of vertices connected in the same way, they are
called isomorphic graphs (denoted by G≅H

).
It is easier to check non-isomorphism than isomorphism. If any of these following conditions
occurs, then two graphs are non-isomorphic −

 The number of connected components are different

 Vertex-set cardinalities are different
 Edge-set cardinalities are different
 Degree sequences are different

Example

The following graphs are isomorphic −

Homomorphism
A homomorphism from a graph G

to a graph H is a mapping (May not be a bijective mapping)h:G→H such that −

(x,y)∈E(G)→(h(x),h(y))∈E(H). It maps adjacent vertices of graph G to the adjacent
vertices of the graph H

Properties of Homomorphisms

 A homomorphism is an isomorphism if it is a bijective mapping.

 Homomorphism always preserves edges and connectedness of a graph.
 The compositions of homomorphisms are also homomorphisms.
 To find out if there exists any homomorphic graph of another graph is a NPcomplete
problem.

Euler Graphs
A connected graph G
is called an Euler graph, if there is a closed trail which includes every edge of the graph G

. An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts and
ends at different vertices.

An Euler circuit is a circuit that uses every edge of a graph exactly once. An Euler circuit always
starts and ends at the same vertex. A connected graph G

is an Euler graph if and only if all vertices of G are of even degree, and a connected graph G

is Eulerian if and only if its edge set can be decomposed into cycles.

The above graph is an Euler graph as “a1b2c3d4e5c6f7g”

covers all the edges of the graph.

Hamiltonian Graphs
A connected graph G

is called Hamiltonian graph if there is a cycle which includes every vertex of G and the cycle is
called Hamiltonian cycle. Hamiltonian walk in graph G

is a walk that passes through each vertex exactly once.

If G

is a simple graph with n vertices, where n≥3 If deg(v)≥n2 for each vertex v, then the graph G

is Hamiltonian graph. This is called Dirac's Theorem.

If G

is a simple graph with n vertices, where n≥2 if deg(x)+deg(y)≥n for each pair of non-
adjacent vertices x and y, then the graph G

is Hamiltonian graph. This is called Ore's theorem.

Previous Page Print Page
Next Page
Advertisements