Ph¹m ThÕ Long
–
Chñ biªn
NguyÔn §øc HiÕu, NguyÔn ThiÖn LuËn
NguyÔn Xu©n Viªn, NguyÔn V¨n XuÊt
To ¸n rêi r¹c
Hµ Néi – 2003 Lời nói đầu
Phân công công việc giữa các tác giả nh- sau:
Chủ biên và hiệu đính toàn bộ nội dung bản thảo: Phạm Thế Long.
Ch-ơng 1: Nguyễn Xuân Viên.
Ch-ơng 2: Nguyễn Thiện Luận, Phạm Thế Long.
Ch-ơng 3: Nguyễn Đức Hiếu, Phạm Thế Long.
Ch-ơng 4: Phạm Thế Long.
Ch-ơng 5: Nguyễn Văn Xuất.
Các tác giả xin bày tỏ lòng cảm ơn chân thành PGS.TSKH Nguyễn Xuân Huy (Viện
Công nghệ Thông Tin), PGS.TS Đặng Huy Ruận (ĐHQG Hà Nội) đã đọc kỹ bản thảo và
cho nhiều ý kiến đóng góp xác đáng.
Chắc chắn không thể tránh khỏi những thiếu sót trong cuốn sách này. Các tác giả
rất mong nhận đ-ợc sự chỉ bảo và đóng góp của tất cả bạn đọc để có thể hoàn chỉnh nội
dung cho những lần xuất bản sau.
Các tác giả
9
2.2 Các phép toán trên tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3. L-ợng tử và vị từ
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.1 Hàm mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.2 Vị từ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.3 Phủ định của vị từ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
4. Quan hệ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.1 Khái niệm và tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.2 Ma trận quan hệ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.3 Quan hệ t-ơng đ-ơng, lớp t-ơng đ-ơng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.4 Quan hệ n - ngôi. Cơ sở dữ liệu quan hệ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. Một số bài toán đếm cơ bản: Hoán vị, tổ hợp, chỉnh hợp . . . . . . . . . . . . . . . . . . . . .
42
2.1. Chỉnh hợp lặp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
2.2. Chỉnh hợp không lặp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
2.3. Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
2.4. Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
2.5. Tổ hợp lặp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
2.6.
Hoán vị của tập hợp có các phần tử giống nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
2.7. Phân bổ các đồ vật vào trong hộp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
2.8. So sánh các cấu hình tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
3. Sinh các cấu hình tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
5.3. Quan hệ chia để trị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
6. Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
6.1. Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
6.2. Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
Ch-ơng 3
đồ thị và ứng dụng
85
1. Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
1.1. Khái niệm và thuật ngữ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
1.2. Đ-ờng đi. Chu trình. Đồ thị liên thông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 Đ-ờng đi Euler và chu trình Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
4.2. Đ-ờng đi và chu trình Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103
5. Bài toán tìm đ-ờng đi ngắn nhất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
106
5.1. Đồ thị có trọng số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
106
5.2. Thuật toán tìm đ-ờng đi ngắn nhất Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
6. Đồ thị phẳng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
110
6.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
110
6.2. Công thức Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
112
6.3. Định lý Kuratowski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
113
7. Tô màu đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
115
9.2 Thuật toán tìm luồng cực đại trong mạng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
145
Bài tập
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
151
Ch-ơng 4
Đại số Boole và mạch tổ hợp
163
1. Khái niệm về mạch tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
163
1.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
163
1.2 Biểu thức Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
165
2. Các tính chất của mạch tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
167
2.1 Các tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
167
2.2 Mạch tổ hợp t-ơng đ-ơng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
185
1.2. Máy hữu hạn trạng thái . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
186
2. Automat hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
188
2.1. Khái niệm và định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
188
2.2. Biểu diễn automat hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
189
2.3. Ngôn ngữ đoán nhận bởi automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
189
2.4. Automat không tất định (nondeterministic automat) . . . . . . . . . . . . . . . . . . . . . . . . .
191
2.5. Quan hệ giữa automat tất định và không tất định . . . . . . . . . . . . . . . . . . . . . . . . . . . .
192
3. Văn phạm và ngôn ngữ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
197
3.1. Các khái niệm và định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
197
3.2. Văn phạm và ngôn ngữ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
221
5.1. Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
221
5.2. Khái niệm và định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
222
5.3. Hàm Turing thực hiện đ-ợc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
224
5.4. Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
226
Bài tập
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
228
Tài liệu tham khảo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
234
Ch-ơng I.
Những khái niệm cơ bản về logic, tập hợp và suy luận toán học
Trong ch-ơng này chúng ta nghiên cứu một số vấn đề mang tính chất cơ sở không chỉ của toán
học rời rạc nói riêng, mà của cả toán học nói chung. Đó là những khái niệm cơ bản về logic
:
B F
hay
B F
.
Ví dụ 1.1.1. Tất cả các khẳng định sau đều là các mệnh đề
1. Hà Nội là Thủ đô của Việt Nam
2. 2>3
3. 1+3=4
Các mệnh đề 1, 3 là các mệnh đề đúng còn mệnh đề 2 là mệnh đề sai.
1.2 Các phép toán trên mệnh đề
Từ các mệnh đề ban đầu A, B, C ng-ời ta có thể xây dựng các mệnh đề mới với sự
giúp đỡ của các phép toán logic tuyển, hội và phủ định sau đây.
Định nghĩa 1.2.1. Giả sử A, B là các mệnh đề. Hội của A, B là một mệnh đề đ-ợc ký hiệu là
A B
và đọc là A và B. Mệnh đề
A B
đúng khi cả A và B đều đúng, và sai trong tất cả các
tr-ờng hợp còn lại.
Có thể biểu diễn hội của
A và B d-ới dạng bảng giá trị chân lý sau
A B
A B
T T T
T F F
,
C A C A
đều là các mệnh đề đúng.
Định nghĩa 1.2.3. Giả sử A là một mệnh đề, phủ định của A, ký hiệu
A
, là một mệnh đề nhận
giá trị đúng khi
A sai và nhận giá trị sai khi A đúng.
1.3 Mệnh đề có điều kiện và sự t-ơng đ-ơng logic
Định nghĩa 1.3.1.
Giả sử A, B là các mệnh đề. Mệnh đề có điều kiện (còn gọi là phép suy diễn
hay phép kéo theo)
A B
là một mệnh đề sai chỉ khi A đúng và B sai, và là mệnh đề đúng
trong mọi tr-ờng hợp còn lại.
Trong mệnh đề
A B
ng-ời ta gọi A là giả thuyết (hay A là nguyên nhân) B là kết luận (hay B
là kết quả). Nh- vậy, theo định nghĩa, phép suy diễn
A B
chỉ bị coi là sai nếu từ giả thuyết
đúng suy ra kết luận sai. Ta có bảng giá trị chân lý
A B
A B
1 1 3
là mệnh đề nhận giá trị đúng chỉ
khi hôm nay không phải là thứ t
Định nghĩa 1.3.2. Giả sử A, B là các mệnh đề. Khi đó mệnh đề A t-ơng đ-ơng với B, ký hiệu
là
A B
, là một mệnh đề nhận giá trị đúng khi và chỉ khi A và B có giá trị chân lý giống nhau.
Ta có bảng giá trị chân lý sau của mệnh đề
A B
.
A B
A B
T T T
T F F
F T F
F F T
Ng-ời ta còn sử dụng các cách gọi khác nhau của mệnh đề
A B
nh- có A khi và chỉ khi B,
A là cần và đủ đối với B hay nếu A thì B và ng-ợc lại.
Ví dụ 1.3.2. Nếu gọi A là mệnh đề Hôm nay trời nắng
B là mệnh đề Nhiệt độ ngoài trời cao hơn 30
0
C
A B A B
T T F T T T
T F F F F T
F F T T T T
F F T T T T
Nhìn trong bảng này ta thấy mệnh đề trên luôn nhận giá trị đúng với mọi giá trị khác nhau của
các mệnh đề sơ cấp
A, B cho nên nó chính là một định lý.
Ghi chú 1.3.1. Để đơn giản hơn trong cách viết các công thức ng-ời ta quy -ớc trật tự các phép
toán nh- sau: các phép toán trong ngoặc thực hiện tr-ớc, công thức nào có phủ định phải thực
hiện nó tr-ớc sau đó theo thứ tự -u tiên nếu không có dấu ngoặc thì phép hội thực hiện tr-ớc
phép tuyển thực hiện sau, cuối cùng mới đến các phép toán suy diễn và t-ơng đ-ơng. Ví dụ công
thức
A B C A
với công thức
A B C A
chỉ là một.
Sau đây chúng ta dẫn ra một số tính chất quan trọng nhất của logic mệnh đề. Các tính chất đó
đều có thể chứng minh đ-ợc bằng ph-ơng pháp lập bảng giá trị chân lý t-ơng tự nh- đã xét
trong ví dụ 1.3.3.
Định lý 1.3.1. Cho A, B, C là các mệnh đề bất kỳ. Khi đó ta có:
a) Luật giao hoán
A B C A B A C
d) Luật luỹ đẳng
A A A
;
A A Ae) Luật hấp thụ
A A B A
;
A A B A
f) Các luật De Morgan
A B A B
;
A B A B
. Nh- vậy giữa phần tử và tập hợp có quan hệ
phụ thuộc. Nếu
a không phải là phần tử của tập A thì ta viết
a A
hay
a A
.
Để ký hiệu tập
A gồm có các phần tử nào thì ta viết các phần tử ấy giữa 2 ngoặc nhọn
, ví
dụ
,
A a b
là một tập hợp có hai phần tử a và b; ta viết
a A
,
b A
. Cũng dễ dàng thấy
trong ví dụ này
0
Xét tập
1,2
A
còn
B
là tập các nghiệm của ph-ơng trình bậc hai
2
3 2 0
x x
.
Rõ ràng là
A = B vì ph-ơng trình
2
3 2 0
x x
có hai nghiệm
1 2
1, 2
x x
.
Định nghĩa 2.1.2. Nếu mọi phần tử của tập A đều là phần tử của tập B thì ta nói tập A là tập con
của
B và viết
A B
( )
A
p
là tập tất cả các tập con của A.
Ví dụ 2.1.3. Nếu
1,2,3
A
thì
( )
A
p
sẽ gồm các phần tử là các tập con của A sau:
, , , , , , , , , , , ,
a b c a b b c a c a b c
A
p
là
2
A
và
gọi tập tất cả các tập con của
A là tập luỹ thừa của A.
Định nghĩa 2.1.3. Giả sử A,B là hai tập hợp. Ta xây dựng tập mới ký hiệu là
A B
, trong đó
, ,
A B a b a A b B
sao cho
, ,
a b c d
khi và chỉ khi
gồm có 6 phần tử
1, , 1, , 2, , 2, , 3, , 3,
a b a b a b
.
A A
gồm có 9 phần tử là
n
A A A
, với
1 2 1 2 1 1 2 2
, , , , , ,
n n n n
A A A a a a a A a A a A
,
1 2 1 2
, , , , , ,
n n
a a a a a a
khi
và chỉ khi
i i
a a
A B x x A x B
hay
x A B x A x B
Ví dụ 2.2.1. Nếu
, , ,
A a b c d
là tập các học sinh trong một tổ tập bóng chuyền còn
, , ,
B a c e f
là tập các học sinh của tổ đó tập bơi thì tập các học sinh của tổ tham gia tập thể
thao (bóng chuyền hoặc bơi) sẽ là
, , , , ,
A B a b c d e f
Ví dụ 2.2.2.
Cũng lấy ví dụ
A,B
từ ví dụ 2.2.1 ta có
,
A B a c
là tập các học sinh trong
tổ tập cả hai môn bóng chuyền và bơi.
Ta có giản đồ Venn của tập
A B
nh- sau:
A B
Định nghĩa 2.2.3. Giả sử A, B là hai tập hợp. Hiệu của A và B, ký hiệu
\
A B
là một tập hợp
gồm các phần tử của
A nh-ng không phải của B. Nh- vậy
BxAxxBA \
, với U là
tập vũ trụ, ta có định nghĩa sau:
Định nghĩa 2.2.4.
A
U
đ-ợc gọi là phần bù của A (đối với U) , ký hiệu là
A
. Nh- vậy
x A x A
Ta có giản đồ Venn của
AA
Ví dụ 2.2.3. Lấy các tập A, B từ ví dụ 2.2.1 thì
\ ,
A B b d
còn
\ ,
B A e f
;
A B C A B A C
d) Luật đồng nhất
A A
;
A A
U
e) Luật nuốt
A
U U
;
A
f) Luật làm đầy
A A
U
;
U
k) Luật De Morgan
A B A B
;
A B A B
Chứng minh.
Nh- ta đã nói ở trên tất cả các luật trong định lý 2.2.1 đều đ-ợc chứng minh bằng
ph-ơng pháp đ-a về các luật t-ơng ứng của logic mệnh đề. Ví dụ ta chứng minh luật hấp thụ
A A B A
nh- sau.
Theo định nghĩa 2.2.1, 2.2.2 thì
khác, mệnh đề mà giá trị của nó phụ thuộc vào các giá trị khác nhau lấy từ một tập nào đó. Ví dụ
khẳng định
x là một số nguyên lớn hơn 5 là một loại khẳng định mà khi thay x bằng một giá
trị nguyên cụ thể nào đó ta sẽ đ-ợc một mệnh đề, chẳng hạn với
2
x
ta có mệnh đề 2 lớn
hơn 5
viết bằng ký hiệu toán học là
5
2
, đây là mệnh đề sai, còn với x bằng 6 ta sẽ đ-ợc
mệnh đề
5
6
là mệnh đề đúng. Loại mệnh đề phụ thuộc vào các tham số lấy giá trị từ một
tập nào đó đ-ợc gọi là hàm mệnh đề. Nói một cách chính xác ta có định nghĩa sau:
Định nghĩa 3.1.1. Hàm
1 2
, , ,
n
P x x x
xác định trên tập A đ-ợc gọi là hàm mệnh đề n - ngôi
nếu khi thay
,
y n
là các số nguyên cụ thể nào đó ta sẽ đ-ợc mệnh đề
m n
.
3.2 Vị từ
Xét khẳng định với mọi số tự nhiên n ta đều có
5
n
. Đây là một khẳng định sai vì ta dễ dàng
tìm thấy một số tự nhiên, chẳng hạn
1 5
. Tuy nhiên, dễ dàng thấy rằng, khẳng định tồn tại số
tự nhiên
n sao cho
5
n
lại là một mệnh đề đúng. Các mệnh đề nh- nêu ở đây đ-ợc xây dựng
từ hàm mệnh đề
5
n
xác định trên tập số tự nhiên với sự giúp đỡ của các toán tử đ-ợc gọi là
P a T
.
x P x
(đọc là tồn tại x
P x
) là một mệnh đề, nó nhận giá trị đúng khi và chỉ khi tồn tại
a A
để
P a T
. Các toán tử
,
x x
gọi là các l-ợng tử.
x
đ-ợc gọi là l-ợng tử chung,
x
x y x y
là một vị từ (mệnh đề) xác định trên tập số nguyên. Mệnh đề này
khẳng định với mọi số nguyên
x m
tồn tại số nguyên
y n
để
m n
. Rõ ràng đây là một
mệnh đề đúng.
3.3 Phủ định của vị từ
Ta xét phủ định của vị từ
5
x x
trên tập số nguyên
Z
, tức là
5
x x
5
x x
là mệnh đề sai. Ta có định lý sau:
Định lý 3.3.1. Nếu
P x
là hàm mệnh đề xác định trên tập A thì các khẳng định sau là hằng
đúng:
a)
xP x xP x
b)
xP x xP x
Chứng minh. Ta chứng minh khẳng định a). Mệnh đề
xP x
nhận giá trị đúng khi và chỉ khi
xP x
n
K n n K a a
.
Hàm mệnh đề
:
n
n K a a
xác định trên tập số tự nhiên
,
n K K N
. Theo chú
thích 3.3.2 thì vị từ của định nghĩa dãy
n
a
không có giới hạn a sẽ là:
0 0
:
n
K n n K a a
giao hoán còn các l-ợng từ khác loại không giao hoán đ-ợc cho nhau. Có thể thấy điều đó qua ví
dụ sau:
Ví dụ 3.3.2. Giả sử
,
P x y
là hàm mệnh đề xác định trên tập số nguyên
Z
. Vị từ
x y x y
là một mệnh đề đúng (ví dụ 3.2.2), nh-ng mệnh đề
y x x y
là mệnh đề sai vì nó khẳng
định tồn tại một số nguyên
0
y m
để
0
m
nhỏ hơn hoặc bằng tất cả các số nguyên
x n
thành phủ định của nó
1 2
, , ,
n
P x x x
.
4. Quan hệ
4.1 Khái niệm và tính chất
Quan hệ giữa hai tập theo ngôn nghĩa trực giác đ-ợc hiểu hiểu là mối quan hệ giữa một số phần
tử của tập này với một số phần tử của tập khác. Chẳng hạn, nếu lấy
A tập các sinh viên nào đó và
B là tập các môn học mà họ đang theo họcthì ta có thể nói sinh viên a có quan hệ với môn học a
nếu sinh viên
a theo học môn a
. Hoàn toàn t-ơng tự nh- vậy nếu lấy A là tập một số ng-ời nào
đó và quan hệ mà ta quan tâm là quan hệ họ hàng chẳng hạn thì ta nói anh a và cô b thuộc quan
hệ này nếu
a và b có họ với nhau.
Định nghĩa 4.1.1. Giả sử X, Y là hai tập hợp. Quan hệ hai ngôi R từ X đến Y đ-ợc định nghĩa là
tập con của tích Decac
X Y
, tức là
R X Y
ng-ời ta th-ờng hay viết
xRy
bắt ch-ớc theo quan hệ
trong tập số
thực:
,
khi và chỉ khi
.
Nếu quan hệ hai ngôi biểu diễn d-ới dạng một bảng gồm 2 cột thì cột thứ nhất gồm các phần tử
của miền xác định, cột thứ hai - miền giá trị.
Ví dụ 4.1.1. Giả sử
2,3,4,5
X
,
1,3,4,5,6,7,9
Y
. Ta xác định quan hệ hai ngôi
4
5
4
6
3
6
9
4
5
Trong đó các phần tử trên cùng một hàng nằm trong quan hệ
R. Nhìn vào bảng này các phần tử
nằm trên cột thứ nhất
5,4,3,2
là tập xác định của quan hệ R còn các phần tử trên cột thứ hai
3,4,6,5,9
là tập giá trị của R.
Ví dụ 4.1.2.
2,3,4,5
X
. Ta nói
,
.
Định nghĩa 4.1.2. Quan hệ R trong tập X đ-ợc gọi là có tính phản xạ nếu
,
x x R
với mọi
x X
.
Quan hệ trong ví dụ 4.1.2 là quan hệ có tính phản xạ.
Ví dụ 4.1.3. Gọi
2,3,4,5
X
. Ta nói
,
a b R
và chỉ khi
a b
. Rõ ràng là
y x
. Rõ ràng đây là quan hệ không có tính phản thân, vì
ví dụ nh-
3,3
R
là do
2 2
3 3
x x
.
Định nghĩa 4.1.6. Quan hệ R trong tập X đ-ợc gọi là có tính bắc cầu nếu với mọi
, ,
x y z X
,
từ
,
x y R
và
,
,
x y X
từ
,
x y R
suy ra
,
y x R
.
Quan hệ trong các ví dụ 4.1.2, 4.1.3 đều không phải là các quan hệ có tính đối xứng vì trong ví
dụ 4.1.2 ta có
2 3
nh-ng
3
2
; Trong ví dụ 4.1.3 có
2,4
R
x y
thì
,
y x R
.
Quan hệ trong các ví dụ 4.1.2, 4.1.3 đều là các quan hệ có tính phản đối xứng là do trong tập số
thực
x y
và
y x
thì x = y.
T-ơng tự nh- vậy trong tập số tự nhiên nếu m chia hết cho n và n chia hết cho m thì m = n. Rõ
ràng là quan hệ trong ví dụ 4.1.4 không có tính phản đối xứng.
Định nghĩa 4.1.9. Quan hệ R trong tập X đ-ợc gọi là quan hệ thứ tự từng phần trong X nếu nó là
quan hệ có tính phản xạ, phản đối xứng và bắc cầu.
Từ các nhận xét trên ta thấy các quan hệ trong các ví dụ 4.1.2, 4.1.3 là các quan hệ thứ tự từng
phần trên các tập
X t-ơng ứng. Nếu R là một quan hệ thứ tự từng phần trong tập X thì khi
,
x y R
ng-ời ta th-ờng nói x, y so sánh đ-ợc với nhau. Khi
là quan
hệ từ
Y vào X đ-ợc xác định nh- sau
1
yR x xRy
hay t-ơng đ-ơng
1
, ,
R y x x y R
4.2 Ma trận quan hệ
Giả sử
R
là một quan hệ từ tập
X
vào tập
Y
. Ta có thể biểu diễn quan hệ
R
d-ới dạng một ma trận
không
j là
1
ij
m
nếu
,
i j
x y R
,
0
ij
m
nếu
,
i j
x y R
.
Ví dụ 4.2.1. Giả sử
2,3,4
X
thứ tự tăng dần) thì ng-ời ta chỉ viết
0 1 0 1
0 1 0 0
0 0 0 1
R
M
Nh- vậy là với mỗi quan hệ
R X Y
từ tập hữu hạn X vào tập hữu hạn Y ta có thể xây dựng
đ-ợc một ma trận quan hệ (chính xác đến sự sắp xếp thứ tự của tập
X và tập Y). Ng-ợc lại với
mỗi ma trận không
một
M
ta có một quan hệ
R
từ
X
vào
Y
.
Thật vậy nếu
X có
X n
thì
R
M
là ma trận vuông cấp n.
Dễ dàng nhận thấy quan hệ
R trong tập X có tính đối xứng khi và chỉ khi
R
M
là ma trận đối
xứng.
R có tính phản đối xứng khi và chỉ khi
1 0
0 1 0
ij ji
ij ji ji
m m
m m m
Quan hệ
R trong tập X có tính phản xạ khi và chỉ khi tất cả các phần tử trên đ-ờng chéo
a b R
khi và chỉ khi a, b cùng màu. Dễ dàng nhận thấy R là một quan hệ t-ơng đ-ơng:
,
a a R
, quả cầu chỉ có một màu
,
a b R
thì
,
b a R
: quả cầu a cùng màu với b thì b cùng màu với a.
,
a b R
,
,
l a l b
. Nh- trên, ở đây
cũng dễ dàng nhận thấy
R là quan hệ t-ơng đ-ơng trong tập X.
Định nghĩa 4.3.2. Họ S các tập con khác rỗng của X đ-ợc gọi là phân hoạch của X, nếu mỗi
phần tử
x của X thuộc một và chỉ một phần tử S. Các phần tử S th-ờng đ-ợc gọi là các lớp của
phân hoạch S.
Nh- vậy họ S
i
i I
X
,
,
i i
X X X
là một phân hoạch của X nếu
i j
X X
và
i
tức là
,
i
x y X
thì
R
là một quan hệ t-ơng đ-ơng trong tập X.
Chứng minh.
Rõ ràng là với mọi
x X
thì
,
x x R
vì
i
i I
X X
, do đó tồn tại
i I
để
yRx
cũng với ý nghĩa nh- thế
,
i
y x X
vậy là quan hệ R lại có
tính đối xứng. Định lý đã đ-ợc chứng minh xong.
Ví dụ 4.3.3. Xét tập
*
0, ,
m
n n m
n
Q N Z
các số hữu tỉ. Hai số hữu tỉ
1
1
1
m
r
n
và
2
2
m
r
n
thì lấy
1
r A
có
1 2
r r B
nên
1
r B
tức là
A B
. Ng-ợc lại lấy
3
r B
thì
3 2
r r A
cho nên
B A
x x X
là một phân hoạch của X.
Chứng minh. Thứ nhất, tập
x x X
cho ta mỗi
x x
S . Thứ hai, hai lớp khác
nhau thì rời nhau. Thật vậy nếu
a
và
b
có chung phần tử
x X
thì với mỗi
a b
cho nhau ta đ-ợc
b a
. Từ các lý luận trên ta có
a b
. Nh-
vậy hai lớp có chung một phần tử thì chúng phải trùng nhau; Điều sau cũng có nghĩa là hai lớp
khác nhau thì rời nhau. Định lý đã đ-ợc chứng minh.
Từ hai định lý 4.3.1 và 4.3.2 ta thấy khái niệm quan hệ t-ơng đ-ơng trong tập
X và phân hoạch
của
X là t-ơng đ-ơng với nhau.
Ví dụ 4.3.4. Cho quan hệ t-ơng đ-ơng
1 3 5 1,3,5
;
2 4 2,4
.
Ví dụ 4.3.5. Lấy
1,2, ,7
X
. Quan hệ t-ơng đ-ơng R đ-ợc xác định nh- sau:
xRy
khi
và chỉ khi
x
1 1,4,7
,
2 2,5
nh- vậy là
3 6
,
1 4 7
,
Copyright: Tài liệu đại học ©