Hàm số - Functions

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete 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 ý tưởng này: Hàm bộ phận (không toàn cục) f xác đị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 saythe signatureof f is A→B. MiÒn gi¸ trÞ vµ ®èi miÒnRange 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 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ất4` 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