Discrete Structures, Logic, and Computability, Second Edition provides a comprehensive introduction to the fundamental ideas underlying contemporary computer science. With a focus on the computation and construction of objects, the topics in this text have been carefully selected to give students a strong foundation in computer science. These topics are unified throughout the text to illustrate the relationships between key ideas. Both formal and informal logic are given extensive coverage throughout the book, along with automatic reasoning and logic programming. Students are provided with the tools and techniques they need to gain self-reliance and confidence in their own problem-solving abilities.

• NEW! Several hundred new exercises, including proofs and challenges, have been added to the book so that there are now over 1700 exercises, with answers provided to half of them. In addition, the exercises are listed by topic and ordered according to difficulty • NEW! Every section has been rewritten to clarify and update complex ideas. In addition, each section now contains many subtopic headings to help identify specific areas of discussion. • Algorithms in the text are presented in a variety of ways, Some are simply a few sentences of explanations. Others are presented in a more traditional notation of assignment statements and control statements • The text covers all topics for the area of discrete structures in the ACM/IEEE Joint Task Force on Computing Curricula report “Computing Curricula 2001” • Discrete Structures (DS) • Recursion (PF5) • Basic Algorithm Analysis (AL1) • Basic Computability Theory (AL5) • Complexity Classes P and NP (AL6) • Automata Theory (AL7) • Formal Methods (SE9) • Knowledge Representation and Reasoning (IS3) • Programming Paradigms (PL10)

Elementary Notions and Notations / Facts about Functions / Construction Techniques / Equivalence, Order, and Inductive Proof / Analysis Techniques / Elementary Logic / Predicate Logic / Applied Logic / Computational Logic / Algebraic Structures and Techniques / Regular Languages and Finite Automata / Context-Free Languages and Pushdown Automata / Turing Machines and Equivalent Models / Computational Notions Answers to Selected Exercises / Bibliography / Greek Alphabet / Symbol Glossary / Index

Graduate Students, Teachers and Researchers