1_Discrete Maths

1_Discrete Maths

1. Proofs

   • Jargon
     • Predicate
       • truth depends on variables
     • Axiom
       • a basic assumption about a mathematical situation
     • Statement - either true or false
       • Lemma
         • true statement used in proving other true statements
       • Corollary
         • true statement that is a simple deduction from a theorem or proposition
       • Conjecture
         • statement believed to be true but has no proof
       • Theorem
         • very important true statement
       • Proposition
         • interesting true statement
   • Statements
     • Implication
     • Bi-implication (iff)
     • Universal quantification (∀)
     • Conjunction (AND)
     • Existential quantification (∃)
     • Disjunction (OR)
     • Negation (¬)
   • Logical deduction
     • Proof strategies
       • Proof by contradiction
         • A implies B, assume ¬B show mathematical contradiction
       • Contrapositive
         • A implies B goes to ¬B implies ¬A
     • Scratch work
     • Logical equivalences
       • page 136
     • Induction
       • Strong induction
         • Same but all k between l and n hold
       • P(l) holds and ∀n>=l in N. (P(n) => P(n+1)) also holds
         • then ∀m>=l in N. P(m) holds
   • Divisibility and congruence
     • A|B - A divides B, i.e. Ak=B
     • A ≡ B (mod C) - C divides A - B
   • Fermat's last theorem
   • Fermat's little theorem
     • if p is a prime number, a(^p)≡a(mod p)

2. Numbers

   • commutative monoid
     • monoid laws
       • 0+n = n = n+0 , (l+m)+n = l+(m+n)
       • 1.n = n = n.1 , (l.m).n = l.(m.n)
     • commutativity law
       • m+n = n+m
       • m.n = n.m
   • ring
     • an algebraic structure with operations that generalize the arithmetic operations of addition and multiplication
     • semiring
       • without the requirement that each element must have an additive inverse (i.e. -x)
   • division theorem
     • m = quo(m,n)n + rem(m,n)
   • Fundamental theorem of arithmetic
     • product of primes

3. Sets

   • Notation
     • {x ∈ A|P(x)}
       • subset of elements of A satisfying P
     • A ⊆ B
       • A is a subset of B
       • Remove the bottom line for 'proper subset'
         • A is a subset of B AND A is not equal to B
     • #S
       • cardinality (number of elements) of set S
     • ℙ(S)
       • Powerset
         • set of all possible subsets of S (includes empty set)
     • <a, b>
       • Ordered pair
         • {{a}, {a, b}}
     • ∅
       • empty set
     • u
       • universal set (everything)
     • A(to the power of c)
       • complement
   • Hasse Diagrams
   • Cartesian product
     • AxB = {(a,b)|a∈A,b∈B}
   • Big union
     • UA
       • union of the sets contained in A
         • UF = {x∈u|∃A∈F.x∈A}
   • Big intersection
     • ⋂A
       • intersection of the sets contained in A
         • ⋂F = {x∈u|∀A∈F.x∈A}
   • Tagging
     • {l}xA = {(l,a)|a∈A}
   • Disjoint union
     • A(∪ with + in) B = ({1}xA)∪({2}xB)

4. Regular languages

5. Finite automata