ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC CÔNG NGHỆ
PHẠM LÊ CƯƠNG
VỀ MỘT MÔ HÌNH CSDL QUAN HỆ VỚI THÔNG
TIN KHÔNG CHẮC CHẮN DẠNG NGÔN NGỮ
GẦN TỰ NHIÊN
LUẬN VĂN THẠC SĨ
CÔNG NGHỆ THÔNG TIN
HÀ NỘI - 2008
ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC CÔNG NGHỆ
PHẠM LÊ CƯƠNG
VỀ MỘT MÔ HÌNH CSDL QUAN HỆ VỚI THÔNG
TIN KHÔNG CHẮC CHẮN DẠNG NGÔN NGỮ
GẦN TỰ NHIÊN
Mã số
: 1.01.10
LUẬN VĂN THẠC SĨ
CÔNG NGHỆ THÔNG TIN
Người hướng dẫn khoa học: PGS,TSKH NGUYỄN CÁT HỔ
HÀ NỘI - 2008
3
MỤC LỤC
LỜI CAM ĐOAN .......................................................................................................1
LỜI CẢM ƠN .............................................................................................................2
MỤC LỤC ...................................................................................................................3
DANH MỤC CÁC KÝ HIỆU CÁC CHỮ VIẾT TẮT ...............................................5
DANH MỤC CÁC HÌNH VẼ.....................................................................................6
MỞ ĐẦU .....................................................................................................................7
CHƯƠNG 1 – TỔNG QUAN .....................................................................................9
1.1 Lý thuyết mờ .........................................................................................................9
1.1.1 Tập mờ ...............................................................................................................9
1.1.2 Lôgic mờ ..........................................................................................................10
1.1.3 Hạn chế của việc quản lý và thao tác thông tin mờ biểu thị bằng lý thuyết tập
mờ trong CSDL .........................................................................................................11
1.1.4 Giới thiệu đại số gia tử .....................................................................................12
1. 1.4.1 Đại số gia tử .................................................................................................14
1. 1.4.1.1 Những phát biểu cơ bản ............................................................................15
1.1.4.1.2 Các khái niệm và tính tuyến tính ...............................................................15
1.1.4.1.3 Topo và tính trù mật trong ĐSGT ..............................................................17
1.1.4.1.4 Độ đo tính mờ ............................................................................................20
1.1.4.1.5 Hàm định lượng ngữ nghĩa của biến ngôn ngữ ..........................................24
1.1.4.1.6 Sự tương tự tô-pô của dữ liệu định nghĩa bởi ánh xạ định lượng ngữ nghĩa
...................................................................................................................................28
CHƯƠNG 2 – XÂY DỰNG MÔ HÌNH CSDL QUAN HỆ VỚI THÔNG TIN
NGÔN NGỮ .............................................................................................................33
2.1 Giới thiệu chung về cơ sở dữ liệu với thông tin ngôn ngữ .................................33
2.2 Quản lý ngữ nghĩa dữ liệu dựa trên ĐSGT .........................................................41
2.3 Phụ thuộc hàm dựa trên độ tương tự trong CSDL ngôn ngữ ..............................46
2.4 Các đặc điểm và tính chất của mô hình mới .......................................................56
CHƯƠNG 3- CÀI ĐẶT MỘT SỐ THỦ TỤC CỦA CSDL NGÔN NGỮ ..............58
3.1 Lập hàm sign .......................................................................................................58
3.2 Lập hàm tính độ đo tính mờ fm ..........................................................................59
3.3 Lập hàm định lượng ngữ nghĩa QSF ...................................................................61
3.4 Lập hàm ánh xạ giá trị các giá trị biến ngôn ngữ sang miền giá trị thực ............62
3.5 Lập hàm xác định lân cận mức k ........................................................................63
3.6 Sửa đổi các thao tác truyền thống trên cơ sở dữ liệu: insert, update, delete, select
...................................................................................................................................63
3.6.1 Thao tác insert ..................................................................................................64
3.6.2 Thao tác update ................................................................................................64
3.6.3 Thao tác delete .................................................................................................64
3.6.4 Thao tác select ..................................................................................................65
3.7 Viết ứng dụng ......................................................................................................65
3.7.1. Các màn hình nhập số liệu ..............................................................................66
4
3.7.2. Các báo cáo chính ...........................................................................................71
KẾT LUẬN ...............................................................................................................74
TÀI LIỆU THAM KHẢO .........................................................................................75
PHỤ LỤC ..................................................................................................................78
5
DANH MỤC CÁC KÝ HIỆU CÁC CHỮ VIẾT TẮT
CSDL: Cơ sở dữ liệu
ĐSGT: Đại số gia tử
6
DANH MỤC CÁC HÌNH VẼ
Hình 1: Tập mờ và tập rõ ..........................................................................................10
Hình 2: Mô tả cường độ dòng điện ...........................................................................12
Hình 3: Minh họa độ đo tính mờ ...............................................................................23
Hình 4: Một ví dụ về hệ lân cận ................................................................................35
Hình 5: Ví dụ về hệ lân cận .......................................................................................40
7
MỞ ĐẦU
Trong những năm gần đây, CSDL mờ đã được nhiều tác giả trong và ngoài nước
quan tâm nghiên cứu và đã có những kết quả đáng kể [1,6,14,15]. Có nhiều cách
tiếp cận khác nhau như cách tiếp cận theo lý thuyết tập mờ [2,14], theo lý thuyết
khả năng do Prade và Testemale năm 1983, tương tự [11] ...Tất cả các cách tiếp cận
trên nhằm mục đích nắm bắt và xử lý một cách thỏa đáng trên một quan điểm nào
đó các thông tin không chính xác (Unexact), không chắc chắn (uncertainty) hay
những thông tin không đầy đủ (Incomplete). Do sự đa dạng của những loại thông tin
này nên chúng ta gặp rất khó khăn trong biểu thị ngữ nghĩa và thao tác với chúng.
Trong những năm gần đây đại số gia tử được nhiều tác giả nghiên cứu trong
[3,4,5,12,13] và đã có những ứng dụng đáng chú ý, đặc biệt trong lập luận xấp xỉ và
trong một số bài toán điều khiển. Vì vậy, mặc dù đã có nhiều kết quả nghiên cứu về
CSDL mờ, theo chiều hướng đó cách tiếp cận nghiên cứu CSDL mờ với ngữ nghĩa
dựa trên đại số gia tử vẫn có thể được xem là một vấn đề nghiên cứu mới.
Khác với CSDL mờ trong đó giá trị ngôn ngữ được xem như là nhãn của tập
mờ, theo cách tiếp cận của ĐSGT, các giá trị như vậy được xem chính là các phần
tử của đại số gia tử, vì theo cách biểu thị ngữ nghĩa trong ĐSGT, chúng có thể được
xem chính là các giá trị ngôn ngữ.
Con người thường phải đối mặt với thông tin không chắc chắn và do đó có một
nhu cầu tự nhiên đối với việc xây dựng CSDL mờ. Việc quản lý và thao tác thông
tin mờ biểu thị bằng lý thuyết tập mờ trong CSDL đã và đang được quan tâm
nghiên cứu mạnh mẽ. Tuy nhiên người ta vẫn gặp một số khó khăn trong biểu diễn
và quản lý thông tin mờ.
Nhiệm vụ của đề tài là nghiên cứu tiếp mô hình CSDL với thông tin được biểu thị
bằng ngôn ngữ tự nhiên với ngữ nghĩa dựa trên cấu trúc thứ tự của đại số gia tử và
phân tích những ưu điểm của mô hình mới. Nghiên cứu và cài đặt các thủ tục thao
8
tác dữ liệu để bảo đảm tính trọn vẹn dữ liệu đối với mô hình CSDL mới này và
chứng tỏ sự thuận tiện và đơn giản của loại mô hình này.
9
CHƯƠNG 1 – TỔNG QUAN
1.1 Lý thuyết mờ
1.1.1 Tập mờ
Các tập mờ hay tập hợp mờ (tiếng Anh: Fuzzy set) là một mở rộng của lý thuyết
tập hợp kinh điển và được dùng trong lôgic mờ. Trong lý thuyết tập hợp kinh đ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 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á 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 thuộc (membership function)
.
Các tập mờ được coi là một mở rộng của lý thuyết tập hợp kinh điển là vì, với một
miền nhất định, một hàm thuộc có thể giữ vai trò của một hàm đặc trưng ánh xạ mỗi
phần tử tới một giá trị 0 hoặc 1 như trong khái niệm kinh điển.
Định nghĩa 1.1
Một tập hợp mờ trên một tập hợp kinh điển Χ được định nghĩa như sau:
Hàm thuộc μA(x) lượng hóa mức độ mà các phần tử x thuộc về tập cơ sở Χ. Nếu
hàm cho kết quả 0 đối với một phần tử thì phần tử đó không có trong tập đã cho, kết
quả 1 mô tả một thành viên toàn phần của tập hợp. Các giá trị trong khoảng mở từ 0
đến 1 đặc trưng cho các thành viên mờ.
10
Hình 1: Tập mờ và tập rõ
Hàm thuộc μA(x) thỏa mãn các điều kiện sau
1.1.2 Lôgic mờ
Lôgic mờ (tiếng Anh: Fuzzy logic) được phát triển từ lý thuyết tập mờ để thực hiện
lập luận một cách xấp xỉ thay vì lập luận chính xác theo lôgic vị từ kinh điển. Lôgic
mờ có thể được coi là mặt ứng dụng của lý thuyết tập mờ để xử lý các giá trị trong
thế giới thực cho các bài toán phức tạp (Klir 1997).
Người ta hay nhầm lẫn khả năng đúng với xác suất. Tuy nhiên, hai khái niệm này
khác hẳn nhau; độ đúng đắn của lôgic mờ biểu diễn độ thuộc với các tập được định
nghĩa không rõ ràng, không phải khả năng xảy ra một biến cố hay điều kiện nào đó.
Để minh họa sự khác biệt, xét tình huống sau: Bảo đang đứng trong một ngôi nhà
có hai phòng thông nhau: phòng bếp và phòng ăn. Trong nhiều trường hợp, trạng
thái của Bảo trong tập hợp gồm những thứ "ở trong bếp" hoàn toàn đơn giản: hoặc
là anh ta "trong bếp" hoặc "không ở trong bếp". Nhưng nếu Bảo đứng tại cửa nối
giữa hai phòng thì sao? Anh ta có thể được coi là "có phần ở trong bếp". Việc định
lượng trạng thái "một phần" này cho ra một quan hệ thuộc đối với một tập mờ.
Chẳng hạn, nếu Bảo chỉ thò một ngón chân cái vào phòng ăn, ta có thể nói rằng Bảo
ở "trong bếp" đến 99% và ở trong phòng ăn 1%. Một khi anh ta còn đứng ở cửa thì
11
không có một biến cố nào (ví dụ một đồng xu được tung lên) quyết định rằng Bảo
hoàn toàn "ở trong bếp" hay hoàn toàn "không ở trong bếp". Các tập mờ được đặt
cơ sở trên các định nghĩa mờ về các tập hợp chứ không phải dựa trên sự ngẫu nhiên.
Lôgic mờ cho phép độ thuộc có giá trị trong khoảng đóng ([0,1]), và ở hình thức
ngôn từ, các khái niệm không chính xác như "hơi hơi", "gần như", "khá là" và "rất".
Cụ thể, nó cho phép quan hệ thành viên không đầy đủ giữa thành viên và tập hợp.
Tính chất này có liên quan đến tập mờ và lý thuyết xác suất. Lôgic mờ đã được đưa
ra lần đầu vào năm 1965 bởi GS. Lotfi Zadeh tại Đại học California, Berkeley.
1.1.3 Hạn chế của việc quản lý và thao tác thông tin mờ biểu thị bằng lý thuyết
tập mờ trong CSDL
Chúng ta có thể nhận thấy việc sử dụng tập mờ và mô hình quan hệ để xử lý thông
tin mờ có một số hạn chế nhất định:
(i) Với các thuộc tính mà giá trị là dữ liệu kinh điển và dữ liệu mờ, (gọi là các thuộc
tính mờ), kiểu dữ liệu không đồng nhất, do đó, việc xử lý dữ liệu gặp nhiều khó
khăn. Chẳng hạn, do dữ liệu ngôn ngữ được biểu diễn dưới dạng các tập mờ, nghĩa
là được thể hiện bởi các hàm thuộc của U, miền thuộc tính cơ sở, vào khoảng đơn vị
[0,1], định nghĩa các quan hệ đối sánh trên các dữ liệu này không phải là một vấn đề
giản đơn và có nhiều cách giải quyết khác nhau. Tất nhiên, sự thỏa mãn các mối
quan hệ trong trường hợp này được định nghĩa dựa trên logic đa trị thay vì logic hai
giá trị. Chúng ta hãy xem xét một thí dụ, thuộc tính AGE (Tuổi) và giả thiết rằng dữ
liệu rather young được thể hiện bằng một tập mờ R.young với hàm thuộc R.young. Với
trường hợp dữ liệu 34 và rather young, đẳng thức 34 = Rather young có thể được
diễn giải là thỏa mãn mức độ chân lý R.young(34). Song có một câu hỏi khó hơn là
làm sao ta có thể diễn giải điều kiện thỏa mãn logic của bất đẳng thức Rather young <
34? . Có một cách là diễn giải bất đẳng thức này bằng cách tính tập mức
R.young,
của tập mờ R.young và kiểm tra bất đẳng thức R.young, < 34, trong đó bất đẳng thức
có nghĩa rằng (u R.young,)(u < 34). Nếu bất đẳng thức này được thỏa mãn,
12
chúng ta nói rằng mức độ thỏa mãn của bất đẳng thức này là giá trị chân lý của .
Như vậy, tùy theo cách diễn giải của người sử dụng, ta cần thiết kế các thủ tục để
quản lý dữ liệu có thuộc tính mờ.
Hình 2: Mô tả cường độ dòng điện
(ii) Việc diễn giải về ngữ nghĩa của dữ liệu ngôn ngữ là một vấn đề cơ bản, tuy
nhiên, nó hoàn toàn phụ thuộc vào cách biểu thị quá chủ quan về ngữ nghĩa của
ngôn ngữ biểu diễn bằng tập mờ. Điều này có nghĩa là mọi người thường tự thiết kế
các tập mờ cho mỗi ứng dụng, trừ khi chọn lựa các giá trị dựa trên ngữ nghĩa trong
thực tế. Không có ràng buộc chính thức nào cho thiết kế kiểu này. Ví dụ như, để
diễn giải nghĩa của bảy thuật ngữ terms very very small, very small, small, medium,
large, very large, very very large nhằm mô tả các giá trị của cường độ dòng điện
trong khoảng [0, 10] am-pe, người ta có thể dựng bảy tam giác cân như hình 2. Đó
là các tam giác bằng nhau trừ tam giác đầu và cuối, hai tam giác này bằng một nửa
các tam giác hoàn chỉnh. Vấn đề dường như rất kỹ thuật và chủ quan, và một câu
hỏi phát sinh là vì sao các tam giác bằng nhau và các cạnh đáy của chúng nằm trùng
lên nhau đúng một nửa. Điều này có vẻ không phù hợp khi xem xét ngữ nghĩa tự
nhiên của các thuật ngữ này.
1.1.4 Giới thiệu đại số gia tử
Trong phần này, chúng ta sẽ tiếp cận đại số gia tử về ngữ nghĩa dựa trên quan hệ
thứ tự của dữ liệu ngôn ngữ của biến ngôn ngữ để xây dựng mô hình CSDL quan hệ
và nghiên cứu các phép thao tác trên các dữ liệu của CSDL với thông tin ngôn ngữ.
Trong cách tiếp cận này, miền giá trị của thuộc tính được phép nhận giá trị ngôn
13
ngữ và giả thiết tập các giá trị ngôn ngữ được nhúng vào một đại số gia tử. Ngữ
nghĩa của các quan hệ hai ngôi trên mỗi miền giá trị thuộc tính, bao gồm các giá trị
kinh điển và các giá trị ngôn ngữ, sẽ được nghiên cứu và trên cơ sở đó các phép
toán đại số quan hệ sẽ được định nghĩa phù hợp với ngữ nghĩa mới. Việc tiếp cận
dựa trên đại số gia tử chỉ ra rằng mô hình CSDL với thông tin mờ trở nên rõ ràng,
nhất quán trong thao tác và thao tác dữ liệu đơn giản hơn.
14
1. 1.4.1 Đại số gia tử
Để xây dựng cách tiếp cận đại số gia tử đối với CSDL mờ, trong phần này
xin trình bày tổng quan về một số nét cơ bản của đại số gia tử và khả năng biểu thị
ngữ nghĩa dựa vào cấu trúc của đại số gia tử.
Chúng ta xét miền ngôn ngữ của biến chân lý TRUTH gồm các từ sau:
Dom(TRUTH)={true, false, very true, very false, more-or-less true, more-or-less
false, possibly true, possibly false, approximately true, approximately false, little
true, little false, very possibly true, very possibly false.....}, trong đó true, false là
các từ nguyên thuỷ, các từ nhấn (mordifier hay intensifier) very, more-or-less,
possibly, approximately true, little gọi là các gia tử (hedges). Khi đó miền ngôn ngữ
T=dom(TRUTH) có thể biểu thị như một đại số AH = ( X, C, H, ), trong đó C là
tập các từ nguyên thuỷ được xem là các phần tử sinh. H là tập các gia tử được xem
như là các phép toán một ngôi, quan hệ trên các từ (các khái niệm mờ) là quan hệ
thứ tự được "cảm sinh" từ ngữ nghĩa tự nhiên. Ví dụ dựa trên ngữ nghĩa, các quan
hệ thứ tự sau là đúng: falsetrue, more truevery true nhưng very false more false,
possibly truetrue nhưng falsepossibly false ... . Tập X được sinh ra từ C bởi các
phép tính trong H. Như vậy mỗi phần tử của X sẽ có dạng biểu diễn x=hnhn1.......h1c,
cC. Tập tất cả các phần tử được sinh ra từ một phần tử x được ký hiệu là
H(x). Nếu C có đúng hai từ nguyên thuỷ mờ, thì một được gọi là phần tử sinh
dương ký hiệu là c+, một gọi là phần tử sinh âm ký hiệu là c- và ta có c- < c+. Trong
ví dụ trên True là dương còn False là âm.
Nếu các tập các phép toán (hay gia tử) H+, H và tập C các phần tử sinh là
tuyến tính thì tập nền X = H(G) cũng tuyến tính. Tuy nhiên tập H(G) thiếu các phần
tử giới hạn, hay nói khác đi nó không đóng đối với phép “lấy giới hạn”. Chính vì
thế, đại số gia tử đầy đủ AX = < X, C, H, , , > được xây dựng bằng cách bổ
sung vào tập X các phần tử giới hạn nhằm làm đẩy đủ miền giá trị của nó.
15
1. 1.4.1.1 Những phát biểu cơ bản
Cho X là một tập sắp thứ tự một phần (partially ordered set) và U, V là hai tập
con của X. Ta ký hiệu U V (phát biểu tương ứng cho U < V), nếu (x U)(y
V){x y} (tương ứng, {x < y}).
Xét đại số gia tử đầy đủ AX = < X, G, LH, , , >. Giả sử x X và nếu nó
có biểu diễn dưới dạng x = hn... h1u, với u X, thì ta sẽ quy ước sử dụng ký pháp
sau: x(i) = hi-1... h1u, 1 i n, với quy ước khi i = 1 thì h0 = I, phép toán đồng nhất
trên X.
Định nghĩa 1.1: ĐSGT AX = < X, G, LH, , , > được gọi là tự do (hay sinh
tự do) nếu với mọi h LH mọi x LH(G) ta đều có hx x. Về trực quan điều này
có nghĩa, mỗi gia tử (phép toán) khi tác động vào một phần tử bất kỳ trong LH(G)
đều được sinh (một cách tự do) ra phần tử mới.
Những kết quả sau đây sẽ được tham chiếu đến trong các chứng minh sau này.
Định lý 1.1: Xét ĐSGT AX = (X, G, LH, , , ) là đại số gia tử mở rộng đầy
đủ. Với mọi y LH(x), x X ta có:
i/
y x
ii/
x H(x) x.
và
y x
Mệnh đề 1.1: Xét ĐSGT mở rộng đầy đủ AX = (X, G, LH, s, , ). Với mọi h
LHic, mọi k LHci+1, nếu x, x lim(x) (hay x, x LH(G)) thì:
hx kx kéo theo
hx = kx,
hx kx kéo theo
fhx = kx.
Bổ đề 1.1: Với mọi x H(G),
x = supremum{Vno+x: o+ UOS, o+x x, n = 1, 2, ...} = Vno+x = o+x và
x = infimum{Vnox: o UOS, ox x, n = 1, 2, ...} = Vnox = ox,
lưu ý rằng V là positive đối với cả hai toán tử đơn vị trong UOS và dãy {Vno+x: o+
UOS, o+x x, n = 1, 2, ...} đơn điệu tăng còn dãy {Vnox: o UOS, ox x, n = 1,
2, ...} đơn điệu giảm.
1.1.4.1.2 Các khái niệm và tính tuyến tính
Định nghĩa 1.2. Đại số gia tử (mở rộng) đầy đủ AX = (X, G, H, , , ) được
gọi là tuyến tính nếu tập các phần tử sinh G = {0, c, W, c+, 1} và các dàn các gia tử
H- = {h-1, ..., h-q}và H+ = {h1,..., hp} là sắp thứ tự tuyến tính, ở đây H = HH+, và
16
giả sử h-1 < h-2 < ... < h-q; h1 < ...< hp. Ký hiệu h0 = I còn Hc mà được hiểu là c
{, +}.
ĐSGT mở rộng đầy đủ với H+ và H là các tập sắp một phần (poset) đã nghiên
cứu. Trong trường hợp chúng là tuyến tính thì LH+ = H+ và LH = H. Với giả thiết
này ta có kết quả quan trọng và được phát biểu trong bổ đề sau:
Bổ đề 1.2. Cho ĐSGT AX = (H(G), G, H, ). Nếu G và H thỏa mãn các giả thiết
như trong Định nghĩa 1.2 thì H(G) là tập sắp thứ tự tuyến tính.
Đối với trường hợp ĐSGT đầy đủ và tuyến tính, ta cũng có định lý sau về tính
tuyến tính của X.
Định lý 1.2. Nếu đại số gia tử mở rộng đầy đủ AX = (X, G, H, , , ) là tuyến
tính thì tập nền X cũng là tuyến tính hay sắp toàn phần.
Chứng minh: Ta có X = H(G) Lim(X). Vì theo Bổ đề 1.2, H(G) là tuyến tính,
nên ta chỉ cần chứng tỏ với mọi x và y, với ít nhất một trong hai phần tử này thuộc
tập Lim(X), chúng đều sánh được với nhau.
Trước hết giả sử chỉ một trong hai phần tử x và y, chẳng hạn là y, thuộc Lim(X)
và chúng có biểu diễn sau: x = hn ... h1u , y = oy’ với y’ = km ... k1u’. Vì H(G) sắp
toàn phần nên x và y’ phải sánh được với nhau và giả định x < y’ (đối với trường
hợp ngược lại sẽ được chứng minh tương tự bằng đối ngẫu). Khi đó, nếu u và u’
được sinh từ hai từ nguyên thủy khác nhau thì ta có x H(c) và y’ H(c+). Suy ra
y = oy’ c+ c x.
Nếu cả hai u, u’ H(c), c {c, c+} và giả sử u = u’, x = hn ... h1u và y’ = km
... k1u với h1 k1. Cũng như trên ta giả định x < y’ và do đó kéo theo h1u < k1u. Lập
luận tương tự như trên, ta thu được y = oy’ k1u h1u H(h1u). Vậy y > x.
Một trong các khả năng khác có thể xảy ra là x = hn ... h1y’. Giả thiết x < y’ sẽ
dẫn đến bất đẳng thức h1y’ < y’. Khi đó, y’ y’ H(h1y’) y’. Vì x H(h1y’) và
vì o {, }, từ các bất đẳng thức cuối ta suy ra y = oy’ và x luôn sánh được với
nhau.
Một khả năng còn lại là y’ = km ... k1x. Cũng như trên, giả thiết x < y’ sẽ dẫn đến
bất đẳng thức k1x > x và do đó H(k1x) > x. Do H(k1x) H(y’), nên ta có H(y’) > x.
Suy ra, y = oy’ x.
Bây giờ ta giả thiết cả hai x và y cùng thuộc Lim(X) và chúng có dạng biểu diễn
x = ox’, y = o’y’ và giả sử x’ = hn ... h1u và y’ = km ... k1u’. Vì H(G) sắp toàn phần
nên x’ và y’ phải sánh được với nhau và, chẳng hạn, x’ < y’. Do đó, tương tự như
17
trên, nếu u và u’ được sinh ra từ hai từ nguyên thủy khác nhau thì ta phải có x’
H(c) còn y’ H(c+). Suy ra, y = o’y’ c+ = c ox’ = x.
Trường hợp cả hai u, u’ H(c), c {c, c+} và giả sử u = u’, x’ = hn ... h1u và
y’ = km ... k1u, với h1 k1. Cũng như trên ta giả định x’ < y’ và do đó h1u < k1u. Lập
luận tương tự như trên, ta thu được y = o’y’ k1u h1u > ox’ = x.
Trường hợp x’ = hn ... h1y’. Giả thiết x’ < y’ sẽ dẫn đến bất đẳng thức h1y’ < y’.
Khi đó, y’ y’ H(h1y’) y’. Do H(x’) H(h1y’) và o, o’ {, }, ta có thể
nhận thấy y = o’y’ và x = ox’ phải sánh được với nhau.
Trường hợp còn lại là y’ = km ... k1x’. Giả thiết x’ < y’ sẽ dẫn đến bất đẳng thức
k1x’ > x’ và do đó H(k1x’) > x’. Do H(k1x’) H(y’) và H(G) sắp toàn phần nên ta
kết luận y = o’y’ và x = oy’ là sánh được.
Như vậy định lý đã được hoàn toàn chứng minh.
1.1.4.1.3 Tô-p và tính trù mật trong ĐSGT
Ta biết rằng X = H(G) Lim(X), nghĩa là Lim(X) là tập các điểm giới hạn của
H(G). Ta có thể có cảm nhận trực quan thấy rằng H(G) là tập trù mật trong X theo
nghĩa sau:
Định nghĩa 1.3. Cho X là tập sắp thứ tự một phần và U, V là các tập con của X,
U V. Tập con U được gọi là trù mật trong V nếu (x,y V){ x < y (z U)[x
< z < y]}. Với x < y, ta ký hiệu
= {z X : x < z < y} và cũng gọi là một
khoảng được xác định bởi x và y.
Tuy nhiên như ta sẽ thấy trên cách nhìn topo, họ các tập H(u), u H(G), có tính
chất khá đặc biệt và tính trù mật của H(G) có đặc trưng mạng hơn Định nghĩa 1.3
rất nhiều. Tính chất này là cơ sở để chứng minh một số quả nghiên cứu tiếp theo.
Trước hết ta hãy khảo sát tính topo của họ = {H(u), u H(G)}. Chúng ta biết
rằng một họ bất kỳ các tập con của X được gọi là một cơ sở topo trên X nếu
chúng có các tính chất sau:
o1) ;
o2) Ui , i = 1, ..., k,
k
Ui .
i 1
Mỗi cơ sở topo sẽ sinh ra một topo trên X, tức là họ tất cả các tập con mở của X
và X trở thành không gian topo. Trong không gian topo ta có khái niệm điểm trong
như sau. Xét một tập con V X. Điểm u V được gọi là điểm trong của tập V nếu
(U ){u U V}, nghĩa là có tồn tại một tập con mở của V chứa u.
18
Ta có khái niệm mới về độ trù mật như sau gọi là độ đậm đặc.
Định nghĩa 1.4. Cho một không gian topo X. Tập V X, được gọi là đậm đặc
trong X, nếu với mọi khoảng của X đều chứa ít nhất một điểm trong u, t.l.
(U ){U V & x < U < y}.
Rõ ràng là nếu V là đậm đặc trong X thì V là trù mật trong X.
Ta có bổ đề sau:
Bổ đề 1.3. Cho ĐSGT AX = (X, G, H, , , ), họ ’ = {} là một cơ sở
topo trên X.
Chứng minh: Xét hai tập H(u) và H(v) bất kỳ. Khi đó chỉ có hai khả năng. Nếu
u và v là độc lập, t.l. v H(u) và uH(v), thì H(u) H(v) = . Nếu ngược lại,
chẳng hạn, u H(v) thì H(u) H(v). Từ đó dễ dàng suy ra họ ’ thỏa mãn điều
kiện o2) trên.
Nhằm thiết lập một tính chất quan trọng dưới đây để sử dụng trong nghiên cứu
việc định lượng hóa ĐSGT ta cần bổ đề sau.
Bổ đề 1.4. Cho ĐSGT (mở rộng) đầy đủ, tuyến tính và tự do AX = (X, G, H, ,
, ), xét phần tử x = hn ... h1u H(G) và phép toán o {, }. Khi đó:
(1) Nếu h1u < ox thì khoảng <h1u,ox> chứa ít nhất một điểm trong. Hơn nữa,
tồn tại zi = hi’hi-1 ... h1u = hi’xi-1 sao cho hi’xi-1 < hixi-1 và h1u = zi < H(zi) =
H(hi’xi-1) < ox.
(2) Còn nếu h1u > ox thì khoảng chứa ít nhất một điểm trong và tồn
tại zi = hi’hi-1 ... h1u = hi’xi-1 sao cho hi’xi-1 > hixi-1 và h1u = zi > H(zi) = H(hi’xi-1)
> ox.
Lưu ý rằng trong cả hai trường hợp trên ta đều có H(zi) H(x) = .
Chứng minh: Trước hết ta luôn nhớ rằng, theo Bổ đề 1.2, tập H(G) là tuyến
tính. Đầu tiên ta xét trường hợp h1u < ox, x = hn ... h1u. Theo Bổ đề 1.1, ta có h1u
= Vn-2oh1u < ohn ... h1u. Khi đó tồn tại i sao cho z = Vn-2oh1u = kixi-1, x = hixi-1,
trong đó , là các xâu gia tử tiền tố tương ứng của z và x. Lưu ý rằng, theo Bổ đề
1.1 ta có h1u = kixi-1 = z. Từ bất đẳng thức cuối cùng ta suy ra kixi-1 < hixi-1, vì
trong trường hợp ngược lại ta thu được bất đẳng thức ohn... h1u hixi-1 kixi-1 =
h1u mâu thuẫn với giả thiết h1u < ox. Do đó, H(kixi-1) < H(hixi-1) và điều này dẫn
đến h1u = kixi-1 < H(kixi-1) < hixi-1 ox, vì x H(hixi-1), và H(zi) H(x) = với
zi = kixi-1.
19
Đối với trường hợp h1u > ox, ta chứng minh tương tự bằng đối ngẫu.
Định lý 1.4. Cho AX = (X, G, H, , , ) là đại số gia tử đầy đủ, tuyến tính và
(sinh) tự do. Khi đó tập H(G) là đậm đặc trong X và hơn nữa ta có
x, y X , x < y (u H(G)){ x < H(u) < y }.
Nhớ rằng ta luôn luôn có H(u) H(G).
Chứng minh: Như ta biết X = H(G) Lim(X) và H(G) Lim(X) = và do
đó ta sẽ chứng minh định lý theo từng trường hợp.
(1) Trường hợp x, y H(G), x = hn ... h1u và y = km ... k1u’. Đầu tiên ta giả sử x
H(c), y H(c+) và giả định x = hn ... h1c và y = km ... k1c+. Ta biết rằng, vì AX
là ĐSGT tự do, nên luôn luôn tồn tại gia tử h H sao cho hx > x. Khi đó ta thu
được bất đẳng thức mong muốn là y > H(hx) > x và H(hx) H(x).
Bây giờ ta giả sử u = u’ và h1u k1u’. Vì x < y ta suy ra h1u < k1u’ và do vậy ta
có H(h1u) < H(k1u’). Cũng như trên ta chọn h H sao cho hx > x và khi đó, vì
H(hx) > x, hx H(h1u), y H(k1u’) và H(hx) H(h1u), ta có điều mong muốn y >
H(hx) > x. Nếu việc sinh của x và y có dạng x = hn ... h1y thì x < y kéo theo h1y < y.
Khi đó cũng tồn tại h H sao cho hx > x và do đó ta cũng có y > H(hx) > x. Một
cách hoàn toàn tương tự, nếu y = km ... k1x thì x < y kéo theo k1x > x. Ta chọn h H
sao cho y > hy H(k1x) > x. Do đó y > H(hy) > x và H(hy) H(y).
(2) Trường hợp x H(G) và y = oy’ Lim(X), trong đó o {, }, x = hn ...
h1u và y’ = km ... k1u’. Đối với cả hai khả năng u = c và u’ = c+ hoặc u = u’ và h1u
k1u’, điều kiện x < y dẫn đến H(x) < H(y’). Ta cũng chọn h H sao cho hx > x và
do H(hx) H(x) ta suy ra y = oy’ y’ x > H(hx) > x, nghĩa là ta có bất đẳng
thức mong muốn. Nếu x = hn ... h1y’ thì x H(h1y’) và x x ta cũng có y = y’ > H(hx) > x.
Nếu y’ = km ... k1x thì x < y kéo theo k1x > x và y = oy’ k1x x.
Nếu oy’ = k1x thì y = k1x > x và khi đó k1 không phải là atom (gia tử nhỏ nhất
trong dàn I). Vậy có tồn tại k’ sao cho H(k1x) > H(k’x) > x và điều này dẫn đến y
= oy’ k1x > H(k’x) > x. Ngoài ra ta cũng có H(u) H(x), với u = k’x.
Nếu oy’ > k1x thì tồn tại u sao cho x k1x = z < H(z) < oy’ và H(z) H(y’)
= .
(3) Trường hợp x = ox’ Lim(X) và y H(G), trong đó o {, } và x = hn ...
h1u và y’ = km ... k1u’ được chứng minh tương tự như trong (2).
20
(4) Trường hợp x = ox’ Lim(X) và y = o’y’ Lim(X), trong đó x’ = hn ... h1u
và y’ = km ... k1u’. Lập luận như trong (2), cả hai khả năng đối với u và u’ đều dẫn
đến h1u k1u’, và từ điều kiện x < y ta suy ra h1u < k1u’.
Nếu h1u = k1u, thì có hai khả năng. Thứ nhất là x = ox’ = h1u và khi đó x =
k1u < o’y’. Tồn tại u = zi sao cho x = ox’ = k1u = zi H(zi) = H(ki’xi-1) < o’y’ = y.
Trong trường hợp này ta có H(zi) H(y’) = . Giả sử h1u k1u. Khi đó điều
kiện x < y kéo theo h1u < k1u và do vậy ox’ h1u < k1u o’y’. Nếu h1, k1 không
cùng thuộc tập gia tử Hc thì h1u < u < k1u và nếu các gia tử này đều là nhỏ nhất thì
h1u = k1u. Ta gặp mâu thuẫn. Vậy một trong hai gia tử này không là nhỏ nhất,
chẳng hạn đó là h1. Khi đó có h’ sao cho h1 < h’ và do đó ta có H(h1u) < H(h’u) <
H(k1u). Nếu h1, k1 cùng thuộc tập gia tử Hc thì chúng không thể là hai gia tử kề
nhau, do đó cũng tồn tại h’ sao cho h1u < h’u < k1u và điều này cũng dẫn đến
H(h1u) < H(h’u) < H(k1u). Từ đây ta suy ra x = ox’ h1u < H(h’u) < k1u o’y’
= y, nghÜa lµ. ta có các bất đẳng thức mong muốn và cũng có điều kiện H(h’u)
H(y’) = .
Bây giờ ta giả định x’ và y’ có dạng liên hệ sau: x’ = hn ... h1y’. Khi đó vì x’
H(h1y’), bất đẳng thức x < y kéo theo h1y’ < y’ và H(h1y’) < y’. Do vậy, vì x’
H(y’), ta suy ra được các bất đẳng thức y’ x = ox’ x’ h1y’ y’ < k1u
y’. Vậy o’ = . Lấy h’ sao cho y’ < h’y’ ta sẽ có x = ox’ < y’ < H(h’y’) y’ = y
và H(h’y’) H(y’).
Vì đối với trường hợp y’ = hn ... h1x’ sẽ được chứng minh tương tự nên định lý hoàn
toàn được chứng minh.
1.1.4.1.4 Độ đo tính mờ
Cho đại số gia tử AX = (X, C, H, ), với X là tập nền, C ={c+, c-}trong đó c+
và c- tương ứng là phần tử sinh dương và âm. H =H+ H- với H = {h1, h2, ..., hp} và
H+ = {hp+1, ..., hp+q}, h1>h2> ... >hp và hp+1<...
- Xem thêm -