Discrete Structures, Logic, And Computability 4th Edition

Book Preface

This book is written for the prospective computer scientist, computer engineer, or applied mathematician who wants to learn the ideas that underlie computer science. The topics come from the fields of mathematics, logic, and computer science itself. I have attempted to give elementary introductions to those ideas and techniques that are necessary to understand and practice the art and science of computing. This fourth edition of the book contains all the topics for discrete structures listed in Computer Science Curricula 2013 by the ACM/IEEE Joint Task Force on Computing Curricula.

Structure and Method

The structure of the fourth edition continues to support the spiral (i.e., iterative or nonlinear) method for learning. The spiral method is a “just in time” approach. In other words, start by introducing just enough basic information about a topic so that students can do something with it. Then revisit the topic whenever new skills or knowledge about the topic are needed for students to solve problems in other topics that have been introduced in the same way. The process continues as much as possible for each topic.

Topics that are revisited with the spiral approach include logic, sets, relations, graphs, counting, number theory, cryptology, algorithm analysis, complexity, algebra, languages, and machines. Therefore, many traditional topics are dispersed throughout the text to places where they fit naturally with the techniques under discussion.

The coverage of logic is much more extensive than in other current books at this level. Logic is of fundamental importance in computer science—not only for its use in problem solving, but also for its use in formal specification of programs, for its formal verification of programs, and for its growing use in areas such as databases, artificial intelligence, robotics, and automatic reasoning systems. Logic is covered in a spiral manner. For example, informal proof techniques are introduced in the first section of Chapter 1. Then we use informal logic without much comment until Chapter 4, where inductive proof techniques are presented. After the informal use of logic is well in hand, we move to the formal aspects of logic in Chapters 6 and 7, where equivalence proofs and rule-based proofs are introduced. Formal logic is applied to proving correctness properties of programs in Chapter 8, where we also introduce higher forms of logic and automatic reasoning.

The coverage of algebraic structures differs from that in other texts. In Chapter 9 we give elementary introductions to algebras and algebraic techniques that apply directly to computer science. In addition to the traditional topic of Boolean algebra, we introduce congruences with applications to cryptology, abstract data types, relational algebra for relational databases, functional algebra for reasoning about programs, and morphisms. In Chapter 11 we introduce the algebra of regular expressions for simplifying representations of regular languages.

The computing topics of languages, automata, and computation are introduced in Chapters 11 and 12. The last section of the book gives an elementary introduction to computational complexity.

Changes for the Fourth Edition

♦ Every section of the book now contains learning objectives and review questions. There are over 350 review questions in the book.

♦ The first section of the book on informal proof (“A Proof Primer”) has been expanded to provide a wider range of proof techniques, along with simple examples of informal proofs that use the techniques.

♦ A new chapter on graphs has been added (Chapter 10). It expands on the introductory material contained in the first chapter.

♦ Two new topics, conditional independence and elementary statistics, have been added to Section 5.4 on discrete probability.

♦ The coverage of logic programming has been reduced, but it is still introduced as an application of resolution in Section 8.3. The coverage of parsing algorithms has been dropped.

♦ Over 125 examples with named headings have been added. There are now more than 550 such headings that contain over 650 individual examples. In addition to the examples that occur under named headings, the book now has more than 1000 examples that occur within the prose, most of which are introduced by the phrase “For example.”

♦ More than 300 new exercises have been added so that the book now contains over 2250 exercises. Answers are provided for about half of the exercises; these exercises are identified with bold numbers.

I hope that this edition has no errors. But I do wish to apologize in advance for any errors found in the book. I would appreciate hearing about them. As always, we should read the printed word with some skepticism.

Note to the Student

Most problems in computer science involve one of the following five questions:

♦ Can the problem be solved by a computer program?

♦ If not, can you modify the problem so that it can be solved by a program?

♦ If so, can you write a program to solve the problem?

♦ Can you convince another person that your program is correct?

♦ Can you convince another person that your program is efficient?

One goal of the book is that you obtain a better understanding of these questions, together with a better ability to answer them. The book’s ultimate goal is that you gain self-reliance and confidence in your own ability to solve problems, just like the self-reliance and confidence you have in your ability to ride a bike.