TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
Bộ môn Ứng dụng tin học
TOÁN RỜI RẠC
Chương 3: QUAN HỆ
GV: Lê Thị Tuyết Nhung
Mục lục I
1Quan hệ hai ngôi
Định nghĩa
Các tính chất quan hệ
Biểu diễn quan hệ
2Quan hệ tương đương
Định nghĩa
Lớp tương đương
Quan hệ đồng dư trên Z
3Quan hệ thứ tự
Phần tử trội
Biểu đồ Hasse
Thứ tự toàn phần
Phần tử cực trị
Chặn trên, chặn dưới
Tuyết Nhung Toán rời rạc Chương 3. Quan hệ 2 / 35
Định nghĩa
Định nghĩa
Một quan hệ hai ngôi từ tập Ađến tập Blà tập con Rcủa tích Descartes A×B.
Quan hệ hai ngôi từ Ađến chính nó được gọi là quan hệ trên A.
Chúng ta sẽ viết aRbthay cho (a,b)∈ R.
Ví dụ. Cho A={a1,a2,a3}và B={b1,b2}. Khi đó
R={(a1,b1),(a1,b2),(a2,b1),(a3,b2)}
là một quan hệ từ Avào B. Quan hệ này được mô tả bằng
Tuyết Nhung Toán rời rạc Chương 3. Quan hệ 3 / 35
Quan hệ hai ngôi
Ví dụ. Cho A={1,2,3,4}và R=n(a,b)|alà ước của bo.
Khi đó R=(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)
Tuyết Nhung Toán rời rạc Chương 3. Quan hệ 4 / 35
Các tính chất quan hệ
Định nghĩa
Quan hệ Rtrên Ađược gọi là phản xạ nếu
∀a∈A, aRa
Ví dụ. Trên tập A={1,2,3,4}.
Quan hệ R1=(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)không phản xạ
vì (3,3) /∈ R1.
Quan hệ R2=(1,1),(1,2),(1,4),(2,2),(3,3),(4,1),(4,4)phản xạ vì
(1,1),(2,2),(3,3) ∈ R2.
Tuyết Nhung Toán rời rạc Chương 3. Quan hệ 5 / 35