Discrete mathematical structures. / Bernard Kolman; Robert C. and Sharon Cuffer Ross

Discrete mathematics is a difficult course to teach and to study at the freshman and sophomore level for several reasons. It is a hybrid course. Its content is mathematics, but many of its applications and more than half its students are from computer science. Thus careful motivation of topics and previews of applications are im- portant and necessary strategies. Moreover, the number of substantive and diverse topics covered in the course is high, so that student must absorb them rather quickiy. At the same time, the student may aiso be expected to develop proof-writing skills. APPROACH First, we have limited both the áreas covered and the depth of coverage to what we deemed prudent in afirst course taught at the freshman and sophomore level. We have identified a set of topics that we feel are of genuine use in computer science and elsewhere and that can be presented in a logically coherent fashion. We have presented an introduction to these topics along with an indication of how they can be pursued in greater depth. Por example, we cover the simpler finite-state machines, not Turing machines. We have limited the coverage of abstract algebra to a discussion of semigroups and groups and have given application of these to the important topics of finite-state machines and error-detecting and error-correcting codes. Error-correcting codes, in turn, have been primarily restricted to simple linear codes. Second, the material has been organized and interrelated to minimize the mass of definitions and the abstraction of some of the theory. Relations and digraphs are treated as two aspects of the same fundamental mathematical idea, with a directed graph being a pictorial representation of a relation. This fundamental idea is then used as the basis of virtually all the concepts introduced in the book, including functions, partial orders, graphs, and algebraic structures. Whenever possible, each new idea introduced in the text uses previously encountered material and, in turn, is developed in such a way that it simplifies the more complex ideas that follow. Thus partial orders, lattices, and Boolean algebras develop from general relations. This material in turn leads naturally to other algebraic structures.