Discrete Mathematics With Combinatorics

by Anderson, James A.

• ISBN13: 9780130869982
• ISBN10: 0130869988
• Edition: 1st
• Format: Hardcover
• Copyright: 2001-01-01
• Publisher: Prentice Hall

Summary

For freshman-level, one- or two-semester courses in Discrete Mathematics. This carefully organized, very readable text covers every essential topic in discrete mathematics in a logical fashion. Placing each topic in context, it covers concepts associated with discrete mathematical systems that have applications in computer science, engineering, and mathematics. The author introduces more basic concepts at the freshman level than are found in other texts, in a simple, accessible form. Introductory material is balanced with extensive coverage of graphs, trees, recursion, algebra, theory of computing, and combinatorics. Extensive examples throughout the text reinforce concepts.

Table of Contents

Preface	xi
Truth Tables, Logic, and Proofs	1	(50)
Statements and Connectives	1	(8)
Conditional Statements	9	(4)
Equivalent Statements	13	(7)
Axiomatic Systems: Arguments and Proofs	20	(10)
Completeness in Propositional Logic	30	(5)
Karnaugh Maps	35	(6)
Circuit Diagrams	41	(10)
Set Theory	51	(43)
Introduction to Sets	51	(3)
Set Operations	54	(6)
Venn Diagrams	60	(7)
Boolean Algebras	67	(5)
Relations	72	(12)
Partially Ordered Sets	84	(4)
Equivalence Relations	88	(6)
Logic, Integers, and Proofs	94	(42)
Predicate Calculus	94	(10)
Basic Concepts of Proofs and the Structure of Integers	104	(5)
Mathematical Induction	109	(10)
Divisibility	119	(5)
Prime Integers	124	(5)
Congruence Relations	129	(7)
Functions and Matrices	136	(29)
Functions	136	(5)
Special Functions	141	(6)
Matrices	147	(11)
Cardinality	158	(2)
Cardinals Continued	160	(5)
Algorithms and Recursion	165	(59)
The ``for'' Procedure and Algorithms for Matrices	165	(4)
Recursive Functions and Algorithms	169	(13)
Complexity of Algorithms	182	(5)
Sorting Algorithms	187	(8)
Prefix and Suffix Notation	195	(5)
Binary and Hexadecimal Numbers	200	(12)
Signed Numbers	212	(5)
Matrices Continued	217	(7)
Graphs, Directed Graphs, and Trees	224	(48)
Graphs	224	(7)
Directed Graphs	231	(7)
Trees	238	(7)
Instant Insanity	245	(2)
Euler Paths and Cycles	247	(7)
Incidence and Adjacency Matrices	254	(11)
Hypercubes and Gray Code	265	(7)
Number Theory	272	(18)
Sieve of Eratosthenes	272	(1)
Fermat's Factorization Method	273	(2)
The Division and Euclidean Algorithms	275	(4)
Continued Fractions	279	(5)
Convergents	284	(6)
Counting and Probability	290	(75)
Basic Counting Principles	290	(7)
Inclusion-Exclusion Introduced	297	(7)
Permutations and Combinations	304	(12)
Generating Permutations and Combinations	316	(4)
Probability Introduced	320	(7)
Generalized Permutations and Combinations	327	(5)
Permutations and Combinations with Repetition	332	(5)
Pigeonhole Principle	337	(5)
Probability Revisited	342	(15)
Bayes' Theorem	357	(2)
Markov Chains	359	(6)
Algebraic Structures	365	(28)
Partially Ordered Sets Revisited	365	(4)
Semigroups and Semilattices	369	(5)
Lattices	374	(6)
Groups	380	(6)
Groups and Homomorphisms	386	(7)
Number Theory Revisited	393	(25)
Integral Solutions of Linear Equations	393	(2)
Solutions of Congruence Equations	395	(4)
Chinese Remainder Theorem	399	(6)
Properties of the Function &phis;	405	(5)
Order of an Integer	410	(8)
Recursion Revisited	418	(44)
Homogeneous Linear Recurrence Relations	418	(12)
Nonhomogeneous Linear Recurrence Relations	430	(10)
Finite Differences	440	(4)
Factorial Polynomials	444	(11)
Sums of Differences	455	(7)
Counting Continued	462	(32)
Occupancy Problems	462	(6)
Catalan Numbers	468	(6)
General Inclusion-Exclusion and Derangements	474	(6)
Rook Polynomials and Forbidden Positions	480	(14)
Generating Functions	494	(34)
Definining the Generating Function (optional)	494	(2)
Generating Functions and Recurrence Relations	496	(12)
Generating Functions and Counting	508	(7)
Partitions	515	(6)
Exponential Generating Functions	521	(7)
Graphs Revisited	528	(62)
Algebraic Properties of Graphs	528	(23)
Planar Graphs	551	(6)
Coloring Graphs	557	(12)
Hamiltonian Paths and Cycles	569	(9)
Weighted Graphs and Shortest Path Algorithms	578	(12)
Trees	590	(60)
Properties of Trees	590	(7)
Binary Search Trees	597	(5)
Weighted Trees	602	(11)
Traversing Binary Trees	613	(7)
Spanning Trees	620	(22)
Minimal Spanning Trees	642	(8)
Networks	650	(31)
Networks and Flows	650	(14)
Matching	664	(8)
Petri Nets	672	(9)
Theory of Computation	681	(27)
Regular Languages	681	(6)
Automata	687	(9)
Grammars	696	(12)
Theory of Codes	708	(20)
Introduction	708	(4)
Generator Matrices	712	(9)
Hamming Codes	721	(7)
Enumeration of Colors	728	(12)
Burnside's Theorem	728	(5)
Polya's Theorem	733	(7)
Rings, Integral Domains, and Fields	740	(29)
Rings and Integral Domains	740	(9)
Integral Domains	749	(3)
Polynomials	752	(7)
Algebra and Polynomials	759	(10)
Group and Semigroup Characters	769	(11)
Complex Numbers	769	(1)
Group Characters	770	(5)
Semigroup Characters	775	(5)
Applications of Number Theory	780	(21)
Application: Pattern Matching	780	(7)
Application: Hashing Functions	787	(7)
Application: Cryptography	794	(7)
Bibliography	801
Hints and Solutions to Selected Exercises	A-1
Index	I-1