Discrete Mathematics with Applications

by Epp, Susanna S.

• ISBN13: 9780534359454
• ISBN10: 0534359450
• Edition: 3rd
• Format: Hardcover
• Copyright: 2003-12-22
• Publisher: Brooks Cole

Summary

Susanna Epp's DISCRETE MATHEMATICS, THIRD EDITION provides a clear introduction to discrete mathematics. Renowned for her lucid, accessible prose, Epp explains complex, abstract concepts with clarity and precision. This book presents not only the major themes of discrete mathematics, but also the reasoning that underlies mathematical thought. Students develop the ability to think abstractly as they study the ideas of logic and proof. While learning about such concepts as logic circuits and computer addition, algorithm analysis, recursive thinking, computability, automata, cryptography, and combinatorics, students discover that the ideas of discrete mathematics underlie and are essential to the science and technology of the computer age. Overall, Epp's emphasis on reasoning provides students with a strong foundation for computer science and upper-level mathematics courses.

Table of Contents

The Logic of Compund Statements	1	(74)
Logical Form and Logical Equivalence	1	(16)
Statements
Compound Statements
Truth Values
Evaluating the Truth of More General Compound Statements
Logical Equivalence
Tautologies and Contradictions
Summary of Logical Equivalences
Conditional Statements	17	(12)
Logical Equivalences Involving →
Representation of If-Then As Or
The Negation of a Conditional Statement
The Contrapositive of a Conditional Statement
The Converse and Inverse of a Conditional Statement
Only If and the Biconditional
Necessary and Sufficient Conditions
Remarks
Valid and Invalid Arguments	29	(14)
Modus Ponens and Modus Tollens
Additional Valid Argument Forms: Rules of Inference
Fallacies
Contradictions and Valid Arguments
Summary of Rules of Inference
Application: Digital Logic Circuits	43	(14)
Black Boxes and Gates
The Input/Output for a Circuit
The Boolean Expression Corresponding to a Circuit
The Circuit Corresponding to a Boolean Expression
Finding a Circuit That Corresponds to a Given Input/Output Table
Simplifying Combinational Circuits
NAND and NOR Gates
Application: Number Systems and Circuits for Addition	57	(18)
Binary Representation of Numbers
Binary Addition and Subtraction
Circuits for Computer Addition
Two's Complements and the Computer Representation of Negative Integers
8-Bit Representation of a Number
Computer Addition with Negative Integers
Hexadecimal Notation
The Logic of Quantified Statements	75	(50)
Introduction to Predicates and Quantified Statements I	75	(13)
The Universal Quantifier: A
The Existential Quantifier: E
Formal Versus Informal Language
Universal Conditional Statements
Equivalent Forms of the Universal and Existential Statements
Implicit Quantification
Tarski's World
Introduction to Predicates and Quantified Statements II	88	(9)
Negations of Quantified Statements
Negations of Universal Conditional Statements
The Relation among A, E, V, and V
Vacuous Truth of Universal Statements
Variants of Universal Conditional Statements
Necessary and Sufficient Conditions, Only If
Statements Containing Multiple Quantifiers	97	(14)
Translating from Informal to Formal Language
Ambiguous Language
Negations of Multiply-Quantified Statements
Order of Quantifiers
Formal Logical Notation
Prolog
Arguments with Quantified Statements	111	(14)
Universal Modus Ponens
Use of Universal Modus Ponens in a Proof
Universal Modus Tollens
Proving Validity of Arguments with Quantified Statements
Using Diagrams to Test for Validity
Creating Additional Forms of Argument
Remark on the Converse and Inverse Errors
Elementary Number Theory and Methods of Proof	125	(74)
Direct Proof and Counterexample I: Introduction	126	(15)
Definitions
Proving Existential Statements
Disproving Universal Statements by Counterexample
Proving Universal Statements
Directions for Writing Proofs of Universal Statements
Common Mistakes
Getting Proofs Started
Showing That an Existential Statement Is False
Conjecture, Proof, and Disproof
Direct Proof and Counterexample II: Rational Numbers	141	(7)
More on Generalizing from the Generic Particular
Proving Properties of Rational Numbers
Deriving New Mathematics from Old
Direct Proof and Counterexample III: Divisibility	148	(8)
Proving Properties of Divisibility
Counterexamples and Divisibility
The Unique Factorization Theorem
Direct Proof and Counterexample IV: Division into Cases and the Quotient-Remainder Theorem	156	(8)
Discussion of the Quotient-Remainder Theorem and Examples
div and mod
Alternative Representations of Integers and Applications to Number Theory
Direct Proof and Counterexample V: Floor and Ceiling	164	(7)
Definition and Basic Properties
The Floor of n/2
Indirect Argument: Contradiction and Contraposition	171	(8)
Proof by Contradiction
Argument by Contraposition
Relation between Proof by Contradiction and Proof by Contraposition
Proof as a Problem-Solving Tool
Two Classical Theorems	179	(7)
The Irrationality of √2
The Infinitude of the Set of Prime Numbers
When to Use Indirect Proof
Open Questions in Number Theory
Application: Algorithms	186	(13)
An Algorithmic Language
A Notation for Algorithms
Trace Tables
The Division Algorithm
The Euclidean Algorithm
Sequences and Mathematical Induction	199	(56)
Sequences	199	(16)
Explicit Formulas for Sequences
Summation Notation
Product Notation
Factorial Notation
Properties of Summations and Products
Change of Variable
Sequences in Computer Programming
Application: Algorithm to Convert from Base 10 to Base 2 Using Repeated Division by 2
Mathematical Induction I	215	(12)
Principle of Mathematical Induction
Sum of the First n Integers
Sum of a Geometric Sequence
Mathematical Induction II	227	(8)
Comparison of Mathematical Induction and Inductive Reasoning
Proving Divisibility Properties
Proving Inequalities
Strong Mathematical Induction and the Well-Ordering Principle	235	(9)
The Principle of Strong Mathematical Induction
Binary Representation of Integers
The Well-Ordering Principle for the Integers
Application: Correctness of Algorithms	244	(11)
Assertions
Loop Invariants
Correctness of the Division Algorithm
Correctness of the Euclidean Algorithm
Set Theory	255	(42)
Basic Definitions of Set Theory	255	(14)
Subsets
Set Equality
Operations on Sets
Venn Diagrams
The Empty Set
Partitions of Sets
Power Sets
Cartesian Products
An Algorithm to Check Whether One Set Is a Subset of Another (Optional)
Properties of Sets	269	(13)
Set Identities
Proving Set Identities
Proving That a Set Is the Empty Set
Disproofs, Algebraic Proofs, and Boolean Algebras	282	(11)
Disproving an Alleged Set Property
Problem-Solving Strategy
The Number of Subsets of a Set
``Algebraic'' Proofs of Set Identities
Boolean Algebras
Russell's Paradox and the Halting Problem	293	(4)
Description of Russell's Paradox
The Halting Problem
Counting and Probability	297	(92)
Introduction	298	(8)
Definition of Sample Space and Event
Probability in the Equally Likely Case
Counting the Elements of Lists, Sublists, and One-Dimensional Arrays
Possibility Trees and the Multiplication Rule	306	(15)
Possibility Trees
The Multiplication Rule
When the Multiplication Rule Is Difficult or Impossible to Apply
Permutations
Permutations of Selected Elements
Counting Elements of Disjoint Sets: The Addition Rule	321	(13)
The Addition Rule
The Difference Rule
The Inclusion/Exclusion Rule
Counting Subsets of a Set: Combinations	334	(15)
r-Combinations
Ordered and Unordered Selections
Relation between Permutations and Combinations
Permutation of a Set with Repeated Elements
Some Advice about Counting
r-Combinations with Repetition Allowed	349	(7)
Multisets and How to Count Them
Which Formula to Use?
The Algebra of Combinations	356	(6)
Combinatorial Formulas
Pascal's Triangle
Algebraic and Combinatorial Proofs of Pascal's Formula
The Bionomial Theorem	362	(8)
Statement of the Theorem
Algebraic and Combinatorial Proofs
Applications
Probability Axioms and Expected Value	370	(5)
Probability Axioms
Deriving Additional Probability Formulas
Expected Value
Conditional Probability, Bayes' Formula, and Independent Events	375	(14)
Conditional Probability
Bayes' Theorem
Independent Events
Functions	389	(68)
Functions Defined on General Sets	389	(13)
Definition of Function
Arrow Diagrams
Function Machines
Examples of Functions
Boolean Functions
Checking Whether a Function Is Well Defined
One-to-One and Onto, Inverse Functions	402	(18)
One-to-One Functions
One-to-One Functions on Infinite Sets
Application: Hash Functions
Onto Functions
Onto Functions on Infinite Sets
Properties of Exponential and Logarithmic Functions
One-to-One Correspondences
Inverse Functions
Application: The Pigeonhole Principle	420	(11)
Statement and Discussion of the Principle
Applications
Decimal Expansions of Fractions
Generalized Pigeonhole Principle
Proof of the Pigeonhole Principle
Composition of Functions	431	(12)
Definition and Examples
Composition of One-to-One Functions
Composition of Onto Functions
Cardinality with Applications to Computability	443	(14)
Definition of Cardinal Equivalence
Countable Sets
The Search for Larger Infinities
The Cantor Diagonalization Process
Application: Cardinality and Computability
Recursion	457	(53)
Recursively Defined Sequences	457	(18)
Definition of Recurrence Relation
Examples of Recursively Defined Sequences
The Number of Partitions of a Set Into r Subsets
Solving Recurrence Relations by Iteration	475	(12)
The Method of Iteration
Using Formulas to Simplify Solutions Obtained by Iteration
Checking the Correctness of a Formula by Mathematical Induction
Discovering That an Explicit Formula Is Incorrect
Second-Order Linear Homogenous Recurrence Relations with Constant Coefficients	487
Derivation of Technique for Solving These Relations
The Distinct-Roots Case
The Single-Root Case
General Recursive Definitions	449	(61)
Recursively Defined Sets
Proving Properties about Recursively Defined Sets
Recursive Definitions of Sum, Product, Union, and Intersection
Recursive Functions
The Efficiency of Algorithms	510	(61)
Real-Valued Functions of a Real Variable and Their Graphs	510	(8)
Graph of a Function
Power Functions
The Floor Function
Graphing Functions Defined on Sets of Integers
Graph of a Multiple of a Function
Increasing and Decreasing Functions
O, Ω, and Θ Notations	518	(13)
Definition and General Properties of O-, Ω-, and Θ-Notations
Orders of Power Functions
Orders of Polynomial Functions
Orders of Functions of Integer Variables
Extension to Functions Composed of Rational Power Functions
Application: Efficiency of Algorithms I	531	(12)
Time Efficiency of an Algorithm
Computing Orders of Simple Algorithms
The Sequential Search Algorithm
The Insertion Sort Algorithm
Exponential and Logarithmic Functions: Graphs and Orders	543	(14)
Graphs of Exponential and Logarithmic Functions
Application: Number of Bits Needed to Represent an Integer in Binary Notation
Application: Using Logarithms to Solve Recurrence Relations
Exponential and Logarithmic Orders
Application: Efficiency of Algorithms II	557	(14)
Divide-and-Conquer Algorithms
The Efficiency of the Binary Search Algorithm
Merge Sort
Tractable and Intractable Problems
A Final Remark on Algorithm Efficiency
Relations	571	(78)
Relations on Sets	571	(13)
Definition of Binary Relation
Arrow Diagram of a Relation
Relations and Functions
The Inverse of a Relation
Directed Graph of a Relation
N-ary Relations and Relational Databases
Reflexivity, Symmetry, and Transitivity	584	(10)
Reflexive, Symmetric, and Transitive Properties
The Transitive Closure of a Relation
Properties of Relations on Infinite Sets
Equivalence Relations	594	(17)
The Relation Induced by a Partition
Definition of an Equivalence Relation
Equivalence Classes of an Equivalence Relation
Modular Arithmetic with Applications to Cryptography	611	(21)
Properties of Congruence Modulo n
Modular Arithmetic
Finding an Inverse Modulo n
Euclid's Lemma
Fermat's Little Theorem and the Chinese Remainder Theorem
Why Does the RSA Cipher Work?
Partial Order Relations	632	(17)
Antisymmetry
Partial Order Relations
Lexicographic Order
Hasse Diagrams
Partially and Totally Ordered Sets
Topological Sorting
An Application
PERT and CPM
Graphs and Trees	649	(85)
Graphs: An Introduction	649	(16)
Basic Terminology and Examples
Special Graphs
The Concept of Degree
Paths and Circuits	665	(18)
Definitions
Euler Circuits
Hamiltonian Circuits
Matrix Representations of Graphs	683	(14)
Matrices
Matrices and Directed Graphs
Matrices and (Undirected) Graphs
Matrices and Connected Components
Matrix Multiplication
Counting Walks of Length N
Isomorphisms of Graphs	697	(8)
Definition of Graph Isomorphism and Examples
Isomorphic Invariants
Graph Isomorphism for Simple Graphs
Trees	705	(18)
Definition and Examples of Trees
Characterizing Trees
Rooted Trees
Binary Trees
Spanning Trees	723	(11)
Definition of a Spanning Tree
Minimum Spanning Trees
Kruskal's Algorithm
Prim's Algorithm
Regular Expressions and Finite-State Automata	734
Formal Languages and Regular Expressions	735	(10)
Definitions and Examples of Formal Languages and Regular Expressions
Practical Uses of Regular Expressions
Finite-State Automata	745	(18)
Definition of a Finite-State Automation
The Language Accepted by an Automation
The Eventual-State Function
Designing a Finite-State Automation
Simulating a Finite-State Automation Using Software
Finite-State Automata and Regular Expressions
Regular Languages
Simplifying Finite-State Automata	763
*-Equivalence of States
k-Equivalence of States
Finding the *-Equivalence Classes
The Quotient Automation
Constructing the Quotient Automation
Equivalent Automata
Appendix A Properties of the Real Numbers	1	(3)
Appendix B Solutions and Hints to Selected Exercises	4
Index	1