Discrete Mathematics with Applications, Metric Version, 5th Edition PDF by Susanna S. Epp


Discrete Mathematics with Applications, Metric Version, Fifth Edition

 By Susanna S. Epp

Discrete Mathematics with Applications Metric Version Fifth Edition



speaking mathematically 1

Variables 1

Using Variables in Mathematical Discourse; Introduction to Universal, Existential,

and Conditional Statements

The Language of Sets 6

The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products; Strings

The Language of Relations and Functions 15

Definition of a Relation from One Set to Another; Arrow Diagram of a Relation;

Definition of Function; Function Machines; Equality of Functions

The Language of Graphs 24

Definition and Representation of Graphs and Directed Graphs; Degree of a Vertex;

Examples of Graphs Including a Graph Coloring Application


the Logic of compound statements 37

Logical Form and Logical Equivalence 37

Statements; Compound Statements; Truth Values; Evaluating the Truth of More General

Compound Statements; Logical Equivalence; Tautologies and Contradictions; Summary

of Logical Equivalences Conditional Statements 53

Logical Equivalences Involving S; 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 66

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 79

Black Boxes and Gates; The Input/Output Table for a Circuit; The Boolean Expression

Corresponding to a Circuit; The Circuit Corresponding to a Boolean Expression; Finding

Circuit That Corresponds to a Given Input/Output Table; Simplifying Combinational

Circuits; NAND and NOR Gates

Application: Number Systems and Circuits for Addition 93

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 108

Predicates and Quantified Statements I I08

The Universal Quantifier: 5; The Existential Quantifier: E; Formal versus Informal

Language; Universal Conditional Statements; Equivalent Forms of Universal and

Existential Statements; Bound Variables and Scope; Implicit Quantification; Tarski’s World

Predicates and Quantified Statements II 122

Negations of Quantified Statements; Negations of Universal Conditional Statements;

The Relation among 5, E, `, and ~; Vacuous Truth of Universal Statements; Variants of

Universal Conditional Statements; Necessary and Sufficient Conditions, Only If

Statements with Multiple Quantifiers 131

Translating from Informal to Formal Language; Ambiguous Language; Negations of

Multiply-Quantified Statements; Order of Quantifiers; Formal Logical Notation; Prolog

Arguments with Quantified Statements 146

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 160

Direct Proof and Counterexample I: Introduction 161

Definitions; Proving Existential Statements; Disproving Universal Statements by

Counterexample; Proving Universal Statements; Generalizing from the Generic

Particular; Method of Direct Proof; Existential Instantiation; Getting Proofs Started; Examples

Direct Proof and Counterexample II: Writing Advice 173

Writing Proofs of Universal Statements; Common Mistakes; Examples; Showing That an

Existential Statement Is False; Conjecture, Proof, and Disproof

Direct Proof and Counterexample III: Rational Numbers 183

More on Generalizing from the Generic Particular; Proving Properties of Rational

Numbers; Deriving New Mathematics from Old

Direct Proof and Counterexample IV: Divisibility 190

Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique

Factorization of Integers Theorem

Direct Proof and Counterexample V: Division into Cases and the

Quotient-Remainder Theorem 200

Discussion of the Quotient-Remainder Theorem and Examples; div and mod; Alternative

Representations of Integers and Applications to Number Theory; Absolute Value and the Triangle Inequality

Direct Proof and Counterexample VI: Floor and Ceiling 211

Definition and Basic Properties; The Floor of ny2

Indirect Argument: Contradiction and Contraposition 218

Proof by Contradiction; Argument by Contraposition; Relation between Proof by

Contradiction and Proof by Contraposition; Proof as a Problem-Solving Tool

Indirect Argument: Two Famous Theorems 228

The Irrationality of Ï2; Are There Infinitely Many Prime Numbers?; When to Use

Indirect Proof; Open Questions in Number Theory

Application: The handshake Theorem 235

The Total Degree of a Graph; The Handshake Theorem and Consequences; Applications;

Simple Graphs; Complete Graphs; Bipartite Graphs

Application: Algorithms 244

An Algorithmic Language; A Notation for Algorithms; Trace Tables; The Division

Algorithm; The Euclidean Algorithm


sequences, mathematical induction,

and recursion 258

Sequences 258

Explicit Formulas for Sequences; Summation Notation; Product Notation; Properties

of Summations and Products; Change of Variable; Factorial and n Choose r Notation;

Sequences in Computer Programming; Application: Algorithm to Convert from Base 10

to Base 2 Using Repeated Division by 2

Mathematical Induction I: Proving Formulas 275

Principle of Mathematical Induction; Sum of the First n Integers; Proving an Equality;

Deducing Additional Formulas; Sum of a Geometric Sequence

Mathematical Induction II: Applications 289

Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibility

Properties; Proving Inequalities; Trominoes and Other Applications

Strong Mathematical Induction and the Well-Ordering

Principle for the Integers 301

Strong Mathematical Induction; The Well-Ordering Principle for the Integers; Binary

Representation of Integers and Other Applications

Application: Correctness of Algorithms 314

Assertions; Loop Invariants; Correctness of the Division Algorithm; Correctness of theEuclidean Theorem

Defining Sequences Recursively 325

Examples of Recursively Defined Sequences; Recursive Definitions of Sum and Product

Solving Recurrence Relations by Iteration 340

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 homogeneous Recurrence Relations

with Constant Coefficients 352

Derivation of a Technique for Solving These Relations; The Distinct-Roots Case; The

Single-Root Case

General Recursive Definitions and Structural Induction 364

Recursively Defined Sets; Recursive Definitions for Boolean Expressions, Strings, and

Parenthesis Structures; Using Structural Induction to Prove Properties about Recursively

Defined Sets; Recursive Functions


set theory 377

Set Theory: Definitions and the Element Method of Proof 377

Subsets: Introduction to Proof and Disproof for Sets; Set Equality; Venn Diagrams;

Operations on Sets; The Empty Set; Partitions of Sets; Power Sets; An Algorithm to

Check Whether One Set Is a Subset of Another (Optional)

Properties of Sets 391

Set Identities; Proving Subset Relations and Set Equality; Proving That a Set Is the

Empty Set

Disproofs and Algebraic Proofs 407

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 414

Boolean Algebras: Definition and Properties; Russell’s Paradox; The Halting Problem


Properties of Functions 425

Functions Defined on General Sets 425

Dynamic Function Terminology; Equality of Functions; Additional Examples of

Functions; Boolean Functions; Checking Whether a Function Is Well Defined; Functions

Acting on Sets

One-to-One, Onto, and Inverse Functions 439

One-to-One Functions; One-to-One Functions on Infinite Sets; Application: Hash

Functions and Cryptographic Hash Functions; Onto Functions; Onto Functions on

Infinite Sets; Relations between Exponential and Logarithmic Functions; One-to-One

Correspondences; Inverse Functions

Composition of Functions 461

Definition and Examples; Composition of One-to-One Functions; Composition of Onto


Cardinality with Applications to Computability 473

Definition of Cardinal Equivalence; Countable Sets; The Search for Larger Infinities: The

Cantor Diagonalization Process; Application: Cardinality and Computability


Properties of relations 487

Relations on Sets 487

Additional Examples of Relations; The Inverse of a Relation; Directed Graph of a

Relation; N-ary Relations and Relational Databases

Reflexivity, Symmetry, and Transitivity 495

Reflexive, Symmetric, and Transitive Properties; Properties of Relations on Infinite Sets;

The Transitive Closure of a Relation

Equivalence Relations 505

The Relation Induced by a Partition; Definition of an Equivalence Relation; Equivalence

Classes of an Equivalence Relation

Modular Arithmetic with Applications to Cryptography 524

Properties of Congruence Modulo n; Modular Arithmetic; Extending the Euclidean

Algorithm; Finding an Inverse Modulo n; RSA Cryptography; Euclid’s Lemma; Fermat’s

Little Theorem; Why Does the RSA Cipher Work?; Message Authentication; Additional

Remarks on Number Theory and Cryptography

Partial Order Relations 546

Antisymmetry; Partial Order Relations; Lexicographic Order; Hasse Diagrams; Partially

and Totally Ordered Sets; Topological Sorting; An Application; PERT and CPM


counting and Probability 564

Introduction to Probability 564

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 573

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 589

The Addition Rule; The Difference Rule; The Inclusion/Exclusion Rule

The Pigeonhole Principle 604

Statement and Discussion of the Principle; Applications; Decimal Expansions of

Fractions; Generalized Pigeonhole Principle; Proof of the Pigeonhole Principle

Counting Subsets of a Set: Combinations 617

r-Combinations; Ordered and Unordered Selections; Relation between Permutations

and Combinations; Permutation of a Set with Repeated Elements; Some Advice about

Counting; The Number of Partitions of a Set into r Subsets

r-Combinations with Repetition Allowed 634

Multisets and How to Count Them; Which Formula to Use?

Pascal’s Formula and the Binomial Theorem 642

Combinatorial Formulas; Pascal’s Triangle; Algebraic and Combinatorial Proofs of

Pascal’s Formula; The Binomial Theorem and Algebraic and Combinatorial Proofs for It; Applications

Probability Axioms and Expected Value 655

Probability Axioms; Deriving Additional Probability Formulas; Expected Value

Conditional Probability, Bayes’ Formula, and Independent Events 662

Conditional Probability; Bayes’ Theorem; Independent Events


theory of Graphs and trees 677

Trails, Paths, and Circuits 677

Definitions; Connectedness; Euler Circuits; Hamiltonian Circuits

Matrix Representations of Graphs 698

Matrices; Matrices and Directed Graphs; Matrices and Undirected Graphs; Matrices and

Connected Components; Matrix Multiplication; Counting Walks of Length N

Isomorphisms of Graphs 713

Definition of Graph Isomorphism and Examples; Isomorphic Invariants; Graph

Isomorphism for Simple Graphs

Trees: Examples and Basic Properties 720

Definition and Examples of Trees; Characterizing Trees Rooted Trees 732

Definition and Examples of Rooted Trees; Binary Trees and Their Properties; Binary Search Trees

Spanning Trees and a Shortest Path Algorithm 742

Definition of a Spanning Tree; Minimum Spanning Trees; Kruskal’s Algorithm; Prim’s

Algorithm; Dijkstra’s Shortest Path Algorithm


analysis of algorithm efficiency 760

Real-Valued Functions of a Real Variable and Their Graphs 760

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


Big-O, Big-Omega, and Big-Theta Notations 769

Definition and General Properties of O-, V-, and Q-Notations; Orders of Power

Functions; Orders of Polynomial Functions; A Caution about O-Notation; Theorems about Order Notation

Application: Analysis of Algorithm Efficiency I 787

Measuring the Efficiency of an Algorithm; Computing Orders of Simple Algorithms;

The Sequential Search Algorithm; The Insertion Sort Algorithm; Time Efficiency of an Algorithm

Exponential and Logarithmic Functions: Graphs and Orders 800

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: Analysis of Algorithm Efficiency II 813

Binary Search; Divide-and-Conquer Algorithms; The Efficiency of the Binary Search

Algorithm; Merge Sort; Tractable and Intractable Problems; A Final Remark on Algorithm Efficiency


regular expressions and Finite-state automata 828

Formal Languages and Regular Expressions 829

Definitions and Examples of Formal Languages and Regular Expressions; The Language

Defined by a Regular Expression; Practical Uses of Regular Expressions

Finite-State Automata 841

Definition of a Finite-State Automaton; The Language Accepted by an Automaton; The

Eventual-State Function; Designing a Finite-State Automaton; Simulating a Finite-State

Automaton Using Software; Finite-State Automata and Regular Expressions; Regular Languages

Simplifying Finite-State Automata 858

*-Equivalence of States; k-Equivalence of States; Finding the *-Equivalence Classes; The

Quotient Automaton; Constructing the Quotient Automaton; Equivalent Automata


Properties of the real Numbers a-1


solutions and hints to selected exercises a-4

Index I-1

This book is US$10
To get free sample pages OR Buy this book

Share this Book!

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.