
Chapter 1 The Logic of Compound Statements 


1  (74) 

1.1 Logical Form and Logical Equivalence Identifying logical form; Statements; Logical connectives: not, and, and or; Translation to and from symbolic notation; Statement forms and their truth tables; Exclusive or; Logical equivalence; De Morgan's laws; Tautologies and contradictions; Summary of logical equivalences 


1  (16) 

1.2 Conditional Statements Conditional statements; The negation of a conditional statement; Contrapositive; Converse and inverse; Only if and the biconditional; Necessary and sufficient conditions 


17  (11) 

1.3 Valid and Invalid Arguments Arguments, argument forms and validity; Modus ponens and modus tollens; Other argument forms; Converse and inverse errors; Relation of the validity or invalidity of an argument and the truth or falsity of its conclusion; contradiction rule; Application to solving logical puzzles 


28  (13) 

1.4 Application: Digital Logic Circuits Relation between switching circuits and Boolean expressions; Black boxes and gates; Circuits, input/output tables, and Boolean expressions; Simplifying circuits 


41  (16) 

1.5 Application: Number Systems and Circuits for Addition Binary representation of numbers; Binary addition and subtraction; Circuits for computer addition; Two's complements and the computer representation of negative integers; Hexadecimal notation 


57  (18) 

Chapter 2 The Logic of Quantified Statements 


75  (37) 

2.1 Predicates and Quantified Statements I Predicates; Set notation; Universal and existential statements; Translating between formal and informal language; Universal conditional statements; Equivalent forms of universal and existential statements; Implicit quantification; Negations of universal and existential statements; Negations of universal conditional statements; Vacuous truth of universal statements 


75  (14) 

2.2 Predicates and Quantified Statements II Alternate forms for universal conditional statements; Statements containing both "for all" and "there exists;" Relation among (XXX) and V; The use of predicates in Prolog 


89  (10) 

2.3 Arguments with Quantified Statements Valid argument forms and arguments; Rule of universal instantiation; Universal modus ponens and universal modus tollens; Proving validity; Using diagrams to test for validity; Converse and inverse errors 


99  (13) 

Chapter 3 Elementary Number Theory and Methods of Proof 


112  (68) 

3.1 Direct Proof and Counterexample I: Introduction Introduction to the basic techniques of direct proof and disproof by counterexample; Properties of even and odd integers and prime and composite numbers 


113  (12) 

3.2 Direct Proof and Counterexample II: Rational Numbers Exploring the definition and properties of rational numbers 


125  (6) 

3.3 Direct Proof and Counterexample III: Divisibility Definition of divisibility; Examples and properties; The unique factorization theorem 


131  (9) 

3.4 Direct Proof and Counterexample IV: Division into Cases and the QuotientRemainder Theorem Discussion of the quotientremainder theorem and examples; div and mod; Alternate representations of integers and applications in number theory 


140  (8) 

3.5 Direct Proof and Counterexample V: Floor and Ceiling Definition and basic properties of the floor and ceiling of a number; The floor of n/2 


148  (6) 

3.6 Indirect Argument: Contradiction and Contraposition Proof by contradiction; There is no greatest integer; The sum of a rational number and an irrational number; Proof by contraposition; When the square of an integer is even 


154  (7) 

3.7 Two Classical Theorems The irrationality of (Square root of 2); The infinitude of the primes 


161  (5) 

3.8 Application: Algorithms Notation for algorithms; Trace tables; The division algorithm; The Euclidean algorithm 


166  (14) 

Chapter 4 Sequences and Mathematical Induction 


180  (51) 

4.1 Sequences Terminology of sequences; Explicit formula for a sequence; Examples; Finding an explicit formula from initial terms; Summation notation; Telescoping sums; Transforming a sum by a change of variable; Product notation; Properties of summations and products; Factorial notation; Onedimensional arrays; Algorithm to change from decimal to binary notation 


180  (14) 

4.2 Mathematical Induction I Principle of mathematical induction; Sum of the first n integers; Sum of a geometric sequence 


194  (11) 

4.3 Mathematical Induction II Comparison of mathematical induction and inductive reasoning; Proving divisibility properties; Proving inequalities 


205  (7) 

4.4 Strong Mathematical Induction and the WellOrdering Principle Explanation and examples including proof that every integer greater than 1 is divisible by a prime, that a sequence has a certain property, that any parenthesization of a product of n distinct factors results in n  1 multiplications, and that every positive integer has a unique binary representation; The wellordering principle; Proof of the quotientremainder theorem 


212  (9) 

4.5 Application: Correctness of Algorithms Meaning of program correctness; General format; preconditions and postconditions; Loop invariants and the loop invariant theorem; Correctness of a loop to compute a product; Correctness of the division algorithm and the Euclidean algorithm 


221  (10) 


231  (42) 

5.1 Basic Definitions of Set Theory Definition of subset; Venn diagrams; Relations among sets of numbers; Distinction between (XXX) and (XXX); Definitions of equality, union, intersection, difference, and complements of sets; Cartesian products; Formal language; Algorithm for checking a subset relation 


231  (13) 

5.2 Properties of Sets List of basic set properties; How to prove set properties using element arguments (via procedural versions of definitions); Disproving proposed set properties; Deriving additional set properties from those on a basic list 


244  (14) 

5.3 The Empty Set, Partitions, Power Sets, and Boolean Algebras How to prove a set is empty; Set properties that involve the empty set; Partitions of sets; Power sets; Boolean algebras 


258  (10) 

5.4 Russell's Paradox and the Halting Problem The barber puzzle; Russell's paradox; The halting problem 


268  (5) 


273  (71) 

6.1 Counting and Probability Concept of sample space; Probability in the equally likely outcomes case; Tossing coins, rolling dice; Counting the elements of lists, sublists, and onedimensional arrays 


274  (7) 

6.2 Possibility Trees and the Multiplication Rule Possibility trees; The multiplication rule; Counting possibilities with and without repetition; Permutations; Permutations of selected elements: rpermutations; Proving properties of P(n, r). 


281  (14) 

6.3 Counting Elements of Disjoint Sets: The Addition Rule The addition rule; The difference rule; The inclusion/exclusion rule; The number of elements in a general union, the number of elements in an intersection 


295  (11) 

6.4 Counting Subsets of a Set: Combinations Rcombinations; Ordered and unordered selections; Relation between permutations and combinations; Permutations of a set with repeated elements; A common mistake: double counting 


306  (16) 

6.5 RCombinations with Repetition Allowed Rcombinations with repetition allowed; Multisets; How to count these; Applications 


322  (8) 

6.6 The Algebra of Combinations Combinatorial formulas; New formulas from old by substitution; Pascal's triangle; Algebraic and combinatorial proofs of Pascal's formula 


330  (6) 

6.7 The Binomial Theorem The binomial theorem; Algebraic and combinatorial proofs; Applications 


336  (8) 


344  (80) 

7.1 Functions Defined on General Sets Definition of a function as a relationship between the elements of two sets; Arrow diagram of a function; Function machines; Equality of functions; Examples of functions such as the identity function, sequences, functions defined on a power set, functions defined on a language, logarithmic functions, encoding and decoding functions, and Hamming distance function; Boolean functions; Determining whether a function is welldefined 


344  (13) 

7.2 Application: FiniteState Automata Definitions and examples of finitestate automata; How to construct a finitestate automaton to do a certain job; The language accepted by a finitestate automaton; The eventualstate function; Simulating a finitestate automaton using software 


357  (12) 

7.3 OnetoOne and Onto, Inverse Functions Definition and examples of onetoone and onto functions; Application to hash functions; Properties of logarithmic and exponential functions; Onetoone correspondences; Inverse functions 


369  (18) 

7.4 Application: The Pigeonhole Principle Statement and discussion of principle; Applications; Generalized pigeonhole principle and applications; Proof of the pigeonhole principle 


387  (14) 

7.5 Composition of Functions Definition and examples; Theorems on composition of onetoone and onto functions 


401  (10) 

7.6 Cardinality with Applications to Computability Definition of cardinality and countability; Countability of the set of all integers, the set of all even integers, and the set of all rational numbers; Uncountability of the real numbers; Countability of the set of all computer programs in a given computer language; Impossibility of computing certain functions 


411  (13) 


424  (52) 

8.1 Recursively Defined Sequences Definition of recurrence relation; Computing terms of recursively defined sequences; The towers of Hanoi; The Fibonacci numbers; Compound interest; Number of bit strings with a certain property; Number of partitions of a set into r subsets; Stirling numbers of the second kind 


424  (17) 

8.2 Solving Recurrence Relations by Iteration Finding explicit formulas for recursively defined sequences by iteration; Arithmetic and geometric sequences; Using mathematical induction to check whether a recursively defined sequence satisfies a given explicit formula 


441  (12) 

8.3 SecondOrder Linear Homogeneous Recurrence Relations with Constant Coefficients Technique for solving these special relations; Formula for the Fibonacci sequence; Gambler's ruin 


453  (13) 

8.4 General Recursive Definitions Recursive definition of Boolean expressions, parentheses structures, arithmetic expressions, (XXX), Pi, and finite unions and intersections; Recursively defined functions 


466  (10) 

Chapter 9 ONotation and the Efficiency of Algorithms 


476  (57) 

9.1 RealValued Functions of a Real Variable and Their Graphs Graph of a function; Graphs of integral and fractional power functions; Graph of the floor function; Graphs of functions defined on sets of integers; The graph of a multiple of a function; Increasing and decreasing functions 


476  (9) 

9.2 ONotation Definition of order; Graphical interpretation; Computing orders of functions from the definition; Orders of polynomial functions; Orders of rational functions; "Best" bigoh approximation 


485  (10) 

9.3 Application: Efficiency of Algorithms I Use of the order notation to discuss algorithm efficiency; Computing orders of simple algorithms; Calculating the efficiency of the sequential search, insertion sort, and selection sort algorithms; Comparing algorithms for polynomial evaluation 


495  (10) 

9.4 Exponential and Logarithmic Functions: Graphs and Orders Graphs of logarithmic and exponential functions; Consequences of the fact that the logarithmic function with base b Greater than 1 is increasing; The number of bits needed to represent an integer in binary notation; Using logarithms to solve a recurrence relation; Exponential and logarithmic orders 


505  (14) 

9.5 Application: Efficiency of Algorithms II Divideandconquer algorithms; Calculating the efficiency of the binary search and merge sort algorithms 


519  (4) 


533  (69) 

10.1 Relations on Sets Definition and notation for relations; Examples of relations; Inverse of a relation; Arrow diagram of a relation; Functions and relations; Directed graph of a relation; nary relations and relational databases 


533  (13) 

10.2 Reflexivity, Symmetry, and Transitivity Reflexive, symmetric, and transitive properties; Transitive closure of a relation; Properties of relations on infinite sets 


546  (9) 

10.3 Equivalence Relations The relation induced by a partition; Equivalence relations; Examples such as congruence classes modulo n and equivalence of digital logic circuits; Equivalence classes; Lemma that two elements are equivalent if, and only if, they are in the same class; Theorem on the partition of a set by an equivalence relation; Examples of equivalence classes 


555  (17) 

10.4 Application: Simplifying FiniteState Automata An equivalence relation on the set of states of a finitestate automaton; The quotient automaton; Equivalent automata 


572  (13) 

10.5 Partial Order Relations Definition and examples; Lexicographic order; Hasse diagrams; Partially and totally ordered sets; Topological sorting; PERT and CPM 


585  (17) 

Chapter 11 Graphs and Trees 


602  (93) 

11.1 Graphs: An Introduction Basic terminology and examples of graphs and directed graphs (communication network, representation of a knowledge system, state graph); Special graphs (simple graphs, complete graphs, bipartite graphs); Subgraphs; The concept of degree; Relation of total degree to number of edges; Applications 


602  (17) 

11.2 Paths and Circuits The puzzle of the Konigsberg bridges; Basic definitions of walks, paths, and circuits; Connectedness; Euler circuits; Euler's theorem; Algorithm for constructing an Euler circuit; Hamiltonian circuits; The traveling salesperson problem 


619  (21) 

11.3 Matrix Representations of Graphs Matrix notation; Adjacency matrices of directed and undirected graphs; Matrices and connected components; Matrix multiplication; Using matrix entries to find the number of walks of length n in a graph 


640  (16) 

11.4 Isomorphisms of Graphs Definition of graph isomorphism; Examples; Finding all nonisomorphic graphs with certain properties; isomorphic invariants; Using isomorphic invariants to show that graphs are not isomorphic; Graph isomorphism for simple graphs 


656  (8) 

11.5 Trees Definition and examples of trees (decision tree, derivation tree, structure of hydrocarbon molecules); Equivalent characterizations of trees; Determining number of trees with certain properties; Rooted trees; Binary trees 


664  (19) 

11.6 Spanning Trees Definition of a spanning tree; Proof of existence; Kruskal's and Prim's algorithms for finding the minimal spanning tree of a weighted graph 


683  (12) 
Appendix A Properties of the Real Numbers 

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

698  (102) 
Photo Credits 

800  
Index 

I1  