Bài giảng Toán rời rạc - Chương 1: Tập hợp, Quan hệ (Set, Relation)

Nội dung

Chương 1

1.1. Tập hợp (Set)

1.2. Phép toán tập hợp (Set operations)

1.3. Đại số tập hợp (Set Algerbra)

Tập hợp, Quan hệ

1.4. Biểu diễn tập hợp trên máy tính (Computer Representation)

1.5. Quan hệ (Relation)

(Set, Relation)

1.6. Ánh xạ (Mapping)

1.7. Quan hệ tương đương và Quan hệ thứ tự

1.8. Lực lượng của tập hợp (Cardinality)

1.9. PP qui nạp toán học. Định nghĩa tập hợp theo qui nạp.

2

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.1.1 Tập hợp và phần tử

1.1. Tập hợp (Set)

(Set and Element)

• Tập hợp là một khái niệm cơ bản của toán học không được

định nghĩa.

• Ta hiểu tập hợp là một họ xác định các đối tượng nào đó. Các

đối tượng cấu thành tập hợp được gọi là các phần tử của tập

hợp. Các phần tử trong tập hợp là khác nhau.

• 1.1.1 Tập hợp và phần tử (Set and Element)

• 1.1.2 Các cách xác định tập hợp (Set Definition)

• 1.1.3 Nghịch lý Russell (Russell Paradox)

• Ví dụ:

– Tập các số tự nhiên N.

– Tập tất cả các số nguyên tố

– Tập các số nguyên Z, tập các số nguyên không âm Z⁺.

– Tập các số thực R, tập các số thực không âm R⁺.

– Tập các học sinh của một lớp, Tập các phòng học của trường ĐHBK

– ...

3

4

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.1.1 Tập hợp và phần tử

• Nếu x là phần tử của tập S thì ta nói x là thuộc vào S và ký

hiệu: x Î S.

• Trái lại, ta nói x không thuộc vào S và ký hiệu x Ï S.

• Ta thường sử dụng các chữ cái latin in hoa A, B, C, ... để ký

hiệu tập hợp và các chữ cái latin in thường a, b, c, ... để ký

hiệu phần tử của tập hợp.

• Các tập hợp như là các đối tượng lại có thể là phần tử

của các hợp khác. Tập hợp mà các phần tử có thể là

các tập hợp thường được gọi là họ hay lớp. Người ta

thường sử dụng các chữ cái latin viết tay hoa: A, B,

C,...để ký hiệu lớp hay họ.

• Tập hợp không chứa phần tử nào cả được gọi là tập

rỗng (trống). Tập rỗng được ký hiệu là Æ.

• Chú ý: Thoạt nhìn khái niệm tập hợp có vẻ là trực quan rõ

ràng. Nhưng thực ra vấn đề không đơn giản. Chẳng hạn, việc

xác nhận một đối tượng có phải là phần tử của một tập hợp

không đơn giản một chút nào.

• Trong những nghiên cứu cụ thể, các phần tử của các

tập hợp được quan tâm đều được lấy từ một tập rộng

lớn hơn U được gọi là tập vũ trụ.

– Chẳng hạn, 86969696969696969696969696967111 là số nguyên tố?

5

6

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.1.2 Các cách xác định tập hợp

(Set Definition)

1.1.2 Các cách xác định tập hợp

• Để xác định một tập hợp cần chỉ ra các phần tử nào thuộc vào

nó. Để làm điều đó có một số cách cơ bản sau đây:

3. Thủ tục sinh: Chỉ ra thủ tục sinh các phần tử của tập hợp

– Ví dụ: M₉= {n| for n:=1 to 9 do <Đưa ra n> }

1. Liệt kê (set extension): Liệt kê các phần tử của tập hợp trong

dấu ngoặc nhọn {}.

• Bằng liệt kê chỉ có thể xác định các tập hợp hữu hạn. Các tập

vô hạn được xác định bởi vị từ đặc trưng hoặc thủ tục sinh

– Ví dụ:

– Ví dụ: M₉= {1, 2, ...,8, 9}, G = {Mai, Mơ, Mận, Me, Muỗm}.

2. Vị từ đặc trưng (set intension): Đưa ra điều kiện mà hễ một

đối tượng thoả mãn nó sẽ là phần tử của tập hợp.

N = {n | n:=1; while n < n+1 do <Đưa ra n > },

R⁺= {x| x là số thực không âm}.

– Ví dụ: M₉={n | (nÎN)Ù(n < 10)}, N_even={n| n - số nguyên dương

chẵn}, Q = { p / q | pÎZ, qÎZ, q ¹ 0 } – tập các số hữu tỷ.

– Tổng quát: M = { x| P(x)}, trong đó P(x) là vị từ.

7

8

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.1.3 Nghịch lý Russell (Russell’s Paradox)

1.1.3 Nghịch lý Russell

• Cách xác định tập hợp bởi vị từ đặc trưng có thể dẫn đến mâu

thuẫn. Tất cả các tập xét trong các ví dụ đã nêu không có tập

nào chứa chính nó như là phần tử. Bây giờ ta xét tập tất cả các

tập không chứa chính nó như là phần tử:

• Có nhiều biện pháp để thoát khỏi nghịch lý Russell. Chẳng

hạn:

1. Hạn chế sử dụng vị từ đặc trưng dưới dạng

P(x) = x Î A thoả mãn Q(x)

Y = {X | X Ï X}

trong đó A là tập vũ trụ cho trước. Trong trường hợp này tập

hợp được ký hiệu là {x Î A | Q(x)}. Đối với tập Y, ta không chỉ

ra tập vũ trụ, vì vậy Y không là tập hợp.

• Nếu tập Y như vậy là tồn tại, thì ta phải trả lời được câu hỏi:

Y Î Y ?

– Giả sử Y Î Y, khi đó theo định nghĩa Y Ï Y ?!

– Giả sử Y Ï Y, khi đó theo định nghĩa Y Î Y ?!

2. Vị từ đặc trưng P(x) được cho dưới dạng hàm tính được

(thuật toán). Phương pháp tính giá trị của vị từ X Î X không

được xác định, vì thế Y không là tập hợp.

• Mâu thuẫn thu được được biết

dưới tên gọi nghịch lý Russell.

• Cách tiếp cận thứ hai là cơ sở để xây dựng toán kiến thiết.

Bertrand Russell

1872-1970

9

10

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.2 Các phép toán tập hợp

Nội dung

(Set Operations)

• 1.2.1 So sánh các tập hợp (Set Comparision)

• 1.2.2 Các phép toán tập hợp (Set Operations)

• 1.2.3 Phân hoạch và phủ (Set Partition and Cover)

1.1. Tập hợp

1.2. Các phép toán tập hợp

1.3. Đại số tập hợp

1.4. Biểu diễn tập hợp trên máy tính

1.5. Quan hệ

1.6. Ánh xạ

1.7. Quan hệ tương đương và Quan hệ thứ tự

1.8. Lực lượng của tập hợp.

1.9. PP qui nạp toán học. Định nghĩa tập hợp theo qui nạp.

11

12

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

So sánh các tập hợp

• Tập A được gọi là tập con của tập B, ký hiệu là A Ì B, nếu mỗi

phần tử của A đều là phần tử của B:

• 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 và ngược lại:

A Ì B Û x Î A Þ x Î B.

• Nếu A là tập con của B thì ta cũng nói là A chứa trong B hoặc

B chứa A.

A = B Û A Ì B và B Ì A.

• Lực lượng của tập A được ký hiệu là |A|. Đối với tập

hữu hạn lực lượng chính là số phần tử của nó.

Ví dụ: |Æ| = 0, nhưng |{Æ}| = 1.

• Nếu A Ì B và A ¹ B thì ta nói A là tập con thực sự của B.

• Ta có: "M: M Ì M và theo định nghĩa Æ Ì M.

• Nếu |A| = |B| thì hai tập A và B được nói là có cùng

lực lượng.

• Chú ý: Trong nhiều tài liệu để phân biệt tập con và tập con

thực sự người ta sử dụng ký hiệu tương ứng là Í và Ì.

13

14

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Các phép toán đối với tập hợp

• Giả sử A và B là hai tập hợp. Có nhiều cách liên kết A và B để

thu được tập mới – mà ta sẽ gọi là các phép toán đối với tập

hợp. Dưới đây là một số phép toán tập hợp thường dùng

• Hiệu đối xứng (Symetric Difference):

A Å B = (AÈB) \ (AÇB)

= {x| (xÎA Ù xÏB) Ú (xÎB Ù xÏA) } .

• Ví dụ: A={1, 2, 3}, B = {3, 4, 5}. Khi đó

AÈB = {1, 2, 3, 4, 5}, AÇB = {3},

• Hợp (Union)

AÈB = {x| x Î A Ú x Î B}

• Giao (Intersection):

A \ B = {1, 2},

AÅB = {1, 2, 4, 5}.

AÇB = {x| x Î A Ù x Î B} .

• Hiệu (Difference):

• Để biểu diễn tập hợp người ta thường dùng

sơ đồ Venn (Venn diagram):

– Các tập được biểu diễn bởi các vòng tròn

– Các phần tử - các điểm trong vòng tròn

– Tập vũ trụ - hình chữ nhật

A \ B = {x| x Î A Ù x Ï B} . (Có chỗ ký hiệu là A- B)

• Phần bù (complement) của A đối với tập vũ trụ X:

`A = {x| x Ï A} = X \ A. (Có chỗ ký hiệu là A^c)

John Venn

1834-1923

15

16

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Sơ đồ Venn (Venn Diagram)

Phân hoạch và Phủ (Partition and Cover)

• Giả sử E = {E_i}_{i ÎI}là họ các tập con của tập M, E_iÌM. Họ E

được gọi là phủ của tập M nếu như mỗi phần tử của M đều là

phần tử của ít nhất một tập nào đó trong số các tập E_i:

A

B

A

B

M Ì E_iÛ

"

xÎ

M

$iÎI xÎE_i.

A \ B

AÇB

AÈB

iÎI

• Họ E được gọi là họ rời nhau nếu như các tập con trong nó đôi

một là không giao nhau:

B

A

" i, jÎI i¹j Þ E_iÇE_j= Æ.

U

• Nếu E là phủ rời nhau của tập M, thì nó được gọi là một phân

hoạch của M, nghĩa là

AÅB

`A

E là phân hoạch của M Û M Ì È_iÎI^E_i^{, E}_i^ÇE_j^{= Æ, i¹j.}

17

18

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Phân hoạch và Phủ (Partition and Cover)

Nội dung

• Ví dụ: M = {1, 2, 3, 4}. Khi đó:

1.1. Tập hợp

- Họ E₁= {{1, 2}, {1, 3}, {2, 4}} là một phủ của M;

- Họ E₂= {{1, 2}, {3,4}} là một phân hoạch của M;

1.2. Phép toán tập hợp

1.3. Đại số tập hợp

1.4. Biểu diễn tập hợp trên máy tính

1.5. Quan hệ

- Họ E₃= {{1, 2}, {3}} là một họ rời nhau nhưng không là

phủ và cũng không là phân hoạch của M.

1.6. Ánh xạ

1.7. Quan hệ tương đương và Quan hệ thứ tự

1.8. Lực lượng của tập hợp.

1.9. Định nghĩa tập hợp theo qui nạp. PP qui nạp toán học

19

20

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.3. Đại số tập hợp (Set Algerbra)

1.3.1 Dàn Bun (Power Set)

Các phép toán tập hợp có hàng loạt tính chất quan trọng mà ta

sẽ xét trong mục này

• Tập tất cả các tập con của tập M được gọi là dàn Bun (tập lực

lượng) và được ký hiệu là 2^M(đôi khi còn ký hiệu là P(M)).

• Ví dụ: M = {0, 1}, P(M)={Æ, {0}, {1}, {0,1}}.

• Định lý. Nếu M là tập hữu hạn thì |2^M| = 2^|M|.

• Chứng minh. Qui nạp theo |M|.

1.3.1. Dàn Bun (Power Set)

1.3.2. Các tính chất của phép toán tập hợp (Properties of Set

Operations)

• Hợp, giao, hiệu của hai tập con trong tập vũ trụ U luôn là tập

con của U. Tập tất cả các tập con của tập U cùng với các phép

toán hợp, giao, hiệu và phần bù tạo thành một đại số tập hợp

của tập U.

21

22

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.3.2. Các tính chất của

các phép toán tập hợp

Các tính chất của

các phép toán tập hợp

• Giả sử U là tập vũ trụ. Khi đó với mọi tập con A, B, C của U ta

Ò୥QJꢀWK஛F

7¬QꢀJ୿L

Giao hoán

có các đẳng thức sau đây được thực hiện:

A È B = B È A

A Ç B = B Ç A

Ò୥QJꢀWK஛F

A È Æ = A

A Ç U = A

A È U = U

A Ç Æ = Æ

A È A = A

A Ç A = A

7¬QꢀJ୿L

Đồng nhất

(Identity laws)

Commutative laws

A È (B È C) = (A È B) È C

A Ç (B Ç C) = (A Ç B) Ç C

Kết hợp

Associative laws

Trội

A Ç (B È C) = (A Ç B) È (A Ç C)

A È (B Ç C) = (A È B) Ç (A È C)

Phân phối

(Domination laws)

Distributive laws

Đồng nhất

Luật De Morgan

AÈ B = A Ç B

AÇ B = A È B

Idempotent laws

De Morgan’s laws

Bù

(A) = A

(Complementation laws)

23

24

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Các đẳng thức tập hợp

Ví dụ 1.

• Có thể chứng minh các đẳng thức tập hợp ở trên nói

riêng và các đẳng thức tập hợp nói chung bằng nhiều

cách:

CM đẳng thức: AÇ(BÈC)=(AÇB)È(AÇC).

• Phần 1: CM AÇ(BÈC) Í (AÇB)È(AÇC).

– Giả sử xÎAÇ(BÈC), cần chỉ ra xÎ(AÇB)È(AÇC).

– Ta biết xÎA, và hoặc là xÎB hoặc là xÎC.

• TH 1: xÎB. Khi đó xÎAÇB, vì thế xÎ(AÇB)È(AÇC).

• TH 2: xÎC. Khi đó xÎAÇC , do đó xÎ(AÇB)È(AÇC).

– Suy ra, xÎ(AÇB)È(AÇC).

1. Vẽ sơ đồ Venn của hai vế

2. Chứng minh A Í B và B Í A.

3. Sử dụng định nghĩa và sự tương đương của các

mệnh đề logic xác định tập hợp.

– Vậy AÇ(BÈC) Í (AÇB)È(AÇC).

• Phần 2: CM (AÇB)È(AÇC) Í AÇ(BÈC). (tương tự)

4. Sử dụng bảng quan hệ thành viên.

25

26

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Ví dụ 2

Bảng quan hệ thành viên

• Chứng minh rằng

• Tương tự như bảng giá trị chân lý trong logic được sử

dụng để chứng minh các đẳng thức logic, ta xây dựng

bảng quan hệ thành viên:

AÇ B = AÈ B

• CM:

– Các cột ứng với các biểu thức tập hợp.

– Các dòng ứng với mọi tổ hợp có thể về quan hệ thành viên

trong các tập đang xét.

A Ç B ={x | x Ï A Ç B}

= {x | Ø(x Î(AÇ B))}

theo ®Þnh nghÜa phÇn bï

®Þnh nghÜa Ï

= {x | Ø(x Î A Ù x Î B)} ®Þnh nghÜa giao

– Sử dụng “1” để ghi nhận là thành viên, “0” để chỉ ra không

= {x | x Ï A Ú x Ï B}

= {x | x Î A Ú x Î B}

= {x | x Î A È B}

luËt De Morgan

®Þnh nghÜa phÇn bï

®Þnh nghÜa hîp

là thành viên.

– Đẳng thức là được chứng minh nếu hai cột tương ứng với

hai biểu thức ở hai vế là giống hệt nhau.

đpcm

27

28

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Ví dụ 3

Nội dung

Chứng minh: (AÈB)-B = A-B.

1.1. Tập hợp

1.2. Phép toán tập hợp

1.3. Đại số tập hợp

A B

AÈB (AÈB)-B A-B

1.4. Biểu diễn tập hợp trên máy tính

1.5. Quan hệ

0 0 0

0 1 1

1 0 1

1 1 1

0

1

0

1

0

1.6. Ánh xạ

1.7. Quan hệ tương đương và Quan hệ thứ tự

1.8. Lực lượng của tập hợp.

1.9. PP qui nạp toán học. Định nghĩa tập hợp theo qui nạp.

29

30

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.4. Biểu diễn tập hợp trên máy tính

1.4.1. Vectơ đặc trưng

(Computer Representation)

• Giả sử tập vũ trụ U = {u₁, u₂, ..., u_n}, trong đó n không quá

lớn. Khi đó mỗi tập con MÌ U có thể biểu diễn bởi một vectơ

b = (b₁, b₂, ..., b_n), trong đó

• Mục này đề cập đến việc biểu diễn tập hợp trên máy tính. Có

nhiều phương pháp biểu diễn khác nhau có thể sử dụng. Việc

lựa chọn phương pháp cụ thể để biểu diễn cần xét dựa trên

nhiều yếu tố, chẳng hạn,

b_i= 1 « u_iÎ M, i =1, 2, ..., n.

Vectơ b xây dựng theo qui tắc vừa nêu được gọi là vectơ đặc

trưng của tập M.

– bộ nhớ mà cách biểu diễn đó đòi hỏi,

– thời gian để thực hiện các thao tác phải tiến hành đối với chúng, ...

• Dễ thấy: Mỗi tập con MÌ U tương ứng với duy nhất một vectơ

đặc trưng b, và ngược lại, mỗi vectơ nhị phân n-chiều b tương

ứng với duy nhất một tập con của U.

• Ví dụ. U = {1, 2, ..., 11}. Xét các tập con S, Q Í U.

– S = {2,3,5,7,11} « 01101010001.

1.4.1. Vectơ đặc trưng (Characteristic Vector)

1.4.2. Liệt kê các tập con của tập M (Subset Enumeration)

1.4.3. Danh sách phần tử (List of elements)

– Q = {1,2,4,11} « 11010000001.

31

32

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.4.1. Vectơ đặc trưng

1.4.2. Liệt kê các tập con

• Trong cách biểu diễn này các phép toán tập hợp È, Ç,` được

• Trong rất nhiều thuật toán duyệt đòi hỏi phải lần lượt xét tất cả

các tập con của một tập cho trước U = {u₁, u₂, ..., u_n}.

thực hiện nhờ phép toán logic OR, AND, NOT với từng bít!

• Ví dụ:

• Nếu biểu diễn các tập con của U bởi các vectơ đặc trưng, bài

toán đặt ra dẫn về liệt kê tất cả các vectơ nhị phân n-chiều. Do

mỗi vectơ nhị phân n-chiều b có thể coi là biểu diễn nhị phân

của một số nguyên không âm a(b) = b₁b₂...b_n, 0 £ a(b) £ 2ⁿ-1,

nên bài toán đặt ra qui về việc liệt kê biểu diễn nhị phân của tất

cả các số nguyên không âm từ 0 đến 2ⁿ-1.

SÈQ = ꢀꢁꢁꢀꢁꢀꢁꢀꢀꢀꢁ

Ú ꢁꢁꢀꢁꢀꢀꢀꢀꢀꢀꢁ

SÈQ « ꢁꢁꢁꢁꢁꢀꢁꢀꢀꢀꢁ

SÇQ = ꢀꢁꢁꢀꢁꢀꢁꢀꢀꢀꢁꢂ

Ù ꢁꢁꢀꢁꢀꢀꢀꢀꢀꢀꢁ

S ÇQ « ꢀꢁꢀꢀꢀꢀꢀꢀꢀꢀꢁ

S = ꢀꢁꢁꢀꢁꢀꢁꢀꢀꢀꢁ

Ø ꢀꢁꢁꢀꢁꢀꢁꢀꢀꢀꢁ

`S « 1ꢀꢀꢁꢀꢁꢀꢁꢁꢁꢀ

• Từ đó ta có thuật toán sau:

• Bước k = 0, 1, ..., 2ⁿ-1: Đưa ra biểu diễn nhị phân của k.

33

34

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.4.2. Liệt kê các tập con

• Dễ thấy là nếu ta đã có b₁b₂...b_nlà biểu diễn nhị phân của số

nguyên không âm k, thì biểu diễn nhị phân của số nguyên k+1

có thể thu được bằng cách cộng nhị phân b₁b₂...b_nvới 1.

• Từ đó thuật toán liệt kê các xâu nhị phân độ dài n có thể mô tả

chi tiết như sau:

• Algorithm BitStringEnum

for i=1 to n do b_i= 0; // Khởi tạo

for k=1 to 2ⁿdo

• Thuật toán sau đây thực hiện tăng nhị phân b₁b₂...b_nlên 1:

i=n;

Print(b₁, b₂, ..., b_n) // Đưa ra xâu đang có

Ví dụ:

while (i>=1) and (b_i=1)

i=n;

b_i=0;

while (i>=1) and (b_i=1)

ꢁꢀꢀꢁꢀꢁꢁꢁꢁꢁꢁꢁꢁꢁꢁ

i = i-1;

ꢁꢀꢀꢁꢁꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ

b_i=1;

b_i=0;

i = i-1;

b_i=1;

35

36

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.4.3. Danh sách phần tử

• Nếu như tập U gồm quá nhiều phần tử, trong khi đó các tập

con của U mà ta cần biểu diễn lại có lực lượng nhỏ, thì cách

biểu diễn tập con bởi vectơ đặc trưng là không thích hợp.

Trong trường hợp này ta thường biểu diễn tập hợp dưới bởi

danh sách các phần tử.

• Với cách biểu diễn này:

– Thời gian để kiểm tra một phần tử có thuộc tập M là O(|A|).

– Thời gian để thực hiện các phép toán Ì, È, Ç đối với hai

tập A, B là O(|A|.|B|).

• Danh sách này thông thường được mô tả dưới dạng danh sách

liên kết (linked list). Mỗi phần tử của danh sách là một bản ghi

gồm 2 trường ghi nhận: thông tin về phần tử và con trỏ đến

phần tử tiếp theo:

• Nếu sắp xếp các phần tử trong danh sách theo thứ tự tăng dần

thì có thể thực hiện tất cả các phép toán với thời gian O(m),

trong đó m = max(|A|, |B|).

• Các thuật toán thực hiện với thời gian tính như vậy đều được

phát triển dựa trên ý tưởng của thuật toán trộn (merge).

elem = record

i: info;

{ trường thông tin về phần tử }

next: ^elem {con trỏ đến phần tử tiếp theo }

end

37

38

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Nội dung

1.5. Quan hệ

1.5.1. Cặp có thứ tự (ordered pair)

1.5.2. Tích Đềcác của các tập hợp

1.5.3. Quan hệ

1.1. Tập hợp

1.2. Phép toán tập hợp

1.3. Đại số tập hợp

1.5.4. Quan hệ hợp thành (composite relation)

1.5.5. Nhân của quan hệ

1.4. Biểu diễn tập hợp trên máy tính

1.5. Quan hệ

1.5.6. Tính chất của quan hệ

1.5.7. Biểu diễn quan hệ

1.6. Ánh xạ

1.7. Quan hệ tương đương và Quan hệ thứ tự

1.8. Lực lượng của tập hợp.

1.9. PP qui nạp toán học. Định nghĩa tập hợp theo qui nạp.

39

40

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.5.1. Cặp có thứ tự

1.5.2. Tích Đềcác của các tập hợp

• Định nghĩa. Tích Đềcác (Cartesian Product).

• Nếu a và b là hai đối tượng thì cặp có thứ tự được ký hiệu là

(a, b), trong đó a được gọi là phần tử thứ nhất còn b là phần tử

thứ hai trong cặp này.

Giả sử A, B là các tập hợp. Tích Đềcác, hay tích trực tiếp của A và B được

ký hiệu bởi A ´ B là tập các bộ có thứ tự (a, b), trong đó a Î A, b Î B:

• Hai cặp có thứ tự (a, b) và (c, d) được gọi là bằng nhau khi và

chỉ khi a=c và b=d.

A ´ B º_def{(a, b)| a Î A, b Î B}.

• Nói chung (a, b) ¹ (b, a).

• Định nghĩa. Giả sử A₁, A₂, …, A_nlà các tập hợp, trong đó n

Î Z⁺và n ³ 3. Tích Đềcác của n tập A₁, A₂, …, A_nlà tập

• Chú ý: Cặp có thứ tự có thể định nghĩa trong ngôn ngữ tập

hợp: cặp (a, b) là tập {{a}, {a,b}} còn cặp (b,a) là tập {{b},

{a,b}}. Như vậy, khái niệm cặp có thứ tự không vượt ra khỏi

khuôn khổ lý thuyết tập hợp. Tuy nhiên, việc sử dụng định

nghĩa cặp có thứ tự như trình bày ở trên là thuận tiện cho việc

sử dụng hơn.

A₁´ A₂´ … ´ A_nº_def{(a₁, a₂, …, a_n) | a_iÎ A_i, 1 £ i £ n}.

Các phần tử của A₁´ A₂´ … ´ A_nđược gọi là các bộ có thứ

tự n phần tử. Khi n=3, ta gọi là bộ ba có thứ tự (triple).

René Descartes

(1596-1650)

41

42

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Tích Đềcác của các tập hợp

•

Chú ý: Với mọi tập A: A ´ f = f ´ A = f.

• Chú ý: Các điểm trên mặt phẳng được xác định bởi cặp có thứ

tự hai toạ độ, tương ứng với hai điểm trên trục hoành và trục

tung. Như vậy, R²=R´R. Phương pháp toạ độ được Đềcác đưa

vào sử dụng đầu tiên, từ đó có tên gọi “tích Đềcác”.

CM. Giả sử ngược lại là A ´ f ¹ f. Khi đó tìm được (a, b) Î A ´ f. Suy ra

a Î A và b Î f. Điều đó là mâu thuẫn với định nghĩa tập rỗng (tập f

không chứa bất cứ phần tử nào).

•

Định lý. Với ba tập A, B, C tuỳ ý, ta có:

a) A ´ (B ∩ C) = (A ´ B) ∩ (A ´ C)

b) A ´ (B È C) = (A ´ B) È (A ´ C)

c) (A ∩ B) ´ C = (A ´ C) ∩ (B ´ C)

d) (A È B) ´ C = (A ´ C) È (B ´ C)

CM: Coi như là bài tập.

• Luỹ thừa n của tập A là tích Đềcác:

Aⁿº_defA ´ A ´ … ´ A (vế phải có n thừa số A)

• Định lý. |A´B| = |A|.|B|.

• CM. Xét (a, b) Î A´B. Thành phần a có thể lựa chọn bởi |A|

cách, thành phần thứ hai b có thể chọn bởi |B| cách. Vậy có tất

cả |A|.|B| cặp có thứ tự.

• Hệ quả. |Aⁿ| = |A|ⁿ.

43

44

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Liệt kê các phần tử của tích Đềcác

1.5.3. Quan hệ

• Định nghĩa. Giả sử A và B là các tập hợp. Ta gọi quan hệ (hai

ngôi) R từ tập A vào tập B (hoặc quan hệ hai ngôi giữa hai tập

A và B) là tập con của tích Đềcác của A và B:

• Để liệt kê các phần tử

của tích Đềcác ta có thể

sử dụng cây liệt kê (tree

diagram).

R Ì A´B.

• Đối với quan hệ hai ngôi, thông thường ta sử dụng ký hiệu sau

• Ví dụ: Giả sử A = {2, 3,

4}, B = {4, 5}, và C = {x,

y}. Cây liệt kê của các

(infix notation)

aR b nghĩa là (a,b) Î R Ì A´B.

• Nếu A=B thì ta nói R là quan hệ trên tập A.

• Nếu aRb thì ta nói a có quan hệ với b (trong quan hệ R).

• Nếu (a, b) Ï R thì ta nói a không có quan hệ với b và ký hiệu

là a R b.

tập A ´ B, B ´ A, và A ´

B ´ C được cho trong

hình vẽ bên:

45

46

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Quan hệ hai ngôi – Ví dụ 1

Quan hệ hai ngôi – Ví dụ 1 (tiếp)

◦ Ví dụ 1:

◦ Ví dụ 1 (tiếp):

Xét tập các số nguyên không âm Z⁺. Xét R_£là quan hệ trên

Z⁺được định nghĩa như là tập R_£= {(x, y)| x £ y} (R_£là quan

hệ “nhỏ hơn hoặc bằng”).

Ta cũng có thể định nghĩa các quan hệ R_<, R , R_>trên Z⁺:

³

R_<= {(x, y)| x < y} (R_<là quan hệ “nhỏ hơn thực sự”).

R = {(x, y)| x ³ y} (R là quan hệ “lớn hơn hoặc bằng”).

³

Khi đó, (7, 7), (7, 8) Î R_£còn (8, 7) Ï R_£.

Do đó ta có: 7 R_£7, 7 R_£8 và 8 R_£7.

R_>= {(x, y)| x > y} (R_>là quan hệ “lớn hơn thực sự”).

• Tương tự như vậy có thể định nghĩa quan hệ R_£, R_<, R , R_>

³

trên các tập số thực R, tập số hữu tỷ Q, hoặc trên trên các tập

con của chúng.

47

48

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Quan hệ hai ngôi – Ví dụ 2

Quan hệ hai ngôi – Ví dụ 3

Ví dụ 2. Giả sử A = {0, 1, 2} và B = {a, b}. Khi đó

{(0,a), (0,b), (1,a), (2,b)}

Ví dụ 3. Gia

̉

sư

̉

A = {1, 2, 3, 4}. Các cặp có thư

́

tư

̣

nào là thuộc vào

quan hê

̣ trên A sau đây: R = { (a, b)| b chia hết a }?

là quan hệ R từ A vào B. Nghĩa là ta có 0Ra, còn 1R b

Giải:

1

2

1

2

3

4

R Í A´B = { (0,a) , (0,b) , (1,a)

A

3

4

B

(1,b) , (2,a) , (2,b)}

ÎR ÎR

0

1

2

a

b

R = { (1,1), (1,2), (1,3), (1,4),

&K¼ꢀ¿ꢀÓୱQꢀ

F£FKꢀEL୵XꢀGL୷Qꢀ

TXDQꢀK୹ꢀWU¬Qꢂ

WୟSꢀ$

(2,2), (2,4),

(3,3),

R

(4,4) }

&K¼ꢀ¿ꢀÓୱQꢀF£FKꢀEL୵XꢀGL୷QꢀTXDQꢀK୹ꢀ

W஝ꢀ$ꢀY¢Rꢀ%

49

50

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Quan hệ hai ngôi – Ví dụ 4

Ví dụ 4 (tiếp)

Giải:

• Ví dụ 4: Xét các quan hệ sau đây trên tập Z:

R₁= { (a, b) | a £ b }

(1,1) (1,2) (2,1) (1,-1) (2,2)

R₂= { (a, b) | a > b }

R₁

R₂

R₃

R₄

R₅

R₆

·

R₁= { (a, b) | a £ b }

R₃= { (a, b) | a = b hoặc a = -b }

R₄= { (a, b) | a = b }

·

R₂= { (a, b) | a > b }

·

R₃= { (a, b) | a = b hoặc a = -b }

R₄= { (a, b) | a = b }

R₅= { (a, b) | a = b+1 }

R₆= { (a, b) | a + b £ 3 }

·

R₅= { (a, b) | a = b+1 }

R₆= { (a, b) | a + b £ 3 }

• Với mỗi cặp trong số các cặp sau đây

(1,1), (1,2), (2,1), (1,-1), và (2,2)

hãy chỉ rõ nó thuộc những quan hệ nào trong các quan hệ trên.

·

51

52

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Quan hệ hai ngôi – Ví dụ 5

Quan hệ hai ngôi – Ví dụ 6

Ví dụ 6: Giả sử U là tập vũ trụ.

Ví dụ 5: Giả sử A = {2, 3, 6, 8, 9}. Xét R là quan hệ “chia hết

cho”, nghĩa là a có quan hệ với b nếu a chia hết cho b. Ta có

◦ Khi đó “Î” (thuộc) có thể xét như quan hệ R₁từ U

R = {(2,2), (3,3), (6,2), (6,3), (6,6), (8,2), (8,8), (9,3), (9,9)}

vào 2^U:

R₁= {(a, A)| a ÎU, A Î 2^U, a ÎA}

hay a R₁A Û a ÎA.

6

2

◦ Còn “Ì” (bao hàm) có thể xét như là quan hệ R₂trên

2^U:

8

3

R₂= {(A, B)| A, B Î 2^U, A Ì B}

hay A R₂B Û A Ì B

9

&K¼ꢀ¿ꢀÓୱQꢀF£FKꢀEL୵XꢀGL୷QꢀTXDQꢀK୹ꢀ

WU¬QꢀWୟSꢀ$

53

54

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Miền xác định và Miền giá trị của quan hệ

(Domain and Range of the Relation)

Quan hệ hai ngôi – Ví dụ 7

Ví dụ 7: Giả sử R là tập con của N

´

N được định nghĩa như sau

R = {(m, n)| n = 7m}.

• Giả sử RÌ A´B là quan hệ từ A vào B. Tập

dom R = {a| (a, b) Î R với một b nào đó}

được gọi là miền xác định (domain) của quan hệ R.

• Tập

Khi đó, R có thể xác định đệ qui như sau:

1) (0,0) Î R;

2) Nếu (s, t) Î R, thì (s+1, t+7) Î R .

Sử dụng định nghĩa trên hãy kiểm tra xem có phải 3 R 21

(nghĩa là kiểm tra (3, 21) Î R ) hay không?

Giải:

range R = {b| (a, b) Î R với một a nào đó}

được gọi là miền giá trị (range) của quan hệ R.

• Ví dụ:

a

1

A={1,2,3,4,5}, B={a,b,c,d}

i) (0, 0) Î R Þ (0+1, 0+7) = (1, 7) Î R

ii) (1, 7) Î R Þ (1+1, 7+7) = (2, 14) Î R và

iii) (2, 14) Î R Þ (2+1, 14+7) = (3, 21) Î R

b

c

2

3

4

5

dom R={1,3,4,5},

range R={a, b, d}

d

55

56

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Quan hệ bù (Complementary Relations)

• Giả sử R

ك

AŐB là quan hệ hai ngôi.

• Khi đó quan hệ bù`R của R được xác định bởi

`R ≡_def{(a,b) | (a,b) Ï R} = (AŐB) − R

http://muse.ci.ritsumei.ac.jp/~fusaoka/DMC07.pdf

• Chú ý là quan hệ bù của`R là R, nghĩa là

R = R.

• Ví dụ:

R_<={(a,b)|(a,b)ÏR_<}={(a,b)| Øa < b}= R .

³

58

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Quan hệ trên tập hợp

Quan hệ ngược (Inverse Relations)

• Mỗi quan hệ hai ngôi R

ك

AŐB đều có quan hệ ngược R⁻¹, xác

• Nhắc lại là ta đã định nghĩa quan hệ từ tập A vào chính nó

được gọi là quan hệ trên tập A. Chẳng hạn, quan hệ “ꢃ” xét

trên trên tập số tự nhiên N, trên tập số nguyên Z, trên tập số

thực R, trên tập số hữu tỷ Q.

định bởi

R⁻¹≡_def{(b,a) | (a,b)ÎR}.

• Ví dụ:

(R_<)⁻¹= {(b,a) | a<b} = {(b,a) | b>a} = R_>.

• Ví dụ: Giả sử B là tập các công việc còn A là tập các thợ thực

hiện công việc. Xét R là quan hệ từ A vào B xác định bởi

aRb Û a thực hiện b. Khi đó

• Quan hệ đồng nhất (identity relation) I_Atrên tập A được định

nghĩa như là

I_A={(a,a)| aÎA}.

b R⁻¹a Û b được thực hiện bởi a. (Cách nói thể bị động.)

• Chú ý: (R⁻¹)⁻¹= R.

59

60

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.5.4. Quan hệ hợp thành (Composite Relation)

Quan hệ n ngôi (n-ary Relations)

• Tổng quát khái niệm quan hệ hai ngôi, ta đưa vào định nghĩa

• Giả sử R

ك

AŐB , và S

ك

BŐC. Khi đó quan hệ hợp thành (còn

gọi là quan hệ tích) R o S của R và S được định nghĩa như sau:

quan hệ n ngôi.

• Định nghĩa. Quan hệ n ngôi R trên các tập A₁, A₂, ..., A_nlà tập

con của tích Đềcác của n tập này:

R o S = {(a,c) | aRb Ù bSc}.

• Ví dụ: Giả sử A={1,2,3,4,5}, B={a,b,c,d}, C={a, b, g}

R Ì A₁´ A₂´ ... ´ A_n.

• Chú ý: Các tập A_ikhông nhất thiết phải khác nhau.

R

S

a

b

c

1

2

3

4

5

a

b

g

• Ví dụ: quan hệ 3 ngôi:

– a ở giữa b và c;

– a nạp b vào c.

d

• Quan hệ n ngôi được sử dụng trong lý thuyết cơ sở dữ liệu

quan hệ (Relational Databases).

•

RoS = {(1, a), (1, g ), (4, a), (4, g ), (5, a) , (5, g )}

ك

AŐC.

61

62

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Luỹ thừa của quan hệ

1.5.5. Nhân của quan hệ

• Nếu R Ì A ´ B là quan hệ từ A vào B, thì RoR^-1được gọi là

nhân (kernel) của R và được ký hiệu là ker R. Như vậy nhân

của quan hệ từ A vào B là quan hệ trên A.

• Giả sử R là quan hệ trên tập A. Lũy thừa n của quan hệ R trên

tập A, ký hiệu là Rⁿ, là tích n lần của chính nó:

Rⁿ≡_defR oR o... oR

(n lần)

• Lũy thừa n của quan hệ R trên tập A (ký hiệu là Rⁿ) có thể định

• Ví dụ: Cho tập M với |M|=n. Xét quan hệ P từ 2^Mvào tập các

nghĩa một cách đệ qui như sau:

số nguyên

R⁰≡_defI_A;

Rⁿ⁺¹_defRⁿoR với mọi n≥0.

≡

0..n =_def{0, 1, 2, ..., n}, P Ì 2^M´ 0..n,

• Luỹ thừa âm của R, nếu cần, có thể định nghĩa như sau

R⁻ⁿ≡_def(R⁻¹)ⁿ.

trong đó P = {(X, k)| X Ì M Ù k Î 0..n Ù |X|=k}. Khi đó nhân

của quan hệ P là quan hệ đồng lực lượng (có cùng lực lượng)

trên 2^M.

63

64

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

1.5.6. Tính chất của quan hệ

Phản xạ (Reflexivity)

• Quan hệ R trên A được gọi là phản xạ (reflexive) nếu

"aÎA, aRa.

• Ta sẽ quan tâm đến các tính chất của quan hệ R trên

tập A (nghĩa là R Ì A²) sau đây:

– Ví dụ, quan hệ R_≥≡_def{(a,b) | a³b} là phản xạ.

– Phản xạ (Reflexivity), Phản xạ bù (irreflexive)

– Đối xứng (Symmetry), Phản đối xứng (antisymmetry)

– Bắc cầu (Transitivity)

• Quan hệ được gọi là phản xạ bù (irreflexive) khi và chỉ khi

quan hệ bù của nó là phản xạ.

– Toàn bộ (Totality), bộ phận (partial relation)

– Chú ý “irreflexive” ¹ “not reflexive”!

– Ví dụ: Quan hệ R_<trên Z⁺là phản xạ bù.

65

66

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

A relation R on a set A is called reflexive

if (a,a)ÎR for every aÎA.

Ví dụ. Quan hệ nào trong số các quan hệ sau đây trên

tập Z là phản xạ ?

Ví dụ. Xét các quan hệ sau đây trên tập {1, 2, 3, 4} :

R₂= { (1,1), (1,2), (2,1) }

R₁= { (a, b) | a £ b }

R₂= { (a, b) | a > b }

R₃= { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R₄= { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

Quan hệ nào là phản xạ ?

R₃= { (a, b) | a = b hoặc a = -b }

R₄= { (a, b) | a = b }

R₅= { (a, b) | a = b+1 }

R₆= { (a, b) | a + b £ 3 }

Trả lời: R₃

7U୕ꢀOஏLꢀꢁ R₁, R₃, R₄

67

68

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

* A relation R on a set A is called symmetric

if for a, bÎA, (a, b)ÎR Þ (b, a)ÎR.

* A relation R on a set A is called antisymmetric

Đối xứng (Symmetry)

if for a, bÎA,(a, b)ÎR and (b, a)ÎR Þ a = b.

• Quan hệ hai ngôi R trên A được gọi là đối xứng khi và chỉ khi

R = R⁻¹, nghĩa là,

Ví dụ. Quan hệ nào trong các quan hệ sau đây trên tập {1, 2, 3, 4}

là đối xứng, phản đối xứng:

(a,b)ÎR Û (b,a)ÎR.

– Ví dụ, quan hệ R₌(bằng) là đối xứng. R_<(nhỏ hơn) không là đối xứng.

R₂= { (1,1), (1,2), (2,1) }

• Quan hệ hai ngôi R là phản đối xứng (antisymmetric) khi và

chỉ khi

R₃= { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R₄= { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

(a,b)ÎR Ù (b,a) Î R Þ a=b

– Ví dụ, quan hệ R_£(nhỏ hơn hoặc bằng) là phản đối xứng.

• Quan hệ hai ngôi R là á đối xứng (asymmetric) khi và chỉ khi

(a,b)ÎR Þ (b,a)ÏR.

Trả lời: R₂, R₃là đối xứng (symmetric)

R₄là phản đối xứng (antisymmetric).

– Ví dụ, quan hệ R_<(nhỏ hơn hẳn) là á đối xứng.

69

70

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

A relation R on a set A is called transitive

if for a, b, c ÎA, (a, b)ÎR and (b, c)ÎR Þ (a, c)ÎR.

Bắc cầu (Transitivity)

•

Quan hệ hai ngôi R trên A được gọi là bắc cầu (hay truyền ứng) khi và chỉ

khi với mọi a, b, c

Ví dụ. Quan hệ nào trong các quan hệ sau đây trên tập {1, 2, 3, 4}

là bắc cầu:

(a,b)ÎR Ù (b,c)ÎR Þ (a,c)ÎR.

•

Quan hệ được gọi là không truyền ứng (intransitive) nếu nó không là quan

hệ truyền ứng.

R₂= { (1,1), (1,2), (2,1) }

R₃= { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R₄= { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

• Trả lời :

Ví dụ:

– Quan hệ “có họ hàng với” là quan hệ truyền ứng trên tập các cư dân.

– Quan hệ R_<là quan hệ truyền ứng.

•

R₂không bắc cầu vì

(2,1) Î R₂và (1,2) Î R₂nhưng (2,2) Ï R₂.

R₃không bắc cầu vì

– Hãy thử nghĩ xem: Quan hệ “là bạn của” trên tập tất cả cư dân trên trái

đất có là truyền ứng hay không?

(2,1) Î R₃và (1,4) Î R₃nhưng (2,4) Ï R₃.

R₄là bắc cầu.

71

72

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Toàn bộ (Totality)

Mối liên hệ giữa các tính chất

• Quan hệ R Í AŐB là toàn bộ nếu với mỗi aÎA, luôn tìm được

ít nhất một bÎB sao cho (a,b)ÎR.

•

Định lý sau đây cho biết mối liên hệ giữa các tính chất vừa

nêu của ánh xạ trên một tập hợp.

Định lý: Giả sử R là quan hệ trên tập A, nghĩa là R

ك

AŐA,

và I_Alà quan hệ đồng nhất trên tập A. (I_A={<a,a>| a

א

A}). Ta

có các khẳng định sau

• Nếu R không là quan hệ toàn bộ thì nó được gọi là quan hệ bộ

phận thực sự (strictly partial).

1. R là phản xạ khi và chỉ khi I_A

ك

R

2. R là đối xứng khi và chỉ khi R= R⁻¹

3. R là bắc cầu khi và chỉ khi RoR

ك

R

4. R là phản đối xứng khi và chỉ khi R ∩ R⁻¹

ك

I_A

5. R là phản xạ bù khi và chỉ khi R ∩ I_A= Æ

6. R là á xứng khi và chỉ khi R ∩ R⁻¹= Æ

• Quan hệ bộ phận (partial relation) là quan hệ có thể không là

bộ phận thực sự, nghĩa là nó có thể là quan hệ toàn bộ. Nói

cách khác tất cả các quan hệ đều có thể xem như là quan hệ bộ

phận.

73

74

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Mối liên hệ giữa các tính chất

Tính chất 3. R là bắc cầu khi và chỉ khi RoR

ك

R

Chứng minh.

Þ) Do R là bắc cầu nên "a,b,c ÎA aRb Ù bRc Þ aRc. Theo định nghĩa RoR:

Tính chất 1. R là phản xạ khi và chỉ khi I_A

ك

R

Þ) "aÎA aRa Þ "aÎA (a,a) Î R Þ I_AÌ R.

Ü) I_AÌ R Þ "aÎA (a,a) Î R Þ "aÎA aRa

aRoRb Û $cÎA aRc Ù cRb. Suy ra

aRoRb Þ aRb. Do đó: RoR

ك

R.

Ü) Do RoR

ك

R, nên ("a,bÎA (a,b)ÎRoR Þ (a,b)ÎR)

Þ (aRc Ù cRb Þ aRb).

Tính chất 2. R là đối xứng khi và chỉ khi R= R⁻¹.

Tính chất 4. R là phản đối xứng khi và chỉ khi R ∩ R⁻¹

ك

I_A

Þ) CM bằng phản chứng. Giả sử R ∩ R⁻¹

ك

I_A

Þ $a¹b aRb Ù aR⁻¹b Þ $a¹b aRb Ù bRa Þ R không là phản đối xứng?!

Ü) R ∩ R⁻¹

ك

I_AÞ (aRb Ù aR⁻¹b Þ a=b)

Þ) ("a,bÎA aRb Þ bRa) Þ ("a,bÎA (a,b) Î R Þ (b,a) Î R), theo định

nghĩa R^-1: (a,b) Î R Û (b,a) Î R^-1, suy ra

RÌ R^-1Ù R^-1Ì R Þ R= R⁻¹

.

Ü) R= R⁻¹Þ "a,bÎA ((a,b)ÎR Þ(a,b)ÎR^-1Ù (a,b)ÎR^-1Þ(a,b)ÎR)

do (a,b) Î R Û (b,a) Î R^-1Þ ((a,b) Î R Þ (b,a) Î R)

Þ ("a,bÎA aRb Þ bRa)

Þ (aRb Ù bRa Þ a=b)

Þ R là phản đối xứng.

75

76

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Bao đóng của quan hệ (Closures of Relations)

Mối liên hệ giữa các tính chất

Tính chất 5. R là phản xạ bù khi và chỉ khi R ∩ I_A= Æ

Þ)

Ü)

Quan hệ R={(1,1), (1,2), (2,1), (3,2)} trên tập A={1, 2, 3} không

là phản xạ.

Vấn đề: Xây dựng quan hệ phản xạ nhỏ nhất (theo nghĩa bao

hàm) R_rsao cho RÍ R_r?

Tính chất 6. R là á xứng khi và chỉ khi R ∩ R⁻¹= Æ

Þ)

Ü)

Giải: Đặt R_r= R È {(2,2), (3,3)}.

nghĩa là, R_r= R È {(a, a)| a Î A}.

R_rlà quan hệ phản xạ chứa R nhỏ nhất có thể. Nó được gọi là bao

đóng phản xạ của R.

CM tương tự, hãy coi như là bài tập

Định nghĩa. Ta gọi bao đóng phản xạ của quan hệ R là quan hệ

phản xạ nhỏ nhất (theo nghĩa bao hàm) chứa R.

77

78

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Bao đóng của quan hệ (Closures of Relations)

Bao đóng đối xứng

•

Ví dụ: Tìm bao đóng phản xạ của quan hệ R={(a,b) | a < b} trên tập số

nguyên Z.

Định nghĩa

1. Bao đóng phản xạ (reflexive closure) R_rcủa quan hệ R trên A

R_r=the smallest set containing R and is reflexive.

R_r=R

׫

{ (a, a) | aÎA , (a, a)ÏR}

Giải :

R_r= R

׫

{ (a, a) | aÎZ }

= { (a, b) | a £ b, a, bÎZ }

2. Bao đóng đối xứng (symmetric closure) R_scủa quan hệ R trên A

R_s=the smallest set containing R and is symmetric

R_s=R

׫

{ (b, a) | (a, b)ÎR & (b, a) ÏR}

3. Bao đóng truyền ứng (transitive closure) R_tcủa quan hệ R trên A

R_t=the smallest set containing R and is transitive.

R_t=R

׫

{ (a, c) | (a, b)ÎR & (b, c)ÎR, nhưng (a, c) ÏR}

•

Ví dụ. Quan hệ R={ (1,1),(1,2),(2,2),(2,3),(3,1),(3,2) } trên tập {1,2,3}

không là đối xứng.

Đặt

R^-1={ (a, b) | (b,a)ÎR }

và Let R_s= RÈR^-1={ (1,1),(1,2),(2,1),(2,2),(2,3), (3,1),(1,3),(3,2) }

•

Khi đó R_slà quan hệ đối xứng nhỏ nhất chứa R và được gọi là bao đóng đối

xứng của R.

79

80

Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội

Bài giảng Toán rời rạc - Chương 1: Tập hợp, Quan hệ (Set, Relation) - Nguyễn Đức Nghĩa