Discrete Maths

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
         • Theorems to learn
           • intermediate value theroem
             • for all y between f(a) and f(b) there exists v in between a and b such that f(v) = y
           • Division theorem
             • for every natural number m and pos. nat. num n, there exists a unique pair of integers q and r such that q>=0, 0<=r<n, and m=q.n+r
           • Euclid's theorem
             • For positive integers m and n, and prime p, if p|(mn) then p|m or p|n
           • Fundamental theorem of arithmetic
             • For every positive integer n there is a unique finite ordered sequence of primes such that n=Π(p1,...,pl)
       • Proposition
         • interesting true statement
   • Statements
     • Implication
     • Bi-implication (iff)
     • Universal quantification (∀)
     • Conjunction (AND)
     • Existential quantification (∃)
       • ∃! means there exists a unique
     • 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
         • finite cardinality when A≅[n] for natural number n
     • ℙ(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)
   • Relations
     • Binary relation R:A⇸B
       • relation between source and target
       • R⊆AxB
       • Relational extensionality
         • R=S:A⇸B iff (∀a∈A.∀b∈B. aRb <=> aSb)
     • composition
       • composition of R:A⇸B and S:B⇸C is the relation S∘R:A⇸C
         • a(S∘R)c <=> ∃b∈B.aRb∧bSc
       • R to the ∘n is the relation R applied n times
     • Directed graph is just a set A and a relation R from A to A
     • Preorder ⊑
       • relation on one set satisfying reflexivity and transitivity
         • reflexivity: ∀x∈P.x⊑x
         • transitivity: ∀x,y,z∈P.(x⊑y ∧ y⊑z) => x⊑z
       • partial order / poset
         • preorder that satisfies antisymmetry: ∀x,y∈P.(x⊑y ∧ y⊑x) => x=y
     • partial function
       • f:A⇀B
         • for each element a of A there is at most one element b of B such that b is a value of f at a
       • function
         • bijection
           • there exists a unique function as the inverse of the function
         • f:A→B
           • partial function but all elements in the domain are sources
           • e.g. x |→ x + 3 for defined function
     • using two lines for the shaft of the arrow means the set of all relations of that type
     • Isomorphism (≅)
       • A≅B when there is a bijection between them
     • Equivalence relation (E)
       • reflexive: xEx for all x in A
       • symmetric: xEy=>yEx
       • transitive: xEy AND yEz => xEz
       • partitions are where all the elements are joined both ways be E
     • characteristic function
       • ℙ(A)≅(A=>[2])
         • [2] = {0,1}
     • surjection
       • f:A↠B
         • for all b, there exists an a so f(a)=b
     • injection
       • f:A↣B
         • f(a1)=f(a2) => a1=a2
     • enumerability
       • there exists a surjection ℕ↠A
         • a countable set is empty or enumerable
     • axiom of choice
       • every surjection has a section of values which can lead to the b

4. Formal Languages and Automata

   • Finite automata
     • Any NFA with epsilon transitions can be represented by a DFA
   • Formal Languages
     • Alphabets ∑
       • set of symbols
       • a string is an ordered tuple of elements of ∑
         • ∑* denotes all strings over ∑ of any finite length
     • given an alphabet ∑, we call any subset of ∑* a formal language over the alphabet ∑
   • Inductive Definitions
     • axioms and rules with the fraction thing
     • can be thought of as a tree with leaves as axioms and the root as the string
     • transitive closure
       • for a relation R, R+ is the smallest binary relation on X that contains R and is transitive
       • reflexive transitive closure
         • R* is reflexive too
   • Abstract Syntax Trees
     • finite rooted trees. vertexes with n children are labelled by operators expecting n arguments
       • Union, Concat, Star, Null, Empty, Syma
   • Regular Languages
     • a language that can be represented by a DFA
   • The Pumping Lemma
   • Kleene's theorem
     • A language is regular iff it is equal to L(M), the set of strings accepted by some deterministic finite automaton M
     • For any regular expression r, the set L(r) of strings matching r is a regular language
       • regex to automata, can do diagrammaticically by cases
     • Conversely, every regular language is the form L(r) for some regular expression r
       • simple OR of all accepting states
   • matching

Images and files in the map