**
**
**
₹895.50 **
₹995.00
Save:
₹99.50 (10%)

**ISBN:**
9789384323264

**Bind:**
Paperback

**Year: **
2017

**Pages:**
1054

**Size:**
171 x 241 mm

**Publisher:**
Jones & Bartlett Learning

**Published in India by:**
Jones & Bartlett India

**Exclusive Distributors:**
Viva Books

**Sales Territory:**
India, Nepal, Pakistan, Sri Lanka, Bhutan

**Description:**

Updated to align to the latest 2013 ACM/IEEE Computer Science curricula,* Discrete Structures, Logic, and Computability, Fourth Edition* is designed for the one-to two-term Discrete Mathematics course. The structure of the book supports the spiral method of learning, by first introducing basic information, allowing students to work on the problem, and then revisiting the topic as new information and skills are established. This method, coupled with a student-friendly and simplified writing style, provides an accessible yet comprehensive level of coverage.

Written for prospective computer scientists, computer engineers, or applied mathematicians, who wish to learn about the ideas that underlie computer science, this edition contains extensive coverage of logic, setting it apart from other books in the field.

**Key Features **

- Over 300 new exercises and 125 new examples have been added throughout the text
- Learning objectives and review questions have been added to every section
- Includes a new Chapter 10, Graph theory, expanding the introductory material presented in Chapter 1
- Provides expanded coverage of informal proof, which includes a wider range of proof techniques and examples
- Provides expanded coverage of discrete probability including conditional independence and elementary statistics

**Target Audience:**

This book is designed for the students and academicians of Mathematics and Computer Science.

**Contents:**

*Preface*

**Chapter 1: Elementary Notions and Notations:** A Proof primer • Statements and Truth Tables • Something to Talk About • Proof Techniques • Exercises • Sets • Definition of a Set • Operations on Sets • Counting Finite Sets • Bags (Multisets) • Sets Should Not Be Too Complicated • Exercises • Ordered Structures • Tuples • Lists • Strings and Languages • Relation • Counting Tuples • Exercises • Graphs and Tress • Introduction to Graphs • Trees • Spanning Trees • Exercises

**Chapter 2: Facts about Functions*** • *Definitions and Examples • Definitions of a Function • Floor and Ceiling Functions • Greatest Common Divisor • The Mod Function • The Log Function • Exercises • Composition of Functions • The Map Function • Exercises • Properties and Applications • Injections, Surjections, and Bijections • The Pigeonhole Principle • Simple Ciphers • Hash Functions • Exercise • Countability • Comparing the Size of Sets • Sets That Are Countable • Diagonalization • Limits on Computability • Exercises

**Chapter 3: Construction Techniques*** • *Inductively Defined Sets • Numbers • Strings • Lists • Binary Trees • Cartesian Products of Sets • Exercises • Recursive Functions and Procedures • Numbers • Strings • Lists • Graphs and Binary Trees • Two More Problems • Infinite Sequences • Exercises • Computer Science: Grammars • Recalling English Grammar • Structure of Grammars • Derivations • Constructing Grammars • Meaning and Ambiguity • Exercises

**Chapter 4: Binary Relationships and Inductive Proof*** • *Properties of Binary Relation • Compohsition of Relations • Closures • Path Problems • Exercises • Equivalence Relations • Definition and Examples • Equivalence Classes • Partitions • Generating Equivalence Relations • Exercise • Order Relations • Partial Orders • Topological Sorting • Well-Founded Orders • Ordinal Numbers • Exercises • Inductive Proof • Proof by Mathematical Induction • Proof by Well-Funded Induction • A Variety of Examples • Exercises

**Chapter 5: Analysis Tools and Techniques*** • *Analyzing Algorithms • Worst-Case Running Time • Decision Trees • Exercises • Summations and Closed Forms • Basic Summations and Closed Forms • Approximating Sums • Approximations with Definite Integrals • Harmonic Numbers • Polynomials and Partial Fractions • Exercises • Permutations and Combinations • Permutations (Order Is Important) • Combinations (Order Is Not Important) • Exercises • Discrete Probability • Probability Terminology • Conditional Probability • Independent Events • Finite Markov Chains • Elementary Statistics • Approximations (Monte Carlo Method) • Exercises • Solving Recurrences • Solving Simple Recurrences • Divide-and-Conquer Recurrences • Generating Functions • Exercises • Comparing Rates of Growth • Big Oh • Big Omega • Big Theta • Little Oh • Using the symbols • Exercises

**Chapter 6: Elementary Logic** • How Do We Reason? • Propositional Calculus • Well-Formed Formulas and Semantics • Logical Equivalence • Truth Functions and Normal Forms • Adequate Sets of Connectives • Exercises • Formal Reasoning • Proof Rules • Proofs • Derived Rules • Theorems, Soundness, and Completeness • Practice Makes Perfect • Exercises • Formal Axiom Systems • An Example Axiom System • Other Axiom Systems • Exercises

**Chapter 7: Predicate Logic** • First-Order Predicate Calculus • Predicates and Quantifiers • Well-Formed Formulas • Interpretations and Semantics • Validity • The Validity Problem • Exercises • Equivalent Formulas • Logical Equivalence • Normal Forms • Formalizing English Sentences • Summary • Exercises • Formal Proofs in Predicate Calculus • Universal Instantiation (UI) • Existential Generalizations (EG) • Existential Instantiation (EI) • Universal Generalization (UG) • Examples of Formal Proofs • Exercises • Equality • Describing equality • Extending Equals for Equals • Exercises

**Chapter 8: Applied Logic** • Program Correctness • Imperative Program Correctness • Array Assignment • Termination • Exercises • Higher-Order Logics • Classifying Higher-Order Logics • Semantics • Higher-Order Reasoning • Exercises • Automatic Reasoing • Clauses and Clausal Forms • Resolution for Propositions • Substitution and Unification • Resolution: The General Case • Theorem Proving with Resolution • Logic Programming • Remarks • Exercises

**Chapter 9: Algebraic Structures and Techniques** • What Is an Algebra? • Definition of an Algebra • Concrete Versus Abstract • Working in Algebras • Inheritance and Subalgebras • Exercises • Boolean Algebra • Simplifying Boolean Expressions • Digital Circuits • Exercises • Congruences and Cryptology • Congruences ?

Cryptology: The RSA Algorithm • Exercises • Abstract Data Types • Natural Numbers • Data Structures • Exercises • Computational Algebras • Relational Algebras • Functional Algebras • Exercises • Morphisms • Exercises

**Chapter 10: Graphy Theory** • Definitions and Examples • Traversing Edges • Complete Graphs • Complement of a Graph • Bipartite Graphs • Exercises • Degrees • Regular Graphs • Degree Sequences • Construction Methods • Exercises • Isomorphic Graphs • Exercises • Matching in Bipartite Graphs • The Matching Algorithm • Hall's Condition for Matching • Perfect Matching • Exercises • Two Traversal Problems • Eulerian Graphs (Traversing Edges) • Hamiltonian Graphs (Visiting Vertices) • Exercises • Planarity • Euler's Formula • Characterizing Planarity • Exercises • Coloring Graphs • Chromatic Numbers • Bounds on Chromatic Numbers • Exercises

**Chapter 11: Languages and Automata** • Regular Languages • Regular Expressions • The Algebra of Regular Expressions • Exercises • Finite Automata • Deterministic Finite Automata • Nondeterministic Finite Automata • Transforming Regular Expressions into Finite Automata • Transforming Finite Automata into Regular Expression • Finite Automata as Output Devices • Representing and Executing Finite Automata • Exercises • Constructing Efficient Finite Automata • Another Regular Expression to NFA Algorithm • Transforming an NFA into a DFA • Minimum-State DFAs • Exercises • Regular Language Topics • Regular Grammars • Properties of Regular Languages • Exercises • Context-Free Languages • Exercises • Pushdown Automata • Equivalent Forms of Acceptance • Context-Free Grammars and Pushdown Automata • Exercises • Context-Free Language Topics • Grammar Transformations • Properties of Context-Free Languages • Exercies

**Chapter 12: Computational Notions** • Turing Machines • Definition of a Turing Machine • Turing Machines with Output • Alternative Definitions • A Universal Turing Machine • Exercises • The Church-Turing Thesis • Equivalence of Computational Models • A Simple Programming Language • Partial Recursive Functions • Machines That Transform Strings • Exercises • Computability • Effective Enumeration • The Halting Problem The Total Problem • Other Problems • Exercises • A Hierachy of Languages • Summary • Exercises • Complexity Classes • The Class P • The Class NP • The Class PSPACE • Intractable Problems • Reduction and NP- Completeness • Formal Complexity Theory • Exercises

**Answers to Selected Exercises**

**Refernces**

**Symbol Glossary**

**Index**

**About the Author**:

**James L. Hein**, Professor Emeritus, Portland State University

James Hein is a Professor Emeritus in the Department of Computer Science at Portland State University. He has a PhD in mathematics from Northwestern University and an MS in computer science from Stanford University. He continues to enjoy finding ways to help students learn about the mathematical foundations of computer science.

10%

10%

10%

10%

10%

10%