함수

2016년 봄학기 강원대학교 컴퓨터과학전공 문양세

이산수학 (Discrete Mathematics)

함수 (Functions)

강의 내용

함수 정의와 구분 함수 합성과 역함수

함수 표현과 주요 함수

Functions

함수의 정의 (1/2)

From calculus, you are familiar with the concept of a real-val- ued function f, which assigns each number xR to a particular value y=f(x), where yR.

( 여러 분이 대수학에서 이미 익숙한 실수 집합에 대한 함수로 이해할 수 있다 .)

But, the notion of a function can also be generalized to the con- cept of assigning elements of any set to elements of any set.

( 함수에 대한 표기는 비단 실수 집합이 아닌 임의의 집합들을 대상으로 일반화 시킬 수 있다 .)

Functions

Definition: For any sets A, B, we say that a function f from (or

“mapping”) A to B (f:AB) is a particular assignment of exactly one element f(x)B to each element xA.

( 함수 f 는 A 의 원소 각각에 대해서 B 의 원소를 단 하나만 대응시킴 )

Definition: A partial function f assigns zero or one elements of B to each element xA.

( 부분함수 f 는 A 의 일부 (or 전체 ) 원소 각각을 B 의 원소 단 하나에 대응시 킴 )

함수의 정의 (2/2)

Functions

Graphical Representations

Functions can be represented graphically in several ways:

• •

A B

a b

f f

•

••

•

•

•

•

•

• x

y

Plot Bipartite Graph

Like Venn diagrams

A B

Functions

Examples of Functions (We’ve seen so far)

A proposition can be viewed as a function from “situa- tions” to truth values {T,F} ⁽ 명제 함수 )

 A logic system called situation theory.

 p=“It is raining.”; s=our situation here, now

 p(s){T,F}

A propositional operator can be viewed as a function from ordered pairs of truth values to truth values: ( 명제 연산자 )

 ((F,T)) = T

 →((T,F)) = F

A set operator such as , , can be viewed as a func-

Functions

Function Terminologies

If f:AB, and f(a)=b (where aA & bB), then:

 A is the domain of f. [ 정의역 ]

 B is the codomain of f. [ 공역 ]

 b is the image of a under f. [ 상 ]

 a is a pre-image of b under f. [ 원상 ] (In general, b may have more than 1 pre-image.)

 The range RB of f is {b | a f(a)=b }. [ 치역 ]

Functions

Range versus Codomain ( 치역과 공역 ) (1/2)

The range of a function might not be its whole codomain.

( 함수의 치역은 전체 공역이 아닐 수 ( 다를 수 ) 있다 .)

The range is the particular set of values in the codomain that the function actually maps elements of the domain to.

( 치역은 공역의 부분집합으로서 , 함수에 의해 실제 매핑이 일어난 원소의 집합이 다 .)

Functions

Range versus Codomain ( 치역과 공역 ) (2/2)

Example

 Suppose I declare to you that: “f is a function mapping students in this class to the set of grades {A, B, C, D, F}.”

(함수 f 는 {A, B, C, D, F} 의 성적을 부여하는 함수라 하자 .)

 At this point, you know f’s codomain is: {A, B, C, D, F}, and its range is unknown!.

(성적을 부여하기 전에 공역은 {A, B, C, D, F} 로 알 수 있으나 , 그 치역은 알지 못한 다 .)

 Suppose the grades turn out all As and Bs.

(공부들을 잘해서 모두 A 와 B 를 주었다고 하자 .)

 Then the range of f is {A, B}, but its codomain is still {A, B, C, D, F}.

(치역은 {A, B} 로 결정 되었지만 , 공역은 그대로 {A, B, C, D, F} 이다 .)

Functions

Function Operators (Example)

, × (“plus”, “times”) are binary operators over R. (Normal addition & multiplication.)

If f,g:RR, then the followings hold: ( 정의 )

 (f  g):RR, where (f  g)(x) = f(x)  g(x)

 (f×g):RR, where (f × g)(x) = f(x) × g(x)

Example

 f,g:RR, f(x) = x², g(x) = x – x²

 (f  g)(x) = f(x) ^ g(x) = (x²)^ (x – x²) = x

 (f×g)(x) = f(x)×g(x) = (x²)×(x – x²) = x³ – x⁴

Functions

Images of Sets under Functions ( 집합에 대한 상 ) Given f:AB, and SA,

The image of S under f is simply the set of all images of the elements of S. (S 의 image 는 S 의 모든 원소의 image 의 집 합 )

f(S) = {f(s) | sS} = {b |  sS(f(s)=b)}.

Note the range of f can be defined as simply the image of f’s domain!

(f 의 치역은 f 의 정의역에 대한 상 (image) 로 정의할 수 있다 .)

Example

 A = {a, b, c, d, e}, B = {1, 2, 3, 4}, S = {b, c, d}

 f(a) = 2, f(b) = 1, f(c) = 4, f(d) = 1, f(e) = 1

 f(S) = {1, 4}

Functions

One-to-One Functions ( 단사함수 )

A function is one-to-one (1-1) or injective iff every ele- ment of its range has only 1 pre-image.

( 치역의 모든 원소는 오직 하나의 역상 (pre-image) 를 가진다 .)

Formally: given f:AB,

“x is injective” = (x,y: xy  f(x)f(y)).

Only one element of the domain is mapped to any given one element of the range.⁽ 정의역의 한 원소는 치역의 한 원소에 대 응 )

 Domain & range have same cardinality. What about codomain?

Functions

One-to-One Illustration

Bipartite (2-part) graph representations of functions that are (or not) one-to-one:

•

••

•

•

•

•

•

• One-to-one

••

••

••

•

•

•

Not one-to-one

••

••

••

•

•

• Not even a

function!

Functions

Sufficient Conditions for 1-1ness For functions f over numbers,

 f is strictly (or monotonically) increasing iff x>y  f(x)>f(y) for all x,y in domain; (strictly increasing function, 단조 증가 함수 )

 f is strictly (or monotonically) decreasing iff x>y  f(x)<f(y) for all x,y in domain; (strictly decreasing function, 단조 감소 함수 )

If f is either strictly increasing or strictly decreasing, then f is one-to-one. E.g. x³

 Converse is not necessarily true. E.g. 1/x

Functions

Onto Functions ( 전사함수 )

A function f:AB is onto or surjective iff its range is equal to its codomain (bB, aA: f(a)=b). ⁽ 치역과 공역이 동일하

다 .)

An onto function maps the set A onto (over, covering) the entirety of the set B, not just over a piece of it.

E.g., for domain & codomain R, x³ is onto, whereas x² isn’t. (Why not?)

Functions

Onto Illustration

Some functions that are or are not onto their codomains:

Onto

(but not 1-1)

•

••

•

•

•

•

•

•

Not Onto (or 1-1)

•

••

•

•

•

•

•

•

Both 1-1 and onto

•

••

•

•

•

•

•

1-1 but not onto

•

••

•

•

•

•

•

•

Functions

Bijection ( 전단사함수 )

A function f is a one-to-one correspondence, or a bijec- tion, or reversible, or invertible, iff it is both one-to-one and onto. ⁽ 전사함수이면서 단사함수이면 , 이를 전단사함수라 한다 .)

both 1-1 and onto

 bijection

•

••

•

•

•

•

•

Functions

Identity Functions ( 항등함수 )

For any domain A, the identity function I:AA (or I_A) is the unique function such that aA: I(a)=a.

( 항등함수는 정의역의 각 원소 (a) 를 자기 자신 (I(a)=a) 에 대응시키는 함수이 다 .

Some identity functions we’ve seen:

 ing 0, ·ing by 1

 ing with T, ing with F

 ing with , ing with U.

Note that the identity function is both one-to-one and onto

Functions

Identity Function Illustration

• •

•

•

•

•

• •

•

Domain and range x

y

Functions

강의 내용

함수 정의와 구분 함수 합성과 역함수

함수 표현과 주요 함수

Functions

Composite Operator ( 함수의 합성 ) (1/2)

For functions g:AB and f:BC, there is a special opera- tor called compose (“◦”).

 It composes (creates) a new function out of f, g by applying f to the result of g. ⁽ 함수 g 의 결과에 대해 함수 f 를 적용한다 .)

 (f◦g):AC, where (f◦g)(a) = f(g(a)).  정의

 Note g(a)B, so f(g(a)) is defined and C.

 Note that ◦ (like Cartesian , but unlike +, , ) is non-commuting.

(Generally, f◦g  g◦f.) ( 일반적으로 , 교환법칙은 성립하지 않는다 .)

Functions

Composite Operator ( 함수의 합성 ) (2/2) 예제

 f,g:NN, f(x) = 2x+3, g(x) = 3x+2

 (f◦g)(x) = f(g(x)) = 2(3x+2)+3 = 6x+7

 (g◦f)(x) = g(f(x)) = 3(2x+3)+2 = 6x+11 

Functions

Composition Illustration

f◦g (f◦g)(a)

g(a) f(b)

A B C

a g(a) = b f(g(a))

g f

Functions

Inverse Functions ( 역함수 ) (1/2)

For bijections f:AB, there exists an inverse of f, written f^1:BA, which is the unique function such that f^1◦f=I.

( 전단사함수 f 에서 f(a) = b 가 성립할 때 , 함수 f 의 역함수 f^1 는 B 의 모든 원소 b 에 대해 A 의 원소 a 를 대응시키는 함수이다 .)

f(a)

A B

a = f^-1(b) f^-1(b) b = f(a)

f f^-1

Functions

Inverse Functions ( 역함수 ) (2/2) 예제

 f:ZZ, f(x) = x + 1

 f is a strictly increasing function, and thus, f is bijection.

 Let f(x) = y, then y = x + 1 and x = y – 1.

 Therefore, f^-1(y) = y – 1.

Functions

강의 내용

함수 정의와 구분 함수 합성과 역함수

함수 표현과 주요 함수

Functions

Graphs of Functions (1/2)

We can represent a function f:AB as a set of ordered pairs {(a, f(a))| aA} called a graph.

( 함수 f 의 그래프는 (a, f(a)) 로 구성되는 순서쌍 (pair) 의 집합이다 .)

Note that a, there is only 1 pair (a, f(a)).

For functions over numbers, we can represent an ordered pair (x, y) as a point on a plane. A function is then drawn as a curve (set of points) with only one y for each x.

(수에 대한 함수인 경우 , 함수를 평면상에 그릴 수 있다 .)

Functions

Graphs of Functions (2/2) 예제

 f:ZZ, f(x) = x²

 graph of f = {…, (-2,4), (-1,1), (0,0), (1,1), (2,4), …)

●

●

●

●

●

●

●

Functions

A Couple of Key Functions

In discrete math, we will frequently use the following functions over real numbers:

 x (“floor of x”) is the largest (most positive) integer  x.

(실수 x 에 대해서 , x 와 같거나 x 보다 작은 수 중에서 x 에 가장 가까운 정수 )

 x (“ceiling of x”) is the smallest (most negative) integer  x.

(실수 x 에 대해서 , x 와 같거나 x 보다 큰 수 중에서 x 에 가장 가까운 정수 )

예제

 1/2 = 0, 1/2 = 1, 3.1 = 3, 3.1 = 4, 7 = 7, 7 = 7

 -1/2 = -1, -1/2 = 0, -3.1 = -4, -3.1 = -3

Functions

Visualizing Floor & Ceiling Functions

Real numbers “fall to their floor” or “rise to their ceiling.”

Note that if xZ,

 x   x (1.5 = 2   1.5 = 1)

 x   x (1.5 = 1   1.5 = 2)

Note that if xZ,

 x = x = x (2 = 2 = 2)

Note that if xR,

 x =  x (1.5 = 2 =  1.5)

 x =  x (1.5 = 1 =  1.5)

0

1 1 2 3

2

3

. . .

. .

. .. .

1.6

1.6=2

1.4= 2

1.4

1.4= 1

1.6=1

3

3=3= 3

Functions

Plots with Floor/Ceiling: Example Plot of graph of function f(x) = x/3:

x Set of points (x, f(x))

+3

2 +2

3

Functions

Bits versus Bytes

How many bytes are necessary to store 100 bits?

 1 byte = 8 bits

 100/8 = 12.5 = 13 bytes

Functions

강의 내용

함수 정의와 구분 함수 합성과 역함수

함수 표현과 주요 함수

Functions

Homework #2

Functions