Viva Group has been honoured with the Best Publisher Award 2022 by the Delhi State Booksellers & Publishers' Association.

Discrete Structures, Logic, and Computability, 4/e

Discrete Structures, Logic, and Computability, 4/e

Discrete Structures, Logic, and Computability, 4/e

  • By: James L. Hein

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

Go to cart

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%

The Metaverse (on procurement ..

By: Matthew Ball

ISBN : 9781324092032

₹ 2,300.40 ₹ 2,556.00

10%

Writing Fast Programs with CD

By: John Riley

ISBN : 9789386385901

₹ 895.50 ₹ 995.00

10%

Software Extension to the PMBO..

By: IEEE Computer Society

ISBN : 9789387486843

₹ 805.50 ₹ 895.00

10%

Analysis of Algorithms, 2/e

By: Jeffery J. McConnell

ISBN : 9789384323189

₹ 805.50 ₹ 895.00

10%

An Introduction to Formal Lang..

By: Peter Linz

ISBN : 9789384323219

₹ 625.50 ₹ 695.00

10%

Foundations of Algorithms, 5/e

By: Richard E Neapolitan

ISBN : 9789384323110

₹ 805.50 ₹ 895.00