Discrete Mathematics PDF

DISCRETE MATHEMATICS  INTRODUCTION "Discrete Math" is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than...

DISCRETE MATHEMATICS  INTRODUCTION "Discrete Math" is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous". It is increasingly being applied in the practical fields of mathematics and computer science. It is a very good tool for improving reasoning and problem- solving capabilities.  Mathematics can be broadly classified into two categories − Continuous Mathematics − It is based upon continuous number line or the real numbers. It is characterized by the fact that between any two numbers, there are almost always an infinite set of numbers. For example, a function in continuous mathematics can be plotted in a smooth curve without breaks. Discrete Mathematics − It involves distinct values; i.e. between any two points, there are a countable number of points. For example, if we have a finite set of objects, the function can be defined as a list of ordered pairs having these objects, and can be presented as a complete list of those pairs.  TOPICS IN DISCRETE MATHEMATICS Though there cannot be a definite number of branches of Discrete Mathematics , following are some of them− Sets, Relations and Functions Mathematical Logic Group theory Counting Theory Probability Mathematical Induction and Recurrence Relations Graph Theory Trees Boolean Algebra  SETS German mathematician G. Cantor introduced the concept of sets. He had defined a set as a collection of definite and distinguishable objects selected by the means of certain rules or description. Set theory forms the basis of several other fields of study like counting theory, relations, graph theory and finite state machines  SET - DEFINITION A set is an unordered collection of objects, called elements or members of the set. A set is said to contain its elements. We write a ∈ A to denote that a is an element of the set A. The notation a ∉ A denotes that a is not an element of the set A. It is common for sets to be denoted using uppercase letters. Lowercase letters are usually used to denote elements of sets.  REPRESENTATION OF A SET Sets can be represented in two ways − Roster or Tabular Form Set Builder Notation  ROSTER OR TABULAR FORM The set is represented by listing all the elements comprising it. The elements are enclosed within braces and separated by commas. EXAMPLE 1 The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}. EXAMPLE 2 The set O of odd positive integers less than 10 can be expressed by O = {1, 3, 5, 7, 9}.  Set Builder Notation Another way to describe a set is to use set builder notation. We characterize all those elements in the set by stating the property or properties they must have to be members. For instance, the set O of all odd positive integers less than 10 can be written as O = {x | x is an odd positive integer less than 10}, or, specifying the universe as the set of positive integers, as O = {x ∈ Z+ | x is odd and x < 10}. We often use this type of notation to describe sets when it is impossible to list all the elements of the set. For instance, the set Q+ of all positive rational numbers can be written as Q+ = {x ∈ R | x = p q , for some positive integers p and q}. SOME IMPORTANT SETS N − the set of all natural numbers = {1,2,3,4,.....} Z − the set of all integers = {.....,−3,−2,−1,0,1,2,3,.....} Z+ − the set of all positive integers Q − the set of all rational numbers R − the set of all real numbers W − the set of all whole numbers  CARDINALITY OF A SET Cardinality of a set S, denoted by |S|, is the number of elements of the set. The number is also referred as the cardinal number. If a set has an infinite number of elements, its cardinality is ∞. Example − |{1,4,3,5}|=4,|{1,2,3,4,5,…}|=∞ If there are two sets X and Y, |X|=|Y| denotes two sets X and Y having same cardinality. It occurs when the number of elements in X is exactly equal to the number of elements in Y. In this case, there exists a bijective function ‘f’ from X to Y. |X|≤|Y| denotes that set X’s cardinality is less than or equal to set Y’s cardinality. It occurs when number of elements in X is less than or equal to that of Y. Here, there exists an injective function ‘f’ from X to Y. |X|=n0) we prove P(k+1) is also true, then P(n) is true for all natural numbers n>=n0. Step 1 is called as the basis of induction, step 2 is called as the induction step. The assumption that P(n) is true for n=k is called as the induction hypothesis. Example on Mathematical Induction Prove that 5n -1 is divisible by 4 for n>=1.