## Lecture Notes On Discrete Mathematics-Free PDF

• Date:08 Dec 2019
• Views:78
• Pages:263
• Size:1.80 MB

Share Pdf : Lecture Notes On Discrete Mathematics

Report CopyRight/DMCA Form For : Lecture Notes On Discrete Mathematics

Transcription:

1 Basic Set Theory 7,1 1 Sets 7,1 2 Operations on sets 9. 1 3 Relations 11,1 4 Functions 15,1 5 Composition of functions 18. 1 6 Equivalence relation 19,2 The Natural Number System 25. 2 1 Peano Axioms 25, 2 2 Other forms of Principle of Mathematical Induction 28. 2 3 Applications of Principle of Mathematical Induction 31. 2 4 Well Ordering Property of Natural Numbers 33,2 5 Recursion Theorem 34.
2 6 Construction of Integers 36,2 7 Construction of Rational Numbers 40. 3 Countable and Uncountable Sets 43,3 1 Finite and infinite sets 43. 3 2 Families of sets 46,3 3 Constructing bijections 49. 3 4 Cantor Schro der Bernstein Theorem 51,3 5 Countable and uncountable sets 55. 4 Elementary Number Theory 61,4 1 Division algorithm and its applications 61.
4 2 Modular arithmetic 65,4 3 Chinese Remainder Theorem 68. 5 Combinatorics I 71,5 1 Addition and multiplication rules 71. 5 2 Permutations and combinations 73, 5 2 1 Counting words made with elements of a set S 73. 5 2 2 Counting words with distinct letters made with elements of a set S 74. 5 2 3 Counting words where letters may repeat 75,5 2 4 Counting subsets 76. 5 2 5 Pascal s identity and its combinatorial proof 77. 4 CONTENTS,5 2 6 Counting in two ways 78,5 3 Solutions in non negative integers 80.
5 4 Binomial and multinomial theorems 83,5 5 Circular arrangements 86. 5 6 Set partitions 91,5 7 Number partitions 95,5 8 Lattice paths and Catalan numbers 98. 6 Combinatorics II 103,6 1 Pigeonhole Principle 103. 6 2 Principle of Inclusion and Exclusion 107,6 3 Generating Functions 110. 6 3 1 Generating Functions and Partitions of n 116. 6 4 Recurrence Relation 119, 6 5 Generating Function from Recurrence Relation 124.
7 Introduction to Logic 133,7 1 Logic of Statements SL 133. 7 2 Formulas and truth values in SL 134,7 3 Equivalence and Normal forms in SL 137. 7 4 Inferences in SL 143,7 5 Predicate logic PL 149. 7 6 Equivalences and Validity in PL 153,7 7 Inferences in PL 156. 8 Partially Ordered Sets Lattices and Boolean Algebra 161. 8 1 Partial Orders 161,8 2 Lattices 169,8 3 Boolean Algebras 176.
8 4 Axiom of choice and its equivalents 181,9 Graphs I 191. 9 1 Basic concepts 191,9 2 Connectedness 197,9 3 Isomorphism in graphs 200. 9 4 Trees 202,9 5 Eulerian graphs 208,9 6 Hamiltonian graphs 210. 9 7 Bipartite graphs 214,9 8 Planar graphs 215,9 9 Vertex coloring 219. 10 Graphs II 221,10 1 Connectivity 221,10 2 Matching in graphs 223.
10 3 Ramsey numbers 226,10 4 Degree sequence 227,CONTENTS 5. 10 5 Representing graphs with matrices 228,11 Polya Theory 231. 11 1 Groups 231,11 2 Lagrange s Theorem 240,11 3 Group action 244. 11 4 The Cycle index polynomial 248,11 5 Polya s inventory polynomial 251. 6 CONTENTS,Basic Set Theory, The following notations will be followed throughout the book.
1 The empty set denoted is the set that has no element. 2 N 1 2 the set of Natural numbers,3 W 0 1 2 the set of whole numbers. 4 Z 0 1 1 2 2 the set of Integers,5 Q pq p q Z q 6 0 the set of Rational numbers. 6 R the set of Real numbers and,7 C the set of Complex numbers. This chapter will be devoted to understanding set theory relations functions We start with the basic. set theory, Mathematicians over the last two centuries have been used to the idea of considering a collection of. objects numbers as a single entity These entities are what are typically called sets The technique of. using the concept of a set to answer questions is hardly new It has been in use since ancient times. However the rigorous treatment of sets happened only in the 19 th century due to the German math. ematician Georg Cantor He was solely responsible in ensuring that sets had a home in mathematics. Cantor developed the concept of the set during his study of the trigonometric series which is now. known as the limit point or the derived set operator He developed two types of transfinite numbers. namely transfinite ordinals and transfinite cardinals His new and path breaking ideas were not well. received by his contemporaries Further from his definition of a set a number of contradictions and. paradoxes arose One of the most famous paradoxes is the Russell s Paradox due to Bertrand Russell. in 1918 This paradox amongst others opened the stage for the development of axiomatic set theory. The interested reader may refer to Katz 8, In this book we will consider the intuitive or naive view point of sets The notion of a set is taken.
as a primitive and so we will not try to define it explicitly We only give an informal description of. sets and then proceed to establish their properties. A well defined collection of distinct objects can be considered to be a set Thus the principal. property of a set is that of membership or belonging Well defined in this context would enable. us to determine whether a particular object is a member of a set or not. 8 CHAPTER 1 BASIC SET THEORY, Members of the collection comprising the set are also referred to as elements of the set Elements. of a set can be just about anything from real physical objects to abstract mathematical objects An. important feature of a set is that its elements are distinct or uniquely identifiable. A set is typically expressed by curly braces enclosing its elements If A is a set and a is an. element of it we write a A The fact that a is not an element of A is written as a 6 A For instance. if A is the set 1 4 9 2 then 1 A 4 A 2 A and 9 A But 7 6 A 6 A the English word. four is not in A etc, Example 1 1 1 1 Let X apple tomato orange Here orange X but potato 6 X. 2 X a1 a2 a10 Then a100 6 X, 3 Observe that the sets 1 2 3 3 1 2 and digits in the number 12321 are the same as the. order in which the elements appear doesn t matter, We now address the idea of distinctness of elements of a set which comes with its own subtleties. Example 1 1 2 1 Consider the list of digits 1 2 1 4 2 Is it a set. 2 Let X 1 2 3 4 5 6 7 8 9 10 Then X is the set of first 10 natural numbers Or equivalently. X is the set of integers between 0 and 11, Definition 1 1 3 The set S that contains no element is called the empty set or the null set and.
is denoted by or A set that has only one element is called a singleton set. One has three main ways for specifying a set They are. 1 Listing all its elements list notation e g X 2 4 6 8 10 Then X is the set of even integers. between 0 and 12, 2 Stating a property with notation predicate notation e g. a X x x is a prime number This is read as X is the set of all x such that x is a prime. number Here x is a variable and stands for any object that meets the criteria after the. b The set X 2 4 6 8 10 in the predicate notation can be written as. i X x 0 x 10 x is an even integer or,ii X x 1 x 11 x is an even integer or. iii x x 2 x 10 x is an even integer etc, Note that the above expressions are certain rules that help in defining the elements of the set. X In general one writes X x p x or X x p x to denote the set of all elements x. variable such that property p x holds In the above note that colon is sometimes replaced. 3 Defining a set of rules which generate its members recursive notation e g let. X x x is an even integer greater than 3,Then X can also be specified by. b whenever x X then x 2 X and, c every element of X satisfies the above two rules.
1 2 OPERATIONS ON SETS 9, In the recursive definition of a set the first rule is the basis of recursion the second rule gives. a method to generate new element s from the elements already determined and the third rule. binds or restricts the defined set to the elements generated by the first two rules The third rule. should always be there But in practice it is left implicit At this stage one should make it. Definition 1 1 4 Let X and Y be two sets, 1 Suppose X is the set such that whenever x X then x Y as well Here X is said to be a. subset of the set Y and is denoted by X Y When there exists x X such that x 6 Y then. we say that X is not a subset of Y and we write X 6 Y. 2 If X Y and Y X then X and Y are said to be equal and is denoted by X Y. 3 If X Y and X 6 Y then X is called a proper subset of Y. Thus X is a proper subset of Y if and only if X Y and X 6 Y. Example 1 1 5 1 For any set X we see that X X Thus Also X Hence the. empty set is a subset of every set It thus follows that there is only one empty set. 2 We know that N W Z Q R C,3 Note that 6,4 Let X a b c Then a X but a X Also a 6 X. 5 Notice that a 6 a and a 6 a though a a a and also a a a. We now mention some set operations that enable us in generating new sets from existing ones. 1 2 Operations on sets,Definition 1 2 1 Let X and Y be two sets. 1 The union of X and Y denoted by X Y is the set that consists of all elements of X and also. all elements of Y More specifically X Y x x X or x Y. 2 The intersection of X and Y denoted by X Y is the set of all common elements of X and. Y More specifically X Y x x X and x Y,3 The sets X and Y are said to be disjoint if X Y.
Example 1 2 2 1 Let A 1 2 4 18 and B x x is an integer 0 x 5 Then. A B 1 2 3 4 5 18 and A B 1 2 4,2 Let S x R 0 x 1 and T x R 5 x 7 Then. S T x R 0 x 7 and S T x R 5 x 1,3 Let X b c b c b and Y a b c Then. X Y b and X Y a b c b c b c, We now state a few properties related to the union and intersection of sets. Lemma 1 2 3 Let R S and T be sets Then, 1 a S T T S and S T T S union and intersection are commutative operations. 10 CHAPTER 1 BASIC SET THEORY, b R S T R S T and R S T R S T union and intersection are.
associative operations,c S S T T S T,d S T S S T T. f S S S S S, 2 Distributive laws combines union and intersection. a R S T R S R T union distributes over intersection. b R S T R S R T intersection distributes over union. Proof 2a Let x R S T Then x R or x S T If x R then x R S and x R T. Thus x R S R T If x 6 R then x S T So x S and x T Here x R S and. x R T Thus x R S R T In other words R S T R S R T, Now let y R S R T Then y R S and y R T Now if y R S then either. y R or y S or both, If y R then y R S T If y 6 R then the conditions y R S and y R T imply that y S. and y T Thus y S T and hence y R S T This shows that R S R T R S T. and thereby proving the first distributive law The remaining proofs are left as exercises. Exercise 1 2 4 1 Complete the proof of Lemma 1 2 3. 2 Prove the following,a S S T S S T S,b S T if and only if S T T.
c If R T and S T then R S T,d If R S and R T then R S T. e If S T then R S R T and R S R T,f If S T 6 then either S 6 or T 6. g If S T 6 then both S 6 and T 6,h S T if and only if S T S T. Definition 1 2 5 Let X and Y be two sets, 1 The set difference of X and Y denoted by X Y is defined by X Y x X x 6 Y. 2 The set X Y Y X denoted by X Y is called the symmetric difference of X and Y. Example 1 2 6 1 Let A 1 2 4 18 and B x Z 0 x 5 Then. A B 18 B A 3 5 and A B 3 5 18,2 Let S x R 0 x 1 and T x R 0 5 x 7 Then.
S T x R 0 x 0 5 and T S x R 1 x 7,3 Let X b c b c b and Y a b c Then. X Y b c b c Y X a c and X Y a c b c b c,1 3 RELATIONS 11. In naive set theory all sets are essentially defined to be subsets of some reference set referred to. as the universal set and is denoted by U We now define the complement of a set. Definition 1 2 7 Let U be the universal set and X U Then the complement of X denoted by. X c is defined by X c x U x 6 X,We state more properties of sets. Lemma 1 2 8 Let U be the universal set and S T U Then. 1 U c and c U,2 S S c U and S S c,3 S U U and S U S. 5 S S c if and only if S,6 S T if and only if T c S c.
7 S T c if and only if S T and S T U,8 S T S T c and T S T S c. 9 S T S T S T,10 De Morgan s Laws,a S T c S c T c,b S T c S c T c. The De Morgan s laws help us to convert arbitrary set expressions into those that involve only. complements and unions or only complements and intersections. Exercise 1 2 9 Let S and T be subsets of a universal set U. 1 Then prove Lemma 1 2 8,2 Suppose that S T T Is S. Definition 1 2 10 Let X be a set Then the set that contains all subsets of X is called the power. set of X and is denoted by P X or 2X,Example 1 2 11 1 Let X Then P P X X. 2 Let X Then P P X X,3 Let X a b c Then P X a b c a b a c b c a b c.
4 Let X b c b c Then P X b c b c b c b c,1 3 Relations. In this section we introduce the set theoretic concepts of relations and functions We will use these. concepts to relate different sets This method also helps in constructing new sets from existing ones. 12 CHAPTER 1 BASIC SET THEORY, Definition 1 3 1 Let X and Y be two sets Then their Cartesian product denoted by X Y is. defined as X Y a b a X b Y The elements of X Y are also called ordered pairs. with the elements of X as the first entry and elements of Y as the second entry Thus. a1 b1 a2 b2 if and only if a1 a2 and b1 b2,Example 1 3 2 1 Let X a b c and Y 1 2 3 4 Then. X X a a a b a c b a b b b c c a c b c c, X Y a 1 a 2 a 3 a 4 b 1 b 2 b 3 b 4 c 1 c 2 c 3 c 4. 2 The Euclidean plane denoted by R2 R R x y x y R, 3 By convention Y X In fact X Y if and only if X or Y.
Remark 1 3 3 Let X and Y be two nonempty sets Then X Y can also be defined as follows. Let x X and y Y and think of x y as the set x x y i e we have a new set in which an. element a set formed using the first element of the ordered pair is. DRAFT 1 2 OPERATIONS ON SETS 9 In the recursive de nition of a set the rst rule is the basis of recursion the second rule gives a method to generate new element s from the elements already determined and the third rule