|
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 Quotient-Remainder Theorem Discussion of the quotient-remainder 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; One-dimensional 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 Well-Ordering 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 well-ordering principle; Proof of the quotient-remainder theorem |
|
|
212 | (9) |
|
4.5 Application: Correctness of Algorithms Meaning of program correctness; General format; pre-conditions and post-conditions; 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 one-dimensional 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: r-permutations; 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 R-combinations; 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 R-Combinations with Repetition Allowed R-combinations 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 well-defined |
|
|
344 | (13) |
|
7.2 Application: Finite-State Automata Definitions and examples of finite-state automata; How to construct a finite-state automaton to do a certain job; The language accepted by a finite-state automaton; The eventual-state function; Simulating a finite-state automaton using software |
|
|
357 | (12) |
|
7.3 One-to-One and Onto, Inverse Functions Definition and examples of one-to-one and onto functions; Application to hash functions; Properties of logarithmic and exponential functions; One-to-one 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 one-to-one 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 Second-Order 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 O-Notation and the Efficiency of Algorithms |
|
|
476 | (57) |
|
9.1 Real-Valued 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 O-Notation Definition of order; Graphical interpretation; Computing orders of functions from the definition; Orders of polynomial functions; Orders of rational functions; "Best" big-oh 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 Divide-and-conquer 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; n-ary 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 Finite-State Automata An equivalence relation on the set of states of a finite-state 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 |
|
I-1 | |
Other versions by this Author