Bài giảng Toán rời rạc - Chương 6: Quan hệ - Nguyễn Anh Thi

Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Bài giảng môn học Toán Rời Rạc
Nguyễn Anh Thi
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Chương 6
Quan hệ
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Nội dung
1 Quan hệ hai ngôi
2 Quan hệ tương đương.
3 Quan hệ thứ tự.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Quan hệ hai ngôi
Định nghĩa
Một quan hệ hai ngôi R trên tập A 6= ∅ là một tập con khác
rỗng của tập tích A× A.
Khi (x; y) ∈ R, ta ghi xRy, nếu không, ta ghi xRy.
Ví dụ
• A = {1; 2; 3},
R = {(1; 1); (1; 2); (2; 1); (2; 2); (2; 3); (3; 3)}.
Ta có 1R2, 2R1, 2R3, và 3R2
• Quan hệ ” = ” trên một tập hợp A bất kỳ:
(aRb)⇔ a = b
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Quan hệ hai ngôi
Ví dụ
• Quan hệ ” ≤ ” trên Z,Q hay R:
(aRb)⇔ a ≤ b
• Gọi L là tập hợp các đường thẳng trong mặt phẳng. Quan
hệ song song được định nghĩa bởi:
(dRd′)⇔ d//d′
• Quan hệ đồng dư modulo n:
(aRb)⇔ a ≡ b( mod n)
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Tính chất
a. Phản xạ (phản hồi): ∀a ∈ A, aRa.
b. Đối xứng: ∀a, b ∈ A, aRb ⇒ bRa.
c. Phản đối xứng (phản xứng): ∀a, b ∈ A, aRb và bRa suy ra
a = b.
d. Bắc cầu (truyền): ∀a, b, c ∈ A, aRb và bRc suy ra aRc.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Ví dụ
• Quan hệ ” = ” trên một tập hợp bất kỳ, quan hệ ” ≤ ”
trên Z,Q,R, quan hệ đồng dư trên Z là phản xạ.
• Các quan hệ ” =,≡, //” là các quan hệ đối xứng.
• Các quan hệ ” =,≡, //,≤ ” là các quan hệ bắc cầu.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Quan hệ tương đương
Định nghĩa
Quan hệ hai ngôi R trên tập A được gọi là một quan hệ tương
đương khi và chỉ khi R có các tính chất phản xa,ï đối xứng, bắc
cầu.
Ví dụ
Các quan hệ ” =,≡, //” là các quan hệ tương đương.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Định nghĩa
Cho R là một quan hệ tương đương trên A. Lớp tương đương
của phần tử x ∈ A là tập con x = {t ∈ A|tRx}.
Tính chất
i. ∀x ∈ A, x 6= ∅;
ii. z ∈ x ⇒ z = x;
iii. ∀x, y ∈ A, x ∩ y = ∅ hoặc x = y (nghĩa là: x 6= y thì
x ∩ y = ∅).
Định nghĩa
Cho R là một quan hệ tương đương trên A. tập hợp các lớp
tương đương (khác nhau) của A được gọi là tập thương của A
trên R, ký hiệu A/R. Như vậy, phần tử của A/R là một tập con
của A.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Quan hệ đồng dư
Định nghĩa
Cho trước n ∈ N, ta định nghĩa quan hệ đồng dư modulo n (ký
hiệu ∼= (mod n )) trên tập Z, như sau:
x ∼= y(mod n)⇔ n|(x− y)
Định nghĩa
Trên Zn ta định nghĩa một cách tự nhiên các phép toán + và .
như sau:
x+ y = x+ y
x.y = x.y,∀x, y ∈ Zn
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Quan hệ thứ tự
Định nghĩa
Một quan hệ S trên tập A 6= ∅ được gọi là một quan hệ thứ tự
khi và chỉ khi S có các tính chất phản xạ, phản xứng, bắc cầu.
Khi đó A được gọi là một tập được sắp (có thứ tự bộ phận).
Nếu ∀x, y ∈ A, luôn luôn có xSy hoặc ySx thì tập được sắp
(A,S) được gọi là tập thứ tự toàn phần.
Ví dụ
Các quan hệ ≥,≤ (theo nghĩa thông thường) là những quan
hệ thứ tự (toàn phần) trên N,Z,Q,R.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Định nghĩa
Cho (A,S) là một tập được sắp, ∅ 6= B ⊆ A
a. Phần tử M ∈ B là phần tử lớn nhất của B khi và chỉ khi
∀x ∈ B, xSM.
b. Phần tử m ∈ B là phần tử nhỏ nhất của B khi và chỉ khi
∀x ∈ B,mSx.
c. Phần tử a ∈ B là phần tử tối tiểu của B khi và chỉ khi
không có x ∈ B, x 6= a và xSa. (Hay nói cách khác,
∀x ∈ B, xSa ⇒ x = a).
d. Phần tử b ∈ B là phần tử tối đại của B khi và chỉ khi không
có x ∈ B, x 6= b và bSx. (Hay nói cách khác,
∀x ∈ B, bSx ⇒ x = b).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Định lý
Phần tử lớn nhất, phần tử nhỏ nhất của một tập được sắp
(nếu có) là duy nhất.
Nhận xét
Trong một tập được sắp, phần tử lớn nhất (nếu có) sẽ là phần
tử tối đại duy nhất, phần tử nhỏ nhất (nếu có) sẽ là phần tử
tối tiểu duy nhất.
Định lý
(A,S) là tập được sắp hữu hạn thì
a. Mọi phần tử a ∈ A đều bị chận trên bởi một phần tử tối đại,
bị chận dưới bởi một phần tử tối tiểu.
b. A có phần tử tối đại, phần tử tối tiểu.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Định nghĩa
Cho (A,S) là một tập được sắp, khi xSy ta bảo x bị trội bởi y, y
trội x. Khi xSy và không tồn tại z sao cho xSz và zSy, ta nói y
là trội trực tiếp của x.
Định nghĩa
Ta biểu diễn một tập thứ tự (A,S) hữu hạn bởi một giản đồ,
gồm những điểm liên kết với những phần tử của A và những
cung có hướng nối x với y khi y là trội trực tiếp của x; giản đồ
trên được gọi là biểu đồ Hasse.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Ví dụ
Với B = {2, 3, 4, 6, 8, 12, 15} với quan hệ thứ tự chia hết, ta có
biểu đồ Hasse của B như sau:
Ví dụ
Biểu đồ Hasse của (U48, |).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Ví dụ
Biểu đồ Hasse của (U30, |) có dạng lập phương.
Nhận xét
Tập thứ tự (A,S) là tập được sắp thứ tự toàn phần khi và chỉ
khi biểu đồ Hasse của nó có dạng dây xích.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Topo hóa một quan hệ thứ tự bán
phần
Định nghĩa
Cho (A,S) là một tập thứ tự bán phần. Topo hóa T của S là
một quan hệ thứ tự toàn phần trên A sao cho
x, y ∈ A, xSy ⇒ xTy (nghĩa là không có x 6= y sao cho xTy mà
ySx).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Quan hệ hai
ngôi
Quan hệ tương
đương.
Quan hệ thứ
tự.
Nội dung
Quan hệ hai ngôi
Quan hệ tương đương.
Quan hệ thứ tự.
Giải thuật tìm topo hóa T của S
khi A là tập hữu hạn, |A| = n
Ta thực hiện theo các bước sau:
i. Chọn x1 là một phần tử tối tiểu của A.
ii. Chọn x2 là một phần tử tối tiểu của A\{x1}
iii. Sau khi chọn được x1, x2, . . . , xk, ta chọn xk+1 là một phần
tử tối tiểu của A\{x1, x2, . . . , x− k}
Khi đã có dãy x1, x2, . . . , xn, ta đặt xiTxj khi và chỉ khi i ≤ j
Chú ý
Vì có thể có nhiều cách chọn lựa trong mỗi bước, nên sẽ có
nhiều topo hóa khác nhau cho cùng một tập thứ tự.
Ví dụ
Topo hóa tập được sắp A = (U30, |).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc