Hàm số - Functions

University of Florida
Dept. of Computer & Information Science & Engineering
COT 3100
Applications of Discrete Structures
Dr. Michael P. Frank
Slides for a Course Based on the Text
Discrete Mathematics & Its Applications (5th Edition)
by Kenneth H. Rosen
Module #4:
Hàm số - Functions
Rosen 5th ed., §1.8
~31 slides, ~1.5 lectures
On to section 1.8… Functions
Trong giải tích ta đã làm quen với khái niệm hàm thực f là tương ứng sao cho với mỗi xR xác định được một giá trị cụ thể nào đó y=f(x), với yR.
Nhưng khái niệm hàm số có thể mở rộng: ứng với mỗi phần tử của tập này cho tương ứng một phần tử của tập kia. (Được biết như ánh xạ.)
Hàm số: Định nghĩa hình thức
Với hai tập bất kỳ A, B, ta nói hàm f từ (hoặc ánh xạ) A vào B (f:A?B) là một phép tương ứng đúng một phần tử f(x)?B cho mỗi một phần tử x?A.
Cú th? khỏi quỏt ti?p ý tu?ng n�y:
H�m b? ph?n (khụng to�n c?c) f xỏc d?nh khụng cú ho?c m?t ph?n t? c?a B cho m?i ph?n t? x?A.
H�m n bi?n; ho?c quan h? (ch. 6).
Biểu diễn đồ thị
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
Các hàm chúng ta đã biết
Mệnh đề có thể coi như hàm số từ “các tình huống” vào các giá trị chân lý{T,F}
Hệ logic được gọi là lý thuyết tình huống.
p=“Trời đang mưa.”; s=trong tình huống ở đây, hịen tại
p(s){T,F}.
Phép toán mệnh đề có thể coi như hàm của cặp có thứ tự các giá trị chân lý vào giá trị chân lý: như, ((F,T)) = T.
Another example: →((T,F)) = F.
Nói thêm về hàm …
Vị từ (predicate) có thể coi là hàm từ tập các đối tượng vào mệnh đề (hoặc giá trị chân lý): P :≡ “is 7 feet tall”;
P(Mike) = “Mike is 7 feet tall.” = False.
Xâu bit B có độ dài n có thể coi như hàm số từ các số {1,…,n} (vị trí bit) vào các bit {0,1}.
E.g., B=101  B(3)=1.
Nói tiếp về hàm
Tập S trong tập vũ trụ U có thể xem như hàm (đặc trưng của S) từ các phần tử của U vào {T, F}, nói rằng mỗi phần tử của U có là phần tử của S không?
S={3} S(0)=F, S(3)=T.
Phép toán tập hợp như ,, có thể coi như hàm từ cặp các tập hợp vào tập hợp.
Example: (({1,3},{3,4})) = {3}
Thủ thuật đơn giản
Đôi khi ta viết YX để chỉ tập F bao gồm mọi hàm có thể f:XY.
Ký hiệu này đặc biệt phù hợp, bởi vì đối với hai tập hữu hạn X, Y, ta có |F| = |Y||X|.
Nếu ta sử dụng biểu diễn F0, T1, 2:{0,1}={F,T}, thì tập con TS có thể xem là hàm từ S vào 2, vì vậy tập mũ của S (tập mọi hàm như vậy) là 2S như đã ký hiệu
Một số thuật ngữ về hàm số
Nếu viết f:AB, và f(a)=b (với aA & bB), thì ta nói:
A là miÒn (domain) của f.
B là ®èi miÒn (codomain) của f.
b là ảnh của a qua f.
a là tiền ảnh của b qua f.
Nói chung, b có thể có nhiều hơn một tiền ảnh.
Miền giá trị (Range) RB của f là
R={b | a f(a)=b }.
We also say
the signature
of f is A→B.
Miền giá trị và đối miền
Range versus Codomain
Miền giá trị của hàm có thể không là toàn bộ codomain.
Codomain là tập mà hàm đang xét sẽ ánh xạ mọi giá trị của domain vào đó.
Miền giá trị là một tập các giá trị trong codomain mà thực tế hàm ánh xạ mọi phần của domain vào đó.
Range vs. Codomain - Example
Giả sử tôi nói với các bạn rằng: “f là hàm ánh xạ mọi sinh viên trong lớp vào tập các điểm {A,B,C,D,E}.”
Bạn cho biết codomain của f là: ________, miền giá trị của f là ________.
Giả sử mọi điểm đều là A và B.
Khi đó miền giá trị của f là _________, nhưng codomain là __________________.
{A,B,C,D,E}
unknown!
{A,B}
still {A,B,C,D,E}!
Phép toán (general definition)
Phép toán n-ngôi trên tập S là hàm bất kỳ từ tập các bộ có thứ tự gồm n phần tử của S vào chính S.
E.g., if S={T,F},  có thể coi như phép toán 1 ngôi, và , là các phép toán 2 ngôi trên S.
Ví dụ khác:  và  là các phép toán 2 ngôi trên tập các tập hợp.
Xây dựng phép toán cho hàm số
Nếu  (“dot”) là bất kỳ phép toán nào trên B, thì ta có thể mở rộng  thành phép toán trên các hàm số từ A nào đó vào B f:AB.
Chẳng hạn: Cho phép toán 2 ngôi bất kỳ :BBB, và các hàm f,g:AB, ta định nghĩa (f  g):AB là hàm số được xác định như sau:
aA, (f  g)(a) = f(a)g(a).
Ví dụ phép toán hàm số
Function Operator Example
,× (“céng”,“nh©n”) lµ c¸c phÐp to¸n hai ng«I trªn R. (Céng vµ nh©n b×nh th­êng hai sè)
Khi ®ã, ta cã thÓ céng vµ nh©n hµm sè f,g:RR:
(f  g):RR, trong ®ã (f  g)(x) = f(x)  g(x)
(f × g):RR,trong ®ã (f × g)(x) = f(x) × g(x)
Phép hợp hàm
Function Composition Operator
Đối với các hàm số g:AB và f:BC, có một phép toán đặc biệt gọi là hợp hàm (compose “○”).
Nó hợp thành hàm mới từ f và g bằng cách áp dụng f cho kết quả của việc áp dụng g.
Ta nói (f○g):AC, với (f○g)(a) :≡ f(g(a)).
Vì g(a)B, nên f(g(a)) được xác định nghĩa và C.
Lưu ý rằng ○ (giống tích Đề các , nhưng không giống +,,) vì không giao hoán. (Nói chung, f○g  g○f.)
Note match here.
Ảnh của tập hợp qua hàm số
Cho f:AB, và SA,
Ảnh của S qua f là tập gồm tất cả các ảnh (qua f) của các phần tử trong S.
f(S) : {f(s) | sS}
: {b |  sS: f(s)=b}.
Lưu ý rằng miền giá trị là ảnh (qua f) của domain của f!
Hàm số 1-1 One-to-One Functions
A function is one-to-one (1-1), hoặc đơn ánh, iff mọi phần tử của miền giá trị chỉ có một nghịch ảnh.
Một cách hình thức: cho f:AB,
“x đơn ánh” : (x,y: xy  f(x)f(y)).
Chỉ có một phần tử của domain được ánh xạ vào một phần tử cho trước của miền giá trị.
Miền (domain) & miền giá trị (range) có cùng lực lượng. Có thể nói gì về đối miền (codomain)?
Dễ nhớ: Mỗi phần tử của domain được ánh xạ vào phần tử riêng biệt của miền giá trị.
So sánh “mỗi liều vaxin được tiêm cho một bệnh nhân khác nhau.”
Biểu diễn 1-1
One-to-One Illustration
Đồ thị hai phần biểu diễn hàm là (hoặc không là) one-to-one:
•
•
•
•
•
•
•
•
•
One-to-one
•
•
•
•
•
•
•
•
•
Not one-to-one
•
•
•
•
•
•
•
•
•
Not even a
function!
Các điều kiện đủ cho ánh xạ 1-1
Với hàm f trên các tập số, ta nói:
f là đơn điệu tăng chặt khi và chỉ khi x>y ? f(x)>f(y) đối với mọi x,y trong miền;
f là đơn điệu giảm chặt khi và chỉ khi x Nếu f là tăng chặt hay giảm chặt thì f là ánh xạ 1 - 1. VD. x3
Ngược lại là không nhất thiết phải đúng.
Hàm toàn ánh –
Onto (Surjective) Functions
Hàm f:AB là hàm lên hay toàn ánh iff miền xác định của nó bằng codomain của nó (bB, aA: f(a)=b).
Think: Hàm lên (onto) ánh xạ tập A lên (over, covering) toàn bộ tập B, chứ không phải chỉ một phần của nó.
VD, §èi víi miÒn vµ ®èi miÒn R, x3 lµ ¸nh x¹ lªn, cßn x2 kh«ng ph¶i. (t¹i sao?)
Illustration of Onto (ánh xạ lên)
Hàm nào là ánh xạ lên đối miền của chúng:
Onto
(but not 1-1)
•
•
•
•
•
•
•
•
•
Not Onto
(or 1-1)
•
•
•
•
•
•
•
•
•
Both 1-1
and onto
•
•
•
•
•
•
•
•
1-1 but
not onto
•
•
•
•
•
•
•
•
•
Song ánh - Bijections
Hàm f được gọi là song ánh hay đảo được, iff nó vừa là 1-1 vừa là toàn ánh.
Đối với song ánh f:AB, tồn tại ánh xạ ngược với f, được viết là f 1:BA, mà là hàm duy nhất sao cho
(với IA là ánh xạ đồng nhất trên A)
Hàm đồng nhất
The Identity Function
Với mọi miền A, hàm đồng nhất I:AA (hoặc viết dạng, IA, 1, 1A) là ánh xạ duy nhất sao cho aA: I(a)=a.
Một số hàm đồng nhất mà ta đã biết:
Cộng + với 0, nhân . với 1, hội  với T, tuyển  với F, hợp  với rỗng , giao  với U.
Lưu ý rằng hàm đồng nhất luôn là ánh xạ một - một và toàn ánh (song ánh).
The identity function:
Biểu diễn hàm đồng nhất
Identity Function Illustrations
Domain and range
x
y
y = I(x) = x
Đồ thị các hàm
Graphs of Functions
Ta có thể biểu diễn hàm f:AB như một tập các cặp có thứ tự {(a,f(a)) | aA}.
Lưu ý rằng a, chỉ có một cặp (a,b).
Sau này (ch.6): Quan hệ (relations) không có tính chất này.
§èi víi hµm trªn sè, ta cã thÓ biÓu diÔn cÆp cã thø tù (x,y) nh­ mét ®iÓm trªn mÆt ph¼ng.
Hµm khi ®ã ®­îc vÏ nh­ mét ®­êng cong (tËp c¸c ®iÓm), víi chØ mét y cho mçi x.
← The function’s graph.
Nói thêm về biểu diễn
Aside About Representations
Có thể biểu diễn kiểu bất kỳ của một cấu trúc rời rạc (propositions, bit-strings, numbers, sets, ordered pairs, functions) theo từ ngữ của một một cấu trúc khác (hoặc kết hợp một số khác).
Có thể không có cấu trúc nào trong số trên là cơ bản hơn các cấu trúc khác (tức là được dùng để biểu diễn các cấu trúc khác). Tuy nhiên, xâu, logic và tập hợp ( strings, logic, and sets) thường được dùng làm cơ sở cho mọi thứ còn lại Như trình bày trong cuốn sách sau 
Một cặp hàm quan trọng
A Couple of Key Functions
Trong toán rời rạc, ta thường sử dụng hai hàm sau trên số thực:
Hàm nền (floor function) ·:R→Z, trong đó x (“nền của x”) là số nguyên lớn nhất mà nhỏ hơn x. I.e., x :≡ max({iZ|i≤x}).
Hàm trần (ceiling function) · :R→Z, trong đó x (“trần của x”) là số nguyên nhỏ nhất mà lớn hơn x. Tức là x :≡ min({iZ|i≥x})
Biểu diễn hàm nền và trần
Visualizing Floor & Ceiling
Các số thực "rơi xuống sàn của chúng" hoặc "nâng lên sàn của chúng"
Lưu ý rằng nếu x?Z,
??x? ? ? ?x? &
??x? ? ? ?x?
Lưu ý rằng nếu x?Z,
?x? = ?x? = x.
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
Vẽ hàm qua nền và trần
Plots with floor/ceiling
Vẽ đồ thị hàm f(x)=x, đồ thị của f chứa điểm (a, 0) đối với mọi giá trị của a mà a0 và a<1, nhưng không phải đối với a=1.
Ta nói rằng tập các điểm (a,0) trong f không bao gồm điểm biên phải (a,1).
Khi vẽ điểm biên ta dùng vòng tròn mở nếu điểm biên không thuộc đồ thị và vòng tròn đặc, nếu điểm biên nằm trên đồ thị.
Ví dụ: Vẽ với sàn và trần
Plots with floor/ceiling: Example
Plot of graph of function f(x) = x/3:
x
f(x)
Set of points (x, f(x))
+3
2
+2
3
Review of §1.8 (Functions)
Function variables f, g, h, …
Notations: f:AB, f(a), f(A).
Terms: image, preimage, domain, codomain, range, one-to-one, onto, strictly (in/de)creasing, bijective, inverse, composition.
Function unary operator f 1,
binary operators , , etc., and ○.
The RZ functions x and x.
Ví dụ hàm số
Tập sinh viên học phần Toán Rời rạc: S
Tập các điểm từ 0 đến 100: D={0,1,.. ,100}
Chấm điểm học kỳ có là ánh xạ C: S ->D?
Các khái niệm về hàm số liên quan đến C:
Cã lµ ¸nh x¹ kh«ng?
MiÒn, ®èi miÒn, miÒn gi¸ trÞ
lªn, 1-1, song ¸nh?


Cái gì là hàm số và nêu tính chất
Quê quán: Sinh viên -> tỉnh
Liên hệ: Sinh viên -> số điện thọai
Bạn thân: Sinh viên -> Sinh viên
Danh tính: Sinh viên -> mã sinh viên
Đăng ký: Sinh viên -> học phần
Bảng điểm thi môn: Sinh viên -> điểm thi môn
Bảng điểm sinh viên: môn học -> điểm
Tạm trú: Sinh viên -> địa chỉ nhà
Phân phòng học: Lớp -> phòng học
Phân phụ trách môn: Môn học -> Thày giáo
Phân giảng: Học phần -> Thày giáo