Discrete Structures, Logic, and Computability

Name: Discrete Structures, Logic, and Computability
Price: 5.95 USD
Availability: InStock
ISBN: 9780763718435

ISBN-10: 0763718432

ISBN-13: 9780763718435

Edition: 2nd 2002 (Revised)

Authors: James L. Hein

List price: $137.95

30 day, 100% satisfaction guarantee!

Marketplace

2 new & used from $5.95

what's this?

Rush Rewards U
Members Receive:

You have reached 400 XP and carrot coins. That is the daily max!

Description:

Discrete Structure, Logic, and Computability introduces the beginning computer science student to some of the fundamental ideas and techniques used by computer scientists today, focusing on discrete structures, logic and computability. The emphasis is on the computational aspects, so that the reader can see how the concepts are actually used. Because of logic's fundamental importance to computer science, the topic is examined extensively in three phases which cover: informal logic; the technique of inductive proof; and formal logic and its applications to computer science. Access the updated errata for this textClick to view/download: Errata.pdf(40 KBytes) The book contains a wide range… of material that focuses on those parts of discrete mathematics, logic, and computability needed for computer science students. The topics can be taught in a variety of ways depending on the length of the course, the emphasis, and the background of students. For example, the preface includes syllabai for fourteen different courses in discrete mathematics ranging in length from ten weeks to a full year. It also includes syllabai for two courses in logic, and two courses in computability. The book is organized more along the lines of technique than on a subject-by-subject basis so that it doesn't fragment into a vast collection of seemingly unrelated ideas. The focus throughout the book is on the computation and construction of objects. So many traditional topics are dispersed throughout the text to places where they fit naturally with the techniques under discussion. Therefore there is a spiral approach to learning these topics. For example, to read about properties of-and techniques for processing-natural numbers, lists, strings, graphs, or trees, it's necessary to look in the index or scan the table of contents to find the several places where they are found. Every example has a title and, for ease of scanning, there are special marks to indicate the beginning and ending of each example. Titles and subtitles are used extensively to make it easy to find things. Important facts and results are boxed for easy reference. The second color also makes it easy to find things. There is a minimum of horizontal lines in the book so that scanning is easy. Exercises at the end of each section are categorized by topic and ordered within each topic by difficulty. There is also a collection of exercises at the end of each section labeled proofs and/or challenges. There are over 1700 exercises with answers provided for about half of them. The exercises with answers in the book are marked in color. The symbol glossary makes it easy to check definitions. The index is extensive so that topics can be easily found. The chapter guidelines and chapter summaries let students see what is to be covered and then to check whether they know the details about what was covered.

Book details

List price: $137.95
Edition: 2nd
Copyright year: 2002
Publisher: Jones & Bartlett Learning, LLC
Publication date: 9/26/2001
Binding: Hardcover
Pages: 943
Size: 7.50" wide x 8.75" long x 1.50" tall
Weight: 3.278
Language: English




Elementary Notions and Notations



A Proof Primer



Logical Statements



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



Relations



Counting Tuples


Exercises



Graphs and Trees



Definition of a Graph



Paths and Graphs



Graph Traversals



Trees



Spanning Trees


Exercises



Chapter Summary



Facts about Functions



Definitions and Examples



Definition of a Function



Some Useful Functions



Partial Functions


Exercises



Constructing Functions



Composition of Functions



The Map Function


Exercise



Properties of Functions



Injections and Surjections



Bijections and Inverses



The Pigeonhole Principle



Simple Ciphers



Hash Functions


Exercises



Countability



Comparing the Size of Sets



Sets that Are Countable



Diagonalization



Limits on Computability


Exercises



Chapter Summary



Construction Techniques



Inductively Defined Sets



Numbers



Strings



Lists



Binary Trees



Cartesian Products of Sets


Exercises



Recursive Functions and Procedures



Numbers



Strings



Lists



Binary Trees



Two More Problems



Infinite Sequences


Exercises



Grammars



Recalling an English Grammar



Structure of Grammars



Derivations



Constructing Grammars



Meaning and Ambiguity


Exercises



Chapter Summary



Equivalence, Order, and Inductive Proof



Properties of Binary Relations



Composition of Relations



Closures



Path Problems


Exercises



Equivalence Relations



Definition and Examples



Equivalence Classes



Partitions



Generating Equivalence Relations


Exercises



Order Relations



Partial Orders



Topological Sorting



Well-Founded Orders



Ordinal Numbers


Exercises



Inductive Proof



Proof by Mathematical Induction



Proof by Well-Founded Induction



A Variety of Examples


Exercises



Chapter Summary



Analysis Techniques



Analyzing Algorithms



Worst-Case Running Time



Decision Trees


Exercises



Finding Closed Forms



Closed Forms for Sums


Exercises



Counting and Discrete Probability



Permutations (Order Is Important)



Combinations (Order Is Not Important)



Discrete Probability


Exercises



Solving Recurrences



Solving Simple Recurrences



Generating Functions


Exercises



Comparing Rates of Growth



Big Theta



Little Oh



Big Oh and Big Omega


Exercises



Chapter Summary



Elementary Logic



How Do We Reason?



What Is a Calculus?



How Can We Tell Whether Something Is a Proof?



Propositional Calculus



Well-Formed Formulas and Semantics



Equivalence



Truth Functions and Normal Forms



Complete Sets of Connectives


Exercises



Formal Reasoning



Inference Rules



Formal Proof



Proof Notes


Exercises



Formal Axiom Systems



An Example Axiom System



Other Axiom Systems


Exercises



Chapter Summary



Predicate Logic



First-Order Predicate Calculus



Predicates and Quantifiers



Well-Formed Formulas



Semantics and Interpretations



Validity



The Validity Problem


Exercises



Equivalent Formulas



Equivalence



Normal Forms



Formalizing English Sentences



Summary


Exercises



Formal Proofs in Predicate Calculus



Universal Instantiation



Existential Generalization (EG)



Existential Instantiation (EI)



Universal Generalization (UG)



Examples of Formal Proofs



Summary of Quantifier Proofs Rules


Exercises



Chapter Summary



Applied Logic



Equality



Describing Equality



Extending Equals for Equals


Exercises



Program Correctness



Imperative Program Correctness



Array Assignment



Termination


Exercises



Higher-Order Logics



Classifying Higher-Order Logics



Semantics



Higher-Order Reasoning


Exercises



Chapter Summary



Computational Logic



Automatic Reasoning



Clauses and Clausal Forms



Resolution for Propositions



Substitution and Unification



Resolution: The General Case



Theorem Proving with Resolution



Remarks


Exercises



Logic Programming



Family Trees



Definition of a Logic Program



Resolution and Logic Programming



Logic Programming Techniques


Exercises



Chapter Summary



Algebraic Structures and Techniques



What Is an Algebra?



Definition of an Algebra



Concrete Versus Abstract



Working in Algebras


Exercises



Boolean Algebra



Simplifying Boolean Expressions



Digital Circuits


Exercises



Abstract Data Types as Algebras



Natural Numbers



Lists and Strings



Stacks and Queues



Binary Trees and Priority Queues


Exercises



Computational Algebras



Relational Algebras



Functional Algebras


Exercises



Other Algebraic Ideas



Congruence



Cryptology: The RSA Algorithm



Subalgebras



Morphisms


Exercises



Chapter Summary



Regular Languages and Finite 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 Expressions



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



Chapter Summary



Context-Free Languages and Pushdown Automata



Context-Free Languages


Exercises



Pushdown Automata



Equivalent Forms of Acceptance



Context-Free Grammars and Pushdown Automata



Representing and Executing Pushdown Automata


Exercises



Parsing Techniques



LL(k) Parsing



LR(k) Parsing


Exercises



Context-Free Language Topics



Transforming Grammars



Properties of Context-Free Languages


Exercises



Chapter Summary



Turing Machines and Equivalent Models



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



Recursive Functions



Machines That Transform Strings


Exercises



Chapter Summary



Computational Notions



Computability



Effective Enumerations



The Halting Problem



The Total Problem



Other Problems


Exercises



A Hierarchy of Languages



The Languages



Summary


Exercises



Complexity Classes



The Class P



The Class NP



The Class PSPACE



Intractable Problems



Completeness



Formal Complexity Theory


Exercises



Chapter Summary


Answers to Selected Exercises


Bibliography


Greek Alphabet


Symbol Glossary


Index