Introduction To Discrete Mathematics

Discrete Mathematics covers such a wide range of topics that it is difficult to give a simple definition of the subject. Whereas calculus deals with continuous or even smooth objects, discrete mathematics deals with things that come in "chunks" that can be counted. We will be a lot more precise about just what sort of "chunks" we are dealing with in the later chapters.

If your mathematical background is only high school calculus you could well believe that mathematics is only about numbers functions and formulas for solving problems. If this is the case, the topics in this book may be quite a surprise because for mathemati­cians, computer scientists and engineers, Discrete Mathematics includes logic, set theory, enumeration, networks, automata, for­mal languages and many other discrete structures. That is what this book is about.

On the other hand, in 19 lectures we can only present an introduction to the subject and we must leave other important topics such as graph theory, error-correcting codes, discrete probability theory and applications to theoretical computer science to a sec­ond or third course.

The topics covered are set theory, logic, Boolean algebra, count­ing, generating functions, recurrence relations, finite automata and formal languages with a lot of emphasis on counting.

The set theory and logic is basic material which will be useful many courses besides Discrete Mathematics. Counting problems which look quite hard when stated in ordinary English can often be solved easily when translated into the language of set theory. We give many examples that reduce to counting the number of functions of various types between sets, or counting the number of subsets of a set.