
The Logic of Compund Statements 


1  (74) 

Logical Form and Logical Equivalence 


1  (16) 







Evaluating the Truth of More General Compound Statements 





Tautologies and Contradictions 



Summary of Logical Equivalences 




17  (12) 

Logical Equivalences Involving → 



Representation of IfThen 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 





Valid and Invalid Arguments 


29  (14) 

Modus Ponens and Modus Tollens 



Additional Valid Argument Forms: Rules of Inference 





Contradictions and Valid Arguments 



Summary of Rules of Inference 



Application: Digital Logic Circuits 


43  (14) 



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 





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 



8Bit Representation of a Number 



Computer Addition with Negative Integers 





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 







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 





Negations of MultiplyQuantified Statements 









Arguments with Quantified Statements 


111  (14) 



Use of Universal Modus Ponens in a Proof 





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) 



Proving Existential Statements 



Disproving Universal Statements by Counterexample 



Proving Universal Statements 



Directions for Writing Proofs of Universal Statements 







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 QuotientRemainder Theorem 


156  (8) 

Discussion of the QuotientRemainder Theorem and Examples 





Alternative Representations of Integers and Applications to Number Theory 



Direct Proof and Counterexample V: Floor and Ceiling 


164  (7) 

Definition and Basic Properties 





Indirect Argument: Contradiction and Contraposition 


171  (8) 



Argument by Contraposition 



Relation between Proof by Contradiction and Proof by Contraposition 



Proof as a ProblemSolving Tool 




179  (7) 



The Infinitude of the Set of Prime Numbers 



When to Use Indirect Proof 



Open Questions in Number Theory 




186  (13) 



A Notation for Algorithms 









Sequences and Mathematical Induction 


199  (56) 


199  (16) 

Explicit Formulas for Sequences 









Properties of Summations and Products 





Sequences in Computer Programming 



Application: Algorithm to Convert from Base 10 to Base 2 Using Repeated Division by 2 




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 





Strong Mathematical Induction and the WellOrdering Principle 


235  (9) 

The Principle of Strong Mathematical Induction 



Binary Representation of Integers 



The WellOrdering Principle for the Integers 



Application: Correctness of Algorithms 


244  (11) 





Correctness of the Division Algorithm 



Correctness of the Euclidean Algorithm 




255  (42) 

Basic Definitions of Set Theory 


255  (14) 

















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




269  (13) 





Proving That a Set Is the Empty Set 



Disproofs, Algebraic Proofs, and Boolean Algebras 


282  (11) 

Disproving an Alleged Set Property 





The Number of Subsets of a Set 



``Algebraic'' Proofs of Set Identities 





Russell's Paradox and the Halting Problem 


293  (4) 

Description of Russell's Paradox 






297  (92) 


298  (8) 

Definition of Sample Space and Event 



Probability in the Equally Likely Case 



Counting the Elements of Lists, Sublists, and OneDimensional Arrays 



Possibility Trees and the Multiplication Rule 


306  (15) 





When the Multiplication Rule Is Difficult or Impossible to Apply 





Permutations of Selected Elements 



Counting Elements of Disjoint Sets: The Addition Rule 


321  (13) 





The Inclusion/Exclusion Rule 



Counting Subsets of a Set: Combinations 


334  (15) 



Ordered and Unordered Selections 



Relation between Permutations and Combinations 



Permutation of a Set with Repeated Elements 



Some Advice about Counting 



rCombinations with Repetition Allowed 


349  (7) 

Multisets and How to Count Them 





The Algebra of Combinations 


356  (6) 





Algebraic and Combinatorial Proofs of Pascal's Formula 




362  (8) 



Algebraic and Combinatorial Proofs 





Probability Axioms and Expected Value 


370  (5) 



Deriving Additional Probability Formulas 





Conditional Probability, Bayes' Formula, and Independent Events 


375  (14) 








389  (68) 

Functions Defined on General Sets 


389  (13) 











Checking Whether a Function Is Well Defined 



OnetoOne and Onto, Inverse Functions 


402  (18) 



OnetoOne Functions on Infinite Sets 



Application: Hash Functions 





Onto Functions on Infinite Sets 



Properties of Exponential and Logarithmic Functions 



OnetoOne Correspondences 





Application: The Pigeonhole Principle 


420  (11) 

Statement and Discussion of the Principle 





Decimal Expansions of Fractions 



Generalized Pigeonhole Principle 



Proof of the Pigeonhole Principle 




431  (12) 



Composition of OnetoOne Functions 



Composition of Onto Functions 



Cardinality with Applications to Computability 


443  (14) 

Definition of Cardinal Equivalence 





The Search for Larger Infinities 



The Cantor Diagonalization Process 



Application: Cardinality and Computability 




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) 



Using Formulas to Simplify Solutions Obtained by Iteration 



Checking the Correctness of a Formula by Mathematical Induction 



Discovering That an Explicit Formula Is Incorrect 



SecondOrder Linear Homogenous Recurrence Relations with Constant Coefficients 


487  

Derivation of Technique for Solving These Relations 







General Recursive Definitions 


449  (61) 



Proving Properties about Recursively Defined Sets 



Recursive Definitions of Sum, Product, Union, and Intersection 





The Efficiency of Algorithms 


510  (61) 

RealValued Functions of a Real Variable and Their Graphs 


510  (8) 







Graphing Functions Defined on Sets of Integers 



Graph of a Multiple of a Function 



Increasing and Decreasing Functions 




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) 

DivideandConquer Algorithms 



The Efficiency of the Binary Search Algorithm 





Tractable and Intractable Problems 



A Final Remark on Algorithm Efficiency 




571  (78) 


571  (13) 

Definition of Binary Relation 



Arrow Diagram of a Relation 





The Inverse of a Relation 



Directed Graph of a Relation 



Nary 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 




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 





Finding an Inverse Modulo n 





Fermat's Little Theorem and the Chinese Remainder Theorem 



Why Does the RSA Cipher Work? 




632  (17) 









Partially and Totally Ordered Sets 










649  (85) 


649  (16) 

Basic Terminology and Examples 








665  (18) 







Matrix Representations of Graphs 


683  (14) 



Matrices and Directed Graphs 



Matrices and (Undirected) Graphs 



Matrices and Connected Components 





Counting Walks of Length N 




697  (8) 

Definition of Graph Isomorphism and Examples 





Graph Isomorphism for Simple Graphs 




705  (18) 

Definition and Examples of Trees 










723  (11) 

Definition of a Spanning Tree 









Regular Expressions and FiniteState Automata 


734  

Formal Languages and Regular Expressions 


735  (10) 

Definitions and Examples of Formal Languages and Regular Expressions 



Practical Uses of Regular Expressions 




745  (18) 

Definition of a FiniteState Automation 



The Language Accepted by an Automation 



The EventualState Function 



Designing a FiniteState Automation 



Simulating a FiniteState Automation Using Software 



FiniteState Automata and Regular Expressions 





Simplifying FiniteState Automata 


763  





Finding the *Equivalence Classes 





Constructing the Quotient Automation 




Appendix A Properties of the Real Numbers 

1  (3) 
Appendix B Solutions and Hints to Selected Exercises 

4  
Index 

1  