Mathematical Structures for Computer Science : A Modern Treatment of Discrete Mathematics

by Gersting

• ISBN13: 9780716743583
• ISBN10: 0716743582
• Additional ISBN(s): 9781429215107
• Edition: 5th
• Format: Hardcover
• Copyright: 2002-07-19
• Publisher: W. H. Freeman
• More Book Details
• Purchase Benefits

Summary

New edition of the classic discrete mathematics text for computer science majors.

Table of Contents

Preface	xvii
Note to the Student	xx
Formal Logic	1	(82)
Statements, Symbolic Representation, and Tautologies	2	(18)
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	(6)
Propositional Logic	20	(13)
Valid Arguments	20	(2)
Derivation Rules for Propositional Logic	22	(4)
Deduction Method and Other Rules	26	(2)
Verbal Arguments	28	(2)
Exercises 1.2	30	(3)
Quantifiers, Predicates, and Validity	33	(12)
Quantifiers and Predicates	33	(3)
Translation	36	(3)
Validity	39	(2)
Exercises 1.3	41	(4)
Predicate Logic	45	(15)
Derivation Rules for Predicate Logic	46	(1)
Universal Instantiation	47	(1)
Existential Instantiation	48	(1)
Universal Generalization	49	(1)
Existential Generalization	50	(1)
More Work with Rules	50	(5)
Verbal Arguments	55	(1)
Conclusion	55	(2)
Exercises 1.4	57	(3)
Logic Programming	60	(10)
Prolog	60	(2)
Horn Clauses and Resolution	62	(4)
Recursion	66	(2)
Expert Systems	68	(1)
Exercises 1.56	69	(1)
Proof of Correctness	70	(13)
Assertions	71	(1)
Assignment Rule	72	(3)
Conditional Rule	75	(3)
Exercises 1.6	78	(2)
Chapter 1 Review	80	(2)
On the Computer	82	(1)
Proofs, Recursion, and Analysis of Algorithms	83	(79)
Proof Techniques	84	(10)
Theorems and Informal Proofs	84	(1)
To Prove or Not to Prove	85	(1)
Exhaustive Proof	86	(1)
Direct Proof	87	(1)
Contraposition	88	(1)
Contradiction	89	(2)
Serendipity	91	(1)
Exercises 2.1	92	(2)
Induction	94	(15)
First Principle of Induction	94	(2)
Proofs by Mathematical Induction	96	(5)
Second Principle of Induction	101	(4)
Exercises 2.2	105	(4)
More on Proof of Correctness	109	(11)
Loop Rule	110	(3)
Euclidean Algorithm	113	(3)
Exercises 2.3	116	(4)
Recursion and Recurrence Relations	120	(28)
Recursive Definitions	120	(1)
Recursively Defined Sequences	121	(2)
Recursively Defined Sets	123	(2)
Recursively Defined Operations	125	(1)
Recursively Defined Algorithms	126	(5)
Solving Recurrence Relations	131	(8)
Exercises 2.4	139	(9)
Analysis of Algorithms	148	(14)
Analysis Using Recurrence Relations (Binary Search)	149	(4)
Upper Bound (Euclidean Algorithm)	153	(1)
Exercises 2.5	154	(3)
Chapter 2 Review	157	(2)
On the Computer	159	(3)
Sets, Combinatorics, and Probability	162	(84)
Sets	163	(25)
Notation	163	(2)
Relationships Between Sets	165	(3)
Sets of Sets	168	(1)
Binary and Unary Operations	168	(2)
Operations on Sets	170	(3)
Set Identities	173	(2)
Countable and Uncountable Sets	175	(3)
Exercises 3.1	178	(10)
Counting	188	(13)
Multiplication Principle	188	(4)
Addition Principle	192	(1)
Using the Principles Together	193	(2)
Decision Trees	195	(1)
Exercises 3.2	196	(5)
Principle of Inclusion and Exclusion; Pigeonhole Principle	201	(8)
Principle of Inclusion and Exclusion	201	(5)
Pigeonhole Principle	206	(1)
Exercises 3.3	207	(2)
Permutations and Combinations	209	(14)
Permutations	209	(2)
Combinations	211	(3)
Eliminating Duplicates	214	(1)
Permutations and Combinations with Repetitions	215	(2)
Exercises 3.4	217	(6)
Probability	223	(13)
Introduction to Finite Probability	223	(2)
Probability Distributions	225	(2)
Conditional Probability	227	(1)
Expected Value	228	(2)
Average Case Analysis of Algorithms	230	(2)
Exercises 3.5	232	(4)
Binomial Theorem	236	(10)
Pascal's Triangle	236	(2)
Binomial Theorem and Its Proof	238	(1)
Applying the Binomial Theorem	239	(1)
Exercises 3.6	240	(2)
Chapter 3 Review	242	(2)
On the Computer	244	(2)
Relations, Functions, and Matrices	246	(93)
Relations	247	(24)
Binary Relations	247	(3)
Properties of Relations	250	(2)
Closures of Relations	252	(2)
Partial Orderings	254	(2)
Equivalence Relations	256	(6)
Exercises 4.1	262	(9)
Topological Sorting	271	(7)
Exercises 4.2	276	(2)
Relations and Databases	278	(11)
Entity-Relationship Model	278	(1)
Relational Model	279	(3)
Operations on Relations	282	(3)
Null Values and Three-Valued Logic	285	(1)
Database Integrity	286	(1)
Exercises 4.3	287	(2)
Functions	289	(32)
Definition	289	(6)
Properties of Functions	295	(1)
Onto Functions	295	(1)
One-to-One Functions	296	(1)
Bijections	297	(1)
Composition of Functions	297	(2)
Inverse Functions	299	(1)
Permutation Functions	300	(3)
How Many Functions	303	(3)
Equivalent Sets	306	(1)
Order of Magnitude of Functions	307	(5)
Exercises 4.4	312	(9)
Matrices	321	(18)
Terminology	321	(2)
Matrix Operations	323	(4)
Boolean Matrices	327	(2)
Exercises 4.5	329	(5)
Chapter 4 Review	334	(2)
On the Computer	336	(3)
Graphs and Trees	339	(71)
Graphs and Their Representations	340	(31)
Definitions of a Graph	340	(3)
Applications of Graphs	343	(2)
Graph Terminology	345	(4)
Isomorphic Graphs	349	(3)
Planar Graphs	352	(5)
Computer Representation of Graphs	357	(1)
Adjacency Matrix	357	(2)
Adjacency List	359	(2)
Exercises 5.1	361	(10)
Trees and Their Representations	371	(16)
Tree Terminology	371	(1)
Applications of Trees	372	(2)
Binary Tree Representation	374	(1)
Tree Traversal Algorithms	375	(5)
Results About Trees	380	(1)
Exercises 5.2	381	(6)
Decision Trees	387	(10)
Searching	388	(2)
Lower Bounds on Searching	390	(1)
Binary Tree Search	391	(1)
Sorting	392	(2)
Exercises 5.3	394	(3)
Huffman Codes	397	(13)
Problem and Trial Solution	397	(2)
Huffman Encoding Algorithm	399	(2)
Justification	401	(2)
Applications of Huffman Codes	403	(1)
Exercises 5.4	404	(3)
Chapter 5 Review	407	(1)
On the Computer	408	(2)
Graph Algorithms	410	(51)
Directed Graphs and Binary Relations; Warshall's Algorithm	411	(14)
Directed Graphs and Binary Relations	412	(2)
Reachability	414	(4)
Warshall's Algorithm	418	(4)
Exercises 6.1	422	(3)
Euler Path and Hamiltonian Circuit	425	(8)
Euler Path Problem	425	(4)
Hamiltonian Circuit Problem	429	(1)
Exercises 6.2	430	(3)
Shortest Path and Minimal Spanning Tree	433	(14)
Shortest-Path Problem	433	(6)
Minimal Spanning Tree Problem	439	(2)
Exercises 6.3	441	(6)
Traversal Algorithms	447	(14)
Depth-First Search	447	(2)
Breadth-First Search	449	(3)
Analysis	452	(1)
Applications	453	(3)
Exercises 6.4	456	(2)
Chapter 6 Review	458	(1)
On the Computer	459	(2)
Boolean Algebra and Computer Logic	461	(57)
Boolean Algebra Structure	462	(17)
Models or Abstractions	463	(1)
Definition and Properties	464	(4)
Isomorphic Boolean Algebras	468	(1)
What Is Isomorphism?	468	(3)
Isomorphism as Applied to Boolean Algebra	471	(3)
Exercises 7.1	474	(5)
Logic Networks	479	(21)
Combinational Networks	479	(1)
Basic Logic Elements	479	(1)
Boolean Expressions	480	(1)
Truth Functions	481	(1)
Networks and Expressions	481	(2)
Canonical Form	483	(2)
Minimization	485	(2)
Programmable Logic Arrays	487	(2)
A Useful Network	489	(2)
Other Logic Elements	491	(1)
Constructing Truth Functions	492	(1)
Exercises 7.2	493	(7)
Minimization	500	(18)
Minimization Process	500	(1)
Karnaugh Map	501	(1)
Maps for Three and Four Variables	502	(2)
Using the Karnaugh Map	504	(4)
Quine-McCluskey Procedure	508	(4)
Exercises 7.3	512	(3)
Chapter 7 Review	515	(1)
On the Computer	516	(2)
Modeling Arithmetic, Computation, and Languages	518	(94)
Algebraic Structures	519	(25)
Definitions and Examples	519	(8)
Basic Results about Groups	527	(3)
Subgroups	530	(3)
Isomorphic Groups	533	(6)
Exercises 8.1	539	(5)
Finite-State Machines	544	(28)
Definition	544	(1)
Examples of Finite-State Machines	545	(3)
Recognition	548	(2)
Regular Sets and Kleene's Theorem	550	(2)
Machine Minimization	552	(1)
Unreachable States	552	(1)
Minimization Procedure	553	(5)
Sequential Networks and Finite-State Machines	558	(4)
Exercises 8.2	562	(10)
Turing Machines	572	(21)
Definition	573	(4)
Turing Machines as Set Recognizers	577	(3)
Turing Machines as Function Computers	580	(2)
Church-Turing Thesis	582	(2)
Decision Problems and Uncomputability	584	(1)
Examples of Decision Problems	584	(2)
Halting Problem	586	(1)
Computational Complexity	587	(3)
Exercises 8.3	590	(3)
Formal Languages	593	(19)
Classes of Grammars	599	(3)
Formal Languages and Computational Devices	602	(1)
Context-Free Grammars	603	(3)
Exercises 8.4	606	(2)
Chapter 8 Review	608	(2)
On the Computer	610	(2)
Appendix A Summation Notation	612	(3)
Appendix B The Logarithm Function	615	(4)
Answers to Practice Problems	619	(34)
Answers to Selected Exercises	653	(58)
Answers to Self-Tests	711	(8)
Index	719