Bài giảng Đặc tả hình thức - Bài 2: Tập hợp và quan hệ - Nguyễn Thị Minh Tuyền
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đặc tả hình thức - Bài 2: Tập hợp và quan hệ - Nguyễn Thị Minh Tuyền", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_giang_dac_ta_hinh_thuc_bai_2_tap_hop_va_quan_he_nguyen_t.pdf
Nội dung text: Bài giảng Đặc tả hình thức - Bài 2: Tập hợp và quan hệ - Nguyễn Thị Minh Tuyền
- 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
- 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
- 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
- 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
- Đị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
- Đị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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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