Discrete Mathematics

by Hein, James L.

• ISBN13: 9780867204964
• ISBN10: 0867204966
• Format: Hardcover
• Copyright: 1996-06-01
• Publisher: Jones & Bartlett Learning

Summary

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.

Table of Contents

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.