i

..

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG

NGUYỄN TUẤN CƢỜNG

TÌM KIẾM THƠNG MINH VỚI ỨNG DỤNG
CỦA TẬP MỜ TRỰC CẢM

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Ngun, tháng 10 năm 2013

Số hóa bởi trung tâm học liệu

/>

i

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG

NGUYỄN TUẤN CƢỜNG

TÌM KIẾM THƠNG MINH VỚI ỨNG DỤNG
CỦA TẬP MỜ TRỰC CẢM
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Giáo viên hƣớng dẫn khoa học: TS. NGUYỄN TÂN ÂN

Thái Nguyên, tháng 10 năm 2013

Số hóa bởi trung tâm học liệu

/>

i

LỜI CAM ĐOAN
Tơi xin cam đoan tồn bộ nội dung trong luận văn này do tôi tự nghiên cứu,
đọc, dịch tài liệu, tổng hợp và thực hiện. Trong luận văn tơi có sử dụng một số tài
liệu tham khảo như đã trình bày trong phần tài liệu tham khảo.
Ngƣời viết luận văn

Nguyễn Tuấn Cƣờng

Số hóa bởi trung tâm học liệu

/>

ii

LỜI CẢM ƠN
Đầu tiên tôi xin gửi lời cảm ơn chân thành đến thầy TS Nguyễn Tân Ân – Đại
học Sư phạm Hà Nội đã tận tình hướng dẫn, chỉ bảo cho tơi trong suốt q trình làm

luận văn.
Tơi cũng xin gửi lời cảm ơn đến các thầy cô trường Đại học Công nghệ thông
tin và Truyền thông – Đại học Thái Nguyên, các thầy cô Viện Công nghệ thông tin
đã truyền đạt những kiến thức và giúp đỡ tôi trong suốt q trình học của mình.
Tơi cũng xin gửi lời cảm ơn tới các đồng nghiệp trong đơn vị cơng tác, gia
đình và bạn bè những người đã động viên tạo mọi điều kiện giúp đỡ tôi trong suốt
hai năm học.

Số hóa bởi trung tâm học liệu

/>

iii

MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
MỤC LỤC ................................................................................................................. iii
DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT............................................... iv
DANH MỤC CÁC HÌNH ...........................................................................................v
MỞ ĐẦU ....................................................................................................................1
Chƣơng 1: NHỮNG KIẾN THỨC CƠ SỞ TẬP MỜ, TẬP MỜ TRỰC CẢM,
VẤN ĐỀ TÌM KIẾM ................................................................................................4
1.1. Tập mờ ..............................................................................................................4
1.1.1. Định nghĩa tập mờ, số mờ [1]........................................................................4
1.1.2. Các phép toán trên tập mờ, số mờ hình thang, số mờ tam giác ....................9
1.2. Tập mờ trực cảm.............................................................................................18
1.2.1. Định nghĩa ...................................................................................................18
1.2.2. Các phép toán trên số mờ trực cảm hình thang, hình tam giác ...................20
1.3. Bài tốn tìm kiếm lời giải và những kỹ thuật tìm kiếm .................................26

1.4. Kết luận chương 1 ..........................................................................................37
Chƣơng 2: TÌM KIẾM THÔNG MINH VỚI ỨNG DỤNG CỦA TẬP MỜ
TRỰC CẢM.............................................................................................................38
2.1. Tìm kiếm thơng minh .....................................................................................38
2.2. Thuật tốn tìm kiếm thơng minh với ứng dụng tập mờ trực cảm ..................53
2.3. Kết luận chương 2 ..........................................................................................58
Chƣơng 3: VÍ DỤ ÁP DỤNG .................................................................................59
3.1. Một số bài tốn tìm kiếm ................................................................................59
3.2. Lời giải ...........................................................................................................61
3.3. Kết luận chương 3 ..........................................................................................82
KẾT LUẬN ..............................................................................................................83
TÀI LIỆU THAM KHẢO ......................................................................................84

Số hóa bởi trung tâm học liệu

/>

iv

DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT
Vague sets (VS)

Tập mờ trực cảm

Vague Number (VN)

Số mờ trực cảm

Vague Relation (VR)


Quan hệ mờ trực cảm

Vague Tolerance Relation (VTR)

Quan hệ gần đúng

Vague Proximity Relation (VPR)

Quan hệ lân cận

Depth First Search (DFS)

Tìm kiếm theo chiều sâu

Breadth First Search (BFS)

Tìm kiếm theo chiều rộng

Domain (Dom)

Miền

Not less than (nlt)

Khơng nhỏ hơn

Sup

Cận trên


Inf

Cận dưới

Số hóa bởi trung tâm học liệu

/>

v

DANH MỤC CÁC HÌNH
Hình 1.1: Biểu diễn tập mờ cho số "integer nhỏ" ....................................................... 4
Hình 1.2: Biểu diễn tập mờ cho các tập người thấp, trung bình và cao ...................... 5
Hình 1.3: Tập mờ lồi ................................................................................................... 6
Hình 1.4: Đồ thị hàm thành viên nhóm hàm đơn điệu ................................................ 7
Hình 1.5: Đồ thị hàm thành viên nhóm hàm hình chng .......................................... 7
Hình 1.6: Hàm thành viên của phần bù mờ ................................................................ 9
Hình 1.7: Hàm thành viên của hợp hai tập mờ có cùng cơ sở .................................... 9
Hình 1.8a: Phép hợp hai tập mờ không cùng cơ sở: Hàm thành viên của 2 tập
mờ A, B ................................................................................................. 10
Hình 1.8b: Phép hợp hai tập mờ không cùng cơ sở: Đưa 2 tập mờ về chung
một cơ sở MxN ...................................................................................... 10
Hình 1.8c: Phép hợp hai tập mờ không cùng cơ sở: Hợp 2 tập mờ trên cơ sở MxN ....... 10
Hình 1.9: Phép giao hai tập mờ cùng cơ sở .............................................................. 11
Hình 1.10: Phép giao hai tập mờ khơng cùng cơ sở ................................................. 12
Hình 1.11: Số mờ hình thang .................................................................................... 17
Hình 1.13: Số mờ trực cảm hình thang ..................................................................... 21
Hình 1.14: Số mờ trực cảm tam giác ........................................................................ 21
Hình 1.15: Đồ thị khơng gian trạng thái ................................................................... 28
Hình 1.16: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số .................... 30

Hình 1.17: Các trạng thái của cây trị chơi................................................................ 36
Hình 1.18: Cây tìm kiếm và sự bùng nổ tổ hợp ........................................................ 37
Hình 2.1: Hình ảnh của tìm kiếm chiều sâu. Nó chỉ lưu ý "mở rộng" trạng thái được
chọn mà không "mở rộng" các trạng thái khác (nút màu trắng). .................... 39
Hình 2.2: Hình ảnh của tìm kiếm chiều rộng. Tại một bước, mọi trạng thái đều
được mở rộng, không bỏ sót trạng thái nào ............................................. 41
Hình 2.3: Chi phí ước lượng h‟ = 6 và chi phí tối ưu thực sự h = 4+5 = 9 (đi
theo đường 1-3-7) .................................................................................... 43
Số hóa bởi trung tâm học liệu

/>

vi

Hình 2.5: Đồ thị khơng gian trạng thái ..................................................................... 47
Hình 2.6: Cây tìm kiếm Beam................................................................................... 48
Hình 2.7: Đồ thị khơng gian trạng thái ..................................................................... 50
Hình 2.8: Sơ đồ biểu thị đường đi ............................................................................. 51
Hình 2.9: Đồ thị khơng gian trạng thái ..................................................................... 55
Hình 3.1: Trạng thái ban đầu và trạng thái kết thúc của bài tốn 8 số ...................... 59
Hình 3.2: Giải bài tốn Ta canh bằng phương pháp tìm kiếm theo chiều sâu .......... 59
Hình 3.3: Giải bài tốn Ta canh bằng thuật giải Heuristics tìm đường đi có giá
nhỏ nhất với tri thức bổ sung ................................................................... 60
Hình 3.1: Trạng thái ban đầu và trạng thái kết thúc của bài tốn 8 số ...................... 61

Số hóa bởi trung tâm học liệu

/>

1


MỞ ĐẦU
Xuất phát từ sự bùng nổ thông tin và mạng internet kết nối hầu hết các máy
tính của các tổ chức thành những kho dữ liệu khổng lồ. Tuy nhiên, dữ liệu được bố
trí sắp xếp và phân tán thành nhiều tập dữ liệu được lưu trữ trên các hệ thống máy
tính lớn nằm rải rác trên tồn thế giới. Với một kỹ thuật đơn giản thì việc tìm kiếm
thơng tin là rất khó khăn và khơng chính xác mất nhiều thời gian tìm kiếm. Câu hỏi
đặt ra là làm thế nào để con người có thể vươn tới tầm cao tri thức làm chủ được
cơng nghệ, tìm kiếm thơng tin nhanh và chính xác.
Cùng với việc phát minh ra các thuật tốn tìm kiếm tối ưu các kỹ thuật mới
xuất hiện và có tốc độ phát triển rất nhanh đóng góp vai trị quan trọng trong việc
tìm kiếm dữ liệu, các thuật toán mới xuất hiện với thời gian tính tốn đã phần nào
giải quyết được những vướng mắc nói trên.
Ngồi ra cịn có sự hỗ trợ của nhiều phương pháp, liên quan đến nhiều lĩnh
vực, ngành khác như: lý thuyết thuật tốn, thị giác máy tính (Visualization), Data
Warehouses, OLAP, tính tốn song song, cấu trúc ơtơmát mờ và các phép tính tốn
kết quả cao…nhưng chủ yếu dựa trên nền tảng của xác suất thống kê, cơ sở dữ liệu,
lý thuyết mờ, lý thuyết ôtômát và học máy.
Đây là một q trình mang tính định tính với mục đích xác định được
lĩnh vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng thể. Trong thực
tế, các cơ sở dữ liệu được chun mơn hố và phân chia theo các lĩnh vực
khác nhau như sản xuất, kinh doanh, tài chính... Với mỗi tri thức phát hiện
được, có thể có giá trị trong lĩnh vực này nhưng lại không mang nhiều ý nghĩa
đối với một lĩnh vực khác. Vì vậy việc xác định lĩnh vực và định nghĩa bài
toán giúp định hướng cho giai đoạn tiếp theo – thu thập và tiền xử lý dữ liệu.
Các cơ sở dữ liệu thu được thường chứa rất nhiều thuộc tính nhưng lại
khơng đầy đủ, khơng thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy,
giai đoạn thu thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá trình
phát hiện tri thức từ cơ sở dữ liệu phục vụ cho việc tìm kiếm dữ liệu.
Quá trình tìm kiếm lời giải thực sự là một bài tốn khó. Các phương pháp vét

cạn kinh điển như tìm kiếm sâu (DFS), tìm kiếm rộng (BFS),… đều khơng thể áp

Số hóa bởi trung tâm học liệu

/>

2

dụng trong khơng gian tìm kiếm lớn bởi độ phức tạp thời gian. Trong mơi trường
mờ vấn đề tìm kiếm càng khó. Lý thuyết tập mờ được L.Zadeh đề nghị năm 1965
đã khẳng định được tính ưu việt của nó. Tuy nhiên lý thuyết mờ cũng không ngừng
được phát triển. Năm 1993 Gau and Buehrer đã đưa ra tập mờ trực cảm
(intuitionistic fuzzy (vague) sets) [6]. Trong nhiều trường hợp tập mờ trực cảm mô
tả thông tin mờ một cách hợp lý hơn và cho kết quả xử lý thông tin tốt hơn tập mờ
của Zadeh. Những nghiên cứu về tập mờ trực cảm, tìm kiếm thơng minh trong mơi
trường mờ nói chung và trong mơi trường được mơ tả bởi tập mờ trực cảm nói riêng
cịn ít. Vì thế trong khuôn khổ của luận văn thạc sĩ, em chọn đề tài “Tìm kiếm thơng
minh với ứng dụng của tập mờ trực cảm” nhằm tìm hiểu các thuật tốn tìm kiếm lời
giải, một nội dung kiến thức rất quan trọng của những chuyên gia về công nghệ
thông tin.
Đối tƣợng và phạm vi nghiên cứu
- Vấn đề tìm kiếm lời giải
- Tập mờ, tập mờ trực cảm
- Tìm kiếm thơng minh với ứng dụng của tập mờ trực cảm
Hƣớng nghiên cứu của đề tài
Nghiên cứu thuật tốn tìm kiếm thơng minh ứng dụng tập mờ trực cảm
Những nội dung nghiên cứu chính
Chƣơng 1: Những kiến thức cơ sở Tập mờ, tập mờ trực cảm, vấn đề tìm kiếm
1.1. Tập mờ
1.1.1. Định nghĩa tập mờ, số mờ

1.1.2. Các phép toán trên tập mờ, số mờ hình thang, số mờ tam giác
1.2. Tập mờ trực cảm
1.2.1. Định nghĩa
1.2.2. Các phép toán trên số mờ trực cảm hình thang, hình tam giác
1.3. Bài tốn tìm kiếm lời giải và những kỹ thuật tìm kiếm
1.4. Kết luận chương 1
Chƣơng 2: Tìm kiếm thơng minh với ứng dụng của tập mờ trực cảm
2.1. Tìm kiếm thơng minh
Số hóa bởi trung tâm học liệu

/>

3

2.2. Thuật tốn tìm kiếm thơng minh với ứng dụng tập mờ trực cảm
2.3. Kết luận chương 2
Chƣơng 3: Ví dụ áp dụng
3.1. Một số bài tốn tìm kiếm
3.2. Lời giải
3.3. Kết luận chương 3
Phƣơng pháp nghiên cứu
- Nghiên cứu lý thuyết: Tìm đọc tài liệu, đối chiếu, so sánh, rút trích, hệ
thống hóa,... viết thành luận văn
- Thực hành: Tìm kiếm lời giải trong một số trường hợp.
Ý nghĩa khoa học của đề tài
Áp dụng và khẳng định tính ưu việt của tập mờ trực cảm trong một số trường
hợp cụ thể, đặc biệt trong tìm kiếm thơng minh.

Số hóa bởi trung tâm học liệu


/>

4

Chƣơng 1
NHỮNG KIẾN THỨC CƠ SỞ TẬP MỜ, TẬP MỜ TRỰC CẢM, VẤN ĐỀ
TÌM KIẾM
1.1. Tập mờ
Trong thực tế chúng ta đánh giá kết quả khơng chỉ mang tính chất đúng
hoặc sai mà cịn mang tính chất định tính khơng chắc chắn thông qua việc sử dụng
các biến ngôn ngữ để phản ánh. Một trong những cách đánh giá và xử lý dạng biếu
diễn thông tin thu được những kết quả rất tốt đó là cách tiếp cận mờ. Từ năm 1965,
L.A.Zadeh đã xây dựng lý thuyết tập mờ, tạo ra một cơ sở toán học cho việc tiếp
cận lập luận tính tốn của con người. Ý tưởng của ơng là mở rộng tập logic cổ điển
(logic Boole), làm tăng thêm khả năng suy luận của con người, góp phần đánh giá
kết quả đi đến độ chính xác nhất. Sau đây là một số khái niệm và tính chất cơ bản
của tập mờ.
1.1.1. Định nghĩa tập mờ, số mờ [1]
Định nghĩa tập mờ
Cho tập vũ trụ U, tập A U được gọi là tập mờ nếu A được xác định bởi
hàm

A

:U [0,1].
A

được gọi là hàm thuộc, hàm thành viên hay hàm đặc trưng.

Với x U thì


A

(x) được gọi là mức độ thuộc của x vào A.

Như vậy ta có thể coi tập rõ là một trường hợp đặc biệt của tập mờ, trong
đó hàm thành viên chỉ nhận 2 giá trị 0 và 1.
Ví dụ 1. Một sự biểu diễn tập mờ cho số "integer nhỏ".

1

1 2 3 .....

int

Hình 1.1: Biểu diễn tập mờ cho số "integer nhỏ"
Số hóa bởi trung tâm học liệu

/>

5

Ví dụ 2. Một sự biểu diễn tập mờ cho các tập người thấp, trung bình và cao

thấp

trung bình

cao


1

4‟

chiều cao

4‟6”

5‟

5‟6”

6‟

6‟6”

Hình 1.2: Biểu diễn tập mờ cho các tập người thấp, trung bình và cao
Ví dụ 3. Cho U={1, 2, 3, 4, 5}, tập mờ A trên U tương ứng với ánh xạ

A

như sau:
1 0

A:

2 1
3 0.5
4 0.3
5 0.2

Ta có tập mờ A={(1,0),(2,1),(3,0.5),(4,0.3),(5,0.2)}
Cách viết trên là sự liệt kê các phần tử khác nhau cùng với mức độ thuộc về
tập hợp A. 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ề µA(x)= 0, a U
- Tập mờ A là tồn phần nếu và chỉ nếu µA(x) = 1, a U
- Hai tập mờ A và B bằng nhau nếu µA(x) = µB(x) a U
Ký hiệu tập mờ, ta có các dạng ký hiệu sau:
 Liệt kê phần tử: giả sử U={a,b,c,d} ta có thể xác định một tập mờ
A=

0.1 0.3
a
b

 A = x,

A

0.2
c

0
d

( x) | x U

( x)
trong trường hợp U là không gian rời rạc
x


 A=

A
x U

 A=

A

( x ) / x trong trường hợp U là khơng gian liên tục

U

Số hóa bởi trung tâm học liệu

/>

6

Lưu ý là các ký hiệu

và

không phải là các phép tính tổng hay tích

phân, mà chỉ là ký hiệu biểu thị tập hợp mờ.
Ví dụ 4. Tập mờ A là tập “số gần 2” xác định bởi hàm thuộc
có thể ký hiệu: A = x, ( x 2) 2 | x U

hoặc A =


A

e

( x 2) 2

ta

( x 2) 2 / x .

Tập mờ cắt mức

( -cut)

Tập mờ cắt mức

là tập rõ trong đó hàm thành viên

A(x)>=

.

Tập mờ lồi
Cho tập mờ A xác định trong khơng gian X có hàm thành viên

A(x).

Khi


đó tập mờ A được gọi là tập mờ lồi nếu hàm thành viên của tập mờ có dạng lồi hay
nói cách khác tập mờ sẽ là tập mờ lồi nếu với mọi điểm x1, x2, x3 thuộc không gian
X sao cho x1A(x2)

1

min[

A(x1),

A(x3)]

A

E
x1

x2

x3

Hình 1.3: Tập mờ lồi
Các dạng hàm thành viên tiêu biểu
Theo lý thuyết thì hàm thành viên có thể là một hàm bất kỳ thoả

A

:X-

>[0,1]. Nhưng trong thực tế thì có các dạng hàm thành viên sau đây là quan trọng và
có tính ứng dụng cao hơn cả.
Nhóm hàm đơn điệu
Nhóm này gồm đơn điệu tăng và đơn điệu giảm.
Ví dụ 5. Tập hợp người già có hàm thành viên đơn điệu tăng theo tuổi trong
khi đó tập hợp người trẻ có hàm thành viên đơn điệu giảm theo tuổi.
Số hóa bởi trung tâm học liệu

/>

7

Ví dụ 6. Cho tập vũ trụ E = Tốc độ = {20,50,80,100,120} đơn vị là km/h.
Xét tập mờ F=Tốc độ nhanh xác định bởi hàm thành viên

nhanh

như đồ thị hình 1.4.

Như vậy tốc độ dưới 20km/h được coi là khơng nhanh. Tốc độ càng cao thì
độ thuộc của nó vào tập F càng cao. Khi tốc độ là 100km/h trở lên thì độ thuộc là 1.

1

nhanh

0.85
0.5

E

20

50

80

100

120

Hình 1.4: Đồ thị hàm thành viên nhóm hàm đơn điệu
Nhóm hàm hình chng
Nhóm hàm này có đồ thị dạng hình chng, bao gồm dạng hàm tam giác,
hàm hình thang, gauss.
Xét ví dụ cũng với tập vũ trụ E ở trên, xét tập mờ F=Tốc độ trung bình xác
định bởi hàm thành viên

trungbình

0
( x 20) / 30

khi x 20 x 100
khi
20 x 50

(100 x) / 50 khi

1

50

x 100

trungbình

0.4
E
20

50

80

100

120

Hình 1.5: Đồ thị hàm thành viên nhóm hàm hình chng
Các khái niệm liên quan
Giả sử A là tập mờ trên vũ trụ U, có hàm thuộc

Số hóa bởi trung tâm học liệu

A

thì ta có các khái niệm sau:

/>

8

 Giá đỡ của A, ký hiệu sup(A) là một tập rõ bao gồm tất cả các phần tử
x U sao cho

A

(x) > 0.

 Nhân của A là một tập rõ bao gồm tất cả các phần tử x
A

U sao cho

(x)=1.

 Biên của A là một tập rõ bao gồm tất cả các phần tử x
0<

A

U sao cho

(x)<1.

 Độ cao của A, ký hiệu height(A) là cận trên đúng của
height(A)= sup

A

A

(x).

( x) .

x U

 Tập mờ A được gọi là tập mờ chuẩn tắc (normal fuzzy set) nếu
height(A)=1. Tức là tập mờ chuẩn tắc có nhân khác rỗng.
Các tập mờ hay tập hợp mờ (Fuzzy set) là một mở rộng của lý thuyết tập
hợp cổ điển và được dùng trong lôgic mờ. Trong lý thuyết tập hợp cổ điển, quan hệ
thành viên của các phần tử trong một tập hợp được đánh giá theo kiểu nhị phân theo
một điều kiện rõ ràng - một phần tử hoặc thuộc hoặc không thuộc về tập hợp.
Ngược lại, lý thuyết tập mờ cho phép đánh giá từ từ về quan hệ thành viên giữa một
phần tử và một tập hợp; quan hệ này được mô tả bằng một hàm thành
viên (membership function)

[0,1]. Các tập mờ được coi là một mở rộng của lý

thuyết tập hợp cổ điển là vì, với một universe (khơng gian tham chiếu hay tập vũ
trụ) nhất định, một hàm thành viên có thể giữ vai trị của một hàm đặc
trưng (indicator function) ánh xạ mỗi phần tử tới một giá trị 0 hoặc 1 như trong khái
niệm cổ điển.
Một lớp tập mờ quan trọng có nhiều ứng dụng thực tế là số mờ
Định nghĩa số mờ
Tập mờ M trên đường thẳng thực R là tập số mờ nếu:
- M là chuẩn hố, tức là có điểm x sao cho
- Ứng với mỗi

R , tập mức x : M x

M x

1

là đoạn đóng

Người ta thường dùng các số mờ tam giác, hình thang và dạng Gauss

Số hóa bởi trung tâm học liệu

/>

9

1.1.2. Các phép tốn trên tập mờ, số mờ hình thang, số mờ tam giác
Các phép toán trên tập mờ [2]
Giả sử A và B là các tập mờ trên vũ trụ U thì ta có các định nghĩa sau:
Quan hệ bao hàm
A được gọi là bằng B khi và chỉ khi

x U,

A

x

B

x .

A được gọi là tập con của B, ký hiệu A B khi và chỉ khi
A

x

x U,

x

B

Phần bù
Phần bù mờ của tập mờ A là tập mờ A với hàm thành viên được xác định bởi:
A

x

1

A

(1)

x

A(x)

1

1

A

x

x

x

b)

a)

Hình 1.6: Hàm thành viên của phần bù mờ
Tập bù A của tập mờ A
a) Hàm thành viên của tập mờ A
b) Hàm thành viên của tập mờ A
Phép hợp
Hợp của hai tập mờ A và B có cùng cơ sở M là một tập mờ cũng xác định
trên cơ sở M với hàm thành viên:
A B

x

max

A

x ,

B

(2)

x

A(x)

B(x)

Hình 1.7: Hàm thành viên của hợp hai tập mờ có cùng cơ sở
Số hóa bởi trung tâm học liệu

/>

10

Có nhiều cơng thức khác nhau được dùng để tính hàm thành viên

A B

của

hợp hai tập mờ như:
1.

max A x ,
1 nếu min

x

A B

2.

A B

x

3.

A B

x

4.

A B

x

a)

min 1,

1

A

A

x

x

x

x ,

B

x

0

0

(Phép hợp Lukasiewicz)

x
B

B

B

A

x

B

B

x

nếu min

x
x ,

A

x

A

x

A

B

(Tổng Einstein)

x
A

x .

(Tổng trực tiếp)...

x

B

A(x)

A(y)

x

y

Hình 1.8a: Phép hợp hai tập mờ không cùng cơ sở: Hàm thành viên của 2 tập
mờ A, B
b)

A

x, y
x, y

B

x

M N

x

M N

y

y

Hình 1.8b: Phép hợp hai tập mờ không cùng cơ sở: Đưa 2 tập mờ về chung một
cơ sở MxN
c)

A B

x, y

x
M N

y

Hình 1.8c: Phép hợp hai tập mờ khơng cùng cơ sở: Hợp 2 tập mờ trên cơ sở MxN
Số hóa bởi trung tâm học liệu

/>

11

Có hai tập mờ A (cơ sở M) và B (cơ sở N). Do hai cơ sở M và N độc lập

với nhau nên hàm thành viên
và ngược lại

B

x ,y

x , x M của tập mờ A sẽ không phụ thuộc vào N

A

N của tập mờ B cũng sẽ không phụ thuộc vào M. Điều này

thể hiện ở chỗ trên cơ sở mới là tập tích MxN hàm
dọc theo trục y và

B

A

x phải là một mặt “cong”

y là một mặt “cong” dọc theo trục x. Tập mờ A được định

nghĩa trên hai cơ sở M và MxN. Để phân biệt được chúng, ký hiệu A sẽ được dùng
để chỉ tập mờ A trên cơ sở MxN. Tương tự, ký hiệu B được dùng để chỉ tập mờ B
trên cơ sở MxN, với những ký hiệu đó thì:
N và

A

x, y

A

x , y

B

x, y

B

y , x M.

Sau khi đã đưa được hai tập mờ A, B về chung một cơ sở là MxN thành A
và B thì hàm thành viên

A, B

x, y của tập mờ A

B được xác định theo cơng thức

tính tổng trực tiếp.
Phép Giao
Giao của tập mờ A và tập mờ B là tập mờ A B với hàm thuộc được xác
định bởi:
A B

(x) = min(

A

(x),

B

A B

A

x

(x))

(3)

x

B

x

x
Hình 1.9: Phép giao hai tập mờ cùng cơ sở
Trong cơng thức trên kí hiệu min xác định phép tính lấy cực tiểu được thực
hiện trên tập mờ, bản chất phép tính khơng có gì thay đổi.
Có nhiều cơng thức khác nhau được dùng để tính hàm thành viên

A B

giao hai tập mờ như:

Số hóa bởi trung tâm học liệu

/>
của


12

1.

A B

min A x ,
0 nếu max

x

2.

A B

x

3.

A B

x

4.

A B

x

m ax 0,

A

2

A

A

x .

x

A

x ,

x

A

x

B

x
B

nếu max

B

x

B

x

A

A

x .

B

x

1

(Tích Einstein)
(Tích đại số)...

x

B

x

(Phép giao Lukasiewicz)

x

x

B

1

1

B

x ,

Công thức trên cũng áp dụng được cho hợp hai tập mờ không cùng cơ sở
bằng cách đưa cả hai tập mờ về chung một cơ sở là tích của hai cơ sở đã cho.
Chẳng hạn có hai tập mờ A định nghĩa trên cơ sở M và B định nghĩa trên cơ
sở N. Do hai cơ sở M và N độc lập với nhau nên hàm thành viên
tập mờ A sẽ không phụ thuộc vào N và ngược lại

B

y ,y

B

y

x , x M của

N của tập mờ B cũng

sẽ không phụ thuộc vào M. Trên cơ sở mới là tập tích MxN hàm
“cong” dọc theo trục y và

A

A

x là một mặt

là một mặt “cong” dọc theo trục x. Tập mờ A

(hoặc B) được định nghĩa trên hai cơ sở M (hoặc N) và MxN. Để phân biệt kí hiệu
A (hoặc B ) sẽ được dùng để chỉ tập mờ A (hoặc B) trên cơ sở mới là MxN. Với

những kí hiệu đó thì:
N và

A

x, y , y

B

x, y , x M
A B

x

x
M N

y
Hình 1.10: Phép giao hai tập mờ khơng cùng cơ sở
Số hóa bởi trung tâm học liệu

/>

13

Tích đề các
Giả sử A1, A2, ..., An là các tập mờ trên các tập vũ trụ U1, U2, ..., Un tương
ứng. Tích đề-các của A1, A2, ..., An là tập mờ A= A1 x A2 x ... x An trên khơng gian
tích U1 x U2 x ... x Un với hàm thành viên được xác định bởi:
A

x1 , x2 ,..., xn

min

A

x1 ,

A

x2 ,...,

A

xn

(4)

x1 U1 , x2 U 2 ,..., xn U n ,

Phép chiếu
Giả sử A là tập mờ trên khơng gian tích U1xU2. Hình chiếu của A trên U1 là
tập mờ A1 với hàm thuộc được xác định bởi:
A

x

max
y U2

A

(5)

x, y

Định nghĩa trên có thể mở rộng cho trường hợp khơng gian tích n chiều
Mở rộng hình trụ
Giả sử A1 là tập mờ trên vũ trụ U1. Mở rộng hình trụ của A1 trên khơng gian
tích U1xU2 là tập mờ A với hàm thuộc được xác định bởi:
A

(x, y) =

A1

(x)

(6)

Các phép tốn mở rộng
Ngồi các phép tốn chuẩn: phần bù, hợp, giao được đề cập ở trên còn có
nhiều cách mở rộng phép tốn trên tập mờ khác có tính tổng qt hóa cao hơn.
Phần bù mờ
Giả sử xét hàm C:[0,1] -> [0,1] cho bởi công thức C(a) = 1 – a, a
Khi đó hàm thuộc của phần bù chuẩn trở thành

A

x

C

A

[0,1].

x . Nếu tổng qt

hố tính chất của hàm C thì ta sẽ có tổng qt hố định nghĩa của phần bù mờ. Từ
đó ta có định nghĩa:
Phần bù mờ của tập mờ A là tập mờ A với hàm thuộc được xác định bởi
A

x

C

A

x , trong đó C là một hàm số thoả các điều kiện sau:

1. Tiên đề C1 (điều kiện biên): C(0) = 1, C(1) = 0
2. Tiên đề C2 (đơn điệu giảm): a, b [0,1]. Nếu aHàm C thoả các điều kiện trên được gọi là hàm phần bù.
Số hóa bởi trung tâm học liệu

/>

14

Ta thấy rằng hàm thuộc của phần bù chuẩn là một hàm đặc biệt trong họ

các hàm phần bù.
Ví dụ 7:
1 a
trong đó
1 a

Hàm phần bù Sugeno C a

bù chuẩn là trường hợp đặc biệt của hàm Sugeno khi
1 aw

Hàm phần bù Yager C a

1
w

là tham số thoả > -1. Hàm
= 0.

trong đó w là tham số thoả w > 0.

Hàm bù chuẩn là trường hợp đặc biệt của hàm Yager khi w = 1.
Hợp mờ – các phép toán S-norm
Phép tốn max trong cơng thức hàm hợp mờ chuẩn có thể được tổng qt
hố thành các hàm S-norm:
Một hàm số S: [0,1]x[0,1] -> [0,1] được gọi là một S-norm nếu thoả các
điều kiện sau:
1. Tiên đề S1 (điều kiện biên): S(0,a) = a, a [0,1]
2. Tiên đề S2 (giao hoán): S(a,b) = S(b,a), a,b [0,1]
3. Tiên đề S3 (kết hợp): S(S(a,b),c) = S(a,S(b,c)), a,b,c [0,1]

4. Tiên đề S4 (đơn điệu tăng): Nếu a b và c d thì S(a,c) S(b,d),
a,b,c,d [0,1]
S-norm còn được gọi là co-norm hoặc T-đối chuẩn.
Hợp của tập mờ A và tập mờ B là tập mờ A B với hàm thuộc được xác
định bởi:
A B

x

S

A

x ,

B

x

trong đó S là một S-norm
Ngồi hàm max, ta có một số hàm S-norm quan trọng sau đây:
 Tổng Drastic :

a b

a if
b if
1 if

b

a
a

Số hóa bởi trung tâm học liệu

0
0

0, b

0

/>

15

 Tổng chặn:

a

b min(1, a b)

 Tổng đại số:

a b

a b ab

 Phép hợp Yager:

S w ( a, b)

min 1, (a

1
w w

w

b )

Trong đó w là tham số thoả w > 0
Giao mờ – các phép tốn T-norm
Ta có định nghĩa hàm T-norm là tổng quát hoá của hàm min:
Một hàm số T: [0,1]x[0,1] -> [0,1] được gọi là một T-norm nếu thoả các
điều kiện:
1. Tiên đề T1 (điều kiện biên): T(1,a) = a, a [0,1]
2. Tiên đề T2 (giao hoán): T(a,b) = T(b,a), a,b [0,1]
3. Tiên đề T3 (kết hợp): T(T(a,b),c) = T(a,T(b,c)), a,b,c [0,1]
4. Tiên đề T4 (đơn điệu tăng): Nếu a b và c d thì T(a,c) T(b,d),
a,b,c,d [0,1]
T-norm còn được gọi là T-chuẩn hoặc chuẩn tam giác.
Giao của tập mờ A và tập mờ B là tập mờ A B với hàm thuộc được xác
định như sau:
A B

x

T

A

x ,

B

x

Trong đó T là một T-norm.
Ngồi hàm min, ta có một số hàm T-norm quan trọng sau đây:
 Tích Drastic:

a b

 Tích chặn:

a

a if
b if

b 1
a 1

0 if

a 1, b 1

b max( 0, a b 1)

Số hóa bởi trung tâm học liệu

/>

16

 Tích đại số:

a.b ab

 Phép giao Yager:

Tw (a, b) 1 min 1, ((1 a )

1
w w

w

(1 b) )

Trong đó w là tham số thoả w>0
Định lý: Với mọi T-norm bất kỳ T và S-norm bất kỳ S ta có:
a b

T(a,b)

min(a,b)

max(a,b)

S(a,b)

a b

Tích đề-các mờ
Tích đề-các của tập mờ A1, A2, …, An trên các vũ trụ U1, U2, …, Un tương
ứng là tập mờ A = A1 x A2 x … x An trên khơng gian tích u = U1 x U2 x … x Un với
hàm thuộc được xác định như sau:
A

x1 , x2 ,..., xn

x1 U 1 , x 2

A1

x T

U 2 , …, xn

A2

x T ...T

An

x

Un

Trong đó T là một T-norm bất kỳ.
Ta thấy đây là định nghĩa mở rộng cho tích đề-các chuẩn khi thay thế hàm
min bằng một T-norm bất kỳ.
Quan hệ mờ
Cho U và V là các vũ trụ. Khi đó một quan hệ mờ hai ngôi R giữa U và V là
một tập mờ trong tích đề-các UxV. Như vậy ta có thể xác định hàm thuộc cho quan
hệ mờ theo cách tính hàm thuộc cho tích đề-các mờ.
Khi U = V ta nói R là quan hệ trên U.
Tổng quát một quan hệ mờ R giữa các tập U1, U2, …, Un là tập mờ A = A1 x
A2 x … x An trên khơng gian tích u = U1 x U2 x … x Un. Trong đó Ai Ui, i = 1..n
Hợp của các quan hệ mờ
Hợp của quan hệ mờ R từ U đến V và quan hệ mờ Z từ V đến W là quan hệ
mờ RoZ từ U đến W có hàm thuộc xác định bởi
RoS

u, w

max T
v V

Số hóa bởi trung tâm học liệu

R

u, v ,

z

v, w

/>

17

Trong T là một T-norm bất kỳ.
Các hàm thuộc quan trọng sau được dùng rộng rãi để xác định hợp của các
quan hệ mờ :
 Hàm hợp max-min:
RoS

u, w

max min

R

v V

u, v ,

z

v, w

 Hàm hợp max-tích (hay max-prod):
RoS

u, w

max max

R

v V

u, v .

z

v, w

Các phép toán trên số mờ
Cộng:
[a,b] + [d,e] = [a+d, b+e]
Trừ:
[a,b] - [d,e] = [a-e, b-d]
Nhân:
[a,b] * [d,e] = [min(ad,ae, bd, be), max(ad,ae, bd, be)]
Chia:
[a,b] / [d,e] = [min(a/d,a/e, b/d, b/e), max(a/d,a/e, b/d, b/e)]
Số mờ hình thang
M(a,b,c,d)
0

M

z

z a

b a
1
d z
d c
0

a

b c

z

a

a

z

b

b

z

c

c

z

d

d

z

d

Hình 1.11: Số mờ hình thang

Số hóa bởi trung tâm học liệu

/>