zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Chương 4: Quan hệ

Chia sẻ: Bach Thanh Trung | Ngày: | Loại File: PDF | Số trang:4

Báo xấu

241
lượt xem 14
download

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

R được gọi là một quan hệ hai ngôi trên tập E nếu R la một tập hợp con của tích Descarte E x E

Chủ đề:

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

Lưu

Nội dung Text: Chương 4: Quan hệ

Chöông 4. Quan heä 4. QUAN HEÄ 4.1. ÑÒNH NGHÓA & TÍNH CHAÁT. 4.1.1. ÑÒNH NGHÓA . ℜ Ñöôïc goïi laø moät QUAN HEÄ hai ngoâi treân taäp E neáu ℜ laø moät taäp con cuûa tích Descartes E x E. Phaàn töû a ñöôïc goïi laø coù quan heä ℜ vôùi phaàn töû b khi (a,b) ∈ ℜ, Kyù hieäu a ℜ b, neáu khoâng, ta ghi a ⎯ℜ b. Thí duï. Cho E ={1,2,3}. ℜ = {(1,1), (1,3),(2,3)}. Ta coù 1 ℜ 3 nhöng 3⎯ℜ 1. 4.1.2. TÍNH CHAÁT. Tính phaûn xaï : ∀ a ∈ E , a ℜ a. Ñoái xöùng : ∀ a, b ∈ E, Neáu a ℜ b thì b ℜ a Phaûn (Ñoái) xöùng : ∀ a, b ∈ E, Neáu a ℜ b vaø b ℜ a thì a= b. Baéc caàu (truyeàn) : ∀ a, b, c ∈ E, Neáu a ℜ b vaø b ℜ c thì a ℜ c. 4.1.3. BIEÅU DIEÃN. Ngoaøi phöông phaùp bieåu dieãn moät Quan heä 2 ngoâi treân moät taäp hôïp höõu haïn, ngöôøi ta coøn coù theå söû duïng ma traän ñeå bieåu dieãn cho Quan heä. Giaû söû ℜ laø moät Quan heä 2 ngoâi treân moät taäp hôïp höõu haïn E = {x1, x2,…,xn}. Quan heä ℜ coù theå ñöôïc bieåu dieãn bôûi ma traän Eℜ = [eij], trong ñoù eij = 1 neáu (xi,xj) ∈ ℜ eij = 0 neáu (xi,xj) ∉ ℜ Thí duï. Vôùi hai quan heä ℜ1 = {(1,1), (1,2),(1,3)} vaø ℜ2 = {(1,1), 1,2),(1,3),(2,2),(2,3),(3,3)}, ta coù ma traän bieåu dieãn nhö sau: 111 111 Aℜ1 Aℜ2 =0 00 = 011 000 001 Tröông Myõ Dung 28
Chöông 4. Quan heä 4.2. QUAN HEÄ TÖÔNG ÑÖÔNG. 4.2.1. ÑÒNH NGHÓA ℜ ñöôïc goïi laø moät QUAN HEÄ TÖÔNG ÑÖÔNG khi ℜ coù tính phaûn xaï, ñoái xöùng vaø baéc caàu. 4.2.2. LÔÙP TÖÔNG ÑÖÔNG. Khi ℜ laø moät quan heä töông ñöông treân E, vaø x ∈ E, ta goïi LÔÙP TÖÔNG ÑÖÔNG chöùa x laø taäp con x = {y ∈ E: y ℜ x}. 4.2.3. TÍNH CHAÁT. x ∈ x, suy ra x ≠ ∅. y ∈ x thì y = x: Lôùp töông ñöông khoâng phuï thuoäc phaàn töû ñaïi dieän. y ∩ x ≠ ∅ ⇔ y = x. Söu taäp caùc lôùp töông ñöông khaùc nhau seõ taïo neân moät phaân hoaïch cuûa taäp E. 4.3. QUAN HEÄ THÖÙ TÖÏ. 4.3.1. ÑÒNH NGHÓA. Moät QUAN HEÄ THÖÙ TÖÏ treân E, kyù hieäu ≤ laø moät quan heä coù tính chaát phaûn xaï, phaûn ñoái xöùng vaø baét caàu. Luùc ñoù (E,≤) laø taäp coù thöù töï. Khi x ≤ y : y laø moät troäi cuûa x (y lôùn hôn x). y laø moät troäi tröïc tieáp (keà treân) cuûa x neáu x ≤ y vaø y ≠ x, khoâng coù troäi naøo naèm giöõa x vaø y : x ≤ z ≤y thì x= z hoaëc y=z. Bieåu ñoà HASSE. Ta duøng ñoà thò coù ñònh höôùng coù ruùt goïn ñeå bieåu dieãn cho moät quan heä. x y QUAN HEÄ THÖÙ TÖÏ TOAØN PHAÀN. Khi aáy, bieåu ñoà HASSE coù daïng daây chuyeàn: ∀ x, y ∈ E, ta coù x ≤ y hay y ≤ x. Cho (E,≤) laø moät taäp hôïp coù thöù töï, vaø A ⊆ E, x ∈ E x laø CHAÄN DÖÔÙI cuûa A neáu vaø chæ neáu ∀ a ∈ A : x ≤ a. CHAÄN DÖÔÙI LÔÙN NHAÁT cuûa A, kyù hieäu Inf (A) laø phaàn töû lôùn nhaát trong taäp hôïp taát caû nhöõng chaän döôùi cuûa A. Töông töï, ta coù ñònh nghóa cho CHAÄN TREÂN NHOÛ NHAÁT, Supp(A). 4.3.2. ÑINH LYÙ. Max (A) neáu coù thì duy nhaát vaø cuõng laø phaàn töû Supp(A) duy nhaát. Tröông Myõ Dung 29
Chöông 4. Quan heä 4.3.3. ÑINH LYÙ. Cho (E, ≤) laø taäp thöù töï höõu haïn. Ta coù: Trong E coù ít nhaát moät phaàn töû toái tieåu (toái ñaïi). Neáu E toàn taïi moät phaàn töû toái tieåu (toái ñaïi) duy nhaát thì phaàn töû ñoù chính laø phaàn töû nhaát töû nhoû nhaát (lôùn nhaát) cuûa E. 4.4. DAØN (LATTICE) . 4.4.1. ÑÒNH NGHÓA. Cho (L, ≤) laø taäp hôïp coù thöù töï. L ñöôïc goïi laø moät DAØN neáu vaø chæ neáu: ∀ a, b ∈ L coù chaän döôùi lôùn nhaát vaø chaän treân nhoû nhaát (töùc laø coù toàn taïi Supp(a, b) vaø Inf(a,b). 4.4.2. ÑÒNH LYÙ Moïi taäp coù thöù töï toaøn phaàn laø moät DAØN. 4.4.3. TÍNH CHAÁT Luõy ñaúng : Supp(a, a) = a Inf (a,a) = a Giao hoaùn: Supp(a, b) = Supp(b, a) Inf (a, b) = Inf (b,a) Keát hôïp : Supp(Supp(a, b),c) = Supp(a, Supp(b,c) Inf(Inf(a, b),c) = Supp(a, Supp(b,c) ( a ≤ b) Supp(a, b) = b ⇔ Inf (a, b) = a ⇔ Inf(a,Supp (a, b)) = a = Supp( a,Inf(a, b)) 4.4.4. ÑÒNH LYÙ Moïi DAØN höõu haïn ñeàu coù phaàn töû lôùn nhaát, phaàn töû beù nhaát. 4.4.5. ÑÒNH NGHÓA. Cho (L,≤) laø moät DAØN vaø B laø taäp con cuûa L. Ta noùi B laø DAØN CON cuûa L khi vaø chæ khi ∀ a, b ∈ B, ta coù Supp(a, b) vaø Inf( a, b) ∈ B. 4.4.6. ÑÒNH NGHÓA. Moät DAØN ñöôïc goïi laø DAØN phaân boá neáu Supp vaø Inf phaân boá laãn nhau: Supp(x,Inf((y, z)) = Inf(Supp(x, y),Supp(x, z)) Inf(x,Supp(y, z)) = Supp(Inf(x, y),Inf(x, z)) Thí duï. ℘(A) laø moät DAØN phaân boá. DAØN {a, b, c, d} nhö bieåu ñoà khoâng phaûi laø DAØN phaân boá vì: b e Inf(d,Supp (b, c)) = Inf(d, e) = d, Tröông Myõ Dung 30
Chöông 4. Quan heä maø Supp(Inf(d, b),Inf(d, c)) = Supp( a, a) ≠ d. d a c 4.4.7. ÑÒNH NGHÓA. Giaû söû DAØN L coù phaàn töû lôùn nhaát Max(L) (kyù hieäu laø 1) vaø phaàn töû nhoû nhaát Min(L) (kyù hieäu laø 0). Phaàn töû x ∈ L coù PHAÀN BUØ ⎯x ∈ L sao cho Supp(x,⎯x ) = 1 vaø Inf (x,⎯x ) = 0. L laø DAØN buø khi vaø chæ khi moïi phaàn töû cuûa L coù phaàn töû buø. Thí duï. Trong DAØN buø sau ñaây e c Phaàn töû d coù 2 phaàn töû buø. d b a L ={öôùc döông cuûa 75} thì L khoâng phaûi laø daøn buø. Chuù yù. ⎯x laø buø cuûa x thì x cuõng laø buø cuûa ⎯x. Max(L) vaø Min(L) luoân luoân laø buø cuûa nhau. 4.4.8. ÑÒNH NGHÓA. Cho (L,≤) vaø (M,≤) laø 2 DAØN. Moät aùnh xaï f:L → M ñöôïc goïi laø ÑOÀNG CAÁU DAØN neáu vaø chæ neáu: ∀ x, y ∈ L f(Supp(x, y)) = Supp(f(x), f(y)), f(Inf(x, y)) = Inf(f(x), f(y)). Tröôøng hôïp f coù theâm tính song aùnh thì ta noùi f laø moät ÑAÚNG CAÁU DAØN. Thí duï. Cho 2 DAØN L, M coù bieåu ñoà HASSE sau: v 4 Aùnh xaï f: L → M ñöôïc ñònh nghóa bôûi: • e• •u f(1) = b, f(2) = e, f(3) = c, f(4) = v • • 2• •3 b• c •d laø moät ñoàng caáu daøn. Aùnh xaï g: L → M ñöôïc ñònh nghóa bôûi: g(1) = a, g(2) = b, g(3) = d, g(4) = v • • 1 a khoâng phaûi laø ñoàng caáu daøn vì DAØN L DAØN M Supp(g(2), g(3)) = Supp(b,d) = c ≠ v = g(4)=g(Supp(2, 3). Tröông Myõ Dung 31

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.