Discrete MathematicsCheat Sheet

Propositional Logic

Propositions, logical connectives (AND, OR, NOT, XOR), truth tables, and compound statements.

Logical Equivalences

De Morgan's laws, distributive laws, absorption, and other equivalence rules for simplifying logical expressions.

Predicate Logic

Predicates, quantifiers (∀ and ∃), nested quantifiers, and translating English to logical statements.

Proof Techniques

Direct proof, proof by contraposition, proof by contradiction, and proof by cases.

Mathematical Induction

Weak induction, strong induction, structural induction, and proving summation formulas.

Proof Strategies

Existence proofs, uniqueness proofs, constructive vs non-constructive proofs.

Boolean Algebra

Boolean functions, logic gates, canonical forms (DNF and CNF), and minimization techniques.

Set Theory

7 topics

Set Basics

Set notation, membership, subsets, power sets, Cartesian products, and set-builder notation.

Set Operations

Union, intersection, complement, difference, symmetric difference, and Venn diagrams.

Set Identities

Commutative, associative, distributive laws, De Morgan's laws for sets, and proving set equality.

Relations

Binary relations, properties (reflexive, symmetric, transitive, antisymmetric), and relation composition.

Equivalence Relations

Equivalence classes, partitions, quotient sets, and modular arithmetic as an equivalence relation.

Partial Orders

Posets, Hasse diagrams, lattices, total orders, well-ordering, and topological sorting.

Functions

Injective, surjective, bijective functions, composition, inverse functions, and function growth.

Combinatorics

7 topics

Counting Basics

Sum rule, product rule, bijection principle, and counting with constraints.

Permutations

Permutations with and without repetition, circular permutations, and permutations with restrictions.

Combinations

Combinations, binomial coefficients, Pascal's triangle, and combinations with repetition.

Binomial Theorem

Binomial expansion, binomial identities, multinomial theorem, and combinatorial proofs.

Pigeonhole Principle

Basic and generalized pigeonhole principles with applications to existence proofs.

Inclusion-Exclusion

Principle of inclusion-exclusion for counting, derangements, and Euler's totient function.

Recurrence Relations

Linear recurrences, characteristic equations, solving homogeneous and non-homogeneous recurrences.

Graph Theory

8 topics

Graph Basics

Vertices, edges, directed and undirected graphs, adjacency matrices, and graph terminology.

Graph Types

Complete graphs, bipartite graphs, regular graphs, trees, and special graph families.

Graph Isomorphism

Isomorphic graphs, graph invariants, and determining when two graphs are isomorphic.

Paths and Circuits

Euler paths/circuits, Hamilton paths/circuits, and existence conditions.

Trees

Tree properties, rooted trees, binary trees, spanning trees, and counting labeled trees.

Graph Coloring

Vertex coloring, chromatic number, edge coloring, and the four-color theorem.

Planar Graphs

Planar graphs, Euler's formula, Kuratowski's theorem, and graph planarity testing.

Matching and Covering

Matchings in bipartite graphs, Hall's theorem, vertex and edge covers.

Number Theory

6 topics

Divisibility

Division algorithm, divisibility rules, GCD, LCM, and the Euclidean algorithm.

Prime Numbers

Prime factorization, Fundamental Theorem of Arithmetic, Sieve of Eratosthenes, and primality testing.

Modular Arithmetic

Congruence, modular operations, linear congruences, and the Chinese Remainder Theorem.

Fermat's Little Theorem

Fermat's theorem, Euler's theorem, and applications to cryptography.

RSA Cryptography

Public-key cryptography, RSA algorithm, key generation, encryption, and decryption.

Number Representations

Binary, octal, hexadecimal systems, base conversion, and computer number representation.

Automata & Languages

5 topics

Finite Automata

DFA, NFA, state diagrams, transition tables, and language acceptance.

Regular Expressions

Regular expression syntax, equivalence with finite automata, and pattern matching.

NFA to DFA Conversion

Subset construction algorithm, epsilon-closure, and automata minimization.

Regular Languages

Closure properties, pumping lemma, and proving languages are not regular.