Discrete Structures, Logic, and Computability

Discrete Structure, Logic, and Computability introduces the beginning computer science student to some of the fundamental ideas and techniques used by computer scientists today, focusing on discrete structures, logic and computability. The emphasis is on the computational aspects, so that the reader can see how the concepts are actually used. Because of logic's fundamental importance to computer science, the topic is examined extensively in three phases which cover: informal logic; the technique of inductive proof; and formal logic and its applications to computer science. Access the updated errata for this text Click to view/download: Errata.pdf (40 KBytes) The book contains a wide range of material that focuses on those parts of discrete mathematics, logic, and computability needed for computer science students. The topics can be taught in a variety of ways depending on the length of the course, the emphasis, and the background of students. For example, the preface includes syllabai for fourteen different courses in discrete mathematics ranging in length from ten weeks to a full year. It also includes syllabai for two courses in logic, and two courses in computability. The book is organized more along the lines of techshy;nique than on a subject-by-subject basis so that it doesnrs"t fragment into a vast collection of seemshy;ingly unrelated ideas. The focus throughout the book is on the comshy;pushy;tation and construction of objects. So many traditional topshy;ics are dispersed throughout the text to places where they fit naturally with the techniques under discussion. Therefore there is a spiral approach to learning these topics. For example, to read about properties of-and techniques for processing-natural numbers, lists, strings, graphs, or trees, itrs"s necshy;esshy;sary to look in the index or scan the table of contents to find the several places where they are found. Every example has a title and, for ease of scanning, there are special marks to indicate the beginning and ending of each example. Titles and subtitles are used extensively to make it easy to find things. Important facts and results are boxed for easy reference. The second color also makes it easy to find things. There is a minimum of horizontal lines in the book so that scanning is easy. Exercises at the end of each section are categorized by topic and ordered within each topic by difficulty. There is also a collection of exercises at the end of each section labeled proofs and/or challenges. There are over 1700 exercises with answers provided for about half of them. The exercises with answers in the book are marked in color. The symbol glossary makes it easy to check definitions. The index is extensive so that topics can be easily found. The chapter guidelines and chapter summaries let students see what is to be covered and then to check whether they know the details about what was covered.