Introduction to Theory of Computation 1장_2 용어,개념정리

Introduction to Theory of Computation 1장_2 용어, 개념 정리

<집합>
 : Sets, a collection of well-defined object
 원소란? element, member
 (ex) { n | 1 ≤ n ≤ 3 인 정수 } = {1, 2, 3}

<집합 기호>
 - N : 자연수들의 집합, N = { 1,2,3,4, … } / set of natural numbers.
 - Z : 정수들의 집합, Z = { … -1, 0, 1, … } / set of integers.
 - Q : 유리수들의 집합, Q = { m/n | n과 m은 Z, n≠0 } / set of rational numbers.
 - e : 무리수들의 집합, set of irrational numbers.
 - R : 실수들의 집합, set of real number.

<부분 집합>
 : subset, A⊆B
            (해석) - A is a subset of B
                    - if and only if
                    - Every element of A is an element of B

(+) A⊆A : A는 A의 부분집합
     ∮⊆A : 공집합은 A의 부분집합

<Power set>
 : 부분집합을 만드는 방법의 수
  P(A) = { B | B⊆A }
- 어느 부분집합들의 집합
- The power set of A is the set of all subsets of A.
   
   => 원소 개수가 n개인 집합의 Poser Set은?  2ⁿ

<Operation>
 : 집합의 연산자
 ① Union : 합집합, A∪B = { x | x∈A or x∈B }
 ② Intersection : 교집합, A∩B = { x | x∈A and x∈B }
 ③ Difference : 차집합, A\B = A-B = { x | x∈A and x∉B }
 ④ Cartesian Product : 집합의 곱 개념, AxB = { (x,y) | x∈A and x∈B }
       (ex) A={1,2,3}, B={a,b}
            A x B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}
            A³ = {(1,1,1), (1,1,2) … (3,3,3)}
 ⑤ Coplement : 여집합,  A∁ = { x | x∉A }

<Function>
 : 함수, 두 집합 사이의 관계        => B, 공역
 F = A->B  /  Function from A to B
                                                  =>  A, 정의역(domain) : 하나의 정의역에 의해 이루어지는 쌍은 오직 한쌍이다.

<함수의 종류>
 => 정의역과 공역 사이의 사이즈 비교가 가능해짐!!
① one to one : 단사 함수, |A|≤|B|
② onto function : 전사 함수, |A|≥|B|
③ bijection : 전단사 함수, |A|=|B|

<String and Language>
- alphabet : set of symbols(기호들의 집합)
- string over alphabet : a finite seguence of symbols in ∑
 
 ※어떠한 문장을 만들기 위한 String을 다루기 이전에 우리들은 symbols(기호들)이 필요로 한다.
  우리들은 이것을 Σ 로 칭할 것이며, Σ = { ... } 부분집합의 조합으로 유한한 문자열이 만들어진다.

- length of string w : |w| ,  the number of symbols in w. (w에 쓰인 기호들의 개수)
   **empty string : ε  , |ε|=0이다.

∴언어란? A language is a set of strings.

<Proof>
 statement : 명제,문장 / theorem : 정리
 ① 직접 증명, Direct proofs
 ② 존재 증명, Comstructive proofs
 ③ 간접 증명, Nonconstructive proofs
 ④ 모순에 의한 증명, Proofs by contradiction
 ⑤ 비둘기 집 원리, The pigeon hole principle