Statements⌗

  • Well Defined
  • Have Meaning
  • Not opinions
  • Either True or False

Statement Variables⌗

  • Lower case letters

Basic Logic⌗

Logical Operators⌗

Negation⌗

  • \(\neg\)
  • means not

\(\neg p = \begin{cases} \text{true} & \neg p \ \text{is false} \\ \text{false} & \neg p \ \text{is true}\end{cases}\)

Disjunction⌗

  • \(\lor\)
  • means and
  • \(p \lor q = \begin{cases} \text{true} & p, q \ \text{or both are true} \\ \text{false} & \text{both} \ p \ \text{and} \ q \ \text{are false}\end{cases}\)
  • “or” in english usually conveys \(\oplus\)

Conjunction⌗

  • \(\land\)
  • means and
  • \(p \land q = \begin{cases} \text{true} & \text{both} \ p \ \text{and} \ q \ \text{are true} \\ \text{false} & p, q \ \text{or both are false}\end{cases}\)

Implication⌗

  • \(p \rightarrow q\)
  • means if antecedent then consequence
  • Implication does not mean causality
  • \(p \to q \equiv \neg p \lor q\)

\(p \to q = \begin{cases} \text{true} & \text{both} \ p \ \text{and} \ q \ \text{are true, or} \ p \ \text{is false} \\ \text{false} & p \ \text{is true and} \ q \ \text{is false} \end{cases}\)

  • Converse

  • Inverse

    • Inverse of \(p \to q\) is \(\neg p \to \neg q\)
    • Not equivalent to the implication

  • Contrapositive

    • Contrapositive \(p \to q\) is \(\neg q \to \neg p\)
    • Equivalent to the implication
    • Inverse of the Converse

  • Necessary

    • \(q\) is necessary for \(p\)
    • Without something necessary, the statement is false
    • Equivalent to an Implication through the Contrapositive

  • Sufficient

    • \(p\) is sufficient for \(q\)
    • If I have something sufficient, the statement is true with no other information
    • Equivalent to an Implication

Biconditional⌗

  • \(p \leftrightarrow q\)
  • means if and only if antecedent then consequence
  • If the meanings of \(p\) and \(q\) make the implication equivalent to its converse
  • \(p \leftrightarrow q \equiv (p \to q) \land (q \to p)\)
  • \(p \leftrightarrow q = \begin{cases} \text{true} & \text{both} \ p \ \text{and} \ q \ \text{are true, or both} \ p \ \text{and} \ q \ \text{are false} \\ \text{false} & p \ \text{is true and} \ q \ \text{is false, or } \ p \ \text{is false and} \ q \ \text{is true} \end{cases}\)

Order of Operations⌗

  1. Parentheses
  2. Negation
  3. Disjunction and Conjunction

Truth Tables⌗

  • Representation of all possible values of a logical statement
\(p\)\(q\)\(r\)\(p \lor q\)\(\neg r\)\((p \lor q) \land ( \neg r )\)
TTTTFF
TTFTTT
TFTTFF
TFFTTT
FTTTFF
FTFTTT
FFTFFF
FFFFTF

Logical Equivalence⌗

  • \(p\) and \(q\) are logically equivalent (\(p \equiv q\)) when they have the same logical value for all value combinations

Double Negative⌗

  • \(p \equiv \neg (\neg p)\)

De Morgan’s Laws⌗

  • \(\neg (p \lor q) \equiv (\neg p) \land (\neg q)\)
  • \(\neg (p \land q) \equiv (\neg p) \lor (\neg q)\)
\(p\)\(q\)\(\neg p\)\(\neg q\)\(p \lor q\)\(\neg p \land \neg q\)\(\neg(p \lor q)\)
TTFFTFF
TFFTTFF
FTTFTFF
FFTTFTT

Tautology⌗

  • Always true
  • \(\neg p \lor p\)

Contradiction⌗

  • Always false
  • \(\neg p \land p\)

Argument⌗

  • Consists of premises (hypotheses) and a conclusion
  • Arguments can be valid, valid and sound, or neither
  • Can have multiple premises but only one conclusion

Validity⌗

  • Valid when if premises are true, conclusion are also true
  • Conclusion must be guaranteed to be true

Validity

\[q\] \[p \lor q\] \[\therefore p \to q\]

Soundness⌗

  • Sound when valid and the premises are actually true

Rules of Inference⌗

Modus Ponens⌗

\[p \to q\] \[p\] \[\therefore q\]

Modus Tollens⌗

\[p \to q\] \[\neg q\] \[\therefore \neg p\]

Generalization⌗

\[p\] \[\therefore p \lor q\]

Specialization⌗

\[p \land q\] \[\therefore p\]

Conjunction⌗

\[p\] \[q\] \[\therefore p \land q\]

Elimination⌗

\[p \lor q\] \[\neg p\] \[\therefore q\]

Transitivity⌗

\[p \to q\] \[q \to r\] \[\therefore p \to r\]

Cases⌗

\[p \lor q\] \[p \to r\] \[q \to r\] \[\therefore r\]

Contradiction⌗

\[\neg p \to c\] \[\therefore p\]

Solving Arguments⌗

Example Proof

  1. \(p \lor q\)
  2. \(q \to r\)
  3. \((p \land s) \to t\)
  4. \(\neg r\)
  5. \(\neg q \to (u \land s)\)
  6. \(\neg q\) Modus Tollens (2,4)
  7. \(p\) Elimination (1,6)
  8. \(u \land s\) Modus Ponens (5,6)
  9. \(s\) Specialization (8)
  10. \(p \land s\) And (7,9)
  11. \(t\) Modus Ponens (3,10)

Numbers⌗

  • Numbers are abstract
  • Types are the concept, Tokens are the actual things
  • Numbers are symbols, representing the abstract entity

Bases⌗

  • A base represents the meanings of digits in a number and the range of digits allowed

Definition of a Base

\[\text{For some base}\ x\ \text{and for any number}\ n_x\] \[n_x\ \text{is written as a series of digits …}\ d_3 d_2 d_1 d_0\] \[0 \leq d_i \leq x-1\] \[n_{10} = \sum_{i=0}^{} d_ix^i\]

Base Conversion⌗

Subtraction Method⌗

  • Repeatedly subtract lower powers of the base to convert to, trying to maximize digits before moving to the next

Division Method⌗

  • Repeatedly divide by the base and the remainder for the nth division step is the nth digit

Grouping Method⌗

  • To convert from a base \(x\) to a base \(x^n\), collapse \(x\) digits into 1 or vice versa

Properties⌗

Integers⌗

  • A number without a fractional part

Parity⌗

  • Whether a number is even or odd or neither. \(x\) is even if there is some integer \(y\) such that \(x=2y\).
  • Just because a number is not even, does not make it odd, and vice versa.

Prime⌗

  • A number is prime if the only positive divisors of it are 1 and itself
  • A number is composite if there are positive integers whose product is the number
  • \(x \leq 1\) is neither prime nor composite

Divisibility⌗

  • \(x\) divides \(y\) if there is some unique integer \(z\) where \(xz=y\)
  • If \(x\) divides \(y\), we say \(x \mid y\), but if it does not, we say \(x \nmid y\)
  • 0 divides everything but nothing divides 0

Modular Arithmetic⌗

  • \(x\!\!\mod m = r\)
  • \(x = km + r\) where \(r\) is positive and less than \(m\) (math definition)
  • \(x \equiv r \pmod m\) where the only constraint is that \(m\) is not 0
    • \(r\) is \(x\) in the context \(\!\!\pmod m\)
    • \(m \mid (x-r)\)

First Order Logic⌗

  • Defines how much of a set
  • Basic notation: \((\text{Quantifier}\ x \in \text{Set})[\text{Predicate}]\)
    • Multiple quantifiers can be used with more preceding parentheticals
    • Order matters if the quantifiers are different or the variables are different
    • Move a quantifier into the square bracket to make it a local variable (one value shared across all)

Predicate⌗

  • Something that is not well-defined due the use of a variable, but will be well-defined and becomes a statement when a value for that variable is given
  • Written as \(P(x)\)

Sets⌗

  • Integers (\(\mathbb{Z}\)): positive whole numbers, zero, negative whole numbers
  • Naturals (\(\mathbb{N}\)): positive whole numbers greater than 0
  • Reals (\(\mathbb{R}\)): all non-complex numbers
  • Quotients (\(\mathbb{Q}\)): any number that can be written as a fraction of two rationals

Quantifiers⌗

For All⌗

  • \(\forall\)
  • Universal, for every single element

Exists⌗

  • \(\exists\)
  • Existential, for one value in the set
  • This statement is the same as using For All with the negated predicate

Negation⌗

  • For All becomes Exists and vice versa
    • If there are multiple quantifiers, flip all of them
  • Negate the predicate
    • Make sure to include the equals case (negating \(\lt\) becomes \(\geq\))

Implications⌗

Proofs⌗

Necessary Information⌗

  • When proving an existential statement:
    • To prove true, you need one example to be true
    • To prove false, you need all examples to be false
  • When proving an universal statement:
    • To prove true, you need all examples to be true
    • To prove false, you need one example to be false

Direct Proofs⌗

  • Start with what was given and work towards the goal
  • Format
    • List the proof
    • Start with the assumptions
    • Manipulate into the antecedent
    • Define any new variables and their domain
    • Closure is often useful and applies to addition and multiplication on the integers

Indirect Proofs⌗

  • Doesn’t directly prove \(p \Rightarrow q\)
  • Methods
    • Prove the contrapositive
    • Proof by contradiction
      • Assume the assumption is false and show it leads to a contradiction

Indirect Proof by Contrapositive

\[\text{Prove: }\ [\forall x \in \mathbb{Z}]((x^2 \mod 2 = 0) \Rightarrow (x \mod 2 = 0))\] \[[\forall x \in \mathbb{Z}]((x \mod 2 \neq 0) \Rightarrow (x^2 \mod 2 \neq 0))\] \[x = 2k + 1\] \[x^2 = 4k^2 + 4k + 1\] \[x^2 = 2(2k^2 + 2k) + 1\] \[(\exists p \in \mathbb{Z})[p = 2k^2+2k] \ \text{by closure}\] \[x^2 = 2p + 1 \Rightarrow x^2 \ \text{is odd}\]

Sets⌗

A collection of unordered and unique things

Partitions⌗

  • A set of mutually distinct sets that when unioned contain all the elements in a given set.
  • The nil set is not allowed

Power Sets⌗

  • \(\mathcal{P}(A)\) represents the set of all subsets of \(A\).
  • \(\lvert \mathcal{P}(A) \rvert = 2 ^{\lvert A \rvert}\)
  • Two things that will always be in a power set is the \(\emptyset\) and the set itself

Cartesian Product⌗

  • Set of all ordered pairs between two sets
  • \(A \times B = \{(a,b) \vert a \in A \land b \in B\}\)

Relations⌗

  • Some subset of the cartesian product of two sets
  • Defines a relation between the sets by giving the pairs for which the relation is true

Reflexivity⌗

  • A relation \(X \subseteq A \times A\) is reflexive if \((\forall x \in A)[(x,x) \in X]\), that is, every element in the domain must satisfy the relation with itself

Symmetry⌗

  • A relation \(X \subseteq A \times A\) is symmetric if \((\forall x,y \in A)[(x,y) \in X \Rightarrow (y,x) \in X]\)

Transitivity Relation⌗

  • A relation \(X \subseteq A \times A\) is transitive if \((\forall x,y,z \in A)[((x,y) \in X \land (y,z)) \in X \Rightarrow (x,z) \in X]\)

Functions⌗

  • Something that maps elements of one set to element of another

Surjective⌗

  • All elements in the codomain can be mapped to by some element of the domain
  • At least/onto
  • \((\forall y \in Y)(\exists x \in X)[y=f(x)]\) for some function \(f: X \mapsto Y\)

Injective⌗

  • Any element mapped to by the function has one and only one correspding element in the domain
  • At most/one-to-one
  • \((\forall x_1,x_2 \in X)[(f(x_1) = f(x_2)) \Rightarrow x_1 = x_2]\) for some function \(f: X \mapsto Y\)

Bijective⌗

Countability⌗

  • Whether the number of elements in a set is countable
  • A set is countable is there is a one-to-one function from the positive naturals to it
  • A set does not have to finite to be countable, there just needs to be a concrete way to get the “next” element
    • Really, all there needs to be is some fundamental unit

Set Proofs⌗

  • Set Proofs are universal, so disproving just requires a concrete example
  • Its hard to prove emptiness

Induction⌗

Weak Induction⌗

  • Start with a base case
  • Assume that it works for some \(k\)
  • Prove that if it works for \(k\), it works for \(k+1\) possibly by using \(k\) to show \(k+1\) is true

Strong Induction⌗

  • Very similar to Weak Induction, but when \(k+1\) depends on more than just \(k\)
  • Start with a base case or multiple
  • Assume that it works for multiple \(k\)
  • Prove that if it works for those \(k\), then it works for \(k+1\) possible by using those cases to show \(k+1\) is true

Structural Induction⌗

  • Very similar to Strong Induction, but works with non-linear sequences
    • There is more than one direct children from any given element
  • Given some set, and some method for generating children from elements in the set, prove some condition holds.
  • Start with a base case
  • Assume it works for some element \(e\) in the set
  • Prove that if it works for \(e\), then it works for the children of \(e\) which are also in the set

Combinatorics⌗

Theory⌗

Factorials⌗

  • \(n!\) is \(n\cdot(n-1)\cdot(n-2)\dots2\cdot1\)
  • It represents the number of ways to order \(n\) elements

Permutations⌗

  • \(P(n,k)\) is the number of ways to order \(k\) elements from a set of \(n\) elements
  • \(P(n,k) = \frac{n!}{(n-k)!}\)
  • This is different from Factorials because the set of elements to pick from can be bigger than the number of elements we actually want to pick
    • Note that when \(k=n\), we simply have the factorials formula because the denominator becomes 1

Combinations⌗

  • \({n \choose k}\) is the number of way to pick \(k\) elements from a set of \(n\) elements
  • \({n \choose k} = \frac{n!}{k!(n-k)!}\)
  • This is simply the Permutations formula with an extra \(k!\) term to account for the ways we can order \(k\) elements that are all the same (but are all only one combination)

Stars and Bars⌗

  • Say I want to pick \(n\) elements from \(k\) groups. I can list all elements in \(n\) stars. I can use \(k-1\) dividers (bars) to separate the \(n\) stars into \(k\) groups. By choosing which elements are the bars, I can find all possible ways to pick \(n\) elements from \(k\) groups.
  • The formula is \({n+(k-1) \choose (k-1)}\)

Relative Orderings⌗

  • A slight variation on Combinations, is finding all relative orderings of a given permuation
  • If the picked list is circular, then I may want to find all possible relative orderings (where the start of a sequence is doesn’t matter)
  • To do so, simply divide by the total number of elements in the circular list

Probability⌗

Theory⌗

Addition Rule⌗

  • The probability of event A or event B occurring, assuming A and B are disjoint, is \(P(A) + P(B)\)

Multiplication Rule⌗

  • Given two independent events, the probability of both occuring is \(P(A)P(B)\)

Inclusion-Exclusion Principle⌗

  • The Addition Rule requires events be disjoint, but what if they aren’t?
  • Add the two probability then subtract their intersection to prevent double-counting
  • \(P(A) + P(B) - P(A \cap B)\)
  • This can be extended to more events as the sign of the intersection levels flip as more terms are in the intersection

Expected Value⌗

  • The expected value of a sample space is the probability that any given event occurs multiplied the event’s value
  • \(\sum_{i=0}^{n} a_ip_i\) for a sample space with \(n\) elements

Conditional Probability⌗

  • Conditional probability represents the probability that an event occurs given that some other event has already occurred

Bayes Theorem⌗

  • \(P(B \mid A) = \frac{P(A \mid B)P(B)}{P(A)} = \frac{P(A \mid B)P(B)}{P(A \mid B)P(B) + P(A \mid B^c)P(B^c)}\)