1_1_Discrete Maths

1_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. Sets

   • Disjoint union
     • A(∪ with + in) B = ({1}xA)∪({2}xB)
   • Tagging
     • {l}xA = {(l,a)|a∈A}
   • Big intersection
     • ⋂A
       • intersection of the sets contained in A
         • ⋂F = {x∈u|∀A∈F.x∈A}