issuhub.com

Discrete Mathematics for Computer Science

(Romina) #1

  • x e A x is an element ofA 1. Sets, Proof Templates, and Induction

  • x f A x is not an element ofA 1.

    • Ix x E A and P(x)} Set notation 1.



  • 2 Integers 1.1. N Natural numbers 1.1.1l

  • Q Rationals 1.1.

  • R Real numbers I.1.

  • A = B Sets A and B are equal 1.1.

  • A C B A is a subset of B 1.1.

    • A g B A is nota subset of B 1.1.

    • A C B A is a proper subset of B 1.1.

    • A 5 B A is nota proper subset of B 1.1.



  • b=•a bimplies a i.1.

  • a b a if and only if b 1.1.

  • AUB A union B 1.3.

  • AFnB A intersect B 1.3.

  • UX Generalized union of family of sets X 1.3.

  • nX Generalized intersection of family of sets X 1.3.

    • Um Xi Xm U ...UXn 1.3.

    • nt=Mxi Xm n n Xn 1.3.

    • A - B Elements of A not in B 1.3.



  • A Elements not in A 1.3.

    • A D B (A U B) - (A n B) 1.3.

    • P(X) Power set of X 1.3.

    • X x Y Product of X and Y 1.3.



  • x A y Meet ofx and y 1.3.

  • x v y Join ofx and y 1.3.

    • -x Complement of x 1.3.

    • T Top 1.



  • I Bottom 1.3.

    • JAI Cardinality of A 1.5.

      • Si a,, + " -". + a,, 1.7.





  • "--p Not p 2. Formal Logic

  • pAq p and q 2.

  • pvq p or q 2.

  • p q p implies q 2.

  • p q p is equivalent to q 2.

  • S X S logically implies X 2.3.

  • P 3 AKP Conjecture about complexity 2.5.

  • (Vx)P(x) For all x, P(x) 2.7.

  • (3x)P(x) There exists an x such that P(x) 2.7.

  • (VxE V)P(x) For all X EV, P(x) 2.7.

    • (3x E V)P(x) There exists an x E V such that P(x) 2.7.



  • A[i ..j] Array with elements Ail, ..., A[j] 2.7.

  • 1 Sheffer stroke 2.

  • V Exclusive or 2.

  • 4, Pierce arrow 2.

  • (x, y) E R or xRy x is R-related to y 3.

  • R-1 The inverse of the relation R 3.2.

  • RoS Composition of relations R and S 3.2.

  • R+ U°° Ri 3.4.

  • R* URO R' 3.4.

  • n =- m(modp) n - m = kp for some k E N 3.

  • Idx Identity relation 3.

  • Lex Less than or equal relation 3.

  • Gtx Greater than relation 3.

  • Gex Greater than or equal relation 3.

  • [x] Equivalence class of x 3.

  • min m divides n 3.8.

  • R D. S Equijoin of relations R and S 3.10.

  • CHAPTER

    • 1.1 Basic Definitions Sets, Proof Templates, and Induction

      • 1.1.1 Describing Sets Mathematically

      • 1.1.2 Set Membership

      • 1.1.3 Equality of Sets

      • 1.1.4 Finite and Infinite Sets

      • 1.1.5 Relations Between Sets

      • 1.1.6 Venn Diagrams

      • 1.1.7 Templates



    • 1.2 Exercises

    • 1.3 Operations on Sets

      • 1.3.1 Union and Intersection

      • 1.3.2 Set Difference, Complements, and DeMorgan's Laws

      • 1.3.3 New Proof Templates

      • 1.3.4 Power Sets and Products

      • 1.3.5 Lattices and Boolean Algebras



    • 1.4 Exercises

    • 1.5 The Principle of Inclusion-Exclusion

      • 1.5.1 Finite Cardinality

      • 1.5.2 Principle of Inclusion-Exclusion for Two Sets

      • 1.5.3 Principle of Inclusion-Exclusion for Three Sets

      • 1.5.4 Principle of Inclusion-Exclusion for Finitely Many Sets



    • 1.6 Exercises

      • 1.7 Mathematical Induction viii Contents

        • 1.71 A First Form of Induction

        • 1.72 A Template for Constructing Proofs by Induction

        • 1.73 Application: Fibonacci Numbers

        • 1.74 Application: Size of a Power Set

        • 1.75 Application: Geometric Series



      • 1.8 Program Correctness

        • 1.8.1 Pseudocode Conventions

        • 1.8.2 An Algorithm to Generate Perfect Squares

          • 1.8.3 Two Algorithms for Computing Square Roots





      • 1.9 Exercises

      • 1.10 Strong Form of Mathematical Induction

        • 1.10.1 Using the Strong Form of Mathematical Induction

        • 1.10.2 Application: Algorithm to Compute Powers

        • 1.10.3 Application: Finding Factorizations

        • 1.10.4 Application: Binary Search



      • 1.11 Exercises

      • 1.12 Chapter Review

        • 1.12.1 Summary

        • 1.12.2 Starting to Review

        • 1.12.3 Review Questions

        • 1.12.4 Using Discrete Mathematics in Computer Science





    • CHAPTER



  • Formal Logic

    • 2.1 Introduction to Propositional Logic

      • 2.1.1 Formulas

      • 2.1.2 Expression Trees for Formulas

      • 2.1.3 Abbreviated Notation for Formulas

      • 2.1.4 Using Gates to Represent Formulas



    • 2.2 Exercises

    • 2.3 Truth and Logical Truth

      • 2.3.1 Tautologies

        • 2.3.2 Substitutions into Tautologies Contents ix

        • 2.3.3 Logically Valid Inferences

        • 2.3.4 Combinatorial Networks

        • 2.3.5 Substituting Equivalent Subformulas

        • 2.3.6 Simplifying Negations



      • 2.4 Exercises

      • 2.5 Normal Forms

        • 2.5.1 Disjunctive Normal Form

        • 2.5.2 Application: DNF and Combinatorial Networks

        • 2.5.3 Conjunctive Normal Form

        • 2.5.4 Application: CNF and Combinatorial Networks

        • 2.5.5 Testing Satisfiability and Validity

        • 2.5.6 The Famous 'P Af r Conjecture

        • 2.5.7 Resolution Proofs: Automating Logic



      • 2.6 Exercises

      • 2.7 Predicates and Quantification

        • 2.71 Predicates

        • 2.72 Quantification

        • 2.73 Restricted Quantification

        • 2.74 Nested Quantifiers

        • 2.75 Negation and Quantification

        • 2.76 Quantification with Conjunction and Disjunction

        • 2.77 Application: Loop Invariant Assertions





    • 2.8 Exercises

    • 2.9 Chapter Review

      • 2.9.1 Summary

      • 2.9.2 Starting to Review

      • 2.9.3 Review Questions

      • 2.9.4 Using Discrete Mathematics in Computer Science



    • CHAPTER



  • Relations

    • 3.1 Binary Relations

      • 3.1.1 n-ary Relations





  • 3.2 Operations on Binary Relations x Contents

    • 3.2.1 Inverses

    • 3.2.2 Composition



  • 3.3 Exercises

  • 3.4 Special Types of Relations

    • 3.4.1 Reflexive and Irreflexive Relations

      • 3.4.2 Symmetric and Antisymmetric Relations



    • 3.4.3 Transitive Relations

    • 3.4.4 Reflexive, Symmetric, and Transitive Closures

      • 3.4.5 Application: Transitive Closures in Medicine and Engineering



    • 3.5 Exercises

    • 3.6 Equivalence Relations

      • 3.6.1 Partitions

      • 3.6.2 Comparing Equivalence Relations



    • 3.7 Exercises

    • 3.8 Ordering Relations

      • 3.8.1 Partial Orderings

      • 3.8.2 Linear Orderings

      • 3.8.3 Comparable Elements

      • 3.8.4 Optimal Elements in Orderings

      • 3.8.5 Application: Finding a Minimal Element

      • 3.8.6 Application: Embedding a Partial Order



    • 3.9 Exercises

    • 3.10 Relational Databases: An Introduction

      • 3.10.1 Storing Information in Relations

      • 3.10.2 Relational Algebra

      • 3.11 Exercises

      • 3.12 Chapter Review

        • 3.12.1 Summary

          • 3.12.2 Starting to Review

          • 3.12.3 Review Questions

          • 3.12.4 Using Discrete Mathematics in Computer Science







    • CHAPTER Contents xi



  • Functions

    • 4.1 Basic Definitions

      • 4.1.1 Functions as Rules

      • 4.1.2 Functions as Sets

      • 4.1.3 Recursively Defined Functions

      • 4.1.4 Graphs of Functions

      • 4.1.5 Equality of Functions

      • 4.1.6 Restrictions of Functions

      • 4.1.7 Partial Functions

      • 4.1.8 1-1 and Onto Functions

      • 4.1.9 Increasing and Decreasing Functions



    • 4.2 Exercises

    • 4.3 Operations on Functions

      • 4.3.1 Composition of Functions

      • 4.3.2 Inverses of Functions

      • 4.3.3 Other Operations on Functions



    • 4.4 Sequences and Subsequences

    • 4.5 Exercises

    • 4.6 The Pigeon-Hole Principle

      • 4.6.1 k to 1 Functions

      • 4.6.2 Proofs of the Pigeon-Hole Principle

      • 4.6.3 Application: Decimal Expansion of Rational Numbers

      • 4.6.4 Application: Problems with Divisors and Schedules

      • 4.6.5 Application: Two Combinatorial Results



    • 4.7 Exercises

    • 4.8 Countable and Uncountable Sets

      • 4.8.1 Countably Infinite Sets

      • 4.8.2 Cantor's First Diagonal Argument

      • 4.8.3 Uncountable Sets and Cantor's Second Diagonal Argument

      • 4.8.4 Cardinalities of Power Sets



    • 4.9 Exercises

    • 4.10 Chapter Review xii Contents

      • 4.10.1 Summary

      • 4.10.2 Starting to Review

      • 4.10.3 Review Questions

      • 4.10.4 Using Discrete Mathematics in Computer Science



    • CHAPTER



  • Analysis of Algorithms

    • 5.1 Comparing Growth Rates of Functions

      • 5.1.1 A Measure for Comparing Growth Rates

      • 5.1.2 Properties of Asymptotic Domination

      • 5.1.3 Polynomial Functions

        • 5.1.4 Exponential and Logarithmic Functions





    • 5.2 Exercises

      • 5.3 Complexity of Programs

        • 5.3.1 Counting Statements

        • 5.3.2 Two Algorithms Illustrating Selection

        • 5.3.3 An Algorithm Illustrating Repetition

        • 5.3.4 An Algorithm Illustrating Nested Repetition

        • 5.3.5 Time Complexity of an Algorithm

        • 5.3.6 Variants on the Definition of Complexity



      • 5.4 Exercises

      • 5.5 Uncomputability

        • 5.5.1 The Halting Problem



      • 5.6 Chapter Review

        • 5.6.1 Summary

        • 5.6.2 Starting to Review

        • 5.6.3 Review Questions

        • 5.6.4 Using Discrete Mathematics in Computer Science





    • CHAPTER Contents xiii



  • Graph Theory

    • 6.1 Introduction to Graph Theory

      • 6.1.1 Definitions

      • 6.1.2 Subgraphs



    • 6.2 The Handshaking Problem

    • 6.3 Paths and Cycles

      • 6.3.1 Hamiltonian Cycles



    • 6.4 Graph Isomorphism

    • 6.5 Representation of Graphs

      • 6.5.1 Adjacency Matrix

      • 6.5.2 Adjacency Lists



    • 6.6 Exercises

    • 6.7 Connected Graphs

      • 6.71 The Relation CONN

      • 6.7.2 Depth First Search

      • 6.7.3 Complexity of Dfs

      • 6.74 Breadth First Search

      • 6.7.5 Finding Connected Components



    • 6.8 The K6nigsberg Bridge Problem

      • 6.8.1 Graph Tracing



    • 6.9 Exercises

    • 6.10 Trees

      • 6.10.1 Definition of Trees

      • 6.10.2 Characterization of Trees



    • 6.11 Spanning Trees

      • 6.11.1 Kruskal's Algorithm

      • 6.11.2 Correctness of Kruskal's Algorithm

      • 6.11.3 Kruskal's Algorithm for Weighted Graphs

      • 6.11.4 Correctness of Kruskal's Weighted Graph Algorithm



    • 6.12 Rooted Trees xiv Contents

      • 6.12.1 Binary Trees

      • 6.12.2 Binary Search Trees

        • 6.12.3 Tree Traversals



      • 6.12.4 Application: Decision Trees

      • 6.13 Exercises

      • 6.14 Directed Graphs

        • 6.14.1 Basic Definitions

        • 6.14.2 Directed Trails, Paths, Circuits, and Cycles

        • 6.14.3 Directed Graph Isomorphism



      • 6.15 Application: Scheduling a Meeting Facility

        • 6.15.1 WAITFOR Graphs



      • 6.16 Finding a Cycle in a Directed Graph

        • 6.16.1 Directed Cycle Detection Algorithm

        • 6.16.2 Correctness of Directed Cycle Detection



      • 6.17 Priority in Scheduling

        • 6.171 Algorithm for Topological Sort

        • 6.172 Correctness of Topological Sort Algorithm



      • 6.18 Connectivity in Directed Graphs

        • 6.18.1 Strongly Connected Directed Graphs

        • 6.18.2 Application: Designing One-Way Street Grids



      • 6.19 Eulerian Circuits in Directed Graphs

      • 6.20 Exercises

      • 6.21 Chapter Review

        • 6.21.1 Summary

        • 6.21.2 Starting to Review

        • 6.21.3 Review Questions

        • 6.21.4 Using Discrete Mathematics in Computer Science





    • CHAPTER



  • Counting and Combinatorics

    • 7.1 Traveling Salesperson's Problem

    • 7.2 Counting Principles Contents xv

      • 7.2.1 The Multiplication Principle

      • 72.2 Addition Principle



    • 7.3 Set Decomposition Principle

      • 7.3.1 Counting the Complement

      • 73.2 Using the Pigeon-Hole Principle

      • 7.3.3 Application: UNIX Logon Passwords



    • 7.4 Exercises

    • 7.5 Permutations and Combinations

      • 7.5.1 Permutations

      • 7.5.2 Linear Arrangements

      • 75.3 Circular Permutations

      • 7.5.4 Combinations

      • 7.5.5 Poker Hands

      • 75.6 Counting the Complement

      • 7.5.7 Decomposition into Subproblems





  • 7.6 Constructing the kth Permutation

    • 7.7 Exercises

    • 7.8 Counting with Repeated Objects

      • 7.8.1 Permutations with Repetitions

        • 78.2 Combinations with Repetitions





    • 7.9 Combinatorial Identities

      • 79.1 Binomial Coefficients

        • 79.2 Multinomials







  • 7.10 Pascal's Triangle

  • 7.11 Exercises

  • 7.12 Chapter Review

    • 712.1 Summary

    • 7.12.2 Starting to Review

    • 712.3 Review Questions

    • 7.12.4 Using Discrete Mathematics in Computer Science

    • CHAPTER xvi Contents



  • Discrete Probability

    • 8.1 Ideas of Chance in Computer Science

      • 8.11 Introductory Examples

      • 8.1.2 Basic Definitions

      • 8.1.3 Frequency Interpretation of Probability

      • 8.1.4 Introductory Example Reconsidered

      • 8.1.5 The Combinatorics of Uniform Probability Density

      • 8.1.6 Set Theory and the Probability of Events



    • 8.2 Exercises

    • 8.3 Cross Product Sample Spaces

      • 8.3.1 A Multiplication Principle

      • 8.3.2 The Cross Product of Sample Spaces

      • 8.3.3 Bernoulli Trial Processes

      • 8.3.4 Events of Cross Product Form

        • 8.3.5 Two Ways of Viewing Events



      • 8.4 Exercises

      • 8.5 Independent Events and Conditional Probability

        • 8.5.1 Independent Events

        • 8.5.2 Introduction to Conditional Probability

        • 8.5.3 Exploring Conditional Probability

        • 8.5.4 Using Bayes' Rule with the Theorem of Total Probability



      • 8.6 Exercises

      • 8.7 Discrete Random Variables

        • 8.7.1 Distributions of a Random Variable

        • 8.72 The Binomial Distribution

        • 8.73 The Hypergeometric Distribution

        • 8.74 Expectation of a Random Variable

        • 8.75 The Sum of Random Variables



      • 8.8 Exercises

      • 8.9 Variance, Standard Deviation, and the Law of Averages

        • 8.9.1 Variance and Standard Deviation

        • 8.9.2 Independent Random Variables





    • 8.10 Exercises Contents xvii

    • 8.11 Chapter Review

      • 8.11.1 Summary

      • 8.11.2 Starting to Review

      • 8.11.3 Review Questions

      • 8.11.4 Using Discrete Mathematics in Computer Science



    • CHAPTER



  • Recurrence Relations

    • 9.1 The Tower of Hanoi Problem

      • 9.1.1 Recurrence Relation for the Tower of Hanoi Problem

      • 9.1.2 Solving the Tower of Hanoi Recurrence



    • 9.2 Solving First-Order Recurrence Relations

      • 9.2.1 Solving First-Order Recurrences Using Back Substitution



    • 9.3 Exercises

    • 9.4 Fibonacci Recurrence Relation

      • 9.4.1 Second Order-Recurrence Relations

      • 9.4.2 Solving the Fibonacci Recurrence

      • 9.4.3 Rules for Solving Second-Order Recurrence Relations



    • 9.5 Exercises

    • 9.6 Divide and Conquer Paradigm

    • 9.7 Binary Search

      • 9.71 Correctness

      • 9.72 Complexity



    • 9.8 Merge Sort

      • 9.8.1 Correctness

      • 9.8.2 Example

      • 9.8.3 Complexity



    • 9.9 Multiplication of n-Bit Numbers

    • 9.10 Divide-and-Conquer Recurrence Relations

      • 9.10.1 Complexity of Divide-and-Conquer Recurrence Relations



    • 9.11 Exercises xviii Contents

    • 9.12 Chapter Review

      • 9.12.1 Summary

      • 9.12.2 Starting to Review

      • 9.12.3 Review Questions

      • 9.12.4 Using Discrete Mathematics in Computer Science





  • Appendix A APPENDIX

  • Appendix B

    • Index



Free download pdf
Get our desktop app
Company
Features
Documentation
Resources
© ISSUHUB. 2024. All rights reserved.