Discrete Mathematics Cheat Sheet Side A

Propositional Logic
Proposition: A declarative statement that is either true or false but not both.
Negation: ¬p (not p) has opposite truth value to p.
Conjunction: p q is true only when both p and q are true.
Disjunction: p q (inclusive) is false only when both p and q are false.
Exclusive OR: p q is true when exactly one of p or q is true.
Implication: p q is false only when p is true and q is false.
Equivalences: ¬(p q) ¬p ¬q; ¬(p q) ¬p ¬q; p q ¬p q; p q (p q) (q p).

Predicate Logic & Quantifiers

Predicate: P(x) becomes a proposition when x from the domain is substituted.
Universal quantifier: x P(x) is true if P(x) holds for all x in the domain.
Existential quantifier: x P(x) is true if P(x) holds for some x in the domain.
Negations: ¬ x P(x) x ¬P(x); ¬ x P(x) x ¬P(x).

Sets & Operations

Set: Unordered collection of distinct objects.
Membership: x A if x is in A; x A if not.
Roster notation: {1, 3, 5}, order irrelevant.
Set-builder: { x U | P(x) } describes elements with property P.
Subset: A B if every element of A is also in B.
Empty set : has no elements; A for any A.
Disjoint: Two sets have no elements in common.
Partition: Collection of nonempty, pairwise disjoint subsets whose union is the original set.
Union: A B = { x | x A or x B }.
Intersection: A B = { x | x A and x B }.
Difference: A B = { x | x A and x B }.
Complement: A = U A = { x | x A }.
Symmetric difference: A B = (A B) (A B).
De Morgan's: ¬(A B) = ¬A ¬B; ¬(A B) = ¬A ¬B.

Relations
Relation: Subset of A×B; ordered pairs relating elements.
Domain/Range: In (a,b) R, a is domain element and b is range element.
One-to-one: No element of B is second coordinate of two distinct pairs.
Onto: Every b B appears as second coordinate in some pair.
Inverse relation: R ¹ = { (b,a) | (a,b) R }.
Complement relation: R contains pairs not in R.
Reflexive: a, (a,a) R.
Irreflexive: a, (a,a) R.
Symmetric: (a,b) R (b,a) R.
Antisymmetric: (a,b) R and (b,a) R a = b.
Transitive: (a,b),(b,c) R (a,c) R.
Intransitive: (a,b),(b,c) R (a,c) R.
 Discrete Mathematics Cheat Sheet Side B
Number Theory Circuit: Closed trail with no repeated edges; vertices may repeat.
Divisibility: a|b means b = a·c for some integer c; a b if b/a not integer.
Quotient Remainder: For integers a and positive d, a = dq + r with 0 r < d.
Prime: Integer 2 divisible only by 1 and itself; composites otherwise.
Fundamental theorem: Every integer >1 is prime or a product of primes.
Prime-power factorization: n>1 uniquely as p ^a p ^a p_k^a_k.
GCD: Largest integer dividing both a and b; gcd(a,b)=1 a and b are relatively prime.
Euclidean algorithm: Repeated division; gcd is last nonzero remainder.
LCM: Smallest positive integer divisible by both; a·b = gcd(a,b)·lcm(a,b).
Euler's totient (n): Count of integers < n relatively prime to n; (p)=p 1; (pq)=(p 1)(q 1).
Congruence: a b (mod m) if m divides (a b).
Congruence properties: a±c b±d and ac bd (mod m) if a b, c d (mod m).

Algorithms
Algorithm: Finite, unambiguous sequence of steps transforming inputs to outputs.
Requirements: Finiteness, definiteness, correctness, effectiveness, well-ordered, generality.
Brute force: Try all possible solutions blindly.
Divide and conquer: Recursively split problem into subproblems; solve and combine.
Backtracking: Build candidate solutions and backtrack when a candidate cannot lead to valid solution.
Dynamic programming: Store optimal solutions to overlapping subproblems and combine.
Probabilistic: Use random choices; small error probability.
Greedy: Make locally optimal choice at each step; may not always be optimal.
Space complexity: Maximum memory used by an algorithm.
Time complexity: Number of key operations as a function of input size.
Big-O: Upper bound on growth; f(n) = O(g(n)) if |f(n)| c|g(n)| for n > k.
Big-Omega: Lower bound; f(n) = (g(n)) if |f(n)| c|g(n)| for n > k.
Big-Theta: Tight bound; f(n) = (g(n)) if it is both O(g(n)) and (g(n)).
Big-O properties: Highest-degree term dominates in sums; multiply exponents in products.

Graph Theory
Graph: G=(V,E) with finite vertex set V and finite edge set E.
Order |V| and size |E|: number of vertices and edges.
Adjacency: u and v adjacent if {u,v} E.
Loops & parallel edges: Loop joins a vertex to itself; multiple edges between same pair.
Simple graph: No loops or parallel edges.
Multigraph: May have multiple edges; Pseudograph: may include loops and multiple edges.
Directed graph: Edges are ordered pairs; Mixed graph: contains both directed and undirected edges.
Degree: Number of incident edges; loops count twice.
Pendant/Isolated: deg=1 pendant (leaf); deg=0 isolated.
Handshaking theorem: Sum of degrees equals twice number of edges; even number of odd-degree vertices.
In-degree/out-degree: For digraphs, count incoming/outgoing edges.
Subgraph: (V ,E ) where V V, E E.
Complement graph: Edge exists where original graph does not.
Graph union & intersection: Combine or intersect vertex and edge sets.
Complete graph K_n: Edge between every pair of vertices; n(n 1)/2 edges.
Cycle graph C_n: n vertices in a cycle; each has degree 2.
Star graph S_{n+1}: n leaves connected to a central vertex.
Wheel graph W_{n+1}: Cycle graph plus central vertex connected to all cycle vertices.
Linear graph P_n: n vertices in a path; endpoints have degree 1.
Grid graph: m×n grid with vertical and horizontal edges.
Hypercube Q_n: 2^n vertices representing bit strings; edges connect strings differing in one bit.
Regular graph: Every vertex has same degree.
Bipartite graph: Vertex set partitioned into two sets; edges only between sets; complete bipartite has |V1|·|V2| edges.
Adjacency matrix: n×n matrix where entry is number of edges between vertices.
Incidence matrix: n×m matrix; entry 1 if edge incident with vertex.
Walk: Sequence of vertices and edges; may repeat vertices and edges.
Trail: Walk with no repeated edges; vertices may repeat.
Path: Trail with no repeated vertices.
Cycle: Path that starts and ends on same vertex; no repetition of other vertices.