DISCRETE MATHEMATICAL STRUCTURES, DEPT.

OF AIML

Module-1: Fundamentals of Logic

Overview:
Propositional logic is a branch of mathematics that studies the logical relationships
between propositions (or statements, sentences, assertions) taken as a whole, and
connected via logical connectives.
A proposition is the basic building block of logic. It is defined as a declarative sentence
that is either True or False, but not both. The Truth Value of a proposition is
True(denoted as T) if it is a true statement, and False(denoted as F) if it is a false
statement. For Example,
1. The sun rises in the East and sets in the West.
2. 1 + 1 = 2
3. ‘b’ is a vowel.
All of the above sentences are propositions, where the first two are Valid(True) and the
third one is Invalid(False). Some sentences that do not have a truth value or may have
more than one truth value are not propositions. For Example,
1. What time is it?
2. Go out and Play
3. x + 1 = 2
The above sentences are not propositions as the first two do not have a truth value, and
the third one may be true or false. To represent propositions, propositional
variables are used. By Convention, these variables are represented by small alphabets
such as 𝑝,𝑞,𝑟,𝑠 p,q,r,s . The area of logic which deals with propositions is
called propositional calculus or propositional logic. It also includes producing new
propositions using existing ones. Propositions constructed using one or more
propositions are called compound propositions. The propositions are combined
together using Logical Connectives or Logical Operators.

Basic Connectives and Truth Tables

Since we need to know the truth value of a proposition in all possible scenarios, we
consider all the possible combinations of the propositions which are joined together by
Logical Connectives to form the given compound proposition. This compilation of all
possible scenarios in a tabular format is called a truth table. Most Common Logical
Connectives-

1. Negation
If 𝑝 is a proposition, then the negation of 𝑝 is denoted by ¬𝑝 , which when translated
to simple English means- “It is not the case that p” or simply “not p“. The truth value of -
p is the opposite of the truth value of p. The truth table of -p is:
p ¬p

T F

F T

Page |1
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Example, Negation of “It is raining today”, is “It is not the case that is raining today” or
simply “It is not raining today”.

2. Conjunction
For any two propositions p and q , their conjunction is denoted by 𝑝∧𝑞 , which means
“ p and 𝑞 “. The conjunction 𝑝∧𝑞 is True when both p and 𝑞 are True, otherwise False.
The truth table of 𝑝∧𝑞 is:
p q p∧q

T T T

T F F

F T F

F F F

Example, Conjunction of the propositions p – “Today is Friday” and q – “It is raining

today”, p∧q is “Today is Friday and it is raining today”. This proposition is true only on
rainy Fridays and is false on any other rainy day or on Fridays when it does not rain.

3. Disjunction
For any two propositions p and 𝑞 , their disjunction is denoted by p∨q , which means
“p or 𝑞 “. The disjunction 𝑝∨𝑞 is True when either p or 𝑞 is True, otherwise False. The
truth table of 𝑝∨𝑞 is:
p q p∨q

T T T

T F T

F T T

F F F

Example, Disjunction of the propositions p – “Today is Friday” and q – “It is raining

today”, p∨q is “Today is Friday or it is raining today”. This proposition is true on any
day that is a Friday or a rainy day (including rainy Fridays) and is false on any day other
than Friday when it also does not rain.

4. Exclusive Or
For any two propositions p and 𝑞 , their exclusive or is denoted by 𝑝⊕𝑞, which means
“either p or 𝑞 but not both”. The exclusive or 𝑝⊕𝑞 is True when either p or 𝑞 is True,
and False when both are true or both are false. The truth table of 𝑝⊕𝑞 is:

Page |2
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

p q p⊕q

T T F

T F T

F T T

F F F

Example, Exclusive or of the propositions p – “Today is Friday” and q – “It is raining

today”, 𝑝⊕𝑞 is “Either today is Friday or it is raining today, but not both”. This
proposition is true on any day that is a Friday or a rainy day(not including rainy Fridays)
and is false on any day other than Friday when it does not rain or rainy Fridays.

5. Implication
For any two propositions p and 𝑞 , the statement “ifp then 𝑞 ” is called an implication
and it is denoted by 𝑝→𝑞 . In the implication 𝑝→𝑞 , p is called
the hypothesis or antecedent or premise and q is called the conclusion or consequence.
The implication is 𝑝→𝑞 is also called a conditional statement. The implication is false
when p is true and q is false otherwise it is true. The truth table of 𝑝→𝑞 is:
p q p→q

T T T

T F F

F T T

F F T

One might wonder that why is 𝑝→𝑞 true when p is false. This is because the implication
guarantees that when p and 𝑞 are true then the implication is true. But the implication
does not guarantee anything when the premise p is false. There is no way of knowing
whether or not the implication is false since p did not happen. This situation is similar
to the “Innocent until proven Guilty” stance, which means that the implication p→q is
considered true until proven false. Since we cannot call the implication 𝑝→𝑞 false
when p is false, our only alternative is to call it true.

Example, “If it is Friday then it is raining today” is a proposition which is of the

form 𝑝→𝑞 . The above proposition is true if it is not Friday(premise is false) or if it is
Friday and it is raining, and it is false when it is Friday but it is not raining.

Page |3
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

6. Biconditional or Double Implication

For any two propositions p and 𝑞, the statement “p if and only if(iff) 𝑞 ” is called a
biconditional and it is denoted by 𝑝↔𝑞. The statement 𝑝↔𝑞 is also called a bi-
implication. p↔q has the same truth value as (𝑝→𝑞)∧(𝑞→𝑝) The implication is true
when p and 𝑞 have same truth values, and is false otherwise. The truth table of 𝑝↔𝑞 is:
p q p↔q

T T T

T F F

F T F

F F T

Some other common ways of expressing p↔q are:

“p is necessary and sufficient for q” if p then q, and conversely p if q”
Example, “It is raining today if and only if it is Friday today.” is a proposition which is of
the form 𝑝↔𝑞. The above proposition is true if it is not Friday and it is not raining or if
it is Friday and it is raining, and it is false when it is not Friday or it is not raining.

Identify Statement and Propositions:

1. “Elephants are bigger than mice.”
Is this a statement? - Yes
Is this a proposition? – Yes
What is the truth value - True
of the proposition?

2. “520 < 111”

Is this a statement? - Yes
Is this a proposition? – Yes
What is the truth value - False
of the proposition?

3. “y > 5”
Is this a statement? - Yes
Is this a proposition? – No
What is the truth value – Depends on value of y – Open Statement
of the proposition?

4. “Today is January 27 and 99 < 5.”

Is this a statement? - Yes
Is this a proposition? – Yes
What is the truth value - False
of the proposition?

5. “Please do not fall asleep.”

Page |4
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Is this a statement? - No, as it is a request

Is this a proposition? – No
What is the truth value – Not applicable
of the proposition?

6. “If the moon is made of cheese then I will be rich.”

Is this a statement? - Yes
Is this a proposition? – Yes
What is the truth value – Probably true
of the proposition?

7. “x < y if and only if y > x.”

Is this a statement? - Yes
Is this a proposition? – Yes
What is the truth value – True
of the proposition?

Express the following problems using logical connectives

1. To take discrete mathematics, you must have taken calculus or a course in
computer science

Soln: Let,
P: take discrete mathematics
Q: take calculus
R: take a course in computer science
Then, P → Q  R

2. When you buy a new car from Acme Motor Company, you get $2000 back in cash
or a 2% car loan.

Solution: Let,
P: buy a car from Acme Motor Company
Q: get $2000 cash back
R: get a 2% car loan

• Then, P → Q  R

3. School is closed if more than 2 feet of snow falls or if the wind chill is below -100

Solution: Let,
P: School is closed
Q: 2 feet of snow falls
R: wind chill is below -100

• Then, Q  R → P

Express following logical statements in English

1.
s: Phyllis goes out for a walk

Page |5
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

t: The moon is out

u: It is snowing
(t  u) → s
Solution:
If the moon is out and it is not snowing then Phyllis goes out for a walk.

2. s: Phyllis goes out for a walk

t: The moon is out
u: It is snowing
t→ (u → s)
Solution:
If the moon is out and it is not snowing then Phyllis goes out for a walk.

3. s: Phyllis goes out for a walk

t: The moon is out
u: It is snowing
 (s  (u  t))

Solution: It is not the case that Phyllis go out for a walk if and only if either moon
is out or it is snowing

Logically Equivalence
An expression's statements are considered logically equivalent if they return identical
truth values for every row in a truth table. In computing, logical equivalence is important
in the design of digital circuits. If multiple circuits are logically equivalent, they have
identical truth table values.

Prove that the statements (PQ) and (P)  (Q) are logically equivalent
Solution:

P Q (PQ) (PQ) P Q (P)(Q)

0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

Tautologies and Contradiction

Tautologies
A proposition P is a tautology if it is true under all circumstances. It means it contains the
only 1 in the final column of its truth table.

Example: Prove that the statement (p⟶q) ↔(q⟶p) is a tautology.

Solution: Make the truth table of the above statement:

Page |6
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

p q p→q q p q⟶p (p→q)⟷( q⟶p)

0 0 1 1 1 1 1
0 1 1 0 1 1 1
1 0 0 1 0 0 1
1 1 1 0 0 1 1
As the final column contains all 1’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.

Solution:
p p p ∧p
0 1 0
1 0 0
Since, the last column contains all 0's, so it's a contradiction.

Definition: two propositional statements S1 and S2 are said to be (logically) equivalent,

denoted S1  S2 if
They have the same truth table, or
S1⟷ S2 is a tautology
Equivalence can be established by
Constructing truth tables
Using equivalence laws
Equivalence Laws:
Identity laws, P  T  P,
Domination laws, P  F  F,
Idempotent laws, P  P  P,
Double negation law,  ( P)  P
Commutative laws, P  Q  Q  P,
Associative laws, P  (Q  R) (P  Q)  R,
Distributive laws, P  (Q  R) (P  Q)  (P  R),
De Morgan’s laws,  (PQ)  ( P)  ( Q)
Law with implication P→QPQ
Absorption Laws pV(p q) p, p (p V q) p

Problem: Show that (P → Q)  (P → R)  P → (Q  R): by equivalence laws

Solution:
Given,
(P → Q)  (P → R)  P → (Q  R)
( P  Q)  ( P  R)  ( P  (Q  R)) [Law of Implication]
( P  Q)  ( P  R)  ( P  Q)  ( P  R) [Distribution of  over ]

Principle of Duality

Page |7
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

If s and t are any statements that contain no logical connectives other than  and V, and
if s ↔ t, then 𝑠 𝑑 ⟷ 𝑡 𝑑
Substitution rule: If compound statement P is a tautology, and p is a primitive statement
that appears in P, and replaced by q in P1, P1 is also a tautology

Problem: Negate and simplify the compound statement:

(p V q) → r

Solution:
 ((p V q) → r )
 ((p V q)) V  r ) [Law of Implication]
p  q V  r [Demorgans Law]

Problem: Let:
p:Joan goes to Lake George
q:Mary pays for Joans shopping spree
Find negation of p →q

Solution:
(p→q)
=(p V q) [Law of Implication]
= p  q [Demorgans Law]
Joan goes to Lake George but Mary does not pay for Joans shopping spree

Converse, Inverse and Contrapositive

If there is a conditional statement x → y, then
o The converse statement will be y → x
o The inverse statement will be x → y
o The contrapositive statement will be y → x

Note: Implication and contrapositives are equivalent

Problem: Let:
p: Jeff is concerned about his LDL and HDL values
q: Jeff walks atleast 2 miles three times a week
Find implication, contrapositive, converse and inverse
Solution:
Implication: p→q, If Jeff is concerned about his LDL and HDL values, then Jeff will walk
atleast 2 miles three times a week

Page |8
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Contrapositive: q p, If Jeff does not walk atleast 2 miles three times a week, then he is
not concerned about his LDL and HDL values
Converse: : q→p, If Jeff walks atleast 2 miles three times a week, then he is concerned
about his LDL and HDL values
Inverse: p → q, If Jeff is not concerned about his LDL and HDL values, then Jeff will not
walk atleast 2 miles three times a week

Problem: Simplify
1. (p V q)  (p  q)
Solution:
(p V q)  (p  q)
= (p V q)  (p V q) [Demorgan Law]
=(p V (q  q)) [ Distribution Law]
=pVT=p
2. [[(p V q)  r] V q]
Solution:
[[(p V q)  r] V q]
= ((p V q)  r)  q [Demorgans Law]
= ((p V q)  r)  q [Double negation]
= (p V q)  (r  q) [Associative Law]
= (p V q)  (r  q) [Commutative Law]
= ((p V q)  q)  r [Associative Law]
= q  r [Absorption Law]

Switching network
❖ It is made of wires and switches connecting 2 terminals
❖ Current flows when switch is closed (1) and does not flow if its open(0)
Eg:

Represents parallel flow: p V q

Represents serial flow: p  q

Page |9
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem:
1. Represent this network with logic

Solution:
There are 3 stages one after the another
Stage1: p V q V r
Stage 2: p V t V q
Stage 3: p V t V r
Three stages are in serial
Hence resulting representation is: (p V q V r)  (p V t V q)  (p V t V r)
2.

There are 2 stages:

Stage 1: p
Stage 2: Again there are stages:
Stage 2(a): r
Stage 2(b): there are 2 stages:
Stage 2(b)(1): t
Stage 2(b)(2): q
Hence Stage 2(b) is t v q

Stage 2: r  (t v q)
Stage 1: p V (r  (t v q))
Final solution: p V (r  (t v q))
Logical Implication
It is of the format:

P a g e | 10
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

((p1 𝛬 p2 𝛬 p3 𝛬.. 𝛬 pn) ⟶ q )

❑ Where, p1,p2,..pn are called premises
❑ q is called conclusion
❑ Hence for validity of this implication, it should lead to a tautology

Problem:
p: Roger studies
q: Roger plays racketball
r: Roger passes discrete mathematics
Let p1,p2 and p3 be premises:
p1: If Roger studies, then he will pass discrete mathematics
p2: If Roger does not play racketball, then he will study
p3: Roger failed discrete mathematics
q: Roger plays racketball
Establish the validity of the argument

Solution:
Truth table approach:
p q r p1: p2: p3: (p1 p2 (p1 p2
p→r q →p r p3) p3) →q
0 0 0 1 0 1 0 1

0 0 1 1 0 0 0 1

0 1 0 1 1 1 1 1

0 1 1 1 1 0 0 1

1 0 0 0 1 1 0 1

1 0 1 1 1 0 0 1

1 1 0 0 1 1 0 1

1 1 1 1 1 0 0 1

Since the resulting column is a tautology, the validity of the argument is established

Points to note:
❖ If p⟶q is established as tautology, then p is said to logically imply q and denoted
by p ⟹q
❖ If p⟷q is established as tautology, then p is said to logically double imply q and
denoted by p ⟺q
❖ If both p⟶q and q ⟶ p is established as tautology, then p ⟺q

Problem: Verify ¬(p 𝜦 q) ⟺ ¬p V ¬q

P a g e | 11
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Solution: Construct Truth table

p q p  q ( p  q) p q p V q
0 0 0 1 1 1 1

0 1 0 1 1 0 1

1 0 0 1 0 1 1

1 1 1 0 0 0 0

Since truth table entries are same, the validity of the logical implication is established

Definitions
• Argument – A sequence of statements, and premises, that end with a
conclusion.
• Validity – A deductive argument is said to be valid if and only if it takes a
form that makes it impossible for the premises to be true and the conclusion
nevertheless to be false.
• Fallacy – An incorrect reasoning or mistake which leads to invalid
arguments.

Rules of Inference
Simple arguments can be used as building blocks to construct more complicated valid
arguments. Certain simple arguments that have been established as valid are very
important in terms of their usage. These arguments are called Rules of Inference. The
most commonly used Rules of Inference are tabulated below –
Rules of Inference Name
𝑝,𝑝→𝑞, Modus Ponens
∴𝑞
¬q, p → q, Modus Tollens
∴ ¬p
p → q, Law of Syllogism
q → r,
∴p→r
¬p, p ∨ q, Disjunctive Syllogism
∴q
p, Rule of Disjunctive Amplification
∴ (p ∨ q)
p,q Rule of conjunction
∴ (p  q)
(p  q) Rule of Conjunctive Simplification
∴p, q

Example of Modus ponens

Lydia wins 10 million dollar lottery
If Lydia wins 10 million dollar lottery, then Kay will quit her job
∴ Kay will quit her job

P a g e | 12
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

If Allison vacations in Paris, then she have to win a scholarship

Allison is vacationing in Paris
∴ Allison won a scholarship

Example:

1) Rita is baking a cake

2) If Rita is baking a cake, then she is not practicing her flute
3) If Rita is not practicing her flute, then her father will not buy a new car
Conclusion:
Rita’s father will not buy a new car [ From Law of Syllogism]

Example of Modus Tollens

If Cannie is selected president of Phi Delta sorority, Helen will pledge sorority Helen did not
pledge Phi Delta sorority
∴ Cannie was not selected president of Phi Delta sorority

Prove using Laws of Logical Inference

1.

Solution:
Reduction Rule
p → r , r→s = p →s Law of syllogism
t V¬s = ¬s V t Commutative Law
¬s V t = s → t Law of implication
¬t V u = t → u Law of implication
s → t, t → u = s → u Law of syllogism
p →s, s → u = p → u Law of syllogism
p → u, ¬u = ¬p Modus Tollens

P a g e | 13
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem:
If Margaret Thatcher is the president of United States, then she is atleast 35 years old
Margaret Thatcher is atleast 35 years old
Can we conclude Margaret Thatcher is the president of United States
Solution:
p: Margaret Thatcher is the president of United States
q: She is atleast 35 years old
Given,
p→q
q
Truth table:
p q p→q (p→q) q ((p→q) q) →p
0 0 1 0 1

0 1 1 1 0

1 0 0 1 1

1 1 1 1 1

Since the resulting column is not tautology, we cannot conclude Margaret Thatcher is the
president of United States

Problem: Establish the validity of the argument

Solution:
Reduction Rule
p → r , = ¬r → ¬p Implication and contrapositive are
equivalent
¬r → ¬p, ¬p → q, ¬r → q Law of syllogism
¬r → q, q → s = ¬r → s Law of syllogism

Problem: Prove the following conclusion

Hypothesis: If I joined JNNCE, I will get best education. If I got best education, then I will get
job in USA. If I get job in USA, then I will become millionaire. I joined JNNCE.
Conclusion: I became millionaire
Solution:
Let, p: I joined JNNCE
q: I got best education
r: I got job in USA
s: I became millionaire
Hence given:
p→ q, q→ r, r→ s

P a g e | 14
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Proof:
Reduction Rule
p → q, q→ r = p→ r Law of syllogism
p→ r, r→ s = p→ s Law of syllogism
p→ s, p = s Modus ponens
Hence, I became millionaire

Problem: Establish the validity of the argument

Solution:
Reduction Rule
p → q, q→ (r s) = p → (r s) Law of syllogism
p  t = p, t Law of Conjunctive Simplification
p → (r s), p = (r s) Modus ponens
(r s) = r, s Law of Conjunctive Simplification
¬r V (¬t V u) =(¬r V ¬t) V u Associative Law
¬(r t) V u Demorgans Law
¬(r t) V u=(rt) → u Implication rule
r, t= rt Rule of Conjunction
(rt) → u, rt = u Modus ponens

Problem: Prove the following

Hypothesis: If band could not play rock music or the refreshments were not delivered on
time, then New Year party would have been cancelled and Alicia would have been angry. If
the party were cancelled, then refunds would have to be made. No refunds were made.
Conclusion: Band could play rock music
Proof:
Let p: Band play rock music,
q: Refreshments were delivered on time
r: New year party is cancelled
s:Alicia is angry
t: Refunds have to be made
Given:
¬p V ¬q → rs
r→t
¬t
Proof:
Reduction Rule
r→t, ¬t = ¬r Modus Tollens
¬r= ¬r V ¬s Law of Disjunctive Amplification

P a g e | 15
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

¬r V ¬s = ¬(r  s) Demorgans Law

¬p V ¬q → rs, ¬(r  s) Modus Tollens
= ¬(¬p V ¬q)
¬(¬p V ¬q) = p  q Double Negation rule
p  q= p, q Law of Conjunctive Simplification
Hence, Band could play rock music

Problem: Establish the validity of the argument using Proof by contradiction

Solution:
For proof by contradiction, conclusion becomes premise as negation
Hence p becomes ¬p
Reduction Rule
¬p ⟷q= ¬p ⟶q and q⟶¬p Double Implication Equivalence
¬p ⟶q, q ⟶ r = ¬p ⟶ 𝑟 Law of Syllogism
¬p ⟶ 𝑟, ¬r = ¬¬p Modus Tollens
¬¬p=p Double Negation
Also we have ¬p due to assumption
of contradiction
But we proved p which is a
contradiction of our assumption,

Establish the validity of the argument using Proof by contradiction

Proof:
For proof by contradiction, conclusion becomes premise as negation
Hence ¬p becomes p
Reduction Rule
p, p ⟶ (q  r) = (q  r) Modus ponens
(q  r) = q, r Law of conjunctive simplification
r, r ⟶ 𝑠 = s Modus ponens
q, s = (q  s) Law of conjunction
(q  s), ¬(q  s) Contradiction , hence ¬p is correct

P a g e | 16
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Quantifiers
Quantifier is used to quantify the variable of predicates. It contains a formula, which is a
type of statement whose truth value may depend on values of some variables. When we
assign a fixed value to a predicate, then it becomes a proposition. In another way, we can
say that if we quantify the predicate, then the predicate will become a proposition. So
quantify is a type of word which refers to quantifies like "all" or "some".
There are mainly two types of quantifiers that are universal quantifiers and existential
quantifiers. Besides this, we also have other types of quantifiers such as nested
quantifiers and Quantifiers in Standard English Usages. Quantifier is mainly used to show
that for how many elements, a described predicate is true. It also shows that for all
possible values or for some value(s) in the universe of discourse, the predicate is true or
not.

Example 1:
"x ≤ 5 ∧ x > 3"
This statement is false for x= 6 and true for x = 4. Now we will compare the above
statement with the following statement
"For every x, x ≤ 5 ∧ x > 3"
This statement is definitely false. Now we will again define a statement
"There exists an x such that "x ≤ 5 ∧ x > 3"
This statement is definitely true. The phrase "there exists an x such that" is known as the
existential quantifier, and "for every x" phrase is known as the universal quantifier. The
variables in a formula cannot be simply true or false unless we bound these variables by
using the quantifier.

Example 2:
Suppose we have two statements that are ∀x : x2 +1 > 0 and ∀x : x2 > 2. For x = 1, the first
statement ∀x : x2 +1 > 0 is true, but the second statement ∀x : x2 > 2 is false, because it
does not satisfy the predicate. On the other side, if we write the second statement as ∃x :
x 2 > 2, it will be true, because x = 2 is an example that satisfies it.
In the quantified expression, if there is a variable, then we always assume that the variable
comes from some base set. If we specify x as a real number, then the statement ∀x : x2 +1
> 0 will be true. But this statement will be false if we specify x as a complex number such
as i. In this case, the predicate will not satisfy by x = i because we don't specify the value
of i.

Universal Quantifiers
Sometimes the mathematical statements assert that if the given property is true for all
values of a variable in a given domain, it will be known as the domain of discourse. Using
the universal quantifiers, we can easily express these statements. The universal quantifier
symbol is denoted by the ∀, which means "for all". Suppose P(x) is used to indicate
predicate, and D is used to indicate the domain of x. The universal statement will be in the
form "∀x ∈ D, P(x)". The main purpose of a universal statement is to form a proposition.
In the quantifiers, the domain is very important because it is used to decide the possible
values of x. When we change the domain, then the meaning of universal quantifiers of P(x)
will also be changed. When we use the universal quantifier, in this case, the domain must
be specified. Without a domain, the universal quantifier has no meaning.

P a g e | 17
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

The sentence ∀xP(x) will be true if and only if P(x) is true for every x in D or P(x) is true
for every value which is substituted for x. The statement ∀xP(x) will be false if and only if
P(x) is false for at least one x in D. The value for x for which the predicate P(x) is false is
known as the counterexample to the universal statement. If finite values such as {n1, n2,
n3, …, nk} are contained by the universe of discovery, the universal quantifier will be
the conjunction of all elements, which is described as follows:
∀xP(x) ⇔ P(n1) ∧ P(n2) ∧ · · · ∧ P(nk)

Example 1: Suppose P(x) indicates a predicate where "x must take an electronics course"
and Q(x) also indicates a predicate where "x is an electrical student". Now we will find the
universal quantifier of both predicates.
Solution: Suppose the students are from ABC College. For both predicates, the universe of
discourse will be all ABC students.

The statements can be: "Every electrical student must take an electronics course". The
following syntax is used to define this statement:
∀x(Q(x) ⇒ P(x))
This statement can be expressed in another way: "Everybody must take an electronics
course or be an electrical student". The following syntax is used to define this statement:
∀x(Q(x) ∨ P(x))

Example 2: Suppose P(x) indicates a predicate where "x is a square" and Q(x) also
indicates a predicate where "x is a rectangle". Now we will find the universal quantifier of
these predicates.
Solution:
The statement must be:
∀x (x is a square ⇒ x is a rectangle), i.e., "all squares are rectangles.'' The following syntax
is used to describe this statement:
∀xP(x) ⇒Q(x)

Problem: Consider Universe of real numbers with

p(x): x>=0, q(x): 𝑥 2 ≥ 0,
r(x):𝑥 2 − 3𝑥 − 4 = 0, s(x): 𝑥 2 − 3 > 0
Verify following open statements are true or false
1. ∃𝑥[𝑝(𝑥)⋀𝑟(𝑥)]
= Let x=4, then p(x)=4 and r(x)=16-3(4)-4=0, Hence true
2. ∀𝑥[𝑝(𝑥) ⟶ 𝑟(𝑥)]
Let x=1, then p(x)=1, r(x)=1-3(1)-4=-6!=0, hence false
3. ∀𝑥[𝑞(𝑥) ⟶ 𝑠(𝑥)]
Let x=1, then q(x)=12=1, s(x)=1-3=-2<0, Hence false
4. ∀𝑥[𝑟(𝑥) ⟶ 𝑝(𝑥)]
For r(x) solution is x=-1, but for p(x), x>=0. Hence false
5. ∀𝑥[𝑝(𝑥) ⟶ 𝑞(𝑥)]
Since we don’t have any value of x such that x>=0 and x2<0, the given universal
implication is true.

Problem: Express the following statements using quantifiers

a) In universe of real numbers, if a number is rational then it is a real number

P a g e | 18
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Solution: ∀𝑥[𝑝(𝑥) ⟶ 𝑞(𝑥)]

b) In universe of triangles, An equilateral triangle has three angles of 60°, and conversely
Solution: ∀𝑥[𝑝(𝑥) ⟶ 𝑞(𝑥)]
c) In universe of real numbers, 𝑠𝑖𝑛2 𝑥 + 𝑐𝑜𝑠 2 𝑥 = 1
Solution: ∀𝑥[𝑠𝑖𝑛2 𝑥 + 𝑐𝑜𝑠 2 𝑥 = 1]
d) In universe of all positive integers, The integer 41 is equal to sum of two perfect squares
Solution: ∃𝑚, 𝑛[41 = 𝑚2 + 𝑛2 ]

Problem: Consider following array declaration

For array A[1],A[2],…A[20],
for n:=1 to 20 do
A[n]:= n*n - n
Express each statement using quantifiers
1. Every entry in the array is non-negative
Solution: ∀𝑖, 𝐴[𝑖 ≥ 0]
2. There exists 2 consecutive entries in the array such that larger entry is twice the smaller
Solution: ∃𝑖, 𝐴[𝑖 + 1] = 2𝐴[𝑖]
3. The entries in the array is sorted in ascending order
Solution: ∀𝑖, 𝐴[𝑖 + 1] > 𝐴[𝑖]
4. The entries in the array are distinct
Solution: ∀𝑚, 𝑛, 𝐴[𝑚] ≠ 𝐴[𝑛]

Problem: For the universe of all integers, consider:

r(x): 2x+1=5 and s(x):𝑥 2 = 9
Verify which of these quantification is true
1. ∃𝑥[𝑟(𝑥) ∧ 𝑠(𝑥)]
Solution: r(x): 2x+1=5=> 2x=4=>x=2
s(x) 𝑥 2 = 9 => x=+3 and x=-3
Hence solutions are different and result is false
2. [∃𝑥 𝑟(𝑥) ∧ ∃𝑥 𝑠(𝑥)]
Since x exists for both r(x) and s(x), it is true

Problem: Let p(x): x is odd, q(x): 𝐱 𝟐 − 𝟏 𝐢𝐬 𝐞𝐯𝐞𝐧

Verify the negation of the statement: If x is odd, then 𝑥 2 − 1 𝑖𝑠 𝑒𝑣𝑒𝑛
Solution:
To verify ¬∀𝑥[𝑝(𝑥) ⟶ 𝑞(𝑥)]
= ∃𝑥¬[𝑝(𝑥) ⟶ 𝑞(𝑥)]
=∃𝑥¬(¬p(x)𝑉 𝑞(𝑥) [Law of implication]
=∃𝑥 (p(x) ∧ ¬ 𝑞(𝑥) ) [Demorgans Law and Double implication]
However this is not possible, as we do not have any integer x that exists such that x is
odd and 𝑥 2 − 1 𝑖𝑠 𝑒𝑣𝑒𝑛

Determine the truth value of each statement, if universe comprises of all nonzero
integers
a) ∃𝑥 ∃𝑦 [𝑥𝑦 = 2]
Solution: Let x=1, y=2 then xy=2, Hence True
b) ∃𝑥 ∀𝑦 [𝑥𝑦 = 2]
Solution: Let x=1, y=4 then xy=4!=2, Hence False
c) ∀𝑥 ∃𝑦 [𝑥𝑦 = 2]

P a g e | 19
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Solution: Let x=4, y=1, then xy=4!=2 Hence False

d) ∃𝑥 ∃𝑦 [(3𝑥 + 𝑦 = 8)𝛬(2𝑥 − 𝑦 = 7)]
Solution: 3x + y =8 ……………….(1)
2x – y =7 …………………(2)
(1) + (2) gives
5x =15 => x=3
Hence, 3(3)+y=8 => y=-1
Since both x and y exists, it is true
e) ∃𝑥 ∃𝑦 [(4𝑥 + 2𝑦 = 3)𝛬(𝑥 − 𝑦 = 1)]
Solution: 4x + 2y = 3 ………….(1)
x-y=1 ………..(2)
2*(2) => 2x – 2y =2 ……………..(3)
(1) + (3) gives, 6x=5 =>x=5/6
5/6-y=1 => y=5/6-1=-1/6
Hence both x and y are rationals and not integers and result is False

The Rule of Universal Specification: If an open statement becomes true for all
replacements by the members in a given universe, then that open statement is true for
each specific individual member in that universe.
Eg:
m(x): x is a mathematics professor
c(x): x has studied calculus
Consider,
All mathematics professor have studied calculus
Leona is a mathematics professor
Therefore Leona has studied calculus
Then, ∀𝑥 [𝑚(𝑥) ⟶ 𝑐(𝑥)]
𝑚(𝑙)
𝑐(𝑙) [From rule of Universal Specification]

Rule of Universal Generalization: If an open statement p(x) is proved to be true when x is

replaced by any arbitrarily chosen element c from our universe, then the universally
quantified statement x p(x) is true.
Prove:
∀𝑥 [𝑝(𝑥) ⟶ 𝑞(𝑥)]
∀𝑥 [𝑞(𝑥) ⟶ 𝑟(𝑥)]
then, ∀𝑥 [𝑝(𝑥) ⟶ 𝑟(𝑥)]
Solution:
Reduction Rule
∀𝑥 [𝑝(𝑥) ⟶ 𝑞(𝑥)]= 𝑝(𝑥) ⟶ 𝑞(𝑥) Rule of Universal Specification
∀𝑥 [𝑞(𝑥) ⟶ 𝑟(𝑥)]= q(𝑥) ⟶ 𝑟(𝑥) Rule of Universal Specification
𝑝(𝑥) ⟶ 𝑞(𝑥), q(𝑥) ⟶ 𝑟(𝑥) = p(𝑥) ⟶ 𝑟(𝑥) Law of syllogism
p(𝑥) ⟶ 𝑟(𝑥)= ∀𝑥 [𝑝(𝑥) ⟶ 𝑟(𝑥)] Rule of Universal Generalization

P a g e | 20
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Model paper solutions:

Show that the compound proposition
( p  q )  ( q  r )  ( r  p )   ( p → q )  ( q → r )  ( r → p )  for primitive statements p,
q, r is logically equivalence.
p q r A: B: C: A X: p Y:q Z: r X
p q r   → q → r → Y
 r p C p Z
q
0 0 0 1 1 1 1 1 1 1 1
0 0 1 1 0 0 0 1 1 0 0
0 1 0 0 0 1 0 1 0 1 0
0 1 1 0 1 0 0 1 1 0 0
1 0 0 0 1 0 0 0 1 1 0
1 0 1 0 0 1 0 0 1 1 0
1 1 0 1 0 0 0 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1
Establish the validity of the following argument using the Rules of
Inference: {𝑝 𝖠 (𝑝 → 𝑞) 𝖠 (𝑠 𝗏 𝑟) 𝖠 (𝑟 →∼ 𝑞)} ⟶ (𝑠 𝗏 𝑡).

Reduction Rule
𝑝 𝖠 (𝑝 → 𝑞)≡q Modus ponens
𝑟 →∼ 𝑞 ≡q→∼r Law with implication
q, q→∼r≡∼r Modus ponens
𝑠 𝗏 𝑟, ∼r≡ s Law of Disjunctive Syllogism
s≡𝑠𝗏𝑡 Law of Disjunctive
Amplification

For the universe of all integers, let p(x), q(x), r(x), s(x) and t(x) denote the following open statements:
p(x): x>0, q(x): x is even, r(x): x is a perfect square, s(x): x is divisible by 3, t(x): x is divisible by 7.
Write the following statements in symbolic form: i) At least one integer is even. ii) There exists a
positive integer that is even. iii) If x is even, then x is not divisible by 3. iv) No even integer is divisible
by 7. v) There exists even integer divisible by 3.

i) At least one integer is even: ∃𝑥, 𝑞(𝑥)

ii) There exists a positive integer that is even: ∃𝑥, [𝑝((𝑥) ∧ 𝑞(𝑥)]
iii) If x is even, then x is not divisible by 3 : ∀𝑥, [𝑞(𝑥) → ¬𝑠(𝑥)]
iv) Noeven integer is divisible by 7: ∀𝑥, [𝑞(𝑥) → ¬𝑡(𝑥)]
v) There exists even integer divisible by 3 ∃𝑥, [𝑞(𝑥) ∧ 𝑠(𝑥)
Define a tautology. Prove that, for any propositions p, q, r the compound
propositions, {(𝑝→𝑞)𝖠(𝑞→𝑟)}→{(𝑝→𝑟)} is tautology.
A proposition P is a tautology if it is true under all circumstances. It means it contains the only 1
in the final column of its truth table

p q r X: p Y:q → XY 𝑝→𝑟 X  Y->

→q r 𝑝→𝑟
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 1 0 1 0 0 1 1
0 1 1 1 1 1 1 1

P a g e | 21
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

1 0 0 0 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1

Hence {(𝑝→𝑞)𝖠(𝑞→𝑟)}→{(𝑝→𝑟)} is tautology.

Prove the following using laws of logic: 𝑝→(𝑞→𝑟)⇔(𝑝𝖠𝑞)→𝑟.

Reduction Rule
𝑞→𝑟≡ ¬𝑞 ∨ 𝑟 Law of Implication
𝑝→(𝑞→𝑟) ≡ ¬𝑝 ∨ ( 𝑞→𝑟) Law of implication
¬𝑝 ∨ ( ¬𝑞 ∨ 𝑟) For Step 1 and Step 2
(¬𝑝 ∨ ( ¬𝑞) ∨ 𝑟) Associative Law
¬(𝑝 ∧ 𝑞) ∨ 𝑟 Demorgans Law
𝑝 ∧ 𝑞 →𝑟 Law of Implication

Give i) direct proof ii) indirect proof iii) proof by contradiction for the
following statement: “if n is an odd integer then n+9 is an even integer”.

To prove the statement "if n is an odd integer then n + 9 is an even integer,"

Direct Proof
Step 1: Define an Odd Integer: An integer n is odd if it can be expressed in the form n = 2k + 1,
where k is an integer.
Step 2: Add 9 to the Odd Integer,
Now, we calculate n + 9: n + 9 = (2k + 1) + 9 = 2k + 10.
Step 3: Factor the Result
We can factor this expression: n + 9 = 2k + 10 = 2(k + 5).
Step 4: Conclusion: Since k + 5 is an integer, we see that n + 9 can be expressed as 2 times an
integer, which means n + 9 is even.

Indirect Proof:
Step 1: Assume the Opposite, Assume that n is an odd integer and n + 9 is not even (i.e., n + 9
is odd).
Step 2: Express n + 9 as Odd
If n + 9 is odd, it can be expressed as n + 9 = 2m + 1 for some integer m.
Step 3: Rearrange the Equation,
Rearranging gives us: n = 2m + 1 - 9 = 2m - 8 = 2(m - 4).
Step 4: Conclusion: This shows that n is even (since it can be expressed as 2 times an integer),
which contradicts our assumption that n is odd. Therefore, our assumption must be false, and n
+ 9 must be even.

Proof by Contradiction:
Step 1: Assume n is Odd, Assume n is an odd integer, so n = 2k + 1 for some integer k.
Step 2: Assume n + 9 is Odd
Assume for contradiction that n + 9 is odd.
Step 3: Express n + 9
Then, n + 9 = (2k + 1) + 9 = 2k + 10 = 2(k + 5), which is even.
Step 4: Conclusion: This leads to a contradiction because we assumed n + 9 is odd. Therefore,
n + 9 must be even.

P a g e | 22
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

The statement "if n is an odd integer then n + 9 is an even integer" is proven true using direct
proof, indirect proof, and proof by contradiction.
Define tautology. Show that [(𝑝˅𝑞)˄(𝑝 → 𝑟)˄(𝑞 → 𝑟)] → 𝑟 is atautology by
constructing the truth table.

A proposition P is a tautology if it is true under all circumstances. It means it contains the

only 1 in the final column of its truth table.

p q r X: pV Y:p → Z:q → P:X P->r

q r r Y Z
0 0 0 0 1 1 0 1
0 0 1 0 1 1 0 1
0 1 0 1 1 0 0 1
0 1 1 1 1 1 1 1
1 0 0 1 0 1 0 1
1 0 1 1 1 1 1 1
1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1
Prove the following using the laws of logic
[¬𝑝˄(¬𝑞˄𝑟)]˅[(𝑞˄𝑟)˅(𝑝˄𝑟)] ⇔ 𝑟.

Reduction Rule
¬𝑝˄¬𝑞˄𝑟 Law of distribution
𝑟˄[(¬𝑝˄¬𝑞) ˅ (𝑞 ˅p)] Law of distribution and
disjunctive simplification
(¬𝑝˄¬𝑞) ˅ (𝑞 ˅p) If p and q are both false
=True ¬𝑝˄¬𝑞 is true
If either q or p is true, 𝑞 ˅p is
true
r˄True=r Substitution
For any two odd integers m and n, show that (i) m+n is even (ii) mn is
odd.

(i) m+n is even

(ii) mn is odd

P a g e | 23
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Define i) an open statement ii) Quantifiers

An open statement, also known as an open sentence, is a mathematical statement that contains
one or more variables. The truth value of an open statement is not fixed, and can be either true or
false depending on the values assigned to the variables. For example, "1 - y = 8" is an open
statement because the value of "y" is unknown. The process of finding the values of variables
that result in a true sentence is called solving the open sentence, and the replacement value is the
solution.

Quantifier is used to quantify the variable of predicates. It contains a formula, which is a

type of statement whose truth value may depend on values of some variables. When we
assign a fixed value to a predicate, then it becomes a proposition. In another way, we can
say that if we quantify the predicate, then the predicate will become a proposition. So
quantify is a type of word which refers to quantifies like "all" or "some".

There are mainly two types of quantifiers that are universal quantifiers and existential
quantifiers. Besides this, we also have other types of quantifiers such as nested quantifiers
and Quantifiers in Standard English Usages. Quantifier is mainly used to show that for how
many elements, a described predicate is true. It also shows that for all possible values or
for some value(s) in the universe of discourse, the predicate is true or not.

Write the following argument in symbolic form and then establish thevalidity
If A gets the Supervisor’s position and works hard, then he will get a raise. If he gets a raise,
then he will buy a car. He has not purchased a car. Therefore he did not get the Supervisor’s
position or he did not
work hard.

Let:
p:He gets a supervisor position
q: He works hard
r:He gets a raise
s: He will buy a car

Given:
𝑝 ∧ 𝑞 ⟶ 𝑟 ……(1)
𝑟 ⟶ 𝑠 ………………(2)
¬𝑠 ……………..(3)
Applying Law of Syllogism on (1) and (2)
𝑝 ∧ 𝑞 ⟶ 𝑠 …..(4)
Applying Modus Tollens on (3) and (4)
¬(𝑝 ∧ 𝑞)

P a g e | 24
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Applying Demorgans Law

¬𝑝 𝑉 ¬𝑞
Which means, he did not get supervisor position or he did not work hard

For the following statements, the universe comprises all non-zerointegers.

Determine the truth value of each statement.
a) ∋ 𝑥 ∋ 𝑦 [𝑥𝑦 = 1] b) ∋ 𝑥∀𝑦 [𝑥𝑦 = 1] c) ∀𝑥 ∋ 𝑦 [𝑥𝑦 = 1]
d) ∋ 𝑥 ∋ 𝑦[(2𝑥 + 𝑦 = 5)˄(𝑥 − 3𝑦 = −8)] e) ∋ 𝑥 ∋ 𝑦[(3𝑥 − 𝑦 =7)˄(2𝑥 + 4𝑦 = 3)]

f) ∃𝑥 ∃𝑦 [𝑥𝑦 = 1]
Solution: Let x=1, y=1 then xy=1, Hence True
g) ∃𝑥 ∀𝑦 [𝑥𝑦 = 1]
Solution: Let x=1, y=4 then xy=4!=1, Hence False
h) ∀𝑥 ∃𝑦 [𝑥𝑦 = 1]
Solution: Let x=4, y=1, then xy=4!=1 Hence False
i) ∃𝑥 ∃𝑦 [(2𝑥 + 𝑦 = 5)𝛬(𝑥 − 3𝑦 = −8)]
Solution: 2x + y =5 ……………….(1)
x – 3y =-8 …………………(2)
(2) - 2*(2) gives
7y =21 => y=3
Hence, 2x+3=5 => x=1
Since both x and y exists, it is true
j) ∃𝑥 ∃𝑦 [(3𝑥 − 𝑦 = 7)𝛬(2𝑥 + 4𝑦 = 3)]
Solution: 3x -y = 7 ………….(1)
2x+4y=3 ………..(2)
4*(1) => 12x – 4y =28 ……………..(3)
(2)+ (3) gives, 14x=31 =>x=31/14
y=3x-7 => y=93/14-7=-5/14
Hence both x and y are rationals and not integers and result is False

P a g e | 25
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

MODULE-II: Properties of the Integers

Overview of Counting:
In daily lives, many a times one needs to find out the number of all possible outcomes for
a series of events. For instance, in how many ways can a panel of judges comprising of 6
men and 4 women be chosen from among 50 men and 38 women? How many different
10 lettered PAN numbers can be generated such that the first five letters are capital
alphabets, the next four are digits and the last is again a capital letter. For solving these
problems, mathematical theory of counting are used. Counting mainly encompasses
fundamental counting rule, the permutation rule, and the combination rule. Principles of
Counting can be applied in vivid areas like coding theory, probability and statistics, and
analysis of algorithms

Rule of Sum:
If first task can be done in ‘m’ ways and second task in ‘n’ ways and both cannot be
simultaneously done, then either of tasks can be performed in ‘m+n’ ways

Problem: College Library has 40 textbooks on Python and 50 textbooks on Data

Structures, a student can select ___ books

Solution: Since books are of different languages, student can select in 40 + 50=90 ways

Problem: Computer instructor has seven different introductory books each on

C++, Java and Perl. Number of books a student can avail is _____

Solution: Since each book belongs to different language, it is 7+7+7=21 ways

Problem: First colleague has 3 books on ADA and other has 5 such books. If n
denotes maximum number of different books on this topic, range of n is ____

Solution: Since books may be same of different, minimum number of unique books is 5
(which is with second colleague and first colleague has same 3 books with first
colleague) and maximum number of unique books is 8 (which is 3 different books from
first colleague + 5 different books from second colleague)
Hence, range of n is: 5<=n<=8

Extension of Sum Rule: If tasks T1,T2,..Tm can be done in n1,n2,..,nm ways and no
two tasks are performed simultaneously, number of ways: n1+n2+..+nm

Problem: If a student can chose project either 20 from AI, 30 from ML, 20 from DL
then number of ways he can chose either is __

Solution: Since books are of different subjects, from extension of sum rule, total number
of ways=20+30+20=70 ways

P a g e | 26
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Product Rule: If a procedure can be split into 2 stages, if there are m outcomes for
Stage-1 and n outcomes for each of m outcomes, total procedure can be carried in
m*n ways.

Problem: Six men and eight women are contesting for lead male and female roles,
director can cast leading couple in ____ ways

Solution: Number of men=6, Number of women=8

Hence for each men, 8 women can be paired for couple role.
Then from product theorem, total number of ways=6 * 8 = 48 ways

Problem: License plate has 2 letters followed by 4 digits. Find number of

possibilities if (i) no repetitions (ii) with repetitions

Solution:
(i) For no repetitions:
2 letters=26 X25
4 digits = 10X9X8X7
Total number of ways=26X25X10X9X8X7

(ii) With repetitions

2 letters=26 X26
4 digits = 10X10X10X10
Total number of ways=26X26X10X10X10X10

Problem: Find total possibilities in each case:

i. Circuit memory – bit
ii. Embedded microcontrollers byte addressable – 1 byte
iii. Kitchen appliance – sequence of 2 1-bytes
iv. Pentium processor – word – 4-bytes

Solution: (i) Circuit memory=1 bit =2 possibilities

(ii) Embedded microcontrollers= 1 byte= 2^8 possibilities
(iii) Kitchen appliance = 2 bytes = 2^8 * 2^8 (Product Theorem)
(iv) Pentium processor = 4 bytes = 2^8 * 2^8*2^8 * 2^8 (Product Theorem)

Problem: Mrs. Foster operates Quick Snack Coffee shop. Menu in the shop is: six
kinds of muffins, eight kinds of sandwiches and five beverages (hot coffee, hot tea,
iced tea, cola and orange juice). Ms. Dodd, sends her assistant Carl to get her
lunch- either a muffin and hot beverage or sandwich and cold beverage. Find the
number of ways

Solution:
Lunch= Muffin and Hot beverage OR Sandwich and cold beverage
Case-1: Muffin and Hot beverage=6*2=12 (Product theorem)
Case-2: Sandwich and cold beverage=8*3=24 (Product theorem)
Total number of ways=12 + 24=36 ways (Sum Rule)

P a g e | 27
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem: A hotel offers 12 kinds of sweets, 10 kinds of hot tiffins and 5 kinds of
beverages (hot tea, hot coffee, juice, coke, icecream). The breakfast consists of
sweet and hot beverage or a hot tiffin and cold beverage. Number of ways in which
breakfast can be ordered

Solution:
Breakfast= Sweet and Hot beverage OR Hot tiffin and cold beverage
Case-1: Sweet and Hot beverage=12*2=24 (Product theorem)
Case-2: Hot tiffin and cold beverage=10*3=30 (Product theorem)
Total number of ways=24 + 30=54 ways (Sum Rule)

Problem: In a class of 10 students, five are to be chosen and seated in a row. How
many such linear arrangements are possible?
Solution:
Number of ways to chose first student=10
Number of ways to chose second student=9 (As already 1 student selected)
Number of ways to chose first student=8 (As already 2 students selected)
Number of ways to chose first student=7 (As already 3 students selected)
Number of ways to chose first student=6 (As already 4 students selected)
Hence total number of ways=10 * 9 * 8 * 7 * 6 ways

Permutation: Given a collection of n distinct objects, any (linear) arrangement of

these objects is called permutation

Problem: The number of words of three distinct letters formed from word “JNTU”
Solution: Number of words of three distinct letters=4P3=4!/(4-3)!=24/1=24

Problem: In how many ways can eight men and eight women be seated in a row if
(a) any person may sit next to any other (b) men and women must occupy alternate
seats (c) generalize result for n men and n women

Solution:
(a) Any person can sit next to any one
Total people=8 men + 8 women = 16

P a g e | 28
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Hence, number of ways=16!

(b) Men and women must occupy alternate seats

There are 2 cases of arranging men and women in alternate seats

Case-1: MWMWMWMWMWMWMWMW = 8!*8!= (8!)2
Case-2: WMWMWMWMWMWMWMWM = 8!*8!= (8!)2
Total number of cases= (8!)2 + (8!)2 = 2 (8!)2

(c) Generalize result for n men and n women = 2 (n!)2

Problem: A committee of eight is to be formed from 16 men and 10 women. In how

many ways committee be formed if

(a) There are no restrictions

Solution: Then total people available=16 men and 10 women=26
Committee size=8
Since ordering does not matter, it is a case of combinations
Hence total number of ways=26C8

(b) There must be 4 men and 4 women

Solution: Selecting 4men from 16 men= 16C4
Selecting 4 women from 10 women=10C4
Since both men and women are to be selected, from product rule
Total number of ways=16C4 * 10C4

(c) There should be an even number of women

Solution: Even number of women means 2, 4,6 and 8
Case-1: Selecting 2 women means remaining 6 are men and number of
ways=10C2*16C6
Case-2: Selecting 4 women means remaining 4 are men and number of
ways=10C4*16C4
Case-3: Selecting 6 women means remaining 2 are men and number of
ways=10C6*16C2
Case-4: Selecting 8 women means remaining 0 are men and number of
ways=10C8*16C0
Hence total number of ways from sum rule
= 10C2*16C6 + 10C4*16C4 + 10C6*16C2 + 10C8*16C0

= ∑4i=1 10C2i ∗ 16C(8 − 2i)

(d) More women than men

Solution: More women than men leads to the cases of (5 women, 3men), (6 women,2men),
(7women, 1men) and (8women, 0 men)
Case-1: 5 women and 3 men=10C5*16C3
Case-2: 6 women and 2 men=10C6*16C2
Case-3: 7 women and 1 men=10C7*16C1
Case-4: 8 women and 0 men=10C8*16C0

P a g e | 29
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Total number of ways= 10C5*16C3 + 10C6*16C2 + 10C7*16C1 + 10C8*16C0

= ∑8i=5 10Ci ∗ 16C(8 − i)

(e) Atleast 6 men

Solution: Atleast 6 men leads to the cases of (6 men, 2 women), (7 men,1 women), (8 men,
0 women)
Case-1: 6 men and 2 women=16C6*10C2
Case-2: 7 men and 1 women=16C7*10C1
Case-3: 8 men and 0 women=16C8*10C0
Total number of ways= 16C6*10C2 + 16C7*10C1 + 16C8*10C0
= ∑8i=6 16Ci ∗ 10C(8 − i)

Permutations with repetitions:

If there are n objects with n1 indistinguishable of first type, n2 of second type and
𝐧!
nr of rth type with n1+n2+..+nr=n, then there are 𝐧𝟏!𝐧𝟐!….𝐧𝐫! of given objects

Find the arrangements (permutations) of words:

(i) BALL
n=4
n1=1 (B), n2=1(A), n3=2 (L)
4! 24
Hence total number of arrangement=1!∗1!∗2! = 2
=12

(ii) DATABASES
n=9
n1=1 (D), n2=3 (A), n3=1 (T), n4=1 (B), n5=2 (S), n6=1 (E)
9!
Hence total number of arrangement=3!∗2!

(iii) MASSASAUGA
n=10
n1=1 (M), n2=4 (A), n3=3 (S), n4=1 (U), n5=1 (G)
10!
Hence total number of arrangement=4!∗3!

Problem: Determine the number of staircase paths in the xy plane from (2,1) to
(7,4) where each such path is made up of individual steps going one unit to the right
(R) or one unit upward (U)

Solution:
Sample ways of reaching from (2,1) to (7,4) is show below:

P a g e | 30
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Hence we have RRRRR=5 right movement and UUU=3 upper movements

n=8
n1=5 (R) , n2=3 (U)
8!
Total number of ways= 5!∗3!=56

Problem: If six people designated as A,B,..F are seated about a round table, how
many different circular arrangements are possible, if arrangements are considered
the same when one can be obtained from other by rotation

Solution: 6 people can be arranged in 6! ways from product theorem i.e 6 X5 X4 X 3 X2 X1

However, we have following arrangements which are circular and can be obtained from
other using rotations
ABCDEF
BCDEFA
CDEFAB
DEFABC
EFABCD
FABCDE
Thus there exists 6 rotations which are repetitive
6!
Hence total number of ways= 6 =120

P a g e | 31
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem: Number of ways in which a 3 cards can be picked from a standard deck of
52 cards
Solution: 3 cards can be selected from 52 cards in 52C3 ways

Problem: A hostess is having a dinner party for some members of her charity
committee. Because of the size of her home she can invite only 11 of 20 members.
Find the number of ways
Solution: 11 members from total 20 members can be invited in 20C11 ways

Problem: Lyan and Patti decide to buy a PowerBall ticket. To win grand prize of
PowerBall ticket one must match 5 numbers selected from 1 to 49 and then must
also match the powerball, an integer from 1 to 42. Find the number of ways
Solution:
5 numbers can be selected from 1to 49 in 49C5 ways
An integer from 1 to 42 can be selected in 42C1 ways
Hence total number of ways=49C5*42C1 ways

Problem: A student taking history exam is directed to answer any seven of the 10
essay questions. Find the number of ways for:
(i) No specific instructions-any 7
Solution: Any 7 questions from 10 can be selected in 10C7 ways=10!/(7!3!)=120
(ii) Three questions from first 5 and four from remaining 5
Solution: 3 questions from first 5 can be selected in 5C3 ways and 4 questions from
remaining 5 can be selected in 5C4 ways.
Hence total number of ways=5C3*5C4=10*5=50 ways
(iii) Atleast three selected from first 5
Solution: Atleast three selected from first 5 has following cases:
Case-1: 3 from first 5, means 4 from remaining 5 = 5C3*5C4=10*5=50
Case-2: 4 from first 5, means 3 from remaining 5 = 5C4*5C3=5*10=50
Case-3: 5 from first 5, means 2 from remaining 5 = 5C5*5C2=1*10=10

P a g e | 32
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Hence total number of ways from sum rule=50+50+10=110

Problem: Gym teacher must make up volleyball teams of nine girls each from 36
freshman girls in her PE class. In how many ways, she can select these four teams

Solution:
First team can be formed in 36C9
Second team can be formed in 27C9 (as 9 already selected in first team)
Third team can be formed in 18C9 (as 18 already selected in first two teams)
Fourth team can be formed in 9C9 (as 27 already selected in first three teams)
Hence total number of ways from product rule = 36C9 * 27C9 * 18C9 * 9C9

Problem For the word TALLAHASSEE, find

(i) Number of arrangements

Solution:
n=11,
n1=1 (T), n2=3 (A), n3=2 (L), n4=1 (H), n5=2(S). n6=2 (E)
11!
Total number of ways= 3!∗2!∗2!∗2!

(ii) How many of these arrangements do not contain adjacent A’s

Solutio: Remove A’s from the word TALLAHASSEE
This results in TLLHSSEE
Number of arrangements for TLLHSSEE:
n=8, n1=1 (T), n2=2 (L), n3=1 (H), n4=2 (S), n5=2 (E)
8!
Total number of ways= 2!∗2!∗2!!

Further A can be put in all vacant positions shown below:

T L L H H S S E E

Total number of vacant positions=9

Number of ways 3 A’s can be put in 9 vacation positions=9C3
8!
Total number of arrangements such that adjacent A’s wont appear is: 2!∗2!∗2!! * 9C3

Problem: Ellen draws five cards from standard deck of 52 cards. In how many ways:
(i) Select card with no clubs
Solution:
There are totally 13 clubs in a pack of 52 cards.
Hence if no clubs are to be selected, remaining cards available=52-13=39 cards
Number of ways 5 cards can be selected from 39 cards = 39C5

(ii) Five card selection contains atleast one club

Solution:
Atleast one club leads to following cases:
(1 club, 4 others) , (2 club, 3 others), (3 club, 2others), (4 club, 1 other), (5 club, 0 others)
Case-1: Number of ways of selecting 1 club and 4 others=13C1*39C4
Case-2: Number of ways of selecting 2 clubs and 3 others=13C2*39C3
Case-3: Number of ways of selecting 3 clubs and 2 others=13C3*39C2

P a g e | 33
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Case-4: Number of ways of selecting 4 clubs and 1 others=13C4*39C1

Case-5: Number of ways of selecting 5 clubs and 0 others=13C5*39C0
Total number of cases= 13C1*39C4 + 13C2*39C3 + 13C3*39C2 + 13C4*39C1 +
13C5*39C0

Binomial Theorem
𝑛 𝑛 𝑛 𝑛
(𝑥 + 𝑦)𝑛 = ( ) 𝑥 0 𝑦 𝑛 + ( ) 𝑥1 𝑦 𝑛−1 + ( ) 𝑥 2 𝑦 𝑛−2 + ⋯ + ( ) 𝑥 𝑛 𝑦 0
0 1 2 𝑛
= ∑𝑛𝑘=0(𝑛𝑘)𝑥 𝑘 𝑦 𝑛−𝑘

(𝑛𝑘) is referred to as Binomial coefficient

Problem:

𝑭𝒊𝒏𝒅 𝒕𝒉𝒆 𝒄𝒐𝒆𝒇𝒇𝒊𝒄𝒊𝒆𝒏𝒕 𝒐𝒇 𝒙𝟓 𝒚𝟐

Solution:
As per Binomial theorem, term 𝑥 5 𝑦 2 appears in the expansion of (x+y)7
Hence, coefficient of 𝑥 5 𝑦 2 as per Binomial theorem is 7C5=21

𝑷𝒓𝒐𝒃𝒍𝒆𝒎: 𝑭𝒊𝒏𝒅 𝒕𝒉𝒆 𝒄𝒐𝒆𝒇𝒇𝒊𝒄𝒊𝒆𝒏𝒕 𝒐𝒇 𝒂𝟓 𝒃𝟐 in the expansion (𝟐𝒂 − 𝟑𝒃)𝟕

Solution:
Let x=2a and y=-3b
Then Binomial theorem will be for (𝑥 + 𝑦)7
Hence coefficient for 𝑥 5 𝑦 2 will be 7C5(2a)5(-3b)2
=21*2^5*(-3)^2𝑎5 𝑏 2
=6048

Multinomial Theorem
𝑭𝒐𝒓 𝒑𝒐𝒔𝒊𝒕𝒊𝒗𝒆 𝒊𝒏𝒕𝒆𝒈𝒆𝒓𝒔 𝒏, 𝒕, 𝒕𝒉𝒆 𝒄𝒐𝒆𝒇𝒇𝒊𝒄𝒊𝒆𝒏𝒕 𝒐𝒇

𝒙𝒏𝟏 𝒏𝟐 𝒏𝒕
𝟏 , 𝒙𝟐 , … , 𝒙𝒏

𝒊𝒏 𝒕𝒉𝒆 𝒆𝒙𝒑𝒂𝒏𝒔𝒊𝒐𝒏 𝒐𝒇 (𝒙𝟏 + 𝒙𝟐 +….+ 𝒙𝒕 )𝒏 is

𝒏!
𝒏𝟏! 𝒏𝟐! … 𝒏𝒕!

P a g e | 34
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem: 𝑰𝒏 𝒕𝒉𝒆 𝒆𝒙𝒑𝒂𝒏𝒔𝒊𝒐𝒏 𝒐𝒇 (𝒙 + 𝒚 + 𝒛)𝟕 , 𝒇𝒊𝒏𝒅 𝒕𝒉𝒆 𝒄𝒐𝒆𝒇𝒇𝒊𝒄𝒊𝒆𝒏𝒕 𝒐𝒇𝒙𝟐 𝒚𝟐 𝒛𝟑

,𝒙𝒚𝒛𝟓 𝒂𝒏𝒅𝒙𝟑 𝒛𝟒
Solution:
7!
𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑜𝑓𝑥 2 𝑦 2 𝑧 3 = 2!2!3!=210
7!
𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑜𝑓𝑥𝑦𝑧 5 = 5!=42
7!
𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑜𝑓𝑥 3 𝑧 4 = 3!4!=35

Combination with repetition

When we wish to select with repetition r of n distinct objects, total number of
arrangements is:
(𝒏 + 𝒓 − 𝟏)!
𝒓! (𝒏 − 𝟏)!
=(𝒏 + 𝒓 − 𝟏)𝑪𝒓

Problem: A donut shop offers 20 kinds of donuts. Assuming that there are atleast
a dozen of each kind, what is the number of selections?
Solution:
Given, n=20, r=12
Then number of selections=(n+r-1)Cr
=(20+12-1)C12=31C12

Problem: In how many ways we can distribute 10(identical) white marbles among six
distinct containers?

Solution:
Given, n=6, r=10
Then number of selections=(n+r-1)Cr
=(6+10-1)C10=15C10

Problem: President Helen has 4 vice presidents. She wishes to distribute among them
1000 as bonus checks where each check will be written as multiple of 100
(i)One or more vicepresidents gets nothing
(ii)Each vice president gets 1 check
Solution:
Given, n=4, r=1000/100=10
(i)One or more vicepresidents gets nothing
number of selections=(n+r-1)Cr

P a g e | 35
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

=(4+10-1)C10=13C10=286
(ii)Each vice president gets 1 check
n=4, r=600/100=6
number of selections=(n+r-1)Cr
=(4+6-1)C6=9C6=84

Problem: In how many ways can we distribute seven bananas and six oranges
among four children so that each child receives atleast one banana

Solution:
Distribution of bananas: Given n=4, r=3 [As each child should get 1 banana atleast=7-4=3
remaining for distribution]
number of selections=(n+r-1)Cr
=(4+3-1)C3=6C3=20
Distribution of oranges: Given n=4, r=6 [As there are 6 oranges for distribution]
number of selections=(n+r-1)Cr
=(4+6-1)C6=9C6=84
Hence total distribution by product rule=20X84=1680 ways

Problem: Determine all integer solutions to the equation:

x1+x2+x3+x4=7 where xi>=0, 1<=i<=4

Solution:
Here 7 has t be distributed among x1, x2, x3 and x4
Hence n=4, r=7
number of selections=(n+r-1)Cr
=(7+4-1)C7=10C7=120

Problem: Find the compositions of 4

Solution:
4
1+3
2+2
3+1
1+1+2
1+2+1
2+1+1
1+1+1+1
=8 ways
Problem: Find the compositions of 7 using combinations
Solution:

P a g e | 36
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Hence required number of compositions is:

6C6+6C5+6C4+6C3+6C2+6C1+6C0

Problem: Find the number of times print happens

for i=1 to 20 do
for j=1 to i do
for k=1 to j do
print(i*j*k)

Solution:
Outermost loop, n=20
There are 3 loops, hence r=3
number of selections=(n+r-1)Cr
=(20+3-1)C3=22C3=1540 times

Problem: Find the number of times print happens

counter=0
for i=1 to n do
for j=1 to i do
counter=counter+1

P a g e | 37
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Solution:
Outer loop, n=n
Number of loops, r=2
Hence, number of selections=(n+r-1)Cr
=n+2-1C2=n+1C2
(n+1)n(n−1)! n(n+1_
= 2!(n−1)! = 2

Problem: In how many ways can 10 (identical) dimes be distributed among five children
if
(a) There are no restrictions
(b) Each child gets atleast one dime
(c) Oldest child gets atleast two dimes

Solution:
(a) There are no restrictions
n=5, r=10
number of selections=(n+r-1)Cr
=5+10-1C10=14C10
(b) Each child gets atleast one dime
n=5, r=5 [As each dime goes to 1 child and remaining 5 dimes to be distributed]
number of selections=(n+r-1)Cr
=5+5-1C5=9C5
(c) Oldest child gets atleast two dimes
n=5, r=8 [As oldest child gets 2 dimes, remaining dimes is 8]
number of selections=(n+r-1)Cr
=5+8-1C8=12C8

Problem: Determine the number of integer solutions for

x1+x2+x3+x4+x5<40, xi>=0, 1<=i<=5

Solution:
x1+x2+x3+x4+x5<40
x1+x2+x3+x4+x5<=39
x1+x2+x3+x4+x5+x6=39
Hence n=6, r=39
number of selections=(n+r-1)Cr
=6+39-1C39=44C39

Problem: A certain ice-cream store has 31 flavours of ice-cream available. In how

many ways can we order a dozen ice cream comes if
(a) we do not want the same flavor more than once
(b) A flavor may be ordered as many as 12 times

Solution:
(a) we do not want the same flavor more than once
31C12 as 12 flavors out of 31 can be selected in those many ways
(b) A flavor may be ordered as many as 12 times
n=31 r=12

P a g e | 38
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

number of selections=(n+r-1)Cr
=31+12-1C12=42C12

Principle of Mathematical Induction

Let S(n) denote an open mathematical statement that involves one or more
occurences of variable m, which represents the integer
(a) If S(1) is true and
(b) If whenever S(k) is true, then S(k+1) is true, k ∈ 𝒁+
then S(n) is true for all n ∈ 𝒁+

Problem: Prove following using Mathematical Induction

𝒏
+
𝒏(𝒏 + 𝟏)
𝑭𝒐𝒓 𝒂𝒍𝒍 𝒏 ∈ 𝒁 , ∑ 𝒊 = 𝟏 + 𝟐+. . +𝒏 =
𝟐
𝒊=𝟏

Proof:
Basis Step:

Induction Step:
Assume it is true for k.
𝑘(𝑘+1)
∑𝑘𝑖=1 𝑖 =
2

To prove for k+1:

LHS=

P a g e | 39
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem: Use mathematical induction to prove that 5 divides 𝐧𝟓 -n, whenever n is a

non-negative integer
Proof:
Basis Step:
n=1, S(1) means 1^5-1=0
Since 5 divides 0, S(1) is true
Induction step:
Let it be true for some k
Means k 5 -k is divisible by 5
Prove for k+1
LHS=(k + 1)5-(k+1)
=k 5 + 5k 4 + 10k 3 + 10k 2 + 5K + 1) − (k + 1)
= (k 5 − k) +5(k 4 + 2k 3 + 2k 2 + K)
Since k 5 -k is divisible by 5 and second term has 5 as multiplicand, both terms are divisible
by 5. Hence statement is true for k+1

Problem: Use mathematical induction to prove that,

𝟐𝐧 > 𝐧𝟐 , whenever n is a positive integer greater than 4

Proof:
Basis Step:
n=5, S(5) means 25 > 52 , 32 >25 is true . Hence basis step Is true
Induction step:
Let it be true for some k
Means 2k > k 2
Prove for k+1
LHS=2k+1
=2. 2k
=2k + 2k

P a g e | 40
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

>k 2 + k 2
>k 2 + 4n
> k 2 + 2k +1
> (k + 1)2 = RHS

Problem: If n is a positive integer, prove that

𝐧(𝐧+𝟏)(𝐧+𝟐)
1.2+2.3+3.4+……+n(n+1)= 𝟑
Proof:
Basis Step:
For n=1, LHS=1.2=2
RHS=1(1+1)(1+2)/3=6/3=2
Hence LHS=RHS and basis step is proved
Induction Step:
Assume it is true for some k.
k(k+1)(k+2)
Means: 1.2+2.3+3.4+……+k(k+1)= 3
To prove for k+1
LHS=1.2+2.3+3.4+……+k(k+1)+(k+1)(k+2)
k(k+1)(k+2)
= +(k+1)(k+2)
3
k(k+1)(k+2)+3(k+1)(k+2)
= 3
(k+1)(k+2)(k+3)
= 3
=RHS

Problem: A wheel of fortune has the numbers 1 to 36 painted on it in a random

manner. Show that regardless of how the numbers are situated, there are 3
consecutive numbers on the wheel whose total is 55 or more
Solution:
This problem is proved using Proof by contradiction
Lets assume. the sum of any 3 consecutive numbers is less than 55
Label the numbers as x1, x2…x36
Then there must be x1+x2+x3<55
x2+x3+x4<55
…..
x36+x1+x2<55
Summing up:
LHS=3 ∗ ∑36i=1 i=3*(36)(36+1)/2=1998
RHS=55*36=1980
Hence actually LHS>RHS contradicting the assumption
Hence, there are 3 consecutive numbers on the wheel whose total is 55 or more

Problem: The typical palindrome under study has the form:

aba=100a+10b+a=101a+10b
where 1<=a<=9 and 0<=b<=9. Find their sum

Solution:

P a g e | 41
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Typical form of palindrome: aba=100a+10b+a=101a+10b

Sum= ∑9a=1(∑9b=0 aba)
= ∑9a=1(∑9b=0(101a + 10b)
= ∑9a=1[(∑9b=0 101a) + (∑9b=0 10b)]
=∑9a=1[(101a ∗ 10) + (10 ∗ 45)]
=∑9a=1[(1010a) + (450)]
=1010*45+450*9=49500

Problem: Prove that for each n ∈ 𝒁+

𝒏
𝒏(𝒏 + 𝟏)(𝟐𝒏 + 𝟏)
∑ 𝒊𝟐 =
𝟔
𝒊=𝟏

Proof:

Induction Step:
Assume it is true for some k
Means:
𝒌
𝒌(𝒌 + 𝟏)(𝟐𝒌 + 𝟏)
∑ 𝒊𝟐 =
𝟔
𝒊=𝟏

To prove for (k+1)

LHS:

=RHS

P a g e | 42
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem: If n ∈ 𝒁+ , 𝒆𝒔𝒕𝒂𝒃𝒍𝒊𝒔𝒉 𝒕𝒉𝒆 𝒗𝒂𝒍𝒊𝒅𝒊𝒕𝒚 𝒐𝒇

𝒏
𝒏𝟐 + 𝒏 + 𝟐
∑ 𝒊 = 𝟏 + 𝟐+. . +𝒏 =
𝟐
𝒊=𝟏

Proof:

Basis Step:
LHS=1
12 +1+2
RHS= 2 =4/2=2
Since LHS is not same as RHS, basis step fails and the validity is disproved

Problem: Prove that sum of first n consecutive odd integers is 𝒏𝟐

Proof:
The statement can be expressed as:

Basis Step:
S(1)=> LHS=1
RHS=1^2=1 Hence LHS=RHS
Induction Step:
Assume it is true for some k. Means
k

∑(2i − 1) = k 2
i=1
To prove for (k+1)
RHS=(k + 1)2
LHS=∑k+1
i=1 (2i − 1)
=∑ki=1(2i − 1) + [2(k + 1) − 1]
=k 2 +2k +1
=(k + 1)2
Since LHS=RHS, sum of first n consecutive odd integers is n2

Problem: For each n ∈ 𝒁+

𝒏

∑ 𝑯𝒋 = (𝒏 + 𝟏)𝑯𝒏 − 𝒏
𝒋=𝟏

Proof:
Basis Step

P a g e | 43
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Induction Step:

Alternate form of principle of Mathematical Induction:

Let S(n) denote open mathematical statement, that involves one or more occurrences
of n, let n0, n1 ∈ 𝒁+ , 𝒏𝟎 ≤ 𝒏𝟏
a) If S(n0), S(n0 +1), S(n1 -1) and S(n1) are true
b) Whenever S(n0), S(n0 +1), S(k -1) and S(k) are true, then S(k+1) is also true

Problem: Consider the sequence 𝒂𝟎 , 𝒂𝟏, …. Where

𝒂𝟎 = 𝟏, 𝒂𝟏 =2, 𝒂𝟐 =3 and
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 + 𝒂𝒏−𝟑
Prove that entries in the sequence are such that:
𝒂𝒏 ≤ 𝟑𝒏

Proof:

P a g e | 44
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem: Consider the recurrence relation:

𝒂𝟎 = 𝟏, 𝒂𝟏 =2, 𝒂𝟐 =3 and
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 + 𝒂𝒏−𝟑
Find 𝒂𝟔
Using direct and indirect methods (forward and backward methods)
Solution:
Direct:

Indirect:

𝒏
Problem: Define a sequence S(1)=1, S(n)=2S⌊𝟐⌋:

Find 𝑺(𝟕𝟑)

P a g e | 45
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Solution:
73
S(73)= 2S⌊ 2 ⌋
36
=2*2*S(36)=4*⌊ 2 ⌋
18
=4*2*S(18)=8*⌊ 2 ⌋
9
=8*S(9)=16*⌊2⌋
=16*S(4)=32*S(2)=64

Problem: Prove the following recurrence relation

let 𝒏𝝐𝒁+ , 𝒏 ≥ 𝟑, 𝟏 ≤ 𝒓 ≤ 𝒏
(𝒑𝟏𝜦𝒑𝟐𝜦. . 𝜦𝒑𝒓)𝜦(𝒑𝒓 + 𝟏𝜦. . 𝜦𝒑𝒌) ⟺ 𝒑𝟏𝜦. . 𝜦𝒑𝒌
Proof:

Assume true for k:

Proof for k+1

Problem: Prove the following recurrence relation

let 𝒏𝝐𝒁+ , 𝒏 ≥ 𝟑, 𝟏 ≤ 𝒓 ≤ 𝒏
(𝑨𝟏 ∪ 𝑨𝟐 ∪. . 𝑨𝒓 ) ∪ (𝑨𝒓+𝟏 ∪. .∪ 𝑨𝒌 )
= 𝑨𝟏 ∪ 𝑨𝟐 ∪. . 𝑨𝒓 ∪ 𝑨𝒓+𝟏 ∪. .∪ 𝑨𝒌
Proof:
Let:

P a g e | 46
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Problem: Prove the following recurrence relation

let 𝒏𝝐𝒁+ , 𝒏 ≥ 𝟐,
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
𝑨𝟏 ∩ 𝑨𝟐 ∩. .∩ 𝑨𝒏 = ̅𝑨̅̅̅𝟏 ∪ ̅𝑨̅̅̅𝟐 ∪. .∪ ̅̅̅̅
𝑨𝒏

Proof:
Basis step is proved using Demorgans Law
Induction step proof:

P a g e | 47
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Model paper Solutions:

𝑛(2𝑛+1)(2𝑛−1)
Prove that 12 + 32 + 52 + ⋯ . +(2𝑛 − 1)2 = by
3
Mathematical Induction.

Basis Step:
For n=1, LHS=12=1
1(2.1+1)(2.1−1)
RHS= =3/3=1
3
Hence basis step is proved

Induction step:
Assume the equation is true for some ‘k’. Means
𝑘(2𝑘+1)(2𝑘−1)
12 + 32 + 52 + ⋯ . +(2k − 1)2 = 3
To prove for k+1:
(𝑘+1)(2𝑘+3)(2𝑘+1)
RHS= 3
LHS=12 + 32 + 52 + ⋯ . +(2k − 1)2+(2k + 1)2
=𝑘(2𝑘+1)(2𝑘−1) + (2k + 1)2
3
(2𝑘+1)(𝑘(2𝑘−1)+3(2𝑘+1)
=
3
(2𝑘+1)(2𝑘 2 −𝑘+6𝑘+3)
=
3
(2𝑘+1)(2𝑘+3)(𝑘+1)
= =RHS
3

Let 𝑎0 = 1, 𝑎1 = 2, 𝑎2 = 3 and 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 𝑎𝑛−3 for 𝑛≥3. Prove that

𝑎𝑛 ≤ 3𝑛 ∀ 𝑛 ∈ 𝑧+.

Find the number of ways of arrangement of the letters of the word

‘TALLAHASSEE’ which have no adjacent A’s.

Remove A’s from the word TALLAHASSEE

This results in TLLHSSEE
Number of arrangements for TLLHSSEE:
n=8, n1=1 (T), n2=2 (L), n3=1 (H), n4=2 (S), n5=2 (E)
8!
Total number of ways= 2!∗2!∗2!!

P a g e | 48
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Further A can be put in all vacant positions shown below:

T L L H H S S E E

Total number of vacant positions=9

Number of ways 3 A’s can be put in 9 vacation positions=9C3
8!
Total number of arrangements such that adjacent A’s wont appear is: 2!∗2!∗2!! * 9C3

Determine the coefficient of 𝑥𝑦𝑧2 in the expansion of (2𝑥 − 𝑦 − 𝑧)4.

Solution:
Let a=2x, b=-y, c=-z
Then (2𝑥 − 𝑦 − 𝑧)4 becomes (a+b+c)4
4!
Coefficient of abc2 becomes 2!=12
Since a=2x, b=-y and c=-z coefficient of 𝑥𝑦𝑧2 is -24
In how many ways one can distribute 8 identical marbles in 4 distinct
containers so that i) no container is empty ii) the fourth container has an oddnumber of marbles in
it.

(i) no container is empty

Given n=4 r=4 [As each container will contain a marble, remaining:8-4=4]
Then number of selections=(n+r-1)Cr

=(4+4-1)C4=7C4=35

ii) the fourth container has an oddnumber of marbles in it.

Case(i) Fourth container has 1 marble, n=3 r=7
Then number of selections=(n+r-1)Cr

=(3+7-1)C7=9C7=36

Case(ii) Fourth container has 3 marbles, n=3 r=5

Then number of selections=(n+r-1)Cr

=(3+5-1)C5=7C5=21
Case(iii) Fourth container has 5 marbles, n=3 r=3
Then number of selections=(n+r-1)Cr

=(3+3-1)C3=5C3=10
Case(iv) Fourth container has 7 marble, n=3 r=1
Then number of selections=(n+r-1)Cr

P a g e | 49
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

=(3+1-1)C1=3C1=3
Hence, total cases=36+21+10+3=70 ways

How many positive integers n can we form using the digits 3,4,4,5,5,6,7 if we
want n to exceed 5,000,000?

- There are 7 digits available (3, 4, 4, 5, 5, 6, 7)

- The number must be larger than 5,000,000, which means it must start with a digit larger than 5
- The available digits that are larger than 5 are 6 and 7
- So the first digit of the number can be either 6 or 7, giving 2 possibilities
- For the remaining 6 digits, there are 7 choices for each digit, giving 7^6 = 117,649 possible
combinations
- Therefore, the total number of positive integers 'n' that can be formed is 2 * 117,649 = 235,298
- However, the question specifies that n must be larger than 5,000,000, so we need to subtract the
numbers from 5,000,001 to 5,999,999, which is 999,999 numbers
- The final answer is therefore 235,298 - 999,999 = 27.

Define the well ordering principle. By Mathematical Induction, Prove that

(𝒏!) ≥ 𝟐𝒏−𝟏 for all integers 𝒏 ≥ 𝟏.
Well ordering principle: Every nonempty set of nonnegative integers has a smallest element. it
requires a nonempty set—it’s false for the empty set which has no smallest element because it has no
elements at all. And it requires a set of nonnegative integers—it’s false for the set of negative integers
and also false for some sets of nonnegative rationals—for example, the set of positive rationals. So,
the Well Ordering Principle captures something special about the nonnegative integers

To prove (𝒏!) ≥ 𝟐𝒏−𝟏 for all integers 𝒏 ≥ 𝟏 using Mathematical Induction

Basis Step:
n=1, LHS=1!=1
RHS=2(1)-1=2-1=1
Hence LHS=RHS and basis step is proved

Induction Step
Assume statement is true for some k
k!>= 2k-1
To prove for k+1
RHS=2(k+1)-1=2k+2-1=2k+1
LHS=(k+1)!
=k+1(k!)
>(k+1)(2k-1)
>(2k2-k+2k-1)
>(2k+1)(2k-1/2)
>(2k+1)=RHS

Prove that every positive integer n≥24 can be written as a sum of 5’sand/or 7’s.

We can prove that each integer n ≥ 24 can be expressed as a sum of 5's and 7's using
strong induction. For n = 24, we can write it as 5 + 5 + 7 + 7, which is a sum of 5's and 7's.

P a g e | 50
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

Assume that every integer k with 24 ≤ k ≤ n can be expressed as a sum of 5's and 7's. Now
we need to prove that n+1 can also be expressed as a sum of 5's and 7's.
Since we can write n as a sum of 5's and 7's, we have two cases:
If n is a multiple of 5, then n+1 is equal to (n-5) + 6. Since n-5 and 6 can be expressed as a
sum of 5's and 7's, n+1 can also be expressed as a sum of 5's and 7's.

If n is not a multiple of 5, then n+1 is equal to (n-7) + 8. Since n-7 and 8 can be expressed as
a sum of 5's and 7's, n+1 can also be expressed as a sum of 5's and 7's.

By the principle of strong induction, we have proven that each integer n ≥ 24 can be expressed
as a sum of 5's and 7's.

How many positive integers 𝑛 , can we form using the digits 3,4,4,5,5,6,7, if
we want 𝑛 to exceed 5,000,000.

- There are 7 digits available (3, 4, 4, 5, 5, 6, 7)

- The number must be larger than 5,000,000, which means it must start with a digit larger than 5
- The available digits that are larger than 5 are 6 and 7
- So the first digit of the number can be either 6 or 7, giving 2 possibilities
- For the remaining 6 digits, there are 7 choices for each digit, giving 7^6 = 117,649 possible
combinations
- Therefore, the total number of positive integers 'n' that can be formed is 2 * 117,649 = 235,298
- However, the question specifies that n must be larger than 5,000,000, so we need to subtract the
numbers from 5,000,001 to 5,999,999, which is 999,999 numbers
- The final answer is therefore 235,298 - 999,999 = 27.

By Mathematical Induction Prove that

𝑛(𝑛+1)(2𝑛+7)
1.3 + 2.4 + ⋯ … … . . +𝑛(𝑛 + 2) = 6

Basis Step:
For n=1, LHS=1.3=4
RHS=1(1+1)(2+7)/6=18/6=3
Hence LHS=RHS and basis step is proved
Induction Step:
Assume it is true for some k.
k(k+1)(2k+7)
Means: 1.3+2.4+3.5+……+k(k+2)= 6

To prove for k+1

LHS=1.3+2.4+3.5+……+k(k+2)+(k+1)(k+3)

P a g e | 51
 DISCRETE MATHEMATICAL STRUCTURES, DEPT. OF AIML

k(k+1)(2k+7)
= +(k+1)(k+3)
6

k(k+1)(2k+7)+6(k+1)(k+3)
= 3

(k+1)(2k2 +7k)+6k+18)
= 6

(k+1)(2k2 +13k+18)
= 6
(k+1)(𝑘+2)(2k+9)
= 6

=RHS

Find the number of permutations of the letters of the word MASSASAUGA. In

how many of these all four 𝐴’𝑠 are together? How many of them begin with 𝑆?

To find the number of permutations of the letters in the word MASSASAUGA, we need to count the
number of total arrangements. The word MASSASAUGA has 11 letters, and there are 3 S's and 4
A's, so there are a total of 10!/ (3!4!) = 25200 permutations of the letters.

To find the number of arrangements where all four A's are together, we can treat the group of four A's
as a single object. So, now we have 8 objects to arrange: M, S, S, S, G, U, A (the group of 4 A's), and
another A. The number of arrangements of these 8 objects is 7!/3! = 840.

To find the number of arrangements that begin with S, we fix the letter S in the first position. Now we
have 10 objects to arrange: S, M, A, S, A, S, A, U, G, A. The number of arrangements of these 10
objects is 9!/3!4! = 7560.

Therefore, there are 840 arrangements in which all four A's are together and 7560 arrangements that
begin with S.

i) Obtain the Coefficient of 𝑎5𝑏2 in the expansion of (2a-3b)7

ii) Using the Binomial theorem find the coefficient of 𝑥 5 𝑦 2 in
the expansion of (𝑥 + 𝑦)7.

(i) Let x=2a and y=-3b

Then Binomial theorem will be for (𝑥 + 𝑦)7
Hence coefficient for 𝑥 5 𝑦 2 will be 7C5(2a)5(-3b)2
=21*2^5*(-3)^2𝑎5 𝑏 2
=6048

(ii) As per Binomial theorem, term 𝑥 5 𝑦 2 appears in the expansion of (x+y)7

Hence, coefficient of 𝑥 5 𝑦 2 as per Binomial theorem is 7C5=21

P a g e | 52