8장. 함수

이산수학

8장. 함수

1

이산수학

출처

본 강좌 자료는 이산수학 (2학년 / 3학점/ 3시간 / 이론) 수업에서 사용한 교재 [이산수학 (수학으로 이해하는 디지털 논리), 한빛

아카데미 출판사] 의 내용 등을 출처로 작성하였음을 알리는 바입니다.

이산수학

학습 목표

■ 함수의 개념 이해

■ 합성함수 이해

3

이산수학

학습 내용

■ 함수의 개념

■ 함수의 연산

■ 함수의 성질

■ 합성함수

■ 함수의 종류

이산수학

함수(function)

■ 함수는 입력을 받고 처리한 뒤 출력을 반환하는 과정

■ 집합 𝑨에서 𝑩로 가는 관계

■ 𝒇 ∶ 𝑨 → 𝑩

■ 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵 에 대하여 𝑎, 𝑏 ∈ 𝑓 ⇒ 𝑓 𝑎 = 𝑏

■ 정의역(Domain, 𝑑𝑜𝑚(𝑓) ) : 𝑨

■ 공변역(Codomain, c𝑑𝑜𝑚(𝑓) ) : 𝑩

■ 함수값 : 𝑓 𝑎 ∈ 𝐵 , for 𝑎 ∈ 𝐴

■ 치역(Range, 𝑟𝑎𝑛(𝑓)) ∶ *𝑓(𝑎)|∀𝑎 ∈ 𝐴+

5

이산수학

예제

함수 sum 정의 함수 sum 호출

이산수학

함수와 관계의 차이

■ 집합 𝐴 에서 집합 𝐵 로의 관계

◻ 집합 𝐵의 원소와 대응하지 않는 집합 𝐴가 존재할 수 있다.

◻ 집합 𝐴 의 원소 하나가 하나 이상의 집합 𝐵의 원소와 대응 가능

■ 집합 𝐴 에서 집합 𝐵 로의 함수

◻ 집합 𝐴 의 모든 원소는 반드시 집합 𝐵의 원소와 대응

◻ 집합 𝐴 의 원소 각각은 집합 𝐵의 원소 하나와 대응

7

이산수학

예제

■ 집합 𝐴 = 𝑎, 𝑏, 𝑐 , 𝐵 = *1, 2, 3, 4+라 하자 (1) 𝑓₁ = * 𝑎, 2 , 𝑏, 1 , 𝑐, 4 + ⇒ 𝑓₁ 함수

(2) 𝑓₂ = * 𝑎, 2 , 𝑎, 3 , 𝑏, 1 , 𝑐, 1 , 𝑐, 3 , 𝑐, 4 + ⇒ 𝑓₂는 함수가 아님 ∵ 𝑓₂(𝑎)=2, 𝑓₂(𝑎)=3

이산수학

예제

■ 다음 관계에 대한 화살표 도표가 함수 인지 아닌지를 구별하라.

9

함수 함수 함수가 아님

이산수학

예제

■ 𝑓 ∶ 𝑅 → 𝑅 일 때, 𝑓 𝑥 = 9 − 𝑥² 이라 하자.

1 𝑓 가 함수인지 아닌지 판별하여라.

(2) 함수가 아닌 경우에는 함수가 될 수 있는 정의역을 구하라.

(풀이)

(1) Note 𝑎 ≥ 0 ⇒ 𝑎 가 성립

9 − 𝑥² ≥ 0 인 경우 𝑓 𝑥 = 9 − 𝑥² 이 성립한다.

∴ 𝑓 ∶ 𝑅 → 𝑅, 𝑓 𝑥 = 9 − 𝑥² 는 함수가 아니다.

(2) 정의역 𝑑𝑜𝑚 𝑓 = *𝑥| − 3 ≤ 𝑥 ≤ 3, 𝑥 ∈ 𝑅+

이산수학

함수의 연산 (합 과 곱)

■ 두 함수 𝒇 ∶ 𝑿 → 𝑹 와 𝒈 ∶ 𝒀 → 𝑹에 대하여

■ 𝒇 + 𝒈 ∶ 𝑿 → 𝑹 𝒔. 𝒕 𝒇 + 𝒈 𝒙 = 𝒇 𝒙 + 𝒈 𝒙

■ 𝒇𝒈 ∶ 𝑿 → 𝑹 𝒔. 𝒕 𝒇𝒈 𝒙 = 𝒇 𝒙 ∙ 𝒈 𝒙

■ 𝑑𝑜𝑚 𝒇 + 𝒈 = 𝑑𝑜𝑚 𝒇𝒈 = 𝑑𝑜𝑚(𝒇) ∩ 𝑑𝑜𝑚(𝒈)

11

이산수학

예제

■ 두 함수의 곱과 덧셈 연산과 정의역을 구하라 .

𝑑𝑜𝑚 𝑓 = 𝑥 −15 < 𝑥 < ∞, 𝑥 ∈ 𝑅 , 𝑓 𝑥 = 𝑥 − 5 𝑑𝑜𝑚 𝑔 = 𝑥 −30 ≤ 𝑥 ≤ 30, 𝑥 ∈ 𝑅 , 𝑔 𝑥 = |𝑥|

(풀이)

(1) 𝑓 + 𝑔 = 𝑥 − 5 + |𝑥|

(2) 𝑓𝑔 = 𝑥 − 5 ∙ |𝑥|

(3)

𝑑𝑜𝑚 𝑓 + 𝑔 = 𝑑𝑜𝑚 𝑓𝑔 = 𝑑𝑜𝑚 𝑓 ∩ 𝑑𝑜𝑚 𝑔 = 𝑥 −15 < 𝑥 ≤ 30, 𝑥 ∈ 𝑅

이산수학

함수의 성질

■ 함수 𝒇 ∶ 𝑿 → 𝒀에 대하여

(1) 단사함수 (Injective function, one-to-one function)

◻ for any 𝑥₁ ≠ 𝑥₂ ∈ 𝑋 ⇒ 𝑓(𝑥₁) ≠ 𝑓(𝑥₂)

◻ 𝑑𝑜𝑚 𝑓 ≤ 𝑐𝑜𝑑𝑜𝑚 𝑓 , 𝑟𝑎𝑛 𝑓 ≤ 𝑐𝑜𝑑𝑜𝑚 𝑓 (2) 전사함수 (Subjective function, Onto function)

◻ for any 𝑦 ∈ 𝑌, ∃𝑥 ∈ 𝑋 𝑠. 𝑡 𝑓 𝑥 = 𝑦

◻ 𝑑𝑜𝑚 𝑓 ≥ 𝑐𝑜𝑑𝑜𝑚 𝑓 , |𝑟𝑎𝑛 𝑓 | = |𝑐𝑜𝑑𝑜𝑚 𝑓 |

(3) 전단사함수(Bijective function, One-to-one correspondence)

◻ 단사함수이면서 전단사함수

◻ 𝑑𝑜𝑚 𝑓 = 𝑐𝑜𝑑𝑜𝑚 𝑓 , 𝑟𝑎𝑛 𝑓 = 𝑐𝑜𝑑𝑜𝑚 𝑓

13

이산수학

예제

■ 𝑓: 𝑍 → 𝑍 일 때, 𝑓 𝑥 = 𝑥 + 1가 전단사함수임을 보여라.

(풀이)

(1) Let 𝑥₁≠𝑥₂ , 𝑤𝑕𝑒𝑟𝑒 𝑥₁, 𝑥₂ ∈ 𝑍 .

𝑓 𝑥₁ = 𝑥₁+1, 𝑓 𝑥₂ = 𝑥₂ + 1 ⇒ 𝑓 𝑥₁ ≠𝑓 𝑥₂ ∴ injective

(2) For any y s. t y = 𝑥 + 1 ⇒ ∃𝑥 ∈ 𝑑𝑜𝑚(𝑓) 𝑠. 𝑡 𝑓 𝑥 = y = 𝑥 + 1 ∴ subjective

(3) ∴ 𝑓 : one-to-one correspondence.

이산수학

합성함수(Composite function)

■ 두 함수 𝑓 ∶ 𝐴 → 𝐵 와 𝑔 ∶ 𝐵 → 𝐶의 합성함수 𝑔 ∘ 𝑓: 𝐴 → 𝐶

■ 𝑔 ∘ 𝑓 𝑥 = 𝑔 𝑓 𝑥 , ∀ 𝑥 ∈ 𝐴

15

이산수학

합성함수의 연산

■ 두 함수의 합성함수는 일반적으로 교환법칙이 성립하지 않는다.

◻ 교환법칙이 성립하는 경우도 있고 안 되는 경우도 있다라는 의미

◻ 𝑓 ∘ 𝑔 𝑥) ≠ (𝑔 ∘ 𝑓 (𝑥)

■ 세 개의 함수의 합성함수의 결합법칙은 성립한다.

◻ ( 𝑓 ∘ 𝑔 ∘ 𝑕)(𝑥) = (𝑓 ∘ (𝑔 ∘ 𝑕))(𝑥)

이산수학

예제

■ 두 함수 𝑓 ∶ 𝑅 → 𝑅 𝑠. 𝑡 𝑓 𝑥 = 𝑥³ + 2𝑥, 𝑔 ∶ 𝑅 → 𝑅 𝑠. 𝑡 𝑔 𝑥 = 𝑥 − 5 . 다음 합성함수의 연산을 구하시오.

(1) 𝑔 ∘ 𝑓 (2) 𝑓 ∘ 𝑔 (3) 𝑓 ∘ 𝑓 (4) 𝑔 ∘ 𝑔 (풀이)

(1) 𝑔 ∘ 𝑓 = 𝑔 𝑓 𝑥 = 𝑔 𝑥³ + 2𝑥 = 𝑥³ + 2𝑥 − 5

(2) 𝑓 ∘ 𝑔 = 𝑓 𝑔 𝑥 = 𝑓 𝑥 − 5 = (𝑥 − 5)³ + 2 𝑥 − 5

= 𝑥³ − 15𝑥² + 77𝑥 − 135

(3) 𝑓 ∘ 𝑓 = 𝑓 𝑓 𝑥 = 𝑓 𝑥³ + 2𝑥 = (𝑥³ + 2𝑥)³+2(𝑥³ + 2𝑥) = 𝑥⁹ + 6𝑥⁷ + 12𝑥⁵ + 10𝑥³ + 4𝑥

(4) 𝑔 ∘ 𝑔 = 𝑔 𝑔 𝑥 = 𝑔 𝑥 − 5 = 𝑥 − 5 − 5 = 𝑥 − 10

17

이산수학

합성함수의 성질

■ 함수 𝑓: A → 𝐵, 𝑔: 𝐵 → 𝐶 에 대해 합성함수 𝑔 ∘ 𝑓 는 다음 성질을 만족한다.

(1) 𝑓, 𝑔 단사함수 ⇒ 𝑔 ∘ 𝑓 단사함수 (2) 𝑓 , 𝑔 전사함수 ⇒ 𝑔 ∘ 𝑓 전사함수 (3) 𝑓, 𝑔 전단사함수 ⇒ 𝑔 ∘ 𝑓 전단사함수 (4) 𝑔 ∘ 𝑓 단사함수 ⇒ 𝑓 단사함수

(5) 𝑔 ∘ 𝑓 전사함수 ⇒ 𝑔 전사함수

(6) 𝑔 ∘ 𝑓 전단사함수 ⇒ 𝑓 는 단사함수, 𝑔 는 전사함수

이산수학

함수의 종류 : 항등함수

■ 항등함수 (Identity function)

■ 𝐼_𝐴: 𝐴 → 𝐴 s.t 𝑓 𝑎 = 𝑎, ∀𝑎 ∈ 𝐴.

■ 항등함수와 일반 함수의 합성

◻함수 𝑓: 𝐴 → 𝐵, 𝐼_𝐴, 𝐼_𝐵 에 대해 𝑓 ∘ 𝐼_𝐴=𝐼_𝐵 ∘ 𝑓 = 𝑓

19

이산수학

예제

■ 집합 𝐴 = 1,2,3 에서 𝐵 = 𝑎, 𝑏, 𝑐, 𝑑 로 가는 함수 𝑓 =

1, 𝑐 , 2, 𝑎 , (3, 𝑑) 에 대해 𝑓 ∘ 𝐼_𝐴=𝐼_𝐵 ∘ 𝑓 = 𝑓 이 성립함을 보이시오.

(풀이)

𝐼_𝐴 = * 1,1 , 2,2 , 3,3 +, 𝐼_𝐵 = * 𝑎, 𝑎 , 𝑏, 𝑏 , 𝑐, 𝑐 , (𝑑, 𝑑)+

(1) (𝑓 ∘ 𝐼_𝐴) 1 = 𝑓 𝐼_𝐴 1 = 𝑓 1 = 𝑐, (𝑓 ∘ 𝐼_𝐴) 2 = 𝑓 𝐼_𝐴 2 = 𝑓 2 = 𝑎 (𝑓 ∘ 𝐼_𝐴) 3 = 𝑓 𝐼_𝐴 3 = 𝑓 3 = 𝑑,

∴ 𝑓 ∘ 𝐼_𝐴 = 𝑓

(2) (𝐼_𝐵 ∘ 𝑓) 1 = 𝐼_𝐵(𝑓(1)) = 𝐼_𝐵(𝑐) = 𝑐, (𝐼_𝐵 ∘ 𝑓) 2 = 𝐼_𝐵(𝑓(2)) = 𝐼_𝐵(𝑎) = 𝑎 (𝐼_𝐵 ∘ 𝑓) 3 = 𝐼_𝐵(𝑓(3)) = 𝐼_𝐵(𝑑) = 𝑑,

∴ 𝐼_𝐵 ∘ 𝑓 = 𝑓

이산수학

함수의 종류 : 역함수

■ 전단사 함수𝑓: 𝐴 → 𝐵 의 역함수(Inverse function)

■ 𝑓⁻¹ ∶ 𝐵 → 𝐴

■ 𝑓 𝑎 = 𝑏 ⇒ 𝑓⁻¹ 𝑏 = 𝑎, ∀𝑎 ∈ 𝐴, ∀𝑏 ∈ 𝐵.

■ 함수 𝑓 : 가역함수

■ 만약 어떤 함수의 역함수가 존재한다면, 그 역함수는 단 하나뿐이다.

21

이산수학

역함수의 성질

■ 𝑓⁻¹ ∘ 𝑓 = 𝑓 ∘ 𝑓⁻¹= 𝐼_{𝑑𝑜𝑚(𝑓)}

■ (𝑓⁻¹ )⁻¹ = 𝑓

■ 𝑓 ∘𝑔 = 𝐼_{𝑑𝑜𝑚(𝑔)} 이면 𝑓와 𝑔는 역함수 관계이다.

■ (𝑓 ∘𝑔 )⁻¹ = 𝑔⁻¹ ∘ 𝑓⁻¹

이산수학

예제

■ 전단사함수 𝑓 ∶ 𝐴 → 𝐵, 𝑔: 𝐵 → 𝐶 에 대하여 다음을 증명하시오.

1 𝑓⁻¹ ∘ 𝑓 = 𝐼_𝐴 (2) 𝑓 ∘ 𝑓⁻¹= 𝐼_𝐵 (3) (𝑔 ∘𝑓 )⁻¹ = 𝑓⁻¹ ∘ 𝑔⁻¹ (풀이)

Let 𝑓 𝑥 = 𝑦 , 𝑔(𝑦) = 𝑧.

1 (𝑓⁻¹ ∘ 𝑓)(𝑥) = 𝑓⁻¹(𝑓(𝑥)) = 𝑓⁻¹(𝑦) = 𝑥 = 𝐼_𝐴(𝑥) 2 (𝑓 ∘ 𝑓⁻¹) 𝑦 = 𝑓 𝑓⁻¹ 𝑦 = 𝑓 𝑥 = 𝑦 = 𝐼_𝐵(𝑦) (3)

(𝑓⁻¹ ∘ 𝑔⁻¹) ∘ 𝑔 ∘ 𝑓 = 𝑓⁻¹ ∘ (𝑔⁻¹∘ 𝑔)∘ 𝑓 = 𝑓⁻¹ ∘ (𝐼_𝐵 ∘ 𝑓) = 𝑓⁻¹ ∘ 𝑓 = 𝐼_𝐴 ∴ (𝑔 ∘ 𝑓)⁻¹= 𝑓⁻¹ ∘ 𝑔⁻¹

23

이산수학

예제

■ 다음 함수 𝑓: 𝑍 → 𝑍 에 대해, 가역함수를 구하시오.

𝑓 𝑥 = 𝑥 − 1 (풀이)

(1) For any 𝑥₁ ≠ 𝑥₂ ∈ 𝑍 ⇒ 𝑥₁ − 1 ≠ 𝑥₂ − 1 ⇒ 𝑓 𝑥₁ ≠ 𝑓(𝑥₂).

∴ injective

2 ∀ 𝑦 ∈ 𝑍 𝑠. 𝑡 𝑓 𝑥 = 𝑦 ⇒ ∃𝑥 ∈ 𝑍 𝑠. 𝑡 𝑥 = 𝑦 + 1. ∴ surjective (3) By (1) & (2), 𝑓 𝑥 : one-to-one correspondence.

(4) Let 𝑓⁻¹ 𝑥 = 𝑥 + 1 ⇒ 가역함수

(i) (𝑓∘𝑓⁻¹) 𝑥 = 𝑓 𝑓⁻¹ 𝑥 = 𝑓 𝑥 + 1 = 𝑥 + 1 − 1 = 𝑥 = 𝐼_𝑍(𝑥)

(ii) (𝑓⁻¹∘𝑓 ) 𝑥 = 𝑓⁻¹ 𝑓 𝑥 = 𝑓⁻¹ 𝑥 − 1 = 𝑥 − 1 + 1 = 𝑥 = 𝐼_𝑍(𝑥)

이산수학

예제

■ 다음 함수 𝑓: 𝑍 × 𝑍 → 𝑍 × 𝑍 에 대해, 가역함수를 구하시오.

𝑓 𝑥, 𝑦 = (−𝑦, −𝑥) (풀이)

(1) For any (𝑥₁, 𝑦₁), (𝑥₂, 𝑦₂) ∈ 𝑍 × 𝑍 𝑠. 𝑡 (𝑥₁, 𝑦₁) ≠ (𝑥₂, 𝑦₂) 𝑓(𝑥₁, 𝑦₁) = (−𝑦₁, −𝑥₁) ≠ −𝑦₂, −𝑥₂ = 𝑓(𝑥₂, 𝑦₂) ∴ injective

2 ∀ −𝑦, −𝑥 ∈ 𝑍 × 𝑍 𝑠. 𝑡 𝑓 𝑥, 𝑦 = −𝑦, −𝑥 ⇒ ∃ 𝑥, 𝑦 ∈ 𝑍 × 𝑍 ∴ surjective

(3) By (1) & (2), 𝑓 𝑥 : one-to-one correspondence.

(4) Let 𝑓⁻¹ 𝑥, 𝑦 = (−𝑦, −𝑥) ⇒ 가역함수

(i) (𝑓∘𝑓⁻¹) 𝑥, 𝑦 = 𝑓 𝑓⁻¹ 𝑥, 𝑦 = 𝑓 −𝑦, −𝑥 = (𝑥, 𝑦) = 𝐼_𝑍×𝑍(𝑥, 𝑦)

(ii) (𝑓⁻¹∘𝑓 ) 𝑥, 𝑦 = 𝑓⁻¹ 𝑓 𝑥, 𝑦 = 𝑓⁻¹ −𝑦, −𝑥 = (𝑥, 𝑦) = 𝐼_𝑍×𝑍(𝑥, 𝑦)

25

이산수학

예제

■ 집합 𝐴 = 𝑎, 𝑏, 𝑐 에서 𝐵 = 𝑥, 𝑦, 𝑧 로 가는 함수

𝑓 = 𝑎, 𝑦 , 𝑏, 𝑧 , (𝑐, 𝑥) 에 대해 𝑓 ∘ 𝑓⁻¹와𝑓⁻¹ ∘ 𝑓 를 구하시오.

(풀이)

Note 𝑓 𝑎 = 𝑦, 𝑓 𝑏 = 𝑧, 𝑓 𝑐 = 𝑥.

1 (𝑓 ∘ 𝑓⁻¹) 𝑥 = 𝑓 𝑓⁻¹ 𝑥 = 𝑓 𝑐 = 𝑥, (𝑓 ∘ 𝑓⁻¹) 𝑦 = 𝑓 𝑓⁻¹ 𝑦 = 𝑓 𝑎 = 𝑦, (𝑓 ∘ 𝑓⁻¹) 𝑧 = 𝑓 𝑓⁻¹ 𝑧 = 𝑓 𝑏 = 𝑧 . ∴ 𝑓 ∘ 𝑓⁻¹ = 𝐼_𝐵

2 (𝑓⁻¹ ∘ 𝑓) 𝑎 = 𝑓⁻¹(𝑓(a)) = 𝑓⁻¹(𝑦) = 𝑎, 𝑓⁻¹ ∘ 𝑓 𝑏 = 𝑓⁻¹ 𝑓 2 = 𝑓⁻¹(𝑧) = 𝑏, (𝑓⁻¹ ∘ 𝑓) 𝑐 = 𝑓⁻¹(𝑓(𝑐)) = 𝑓⁻¹(𝑥) = 𝑐 . ∴ 𝑓⁻¹ ∘ 𝑓 = 𝐼_𝐴

이산수학

함수의 종류 : 상수함수

■ 상수함수 (Constant function)

■ 함수 𝑓: 𝐴→ 𝐵

■ ∀𝑎 ∈ 𝐴, ∃𝑐 ∈ 𝐵 s. t 𝑓 𝑎 = 𝑐

27

𝑓 𝑥 = 5, ∀𝑥 ∈ 𝑅

이산수학

함수의 종류 : 특성함수

■ 특성함수 (Characteristic function)

■ 함수 𝐻_𝐴: 𝑈→ 0, 1 𝑠. 𝑡 1, 𝑖𝑓 𝑥 ∈ 𝐴

0, 𝑖𝑓 𝑥 ∉ 𝐴 , for som𝑒 𝑠𝑢𝑏𝑠𝑒𝑡 𝐴 ⊂ 𝑈

𝐻_,0,∞): 𝑅→ 0, 1

이산수학

함수의 종류 : 바닥함수

■ 바닥함수 (Floor function) : 𝑓 ∶ 𝑅 → 𝑍

◻ ∀𝑥 ∈ 𝑅 , 𝑓 𝑥 = 𝑥 = sup 𝑛 ∈ 𝑍 𝑛 ≤ 𝑥+

◻ 𝑥 = 𝑛 ⇔ 𝑥 ≤ 𝑥 < 𝑥 + 1

29

이산수학

함수의 종류 : 천정함수

■ 천정함수 (Ceiling function) : 𝑓 ∶ 𝑅 → 𝑍

◻ ∀𝑥 ∈ 𝑅 , 𝑓 𝑥 = 𝑥 = inf 𝑛 ∈ 𝑍 𝑥 ≤ 𝑛+

◻ 𝑓 x = 𝑥 = 𝑛 ⇔ 𝑥 < 𝑥 ≤ 𝑥 + 1

이산수학

예제

■ 다음을 계산하시오.

(1) ¹

3 + ¹

2 , ¹

3 + ¹

2 (2) ¹

2 + ¹

3 , ¹

2 + ¹

3

(풀이) (1) ¹

3 + ¹

2 = 0.333 + 0.5 = 0.333 + 1 = 1.333 = 2 ¹

3 + ¹

2 = 0.333 + 0.5 = 0.333 + 0 = 0.333 = 0 (2) ¹

2 + ¹

3 = 0.5 + 0.333 = 0.5 + 0 = 0.5 = 1 ¹

2 + ¹

3 = 0.5 + 0.333 = 0.5 + 1 = 1.5 = 1

31