이산수학(Discrete Mathematics)  함수 (Functions) 2013년 봄학기 강원대학교 컴퓨터과학전공 문양세

함수의 정의 (1/2) 1.8 Functions From calculus, you are familiar with the concept of a real-valued 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 concept of assigning elements of any set to elements of any set. (함수에 대한 표기는 비단 실수 집합이 아닌 임의의 집합들을 대상으로 일반화시킬 수 있다.)

함수의 정의 (2/2) 1.8 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의 원소 단 하나에 대응시킴)

Graphical Representations 1.8 Functions Functions can be represented graphically in several ways: A B f • • f • • • • • a b • y • • • A x B Bipartite Graph Like Venn diagrams Plot

Examples of Functions (We’ve seen so far) A proposition can be viewed as a function from “situations” 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 function from pairs of sets to sets. (집합 연산자) Example: ({1,3},{3,4}) = {3}

Function Terminologies 1.8 Functions 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 }. [치역]

Range versus Codomain (치역과 공역) (1/2) 1.8 Functions 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. (치역은 공역의 부분집합으로서, 함수에 의해 실제 매핑이 일어난 원소의 집합이다.)

Range versus Codomain (치역과 공역) (2/2) 1.8 Functions 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}이다.)

Function Operators (Example) 1.8 Functions , × (“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 (예제 4) f,g:RR, f(x) = x2, g(x) = x – x2 (f  g)(x) = f(x)  g(x) = (x2)  (x – x2) = x (f×g)(x) = f(x)×g(x) = (x2)×(x – x2) = x3 – x4

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 (예제 5) 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}

One-to-One Functions (단사함수) A function is one-to-one (1-1) or injective iff every element 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? ( may be larger)

One-to-One Illustration 1.8 Functions 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!

Sufficient Conditions for 1-1ness 1.8 Functions 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. x3 Converse is not necessarily true. E.g. 1/x

Onto Functions (전사함수) 1.8 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, x3 is onto, whereas x2 isn’t. (Why not?)

Some functions that are or are not onto their codomains: Onto Illustration 1.8 Functions 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

Bijection (전단사함수) 1.8 Functions A function f is a one-to-one correspondence, or a bijection, or reversible, or invertible, iff it is both one-to-one and onto. (전사함수이면서 단사함수이면, 이를 전단사함수라 한다.) • • • • • • • • both 1-1 and onto  bijection

Identity Functions (항등함수) For any domain A, the identity function I:AA (or IA) 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 (bijective). (모든 원소에 대해 자기 자신을 대응시키므로 당연!)

Identity Function Illustration 1.8 Functions • • • y • • • • • • x Domain and range

Composite Operator (함수의 합성) (1/2) 1.8 Functions For functions g:AB and f:BC, there is a special operator 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.) (일반적으로, 교환법칙은 성립하지 않는다.)

Composite Operator (함수의 합성) (2/2) 1.8 Functions 예제 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 

Composition Illustration 1.8 Functions (f◦g)(a) g(a) f(b) a g(a) = b f(g(a)) g f A B C f◦g

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) b = f(a) f-1(b) f f-1

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.

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. (수에 대한 함수인 경우, 함수를 평면상에 그릴 수 있다.)

Graphs of Functions (2/2) 예제 f:ZZ, f(x) = x2 graph of f = {…, (-2,4), (-1,1), (0,0), (1,1), (2,4), …) ●

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

. 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) 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

Plots with Floor/Ceiling: Example 1.8 Functions Plot of graph of function f(x) = x/3: Set of points (x, f(x)) +2 3 x +3 2

How many bytes are necessary to store 100 bits? Bits versus Bytes 1.8 Functions How many bytes are necessary to store 100 bits? 1 byte = 8 bits 100/8 = 12.5 = 13 bytes

Homework #2 1.8 Functions