DISCRETE MATHEMATICS
AND STRUCTURES
DISCRETE
MATHEMATICS
AND
STRUCTURES
[For B.E./B.Tech. (Computer Science), B.C.A., M.C.A., M.Sc. (Computer Science)]
By
Dr. Satinder Bal Gupta
B.Tech. (CSE), MCA, UGCNET, Ph.D (CS)
Professor, Deptt. of Computer Science & Applications
Vaish College of Engineering, Rohtak,
Haryana
UNIVERSITY SCIENCE PRESS
(An Imprint of Laxmi Publications (P) Ltd.)
BANGALORE N
CHENNAI
JALANDHAR N
KOLKATA N
COCHIN
GUWAHATI
HYDERABAD
LUCKNOW
MUMBAI
RANCHI
NEW DELHI
BOSTON, USA
Copyright 2013 by Laxmi Publications Pvt. Ltd. All rights reserved with the
Publishers. No part of this publication may be reproduced, stored in a retrieval system,
or transmitted in any form or by any means, electronic, mechanical, photocopying,
recording or otherwise without the prior written permission of the publisher.
Published by :
UNIVERSITY SCIENCE PRESS
(An Imprint of Laxmi Publications Pvt. Ltd.)
113, Golden House, Daryaganj,
New Delhi-110002
Phone : 011-43 53 25 00
Fax : 011-43 53 25 28
www.laxmipublications.com
[email protected]Price : ` 450.00 Only.
First Edition : 2002, Second Edition : 2004,
Third Edition : 2006, Fourth Edition : 2007,
Fifth Edition : 2008, Reprint : 2013, Sixth Edition : 2014
OFFICES
Bangalore
Chennai
Cochin
Guwahati
Ranchi
080-26 75 69 30
044-24 34 47 26
0484-237 70 04, 405 13 03
0361-251 36 69, 251 38 81
0651-221 47 64
Kolkata
Lucknow
Mumbai
Hyderabad
Jalandhar
033-22 27 43 84
0522-220 99 16
022-24 91 54 15, 24 92 78 69
040-24 65 23 33
0181-222 12 72
C16452/08/09
UDM-9232-450-DISCRETE MATH & STRU-GUP
Typeset at : Excellent Graphics, Delhi.
Printed at :
To My
Little Daughter
ARSHITA
PREFACE
It gives me a great pleasure in bringing out the Sixth Edition of the book Discrete
Mathematics and Structures. The necessity for Discrete Structure in Computer Science arises
due to selection of certain applications from various areas of the field. As the subject Discrete
Mathematics or Discrete Structures is taught in most Engineering Institutions, the students face
a lot of problems in this subject as no book covers the whole syllabi and also due to lack of solved
problems in the various books. This book is based on the experience gained in teaching a course on
the subject. My intention is to cover all topics in the book with a number of solved problems and
solutions of the questions from the previous question papers of different universities and other
competitive examinations. I am sure that this book will help a student to grip each topic without
any difficulty.
What is New in the Sixth Edition
Many changes have been made in the sixth edition as the goal is to expand the coverage of
topics and more examples.
New chapters has been added on series and sequences, Automation and languages, Boolean
algebra etc.
Many new sections in every chapter.
Additional problems in every chapter.
Multiple choice questions and unsolved exercises.
I would seek the indulgence of my readers in intimating me about any error or shortcomings
noticed by them in the book.
AUTHOR
How to Study Discrete Structures
1. How to Read Math
Read slowly & actively:
Make sure you understand everything before reading anything new
After reading each sentence, ask yourself:
Why?
Do I agree?
Algorithm for Slow & Active Reading
See next page,
2. How to Take Notes in Class
Copy as much as possible from the board or screen.
Copy as accurately as possible.
Include what Teacher say but dont write.
Use abbreviations
Dont necessarily try to understand!
Write down any questions you have.
Then re-write your notes at home, neatly & without abbreviations
That is when you should try to understand!
3. How to Practice Doing Math
Do the odd-numbered problems from Text.
Work with 1 or 2 other students in small study groups;
check each others work.
But dont cheat!
4. How to Study for Tests
Use your recopied class notes, together with your highlighted text and notebook, to
make an outline of the material.
Solve lots of sample problems.
Golden Rule: Never read Mathematics. Always solve problems by writing while reading.
Algorithm for Slow
& Active Reading
HOW TO READ (A COMPUTER SCIENCE TEXT)
Algorithm by William J. Rapaport
WHILE there is a next.sentence to read, DO:
BEGIN (* while *)
1. Read it, SLOWLY;
2. IF you do not understand it, THEN
BEGIN (* if *)
(a) re-read the previous material, SLOWLY;
(b) re-read the incomprehensible sentence, SLOWLY;
(c) IF you still dont understand it, THEN
ask a fellow student to explain it;
(d) IF you still dont understand it, THEN
Ask your Teacher to explain it;
(e) IF you are in an upper-level course & you still dont
understand it, THEN
write a paper about it (!)
END (* IF *)
END; (* while *)
Since there is no next sentence (because the Boolean test in the WHILE is false), youve
understood the text!
ACKNOWLEDGMENTS
It is difficult to acknowledge adequately the help & encouragement, I have received in
completion and final publication of this work which has been exercising my mind since long. First,
I must express my gratitude to the Professors & Lecturers of the Sant Longowal Institute of
Engg. & Technology, Longowal (Punjab) where I learnt the elements of Discrete Mathematics and
Structures during the course of my various assignments on the subject.
I also owe a debt of gratitude to the Esteemed Management of Vaish College of Engg.,
Rohtak who has been a source of inspiration to me in attempting this work. I should also express
my grateful thanks to my associates with whom I had occasions to discuss the work of my book at
length which are in large numbers. I must express my indebtness to the students who have helped
me in fixing the pattern of emphasis & in correction of proofs, to mention the least are Manish
Goel, Ashish Goel & Manish Kansal.
Last, but not the least, I express my appreciation to my wife, Monika Gupta for her assistance
and constant encouragement without which the venture would have failed.
AUTHOR
CONTENTS
Chapters
1.
Page No.
SETS
135
1.1
Definition .................................................................................................................. 1
1.2
Set Formation .......................................................................................................... 1
1.3
Standard Notations .................................................................................................. 1
1.4
Various Types of Sets .............................................................................................. 2
1.5
Operations on Sets ................................................................................................... 7
1.6
Algebra of Sets ......................................................................................................... 8
1.7
Cardinality of a Set ............................................................................................... 12
1.8
Venn Diagrams ...................................................................................................... 13
1.9
Multisets ................................................................................................................. 14
1.10 Ordered Pairs ......................................................................................................... 15
1.11 Cartesian Product of Two Sets ............................................................................. 15
Solved Problems ............................................................................................................... 17
Multiple Choice Questions ............................................................................................... 26
Exercises ........................................................................................................................... 27
2.
PRINCIPLE OF INCLUSION AND EXCLUSION
3647
2.1
First Principle ........................................................................................................ 36
2.2
Inclusion-Exclusion Principle in General ............................................................. 37
Solved Problems ............................................................................................................... 37
Multiple Choice Questions ............................................................................................... 42
Exercises ........................................................................................................................... 42
3.
MATHEMATICAL INDUCTION
3.1
3.2
3.3
4864
Principle ................................................................................................................. 48
Working Rule ......................................................................................................... 48
Peanos Axioms ...................................................................................................... 48
Chapters
Page No.
Solved Problems ............................................................................................................... 49
Multiple Choice Questions ............................................................................................... 59
Exercises ........................................................................................................................... 60
4.
RELATIONS
65119
4.1
Binary Relation ...................................................................................................... 65
4.2
Complement of a Relation ..................................................................................... 66
4.3
Inverse of a Relation ............................................................................................. 66
4.4
Representation of Relations ................................................................................... 67
4.5
Composition of Relations ........................................................................................ 69
4.6
Path in Relations ................................................................................................... 71
4.7
Composition of Paths ............................................................................................. 76
4.8
Computer Representation of Relations .................................................................. 77
4.9
Representation of Relation in Computer ............................................................... 78
4.10 Properties of Relations ........................................................................................... 82
4.11 Closure Properties of Relations ............................................................................. 85
4.12 Warshalls Algorithm to Find Transitive Closure ............................................... 87
4.13 Equivalence Relations ............................................................................................ 88
4.14 Partial Order Relation ........................................................................................... 89
4.15 Total Order Relation .............................................................................................. 90
4.16 Partition ................................................................................................................. 90
4.17 Equivalence Class .................................................................................................. 91
4.18 Circular Relation .................................................................................................... 91
Solved Problems ............................................................................................................... 92
Multiple Choice Questions ............................................................................................. 103
Exercises ......................................................................................................................... 106
5.
FUNCTIONS
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
120158
Definition .............................................................................................................. 120
Functions as a Set .............................................................................................. 120
Domain of a Function ......................................................................................... 120
Co-domain of a Function ..................................................................................... 121
Image of an Element ........................................................................................... 121
Range of a Function ............................................................................................ 121
Representation of a Function .............................................................................. 122
Everywhere Defined Function ............................................................................. 122
Chapters
Page No.
5.9
Types of Functions .............................................................................................. 123
5.10 Equal Functions ................................................................................................... 126
5.11 Identity Functions ............................................................................................... 126
5.12 Invertible (Inverse) Functions ............................................................................. 127
5.13 Composition of Functions .................................................................................... 127
5.14 Functions Applicable in Computer Science ........................................................ 129
5.15 Permutation Functions ........................................................................................ 133
Solved Problems ............................................................................................................. 139
Multiple Choice Questions ............................................................................................. 148
Exercises ......................................................................................................................... 150
6.
ALGORITHMS
159181
6.1
Algorithm ............................................................................................................. 159
6.2
Characteristics of Algorithms ............................................................................. 159
6.3
Trace of the Algorithm ........................................................................................ 160
6.4
Pseudo Code ......................................................................................................... 160
6.5
Analysis (complexity) of Algorithms ................................................................... 160
6.6
Asymptotic Notations ........................................................................................... 161
6.7
Big-oh (O) Notation .............................................................................................. 161
6.8
Omega () Notation ............................................................................................ 162
6.9
Theta () Notation ............................................................................................... 162
6.10 Recursive Algorithms ........................................................................................... 163
Solved Problems ............................................................................................................. 164
Multiple Choice Questions ............................................................................................. 170
Exercises ......................................................................................................................... 171
7.
GRAPHS
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
7.9
182244
Basic Terminology ............................................................................................... 182
Subgraph .............................................................................................................. 189
Cut Set ................................................................................................................. 191
Cut Points or Cut Vertices ................................................................................. 191
Bridge (Cut Edges) ............................................................................................... 192
Isomorphic Graphs ............................................................................................... 194
Homeomorphic Graphs ........................................................................................ 195
Directed Graphs ................................................................................................... 196
Labeled Graphs .................................................................................................... 199
Chapters
Page No.
7.10 Weighted Graphs ................................................................................................. 199
7.11 Multigraph ........................................................................................................... 200
7.12 Representation of Graphs .................................................................................... 201
7.13 Other Important Graphs ..................................................................................... 204
7.14 Graph Colouring .................................................................................................. 213
7.15 Shortest Path in Weighted Graphs .................................................................... 216
7.16 Travelling Salesman Problem ............................................................................. 218
Solved Problems ............................................................................................................. 220
Multiple Choice Questions ............................................................................................. 231
Exercises ......................................................................................................................... 234
8.
TREES
245300
8.1
General Trees ....................................................................................................... 245
8.2
Directed Trees ...................................................................................................... 245
8.3
Ordered Trees ...................................................................................................... 246
8.4
Rooted Trees ......................................................................................................... 246
8.5
Path Length of a Vertex ..................................................................................... 247
8.6
Forest .................................................................................................................... 248
8.7
Binary Tree .......................................................................................................... 248
8.8
Infix, Prefix and Postfix Notations ..................................................................... 251
8.9
Complete Binary Tree .......................................................................................... 258
8.10 Full Binary Tree .................................................................................................. 258
8.11 Traversing Binary Trees ..................................................................................... 261
8.12 Algorithms to Draw Binary Trees ...................................................................... 262
8.13 Binary Search Trees ............................................................................................ 267
8.14 Spanning Tree ...................................................................................................... 269
8.15 Game Trees .......................................................................................................... 272
Solved Problems ............................................................................................................. 276
Multiple Choice Questions ............................................................................................. 288
Exercises ......................................................................................................................... 291
9.
PROPOSITIONAL CALCULUS
9.1
9.2
9.3
9.4
301341
Proposition ............................................................................................................ 301
Combination of Propositions ................................................................................ 301
Principle of Duality ............................................................................................. 307
Equivalence of Propositions ................................................................................. 308
Chapters
Page No.
9.5
Tautologies ........................................................................................................... 308
9.6
Contradiction ........................................................................................................ 309
9.7
Contingency .......................................................................................................... 309
9.8
Functionally Complete Sets of Connectives ........................................................ 311
9.9
Argument ............................................................................................................. 312
9.10 Existential Quantifier .......................................................................................... 321
9.11 Universal Quantifier ............................................................................................ 321
9.12 Negation of Quantified Propositions ................................................................... 322
9.13 Propositions with Multiple Quantifiers .............................................................. 323
Solved Problems ............................................................................................................. 323
Multiple Choice Questions ............................................................................................. 333
Exercises ......................................................................................................................... 335
10. PROBABILITY THEORY
342361
10.1 Important Terms Related with Probability ........................................................ 342
10.2 Probability Definition ........................................................................................... 343
10.3 Addition Theorem ................................................................................................. 343
10.4 Multiplication Theorem ....................................................................................... 347
10.5 Conditional Probability ........................................................................................ 350
Solved Problems ............................................................................................................. 354
Multiple Choice Questions ............................................................................................. 358
Exercises ......................................................................................................................... 359
11. COUNTING TECHNIQUES
362391
11.1 First Counting Principle ..................................................................................... 362
11.2 Second Counting Principle .................................................................................. 365
11.3 Define Factorial N ............................................................................................... 366
11.4 Permutation ......................................................................................................... 367
11.5 Combination ......................................................................................................... 373
11.6 The Pigeonhole Principle ..................................................................................... 376
Solved Problems ............................................................................................................. 377
Multiple Choice Questions ............................................................................................. 382
Exercises ......................................................................................................................... 384
Chapters
Page No.
12. SEQUENCES AND SERIES
392416
12.1 Sequences ............................................................................................................. 392
12.2 Representation of Sequences ................................................................................ 393
12.3 Sequences of Symbols or Letters ........................................................................ 393
12.4 Set Corresponding to a Sequence ........................................................................ 394
12.5 Series .................................................................................................................... 394
Solved Problems ............................................................................................................. 405
Multiple Choice Questions ............................................................................................. 413
Exercises ......................................................................................................................... 414
13. RECURRENCE RELATIONS AND GENERATING FUNCTIONS
417447
13.1 Definition .............................................................................................................. 417
13.2 Order of the Recurrence Relation ....................................................................... 417
13.3 Degree of the Difference Equation ...................................................................... 417
13.4 Linear Recurrence Relations with Constant Coefficients .................................. 418
13.5 Total Solution ....................................................................................................... 425
13.6 Generating Functions .......................................................................................... 429
Solved Problems ............................................................................................................. 434
Multiple Choice Questions ............................................................................................. 444
Exercises ......................................................................................................................... 444
14. ALGEBRAIC STRUCTURES
14.1
14.2
14.3
14.4
14.5
14.6
14.7
14.8
14.9
14.10
14.11
14.12
14.13
448482
Definition .............................................................................................................. 448
Binary Operation ................................................................................................. 448
Tables of Operation .............................................................................................. 449
Properties of Binary Operations ......................................................................... 449
Semigroup ............................................................................................................. 452
Congruence Relation ............................................................................................ 454
Monoid .................................................................................................................. 455
Group .................................................................................................................... 455
Abelian Group ...................................................................................................... 459
Product of Groups ................................................................................................ 460
Cyclic Groups ....................................................................................................... 461
Cosets .................................................................................................................... 462
Lagranges Theorem ............................................................................................ 463
