Discrete Structures

and Graph Theory

Discrete Structures and Graph Theory
• A branch of mathematics that uses algebra and arithmetic and involves
discrete elements is known as Discrete Mathematics.
.
• Reasoning and problem-solving capabilities are improved by discrete
mathematics.
Schema
Syllabus
Syllabus
Chapter 1

LOGIC
 Introduction
• Logic is a discipline that deals with methods of reasoning.
• It provides the rules by which one can determine whether any particular proof or argument is
valid or not.
• Logical reasoning is used in mathematics to prove theorems, in Computer Science to verify the
correctness of programs and to prove theorems, and in social sciences and everyday lives to
solve a multitude of problems.
• Indeed, we constantly are using logical reasoning.
• E.g. He tries to study hard.
He tries hard to study.

• Mere shifting of word change the entire meaning.

• To avoid such mishaps, a formal language is developed using symbols and well defined rules
for calculating with those symbols.

• This is symbolic logic.

 Prepositions
• A preposition or Statement is a declarative sentence which is either True or False, but
not both.

• Examples-
i. There are seven days in a week-True
ii. The earth is in spherical shape.-True
iii. 2+5=8 -False

• But,
1. X+3=5 -is not a preposition since its truth value depends on value of x.
2. Bring that Book- is a command, not a statement.

• The statements which can not be further split or broken down into simpler sentences
are called as Primary, Primitive or atomic statements.
 Logical Operations
1. Negation-
If p denotes a statement, then negation of P is ~ p or
e.g. p - I am going for a walk
~p –I am not going for a walk OR
It is not the case that I am going for a walk.

2. Conjunction (and)-
If p and q are statements, the compound statement ‘p and q’ is called as the
conjunction pf p and q.
It is denoted by p˄q.
Examples-
a) p:The sun is shining
q: The birds are singing
Then
p˄q: The sun is shining and the birds are singing.

b). Translate into symbolic form.

Rahul is poor but happy.

p: Rahul is poor.
q: Rahul is happy.

Symbolic form- p˄q

3. Disjunction (or)-
If p and q are statements, the compound statement ‘p or q’ is called as the
disjunction of p and q.
It is denoted by p˅q.
Examples-
p:There is an error in the program.
q: The data is wrong.
Then
p˅q: There is an error in the program or the data is wrong.
4. Conditional (If….then)
If p and q are statements, the compound statement ‘If p then q’ is called as
a conditional statement.
It is denoted by ‘p → q’

p is called the Antecedent or Hypothesis.

q is called the consequent.

e.g. p: Rajesh studies hard.

q:Rajesh will pass the exam.

p → q: If Rajesh studies hard, then he will pass the exam.

 Converse, Inverse and Contrapositive Prepositions
• If p → q is the conditional statement, then
1. q → p is called its Converse
2. ~ p → ~ q is called its Inverse
3. ~ q → ~ p is called its Contrapositive.

• Example 1 -Give the Converse and Contrapositive of the conditional.

If it rains, then I carry an umbrella.
Solution- p: It rains.
q: I carry an umbrella.
1. Converse of p → q is
q → p: If I carry an umbrella, then it rains.
2. Contrapositive of p → q is-
~ q → ~ p : If I do not carry an umbrella, then it does not rain.

• Example 2 –
• Put the statement into Symbolic form-
Unless I reach the station on time, I will miss the train.
Solution-
Let p: I reach the station on time.
q: I will miss the train.

Symbolic form- ~p→q

5. Biconditional (If and only if or iff)-
If p and q are statements, the compound statement ‘p if and only if q’ is
called as a biconditional statement.
It is denoted by p ↔q.

E.g.
1. An integer is even if and only if it is divisible by 2.
2. Two lines are parallel if and only if they have the same slope.
 Prepositional or Statement Form
• Using the logical connectives, defined above, we can construct or form an
expression.
• Examples of Statement form-
1. ~ (p˅q) →p
2. (p → q) ↔(p˄ ~ q)

• So we can construct any number of complicated statement forms from the

variables by using the logical connectives.
• A statement has no fixed truth value. It can be either
True(T or 1) or False(F or 0)
• Using the following statements,
p: I will study DSGT.
q:I will go to a movie.
r: I am in a good mood.
Write the following statements in symbolic form.
i. If I am not in a good mood, then I will go to a movie.
ii. I will not go to a movie and I will study DSGT.
iii. I will go to a movie only if I will not study DSGT.
iv. I will study DSGT, then I am in a good mood.
i. ~r → q
ii. ~q ˄ p
iii. q → ~p
iv. ~p → ~r
 Truth Tables
• A statement giving all possible truth values of a statement, corresponding to
the truth values assigned to its variables, is called truth table.
1. ~p (Negation) p ~p
T F
F T

2. p ˄q (AND)
P q p ˄q
T T T
T F F
F T F
F F F
3. p˅q (OR) P q p˅q
T T T
T F T
F T T
F F F

4. p → q(Conditional)
P q p→q
T T T
T F F
F T T
F F T
5.p ↔q(Biconditional)
P q p ↔q
T T T
T F F
F T F
F F T

6.p↑q (NAND)
P q p↑q
T T F
T F T
F T T
F F T
7. p ↓q(NOR)
P q p ↓q
T T F
T F F
F T F
F F T
8. p⨁q(EX-OR)
P q p⨁q
T T F
T F T
F T T
F F F
• Construct a truth table for- 1. ~[p ˄(p ˅ ~ q)]

p q ~q p˅~q p ˄(p ˅ ~ q) ~[p ˄(p ˅ ~ q)]

T T F T T F

T F T T T F

F T F F F T

F F T T F T

2. (~p ˅q) →q
 p q ~p (~p ˅q) (~p ˅q) →q
T T F T T
T F F F T
F T T T T
F F T T F

3. (~p →r) ˄p ↔q
 Tautology and Contradiction
• Tautology-A proposition P is a tautology if it is true under all circumstances.
It means it contains the only T in the final column of its truth table.
• Example: Prove that the statement (p⟶q) ↔(∼q⟶∼p) is a tautology.

p q p→q ~q ~p ~q⟶∼p (p→q)⟷( ~q⟶~p)

T T T F F T T
T F F T F F T
F T T F T T T
F F T T T T T

• As the final column contains all T's, so it is a tautology.

• Contradiction:
• A statement that is always false is known as a contradiction.
• Example: Show that the statement p ∧∼p is a contradiction.
p ∼p p ∧∼p
T F F
F T F

• Contigency:
A statement which is neither p q p →q p∧q (p →q)⟶ (p∧q )
Tautology nor contradiction T T T T T
is called a contigency. T F F F T
F T T F F
F F T F F
• Construct a truth table to determine whether each of the following is a
Tautology, a Contigency or a Contradiction.
1. p →(q→p)
2. (p ˄q ) ˄ ~(p ˅q)
 Propositional Equivalences
• Two statement forms are logically equivalent if both have the same truth
values.
• Example-
• 1. Prove p∧q and q∧p are logically equivalent.
p q p∧q q∧p
T T T T
T F F F
F T F F
F F F F

2. p and ∼ (∼p)
 Laws of Logic
1. Idempotent laws- p ˅p ≡ p
p∧p≡p
2. Commutative Laws- p ˅q ≡ q ˅ p
p∧q≡q∧p
3. Associative laws- (p∧q)∧r≡p∧(q∧r)
(p∨q)∨r≡p∨(q∨r)
4. Distributive laws: p∨(q∧r)≡(p∨q)∧(p∨r)
p∧(q∨r)≡(p∧q)∨(p∧r)
5. Absorption laws: p∨(p∧q)≡p
p∧(p∨q)≡p
6. De Morgan’s Laws: ∼(p∧q)≡ ∼ p∨ ∼ q
∼(p∨q)≡ ∼ p∧ ∼ q
7. Identity Laws: p∨T≡T p∧T≡p
p∨F≡p p∧F≡F
8. Complement/Inverse Laws: p ∨ ∼ p ≡ T p∧∼p≡F
∼T≡F ∼F≡T
∼ (∼ p)=p
9. Implication law: p ⟶ q= ∼ p ∨q
• Using laws of logic, show that ∼(∼ p ∧ q) ∧(p ˅ q) ≡p.
Solution-

∼(∼ p ∧ q) ∧(p ˅ q)
≡ (∼(∼ p) ˅ ∼ q) ∧(p ˅ q) (by De Morgan’s laws) ∼(p∧q)≡ ∼ p∨ ∼ q
≡ (p ˅ ∼ q) ∧(p ˅ q) (by complement law) ∼ (∼ p)=p
≡ p ˅(∼ q ∧ q) (by distributive law) p∨(q∧r)≡(p∨q)∧(p∨r)
≡ p ˅(q ∧ ∼ q) (by the commutative law) p ∧ q ≡ q ∧ p
≡p˅F (by the Complement law) p ∧ ∼ p ≡ F
≡p (by the identity law) p∨F≡p

• Prove- a ∧(∼ a ˅ b)= a ∧b

 Logical Implication
• Let s be the set of prepositions and r and s be prepositions generated by s.
• We say that r implies s, if r ⇒s is a tautology.
• We write r ⇒s to indicate this implication.
Example-
Show that p ⇒ (p˅q)

p q p˅q p→(p˅q)
T T T T
T F T T
F T T T
F F F T
 Quantifiers
• x+3=5 -not a preposition if x=2,becomes a preposition.
• An assertion that contains 1 or more variables is called a Predicate.
• A predicate P containing n variables x1,x2….xn is called n-place predicate.
• E.g. x is a city in India - P(x)
• The values which the variables may assume constitute a collection or set called
as the Universe of discourse.
• When we specify a value for a variable appearing in a predicate, we bind that
variable.
• A predicate becomes a preposition only when all its variables are bound.

• Consider, P(x):x+3=5
• Let the Universe of discourse be set of all integers.
• Binding x=-1,we get False preposition. x=2 True preposition.
 Quantifiers
• The second method of binding individual variables in a predicate is by Quantification
of variable.
• Types of Quantifiers-
• 1. Universal Quantifiers- If P(x) is a predicate with the individual variable x as an
argument, then the assertion ‘For all x P(x)’ is a statement in which the variable x is
said to be universally quantified.
• For all- ∀
• E.g. P(x)- predicate and x>=0 (integer), then the preposition ∀xP(x) is True.
But if x is any real number, then its False preposition.
2. Existential Quantifiers-Suppose, for predicate P(x), ∀xP(x) is false, but there exists
at lest 1 value of x for which P(x) is true, then we say that in this preposition, x is bound
by existential quantification.
There exists- ∃
∃x P(x) means there exists a value of x(in Universe of discourse) for which P(x) is true.
Examples- Let P(x,y) be a 2-phase predicate, then

∀y ∃x P(x,y)- For each value of y, there exists an x such that P(x,y) is true.
∃ y ∃x P(x,y)-There exists a value of x and a value of y such that P(x,y) is true.
∀y ∀ x P(x,y)- For all values of x and y, P(x,y) is true.
 Rules of Inference for Prepositional Calculus
• In logical reasoning, some prepositions are assumed to be true and based on
those assumptions, other prepositions are inferred or derived.

• The prepositions that are assumed to be true are called Premises or hypotheses.

• The prepositions derived by using rules of inferences is called a conclusion.

• The process of deriving conclusion based on assumption of premises is called a

valid argument.
1. Addition
If P is a premise, we can use Addition rule to derive P∨Q.

Example
Let P be the proposition, “He studies very hard” is true
Therefore − "Either he studies very hard Or he is a very bad student." Here Q is the proposition
“he is a very bad student”.

2. Conjunction
If P and Q are two premises, we can use Conjunction rule to derive P∧Q.

Example
Let P − “He studies very hard”
Let Q − “He is the best boy in the class”
Therefore − "He studies very hard and he is the best boy in the class"
3. Simplification
If P∧Q is a premise, we can use Simplification rule to derive P.

Example
"He studies very hard and he is the best boy in the class", P∧Q
Therefore − "He studies very hard“

4. Modus Ponens
If P and P→Q are two premises, we can use Modus Ponens to derive Q.

Example
"If you have a password, then you can log on to facebook", P→Q
"You have a password", P
Therefore − "You can log on to facebook"
5. Modus Tollens
If P→Q and ¬Q are two premises, we can use Modus Tollens to derive ¬P.

Example
"If you have a password, then you can log on to facebook", P→Q
"You cannot log on to facebook", ¬Q
Therefore − "You do not have a password "

6.Disjunctive Syllogism
If ¬P and P∨Q are two premises, we can use Disjunctive Syllogism to derive Q.

Example
"The ice cream is not vanilla flavored", ¬P
"The ice cream is either vanilla flavored or chocolate flavored", P∨Q
Therefore − "The ice cream is chocolate flavored”
7. Hypothetical Syllogism
If P→Q and Q→R are two premises, we can use Hypothetical Syllogism to derive P→R

Example
"If it rains, I shall not go to school”, P→Q
"If I don't go to school, I won't need to do homework", Q→R
Therefore − "If it rains, I won't need to do homework“
8. Constructive Dilemma
If (P→Q)∧(R→S) and P∨R are two premises, we can use constructive dilemma to derive Q∨S.

Example
“If it rains, I will take a leave”, (P→Q)
“If it is hot outside, I will go for a shower”, (R→S)
“Either it will rain or it is hot outside”, P∨R
Therefore − "I will take a leave or I will go for a shower"
9. Destructive Dilemma
If (P→Q)∧(R→S) and ¬Q∨¬S are two premises, we can use destructive dilemma to
derive ¬P∨¬R.

Example
“If it rains, I will take a leave”, (P→Q)
“If it is hot outside, I will go for a shower”, (R→S)
“Either I will not take a leave or I will not go for a shower”, ¬Q∨¬S
Therefore − "Either it does not rain or it is not hot outside"
• Test the validity of the following argument-
p⇒r
∼ p ⇒q
q ⇒s
∼r ⇒ s
∴

Solution-
p ⇒ r can be written as ∼r⇒∼p (If p → q, then ~ q → ~ p is called its Contrapositive)

(∼r⇒∼p) ∧(∼p⇒q) gives ∼r⇒q by hypothetical syllogism

(∼r⇒q) ∧(q ⇒s) gives ∼r ⇒ s by hypothetical syllogism.
Hence, the argument is valid.
• Check the validity of the following argument.
“If there was a ball game, then travelling was difficult. If they arrived on time, then travelling was not difficult.
They arrived on time. Therefore there was no ball game.”
Solution- Let, p: There was a ball game.
q:Travelling was difficult.
r:They arrive on time.
Then, Argument in Symbolic form-

Proof: Steps Reasons

1.r⟶∼q Premise(ii)
2.q ⟶∼r Step(1) and contrapositive(~ q → ~ p )
3.p⟶q Premise(i)
4.p ⟶∼r Step(3) & (2) and law of hypo. Syllogism
5.r Premise(iii)
6. ∼(∼r) Step(5) and complement law
7. ∴ ∼p Step 4 and 6 and modus Tollens
 Inference theory of predicate calculus
Rule of Inference Name
• To reach on a conclusion on quantified
statements, there are four rules of Rule US: Universal
Specification
inference which are collectively
called as Inference Theory of the
Predicate Calculus. Rule UG: Universal
• Rule US: Universal Specification – Generalization

From ∀(x)P(x), one can conclude P(y).

• Rule UG: Universal Generalization –
From P(c), one can conclude ∀xP(x) Rule ES: Existential
Specification
• Rule ES: Existential Specification –
From (∃x)P(x), one can conclude P(c)
• Rule EG: Existential Generalization –
Rule EG: Existential
From P(c), one can conclude (∃y)P(y). Generalization
Rule 1: (Universal Specification/Instantiation)
If a statement of the form ∀ x, P(x) is assumed to be true, then the universal quantifier can
be dropped to obtain P(c) is true for an arbitrary element c in the universe of discourse.

e.g. Every man is mortal, Socrates is a man. Therefore, Socrates is mortal.

Socrates is a member of universe of discourse of all men. This form of argument is called
instantiation because it consists of taking a particular instance of a statement.

Rule 2: (Universal Generalization)

If a statement P(c) is true for each element ‘c’ of the universe, then the universal
quantifier may be prefixed to obtain ∀x, P(x). In symbols
P(c) for all c
therefore ∀ x, P(x)
Rule 3: (Existential Specification)
If ∃x, P(x) is assumed to be true, then there is an element c in the universe of
discourse such that P(c) is true.
In symbolic notation ∃x, P(x)
therefore P(c) for some c

Rule 4: (Existential Generalization)

If P(c) is true for some element c in the universe of discourse, then ∃x, P(x),
P(x) is true. In symbols,
P(c) for some c
therefore ∃x, P(x)
• Universal Modus Ponens- The rule of universal instantiation can be combined
with modus ponens to obtain the rule called Universal Modus Ponens.

∀ x, if P(x) then Q(x)

P(a) for a particular a
∴Q(a)
• Universal Modus Tollens- The rule of universal instantiation can be combined
with modus tollens to obtain the rule called Universal Modus tollens.

∀ x, if P(x) then Q(x)

∼Q(a) for a particular a
∴∼P(a)
• Example1:
Show that (x) (H(x) ⟶ M(x)) ∧ H(s) ⇒ M(s).
This is a well - known argument known as the "Socrates argument" which is given by
All men are mortal.
Socrates is a man.
Therefore Socrates is mortal.
If we denote H(x) : x is a man, M(x) : x is a mortal and s : Socrates, we can put the
argument in the above form.
Solution:
(1) (x)(H(x)⟶M(x)) Hyptheses
(2) H(s) ⟶ M(s) Rule US, using(1)
(3) H(s) Hyptheses
(4) M(s) (2), (3) Simplification
 Normal Forms
• It is easy to find if a statement is T or F using truth table. But when the statements contain more variables or are of
complex form, then the method of truth table is inefficient. So, we’ll have to reduce statement to Normal forms.
• We can convert any proposition in two normal forms −
1. Disjunctive Normal Form An expression of n variables x1 to xn is said to be a minterm, if
it is of the form, x1 ∧ x2 ∧ x3 ∧…. ∧xn
An expression is said to be in disjunctive normal form if it is a join of minterms.
(x1 ∧ x2 ∧ x3 ) ∨ (x1’∧ x2’∧ x3’)
Example- (p ∧ q) ∨ ∼ q,
(∼ p ∧ q) ∨ ( p ∧ q) ∨q
2. Conjunctive Normal Form- An expression of n variables x1 to xn is said to be a maxterm,
if it is of the form, x1 ∨ x2 ∨ x3 ∨…. ∨xn
An expression is said to be in conjunctive normal form if it is a meet of maxterms.
(x1 ∨ x2 ∨ x3 ) ∧ (x1’∨ x2’∨ x3’)
Example- ∼ p ∧(p∨q)
(p∨q∨r)∧ (p∨ ∼ r)
• Examples-

• Obtain the CNF of the form-

p∧(p→q) = p∧(∼ p∨q) (by Implication law)

• Obtain the DNF of the form-

(p→q) ∧ (∼p∧q)
= (∼ p∨q) ∧ (∼ p ∧ q) (By Implication Law) p ⟶ q= ∼ p ∨q
= (∼p∧∼p∧q) ∨ (q∧∼p∧q)
=(∼p∧q) ∨ (q∧∼p) (By Idempotent law) p∧p≡p

• Obtain the CNF of the form-

(p∧q) ∨(∼p∧q∧r)
• Obtain the CNF of the form-
(p∧q) ∨(∼p∧q∧r)
=(p∨(∼p∧q∧r))∧(q ∨(∼p∧q∧r)) Distributive law
=(p∨∼p) ∧(p∨q) ∧(p∨r)∧(q∨∼p) ∧ (q∨q) ∧ (q∨r))
=(p∨q) ∧(p∨r)∧(q∨∼p) ∧q∧ (q∨r) since, (p∨∼p) =T & T ∧p=p
 Mathematical Induction
• In mathematics, we are often required to generalize a particular solution.
Mathematical induction is used for this.

• Principle of Mathematical Induction-

Statement-
Let P(n) be a statement involving a natural number n,

Step 1(Basis of Induction)-If P(n) is true for n=n0 &

Step 2 (Induction Step)- Assuming P(k) is true, (k>= n0), we prove P(k+1) is
also true.
The assumption that P(n) is true for n=k is called the Induction Hypothesis.
• Examples-
1. Prove by Induction-
1+2+3+….+n=(n(n+1))/2 for all natural number values of n.
Solution-
Let P(n) be the statement,
1+2+3+….+n=(n(n+1))/2
I. Basis of Induction-
for n=1, P(1)=1=(1(2))/2=1
I. Induction step-
• So, assuming P(k) is true, P(k+1) is also true. Hence, proved.
2. Prove by induction that the sum of the cubes of three consecutive natural numbers is divisible by 9.
Solution-Let P(n) be the statement given by P(n): Sum of the cubes of three consecutive natural numbers
starting from n is divisible by 9.
Step I: P(1): Sum of the cubes of first three consecutive natural numbers is divisible by 9.
since 13+23+33=36, which is divisible by 9.
∴P(1) is true.
Step II: Assume P(k) be true. So, P(k)= k3+(k+1)3+(k+2)3 ______(1)
So prove P(k+1) is also true.
P(k+1)=(k+1)3+(k+2)3+(k+3)3
=(k+1)3+(k+2)3+k3+9k2+27k+27 Since,(a+b)3=a3+3a2b+3ab2+b3
=k3+(k+1)3+(k+2)3+9(k2+3k+3)
=P(k)+9(k2+3k+3) _______[Using (1)]
which is divisible by 9.
∴P(k+1) is true
Hence, by the principle of mathematical induction P(n) is true for all n∈N.
• Show that n3+2n is divisible by 3 for all n>=1
Solution-
1.Basis of Induction-
It is given that, for all n>=1, let n=1.
(1)3+2(1)=1+2=3.
2. Induction step-
Assuming that for n=k. it is true. i.e. k3+2k is divisible by 3, we will prove it for
n=k+1
(k+1)3+2(k+1)=k3+3k2(1) +3k (1)2+ (1)2+2k+2
=k3+3k2+3k+1+2k+2
=k3+2k+3k2+3k+3
=(k3+2k)+3(k2+k+1) which is divisible by 3.
Hence, proved.