Discrete Mathematics Cheat Sheet: Key Concepts & Formulas
Discrete Mathematics Cheat Sheet
Propositional Logic
Consistent – Set of statements that are all satisfiable and all true for the same set of propositional variables
Satisfiable – Evaluates to true for at least one set of variables
Tautology – All true
Logically Correct Argument – Every situation that makes all premises true, conclusion also true
Contradiction – All false
Proof
Induction – Basis: show P(1), assume P(x) (inductive hypothesis), Inductive: show P(x+1) using P(x)
Direct – Arbitrary entity x = 2k i.e. used/manipulated to get into desirable form
Indirect Contradiction – Show that ¬p -> (¬q and q) is true for some propositions p and q
Sets
Recursion – Basis: c in A, Recursive: rule to get new term from x in A
Relation Function – For every a in A there is a b in B + no tuples have the same start element
Countable – Finite or there exists a bijection between set and N
Cartesian Product AxB – All ordered pairs 1st element from 1st set, 2nd from 2nd
Binary Relation – Subset of Cartesian Product
Intersection A∩B – Elements in A and B
Union A∪B – Elements in A or B or both
Complement B(Bar) wrt A (A – B) – Elements in A but not in B
N = 0, 1, 2, 3… Z = …-2, -1, 0, 1, 2… Q = rational a/b both ints
– Set builder notation
Proper Subset – Subset but A != B
Graphs
Reflexive – (a,a) in relation, i.e. every vertex has loop. Irreflexive if no vertices have loops
Symmetric – (a,b)(b,a) in relation i.e. all arrows come in pairs. Antisymmetric if no arrows in pairs
Transitive – Every two-step journey can be done in one step
Equivalence Relation – Reflexive, Symmetric and Transitive
Partial Order – Reflexive, Antisymmetric and Transitive
Hasse Diagram – Remove loops, remove two-trip edges, put all arrows pointing upwards (not horizontal), remove arrow tips
Linear Order – (a,b) or (b,a) in R. Hasse diagram is a line
Warshall’s Algorithm – First elements in tuples go down left, second go across top, compare bars move right one and down one every round. 1 in both compare bars for 0 changes it to 1
Number of Edges Undirected (Handshaking) = sum of the degrees of vertices / 2
Hamiltonian – Hamiltonian path is simple (no same edge twice) and passes through every vertex exactly once. Cycle same as path just comes back around to the same point.
N-Clique – Edge between each pair of distinct vertices, N-Cycle is cycle version
Isomorphic – Has bijection function takes vertices A to vertices B, edges to edges and non-edges to non-edges. Invariant holds for A and B. Invariants – #Edges, #Vertices of each degree, k3 subgraph, simple cycle of length four. G has inv, and G & H are isomorphic, H has inv.
Rooted Tree – Connected simple graph with no simple cycles, root is top, parent of vertex is above, children are directly below, siblings are children of same parent, ancestors are all above to and including root, descendants are all below, internal vertices are all but the final vertices of edges, leaves are all final vertices of edges. Level starts at 0 from root, height is max levels. Balanced if all leaves are level height or height – 1.
M-Ary Tree vs Full M-Ary Tree – No more than m children for internal vertices vs exactly m
Binary Search Tree – Using linearly ordered list, start at root, move left if less than current, move right if greater than current, create new branch when you compare to leaf.
Postorder Traversal – Root then leftmost subtrees going down through each edge and moving right
Inorder Traversal – Leftmost subtree in order, then visit root, then continue subtrees inorder from left to right
Preorder Traversal – Leftmost subtree from bottom, continue traversing bottom leaves, then work your way up parents and keep moving right when you’re on the same level as another leaf (move down and then up to the top of subtree, never up down up down)
Functions
Function – All domain mapped, each can’t be mapped to 2 different places in co-domain, identity function itself, inverse takes B back to A
Floor/Ceiling – Largest integer less than, Smallest integer greater than
One-to-one – Distinct A to distinct B
Onto – All B mapped to
Bijection = onto and one-to-one
Pigeonhole Principle – n objects placed into k boxes means at least one box has ceiling n/k objects
Probability
Choosing k objects from n objects:
Changing order matters, Repeating allowed – 
Changing order matters, Repeating not allowed – 
Changing order doesn’t matter, Repeating allowed – 
Changing order doesn’t matter, Repeating not allowed – 
Conditional Probability of E given F – 
Bayes’ Theorem – 
Independence Test – 
Automata
Subset Construction – New States = All subsets of states in NFA, Initial State = NFA initial state + all states reachable by e-jumps, Favourable states = Subsets with at least one of NFA favourable states, Arrow to State = All reachable NFA states by that arrow + any e-jumps for each state in the subset, Empty Set maps to itself
Regex to NFA – a is arrow between two labelled a, ab is two consecutive arrows, a* is four states, arrows between and from 1 to 4 and 4 to 2, a on middle arrow and e others, a|b is two states with two routes, one a and one b
Language – Set of words that FA accepts. Regular if it can be represented by a regex
Alphabet – Set of strings (characters)
NFA – Non-deterministic, choice involved, state doesn’t determine next. Accepts if there exists a computation that ends up in a favourable state. Can get stuck without having read all symbols and that means rejected. Also computation can use any number of jumps necessary
Regex Recursion – Basis: Empty set, empty word and symbols from S are regex. Recursive: R and Z regex, R|Z regex, RZ regex, R* regex