이산수학(Discrete Mathematics)

Slides:



Advertisements
Similar presentations
2016 년 봄학기 강원대학교 컴퓨터과학전공 문양세 이산수학 (Discrete Mathematics) 알고리즘과 복잡도 (Algorithms and Complexity)
Advertisements

Lesson 2 A Caring Friend. Making true friends is hard. Keeping them is even harder. To keep a good friendship, you need to care about others. Then, how.
2012 년 봄학기 강원대학교 컴퓨터과학전공 문양세 이산수학 (Discrete Mathematics)  중첩된 한정기호 (Nested Quantifiers)
Add Your Text 5. 지수함수와 로그함수 1. 지수함수 2. 로그함수 · 지수함수와 그 그래프 · 지수방정식과 지수부등식 · 로그 함수와 그 그래프 · 로그방정식과 로그부등식.
ALL IN ONE WORKING HOLIDAY!
Chapter 7: Entity-Relationship 모델
Lecture 9 프로그램 실행의 비용 computation cost – 시간 time, 메모리 memory – tractable vs intractable problems.
이산수학(Discrete Mathematics)
(Mathematical Induction)
C++ Tutorial 1 서강대학교 데이터베이스 연구실.
Sources of the Magnetic Field
Mathematics for Computer Graphics
Chapter 7 ARP and RARP.
이산수학(Discrete Mathematics)  정수와 나눗셈 (The Integers and Division)
이산수학(Discrete Mathematics)  정수와 나눗셈 (The Integers and Division)
이산수학(Discrete Mathematics)
1.8 함수 (Functions) 이산수학 (Discrete Mathematics) 2006년 봄학기 문양세
이산수학(Discrete Mathematics)
Chaper 2 ~ chaper 3 허승현 제어시스템 설계.
이산수학(Discrete Mathematics)
Discrete Math II Howon Kim
외국인과 대화를~~ 대학에서 교환학생을~~
이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)
제 14 장 거시경제학의 개관 PowerPoint® Slides by Can Erbil
Chapter 2. Finite Automata Exercises
Discrete Math II Howon Kim
숭실대학교 마이닝연구실 김완섭 2009년 2월 8일 아이디어  - 상관분석에 대한 연구
계수와 응용 (Counting and Its Applications)
Student A Say “I’m going to ask you some questions about The Internet and Technology.” Are you ready?
Medical Instrumentation
1.4 중첩된 한정기호 (Nested Quantifiers) 이산수학 (Discrete Mathematics)
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
(Relations and Its Properties)
Write and say bye to friends,
Mathematical Description of Continuous-Time Signals
제 8 장 실업과 인플레이션.
Introduction to Programming Language
Discrete Math II Howon Kim
이산수학(Discrete Mathematics)  증명 방법 (Methods of Proof)
이산수학 (Discrete Mathematics)
이산수학(Discrete Mathematics)
이산수학(Discrete Mathematics)  명제의 동치 (Propositional Equivalence)
합집합과 교집합이란 무엇인가? 01 합집합 두 집합 A, B에 대하여 A에 속하거나 B에 속하는 모든 원소로 이루어진 집합을 A와 B의 합집합이라고 하며, 기호 A∪B로 나타낸다. A∪B ={x | x∈A 또는 x∈B}
6.1 점화 관계 (Recurrence Relations)
CEO가 가져야 할 품질 혁신 마인드.
Discrete Math II Howon Kim
2. Boole 대수와 논리 게이트.
이것만은 기억해라!! (크리에이티브한 광고 만드는 방법 3가지) 광고 홍보 학과 박태진.
제 세 동.
이산수학(Discrete Mathematics) 비둘기 집 원리 (The Pigeonhole Principle)
이산수학(Discrete Mathematics)
이산수학(Discrete Mathematics)  집합 연산 (Set Operations)
점화와 응용 (Recurrence and Its Applications)
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
1. 관계 데이터 모델 (1) 관계 데이터 모델 정의 ① 논리적인 데이터 모델에서 데이터간의 관계를 기본키(primary key) 와 이를 참조하는 외래키(foreign key)로 표현하는 데이터 모델 ② 개체 집합에 대한 속성 관계를 표현하기 위해 개체를 테이블(table)
자동제어공학 4. 과도 응답 정 우 용.
2.7 행렬 (Matrices] 이산수학 (Discrete Mathematics) Matrix Reloaded
이산수학(Discrete Mathematics)
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
이산수학(Discrete Mathematics) 수열과 합 (Sequences and Summations)
(Predicates and Quantifiers)
이산수학(Discrete Mathematics)  술어와 한정기호 (Predicates and Quantifiers)
Presentation by Timothy Kane
Introduction to Computer System 컴퓨터의 이해 3: 데이터 표현
[CPA340] Algorithms and Practice Youn-Hee Han
빈칸에 알맞은 것을 [보기]에서 골라 문장을 완성하시오
(Permutations and Combinations)
Chapter 4. Energy and Potential
Ⓒ Copyright CARROT Global. All Rights Reserved.
Sawasdee ka.
Presentation transcript:

이산수학(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