//이 자료는 Discrete mathmatics and its application 7th edition에서 나오는 예제를 간추린 것입니다. 저는 코딩에 관심 있는 학생이며, 타인의 지적재산을 단지 학습을 위해 사용할 뿐 개인의 금리적 이윤을 위한 상업적인 용도로 쓰지 않습니다. 만약 저작권 관련 문제가 될 시 즉시 문서를 삭제하겠습니다.//
많은 경우에 한 집합에서 각 원소들을 두번째 집합의 특정 원소들에 할당합니다. (두번째 집합은 첫번째 집합과 같을 수도 있습니다.) 예로, 이산수학 수업을 듣는 학생들이 학점 집합 {A, B, C, D, F}에 할당된다고 합시다. 그리고 A 학점은 애덤에게, C는 쵸우, B는 좋은친구, A인 로드리게즈, 스티븐은 F를 주기로 합시다. 이를 표현한 그림은 아래와 같습니다.
이렇게 이루어진 할당은 함수의 한 예입니다. 함수의 개념은 수학과 컴퓨터 과학에서 정말 중요합니다. 예로, 이산수학 함수들은 수열과 문자열과 같은 이산구조의 정의에 활용됩니다. 함수들은 또한 컴퓨터가 주어진 크기의 문제를 풀기 위해 얼마만큼의 시간을 소요하는지 표현하는데 사용되기도 합니다. 많은 컴퓨터 프로그램과 서브루틴 프로그램들은 함수의 값을 연산하기 위해 설계되었습니다. 재귀함수는 말 그대로 함수이고, 컴퓨터 과학 전체에서 사용됩니다. 5 챕터에서 살펴볼 것 입니다. 이 섹션에서는 이산구조에서 필요한 함수를 포함한 기초개념들에 대해서 살펴볼것입니다.
정의 1
A와 B를 공집합이 아닌 집합이라고 하자. A에서 B로의 함수는 정확히 A의 한 원소를 B의 각 원소에 할당하는 것입니다. 이를 f(a) = b라 표현합니다. 여기서 b는 B의 원소이며 함수 f와 A의 원소 a에 의해 할당되었습니다. 만약 f가 A에서 B로의 함수이면 다음과 같이 씁니다. f : A -> B
함수는 때론 매핑mapping 또는 변형transformation이라고 불립니다. 함수는 다양한 방법으로 정의될 수 있습니다. 위의 그림처럼 정의할 수 있지만 주로 수식을 통해 표현합니다. f(x) = x +1는 수식을 이용해 함수를 정의한 예입니다. 때론 컴퓨터 프로그램을 이용해 함수를 표현할 수 있습니다.
함수 f : A→B 는 때론 A에서 B로의 관계라는 용어로 정의될 수 있습니다. A에서 B로의 관계는 단지 데카르트 곱 A x B의 부분집합입니다. A x B는 순서쌍 (a, b)로 이루어져있습니다. 여기서 (a, b) 모든 a∈A에 대해 A에서 B로의 함수를 정의한 것입니다. 이 함수는 할당하는 f(a) = b로 정의되었으며 여기서 (a,b)는 고유한 순서쌍입니다. 이런 순서쌍은 관계내에 있으며, a를 첫번째 원소로 가집니다.
정의 2
만약 f가 A에서 B로의 함수이면, A는 f의 정의역domain이라 표현하고 B는 공역codomain이라고 합니다. b는 a의 상image 라고하며 a는 b의 원상preimage라고 합니다. 함수 f의 치역range 또는 상image은 A의 모든 원소에 대한 상image의 집합입니다. 또한, 만약 f가 A에서 B로의 함수이면, f는 A를 B로 매핑한다고 합니다. //we say that f maps A to B
아래 그림은 A에서 B로의 함수 f를 표현합니다.
함수를 정의할 때는 정의역domain과 그 공역codomain 그리고 정의역의 원소를 공역 원소에 대해 매핑mapping 하는 것을 명시해야합니다. 두 함수는 같은 정의역과, 공역, 그리고 정의역과 공역으로의 각 원소 맵핑이 같을 때 동일한 함수입니다. 한 함수의 정의역이나 공역을 약간이라도 변경하게 된다면, 우리는 다른 함수를 갖게됩니다. 또 만약 원소간의 맵핑을 바꾼다면, 이전과는 다른 함수를 얻게 됩니다.
예제 2
R을 정렬된 쌍 (Abdul, 22), (Brenda, 24), (Carla, 21), (Desire, 22), (Eddie, 24), (Felicia, 22)으로 이루어진 관계relation이라고 합시다. 각 쌍들은 학부생과 나이로 이루어져 있습니다. 이 관계를 바탕으로 함수를 구체적으로 설명해보세요.
*** R에 의해 기술된 함수 f는, f(Abdul) = 22, f(Brenda) = 24, f(Carla) = 21..(생략) 입니다. 여기서 f(x)는 x의 나이이며, 여기서 x 학생입니다. 정의역에서, 집합 {Abdul, Brenda, ... , Felicia}를 얻을 수 있습니다. 또한 공역은 모든 가능한 학생들의 나이로 명시할 수 있습니다. 모든 학생들이 100살 보다 어릴것으로 예상하므로, 공역을 100 이하의 양의 정수들의 집합으로 정의 할 수 있습니다. (물론 10 이상 90 이하의 양의 정수 집합을 공역으로 할 수 있습니다. 이렇게 한다면 함수를 바꿔야합니다. 공역을 넓게 잡는다면 나중에 학생들의 이름과 나이를 추가하여 함수를 확장하는데 좋습니다.) 함수의 치역range은 학생들의 다른 나이들의 집합이므로 {21, 22, 24} 입니다.
예제 4
함수 f : Z -> Z는 한 정수에게 이 정수의 제곱을 할당한다고 합시다. 그렇다면, f(x) = x^2 이며 여기서 f의 정의역은 모든 정수들의 집합입니다. 그리고 f의 공역은 모든 정수의 집합입니다. f의 치역range는 완전 제곱수인 모든 정수들의 집합입니다. {0, 1, 4, 9, ...}
예제 5
프로그래밍 언어에서 함수의 정의역과 공역은 자주 명시됩니다. 예로 Java 구문 int floor(float real){...}과 C++ 함수 구문 int function(float x) {...} 는 함수의 정의역이 실수이고 (소수점을 가진 숫자) 그리고 공역은 정수들의 집합입니다.
함수가 만약 실수들의 집합을 공역으로 가진다면 real-valued라고 부릅니다. 그리고 정수들의 집합을 공역으로 가지게 된다면 integer-valued라고 불립니다. 두 실수값의 함수 또는 두 정수값의 함수는 서로 더해질 수 있고, 곱해질 수도 있습니다.
정의 3
f1과 f2를 A에서 R(실수)로의 함수라고 하자. 그렇다면 f1+f2과 f1f2 는 또한 모든 x ∈A 에대해 A에서 B로의 함수입니다.
(f1 + f2)(x) = f1(x) + f2(x)
(f1f2)(x) = f1(x) + f2(x)
함수 f1+f2와 f1f2의 x에서의 값은 f1과 f2의 x에서의 값에 의해 결정됩니다.
예제 6
f1과 f2를 R에서 R로의 함수라고 하자. f1(x) = x^2이고 f2(x) = x-x^2 입니다. 함수 f1+f2와 f1f2은 무엇입니까?
*** (f1+f2)(x) = f1(x) + f2(x) = x^2 + (x-x^2) = x 그리고 (f1f2)(x) = x^2(x-x^2) = x^3 - x^4 입니다.
만약 A에서 B로의 함수가 있을때, A의 부분집합의 상image 또한 정의될 수 있습니다.
정의 4
f를 A에서 B로의 함수라 하자. 그리고 A의 부분집합을 S라고 하자. 함수 f아래에서 S의 상image은 S의 원소들의 상들로 이루어진 B의 부분집합입니다. S의 상image을 f(S)로 표현가능합니다.
f(S) = {t|∃s∈S(t=f(s))} 또한 다음과 같이 짧게 이 집합을 표현할 수 있습니다. {f(s)|s∈S}
여기서 f(S)는 함수 f에서의 집합 S의 상을 뜻하는데 잠재적으로 모호합니다. 여기서, f(S)는 집합을 뜻하며, 집합 S에 대한 함수 f의 값을 뜻하는 것이 아닙니다.
예제 7
집합 A = {a, b, c, d, e}와 집합 B = {1, 2, 3, 4}라 합시다. f(a) = 2, f(b) = 1, f(c) = 4, f(d)=1, f(e)=1 입니다. 부분집합 S = {b,c,d}의 상image는 집합 f(S) = {1, 4} 입니다.
일대일 함수와 전사 함수 One-to-One and Onto Functions
어떤 함수들은 정의역 내에 다른 원소들을 절대 같은 값에 할당하지 않습니다. 이 함수들을 일대일 함수one-to-one functions 또는 단사함수 injective function 이라고 합니다.
정의 5
함수 f가 일대일이라고 합시다. 그렇다면 f(a) = f(b)는 A의 정의역 내 모든 원소 a와 b에 대해 a=b 임을 뜻합니다. 함수가 일대일이라면 단사 함수라고 합니다.
만약 함수 f가 일대일이면 a≠b일 때 f(a)≠f(b)를 뜻합니다.
함수 f가 일대일인 것을 정량자를 통해 표현할 수 있습니다. ∀a∀b(f(a)=f(b)→a=b) 또는 ∀a∀b(a≠b → f(a) ≠ f(b)) 로 표현할 수 있습니다.
예제 8
{a, b, c, d} 에서 {1, 2, 3, 4, 5} 함수 f가 일대일 함수인지 판단하세요. f(a) = 4, f(b) = 5, f(c) = 1, f(d) = 3 입니다.
*** 함수 f는 일대일입니다. f는 정의역에 존재하는 네 원소를 각 다른값으로 가집니다. 다음과 같은 그림으로 표현할 수 있습니다.
예제 9
함수 f(x) = x^2 일대일인지 판단하시오. 정수에서 정수로의 함수 입니다.
*** 함수 f(x) = x^2는 일대일 함수가 아닙니다. 예로 f(1) = f(-1) =1 이지만 1≠-1 입니다.
함수 f(x) = x^2는 정의역이 Z+일때만 일대일입니다. 기술적으로, 함수의 정의역을 제한하면, 제한한 정의역에서의 원소에 대해 원래 함수와 같은 값을 가지는 새로운 함수를 갖게됩니다. 제한된 함수는 제한된 정의역 바깥의 원래 정의역에 대해선 정의되지 않습니다.
예제 10
다음 함수가 일대일 함수인지 확인하세요. f(x)=x+1는 실수 집합에서 실수 집합으로의 함수입니다.
*** 함수 f(x) = x+1 는 일대일 함수입니다. 이것을 증명하려면, x≠y 일 때 x+1≠y+1 임을 보면 됩니다.
예제 11
피고용자들로 이루어진 그룹에서 각 노동자들은 각 노동자가 수행 가능한 작업들의 집합의 한 작업으로 할당되었다고 가정합시다. 이 경우에, 각 노동자에게 한 작업을 할당하는 함수 f는 일대일입니다. 이는 x와 y가 각 다른 작업자이면, f(x) ≠ f(y) 임을 확인하면됩니다. 두 작업자 x와 y는 반드시 다른 작업들을 맡아야 하기 때문입니다.
이제 함수가 일대일인지 보장하기 위해 어떤 조건들을 제시해볼것입니다.
정의 6
정의역과 공역이 실수의 부분집합인 함수 f는, f의 정의역 x와 y가 있고 x<y일 때, f(x) ≤ f(y) 이면 증가함수라고 불리며 f(x) < f(y) 이면 강한 증가함수라고 합니다. 유사하게, 만약 f(x) ≥ f(y) 이면 함수 f는 감소함수입니다. f(x) > f(y)이면 강한 감조함수입니다.
∀x∀y(x < y → f(x) ≤ f(y)) 이면 함수 f는 증가함수입니다. ∀x∀y(x < y → f(x) < f(y)) 이면 함수 f는 강한 증가함수입니다. ∀x∀y(x < y → f(x) ≥ f(y)) 이면 감소함수입니다. ∀x∀y(x < y → f(x) > f(y)) 이면 강한 감소함수입니다.
이 정의들로부터, 강한 증가함수 강한 감소함수는 반드시 일대일 함수여야 합니다. 그러나, 강하지 않은 증가함수와 감소함수는 일대일 함수가 아닙니다.
어떤 함수들은, 치역range와 공역codomain이 같습니다. 즉, 공역의 모든 멤버들이 정의역의 어떤 원소의 상image인 경우입니다. 이런 특성의 함수들은 전사함수onto functions 입니다.
정의 7
A에서 B로의 함수 f는 전사onto라고 불립니다. 만약 모든 원소 b ∈ B 에 대해 f(a) = b를 만족하는 원소 a ∈ A 가 존재한다면 전사함수입니다.
∀y∃x(f(x) = y)라면 함수 f는 전사함수입니다. 여기서 x의 정의역은 함수의 정의역이고 y의 정의역은 함수의 공역입니다.
이제 전사함수와 전사이지 않은 함수를 살펴볼 것입니다.
예제 12
{a, b, c, d}에서 {1, 2, 3}로의 함수를 f라고 합시다. f(a) = 3, f(b) = 2, f(c) = 1, f(d) = 3입니다. f는 전사함수입니까?
*** 공역의 모든 세 원소가 정의역의 원소들의 상image입니다. 그러므로 f는 전사함수입니다. 아래의 그림을 확인합시다. 공역이 { 1, 2, 3, 4} 라면 f는 전사함수가 아닙니다.
예제 13
함수 f(x)=x^2가 전사함수입니까? 함수f(x)는 정수들의 집합에서 정수들의 집합으로의 함수입니다.
*** 함수 f는 전사함수가 아닙니다. 예로 x^2 = -1 을 만족하는 정수 x가 존재하지 않습니다.
예제 14
함수 f(x) = x+1는 전사함수입니까? 정수들의 집합에서 정수들의 집합으로의 함수입니다.
*** 함수는 전사함수입니다. 모든 정수 y에 대하여 f(x) = y 인 정수 x가 존재하기 때문입니다. 예로 f(x) = y는 x+1=y, x= y-1 입니다.
정의 8
함수 f가 일대일 함수이고 전사함수이면 전단사 함수라고합니다.
예제 16
함수 f 가 {a, b, c, d}에서 {1, 2, 3, 4}로의 함수라고 합시다. f(a) = 4, f(b) = 2, f(c) = 1, f(d) = 3입니다. 함수 f는 전단사함수입니까?
*** 함수 f는 전단사 함수입니다. 정의역의 어떠한 원소도 같은 함수 값을 가지지 않으므로 일대일 대응입니다. 그리고 모든 공역codomain 원소 네개가 정의역의 원소들의 상image 이므로 전사함수입니다. 따라서 함수 f는 전단사함수입니다.
예제 17
A를 집합이라고 합시다. A로의 항등 함수identity function는 ιA : A →A 입니다. 여기서 모든 x∈A에 대해 ιA(x) = x 입니다. 다른 말로는, 항등 함수identity function ιA는 자신으로의 원소를 할당하는 함수입니다. ιA는 일대일대응이며 전사함수이며 따라서 전단사함수입니다. (ι은 그리스어 iota입니다.)
참고로, 함수가 일대일인지 전사인지 확인하기위해 보여야할 것을 요약해보았습니다.
함수 f가 단사함수인지 보이려면: f(x)=f(y)인지 보여야합니다. 여기서 임의의 x, y는 A의 원소이며, x와 y는 같지않습니다. 만약 f(x)=f(y)라면 x=y입니다.
함수 f가 단수함수가 아님을 보이려면 : 집합 A의 특정 원소 x, y를 찾아야합니다. 원소 x, y는 서로 같지않으면서 f(x)= f(y)를 만족해야합니다.
함수 f가 전사함수인지 보이려면: B의 임의의 원소 y에 대해 f(x) =y를 만족하는 집합 A의 원소 x를 찾아야합니다.
함수 f가 전사함수가 아님을 보이려면: 집합 A의 모든 원소 x에 대해 f(x)≠y를 만족하는 집합 B의 특정 원소 y를 찾으면됩니다.
역함수와 합성함수 Inverse Functions and Compositions of Functions
A에서 B로의 전단사 함수 f를 고려해봅시다. f가 전사함수이므로, B의 모든 원소들이 A의 어떤 원소들의 상image 입니다. 또, f가 단사함수이므로, B의 모든원소가 A의 고유한 원소들의 상image 입니다. 따라서, B에서 A로의 새로운 함수를 정의할 수 있습니다. 이 함수는 함수 f의 역과 일치합니다. 이는 다음의 정의를 이끌어냅니다.
정의 9
집합 A에서 집합 B로의 전단사 함수를 f라 합시다. f의 역함수는 B에 속한 원소 b에게 A의 고유한 우너소 a에게 할당하는겁니다. 이는 f(a) = b를 만족해야합니다. f의 역함수는 f^-1로 표기됩니다. 따라서 f(a) = b이면 f^-1(b) = a입니다.
함수 f가 전단사 함수가 아니라면, f의 역함수를 정의할 수 없습니다. f가 전단사 함수가 아니라면, 전사가 아니거나 단사가 아닙니다. f가 일대일 대응이 아닐때, 공역에 속한 어떤 원소 b는 하나보다 더 많은 정의역의 원소의 상image 입니다. 만약 f가 전사가 아니면, 공역에 속한 어떤 원소 b에 대해 f(a)=b를 만족하는 정의역 내에 위치한 원소 a가 존재하지 않습니다. 따라서, 만약 함수 f가 전단사가 아니라면, 공역에 위치한 각 원소 b에 대해 f(a)=b를 만족할 수 있는 고유한 a 원소를 할당할 수 없습니다. (왜냐하면 어떤 b에 대해서 하나보다 많은 a 또는 어떠한 a도 할당될 수 없기 때문입니다.)
전단사 함수는 역가능하다고 할 수 있습니다. 왜냐하면 이 함수의 역함수를 정의할 수 있기 때문입니다. 만약 전단사가 아니라면 역가능하지 않습니다. 왜냐하면 그런 함수의 역은 존재하지 않기 때문입니다.
예제 18
집합 {a, b, c}에서 {1, 2, 3}으로의 함수를 f라 하자. f(a)=2, f(b)=3, f(c)=1라 합시다. f는 역가능합니까? 역가능하다면 무엇입니까?
*** 함수 f는 역가능합니다. 왜냐하면 전단사 함수이기 때문입니다. 역함수 f-1은 f의 역에 대응합니다. f-1(1)=c, f-1(2)=a, f-1(3)=b 입니다.
예제 19
ff(x) = x+1를 만족하는 f: Z->Z라 합시다. 만약 f가 역가능하다면, 그 역은 무엇입니까?
*** 함수 f는 역을 가집니다. 왜냐하면 전단사 함수이기 때문입니다.
예제 20
R에서 R로의 함수를 f라 합시다. f(x)=x^2일 때, f는 역가능합니까?
*** 함수 f는 일대일 대응이아닙니다. 예로 f(-2) = f(2) = 4입니다. 따라서, f는 역가능하지 않습니다.
정의 10
g를 집합 A에서 B로의 함수라고 하고 f를 집합 B에서 집합 C로의 함수라고하자. 함수 f와 g의 합성은, 모든 원소 a∈A에 대해 f⋅g로 표기됩니다. (f⋅g)(a) = f(g(a))
예제 22
집합 {a, b, c}에서 자신으로의 함수를 g라 합시다. 함수 g는 g(a) = b, g(b)=c, g(c)=a를 만족합니다. 집합 {a, b, c}에서 집합 {1, 2, 3}으로의 함수를 f로 합시다. 함수 f는 f(a)=3, f(b)=2, f(c)=1라 합시다. 합성함수 f⋅g와 g⋅f는 무엇입니까?
*** 합성함수 f⋅g는 f(g(a))=f(b)=2, f(g(b))=f(c)=1, f(g(c)=f(a)=3 입니다. 합성함수 g⋅f는 정의될 수 없습니다. 왜냐하면 f의 치역range는 g의 정의역의 부분집합이 아니기 때문입니다.
예제 23
정수들의 집합에서 정수들의 집합으로의 함수를 f와 g라 하자. f(x) = 2x+3이고 g(x) = 3x+2이다. 합성함수 f⋅g는 무엇입니까? 합성함수 g⋅f는 무엇입니까?
*** f⋅g(x)=f(g(x)) = f(3x+2)=6x+7 이고 g⋅f(x)=g(f(x))=g(2x+3)=6x+11 입니다.
위 예제에서 살펴볼 수 있듯이 합성함수의 교환법칙은 성립하지 않습니다.
만약 함수 f가 집합 A에서 집합 B로의 전단사 함수라고 합시다. 그러면 f와 f 역함수의 합성함수로 항등함수를 얻을 수 있습니다. f-1⋅f(a) = f-1(f(a)) = f-1(b) = a 이고 f⋅f-1(b)=f(f-1(b))=f(a)=b 입니다. 따라서 f-1⋅f= ιA와 f⋅f-1 = ιB 입니다. 여기서 ιA와 ιB는 각각 집합 A와 B로의 항등 함수identity functions 입니다. 즉, (f-1)-1= f입니다.
함수의 그래프
정의 11
f를 집합 A에서 B로의 함수라고하자. 함수 f의 그래프는 다음 순서쌍들의 집합이다. {(a,b)|a∈A 그리고 f(a) = b}
정의로부터, A에서 B로의 함수의 그래프는 함수 f와 그 첫번째 원소 a에 의해 결정되는 집합 B의 원소 b로 이루어진 어떤 정렬된 쌍을 포함하는 A x B의 부분집합입니다. 또한, 집합 A에서 B로의 함수 f의 그래프는 함수 f에 의해 정의되는 A에서 B로의 관계와 같다는 것을 참조하세요.
예제 24
정수들 집합에서 정수들 집합으로의 함수 f(n)=2n+1의 그래프를 표현하세요.
*** f의 그래프는 정렬된 쌍들의 집합입니다. 형식은 (n, 2n+1) 이며 여기서 n은 정수입니다.
몇 몇 중요한 함수들
다음으로, 이산수학에서 몇 몇 중요한 함수들을 소개해보려고 합니다. 내림함수Floor funcionts와 올림함수ceiling functions입니다. x를 실수라고 합시다. 내림함수는 x와 같거나 x보다 작은 가장 근접한 정수로 내림됩니다. 이 함수들은 객체들을 셀 때 사용됩니다. 이 함수는 특정 단계들의 숫자들을 분석하는데 중요한 역할을 합니다. 이 단계들은 특정 크기의 문제를 푸는 절차들로 사용됩니다.
정의 12
내림 함수 floor function은 실수 x를 x와 동등하거나 가장 근접한 정수로 내림하는 것입니다. x에서의 내림함수 값은 다음과 같이 표기됩니다. ⌊x⌋. 올림함수ceiling function은 실수 x를 x와 동등하거나 가장 근접한 정수로 올림하는 것입니다. x에서의 올림함수 값은 다음과 같이 표기됩니다. ⌈x⌉.
예제 27
컴퓨터 디스크에 저장된 데이터거나 데이터 네트워크로 전송되는 데이터는 주로 바이트들의 문자열로 표현됩니다. 1 byte는 8 bits로 구성됩니다. 100bit 자료를 전송하기위해 얼마의 bytes가 필요합니까?
*** ⌈100/8⌉ = ⌈12.5⌉ = 13 바이트가 필요합니다.
