**Discrete Mathematics**

Sandy Irani

zyBooks 2017

Table of Contents

**1. Logic**

1.1 Propositions and logical operations

1.2 Evaluating compound propositions

1.3 Conditional statements

1.4 Logical equivalence

1.5 Laws of propositional logic

1.6 Predicates and quantifiers

1.7 Quantified Statements

1.8 De Morgan’s law for quantified statements

1.9 Nested quantifiers

1.10 More nested quantified statements

1.11 Logical reasoning

1.12 Rules of inference with propositions

1.13 Rules of inference with quantifiers

**2. Proofs**

2.1 Introduction to proofs

2.2 Direct proofs

2.3 Proof by contrapositive

2.4 Proof by contradiction

2.5 Proof by cases

**3. Sets**

3.1 Sets and subsets

3.2 Set of sets

3.3 Union and intersection

3.4 More set operations

3.5 Set identities

3.6 Cartesian products

3.7 Partitions

**4. Functions**

4.1 Definition of functions

4.2 Floor and ceiling functions

4.3 Properties of Functions

4.4 The Inverse of a function

4.5 Composition of functions

4.6 Logarithms and exponents

**5. Boolean Algebra**

5.1 An introduction to Boolean algebra

5.2 Boolean functions

5.3 Disjunctive and conjunctive normal form

5.4 Functional completeness

5.5 Boolean satisfiability

5.6 Gates and circuits

**6. Relations / Digraphs**

6.1 Introduction to binary relations

6.2 Properties of binary relations

6.3 Directed graphs, paths, and cycles

6.4 Composition of relations

6.5 Graph powers and the transitive closure

6.6 Matrix multiplication and graph powers

6.7 Partial orders

6.8 Strict orders and directed acyclic graphs

6.9 Equivalence relations

6.10 N-ary relations and relational databases

**7. Computation**

7.1 An introduction to algorithms

7.2 Asymptotic growth of functions

7.3 Analysis of algorithms

7.4 Finite state machines

7.5 Turing machines

7.6 Decision problems and languages

**8. Induction And Recursion**

8.1 Sequences

8.2 Recurrence relations

8.3 Summations

8.4 Mathematical induction

8.5 More inductive proofs

8.6 Strong induction and well-ordering

8.7 Loop invariants

8.8 Recursive definitions

8.9 Structural induction

8.10 Recursive algorithms

8.11 Induction and recursive algorithms

8.12 Analyzing the time complexity of recursive algorithms

8.13 Divide-and-conquer algorithms: Introduction and mergesort

8.14 Divide-and-conquer algorithms: Binary search

8.15 Solving linear homogeneous recurrence relations

8.16 Solving linear non-homogeneous recurrence relations

8.17 Divide-and-conquer recurrence relations

**9. Integer Properties**

9.1 The Division Algorithm

9.2 Modular arithmetic

9.3 Prime factorizations

9.4 Factoring and primality testing

9.5 Greatest common divisor and Euclid’s algorithm

9.6 Number representation

9.7 Fast exponentiation

9.8 Introduction to cryptography

9.9 The RSA cryptosystem

**10. Introduction To Counting**

10.1 Sum and product rules

10.2 The bijection rule

10.3 The generalized product rule

10.4 Counting permutations

10.5 Counting subsets

10.6 Subset and permutation examples

10.7 Counting by complement

10.8 Permutations with repetitions

10.9 Counting multisets

10.10 Assignment problems: Balls in bins

10.11 Inclusion-exclusion principle

10.12 Counting problem examples

**11. Advanced Counting**

11.1 Generating permutations and combinations

11.2 Binomial coefficients and combinatorial identities

11.3 The pigeonhole principle

11.4 Generating functions

**12. Discrete Probability**

12.1 Probability of an event

12.2 Unions and complements of events

12.3 Conditional probability and independence

12.4 Bayes’ Theorem

12.5 Random variables

12.6 Expectation of a random variable

12.7 Linearity of expectations

12.8 Bernoulli trials and the binomial distribution

**13. Graphs**

13.1 Introduction to graphs

13.2 Graph representations

13.3 Graph isomorphism

13.4 Walks, trails, circuits, paths, and cycles

13.5 Graph connectivity

13.6 Euler circuits and trails

13.7 Hamiltonian cycles and paths

13.8 Planar graphs

13.9 Graph coloring

**14. Trees**

14.1 Introduction to trees

14.2 Tree application examples

14.3 Properties of trees

14.4 Tree traversals

14.5 Spanning trees and graph traversals

14.6 Minimum spanning trees