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 tượng

v Ví dụ:

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.

§  {2,4,5,6,…} §  {red, yellow, blue} §  {true, false} §  {red, true, 2}

không phải tập hợp.

2 Nguyễn Thị Minh Tuyền Đặ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ụ:

Các số nguyên nhỏ hơn 10

§  {x : N | x < 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):

e " Y }

X ! Y ! {e | e " X or {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}

8 Nguyễn Thị Minh Tuyền Đặ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ụ:

{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}

10 Nguyễn Thị Minh Tuyền Đặ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)

11 Nguyễn Thị Minh Tuyền Đặ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.

Soup

Chips & Salsa

Steak Pizza

Sweet & Sour Pork

Cake Apple pie

Ice Cream

13 Nguyễn Thị Minh Tuyền Đặ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

14 Nguyễn Thị Minh Tuyền Đặ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

A ! B " {(a, b) | a # A and b # B }

v Ví dụ:

§  PrimaryColor: {red, green, blue} §  Boolean: {true, false} §  PrimaryColor x Boolean:

(red, false),

(blue, false),

(red, true), (blue, true), (green, true),

(green, false)

! ## " # # $

% ## & # # '

17 Nguyễn Thị Minh Tuyền Đặ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

x ! X y ! Y

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 Đặ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),

19 Nguyễn Thị Minh Tuyền Đặ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

+

= 1

x 2 9

y2 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

{(a,b) ! R2 | a is less than b}.

22 Nguyễn Thị Minh Tuyền Đặ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

23 Nguyễn Thị Minh Tuyền Đặ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

One-to-Many

Many-to-One

Many

One

Many

One

One-to-One

Many-to-Many

Many

Many

One

One

25 Nguyễn Thị Minh Tuyền Đặ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

26 Nguyễn Thị Minh Tuyền Đặ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

Parent

Many-to-Many

John Lorie

Autumn Sam

Square

Many-to-One

1 -2 -1

4 1

ClassGrades

One-to-One

Todd Virg

A B

Một hàm là một quan hệ X-to-one

28 Nguyễn Thị Minh Tuyền Đặ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

29 Nguyễn Thị Minh Tuyền Đặ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

30 Nguyễn Thị Minh Tuyền Đặ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 )

31 Nguyễn Thị Minh Tuyền Đặ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

Injective Function

Surjective Function

33 Nguyễn Thị Minh Tuyền Đặc tả hình thức

onto

Bijective

Non-injective and non-surjective

Injective and non-surjective (injection, or one-to-one)

34 Nguyễn Thị Minh Tuyền Đặ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)}

35 Nguyễn Thị Minh Tuyền Đặc tả hình thức

Các trường hợp đặc biệt

Onto

Total Functions

One-to-One

Partial Functions

Relations

36 Nguyễn Thị Minh Tuyền Đặ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

U

thường dùng. §  ClassGrades == {(Todd,A), (Jane,B)} §  #(ClassGrades {(Matt,C)}) = 3

37 Nguyễn Thị Minh Tuyền Đặ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

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)}

39 Nguyễn Thị Minh Tuyền Đặ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+

40 Nguyễn Thị Minh Tuyền Đặ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)+

41 Nguyễn Thị Minh Tuyền Đặ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 Đặc tả hình thức

LOGO