Bài giảng môn Toán tin - Chương 2: Quan hệ

Bài giảng môn "Toán tin - Chương 2: Quan hệ" trình bày các nội dung: Định nghĩa và tính chất của quan hệ, biểu diễn quan hệ, quan hệ tương đương và quan hệ đồng dư, quan hệ thứ tự. Hi vọng đây sẽ là một tài liệu tham khảo hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu tham khảo phục vụ học tập và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng môn Toán tin - Chương 2: Quan hệ 21. Định nghĩa và tính chất2. Biểu diễn quan hệ3. Quan hệ tương đương. Đồng dư4. Quan hệ thứ tự. 3Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích Descartes R  A x B.Chúng ta sẽ viết a R b thay cho (a, b)  RQuan hệ từ A đến chính nó được gọi là quan hệ trên A R = { (a1, b1), (a1, b3), (a3, b3) } 4A = tập sinh viên; B = các lớp học. R = {(a, b) | sinh viên a học lớp b} 5Cho A = {1, 2, 3, 4}, và R = {(a, b) | a là ước của b}Khi đó R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)} 1 2 3 4 1 2 3 4Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu: (a, a)  R với mọi a  AVí 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 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), (4, 4)  R2 6 Quan hệ  trên Z phản xạ vì a  a với mọi a Z Quan hệ > trên Z không phản xạ vì 1 > 1 7 8Quan hệ R trên A được gọi là đối xứng nếu: a  A b  A (a R b)  (b R a)Quan hệ R được gọi là phản xứng nếu  a  A b  A (a R b)  (b R a)  (a = b)Ví dụ. Quan hệ R1 = {(1,1), (1,2), (2,1)} trên tập A = {1, 2, 3, 4} là đối xứng Quan hệ  trên Z không đối xứng.Tuy nhiên nó phản xứng vì (a  b)  (b  a)  (a = b) 9Định nghĩa. Quan hệ R trên A có tính bắc cầu nếu a  A b  A c  A (a R b)  (b R c)  (a R c)Ví dụ.Quan hệ R = {(1,1), (1,2), (2,1), (2, 2), (1, 3), (2, 3)}trên tập A = {1, 2, 3, 4} có tính bắc cầu.Quan hệ  và “|”trên Z có tính bắc cầu (a  b)  (b  c)  (a  c) (a | b)  (b | c)  (a | c) 101. Ma trận2. Biểu diễn Quan hệ 11 Cho R là quan hệ từ A = {1,2,3,4} đến B = {u,v,w}: R = {(1,u),(1,v),(2,w),(3,w),(4,u)}. Khi đó R có thể biễu diễn như sau u v w 1 1 1 0 2 0 0 1 3 0 0 1 4 1 0 0Đây là ma trận cấp 4×3 biễu diễn cho quan hệ R Định nghĩa. Cho R là quan hệ từ A = {a1, a2, …, am} đến B = {b1, b2, …, bn}. Ma trận biểu diễn của R là ma trận cấp m × n MR = [mij] xác định bởi 0 nếu (ai , bj)  R mij = 1 nếu (ai , bj)  R 1 2Ví dụ. Nếu R là quan hệ từ A = {1, 2, 3} đến B = {1, 2} sao cho a R b 1 0 0 nếu a > b. 2 1 0 Khi đó ma trận biểu diễn của R là 3 1 1 12 13Biểu diễn Quan hệ 1 nếu (ai , bj)  R mij = 0 nếu (ai , bj)  RVí dụ. Cho R là quan hệ từ A = {a1, a2, a3} đếnB = {b1, b2, b3, b4, b5} được biễu diễn bởi ma trận b1 b2 b3 b4 b5 a1 0 1 0 0 0  a2 M  1 0 1 1 0 a3 R   1 0 1 0 1Khi đó R gồm các cặp:{(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)} 14 Cho R là quan hệ trên tập A, khi đó MR là ma trận vuông. R là phản xạ nếu tất cả các phần tử trên đường chéo của MR đều bằng1: mii = 1 với mọi i u v w u 1 1 0 v 0 1 1 w 0 0 1 15R là đối xứng nếu MR là đối xứng mij = mji u v w u 1 0 1 v 0 0 1 w 1 1 0 16R là phản xứng nếu MR thỏa: mij = 0 hoặc mji = ...