Discrete Mathematics : Proof Techniques and Mathematical Structures

by Penner, R. C.

• ISBN13: 9789810240882
• ISBN10: 9810240880
• Format: Hardcover
• Copyright: 1999-09-01
• Publisher: WORLD SCIENTIFIC PUB CO INC

Summary

Based on a first course in mathematics for students from diverse disciplines developed and taught by Robert Penner over a period of fifteen years at the University of Southern California, where the author is Professor of Mathematics and Physics. DLC: Mathematics.

Author Biography

Robert Penner is Professor of Mathematics and Physics.

Table of Contents

General Preface	xi
Preface for Instructors	xii
PART 1
Proof Techniques	1	(44)
Elements of Logic and Induction	2	(22)
Definitions	2	(1)
Propositions and Predicates	3	(4)
Conjunction and Negation	7	(2)
Implication	9	(3)
Proofs by Induction for Natural Numbers	12	(12)
Methods of Proof	24	(21)
Chains of Implications	24	(8)
Proof by Contradiction	32	(6)
Instantiation	38	(2)
Constructive and Non-Constructive Proofs	40	(3)
Disproofs	43	(2)
Predicate Calculus	45	(48)
Logical Operators	46	(2)
Propositional Forms	48	(2)
Parentheses	50	(3)
Standard Logical Identities	53	(2)
Standard Rules of Inference	55	(2)
Aristotelean Logic	57	(5)
Logical Equivalence	62	(6)
Commutativity and Associativity	68	(4)
Proving Propositional Forms	72	(2)
Predicate Forms and Quantification	74	(6)
Standard Valid Predicate Forms	80	(3)
Proving Predicate Forms	83	(3)
Disproofs	86	(7)
Set Theory	93	(58)
Axioms and the Primitives of Set Theory	94	(4)
The Basics of Set Theory	98	(9)
ZFC Set Theory	107	(7)
Binary Operations on Sets	114	(8)
Cartesian Products	122	(5)
Absolute Complements and DeMorgan's Laws	127	(7)
The Set of Non-Negative Integers	134	(7)
Inductive Definitions	141	(9)
Sets of Numbers	150	(1)
Elementary Number Theory	151	(28)
Common Multiples	152	(2)
The Division Algorithm	154	(2)
Common Divisors	156	(1)
Relatively Prime Pairs	157	(2)
Linear Diophantine Equations	159	(5)
The Fundamental Theorem of Arithmetic	164	(4)
The Euclidean Algorithm	168	(4)
Continued Fractions	172	(7)
Relations	179	(80)
N-ary Relations	180	(4)
Binary Relations and Digraphs	184	(5)
Properties of Relations	189	(5)
Set-Theoretic Operations	194	(2)
Inversion	196	(2)
Composition	198	(5)
Iterations	203	(5)
Posets	208	(6)
Linear and Well Orders	214	(8)
Bounds in Posets	222	(3)
Axiom of Choice Revisited	225	(2)
Equivalence Relations	227	(7)
Partitions	234	(7)
Closure Operations	241	(8)
Meets and Joins of Partitions	249	(3)
Lattices	252	(7)
Functions	259	(54)
Definitions and Examples	260	(9)
Composition	269	(6)
Restriction and Extension	275	(3)
Injectivity, Surjectivity, and Bijectivity	278	(7)
Inverses	285	(7)
Images and Pre-Images	292	(9)
Elements of Dynamical Systems	301	(6)
Permutations	307	(6)
PART 2
Cardinality	313	(28)
Finite Sets	314	(5)
Infinite Sets	319	(3)
Countable Sets	322	(6)
Uncountable Sets	328	(4)
Comparing Cardinalities	332	(9)
Elements of Combinatorics	341	(42)
Finite Cardinalities	342	(3)
Combinatorial Proofs	345	(8)
Recursively Defined Sequences	353	(8)
Inductive Proofs and Solving Recursions	361	(7)
Characteristic Equations	368	(6)
Generating Functions	374	(9)
Languages and Finite State Automata	383	(42)
Alphabets, Words, and Concatenation	384	(4)
Languages	388	(8)
Regular Expressions	396	(3)
Finite State Automata	399	(9)
Kleene's Theorem	408	(9)
Semigroups and Monoids	417	(8)
Graphs	425	(30)
Definitions and Examples	426	(6)
Trees	432	(6)
Hamiltonian and Eulerian Paths	438	(3)
Planarity	441	(5)
Connectivity, Matching, and Coloring	446	(9)
Suggestions for Further Reading	455	(1)
Index of Notation	456	(3)
Index	459