Discrete Mathematics
, by Hein, James L.Note: Supplemental materials are not guaranteed with Rental or Used book purchases.
- ISBN: 9780867204964 | 0867204966
- Cover: Hardcover
- Copyright: 6/1/1996
This book 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.
Elementary Notions and Notations | p. 1 |
A Proof Primer | p. 2 |
Logical Statements | p. 2 |
Something to Talk About | p. 5 |
Proof Techniques | p. 6 |
Exercises | p. 12 |
Sets | p. 13 |
Definition of a Set | p. 13 |
Operations on Sets | p. 18 |
Counting Finite Sets | p. 26 |
Bags (Multisets) | p. 29 |
Sets Should Not Be Too Complicated | p. 30 |
Exercises | p. 31 |
Ordered Structures | p. 35 |
Tuples | p. 35 |
Lists | p. 39 |
Strings and Languages | p. 41 |
Relations | p. 46 |
Counting Tuples | p. 49 |
Exercises | p. 52 |
Graphs and Trees | p. 55 |
Definition of a Graph | p. 55 |
Paths and Graphs | p. 59 |
Graph Traversals | p. 61 |
Trees | p. 63 |
Spanning Trees | p. 68 |
Exercises | p. 70 |
Chapter Summary | p. 72 |
Facts about Functions | p. 73 |
Definitions and Examples | p. 74 |
Definition of a Function | p. 74 |
Some Useful Functions | p. 79 |
Partial Functions | p. 87 |
Exercises | p. 88 |
Constructing Functions | p. 91 |
Composition of Functions | p. 91 |
The Map Function | p. 96 |
Exercise | p. 98 |
Properties of Functions | p. 100 |
Injections and Surjections | p. 100 |
Bijections and Inverses | p. 102 |
The Pigeonhole Principle | p. 105 |
Simple Ciphers | p. 106 |
Hash Functions | p. 109 |
Exercises | p. 111 |
Countability | p. 115 |
Comparing the Size of Sets | p. 115 |
Sets that Are Countable | p. 116 |
Diagonalization | p. 119 |
Limits on Computability | p. 121 |
Exercises | p. 124 |
Chapter Summary | p. 125 |
Construction Techniques | p. 127 |
Inductively Defined Sets | p. 128 |
Numbers | p. 129 |
Strings | p. 132 |
Lists | p. 134 |
Binary Trees | p. 138 |
Cartesian Products of Sets | p. 140 |
Exercises | p. 142 |
Recursive Functions and Procedures | p. 145 |
Numbers | p. 146 |
Strings | p. 150 |
Lists | p. 153 |
Binary Trees | p. 159 |
Two More Problems | p. 163 |
Infinite Sequences | p. 165 |
Exercises | p. 168 |
Grammars | p. 173 |
Recalling an English Grammar | p. 173 |
Structure of Grammars | p. 174 |
Derivations | p. 177 |
Constructing Grammars | p. 181 |
Meaning and Ambiguity | p. 186 |
Exercises | p. 188 |
Chapter Summary | p. 191 |
Equivalence, Order, and Inductive Proof | p. 193 |
Properties of Binary Relations | p. 194 |
Composition of Relations | p. 195 |
Closures | p. 199 |
Path Problems | p. 204 |
Exercises | p. 209 |
Equivalence Relations | p. 213 |
Definition and Examples | p. 214 |
Equivalence Classes | p. 218 |
Partitions | p. 219 |
Generating Equivalence Relations | p. 225 |
Exercises | p. 229 |
Order Relations | p. 232 |
Partial Orders | p. 233 |
Topological Sorting | p. 239 |
Well-Founded Orders | p. 242 |
Ordinal Numbers | p. 250 |
Exercises | p. 251 |
Inductive Proof | p. 253 |
Proof by Mathematical Induction | p. 253 |
Proof by Well-Founded Induction | p. 259 |
A Variety of Examples | p. 261 |
Exercises | p. 267 |
Chapter Summary | p. 272 |
Analysis Techniques | p. 273 |
Analyzing Algorithms | p. 274 |
Worst-Case Running Time | p. 274 |
Decision Trees | p. 277 |
Exercises | p. 281 |
Finding Closed Forms | p. 281 |
Closed Forms for Sums | p. 282 |
Exercises | p. 287 |
Counting and Discrete Probability | p. 289 |
Permutations (Order Is Important) | p. 289 |
Combinations (Order Is Not Important) | p. 293 |
Discrete Probability | p. 298 |
Exercises | p. 309 |
Solving Recurrences | p. 312 |
Solving Simple Recurrences | p. 313 |
Generating Functions | p. 319 |
Exercises | p. 332 |
Comparing Rates of Growth | p. 334 |
Big Theta | p. 334 |
Little Oh | p. 338 |
Big Oh and Big Omega | p. 339 |
Exercises | p. 341 |
Chapter Summary | p. 342 |
Elementary Logic | p. 345 |
How Do We Reason? | p. 346 |
What Is a Calculus? | p. 347 |
How Can We Tell Whether Something Is a Proof? | p. 348 |
Propositional Calculus | p. 348 |
Well-Formed Formulas and Semantics | p. 349 |
Equivalence | p. 353 |
Truth Functions and Normal Forms | p. 358 |
Complete Sets of Connectives | p. 365 |
Exercises | p. 367 |
Formal Reasoning | p. 369 |
Inference Rules | p. 370 |
Formal Proof | p. 372 |
Proof Notes | p. 380 |
Exercises | p. 381 |
Formal Axiom Systems | p. 384 |
An Example Axiom System | p. 384 |
Other Axiom Systems | p. 391 |
Exercises | p. 392 |
Chapter Summary | p. 394 |
Predicate Logic | p. 397 |
First-Order Predicate Calculus | p. 397 |
Predicates and Quantifiers | p. 398 |
Well-Formed Formulas | p. 402 |
Semantics and Interpretations | p. 404 |
Validity | p. 409 |
The Validity Problem | p. 413 |
Exercises | p. 413 |
Equivalent Formulas | p. 416 |
Equivalence | p. 416 |
Normal Forms | p. 424 |
Formalizing English Sentences | p. 427 |
Summary | p. 429 |
Exercises | p. 430 |
Formal Proofs in Predicate Calculus | p. 432 |
Universal Instantiation | p. 433 |
Existential Generalization (EG) | p. 437 |
Existential Instantiation (EI) | p. 438 |
Universal Generalization (UG) | p. 440 |
Examples of Formal Proofs | p. 443 |
Summary of Quantifier Proofs Rules | p. 450 |
Exercises | p. 451 |
Chapter Summary | p. 456 |
Applied Logic | p. 457 |
Equality | p. 458 |
Describing Equality | p. 458 |
Extending Equals for Equals | p. 464 |
Exercises | p. 465 |
Program Correctness | p. 466 |
Imperative Program Correctness | p. 467 |
Array Assignment | p. 478 |
Termination | p. 482 |
Exercises | p. 486 |
Higher-Order Logics | p. 491 |
Classifying Higher-Order Logics | p. 492 |
Semantics | p. 496 |
Higher-Order Reasoning | p. 498 |
Exercises | p. 501 |
Chapter Summary | p. 503 |
Computational Logic | p. 505 |
Automatic Reasoning | p. 505 |
Clauses and Clausal Forms | p. 506 |
Resolution for Propositions | p. 512 |
Substitution and Unification | p. 514 |
Resolution: The General Case | p. 521 |
Theorem Proving with Resolution | p. 526 |
Remarks | p. 529 |
Exercises | p. 530 |
Logic Programming | p. 533 |
Family Trees | p. 534 |
Definition of a Logic Program | p. 536 |
Resolution and Logic Programming | p. 537 |
Logic Programming Techniques | p. 549 |
Exercises | p. 553 |
Chapter Summary | p. 555 |
Algebraic Structures and Techniques | p. 557 |
What Is an Algebra? | p. 558 |
Definition of an Algebra | p. 560 |
Concrete Versus Abstract | p. 562 |
Working in Algebras | p. 564 |
Exercises | p. 570 |
Boolean Algebra | p. 572 |
Simplifying Boolean Expressions | p. 574 |
Digital Circuits | p. 578 |
Exercises | p. 583 |
Abstract Data Types as Algebras | p. 585 |
Natural Numbers | p. 585 |
Lists and Strings | p. 589 |
Stacks and Queues | p. 592 |
Binary Trees and Priority Queues | p. 596 |
Exercises | p. 599 |
Computational Algebras | p. 601 |
Relational Algebras | p. 601 |
Functional Algebras | p. 607 |
Exercises | p. 611 |
Other Algebraic Ideas | p. 613 |
Congruence | p. 613 |
Cryptology: The RSA Algorithm | p. 616 |
Subalgebras | p. 621 |
Morphisms | p. 623 |
Exercises | p. 629 |
Chapter Summary | p. 632 |
Regular Languages and Finite Automata | p. 633 |
Regular Languages | p. 634 |
Regular Expressions | p. 635 |
The Algebra of Regular Expressions | p. 638 |
Exercises | p. 640 |
Finite Automata | p. 642 |
Deterministic Finite Automata | p. 642 |
Nondeterministic Finite Automata | p. 646 |
Transforming Regular Expressions into Finite Automata | p. 648 |
Transforming Finite Automata into Regular Expressions | p. 650 |
Finite Automata as Output Devices | p. 655 |
Representing and Executing Finite Automata | p. 658 |
Exercises | p. 664 |
Constructing Efficient Finite Automata | p. 666 |
Another Regular Expression to NFA Algorithm | p. 667 |
Transforming an NFA into a DFA | p. 669 |
Minimum-State DFAs | p. 675 |
Exercises | p. 681 |
Regular Language Topics | p. 683 |
Regular Grammars | p. 684 |
Properties of Regular Languages | p. 689 |
Exercises | p. 693 |
Chapter Summary | p. 695 |
Context-Free Languages and Pushdown Automata | p. 697 |
Context-Free Languages | p. 697 |
Exercises | p. 700 |
Pushdown Automata | p. 700 |
Equivalent Forms of Acceptance | p. 703 |
Context-Free Grammars and Pushdown Automata | p. 707 |
Representing and Executing Pushdown Automata | p. 712 |
Exercises | p. 715 |
Parsing Techniques | p. 717 |
LL(k) Parsing | p. 717 |
LR(k) Parsing | p. 731 |
Exercises | p. 744 |
Context-Free Language Topics | p. 746 |
Transforming Grammars | p. 746 |
Properties of Context-Free Languages | p. 751 |
Exercises | p. 755 |
Chapter Summary | p. 756 |
Turing Machines and Equivalent Models | p. 757 |
Turing Machines | p. 757 |
Definition of a Turing Machine | p. 758 |
Turing Machines with Output | p. 762 |
Alternative Definitions | p. 765 |
A Universal Turing Machine | p. 769 |
Exercises | p. 773 |
The Church-Turing Thesis | p. 774 |
Equivalence of Computational Models | p. 775 |
A Simple Programming Language | p. 776 |
Recursive Functions | p. 778 |
Machines That Transform Strings | p. 781 |
Exercises | p. 787 |
Chapter Summary | p. 789 |
Computational Notions | p. 791 |
Computability | p. 791 |
Effective Enumerations | p. 792 |
The Halting Problem | p. 795 |
The Total Problem | p. 796 |
Other Problems | p. 798 |
Exercises | p. 802 |
A Hierarchy of Languages | p. 803 |
The Languages | p. 803 |
Summary | p. 807 |
Exercises | p. 807 |
Complexity Classes | p. 808 |
The Class P | p. 809 |
The Class NP | p. 810 |
The Class PSPACE | p. 811 |
Intractable Problems | p. 813 |
Completeness | p. 815 |
Formal Complexity Theory | p. 821 |
Exercises | p. 824 |
Chapter Summary | p. 825 |
Answers to Selected Exercises | p. 827 |
Bibliography | p. 915 |
Greek Alphabet | p. 921 |
Symbol Glossary | p. 923 |
Index | p. 929 |
Table of Contents provided by Syndetics. All Rights Reserved. |
What is included with this book?
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.