• Proof

  • formal proof(형식적 증명)

    • 공리들과 규칙을 통해서 증명을 한다.
    • 비 직관적이나 오류가 적다.

  • deduction (연역) hypothesis to conclusion 전제로부터 결론을 도출

    

  • induction (귀납) 관찰에서 출발 basis: 1 증명 induction step: k 가정 k+1 증명

    

  • contradiction(귀류) false를 가정, 모순 도출

    

Math Terms

• Set(집합)
  • collection of elements
  • 부분집합, 진부분집합
  • 합집합, 교집합, 차집합, 여집합
  • 서로소
  • 멱집합(power set)
  • 곱집합(Cartesian product, 카르테시안곱)
• Function (함수)
  • 공역(codomain)의 한 원소에 정의역(Domain)의 원소의 대응
  • 치역(range)
  • injective (one-to-one, 전사 함수, 일대일 함수) 정의역의 원소 하나에서 공역의 원소 하나에 대응된다.
  • surjective (onto, 단사 함수) 치역=공역
  • bijection (one-to-one correspondence, 전단사 함수, 일대일 대응) 치역=공역이고 하나씩 대응된다.
• Graph
  • g(V,E)
  • V: vertices, E: Edges
  • Walk: sequence of edges v0 to vn 엣지 노드 겹쳐도 됨
  • Trail: for distinct edges 노드 겹쳐도 됨
  • Path: for distinct edges and distinct vertices, v0≠vn 한붓그리기
  • closed: v0==vn
  • cycle: closed path, containing at least one edge
• Tree
  • Connected, Acyclic Graph

Automata theory

• Terms
  • Alphabets ( SIGMA )
    • finite, nonempty set of symbols
    • binary alphabet: SIGMA = { 0, 1 }
    • lower-case letters: SIGMA = {a,b,…,z}
    • ASCII Characters are also Alphabets
  • String

    • finite seq. of symbols, chosen from some alphabet

    • ex. given SIGMA = { 0 , 1 }, 01,0011,0100… = “string”

    • empty string: epsilon

    • length of string: |s|

    • powers of an alphabet: SIGMA^k

      • k자리의 string
      • set of all string: SIGMA^*

        • infinite이다.

          

    • concatenation of string

      • 두개를 이어붙이는 연산이다.
      • 항등원 = epsilon
      • w^0 = epsilon
  • Languages(L)
    • set of strings, chosen from some SIGMA^*, given alphabet SIGMA
    • ex. set of legal english words
    • ex. set of legal c program
    • ex. set of strings, consisting of n개의 0’s , followed by n개의 1’s { epsilon, 01, 0011, 000111 }
    • empty language : phi, language over any alphabet phi ≠ {epsilon}
  • Problems

    • whether a given string is a member of a particular language