Discrete math

Injective (one-to-one)

f(a) = f(b) implies a = b

surjective (onto)

all outputs are accounted for by an input. (calculate output in terms of input)

set minus (A \ B)

A intersection B’. all of A that doesn’t overlap with B

Cartesian Product (AxB)

the set of all pair combinations of A and B

power set (P(A))

the set of all subsets of A (including the empty set)

composition (gof)

gof = g(f(x)). the output set of f(x) must be the input set of g(x)

inversion

an evil twin of a function where both compositions of the pair result in just the input

a|b

a divides b. b = a*k where k is an integer

modus ponens

(p→q)^p => q

simplification

p^q=>p

implication

p→q <=> not(p) or q

conjugation

any two statements can be brought together with an and (^) statement

contrapositive

a→b <=> not(b) → not(a)

c

proper subset. A c B if A is a subset of B but B isn’t a subset of A

= (for sets)

A is a subset of B and B is a subset of A

simple graph

doesn’t have loops

circuit

path starting and ending on same vertex

modus tollens

(p→not(q)) ^ q => not(p)

equivalence relation

REFLEXIVITY (everything relates to itself), TRANSITIVITY (if xRy and yRz then xRz), and SYMMETRY (if xRy then yRx)

partial ordering

REFLEXIVITY, TRANSITIVITY, ANTISYMMETRY (if xRy and yRx then x=y)

Equivalence class [k]

set of all terms relating to k

meet a^b

nearest common element below (like intersection, terms below are already components)

join avb

nearest common element above

complement

only common elements are top and bottom

addition

p => p v q