PREFACE BOOK “FOUNDATIONS OF DISCRETE MATHEMATICS”

Foundations of Discrete Mathematics introduces students to basic ideas and techniques of discrete mathematics. The text presumes no background in calculus or computer science, and is designed for a one– or two–semester course to be taken by students with the same mathematical maturity that is expected of calculus students. Two years of high school algebra is the only prerequisite, and students whose mathematical background exceeds our minimum requirements should be able to skim, or skip entirely, much of the material of the first four chapters.

Paul Halmos once observed: ”Calculus books are bad because there is no subject as calculus; it is not a subject because it is many subjects.“ We believe that Halmos could have leveled this same charge at discrete mathematics texts. Certainly to most college students the distinction between discrete mathematics and other mathematics is not well understood, and so there is the danger that a course in discrete mathematics will be perceived as a hodgepodge of unrelated topics or as a mathematical muddling of computer science. For this reason, we have taken care to explain what discrete mathematics is and to highlight some common threads that unify our subject. We have in mind the ground shared by algorithms and recursion, techniques of counting inherent in combinatorics and probability, and the interest in (discrete) structures common to the study of directed graphs, graphs, trees, and Boolean algebras.

As a mathematics text, our book strives to teach mathematical reasoning and an appreciation of the need to read and write mathematics with care. Because we assume no background in calculus, some compromises are inevitable. We do not define real numbers or logarithms, and our definition of a matrix is the usual doodle-definition, a rectangular array of numbers. We hope, however, that we have treated the reader honestly. Knowing that our students may soon be considering formal languages, we have tried to give an elementary explanation of the difference between a proposition and a propositional expression. We are uncomfortable with the definition found in other discrete mathematics texts that a tautology is a compound proposition that is always true. After all, there is no true proposition, compound or otherwise, which, like Cinderella’s coach-and-four, suddenly turns false at the stroke of midnight. The notion of recursive definition is fundamental to discrete mathematics, and we have no qualms in taking as an axiom that this method of definition really does define a sequence. While it is true that our axiom is a consequence of the axiom of induction, it is not fair to invite readers to prove this consequence knowing full well that they will fall into the trap of saying “It is defined for 1; if it is defined for n, it is defined n + 1; so by induction it is defined.” It is also possible to hoodwink readers by saying nothing, where in all fairness something needs to be said. For instance, the equivalence classes of an equivalence relation form a partition, and the natural relation formed from a partition is an equivalence relation. Enough said? No. We still need to know that, going from equivalence relation to partition to equivalence relation, we get home again, and that the trip from partition to equivalence relation to partition also brings us back where we started.

One misconception about our subject is that there is no room in mathematics for trial and error, as if somehow proof precedes conjecture. We therefore give the student a chance to experiment.

For the most part we have followed the guidelines presented by the Mathematical Association of America in the report from Committee on Discrete Mathematics in the First Two Years (1986). In particular, our book presents a beginning discrete mathematics course, and, as recommended by the MAA, it can be used for a one–year course, at the level of the calculus but independent of it. However, with reality in mind, we also designed the text so that it can be used readily in a one–semester course. This text is intended to be comprehensive, and students (particularly those who are taking computer science courses) may find it a handy reference at a later date.

( Sumber : Foundations of Discrete Mathematics, by : Peter Fletcher, Hughes Hoyle, and C. Wayne Patty )