Toán tin - Tập hợp, ánh xạ

Nội dung text: Toán tin - Tập hợp, ánh xạ

1. 1. Lý thuyết tập hợp 2. Ánh xạ
2. Tập hợp là khái niệm cơ bản của toán học dùng để biểu diễn 1 lực lượng nào đó Ví dụ : Tập hợp số thực Sơ đồ Ven : Ký hiệu : a A ; Tập hợp rỗng không chứa bất kỳ phần tử nào. Ký hiệu : Ø
3. Liệt kê : . A={1, 2, 3, 4, a, b} Theo tính chất : . B={ n N | n là số chính phương}
4. Hai tập hợp bằng nhau khi chúng có cùng các phần tử Cho tập hợp: A { 3 , 4 } và B {x R | x2 x 12 0} C {3, 2} Hỏi A, B và C có bằng nhau hay không ?
5. Nếu mọi phần tử của tập A đều là phần tử của tập B thì A là tập hợp con của B. Ký hiệu : A  B Ta luôn có : A  A ; Ø  A Chứng minh hai tập hợp bằng nhau ?
6. Cho X là một tập hợp. Khi đó tập tất cả các tập con của X được ký hiệu là P(X) Ví dụ : Cho tập X = {a, b} P( X )  { ,{},{},{, a b a b }} YPY {1,2,3}, ( ) ? Với tập hợp |X|=k. P(X)=?
7. a. Phép hợp : Cho 2 tập hợp A và B. Ta nói A hợp B. Ký hiệu : AB ()()x A  B x A  x B Ví dụ : A = { 1, 2 , 3}; B = { a, b, c } Xác định :
8. 1. Tính lũy đẳng : AAA 2. Tính giao hoán : ABBA  3. Tính kết hợp : ABCABC()()    4. Hợp với tập rỗng :  AAA 
9. b. Phép giao : Giao của 2 tập hợp A và B là tập hợp tạo bởi các phần tử vừa thuộc A vừa thuộc B. Ký hiệu : AB  ()()x A  B x A  x B Ví dụ : Xác định giao của hai tập hợp sau : A = { 1, 0 , 2, a, } B = { 2, 0, 1 }
10. 1. Tính lũy đẳng : AAA 2. Tính giao hoán : ABBA  3. Tính kết hợp : ABCABC()()    4. Giao với tập rỗng : AA   Tính phân phối của phép giao và phép hợp : 1)ABCABAC (  ) (  )  (  ) 2)ABCABAC (  ) (  )  (  )
11. . c. Phép hiệu : Hiệu của hai tập hợp là tập tạo bởi tất cả các phần tử thuộc tập A mà không thuộc tập B . Ký hiệu A\B (\)()x A B x A  x B
12. Phần bù : Khi AB  thì B\A gọi là bù của A trong B. Ký hiệu A hay CA B
13. Tích Đề các của tập hợp A với tập hợp B (theo thứ tự lấy) là tập hợp bao gồm tất cả các cặp thứ tự (x,y) với x A, y B (,)()x y A B x A  y B Ký hiệu AxB hoặc A.B Chú ý: Tích của 2 tập hợp không có tính chất giao hoán. Ví dụ : A ={1, 2} B={a, b} A x B = { (1,a), (1,b), (2,a), (2,b)}
14. 1) ABAB  2) ABAB  Chứng minh : x A B x (A B) x A và x B x A x B x A x B
15. Các phép toán trên tập hợp có thể mở rộng cho nhiều hơn 2 tập hợp tạo thành 1 phân hoạch : Aii {x  i I, x A } iI Aii {x  i I, x A } iI  Ai (x i ) i I  i I, x i A i iI