Includes index (I1-I14 p.)

1 Speaking Mathematically

1 Variables . Using Variables in Mathematical Discourse Introduction to Universal Existential and Conditional Statement :

6 The Language of Set. The Set-Roster and set Builder Notations: Subsets Cartesian Products

13 The Language of Relations and Functions . Definition of a Relation from one set to Another: Arrow Diagram of a Rotation : Definition of Function: function machines : Equality of Functions

23 The Logic of Compound Statements

23 Logical Form and Logical Equivalence. Statement Compound Statements: Truth Values: Evaluating the Truth of More General Compound Statements: Logical Equivalence: Tautologies and Contradictions Summary of Logical Equivalence

39 Conditional Statements . Logical Equivalence Involving : Representation of Fi 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 Condition Remark

51 Valid and Invalid Arguments. Modus Ponens and Modus Tollens: Additional Valid Argument Forms: Rules of Inference: Fallacies: Contradiction and Valid Arguments Summary of Rules of Inference

64 Application Digital Logic Circuits. Black Boxes and Gates: The Input/output table for a Circuit, The Boolean Expression Corresponding to a Circuit That Corresponds to a Given Input/output table Simplifying Combinational Circuits NAND and NOR gates

78 Application: Number System and Circuits for Addition. Binary Representation of Number: Binary Addition and Subtraction, Circuits to Computer Addition Two's Complements and the Computer Representation of Negative Integers 8-Bit Representation of a Number Computer Addition with Negative Integers: Hexadecimal Notation

96 The Logic of Quantified Statements

96 Predicates and Quantified Statements I The Universal Quantified : ∀ : The Existential Quantifier ∃: Formal Versus Informal Language: Universal Conditional Statements Equivalent Forms of Universal and Existential Statements Implicit Quantification: Tarki's World

108 Predicates and Quantifies Statements II . Negations of Quantified Statements: Negations of Universal Conditional Statements : The Relation Among ∀,∃,∧ AND v: Various Truth of Universal Statements Variants of Universal Conditional Statements: Necessary and Sufficient Conditions Only if.

117 Statements with Multiple Quantifiers. Translating from informed to Formal Language: Ambiguous Language: Negations of Multiply-Quantified Statements : Order of Quantifiers: Formed Logical Notation Prelog

145 ELEMENTARY NUMBER THEORY AND METHODS OF PROOF.

146 Elementary Number Theory and Method of proof

146 Direct Proof and Counterexamples I: Introduction : Definitions: Proving Existential statements: Disproving Universal Statements by Counterexamples: Proving Universal Statements: Directions for Writing Proofs of Universal Statements Variation among proofs Common Mistakes Getting Proofs Started Showing that an Existential Statement is False Conjecture, Proof, and Disproof,

163 Direct Proof and Counterexample II: Rational Number :More on Generalizing from the Genetic Particular: Proving Properties of Rational Numbers: Deriving New Mathematics From Old

170 Direct Proof and Counterexample III: Divisibility Proving Properties of Divisibility : Counterexamples and Divisibility: The Unique Factorization of Integers Theorem

180 Direct Proof and Counterexamples IV: Division Into Cases and the Quotient Reminder Theorem Discussion of the Quotient-Reminder Theorem and Examples div and mod :alternative Representations of Integers and Application to Numbers Theory: Absolute Value and the Triangle Inequality.

191 Direct Proof and Counterexample V: Floor and Ceiling Definition and Basic Properties : The Floor n/2

198 Indirect Argument: Contradiction and Contraposition Proof by Contradiction: Relation Between Proof by Contradiction and Poof by Contraposition, Proof as a problem Problem Solving Tool.

207 Indirect Argument : Two Classical Theorems The Irrationality of √2: Are There Infinity Many Prime Number? When to Use Indirect Proof. Open Questions In Number Theory

214 Application Algorithm An Algorithm Language: A Notation for Algorithm: Trace Tables: The Division Algorithm The Euclidean Algorithm

227 Sequences Mathematical Induction and Recursion

227 Sequences. Explicit Formulas For Sequences. Summation Notation, Product Notation Properties of Summations and Products Change of Variable Factorial and n Choose r Notation Sequences in Computer Programming, Application ; Algorithm to Convert From BASE 10 to 2 Using Repeated Division by 2

244 Mathematical Induction I Principle of Mathematical Induction Sum if the First n Integers: Proving an Equality Properties: Proving Inequalities Sum of a Geometric Sequence

258 Mathematical Induction II Comparison of Mathematical Induction and Inductive Reasoning : Proving Divisibility Properties Proving Inequalities : A Problem with Trominoes

268 Strong Mathematical Induction and the well-Ordering Principles for the Integers. Strong Mathematical Induction: Binary Representation of Integers The Well Ordering Principles for the Integers

279 Application: Correctness of Algorithms. Assertion: Loop Invariants: Correctness of the Division Algorithm: Correctness of the Euclidean Theorem

290 Defining Sequence Recursively. Definition of Recurrence Relation: Examples of Recursively Defined Sequence Recursive Definitions of Sum and Product

304 Solving Recurrence Relations by Iteration The method of Iteration: Using formulas to Simply Solutions Obtained by lteration Checking the Correctness of a formula by Mathematical Induction: Discovering That an Explicit Formula Is Incorrect

317 Second -Order Linear Homogenous Recurrence Relations With Constant Coefficients Derivation of a Technique for Solving These Relations The Distinct-Roots Case The Single-Root Case

328 General Recursive Definitions and Structural Induction Recursively Defined Sets: Using Structural Induction tp prove Properties about Recursively Defined Sets: Recursive Functions

336 Set Theory

336 Set Theory: Definitions and the Element Method of Proof Subject: Proof and Disproof, set Equality : Venn Diagrams Operations on Sets The Empty Set Partitions of Sets Power sets Cartesian Products An Algorithm to Check Whether One Set is a Subset of Another (Optional)

352 Properties of Sets Set Identities Proving Set Identities: Proving That a Set is the Empty Set

367 Disproofs and Algebraic Proofs. Disproving an Alleged Set Property: Problem Solving Strategy : The Number of Subset of a Set Algebraic Proofs of Set Identities

374 Boolean Algebras, Russell's Paradox and the Halting Problem. Boolean Algebras: Description of Russell's Paradox The halting problem

383 Functions

383 Functions Defined on General Sets Additional Function Terminology: More Examples of Functions Boolean Functions Checking Whether a Function is Well Defined: Function Acting on Sets.

397 One to One and Onto. Inverse Functions. One-to-One Function: One-to-One Function on Infinite Sets: Application Hash Functions: Onto Functions: Onto Functions on Infinite Sets Relations Between Exponential and Logarithmic Functions : One -to -One Correspondences, Inverse Function

416 Composition of Function . Definition and Examples: Composition of One-to-One Functions: Composition of Onto Functions.

428 Cardinally With Applications to Computability Definition of Cardinal Equivalence: Countable Sets :The Search For Larger Infinities The cantor Diagonalization Process Application Cardinally and Computability

442 Relations

442 Relations on Sets. Additional Examples of Relations: The Inverse of a Relation: Directed Graph of a Relation N-ary Relations and Relational Database

449 Reflexivity, Symmetry and Transitivity. Reflexive, Symmetric, and Transitive Properties : Properties of Relations on Infinite Sets The Transitive Closure of an Equivalence Relation

459 Equivalence Relations. The Relation Induced By a Partition: Definition of an Equivalence Relation: Equivalence Classes of an Equivalence Relation,

479 Modular Arithmetic with Application to Cryptography. Properties of Congruence Modulo n: Modular Arithmetic Extending the Euclidean Algorithm: Finding an Inverse Modula n: RSA cryptography Eulid's Lemmk Fermat's Little Theorem: They Does The RSA Cipher Work?: Additional Remark on Number Theory and Cryptography

498 Partial Order Relations . Antisymmetry: Partial Order Relations: Lexicographic Order: Hasse Diagram Partially and Totally Ordered Sets; Topological Sorting : An Application PERT and CPM

516 Counting and Probability

517 Introduction. Definition of Sample Space and Event Probability in the Equally Likely Case Counting the Elements of Lists Sublists and One-Dimensional Arrays

525 Possibility Trees and the Multiplication Rule Possibility Trees: The Multiplications Rule: When the Multiplication Rule Is Difficult or Impossible to Apply: Permutations: Permutation of Selected Elements

540 Counting Elements of Disjoint set: The Addition Rule The Inclusive /Exclusion Rule

554 The Pigeonhole Principle. Statement and Discussion of the Principle: Applications Decimal Expansion of Fractions Generalized Pigeonhole Principle: Proof of the Pigeonhole Principles

565 Countıng Subset of a set Combination; r-Combination: Ordered and Unordered Selection : Relation between permutations and Combination Permutation of a set With Respond Elements: Some Advice about Counting: The Number of Partition of a Set into r Subsets

584 r-Combination with Repetition Allowed Multisets and how to Count Them which Formula to Use?

592 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 to it Applications

605 Probability Axioms and Expected Value Probability Axioms Deriving Additional Probability Formulas . Expected Value

611 Conditional Probability Bayes Formula and Independent Event. Conditional Probability Bayes Theorem Independent Event

625 Graphs and Trees

625 Graphs Definitions and Basic Properties. Basic Terminology and Example of Graph Special Graphs The Concepts of Degree

642 Trails. Paths and Circuits.Definitions Connectedness, Euler Circuits Hamiltonian Circuits

661 Matrix Representation of Graph :Matrices Matrices and Directed Graph Matrices and Undirected Graphs. Matrices and Connected Components : Matrix multiplication Counting Walks of Length N

675 Isomorphisms of Graphs. Definition of Graph Isomorphisms and Examples Isomorphic Invariants : Graph Isomorphism for simple Graphs

683 Trees Definition and Examples of Trees Characterizing Trees

694 Rooted Trees Definition and Examples of Rooted Trees Binary Trees and their Properties

701 Spanning Tree and Shortest Paths Definition of a Spanning Tree Minimum Spanning Trees Kruskal's Algorithm Prim's Algorithm Dijkurn's Shortest Path Algorithm

717 Analysis of Algorithm Efficiency

717 Real -Valued Functions of A Real Variable and Their Graphs. Graph of a Function Power Functions The Floor Function Graphing Function Defined on Sets of Integer Graph of a Multiple of a Function of Increasing and Decreasing Functions

725 O Ω and θ Notations Definition and General Properties of O Ω and θ Notations Orders of Power Functions: Orders of Polynomial Functions Orders For Function: Integer Variable : Extension to Functions Composed of Rational Power Functions.

739 Application Analysis of Algorithm Efficiency I Computing Orders of Simple Algorithm: The Sequential Search Algorithm: The Insertion Sort Algorithm : Time Efficiency of an Algorithm

751 Exponential and Logarithmic Functions Graph and Orders . Graph 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

764 Application: Analysis of Algorithm Efficiency II; Binary Search: Divide-and-Conquer Algorithms: The Efficiency of the Binary Search Algorithm: Merge Sort : Tractable and Intractable Problems: A Final Remark on Algorithm Efficiency

779 Regular Expressions and Finite-State Automata

780 Formal Language and Regular Expression. Definitions and examples of formal Language and Regular Expressions: The Language Defined by a Regular Expressions: Practical Uses of Regular Expressions

791 Finite-State Automata. Definition of a Finite-State Automation: The Language Accepted by an Automation: The Eventual-State Function: Designing a finite -state Automation Stimulating a Finite-State Automation Using Software Finite-state Automata and Regular Expression Regular Languages

808 Simplifying finite-State Automata. *- Equivalence of State :k-Equivalence of State: Finding The *-Equivalence Classes: The Quotient Automation Constructing the Quotation Automation Equivalent Automata

A-1 AppendIx A Properties of the Real Numbers

A-4 Appendix B Solutions and Hints to Selected Exercises

I-1 Index