Giáo trình Đặc tả hình thức - Chương 2: Tập hợp và quan hệ - Nguyễn Thị Minh Tuyền

Nội dung text: Giáo trình Đặc tả hình thức - Chương 2: Tập hợp và quan hệ - Nguyễn Thị Minh Tuyền

1. LOGO Đặc tả hình thức Tập hợp và quan hệ Nguyễn Thị Minh Tuyền Nguyễn Thị Minh Tuyền 1
2. Tập hợp (Set) v Tập các đối tượng rời rạc (không có thứ tự). v Một tập hợp được tạo ra từ một miền (domain) các đối tượng mà trong đó tất cả các đối tượng có cùng kiểu (type) § Tập hợp có tính đồng nhất. Miền đối v Ví dụ: tượng § {2,4,5,6, } tập hợp các số nguyên. § {red, yellow, blue} tập hợp các màu. § {true, false} tập hợp các giá trị boolean. § {red, true, 2} không phải tập hợp. Nguyễn Thị Minh Tuyền 2 Đặc tả hình thức
3. Giá trị của một tập hợp v Là tập hợp các phần tử của tập hợp. v Hai tập A và B là bằng nhau nếu § Mọi phần tử của A đều là phần tử của B. § Mọi phần tử của B đều là phần tử của A. § Ký hiệu: A = B § Ví dụ: • {a, b, c} = {c, b, a} v x ∈ S nghĩa là “x là một phần tử của S”. § Ví dụ: • x∈{x, y, z} • 50∈N Nguyễn Thị Minh Tuyền 3 Đặc tả hình thức
4. Giá trị của một tập hợp v x ∉ S nghĩa là “x không phải là một phần tử của S”. § Ví dụ: 10∉{1,7,20} v Tập rỗng, ký hiệu {} Nguyễn Thị Minh Tuyền 4 Đặc tả hình thức
5. Định nghĩa tập hợp[1] v Định nghĩa tập hợp bằng cách liệt kê § PrimaryColors == {red, yellow, blue} § Boolean == {true, false} § Evens == { , -4, -2, 0, 2, 4, } Nguyễn Thị Minh Tuyền 5 Đặc tả hình thức
6. Định nghĩa tập hợp[2] v Định nghĩa tập hợp bằng cách mô tả thuộc tính mà các phần tử của nó phải có. v Ký hiệu: § { x : S | P(x) } § Hình thành một tập các phần tử từ một tập hợp/miền S trong đó các phần tử phải thỏa mãn vị từ (predicate) P. v Ví dụ: § {x : N | x < 10} Các số nguyên nhỏ hơn 10 § {x : Z | (∃y : Z | x = 2y)} Tập các số nguyên chẵn § {x : N | false} Tập rỗng các số tự nhiên Nguyễn Thị Minh Tuyền 6 Đặc tả hình thức Các số chẵn Tập rỗng các số nguyên
7. Cardinality v Cardinality (#) của một tập hữu hạn là số phần tử của tập đó. v Ví dụ: § # {red, yellow, blue} = 3 § # {1, 23} = 2 § # Z = ? v Cardinality cũng có thể được dùng để định nghĩa các tập vô hạn nhưng ở đây chúng ta chỉ xem xét cardinality cho các tập hữu hạn. Nguyễn Thị Minh Tuyền 7 Đặc tả hình thức
8. Các phép toán trên tập hợp v Hợp (Union): X !Y ! {e | e " X or e " Y } {red} ! {blue} = {red, blue} v Giao (Intersection) X !Y " {e | e # X and e # Y } {red, blue}!{blue, yellow} = {blue} v Hiệu(Difference) X \ Y ! {e | e " X and e # Y } {red, yellow, blue} \ {blue, yellow} = {red} Nguyễn Thị Minh Tuyền 8 Đặc tả hình thức
9. Bài tập v Chứng minh rằng § #(A∩B) + #(A∪B) = #(A) + #(B) Nguyễn Thị Minh Tuyền 9 Đặc tả hình thức
10. Tập con (subset) v Tập con là tập hợp chứa các phần tử của một tập hợp khác § X ⊆ Y iff {e | e∈X⇒ e∈Y} v Ví dụ: {1, 7, 9,12, 25} ! Z {1,3, 7} ! {1, 2,3, 5, 7} v Một tập con nghiêm ngặt S của một tập hợp A được định nghĩa bằng § S ⊂ A v So sánh hai tập hợp § A = B iff {A⊆B ⋀ B⊆A} Nguyễn Thị Minh Tuyền 10 Đặc tả hình thức
11. Tập lũy thừa (Power Set) v Tập lỹ thừa của một tập hợp S (viết là Pow(S)) là tập hợp các tập con của S. Pow(S) ! {e | e " S} v Ví dụ: Pow({a, b,c}) = {!,{a},{b},{c}, {a, b},{a,c},{b,c} {abc}} v Chú ý: với mọi tập S, ∅ ⊆S § vì vậy, ∅ ⊆Pow(S) Nguyễn Thị Minh Tuyền 11 Đặc tả hình thức
12. Bài tập v Biểu diễn các tập con sau bằng cách mô tả thuộc tính của nó § Tập các số lẻ § Tập các số lẻ > 0 § Tập bình phương của các số nguyên.Ví dụ {1,4,9, } v Biểu diễn các thuộc tính trên tập hợp mà không sử dụng toán tử # § Tập có ít nhất 1 phần tử § Tập rỗng § Tập có chính xác 1 phần tử § Tập có ít nhất 2 phần tử § Tập có chính xác hai phần tử Nguyễn Thị Minh Tuyền 12 Đặc tả hình thức
13. Phân hoạch tập hợp (Set Partitioning) v Các tập hợp không giao nhau nếu chúng không có chung phần tử nào. v Khi mô hình hóa, chúng ta sẽ lấy một tập S nào đó và chia những phần tử của nó thành những tập con không giao nhau thì gọi là phân hoạch tập hợp. v Mỗi phần tử của S thuộc về duy nhất một tập hợp. Soup Chips & Salsa Steak Pizza Sweet & Sour Pork Cake Apple pie Ice Cream Nguyễn Thị Minh Tuyền 13 Đặc tả hình thức
14. Ví dụ v Tập hợp ban đầu: Person, Residence § Phân chia Person thành Child, Student, Adult Child Adult Person Student § Phân chia Residence thành Home, DormRoom, Apartment Residence Home DormRoom Appart Nguyễn Thị Minh Tuyền 14 Đặc tả hình thức
15. Bài tập v Biểu diễn các thuộc tính sau của cặp các tập hợp § Hai tập hợp không giao nhau § Hai tập hợp được hình thành bằng cách phân hoạch một tập thứ ba. Nguyễn Thị Minh Tuyền 15 Đặc tả hình thức
16. Biểu diễn quan hệ (relationship) v Hữu ích khi chỉ đến các giá trị có cấu trúc § Một nhóm các giá trị được hạn chế/giới hạn cùng nhau § Ví dụ: struct, record, object fields v Alloy là một ngôn ngữ tính tính toán dựa vào các quan hệ. v Tất cả các mô hình của Alloy sẽ được xây dựng dựa vào quan hệ. Nguyễn Thị Minh Tuyền 16 Đặc tả hình thức
17. Product v Cho sẵn hai tập A và B, product của A và B, thường ký hiệu là A x B, là tập tất cả các cặp có thể (a,b) sao cho A ! B " {(a, b) | a # A and b # B } v Ví dụ: § PrimaryColor: {red, green, blue} § Boolean: {true, false} § PrimaryColor x Boolean: ! % (red,true), (red, false), # # " (blue,true), (blue, false), & # (green,true), (green, false) # $# '# Nguyễn Thị Minh Tuyền 17 Đặc tả hình thức
18. Quan hệ - Ví dụ v Khái niệm về quan hệ khá thông dụng trong đời sống hằng ngày. v Ví dụ: § X là tập các phụ nữ, Y là tập các nam giới § Quan hệ vợ-chồng R có thể được xem như là một quan hệ của X và Y. § Đối với một quý bà: x ! X § Đối với một quý ông: y ! Y § x liên quan tới y bởi R nếu x là vợ của y. § Để định nghĩa quan hệ R: liệt kê tập hợp tất cả các cặp có thứ tự(x,y) sao cho x liên quan tới y bởi R. Tập hợp các cặp có thứ tự như vậy là một tập con của X x Y. Nguyễn Thị Minh Tuyền 18 Đặc tả hình thức
19. Quan hệ nhị phân (Binary relations) v Cho hai tập không rỗng A và B. Một quan hệ nhị phân R từ A đến B là một tập con R ! A " B v Hay nói cách khác, R là một phần tử của Pow(A x B), Nguyễn Thị Minh Tuyền 19 Đặc tả hình thức
20. Quan hệ bậc n v Một quan hệ bậc ba (ternary relation) R giữa A, B và C là một phần tử của Pow(A x B x C). v Ví dụ: § FavoriteBeer : Person x Beer x Price § FavoriteBeer == {(John, Miller, $2), (Ted,Heineken, $4), (Steve, Miller, $2)} v Quan hệ bậc N (N-ary relations) với n>3 được định nghĩa tương tự (n là bậc của quan hệ). Nguyễn Thị Minh Tuyền 20 Đặc tả hình thức
21. Quan hệ nhị phân - Ví dụ 1 § Một gia đình A có 5 người con: Amy, Bob, Charlie, Debbie, and Eric. § A = (a, b, c, d, e). § Quan hệ brother - sister Rbs: Rbs={(b, a), (b, d), (c, a), (c, d), (e, a), (e, d)} § Quan hệ sister-brother Rsb: Rsb = {(a, b), (a, c), (a, e), (d, b), (d, c), (d, e)} § Quan hệ brother Rb: Rb={(b, b), (b, c), (b, e), (c, b), (c, c), (c, e), (e, b), (e, c), (e, e)} § Quan hệ sister Rs: Rs={ (a, a), (a, d), (d, a), (d, d)} Nguyễn Thị Minh Tuyền 21 Đặc tả hình thức
22. Quan hệ nhị phân - Ví dụ 2 v Đồ thị của phương trình x2 y2 + =1 9 4 Là một quan hệ nhị phân trên R. Đồ thị là một hình ellipse. v Quan hệ nhỏ hơn (a<b) Là một quan hệ nhị phân trên R. Vì nó là một tập con của R2=RxR, quan hệ là tập {(a,b) ! R2 | a is less than b}. Nguyễn Thị Minh Tuyền 22 Đặc tả hình thức
23. Quan hệ nhị phân - Ví dụ 3 v Một hàm f : X -> Y v Được xem là một quan hệ nhị phân từ X đến Y. Quan hệ nhị phân là đồ thị của nó. G( f ) := {(x, f (x)) | x ! X} " X #Y Nguyễn Thị Minh Tuyền 23 Đặc tả hình thức
24. Quan hệ nhị phân v Miền định nghĩa (definition domain) của quan hệ § Tập những phần tử đầu tiên v Ví dụ: § Rbs={(b, a), (b, d), (c, a), (c, d), (e, a), (e, d)} § domain(Rbs) = {b, c, e} v Ảnh (image) của quan hệ § Tập những phần tử cuối cùng. v Ví dụ: § image (Rbs) = {a, d} § Với {(1,blue), (2,blue), (1,red)}: miền? ảnh? Nguyễn Thị Minh Tuyền 24 Đặc tả hình thức
25. Cấu trúc những quan hệ thường gặp One-to-Many Many-to-One Many One Many One One-to-One Many-to-Many Many Many One One Nguyễn Thị Minh Tuyền 25 Đặc tả hình thức
26. Hàm (Functions) v Hàm là một quan hệ F bậc n+1 không chứa hai chuỗi khác nhau với cùng n phần tử đầu tiên, nghĩa là với n = 1 !(a1, b1) " F,!(a2, b2 ) " F,(a1 = a2 # b1 = b2 ) v Ví dụ: § {(2, red), (3, blue), (5, red)} § {(4, 2), (6,3), (8, 4)} v Thay vì F: A1 x A2 x x An x B, chúng ta viết F: A1 x A2 x An -> B Nguyễn Thị Minh Tuyền 26 Đặc tả hình thức
27. Bài tập v Tập nào sau đây là hàm? § Parent == {(John, Autumn), (John, Sam)} § Square = {(1, 1), (-1, 1), (-2, 4)} § ClassGrades = {(Todd, A), (Virg, B)} Nguyễn Thị Minh Tuyền 27 Đặc tả hình thức
28. Quan hệ vs. Hàm John Parent Autumn Many-to-Many Lorie Sam 1 Square 4 -2 Many-to-One -1 1 Todd ClassGrades A One-to-One Virg B Một hàm là một quan hệ X-to-one Nguyễn Thị Minh Tuyền 28 Đặc tả hình thức
29. Những loại hàm đặc biệt v Xét một hàm f từ S đến T § f là toàn phần (total) nếu nó được định nghĩa cho tất cả các giá trị của S. Total Function Nguyễn Thị Minh Tuyền 29 Đặc tả hình thức
30. Những loại hàm đặc biệt v Xét một hàm f từ S đến T § f là bộ phận (partial) nếu nó được định nghĩa cho một số giá trị của S. Partial Function Giá trị đầu vào này không được định nghĩa Chú ý: Hàm rỗng là một hàm bộ phận Nguyễn Thị Minh Tuyền 30 Đặc tả hình thức
31. v Ví dụ: § Squares : Z -> N, Squares = {(-1,1), (2,4)} Abs = {(x, y) : Z ! N | ( x < 0 and y = !x ) or ( x " 0 and y = x ) Nguyễn Thị Minh Tuyền 31 Đặc tả hình thức
32. Các loại hàm đặc biệt v Một hàm f: S -> T là § one-to-one (injective) nếu không có phần tử ảnh nào được nối với nhiều phần tử miền. § onto (surjective) nếu ảnh của nó là T. § Bijective nếu nó vừa là injective và surjective. Nguyễn Thị Minh Tuyền 32 Đặc tả hình thức
33. Các cấu trúc hàm Injective Function Surjective Function Nguyễn Thị Minh Tuyền 33 Đặc tả hình thức
34. onto Bijective Injective and non-surjective Non-injective and non-surjective (injection, or one-to-one) Nguyễn Thị Minh Tuyền 34 Đặc tả hình thức
35. Bài tập v Xác định loại hàm/quan hệ sau: Abs = {(x, y) : Z ! N | (x < 0 and y=-x) or (x " 0 and y=x)} Squares : Z ! N, Square = {(-1,1),(2,4)} Nguyễn Thị Minh Tuyền 35 Đặc tả hình thức
36. Các trường hợp đặc biệt Onto Total Functions One-to-One Partial Functions Relations Nguyễn Thị Minh Tuyền 36 Đặc tả hình thức
37. Sử dụng hàm như một tập hợp v Hàm là các quan hệ vì vậy nó là các tập hợp. v Có thể áp dụng cho tất cả các phép tính thường dùng. § ClassGrades == {(Todd,A), (Jane,B)} § #(ClassGrades U {(Matt,C)}) = 3 Nguyễn Thị Minh Tuyền 37 Đặc tả hình thức
38. Bài tập v Các phép toán nào sau đây không giữ được tính chất hàm, onto, one-to-one? Cho ví dụ § ⋂ ? § ⋃ ? § \ ? Nguyễn Thị Minh Tuyền 38 Đặc tả hình thức
39. Tổ hợp quan hệ (Relation composition) v Sử dụng hai quan hệ để tạo ra một quan hệ mới. § ánh xạ miền của quan hệ thứ nhất với ảnh của quan hệ thứ hai § Cho trước s: A x B và r: B x C, ta sẽ có s;r : A x C s;r ! {(a,c) | (a, b) " s and (b,c) " r} v Ví dụ: § s == {(red,1), (blue,2)} § r == {(1,2), (2,4), (3,6)} § s;r = {(red,2), (blue,4)} Nguyễn Thị Minh Tuyền 39 Đặc tả hình thức
40. Tập đóng của quan hệ(Relation Closure) v Tập đóng của một quan hệ r: S x S (được viết là r+) v là những gì có được khi tiếp tục điều hướng (navigating) qua r cho đến khi ta không thể đi xa hơn được nữa. r+ ! r "(r;r)"(r;r;r)" v Ví dụ: § GrandParent == Parent;Parent § Ancestor == Parent+ Nguyễn Thị Minh Tuyền 40 Đặc tả hình thức
41. Chuyển vị quan hệ (Relation Transpose) v Dễ thấy, chuyển vị của một quan hệ: § r: S x T (được viết là ~r) § Là những gì có được khi đảo ngược thứ tự của tất cả các cặp trong r. ~ r ! {(b, a) | (a, b) " r} v Ví dụ: § ChildOf == ~Parent § DescendantOf == (~Parent)+ Nguyễn Thị Minh Tuyền 41 Đặc tả hình thức
42. Bài tập v Phép toán quan hệ nào sau đây không giữ được tính chất hàm, onto, one-to-one? Cho ví dụ. § quan hệ cộng gộp § quan hệ đóng § chuyển vị quan hệ Nguyễn Thị Minh Tuyền 42 Đặc tả hình thức