DM - Technical.pdf

SUBJECT CODE : 210241 Strictly as per Revised Syllabus of Savitribai Phule Pune University Choice Based Credit System (CBCS) S.E. (Computer) Semester - I Discrete Mathematics (For IN SEM Exam - 3...

SUBJECT CODE : 210241 Strictly as per Revised Syllabus of Savitribai Phule Pune University Choice Based Credit System (CBCS) S.E. (Computer) Semester - I 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 : [email protected] Mobile : 9011227141 Dr. Rajesh Nandkumar Phursule Ph.D. (Computer Science and Engineering) Associate Professor, Pimpri Chinchwad College of Engineering Nigdi, Pune. ® ® TECHNICAL PUBLICATIONS SINCE 1993 An Up-Thrust for Knowledge (i) Discrete Mathematics (For IN SEM Exam - 30 Marks) Subject Code : 210241 S.E. (Computer) Semester - I First Edition : August 2020 ã Copyright with Dr. H. R. Bhapkar All publishing rights (printed and ebook version) reserved with Technical Publications. No part of this book should be reproduced in any form, Electronic, Mechanical, Photocopy or any information storage and retrieval system without prior permission in writing, from Technical Publications, Pune. 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 : [email protected] 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 9 789333 202763 SPPU 19 9789333202763 (ii)  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 Dedicated to the Readers of the Book (iii) Syllabus Discrete Mathematics - (210241) Credit Scheme Examination Scheme and Marks 03 Mid_Semester (TH) : 30 Marks Unit I Set Theory and Logic Introduction and significance of Discrete Mathematics, Sets – Naïve Set Theory (Cantorian Set Theory), Axiomatic Set Theory, Set Operations, Cardinality of set, Principle of incl usion 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, Propositional Logic - logic, Propositional Equivalences, Application of Propositional Logic - Translating English Sentences, Proof by Mathematical Induction and Strong Mathematical Induction. (Chapters - 1, 2, 3) Unit II Relations and Functions 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. Functions - Surjective, Injective and Bijective functions, Identity function, Partial function, Invertible function, Constant function, Inverse functions and Compositions of functions, The Pigeonhole Principle. (Chapters - 4, 5) (iv)  Table of Contents Unit - I Chapter - 1 Theory of Sets (1 - 1) to (1 - 48) 1.1 Introduction......................................................................................................1 - 2 1.2 Sets...................................................................................................................1 - 2 1.3 Methods of Describing Sets..............................................................................1 - 2 1.3.1 Roster Method (Listing Method)...................................... 1 - 2 1.3.2 Statement Form................................................... 1 - 2 1.3.3 Set Builder Notation................................................ 1 - 3 1.4 Some Special Sets.............................................................................................1 - 3 1.5 Subsets..............................................................................................................1 - 3 1.5.1 Proper Subset..................................................... 1 - 3 1.5.2 Improper Subsets.................................................. 1 - 4 1.5.3 Equal sets......................................................... 1 - 4 1.6 Types of Sets.....................................................................................................1 - 4 1.7 Venn Diagrams..................................................................................................1 - 6 1.8 Operations on Sets............................................................................................1 - 6 1.8.1 Union of Two Sets.................................................. 1 - 6 1.8.2 Intersection of Two Sets............................................. 1 - 7 1.8.3 Disjoint Sets....................................................... 1 - 8 1.8.4 Complement of a Set............................................... 1 - 8 1.8.5 Difference of Sets.................................................. 1 - 8 1.8.6 Symmetric Difference of Sets....................................... 1 - 10 1.9 Algebra of Set Operations...............................................................................1 - 11 1.10 Principle of Duality........................................................................................1 - 12 1.11 Cardinality of Sets........................................................................................ 1 - 23 1.12 The Principle of Inclusion and Exclusion for Sets..........................................1 - 24 (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 Chapter - 2 Propositional Calculus (2 - 1) to (2 - 38) 2.1 Introduction......................................................................................................2 - 2 2.2 Statements or Propositions..............................................................................2 - 2 2.3 Laws of Formal Logic.........................................................................................2 - 3 2.3.1 Law of Contradiction................................................ 2 - 3 2.3.2 Law of Excluded Middle............................................. 2 - 3 2.4 Connectives and Compound Statements.........................................................2 - 3 2.4.1 Compound Statement.............................................. 2 - 3 2.4.2 Truth Table....................................................... 2 - 4 2.4.3 Negation......................................................... 2 - 4 2.4.4 Conjunction....................................................... 2 - 4 2.4.5 Disjunction........................................................ 2 - 5 2.4.6 Conditional Statement (If..... then....)................................. 2 - 6 2.4.7 Biconditional (If and only if).......................................... 2 - 7 2.4.8 Special Propositions................................................ 2 - 8 2.5 Propositional or Statement Formula..............................................................2 - 12 2.6 Tautology........................................................................................................2 - 12 2.7 Contradiction..................................................................................................2 - 12 2.8 Contingency....................................................................................................2 - 12 2.9 Precedence Rule.............................................................................................2 - 16 2.10 Logical Equivalence.......................................................................................2 - 16 2.11 Logical Identities...........................................................................................2 - 18 2.12 The Duality Principle.....................................................................................2 - 20 2.13 Logical Implication........................................................................................2 - 20 (vi)  2.14 Important Connectives.................................................................................2 - 20 2.15 Normal Forms...............................................................................................2 - 21 2.15.1 Disjunctive Normal Form (dnf)..................................... 2 - 22 2.15.2 Conjunctive Normal Form (cnf)..................................... 2 - 22 2.15.3 Principal Normal Form............................................ 2 - 22 2.16 Methods of Proof..........................................................................................2 - 27 2.16.1 Law of Detachment (or Modus Ponens).............................. 2 - 28 2.16.2 Modus Tollen (Law of Contrapositive)............................... 2 - 29 2.16.3 Disjunctive Syllogism............................................. 2 - 29 2.16.4 Hypothetical Syllogism............................................ 2 - 29 2.17 Quantifiers....................................................................................................2 - 32 2.17.1 Universal Quantifiers............................................. 2 - 33 2.17.2 Existential Quantifier............................................. 2 - 33 2.17.3 Negation of Quantified Statement.................................. 2 - 33 Chapter - 3 Mathematical Induction (3 - 1) to (3 - 18) 3.1 Introduction..................................................................................................... 3 - 2 3.2 First Principle of Mathematical Induction Statement.......................................3 - 2 3.3 Second Principle of Mathematical Induction Statement (Strong Mathematical Induction)......................................................................3 - 2 Unit - II Chapter - 4 Relations (4 - 1) to (4 - 64) 4.1 Introduction......................................................................................................4 - 2 4.2 Cartesian Product............................................................................................4 - 2 4.3 Relation............................................................................................................4 - 3 4.4 Matrix Representation of a Relation................................................................4 - 4 4.4.1 Relation Matrix Operations.......................................... 4 - 5 4.4.2 Properties of Relation Matrix........................................ 4 - 6 4.5 Diagraphs.........................................................................................................4 - 6 4.6 Special Types of Relations................................................................................4 - 9 4.6.1 Inverse Relation (OR Converse Relation)............................... 4 - 9 (vii)  4.6.2 Complement of a Relation.......................................... 4 - 10 4.6.3 Composite Relation............................................... 4 - 11 4.7 Types of Relations on Set................................................................................4 - 12 4.7.1 Identity Relation.................................................. 4 - 12 4.7.2 Reflexive Relation................................................ 4 - 13 4.7.3 Symmetric Relation............................................... 4 - 14 4.7.4 Compatible Relation............................................... 4 - 14 4.7.4.1 Asymmetric Relation........................ 4 - 15 4.7.5 Antisymmetric Relation............................................ 4 - 15 4.7.6 Transitive Relation................................................ 4 - 15 4.7.7 Equivalence Relation.............................................. 4 - 16 4.7.8 Properties of Equivalence Relations................................. 4 - 16 4.7.9 Equivalence Classes............................................... 4 - 17 4.8 Partitions of a Set............................................................................................4 - 36 4.8.1 Relation Induced by a Partition...................................... 4 - 37 4.8.2 Refinement of Partitions........................................... 4 - 39 4.8.3 Product and Sum of Partitions....................................... 4 - 40 4.8.4 Quotient Set..................................................... 4 - 40 4.9 Closure of a Relation.......................................................................................4 - 40 4.9.1 Reflexive Closure.................................................. 4 - 40 4.9.2 Symmetric Closure................................................ 4 - 41 4.9.3 Transitive Closure................................................. 4 - 42 4.9.4 Warshall's Algorithm to Find Transitive Closure........................ 4 - 42 4.10 Partially Ordered Set.....................................................................................4 - 52 4.10.1 Hasse Diagram................................................. 4 - 53 4.10.2 Chains and Antichains............................................ 4 - 54 4.10.3 Elements of Poset................................................ 4 - 54 4.10.4 Types of Lattices................................................. 4 - 56 4.10.5 Properties of a Lattice............................................ 4 - 58 4.10.6 Types of Lattices................................................. 4 - 58 4.11 Principle of Duality........................................................................................4 - 59 (viii) Chapter - 5 Functions (5 - 1) to (5 - 28) 5.1 Introduction......................................................................................................5 - 2 5.2 Function............................................................................................................5 - 2 5.2.1 Important Definitions............................................... 5 - 2 5.2.2 Partial Functions................................................... 5 - 3 5.2.3 Equality of Two Functions........................................... 5 - 4 5.2.4 Identity Function................................................... 5 - 4 5.2.5 Constant Function.................................................. 5 - 4 5.2.6 Composite Function................................................ 5 - 4 5.3 Special Types of Functions................................................................................5 - 6 5.4 Infinite Sets and Countability..........................................................................5 - 17 5.4.1 Infinite Set....................................................... 5 - 17 5.4.2 Countable Sets................................................... 5 - 18 5.5 Pigeon Hole Principle......................................................................................5 - 20 5.6 Discrete Numeric Functions............................................................................5 - 22 5.6.1 Basic Operations on Numeric Functions............................... 5 - 23 5.6.2 Finite Differences of a Numeric Functions............................. 5 - 24 (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 TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1-2 Theory of Sets 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. 1.3 Methods of Describing Sets The following are the most useful and common methods of describing sets. 1.3.1 Roster Method (Listing Method) 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} 1.3.2 Statement Form In this form, set is formed especially where the elements have a common characteristic. ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1-3 Theory of Sets e.g. 1) The set of all even integers 2) The set of all Prime Ministers of India 1.3.3 Set Builder Notation 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.4 Some Special Sets The following sets are important and occur frequently in our discussion. 1) Set of natural numbers = N = {1, 2, 3,....} 2) Set of all integers = Z = {...–3, –2, –1, 0, 1, 2, 3....} 3) Set of all positive integers = Z + = {0, 1, 2, 3,...} p 4) Set of all rational numbers = Q = ìí | p, q Î R, (p, q) =1 q ¹ 0üý î q þ 5) Set of real numbers =  6) Set of complex numbers = C 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 1.5.1 Proper Subset A set A is called proper subset of B iff ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1-4 Theory of Sets 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 1.5.2 Improper Subsets 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.5.3 Equal sets SPPU : May-18 Two sets A and B are said to be equal sets if A Ì B and BÌ A. We write A = B e.g. If A = { x | x 2 = 1 } and B = {1, – 1 } then A = B 1.6 Types of Sets Depending upon some properties there are mainly following types of sets. 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 Discrete Mathematics 1-5 Theory of Sets 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. i) A = {a, b}, P(A) = { f, {a }, {b}, {a, b}}. ii) P(A) = f iff A = f i.e. empty set has only subset f, \ P( f) = {f } iii) A = {a, b, c}, P(A) = {f, {a }, {b}, {c }, {a, b}, {b, c }, {a, c }, {a, b, c }}. 6) Power set of power set of A : The power set of the power set of A is denoted by P(P(A)). e.g. If A = {a, b}, p(A) = { f, {a }, {b }, {a, b }} P(P(A)) = {f, p(A), {f}, {a}, {b}, {a, b}, {{a}, {b}}{f, {a}} {{a}, {a, b }}, {f, { b }}, {{b }, {a, b }} { f {a, b}}, {f, {a}, {b}}, { f, {a}, {a, b}} { f, {b}, {a, b}}, {{a}, {b}, {a, b}}} If |A| = 2 then |P(A)| = 2 2 , |P(P(A)| = 2 4 = 16 7) A set itself can be an element of some set Hence one should understand the difference between an element of a set and subset of a set. e.g. If A = {x, y}, P(A) = {f, A, {x }, {y }} 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 Discrete Mathematics 1-6 Theory of Sets viii) f Ì f, f Ì {f }, f Î {f }, {f } Ì {f } are true ix) f Î f is false x) {a, b} Î {a, b, c, {a, b, c}} is false xi) {a, b, c } Î {a, b, c, {a, b, c}} is true. xii) {a, b} Ì {a, b, c, {a, b, c}} is true xiii) {a, f } Î {f, {a, f }} 1.7 Venn Diagrams We often use pictures in mathematics. The relation between sets can be conveniently illustrated by certain diagrams called Venn diagrams. This representation first time used by the British Logician John Venn. In Venn diagram i) Universal set (U) is represented by a large rectangle. ii) Subsets of U are represented by circles or some closed curve iii) If AÌ B then the circle representing A lies inside of circle representing B. iv) If A and B are disjoint sets then circles of A and B do not have common area. v) If A and B are not disjoint sets then circles of A and B have some common area. 1) A Ì U U 2) A Ì B U A A B Fig. 1.7.1 1.8 Operations on Sets To define new sets by combining the given sets, we require set operations. These operations are analogous to the algebraic operations +, –, × of numbers. 1.8.1 Union of Two Sets SPPU : May-18 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 Discrete Mathematics 1-7 Theory of Sets By Venn diagram A È B is represented as U A B AB 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} 1.8.2 Intersection of Two Sets 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 B AB AB: Fig. 1.8.2 Examples : 1) A = {1, 2, 3, 4, 5}, B = {1, 4} \ A Ç B = {1, 4} = B 2) AÇ f = f 3) A = {a, b, c}, B = {x, y} AÇ B = f ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1-8 Theory of Sets 1.8.3 Disjoint Sets I) Two sets A and B are said to be disjoint sets if AÇ B = f e.g. A = {1, 2}, B = {x, y} are disjoint sets. 1.8.4 Complement of a Set Let A be a given set. The complement of A is denoted by A or A' and defined as A = {x | x Ï A}. By Venn diagram A' is represented as A A or A' Fig. 1.8.3 Examples : 1) A = {Set of even numbers} and È = IR then A or A' = set of odd numbers 2) U = {1, 2, 3, 4, 5,.... 15}, A = {1, 2, 3, 4, 5, 6, 7} A = {8, 9, 10, 11, 12, 13, 14, 15} Properties of complement of sets 1) U = f and f = U 2) ( A) = A 3) A È A = U, AÇ A=f 4) A È U = U, AÇ U=A 1.8.5 Difference of Sets Let A and B be two sets. The difference A-B is the set defined as A – B = {x | x Î A and x Î B } It is also known as the relative complement of B in A. ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1-9 Theory of Sets Similarly, B – A = {x | x Î B and x Ï A} By Venn diagram it is represented as A U B B–A A–B Fig. 1.8.4 Examples : 1) A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6, 7} \ A – B = {1, 2}, B – A = {6, 7} 2) A = Set of prime numbers B = Set of odd integers A – B = {2} 3) A = {a, b, f, {a, c }} A – {a, b} = {{a, c }, f } {a, c} – A = {c} 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 Discrete Mathematics 1 - 10 Theory of Sets 1.8.6 Symmetric Difference of Sets The symmetric difference of two sets A and B is denoted by A Å B and defined as A Å B = {x | x Î A – B or x ¬ B– A } i.e. A Å B = (A – B) È (B– A) If is also denoted by A D B. By Venn diagram it is represented as U A B AB: Fig. 1.8.5 Examples : 1) A = {1, 2, 3, 4, 5, 6}, B = {3, 4, 5, 6, 7, 8} A – B = {1, 2}, B – A = {7, 8} A Å B = {1, 2, 7, 8} 2) A = f, B = {x, f, {f}} A Å B = {x, {f}} 3) A = {a}, B = {a, b} P(A) Å P(B) = {{b}, {a, b}} Properties of symmetric difference 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 Discrete Mathematics 1 - 11 Theory of Sets 1.9 Algebra of Set Operations The set operations obey the same rules as those of numbers such as commutativity, associativity and distributivity. In addition there are similar rules to logic such as Idempotent, Absorption De Morgan's Law's and so on. Theorem : Let A, B, C be any sets then 1) Commutativity with respect to È and Ç a) A È B = B È A b) A Ç B = B Ç A 2) Associativity w.r.t. È and Ç a) A È (BÈ C) = ( A È B) È C b) A Ç (BÇ C) = ( A Ç B) Ç C 3) Distributivity a) A È (BÇ C) = ( A È B) Ç (A È C) b) A Ç (BÈ C) = ( A Ç B) È (A Ç C) 4) Idempotent Laws a) A È A = A b) A Ç A = A 5) Absorption Laws a) A È ( A Ç B) = A b) A Ç ( A È B) = A 6) De Morgan's Laws a) (A È B) = A Ç B b) A Ç B = A È B 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 Discrete Mathematics 1 - 12 Theory of Sets Similarly prove that (A È B) Ç (A È C) Ì A È ( BÇ C) Hence the proof Similarly reader can prove 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 Similarly the reader can prove ( 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. e.g. The dual of A È A = U is A Ç A = f Examples Example 1.10.1 If U = {x Î Z ¢ | – 5 < x < 5} and A = {x Î Z ¢ | – 2 < x < 3} Where Z ¢ = Set of integers. State the elements of the sets. A, A Ç A, AÇ U, AÈ U, A Ç U, AÇ A Solution : A = {x Î Z ¢ (–5 < x < –2) È (3 < x < 5)} ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 13 Theory of Sets AÇ A = A AÇ U = A , AÈ U = U AÇ U = A AÇ A = f Example 1.10.2 If A = {x , y, {x , z } f }. Determine the following sets i) A – {x, z} ii) {{x, z} – A iii) A – {{x, y}} iv) {x, z} – A v) A – P(A) vi) {x} – A vii) A – {x} viii) A – f ix) f – A x) {x , y, f } – A SPPU : Dec.-08, Marks 4 Solution : i) A – {x, z} = {x, y, f } ii) {{x, z }} – A = f iii) A – {{x, y}} = A iv) {x, z} – A = {z} v) A – p(A) = {x, y, {x, z}} vi) {x} – A = f vii) A – {x} = {y, {x, z }, f } viii) A – f = {x, y, {x, z}} ix) f– A = f x) {x, y, f} – A = {{x, z}} Example 1.10.3 If A = {f, b}, construct the following sets A – f, {f} – A, A È P ( A) SPPU : Dec.-19, Marks 03 Solution : We have A = {f, b } \ 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 Discrete Mathematics 1 - 14 Theory of Sets Example 1.10.4 Let U = Z ¢ = Set of all integers A = Set of even integers B = Set of odd integers C = Set of prime numbers Find A – B,, B – A,, C – A, A – C, B – C Solution : A – B = B– B = f B– A = A – A = f C – A = Set of non prime integers which are not even A – C = B – C = Set of odd integers which are not prime = { ± 1, ± 9, ± 15,... } B– C = A – C = Set of even integers which are not prime = { ± 4 , ± 6, ± 8,... } Example 1.10.5 Let A, B, C be three sets and A Ç B = A Ç C A Ç B = A Ç C is it necessary that B = C ? Justify. Solution : 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 Example 1.10.6 Let A, B, C be three sets i) Given that A È B = A È C, is it necessary that B = C ? ii) Given that A Ç B = A Ç C, is it necessary that B = C ? Solution : i) No, Let A = {x, y, z}, B = {x}, C = {z} AÈ B = A and AÈ C = A \ AÈ B = AÈ C = A But B¹ C ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 15 Theory of Sets 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. The powr set of A is the set of all subsets of a set A. Let P(A) be the power set of A and P(B) be the power set of B. If A is a subset of B i.e. A Í B then all elements of A are in B. If X Í P(A) but A Í B Þ X Î P(B) Thence P(A) Í P(B) " ´ ÎP(A) Example 1.10.9 If f is an empty set then find p( f), p( p( f)) p( p( p( f))) 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 Discrete Mathematics 1 - 16 Theory of Sets Example 1.10.10 Show that [ A Ç ( B È A )] È B = B Solution : [A Ç (BÈ A)] È B = [(A Ç B) È ( A Ç A)] È B = [(A Ç B) È f] È B = (A Ç B) È B = B Example 1.10.11 Prove that A Ç ( B – C )] Ì A – ( B Ç C ) Solution : Let x Î A Ç (B– C) then Þ 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 Discrete Mathematics 1 - 17 Theory of Sets 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. ii) Consider the following Venn diagrams. A B U U A B C C c 1 ABC= 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 From (2) and (5) (A  B  C)c = (A  C)c  (A  B)c C c c 5 (A  B)  (A  C) Fig. 1.10.3 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 18 Theory of Sets A U A U B B 1 UA= 2 BA= 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 Example 1.10.15 Using Venn diagram show that : A È ( B Ç C) = ( A È B ) Ç ( A È C) SPPU : May-05, Marks 4 Solution : Consider the following venn diagrams B = {x / x Ï B} 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 AB= and ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 19 Theory of Sets 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) Example 1.10.16 Using Venn diagram, prove or disprove. i) A Å (B Å C) = (A Å B) Å C ii) A Ç B Ç C = A - [( A - B) È ( A - C)] SPPU : May-06, Marks 4 Solution : i) A Å B = (A È B) - (A Ç B) A Å B : elements which are either in A or in B but not in both A and 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 Discrete Mathematics 1 - 20 Theory of Sets ii) A Ç B Ç C = A - [(A - B) È (A - C)] A B X A B X C C ABC= A–B= 1 2 A B X A B X C C A–C= (A – B)  (A – C) = 3 4 and A B C A – [(A–B)  (A–C)] = 5 From 1 and 5 A Ç B Ç C = A - [(A - B) È (A - C)] Example 1.10.17 Using Venn diagrams show that A È ( B Ç C) = ( A È B) Ç ( A È C) SPPU : May-08, Dec.-12, Marks 3 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 21 Theory of Sets Solution : A B X A B X C C BC= A  (B  C) = 1 2 A B X A B X C C AB= AC= 3 4 A B X C (AB)  (AC) = 5 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 Discrete Mathematics 1 - 22 Theory of Sets 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 = Æ Example 1.10.19 Prove the following using Venn diagram. A Ç (B Å C) = ( A Ç B) Å ( A Ç C) SPPU : May-08, 14, Dec.-12, Marks 3 Solution : A X A X B B C C BC= A  (B  C) = 1 2 A B X A B X C C AB= AC= 4 3 A B X C (AB)  (AC)= 5 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 23 Theory of Sets From 2 and 5 A Ç (B Å C) = (A Ç B) Å (A Ç C) 1.11 Cardinality of Sets In the analysis of computer algorithms, we required to count the number of operations executed by various algorithms. This is necessary to estimate the cost effectiveness of a particular algorithm. Hence we require to study the cardinality of finite sets and understand related properties. Definition : Let A be any finite set. The number of elements in the set A, is called the cardinality of the set A. It is denoted by |A| or n(A). e.g. If A = {x, y, z, p} then |A| = 4 Theorem 1 : If A = f then |A| = 0 Theorem 2 : If A Ì B then |A| £ |B| Theorem 3 : (Addition Principle) 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 Let us assume that A ¹ f, B¹ f Suppose A = { a 1 , a 2 ,.... a n }, B = { b1 , b 2 ,.... b m } \ A Ç B = f, |A| = n, |B| = m \ A È B = { a 1 , a 2 ,... a n , b1 , b 2 ,.... b m } \ |A È B| = m + n = |A| + |B|. Hence the proof Theorem 4 : Let A1 , A 2 , A 3 ,.... A n be mutually disjoint finite sets then |A1 È A 2 È A 3 È... È A n | = |A1| +|A 2|+|A 3|+... +|A n | Theorem 5 : If A is finite set and B is any set then |A – B| = |A|–|A Ç B| A B Proof : By Venn diagram A = (A – B) È (A Ç B) (A – B) Ç (A Ç B) = f A–B \ By addition principle |A| = |A – B|+|A Ç B| Fig. 1.11.1 Þ |A – B| = |A|–|A Ç B| ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 24 Theory of Sets 1.12 The Principle of Inclusion and Exclusion for Sets SPPU : Dec.-04, 05, 07, 08, 10, 13, 14, 15, 19 May-05, 06, 07, 08, 14, 15, 17, 19 Theorem 6 : (Principle of Inclusion - Exclusion for 2 sets) Let A and B be finite sets then |A È B| = |A|+|B|–|A Ç B| A B Proof : By venn diagram A È B = ( A – B) È B A–B AB As A–B and B are disjoint sets. |A È B| = | A – B| +| B| = | A| – | A Ç B| +| B| |A È B| = | A| +| B| – | A Ç B| Fig. 1.12.1 Principle of Inclusion-Exclusion for three sets. Theorem 7 : Let A, B, C be finite sets. Then |A È BÈ C| = | A| +| B| +|C| – | A Ç B| –|A Ç C| –|BÇ C| Proof Let D = BÈ C \ |A È D| = |A|+|D| = |A Ç D| and |D| = |BÈ C| = |B|+|C|–|BÇ C| \ |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|–|A Ç B | –|A Ç C| –|B Ç C| + | A Ç B Ç C| Theorem 8 : Let A, B, C, D be finite sets then |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 Discrete Mathematics 1 - 25 Theory of Sets 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 by 3, B denotes the set of integers 1 to 300 divisible by 5, C denotes the set of integers 1 to 300 divisible. by 7 |A| = é 300ù = 100 , |B| = é 300ù = 60, |C| = é 300ù = 42, |A Ç B| = é 300 ù = 20 êë 3 úû êë 5 úû êë 7 úû êë 3 ´ 5úû 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 Hence 160 integers between 1 – 300 are not divisible by 3, not by 5. | 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 We have |A| = 15, |B| = 8, |C| = 6, |A Ç BÇ C| = 3 |A È BÈ C| = | A| +| B| +|C| – | A Ç B| – | A Ç C| – | BÇ C| +| A Ç BÇ C| = 15 +8 +6 – | A Ç B| – | A Ç C| – | BÇ C| +3 = 32 – | A Ç B| – | A Ç C| – | BÇ C| But |A Ç B| ³ |A Ç BÇ C|, |BÇ C| ³ |A Ç BÇ C| and |A Ç C| ³ |A Ç BÇ C| ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 26 Theory of Sets \ |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. Example 1.12.3 How many integers between 1 to 2000 are divisible by 2 or 3 or 5 or 7. 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. 2000ù A = é = 1000 êë 2 úû 2000ù B = é = 666 êë 3 úû 2000ù C = é = 400 êë 5 úû 2000ù D = é = 285 êë 7 úû 2000ù AÇB = é = 333 êë 2 ´ 3 úû 2000ù AÇC = é = 200 êë 2 ´ 5 úû 2000ù AÇD = é = 142 êë 2 ´ 7 úû 2000ù BÇ C = é = 133 êë 3 ´ 5 úû BÇ D = é 2000ù = 95 êë 3 ´ 7 úû 2000ù CÇ D = é = 57 êë 5 ´ 7 úû ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 27 Theory of Sets 2000 ù A Ç BÇ C = é = 66 êë 2 ´ 3 ´ 5úû 2000 ù A Ç BÇ D = é = 47 êë 2 ´ 3 ´ 7 úû 2000 ù A Ç CÇ D = é = 28 êë 2 ´ 5 ´ 7 úû 2000 ù BÇ CÇ D = é = 19 êë 3 ´ 5 ´ 7 úû 2000 ù A Ç BÇ CÇ D = é = 9 êë 2 ´ 3 ´ 5 ´ 7 úû Number of elements divisible by 2 or 3 or 5 or 7 are A È B È C È D. From inclusion exclusion principle A È BÈ CÈ D = A + B + C + D – [ A Ç B + BÇ C + A Ç C + A Ç D + BÇ D + CÇ D ] + [ A Ç B Ç C + A Ç B Ç D +|A Ç C Ç D|+|B Ç C Ç D|] – [ A Ç BÇ CÇ D ] \ A È BÈ CÈ D = 1000 + 666 + 400 + 285 – [333 + 200 + 142 + 133 + 95 + 57] + [66 + 47 + 28 + 19] – 9 = 2351 – 960 + 160 – 9 = 1542 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. Let B be the set of students, taken a cs course Let C be the set of students, taken a business course. ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 28 Theory of Sets \ We have U = 260, |A| = 64, |B| = 94 | C| = 58, A Ç C| = 28, |A Ç B| = 26 |B Ç C| = 22, |A Ç B Ç C| = 14, We have, |A È B È C| = |A| + |B| + |C| – |A Ç B| – |A Ç C} – |B Ç C| + |A Ç B Ç C| = 64 + 94 + 58 – 28 – 26 – 22 + 14 = 154 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 Discrete Mathematics 1 - 29 Theory of Sets 70 = 97 – + A Ç B Ç C 70 – 65 = A Ç BÇ C Þ A Ç BÇ C = 5 5 students study all 3 subjects. b) Number of students studying exactly one subject. X A B C Number of students studying only mathematics is A - A Ç B - A Ç C + A Ç BÇ C = 32 – 7 – 15 + 5 = 15 Number of students studying only physics is B - BÇ A - BÇ C + A Ç BÇ C = 20 – 7 – 10 + 5 = 8 Number of students studying only biology is C - A Ç C - BÇ C + A Ç BÇ C = 45 – 15 – 10 + 5 = 25 \ Number of students studying exactly one subject = 15 + 8 + 25 = 48 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 30 Theory of Sets 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 Let A be the number of Democrats. A = 595 B be the number of people who wear glasses. B = 595 C be the number of people who like icecream. C = 550 AÇB = 395 AÇC = 350 BÇ C = 400 A Ç BÇ C = 250 A È BÈ C = A + B + C -[ A Ç B + BÇ C + A Ç C ] + A Ç BÇ C = 595 + 595 + 550 – [395 + 350 + 400] + 250 A È BÈ C = 845 845 people are either Democrats or wear glasses or icecream. Þ 1000 – 845 = 155 people are neither Democrats, nor wear glasses nor like icecream. 1000 A B C ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 31 Theory of Sets 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 C 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 Discrete Mathematics 1 - 32 Theory of Sets 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 X 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 i) Number of students who got A in both the examination will be F Ç S. Now FÈ S = F + S - FÇ S 132 = 104 + 84 – F Ç S \ FÇ S = 56 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 33 Theory of Sets ii) F = S The total number of students who got A in exactly one examination is F - S È S - F i.e. F Å S and |F Å S| = 160 16 students did not get A in either examination \ (F È S) ¢ = 16 Þ FÈ S = X – (F È S) ¢ Þ FÈ S = 200 – 16 = 184 Now FÈ S = F Å S + FÇ S As F Å S and F Ç S are pairwise disjoint sets. Þ 184 = 160 + F Ç S Þ FÇ S = 184 – 160 = 24 \ FÈ S = F + S - FÇ S 184 = 2 F - 24 2 F = 208 Þ F = 104 and F = S Þ S = 104 \ Number of students who got A in first examination = F - FÇ S = 104 – 24 = 80 Similarly number of students who got A in second examination = |S| –| F Ç S | = 104 - 24 = 80 Example 1.12.9 Consider a set of integers 1 to 500. Find i) How many of these numbers are divisible by 3 or 5 or by 11 ? Dec.-14 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. B denote numbers divisible by 5. C denote numbers divisible by 11. A denotes cardinality of A similarly B and C denotes cardinality of B and C. ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 34 Theory of Sets 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 = 166 + 100 + 45 – [13 + 15 + 9] + 3 = 257 ii) X A B C Number of integers divisible by 3 or by 11 but not by all 3, 5 and 11. = A È C - A Ç BÇ C = [ A + C - A Ç C ] - A Ç BÇ C = 166 + 45 – 15 – 3 = 193 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 35 Theory of Sets iii) X A B C Number of integers divisible by 3 or 11 but not by 5. = A È BÈ C – B = 257 – 100 = 157 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 T denote the number of people who read time magazine. \ T = 26 F denote the number of people who read fortune magazine. \ F = 26 NÇ T = 11 NÇ F = 9 TÇ F = 8 N¢Ç T¢Ç F¢ = 8 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 36 Theory of Sets Using DeMorgan's law N¢Ç T¢Ç F¢ = X - NÈ TÈ F 8 = 60 – N È T È F Þ NÈ TÈ F = 52 i) NÈ TÈ F = N + T + F -[ NÇ T + NÇ F + TÇ F ] + NÇ TÇ F Þ 52 = 25 + 26 + 26 – [11 + 9 + 8] + N Ç T Ç F Þ NÇ TÇ F = 3 ii) 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 Þ People read only N and F = 9 – 3 i.e. 6. Also, N = 25, which includes N Ç T , N Ç F and N Ç T Ç F. People who read only N = N – [ NÇ T + NÇ F ] + NÇ TÇ F = 25 – [11 + 9] + 3 \ People who read only N = 8 …(1) People who read only T = T – [ N Ç T + T Ç F ] + N Ç T Ç F = 26 – [11 + 8] + 3 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 37 Theory of Sets \ People who read only T = 10 … (2) People who read only F = F – [ NÇ F + TÇ F ]+ NÇ TÇ F = 26 – [9 + 8] + 3 \ People who read only F = 12 … (3) iii) Number of people who reads exactly one magazine = Equation [(1) + (2) + (3) ] = 8 + 10 + 12 = 30 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 Hence 8 students study all three languages. ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 38 Theory of Sets ii) F G 28 12 18 8 17 7 10 R Explanation As FÇ G Ç R = 8 Students who study F and G but not all 3 will be FÇ G – FÇ G Ç R = 20 – 8 = 12 … (1) Students who study F and R but not all 3 will be FÇ R – FÇ G Ç R = 25 – 8 = 17 … (2) Students who study G and R but not all 3 will be GÇ R – FÇ G Ç R = 15 – 8 = 7 … (3) Students who study only F but not G and not R. = F -[ FÇ G + FÇ R ] + FÇ G Ç R = 65 – [20 + 25] + 8 = 28 … (4) Students who study only G but not F and not R = G -[ FÇ G + G Ç R ] + FÇ G Ç R = 45 – [20 + 15] + 8 = 18 … (5) Students who study only R but not F and not G. = R -[ FÇ R + G Ç R ] + FÇ G Ç R = 42 – [25 + 15] + 8 = 10 … (6) ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 39 Theory of Sets iii) a) Number of students who study exactly one language = Equation (4) + Equation (5) + Equation (6) = 28 + 18 + 10 = 56 b) Number of students who study exactly two languages. = Equation (1) + Equation (2) + Equation (3) = 12 + 17 + 7 = 36 Example 1.12.12 Out of the integers 1 to 1000. i) How many of them are not divisible by 3, nor by 5, nor by 7 ? ii) How many are not divisible by 5 and 7 but divisible by 3 ? SPPU : May-06, 08, 14, Marks 6, May-19, Marks 13 Solution : i) Let A denote numbers divisible by 3. B denote numbers divisible by 5. and C denote numbers divisible by 7. 1000ù A = é = 333 êë 3 úû 1000ù B = é = 200 êë 5 úû 1000ù C = é = 142 êë 7 úû 1000ù AÇB = é = 66 êë 3 ´ 5 úû 1000ù AÇC = é = 47 êë 3 ´ 7 úû 1000ù BÇ C = é = 28 êë 5 ´ 7 úû 1000 ù A Ç BÇ C = é = 9 êë 3 ´ 5 ´ 7 úû A È BÈ C = A + B + C -[ A Ç B + A Ç C + BÇ C ] + A Ç BÇ C = 333 + 200 + 142 – [66 + 47 + 28] + 9 = 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 Discrete Mathematics 1 - 40 Theory of Sets = |A ¢ Ç B ¢ Ç C¢| = X – A È BÈ C = 1000 – 543 = 457 ii) A B C Number of integers divisible by 3 but not by 5 and not by 7 is|A Ç B ¢ Ç C¢|. |A Ç B ¢ Ç C¢| = |A Ç (B È C) ¢| = A -[ A Ç B + A Ç C ]+ A Ç BÇ C = 333 – [66 + 47] + 9 = 229 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. Let M denote set of students studying mathematics. P denote set of students studying physics and C denote set of students studying chemistry. Then X = 55, M = 23, P = 24, C = 19, M Ç P = 12, MÇ C = 9, P Ç C = 7 M Ç PÇ C = 4 i) M È PÈ C = M + P + C - [ M Ç P + M Ç C + PÇ C ] + M Ç PÇ C = 23 + 24 + 19 – [12 + 9 + 7] + 4 = 42 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 41 Theory of Sets 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) Hence number of students studying exactly one subject = 6 + 9 + 7 = 22 iii) Number of students studying mathematics and physics but not chemistry = M Ç P – M Ç PÇ C = 12 – 4 = 8 … (4) Number of students studying physics and chemistry but not mathematics = PÇ C - M Ç P Ç C = 7–4=3 … (5) Number of students studying mathematics and chemistry but not physics = M Ç C – M Ç PÇ C = 9–4=5 … (6) Hence number of students studying exactly two subjects = 8 + 3 + 5 = 16 X M P 6 8 9 4 5 3 7 C ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 42 Theory of Sets 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 Let A denote number of students taking part in group discussion. B denote number of students taking part in debate and C denote number of students taking part in quiz. A È B È C = 100, A = 65, B = 45, C = 42, A Ç B = 20, A Ç C = 25, B Ç C = 15. i) A È BÈ C = A + B + C - [ A Ç B + A Ç C + BÇ C ] + A Ç BÇ C 100 = 65 + 45 + 42 – [20 + 25 + 15] + A Ç B Ç C Þ A Ç BÇ C = 8 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) Hence number of students doing exactly one activity = 28 + 18 + 10 = 56 ® TECHNICAL PUBLICATIONS - An up thrust for knowledge Discrete Mathematics 1 - 43 Theory of Sets 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. B denote the set of students who know ‘C’. and C denote the set of students who know PASCAL. and X denote universal set. Then X = 80, A = 50, B = 55, C = 46 A Ç B = 37, B Ç C = 28, A Ç C = 25 A ¢Ç B¢Ç C¢ = 7 Hence (A È B È C) ¢ = 7 Also A È B È C = X - (A È B È C) ¢ Hence A È B È C = 80 – 7 = 73 i) A È BÈ C = A + B + C -[ A Ç B + A Ç C + BÇ C ] + A Ç BÇ C 73 = 50 + 55 + 46 – [37 + 28 + 25] + A Ç B Ç C Þ A Ç B Ç C = 12 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 Discrete Mathematics 1 - 44 Theory of Sets = 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) Hence number of students who know exactly two languages. = 25 + 13 + 16 = 54 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) Hence number of students who know only one language = 0 + 2 + 5 = 7 X B A 25 2 12 13 16 5 C 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 Discrete Mathematics 1 - 45 Theory of Sets Solution : Let F denote the set of people who watch football. H denote the set of people who watch hockey and B denote the set o