Discrete Mathematics Formulas and Proof Techniques
Problem: what is the power set P(S) of S=(a,b,c) Solution: ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. |p ∨ (p ∧ q) ≡ p|, |p ∧ (p ∨ q) ≡ p|, |p → q ≡ ¬p ∨ q|, |p → q ≡ ¬q → ¬p|, |p ∨ q ≡ ¬p → q|, |p ∧ q ≡ ¬(p → ¬q)|, |¬(p → q) ≡ p ∧ ¬q|, |(p → q) ∧ (p → r) ≡ p → (q ∧ r)|, |(p → r) ∧ (q → r) ≡ (p ∨ q) → r|, |(p → q) ∨ (p → r) ≡ p → (q ∨ r)|, |(p → r) ∨ (q → r) ≡ (p ∧ q) → r|, |p ↔ q ≡ (p → q) ∧ (q → p)|, |p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q|, |¬(p ↔ q) ≡ p ↔ ¬q|. Original: If p then q. Converse: if q then p. Inverse: If not P, then not Q. Contra-positive: If not Q, then not P. A=(a,b) B=(1,2,3) |A x B|=6. Direct proof:
prove exactly what is being asked. Proof by contraposition: prove the contrapositive is true. Proof by contradiction: assume the opposite is true. Proof by induction: do base case then assume that for s(k) that s(k+1) also works. Example: S(n)= n(n+1)/2, S(k)= k(k+1)/2, S(k+1)=k(k+1)/2 + (k+1). Do algebra to show that is is equal to (k+1)((k+1)+1)/2. Ways to choose if title matters and no repeats: P(x,n) x=number of people, n=positions, this is x!/(x-n)!. Ways to choose if position does not matter: C(x,n) which is x!/n!(x-n)!. Given length of string and options for each character if repeats area allowed then it is number of options^length. If repeats is not allowed it is number of options!. If you cant prove a base case you can prove anything using induction. Permutations containing a specific combination, Example how many ways to arrange ABCDEFGH contain DEF. Group DEF together plus 5 other letter so answer is 6!. Example problem: In a department with 34 people, how many ways are there to pick a committee consisting of 4 people, if one of the people picked must be the chair. Chair has a title so it must be treated differently so we get 34 * C(33,3) which is 33!/3!(33-3)!. To find a coefficient n sigma k=0 (n/k) a^(n-k)b^k so your value would be n!/k!(n-k)! * the value infront of x^n-k * the value infront of y^k. How many ways to pick when choosing different types: n= types r=amount sol.: (n+r-1/r)=(n+r-1)!/r!(n-r)!. How many ways to solve the equation x1+x2+…Xk=n (non-negative): (n+k-1/k-1)= (n+k-1)!/(k-1)!(n-k)!. How many ways to solve the equation x1+x2+…Xk=n (positive integers): (n-1/k-1)=(n-1)!/(k-1)!(n-k)!. How many ways can you rearrange letters in FLIBBERTIGIBBET: n= number of total letters, bottom values in number of individual letters so, 15!/2!*2!*3!*4!. Certain letter appear next to each other but not in a particular order n!*k! N=number of options k= length of string that appears next to each other. A graph is undirected if it has no arrows on the edges. A graph with only 1 edge from each vertice to each other is single loop.
If and edge starts and ends at the same verticy then it is a loop. Simple graph: undirected, no multiple edges, no loops. Multigraph: undirected, multiple edges, no loops. Pseudograph: undirected, mutliple edges, yes loops. Simple directed: directed, no multi edges, no loops. Directed multigraph: directed, multiple edges, loops. Mixed graph: directed and undirected, multi edges, loops. Degree is determined by how many edges touch a verticy. Bipartite means that you can color a verticy red or blue and no blue or reds will touch. Graph matrix: for simple they must be touching for a 1 for directed the 1 goes in the horizontal column not vertical if touching. A graph is connected if you can go from any vertex to any other vertex. A Euler circuit is a path that touches every edge exactly once.