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

LOGO Đặc tả hình thức Nguyễn Thị Minh Tuyền Tập hợp và quan hệ Nguyễn Thị Minh Tuyền 1 Đặc tả hình thức 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. v Ví dụ: §  {2,4,5,6,} §  {red, yellow, blue} §  {true, false} §  {red, true, 2} 2 Nguyễn Thị Minh Tuyền Miền đối tượng tập hợp các số nguyên. tập hợp các màu. tập hợp các giá trị boolean. không phải tập hợp. Đặ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 3 Nguyễn Thị Minh Tuyền Đặ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 {} 4 Nguyễn Thị Minh Tuyền Đặ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, } 5 Nguyễn Thị Minh Tuyền Đặ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 Các số chẵn Tập rỗng các số nguyên 6 Nguyễn Thị Minh Tuyền Đặc tả hình thức 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. 7 Nguyễn Thị Minh Tuyền Đặc tả hình thức Các phép toán trên tập hợp v Hợp (Union): v Giao (Intersection) v Hiệu(Difference) 8 Nguyễn Thị Minh Tuyền X !Y ! {e | e" X or e" Y } {red}!{blue} = {red,blue} X!Y " {e | e# X and e# Y } {red,blue}!{blue, yellow} = {blue} X \ Y ! {e | e" X and e# Y } {red, yellow,blue} \ {blue, yellow} = {red} Đặc tả hình thức Bài tập v Chứng minh rằng §  #(A∩B) + #(A∪B) = #(A) + #(B) 9 Nguyễn Thị Minh Tuyền Đặ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ụ: 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} 10 Nguyễn Thị Minh Tuyền {1, 7, 9,12, 25}! Z {1,3, 7}! {1,2,3, 5, 7} Đặ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. v Ví dụ: v Chú ý: với mọi tập S, ∅ ⊆S §  vì vậy, ∅ ⊆Pow(S) 11 Nguyễn Thị Minh Tuyền Pow(S) ! {e | e" S} Pow({a,b,c}) = {!,{a},{b},{c}, {a,b},{a,c},{b,c} {abc}} Đặ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ử 12 Nguyễn Thị Minh Tuyền Đặ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. 13 Nguyễn Thị Minh Tuyền Soup Chips & Salsa Steak Pizza Sweet & Sour Pork Cake Apple pie Ice Cream Đặ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 §  Phân chia Residence thành Home, DormRoom, Apartment 14 Nguyễn Thị Minh Tuyền Child Student Person Adult DormRoom Residence Home Appart Đặ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. 15 Nguyễn Thị Minh Tuyền Đặ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ệ. 16 Nguyễn Thị Minh Tuyền Đặ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 v Ví dụ: §  PrimaryColor: {red, green, blue} §  Boolean: {true, false} §  PrimaryColor x Boolean: 17 Nguyễn Thị Minh Tuyền A!B " {(a,b) | a # A and b# B} (red, true), (blue, true), (green, true), (red, false), (blue, false), (green, false) ! " ## $ # # % & ## ' # # Đặ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à: §  Đối với một quý ông: §  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. 18 Nguyễn Thị Minh Tuyền x ! X y ! Y Đặ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 v Hay nói cách khác, R là một phần tử của Pow(A x B), 19 Nguyễn Thị Minh Tuyền R ! A"B Đặ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ệ). 20 Nguyễn Thị Minh Tuyền Đặ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)} 21 Nguyễn Thị Minh Tuyền Đặc tả hình thức Quan hệ nhị phân - Ví dụ 2 v Đồ thị của phương trình 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 22 Nguyễn Thị Minh Tuyền x2 9 + y2 4 =1 {(a,b)! R2 | a is less than b}. Đặ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ó. 23 Nguyễn Thị Minh Tuyền G( f ) := {(x, f (x)) | x ! X}" X #Y Đặ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? 24 Nguyễn Thị Minh Tuyền Đặc tả hình thức Cấu trúc những quan hệ thường gặp 25 Nguyễn Thị Minh Tuyền One Many One-to-Many One One One-to-One Many One Many-to-One Many Many Many-to-Many Đặ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 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 26 Nguyễn Thị Minh Tuyền !(a1,b1)" F,!(a2,b2 )" F, (a1 = a2 # b1 = b2 ) Đặ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)} 27 Nguyễn Thị Minh Tuyền Đặc tả hình thức Quan hệ vs. Hàm 28 Nguyễn Thị Minh Tuyền John Lorie Autumn Sam Parent Many-to-Many 1 -2 -1 4 1 Square Many-to-One Todd Virg A B ClassGrades One-to-One Một hàm là một quan hệ X-to-one Đặ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. 29 Nguyễn Thị Minh Tuyền Total Function Đặ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. 30 Nguyễn Thị Minh Tuyền Giá trị đầu vào này không được định nghĩa Partial Function Chú ý: Hàm rỗng là một hàm bộ phận Đặc tả hình thức v Ví dụ: §  Squares : Z -> N, Squares = {(-1,1), (2,4)} 31 Nguyễn Thị Minh Tuyền Abs = {(x, y) : Z !N | ( x < 0 and y = !x ) or ( x " 0 and y = x ) Đặ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. 32 Nguyễn Thị Minh Tuyền Đặc tả hình thức Các cấu trúc hàm 33 Nguyễn Thị Minh Tuyền Injective Function Surjective Function Đặc tả hình thức 34 Nguyễn Thị Minh Tuyền Bijective onto Non-injective and non-surjective Injective and non-surjective (injection, or one-to-one) Đặc tả hình thức Bài tập v Xác định loại hàm/quan hệ sau: 35 Nguyễn Thị Minh Tuyền Abs = {(x, y) : Z !N | (x < 0 and y=-x) or (x " 0 and y=x)} Squares : Z !N, Square = {(-1,1),(2,4)} Đặc tả hình thức Các trường hợp đặc biệt 36 Nguyễn Thị Minh Tuyền Onto Total Functions One-to-One Partial Functions Relations Đặ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 {(Matt,C)}) = 3 37 Nguyễn Thị Minh Tuyền U Đặ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ụ §  ⋂ ? §  ⋃ ? §  \ ? 38 Nguyễn Thị Minh Tuyền Đặ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 v Ví dụ: §  s == {(red,1), (blue,2)} §  r == {(1,2), (2,4), (3,6)} §  s;r = {(red,2), (blue,4)} 39 Nguyễn Thị Minh Tuyền s;r ! {(a,c) | (a,b)" s and (b,c)" r} Đặ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. v Ví dụ: §  GrandParent == Parent;Parent §  Ancestor == Parent+ 40 Nguyễn Thị Minh Tuyền r+ ! r" (r;r)" (r;r;r)"... Đặ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. v Ví dụ: §  ChildOf == ~Parent §  DescendantOf == (~Parent)+ 41 Nguyễn Thị Minh Tuyền ~ r ! {(b,a) | (a,b)" r} Đặ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ệ 42 Nguyễn Thị Minh Tuyền LOGO