Tiểu luận môn Cơ sở Toán tin học: Tìm hiểu quan hệ và ứng dụng

Chia sẻ: Cao Chi Hien Hien | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST

Báo xấu

119
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tiểu luận môn Cơ sở Toán tin học: Tìm hiểu quan hệ và ứng dụng với các nội dung quan hệ và các tính chất của nó; quan hệ tương đương; quan hệ thứ tự; ứng dụng của quan hệ. Để nắm chi tiết nội dung nghiên cứu, mời các bạn cùng tham khảo tiểu luận.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tiểu luận môn Cơ sở Toán tin học: 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ị Thụy + Nguyễn Thị Thảo + Đào Thị 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.2 ÁNH XÃ CŨNG NHƢ MỘT QUAN HỆ (HÀM CŨNG LÀ MỘT QUAN HỆ) ........... 3 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.3 Định nghĩa 3: PHẦN TỬ LỚN NHẤT (NHỎ NHẤT) ................................................... 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 I. BÀI TẬP MINH HỌA CÁC TÍNH CHẤT CỦA QUAN HỆ .......................................... 15 II. MÔT SỐ BÀI TẬP QUAN HỆ TƢƠNG ĐƢƠNG ......................................................... 18 III. MỘT SỐ BÀI TẬP QUAN HỆ THỨ TỰ ...................................................................... 20 IV. MỘT SỐ BÀI TẬP QUAN HỆ TUẦN TỰ - DÀN ......................................................... 23 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 Tạo bao đóng bắc cầu.............................................................................................................. 26 TÀI LIỆU THAM KHẢO .......................................................................................................... 27
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 của 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 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 y (modn). 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ó n 2 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ó 9 2n tập con. Vì cậy có 2n quan hệ trên tập n phần tử. Víu dụ 23 = 2 = 512 quan hệ 2 2 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 có 3 tính chất: phản xạ, đối xứng, bắc cầu. * 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 R 1 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 =RnoR 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 R n  R với mọi n  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)  x | 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, [a] R = A a A 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à Ai  S iI 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 ∈I các 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 các số tự nhiên là một quan hệ thứ thự toàn phần. 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 đó có phần tử nhỏ nhất là 0 và không có phần tử lớn nhất. 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} . Khi đó các số 0, 1, 2, 3 là các chặn dưới của X và các số tự 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 đó 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 |  1 n  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ử: { x 1}, { 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 . iii) Luật kết hợp:  a  b   c  a  (b  c),  a  b   c  a  (b  c) . 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 là BCNN(m, n) và m  n là UCLN(m, n). 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 có A  B là A B và A  B là A B . 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  E và P * Tính đối xứng: 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  2. 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. 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
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