segomin/algo12.9_1-6.md

## algo12.9_1-6.md

      
    Raw
  

              algo12.9_1-6.md
            
          
    1. True / False


(a) 0 le x**2
(b) x < 2x
(c) x2 -x-12=(x-3)×(x+4)
(d) x2 +x-20=(x-4)×(x+5)
(e) (-x)**3 = -(x3)**3

False :


(b) {x | ∈ x < 0}
(e) {x | ∈ x < 0}

2. 집합의 원소를 나열


(a) {0,1,4} ∪ {4,1,3}

{0,1,4,3}


(b) {0,1,4} ∩ {4,1,3}

{1,4}


(c) ({2,4,6} ∪ ∅ ∪ {9}) ∩ {9,4}

({2,4,6,9}) ∩ {9,4}
∅


(d) {m|m ∈ {0,1,4} ∪ {4,1,3} ∧ even(m)}

{m|m ∈ {0,1,4,3} ∧ even(m)}
{0,4}


(e) ∅ ∩ {2,4}

∅


(f) {0,1,4} + {4,1,3}

{{l,0}, {l,1}, {l,4}, {r,4}, {r,1}, {r,3}}


(g) {0, 1} × {0, 1}

{{0,0}, {0,1}, {1,0}, {1,1}}


(h) {0,1,2} + ({1} × {3,5})

{0,1,2} + ({{1,3}, {1,5}})
{{l,{0,1,2}}, {r,{{1,3}, {1,5}}}


(i) 2**{0}

(A의 모든 부분집합의 집 합을 2A로 표기하자는 제안을 할 수 있고 p.255)
???


3. 집합에 속한 원소의 개수. 집합의 속한 원소를 모두 나열하지 않고 문제를 풀어 보아라.


(a) {m|0≤m<1000} ==> 1000개
(b) {m|0≤m<1000}+{m|2000 ≤ m < 2500}

1000 + 500
1500


(c) {0,1} × {m|0≤m<1000}

2 * 1000
2000


(d) 2**∅

1


(e) 2**{m | 0≤m<3}

2**3 == 8


(f) {∅,{a,b}}

2


(g) {a, b} → {red,green,blue}

(입력 값의 자료형은 정의역 (domain)이라고 하며, 출력 값의 자료형은 공역(codomain)이라고 한다. 정의역이 A, 공역이 B인 함수의 자료형은 A→B로 나타낸다. 예를 들어, Z→Bool은 함수 even의 자료형이다. p.253)
9 -> 2 x 3 => 6


(h) {red,green,blue} → {a, b}

8 -> 3 x 2 => 6


4. 이항 연산자의 좌영원과 우영원은 유일함을 보여라. 대칭적인 이진 연산자의 단위원은 유일함을 보여라.


...

5. 함수 double과 square를 다음과 같이 정의하자.


double(x) = 2 × x
square(x) = x**2
아래의 참 거짓을 밝혀라

(a) double은 덧셈에 대하여 분배 가능하다.

double(a + b) ==? double(a) + double(b)
double(a + b) == 2 x (a + b) == 2a + 2b
double(a) + double(b) == 2a + 2b
가능


(b) double은 곱셈에 대하여 분배 가능하다.

double(a x b) ==? double(a) x double(b)
double(a x b) == 2 x (a x b) == 2ab
double(a) x double(b) == 2a x 2b == 4ab
불가능


(c) double은 지수에 대하여 분배 가능하다.

double(a ** b) ==?  double(a) ** b
double(a ** b) == 2 x (a ** b) == 2(a**b)
double(a) ** b == (2 x a) ** b == (2a)**b
불가능


(d) double은 최소에 대하여 분배 가능하다.

double(min(a,b)) ==? min(double(a), double(b))
double(min(a,b)) == 2 x (min(a,b))
min(double(a), double(b)) == min(2a, 2b)
가능


(e) square는 덧셈에 대하여 분배 가능하다.

square(a + b) ==? square(a) + square(b)
square(a + b) == (a + b) ** 2 == a2 * ab * b2
square(a) + square(b) == a2 + b2
불가능


(f) square는 곱셈에 대하여 분배 가능하다.

square(a x b) ==? square(a) x square(b)
square(a x b) == (a x b) ** 2 == (ab) ** 2 == a ** 2 x b ** 2
square(a) x square(b) == a ** 2 x b ** 2
가능


(g) square는 지수에 대하여 분배 가능하다.

square(a ** b) ==? square(a) ** b
square(a ** b) == (a ** b) ** 2 == a ** 2b
square(a) ** b == (a ** 2) ** b == a ** 2b
가능해 보이지만, (b 가 음수인 경우 동일하지 않을 수 있다고 함)


(h) square는 최소에 대하여 분배 가능하다.

square(min(a,b)) ==? min(square(a),square(b)
square(min(a,b)) == min(a,b) ** 2
min(square(a),square(b) == min(a2, b2)
a 가 음수인 경우 불가능


## algo12.9_7-10.md

      
    Raw
  

              algo12.9_7-10.md
            
          
    7. 군 $$(A,1,×, ^{-1})$$에서 $$1^{-1} =1$$임을 보여라.


군의 정의


$$(A, 1, ×)$$는 모노이드다.
^{-1} 은 A에서 정의된 단항 연산자이다.
$$[x \times (x^{-1}) = 1 = (x^{-1}) \times x]$$


따라서 x 에 1 을 넣으면

$$1 \times (1^{-1}) = 1$$ 이므로, $$1^{-1} = 1$$


8. 문자열 ABBA에서 정의된 ‘뒤따르는’ 관계는 대칭적이다. 이는 ABBA가 회문 (palindrome)이라는 사실로부터 증명할 수 있다. (회문이란, 앞으로 읽으나 뒤 로 읽으나 똑같은 단어를 뜻한다.) A와 B로 이루어진 문자열 중에서 회문은 아니지만 글자에 대한 ‘뒤따르는’ 관계는 대칭적인 경우를 구성하라.


대칭성


$$x \rightarrow y$$ 가 성립하면 $$y \rightarrow x$$ 도 성립해야 함


ABAB : $$A \rightarrow B$$, $$B \rightarrow A$$ 이 존재하므로 대칭적임

9. 문자열 ABBA에서 ‘뒤따르는’ 관계는 반사적인가? 전이적인가?


반사성


$$[xRx]$$ 를 만족하는 관계


전이성


$$x \rightarrow y, y \rightarrow z$$ 이면 $$x \rightarrow z$$ 가 성립하는 관계


$$A \rightarrow B, B \rightarrow B, B \rightarrow A$$ 에서 $$A \rightarrow A$$ 관계가 안되므로 반사적이지 않음

$$A \rightarrow B, B \rightarrow B $$ 에서 $$A \rightarrow B$$ 관계가 성립하고

$$B \rightarrow B, B \rightarrow A $$ 에서 $$B \rightarrow A$$ 관계가 성립하므로 전이적임

10. 비어 있는 단어란 문자열 중에서 길이가 0인 것을 의미한다. (비어 있는 단어와 공집합을 구분해서 사용하라.) 비어 있는 단어에서 정의된 ‘뒤따르는’ 관계는 대칭적인가? 전이적인가?


비어있는 단어가 자기 자신을 뒤따른다고 할 때

$$\varnothing \rightarrow \varnothing$$ 와 $$\varnothing \rightarrow \varnothing$$ 가 성립하기 때문에 대칭적이고, 전이적임

10. ‘뒤따르는’ 관계가 아래 각각의 조건을 만족하도록, A와 B로 이루어진 문자열을 구성하라.


(a) 반사적이고 전이적이지만 대칭 관계는 아니다.
(b) 전이적이지만 반사 관계나 대칭 관계는 아니다.
(c) 동치 관계이다.
각각의 조건에 대하여, 문자열을 최대한 짧게 구성해 보아라.
‘뒤따르는’ 관계가 반사적이고 대칭적이지만 전이 관계는 아니도록, A와 B로만 이루어진 문자열을 구성하는 것은 불가능하다. 왜인가?
AABB


$$A \rightarrow A$$, $$B \rightarrow B$$ 관계와

$$A \rightarrow A, A \rightarrow B$$ 의 $$A \rightarrow B$$ 관계

$$A \rightarrow B, B \rightarrow B$$ 의 $$A \rightarrow B$$ 관계가 성립하므로 반사적이고, 전이적임


AB

???


A


$$A \rightarrow A$$ 관계로 반사적이며, 대칭적이고, 전이적이므로 동치관계임
반사적이면서 대칭적이면 모든 요소 $$x$$에 대해 $$x \rightarrow x$$ 가 성립하고, $$x \rightarrow y$$ 이면, $$y \rightarrow x$$ 도 성립함
모든 $$x$$와 $$y$$가 서로를 뒤따르게 되어 전이성도 성립하게 됨