Discrete Mathematics For Sppu 2 DR H R Bhapkar
Discrete Mathematics For Sppu 2 DR H R Bhapkar
Discrete Mathematics
(For IN SEM Exam - 30 Marks)
Dr. H. R. Bhapkar
M.Sc. SET, Ph.D. (Mathematics)
MIT Art, Design and Technology University’s
MIT School of Engineering, Lonikalbhor, Pune
Email : drhrbhapkar@gmail.com
Mobile : 9011227141
® ®
TECHNICAL
PUBLICATIONS
SINCE 1993 An Up-Thrust for Knowledge
(i)
Discrete Mathematics
(For IN SEM Exam - 30 Marks)
Published by :
® ®
Amit Residency, Office No.1, 412, Shaniwar Peth,
TECHNICAL Pune - 411030, M.S. INDIA, Ph.: +91-020-24495496/97
PUBLICATIONS
SINCE 1993 An Up-Thrust for Knowledge Email : sales@technicalpublications.org Website : www.technicalpublications.org
Printer :
Yogiraj Printers & Binders
Sr.No. 10/1A,
Ghule Industrial Estate, Nanded Village Road,
Tal. - Haveli, Dist. - Pune - 411041.
ISBN 978-93-332-0276-3
Preface
The importance of Discrete Mathematics is well known in various engineering fields.
Overwhelming response to our books on various subjects inspired us to write this book.
The book is structured to cover the key aspects of the subject Discrete Mathematics.
The book uses plain, lucid language to explain fundamentals of this subject. The
book provides logical method of explaining various complicated concepts and stepwise
methods to explain the important topics. Each chapter is well supported with necessary
illustrations, practical examples and solved problems. All the chapters in the book are
arranged in a proper sequence that permits each topic to build upon earlier studies. All
care has been taken to make students comfortable in understanding the basic concepts
of the subject.
The book not only covers the entire scope of the subject but explains the philosophy
of the subject. This makes the understanding of this subject more clear and makes it
more interesting. The book will be very useful not only to the students but also to the
subject teachers. The students have to omit nothing and possibly have to cover nothing
more.
We wish to express our profound thanks to all those who helped in making this
book a reality. Much needed moral support and encouragement is provided on
numerous occasions by our whole family. We wish to thank the Publisher and the
entire team of Technical Publications who have taken immense pain to get this book
in time with quality printing.
Any suggestion for the improvement of the book will be acknowledged and well
appreciated.
Authors
Dr. H. R. Bhapkar
Dr. Rajesh N. Phursule
(iii)
Syllabus
Discrete Mathematics - (210241)
Credit Scheme Examination Scheme and Marks
03 Mid_Semester (TH) : 30 Marks
(iv)
Table of Contents
Unit - I
(v)
1.13 Multiset.........................................................................................................1 - 45
1.13.1 Multiplicity of an Element . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 46
1.13.2 Equality of Multisets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 46
1.13.3 Union and Intersection of Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 46
1.13.4 Difference of Multisets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 47
1.13.5 Sum of Multisets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 - 47
(vi)
Unit - II
(vii)
(viii)
(ix)
(x)
Unit - I
1 Theory of Sets
Syllabus
Introduction and significance of Discrete Mathematics, Sets – Naïve Set Theory (Cantorian Set
Theory), Axiomatic Set Theory, Set Operatio ns, Cardinality of set, Principle of inclusion and
exclusion, Types of Sets - Bounded and Unbounded Sets, Diagonalization Argument, Countable
and Uncountable Sets, Finite and Infinite Sets, Countably Infinite and Uncountably Infinite Sets,
Power set.
Contents
1.1 Introduction
1.2 Sets
1.3 Methods of Describing Sets
1.4 Some Special Sets
1.5 Subsets
1.6 Types of Sets
1.7 Venn Diagrams
1.8 Operations on Sets
1.9 Algebra of Set Operations
1.10 Principle of Duality . . . . . . . . . . . . . . . . . . Dec.-06, 08, 11, 12, 13, 14, 15, 17, 19
. . . . . . . . . . . . . . . . . . May-05, 06, 08, 14 · · · · · · · · · Marks 6
1.11 Cardinality of Sets
1.12 The Principle of Inclusion and Exclusion for Sets
. . . . . . . . . . . . . . . . . . Dec.-04, 05, 07, 08, 10, 13, 14, 15, 19
. . . . . . . . . . . . . . . . . . May-05, 06, 07, 08,
. . . . . . . . . . . . . . . . . . 14, 15, 17, 19, · · · · · · · · · · · · Marks 13
1.13 Multiset . . . . . . . . . . . . . . . . . . Dec.-13, May-19 · · · · · · · · · · · Marks 4
(1 - 1)
TM
1.1 Introduction
The notion of a set is a fundamental concept to all of Mathematics and every branch
of mathematics can be considered as a study of sets of objects of one kind or another. A
great mathematician Cantor was the founder of the theory of sets. Let us now consider
the idea of a set.
1.2 Sets
A set is a collection of well defined objects. An object in the set is called a member or
element of the set. The objects themselves can be almost anything. e.g. Books, numbers,
cities, countries, animals, etc. In the above definition, the words set and collection for
almost all practical purposes are synonymous. Elements of a set are usually denoted by
lower case letters i.e. a, b, c, ... while sets are denoted by capital letters i.e.
A, B, C, ...
The symbol ' Î' indicates the membership in a set.
If "x is an element of a set A" then we write x Î A.
If "x is not an element of a set A" then we write as x Ï A.
Examples :
1) The set of letters forming the word "MATHEMATICS"
2) The set of students in a class SE Computer Engineering
3) s = {1, 2, 3, 4, 5, 6}
4) The set of professors in SPPU university.
5) The set of all telephone numbers in the directory.
A set may be described by listing all the members of the set between a pair of braces.
In this method the order in which the elements are listed is immaterial and it is used
for small sets. e.g. A = {1, 2, 3, 4, 5}, B = {a, b, c, d, e, f, g}
In this form, set is formed especially where the elements have a common
characteristic.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
It is not always possible to describe a set by the listing method or statement form.
A more compact or concise way of describing the set is to specify the common
property of all elements of the set
e.g. A = { x|x is real and x 2 > 100 }
B = { x|x is real and x 20 – x 10 + 1 = 0 }
1.5 Subsets
A set A is said to be a subset of the set B if every element of A is also an element of
B.
We also say that A is contained in B and denoted by A Ì B
If A is a subset of B i.e. A Ì B, then the set
B is called the superset of A.
The set with no elements is called an empty set or null set. It is denoted by f or { }.
If A Ì B then there are two possibilities.
i) A = B
ii) A ¹ B, A Ì B
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
i) A Ì B i.e. A is a subset of B.
ii) $ at least one element in B which is not in A.
i.e. B is not subset of A.
e.g. If A = {1, 2, 3} and B = {1, 2, 3, 4, 5}
then A is a proper subset of B.
It is denoted by A Ì B or A Ì B
Every set is a subset of itself and null set is a subset of every set.
Subsets A and Q are called improper subsets of A.
1) Universal Set :
A non empty set of which all the sets under consideration are subsets is called
universal set.
It is denoted by U. Universal set is not unique.
2) Singleton Set :
A set having only one element is called a singleton set. e.g. A = {5}, B = {f}
3) Finite Set :
A set is said to be finite if it has finite number of elements.
The number of elements in a set is called the cardinality of that set. It is denoted by
|A| cardinality of set may be finite or infinite.
e.g. {1, 2, 3, 4 , 5} Þ|A| = 5
4) Infinite Set :
A set is said to be infinite if it has infinite number of elements
e.g. N = set of natural numbers
|N| = ¥
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
5) Power Set :
The set of all subsets of a set A is called the power set of A.
The power set of A is denoted by P(A)
Hence P(A) = {X | X Ì A}
If A has n elements then P(A) has 2 n elements.
e.g.
Then
i) x Î A is true. But x Ì A is false as x is an element of A not subset of A
ii) {x } Ì A is true as {x} is a subset of A
iii) {x } Î A is false as {x} is not an element of A
iv) {x } Î P(A) is true.
v) f Î P(A), f Ì P(A) are true.
vi) {x } Î P(A) is true.
vii) {{x }} Î P(A) is false but {{x }} Ì P(P(A))
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
1) A Ì U U 2) A Ì B U
A
A
B
Fig. 1.7.1
Let A and B be two sets. The union of two sets A and B is the set of all those
elements which are either in A or in B or in both sets.
If is denoted by A È B
\ A È B = {x | x Î Aor x Î B }
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A B
AB
Fig. 1.8.1
Examples
1) A = {1, 2, 3, 4}, B = {x, y, z}
A È B = {1, 2, 3, 4, x, y, z}
2) A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, B = {2, 3, 5, 7, 11, 13}
A È B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13}
The intersection of two sets A and B is the set of all elements which are in A and
also in B. It is denoted by A Ç B -
\ A Ç B = {x | x Î A and x Î B }
By Venn diagram A Ç B is represented as
A U
AB
AB:
Fig. 1.8.2
Examples :
A
A or A'
Fig. 1.8.3
Examples :
1) U = f and f = U
2) ( A) = A
3) A È A = U, AÇ A=f
4) A È U = U, AÇ U=A
Let A and B be two sets. The difference A-B is the set defined as
A – B = {x | x Î A and x Î B }
Similarly,
B – A = {x | x Î B and x Ï A}
A U
B–A
A–B
Fig. 1.8.4
Examples :
Properties of difference
Let A and B be two sets. Then
1) A = U–A
2) A – A = f, f– f = f
3) A – A = A, A – A = A, U – f = f,
4) A – f = A, A– f = U – A
5) A – B = A Ç B
6) A – B = B – A iff A=B
7) A – B = A iff AÇ B = f
8) A – B = f iff AÌ B
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
If is also denoted by A D B.
By Venn diagram it is represented as
U
A B
AB:
Fig. 1.8.5
Examples :
1) AÅA = f
2) AÅf = A
3) AÅU = U – A = A
4) AÅA = U
5) A Å B = ( A È B) – ( A Ç B)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
7) Double Complement : ( A) = A
Proof : Proofs of 1), 2), 4), 5) are easy, so reader can prove these
3) To Prove A È (BÇ C) = (A È B) Ç ( A È C)
Let x Î A È (BÇ C) Þ x Î A or x Î BÇ C
Þ x Î A or (x Î B and x Î C)
Þ (x Î A or x Î B) and (x Î A or x Î C)
Þ (x Î A È B) and ( x Î A Ç C)
Þ x Î ( A È B) Ç ( A Ç C)
Hence A È (BÇ C) Ì (A È B) Ç (A È C)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A Ç ( BÈ C) Ì (A Ç B) È ( A Ç C)
6) Prove that AÈ B = AÇ B
Let x Î AÈ B Þ x Ï AÈ B
Þ x Ï A and x Ï B
Þ x Î A and x Î B
Þ x Î AÇ B
Þ AÈ B Ì AÇ B
Similarly AÇ B = AÈ B
Hence AÈ B = AÇ B
( A Ç B) = A È B
7) A = {x | x Ï A}
= {x | x Î A} = A
1.10 Principle of Duality SPPU : Dec.-06, 08, 11, 12, 13, 14, 15, 17, 19,
May-05, 06, 08, 14
The principle of duality states that any proved result involving sets and complements
and operations of union and intersection gives a corresponding dual result by replacing
È by f and È by Ç and vice versa.
Examples
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
AÇ A = A
AÇ U = A , AÈ U = U
AÇ U = A
AÇ A = f
i) A – {x, z} = {x, y, f }
ii) {{x, z }} – A = f
vi) {x} – A = f
ix) f– A = f
\ A – f = {b}
{f} – A = f and P(A) = {f, {f}, {b}, A}
A È P(A) = {f, {f}, {b}, A}
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A – B = B– B = f
B– A = A – A = f
Yes, B = C.
Consider B = B Ç U = BÇ ( A È A)
= (B Ç A) È ( B Ç A)
= (A Ç B) È ( A Ç B)
= (A Ç C) È ( A Ç C)
= (A È A) Ç C
= UÇ C
\ B=C
ii) No,
Let A = {x, y}, B = {y, z, w}, C = {y, p, q}
A Ç B = {y} = BÇ C But B¹ C
Example 1.10.7 If A Å B = A Å C, is B = C ?
Solution :
Yes, Let x Î B Þ x Î A or x Ï A
Suppose x Î A then x Î A Ç B Þ x Ï A Å B
Hence x Ï A Å C Þ x Î A Ç C Þ x Î C
i.e. if x Î A then BÍ C
Suppose x Ï A then x Ï A Ç B so that x Î A Å B
Þ x Ï A Å C Þ x Ï AÈ B Þ x ÎC
Hence BÍ C
Similarly C Í B
Hence B=C
Example 1.10.8 Let A and B are two sets. If A Í B, then prove that P(A) Í P(B). where
P(A) and P(B) are power sets of A and B sets. SPPU : Dec.-17, Marks 6
Solution : Let A and B be two sets.
Solution :
p( f) = {f }
p (p( f)) = {f, {f }}
p ( p ( p ( f))) = {f, {f }, {{f }}, {f, {f }}}
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Solution :
= [(A Ç B) È f] È B
= (A Ç B) È B = B
Þ x Î A and x Î B– C
Þ x Î A and ( x Î Band x Ï C)
Þ x Î A and x Ï ( BÇ C)
Þ x Î A – ( BÇ C)
\ A Ç (B– C) Ì A – (BÇ C)
Example 1.10.12 Salad is made with combination of one or more eatables, how many different
salads can be prepared from onion, carrot, cabbage and cucumber?
SPPU : Dec.-13, Marks 4
Solution : The number of different salads can be prepared from onion, carrot, cabbage
and cucumber with combination of one or more eatables is 2 4 – 1 = 16 – 1 = 15
Example 1.10.13 Explain the concepts of countably infinite set with example.
SPPU : Dec.-14, Marks 4
Solution : A set is said to be countable if its all elements can be labelled as 1, 2, 3, 4, ...
A set is said to be countably infinite
if, i) It is countable
ii) It has infinitely many elements i.e. It's cardinality is ¥.
For example
1) The set of natural numbers {1, 2, 3, ...} is countably infinite.
2) The set of integers is countably infinite.
3) The set of real numbers is infinite but not countable.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 1.10.14 Draw Venn diagram and prove the expression. Also write the dual of each of
the given statements.
i) ( A È B È C ) C = ( A È C ) C Ç ( A È B ) C
ii) (U Ç A) È (B Ç A) = A SPPU : Dec.-11, Marks 6
Solution : Consider the following Venn diagrams.
A B U U
A B
C C
c
1 ABC= 2 (A B C) =
Fig. 1.10.1
A B A B U
C C
c c
3 (A B) = 4 (A C) =
Fig. 1.10.2
A B U
c c
5 (A B) (A C)
Fig. 1.10.3
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A U A U
B B
1 UA= 2 BA=
A U A U
B B
3 (U A) (B A) = 4 A=
Fig. 1.10.4
From Venn diagrams (3) and (4)
(U Ç A) È (BÇ A) = A
A U A U
B B
C C
1 B= 2 B C=
A U A U
B B
C C
3 A (B C) = 4 AB=
and
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A U A U
B B
C C
5 A C= 6 (A B) (A C) =
From 3 and 6 ,
A È (B Ç C) = (A È B) Ç (A È C)
Solution : i) A Å B = (A È B) - (A Ç B)
A X A Y
B B
C C
AÅB= (A Å B) Å C
1 2
A B A B
C C
BÅC= A Å (B Å C)
3 and 4
From 2 and 4 ,
(A Å B) Å C = A Å (B Å C)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A B X A B X
C C
ABC= A–B=
1 2
A B X A B X
C C
A–C= (A – B) (A – C) =
3 4
and
A B
A – [(A–B) (A–C)] =
From 1 and 5
A B C = A [(A B) (A C)]
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Solution :
A B X A B X
C C
BC= A (B C) =
1 2
A B X A B X
C C
AB= AC=
3 4
A B X
(AB) (AC) =
From 2 and 5 ,
A (B C) = (A B) (A C)
Example 1.10.18 Let A, B, C be sets. Under what conditions the following statements are
true ?
i) ( A B) ( A C) A ii) ( A B) ( A C) SPPU : Dec.-06, 15, Marks 3
Solution : i) (A B) (A C) A
A X A X
B C OR
C
B
1 2
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
If B Ì A and C Ì A
then (A – B) È (A – C) = A
Or A, B, C are disjoint sets.
i.e. A Ç B Ç C = Æ
Then (A - B) È (A - C) = A
ii) (A - B) È (A - C) = Æ is true.
If A is empty set i.e. A = Æ
A X A X
B B
C C
BC= A (B C) =
1 2
A B X A B X
C C
AB= AC=
4
3
A B X
(AB) (AC)=
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
From 2 and 5
A (B Å C) = (A B) Å (A C)
Let A and B be two finite sets which are disjoint then |A È B| = |A| + |B|
Proof : If A = f, B=f then proof is obvious
|A – B| = |A|–|A Ç B| A B
Proof : By Venn diagram
A = (A – B) È (A Ç B)
(A – B) Ç (A Ç B) = f A–B
Proof Let D = BÈ C
\ |A È D| = |A|+|D| = |A Ç D|
\ |A È BÈ C| = |A È D| = |A|+|B|+|C|–|BÇ C| – | A Ç D|
= |A|+|B|+|C|–|BÇ C| – | A Ç (BÈ C) |
= |A|+|B|+|C|–|BÇ C| – | ( A Ç B) È ( A Ç C) |
= |A|+|B|+|C|–|BÇ C| – | A Ç B| –|A Ç C| +| A Ç BÇ C|
|A È BÈ C È D| = | A| +| B| +|C| +| D| – | A Ç B| – | A Ç C| – | A Ç D|
– | BÇ C| – | BÇ D| – |C Ç D|
= | A Ç BÇ C| +|A Ç BÇ D| +| A Ç C Ç D| +| BÇ C Ç D|
– | A Ç BÇ C Ç D|
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Examples :
Example 1.12.1 Among the integers 1 to 300 find how many are not divisible by 3, not by 5.
Find also how many are divisible by 3 but not by 7. SPPU : Dec.-08, Marks 6
Solution : Let A denotes the set of integers 1 to 300 divisible
Find |A Ç B| and |A - C|
We have A Ç B = A È B = U – (A È B)
\ |A È B| = | A| +| B| – | A Ç B|
= 100 + 60 – 20 = 140
\ |A Ç B| = |U|–|A È B| = 300 – 140 = 160
| A Ç C| = é
300 ù
|A – C| = | A| – | A Ç C|, = 14
êë 3 ´ 7 úû
|A – C| = 100 – 14 = 86
Hence, 86 integers between 1 – 300 are not divisible by 3 but not by 7.
Example 1.12.2 Out of 30 students in a college, 15 take an art course, 8 take maths course, 6
take physics course. It is know that 3 students take all courses. Show that 7 or more
students take none of the courses?
Solution : Let A be the set of students taking an art course
B be the set of students taking a maths course
C be the set of students taking a physics course
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
\ |A Ç B| ³ 3, |BÇ C| ³ 3, |A Ç C| ³ 3
\ |A Ç B| +|A Ç C| +|BÇ C| ³ 3|A Ç BÇ C|
\ |A È BÈ C| ³ 32 – 3| A Ç BÇ C| = 32 – 3 × 3 = 23
Hence |A È BÈ C| ³ 23
Hence the number of students taking at least one course is ³ 23. The students taking
none of the course is £ 30 – 23 = 7
Thus 7 or less students take none of the courses.
Solution : Suppose set A denotes the number of integers between 1 to 2000 divisible
by 2.
Set B is the number of integers between 1 and 2000 divisible by 3.
Set C is the number of integers between 1 and 2000 divisible by 5.
Set D is the number of integers between 1 and 2000 divisible by 7.
A = é
2000ù
= 1000
êë 2 úû
é 2000ù = 666
B =
êë 3 úû
é 2000ù =
C = 400
êë 5 úû
D = é
2000ù
= 285
êë 7 úû
é 2000ù =
AÇB = 333
êë 2 ´ 3 úû
AÇC = é
2000ù
= 200
êë 2 ´ 5 úû
é 2000ù =
AÇD = 142
êë 2 ´ 7 úû
BÇ C = é
2000ù
= 133
êë 3 ´ 5 úû
é 2000ù =
BÇ D = 95
êë 3 ´ 7 úû
é 2000ù =
CÇ D = 57
êë 5 ´ 7 úû
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
é 2000 ù =
A Ç BÇ C = 66
êë 2 ´ 3 ´ 5úû
A Ç BÇ D = é
2000 ù
= 47
êë 2 ´ 3 ´ 7 úû
é 2000 ù =
A Ç CÇ D = 28
êë 2 ´ 5 ´ 7 úû
BÇ CÇ D = é
2000 ù
= 19
êë 3 ´ 5 ´ 7 úû
é 2000 ù =
A Ç BÇ CÇ D = 9
êë 2 ´ 3 ´ 5 ´ 7 úû
Example 1.12.4 In the survey of 260 college students, the following data were obtained :
64 had taken a maths course,
94 had taken a cs course,
58 had taken a business course,
28 had taken both a maths and a business course,
26 had taken both a maths and a cs course,
22 had taken both a cs and a business course,
14 had taken all types of courses.
How many students were - surveyed who had taken none of the three types of courses.
SPPU : May-17, Marks 3
Solution : Let A be the set of students, taken a maths course.
The total number of students taken none of the three types of courses
= |U| – |A È B È C|
= 260 – 154 = 106
Example 1.12.5 Among 100 students, 32 study mathematics, 20 study physics , 45 study
biology, 15 study mathematics and biology, 7 study mathematics and physics, 10 study
physics and biology and 30 do not study any of the three subjects.
a) Find the number of students studying all three subjects.
b) Find the number of students studying exactly one of the three subjects.
Solution : Let A, B, C denotes the set of students studying mathematics, physics and
biology respectively.
And X = 100
A = 32
B = 20
C = 45
AÇC = 15
AÇB = 7
BÇ C = 10
A ¢Ç B¢Ç C¢ = 30
A ¢Ç B¢Ç C¢ = 100 - A È B È C
Or A È B È C = 100 – 30
= 70
a) A È BÈ C = A + B + C -[ A Ç B + A Ç C + BÇ C ] + A Ç BÇ C
70 = 32 + 20 + 45 – [7 + 15 + 10] + A Ç B Ç C
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
70 = 97 – [32] + A Ç B Ç C
70 – 65 = A Ç BÇ C
Þ A Ç BÇ C = 5
X
A B
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 1.12.6 A survey was conducted among 1000 people of these 595 are Democrats, 595
wear glasses, and 550 like icecream. 395 of them are Democrats who wear glasses, 350 of
them are Democrats who like icecream, and 400 of them wear glasses and like icecream 250
of them are Democrats who wear glasses and like icecream. How many of them are not
Democrats do not wear glasses, and do not like icecream ? How many of them are
Democrats who do not wear glasses and do not like icecream ?
Solution : X = 1000
1000
A B
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Number of people who are Democrats who do not like icecream and do not wear
glasses.
= A - A Ç B - A Ç C + A Ç BÇ C
= 595 – [395 + 300] + 250
= 845 – 695
= 150
Example 1.12.7 It is known that at the university 60 percent of the professors play tennis, 50
percent of them play bridge. 70 percent jog, 20 percent play tennis and bridge, 30 percent
play tennis and jog, and 40 percent play bridge and jog. If some one claimed that 20
percent of the professors jog and play bridge and tennis, would you believe this claim ?
Why ? SPPU : Dec.-13, Marks 6
Solution :
100
A B
Let A, B, C, denotes the number of professors play tennis, bridge and jog
respectively.
A = 60
B = 50
C = 70
AÇB = 20
AÇC = 30
BÇ C = 40
A Ç BÇ C = 20
A È BÈ C = A + B + C -[ A Ç B + A Ç C + BÇ C ] + A Ç BÇ C
= 60 + 50 + 70 – [20 + 30 + 40] + 20
= 110
which is not possible as A È B È C Ì X and the number of elements in A È B È C
cannot exceed number of elements in the universal set X.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 1.12.8 Among 200 students in a class, 104 students got an 'A', in first examination
and 84 students got 'A' in second examination. If 68 students did not get an 'A' in either
of the examination.
i) How many students got 'A' in both the examination.
ii) If number of students who got an 'A' in the first examination is equal to that who got
an 'A' in second examination. If the total number of students who got 'A' in exactly one
examination is 160 and if 16 students did not get 'A' in either examination. Determine
the number of students who got 'A' in first examination, those who got ‘A’ in second
examination and number of students who got 'A' in both examinations.
SPPU : Dec.-04, Marks 6
Solution : X Universal set
X = 200
F S
Let F denote the set of students who got an 'A' in first examination and S denote the
set of students who got an 'A' in second examination.
68 students did not get A in either examination i.e.
(F È S) ¢ = 68
Þ FÈ S = X - 1 (F È S) ¢
= 200 – 68
Þ FÈ S = 132
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
ii) F = S
ii) Also indicate how many are divisible by 3 or by 11 but not by all 3, 5 and 11.
iii) How many are divisible by 3 or 11 but not by 5 ? SPPU : May-05, Marks 6
Solution : Let A denote numbers divisible by 3.
=
500
A 166
3
=
500
B = 100
5
=
500
C = 45
11
= é
500 ù
AÇB = 33
êë 3 ´ 5úû
= é
500 ù
AÇC = 15
êë 3 ´ 11úû
= é
500 ù
BÇ C =9
êë 5 ´ 11úû
= é
500 ù
A Ç BÇ C =3
êë 3 ´ 5 ´ 11úû
i) A È BÈ C = A + B + C -[ A Ç B + A Ç C + BÇ C ] + A Ç BÇ C
= 257
ii)
X
A B
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
iii)
X
A B
Example 1.12.10 In the survey of 60 people, it was found that 25 read newsweek magazine,
26 read time, 26 read fortune. Also 9 read both newsweek and fortune, 11 read both
newsweek and time, 8 read both time and fortune and 8 read no magazine at all.
i) Find out the number of people who read all the three magazines.
ii) Fill in the correct numbers in all the regions of the Venn diagram.
iii) Determine number of people who reads exactly one magazine.
SPPU : Dec.-05, 10, 19, Marks 6
Solution : X ® Universal set
X = 60
Let N denote the number of people who read newsweek magazine.
\ N = 25
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
60
N T
8 8 10
3
6 5
12
F
Explanation :
As N T F = 3
and people who read N and T both = 11 which includes people of N T F also.
Hence people who read only N and T but not F will be 11 – 3, hence 8 people read
only N and T similarly T F = 8.
Then people read only T and F = 8 – 3 i.e. 5.
and N F = 9
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 1.12.11 Suppose that 100 out of 120 mathematics students at a college take at least
one of the languages French, German and Russian. Also suppose
65 study French, 20 study French and German
45 study German, 25 study French and Russian
42 study Russian, 15 study German and Russian
i) Find the number of students who study all the three languages.
ii) Fill in correct number of students in each region of Venn diagram.
iii) Determine the number K of students who study
a) Exactly one language.
b) Exactly two languages. SPPU : Dec.-05, Marks 6
Solution : X Universal set
X = 120
Let F be the number of students who study French. G be the number of students
who study German and R be the number of students who study Russian.
| F G R | = 100
F = 65, F G = 20
G = 45, F R = 25
R = 42, G R = 15
i) F G R = F G R [ F G F R G R ] F G R
100 = 65 + 45 + 42 – [20 + 25 + 15] + F G R
100 = 92+ F G R
F G R = 8
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
ii)
F G
28 12 18
8
17 7
10 R
Explanation
As F G R = 8
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A B C = A B C [ A B A C B C ] A B C
= 543
This show 543 numbers are divisible by 3 or 5 or 7. Hence numbers which are not
divisible by 3, nor by 5, nor by 7.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
= |A B C|
= X – A B C
A B
Example 1.12.13 In the class of 55 students the number of studying different subjects are as
given below : Maths 23, Physics 24, Chemistry 19, Maths + Physics 12, Maths +
Chemistry 9, Physics + Chemistry 7, all three subjects 4.
Find the number of students who have taken :
i) At least one subject ii) Exactly one subject iii) Exactly two subjects.
SPPU : May-07, Marks 6
Solution : Let X denote universal set.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
ii) Number of students studying mathematics but not physics and not chemistry.
= M – [ M P M C ] M P C
= 23 – [12 + 9] + 4 = 6 ... (1)
Number of students studying physics but not mathematics and not chemistry.
= P – [ M P P C ] M P C
= 24 – [12 + 7] + 4 = 9 ... (2)
Number of students studying chemistry but not mathematics and not physics.
= C [ M C P C ] M P C
= 19 – [9 + 7] + 4 = 7 … (3)
X
M P
6 8 9
4
5 3
7
C
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 1.12.14 100 of the 120 engineering students in a college take part in atleast one of
the activity group discussion, debate and quiz.
Also : 65 participate in group discussion, 45 participate in debate, 42 participate in quiz,
20 participate in group discussion and debate 25 participate in group discussion and quiz
15 participate in debate and quiz. Find the number of students who participate in : i) All
the three activities ii) Exactly one of the activities. SPPU : Dec.-07, Marks 4
Solution : Let X denote universal set
X = 120
ii) Number of students taking part in group discussion but not in debate and not in
quiz.
= A [ A B A C ] A B C
= 65 – [20 + 25] + 8 = 28 ... (1)
Number of students taking part in debate but not in group discussion and not in
quiz.
= B [ A B B C ] A B C
= 45 – [20 + 15] + 8 = 18 ... (2)
Number of students taking part in quiz but not in group discussion and not in
debate.
= C [ A C B C A B C ]
= 42 – [25 + 15] + 8 = 10 ... (3)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A B
28 12
18
8
17 7
10 C
Example 1.12.15 It was found that in the first year computer science class of 80 students, 50
knew COBOL, 55 'C' and 46 PASCAL. It was also know that 37 knew 'C' and COBOL,
28 'C' and PASCAL and 25 PASCAL and COBOL. 7 students however knew none of the
languages. Find
i) How many knew all the three languages ?
ii) How many knew exactly two languages ?
iii) How many knew exactly one language ? SPPU : May-15, Dec.-15, Marks 4
Solution : Let A denote the set of students who know COBOL.
ii) Number of students who know only COBOL and 'C' but not PASCAL.
= A B A B C
= 37 – 12 = 25 ... (1)
Number of students who know only COBOL and PASCAL but not 'C'.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
= A C A B C
= 25 – 12 = 13 ... (2)
Number of students who know only 'C' and PASCAL but not COBOL.
= B C A B C
= 28 – 12 = 16 ... (3)
iii) Number of students who know only COBOL but not 'C' and not PASCAL.
= A [ A B A C ] A B C
= 50 – [37 + 25] + 12 = 0 ... (4)
Number of students who know only 'C’ but not COBOL and not PASCAL.
= B [ A B B C ] A B C
= 55 – [37 + 28] + 12 = 2 ... (5)
Number of students who know only PASCAL but not COBOL and not 'C'.
= C [ A C B C ] A B C
= 46 – [25 + 28] + 12 = 5 ... (6)
X
B
A 25 2
12
13 16
Example 1.12.16 In a survey of 500 television watchers produced the following information
285 watch football, 195 watch hockey, 115 watch basketball, 45 watch football and
basketball, 70 watch football and hockey, 50 watch hockey and basketball and 50 do not
watch any of the three games.
i) How many people in the survey watch all three games ?
ii) How many people watch exactly one game ? SPPU : May-08, Marks 6
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
H denote the set of people who watch hockey and B denote the set of people who
watch basketball.
X Denote universal set
Then X 500, F = 285, H = 195, B = 115.
F B = 45, F H = 70, H B = 50
F B H = 50
i.e. |(F B H) | = 50
F B H = X ( F B H)
= 500 – 50 = 450
We know that the set is the collection of well defined distinct objects. But there are so
many practical situations in which objects are not distinct. For example 1) The collection
of alphabets in the word "Missicippi", collection = [m, i, i, i, i, s, s, c, p, p]
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Let A and B be two multisets. A and B are said to be equal multisets iff
( x) = B ( x), x Aor B
e.g. [a, b, a, b] = [a, a, b, b] but [ a, a] [ a]
Subset of Multisets
A multiset 'A' is said to be the multiset of B if multiplicity of each element in A is
less or equal to it's multiplicity in B.
e.g. [a] [a, a], [a, b, a, b, a] [a, a, a, b, b, b].
Example :
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Let A and B be two multisets. The sum of A and B is denoted by A + B and defined
as for each
x A + B, (x) = A ( x) B ( x)
e.g. A = [a, b, c, c], B = [a, a, b, b, c, c]
A + B = [a, a, a, b, b, b, c, c, c, c]
Examples :
(1) = 2, ( 2) = 2, ( 3) = 2, ( 4) = 1
Therefore,
A = [1, 2, 3, 4] or A = [1, 1, 2, 2, 3, 3, 4]
Example 1.13.2 Explain examples of multisets with its significance. SPPU : Dec.-13, Marks 4
x 3 3x 2 3x +1 = 0
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
P Q = {a, a, a, b, c, c, d, d}
P Q = {a,a,c}
P – Q = {a, d, d}
qqq
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Unit - I
2 Propositional Calculus
Syllabus
Propositional Logic - logic, Propositional Equivalences, Application of Propositional Logic -
Translating English Sentences.
Contents
2.1 Introduction
2.2 Statements or Propositions
2.3 Laws of Formal Logic
2.4 Connectives and Compound Statements . . . . . Dec.-06, 18, May-05, 07, 08, · · Marks 6
2.5 Propositional or Statement Formula
2.6 Tautology
2.7 Contradiction
2.8 Contingency . . . . . . . . . . . . . . . . . . Dec.-10, 12, · · · · · · · · · · · · · · Marks 6
2.9 Precedence Rule
2.10 Logical Equivalence . . . . . . . . . . . . . . . . . . Dec.-12, · · · · · · · · · · · · · · · · · Marks 3
2.11 Logical Identities
2.12 The Duality Principle
2.13 Logical Implication
2.14 Important Connectives
2.15 Normal Forms . . . . . . . . . . . . . . . . . . Dec.-04, 06, 08, 10, 12, 14
. . . . . . . . . . . . . . . . . . May-17, · · · · · · · · · · · · · · · · · Marks 4
2.16 Methods of Proof . . . . . . . . . . . . . . . . . . Dec.-09, May-06, 10 · · · · · · · · Marks 4
2.17 Quantifiers . . . . . . . . . . . . . . . . . . Dec.-08, 09, 10, 11, 15,
. . . . . . . . . . . . . . . . . . May-15· · · · · · · · · · · · · · · · · · Marks 4
(2 - 1)
TM
2.1 Introduction
A discrete structure is defined by a set of axioms. The properties of structure are
derived from the axioms as theorems. Such theorems are proved using valid rules of
reasoning. The propositional calculus (Mathematical logic) is concerned with all kinds of
reasoning. It has two aspects.
1) It is analytic theory of art of reasoning whose goal is systematic and codify the
principles of valid reasoning.
2) It is inter-related with problems relating the foundation of mathematics.
A great mathematician Frege G. (1884-1925) developed the idea regarding a
mathematical theory as applied branch of logic.
Every student of engineering should learn logic because principles of logic are
valuable to problem analysis, programming, logic designing, code designing and many
more.
Examples :
1) There are 5 days in a week
2) 2 + 5 = 7
3) y + 3 = 8
4) It will rain tomorrow
5) There are 12 months in a year
Examples (2) and (5) are true statements
Example (1) is false statement
In example (3), it's truth value depends upon the value of y. If y is 5 then sentence is
true and if y ¹ 5 then sentence is false. Therefore (4) is not a statement.
In example (4), it's truth value cannot be predicted at this moment but it can be
definitely determined tomorrow. Hence it is a statement.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A statement which cannot be further split into simple sentences, is called primary or
primitive or atomic statements.
In day to day life, we use the words NOT, AND, OR, IF-Then, as well as, BUT,
WHILE to connect two or more sentences. But these connectives are flexible in their
meanings, and lead to inexact and ambiguous interpretations. However, mathematics is a
very precise language and every symbol of mathematics has the unique meaning or
interpretation in mathematical ocean.
Hence we take some special connectives with precise meaning to suit our purpose.
Following are the common connectives with symbols or their rotations.
2 And (Meet) ^
3 Or (Join) v
4 If .... then ®
5 If an only if (iff) «
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
A table showing the truth value of a statement formula is called truth table.
2.4.3 Negation
Let p be any simple statement, then the negation of p is formed by writing "It is false
that" before p or introducing the word "not" at the proper place. The negation of p is
also obtained by writing "p is false". The negation of p is denoted by ~ p or Ø p or p. If
the statement p is true, then ~ p is false and if p is false then ~ p is true.
The truth table for negation of p is given below
p ~p
T F
F T
Examples :
2.4.4 Conjunction
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
p q pÙq
T T T
T F F
F T F
F F F
Example 2.4.1
T (n = 2) F (n = 2) F (Q n < 5)
F (n = 50) F --- F (There does not exist any number s.t. n > 20 and n < 5)
2.4.5 Disjunction
A compound statement obtained by combining two simple statements by using the
connective "or" is called the disjunction.
i.e. If p and q are simple statements then the compound statement "p or q" is the
disjunction of p and q. It is denoted by p Ú q. p Ú q is read as "p or q" or "p join q".
If p is false and q is false then p Ú q is false. Otherwise p Ú q is true. The truth table of
p Ú q is as follows :
p q pÚq
T T T
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
T F F
F T T
F F F
Sr. p q Disjunction p Ùq
No.
p q p®q
T T T
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
T F F
F T T
F F T
Examples :
1) Let p : Atharva is a graduate
q:3+5=8
\ p ® q : If Atharva is a graduate then 3 + 5 = 8
Let N be the set of natural numbers and Q be the set of rational numbers. We know
that every natural number is a rational number.
Let p : n is a natural number
q : n is a rational number
p : n ÎN q : n ÎQ p ® q : if n Î N then n Î Q
T (n = 2) T (n Î Q) T (Q n = 2 is rational)
Note : If p then q
p only if q
q if p
p is sufficient for q
q is necessary for p
Above all are equivalent to p ® q
If p and q are two statements, then the compound statement "p if and only if q" is
called a biconditional statement. It is denoted by P ® or p « q.
¬
The biconditional statement is also read as
"p if and only if q" or "p iff q" or "p implies and implied by q" or "p is necessary and
sufficient for q".
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
If p and q have the same truth value then p « q is true. In other cases p « is false.
The truth table for p « q is as follows
p q p«q p®q q ®p (p ® q) Ù (q ® p)
T T T T T T
T F F F T F
F T p T F F
F F T T T T
By above table
p « q and ( p ® q) Ù (q ® p) are equivalent.
Examples
1) Let p : x = 4 q : x + 9 = 13
\ p «q : x = 4 if and only if x + 9 = 13
2) 5 + 6 = 11 iff 11 + 6 = 17
3) We know that an integer n is an even iff n is divisible by 2.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
T F F T F T T F
F T T F T F F T
F F T T T T T T
Example 2.4.3 Let p denote the statement, "The material is interesting'. q denote the
statement, "The exercises are challenging", and r denote the statement, "The course is
enjoyable".
Write the following statements in symbolic form :
i) The material is interesting and exercises are challenging.
ii) The material is interesting means the exercises are challenging and conversely.
iii) Either the material is interesting or the exercises are not challenging but not both.
iv) If the material is not interesting and exercises are not challenging, then the course is
not enjoyable.
v) The material is uninteresting, the exercises are not challenging and the course is not
enjoyable. SPPU : Dec.-06, May-08, Marks 6
Solution :
i) pÙq
ii) (p ® q) Ù (q ® p)
iii) p Å ~ q
iv) (~ p Ù ~ q) ® ~ r
v) ~ p Ù ~ q Ù ~ r
Example 2.4.4 Express following statement in propositional form :
i) There are many clouds in the sky but it did not rain.
ii) I will get first class if and only if I study well and score above 80 in mathematics.
iii) Computers are cheap but softwares are costly.
iv) It is very hot and humid or Ramesh is having heart problem.
v) In small restaurants the food is good and service is poor.
vi) If I finish my submission before 5.00 in the evening and it is not very hot I will go
and play a game of hockey. SPPU : May-05, Marks 6
Solution :
i) p : There are many clouds in the sky
q : It rain
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
\ p Ù~q
ii) p : I will get first class
q : I study well
r : Score above 80 in mathematics
\ p « (q Ù r)
iii) p : Computers are cheap
q : Softwares are costly
\ p Ùq
iv) p : It is very hot
q : It is very humid
r : Ramesh is having heart problem
\ (p Ù q) Ú r
v) p : In small restaurant food in good
q : Service is poor
\ p Ùq
vi) p : I finish my submission before 5:00 p.m.
q : It is very hot
r : I will go
s : I will play a game of hockey
\ (p Ù ~ q) ® (r Ù s)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Solution :
p : 3<b
q : 1+1=2
p 1
r : sin =
3 2
Symbolic form : p Ù q ® r
Contrapositive : (~ r ® ~ (p Ù q))
i.e. ~ r ® (~ p Ú ~ q)
p 1
i.e. if sin ¹ then 3 ³ b or 1 + 1 ¹ 2
3 2
Converse : r ® (p Ù q)
p 1
i.e. if sin = then 3 < b and 1 + 1 = 2
3 2
Inverse : ~( p Ù q) ® ~ r
i.e. (~ pÚ ~ q) ® ~ r
p 1
i.e. if 3 ³ b or 1 + 1 ¹ 2 then sin ¹
3 2
Example 2.4.7 Express the contrapositive, converse, inverse and negation forms of the
conditional statement given below.
'If x is rational, then x is real'. SPPU : Dec.-06, Marks 4
Solution :
Let p : x is rational
q : is real
Symbolic form : p ® q
Contrapositive : (~ q ® ~ p)
If x is not real, then x is not rational
Converse : (q ® p)
If x is real then x is rational
Inverse - (~ p ® q)
If x is not rational, then x is not real
Negation : ~ ( p ® q)
º ~ ( p Ú ~ q)
º ~ pÙ~~q
º ~p Ù q
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
2.6 Tautology
A statement formula that is true for all possible values of it's propositional variables
is called a Tautology.
e.g. p Ú ~ p is a tautology
2.7 Contradiction
A statement formula that is always false for all possible values of variables is called a
contradiction or absurdity.
Example : p Ù ~ p is a contradiction
p p p®p
T T T
F F T
p ~p p Ú~ p ~ (p Ú ~ p)
T F T F
F T T F
p ~p p Ù~ p ~ (p Ù ~ p)
T F F T
F T F T
T T T T F F
T F F T F F
F T F T F F
F F F F T F
Hence ( p Ù q) Ù ~ ( p Ú q) is a contradiction
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
p q ~p p®q qÚ~ p (p ® q) « (q Ú ~ p)
T T F T T T
T F F F F T
F T T T T T
F F T T T T
p q r p ® q p ® r q ® r p ® (q ® r) (p ® q) ® (p ® r) [ p ® (q ® r) ] ®
[ (p ® q) ® (p ® r) ]
T T T T T T T T T
T T F T F F F F T
T F T F T T T T T
T F F F F T T T T
F T T T T T T T T
F T F T T F T T T
F F T T T T T T T
F F F T T T T T T
Hence [ ( p ® (q ® r) ] ® [ ( p ® q) ® ( p ® r) ] is a tautology.
iv) Consider the truth table
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T 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
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
T T T T T T T T T T
T T T F T F T F T T
T T F T T T T T T T
T T F F T T T T T T
T F T T F T T F T T
T F T F F F T F F T
T F F T F T T F T T
T F F F F T T F F T
F T T T T T T T T T
F T T F T F T F T T
F T F T T T F F T T
F T F F T T F F T T
F F T T T T T T T T
F F T F T F T F F T
F F F T T T F F T T
F F F F T T F F F T
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
I II
P Q R QÚR P ® (Q Ú R) P®Q P ® R (P ® Q) Ú (P ® R)
T T T T T T T T
T T F T T T F T
T F T T T F T T
T F F F F F F F
F T T T T T T T
F T F T T T T T
F F T T T T T T
F F F F T T T T
In real life, we come across several similar things with respect to different aspects.
e.g. Two cars are similar with respect to average, two students are similar with respect
to F.E. marks.
Likewise in logic, we can say that two propositions are similar with respect to their
truth values.
Definition : Two propositions A and B are logically equivalent iff they have the same
truth value for all choices of the truth values of simple propositions involved in it.
Two propositions (formulas) are equivalent even if they have different variables. Two
statement formulas P and Q are equivalent
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Iff P « Q is a tautology.
If p is equivalent to Q then it can be represented as P Û Q or P º Q.
The symbol Û is not a connective
Example 2.10.1 Prove by constructing the truth table p ® ( q Ú r) º ( p ® q) Ú ( p ® r) .
SPPU : Dec.-12, Marks 3
Solution : Consider truth table
p q r q Úr p ® (q Ú r) p®q p®r (p ® q) Ú (p ® r)
T T T T T T T T
T T F T T T F T
T F T T T F T T
T F F F F F F F
F T T T T T T T
F T F T T T T T
F F T T T T T T
F F F F T T T T
In the columns of p ® (q Ú r) and (p ® q) Ú ( p ® r), truth values are same for all
possible choices of truth values of p, q and r. Hence
p ® (q Ú r) º ( p ® q) Ú ( p ® r )
Example 2.10.2 Prove that
p « q º ( p ® q) Ù ( q ® p) º (~ p Ú q) Ù (~ q Ú p).
p q ~p ~q p®q q ® p (p ® q) p « q ~ p Ú q ~ q Ú p (~ p Ú q) Ù (~ q Úp)
Ù (q ® p)
T T F F T T T T T T T
T F F T F T F F F T F
F T T F T F F F T F F
F F T T T T T T T T T
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
2. Idempotence of Ù p º pÙp
5. Associativity of Ú p Ú ( q Ú r) º ( p Ú q) Ú r
6. Associativity of Ù p Ù ( q Ù r) º ( p Ù q) Ù r
7. Distributivity of Ù over Ú p Ù ( q Ú r) º ( p Ù q) Ú ( p Ù r)
8. Distributivity of Ú over Ù p Ú ( q Ù r) º ( p Ú q) Ù ( p Ú r)
9. Double negation p º ~ (~ p)
p q ~p ~q pÚq ~ (p Ú q) ~ pÙ~ q
T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T
From the table, truth values of ~ ( p Ú q) and ~ pÙ ~ q are same for each choice of
p and q
Hence ~ ( p Ú q) º ~ p Ù ~ q
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
ii) ~ ( p Ú q) º ~ p Ú ~ q
Consider the table
p q ~p ~q pÙq ~ (p Ù q) ~ pÚ~ q
T T F F T F F
T F F T F T T
F T T F F T T
F F T T F T T
From the table, truth values of ~ ( p Ù q) and (~ pÚ ~ q) are same for each choice of p
and q.
Hence ~ ( p Ù q) º (~ p Ú ~ q)
Example 2.11.2 Absorption laws
i) p Ú ( p Ù q) º p ii) p Ù ( p Ú q) º p
Solution :
i) p Ú (p Ù q) º p
Consider the table
p q pÙq p Ú (p Ù q) p
T T T T T
T F F T T
F T F F F
F F F F F
From the table, in last two columns truth tables of p Ú (p Ù q) and p are same for each
choice of p and q.
Hence p Ú (p Ù q) º p
ii) p Ù (p Ú q) º p
Consider the table
p q pÚq p Ù (p Ú q) p
T T T T T
T F T T T
F T T F F
F F F F F
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
p q ~p ~ pÚq p®q
T T F T T
T F F F F
F T T T T
F F T T T
II) NOR :
The connective "NOR" is a combination of "NOT" and "OR" where "NOT" stands for
negation and "OR" stands for the disjunction. It is denoted by the symbol ¯ and defined
as
P ¯ Q « ~ (P Ú Q) \ P ¯ Q º ~ (P Ú Q)
2.15 Normal Forms SPPU : Dec.-04, 06, 08, 10, 12, 14, May-17
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Examples :
1) (p Ù q) Ú (q) Ú (~ q Ù p)
2) (p Ù q Ù r) Ú (p Ù r) Ú (p Ù q) Ú (p Ù r)
3) ( p Ù r ) Ú ( p Ù q)
4) (~ p Ù r ) Ú (~ q Ù r ) Ú (~ r )
All above examples are in disjunctive normal form.
Examples :
1) p Ù (p Ú q)
2) ( p Ú q) Ù (~ p Ú q) Ù (~ q)
3) ( p Ú q Ú r ) Ù (~ p Ú r ) Ù ( p Ú ~ q Ú r )
All above examples are in conjunctive normal form.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Solution :
i) p Ù (p ® q) º p Ù (~ p Ú q) ~ cnf
º (p Ù ~ p) Ú ( p Ù q)
º F Ú (p Ú q)
º (p Ù q) … Definition a single conjunctive
ii) ~ (p Ú q) ®
¬ (p Ù q) º ( ~ ~ (p Ú q) Ú ( p Ù q)) Ù ( ~ (p Ù q) Ú ~ (p Ú q))
º ((p Ú q) Ú ( p Ù q) Ù ((~ p Ú ~ q) Ú (~ p Ù ~ q)
º (p Ú q) Ù ((~ p Ú ~ q Ú ~ p) Ù (~ p Ú ~ q Ú ~ q))
º (p Ú q) Ù (~ p Ú ~ q) Ù (~ p Ú ~ q)
º (p Ú q) Ù (~ p Ú ~ q) … cnf
Further
(p Ú q) Ù (~ p Ú ~ q) º ((p Ú q) Ù ~ p) Ú ((p Ú q) Ù ~ q)
º (p Ù ~ q) Ú (q Ù ~ p) Ú ((p Ù ~ q) Ú (q Ù ~ q)
º F Ú (q Ù ~ p) Ú ( p Ù ~ q) Ú F
º (p Ù ~ p) Ú ( p Ù ~ q) … Definition
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 2.15.2 Find the conjunctive normal form and disjunctive normal form for the
following :
i) ( p Ú q) ® q ii) p « ( p Ú q) SPPU : Dec.-06, 14, May-17, Marks 3
Solution :
i) ( p Ú q) ® q º ( p Ú q) Ú q
º ( p Ù q) Ú q
º (p Ù q) Ú q … Definition
(p Ù q) Ú q º ( p Ú q) Ù (q Ú q)
º (~ p Ú q) Ù q … cnf
p ´ (p Ú q) º (p Ú ( p Ú q)) Ù ((p Ú q) Ú p)
º (p Ú p Ú q) Ù ((p Ù q) Ú p)
º (p Ú q) Ù ( p Ú p) Ù (q Ú p)
º (p Ú q) Ù p Ù (q Ú p) … cnf
º ((p Ù p) Ú (q Ù p)) Ù (q Ú p)
º (F Ú (q Ù p)) Ù (q Ú p)
º (q Ù p) Ù (q Ú p)
º (q Ù p Ù q) Ú (q Ù p Ù p)
º (F Ù p) Ú (q Ù p)
º F Ú (q Ù p)
º (q Ù p) … Definition
Example 2.15.3 Find the conjunctive and disjunctive normal forms for the following without
using truth table
i) ( p ® q) Ù ( q ® p) ii) (( p Ù ( p ® q)) ® q) SPPU : Dec.-04, 10, 14, Marks 4
Solution :
i) (p ® q) Ù (q ® p) º (~ p Ú q) Ù (~ q Ú p)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
i) p Ù (p ® q) º ( p Ù (~ p Ú q))
º ( p Ù ~ p) Ú ( p Ù q)
º Ú ( p Ù q)
º ( p Ù q) … cnf
ii) q Ú (p Ù ~ q) Ú (~ p Ù ~ q) º ((q Ú p) Ù (q Ú ~ q) Ú (~ p Ú ~ q)
º (q Ú p) Ù T Ú ( ~ p Ù ~ q)
º (q Ú p) Ú (~ p Ù ~ q)
º (q Ú p Ú ~ p) Ù (q Ù p Ú ~ q)
º (q Ú T) Ù ( p Ú q Ú ~ q)
º T Ù (p Ú T) º T Ù T
º T º (pÚ ~ p) which is the required cnf (single disjunct)
Example 2.15.5 Find DNF of (( p ® q) Ù ( q ® p)) Ú p
SPPU : Dec.-14, Marks 4, May-17, Marks 3
Solution :
Solution :
(~ p Ù q Ù r ) Ú ( p Ù q) º ( p Ù q) Ú (~ p Ù q Ù r )
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
º ( p Ú (~ p Ù q Ù r )] Ù [q Ú (~ p Ù q Ù r )]
º [( p Ú ~ p) Ù ( p Ú q)] Ù [ p Ú r)] Ù [ (q Ú ~ p) Ù (q Ú q) Ù (q Ú r )]
º [T Ù ( p Ú q) Ù ( p Ú r )] Ù [(q Ú ~ p) Ù q Ù (q Ú r)]
º ( p Ú q) Ù ( p Ú r ) Ù (q Ú ~ p) Ù q which is the required cnf
p q r ~p q Úr p « (q Ú r) [p « (q Ú r)] ® ~ p
T T T F T T F
T T F F T T F
T F T F T T F
T F F F F F T ¬ 1
F T T T T F T ¬ 2
F T F T T F T ¬ 3
F F T T T F T ¬ 4
F F F T F T T ¬ 5
Consider only 'T' from last column and choose corresponding values of 'T' from p, q
and r. For the first marked row 1 corresponding p is T, q is F and r is F. So take
p Ù ~ q Ù ~ r or p Ù q ¢ Ù r ¢
For 2 nd T ® ~ p Ù q Ù r, 3 rd T ® ~ p Ù q Ù ~ r,
4 th T ® ~ p Ù q Ù r, and 5 th T ® ~ pÙ ~ q Ù ~ r
Hence the logically equivalent dnf form is
[ p « (q Ú r)] ® ~ p º (p Ù ~ q Ù r) Ú (~ p Ù q Ù r) Ú (~ p Ù q Ù ~ r)
Ú (~ p Ù ~ q Ù r) Ú (~ p Ù ~ q Ù ~ r)
Solution :
(~ p Ú ~ q) ® (~ p Ù ~ r) º ~ (~ p Ú ~ q) Ú (~ p Ù r)
º (~ (~ p) Ù ~ (~ q)] Ú (~ p Ù r)
º (p Ù q) Ú (~ p Ù r) which is dnf
º (p Ù q Ù (r Ú ~ r)) Ú (~ p Ù r Ù (q Ú ~ q))
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
º (p Ù q Ù r) Ú (p Ù q Ù ~ r) Ú (~ p Ù r Ù q) Ú (~ p Ù r Ù ~ q)
Solution :
[( p Ù q) Ú ( ~ p Ù r) º [(p Ù q) Ú ~ p] Ù [ (p Ù q) Ú r]
º (p Ú ~ p) Ù (q Ú ~ p) Ù (p Ú r ) Ù ( q Ú r)
º (q Ú ~ p Ú ( r Ù ~ r ) Ù (p Ú r Ú ( q Ù ~ q)) Ù (q Ú r Ú ( p Ù ~ p) )
º (q Ú ~ p Ú r ) Ù (q Ú ~ p Ú ~ r ) Ù (p Ú r Ú q) Ù (p Ú r Ú ~ q) )
Ù (q Ú r Ú p) Ù (q Ú r Ú ~ p)
º (p Ú q Ú r ) Ù (~ p Ú q Ú r ) Ù (~ p Ú q Ú ~ r) Ù (p Ú ~ q Ú r)
Solution :
~ p Ú q º [~ p Ù (q Ú ~ q)] Ú [q Ù ( p Ú ~ p)]
º (~ p Ù q) Ú (~ p Ù ~ q) Ú (q Ù p) Ú (q Ù ~ p)
º (~ p Ù q) Ú (~ p Ù ~ q) Ú (p Ù q)
We have learned statements or propositions and their truth values. Now, we will
discuss ways by which statements can be linked to form a logically valid argument.
Whenever an assertion is made, which is claimed to be true, one has to state an
argument which produces the truth of the assertion. To construct a proof we need to
derive new assertions from existing ones by different ways. This is also done by using
valid of inference.
Valid argument : A valid argument is a finite sequence of statements p1 , p 2 , .... p n
called as premises (or assumptions or hypothesis) together with a statement C, called the
conclusion such that p1 Ù p 2 Ù p 3 Ù ... Ù p n ® C is a tautology.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
As mathematical proof is a logical argument that verifies the truth of the theorem.
There are several ways of proving a theorem which are based on one or more rules of
inference.
There are following most commonly used rules of inference.
Whenever the statements p and p q are accepted as true, then we must accept the
statement q as true. This rule is represented in the following form
pq
p
q
The assertions above the horizontal line are called premises OT hypothesis. And the
assertion below the line is called the conclusion.
This rule constitutes a valid argument as (p q) p q is a tautology.
The truth table is as follows
p q pq (p q) p [(p q) p] q
T T T T T
T F F F T
F T T F T
F F T F T
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 2.16.1 Determine whether the argument is valid or not. If I try hard and I have
talent then I will become a musician. If I become a musician, then I will be happy.
Therefore if I will not be happy then I did not try hard or I do not have talent.
SPPU : May-10, Marks 4
Solution :
Let p : I try hard
q : I have talent
r : I will become musician
s : I will be happy
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
To check validity of this statement, one way is to use truth table or prove logically.
Suppose assignment is invalid. This means that for some assignment of truth values s 1
Example 2.16.2 Test the validity of the argument. If a person is poor, he is unhappy. If a person
is unhappy, he dies young. Therefore poor person dies young. SPPU : Dec.-09, Marks 4
Solution :
Solution :
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
s1 : p q
s2 : q r
s : r ~ p
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 2.16.5 I am happy if my program runs. A necessary condition for the program to
run is it should be error free. I am not happy. Therefore the program is not error free.
Solution :
Let p : I am happy
q : My program runs
r : Program should be error free
In symbolic form
qp
qr
~p
~r
p q r q p q r ~p (q p) (q r) ~ p (I) ~ r
(I)
F F T T T T T F
In grammar a predicate is the word in a sentence which expresses what is said about
object. i.e. properties of an object or relation among objects. For example "is a good
teacher", "is a clever student" are predicates. In logic predicate has a broaden role than
in grammar. Predicate is presented by using a variable x in place of holder. e.g. x is a
prime number.
An assertion that contains one or more variables is called a predicate. It's truth value
is predicated after assigning truth values to its variables.
A predicate p containing n variables x 1 , x 2 , ... x n is called an n-place predicate and
denoted by p (x 1 , x 2 , x 3 , ... x n ). Each variable x i is called as argument.
The values which the variables may assume constitute a collection is called the
universe of discourse or domain of discourse.
There are two types of quantifiers.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
If p(x) is a predicate with x as an argument then the universal quantifier for p(x) is
the statement.
"For all values of x, p(x) is true". We denote the phrase "For all" by
means for all or for each or for every.
If p(x) is true for all values of x then
x p(x) is true.
For example - p(x) : x 0, where x is any positive integer.
The proposition x p(x) is true.
However, if x is an integer x p(x) is false.
2. x [~ p(x)] x p(x)
x [p Q(x)] p ( x Q(x))
2) Distributivity of over
x [p(x) Q(x)] x p(x) x Q(x)
x [p Q(x)] p (x Q(x))
3) x [p Q(x)] p [ x Q(x)]
4) x [p Q(x)] p [x Q(x)]
5) ~ [ xp(x)] x [~ p(x)]
6) ~ [ x p(x)] x [~ p(x)]
7) x p(x) x p(x)
8) x p(x) x Q(x) x ( p(x) Q(x)
9) x(p(x) Q(x)) x p(x) x Q(x)
III)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 2.17.1 Represent the arguments using quantifiers and find its correctness.
All students in this class understand logic. Ganesh is a student in this class. Therefore
Ganesh understands logic. SPPU : Dec.-11, Marks 4
Solution :
Let C(x) : x is a student in this class
L(x) : x understands logic
In symbolic form
x (C(x) L(x))
C(a)
L(a)
Example 2.17.3 Using information in example 2.17.2 write an english sentence for each of the
symbolic statement given below
i) x (~ Q ( x ))
ii) y(~ p( y))
iii) ~ [ x ( p( x ) Q ( x ))] SPPU : Dec.-10, Marks 4
Solution :
i) All integers are not prime numbers
ii) At least one integer is not even.
iii) It is not the case that there exists an integer which is even and prime.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 2.17.6 Rewrite the following statements using quantifier variables and predicate
symbols.
i) All birds can fly
ii) Not all birds can fly
iii) Some men are genius
iv) Some numbers are not rational
v) There is a student who likes Maths but not Hindi
vi) Each integer is either even or odd SPPU : Dec.-08, Marks 4
Solution :
i) Let B(x) : x is a bird
F(x) : x can fly
Then the statement can be written as
x [B(x) F(x)]
ii) x [B(x) ~ F(x)]
iii) Let M(x) : x is a man
G(x) : x is a genius
The statement in symbolic form as x [M(x) G(x)]
iv) Let N(x) : x is a number
R(x) : x is rational
The statement in symbolic form as x [N(x) ~ R(x)] or ~ [ x (N(x) R(x)]
v) Let S(x) : x is a student
M(x) : x likes Maths
H(x) : x likes Hindi
The statement in symbolic form as x [S(x) M(x) ~ H(x)]
vi) Let I(x) : x is an integer
E(x) : x is even
O(x) : x is odd
The statement in symbolic form as x [I(x) E(x) O(x)]
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
qqq
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Unit - I
3 Mathematical Induction
Syllabus
Proof by Mathematical Induction and Strong Mathematical Induction.
Contents
3.1 Introduction
3.2 First Principle of Mathematical Induction Statement
3.3 Second Principle of Mathematical Induction Statement
(Strong Mathematical Induction) . . . . . . . . . . . Dec.-04, 05, 06, 08, 10, 11,12,
. . . . . . . . . . . . . . . . . . 13, 14, 15, 18, May-05, 06, 07, 08,
. . . . . . . . . . . . . . . . . . 14, 15, 17, 18, 19 · · · · · · · · · · Marks 6
(3 - 1)
TM
3.1 Introduction
Mathematical induction is a powerful technique in applied mathematics especially in
number theory, where many properties of natural numbers are proved by this method.
In day to day life, we are often required to generalise a particular pattern for the
prediction purpose. The generalisation is achieved by using a statement involving a
variable as natural number.
Mathematical induction is very useful technique or tool for the programmers to check
whether a program statement is loop invariant or not.
There are two principles of mathematical induction :
1) First principle of mathematical induction.
2) Second principle of mathematical induction.
Example 3.3.1 n( n 1)
Prove that : 1 + 2 + 3 + 4 … + n =
2
SPPU : May-17, Dec.-18, Marks 4
Solution : Let, P(n) be the given statement
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
For n = 1, L.H.S. = 1
1(1 1)
R.H.S. = =1
2
For n = 1, L.H.S. = R.H.S.
P(1) is true.
Step 2 : Assume that P(k) is true
k(k 1)
i.e. 1 + 2 + 3 + ...... + k = … (1)
2
Consider, 1 + 2 + 3 + ...... + k + (k+ 1)
k(k 1) k(k 1) + 2(k 1) (k 1) + (k 2)
= k 1 = =
2 2 2
Hence P(k + 1) is true
By the principle of mathematical induction P(n) is true for all n.
1. Basis of induction
Hence assuming P(k) is true, P(k + 1), is also true. Therefore by mathematical
induction P(n) is true for all n 1.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
1. Basis of induction :
For n = 1, L.H.S. = 1 2 = 1,
1 (1) ( 3)
R.H.S. = =1
3
L.H.S. = R.H.S.
Hence
k (2k 1) (2 k 1 )
[1 2 3 2 5 2 ... (2k 1) 2 ] (2k 1) 2 = (2k 1) 2 ... (Using 1)
3
(2k 1)
= [2k 2 k + 3 (2k 1)]
3
(2k 1)
= [2k 2 5k 3]
3
(2k 1)
= [2k 2 2k 3k 3]
3
(2k 1)
= [(2k 3) (k 1)]
3
(k 1)(2 k + 1) (2k 3)
=
3
(k 1) [2 (k 1) 1][2 (k 1) 1]
=
3
Example 3.3.4 n 2 (n + 1) 2
Show that 1 3 2 3 3 3 ... n3 = = (1 2 3 ... n) 2
4
SPPU : Dec.-12, May-18, Marks 4
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
1. Basis of induction :
For n = 1, L.H.S. = 1,
1 ( 1 1) 2
R.H.S. = =1
4
L.H.S. = R.H.S.
k 2 (k 1) 2
i.e. 1 3 2 3 3 3 ... + k 3 = … (1)
4
Then we have
(1 3 2 3 3 3 ... + k 3 ) (k 1) 3 = (1 2 3 ... k) 2 (k 1) 3 (Using 1)
2
k (k 1)
= (k 1) 3
2
k2
= (k 1) 2 k 1
4
k 2 + 4k 4
= (k 1) 2
4
(k 1) 2 (k 2) 2
=
4
2
(k 1)(k 2) (k +1) 2 (k 2) 2
= =
2 4
Example 3.3.5 12 22 n2 n (n 1)
Show that ...
1 3 3 5 (2n 1) (2n 1) 2(2n 1)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
L.H.S. = R.H.S.
12 22 k2 k (k 1)
i.e. ... = ... (1)
1 3 3 5 (2k 1) (2k + 1) 2 (2k 1)
Then we have,
12 22 k2 (k 1) 2
...
1 3 3 5 (2k 1) (2k 1) [2 (k 1) 1][2 (k 1) 1]
k (k 1) (k 1) 2
= ... (Using 1)
2 (2k 1) (2k 1) (2k 3)
(k 1) k (2k 3) 2 (k 1)
=
(2k 1) 2 (2k 3)
(k 1) 2k 2 5k 2
=
2k 1 2 (2k 3)
(k 1) 2k 2 4k k 2
=
(2k 1) 2 (2k 3)
(k 1) 2k (k 2) 1 (k 2)
=
(2k 1) 2 (2k 3)
(k 1) (k 2)
=
2 (2k 3)
(k 1) [(k 1) 1]
=
2 [2(k 1) 1]
P(k + 1) is true.
Therefore by mathematical induction P(n) is true for all n 1.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
1 1 1 1 n
Example 3.3.6 Show that a) ...
1 2 2 3 3 4 n (n 1) n 1
1 1 1 1 n
b) Show that ...
1 3 3 5 5 7 ( 2n 1) ( 2n 1) 2n 1
1 1 1 1 n
c) Show that ...
1 4 4 7 7 10 ( 3n 1) ( 3n 1) 3n 1
SPPU : Dec.-05, Marks 6
Solution : Let P(n) be the given statement,
a) 1. Basis of induction :
1 1
For n = 1 L.H.S. = =
1.2 2
1 1
R.H.S. = =
1+1 2
L.H.S. = R.H.S.
Then we have
1 1 1 1 1 k 1
... = ... (Using 1)
1 2 2 3 3 4 k (k 1) (k 1) (k 2) k 1 (k 1)(k 2)
k (k 2) 1
=
(k 1) (k 2)
k 2 2k 1
=
(k 1) (k 2)
(k 1) 2
=
(k 1) (k 2)
k 1 (k 1)
=
k 2 (k 1) 1
Hence assuming P(k) is true, P(k + 1) is also true. Therefore P(n) in true for all n 1.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
1 1 1 1 n
b) Let P(n) : ... =
1 3 3 5 5 7 (2 n 1)(2n 1) 2n 1
Then we have,
1 1 1 1
...
1 3 3 5 (2k 1)(2k 1) (2k 1)(2k 3)
k 1
=
2k 1 (2k 1)(2k 3)
2k 2 3k 1
=
(2k 1) (2k 3)
(2k 1) (k 1)
=
(2k 1)(2k 3)
k 1
=
2k 3
k 1
=
2(k 1) 1
Hence assuming P(k) is true. P(k + 1) is also true. Therefore P(n) is true for all n 1.
1 1 1 1 n
c) Let P(n) : ... =
1 4 4 7 7 10 (3n 2)(3n 1) 3n 1
1. Basis of induction
1 1 1
For n = 1, L.H.S. = = , R.H.S. =
1.4 4 4
1 1
=
1.4 3.1+1
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
L.H.S. = R.H.S.
Then we have,
1 1 1 1
+ ... ... (Using 1)
1 4 4 7 (3k 2)(3k 1) (3k 1) (3k 4)
k 1
=
(3k 1) (3k 1)(3k 4)
3k 2 4k 1
=
(3k 1) (3k 4)
(3k 1) (k 1)
=
(3k 1)(3(k 1) + 1)
k 1
=
3(k 1) + 1
Hence assuming P(k) is true. P(k + 1) is also true. Therefore P(n) is true for all n 1.
Example 3.3.7 1 – a n 1
Prove by induction for n 0. 1 a a 2 ... a n .
1– a
SPPU : Dec.-10, Marks 4
Solution : Let P(n) be the given statement,
1. Basis of induction
1– a
For n = 0, L.H.S. = 1, R.H.S. = =1
1– a
1– a 2
For n = 1, L.H.S. = 1 + a, R.H.S. = =1+a
1– a
For n = 0, 1, L.H.S. = R.H.S.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Consider,
1 – a k+1
1 a + a 2 .... a k a k+1 = a k+1 … (Using 1)
1– a
1 – a k+1 (1 – a) a k+1
=
1– a
1– a k+1 a k+1 – a k+2
=
1– a
1– a k+2
=
1– a
Example 3.3.8 Use mathematical induction to show that n ( n 2 – 1) is divisible by 24. Where n
is any odd positive number. SPPU : Dec.-14, Marks 4
Solution : If n (n 2 –1) = n3 – n is divisible by 24.
For n = 3, n n 2 1 = 24 which is divisible by 24.
P(1) and P(3) is true.
2. Induction step :
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
= 24 ( m 0 m 1 )
= 24 m 2 (Q m 0 m 1 m 2 )
P(k + 1) is true.
By mathematical induction P(n) is true for all n odd positive number.
Example 3.3.9 Show that n 4 4 n 2 is divisible by 3 for all n 2. SPPU : Dec.-15, Marks 4
For n = 2
2 4 4 ( 2 2 ) = 16 – 16
= 0 is divisible by 3 as 0 is divisible by every number
P(2) is true.
k 4 4 k 2 is divisible by 3.
k 3 2k is divisible by 3
Also 6 k 2 12 k 3 = 3 (2k 2 4k 1) is divisible by 3.
Hence (k 1) 4 4 (k + 1) 2 is divisible by 3.
Hence assuming P(k) is true.
P(k + 1) in also true. Therefore P(n) is true for n 2.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
1. Basis of induction
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
k(k 1)
= ( 1) k 1 ( 1) k (k 1) 2
2
k
= ( 1) k (k 1) (k 1)
2
k 2k 2
= ( 1) k (k 1)
2
(k 1)(k 2)
= ( 1) k
2
Hence assuming P(k) is true, P(k + 1) is also true. Therefore P(n) in true for all n 1.
1. Basis of induction
Example 3.3.13 Prove that for any positive integer n the number n 5 – n is divisible by 5.
SPPU : Dec.-08, Marks 6
Solution : Let P(n) be the given statement,
1. Basis of induction :
For n = 1, 15 1 = 0 is divisible by 5.
As 0 is divisible by every number.
Hence P(1) is true.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
k5 k is divisible by 5.
and 5 (k 4 2k 3 2k 2 k) is divisible by 5.
Hence (k 1) 5 (k 1) is divisible by 5.
Hence assuming P(k) is true. P(k + 1) is also true. Therefore P(n) is true for n 1.
1. Basis of induction :
For n = 1 81 31 = 5
= 5 1
Obviously a multiple of 5.
P(1) is true.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 3.3.15 Show that the sum of the cubes of three consecutive natural number is
divisible by 9. SPPU : Dec.-06, Marks 6
Solution : Let n, n + 1, n + 2 be three consecutive natural numbers.
1 3 2 3 3 3 = 1 + 8 + 27 = 36 which is divisible by 9.
P(1) is true.
Statement, We get
5 n +1 – 1
1 5 5 2 ....5 n = … (1)
5–1
Example 3.3.17 Let n be a positive integer. Show that any 2 n 2 n chessboard with one
square removed can be covered by L-shaped pieces, where each piece covers three squares at
a time.
Solution : Let P(n) be the proposition that any 2 n 2 n chessboard with one square
removed can be covered using L-shaped pieces.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Basis of induction : For n = 1, P(1) implies that any 2 2 chessboard with one square
removed can be covered using L shaped pieces. P(1) is true, as seen below.
Induction step : Assume that, P(k) is true i.e. any 2 k 2 k chessboard with one square
removed can be covered using L-shaped pieces.
Then, we have to show that P(k + 1) is true. For this consider, a 2 k 1 2 k 1
chesshoard with one square removed. Divide the chessboard into four equal halves of
size 2 k 2 k , as shown below.
k k
2 2
C1
k C2 k
2 2
k C3 C4 k
2 2
k k
2 2
The square which has been removed, would have been removed from one of the four
chessboards, say C 1 . Then by induction hypothesis, C 1 can be covered using L-shaped
pieces. Now, from each of the remaining chessboards, remove that particular piece (or
tile), lying at the centre of the large chessboards.
k k
2 2
C2 C1
k k
2 2
k k
2 C3 C4 2
k k
2 2
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Then by induction hypothesis, each of these 2 k 2 k chessboards with a piece (or tile)
removed can be covered by the L-shaped pieces. Also the three tiles removed from the
centre can be covered by one L-shaped piece. Hence the chessboard of 2 k 1 2 k 1 can
be covered by L-shaped pieces.
Hence proved.
Example 3.3.18 Suppose we have unlimited stamps of two different denominations, 3 rupees
and 5 rupees. We want to show that it is possible to make up exactly any postage of 8
rupees or more using stamps of these two denominations.
Solution : For k = 8, we have one 5 rupees stamp and one 3 rupees stamp.
For k = 9, replace 5 rupees stamp by two 3 rupees stamp, similarly for k = 10,
replace all 3, 3 rupees stamps by, two 5 rupees stamp an so on.
Hence let us assume that, it is possible to make up k rupees stamp using 3 rupees
and 5 rupees stamps (for k 8).
Now we have to show that it is also possible to make up (k + 1) rupees stamps using
3 rupees and 5 rupees stamps.
We examine two cases :
1) Suppose we make up stamps of k rupees using at least one 5 rupees stamp.
Replacing a 5 rupees stamp by two 3 rupees stamp, we can make up k + 1
rupees stamps.
2) Suppose we make up a stamp of k rupees using 3 rupees only. Since k 8 we
must have at least 3, 3 rupees stamps. Replacing these 3, 3 rupees stamps by two
five rupees stamps. We can make up stamps of k + 1 rupees.
Hence proved.
Example 3.3.19 The king summoned the best mathematicians in the kingdom to the palace to
find out how smart they were. The king told them
"I have placed white hats on some of you and black hats on the others. You may look at,
but not talk, to, one another. I will leave now and will come back every hour on the hour.
Every time I return, I want those of you who have determined that you are wearing white
hats to come up and tell me immediately."
As it turned out, at the nth hour every one of the n mathematician who were given white
hats informed the king that she knew that she was wearing a white hat. Why ?
Solution :
1. Basis of induction : For n = 1, there is only one mathematician wearing a white
hat. Since the king said that white hats were placed on some one of the mathematician
(king never lie). The mathematician who saw that all other mathematicians had on black
hats would realize immediately that she was wearing a white hat. Consequently she
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
would inform the king on the first hour. (when the king returned for the first time) that
she was wearing a white hat.
Now let n = 2, i.e. two mathematicians wearing white hats.
Consider, one of these two mathematicians. She saw that one of her colleagues was
wearing a white hat. She reasoned that if she were wearing a black hat, her colleague
would be the only one wearing a white hat. In that case, her colleague would have
figured out the situation and informed the king on the first hour. That did not happen
shows that she was also wearing a white hat. Conesquently she told the king on the
second hour (and so did the other mathematician with a white hat, since all the
mathematicians are smart).
2. Induction step : Assume that, if there were k mathematicians wearing white hats,
then they would have figured out that they were wearing white hats and informed the
king so on the k th hour. Now, suppose that there were k + 1 mathematicians wearing
white hats.
Every mathematician wearing a white hat saw that k of her colleagues were wearing
white hats. However, that her k colleagures did not inform the king of their findings on
the k th hour can only imply that there were more then k. People wearing white hats.
Consequently she knew that, she must be wearing a white hat also on the (k 1) th hour.
She (together with all other mathematicians wearing white hats) would inform the king
their conclusion.
qqq
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Unit - II
4 Relations
Syllabus
Relations and their Properties, n-ary relations and their applications, Representing relations,
Closures of relations, Equivalence relations, Partial orderings, Partitions, Hasse diagram,
Lattices, Chains and Anti-Chains, Transitive closure and Warshall‘s algorithm.
Contents
4.1 Introduction
4.2 Cartesian Product
4.3 Relation
4.4 Matrix Representation of a Relation
4.5 Diagraphs
4.6 Special Types of Relations
4.7 Types of Relations on Set . . . . . . . . . . . . . . . . Dec.-10, 11, 12, 14, 18, 19,
. . . . . . . . . . . . . . . . . . May-14, 17, 18, 19, · · · · · · · Marks 6
4.8 Partitions of a Set . . . . . . . . . . . . . . . . . . Dec.-11, 12, May-17, · · · · · · Marks 3
4.9 Closure of a Relation . . . . . . . . . . . . . . . . . . Dec.-05, 07, 12, 13, 14, 15, 16
. . . . . . . . . . . . . . . . . . May-06, 07, 08, 15, 18, · · · · Marks 6
4.10 Partially Ordered Set . . . . . . . . . . . . . . . . . . Dec.-06
4.11 Principle of Duality . . . . . . . . . . . . . . . . . . Dec.-10, 11, 13, 14, 15, 16,
. . . . . . . . . . . . . . . . . . May-14, 15, 19 · · · · · · · · · · Marks 6
(4 - 1)
TM
4.1 Introduction
In the chapter 1, we dealt with sets, elements, different types and general properties
of sets. There may exists various relationships among elements of sets. We will study
relations and functions with various properties and examples.
Relation may involves equality or inequality of elements. In mathematics the
expressions like '' is equal to " is similar to ", " is greater than", "is parallel to " are some
relations.
Þ x Î B and y ÎC
Þ (x, y) Î B ´ C
Hence A ´ C Í B ´ C
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
i) A ´ (B Ç C) = (A ´ B) Ç ( A ´ C)
ii) (A Ç B) ´ C = (A ´ C) Ç (B ´ C)
iii) A ´ (BÈ C) = (A ´ B ) È (A ´ C)
iv) (A È B) ´ C = (A ´ C) È (B ´ C)
Proof :
i) A ´ (B Ç C) = {(x, y) / x Î A and (y Î B Ç C) }
= {(x, y) / x Î A and / (y Ï B and y Î C)}
= {(x, y) / x Î A, y Î B and y Î A, y ÎC}
= {(x, y) / (x, y) Î A ´ B and (x, y) Î A ´ C}
= {(x, y) / (x, y) Î (A ´ B) Ç (A ´ C)}
A ´ (B Ç C) = (A ´ B) Ç (A ´ C)
4.3 Relation
Let A and B be two non empty sets. A relation from A to B is any subset of A ´ B. It
is denoted by R : A ® B
e.g. Let A = {x,y,z), B = {1, 2, 3)
then A´B = {(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2) (z, 3)}
R 1 = {(x,1), (y, 2), (z,1), )}, R 2 = {(z, 3)}, R 3 = { f }
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
The range of R is the set of all second co-ordinates of the ordered pairs (a,b) Î R.
It is denoted by R (R) = {(b/(a, b) Î R}.
5) The null set is the subset of A ´ B .
\ f is a relation called null relation or empty relation.
Example :
Let A = {1, 2, 3}, B = {x, y}
then R 1 = {1, x) (1, y), (3, x)} is a relation from A to B
\ D (R 1 ) = {1,3}
R (R 1 ) = {x, y}
Example 4.4.1 Let A = {1, 2, 3, 4} and R = {(x, y)/ x < y } then find M R .
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.4.3 A = {x, y, z} Find the relation matrices of the following relations.
i) R 1 = {(x, x) (y, y) (z, z)} ii) R 2 = {(x, y) (y, x), (y, z), (z, y)} iii) R 3 = {(x, x)
(x, y), (x, z) (y, x) (y, y) (y, z), (z, x) (z, y) (z, z)
Solution : (5,5) (6,6)
x y z
1 0 0ù
i) M R1 = é
ê0 1 0ú
ê ú
êë0 0 1úû 3 ´ 3
x y z
0 1 0ù
ii) M R2 = é
ê1 0 1ú
ê ú
êë0 1 0úû
é1 1 1ù
iii) M R3 = ê1 1 1ú
ê ú
êë1 1 1úû
We know that relation matrix is a boolean matrix as all entries are either 0 or 1
I) Let A = [ a ij ] m ´ n , B = [b ij ] m ´ n be two relation matrices then
A + B = [ a ij + b ij ] = [c ij ] m ´ n
where c ij = 1 if a ij = 1, or b ij = 1
= 0 if a ij = 0, and b ij = 0
é1 1 1ù
then A + B = ê 0 1 1ú
ê ú
êë1 1 0úû
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
é1 1 1ù
and A B = ê1 1 1ú
ê ú
êë1 1 1úû
a b
iii) If aRa then the vertex a is joined to itself by a loop around a. e.g. if aRa then
1) aRa 2) aRb
a b
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
a b
a b c
c
Examples :
Example 4.5.1 A = {1,2,3,4,5,6} and a R b iff a/b (a divides b). Draw diagraph of R.
Solution : We have
(1,1) ( 2, 2) ( 3, 3) ( 4 , 4) ( 5, 5) ( 6, 6)ü
ï
R = (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) ý
ï ( 2, 4) ( 2, 6) ( 3, 6) ï
î þ
The diagraph of R is as follows :
1
2
6
3
5 4
Fig. 4.5.1
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.5.2 é1 0 0 1ù
ê0 1 0 1ú
Let A = {a, b, c, d} and M R =ê ú Draw diagraph of R.
ê1 1 0 0ú
ê1 0 0 0úû
ë
Solution : We have
R = {(a,a) (a,d) (b,b) b,d) (c,a) (c,b) (d,a)}
The digraph of R is as follows :
a b
d c
Fig. 4.5.2
Fig. 4.5.3
R = {(1, 1) (1, 3) (3, 1) (2, 3) (3, 2), (2, 4) (4, 2) (4, 4) (3, 4) (4, 3)}
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
i.e. if x R y then yR –1 x
It is also denoted by R c
It is also known as the converse relation.
Example :
1) If R = {(1,2) (2,3) (3,1) (4,5) } then R –1 or R c = {(2,1) (3,2) (1,3) (5,4)}
é1 0 1 1ù é1 1 0 0ù
ê1 0 1 1 ú ê0 0 0 0ú
2) If M R =ê ú then M –1 = ê ú = [M R ] t
ê0 0 1 1ú R ê1 1 1 0ú
ê0 0 0 1úû ê1 1 1 1úû
ë ë
3) If the diagraph R is given by
\ R = {(1,1) (1,2) (2,3) (4,2) (4,1) (4,3) (3,4) }
1 2
4 3
Fig. 4.6.1
then the diagraph of R –1 is obtained by changing the direction of arrow only which
is given below.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
1 2
4 3
Fig. 4.6.2
Theorem 1 : If R, R 1 , R 2 are relations from A to B then
i) (R –1 ) –1 = R
ii) (R 1 È R 2 ) -1 = R –1
2
È R 1–1 = R 1–1 È R –1
2
iii) ( R 1 Ç R 2 ) -1 = R 1–1 Ç R –1
2
Examples :
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.6.2 If A = {a, b, c, d} and R = {(a, b) (c,d) (c,c) (d,a) (a,a) (b,b) (d,d) } is a relation
on A. Draw diagraph of R .
Solution :
R = {(a, c) (a, d) (b, a) (b, c) (b, d) (c, a) (c, b) (d, b) (d, c)}
The diagraph of R is as follows :
a b
d c
Fig. 4.6.3
Example 4.6.3 é1 0 1ù
Obtain the matrix of R if M R = ê 0 0 1ú
ê ú
êë1 1 0úû
Solution : The matrix of R is obtained from M R be replacing 0 and 1 by 1 and 0
respectively
é0 1 0ù
M R = ê1 1 0ú
ê ú
êë 0 0 1úû
Note : 1) (R 1 È R 2 ) = R 1 Ç R 2
2) (R 1 Ç R 2 ) = R 1 È R 2
In R 1 In R 2 R1 × R2
1) (x, y) (y, x) (x, x)
(y, y) (x, y)
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fig. 4.6.4
Example 4.6.5 Let A = (1, 2, 3, 4). Let R 1 = {(x, y)/ x+y = 5} and R 2 = (x, y) / (y – x) = 1}
verify ( R 1 × R 2 ) C = R C
2
× R 1C
Solution : We have A = {1, 2, 3, 4}
RC
2
= {(2,1), (3,2) (4,3)}
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
The diagraph of the identity relation is the graph with loops only and it's relation
matrix is the diagonal matrix with 0 and 1.
Notes :
1) If R is a reflexive relation on set A then
i) The relation matrix (M R ) is the identity matrix.
ii) Diagraph of reflexive relation will have loop for every element of A.
2) The relation matrix of irreflexive relation has all diagonal elements zero. It's
diagraph is free from loops.
Examples
Example 1 :
Let A = {1,2, 3,4}. Then
i) R1 = {(1, 1) (2, 2) (3, 3) (4, 4)} is the reflexive relation. It is known as the smallest
reflexive relation on set A.
ii) R 2 = {(1, 1) (2, 2) (3, 3) (4, 4) (2, 4) (1, 2) (3, 2)} is reflexive relation.
iii) R 3 = { (1, 1) (2, 2) (3, 4)} is not reflexive relation as 3 Î A but 3 R 33 .
/ 4 a.
iv) R 4 = {(2, 3) (3, 4)} is irreflexive relation A as " a Î A, a R
Example 2 :
Let A = Set of all straight lines in a plane. x R y iff x is parallel to y.
For any line x Î A, x is parallel to x.
\ x Rx " x Î A
\ R is a reflexive relation.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
ii) R 2 = {(1, 1) (2, 2) (3, 3) (4, 4)} is a symmetric as well as reflexive relation.
iii) R 3 = { (1, 1) (2, 2) (3, 3) (4, 4) (3, 4)} is reflexive but not symmetric relation.
Example 4.7.1 Let A = Set of all straight lines in a plane. x R y iff x || y i.e. x is parallel
to y. S. T. R is a symmetric relation.
Solution : R = {x R y | x is parallel to y}
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Let R be a relation on set A. R is said to be transitive relation if aRb and bRc, then
aRc for a,b,c, in R.
\ A relation R is not transitive if $ a, b and c in A.
/
Such that aRb, bRc but aRc
Examples :
Then R is transitive as a £ b, b £ c Þ a £ c
2) If A = {x, y, z w} then,
i) R 1 = {(x, y) (y, z)} is not transitive relation as x Ry, y Rz but x R/ z.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.7.3 If A = {x, y, z } and R = {(x, x) (y, y) (z, z)}. It is an equivalence relation ?
R 1 Ç R 2 is an equivalence relation.
2) If R 1 and R 2 are equivalence relations on a set A, then it is not necessary that
R 1 È R 2 is an equivalence relation.
Let A = {a, b, c)
And R 1 = {(a, a) (b, b) (c, c) (a, b) (b, a)}
R 2 = { (a, a) (b, b) (c, c) (a, c) (c, a)} are equivalence relation.
R 1 È R 2 = {(a, a) (b, b) (c, c) (a, b) (b, a) (a, c) (c, a)}
(b, a) and (a, c) Î R 1 È R 2 but (b, c) Ï R 1 È R 2 .
Example 1 :
Let A = {x, y, z }
R = A ´ A = {(x, x) (y, y) (z, z) (x, y) (x, z) (y, z) (y, x) (z, x) (z, y)}
is an equivalence relation.
\ The equivalence class of x is
[x] R = {x, y, z} = [y] R = [z] R
\ x Rx Þ R is reflexive relation.
Suppose x Ry Þ x + y = even
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Þ y + x = even
Þ yRx
\ R is symmetric relation.
Suppose xRy and yRz Þ x + y = even, y + z = even
Þ x + y + y + z = even
Þ x + z = even – 2y = even
Þ x + z = even
Þ xRz
\ R is a transitive relation.
\ R is an equivalence relation.
\ The equivalence class of 1 Î z is
[1] R = {xR 1 / x +1 = even}
= {xR 1 / x = even –1= odd}
= {xR 1 / x is odd}
[1] R = Set of all odd integers = {… –3, –1, 1, 3, 5, …}
[ 2] R = {xR 2 |x +2 = even}
= {xR 2| x = even}
= Set of all even integers
[ 2] R = {… – 4, – 2, 0, 2, 4 …]
Theorem 3 : A = U [a]
a ÎA
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
iv) Diagraph
2
1
9
Example 4.7.7 If R is a relation from A to B where A = {1, 2, 8}, B = {1, 2, 3, 5} and aRb
iff a < b. Find : a) R in Roster form b) Domain and Range c) Diagraph.
SPPU : May-18, Marks 4
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
1 2
5 3
Example 4.7.8 If R is a relation on set A = {1, 2, 3, 4, 5}, R = {(1, 1) (1, 2) (2, 1) (3, 1)
(4, 1) (5, 2)}. Find domain set, codomain set, range. Draw its diagraph and find relation
matrix.
Solution : Given that A = {1, 2, 3, 4, 5}
1
2
3
5
4
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.7.9 Let A = {1, 2, 3, 4, 5} and aRb if a < b. Find i) R in Roster form ii) Domain
and Range of R iii) Diagraph of R. SPPU : Dec.-19, Marks 3
Solution : We have
A = {1, 2, 3, 4, 5}
i) By considering the given conditions,
R in Roster form is
R = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 3) (2, 4), (2, 5) (3, 4) (3, 5) (4, 5)}
ii) Domain of R is = {1, 2, 3, 4}
Range of R is = {2, 3, 4, 5}
iii) The vertex set of R is {1, 2, 3, 4, 5}
It's diagraph is as follows :
5
1
2 3
R = {(1, 1), (2, 1), (2, 2), (3, 1), (3, 3), (4, 1), (4, 2), (4, 4), (5, 1), (5, 5),
(6, 1), (6, 2), (6, 3), (6, 6)}
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
2
1
3
6
4
5
(iv) The indegree of a vertex in diagraph is the number of edges coming towards that
vertex. The outdegree of a vertex is defined as the number of edges going out from a
vertex. Consider the following table.
2 3 2 5
3 2 2 4
4 3 1 4
5 2 1 3
6 4 1 5
Example 4.7.12 Let A = {1, 2, 3, 4, 6} and let R be defined on A as xRy iff x | y (i.e. x
divides y)
(i) Write R as a set of ordered pairs
(ii) Find R -1 and describe R -1 in words
Solution : Given that,
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
and R = {(1, 1), (1, 2), (1, 3), (2, 3), (3, 3)}
In R, (1, 1), (1, 2) Î R Þ (1, 2) Î R
(1, 1), (1, 3) Î R Þ (1, 3) Î R
(1, 2), (2, 3) Î R Þ (1, 3) Î R
(1, 3), (3, 3) Î R Þ (1, 3) Î R
(2, 3), (3, 3) Î R Þ (2, 3) Î R
Hence for any (a, b), (b, c) Î R Þ (a, c) Î R
Thus R is a transitive relation on A.
Example 4.7.15 Let A = {Set of all lines in a plane} and x, y Î A. Define xRy iff x is
perpendicular to y. Is R transitive, reflexive and symmetric ?
Solution : Given that xRy iff x perpendicular y.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.7.16 Let A = {set of lines in a plane} and x, y Î A. xRy iff x is parallel to y. Is R
equivalence relation ? Find the equivalence class of any line 'L'.
Solution :
(i) We know that every line is parallel to itself.
\ xRx , " x Î A
Þ R is reflexive relation.
(ii) Suppose xRy
Þ x is parallel to y.
Þ y is parallel to x.
Þ yRx Þ R is symmetric relation.
(iii) Suppose xRy and yRz.
Þ x is parallel to y and y is parallel to z.
Þ x is parallel to z.
Þ xRz Þ R is transitive relation.
Thus R is an equivalence relation.
Let L be any line in A.
Equivalence class of L = [L] = {xRL | x is parallel to L}
[L] = {x|x is parallel to L}
= Set of all lines which are parallel to L.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.7.17 é1 0 0ù
Let A = {a, b, c} and M (R) = ê 0 1 1ú .
ê ú
êë 0 1 1úû
Determine whether R is an equivalence relation ? Find the equivalence class of b in A.
Solution : From relation matrix, the relation R is
Example 4.7.18 If R = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5) (3, 5), (5, 3), (1, 3), (3, 1)}
is an equivalence relation on X = {1, 2, 3, 4, 5}. Find equivalence
classes. SPPU : May-19, Marks 3
Solution : If R is an equivalence relation on X and a Î X then [a] = a = {x|x~ a }.
Example 4.7.19 Let A be the set of integers and let R be defined as xRy iff x £ y. Is R
equivalence relation ?
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
a+f = b+e
(a, b) ~ (e, f)
~ is a transitive relation.
Example 4.7.22 Prove that in the set N × N, the relation R defined by (a, b) R (c, d) iff
ad = bc is an equivalence relation.
Solution : We know that relation R is an equivalence relation if R is reflexive, symmetric
and transitive.
(i) We have, ab = ba
(a, b) R (a, b)
R is reflexive relation.
(ii) Suppose (a, b) R (c, d)
ad = bc
bc = ad
cb = da
(c, d) R (a, b)
R is symmetric relation.
(iii) Let (a, b) R (c, d) and (c, d) R (e, f)
ad = bc and cf = ed
adcf = bced
af = be (a, b) R (e, f)
R is transitive relation.
Thus, R is an equivalence relation.
Example 4.7.23 Let A = R × R (R is set of real numbers) and define the following relation on
A. (a, b) R (c, d) iff a 2 b 2 = c 2 d 2
(i) Show that (A, R) is an equivalence relation.
(ii) Find equivalence class of (3, 2)
Solution : Given that (a, b) R (c, d) iff a 2 b 2 = c 2 d 2
R is a reflexive relation.
(b) If (a, b) R (c, d) then a 2 b 2 = c 2 d 2
c 2 d2 = a 2 b 2
(c, d) R (a, b)
R is symmetric relation.
(c) Suppose (a, b) R (c, d) and (c, d) R (e, f)
a 2 b 2 = c 2 d 2 and c 2 d 2 = e2 + f2
a 2 b 2 = e2 f 2
(a, b) R (e, f)
R is transitive relation.
Thus, R is an equivalence relation.
(ii) An equivalence class of (3, 2) is the set of elements of A which are equivalent to
(3, 2)
[(3, 2)] = {(x, y) | (x, y) R (3, 2) ; x, y R}
= {(x, y) | x 2 y 2 = 9 + 4 = 13 ; x, y }
[(3, 2)] = The set of points on circle x 2 y 2 = 13.
R = {(a, b) R 2 | (a – b) 3}
Example 4.7.25 Let S be the set of points in a plane. Let R be a relation such that xRy iff y
is within two centimeter from x. Is R equivalence relation ?
Solution : Given that
Example 4.7.26 Let R be a relation on the set of positive integers such that
R = {(x, y)|x – y is an odd positive integer}
Is R reflexive, symmetric, transitive, antisymmetric, an equivalence relation ?
(y, x) R
x–y+y–z = p+q
x y and y x
x = y
R is antisymmetric relation.
Example 4.7.27 Show that R = {(a, b) / a b (mod m)} is an equivalence relation on z. Show
that x 1 y 1 and x 2 y 2 then x 1 + x 2 y 1 + y 2
Solution : Given that
a – b = mk , k z
a – b + b – c = mk1 + mk2
a – c = m(k1 + k2) = mk
m|(a - c) a c (mod m)
(a, c) R
R is transitive relation.
R is reflexive, symmetric and transitive.
Thus R is an equivalence relation,
Now, x1 y1 x1 y1 (mod m)
x2 y2 x2 y2 (mod m)
Example 4.7.28 For each of these relations on set A = {1, 2, 3, 4} decide whether it is
reflexive,
symmetric, transitive or antisymmetric.
R1 = {(1, 1) (2, 2) (3, 3) (4, 4)}
R 2 = {(1,1)(1, 2) (2, 2) (2,1) (3, 3) (4, 4)}, R 3 = {(1, 3) (1, 4) (2, 3) (2, 4) (3, 1) (3,4,)}.
SPPU : Dec.-10
Solution : i) For R 1 :
As a A, (a, a) R 1
R 1 is Reflexive, symmetric relation.
(a, b) and (b, c) R 1 R 1 is transitive relation.
(a, b) and (b, a) R 1 R 1 is antisymmetric relation.
R 1 reflexive, symmetric, transitive and anti-symmetric relation.
ii) For R 2 :
As a A (a, a) R 2 and aR 2 b bR 1 a, for a,b A
R 2 reflexive and symmetric relation.
For any aR2b and bR2C aR2C
R2 is transitive realtion
R2 is an equivalence relation
But (1, 2) and (2, 1) R2 and 1 2
R2 is not antisymmetric relation.
iii) For R 3 :
As 2 R 3 but (2, 2) R3
R 3 is not reflexive relation.
As (1, 4) R 3 but (4, 1) R3
R 3 is not symmetric relation.
As (2, 3) and (3, 1) R 3 but (2, 1) R 3.
R 3 is not transitive relation.
As (1, 3) and (3, 1) R3 but 1 3.
R3 is not transitive relation
As (1, 3) and (3, 1) R 3 but 1 3
R3 is not antisymmetric relation
1 7 3
4
2 5
Fig. 4.7.2
Let P be the partition of a non empty set A. We can define a relation R on a set A as
x Ry iff x and y belong to the same block of the partition P. This relation R is called
as the relation induced by the partition.
e.g. i) Let A = Z and P = {A1 , A2 }
where A1 = Set of even integers and
A 2 = Set of odd integers
P is a partition for A = Z
Define x Ry Iff x and y belong to the same partition of Z
i.e. x and y belong to either A1 or A 2
i.e. x and y are either even or odd
This relation is an equivalence relation.
Theorem 2 : Let A be any non empty set and let be a partition of A. Then induces
an equivalence relation on set A.
Example 4.8.1 Let A = {x, y, z, u, v}, = {{x, y}, {z}, {u, v}}. Find the equivalence relation
induced by .
Solution :
We know that equivalence classes form a partition for the corresponding set.
P1 = {1, 2, 3} and P2 = {4} are two equivalence classes.
In each equivalence class, every element is related to all elements of that class.
Due to P1 = (1, 1) (1, 2), (1, 3), (2, 2), (2, 3), (2, 1), (3, 3), (3, 1), (3, 2) and for P2 , (4, 4)
Hence R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4)}
is an equivalence relation with respect to the given partition P.
Example 4.8.3 Let A = {1, 2, 3, 4}, = {{1}, {2, 3}, {4}}. Find the equivalence relation
induced by .
Solution : Given that
Example 4.8.4 Define partition of a set. Let x = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Determine whether
or not each of the following is a partition of x :
A = {{2, 4, 5, 8}, {1, 9}, {3, 6, 7}}
B = {{1, 3, 6}, {2, 8}, {5, 7, 9}} SPPU : Dec.-11
Solution : Please refer section 4.8 for definition.
i) For set A :
The set A has 3 blocks,
A1 = {2, 4, 5, 8}, A 2 = {1, 9} A 3 = {3, 6, 7}
· The union of all these blocks is a set X
A1 A2 A3 = X
As B1 B2 B3 X,
S = {1, 2, 3, 4, 5, 6, 7, 8, 9}
i) A is not a partition of S because S is not the union of all blocks of A.
i.e. S A1 A2 A3
ii) B is the partition of S as B1 B2 B3 = S and B1 , B2 , B3 are mutually disjoints.
iii) As blocks of set C are not disjoints. The set C is not a partition of S.
iv) D = {{s}} is a partition of S, called as trivial partition.
Depending upon the nature of relations, there are mainly three types of closures of
relations.
Example 4.9.1 Let A = {1, 2, 3}. R 1 , R 2 and R 3 are relations on set A. Find the reflexive
closures of R 1 , R 2 and R 3 .
Where R 1 = {(1, 1) (2, 1)}, R 2 = {(1, 1) (2, 2), (3, 3)},
R 3 = {(3, 1) (1, 3), (2, 3)}.
Solution :
We have A = {1, 2, 3} = {(1, 1), (2, 2), (3, 3)}
Then
i) The reflexive closure of R 1 is R = R 1
R = {(1, 1) (2, 2) (3, 3) (2, 1)}
Example 4.9.2 Find the symmetric closure of the following relations. On A = {1, 2, 3}.
We have A = {1, 2, 3}
i) R 1–1 = {(1, 1) (1, 2)}
R = R 1 R 1–1 = {(1, 1) (1, 2) (2, 1)} is the symmetric closure
of R 1
ii) R –1
2
= {(2, 1) (1, 2) (2, 3) (2, 2)}
R = R 2 R –1
2
= {(1, 2) (2, 1) (3, 2) (2, 3) (2, 2)} is the
symmetric closure of R 2
iii) R 3 is the symmetric relation.
Let R be a relation on a set A which is not transitive relation. The transitive closure
of a relation R is the smallest transitive relation containing R. It is denoted by R .
The following theorem gives a procedure to find the transitive closure of a given
relation.
Theorem : Let A be any non empty set and |A| = n. Let R be a relation on A. Then
the transitive closure of R is R = R R 2 R 3 ... R n .
Example 4.9.3 If A = {1, 2, 3, 4, 5} and R = {(1, 2), (3, 4), (4, 5), (4, 1), (1, 1)}. Find it's
transitive closure.
Solution : Let R be the transitive closure of given relation R.
R = R R2 R3 R4 R5
Now R 2 = R R = {(3, 5) (3, 1) (4, 2) (4, 1) (1, 2) (1, 1)}
R 3 = R R 2 = {(3, 2) (3, 1) (4, 2) (4, 1) (1, 1) (1, 2)}
R 4 = R R 3 = {(3, 1) (3, 2) (4, 1) (4, 2) (1, 1) (1, 2)} = R 3
R 5 = R R 4 = {(3, 1) (3, 2) (4, 1) (4, 2) (1, 1) (1, 2)} = R 4 = R 3
R = {(1, 2) (3, 4) (4, 5) (4, 1) (1, 1) (3, 5) (3, 1) (4, 2) (3, 2)}
Step 3 : Stop the procedure when Wn is obtained and it is the required transitive
closure of R.
Examples
R = {(1, 3), (3, 1), (2, 4), (4, 2), (4, 6), (6, 4), (3, 5), (5, 3)}
1 2 3 4 5 6
1 0 0 1 0 0 0
2 0 0 0 0 1 0
3 1 0 0 0 1 0
W0 = MR =
4 0 1 0 0 0 1
5 0 0 1 0 0 0
6 0 0 0 1 0 0
Step 2 : To find W1 :
0 0 1 0 0 0
0 0 0 1 0 0
1 0 1 0 1 0
W1 =
0 1 0 0 0 1
0 0 1 0 0 0
0 0 0 1 0 0
Step 3 : To find W2 :
To find W2 from W1 , we consider the second column C 2 and second row R 2 .
In C 2 , 1 is present at R 4
In R 2 , 1 is present at C 4
Thus add new entry in W2 at (R 4 , C 4 ), which is given below
0 0 1 0 0 0
0 0 0 1 0 0
1 0 1 0 1 0
W2 =
0 1 0 1 0 1
0 0 1 0 0 0
0 0 0 1 0 0
Step 4 : To find W3 :
To find W3 from W2 , we consider the third column and third row.
In C 3 , 1 is present at R 1 , R 3 , R 5
In R 3 , 1 is present at C1 , C 3 , C 5
Thus add new entries in W3 at ( R 1 , C1 ), ( R 1 , C 3 ), ( R 1 , C 5 )
( R 2 , C1 ), ( R 2 , C 3 ), ( R 2 , C 5 ) ( R 3 , C1 ), ( R 3 , C 3 ), ( R 3 , C 5 ) which is given below
1 0 1 0 1 0
0 0 0 1 0 0
1 0 1 0 1 0
W3 =
0 1 0 1 0 1
1 0 1 0 1 0
0 0 0 1 0 0
Step 5 : To find W4 :
To find W4 from W3 , we consider the fourth column and fourth row.
In C 4 , 1 is present at R 2 , R 4 , R 6
In R 4 , 1 is present at C 2 , C 4 , C 6
Thus add new entries in W4 at (R 2 , C 2 ), (R 2 , C 4 ), (R 2 , C 6 ), (R 4 , C 2 ), (R 4 , C 4 ),
(R 4 , C 6 ), (R 6 , C 2 ), (R 6 , C 4 ), (R 6 , C 6 ) which is given below
1 0 1 0 1 0
0 1 0 1 0 1
W4 = 1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
Step 6 : To find W5 :
To find W5 from W4 , we consider the 5 th column and 5 th row.
In C 5 , 1 is present at R 1 , R 3 , R 5
In R 5 , 1 is present at C1 , C 3 , C 5
Thus add new entries in W5 at (R 1 , C1 ), (R 1 , C 3 ), (R 1 , C 5 ), (R 3 , C1 ), (R 3 , C 3 ),
(R 3 , C 5 ), (R 5 , C1 ), (R 5 , C 3 ), (R 5 , C 5 ) which is given below
1 0 1 0 1 0
0 1 0 1 0 1
W5 = 1 0 1 0 1 0
= W4
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
Step 7 : To find W6 :
To find W6 from W5 we consider the 6 th column and 6 th row.
In C 6 , 1 is present at R 2 , R 4 , R 6
In R 6 , 1 is present at C 2 , C 4 , C 6
Thus add new entries in W6 at (R 2 , C 2 ), (R 2 , C 4 ), (R 2 , C 6 ), (R 4 , C 2 ), (R 4 , C 4 ),
(R 4 , C 6 ), (R 6 , C 2 ), (R 6 , C 4 ), (R 6 , C 6 ) which is given below
W6 = W5 = W4
Example 4.9.5 Let R = {(a, d), (b, a), (b, d), (c, b), (c, d), (d, c)}
Use Warshall's algorithm to find the matrix of transitive closure where A = {a, b, c, d}
SPPU : Dec.-15
Solution : Step 1 : We have
A = {a, b, c, d} |A| = 4
R = {(a, d) (b, a), (b, d) (c, b), (c, d), (d, c)}
a b c d
a 0 0 0 1
b 1 0 0 1
W0 = MR =
c 0 1 0 1
d 0 0 1 0
Step 2 : To find W1 :
To find W1 from Wo , we consider the first column and first row.
In C1 , 1 is present at R 2
In R 1 , 1 is present at C 4
Thus add new entry in W1 at (R 2 , C 4 )
0 0 0 1
1 0 0 1
W1 =
0 1 0 1
0 0 1 0
Step 3 : To find W2
To find W2 , from W1 , we consider the second column and second row.
In C 2 , 1 is present at R 3
In R 2 , 1 is present at C1 and C 4
Thus add new entries in W2 at (R 3 , C1 ), (R 3 , C 4 ) which is given below.
0 0 0 1
1 0 0 1
W2 =
1 1 0 1
0 0 1 0
Step 4 : To find W3 :
To find W3 from W2 , we consider the 3 rd column and 3 rd row.
In C 3 , 1 is present at R 4
In R 3 , 1 is present at C1 , C 2 , C 4
Thus add news entries in W3 at (R 4 , C 1 ), (R 4 , C 2 ), (R 4 , C 4 )
Which is given below
0 0 0 1
1 0 0 1
W3 =
1 1 0 1
1 1 1 1
Step 5 : To find W4 :
To find W4 from W3 , we consider the 4 th column and 4 th row.
In C 4 , 1 is present at R 1 , R 2 , R 3 , R 4
In R 4 , 1 is present at C1 , C 2 , C 3 , C 4
Thus we add new entries in W4 at (R1 , C1 ), (R1 , C2 ), (R1 , C3 ), (R1 , C4 ), (R 2 , C1 ),
(R 2 , C2 ), (R 2 , C3 ), (R 2 , C4 ), (R 4 , C3 ), (R 3 , C1 ), (R 3 , C2 ), (R 3 , C4 ), (R 4 , C1 ), (R 4 , C2 ),
(R 4 , C3 ), (R 4 , C4 )
Which is given below
1 1 1 1
1 1 1 1
W4 =
1 1 1 1
1 1 1 1
Hence W4 is the relation matrix of R .
(a, a), (a, b) (a, c) (a, d) (b, a) (b, b) (b, c) (b, d)
and R =
(c, a), (c, b) (c, c) (c, d) (d, a) (d, b) (d, c) (d, d)
1 2 3 4
1 0 1 1 1
2 1 0 1 0
W0 = MR =
3 0 1 0 1
4 0 1 1 0
Step 2 : To find W1 :
To find W1 from W0 , we consider the first column and first row.
In C1 , 1 is present at R 2
In R 1 , 1 is present at C 2 , C 3 , C 4
Thus add new entries in W1 at (R 2 , C2 ), (R 2 , C3 ), (R 2 , C4 ) which is given below
0 1 1 1
1 1 1 1
W1 =
0 1 0 1
0 1 1 0
Step 3 : To find W2 :
To find W2 from W1 , we consider the 2 nd column and 2 nd row.
In C 2 , 1 is present at R 1 , R 2 , R 3 , R 4
In R 2 , 1 is present at C1 , C 2 , C 3 , C 4
Thus we add new entries in W2 at (R1 , C1 ), (R1 , C2 ), (R1 , C3 ), (R1 , C4 ), (R 2 , C1 ),
(R 2 , C2 ), (R 2 , C3 ), (R 2 , C4 ), (R 3 , C1 ), (R 3 , C2 ), (R 3 , C2 ), (R 3 , C4 ), (R 4 , C1 ), (R 4 , C2 ),
(R 4 , C3 ), (R 4 , C4 )
Which is given below
1 1 1 1
1 1 1 1
W2 =
1 1 1 1
1 1 1 1
Example 4.9.7 If R = {(a, b), (b, a), (b, c), (c, d), (d, a)} be a relation on the set A = {a, b, c,
d}. Find the transitive closer of R using Warshall's algorithm. SPPU : Dec.-16, Marks 6
Solution :
Step 2 : To find W 1
To find W 1 from W 0 , we consider the first column and first row. In C 1 , 1 is present
R 2 and R 4
In R 1 , 1 is present at C 2
Thus add new entries in W 1 at (R 2 , C 2 ) (R 4 , C 2 )
0 1 0 0
W1 = 1 1 1 0
0 0 0 1
1 1 0 0
Step 3 : To find W 2
To find W 2 from W 1 , we consider second column and second row of W 1 .
In C 2 , 1 is present at R 1 , R 2 , R 3
In R 2 , 1 is present at C 1 , C 2 , C 3
Add new entries in W 2 at (R 1 , C 1 ), (R 1 , C 2 ), (R 1 , C 3 ) (R 2 , C 1 ), (R 2 , C 2 ), (R 2 , C 3 )
(R 3 , C 1 ), (R 3 , C 2 ), (R 3 , C 3 )
1 1 1 0
1 1 1 0
W2 = 1 1 1 1
1 1 0 0
Step 4 : To find W 3
To find W 3 from W 2 , we consider the III rd row and III rd column of W 2 .
In C 3 , 1 is present at R 1 , R 2 , R 3
In R 3 , 1 is present at C 1 , C 2 , C 3 , C 4
Add new entries in W 2 at (R 1 , C 1 ), (R 1 , C 2 ), (R 1 , C 3 ), (R 1 , C 4 ), (R 2 , C 1 ), (R 2 , C 2 ),
(R 3 , C 3 ), (R 2 , C 4 ), (R 3 , C 1 ), (R 3 , C 2 ), (R 3 , C 3 ), (R 3 , C 4 )
1 1 1 1
W3 = 1 1 1 1
1 1 1 1
1 1 0 0
Step 5 : To find W 4
To find W 4 from W 3 , we consider 4 th row and 4 th column of W 3 .
In C 4 , 1 is present at R 1 , R 2 , R 3
In R 4 , 1 is present at C 1 , C 2 , C 3
Add new entries in W 3 at (R 1 , C 1 ), (R 1 , C 2 ), (R 1 , C 3 ), (R 2 , C 1 ), (R 2 , C 2 ) ,(R 2 , C 3 ),
(R 3 , C 1 ), (R 3 , C 2 ), (R 3 , C 3 )
1 1 1 1
1 1 1 1
W4 =
1 1 1 1
1 1 0 0
Hence the W 4 is the relation metrix of R
(a, a) (a, b) (a, c) (a, d) (b, a) (b, b) (b, c)
And R =
(b, d) (c, a) (c, b) (c, c) (c, d) (d, a) (d, b)
Example 4.9.8 Find the transitive closure of R by Warshall's algorithm. A = {Set of positive
integers ! 10}.
R = {(a, b) / a divides b} SPPU : May-07
Solution :
The relation R itself is a transitive relation on the set of positive integers. Hence
R = R and
W0 = M R is the relation matrix of R
TECHNICAL PUBLICATIONS® - An up thrust for knowledge
1 0 1
W0 = MR = 0 1 0
1 1 0
Step 2 : To find W1 :
To find W1 from W0 , we consider the first column and the first row.
In C1 , 1 is present at R 1 , R 3
In R 1 , 1 is present at C1 and C 3
Thus add new entries in W1 at (R1 , C1 ), (R1 , C3 ), (R 3 , C1 ), (R 3 , C3 )
Which is given below
1 0 1
W1 = 0 1 0
1 1 1
Step 3 : To find W2 :
To find W2 from W1 , we consider the 2 nd column and 2 nd row.
In C 2 , 1 is present at R 2 , R 3
In R 2 , 1 is present at C 2
Thus add new entries in W2 at (R 2 , C2 ), (R 3 , C2 ) which is given below
1 0 1
W2 = 0 1 0 = W1
1 1 1
Step 4 : To find W3
To find W3 from W2 , we consider the 3 rd column and 3 rd row.
In C 3 , 1 is present at R 1 , R 3
In R 3 , 1 is present at C1 , C 2 , C 3
Examples :
1) (Â, £) (N, £) are Posets.
where '£' is reflexive, antisymmetric and transitive relation.
2) If A = P(S) where S = (a, b, c) and for X, Y Î A, Define X £ Y or XRY iff X Í Y.
As X £ X Þ X £ X. \ ' £ ' is reflexive.
If X £ Y, Y £ Z Þ X Í Y and Y Í X Þ X = Y
\ ' £ ' is antisymmetric relation.
If X £ Y, Y £ Z Þ X Í Y and Y Í Z Þ X Í Z Þ X £ Z
Þ ' £' is transitive relation.
\ (P(S), Í) or (P(S), £) is a poset.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
II) Totally ordered set : Let A be any nonempty set. The set A is called linearly
ordered set or totally ordered set if every pair of elements in A are comparable.
i.e. for any a, b Î A either a £ b or b £ a .
It is useful tool, which completely describes the associated partially ordered relation.
It is also known as ordering diagram.
A diagram of graph which is drawn by considering comparable and non-comparable
elements is called Hasse diagram of that relation. Therefore while drawing Hasse
diagram following points must be followed.
4) If a £/ b and b £/ a i.e. a and b are non - comparable elements, then they lie on same
level and there is no edge between a and b.
Example 4.10.1 Draw Hasse diagram of a poset (P(s), Í) where S = {a, b, c}.
Solution : P (s) = { f, {a}, {b}, {c}, {a, b} {a, c} {b, c} {a, b, c}}
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
{a,b,c}
Level 4
Level 2 {a}
{b} {c}
Level 1
Fig. 4.10.1
4.10.2 Chains and Antichains
Let (A, £) be a poset. A subset of A is called a chain if every pair of elements in the
subset are related.
A subset of A is called antichain if no two distinct elements in a subset are related.
e.g. In above example (4.10.1)
1) The chains are {f, {a }, {a, b}, {a, b, c}}, {{a}, {a, c}, {a, b, c}}, {{b, c}, {a, b, c}}
2) Antichains are {{a}, {b}, {c}}
Note : 1) The number of elements in the chain is called the length of chain.
2) If the length of chain is n in a poset (A, £ ) then the elements in A can be
partitioned into n disjoint antichains.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.10.2 Determine the greatest and least elements of the poset whose Hasse diagrams
are shown below.
d
d e d c d
c
c b b c
b
a b a a
a
I II III IV
Fig. 4.10.2
Solution : The Poset shown in Fig. 4.10.2 (I) has neither greatest not least element.
The Poset shown in Fig. 4.10.2 (II), has greatest and a as least element.
The Poset shown in Fig. 4.10.2 (III), has no greatest element but a is the least element.
The Poset shown in Fig. 4.10.2 (IV), has greatest and a as least element.
Example 4.10.3 Find glb, lwb, ub, lb, maximal, minimal, of the poset (A, R), Here aRb if
a / b where. A = { 2, 3, 5, 6, 10, 15, 30, 45}
Solution : We have A = {2, 3, 5, 6, 10, 15, 30, 45} and aRb iff a|b.
30
Level 3 45
Level 2 6 10
15
Level 1 2
3 5
Fig. 4.10.3
1) Here 10 and 30 are upper bounds of 2 and 5, But 10 is the least upper bound of
2 and 5.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
2) 5, 15, 3 are lower bounds of 30 and 45. But 15 is the greatest lower bound of 30
to 45.
3) This Poset has neither greatest element nor least element.
4) This poset has two maximal elements 45 and 30 as there is no element c such
that 45 £ C and 30 £ C.
5) This poset has three minimal elements 2, 3 and 5. because there is no element
x Î A such that x £ 2, x £ 3 and x £ 5
A lattice is a poset in which every pair of elements has a least upper bound (lub) and
a greatest lower (glb).
Let (A, £) be a poset and a, b Î A then lub of a and b is denoted by a Ú b. It is called
the join of a and b.
i.e. a Ú b = lub (a, b)
The greatest lower bound of a and b is called the meet of a and b and it is denoted
by a Ù b
\ a Ù b = glb (a, b)
From the above discussion, it follows that a lattic is a mathematical structure with
two binary operations Ú (join) and Ù (meet). It is denoted by {L, Ú , Ù }.
Examples :
Example 4.10.4 Let A = {1, 2, 3} P (A) = { f, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3 } show that
P(A), Í ) is a lattice
Solution : The Hasse diagram of the poset (P(A), Í) is given below :
{a,b,c}
{a,b} {a,c}
{b,c}
{a}
{b} {c}
Fig. 4.10.4
Here every pair of elements of a poset has lub and glb. Hence (P(A), Í) is a lattice.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
f
6 4
5 d c
3 d e
2 b
2
4 c
3 1
a
1 a b
I II III IV
Fig. 4.10.5
Solution : I) In Fig. 4.10.5 (I), every pair of elements has lub and glb.
\ It is a lattice.
II) In Fig. 4.10.5 (II), every pair of elements has lub and glb.
\ It is a lattice.
II) In Fig. 4.10.5 (III), a Ù b does not exist.
\ It is not a lattice.
IV) In Fig. 4.10.5 (IV), c Ú d does not exist.
\ It is not a lattice.
Example 4.10.6 Let A be the set of positive factors of 15 and R be a relation on A s.t.
R = {xRy| x divides y, x y Î A}. Draw Hasse diagram and give and Ù and Ú for lattice.
SPPU : Dec.-06
Solution : We have A = {1, 3, 5, 15}
Ú 1 3 5 15 Ù 1 3 5 15
15 1 1 3 5 15 1 1 1 1 1
3 3 3 15 15 3 1 3 1 3
5 3
5 5 15 5 15 5 1 1 5 5
1
15 15 15 15 15 15 1 3 5 15
Fig. 4.10.6
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
2) Associative law
a Ú (b Ù c) = (a Ú b) Ù (a Ú c)
a Ù (b Ú c) = (a Ù b) Ú (a Ù c)
3) Absorption law
a Ù (a Ú b) = a and av (a Ù b) = a
3) a Ù a = a, a Ú a = a
4) a Ù b = a iff a Ú b = b
III) Distributive lattice : A lattice (L, Ú , Ù ) is called a distributive lattice if for any
elements a,b,c Î L, it satisfies the following properties,
i) a Ú (b Ù c) = ( a Ú b) Ù (a Ú c)
ii) a Ù (b Ú c) = ( a Ù b) Ú (a Ù c)
If the lattice does not satisfy the above properties then it is called a non distributive
lattice.
Theorem : Let, (L, Ù , Ú) be a lattice with universal bounds 0 and 1 then for any
a Î L, a Ú 1 =1, a Ù 1 = a, 0 Ú a = a, 0 Ù a = 0.
30 1
III) Complement lattice : Let (L, Ù , Ú) be a lattice with
universal bounds 0 and 1 for any a Î L, b Î L is said to be
2 3 5
complement of a if a Ú b = 1 and a Ù b = 0.
A Lattice in which every element has a complement in that 10
lattice, is called the complemented lattice.
e.g. 1) The Hasse diagram is here 0 » 1 and 1 » 30. Fig. 4.10.7
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
i) 2 Ù 3 = 0 and 2 Ú 3 = 1, 2 Ù 5 = 0 and 2 Ú 5 = 1
\ 2 has two compliments 3 and 5
Hence the complement is not unique.
4.11 Principle of Duality SPPU : Dec.-10, 11, 13, 14, 15, 16, May-14, 15, 19
Any statement about lattice involving Ù , Ú £ , ³ remains true if 'Ù' is replaced by 'Ú',
'Ú by Ù ', ' £ by ³', ' ³ by £', '0 by 1' and '1 by 0'.
e.g. 1) a Ú (b Ù c) = a Ù (b Ú c)
2) a Ù (b Ú 1) = a Ú (b Ù 0)
Examples
ì(1,1), (1,2), (1,3), (1,4) (1,6), (1,9), (1,12), (2,2), (2,4), (2,6),(2,12) (3,3), (3,6), (3,9) ü
and R = í ý
î(3,12), (4,4), (4,12), (6,6), (6,12), (9,9), (12,12) þ
4 6 9
3
2
1
Fig. 4.11.1
i) Chains are
{1, 2, 4, 12}
{1, 2, 6, 12}
{1, 3, 6, 12}
ii) Antichains are
{6, 9} {9, 12}
{4, 9}
Example 4.11.2 Determine whether the poset represented by each of the Hasse diagram are
lattices. Justify your answer.
6 h
f
e 4 5 c g
f
c d
c
2 3 b d
b
a
1 a
Fig. 4.11.2 SPPU : Dec.-10
Solution :
I) In Fig. 4.11.2 (I), every pair of element has glb and lub. \ It is a lattice.
II) In Fig. 4.11.2 (II), every pair of elements has lub and glb. \ It is a lattice.
III) In Fig. 4.11.2 (III), every pair of elements gas lub and glb. \ It is a lattice.
Example 4.11.3 Show that the set of all divisors of 36 forms a lattice. SPPU : Dec.-14
Solution : Let A = {1, 2, 3, 4, 6, 9,12, 18, 36 } and Let '£' is a divisor of.
It's Hasse diagram is as follows.
36 1
12 18
4 6 9
2 3
10
Fig. 4.11.3
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
The universal upper bound 1 is 36 and lower bound 0 is 1. Every pairs of elements
of this poset has lub and glb.
\ It is a lattice.
Example 4.11.4 SLet n be a positive integer, S n be the set of all divisors of n, Let D denote
the relation of divisor. Draw the diagram of lattices for n = 24, 30, 6. SPPU : May-15
Solution : Given that
24
12 30
6 6 6 10
4 15
2
2 3 2 3 3 5
1 1 1
S6 S24 S30
Fig. 4.11.4
Example 4.11.5 Show that the set of all divisors of 70 forms a lattice.
SPPU : Dec.-13, May-19, Marks 3
Solution : Let A = {1, 2, 5, 7, 10, 14, 35, 70}
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
70
10 14
35
2
5 7
1
Fig. 4.11.5
Example 4.11.6 Let A = {1, 2, 3, 4 , 5, 6, 7, 8 ,9, 12, 18, 24} be ordered by the relation x
divides y. Show that the relation is a partial ordering and draw Hasse diagram.
SPPPU : Dec-15
Solution : We have A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 18, 24}
8 18
12
4 6 9
5 7
3
2
1
Fig. 4.11.6
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Example 4.11.7 Let x = {2, 3, 6, 12, 24, 36} and x £ y iff x divides y find
i) Maximal element ii) Minimal element iii) Chain iv) Antichain v) Is Poset lattice
SPPU : May-14
Solution : We have x = {2, 3, 6, 12, 24, 36}
The relation 'R' = '£'
\ R = {(2, 2) (2, 6) (2, 12) (2, 24) (2, 36) (3, 3) (3, 6) (3, 12) (3, 24) (3, 36),
(6, 6) (6, 12) (6, 24) (6, 36) (12, 12)(12, 24) (12, 36) (24, 24) (36, 36)}.
It's Hasse diagram is as follows .
36 24
12
2 3
Fig. 4.11.7
i) Maximal elements are 24, 36
ii) Minimal elements are 2, 3
iii) Chain { 2, 6, 12, 24}, { 2, 6, 12, 36}, {3, 6, 12, 24}, {3, 6, 12, 36}
iv) Antichain : {2, 3} {24, 36}
v) The given poset is not a lattice as 2 Ù 3 does not exist.
Example 4.11.8 The following is the Hasse diagram of the poset :
{(a, b, c, d, e), <} Is it a lattice ? Justify SPPU : Dec.-16, Marks 2
b c d
e
Fig. 4.11.8
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Solution : Let
A = {a, b, c, d, e}
From the given Hasse diagram, every pair of element has glb and lub. Hence it is a
lattice.
qqq
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
TM
5.1 Introduction
The concept of relation was defined very generally in the preceeding chapter. We
shall now discuss a particular class of relations called functions. Many concepts of
computer science can be conveniently stated in the language of functions.
In other words, range of f is the set of all images of the elements of A under f.
Examples
Example 5.2.1 If f is a function such that f(x) = x 2 – 1 where x Î R find the values of f(–1),
f(0), f(1), f(3) and range set of f.
Solution : We have f(x) = x 2 – 1
\ f(–1) = (–1) 2 – 1 = 1 – 1 = 0
f(0) = 0 – 1 = –1
f(1) = 1 2 – 1 = 0
f(3) = 3 2 – 1 = 8
For any x Î Â, x 2 – 1 Î Â
\ The range of f is R(f) = {x –1 £ x < ¥}
Let A and B be two non empty sets. A partial function f with domain set A and
codomain set B is any function from A' to B where A' CA. For any x Î A – A' , f(x) is not
defined.
To make the distinction more clear, the function which is not partial is called as a
total function.
e.g.
1)
A f B
1 a
A' 2 b f : A' B is a partial function
3 c
4 d
5 e
Fig. 5.2.1
1
2) The function f : Â ® Â defined as f(x) = is a partial function. As it is not
x
defined for x = 0.
3) The function f : Â ® Â defined as f(x) = x is a partial function, as x is not
defined for x < 0, in Â.
1 1
2 2 A is the identity function
f:A
3 3
4 4
Fig. 5.2.2
Note : gof is defined only when the range of f is a subset of the domain of g.
e.g. 1)
2
A f(x) = x B g(x) = x C gof
Therefore gof : A C A C
1 1 1 gof (1) = g[f(1)] = g(1) = 1 1 1
2 4 4 2 4
gof (2) = g[f(2)] = g(4) = 4
3 9 9 3 9
gof (3) = g[f(3)] = g(9) = 9 16
4 16 16 4
25 gof (4) = g[f(4)] = g(16) = 16 25
25
36 36
Example 5.2.3 Let f(x) = x+2, g(x) = x – 2, h(x) = 3x, for x Î Â Where  is the set of real
numbers
Find i) gof ii) fog iii) fof iv) hog v) gog vi) foh vii) hof viii) fohog ix) gofoh.
SPPU : May-08, 15, Dec.-12, Marks 4
Solution : Let x Î Â be any real number.
= 3x – 6 + 2 = 3 x – 4
= g[3 x + 2] = 3 x + 2 – 2 = 3 x
= ( 2 a +5) 2 – 2 = 4 a 2 +20a + 23
= 2[(a 2 + 4 a +2] +1 = 2 a 2 +8 a +5
= [2 a + 7] 2 – 2 = 4 a 2 +28 a + 47
5.3 Special Types of Functions SPPU : Dec.-10, 11, 16, 17, May-18
I) Let f : A ® B be a function.
i) Function f is said to be one to one (or Injective) function if distinct elements of A
are mapped into distinct elements of B.
i.e. f is one to one if
a 1 ¹ a 2 Þ f(a 1 ) ¹ f(a 2 )
OR f(a 1 ) = f(a 2 ) Þ a 1 = a 2
ii) Function f is said to be onto function if each element of B has at least one
preimage in A.
OR
A function f : A ® B is called onto (or surjective) function if the range set of f is equal
to B.
iii) A function f is called a objective function if it is both one to one and onto.
iv) A function f is called into function if $ at least one element in B which has no
preimage in A.
i.e. A function f is called into function if R(f) ¹ B
2) Let a function f : A ® B be a bijective function then f –1 : B ® A is called the
inverse mapping of f and defined as f(b) –1 = a iff f(a) = b
It is also known as invertible mapping.
3) Characteristic function of a set :
Let U be a universal set and A be a subset of U.
Then the function y A : U ® {0, 1} defined by
ì1 if x Î A
y A (x) = í
î0 if x Ï A
Examples
2
f(x) = x
A B
1 1
2 4
3 9
4 16
25
Fig. 5.3.1
A B
–2
–1 0
0 1
1 4
2
Fig. 5.3.2
A f B
–2
0
–1
1
0
4
1
9
2
Fig. 5.3.3
A f B
1 1
2 4
3 9
4 16
5 25
Fig. 5.3.4
e) Into function
A f B
1 1
2 2
3 3
Fig. 5.3.5
f) Inverse function
–1
A f B f A
1 1 1
2 4 2
3 9 3
4 16 4
Fig. 5.3.6
Example 5.3.3 Let A = {a, b, c, d} and B = {1, 2, 3}. Determine whether the relation R from
A to B is a function. Justify. If it is function give the range :
i) R = [(a, 1), (b, 2), (c, 1), (d, 2)]
ii) R = [(a, 1), (b, 2), (a, 2), (c, 1), (d, 2)] SPPU : Dec.-16, Marks 4
Solution : Given that
Every element of the domain set A is related to the unique element of set B.
R is a funtion from A ® B.
Range of R is {1, 2}.
ii) R = {(a, 1), (b, 2), (a, 2), (c, 1) (d, 2)}
Here a ® 1 and a ® 2 hence a has two images 1 and 2 in set B. i.e. a has no unique
image in set B. Thus given relation R is not a function.
Example 5.3.4 What are relations and functions. Given a relation R = {(1, 4), (2, 2), (3, 10),
(4, 8), (5, 6)} and chek whether the following relations R 1 , R 2 , R 3 and R 4 is a function
or not.
R 1 = {(1, 4), (2, 4), (3, 4), (4, 4), (5, 4)}
R 2 = {(1, 2), (2, 4), (2, 10), (3, 8), (4, 6), (5, 4)}
R 3 = {(1, 6), (2, 2), (4, 4), (5, 10)}
R 4 = {(1, 6), (2, 2), (3, 2), (4, 4), (5, 10} SPPU : Dec.-17, Marks 6
Solution : Refer sections 4.3 and 5.2
R 4 = {(1, 6), (2, 2), (3, 2), (4, 4), (5, 10)}
Every element of a domain set has unique image in codomain set so R 4 is a function.
\ f is injective mapping
Let y Î B and f(x) = y Þ 2x 3 – 1 = y
1+ y
\ 2x 3 = 1+ y Þ x 3 =
2
3
1+ y 3
y 1
Þ x = = + Î A = Â for any y Î B
2 2 2
\ f is a surjective mapping.
Thus f is injective as well as surjective function.
Hence f is a bijective function.
1 1 1 1
We have f(x) = y Þ x = 3 y + Þ f –1 ( y) = x = 3 y + = g(y)
2 2 2 2
Solution : Depending upon the nature of function, there are mainly two functions.
(a) Trigonometric function : The six functions sin x, cos x, tan x, sec x, cosec x, cot x,
where x is in radians are called trigonometric functions.
e.g. f(x) = sin x + tan x.
(b) Inverse trigonometric function : The six functions sin–1 x, cos–1 x, tan–1 x,
cosec–1 x, sec–1 x and cot–1 x are called inverse trigonometric functions.
e.g. f(x) = cos–1 x + 5 tan–1 x
x1 = x 2
Þ g(y) = h (y) " y
Þ g º h i.e. g and h are equal function.
Example 5.3.8 If f : A ® B and g : B ® C are bijective functions the gof is also bijective.
(ii) Let z Î C.
\ $ y in B such that g (y) = z and $ x in A such that f(x) = y.
\ g(y) = z Þ z = g (f (x)) = gof (x) where x Î A
Þ gof is onto function.
Hence gof is bijective function.
a b
f(a) = f(b) Þ = Þ a=b
2 2
In particular a = 7, b = 6
7 -1 6
f(7) = =3 f(6) = =3
2 2
f(7) = f(6) but 6 ¹ 7
Example 5.3.10 Let f (x) = ax2 + b and g(x) = cx2 + d, where a, b, c, d are constants.
Determine for which values of constants gof (x) = fog (x).
Solution : Given that, f(x) = ax2 + b and g(x) = cx2 + d
Example 5.3.11 Show that the functions f(x) = x3 + 1 and g(x) = (x – 1)1/3 are converse to
each other.
Solution : We have, g(x) = (x - 1) 1 3
Let y = g (x) = (x - 1) 1 3
Þ y3 = x – 1
Þ x = y3 + 1 ... (Which is f (x))
Example 5.3.12 Let f : X ® Y and X and Y are set of real numbers. Find f–1 if
2x - 1
(i) f(x) = x2 ; (ii) f(x) =
5
Solution : Let f : X ® Y and X, Y Í Â
(i) f(x) = x2
Let f(x) = y
x2 = y
Þ y = x2
Þ y = ± x
Therefore, given function is not one to one. Hence f–1 does not exist.
(ii) Let f(x) = y
2x - 1
= y
5
Þ 2x = 5y + 1
5y + 1
x = " yÎÂ
2
Example 5.3.13 Let X = {a, b, c}. Define f : X ® X such that f = {(a, b) (b, a) (c, c)}.
Find (i) f –1 ; (ii) f 2 ; (iii) f 3 ; (iv) f 4
Solution : Given fucntion f is bijective function.
Example 5.3.14 Let A = {1, 2, 3}, B = {1, 2, 3} and f 1 and f 2 are functions from A to B.
f 1 = {(1, 2), (2, 3), (3, 1)}
f 2 = {(1, 2), (2, 1), (3, 3)}
Compute f 1 o f 2 and f 2 o f 1 SPPU : May-18, Marks 4
Solution : We have f1 o f2 ( x) = f1 [ f2 ( x)]
f1 [ f2 (1)] = f1 [ 2] = 3
f1 [ f2 ( 2)] = f1 [1] = 2
f1 [ f2 ( 3)] = f1 [ 3] = 1
Now, f2 o f1 ( x) = f2 [f1 (x)]
f2 [ f1 (1)] = f2 [ 2] = 1
f2 [ f1 ( 2)] = f2 [ 3] = 3
f2 [ f1 ( 3)] = f2 [1] = 2
1 p a
2
q b
3
gof
Fig. 5.3.7
Example 5.3.16 Let R be the set of real numbers and f, g, h : Â ® Â such that
1
f(x) = x + 2 , g (x) = h (x) = 3. Compute
x2 +1
(i) f–1 g (x) ; (ii) hf (gf–1) [h f (x)]
Solution : (i) Given that f (x) = x + 2
=
1 - 2x 2 - 2
=
(
- 2x 2 + 1 )
(x 2 + 1) x2 +1
1
(g f–1) [h f (x)] = g f–1 (3) =
32 - 2(3) + 5
1 1
= =
9-6+6 8
é 1ù é æ 1 öù
\ h f (g f–1) (h f (x)) = h f ê ú = h ê f ç ÷ ú
ë 8û ë è 8 øû
é1 ù é 17 ù
= h ê + 2ú = h ê ú = 3
ë 8 û ë 8û
i.e. h f (g f–1) (h f (x)) = 3
Example 5.3.17 Show that f, g : N ´ N ® N as f (x, y) = x + y. g(x, y) = xy are onto but not
one-one
Solution : (i) Suppose f (x 1 , y 1 ) = f (x 2 , y 2 )
Þ x1 + y 1 = x 2 + y 2
Þ x1 ¹ x2 and y1 ¹ y2
e.g. x1 = 5 , x2 = 2 , y1 = 4 , y2 = 7.
We know that the codinality of a set is the number of elements of that set. If set is
finite then, we can list elements as 1, 2, 3, …. Therefore every finite set is countable. As
|f| = 0, the null set is also countable. A question remains same for an infinite sets. Let
us define countable infinite sets.
Definition :
An infinite set A is said to be countable if there exists a bijection f : N®A
\ A = { f (1), f (2), f (3), …}
Þ Define f : A È B ® N as f (a i ) = 2 i – 1
and f (b i ) = 2 i
f is bijective \ A È B is countable
3) Prove that the set of rational numbers is countably infinite.
SPPU : May-18, 19, Marks 4
Proof : We know that the countable union of countable sets is countable. Therefore it is
sufficient to prove that the set of rational numbers in [0, 1] is countable.
We have to prove that $ atleast one function f.
f : [0, 1] ® N such that f is injective.
We arrange the rational numbers of the interval according to increasing denominators
as
1 1 2 1 3 1 2 3 4
0, 1, , , , , , , , , ,L
2 3 3 4 4 5 5 5 5
then the one to one correspondence is as follows
0«1
1«2
1
«3
2
1
«4
3
2
«5
3
1
« 6 and so on
4
Hence set of rationals in [0, 1] is countable. Thus the set of rational numbers is
countable and as the set is infinite, it is countably infinite.
Proof : Any real number in (0, 1) can be written in a unique decimal without an
infinite string of 9's at the end. i.e. 0.3459999 will be represented as 0.345000. Let the
infinite sequence be given by,
1 ® x 1 = 0 × a 11 a 12 a 13 …
2 ® x 2 = 0 × a 21 a 22 a 23 …
3 ® x 3 = 0 × a 31 a 32 a 33 …
M M
n ® x n = 0.a n1 a n2 a n3 …
M M
Construct a new number y = 0 × b1 b 2 b 3 …
Where b i = 0 if a ii ¹ 0
b i = 1 if a ii = 0
Hence b1 ¹ a 11 , b 2 ¹ a 22 , b 3 ¹ a 33 … b n ¹ a nn
\ b i ¹ a ii , " i
\ y ¹ x1 , y ¹ x i " i
Hence y is not in the list of numbers {x 1 , x 2 , L x n L} Thus y Î(0, 1) and it is
different from elements in {x 1 , x 2 , L x n L} which is contradiction that A is countable.
Hence A is not countable.
Thus the set of real numbers is not countable.
I) This principle states that if there are n + 1 pigeons and only n pigeon holes then
two pigeons will share the same whole.
This principle is stated by using the analogy of the bijective mapping i.e. If A and B
are any two sets such that |A| > |B| then there does not exist bijective mapping from A
to B.
Examples
Example 5.5.1 If 11 shoes are selected from 10 pairs of shoes then there must be a pair and
matched shoes among the selection.
Solution : In the pigeonhole principle, 11 shoes are pigeons and the 10 pairs are the
pigeon holes.
Example 5.5.2 Show that if seven numbers from 1 to 12 are chosen then two of them will add
upto 13.
Solution : We have A = {1, 2, 3, 4, 5, … 12}
We form the six different sets each containing 2 numbers that add uptot 13.
A1 = {1, 12}, A 2 = {2, 11}, A 3 = {3, 10}, A 4 = {4, 9}, A 5 = {5, 8}, A 6 = {6, 7}
Each of the seven numbers chosen must belong to one of these sets. As there are only
six sets, by pigeonhole principle two of the chosen numbers must belong to the same set
and their sum is 13.
II) The extended pigeon hole principle
If n pigeons are assigned to m pigeon holes, then one of the pigeon holes must be
é n - 1ù
occupied by at least ê + 1 pigeons. It is also known as generalized pigeon hole
ë m úû
é n - 1ù é 9ù é 16ù
principle. Here ê ú is the integer division of n – 1 by m. e.g. ê ú = 4, ê ú = 3,
ë m û 2
ë û ë 5û
é 8ù
êë 3úû = 2.
Examples
Example 5.5.3 Show that 7 colours are used to paint 50 bicycles, then at least 8 bicycles will
be of same colour. SPPU : Dec.-09, 12, Marks 4
é n - 1ù
Solution : By the extended pigeonhole principle, at least ê + 1 pigeons will occupy
ë m úû
one piegeonhole.
Here n = 50, m = 7 and m < n then
é 50 - 1ù
ê 7 ú +1 = 7+1=8
ë û
Example 5.5.4 Write generalized pigeonhole principle. Use any form of pigeonhole principle to
solve the given problem.
i) Assume that there are 3 mens and 5 womens in a party show that if these people are
lined up in a row at least two women will be next to each other.
ii) Find the minimum number of students in the class to be sure that three of them are
born in the same month. SPPU : Dec.-11, Marks 4
Solution : Please refer section 5.5 (II) for definition.
Given that three students in the class are born in the same month.
é n - 1ù
êë m úû + 1 = 3
n- 1
Þ = 3–1=2
12
n = 2 ´ 12 + 1 = 25
Example 1 :
1 ì 1 1 1 ü
If ar = , r ³ 0 then a = í1, , , , Ký
3r î 3 2
3 3 3
þ
ì 5 5 5 ü
and 5a = í5, , , , Lý
î 3 32 33 þ
1
\ 5 a r = 5×
3r
Example 2 :
ì 1 if 0 r 2 ì2 r + 1 , 0 £ r £ 1
If ar = í and br = í
î3 r if r³ 3 î r- 5 , r³ 2
then a+b = c
ì2r + 1 + 2 , 0 £ r £ 1
ï
\ cr = a r + b r = í 1 + ( - 3) , r= 2
ï3 r + r - 5 , r³ 3
î
ì2 r + 1 + 2 , 0 £ r £ 1
ï
= í -2 , r= 2
ï 4 r- 5 , r³ 3
î
ì 1 (2 r + 1) , 0 £ r £ 1
ï
and d = ab and d r = a r b r = í 1 ( - 3) , r= 2
ï3 r ( r - 5) , r³ 3
î
ì 2r + 1 , 0£ r£ 1
ï
dr = í -3 , r= 2
ï3 r - 15 r ,
2 r³ 3
î
Example 3 :
If a r = 3r , r ³ 0
br = 5r , r ³ 0
r
then c = a * b Þ cr = å a n br - n = a 0 br + a 1 br - 1 + a 2 br - 2 +L + a r b0
n= 0
Example 1 :
If a r = 5 r , r ³ 0 then E [a r ] = a r + 1 = 5r + 1
E 2 [a r ] = a r + 2 = 5 r + 2 , E - n [a r ] = a r - n = 5 r - n
Example 2 :
ìr 3 - 2r + 5 ; 0 £ r £ 6
If ar = í
î 3 ; r³ 7
ì 0 , 0£ r< 2
3 [a ï 3
then E r ] = í(r + 3) - 2 (r + 3) + 5 , 3 £ r £ 9
ï 3 , r ³ 10
î
ì(r - 2) 3 - 2(r - 2) + 5 ; 0 £ r £ 4
and E - 2 [a r = í
î 3 ; r³ 5
Example 1 :
If a r = 3 r ; r ³ 0 then
D ar = ar+ 1 – a r = 3r + 1 - 3r
= (3 – 1) 3 r = 2.3 r
Example 2 :
ì 3 ; 0£ r£ 4
If ar = í
î r + 2 ; r³ 5
then D ar = ar+ 1 - ar
ì 3 ; 0£ r+ 1£ 4
\ ar+ 1 = í
î(r + 1) + 2 ; r+ 1³ 5
ì 3 ; 0£ r£ 3
ar+ 1 = í
îr + 3 ; r³ 4
ì 0 ; 0£ r£ 3
ï
\ D ar = í - 3 + (4 + 3) ; r= 4
ï(r + 3) - (r + 2) ; r³ 5
î
ì0 ; 0 £ r £ 3
ï
D ar = í4 ; r= 4
ï1 ; r³ 5
î
Examples
Example 1 :
Let a r = 6r ; r ³ 0
a r - 1 = 6 r - 1 ; r – 1 ³ 0 i.e. r ³ 1
\ Ñ a r = a r – a r - 1 = 6r - 6r - 1 ; r ³ 1
= (6 – 1) 6 r - 1 ; r ³ 1
Ñ a r = 5 × 6r - 1 ; r ³ 1
Example 2 :
ì1 ; 0£ r£ 2
If ar = í r
î3 ; r³ 3
ì 1 ; 0£ r- 1£ 2
ar- 1 = í r- 1
î3 ; r- 1³ 3
ì 1 ; 1£ r£ 3
= í r- 1
î3 ; r ³4
ì 0 ; r= 0
ï 1 ; r= 1
ïï
Ñ ar = ar – ar- 1 =í 0 ; r= 2
ï 26 ; r= 3
ï
ïî2 ´ 3 r - 1 ; r³ 4
\ c r = a 0 br + a1 br -1 + a 2 br - 2 + … + a r b0
\ c 0 = a 0 b0 = 1 ´ 1 = 1
c 1 = a 0 b1 + a 1 b 0 = 1.2 + 1.1 = 3
c 2 = a 0 b 2 + a 1 b1 + a 2 b 0 = 1.3 + 1.2 + 1.1 = 6
c 3 = a 0 b 3 + a 1 b 2 + a 2 b1 + a 3 b 0
= 1.0 + 1.3 + 1.2 + 1.0 = 5
c 4 = a 0 b 4 + a 1 b 3 + a 2 b 2 + a 3 b1 + a 4 b 0
c 4 = 0 + 0 + 1.3 + 0 + 0 = 3
c 5 = 0, c 6 = 0, c r = 0 ; r ³ 5
Notes