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 Mathematical definitions
2.2 Introduction to proofs
2.3 Best practices and common errors in proofs
2.4 Writing direct proofs
2.5 Proof by contrapositive
2.6 Proof by contradiction
2.7 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
A hands-on, interactive introduction to this foundational computer science and engineering subject
Discrete Mathematics zyBook teaches students how to translate descriptions of everyday scenarios into precise mathematical statements that can be used for formal analysis. It provides a solid pathway to more advanced study of computer science and engineering.
- Includes new block proof tool that gives instructors the ability to teach proof-writing skills at scale
- Interactive animations help students visualize and comprehend difficult discrete math concepts
- Students get a feel for how the mathematical tools they’re learning will be applied later in their studies
- Includes 750 learning questions, animations, and interactive tools, including hundreds of end-of-section exercises
- Adopters have access to a test bank with over 700 questions
The block ordering tool gives instructors the ability to assess and teach proof-writing skills in large introductory discrete math courses. Learn more here.
Author Dr. Sandy Irani explains how students learn with the new block proof tool:
What is a zyBook?
Discrete Mathematics is a web-native, interactive zyBook that helps students visualize concepts to learn faster and more effectively than with a traditional textbook. (Check out our research.)
Since 2012, over 1,700 academic institutions have adopted digital zyBooks to transform their STEM education.
zyBooks benefit both students and instructors:
- Instructor benefits
- Customize your course by reorganizing existing content, or adding your own content
- Continuous publication model updates your course with the latest content and technologies
- Robust reporting gives you insight into students’ progress, reading and participation
- Save time with auto-graded labs and challenge activities that seamlessly integrate with your LMS gradebook
- Build quizzes and exams with hundreds of included test questions
- Student benefits
- Learning questions and other content serve as an interactive form of reading
- Instant feedback on labs and homework
- Concepts come to life through extensive animations embedded into the interactive content
- Review learning content before exams with different questions and challenge activities
- Save chapters as PDFs to reference the material at any time
Author
Dr. Sandy Irani
Professor of Information and Computer Science, University of California, Irvine
