Tiểu luận Cơ sở toán tin học - Đề tài: Tìm hiểu quan hệ và ứng dụng
TRƢỜNG ĐẠI HỌC KHOA HỌC HUẾ
KHOA CÔNG NGHỆ THÔNG TIN
TIỂU LUẬN
CƠ SỞ TOÁN TIN HỌC
ĐỀ TÀI:
TÌM HIỂU QUAN HỆ VÀ ỨNG DỤNG
LỚP CAO HỌC: NGÀNH KHOA HỌC MÁY TÍNH
GVHD: PGS TS: TRƢƠNG CÔNG TUẤN
Lớp: Cao học KHMT-GIA LAI 2018
HVTH: Nhóm 2
+ Cao Chí
Hiển, ĐT 0985945261
+ Nguyễn Thị
+ Nguyễn Thị
+ Đào Thị
Thụy
Thảo
Hiểu
+ Dƣơng Thị Minh Thảo
GIA LAI, 7/ 2018
MỤC LỤC
LỜI NÓI ĐẦU ...............................................................................................................................1
PHẦN I: CỞ SỞ KHOA HỌC.....................................................................................................2
I. QUAN HỆ VÀ CÁC TÍNH CHẤT CỦA NÓ..........................................................................2
1.1 ĐỊNH NGHĨA......................................................................................................................2
1.3 CÁC QUAN HỆ TRÊN MỘT TẬP HỢP .........................................................................3
1.4 CÁC TÍNH CHẤT CỦA QUAN HỆ .................................................................................4
1.5 TỔ HỢP CÁC QUAN HỆ ..................................................................................................5
II. QUAN HỆ TƢƠNG ĐƢƠNG................................................................................................5
2.1 ĐỊNH NGHĨA......................................................................................................................6
2.2 CÁC LỚP TƢƠNG ĐƢƠNG.............................................................................................6
2.2.2. MỆNH ĐỀ:.......................................................................................................................7
2.2.3. Định nghĩa: Tập thƣơng của A theo quan hệ R ...........................................................7
2.3. PHÂN HOẠCH ..................................................................................................................8
2.3.2. Mệnh đề:...........................................................................................................................8
III. QUAN HỆ THỨ TỰ...............................................................................................................9
3.1 Định nghĩa 1: QUAN HỆ THỨ TỰ ...................................................................................9
3.2 Định nghĩa 2: QUAN HỆ THỨ TỰ TOÀN PHẦN ........................................................10
3.4 Định nghĩa 4: CHẶN TRÊN (CHẶN DƢỚI) .................................................................11
3.5 Định nghĩa 5: CÂN TRÊN, CẬN DƢỚI .........................................................................12
3.6 Định nghĩa 6: PHẦN TỬ TỐI ĐẠI (TỐI TIỂU)............................................................13
3.7. Mệnh đề:...........................................................................................................................13
3.12. Bổ đề Zore: ......................................................................................................................14
PHẦN II: MỘT SỐ BÀI TẬP VẬN DỤNG..........................................................................15
III. MỘT SỐ BÀI TẬP QUAN HỆ THỨ TỰ......................................................................20
PHẦN III: ỨNG DỤNG CỦA QUAN HỆ ................................................................................25
Tạo bao đóng phản xạ.............................................................................................................25
Tạo bao đóng đối xứng............................................................................................................25
LỜI NÓI ĐẦU
Các mối quan hệ giữa những phần tử của tập hợp xuất hiện trong nhiều bối
cảnh. Thường ngày ta vẫn gặp những mối quan hệ này, chẳng hạn mối quan hệ
giữa một trường học với số điện thoại của nó, mối quan hệ giữa một giáo viên với
lương của người đó, mối quan hệ của một người với người thân của anh ta... Trong
toán học, ta nghiên cứu mối quan hệ như mối quan hệ giữa một số nguyên dương
và một ước số của nó, mối quan hệ giữa một số nguyên và một số nguyên khác
đồng dư với nó theo môđulô n, mối quan hệ giữa một số thực và một số thực khác
lớn hơn nó... Các mối quan hệ như quan hệ giữa một chương trình và một biến mà
chương trình đó sử dụng và quan hệ giữa một ngôn ngữ máy tính với một mệnh đề
đúng trong ngôn ngữ đó cũng thường xuất hiện trong tin học.
Các quan hệ có thể được dùng để giải các bài toán như xác định các cặp
thành phố nào được nối bằng các chuyến bay trong một mạng, tìm trật tự khả dĩ
thành công cho các pha khác nhau của một dữ án phức tạp, hoặc tạo một cách tiện
ích để lưu trữ thông tin trong các cơ sở dữ liệu của máy tính. Các mối quan hệ giữa
những phần tử của các tập hợp được biểu diễn bằng một cấu trúc được gọi là Quan
Hệ. Đây là nội dung chính trong đề tài tiểu luận của nhóm em: TÌM HIỂU VỀ
QUAN HỆ VÀ ỨNG DỤNG
Mặc dù đã rất cố gắng nhưng tiểu luận này không tránh khỏi những sai sót.
Nhóm chúng em rất mong nhận được các ý kiến góp ý của thầy hướng dẫn và các
bạn.
Xin chân thành cảm ơn PGS.TS. TRƢƠNG CÔNG TUẤN đã tận tình
hướng dẫn và tạo điều kiện cho chúng em hoàn thành môn học này.
Gia Lai, ngày 10 tháng 08 năm 2018
Học viên thực hiện
NHÓM 2
Trang: 1
PHẦN I: CỞ SỞ KHOA HỌC
I. QUAN HỆ VÀ CÁC TÍNH CHẤT CỦA NÓ.
Cách trực tiếp nhất để biểu diễn mối quan hệ giữa các phần tử của hai tập
hợp là dùng các cặp được sắp tạo bởi hai phần tử có quan hệ. Vì lí do đó, tập các
cặp được sắp được gọi là quan hệ hai ngôi. Sau đó chúng ta sẽ dùng các quan hệ để
giải các bài toán có liên quan với các mạng thông tin, nhận dạng các phần tử của
các tâp hợp có những tính chất chung.
1.1 ĐỊNH NGHĨA
Cho hai tập A và B. Một quan hệ hai ngôi từ A đến B là một tập con
tích Descartes A x B. Ta nói phần tử a A có quan hệ với phần tử b B nếu
(a, b) và ký hiệu là a b.
Ví dụ 1: Cho A là tập các sinh viên của Đại học Huế và B là tập hợp các
của
môn học. cho R là quan hệ bao hàm gồm các tập (a, b) trong đó a là sinh viên học
môn b. Chẳng hạn, bạn An và bạn Tùng là sinh viên của Đại học Huế đều học môn
đại số có mã là NMDSO, thì các cặp (An, NMDSO) và (Tùng, NMDSO) thuộc R.
Nếu An còn học môn Giải tích 1 có mã số GTICH1 thì cặp (Tùng, GTICH1) không
thuộc R.
Ví dụ 2: Cho A là tập hợp các quận, huyện và B là tập hợp các tỉnh thành
phố của Việt Nam. Ta định nghĩa quan hệ R bằng cách chỉ rõ rằng (a, b) thuộc R
nếu quận hay huyện a thuộc tỉnh hay thành phố b. Chẳng hạn (Phú Lộc, Thừa
Thiên Huế), (Ba Đình, Hà Nội), (Phú quốc, Kiên Giang), (Nam Đàn, Nghệ An), ...
đều thuộc R.
Ví dụ 3: Cho A = {0, 1, 2} và B {a, b}. Khi đó {(0, a), (0, b),(1,a), (2, b)} là
một quan hệ từ A đến B. Điều này có nghĩa là, chẳn hạn 0Ra nhưng 1Rb (1 không
quan hệ với b).
Trang: 2
1.2 ÁNH XÃ CŨNG NHƢ MỘT QUAN HỆ (HÀM CŨNG LÀ MỘT QUAN
HỆ)
Hãy nhớ rằng một ánh xạ f từ tập hợp A đến tập hợp B gán cho mỗi phần tử
của A một phần tử duy nhất của B. Đồ thị của f là tập các cặp (a, b) sao cho b =
f(a). Vì đồ thị của f là một tập con của A x B, nên nó là một quan hệ từ A đến B.
Ngược lại, nếu là một qu an hệ từ A đến B sao cho mỗi phần tử của A là
phần tử đầu tiên của đúng một cặp của , thì có thể định nghĩa được một ánh xạ
với
là đồ thị của nó. Điều này được làm bằng cách gán cho mỗi phần tử a A
một phần tử duy nhất b B sao cho (a, b)
.
Một quan hệ cũng có thể được dùng để biểu diễn các mối quan hệ một -
nhiều giữa các phần tử của hai tập hợp A và B, trong đó một phần tử của A có thể
có quan hệ với hơn một phần tử của B. Trong khi đó, một ánh xạ biểu diễn một
quan hệ trong đó mỗi phần tử của A có quan hệ với đúng một phần tử của B.
Quan hệ là sự tổng quát hóa khái niệm hàm; chúng có thể được dùng để biểu
diễn một lớp rộng lớn của các mối quan hệ giữa các tập hợp.
1.3 CÁC QUAN HỆ TRÊN MỘT TẬP HỢP
Định nghĩa: Một quan hệ trên tập A là một quan hệ từ A đến A. Nói một
cách khác, một quan hệ trên tập A là một tập con của tập A × A.
Ví dụ 1:
i) Quan hệ "nhỏ hơn hoặc bằng" ( ) là một quan hệ trên tập hợp các số thực.
ii) Quan hệ "chia hết" (|) là một quan hệ trên tập N các số tự nhiên.
iii) Quan hệ "vuông góc" (┴) là một quan hệ trên tập hợp các đường thẳng trong
mặt phẳng.
iiii) Với n là một số nguyên dương, R= {(x, y)
x
| x - y chia hết cho n} là
một quan hệ trên , gọi là quan hệ đồng dư môđulô n. Khi xRy, ta viết x
(modn).
y
iiiii) Quan hệ "cùng tuổi" là một quan hệ trên tập hợp các con người trên trái đất.
Ví dụ 2: Cho A là tập các phần tử {1, 2, 3, 4}. Hỏi các tập được sắp nào
thuộc quan hệ R = {(a,b) | b chia hết cho a}?
Trang: 3
Giải. Vì (a, b) thuộc R nếu và chỉ nếu a và b là các số nguyên dương không
vượt quá 4 sao cho b chia hết cho a, ta có:
R = {(1, 1), (1, 2), (1,3), (1, 4), (2,2), (2,4), (3,3), (4,4)}
Ví dụ 3: Có bao nhiêu quan hệ trên tập có n phần tử?
Giải: Một quan hệ trên tập A là một tập con của A x A. Vì A x A có n2 phần
tử khi A có n phần tử và một tập gồm m phần tử có 2m tập con, nên A x A có
2
2
n2
2n
tập con. Vì cậy có
quan hệ trên tập n phần tử. Víu dụ
= 29 = 512 quan hệ
23
2
trên tập {a, b, c}
1.4 CÁC TÍNH CHẤT CỦA QUAN HỆ
14.1. Định nghĩa: Quan hệ R được gọi là có tính phản xạ nếu với mọi a ∈ A,
(a, a)∈R với mọi a ∈ A.
1.4.2. Định nghĩa: Quan hệ R trên tập A gọi là đối xứng nếu với mọi a, b ∈
A, a R b thì b R a.
1.4.3. Định nghĩa: Quan hệ R trên tập A đuợc gọi là có tính phản đối xứng
hay phản xứng nếu với mọi a, b ∈ A, (a, b)∈R và (b, a)∈R thì a = b.
1.4.4. Định nghĩa: Một quan hệ R trên tập A được gọi là có tính bắc cầu nếu
a, b, c ∈ A, (a, b) ∈R và (b, c)∈R thì (a, c) ∈R.
i) Quan hệ "bằng nhau" (=) trên một tập X tùy ý có 4 tính chất: phản xạ, đối
xứng, phản đối xứng và bắc cầu.
ii) Quan hệ trên tập hợp X, với X là tập con tùy ý của R, có 3 tính chất:
phản xạ, phản đối xứng và bắc cầu.
iii) Quan hệ "đồng dư modn" trên tập hợp
xứng, bắc cầu.
có 3 tính chất: phản xạ, đối
iiii) Quan hệ "chia hết" trên tập * các số nguyên dương có 3 tính chất: phản
xạ, phản đối xứng và bắc cầu. Tuy nhiên, nếu xét trên tập thì quan hệ này chỉ có
tính bắc cầu.
iiiii) Quan hệ bao hàm ( ) trên tập hợp P(X) tất cả các tập con của tập hợp
X tùy ý có 3 tính chất phản xạ, phản đối xứng, bắc cầu.
Trang: 4
1.5 TỔ HỢP CÁC QUAN HỆ
Vì các quan hệ từ A đến B là tậ p con của tập A×B, nên hai quan hệ từ A đến
B cũng có thể đuợc tổ hợp như hai tập hợp. Chẳng hạn, với R1 và R2 là hai quan hệ
từ A đến B thì ta có những quan hệ R1 R2, R1 R2, R1\ R2
R2 từ A
đến B.
1.5.1. Định nghĩa: Cho R là một quan hệ từ tập A đến tập B. S là quan hệ từ
tập B đến tập C. Hợp thành của R và S là một quan hệ chứa các cặp được sắp (a, c)
trong đó a∈A và c∈C và đối với chúng tồn tại một phần tử b∈B sao cho (a,
b)∈R và (b, c)∈ S. Ta ký hiệu hợp thành của R và S là SoR, xác định bởi
SoR = {(a,c) ∈ A x C| ∃b ∈ B, (a, b) ∈ R và (b, c) ∈ S}
Đặc biệt, khi R là đồ thị của ánh xạ f và S là đồ thị của ánh xạ g thì S o R là
đồ thị của ánh xạ gof.
1.5.2. Định nghĩa: Cho R là một quan hệ trên tập A. Lũy thừa Rn với n = 1, 2,
3, …được định nghĩa bằng quy nạp như sau:
R1 = R và Rn+1 =Rn R
o
Như vậy, (a, b) ∈ Rn khi và chỉ khi tồn tại x1, x2, ...., xn-1 ∈ A sao cho (a, x1),
(x1, x2), ..., (xn-1, b) ∈ R.
1.5. 3. Mệnh đề: Quan hệ R trên tập A có tính chất bắc cầu khi va chỉ khi
Rn R
n
với mọi
II. QUAN HỆ TƢƠNG ĐƢƠNG
Các số nguyên a và b quan hệ với nhau bằng phép “đồng dư theo môdun 4”
khi a – b chia hết cho 4. Dưới đây ta sẽ chỉ ra răng quan hệ này cũng là phản xạ,
đối xứng và bắc cầu. Dễ dàng thấy rằng a quan hệ với b nếu và chỉ nếu a và b có
cùng số dư khi chia cho 4. Từ đây suy ra rằng quan hệ này tách tập hợp các số
nguyên thành 4 lớp khác nhau. Khi đó ta chỉ cần quan tâm một số nguyên khi chia
cho 4 cho số dư nào, chỉ cần biết nó thuộc lớp nào chứ không cần biết giá trị nó là
bao nhiêu.
Quan hệ R và phép đồng dư theo môdun 4 là ví dụ về quan hệ tương đương,
cụ thể là quan hệ có tính chất phản xã, đối xứng và bắc cầu. Trong mục này chúng
Trang: 5
ta chỉ ra rằng các quan hệ như vậy sẽ tách các tác tập thành những lớp rời nhau
gồm các phần tử tương đương. Khi đó ta chỉ quan tâm một phần tử của tập thuộc
lớp nào chứ không cần quan tâm tới các đặc điểm của nó.
Trong mục này chúng ta sẽ nghiên cứu các quan hệ với một tổ hợp đặc biệt
các tính chất cho phép cúng được dùng để liên hệ các đối tượng tương đương nhau
theo một định nghĩa nào đó.
2.1 ĐỊNH NGHĨA
Quan hệ cho trên tập A được gọi là tương đương nếu nó là phản xạ, đối
xứng và bắc cầu.
Ví dụ 1. Quan hệ đồng dư "modn" trên tập hợp là một quan hệ tương đương.
Ví dụ 2. Quan hệ "đồng dạng" trên tập hợp các tam giác là một quan hệ tương
đương.
Ví dụ 3. Quan hệ "cùng phương" (song song hoặc trùng nhau) trên tập hợp các
đường thẳng của mặt phẳng là một quan hệ tương đương.
Ví dụ 4: = {(m, n) | m – n chẵn} là quan hệ tương đương.
2.2 CÁC LỚP TƢƠNG ĐƢƠNG
Cho A là tập tất cả các sinh viên ở trường đã tốt nghiệp phổ thông. Xét quan
hệ R trên A gồm tất cả các cặp (x, y), trong đó x và y tốt nghiệp ở cùng một trường
phổ thông. Vơi sinh viên x đã cho, ta có thể lấy một tập các sinh viên tương đương
với x đối với R. Tập này gồm tất cả các sinh viên đã tốt nghiệp phổ thông ở cùng
trường với x. Tâp con này của A được gọi là một lớp tương đương của quan hệ đó.
2.2.1 Định nghĩa: Cho R là một quan hệ tương đương trên tập hợp A và a ∈
A. Tập hợp {x ∈ A | xRa} được gọi là lớp tương đương của phần tử a, ký hiệu là
hoặc [a] hoặc C(a).
Nói cách khác, nếu R là một quan hệ tương đương trên tậ Athì lớp tương
đương của các phần tử a là [a] = {s | (a, s) R}
Nếu b [a] thì b được gọi là đại diện của lớp tương đương
Ví dụ: Xác định lớp tương đương của 0 và 1 đối với quan hệ đồng dư môdun 4.
Lớp tương đương của 0 chứa tất cả các số a sao cho a 0(mod 4) .
Trang: 6
Các số nguyên thuộc lớp này chính là các sô nguyên chia hết cho 4, lớp tương
đương của 0 đối với quan hệ này là:
[0] = {…, -8, - 8, 0, 4, 8, 12,… }
Tương tự, lớp tương đương của 1 chứa tất cả các số a sao cho a 1(mod 4),
đó là các số nguyên a chia cho 4 dư 1. Vì vậy lớp tương đương này là:
[1] = {…, -7, - 3, 1, 5, 9, 13,… }
2.2.2. MỆNH ĐỀ:
Cho R là một quan hệ tương đương trên tập hợp A và a, b ∈ A. Khi đó ta có:
i) ≠ .
ii) = khi và chỉ khi aRb.
iii) = hoặc
= .
2.2.3. Định nghĩa: Tập thƣơng của A theo quan hệ R
Cho R là một quan hệ tương đương trên tập hợp A. Khi đó A được chia thành
các lớp tương đương khác rỗng, rời nhau đôi một. Tập hợp các lớp tương đương đó
gọi là tập thương của A theo quan hệ tương đương R và ký hiệu là A/R. Như vậy,
A/R = { | a ∈ A}.
Ví dụ 1: Xét quan hệ tương đương "cùng phương" trên tập hợp D tất cả các
đường trong mặt phẳng. Khi đó với đường thẳng a ∈ D, lớp tương đương là tập
hợp gồm a và các đường thẳng trong D song song với a. Trong toán học, người ta
coi mỗi lớp tương đương nói trên là một phương trên mặt phẳng. Vì vậy có thể coi
tập thương là tập hợp các phương của mặt phẳng.
Ví dụ 2: Cho X= {1, 2, 3, 4}. Trên P(X), xét quan hệ R như sau:
A, B ∈ P(X), A R B
|A| = |B|.
Dễ dàng có được R là một quan hệ tương đương trên P(X). Các lớp tương
đương theo quan hệ R là:
C0= { (tập con của X không có phần tử nào),
C1= {{1}, {2}, {3}, {4}} (các tập con của X có 1 phần tử),
C2= {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}} (các tập con của X có 2
phần tử),
Trang: 7
C3= {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}} (các tập con của X có 3 phần
tử),
C4= {{X}} (tập con của X có 4 phần tử).
Tập thương của X theo quan hệ R là P(X)/R= {C0, C1, C2, C3, C4}.
2.3. PHÂN HOẠCH
Cho R là một quan hệ tương đương trên tập A. Hợp các lớp tương đương của
R là toàn bộ tập A, vì một phần tử a A sẽ thuộc một lớp tương đương riêng của
nó, cụ thể là lớp [a]k. Nói một cách khác,
R = A
aA
Thêm vào đó, theo mệnh đề suy ra rằng các lớp tương đương này hoặc là
bằng nhau hoặc là rời nhau, nghĩa là: [a]R [b]R = khi [a]R [b]R
Nhận xét trên chứng tỏ rằng các lớp tương đương tạo nên một phân hoạch
của tập A, vì nó tách tập A thành các tập con rời nhau. Nói một cách khác hơn một
phân hoạch của tập S là một tập hợp các tập con không rỗng rời nhau của S và có S
như là hợp của chúng. Nói một cách khác, tập các tập con Ai , i I (ở đây I là tập
chỉ số) tạo nên một phân hoạch của S nếu và chỉ nếu:
Ai với i I
Ai Aj khi i j và
iI
2.3.1. Định nghĩa: Một phân hoạch cặp của tập hợp A là một họ (Ai)i các
I
∈
tập con của A sao cho
Ai , Ai Aj = (
(
≠ j),
= A.
Như vậy, khi có một quan hệ tương đương trên tập hợp A thì họ gồm tất cả
các lớp tương đương theo quan hệ này tạo thành một phân hoạch cặp của tạp hợp
A.
2.3.2. Mệnh đề:
Mỗi phân hoạch cặp của tập hợp A xác định một quan hệ tương đương trên A.
Trang: 8
III. QUAN HỆ THỨ TỰ
Chúng ta thường dùng quan hệ để sắp xếp một số hay tất cả các phần tử của
một tập. Ví du, để sắp xếp các từ chúng ta dùng quan hệ chứa các cắp (x, y) trong
đó x đi trước y trong từ điển. Chúng ta lập lịch thực hiện các dự án bằng cách dùng
quan hệ chứa các cặp (x, y) trong đó x, y là các nhiệm vụ của dữ án sao cho x phản
hoàn toán trước khi y bắt đầu. Chúng ta cũng sắp xếp tập các số nguyên khi dùng
quan hệ chứa các cắp (x, y) trong đó x nhỏ hơn y. Khi đó thêm tất cả các cặp dang
(x, x) vào các quan hệ này chúng ta nhận được quan hệ phản xạ, đối xứng và bắc
cầu. Đó là các tính chất đặc trưng cho các quan hệ dùng để sắp xếp các phần tử của
một tập có dùng kích cỡ tương đối của chúng.
3.1 Định nghĩa 1: QUAN HỆ THỨ TỰ
Một quan hệ trên tập hợp A được gọi là quan hệ thứ tự nếu nó có các tính chất
phản xạ, phản đối xứng và bắc cầu.
Người ta thường ký hiệu một quan hệ thứ tự bởi ký hiệu .
Nếu trên tập hợp A có một quan hệ thứ tự thì ta nói A là một tập hợp được
sắp xếp thứ tự.
Với hai phần tử a, b A (trong đó A được sắp xếp thứ tự bởi quan hệ thứ tự
), nếu ta có a b thì ta còn viết b a.
Khi có quan hệ thứ tự trên A, ta có thể xác định quan hệ < như sau:
a, b A, a < b
a b và a ≠ b.
Nếu có a < b, ta còn viết b > a.
Ta có thể mô tả việc sắp xếp thứ tự một tập hữu hạn A (với quan hệ thứ tự )
bằng một biểu đồ gọi là biểu đồ Hasse. Đó là biểu đồ biểu diễn các phần tử của A
bởi các dấu chấm và nếu có a b (a, b A) thì nối a với b bởi một đoạn thẳng từ
dưới lên trên.
Ví dụ 1. Quan hệ thông thường trên các tập hợp số là quan hệ thứ
tự.
Ví dụ 2. Quan hệ "chia hết" trên tập hợp * là một quan hệ thứ tự.
Trang: 9
Ví dụ 3. Quan hệ "bao hàm" trên tập hợp P(X) các tập con của tập hợp X là
một quan hệ thứ tự.
3.2 Định nghĩa 2: QUAN HỆ THỨ TỰ TOÀN PHẦN
Cho A là tập hợp được sắp xếp thứ tự (bởi quan hệ ). Với hai phần tử a, b
A, nếu ta có a b hoặc b a thì ta nói a và b so sánh được với nhau, còn nếu ta
không có cả a b lẫn b a thì ta nói a và b không so sánh được với nhau.
Tập hợp được sắp thứ tự A gọi là một tập hợp được sắp thứ tự toàn phần nếu
hai phần tử bất kỳ a, b A luôn có thể so sánh được với nhau. Khi đó ta cũng gọi
quan hệ thứ tự là một quan hệ thứ tự toàn phần.
Trong trường hợp ngược lại, tức là nếu tồn tại hai phần tử a, b A không so
sánh được với nhau thì ta gọi A là một tập hợp được sắp thứ tự bộ phận và quan hệ
thứ tự là một quan hệ bộ phận.
Ví dụ 1: Quan hệ thứ tự thông thường trên tập hợp
một quan hệ thứ thự toàn phần.
các số tự nhiên là
Ví dụ 2: Tập hợp * các số tự nhiên khác không với quan hệ thứ tự "chia
hết" là một tập hợp được sắp thứ tự bộ phận, vì chẳng hạn, ta không có 2|3 và cũng
không có 3|2.
Ví dụ 3: Quan hệ "bao hàm" trong tập hợp P(X) các tập con của tập hợp X,
trong đó |X| > 1, là một quan hệ thứ tự bộ phận, vì chẳng hạn, với x, y X, x y,
ta có hai phần tử {x} và {y} của P(X) không so sánh được với nhau.
Với X= hoặc X= {x}, ta dễ nhận thấy P(X) được sắp thứ tự toàn phần bởi
quan hệ .
3.3 Định nghĩa 3: PHẦN TỬ LỚN NHẤT (NHỎ NHẤT)
Cho tập hợp được sắp thứ tự A bởi quan hệ và X là một tập con khác rỗng
của A. Phần tử a X được gọi là phần tử lớn nhất (t.ư. nhỏ nhất) của X nếu với
mọi x X ta có x a (t.ư. x a).
Phân tử lớn nhất (t.ư nhỏ nhất) của X nếu tồn tại duy nhất. Thật vậy nếu a và
b là hai phần tử lớn nhất (t.ư nhỏ nhất) của X thì theo định nghĩa ta có a b, b a;
theo tính chất phản đối xứng của , ta có a = b.
Trang: 10
Ví dụ:
i) Xét tập hợp N các số tự nhiên với quan hệ thông thường. Khi đó
phần tử nhỏ nhất là 0 và không có phần tử lớn nhất.
có
Xét tập con X= {10, 15, 1, 4, 9, 22, 11} của N. Khi đó phần tử nhỏ nhất của X
là 1 và phần tử lớn nhất là 22.
ii) Xét tập hợp * các số tự nhiên khác không được sắp thứ tự bởi quan hệ
"chia hết". Khi đó 1 là phần tử nhỏ nhất (vì 1|a, a N*) và không có phần tử lớn
nhất.
Xét X= {2, 3, 6, 8, 12, 24}
*. Khi đó X có phần tử lớn nhất là 24 và
không có phần tử nhỏ nhất.
iii) Cho X là một tập hợp. Xét tập hợp P(X) gồm các tập con của X được sắp
thứ tự bởi quan hệ "bao hàm". Khi đó P(X) có phần tử nhỏ nhất là và phần tử lớn
nhất là X.
3.4 Định nghĩa 4: CHẶN TRÊN (CHẶN DƢỚI)
Cho tập hợp được sắp thứ tự A bởi quan hệ và X là một tập con khác rỗng
của A. Phần tử c A được gọi là một chặn trên (t.ư. chặn dưới) của X nếu với mọi
x X ta có x c (t.ư. x c). Nếu X có ít nhất một chặn trên (t.ư. chặn dưới) thì ta
nói X là tập con bị chặn trên (t.ư. bị chặn dưới).
Một tập con X của tập hợp được sắp thứ tự A có thể không có chặn trên (t.ư.
chặn dưới), cũng có thể có một hay nhiều chặn trên (t.ư. chặn dưới).
Với X là một tập con của tập hợp được sắp thứ tự A và a X. Phần tử a là
phần tử lớn nhất (t.ư. nhỏ nhất) của X khi và chỉ khi a là một đoạn chặn trên (t.ư.
chăn dưới) của X.
Ví dụ :
i) Xét tập hợp được sắp thứ tự bởi quan hệ thông thường và X= {6, 8, 4, 9,
45, 10, 7, 12}
nhiên x 45 là các chặn trên của X.
ii) Xét tập hợp các số hữu tỉ không âm với quan hệ thứ tự thông thường
X= {1/n n *}
. Khi đó các số 0, 1, 2, 3 là các chặn dưới của X và các số tự
. Khi đó 0 là chặn dưới duy nhất của X mà không là phần
Trang: 11
tử nhỏ nhất của X và các số hữu tỉ x 1 là các chặn trên của X mà 1 là phần tử lớn
nhất của X.
iii) Xét tập hợp * được sắp thứ tự bởi quan hệ "chia hết" và X= {2, 4, 6, 8,
12}
*. Khi đó các số 1, 2 là các chặn dưới của X và các số x
* sao cho x
là bội chung của 2, 4, 6, 8, 12 là các chặn trên của X.
3.5 Định nghĩa 5: CÂN TRÊN, CẬN DƢỚI
Cho tập hợp được sắp thứ tự A bởi quan hệ và X là một tập con khác rỗng
của A. Phần tử nhỏ nhất (t.ư lớn nhất) của tập hợp các chặn trên (t.ư. chặn dưới)
của X được gọi là cận trên (t.ư. cận dưới) của X trong A, ký hiệu
(t.ư.
) .
Như vậy phần tử a A là cận trên (t.ư. cận dưới) của tập con X của A khi và
chỉ khi a là một chặn trên (t.ư. chạn dưới) của A và a c (t.ư. a c) với mọi chặn
trên (t.ư. chạn dưới) c của X.
Cận trên (t.ư. cận dưới) của mỗi tập con X của tập hợp được sắp thứ tự A nếu
tồn tại là duy nhất. Ngoài ra, cận trên (t.ư. cận dưới) của X là thuộc X khi và chỉ
khi nó là phần tử lớn nhất (t.ư. nhỏ nhất) của X.
Ví dụ:
i) Xét tập hợp được sắp thứ tự bởi quan hệ thông thường và X= {x
|
n
1
1 < x < 2} = (1, 2)
và X' = 1
| n N*
. Khi đó, tập hợp các chặn
n
trên của X là [2, + ) và của X' là [e, + ), tạp hợp các chặn dưới của X là (- , 1]
và của X' là (- ,2]. Do đó
= 2,
,
= 1,
= 2 ( X').
ii) Xét tập hợp * được sắp thứ tự bởi quan hệ "chia hết" và X= {2, 3, 6, 8}.
Khi đó tập hợp các chặn trên của X là các bội chung trong * của 2, 3, 6, 8 và tập
hợp các chặn dưới của X là các ước chung trong N* của 2, 3, 6, 8. Do đó
BCNN(2, 3, 6, 8) = 24 và = UCLN(2, 3, 6, 8) = 1.
iii) Xét tập hợp P(X) được sắp thứ tự bởi quan hệ "bao hàm" và X= {A1, A2,...
=
An} P(X). Khi đó
=
và
=
.
Trang: 12
3.6 Định nghĩa 6: PHẦN TỬ TỐI ĐẠI (TỐI TIỂU)
Cho tập hợp được sắp thứ tự A bởi quan hệ và X là một tập con khác rỗng
của A. Phần tử m X được gọi là phần tử tối đại (t.ư. tối tiểu) của X nếu với mọi x
X ta có:
m x x = m (t.ư. x m x = m),
tức là không tồn tại phần tử x nào của X sao cho x > m (t.ư. x < m).
Rõ ràng phần tử tối đại (t.ư. tối tiểu) m của A sao cho m X cũng là phần tử
tối đại (t.ư. tối tiểu) của X. Tuy nhiên, nếu m là phần tử tối đại (t.ư. tối tiểu) của X
thì chưa chắc m là phần tử tối đại (t.ư. tối tiểu) của A.
Phần tử tối đại (t.ư. tối tiểu) của một tập hợp có thể không có và nếu tồn tại,
có thể có hơn 1.
3.7. Mệnh đề:
Cho tập hợp được sắp thứ tự A bởi quan hệ và X là một tập con khác rỗng
của A. Khi đó:
i) Nếu X có phần tử lớn nhất (t.ư. nhỏ nhất) là a thì a là phần tử tối đại (t.ư. tối
tiểu) duy nhất của X.
ii) Nếu X được sắp thứ tự toàn phần bởi quan hệ thì phần tử a X là phần
tử lớn nhất (t.ư. nhỏ nhất) của X khi và chỉ khi a là phần tử tối đại (t.ư. tối tiểu) của
X.
Ví dụ:
*
i) Tập hợp
với quan hệ "chia hết" có phần tử tối tiểu duy nhất là 1, đó cũng
là phần tử nhỏ nhất của * , không tồn tại phần tử tối đại.
*
*
Tập con X =
\ {1} của
có các phần tử tối tiểu là các số nguyên tố và
không có phần tử tối đại.
*
Tập con X' = {2, 3, 4, 6, 9, 12, 19, 24} của
có các phần tử tối tiểu là 2, 3,
19 và các phần tử tối đại là 9, 19, 24.
ii) cho tập hợp X= {x1, x2, ..., xn}. Xét tập hợp A= P(X) \ {
với quan hệ
"bao hàm". Khi đó A có các phần tử tối tiểu là các tập con 1 phần tử: { x1}, { x2},
Trang: 13
... , { xn} và có các phần tử tối đại là các tập con n - 1 phần tử: {x2, x3, ..., xn}, {x1,
x3, ..., xn}, ... , {x1, x2, ..., xn-1}.
3.8. Định nghĩa: Cho tập hợp được sắp thứ thự A bởi quan hệ . Ta nói A
được sắp thứ tự tốt bởi quan hệ này nếu mọi tập con khác rỗng của A đểu có phần
tử nhỏ nhất.
3.9. Hệ quả: Nếu một tập hợp được sắp thứ tự tốt bởi một quan hệ nào đó thì
nó được sắp thứ tự toàn phần bởi quan hệ đó.
Ví dụ:
i) Tập hợp được sắp thứ tự tốt bởi quan hệ thông thường.
*
ii) Tập hợp
không được sắp thứ tự tốt bởi quan hệ "chia hết".
iii) Các tập hợp không được sắp thứ tự tốt bởi quan hệ
thường.
thông
3.10. Định nghĩa: Tập hợp được sắp thứ tự A được gọi là một dàn nếu với hai
phần tử bất kỳ a, b A, tập hợp {a, b} luôn có cận trên và cận dưới. Cận trên và
cận dưới của {a, b} lần lượt được ký hiệu a b và a b
3.11. Tính chất: Cho A là một dàn. Khi đó với mọi a, b, c A, ta có:
i) Luật lũy đẳng: a a a,a a a
ii) Luật giao hoán: a b = b a, a b = b a
.
.
.
a b c a (b c), a b c a (b c)
iii) Luật kết hợp:
.
iiii) Luật hấp thụ: a (a b) a,a (a b) a
.
Ví dụ:
*
i) Tập hợp
với quan hệ chia hết là một dàn vì với mọi m, n
* , ta có
m n
m n
là UCLN(m, n).
là BCNN(m, n) và
ii) tập hợp P(X) với qua hệ "bao hàm" là một dàn vì với mọi A, B P(X), ta
A B
A
A B
A
là .
có
là
và
3.12. Bổ đề Zore:
Nếu tập hợp khác rỗng X được sắp thứ tự quy nạp nghĩa là mọi tập con được
sắp thứ tự toàn phần của nó đều có chặn trên thì X có phần tử tối đại.
Trang: 14
PHẦN II: MỘT SỐ BÀI TẬP VẬN DỤNG
I. BÀI TẬP MINH HỌA CÁC TÍNH CHẤT CỦA QUAN HỆ
Bài 1:
Cho S={0, 1, 2, 3}
Quan hệ “thứ tự nhỏ” trên S được xác định bởi tập: L ={ (0,1), (0,2), (0,3), (1, 2),
(1, 3), (2,3)}
Quan hệ “bằng” được xác định trên S bởi tập: E = { (0, 0), (1, 1), (2, 2), (3, 3)}
Quan hệ “chẵn lẻ” trên S được xác định bởi: P = {(0,0), (1, 1), (2, 2), (3, 3), (0,
2), (2, 0), (1, 3), (3, 1)}
Giải:
* Tính phản xạ:
Quan hệ L không có tính phản xạ vì cặp (0,0)
L.
Quan hệ E và P có tính phản xạ vì tất cả các cặp dạng (a, a), cụ thể (0, 0),
(1, 1),(2, 2),(3,3) đều
* Tính đối xứng:
E và P
Quan hệ L là không đối xứng vì trong mỗi trường hợp (a, b) thuộc quan hệ
nhưng không có (b, a) thuộc quan hệ.
Quan hệ E và P là đối xứng vì có cặp (a, b) thuộc quan hệ thì có (b, a)
thuộc quan hệ.
* Tính phản xứng:
Quan hệ E có tính phản xứng vì vợi mọi a, b thuộc S, (a, b) thuộc E và (b,
a) thuộc L có a=b.
Quan hệ P không có tính phản xứng vì có cặp ( 0, 2) thuộc P và (2, 0)
thuộc P nhưng 0
Quan hệ L không có tính phản xứng vì có cặp ( a, b) thuộc L và (b, a)
thuộc L mà a = b.
* Tính bắc cầu:
Quan hệ L có tính bắc cầu vì có (0, 1) (1, 2) thuộc L có (0, 2) thuộc L.
Quan hệ E không có tính bắc cầu vì không có (a, b) (b,c) thuôc E mà (a, c)
thuộc E.
2.
Trang: 15
Quan hệ P có tính bắc cầu vì tồn tại (1, 3), ( 3, 1) thuộc P và (1,1) cũng
thuộc P.
Bài 2: Cho tập {1, 2 , 3, 4} xét các quan hệ sau:
R1= {(1,1),(1,2),(2,1)(2,2),(3,4),(4,1),(4,4)}
R2 = {{1,1),(1,2),(2,1)}
R3 = {(1,1), (1,2), (1,4)(2,1), (2,2), (3,3), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (44)}
R6 = {(3,4)}
Giải:
* Tính phản xạ:
Quan hệ R3 có tính phản xạ vì tất cả các cặp dạng (a, a), cụ thể là: (1,1), (2,
2), (3, 3), (4, 4) đều thuộc R3 .
Tương tự, quan hệ R5 cũng có tính phản xạ.
Quan hệ R1 không có tính phản xạ vì cặp (3, 3) không thuộc R1.
Tương tự, các quan hệ R2, R4, R6 cũng không có tính phản xạ.
* Tính đối xứng :
Các quan hệ R2, R3 là đối xứng vì trong mỗi trường hợp (a, b) thuộc quan
hệ thì đều có (b, a) thuộc quan hệ.
Quan hệ R1 không đối xứng vì có cặp (3, 4) thuộc R1 nhưng (4, 3) không
thuộc R1.
Tương tự, dễ dàng kiểm ta các quan hệ còn lại cũng không có tính đối xứng
bằng cách tìm một cặp (a, b) thuộc quan hệ nhưng (b, a) không thuộc quan hệ đó.
*Tính phản xứng:
Quan hệ R1 không phản xứng vì có cặp (1, 2) và (2, 1) thuộc R1 nhưng 1 ≠ 2
Tương tự R2 không phản xứng.
Quan hệ R3, R4, R6 không phản xứng.
Quan hệ R5 là phản xứng.
* Tính bắc cầu:
Trang: 16
Quan hệ R1 không có tính bắc cầu vì (3, 4) và (4, 1) thuộc R1 nhưng (3, 1)
không thuộc R1.
Quan hệ R4 có tính bắc cầu vì (3, 2) và (2, 1) thuộc R4 thì (3, 1) cũng thuộc
R4.
Tương tự, (4, 2), (2, 1), (4, 1) và (4, 3), (3, 1), (4, 1) thuộc R4.
Quan hệ R2, R3, R5, R6 không có tính bắc cầu.
Bài 3: Quan hệ “chia hết” trên tập các số tự nhiên.
Giải:
* Tính phản xạ:
Vì a|a với mọi a là số tự nhiên nên quan hệ “chia hết” có tính phản xạ.
* Tính phản xứng:
Vì với mọi là số tự nhiên a, b, nếu a| b và b|a thì ta có a = b. Do đó quan hệ
chia hết trên tập các số nguyên dương có tính phản xứng.
* Tính đối xứng:
Không có tinh đối xứng
* Tính bắc cầu:
Vì tồn tại a, b, c thuộc số tự nhiên , giả sử aRb và bRc a|b và b|c=>
a|c=>aRc, nên có tính bác cầu
Bài 4: Cho R là quan hệ trên tập số thực : aRb nếu a<= b
Giải:
* Tính phản xạ: Tính phản xạ.
* Tính phản xứng: Tính phản xứng.
* Tính đối xứng: Không có tinh đối xứng
* Tính bắc cầu:
Có tính bắc cầu
Bài 5:
Cho A={ 1, 2, 3, 4), quan hệ R trên A, a, b A, aRb
a-b 3
Giải:
* Tính phản xạ:
Vì a A ta có a- a=0 3, nên có tính phản xạ
* Tính đối xứng:
Trang: 17
Vì
a, b A, giả sử aRb => a-b 3 => b-a= -(a-b) 3 => bRa, nên có tính
đối xứng
* Tính phản xứng:
R không phản xứng vì lấy a=1, b=4 đều thuộc A ta có 1R4 và 4R1 nhưng
1
4.
* Tính bắc cầu:
Vì a, b, c A, giả sử aRb bRc => a-b 3 và b- c 3
Ta có: (a-b)+(b-c)= (a-c) 3 => aRc, nên có tính bắc cầu.
II. MÔT SỐ BÀI TẬP QUAN HỆ TƢƠNG ĐƢƠNG
Bài 1. Cho R là một quan hệ trên tập số thực sao cho aRb nếu và chỉ nếu (a - b) là
một số nguyên. R có là một quan hệ tương đương không?
Giải: Vì a – a = 0 là một số nguyên với một số thực a, nên R là phản xạ.
Giải sử rằng aRb. Khi đó (a – b) là một số nguyên và (b – a ) cũng là một số
nguyên. Vậy bRa nên R là đối xứng.
Nếu aRb và bRc thì (a – b) và (b – c) là các số nguyên.
Khi đó a – c = (a – b) + (b – c) cũng là số nguyên. Vậy aRc, tức R là bắc cầu
Do đó, R là quan hệ tương đương.
Bài 2. Đồng dư theo môdun m. Cho m là một số nguyên dương lớn hơn 1. Chứng
minh rằng quan hệ
R = {(a, b) | a b (mod m)} là một quan hệ tương đương trên tập số nguyên.
Giải: Ta biết rằng a b (mod m) nếu và chỉ nếu (a – b) chia hết cho m.
Mà a – a = 0 chia hết cho m, vì 0 = 0.m, nên a a (mod m), vậy R là phản xạ
Gia sử a b (mod m), khi đó (a – b) chia hết cho m, nghĩa là a – b = km,
với k là một số nguyên. Từ đó suy ra (b – a) = - km, vậy b a (mod m), vậy R là
đối xứng.
Giả thuyết rằng a b (mod m) và b c (mod m). Khi đố (a – b) và (b – c)
đều chia hết cho m.
Do đó, tồn tại số nguyên k và l sao cho (a – b) = km và (b – c) = lm.
Cộng 2 phương trình trên ta được: a – c = km + lm = (k+l)m
Suy ra a c (mod m). Do đó, R có tính bắc cầu
Trang: 18
Tải về để xem bản đầy đủ
29 trang
29/03/2022
9520
Bạn đang xem 20 trang mẫu của tài liệu "Tiểu luận Cơ sở toán tin học - Đề tài: Tìm hiểu quan hệ và ứng dụng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tieu_luan_co_so_toan_tin_hoc_de_tai_tim_hieu_quan_he_va_ung.pdf
