Discrete Structures, Logic, and Computability, 4th Edition

Discrete Structures, Logic, and Computability, 4th Edition

by James L. Hein
Released December 2015
Publisher(s): Jones & Bartlett Learning
ISBN: 9781284070453

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description


Following the recent updates to the 2013 ACM/IEEE Computer Science curricula, Discrete Structures, Logic, and Computability, Fourth Edition, has been designed for the discrete math course that covers one to two semesters. Dr. Hein presents material in a spiral medthod of learning, introducing basic information about a topic, allowing the students to work on the problem and revisit the topic, as new information and skills are established. Written for prospective computer scientist, computer engineers, or applied mathematicians, who want to learn about the ideas that inspire computer science, this edition contains an extensive coverage of logic, setting it apart from similar books available in the field of Computer Science.

Table of contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Contents
  5. Preface
  6. 1 Elementary Notions and Notations
    1. 1.1 A Proof Primer
      1. Statements and Truth Tables
      2. Something to Talk About
      3. Proof Techniques
      4. Exercises
    2. 1.2 Sets
      1. Definition of a Set
      2. Operations on Sets
      3. Counting Finite Sets
      4. Bags (Multisets)
      5. Sets Should Not Be Too Complicated
      6. Exercises
    3. 1.3 Ordered Structures
      1. Tuples
      2. Lists
      3. Strings and Languages
      4. Relations
      5. Counting Tuples
      6. Exercises
    4. 1.4 Graphs and Trees
      1. Introduction to Graphs
      2. Trees
      3. Spanning Trees
      4. Exercises
  7. 2 Facts about Functions
    1. 2.1 Definitions and Examples
      1. Definition of a Function
      2. Floor and Ceiling Functions
      3. Greatest Common Divisor
      4. The Mod Function
      5. The Log Function
      6. Exercises
    2. 2.2 Composition of Functions
      1. The Map Function
      2. Exercises
    3. 2.3 Properties and Applications
      1. Injections, Surjections, and Bijections
      2. The Pigeonhole Principle
      3. Simple Ciphers
      4. Hash Functions
      5. Exercises
    4. 2.4 Countability
      1. Comparing the Size of Sets
      2. Sets That Are Countable
      3. Diagonalization
      4. Limits on Computability
      5. Exercises
  8. 3 Construction Techniques
    1. 3.1 Inductively Defined Sets
      1. Numbers
      2. Strings
      3. Lists
      4. Binary Trees
      5. Cartesian Products of Sets
      6. Exercises
    2. 3.2 Recursive Functions and Procedures
      1. Numbers
      2. Strings
      3. Lists
      4. Graphs and Binary Trees
      5. Two More Problems
      6. Infinite Sequences
      7. Exercises
    3. 3.3 Computer Science: Grammars
      1. Recalling English Grammar
      2. Structure of Grammars
      3. Derivations
      4. Constructing Grammars
      5. Meaning and Ambiguity
      6. Exercises
  9. 4 Binary Relations and Inductive Proof
    1. 4.1 Properties of Binary Relations
      1. Composition of Relations
      2. Closures
      3. Path Problems
      4. Exercises
    2. 4.2 Equivalence Relations
      1. Definition and Examples
      2. Equivalence Classes
      3. Partitions
      4. Generating Equivalence Relations
      5. Exercises
    3. 4.3 Order Relations
      1. Partial Orders
      2. Topological Sorting
      3. Well-Founded Orders
      4. Ordinal Numbers
      5. Exercises
    4. 4.4 Inductive Proof
      1. Proof by Mathematical Induction
      2. Proof by Well-Founded Induction
      3. A Variety of Examples
      4. Exercises
  10. 5 Analysis Tools and Techniques
    1. 5.1 Analyzing Algorithms
      1. Worst-Case Running Time
      2. Decision Trees
      3. Exercises
    2. 5.2 Summations and Closed Forms
      1. Basic Summations and Closed Forms
      2. Approximating Sums
      3. Approximations with Definite Integrals
      4. Harmonic Numbers
      5. Polynomials and Partial Fractions
      6. Exercises
    3. 5.3 Permutations and Combinations
      1. Permutations (Order Is Important)
      2. Combinations (Order Is Not Important)
      3. Exercises
    4. 5.4 Discrete Probability
      1. Probability Terminology
      2. Conditional Probability
      3. Independent Events
      4. Finite Markov Chains
      5. Elementary Statistics
      6. Properties of Expectation
      7. Approximations (the Monte Carlo Method)
      8. Exercises
    5. 5.5 Solving Recurrences
      1. Solving Simple Recurrences
      2. Divide-and-Conquer Recurrences
      3. Generating Functions
      4. Exercises
    6. 5.6 Comparing Rates of Growth
      1. Big Oh
      2. Big Omega
      3. Big Theta
      4. Little Oh
      5. Using the Symbols
      6. Exercises
  11. 6 Elementary Logic
    1. 6.1 How Do We Reason?
    2. 6.2 Propositional Calculus
      1. Well-Formed Formulas and Semantics
      2. Logical Equivalence
      3. Truth Functions and Normal Forms
      4. Adequate Sets of Connectives
      5. Exercises
    3. 6.3 Formal Reasoning
      1. Proof Rules
      2. Proofs
      3. Derived Rules
      4. Theorems, Soundness, and Completeness
      5. Practice Makes Perfect
      6. Exercises
    4. 6.4 Formal Axiom Systems
      1. An Example Axiom System
      2. Other Axiom Systems
      3. Exercises
  12. 7 Predicate Logic
    1. 7.1 First-Order Predicate Calculus
      1. Predicates and Quantifiers
      2. Well-Formed Formulas
      3. Interpretations and Semantics
      4. Validity
      5. The Validity Problem
      6. Exercises
    2. 7.2 Equivalent Formulas
      1. Logical Equivalence
      2. Normal Forms
      3. Formalizing English Sentences
      4. Summary
      5. Exercises
    3. 7.3 Formal Proofs in Predicate Calculus
      1. Universal Instantiation (UI)
      2. Existential Generalization (EG)
      3. Existential Instantiation (EI)
      4. Universal Generalization (UG)
      5. Examples of Formal Proofs
      6. Exercises
    4. 7.4 Equality
      1. Describing Equality
      2. Extending Equals for Equals
      3. Exercises
  13. 8 Applied Logic
    1. 8.1 Program Correctness
      1. Imperative Program Correctness
      2. Array Assignment
      3. Termination
      4. Exercises
    2. 8.2 Higher-Order Logics
      1. Classifying Higher-Order Logics
      2. Semantics
      3. Higher-Order Reasoning
      4. Exercises
    3. 8.3 Automatic Reasoning
      1. Clauses and Clausal Forms
      2. Resolution for Propositions
      3. Substitution and Unification
      4. Resolution: The General Case
      5. Theorem Proving with Resolution
      6. Logic Programming
      7. Remarks
      8. Exercises
  14. 9 Algebraic Structures and Techniques
    1. 9.1 What Is an Algebra?
      1. Definition of an Algebra
      2. Concrete Versus Abstract
      3. Working in Algebras
      4. Inheritance and Subalgebras
      5. Exercises
    2. 9.2 Boolean Algebra
      1. Simplifying Boolean Expressions
      2. Digital Circuits
      3. Exercises
    3. 9.3 Congruences and Cryptology
      1. Congruences
      2. Cryptology: The RSA Algorithm
      3. Exercises
    4. 9.4 Abstract Data Types
      1. Natural Numbers
      2. Data Structures
      3. Exercises
    5. 9.5 Computational Algebras
      1. Relational Algebras
      2. Functional Algebras
      3. Exercises
    6. 9.6 Morphisms
      1. Exercises
  15. 10 Graph Theory
    1. 10.1 Definitions and Examples
      1. Traversing Edges
      2. Complete Graphs
      3. Complement of a Graph
      4. Bipartite Graphs
      5. Exercises
    2. 10.2 Degrees
      1. Regular Graphs
      2. Degree Sequences
      3. Construction Methods
      4. Exercises
    3. 10.3 Isomorphic Graphs
      1. Exercises
    4. 10.4 Matching in Bipartite Graphs
      1. The Matching Algorithm
      2. Hall’s Condition for Matching
      3. Perfect Matching
      4. Exercises
    5. 10.5 Two Traversal Problems
      1. Eulerian Graphs
      2. Hamiltonian Graphs (Visiting Vertices)
      3. Exercises
    6. 10.6 Planarity
      1. Euler’s Formula
      2. Characterizing Planarity
      3. Exercises
    7. 10.7 Coloring Graphs
      1. Chromatic Numbers
      2. Bounds on Chromatic Number
      3. Exercises
  16. 11 Languages and Automata
    1. 11.1 Regular Languages
      1. Regular Expressions
      2. The Algebra of Regular Expressions
      3. Exercises
    2. 11.2 Finite Automata
      1. Deterministic Finite Automata
      2. Nondeterministic Finite Automata
      3. Transforming Regular Expressions into Finite Automata
      4. Transforming Finite Automata into Regular Expressions
      5. Finite Automata as Output Devices
      6. Representing and Executing Finite Automata
      7. Exercises
    3. 11.3 Constructing Efficient Finite Automata
      1. Another Regular Expression to NFA Algorithm
      2. Transforming an NFA into a DFA
      3. Minimum-State DFAs
      4. Exercises
    4. 11.4 Regular Language Topics
      1. Regular Grammars
      2. Properties of Regular Languages
      3. Exercises
    5. 11.5 Context-Free Languages
      1. Exercises
    6. 11.6 Pushdown Automata
      1. Equivalent Forms of Acceptance
      2. Context-Free Grammars and Pushdown Automata
      3. Exercises
    7. 11.7 Context-Free Language Topics
      1. Grammar Transformations
      2. Properties of Context-Free Languages
      3. Exercises
  17. 12 Computational Notions
    1. 12.1 Turing Machines
      1. Definition of a Turing Machine
      2. Turing Machines with Output
      3. Alternative Definitions
      4. A Universal Turing Machine
      5. Exercises
    2. 12.2 The Church-Turing Thesis
      1. Equivalence of Computational Models
      2. A Simple Programming Language
      3. Partial Recursive Functions
      4. Machines That Transform Strings
      5. Exercises
    3. 12.3 Computability
      1. Effective Enumerations
      2. The Halting Problem
      3. The Total Problem
      4. Other Problems
      5. Exercises
    4. 12.4 A Hierarchy of Languages
      1. Hierarchy Table
      2. Exercises
    5. 12.5 Complexity Classes
      1. The Class P
      2. The Class NP
      3. The Class PSPACE
      4. Intractable Problems
      5. Reduction
      6. Formal Complexity Theory
      7. Exercises
  18. Answers to Selected Exercises
  19. References
  20. Symbol Glossary
  21. Index

Product information

  • Title: Discrete Structures, Logic, and Computability, 4th Edition
  • Author(s): James L. Hein
  • Release date: December 2015
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781284070453