|
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 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 |
|
|
|
|
|
|
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 |
|
|
|
8-Bit 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 Multiply-Quantified 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 Quotient-Remainder Theorem |
|
|
156 | (8) |
|
Discussion of the Quotient-Remainder 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 Problem-Solving 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 Well-Ordering Principle |
|
|
235 | (9) |
|
The Principle of Strong Mathematical Induction |
|
|
|
Binary Representation of Integers |
|
|
|
The Well-Ordering 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 One-Dimensional 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 |
|
|
|
r-Combinations 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 |
|
|
|
One-to-One and Onto, Inverse Functions |
|
|
402 | (18) |
|
|
|
|
One-to-One Functions on Infinite Sets |
|
|
|
Application: Hash Functions |
|
|
|
|
|
|
Onto Functions on Infinite Sets |
|
|
|
Properties of Exponential and Logarithmic Functions |
|
|
|
One-to-One 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 One-to-One 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 |
|
|
|
Second-Order 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) |
|
Real-Valued 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) |
|
Divide-and-Conquer 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 |
|
|
|
N-ary 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 Finite-State 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 Finite-State Automation |
|
|
|
The Language Accepted by an Automation |
|
|
|
The Eventual-State Function |
|
|
|
Designing a Finite-State Automation |
|
|
|
Simulating a Finite-State Automation Using Software |
|
|
|
Finite-State Automata and Regular Expressions |
|
|
|
|
|
|
Simplifying Finite-State 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 | |
Other versions by this Author