Mathematics A Discrete Introduction

by Scheinerman, Edward A.

• ISBN13: 9780534398989
• ISBN10: 0534398987
• Edition: 2nd
• Format: Hardcover
• Copyright: 2005-06-06
• Publisher: Brooks Cole

Summary

Master the fundamentals of discrete mathematics and proof-writing with MATHEMATICS: A DISCRETE INTRODUCTION! With a wealth of learning aids and a clear presentation, the mathematics text teaches you not only how to write proofs, but how to think clearly and present cases logically beyond this course. Though it is presented from a mathematician's perspective, you will learn the importance of discrete mathematics in the fields of computer science, engineering, probability, statistics, operations research, and other areas of applied mathematics. Tools such as Mathspeak, hints, and proof templates prepare you to succeed in this course.

Table of Contents

To the Student	xv
How to Read a Mathematics Book	xvi
Exercises	xvii
To the Instructor	xix
Audience and Prerequisites	xix
Topics Covered and Navigating the Sections	xix
Sample Course Outlines	xxi
Special Features	xxi
What's New in This Second Edition	xxiii
Acknowledgments	xxv
This New Edition	xxv
From the First Edition	xxv
Fundamentals	1	(36)
Joy	1	(1)
Why?	1	(1)
The Agony and the Ecstasy	2	(1)
Exercise	2	(1)
Definition	2	(6)
Recap	5	(1)
Exercises	5	(3)
Theorem	8	(8)
The Nature of Truth	8	(1)
If-Then	9	(2)
If and Only If	11	(1)
And, Or, and Not	12	(1)
What Theorems Are Called	13	(1)
Vacuous Truth	14	(1)
Recap	14	(1)
Exercises	15	(1)
Proof	16	(9)
A More Involved Proof	20	(2)
Proving If-and-Only-If Theorems	22	(2)
Proving Equations and Inequalities	24	(1)
Recap	25	(1)
Exercises	25	(1)
Counterexample	25	(2)
Recap	27	(1)
Exercises	27	(1)
Boolean Algebra	27	(10)
More Operations	31	(1)
Recap	32	(1)
Exercises	32	(2)
Chapter 1 Self Test	34	(3)
Collections	37	(46)
Lists	37	(8)
Counting Two-Element Lists	37	(3)
Longer Lists	40	(3)
Recap	43	(1)
Exercises	43	(2)
Factorial	45	(4)
Much Ado About 0!	46	(1)
Product Notation	47	(1)
Recap	48	(1)
Exercises	48	(1)
Sets I: Introduction, Subsets	49	(9)
Equality of Sets	51	(2)
Subset	53	(2)
Counting Subsets	55	(2)
Power Set	57	(1)
Recap	57	(1)
Exercises	57	(1)
Quantifiers	58	(6)
There Is	58	(1)
For All	59	(1)
Negating Quantified Statements	60	(1)
Combining Quantifiers	61	(1)
Recap	62	(1)
Exercises	63	(1)
Sets II: Operations	64	(12)
Union and Intersection	64	(2)
The Size of a Union	66	(2)
Difference and Symmetric Difference	68	(5)
Cartesian Product	73	(1)
Recap	74	(1)
Exercises	74	(2)
Combinatorial Proof: Two Examples	76	(7)
Recap	80	(1)
Exercises	80	(1)
Chapter 2 Self Test	80	(3)
Counting and Relations	83	(52)
Relations	83	(6)
Properties of Relations	86	(1)
Recap	87	(1)
Exercises	87	(2)
Equivalence Relations	89	(9)
Equivalence Classes	92	(3)
Recap	95	(1)
Exercises	96	(2)
Partitions	98	(6)
Counting Classes/Parts	100	(2)
Recap	102	(1)
Exercises	102	(2)
Binomial Coefficients	104	(13)
Calculating (n/k)	107	(2)
Pascal's Triangle	109	(2)
A Formula for (n/k)	111	(2)
Recap	113	(1)
Exercises	113	(4)
Counting Multisets	117	(6)
Multisets	117	(2)
Formulas for (n/k)	119	(3)
Recap	122	(1)
Exercises	122	(1)
Inclusion-Exclusion	123	(12)
How to Use Inclusion-Exclusion	126	(3)
Derangements	129	(3)
A Ghastly Formula	132	(1)
Recap	132	(1)
Exercises	132	(1)
Chapter 3 Self Test	133	(2)
More Proof	135	(58)
Contradiction	135	(7)
Proof by Contrapositive	135	(2)
Reductio ad Absurdum	137	(4)
A Matter of Style	141	(1)
Recap	141	(1)
Exercises	141	(1)
Smallest Counterexample	142	(13)
Well-Ordering	148	(5)
Recap	153	(1)
Exercises	153	(1)
And Finally	154	(1)
Induction	155	(16)
The Induction Machine	155	(2)
Theoretical Underpinnings	157	(1)
Proof by Induction	157	(3)
Proving Equations and Inequalities	160	(2)
Other Examples	162	(1)
Strong Induction	163	(2)
A More Complicated Example	165	(3)
A Matter of Style	168	(1)
Recap	168	(1)
Exercises	168	(3)
Recurrence Relations	171	(22)
First-Order Recurrence Relations	172	(3)
Second-Order Recurrence Relations	175	(3)
The Case of the Repeated Root	178	(2)
Sequences Generated by Polynomials	180	(7)
Recap	187	(1)
Exercises	188
Chapter 4 Self Test	180	(13)
Functions	193	(52)
Functions	193	(12)
Domain and Image	195	(1)
Pictures of Functions	196	(1)
Counting Functions	197	(1)
Inverse Functions	198	(4)
Counting Functions, Again	202	(1)
Recap	203	(1)
Exercises	203	(2)
The Pigeonhole Principle	205	(6)
Cantor's Theorem	208	(2)
Recap	210	(1)
Exercises	210	(1)
Composition	211	(5)
Identity Function	214	(1)
Recap	215	(1)
Exercises	215	(1)
Permutations	216	(15)
Cycle Notation	217	(3)
Calculations with Permutations	220	(1)
Transpositions	221	(5)
A Graphical Approach	226	(2)
Recap	228	(1)
Exercises	228	(3)
Symmetry	231	(5)
Symmetries of a Square	231	(1)
Symmetries as Permutations	232	(1)
Combining Symmetries	233	(2)
Formal Definition of Symmetry	235	(1)
Recap	236	(1)
Exercises	236	(1)
Assorted Notation	236	(9)
Big oh	236	(3)
Ω and Θ	239	(1)
Little oh	240	(1)
Floor and Ceiling	241	(1)
Recap	242	(1)
Exercises	242	(1)
Chapter 5 Self Test	242	(3)
Probability	245	(48)
Sample Space	245	(4)
Recap	248	(1)
Exercises	248	(1)
Events	249	(8)
Combining Events	252	(1)
The Birthday Problem	253	(1)
Recap	254	(1)
Exercises	255	(2)
Conditional Probability and Independence	257	(9)
Independence	259	(2)
Independent Repeated Trials	261	(1)
The Monty Hall Problem	262	(1)
Recap	263	(1)
Exercises	263	(3)
Random Variables	266	(5)
Random Variables as Events	267	(2)
Independent Random Variables	269	(1)
Recap	270	(1)
Exercises	270	(1)
Expectation	271	(22)
Linearity of Expectation	276	(3)
Product of Random Variables	279	(3)
Expected Value as a Measure of Centrality	282	(1)
Variance	283	(4)
Recap	287	(1)
Exercises	287	(2)
Chapter 6 Self Test	289	(4)
Number Theory	293	(44)
Dividing	293	(5)
Div and Mod	296	(1)
Recap	297	(1)
Exercises	297	(1)
Greatest Common Divisor	298	(11)
Calculating the gcd	299	(2)
Correctness	301	(1)
How Fast?	302	(2)
An Important Theorem	304	(3)
Recap	307	(1)
Exercises	307	(2)
Modular Arithmetic	309	(11)
A New Context for Basic Operations	309	(1)
Modular Addition and Multiplication	310	(1)
Modular Subtraction	311	(2)
Modular Division	313	(5)
A Note on Notation	318	(1)
Recap	318	(1)
Exercises	318	(2)
The Chinese Remainder Theorem	320	(5)
Solving One Equation	320	(2)
Solving Two Equations	322	(2)
Recap	324	(1)
Exercises	324	(1)
Factoring	325	(12)
Infinitely Many Primes	327	(1)
A Formula for Greatest Common Divisor	328	(1)
Irrationality of √2	329	(2)
Recap	331	(1)
Exercises	331	(4)
Chapter 7 Self Test	335	(2)
Algebra	337	(52)
Groups	337	(10)
Operations	337	(1)
Properties of Operations	338	(2)
Groups	340	(2)
Examples	342	(3)
Recap	345	(1)
Exercises	345	(2)
Group Isomorphism	347	(6)
The Same?	347	(2)
Cyclic Groups	349	(3)
Recap	352	(1)
Exercises	352	(1)
Subgroups	353	(9)
Lagrange's Theorem	356	(3)
Recap	359	(1)
Exercises	359	(3)
Fermat's Little Theorem	362	(8)
First Proof	362	(1)
Second Proof	363	(3)
Third Proof	366	(1)
Euler's Theorem	367	(1)
Primality Testing	368	(1)
Recap	369	(1)
Exercises	369	(1)
Public Key Cryptography I: Introduction	370	(3)
The Problem: Private Communication in Public	370	(1)
Factoring	370	(1)
Words to Numbers	371	(2)
Cryptography and the Law	373	(1)
Recap	373	(1)
Exercises	373	(1)
Public Key Cryptography II: Rabin's Method	373	(7)
Square Roots Modulo n	374	(4)
The Encryption and Decryption Procedures	378	(1)
Recap	379	(1)
Exercises	379	(1)
Public Key Cryptography III: RSA	380	(9)
The RSA Encryption and Decryption Functions	381	(2)
Security	383	(1)
Recap	384	(1)
Exercises	384	(1)
Chapter 8 Self Test	385	(4)
Graphs	389	(60)
Fundamentals of Graph Theory	389	(10)
Map Coloring	389	(2)
Three Utilities	391	(1)
Seven Bridges	391	(1)
What Is a Graph?	392	(1)
Adjacency	393	(1)
A Matter of Degree	394	(2)
Further Notation and Vocabulary	396	(1)
Recap	397	(1)
Exercises	397	(2)
Subgraphs	399	(7)
Induced and Spanning Subgraphs	400	(2)
Cliques and Independent Sets	402	(1)
Complements	403	(1)
Recap	404	(1)
Exercises	404	(2)
Connection	406	(7)
Walks	406	(1)
Paths	407	(3)
Disconnection	410	(1)
Recap	411	(1)
Exercises	411	(2)
Trees	413	(8)
Cycles	413	(1)
Forests and Trees	413	(1)
Properties of Trees	414	(2)
Leaves	416	(2)
Spanning Trees	418	(1)
Recap	419	(1)
Exercises	420	(1)
Eulerian Graphs	421	(6)
Necessary Conditions	422	(1)
Main Theorems	423	(2)
Unfinished Business	425	(1)
Recap	426	(1)
Exercises	426	(1)
Coloring	427	(8)
Core Concepts	427	(2)
Bipartite Graphs	429	(4)
The Ease of Two-Coloring and the Difficulty of Three-Coloring	433	(1)
Recap	434	(1)
Exercises	434	(1)
Planar Graphs	435	(14)
Dangerous Curves	435	(1)
Embedding	436	(1)
Euler's Formula	437	(3)
Nonplanar Graphs	440	(2)
Coloring Planar Graphs	442	(2)
Recap	444	(1)
Exercises	444	(2)
Chapter 9 Self Test	446	(3)
Partially Ordered Sets	449	(38)
Fundamentals of Partially Ordered Sets	449	(6)
What Is a Poset?	449	(3)
Notation and Language	452	(2)
Recap	454	(1)
Exercises	454	(1)
Max and Min	455	(3)
Recap	457	(1)
Exercises	457	(1)
Linear Orders	458	(3)
Recap	460	(1)
Exercises	461	(1)
Linear Extensions	461	(8)
Sorting	465	(2)
Linear Extensions of Infinite Posets	467	(1)
Recap	468	(1)
Exercises	468	(1)
Dimension	469	(8)
Realizers	469	(2)
Dimension	471	(2)
Embedding	473	(3)
Recap	476	(1)
Exercises	476	(1)
Lattices	477	(10)
Meet and Join	477	(2)
Lattices	479	(2)
Recap	481	(1)
Exercises	482	(1)
Chapter 10 Self Test	483	(4)
Appendices	487	(68)
A Lots of Hints and Comments; Some Answers	487	(28)
B Solutions to Self Tests	515	(29)
Chapter 1	515	(1)
Chapter 2	516	(2)
Chapter 3	518	(2)
Chapter 4	520	(4)
Chapter 5	524	(2)
Chapter 6	526	(4)
Chapter 7	530	(2)
Chapter 8	532	(3)
Chapter 9	535	(4)
Chapter 10	539	(5)
C Glossary	544	(8)
D Fundamentals	552	(3)
Numbers	552	(1)
Operations	552	(1)
Ordering	553	(1)
Complex Numbers	553	(1)
Substitution	553	(2)
Index	555