# Discrete Mathematics An Introduction to Mathematical Reasoning

Discrete Mathematics An Introduction to Mathematical Reasoning Brief Edition by Susanna S. Epp

## Contents of Discrete Mathematics eBook

• Chapter Speaking Mathematically
• Variables
• Using Variables in Mathematical Discourse; Introduction to Universal, Existential,
• and Conditional Statements
• The Language of Sets
• The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products
• The Language of Relations and Functions
• Definition of a Relation from One Set to Another; Arrow Diagram of a Relation;
• Definition of Function; Function Machines; Equality of Functions
• Chapter The Logic of Compound Statements
• Logical Form and Logical Equivalence
• Statements; Compound Statements; Truth Values; Evaluating the Truth of More General
• Compound Statements; Logical Equivalence; Tautologies and Contradictions;
• Summary of Logical Equivalences
• Conditional Statements
• 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
• Modus Ponens and Modus Tollens; Additional Valid Argument Forms: Rules of
• Inference; Fallacies; Contradictions and Valid Arguments; Summary of Rules of
• Inference
• Chapter The Logic of Quantified Statements
• Predicates and Quantified Statements I
• The Universal Quantifier: ∀; The Existential Quantifier: ∃; Formal Versus Informal
• Language; Universal Conditional Statements; Equivalent Forms of Universal and
• Existential Statements; Implicit Quantification; Tarski’s World
• Copyright Cengage Learning All Rights Reserved May not be copied, scanned, or duplicated, in whole or in part Due to electronic rights, some third party content may be suppressed from the eBook
• Predicates and Quantified Statements II
• Negations of Quantified Statements; Negations of Universal Conditional Statements;
• The Relation among ∀, ∃, ∧, and ∨; Vacuous Truth of Universal Statements; Variants
• of Universal Conditional Statements; Necessary and Sufficient Conditions, Only If
• Statements with Multiple Quantifiers
• Translating from Informal to Formal Language; Ambiguous Language; Negations of
• Multiply-Quantified Statements; Order of Quantifiers
• Arguments with Quantified Statements
• 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
• Chapter Elementary Number Theory
• and Methods of Proof
• Direct Proof and Counterexample I: Introduction
• Definitions; Proving Existential Statements; Disproving Universal Statements by
• Counterexample; Proving Universal Statements; Directions for Writing Proofs of
• Universal Statements; Variations among Proofs; Common Mistakes; Getting Proofs
• Started; Showing That an Existential Statement Is False; Conjecture, Proof, and
• Disproof
• Direct Proof and Counterexample II: Rational Numbers
• More on Generalizing from the Generic Particular; Proving Properties of Rational
• Numbers; Deriving New Mathematics from Old
• Direct Proof and Counterexample III: Divisibility
• Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique
• Factorization of Integers Theorem
• Direct Proof and Counterexample IV: Division into Cases
• and the Quotient-Remainder Theorem
• 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
• Indirect Argument: Contradiction and Contraposition
• Proof by Contradiction; Argument by Contraposition; Relation between Proof by
• Contradiction and Proof by Contraposition; Proof as a Problem-Solving Tool
• Indirect Argument: Two Classical Theorems
• The Irrationality of
• ; Are There Infinitely Many Prime Numbers?; When to Use
• Indirect Proof; Open Questions in Number Theory
• Chapter Sequences, Mathematical Induction,
• and Recursion
• Sequences
• Explicit Formulas for Sequences; Summation Notation; Product Notation; Properties
• of Summations and Products; Change of Variable; Factorial and n Choose
• r Notation
• Mathematical Induction I
• Principle of Mathematical Induction; Sum of the First n Integers; Proving an Equality;
• Deducing Additional Formulas; Sum of a Geometric Sequence
• Mathematical Induction II
• Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibility
• Properties; Proving Inequalities; A Problem with Trominoes
• Strong Mathematical Induction
• and the Well-Ordering Principle for the Integers
• Strong Mathematical Induction;Binary Representation of Integers;TheWell-Ordering
• Principle for the Integers
• Defining Sequences Recursively
• Definition of Recurrence Relation; Examples of Recursively Defined Sequences;
• Recursive Definitions of Sum and Product
• Solving Recurrence Relations by Iteration
• 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
• Chapter Set Theory
• Set Theory: Definitions and the Element Method of Proof
• Subsets; Proof and Disproof; Set Equality; Venn Diagrams; Operations on Sets; The
• Empty Set; Partitions of Sets; Power Sets; Cartesian Products
• Properties of Sets
• Set Identities; Proving Set Identities; Proving That a Set Is the Empty Set
• Disproofs and Algebraic Proofs
• Disproving an Alleged Set Property; Problem-Solving Strategy; The Number of Subsets
• of a Set; “Algebraic” Proofs of Set Identities
• Boolean Algebras and Russell’s Paradox
• Boolean Algebras; Description of Russell’s Paradox
• Chapter Functions
• Functions Defined on General Sets
• Additional Function Terminology; More Examples of Functions; Checking Whether
• a Function Is Well Defined; Functions Acting on Sets
• One-to-One and Onto, Inverse Functions
• One-to-One Functions; One-to-One Functions on Infinite Sets; Onto Functions; Onto
• Functions on Infinite Sets; Relations between Exponential and Logarithmic Functions;
• One-to-One Correspondences; Inverse Functions
• Composition of Functions
• Definition and Examples; Composition of One-to-One Functions; Composition of
• Onto Functions
• Cardinality and Sizes of Infinity
• Definition of Cardinal Equivalence; Countable Sets; The Search for Larger Infinities:
• The Cantor Diagonalization Process
• Chapter Relations
• Relations on Sets
• Additional Examples of Relations; The Inverse of a Relation; Directed Graph of
• a Relation
• Reflexivity, Symmetry, and Transitivity
• Reflexive, Symmetric, and Transitive Properties; Properties of Relations on Infinite
• Sets
• Equivalence Relations
• The Relation Induced by a Partition; Definition of an Equivalence Relation; Equivalence
• Classes of an Equivalence Relation
• Modular Arithmetic and Zn
• Properties of Congruence Modulo n; Modular Arithmetic; Applications; Zn; Definition
• of a Commutative Ring
• The Euclidean Algorithm and Applications
• The Euclidean Algorithm; Extending the Euclidean Algorithm; Euclid’s Lemma; the
• Diophantine Equation ax + by = c; Multiplication in Zn; Definition of Field
• Chapter Counting and Probability
• Introduction
• Definition of Sample Space and Event; Probability in the Equally Likely Case; Counting
• the Elements of Lists
• Possibility Trees and the Multiplication Rule
• 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
• The Addition Rule; The Difference Rule; The Inclusion/Exclusion Rule
• The Pigeonhole Principle
• 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
• r-Combinations; Ordered and Unordered Selections; Relation between Permutations
• and Combinations; Permutation of a Set with Repeated Elements; Some Advice
• Pascal’s Formula and the Binomial Theorem
• Combinatorial Formulas; Pascal’s Triangle; Algebraic and Combinatorial Proofs of
• Pascal’s Formula; The Binomial Theorem and Algebraic and Combinatorial Proofs
• for It; Applications
• Chapter Graphs and Trees
• Graphs: Definitions and Basic Properties
• Basic Terminology and Examples of Graphs; Special Graphs; The Concept of Degree
• Trails, Paths, and Circuits
• Definitions; Connectedness; Euler Circuits; Hamiltonian Circuits
• Trees
• Definition and Examples of Trees; Characterizing Trees
• Rooted Trees
• Definition and Examples of Rooted Trees; Binary Trees and Their Properties