DISCRETE

MATHEMATICS 231MA202
For I year II Semester B.E/CSE

ech
lti T
Mu
DEPARTMENT OF MATHEMATICS
h

VEL TECH MULTI TECH DR. RANGARAJAN DR. SAKUNTHALA

Tec

ENGINEERING COLLEGE
42, VEL TECH ROAD, VEL NAGAR, AVADI,
CHENNAI, TAMILNADU, 600062.
Vel

Dr. K. SIVA

Dr. R. ARASU
 Contents

1 LOGIC AND PROOFS 1

1.1 Logical Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Law of Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Normal Forms [DNF & CNF] . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Minterms and Maxterms . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Quantiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Rules of Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 COMBINATIONS 24

ech
2.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . .
lti T 28
2.3 Permutation and Combinations . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5 Linear Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Mu
2.7 Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
h
Tec
Vel

1
 Chapter 1
LOGIC AND PROOFS
☞ Logical Connectives

☞ Propositional Equivalences

☞ Law of Logic

☞ Normal Forms [DNF & CNF]

☞ Minterms, Maxterms

ech
☞ Rules of Inference

1.1 Logical Connectives

lti T
1.1.1 Introduction
Mu
A proposition is a declarative sentence that is either true or false, but not both. The area
of logic that deals with propositions is called the propositional calculus or propositional
logic. It was rst developed systematically by the Greek philosopher Aristotle more than
h

2300 years ago.

Tec

English mathematician George Boole discussed new propositions from those that we
already have, in his book "The Laws of Thought" in 1854.
Many mathematical statements are constructed by combining one or more propo-
sitions. New propositions called compound propositions, are formed from existing
Vel

propositions using logical operators.

1.1.2 Propositions
Denition 1. A proposition (statement) is a declarative sentence that is either true or
false, but not both.
Example:
▶ Chennai is the capital of Tamil Nadu [True]

▶ 1+5=6 [True]

▶ 2 + 7 = 10 [False]

▶ Delhi is in America. [False]

1
 2

Notation :
P, Q, R, S . . . are used to denote propositions.

T is used to denote True proposition.

F is used to denote False proposition.

Denition 2. Atomic statements : [Primary statements] [Simple]

Declarative sentences which cannot be further split into simpler sentences are called
Atomic statements (also called primary statements or primitive statements)
Example : Rama is a boy.
Table 1.1: Five Basic Connectives

English
Logical Type of
language Symbols
connectives operator
usages

ech
1. and conjunction binary ∧
2. or
lti T
disjunction

negation (or)
binary ∨

3. not unary ¬
denial
Mu
implication

4. if ... then (or) binary →

h

conditional
Tec

5. if and only if biconditional binary ↔

Denition 3. Conjunction [∧] [AND]

Vel

The conjunction of two statements P and Q is the statement P ∧ Q which is read as

"P and Q".
The statement P ∧ Q has the truth value T whenever both P and Q have the truth
value T ; otherwise it has the truth value F.
The truth table for the conjunction
of two propositions
P Q P ∧Q
T T T
T F F
F T F
F F F

Denition 4. textbfDisjunction [∨] [or]

The disjunction of two statements P and Q is the statement P ∨ Q which is read as
"P or Q".
The statement P ∨ Q has the truth value F only when both P and Q have the truth
value F ; otherwise it is true.
 3

The truth table for the disjunction

of two propositions
P Q P ∨Q
T T T
T F T
F T T
F F F

Denition 5. Negation [¬] [Not]

The negation of a statement is generally formed by introducing the word 'not' at a
proper place in the statement.
If 'P ' denotes a statement, then the negation of P is written as '¬p' and read as 'not
P '.

The Truth table for the

negation of a proposition.
¬P

ech
P
T F
F lti T T

Denition 6. Conditional Statement : [If, ... then] [→]

If P and Q are any two statements, then the statement P → Q which is read as "If
P , then Q" is called a conditional statement.
The statement P → Q has a truth value F when P the truth value T and Q has the
Mu
truth value F , otherwise it has the truth value T .
The truth table for the implication P →Q
h

P Q P →Q
Tec

T T T
T F F
F T T
F F T
Vel

Denition 7. Biconditional [equivalence] statement [↔] [if and only if ]

If P and Q are any two statements, then the statement P ↔ Q, which is read as, "P
if and only if Q" and abbreviated as "P i Q", is called a biconditional statement.
The statement P ↔ Q has the truth value T whenever both P and Q have identical
truth values.
The truth table for the Biconditional P ↔Q
P Q P ↔Q
T T T
T F F
F T F
F F T

Example 1. Construct the truth table for (P → Q) ↔ (¬ Q → ¬ P)

 4

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

ˆ Tautology :
A statement that is true for all possible values of its propositional variables is called
a tautology or universally valid formula or a logical truth.

ˆ Contradiction :
A statement that is always false is called a contradiction or absurdity.

Note :

h
Tec
1. The negation of a contradiction is a Tautology.

2. A propositional function that is neither a tautology nor a contradiction is called a

contingency.
ulti
Tautology Contradiction Fallacy
In the result In the result In the result
hM

column all the column all the column any one

entries are T (True) entries are F (False) entry is F (False)
T F T
T F T
Tec

T F F
T F T

Example 2. Show that Q ∨ (P ∧ ¬Q) ∨ (¬P ∧ ¬Q) is a tautology.

Vel

Solution : Let S = Q ∨ (P ∧ ¬Q) ∨ (¬P ∧ ¬Q)

P Q ¬P ¬Q P ∧ ¬Q ¬P ∧ ¬Q Q ∨ (P ∧ ¬Q) S
T T F F F F T T
T F F T T F T T
F T T F F F T T
F F T T F T F T

Since the truth value in the last column is T, the given formula is a tautology.

Example 3. Using the truth table verify that the proposition

(P ∧ Q) ∧ ¬(P ∨ Q)

Solution :
 5

P Q P ∧Q P ∨Q ¬(P ∨ Q) (P ∧ Q) ∧ ¬(P ∨ Q)
T T T T F F
T F F T F F
F T F T F F
F F F F T F

All the entries in the last column are F therefore the given proposition is a contra-
diction.

Example 4. Show that (P → Q) ∧ (Q → R) → (P → R) is a tautology.

Solution: Let A = (P → Q) ∧ (Q → R) → (P → R)

P Q R P → Q Q → R (P → Q) ∧ (Q → R) P → R A
T T T T T T T T
T T F T F F F T

ech
T F T F T F T T
T F F F T F F T
F T T T T lti T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Mu
1.2 Law of Logic
h
Tec

Table logic equivalences

Equivalence Name
P ∧T ⇔P Identity laws
Vel

P ∨F ⇔P
P ∨T ⇔T Domination laws

P ∧F ⇔F
P ∨P ⇔P Idempotent laws

P ∧P ⇔P
¬(¬P ) ⇔ P Double negation law

P ∨Q⇔Q∨P Commutative laws

P ∧Q⇔Q∧P
 6

(P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R) Associative laws

(P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R)
P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R) Distributive laws

P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)

(P ∨ Q) ∧ R ⇔ (P ∧ R) ∨ (Q ∧ R)
(P ∧ Q) ∨ R ⇔ (P ∨ R) ∧ (Q ∨ R)
¬(P ∧ Q) ⇔ ¬P ∨ ¬Q De Morgan's law

¬(P ∨ Q) ⇔ ¬P ∧ ¬Q

ech
P ∨ (P ∧ Q) ⇔ P Absorption laws

P ∧ (P ∨ Q) ⇔ P
P ∨ ¬P ⇔ T (or)
lti T
¬P ∨ P ⇔ T Negation laws

P ∧ ¬P ⇔ F (or) ¬P ∧ P ⇔ F
h Mu
Tec

Logical Equivalences Involving conditionals

Vel

P → Q ⇔ ¬P ∨ Q
P → Q ⇔ ¬Q → ¬P
P ∨ Q ⇔ ¬P → Q
P ∧ Q ⇔ ¬(P → ¬Q)
¬(P → Q) ⇔ P ∧ ¬Q
(P → Q) ∧ (P → R) ⇔ P → (Q ∧ R)
(P → R) ∧ (Q → R) ⇔ (P ∨ Q) → R
(P → Q) ∨ (P → R) ⇔ P → (Q ∨ R)
(P → R) ∨ (Q → R) ⇔ (P ∧ Q) → R
 7

Logical Equivalences Involving Biconditionals

P ↔ Q ⇔ (P → Q) ∧ (Q → P )
P ↔ Q ⇔ ¬P ↔ ¬Q
P ↔ Q ⇔ (P ∧ Q) ∨ (¬P ∧ ¬Q)
¬(P ↔ Q) ⇔ P ↔ ¬Q

Example 5. Show that (¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R

Solution :
Steps Reasons

(i) ¬P ∧ (¬Q ∧ R)
⇔ (¬P ∧ ¬Q) ∧ R Associative law

h
⇔ ¬(P ∨ Q) ∧ R DeMorgan's law

Tec
(ii) (Q ∧ R) ∨ (P ∧ R)
⇔ (Q ∨ P ) ∧ R Distributive law
ulti
⇔ (P ∨ Q) ∧ R Commutative law

(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) Given

hM

⇔ (¬(P ∨ Q) ∧ R) ∨ ((P ∨ Q) ∧ R) by (i) & (ii)

⇔ (¬(P ∨ Q) ∨ (P ∨ Q)) ∧ R Distributive law

⇔T ∧R Negation law
Tec

[¬P ∨ P ⇔ T ]
⇔R Identity law
Vel

Example 6. Show that ¬(P ∨ (¬P ∧ Q)) and ¬P ∧ ¬Q are logically equivalent.
Solution :
¬(P ∨ (¬P ∧ Q)) Reasons

⇔ ¬P ∧ ¬(¬P ∧ Q) De Morgan's law

⇔ ¬P ∧ [¬(¬P ) ∨ ¬Q] De Morgan's law

⇔ ¬P ∧ (P ∨ ¬Q) Double negation law

⇔ (¬P ∧ P ) ∨ (¬P ∧ ¬Q) Distributive law

⇔ F ∨ (¬P ∧ ¬Q) Since ¬P ∧ P ⇔ F

⇔ (¬P ∧ ¬Q) ∨ F Commutative law

⇔ ¬P ∧ ¬Q Identity law
 8

Consequently, ¬(P ∨ (¬P ∧ Q)) and ¬P ∧ ¬Q are logically equivalent.

Example 7. Show that ¬(P ∧ Q) → (¬P ∨ (¬P ∨ Q)) ⇔ (¬P ∨ Q) (use only the laws)
Reasons
¬P ∨ (¬P ∨ Q)
(i)
⇔ (¬P ∨ ¬P ) ∨ Q Associative law
⇔ ¬P ∨ Q Idempotent law P ∨P ⇔P
¬(P ∧ Q) → (¬P ∨ (¬P ∨ Q)) Given
⇔ ¬(P ∧ Q) → (¬P ∨ Q) by (i)
⇔ (P ∧ Q) ∨ (¬P ∨ Q) P → Q ⇔ ¬P ∨ Q
Distributive law
⇔ (P ∨ (¬P ∨ Q)) ∧ (Q ∨ (¬P ∨ Q))
(P ∧ Q) ∨ R ⇔ (P ∨ R) ∧ (Q ∨ R)
Associative law &
⇔ ((P ∨ ¬P ) ∨ Q) ∧ (Q ∨ (Q ∨ ¬P ))
Commutative law
⇔ (T ∨ Q) ∧ ((Q ∨ Q) ∨ ¬P ) Negation law & Associative law
⇔ T ∧ (Q ∨ ¬P ) Domination law & Idempotent law

ech
⇔ Q ∨ ¬P Identity law
⇔ ¬P ∨ Q Commutative law

Example 8. Show that (P → Q) ∧ (R → Q) ⇔ (P ∨ R) → Q.

lti T
Solution :
(P → Q) ∧ (R → Q) Reasons
Mu
⇔ (¬P ∨ Q) ∧ (¬R ∨ Q) since P → Q ⇔ ¬P ∨ Q

⇔ (¬P ∧ ¬R) ∨ Q Distributive law

h

⇔ ¬(P ∨ R) ∨ Q De Morgan's law

Tec

⇔P ∨R→Q since ¬P ∨ Q ⇔ P → Q

Example 9. Show that the given formula is an implication

Vel

((P ∨ ¬Q) → Q) → ((P ∨ ¬P ) → R) → (Q → R)

Solution : To prove ((P ∨ ¬Q) → Q) → ((P ∨ ¬P ) → R) → (Q → R) is a tautology.

(i) (P ∨ ¬Q) → Q Reason

⇔ ¬(P ∨ ¬Q) ∨ Q since P → Q ⇔ ¬P ∨ Q
⇔ (¬P ∧ ¬(¬Q)) ∨ Q De Morgan
⇔ (¬P ∧ Q) ∨ Q Double negation
⇔ (¬P ∨ Q) ∧ (Q ∨ Q) Distributive law
⇔ (¬P ∨ Q) ∧ Q Idempotent law

(ii) (P ∨ ¬P ) → R Reason
⇔T →R Negation law
⇔ ¬T ∨ R P → Q ⇔ ¬P ∨ Q
⇔ ¬(T ∧ ¬R) De Morgan
⇔ ¬(T ) Dominative law
⇔F
 9

(iii) ((¬P ∨ Q) ∧ Q) → F
⇔ ¬((¬P ∨ Q) ∧ Q) ∨ F
⇔ (¬(¬P ∨ Q) ∨ ¬Q) ∨ F
⇔ ((¬(¬P ) ∧ ¬Q) ∨ ¬Q) ∨ F
⇔ ((P ∧ ¬Q) ∨ ¬Q) ∨ F

(iv) ((P ∧ ¬Q) ∨ ¬Q) ∨ F → (Q → R)

⇔ ¬((P ∧ ¬Q) ∨ ¬Q) ∨ F ) ∨ (¬Q ∨ R)
⇔ (¬((P ∧ ¬Q) ∨ ¬Q) ∧ ¬F ) ∨ (¬Q ∨ R)
⇔ ((¬P ∨ ¬(¬Q)) ∨ ¬Q) ∧ T ) ∨ (¬Q ∨ R)
⇔ (¬P ∨ Q ∨ ¬Q ∨ (¬Q ∨ R))
⇔ (¬P ∨ (Q ∨ ¬Q) ∨ (¬Q ∨ R))
⇔ (¬P ∨ T ) ∨ (¬Q ∨ R)
⇔ T ∨ (¬Q ∨ R)
⇔T

Hence the proof.

ech
1.3 Normal Forms [DNF & CNF] lti T
Disjunctive Normal Form (DNF)
♦ Denition
A formula which is equivalent to a given formula and which consists of a sum of elementary
Mu
products is called a disjunctive normal form (DNF) of the given formula.
Procedure to obtain DNF
h

1. An equivalent formula can be obtained by replacing → and ↔ with ∧, ∨ and ¬.

Tec

2. Apply negation to the formula or to a part of the formula and not to the variables.

3. Using DeMorgan's law, apply negation to variables.

Vel

4. Repeated application of distributive laws will give the required DNF.

ˆ Conjunctive Normal Form :

A formula which is equivalent to a given formula and which consists of a product
of elementary sums is called a conjunctive normal form of the given formula.

Example 10. Obtain a disjunctive normal form of

P → ((P → Q) ∧ ¬(¬Q ∨ ¬P ))

Solution :
 10

Let S ⇔ P → [(P → Q) ∧ ¬(¬Q ∨ ¬P )]

⇔ ¬P ∨ [(P → Q) ∧ ¬(¬Q ∨ ¬P )]
[∵ (P → Q) ⇔ (¬P ∨ Q)]
⇔ ¬P ∨ [(¬P ∨ Q) ∧ (Q ∧ P )]
[∵ (P → Q) ⇔ (¬P ∨ Q) and Demorgan's law]

⇔ ¬P ∨ [(¬P ∧ (Q ∧ P )) ∨ (Q ∧ (Q ∧ P ))]
[∵ Distributive law]
⇔ ¬P ∨ [(¬P ∧ (Q ∧ P ))] ∨ [Q ∧ (Q ∧ P )]
⇔ ¬P ∨ [¬P ∧ (Q ∧ P )] ∨ [(Q ∧ Q) ∧ P ]
[∵ Associative law]
⇔ ¬P ∨ [¬P ∧ (Q ∧ P )] ∨ [Q ∧ P ]
[∵ Q ∧ Q ⇔ Q]

ech
Example 11. Obtain a conjunctive normal form of the formula.

Solution :
lti T
P → ((P → Q) ∧ ¬(¬Q ∨ ¬P ))
Mu
P → ((P → Q) ∧ ¬(¬Q ∨ ¬P )) Reasons
⇔ ¬P ∨ ((P → Q) ∧ ¬(¬Q ∨ ¬P )) P → R ⇔ ¬P ∨ R
⇔ ¬P ∨ ((¬P ∨ Q) ∧ ¬(¬Q ∨ ¬P )) P → R ⇔ ¬P ∨ R
h

⇔ ¬P ∨ ((¬P ∨ Q) ∧ (Q ∧ P )) De Morgan's law

Tec

⇔ (¬P ∨ (¬P ∨ Q)) ∧ ((¬P ∨ (Q ∧ P ))) Distributive law

⇔ ((¬P ∨ ¬P ) ∨ Q) ∧ ((¬P ∨ Q) ∧ (¬P ∨ P )) associative law

⇔ (¬P ∨ Q) ∧ (¬P ∨ Q) ∧ T Negation law

Vel

⇔ (¬P ∨ Q) ∧ (¬P ∨ Q) identity law

This is a CNF, as it is a product of elementary sums.

1.4 Minterms and Maxterms

Min terms
Let P and Q be two statement variables. Construct all possible formula which consist
of conjunctions of P or its negation and conjunctions of Q or its negation. None of the
formula should contain both a variable and its negation. Delete a formula if it is the
commutative of any one of the remaining formulae. Such conjunctions of P and Q are
called the min terms of P and Q.
Example :
Minterms of P and Q are P ∧ Q, P ∧ ¬Q, ¬P ∧ Q and ¬P ∧ ¬Q
Note :
(i) P ∧Q or Q∧P is included but not both.
 11

(ii) P ∧ ¬P and Q ∧ ¬Q are not allowed.

(iii) No two minterms are equivalent.

(iv) Each minterm has the truth value T for exactly one combination of the truth values
of the variables P and Q.

Principal Disjunctive Normal Form (PDNF)

♦ The sum of products normal form
A formula which is equivalent to a given formula and which consists of sum of its
min terms is called "principal disjunctive normal form" (or) "sum of product of canonical
form" of the given formula.
Construction of PDNF without truth tables:
(i) to replace conditionals and biconditionals by their equivalent formula involving
∧, ∨, ¬ only.

ech
(ii) to use De Morgan's laws and distributive laws.

(iii) to drop any elementary product which is a contradiction.

lti T
(iv) to obtain minterms in the disjunctions by introducing missing factors.

(v) to delete identical minterms keeping only one, that appear in the disjunctions.

Maxterms
Mu
For a given number of variables, the maxterm consists of disjunctions in which each
variable or its negation, but not both, appears only once.
h

♦ Remarks:
Tec

(i) The max terms are the duals of minterms.

(ii) Either from the duality principle or directly from the truth tables, it can be ascer-
Vel

tained that each of the maxterms has the truth value F for exactly one combination
of the truth values of the variables.

(iii) Dierent maxterms have the truth value F for dierent combinations of the truth
values of the variables.

♦ Principal Conjunctive Normal Form (or) Product-of-sums canonical form:

An equivalent formula consisting of conjunctions of max terms only is known as its
principal conjunctive normal form or the product-of-sums canonical form.
 12

Example 12. Obtain the principal disjunctive normal forms of ¬P ∧ Q (or) P → Q.

Also nd p.c.n.f

P Q ¬P Q S Minterms (T) Maxterms (F)

T T F T T P ∧Q
T F F F F ¬P ∨ Q
F T T T T ¬P ∧ Q
F F T F T ¬P ∧ ¬Q

PDNF (S) = (P ∧ Q) ∨ (¬P ∧ Q) ∨ (¬P ∧ ¬Q)

PCNF (S) = (¬P ∨ Q)

Example 13. Obtain PDNF of (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R). Also nd PCNF.

Solution:
LetS ⇔ (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R)

ech
Let A = (¬P ∧ R) ∨ (Q ∧ R)

P Q R P ∧Q ¬P ∧ R Q∧R lti T A S Minterm Maxterm

T T T T F T T T P ∧Q∧R
T T F T F F F T P ∧ Q ∧ ¬R
T F T F F F F F ¬P ∨ Q ∨ ¬R
T F F F F F F F ¬P ∨ Q ∨ R
Mu
F T T F T T T T ¬P ∧ Q ∧ R
F T F F F F F F P ∨ ¬Q ∨ R
F F T F T F T T ¬P ∧ ¬Q ∧ R
h

F F F F F F F F P ∨Q∨R
Tec

PDNF (S) = (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R) ∨ (¬P ∧ Q ∧ R) ∨ (¬P ∧ ¬Q ∧ R)

PCNF (S) = (¬P ∨ Q ∨ ¬R) ∧ (¬P ∨ Q ∨ R) ∧ (P ∨ ¬Q ∨ R) ∧ (P ∨ Q ∨ R)

Example 14. Without constructing the truth table obtain the product of sums canonical
Vel

form of the formula.

(¬P → R) ∧ (Q ⇔ P ). Hence nd the sum of products canonical form.

Solution : Let S ⇔ (¬P → R) ∧ (Q ⇔ P )

 13

P Q R ¬P ¬P → R Q⇔P S minterm maxterm

T T T F T T T P ∧Q∧R 

T T F F T T T P ∧ Q ∧ ¬R 

T F T F T F F  ¬P ∨ Q ∨ ¬R
F T T T T F F  P ∨ ¬Q ∨ ¬R
T F F F T F F  ¬P ∨ Q ∨ R
F F T T T T T ¬P ∧ ¬Q ∧ R 

F T F T F F F  P ∨ ¬Q ∨ R
F F F T F T F  P ∨Q∨R

PDNF (S) = (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R) ∨ (¬P ∧ ¬Q ∧ R)

ech
PCNF (S) = (¬P ∨ Q ∨ ¬R) ∧ (P ∨ ¬Q ∨ ¬R) ∧ (¬P ∨ Q ∨ R) ∧ (P ∨ ¬Q ∨ R) ∧ (P ∨ Q ∨ R)

Example 15. Obtain the principal disjunctive and conjunctive normal forms
lti T
[P → (Q ∧ R)] ∧ [¬P → (¬Q ∧ ¬R)]

Solution :
Mu
Let S ⇔ [P → (Q ∧ R)] ∧ [¬P → (¬Q ∧ ¬R)]
A ⇔ P → (Q ∧ R)
B ⇔ ¬Q ∧ ¬R
C ⇔ ¬P → (¬Q ∧ ¬R)
h

i.e., S ⇔ A ∧ C
Tec

P QR Q∧R ¬P ¬Q ¬R B C A S Minterm Maxterm

Vel

TTT T F F F F T T T P ∧Q∧R
TTF F F F T F T F F - ¬P ∨ ¬Q ∨ R
TFT F F T F F T F F - ¬P ∨ Q ∨ ¬R
FTT T T F F F F T F - P ∨ ¬Q ∨ ¬R
TFF F F T T T T F F - ¬P ∨ Q ∨ R
FTF F T F T F F T F - P ∨ ¬Q ∨ R
FFT F T T F F F T F - P ∨ Q ∨ ¬R
FFF F T T T T T T T ¬P ∧ ¬Q ∧ ¬R

pdnf = (P ∧ Q ∧ R) ∨ (¬P ∧ ¬Q ∧ ¬R) by using minterms

pcnf = (¬P ∨ ¬Q ∨ R) ∧ (¬P ∨ Q ∨ ¬R) ∧ (P ∨ ¬Q ∨ ¬R) ∧(¬P ∨ Q ∨ R) ∧ (P ∨ ¬Q ∨ R)

∧ (P ∨ Q ∨ ¬R) by using maxterms.

Example 16. Obtain the P.D.N.F. of P ∨ (¬P ∧ (Q ∨ (¬Q → R))).

Solution: Let f = P ∨ (¬P ∧ (Q ∨ (¬Q → R))). Constructing the truth table:
 14

P Q R ¬P ¬Q → R ¬P ∧ (Q ∨ (¬Q → R)) f
T T T F T F T
T T F F T F T
T F T F T F T
T F F F F F T
F T T T T T T
F T F T T T T
F F T T T T T
F F F T F F F
The P.D.N.F. consists of the disjunction of minterms where f is True:

(P ∧Q∧R)∨(P ∧Q∧¬R)∨(P ∧¬Q∧R)∨(P ∧¬Q∧¬R)∨(¬P ∧Q∧R)∨(¬P ∧Q∧¬R)∨(¬P ∧¬Q∧R)

1.5 Quantiers

h
Example 17. 1. Symbolise : For every x, there exists a y such that x2 + y2 ≥ 100.

matics book".
(i) Solution : (∀x)(∃y)(x2 + y2 ≥ 100) Tec
2. Give the symbolic form of the statement "every book with a blue cover is a mathe-
ulti
(ii) Solution :
hM

∀x(S(x)) → P (x)
where S(x) = x is every book with a blue cover
P (x) = Mathematics book
Tec

Example 18. Write each of the following in symbolic form.

(a) All men are good
(b) No men are good
Vel

(c) Some men are good

(d) Some men are not good
Solution : We assume that the universe consists of objects some of which are not men.

Let M (x) : x is a man and

G(x) : x is good

(a) means 'for all x, if x is a man, then x is good'.

So (a) is (∀x[M (x) → G(x)])

(b) means "For all x, if x is a man, then x is not good' a

So (b) is (∀x)[M (x) → ¬G(x)]

(c) means "there is an x, such that x is a man and x is good".

 15

So (c) is (∃x)(M (x) ∧ G(x))

(d) means, "there is an x, such that x is a man and x is not good".

So (d) is (∃x)(M (x) ∧ ¬G(x))
√
Example 19. Express " 2 is an irrational number" using quantiers.
√
Solution
√ : Let P be the proposition  2 is irrational". Suppose that ¬P is true. Then
2 is√rational. We will show that this leads to a contradiction.
√ Under the assumption
a
that 2 is rational, there exist integers a and b with 2 = b , where a and b have no
a
√
common factors (so that the fraction
b
is in lowest terms). Since 2 = ab ,
Squaring on both sides we get
a2
2=
b2
Hence,
2b2 = a2

ech
This means that a2 is even, implying that a is even. Further more, since a is even,
a = 2c for some integer c. Thus,
2b2 = 4c2
lti T
So,
b2 = 2c2
This means that b2 is even. Hence, b must be even as well.
Mu
√
It has been shown that ¬P implies that 2 = ab , where a and b have no common
factors, and 2 divides a and b. This is a contradiction since we have shown that ¬P
implies both r and ¬r , where r is the statement that a and b are integers with no
√
h

common factors. Hence, ¬P is false, so that P : ” 2 is irrational” is true.

Tec
Vel
 16

1.6 Rules of Inference

I1 P ∧Q⇒P Simplication

I2 P ∧Q⇒Q
I3 P ⇒P ∨Q Addition

I4 Q⇒P ∨Q
I5 ¬P ⇒ P → Q
I6 Q⇒P →Q
I7 ¬(P → Q) ⇒ P
I8 ¬(P → Q) ⇒ ¬Q
I9 P, Q ⇒ P ∧ Q

ech
I10 ¬P, P ∨ Q ⇒ Q (disjunctive syllogism)

I11 P, P → Q ⇒ Qlti T (modus ponens)

I12 ¬Q, P → Q ⇒ ¬P (modus tollens)

I13 P → Q, Q → R ⇒ P → R (hypothetical syllogism)

Mu
I14 P ∨ Q, P → R, Q → R ⇒ R (dilemma)
h

E1 ¬¬P ⇔ P double negation

Tec

E2 P ∧Q⇔Q∧P Commutative laws

E3 P ∨Q⇔Q∨P
E4 (P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R) Associative laws
Vel

E5 (P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R)
E6 P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R) Distributive laws

E7 P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)
E8 ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q DeMorgan's laws

E9 ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q
E10 P ∨P ⇔P
E11 P ∧P ⇔P
E12 R ∨ (P ∧ ¬P ) ⇔ R
E13 R ∧ (P ∨ ¬P ) ⇔ R
 17

E14 R ∨ (P ∨ ¬P ) ⇔ T
E15 R ∧ (P ∧ ¬P ) ⇔ F
E16 P → Q ⇔ ¬P ∨ Q
E17 ¬(P → Q) ⇔ P ∧ ¬Q
E18 P → Q ⇔ ¬Q → ¬P
E19 P → (Q → R) ⇔ (P ∧ Q) → R
E20 ¬(P ↔ Q) ⇔ P ↔ ¬Q
E21 P ↔ Q ⇔ (P → Q) ∧ (Q → P )
E22 (P ↔ Q) ⇔ (P ∧ Q) ∨ (¬P ∧ ¬Q)

Example 20. Show that R ∨ S follows logically from the premises C ∨ D, (C ∨ D) →

h
¬H, ¬H → (A ∧ ¬B) and (A ∧ ¬B) → (R ∨ S).

Tec
Solution:
{1} (1) (C ∨ D) → ¬H P
ulti
{2} (2) ¬H → (A ∧ ¬B) P

{1, 2} (3) (C ∨ D) → (A ∧ ¬B) T, (1), (2) and I13

hM

{4} (4) (A ∧ ¬B) → (R ∨ S) P

{1, 2, 4} (5) (C ∨ D) → (R ∨ S) T, (3), (4) and I13

Tec

{6} (6) C ∨D P

{1, 2, 4, 6} (7) R∨S T, (5), (6) and I11

Example 21. Show that R → S can be derived from the premises

Vel

P → (Q → S), ¬R ∨ P and Q.

Solution : Instead of deriving R → S, we shall include R as an additional premise and

show S rst.

{1} (1) ¬R ∨ P P

{2} (2) R P (assumed premise)

{1, 2} (3) P T, (1), (2) and I10

{4} (4) P → (Q → S) P

{1, 2, 4} (5) Q→S T, (3), (4) and I11

{6} (6) Q P

{1, 2, 4, 6} (7) S T, (5), (6) and I11

{1, 4, 6} (8) R→S CP
 18

Example 22. Show that the following premises are inconsistent.

1. If Jack misses many classes through illness, then he fails high school.
2. If Jack fails high school, then he is uneducated.
3. If Jack reads a lot of books, then he is not uneducated.
4. Jack misses many classes through illness and reads a lot of books.
Solution:
E : Jack misses many classes.
S : Jack fails high school.
A : Jack reads a lot of books.
H : Jack is uneducated.

The premises are E → S , S → H , A → ¬H and E ∧ A.

ech
{1} (1) E→S P
{2} (2) S→H P
{1, 2} E→H T, (1), (2) and I13
{4}
{4}
(3)
(4)
(5)
lti T
A → ¬H
H → ¬A
P
T, (4), E18
{1, 2, 4} (6) E → ¬A T, (3), (5), I13
{1, 2, 4} (7) ¬E ∨ ¬A T, (6), E16
Mu
{1, 2, 4} (8) ¬(E ∧ A) T, (7), E8
{9} (9) E∧A P
{1, 2, 4, 9} (10) (E ∧ A) ∧ ¬(E ∧ A) T, (8), (9), I9
h
Tec

Example 23. Show that the following set of premises is inconsistent.

If the contract is valid, then John is liable for penalty. If John is liable for penalty, he
will go bankrupt. If the bank will loan him money, he will not go bankrupt. As a matter
of fact, the contract is valid and the bank will loan him money.
Vel

Solution : We indicate the given statements as follows :

V : The contract is valid.

L : John is liable for penalty.

M : Bank will loan him money.

B : He will go bankrupt.

Then the given premises are

V → L, L → B, M → ¬B, V ∧ M
 19

[1] (1) V →L Rule P

[2] (2) L→B Rule P
[1, 2] (3) V →B Rule T, (1), (2) law of hypo syllogism
[4] (4) V ∧M Rule P
[4] (5) V Rule T, (4), simplication
[4] (6) M Rule T, (4), simplication
[1, 2, 4] (7) B Rule T, (3), (5), modus ponens
[8] (8) M → ¬B Rule P
[4, 8] (9) ¬B Rule T, (6), (8)
[1, 2, 4, 8] (10) B ∧ ¬B Rule T, (7), (9), contradiction

Hence it is inconsistent.
Example 24. 1. Show the following argument is valid.
"My father praises me only if I can be proud of myself. Either I do well in sports
or I cannot be proud of myself. If I study hard, then I cannot do well in sports.
Therefore, if father praises me, then I do not study well"

h
2. Show that the hypothesis (P ∧ Q) ∨ R and R → S imply the conclusion P ∨ S
(i) Solution : Let
A : My father praises me.
Tec
ulti
B : I can be proud of myself.

C : I do well in sports.
hM

D : I study hard.

then the given premises are

Tec

A → B, C ∨ ¬B, D → ¬C and the conclusion is A → ¬D.

For, let us assume A as one more premise

{1} (1) A Rule P (assumed)

Vel

{2} (2) A→B Rule P

{1, 2} (3) B Rule T, 1, 2, I11
{4} (4) C ∨ ¬B Rule P
{1, 2, 3, 4} (5) C Rule T, 3, 4, I10
{6} (6) D → ¬C Rule P
{6} (7) C → ¬D Rule T, 5, E18 , E1
{5, 7} (8) ¬D Rule T, 5, 7, I11
{1, 8} (9) A → ¬D Rule CP, 1, 8

Hence it is a valid argument.

(ii) Solution :
1. (P ∧ Q) ∨ R Rule : P
2. (P ∨ R) ∧ (Q ∨ R) Distributive laws
3. P ∨R Simplication
4. R→S Rule P
5. ¬R ∨ S T by E16
6. P ∨S T from (3) and (5)
 20

Example 25. 1. By indirect proof, show that

P → Q, Q → R, P ∨ R ⇒ R.

2. Show that the following implication by using indirect method.

(R → ¬Q), R ∨ S, S → ¬Q, P → Q ⇒ ¬P

(i)
Solution : The desired result is R. Include ¬R as a new premise.

[1] (1) Q→R Rule P

[2] (2) ¬R Rule P (additional premise)
[1, 2] (3) ¬Q Rule T, (1), (2)
[4] (4) P →Q Rule P
[1, 2, 4] (5) ¬P Rule T, (3), (4), modus ponens
[6] (6) P ∨R Rule P

ech
[1, 2, 4, 6] (7) R Rule T, (5), (6)
[1, 2, 4, 6] (8) R ∧ ¬R Rule T, (2), (7), Contradiction

(ii)
Solution :
lti T
To use the indirect method, we will include
premise and prove a contradiction.
¬¬P ⇔ P as an additional
Mu
1. P Rule P

2. P →Q Rule P

3. Q T, (1), (2) and modus ponens

h
Tec

4. R → ¬Q P

5. S → ¬Q P

6. (R ∨ S) → ¬Q T, (4), (5) and equivalence

Vel

7. R∨S P

8. ¬Q T, (6), (7) and modus ponens

9. Q ∧ ¬Q T, (3), (8) and conjunction

10. F T, 9 and negation law [contradiction]

Example 26. Show that the following sets of premises are inconsistent.
P → Q, P → R, Q → ¬R, P

Solution :
 21

(1) P →Q Rule P

(2) Q → ¬R Rule P

(3) P → ¬R from (1) & (2) Rule T

(4) P Rule P

(5) ¬R Rule T from (3) & (4)

(6) P →R Rule P

(7) ¬P Rule T from (5) & (6)

(8) P ∧ ¬P Rule T

Thus the given set of premises leads to a contradiction and hence it is inconsistent.

Example 27. Show that (∃x)M (x) follows logically from the premises
(x)(H(x) → M (x)) and (∃x)H(x)

ech
Solution : lti T
{1} (1) (∃x)H(x) P

{1} (2) H(y) ES, (1)

{3} (3) (x)(H(x) → M (x)) P

Mu
{3} (4) H(y) → M (y) US, (3)

{1, 3} (5) M (y) T, (2), (4), I11

h

{1, 3} (6) (∃x)M (x) EG, (5)

Tec

Note that in step 2 the variable y is introduced by ES. Therefore a conclusion such as
(x)M (x) could not follow from step 5 because it would violate the rules given for UG.
Vel

Example 28. Example 5. Prove that (∃x)(P (x) ∧ Q(x)) ⇒ (∃x)P (x) ∧ (∃x)Q(x)
Solution :
{1} (1) (∃x)(P (x) ∧ Q(x)) P

{1} (2) P (y) ∧ Q(y) ES, (1), y xed

{1} (3) P (y) T, (2), I1

{1} (4) Q(y) T, (2), I2
{1} (5) (∃x)P (x) EG, (3)

{1} (6) (∃x)Q(x) EG, (4)

{1} (7) (∃x)P (x) ∧ (∃x)Q(x) T, (4), (5), I9

Example 29. Show that the premises "A student in this class has not read the book",
and "Everyone in this class passed the rst exam" imply the conclusion "someone who
passed the rst exam has not read the book".
 22

Solution : Let P (x) : x is in this class

Q(x) : x has read the book
R(x) : x passed the rst exam

Step Reason
1. ∃x (P (x) ∧ ¬Q(x)) Premise

2. P (a) ∧ ¬Q(a) E.S

3. P (a) Simplication from (2)

4. ∀x [P (x) → R(x)] Premise

5. P (a) → R(a) U.S from (4)

6. R(a) Modus ponens from (3) and (5)

7. ¬Q(a) Simplication from (2)

ech
8. R(a) ∧ ¬Q(a) Conjunction from (6) and (7)

9. ∃x (R(x) ∧ ¬Q(x)) E.G from (8)

lti T
Example 30. Give a direct proof of the statement.
"The square of an odd integer is an odd integer".
Solution : Given : "The square of an odd integer is an odd integer".
Mu
2
i.e., "If n is an odd integer, then n is an odd integer".
Let P : n is an odd integer.
Q : n2 is an odd integer.
h

1. Hypothesis : First assume that P is true.

Tec

i.e., n is an odd integer is true.

2. Analysis : By the denition of an odd integer,

Vel

n = 2k + 1, where k is some integer.

n2 = (2k + 1)2
= 4k 2 + 4k + 1
= 2(2k 2 + 2k) + 1

3. Conclusion : We observe that R.H.S value is not divisible by 2.

∴ n2 is not divisible by 2.

n2 is an odd integer.

i.e., P →Q is true.

Example 31. Prove that if x is irrational then 1

x
is irrational.
Solution : P : x is irrational.
Q : x1 is irrational.
 23

1. Hypothesis : Assume that P →Q is false.

That is, assume that P is true and Q is false.

1 1
i.e.,
x
is not irrational ⇒ x
is rational.

2. Analysis : 1
x
is rational.

⇒ 1
x
= pq , q ̸= 0 [If p = 0, 1 = (0)(x) which is absurd]

1
⇒ x
cannot be zero.

⇒ 1
x = (1/x) 1
= (p/q) = pq (p ̸= 0)

3. Conclusion : Thus by denition x is rational. This contradicts our assumption P

is true.

From this we get P →Q is true.

ech
lti T
h Mu
Tec
Vel
 Chapter 2
COMBINATIONS
☞ Mathematical Induction

☞ The Pigeonhole Principle

☞ Permutation and Combinations

☞ Recurrence Relations

☞ Linear Recurrence Relations

ech
☞ Generating Functions

☞ Inclusion and Exclusion

lti T
2.1 Mathematical Induction
Mu
Example 32. Show that 12 + 22 + 32 + · · · + n2 = n(n+1)(2n+1)
6
, n ≥ 1 by mathematical
induction.
Solution: P (n) : 12 + 22 + 32 + · · · + n2 = n(n+1)(2n+1)
h

Let
6
Tec

Step 1: To prove P (1) is true.

For n=1
1(1 + 1)(2 + 1)
12 =
Vel

6
1=1

So P (1) is true.

Step 2: Assume that P (k) is true.

k(k + 1)(2k + 1)
(i.e.,) 12 + 22 + 32 + · · · + k 2 =
6

Step 3: To prove P (k + 1) is true.

(k + 1)(k + 2)(2k + 3)
(i.e.,) To prove P (k + 1) =
6

24
 25

 
2 2 2 2 2 k(k + 1)(2k + 1)
[1 + 2 + 3 + · · · + k ] + (k + 1) = + (k + 1)2
6
k(k + 1)(2k + 1) + 6(k + 1)2
=
6
2
(k + 1)[2k + k + 6k + 6]
=
6
(k + 1)[2k 2 + 7k + 6]
=
6
(k + 1)(k + 2)(2k + 3)
=
6
which is P (k + 1).

That is P (k + 1) is true whenever P (k) is true.

ech
By the principle of mathematical induction P (n) is true for all positive integer n.

Example 33. Prove by mathematical induction that 2n > n for all n ∈ N. (or) n < 2n
lti T
for all positive integers n.
Solution : Let P (n) : n < 2n
Step 1 : To prove P (1) is true.
Mu
1 < 21
⇒1<2
h

Hence P (1) is true.

Tec

Step 2 : Assume that P (k) is true.

(i.e., ) k < 2k
Vel

Step 3 : To prove : P (k + 1) is true

(i.e., ) To prove : P (k + 1) = 2k+1

(i.e., ) k < 2k
⇒ k + 1 < 2k + 1
⇒ k + 1 < 2k + 2k [∵ 1 ≤ 2k ]
⇒ k + 1 < 2(2k )
⇒ k + 1 < 2k+1

which is P (k + 1)
That is P (k + 1) is true whenever P (k) is true.

Example 34. 1. Use mathematical induction to prove that n3 − n is divisible by 3

whether n is a positive integer.
2. Show that an − bn is divisible by (a − b) for all n ∈ N
 26

Solution : Let P (n) : (n3 − n) is divisible by 3.

Step 1 : To prove P (1) is true.

1−1=0 is divisible by 3.

Hence P (1) is true.

Step 2 : Assume that P (k) is true.

(i.e.,) (k 3 − k) is divisible by 3.

Step 3 : To prove P (k + 1) is true.

(k + 1)3 − (k + 1) is divisible by
(i.e.,) To prove 3.

(k + 1)3 − (k + 1) = (k 3 + 3k 2 + 3k + 1) − (k + 1)
= (k 3 − k) + 3(k 2 + k)

ech
which is divisible by 3.

Hence P (k + 1) is true.
lti T
This completes the inductive step.
(ii) Solution : n n
Let P (n) : (a − b ) is divisible by (a − b)
Step 1 : To prove P (1) is true.
Mu
(a1 − b1 ) = (a − b) is divisible by (a − b)
h

Hence P (1) is true.

Tec

Step 2 : Assume that P (k) is true. Let (ak − bk ) = c(a − b)

⇒ ak = bk + c(a − b) . . . (1)
Vel

Now,

ak+1 − bk+1 = ak a − bk b
= a[bk + c(a − b)] − bk b by (1)
k k
= ab + ac(a − b) − b b
= bk (a − b) + ac(a − b)
= (a − b)(bk + ac)

which is divisible by (a − b)
(i.e., ) That is P (k + 1) is true whenever P (k) is true.
∴ By the principle of mathematical induction, P (n) is true for all n ∈ N.

Example 35. Prove by mathematical induction that 6n+2 + 72n+1 is divisible by 43 for
each positive integer.
 27

Solution : Let P (n) : 6n+2 + 72n+1 is divisible by 43.

Step 1 : To prove P (1) is true.

61+2 + 72(1)+1 = 63 + 73
= 216 + 343
= 559
= (43)(13)

which is divisible by 43.

∴ P (1) is true.

Step 2 : Assume that P (k) is true.

(i.e.,) 6k+2 + 72k+1 = (43)(m) for some integer m.

ech
Step 3 : To prove P (k + 1) is true.

(i.e.,) 6(k+1)+2 + 72(k+1)+1 = 6k+3 + 72k+3

lti T = 6k+3 + 72k+1 (72 )
= 6(6k+2 ) + 72k+1 (49)
= 6(6k+2 ) + 72k+1 (6 + 43)
Mu
= 6(6k+2 + 72k+1 ) + (43)72k+1
= 6(43)(m) + 43(72k+1 )
= 43[6m + 72k+1 ]
h
Tec

which is divisible by 43.

Hence P (k + 1) is true whenever P (k) is true.

By the principle of mathematical induction P (n) is true for all positive integer n.
Vel

Example 36. Prove by mathematical induction that 3n+1 −1

for n ∈ N0 .
Pn
r=0 3r = 2

Step 1 : To prove P (1) is true.

P0 r
LHS: r=0 3 = 30 = 1
30+1 −1
RHS:
2
= 22 =1
So P (1) is true.

Step 2 : Assume that P (k) is true.

k
X 3k+1 − 1
3r =
r=0
2
 28

Step 3 : To prove P (k + 1) is true.

k+1 k
!
X X
3r = 3r + 3k+1
r=0 r=0
k+1
3 −1
= + 3k+1 (by hypothesis)
2
3k+1 − 1 + 2(3k+1 )
=
2
3(3k+1 ) − 1
=
2
k+2
3 −1
=
2
Hence P (k + 1) is true whenever P (k) is true.
By the principle of mathematical induction P (n) is true for all positive integer
n ≥ 0.

ech
Example 37. 1.
lti T
2. Any positive integer n ≥ 2 is either a prime or a product of primes. To prove this
we use the principle of strong mathematical induction.
(ii) Solution : Let P (n) : n ≥ 2 is either a prime or a product of primes.
Mu
Step 1 : To prove P (2) is true. 2=2 is a prime.
Hence P (2) is true.

Step 2 :
h

Assume that the statement is true for 2≤n≤k

Tec

Step 3 : To prove P (k + 1) is true.

For the integer k + 1, if k + 1 is a prime, the statement is true. If k + 1 is not a prime,

then k+1 can be written as pq , for some 2 ≤ p ≤ k and 2 ≤ q ≤ k .
Vel

According to the induction hypothesis, p is either a prime or a product of prime. Also,

q is either a prime or a product of prime. Consequently, pq is a product of prime.

2.2 The Pigeonhole Principle

Example 38. Apply the pigeonhole principle to prove that if seven colors are used to
paint 50 cars, atleast eight cars will have the same colour.
Solution :
Assume that 50 cars (pigeons) are assign 7 colors (pigeonholes). Hence, by the gen-
eralised pigeonhole principle, atleast
 
50 − 1
+1=8 cars will have the same colour.
7

Example 39. Seven members of a family have total Rs. 2,886 in their pockets. Show
that atleast one of them must have atleast Rs. 413 in his pocket.
 29

Solution : Let us assume

members → pigeonholes
Rupees → pigeons

Now 2886 pigeons are to be assigned to 7 pigeonholes.

Using the extended pigeonhole principle

k−1
(i.e.,) +1 where k = 2886, n = 7
n

2886 − 1
∴ + 1 = 413.14... ≈ 413
7
Hence, there are 413 rupees in one member's pocket.

2.3 Permutation and Combinations

ech
Permutation
A permutation of a set of distinct objects is an ordered arrangement of these objects.
lti T(or)

Permutation means selection and arrangement of factors.

Notation : n Pr (or) P (n, r)
Mu
n!
nPr =
(n − r)!
Results:
h
Tec

1. nP0 = 1
2. nP1 = n
3. nPn = n!
Vel

Combinations
A combinations is a selection of objects without regard to order.
Notation : nCr (or) C(n, r)
n!
nCr =
r!(n − r)!
Results:
1. nC0 = 1
2. nCn = 1
3. nCr = nC − n − r
Example 40. Suppose that there are eight runners in a race. The winner receives rst
prize, the second-place nisher receives second prize, and the third place nisher receives
third prize. How many dierent ways are there to receive these prizes, if all possible
outcomes of the race can occur and there are no ties ?
 30

Solution : The number of ways to pick the three prize winners in the number of ordered
selections of three elements from 8.

∴ P (8, 3) = (8)(7)(6) = 336 possible ways.

Example 41. Suppose that there are 9 faculty members in the mathematics department
and 11 in the computer science department. How many ways are there to select a com-
mittee to develop a discrete mathematics course at a school if the committee is to consist
of three faculty members from the mathematics department and four from the computer
science department ?
Solution : By the product rule, the answer is the product of the number of 3-combinations
of a set with nine elements and the number of 4-combinations of a set with 11 elements.
By theorem, the number of ways to select the committee is

9! 11!
C(9, 3) · C(11, 4) = · = (84)(330) = 27, 720.
3!6! 4!7!

ech
Example 42. A computer password consists of 2 letters of the English alphabet followed
by 3 digits. Find the following: lti T
(i) The total number of passwords that can be used.
(ii) The number of passwords in which no digit repeats.
Solution:
Mu
The password structure consists of 5 slots: L1 L2 D1 D2 D3 .

(i) Total number of passwords In this case, repetition is allowed for both letters and
digits. Each letter slot has 26 possibilities, and each digit slot has 10 possibilities.
h
Tec

Total Passwords = 26 × 26 × 10 × 10 × 10
= 262 × 103
= 676 × 1, 000
Vel

= 676, 000

(ii) Number of passwords with no repeating digits In this case, letters can still
repeat (as no restriction was placed on them), but the digits must be unique.

Total Passwords = 26 × 26 × 10 × 9 × 8
= 676 × 720
= 486, 720

Example 43. Analyze the structure of bit strings of length 12 and determine the number
of bit strings that contain:
(i) Exactly three 1's.
(ii) At most three 1's.
 31

Solution: For a bit string of length n = 12, each position can be either a 0 or a 1.
(i) Number of bit strings containing exactly three 1's
To nd the number of strings with exactly three 1's, we choose 3 positions out of 12
to place the 1's. The remaining 9 positions will automatically be lled with 0's. Using
the combination formula
n!
nCr =
r!(n − r)!
:

12!
12C3 =
3!(12 − 3)!
12 × 11 × 10
=
3×2×1
= 2 × 11 × 10
= 220

220 bit strings with exactly three 1's.

ech
There are
(ii) Number of bit strings containing at most three 1's
"At most three 1's" means the string can contain zero, one, two, or three
lti T 1's. We sum
the combinations for each case:

Total = 12C0 + 12C1 + 12C2 + 12C3

Mu
= 1 + 12 + 66 + 220
= 299

There are 299 bit strings with at most three 1's.

h

Example 44. Examine the placement of digits 1, 2, 3, 4, and 5 and analyze the number
Tec

of three-digit odd numbers that can be formed.

Solution: To form an odd number, the units digit must be chosen from the odd digits
Vel

in the set: {1, 3, 5}.

1. Case 1: Repetition of digits is allowed

ˆ Hundreds place: 5 choices (1, 2, 3, 4, 5)

ˆ Tens place: 5 choices (1, 2, 3, 4, 5)

ˆ Units place: 3 choices (1, 3, 5)

Total numbers = 5 × 5 × 3 = 75.

2. Case 2: Repetition of digits is not allowed

ˆ Units place: 3 choices (must be 1, 3, or 5)
ˆ Hundreds place: 4 choices (remaining digits)

ˆ Tens place: 3 choices (remaining digits)

Total numbers = 4 × 3 × 3 = 36.

 32

Example 45. Analyze the repetition of letters and obtain the number of distinct permu-
tations that can be formed from the letters of each of the following words:
1. RADAR
2. MATHEMATICS
Solution:
1. RADAR
The word RADAR consists of n = 5 letters. The counts of repeating letters are: R
are 2 times, A are 2 times and D is one time
The number of distinct permutations is given by:

5! 120
P = = = 30
2! · 2! · 1! 4
2. MATHEMATICS
The word MATHEMATICS consists of n = 11 letters. The counts of repeating
letters are: M are 2 times, A are 2 times and T are two times others one time.

ech
The number of distinct permutations is given by:

11! 39, 916, 800

lti T
P = = = 4, 989, 600
2! · 2! · 2! 8
Example 46. From a committee consisting of 6 men and 7 women, in how many ways
can we select a committee of:
Mu
(i) 1 men and 4 women
(ii) 4 members which has at least one women
(iii) 4 persons that has at most one gender
h
Tec

(iv) 4 persons of both genders

Solution:
Given: 6 Men, 7 Women. Total = 13 persons.
Vel

(i) 1 men and 4 women

Number of ways = 6C1 × 7C4
7×6×5
6× = 6 × 35 = 210
3×2×1
(ii) 4 members with at least one women
Using the complement (Total - No women):

13C4 − 6C4 = 715 − 15 = 700

(iii) 4 persons of a single gender
Sum of cases for all men or all women:

6C4 + 7C4 = 15 + 35 = 50
(iv) 4 persons of both genders
Total combinations minus single-gender combinations:

13C4 − (6C4 + 7C4 ) = 715 − 50 = 665

 33

Example 47. How many ways are there for eight men and ve women to stand in a line
so that no two women stand next to each other?
Solution:
To ensure no two women are adjacent, we rst arrange the men and then place the
women in the "gaps" created between them.

1. Arrange the 8 Men: The 8 men can be arranged among themselves in 8! ways.

8! = 40, 320

2. Identify the Gaps: When 8 men stand in a line, they create 8+1 = 9 possible
positions (gaps) where women can stand (including the ends of the line).

_M1 _M2 _M3 _M4 _M5 _M6 _M7 _M8 _

Arrange the 5 Women:

ech
3. We must choose 5 gaps out of the 9 available and arrange
9
the 5 women in them. This is represented by the permutation P5 :

9 9! lti T
P5 = = 9 × 8 × 7 × 6 × 5 = 15, 120
(9 − 5)!

∴ The total number of arrangements is

Mu
Total Ways = 8! × 9 P5
= 40, 320 × 15, 120
= 609, 638, 400
h
Tec
Vel
 34

2.4 Recurrence Relations

Denition :
A recurrence relation for the sequence {an } is an equation that shows an in terms of
one or more of the previous terms of the sequence a0 , a1 , ... an−1 , for all integers n with
n ≥ n0 , where n0 is a non-negative integer.
Note : A sequence is called a solution of a recurrence relation if its terms satisfy the
recurrence relation.

Example 48. Write an explicit formula for an , if an = 3an−1 with a1 = 2.

Solution:

an = 3an−1
r =3
an = a1 rn−1

ech
∴ an = 2(3)n−1
Example 49. Solve the recurrence relation an = 6an−1 − 9an−2 if a0 = 1, a1 = 6
lti T
Solution:
an = 6an−1 − 9an−2 a0 = 1, a1 = 6
an − 6an−1 + 9an−2 = 0
Mu
The C.E is

r2 − 6r + 9 = 0
h

(r − 3)(r − 3) = 0
Tec

r = 3, r=3
The roots are equal

an = (C1 + C2 n)rn
∴ an = (C1 + C2 n)(3)n
Vel

(1)

a0 = 1, a1 = 6
F or n = 0 :
a0 = (C1 + C2 (0))30
1 = C1
∴ C1 = 1

F or n = 1 :
a1 = (C1 + C2 )(3)1
6 = (1 + C2 )3
2 − 1 = C2
∴ C2 = 1
∴ an = (1 + n)(3)n
 35

Example 50. Let an = 2n + (5)(3n ) for n = 0, 1, 2, . . .

(a) Find a0 , a1 and a2 . (b) Show that a4 = 5a3 − 6a2 .
Solution :
(a) Given : an = 2n + (5)(3n )
a0 = 20 + (5)(30 ) = 1 + (5)(1) = 6

a1 = 21 + (5)(31 ) = 2 + (5)(3) = 17

a2 = 22 + (5)(32 ) = 4 + (5)(9) = 49
(b) Given : an = 2n + 5(3n )
a3 = 23 + 5(33 ) = 8 + 5(27) = 143
To prove : a4 = 5a3 − 6a2

ech
L.H.S. = a4 = 24 + 5(34 ) = 16 + 5(81) = 421

R.H.S. = 5a3 − 6a2lti T

= 5(143) − 6(49)

= 715 − 294
Mu
= 421
L.H.S. = R.H.S. Hence the proof.

Example 51.
h
Tec

A sequence is dened by the recurrence relation an = −3an−1 −3an−2 −an−3 with initial
conditions a0 = 5, a1 = −9, a2 = 15. Evaluate the solution of this recurrence relation by
solving it using an appropriate method and justify the validity of the obtained solution
Vel

with respect to the given initial conditions.

Soln;
an = −3an−1 − 3an−2 − an−3
a0 = 5, a1 = −9, a2 = 15
C.E (Characteristic Equation):
r3 + 3r2 + 3r + 1 = 0
(r + 1)3 = 0
∴ r = −1
Roots are equal:
an = (C1 + C2 n + C3 n2 )rn
an = (C1 + C2 n + C3 n2 )(−1)n
Applying initial conditions:
 36

ˆ For a0 = 5:

5 = (C1 + C2 (0) + C3 (0))(−1)0

∴ C1 = 5

ˆ For a1 = −9:

−9 = (C1 + C2 + C3 )(−1)1
9 = 5 + C2 + C 3
C2 + C3 = 4 . . . (1)

ˆ For a2 = 15:

15 = (C1 + 2C2 + 4C3 )(−1)2

15 = 5 + 2C2 + 4C3
10 = 2C2 + 4C3

ech
Divide by 2: C2 + 2C3 = 5 ... (2)

Solving equations 1 and 2 : O O lti T O

Subtract 1 from 2 : O
(C2 + 2C3 ) − (C2 + C3 ) = 5 − 4
∴ C3 = 1

O
Mu
Substitute C3 = 1 in 1 :

C2 + 1 = 4
h

∴ C2 = 3
Tec

Final Solution:
an = (5 + 3n + n2 )(−1)n
Example 52. A factory makes custom sports cars at an increasing rate, in the rst
Vel

month only one car is made; in the second month two cars are made, and so on, with n
cars made with nth month.
i) Set up recurrence relation for the number of cars produced in the rst n months by
the factory.
ii) How many cars are produced in the rst year.
Soln:
i) Cars produced:

Month 1=1
Month 2=2
Month 3=3

Recurrence relation:
an = an−1 + n for n≥2
 37

ii) Cars produced in rst year:

a12 = 1 + 2 + 3 + · · · + 12
n(n + 1)
an =
2
12(13)
a12 =
2
∴ a12 = 78

Total cars produced in rst year = 78.

2.5 Linear Recurrence Relations

Denition :
A linear recurrence relation with constant coecient is of the form

ech
c0 an + c1 an−1 + c2 an−2 + · · · + ck an−k = f (n)

where C is are constants.

lti T
A linear homogeneous recurrence relation with constant coecients of degree K is of
the form
an = c1 an−1 + c2 an−2 + · · · + ck an−k , where c 1 , c2 , . . .
Mu
ck are real numbers, and ck ̸= 0.
The three methods of solving recurrence relations are
h

1. Iteration
Tec

2. Characteristic roots

3. Generating functions.

Example 53. Find an explicit formula for the Fibonacci

Vel

numbers.

Solution : The sequence of Fibonacci numbers satises the recurrence relation

fn = fn−1 + fn−2 (1)

and satises the initial conditions f0 = 0 and f1 = 1

(1) ⇒ fn − fn−1 − fn−2 = 0 (2)

Let fn = r n be a solution of the given equation

(2) ⇒ rn − rn−1 − rn−2 = 0

 
n 1 1
r 1− − 2 =0
r r
 38

∴ The characteristic equation is r2 − r − 1 = 0

p
1 ± (−1)2 − 4(1)(−1)
r=
√ 2
1± 1+4
r=
2
√ √
1+ 5 1− 5
Let r1 = 2
, r2 = 2
∴ By theorem
√ !n √ !n
1+ 5 1− 5
fn = α1 + α2 (3)
2 2
√ !0 √ !0
1+ 5 1− 5
f 0 = 0 ⇒ f 0 = α1 + α2 =0
2 2
⇒ α1 + α2 = 0 (4)
√ ! √ !

h
1+ 5 1− 5
f1 = 1 ⇒ f1 = α1 + α2 =1

Tec
2 2
√ √
5)α1 + (1 − 5)α2
(1 + =2 (5)
√ √ √
(4) × (1 + 5) ⇒ (1 + 5)α1 + (1 + 5)α2 =0
ulti
(6)
√ √
(5) × 1 ⇒ (1 + 5)α1 + (1 − 5)α2 =2 (7)
√
(6) − (7) ⇒ 2 5α2 = −2
hM

−1
α2 = √
5
1
(4) ⇒ α1 = √
Tec

5
  √ !n √ !n
1 1+ 5 1 1− 5
(3) ⇒ fn = √ −√ (8)
5 2 5 2
Vel

2.6 Generating Functions

Example 54. Find a closed form for the generating function an = 5 for all n = 0, 1, 2, . . .
Solution : Given : an = 5 for all n = 0, 1, 2, . . .

(i.e.,) a0 = 5, a1 = 5, a2 = 5, a3 = 5, . . .
(i.e.,) 5, 5, 5, 5, . . .
The generating function of 5, 5, 5, 5, . . . is

5 + 5x + 5x2 + . . . = 5[1 + x + x2 + . . . ]
= 5[1 − x]−1
5
=
1−x
5
∴ G(x) = 1−x
which is the G.F. of the given sequence.
 39

Example 55. Use generating functions to solve the recurrence relation

an = 3an−1 + 2 with the initial condition a0 = 1.
Solution: P ∞ n
LetG(x) = n=0 an x . . . (1)
where G(x) is the G.F (Generating Function) for the sequence {an }.
Given: an = 3an−1 + 2
Multiply by xn and sum from n=1 to ∞:
∞
X ∞
X ∞
X
n n
an x = 3 an−1 x + 2 xn
n=1 n=1 n=1

Rewriting the sums in terms of G(x):

∞  
X
n−1 1
G(x) − a0 = 3x an−1 x +2 −1
n=1
1−x
P∞ P∞
Since xG(x) = an xn+1 = an−1 xn , we substitute:

ech
n=0 n=1
 
1
G(x) − a0 = 3xG(x) + 2 −1
1−x
lti T
Using a0 = 1:  
1
G(x) − 3xG(x) = 1 + 2 −1
1−x
Mu
 
1−1+x
G(x)[1 − 3x] = 1 + 2
1−x
2x
G(x)[1 − 3x] = 1 +
h

1−x
1 − x + 2x 1+x
Tec

G(x)[1 − 3x] = =
1−x 1−x
1+x
⇒ G(x) = . . . (2)
(1 − x)(1 − 3x)
Vel

Partial Fractions: Let

1+x
(1−x)(1−3x)
= A
1−x
+ B
1−3x

1 + x = A(1 − 3x) + B(1 − x)

Put x = 1: Put x = 0:

1 + 1 = A(1 − 3) 1=A+B
2 = −2A 1 = −1 + B
A = −1 B=2

Substituting A and B back into (2):

2 1
G(x) = −
1 − 3x 1 − x
∞
X ∞
X X∞
n n n
an x = 2 3 x − xn
n=0 n=0 n=0
Hence an = 2(3 ) − 1 which is the required solution.
n
 40

Example 56. To nd G.F of a sequence 1, 2, 3, . . . , ∞

Soln: 1, 2, 3, . . . , ∞ = a0 , a1 , a2 , . . . , ∞
G(x) = a0 + a1 x + a2 x2 + . . . ∞
∞
X
= 1 + 2x + 3x2 + . . . ∞ = (n + 1)xn
n=0
−2
= (1 − x)
1
∴ G(x) =
(1 − x)2
Example 57. Examine the recurrence relation yn+2 − 6yn+1 + 5yn = 0 with y0 = 2 and
y1 = 6 and analyze the use of generating functions in solving it.

Soln:
yn+2 − 6yn+1 + 5yn = 0

ech
y0 = 2, y1 = 6
Generating function:
G(x) =
lti T
∞
X
yn xn
n=0
∞
G(x) − y0
Mu
X
yn+1 xn =
n=0
x

∞
h

X G(x) − y0 − y1 x
yn+2 xn =
Tec

n=0
x2
∞
X ∞
X ∞
X
n n
yn+2 x − 6 yn+1 x + 5 yn xn = 0
n=0 n=0 n=0
Vel

G(x) − y0 − y1 x G(x) − y0
2
−6 + 5G(x) = 0
x x
Multiplying by x2 :

G(x) − 2 − 6x − 6x(G(x) − 2) + 5x2 G(x) = 0

G(x) − 2 − 6x − 6xG(x) + 12x + 5x2 G(x) = 0
G(x)[1 − 6x + 5x2 ] + (6x − 2) = 0
G(x)(1 − 6x + 5x2 ) = 2 − 6x

Generating function:

2 − 6x
G(x) =
1 − 6x + 5x2
1 − 6x + 5x2 = (1 − x)(1 − 5x)
2 − 6x
G(x) =
(1 − x)(1 − 5x)
 41

Partial fraction:

2 − 6x A B
= +
(1 − x)(1 − 5x) 1 − x 1 − 5x
2 − 6x = A(1 − 5x) + B(1 − x) (1)

Solving (1) we get

A = 1, B=1

1 1
∴ G(x) = +
1 − x 1 − 5x
X X
G(x) = xn + 5n xn
X
G(x) = (1 + 5n )xn

ech
∴ yn = 1 + 5n

2.7 Inclusion and Exclusion

lti T
Example 58. 40 computer programmers interviewed for a job. 25 knew JAVA, 28 knew
ORACLE, and 7 knew neither language. How many knew both languages ?
Mu
Solution :
J represent JAVA
O represent ORANGE
h
Tec

|J| = 25
|O| = 28
|J ∪ O| = 40 − 7 = 33
Vel

Computer programmers who knew both languages are

|J ∩ O| = |j| + |O| − |J ∪ O|

|J ∩ O| = 25 + 28 − 33 = 20.

Example 59. A total of 1232 students have taken a course in Tamil, 879 have taken
a course in English and 114 have taken a course in Telugu. Further, 103 have taken
courses in both Tamil and English, 23 have taken courses in both Tamil and Telugu and
14 have taken courses in both English and Telugu. If 2092 students have taken at least
one of Tamil, English and Telugu, how many students have taken a course in all three
languages?
Solution : Let

T → students who have taken a course in Tamil.

E→ students who have taken a course in English.

 42

R→ students who have taken a course in Telugu.

|T | = 1232, |E| = 879, |R| = 114

i.e.,
|T ∩ E| = 103, |T ∩ R| = 23, |E ∩ R| = 14
and
|T ∪ E ∪ R| = 2092
by the principle of inclusion and exclusion we get

|T ∪ E ∪ R| = |T | + |E| + |R| − |T ∩ E| − |T ∩ R| − |E ∩ R| + |T ∩ E ∩ R|
2092 = 1232 + 879 + 114 − 103 − 23 − 14 + |T ∩ E ∩ R|
|T ∩ E ∩ R| = 7

Therefore, there are 7 students who have taken courses in Tamil, English and Telugu.

Example 60. Among the rst 1000 positive integers:

Determine the integers which are not divisible by 5, nor by 7, nor by 9.
Solution:

ech
Let

A be the set of number of integers divisible by 5

lti T
B be the number of integers divisible by 7.

C be the number of integers divisible by 9.

Mu
 
1000
∴ |A| = = 200
5
 
1000
h

|B| = = 142
7
Tec

 
1000
|C| = = 111
9
 
1000
Vel

|A ∩ B| = = 28
5×7
 
1000
|A ∩ C| = = 22
5×9
 
1000
|B ∩ C| = = 15
7×9
 
1000
|A ∩ B ∩ C| = =3
5×7×9
The number of integers divisible by 5, 7 and 9.

|A ∪ B ∪ C| = 200 + 142 + 111 − 28 − 22 − 15 + 3

= 391

The number of integers not divisible by 5, nor by 7, nor by 9.

= Total number of integers − integers divisible by 5, 7 and 9

= 1000 − 391 = 609

 43

Example 61. Analyse the integers from 1 to 250 by examining the divisibility properbes
with respect to 2, 3, 5, and 7, and day persist the inchesion-extusten principle
Solution:
Let S = {x ∈ Z | 1 ≤ x ≤ 250}. We seek the cardinality of the union of sets
A2 , A3 , A5 , and A7 , where An is the set of integers divisible by n.
1. Individual Set Cardinalities
|A2 | = ⌊ 250
2
⌋ = 125
250
|A3 | = ⌊ 3 ⌋ = 83
|A5 | = ⌊ 250
5
⌋ = 50
|A7 | = ⌊ 250
7
⌋ = 35

Sum of singles (S1 ) = 125 + 83 + 50 + 35 = 293.

2. Intersections of Two Sets
ˆ |A ∩ A | = ⌊ 250
⌋

ech
2 3 6
= 41

ˆ |A ∩ A | = ⌊
2 5
250
10
⌋ = 25

ˆ |A ∩ A | = ⌊
2 7
250
14
⌋ = 17
lti T
ˆ |A ∩ A | = ⌊
3 5
250
15
⌋ = 16

ˆ |A ∩ A | = ⌊ 250
⌋
Mu
3 7 21
= 11

ˆ |A ∩ A | = ⌊
5 7
250
35
⌋ =7

Sum of doubles (S2 ) = 41 + 25 + 17 + 16 + 11 + 7 = 117.

h

3. Intersections of Three and Four Sets Sum of triples (S3 ):

Tec

|A2 ∩ A3 ∩ A5 | = ⌊ 250
30
⌋=8
250
|A2 ∩ A3 ∩ A7 | = ⌊ 42 ⌋ = 5
|A2 ∩ A5 ∩ A7 | = ⌊ 250
Vel

70
⌋=3
250
|A3 ∩ A5 ∩ A7 | = ⌊ 105 ⌋ = 2

S3 = 8 + 5 + 3 + 2 = 18.
250
Sum of quadruples (S4 ): |A2 ∩ A3 ∩ A5 ∩ A7 | = ⌊ ⌋ = 1.
210
4. Final Calculation By the Principle of Inclusion-Exclusion:
|A2 ∪ A3 ∪ A5 ∪ A7 | = S1 − S2 + S3 − S4

|A2 ∪ A3 ∪ A5 ∪ A7 | = 293 − 117 + 18 − 1 = 193

The number of integers from 1 to 250 not divisible by 2, 3, 5, or 7 is:

250 − 193 = 57
Vel
Tec
h Mu
lti T
ech
44