Tài liệu Mô hình dữ liệu dạng khối mờ

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 TRỊNH NGỌC TRÚC MÔ HÌNH DỮ LIỆU DẠNG KHỐI MỜ LUẬN VĂN THẠC SĨ MÁY TÍNH HÀ NỘI, 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 TRỊNH NGỌC TRÚC MÔ HÌNH DỮ LIỆU DẠNG KHỐI MỜ Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ MÁY TÍNH Người hướng dẫn khoa học: PGS.TS Trịnh Đình Thắng HÀ NỘI, 2013 Lêi c¶m ¬n T«i xin bµy tá lßng biÕt ¬n s©u s¾c ®Õn thÇy gi¸o PGS.TS TrÞnh §×nh Th¾ng, ng-êi ®· tËn t×nh h-íng dÉn, gióp ®ì vµ ®éng viªn t«i trong suèt qu¸ tr×nh lµm luËn v¨n. Xin c¸m ¬n tÊt c¶ c¸c thÇy gi¸o, c« gi¸o trong Tr-êng §¹i häc S- ph¹m Hµ Néi 2 ®· t¹o ®iÒu kiÖn hÕt søc ®Ó t«i ®-îc häc tËp vµ hoµn thµnh khãa häc ®-îc thuËn lîi. Xin ch©n thµnh c¶m ¬n c¸c thÇy gi¸o, c« gi¸o ®· trùc tiÕp gi¶ng d¹y vµ mang ®Õn cho t«i niÒm say mª nghiªn cøu khoa häc. T«i xin göi lêi biÕt ¬n ch©n thµnh tíi ®ång nghiÖp, b¹n bÌ, gia ®×nh ®· lu«n t¹o ®iÒu kiÖn, ñng hé vÒ mäi mÆt ®Ó t«i hoµn thµnh luËn v¨n. Hµ Néi, th¸ng 11 n¨m 2013 T¸c gi¶ luËn v¨n TrÞnh Ngäc Tróc LêI cam ®oan T«i xin cam ®oan r»ng kÕt qu¶ nghiªn cøu trong luËn v¨n nµy lµ trung thùc vµ kh«ng trïng lÆp víi c¸c ®Ò tµi kh¸c. T«i còng xin cam ®oan r»ng c¸c th«ng tin trÝch dÉn trong luËn v¨n ®· ®-îc chØ râ nguån gèc. T¸c gi¶ luËn v¨n TrÞnh Ngäc Tróc 3 Môc lôc Trang Më ®Çu 6 1. Lý do chän ®Ò tµi 6 2. NhiÖm vô nghiªn cøu 8 3. Môc ®Ých nghiªn cøu 8 4. §èi t-îng vµ ph¹m vi nghiªn cøu 9 5. Nh÷ng ®ãng gãp míi cña ®Ò tµi 9 6. Ph-¬ng ph¸p nghiªn cøu 9 7. CÊu tróc cña luËn v¨n. 9 Ch-¬ng 1: TËP Mê Vµ M¤ H×NH D÷ LIÖU QUAN HÖ 10 1.1. Giíi thiÖu vÒ TËp mê 10 1.2. Kh¸i niÖm tËp mê (fuzzy set) 10 1.2.1. §Þnh nghÜa tËp mê (Fuzzy set): 11 1.2.2. C¸c phÐp to¸n vÒ tËp mê 13 1.3. Logic mê 19 1.3.1. §Þnh nghÜa mÖnh ®Ò mê 19 1.3.2. C¸c phÐp to¸n trªn logic mê 19 1.4. M« h×nh d÷ liÖu quan hÖ 20 1.4.1. Tæng quan vÒ m« h×nh d÷ liÖu quan hÖ 20 1.4.2. Thuéc tÝnh vµ miÒn thuéc tÝnh 21 1.4.3. Quan hÖ, l-îc ®å quan hÖ 21 1.4.4. Kho¸ cña quan hÖ 22 1.4.5. C¸c phÐp to¸n ®¹i sè quan hÖ 23 1.4.5.1. PhÐp hîp 23 1.4.5.2. PhÐp giao 24 4 1.4.5.3. PhÐp trõ 24 1.4.5.4. TÝch ®Ò c¸c 24 1.4.5.5. PhÐp chiÕu 25 1.4.5.6. PhÐp chän 26 1.4.5.7. PhÐp kÕt nèi 27 1.4.5.8. PhÐp chia 29 1.5. M« h×nh c¬ së d÷ liÖu quan hÖ mê 29 1.5.1. L-îc ®å quan hÖ mê 29 1.5.2. Quan hÖ mê 30 1.5.3. Bé d÷ liÖu 30 CH¦¥NG 2: M¤ H×NH D÷ LIÖU D¹NG KHèI 31 2.1. M« h×nh d÷ liÖu d¹ng khèi 31 2.1.1. Khèi, l-îc ®å khèi 31 2.1.2. L¸t c¾t 32 2.2. §¹i sè quan hÖ trªn khèi 34 2.2.1. PhÐp hîp 35 2.2.2. PhÐp giao 35 2.2.3. PhÐp trõ 35 2.2.4. TÝch §Ò c¸c 35 2.2.5. TÝch §Ò c¸c theo tËp chØ sè 36 2.2.6. PhÐp chiÕu 36 2.2.7. PhÐp chän 37 2.2.8. PhÐp kÕt nèi 37 2.2.9. PhÐp chia 39 Ch-¬ng 3: M« h×nh d÷ liÖu d¹ng khèi mê 39 3.1. Khèi mê, l-îc ®å khèi mê 39 3.2. C¸c phÐp tÝnh trªn khèi mê 44 5 3.2.1. PhÐp chÌn 44 3.2.2. PhÐp lo¹i bá 45 3.2.3. PhÐp söa ®æi 46 3.3. §¹i sè quan hÖ trªn khèi mê 47 3.3.1. PhÐp hîp 47 3.3.2. PhÐp giao 48 3.3.3. PhÐp trõ 48 3.3.4. PhÐp chiÕu 49 3.3.5. PhÐp chän 50 3.4. ThuËt to¸n cµi ®Æt c¸c phÐp to¸n 51 3.4.1. ThuËt to¸n hîp 51 3.4.2. ThuËt to¸n giao 51 3.4.3. ThuËt to¸n trõ 52 3.4.4. ThuËt to¸n chiÕu 52 3.4.5. ThuËt to¸n chän 53 KÕT LUËN 53 Tµi liÖu tham kh¶o 54 6 Më ®Çu 1. Lý do chän ®Ò tµi Trong thêi ®¹i c«ng nghÖ th«ng tin hiÖn nay, thuËt ng÷ c¬ së d÷ liÖu (database) kh«ng cßn xa l¹ víi nh÷ng ng-êi lµm viÖc trong lÜnh vùc tin häc. C¸c øng dông tin häc cã trong mäi lÜnh vùc vµ ngµy cµng cã xu h-íng t¨ng nhanh. Xu h-íng tÝch cùc ®ã kÐo theo ngµy cµng ®«ng ®¶o ng-êi tham gia quan t©m ®Õn thiÕt kÕ x©y dùng c¸c c¬ së d÷ liÖu. HiÖn nay cã nhiÒu m« h×nh c¬ së d÷ liÖu, mçi m« h×nh ®Òu cã -u nh-îc ®iÓm riªng, dùa trªn c¸c m« h×nh c¬ së d÷ liÖu, c¸c h·ng m¸y tÝnh lín ®· x©y dùng c¸c HÖ qu¶n trÞ C¬ së d÷ liÖu cã nhiÒu tÝnh n¨ng rÊt m¹nh. §ã lµ nh÷ng c«ng cô tèt cho ng-êi lËp tr×nh, ®Ó gióp hä x©y dùng nªn c¸c øng dông qu¶n lý ®a d¹ng phôc vô cho mäi yªu cÇu cña c«ng t¸c qu¶n lý vµ ®iÒu hµnh. Tuy nhiªn m« h×nh C¬ së d÷ liÖu quan hÖ (Relational data Model) do E.Codd ®Ò xuÊt tá ra cã nhiÒu -u ®iÓm khi thiÕt kÕ c¸c øng dông, bëi lÏ m« h×nh nµy ®-îc x©y dùng trªn mét c¬ së to¸n häc chÆt chÏ - ®ã lµ lÝ thuyÕt to¸n häc vÒ c¸c quan hÖ cã ¸p dông réng r·i c¸c c«ng cô ®¹i sè vµ logic. Tuy nhiªn, do c¸c quan hÖ cã cÊu tróc ph¼ng (tuyÕn tÝnh) nªn m« h×nh nµy ch-a ®ñ ®¸p øng ®èi víi c¸c øng dông phøc t¹p, c¸c c¬ së d÷ liÖu cã cÊu tróc phi tuyÕn. Trong nh÷ng n¨m gÇn ®©y, viÖc nghiªn cøu nh»m më réng m« h×nh d÷ liÖu quan hÖ ®· ®-îc nhiÒu nhµ khoa häc quan t©m. Theo h-íng nghiªn cøu nµy mét m« h×nh míi ®· ®-îc ®Ò xuÊt, ®ã lµ m« h×nh d÷ liÖu d¹ng khèi, m« h×nh nµy cã thÓ xem lµ mét më réng cña m« h×nh quan hÖ, Víi m« h×nh nµy c¬ së d÷ liÖu cã thÓ ®-îc l-u ®a chiÒu, tøc lµ víi cïng mét phÇn tö, ta cã thÓ l-u tr÷ vµ xö lý ë c¸c thêi ®iÓm kh¸c nhau, viÖc cËp nhËt d÷ liÖu kh«ng ¶nh h-ëng ®Õn d÷ liÖu tr-íc ®ã. Trªn c¬ së nghiªn cøu vÒ m« h×nh nµy, mét lo¹t kÕt qu¶ nghiªn cøu ®· ®-îc c«ng bè nh»m m« t¶ chi tiÕt h¬n vÒ m« h×nh d÷ 7 liÖu d¹ng khèi, nh»m t¨ng c-êng h¬n n÷a kh¶ n¨ng ®¶m b¶o ng÷ nghÜa, gãp phÇn hoµn chØnh thªm vÒ m« h×nh d÷ liÖu d¹ng khèi. Trªn c¬ së ®ã cã thÓ ®-a m« h×nh nµy øng dông vµo thùc tÕ. ViÖc nµy sÏ më ra kh¶ n¨ng qu¶n lý d÷ liÖu ®éng, ®¸p øng nhu cÇu thùc tÕ tèt h¬n. Tuy nhiªn víi hai m« h×nh: c¬ së d÷ liÖu quan hÖ do E.Codd ®Ò xuÊt n¨m 1970 vµ m« h×nh d÷ liÖu d¹ng khèi ®Òu h¹n chÕ trong viÖc biÓu diÔn th«ng tin kh«ng ®Çy ®ñ, kh«ng ch¾c ch¾n (gäi chung lµ d÷ liÖu mê), lo¹i d÷ liÖu nµy ®-îc con ng-êi sö dông th-êng xuyªn trong thùc tÕ. Do ®ã, khi ng-êi qu¶n trÞ mét c¬ së d÷ liÖu thùc tÕ nµo ®ã dùa trªn m« h×nh d÷ liÖu quan hÖ, th-êng gÆp nh÷ng tr-êng hîp sau: T¹i thêi ®iÓm cÇn cËp nhËt mét ®èi t-îng nµo ®ã vµo c¬ së d÷ liÖu nh-ng ch-a cã ®Çy ®ñ th«ng tin vÒ ®èi t-îng ®ã, ch¼ng h¹n biÕt mét c¸n bé gi¶ng d¹y "th©m niªn" nh-ng kh«ng râ n¨m vµo biªn chÕ (Gi¸ trÞ hiÖn t¹i lµ Unknown). BiÕt mét c¸n bé gi¶ng d¹y cã "nhiÒu" c«ng tr×nh nghiªn cøu khoa häc, nh-ng kh«ng biÕt cô thÓ lµ bao nhiªu (Kh¸i niÖm mê Vague). NÕu giíi h¹n trong m« h×nh c¬ së d÷ liÖu quan hÖ th× ph¶i ®îi ®Çy ®ñ th«ng tin vÒ ®èi t-îng ®ã míi cËp nhËt vµo c¬ së d÷ liÖu, hoÆc nÕu cø nhËp th× sÏ g©y khã kh¨n, mÊt ng÷ nghÜa vµ kh«ng nhÊt qu¸n trong xö lý d÷ liÖu. Do vËy viÖc t×m hiÓu c¬ së d÷ liÖu mê vµ øng dông vµo gi¶i quyÕt c¸c bµi to¸n thùc tÕ lµ mét nhu cÇu cÊp thiÕt trong thùc tiÔn. Mét trong nh÷ng c¸ch x©y dùng mét c¬ së d÷ liÖu mê lµ më réng c¬ së d÷ liÖu quan hÖ. Cã thÓ më réng m« h×nh quan hÖ ®Ó ®¸p øng nhu cÇu l-u tr÷ vµ khai th¸c d÷ liÖu mê theo hai h-íng, ®ã lµ: më réng ng÷ nghÜa cña d÷ liÖu ®Ó khai th¸c d÷ liÖu râ víi yÕu tè mê vµ më réng miÒn trÞ thuéc tÝnh ®Ó biÓu diÔn ®-îc d÷ liÖu mê. H-íng më réng ng÷ nghÜa, d÷ liÖu vÉn ®-îc l-u tr÷ nh- m« h×nh quan hÖ, d÷ liÖu t¹i c¸c thuéc tÝnh cña c¸c bé vÉn lµ d÷ liÖu râ nh-ng cho phÐp khai th¸c 8 d÷ liÖu víi ng÷ nghÜa réng h¬n (cã yÕu tè mê). C¸ch tiÕp cËn nµy sö dông lý thuyÕt tËp mê ®Ó më réng b»ng c¸ch thªm thuéc tÝnh ®é thuéc cho mçi bé trong quan hÖ vµo quan hÖ. VÝ dô ta cã thÓ truy xuÊt mét c¬ së d÷ liÖu nguån lùc cña mét doanh nghiÖp víi mét c©u hái nh- sau: LiÖt kª nh÷ng ng-êi trÎ tuæi trong c«ng ty. ThÕ nµo lµ trÎ tuæi?, ta sÏ ph¶i x©y dùng c¬ së logic cho viÖc xö lý ng÷ nghÜa më réng cña d÷ liÖu, lý thuyÕt tËp mê vµ logic mê lµ c¬ së ®Ó thùc hiÖn kh¶ n¨ng ®ã. Trªn c¬ së lý thuyÕt vÒ c¸c kÕt qu¶ nghiªn cøu cña c¸c nhµ khoa häc vÒ c¬ së d÷ liÖu mê vµ m« h×nh d÷ liÖu d¹ng khèi, trong luËn v¨n nµy chóng t«i ®Ò xuÊt x©y dùng m« h×nh d÷ liÖu míi lµ ‚M« h×nh d÷ liÖu d¹ng khèi mê‛ nh»m më réng kh¶ n¨ng xö lý ng÷ nghÜa cña d÷ liÖu trªn khèi, ®ång thêi chóng t«i mong muèn ®ãng gãp nh»m bæ sung lý thuyÕt vµo C¸c m« h×nh d÷ liÖu. 2. Môc ®Ých nghiªn cøu §Ò xuÊt ra M« h×nh d÷ liÖu d¹ng khèi mê nh»m më réng kh¶ n¨ng xö lý ng÷ nghÜa cña d÷ liÖu trªn khèi. Trong m« h×nh nµy chóng t«i tËp trung vµo x©y dùng c¸c kh¸i niÖm c¬ b¶n nh- khèi mê, l-îc ®å khèi mê, ®¹i sè quan hÖ trªn khèi mê, mét sè tÝnh chÊt trong m« h×nh d÷ liÖu d¹ng khèi mê. 3. NhiÖm vô nghiªn cøu §Ó ®¹t ®-îc môc ®Ých trªn, luËn v¨n ®Æt ra c¸c nhiÖm vô nghiªn cøu sau: - T×m hiÓu vÒ m« h×nh c¬ së d÷ liÖu d¹ng khèi. - T×m hiÓu vÒ tËp mê, logic mê. - T×m hiÓu c¬ së d÷ liÖu mê. - Tõ nh÷ng t×m hiÓu trªn, chóng t«i ®Ò xuÊt x©y dùng M« h×nh d÷ liÖu d¹ng khèi mê, mµ cô thÓ b-íc ®Çu x©y dùng c¸c kh¸i niÖm c¬ b¶n nh- trong môc ®Ých nghiªn cøu. 9 4. §èi t-îng vµ ph¹m vi nghiªn cøu §èi t-îng vµ ph¹m vi nghiªn cøu lµ c¸c m« h×nh d÷ liÖu, tËp trung nghiªn cøu vÒ C¬ së d÷ liÖu mê, m« h×nh d÷ liÖu d¹ng khèi tõ ®ã ®Ò xuÊt ra m« h×nh d÷ liÖu d¹ng khèi mê, b-íc ®Çu x©y dùng c¸c kh¸i niÖm c¬ b¶n nh- khèi mê, l-îc ®å khèi mê, ®¹i sè quan hÖ trªn khèi mê, mét sè tÝnh chÊt trong m« h×nh d÷ liÖu d¹ng khèi mê. 5. Nh÷ng ®ãng gãp míi cña ®Ò tµi Víi ®Ò tµi: ‚M« h×nh d÷ liÖu d¹ng khèi mê‛, chóng t«i mong muèn më réng kh¶ n¨ng xö lý ng÷ nghÜa cña d÷ liÖu trªn khèi, ®ång thêi mong muèn ®ãng gãp nh»m bæ sung lý thuyÕt vµo C¸c m« h×nh d÷ liÖu. Cô thÓ ®Ò tµi x©y dùng ®-îc c¸c kh¸i niÖm c¬ b¶n nh- khèi mê, l-îc ®å khèi mê, ®¹i sè quan hÖ trªn khèi mê, mét sè tÝnh chÊt trong m« h×nh d÷ liÖu d¹ng khèi mê, mét sè thuËt to¸n trªn khèi mê. 6. Ph-¬ng ph¸p nghiªn cøu Trong qu¸ tr×nh triÓn khai ®Ò tµi, chóng t«i sö dông chñ yÕu c¸c ph-¬ng ph¸p: Thu thËp tµi liÖu, ph©n tÝch, suy luËn, tæng hîp, ®¸nh gi¸. Tõ ®ã ®Ò xuÊt M« h×nh d÷ liÖu d¹ng khèi mê. 7. CÊu tróc cña luËn v¨n. T-¬ng øng víi nhiÖm vô nghiªn cøu ®Æt ra, ngoµi phÇn më ®Çu vµ phÇn kÕt luËn, néi dung cña luËn v¨n ®-îc triÓn khai trong 3 ch-¬ng. Ch-¬ng 1: Lý thuyÕt tËp mê vµ logic mê Ch-¬ng 2: M« h×nh d÷ liÖu quan hÖ vµ M« h×nh d÷ liÖu d¹ng khèi Ch-¬ng 3: M« h×nh d÷ liÖu d¹ng khèi mê Sau cïng lµ Phô lôc vµ Tµi liÖu tham kh¶o 10 Ch-¬ng 1: TËP Mê Vµ M¤ H×NH D÷ LIÖU QUAN HÖ 1.1. Giíi thiÖu vÒ TËp mê Nh- ®· biÕt, trong nh÷ng suy luËn ®êi th-êng còng nh- c¸c suy luËn khoa häc, logic to¸n häc ®ãng mét vai trß rÊt quan träng. Ngµy nay, x· héi cµng ph¸t triÓn th× nhu cÇu con ng-êi ngµy cµng cao. Do ®ã, sù tiÕn bé cña khoa häc còng rÊt cao. Suy luËn logic mÖnh ®Ò ®· giíi thiÖu trong ch-¬ng 1 (t¹m gäi lµ logic nguyªn thñy hay logic râ) víi hai gi¸ trÞ ®óng, sai hay 1, 0 ®· kh«ng gi¶i quyÕt ®-îc hÕt c¸c bµi to¸n phøc t¹p n¶y sinh trong thùc tÕ. VÝ dô: quÇn ¸o nh- thÕ nµo ®-îc gäi lµ dÇy, lµ máng ®Ó m¸y giÆt biÕt ®-îc mµ cã chÕ ®é tù ®éng sÊy kh« cho hîp lý? Hay trong th¬ v¨n cã c©u: "Tr¨ng kia bao tuæi tr¨ng giµ? Nói kia bao tuæi gäi lµ nói non?" Kh¸i niÖm tr¨ng giµ hay nói non lµ kh«ng ®-îc ®Þnh nghÜa râ rµng. Nh÷ng bµi to¸n nh- vËy ngµy mét nhiÒu h¬n trong c¸c lÜnh vùc ®iÒu khiÓn tèi -u, nhËn d¹ng hÖ thèng,... nãi chung lµ trong c¸c qu¸ tr×nh quyÕt ®Þnh nh»m gi¶i c¸c bµi to¸n víi c¸c d÷ liÖu kh«ng ®Çy ®ñ, hoÆc kh«ng ®-îc ®Þnh nghÜa mét c¸ch râ rµng (trong ®iÒu kiÖn thiÕu th«ng tin ch¼ng h¹n). Mét c¸ch tiÕp cËn míi ®· mang l¹i nhiÒu kÕt qu¶ thùc tiÔn vµ ®ang tiÕp tôc ph¸t triÓn ®ã lµ c¸ch tiÕp cËn cña lý thuyÕt tËp mê (FUZZY SET THEORY), do gi¸o s- Lotfi Zadeh cña tr-êng ®¹i häc California - Mü ®Ò ra n¨m 1965. Lý thuyÕt tËp mê ngµy cµng phong phó vµ hoµn chØnh, ®· t¹o nÒn v÷ng ch¾c ®Ó ph¸t triÓn logic mê. Trong ch-¬ng nµy, chóng t«i giíi thiÖu kh¸i niÖm c¬ b¶n vÒ tËp mê, logic mê, c¸c phÐp to¸n c¬ b¶n vÒ tËp mê. 1.2. Kh¸i niÖm tËp mê (fuzzy set) Nh- chóng ta ®· biÕt, tËp hîp lµ tËp tÊt c¶ c¸c phÇn tö cã cïng tÝnh chÊt chung nµo ®ã. VÝ dô: tËp c¸c sinh viªn. 11 Ta cã : T = {t / t lµ sinh viªn} VËy, nÕu mét ng-êi nµo ®ã lµ sinh viªn th× thuéc tËp T, ng-îc l¹i lµ kh«ng thuéc tËp T. Tuy nhiªn, trong thùc tÕ cuéc sèng còng nh- trong khoa häc kü thuËt cã nhiÒu kh¸i niÖm kh«ng ®-îc ®Þnh nghÜa mét c¸ch râ rµng. VÝ dô, khi nãi mét ‚nhãm sinh viªn kh¸‛, vËy thÕ nµo lµ kh¸? Kh¸i niÖm vÒ kh¸ kh«ng râ rµng v× cã thÓ sinh viªn cã ®iÓm thi trung b×nh b»ng 8.4 lµ kh¸, còng cã thÓ ®iÓm thi trung b×nh b»ng 6.6 còng lµ kh¸ (d¶i ®iÓm kh¸ cã thÓ tõ 6.5 ®Õn 8.5),... Nãi c¸ch kh¸c, ‚nhãm sinh viªn kh¸‛ kh«ng ®-îc ®Þnh nghÜa mét c¸ch t¸ch b¹ch râ rµng nh- kh¸i niÖm vÒ tËp hîp. HoÆc, khi chóng ta nãi ®Õn mét ‚líp c¸c sè lín h¬n 10‛ hoÆc ‚mét ®èng quÇn ¸o cò‛,... lµ chóng ta ®· nãi ®Õn nh÷ng kh¸i niÖm mê hay nh÷ng kh¸i niÖm kh«ng ®-îc ®Þnh nghÜa mét c¸ch râ rµng. H×nh 1.1: BiÓu diÔn logic râ qua ®å thÞ H×nh 1.2: BiÓu diÔn logic mê qua ®å thÞ 1.2.1. §Þnh nghÜa tËp mê (Fuzzy set): Cho x¹ tõ lµ kh«ng gian nÒn, mét tËp mê A trªn ®Õn ®o¹n [0,1]. [2] t-¬ng øng víi mét ¸nh 12 A: [0,1] ®-îc gäi lµ hµm thuéc vÒ (membership function) KÝ hiÖu A = {(a, A(a)) / a } Trong ®ã, [0,1] chØ møc ®é thuéc vÒ (membership degree) (a)) A cña phÇn tö a vµo tËp mê A. Kho¶ng x¸c ®Þnh cña hµm (a) lµ ®o¹n [0, 1], A trong ®ã gi¸ trÞ 0 chØ møc ®é kh«ng thuéc vÒ, cßn gi¸ trÞ 1 chØ møc ®é thuéc vÒ hoµn toµn. VÝ dô 1: Biểu diễn tập mờ cho số “integer nhỏ” int H×nh 1.3: BiÓu diÔn tËp mê cho sè “integer nhá” VÝ dô 2: BiÓu diÔn tËp mê cho c¸c tËp ng-êi ®µn «ng thÊp, trung b×nh vµ cao H×nh 1.4: BiÓu diÔn tËp mê cho c¸c tËp ng-êi ®µn «ng thÊp, trung b×nh vµ cao VÝ dô 3: Cho = {1, 2, 3, 4, 5}, tËp mê A trªn nh- sau: A : 1 0 2 1 3 0.5 4 0.3 5 0.2 t-¬ng øng víi ¸nh x¹ A 13 Ta cã tËp mê A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} Tõ ®Þnh nghÜa trªn chóng ta cã thÓ suy ra: - TËp mê A lµ rçng nÕu vµ chØ nÕu hµm thuéc vÒ - TËp mê A lµ toµn phÇn nÕu vµ chØ nÕu - Hai tËp mê A vµ B b»ng nhau nÕu (a)= 0 , a A (a) = 1 , a A (x) = A B (x) víi mäi x trong . 1.2.2. C¸c phÐp to¸n vÒ tËp mê §Ó cã thÓ tiÕn hµnh m« h×nh hãa c¸c hÖ thèng cã chøa tËp mê vµ biÓu diÔn c¸c qui luËt vËn hµnh cña hÖ thèng nµy, tr-íc tiªn chóng ta cÇn tíi viÖc suy réng c¸c phÐp to¸n logic c¬ b¶n víi c¸c mÖnh ®Ò cã ch©n trÞ trªn ®o¹n [0, 1]. [2] Cho = {P1, P2, ...} víi P1, P2, ... lµ c¸c mÖnh ®Ò. TËp mê A trªn t-¬ng øng víi ¸nh x¹ v nh- sau: v: [0, 1] Pi v(Pi) Ta gäi v(Pi) lµ ch©n trÞ cña mÖnh ®Ò Pi trªn [0, 1]. [2] 1.2.2.1. PhÐp bï PhÐp phñ ®Þnh trong logic kinh ®iÓn lµ mét trong nh÷ng phÐp to¸n c¬ b¶n cho viÖc x©y dùng phÐp bï cña 2 tËp hîp. §Ó suy réng phÐp nµy trong tËp mê chóng ta cÇn tíi to¸n tö v(NOT P). To¸n tö nµy ph¶i tháa c¸c tÝnh chÊt sau: - v(NOT P) chØ phô thuéc vµo v(P). - NÕu v(P)=1 th× v(NOT P)=0 - NÕu v(P)=0 th× v(NOT P)=1 - NÕu v(P1) v(P2) th× v(NOT P1) v(NOT P2) §Þnh nghÜa 1: [2] Hµm n : [0,1] [0, 1] kh«ng t¨ng tháa m·n c¸c ®iÒu kiÖn n(0) = 1, n(1) = 0, ®-îc gäi lµ hµm phñ ®Þnh. VÝ dô 4: n(x) = 1 - x hay n(x) = 1 - x2 lµ c¸c hµm phñ ®Þnh. Ta cã nhËn xÐt: 14 - NÕu v(P1) < v(P2) th× v(NOT P1) > v(NOT P2) - v(NOT P) phô thuéc liªn tôc vµo v(P) - v(NOT (NOT P)) = v(P) §Þnh nghÜa 2 (PhÇn bï cña mét tËp mê): [2] Cho n lµ hµm phñ ®Þnh, phÇn bï Ac cña tËp mê A lµ mét tËp mê víi hµm thuéc vÒ ®-îc x¸c ®Þnh bëi: Ac (a) n( A (a)) víi mçi a §å thÞ cña hµm thuéc vÒ cã d¹ng sau: x x Ac x x H×nh 1.5. Hµm thuéc vÒ cña tËp mê VÝ dô 5: Cho vµ tËp mê Ac = {1, 2, 3, 4, 5}, vµ A lµ tËp mê trong nh- sau: A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} Ta cã: Ac = {(1,1), (2,0), (3,0.5), (4,0.7), (5,0.8)} §Þnh nghÜa 3: [2] a. Hµm phñ ®Þnh n lµ nghiªm ngÆt (strict) nÕu nã lµ hµm liªn tôc vµ gi¶m nghiªm ngÆt. b. Hµm phñ ®Þnh n lµ m¹nh (strong) nÕu nã lµ chÆt vµ tháa n(n(x)) = x, x [0,1]. §Þnh nghÜa 4: [2] Hµm = [a, b] [a, b] gäi lµ mét tù ®ång cÊu (automorphism) cña ®o¹n [a,b] nÕu nã lµ hµm liªn tôc, t¨ng nghiªm ngÆt vµ (a) = a, (b) = b. 15 §Þnh lý 1: [2] Hµm n:[0,1] ®ång cÊu [0,1] lµ hµm phñ ®Þnh m¹nh khi vµ chØ khi cã mét tù cña ®o¹n [0,1] sao cho N(x) = N (x) = -1 (1- (x)). §Þnh lý 2: [2] Hµm n: [0,1] [0,1] lµ hµm phñ ®Þnh nghiªm ngÆt khi vµ chØ khi cã hai phÐp tù ®ång cÊu , cña [0,1] sao cho n(x) = (1- (x)). 1.2.2.2. PhÐp giao PhÐp héi AND trong logic kinh ®iÓn lµ c¬ së ®Ó ®Þnh nghÜa phÐp giao cña 2 tËp mê. AND tho¶ c¸c tÝnh chÊt sau: - v(P1 AND P2) chØ phô thuéc vµo v(P1), v(P2). - NÕu v(P1)=1 th× v(P1 AND P2) = v(P2) , víi mäi P2 - Giao ho¸n v(P1 AND P2) = v(P2 AND P1) - NÕu v(P1) v(P2) th× v(P1 AND P3) v(P2 AND P3), víi mäi P3 - KÕt hîp v(P1 AND (P2 AND P3 )) = v((P1 AND P2 )AND P3 ) §Þnh nghÜa 5: [2] Hµm T : [0,1]2 [0,1] lµ phÐp héi (t-chuÈn) khi vµ chØ khi tháa c¸c ®iÒu kiÖn sau: - T(1, x) = x, víi mäi 0 x 1. - T cã tÝnh giao ho¸n, nghÜa lµ : T(x,y) = T(y,x), víi mäi 0 x,y 1. - T kh«ng gi¶m theo nghÜa : T(x,y) T(u,v), víi mäi x u, y v. - T cã tÝnh kÕt hîp : T(x,T(y,z)) = T(T(x,y),z), víi mäi 0 x,y, z 1. Tõ c¸c tÝnh chÊt trªn cã thÓ suy ra T(0,x) = 0. §Þnh nghÜa 6: [2] Cho hai tËp mê A, B trªn cïng kh«ng gian nÒn vÒ (a), A B víi hµm thuéc (a), cho T lµ mét phÐp héi. øng víi phÐp héi T, tËp giao cña hai tËp mê A, B lµ mét tËp mê trªn 16 víi hµm thuéc vÒ cho bëi: A B (a) = T( A (a), B (a)) Víi T(x,y)=min(x,y) ta cã: Víi T(x,y) = x.y ta cã: A B a A B (a) = min( (a) = (a). A B (a), A B (a)) (a) (tÝch ®¹i sè) Ta cã thÓ biÓu diÔn phÐp giao cña hai tËp mê qua hai hµm T(x,y)=min(x,y) vµ T(x,y) = x.y theo c¸c ®å thÞ sau ®©y: - H×nh a: Hµm thuéc vÒ cña hai tËp mê A vµ B - H×nh b: Giao cña hai tËp mê theo T(x,y) = min(x,y) - H×nh c: Giao cña hai tËp mê theo T(x,y) = x.y B(x) A(x) A(x) B(x) x a B(x) A(x) x b x c H×nh 1.6 §å thÞ biÓu diÔn phÐp giao cña hai tËp mê T(x,y) VÝ dô: Cho = {1, 2, 3, 4, 5}, vµ A, B lµ c¸c tËp mê trong nh- sau: A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} B = {(1,0), (2,0.5), (3,0.7), (4,0.2), (5,0.4)} Víi T(x,y) = min(x,y), ta cã : A B = {(1,0), (2,0.5), (3,0.5), (4,0.2), (5,0.2)} A Ac = {(1,0), (2,0), (3,0.5), (4,0.3), (5,0.2)} 1.2.2.3. PhÐp hîp PhÐp tuyÓn OR trong logic kinh ®iÓn lµ c¬ së ®Ó ®Þnh nghÜa phÐp hîp cña 2 tËp mê. OR tho¶ c¸c tÝnh chÊt sau: 17 - v(P1 OR P2) chØ phô thuéc vµo v(P1), v(P2). - NÕu v(P1) = 0 th× v(P1 OR P2) = v(P2) , víi mäi P2 - Giao ho¸n v(P1 OR P2) = v(P2 OR P1) - NÕu v(P1) v(P2) th× v(P1 OR P3) v(P2 OR P3), víi mäi P3 - KÕt hîp v(P1 OR (P2 OR P3 )) = v((P1 OR P2 ) OR P3 ). §Þnh nghÜa 7: [2] Hµm S :[0,1]2 [0,1] ®-îc gäi lµ phÐp tuyÓn (t- ®èi chuÈn) nÕu tháa c¸c tiªn ®Ò sau: - S(0, x) = x, víi mäi 0 x 1. - S cã tÝnh giao ho¸n, nghÜa lµ : S(x,y) = S(y,x), víi mäi 0 x,y 1. - S kh«ng gi¶m theo nghÜa : S(x,y) S(u,v), víi mäi x - S cã tÝnh kÕt hîp : S(x,S(y,z)) = S(S(x,y),x), víi mäi 0 u, y x,y,z v. 1. Tõ c¸c tÝnh chÊt trªn suy ra S(1,x) = 1. VÝ dô: S(x,y) = max(x,y) S(x,y) = min(1, x+y) S(x,y) = x + y - x.y §Þnh nghÜa 8: [2] Cho hai tËp mê A, B trªn cïng kh«ng gian nÒn vÒ (a), A tËp mê trªn B víi hµm thuéc (a). Cho S lµ phÐp tuyÓn, phÐp hîp cña hai tËp mê A, B lµ mét víi hµm thuéc vÒ cho bëi : A B (a) = = S( A(a), B (a)) , a Víi S(x,y) = max(x,y) ta cã : A B (a) = max( A(a), B (a)) (xem h×nh a) Víi S(x,y) = min(1, x+y) A B (a) = min(1, (a) + A B (a)) (xem h×nh b) 18 Víi S(x,y) = x + y + x.y A (a) A B B (a) = ( A(a) + (a) B (a) - ( A(a). (a) A B B (a)) (xem h×nh c) (a) x (a) A B (a) x a x b c H×nh 1.7: §å thÞ biÓu diÔn c¸c phÐp to¸n cña S(x,y) VÝ dô: Cho = {1, 2, 3, 4, 5}, vµ A, B lµ c¸c tËp mê trong nh- sau: A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} B = {(1,0), (2,0.5), (3,0.7), (4,0.2), (5,0.4)} Ta cã: A B = {(1,0), (2,1), (3,0.7), (4,0.3), (5,0.4)} A Ac = {(1,1), (2,1), (3,0.5), (4,0.7), (5,0.8)} 1.2.2.4. PhÐp kÐo theo Chóng ta sÏ xÐt phÐp kÐo theo nh- mét mèi quan hÖ, mét to¸n tö logic. Ta cã c¸c tiªn ®Ò sau cho hµm v(P1 - v(P1 P2) : P2) chØ phô thuéc vµo v(P1), v(P2). - NÕu v(P1) v(P3) th× v(P1 P2) v(P3 P2), P2 - NÕu v(P2) v(P3) th× v(P1 P2) v(P1 P3), P1 - NÕu v(P1) = 0 th× v(P1 P) = 1 , P. - NÕu v(P1) = 1 th× v(P P1) = 1 , P. - NÕu v(P1) = 1 vµ v(P2) = 0 th× v(P1 P2) = 0. TÝnh hîp lý cña nh÷ng tiªn ®Ò nµy dùa vµo logic kinh ®iÓn vµ nh÷ng t-