Mathematical Structures for Computer Science

by Gersting, Judith L.

• ISBN13: 9780716768647
• ISBN10: 071676864X
• Edition: 6th
• Format: Hardcover
• Copyright: 2006-07-07
• Publisher: W. H. Freeman

Summary

Computing Curricula 2001 (CC2001), a joint undertaking of the Institute for Electrical and Electronic Engineers/Computer Society (IEEE/CS) and the Association for Computing Machinery (ACM), identifies the essential material for an undergraduate degree in computer science. This Sixth Edition ofMathematical Structures for Computer Sciencecovers all the topics in the CC2001 suggested curriculum for a one-semester intensive discrete structures course, and virtually everything suggested for a two-semester version of a discrete structures course. Gersting's text binds together what otherwise appears to be a collection of disjointed topics by emphasizing the following themes: Importance of logical thinking Power of mathematical notation Usefulness of abstractions

Table of Contents

Preface	xv
Note to the Student	xvii
Formal Logic	1	(87)
Statements, Symbolic Representation, and Tautologies	2	(19)
Connectives and Truth Values	2	(6)
Tautologies	8	(2)
Logical Connectives in the Real World	10	(1)
An Algorithm	11	(3)
Exercises 1.1	14	(7)
Propositional Logic	21	(14)
Valid Arguments	21	(3)
Derivation Rules for Propositional Logic	24	(3)
Deduction Method and Other Rules	27	(2)
Verbal Arguments	29	(2)
Exercises 1.2	31	(4)
Quantifiers, Predicates, and Validity	35	(14)
Quantifiers and Predicates	35	(3)
Translation	38	(3)
Validity	41	(2)
Exercises 1.3	43	(6)
Predicate Logic	49	(14)
Derivation Rules for Predicate Logic	49	(2)
Universal Instantiation	51	(1)
Existential Instantiation	51	(1)
Universal Generalization	52	(1)
Existential Generalization	53	(1)
More Work with Rules	54	(4)
Verbal Arguments	58	(1)
Conclusion	59	(1)
Exercises 1.4	60	(3)
Logic Programming	63	(11)
Prolog	64	(2)
Horn Clauses and Resolution	66	(3)
Recursion	69	(3)
Expert Systems	72	(1)
Exercises 1.5	72	(2)
Proof of Correctness	74	(14)
Assertions	75	(1)
Assignment Rule	76	(3)
Conditional Rule	79	(3)
Exercises 1.6	82	(2)
Chapter 1 Review	84	(3)
On the Computer	87	(1)
Proofs, Recursion, and Analysis of Algorithms	88	(98)
Proof Techniques	89	(11)
Theorems and Informal Proofs	89	(1)
To Prove or Not to Prove	90	(1)
Exhaustive Proof	91	(1)
Direct Proof	92	(1)
Contraposition	93	(2)
Contradiction	95	(1)
Serendipity	96	(1)
Common Definitions	97	(1)
Exercises 2.1	98	(2)
Induction	100	(18)
First Principle of Induction	100	(2)
Proofs by Mathematical Induction	102	(5)
Second Principle of Induction	107	(5)
Exercises 2.2	112	(6)
More on Proof of Correctness	118	(11)
Loop Rule	118	(3)
Euclidean Algorithm	121	(3)
Exercises 2.3	124	(5)
Recursive Definitions	129	(18)
Recursively Defined Sequences	129	(3)
Recursively Defined Sets	132	(2)
Recursively Defined Operations	134	(1)
Recursively Defined Algorithms	135	(5)
Exercises 2.4	140	(7)
Recurrence Relations	147	(22)
Linear First-Order Recurrence Relations	147	(1)
Expand, Guess, and Verify	147	(2)
A Solution Formula	149	(7)
Linear Second-Order Recurrence Relations	156	(5)
Divide-and-Conquer Recurrence Relations	161	(3)
Exercises 2.5	164	(5)
Analysis of Algorithms	169	(17)
The General Idea	169	(3)
Analysis Using Recurrence Relations	172	(2)
Upper Bound (Euclidean Algorithm)	174	(1)
Exercises 2.6	175	(6)
Chapter 2 Review	181	(2)
On the Computer	183	(3)
Sets, Combinatorics, Probability, and Number Theory	186	(99)
Sets	187	(24)
Notation	187	(2)
Relationships Between Sets	189	(2)
Sets of Sets	191	(1)
Binary and Unary Operations	192	(2)
Operations on Sets	194	(2)
Set Identities	196	(3)
Countable and Uncountable Sets	199	(3)
Exercises 3.1	202	(9)
Counting	211	(14)
Multiplication Principle	212	(3)
Addition Principle	215	(1)
Using the Principles Together	216	(2)
Decision Trees	218	(2)
Exercises 3.2	220	(5)
Principle of Inclusion and Exclusion; Pigeonhole Principle	225	(8)
Principle of Inclusion and Exclusion	225	(5)
Pigeonhole Principle	230	(1)
Exercises 3.3	231	(2)
Permutations and Combinations	233	(19)
Permutations	233	(2)
Combinations	235	(3)
Eliminating Duplicates	238	(1)
Permutations and Combinations with Repetitions	239	(7)
Exercises 3.4	246	(6)
Probability	252	(14)
Introduction to Finite Probability	252	(2)
Probability Distributions	254	(2)
Conditional Probability	256	(1)
Expected Value	257	(3)
Average Case Analysis of Algorithms	260	(1)
Exercises 3.5	261	(5)
Binomial Theorem	266	(6)
Pascal's Triangle	266	(1)
Binomial Theorem and Its Proof	267	(2)
Applying the Binomial Theorem	269	(1)
Exercises 3.6	270	(2)
Number Theory	272	(13)
Fundamental Theorem of Arithmetic	272	(4)
More on Prime Numbers	276	(1)
Euler Phi Function	277	(2)
Exercises 3.7	279	(2)
Chapter 3 Review	281	(2)
On the Computer	283	(2)
Relations, Functions, and Matrices	285	(116)
Relations	286	(25)
Binary Relations	286	(3)
Properties of Relations	289	(2)
Closures of Relations	291	(2)
Partial Orderings	293	(2)
Equivalence Relations	295	(6)
Exercises 4.1	301	(10)
Topological Sorting	311	(8)
Exercises 4.2	316	(3)
Relations and Databases	319	(12)
Entity-Relationship Model	319	(1)
Relational Model	320	(3)
Operations on Relations	323	(3)
Null Values and Three-Valued Logic	326	(2)
Database Integrity	328	(1)
Exercises 4.3	329	(2)
Functions	331	(31)
Definition	332	(5)
Properties of Functions	337	(1)
Onto Functions	337	(1)
One-to-One Functions	338	(1)
Bijections	339	(1)
Composition of Functions	339	(2)
Inverse Functions	341	(2)
Permutation Functions	343	(2)
How Many Functions	345	(3)
Equivalent Sets	348	(1)
Order of Magnitude of Functions	349	(3)
More on Analysis of Algorithms	352	(2)
Exercises 4.4	354	(8)
The Mighty Mod Function	362	(20)
Hashing	363	(3)
Computer Security	366	(1)
Cryptography	366	(6)
Hashing for Password Encryption	372	(1)
Miscellaneous Applications	373	(1)
Identification Codes	373	(2)
Generating and Decomposing Integers	375	(1)
Modular Arithmetic Designs	376	(2)
Exercises 4.5	378	(4)
Matrices	382	(19)
Terminology	382	(2)
Matrix Operations	384	(4)
Boolean Matrices	388	(2)
Exercises 4.6	390	(6)
Chapter 4 Review	396	(3)
On the Computer	399	(2)
Graphs and Trees	401	(74)
Graphs and Their Representations	402	(31)
Definitions of a Graph	402	(3)
Applications of Graphs	405	(2)
Graph Terminology	407	(3)
Isomorphic Graphs	410	(3)
Planar Graphs	413	(5)
Computer Representation of Graphs	418	(1)
Adjacency Matrix	418	(2)
Adjacency List	420	(3)
Exercises 5.1	423	(10)
Trees and Their Representations	433	(18)
Tree Terminology	433	(2)
Applications of Trees	435	(2)
Binary Tree Representation	437	(1)
Tree Traversal Algorithms	438	(4)
Results About Trees	442	(2)
Exercises 5.2	444	(7)
Decision Trees	451	(11)
Searching	452	(2)
Lower Bounds on Searching	454	(1)
Binary Tree Search	455	(2)
Sorting	457	(2)
Exercises 5.3	459	(3)
Huffman Codes	462	(13)
Problem and Trial Solution	462	(2)
Huffman Encoding Algorithm	464	(2)
Justification	466	(2)
Applications of Huffman Codes	468	(1)
Exercises 5.4	469	(3)
Chapter 5 Review	472	(2)
On the Computer	474	(1)
Graph Algorithms	475	(59)
Directed Graphs and Binary Relations; Warshall's Algorithm	476	(14)
Directed Graphs and Binary Relations	477	(2)
Reachability	479	(4)
Warshall's Algorithm	483	(4)
Exercises 6.1	487	(3)
Euler Path and Hamiltonian Circuit	490	(9)
Euler Path Problem	490	(5)
Hamiltonian Circuit Problem	495	(1)
Exercises 6.2	496	(3)
Shortest Path and Minimal Spanning Tree	499	(14)
Shortest-Path Problem	499	(6)
Minimal Spanning Tree Problem	505	(2)
Exercises 6.3	507	(6)
Traversal Algorithms	513	(11)
Depth-First Search	513	(2)
Breadth-First Search	515	(3)
Analysis	518	(1)
Applications	519	(2)
Exercises 6.4	521	(3)
Articulation Points and Computer Networks	524	(10)
The Problem Statement	524	(1)
The Idea Behind the Algorithm	525	(1)
The Algorithm Itself	526	(3)
Exercises 6.5	529	(2)
Chapter 6 Review	531	(1)
On the Computer	532	(2)
Boolean Algebra and Computer Logic	534	(58)
Boolean Algebra Structure	535	(17)
Models or Abstractions	536	(1)
Definition and Properties	537	(4)
Isomorphic Boolean Algebras	541	(1)
What Is Isomorphism?	541	(3)
Isomorphism as Applied to Boolean Algebra	544	(2)
Exercises 7.1	546	(6)
Logic Networks	552	(22)
Combinational Networks	552	(1)
Basic Logic Elements	552	(1)
Boolean Expressions	553	(1)
Truth Functions	554	(1)
Networks and Expressions	554	(2)
Canonical Form	556	(2)
Minimization	558	(2)
Programmable Logic Arrays	560	(2)
A Useful Network	562	(2)
Other Logic Elements	564	(1)
Constructing Truth Functions	565	(1)
Exercises 7.2	566	(8)
Minimization	574	(18)
Minimization Process	574	(1)
Karnaugh Map	575	(1)
Maps for Three and Four Variables	576	(2)
Using the Karnaugh Map	578	(4)
Quine-McCluskey Procedure	582	(4)
Exercises 7.3	586	(4)
Chapter 7 Review	590	(1)
On the Computer	591	(1)
Modeling Arithmetic, Computation, and Languages	592	(93)
Algebraic Structures	593	(25)
Definitions and Examples	593	(7)
Basic Results About Groups	600	(3)
Subgroups	603	(3)
Isomorphic Groups	606	(6)
Exercises 8.1	612	(6)
Finite-State Machines	618	(28)
Definition	618	(1)
Examples of Finite-State Machines	619	(3)
Recognition	622	(2)
Regular Sets and Kleene's Theorem	624	(2)
Machine Minimization	626	(1)
Unreachable States	626	(1)
Minimization Procedure	627	(5)
Sequential Networks and Finite-State Machines	632	(4)
Exercises 8.2	636	(10)
Turing Machines	646	(20)
Definition	647	(4)
Turing Machines as Set Recognizers	651	(2)
Turing Machines as Function Computers	653	(2)
Church-Turing Thesis	655	(2)
Decision Problems and Uncomputability	657	(1)
Examples of Decision Problems	658	(1)
Halting Problem	659	(1)
Computational Complexity	660	(3)
Exercises 8.3	663	(3)
Formal Languages	666	(19)
Classes of Grammars	672	(3)
Formal Languages and Computational Devices	675	(1)
Context-Free Grammars	676	(3)
Exercises 8.4	679	(3)
Chapter 8 Review	682	(2)
On the Computer	684	(1)
Appendix A Derivation Rules for Propositional and Predicate Logic	685	(2)
Appendix B Summation Notation	687	(3)
Appendix C The Logarithm Function	690	(3)
Answers to Practice Problems	693	(34)
Answers to Selected Exercises	727	(62)
Answers to Self-Tests	789	(8)
Index	797