Tìm hiểu Logic mô tả EL
LỜI NÓI ĐẦU
Logic mô tả từ lâu đã đúng một vai trò quan trọng như một loại hình tiêu biểu
biểu diễn tri thức hiệu quả. Logic mô tả cung cấp khả năng biểu diễn tri thức thông
qua các khái niệm, các quan hệ và các luật cú pháp tương ứng với từng ngôn ngữ.
Logic mô tả ngày càng được phát triển và ứng dụng rộng rãi trong các hệ thống ứng
dụng thông minh. Quá trình tìm kiếm hướng tới sự dễ sử dụng và kiểm soát các
ngôn ngữ Logic mô tả đã được bắt đầu từ những năm 1980s [Brachman and
Levesque 1984;. Nebel 1988]. Mục đích của quá trình tìm kiếm là tìm ra những thủ
tục suy diễn ứng dụng trong thực tiễn, những thuật toán dễ dàng được thực thi và
mang lại tính khả quan [Horrocks, 1998; Haarslev and M¨oller, 2001]. Một trong số
những hướng nghiên cứu chính được quan tâm dựa trên ý tưởng biểu diễn tri thức
theo lĩnh vực và phải được đặc trưng hóa thành các lớp đối tượng và mối quan hệ
giữa chúng, các lớp sử dụng để mô tả lĩnh vực quan tâm được tổ chức theo cấu trúc
phân cấp. Bên cạnh khả năng biểu diễn thông tin một cách hiệu quả, Logic mô tả
còn cho phép thực hiện các dịch vụ suy diễn với độ phức tạp tính toán phù hợp.
Các hệ thống miêu tả dữ liệu dựa trên các hệ thống Logic mô tả cung cấp cho
người sử dụng các khả năng suy diễn khác nhau để rút ra tri thức ẩn từ các tri thức
đã biết. Để đảm bảo một hệ thống Logic mô tả hoạt động hợp lý thì phải giải quyết
được các bài toán quyết định của Logic mô tả với độ phức tạp chấp nhận được. Tìm
hiểu sự cân bằng giữa khả năng biểu diễn tri thức của Logic mô tả và độ phức tạp
của các bài toán quyết định trong Logic mô tả trở thành một trong những kết quả
quan trọng trong nghiên cứu Logic mô tả. Logic mô tả ALC và Logic mô tả EL là
một trong các ngôn ngữ đạt được các yêu cầu trên. Nhưng Logic mô tả EL có tính
vượt trội hơn, do độ phức tạp của các bài toán quyết định trong Logic mô tả EL chỉ
là đa thức [Nebel 7] so với Logic mô tả ALC thì độ phức tạp tính toán là ExpTime-
Complete [M.Schmidt-SchauB and G. Smolka 1991, 15].
Nhiệm vụ của đồ án là tìm hiểu về Logic mô tả EL và cài đặt ví dụ minh họa.
Bố cục của đồ án được phân ra như sau:
Chương 1. Tổng quan về Logic mô tả EL. Chương này trình bày về các nội
dung cơ bản trong Logic mô tả như: Định nghĩa, cú pháp, ngữ nghĩa của các Logic

chương trình, và cuối cùng cài đặt một ví dụ thử nghiệm.
Do thời gian tìm hiểu và nghiên cứu về Logic mô tả EL còn hạn chế nên trong
đồ án còn có những thiếu sót, chưa trình bày đầy đủ về họ Logic mô tả EL như:
EL
+
, EL
++
, ELH, và các Logic mô tả EL có thêm các luật: phép hợp, phép phủ định,
giới hạn số, lượng từ với mọi… , khái niệm đáy. Em rất mong sự đánh giá và góp ý
bổ sung của các thầy giáo, cô giáo và các bạn để đồ án được hoàn thiện hơn.
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
2
Tìm hiểu Logic mô tả EL
LỜI CẢM ƠN
Đầu tiên em muốn gửi lời cảm ơn chân thành nhất tới Ban giám hiệu, các
thầy cô giáo trong trường Đại Học Bách Khoa Hà Nội nói chung, cũng như các thầy
cô trong khoa Công Nghệ Thông Tin nói riêng đã tạo điều kiện và dạy bảo cho em
những kiến thức thiết yếu trong năm năm học tại trường.
Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Trần Đình Khang đã
tận tình hướng dẫn em học tập và nghiên cứu trong suốt quá trình thực tập và làm
đồ án tốt nghiệp.
Em xin gửi lời cảm ơn đến anh Đinh Khắc Dũng đã hướng dẫn em trong việc
tìm kiếm công nghệ thích hợp cho đồ án.
Con xin được gửi lời biết ơn tới bố mẹ đã hy sinh rất nhiều vì việc học tập
của con gần hai mươi năm qua.
Cuối cùng em gửi lời biết tới chị gái, và cám ơn những người bạn của tôi đã
giúp đỡ, động viên tôi trong quá trình học tập và hoàn thành đồ án.
Hà Nội, tháng 5 – 2008
SINH VIÊN THỰC HIỆN
Nguyễn Đức Vượng

Hình 4.20. Giao diện hiển thị cơ sở tri thức trước khi chuẩn hóa 60
Hình 4.21. Giao diện thực hiện khử phép bao hàm 60
Hình 4.22. Giao diện triển khai TBox 61
Hình 4.23. Giao diện hiển thị cơ sở tri thức sau khi chuẩn hóa 61
Hình 4.24. Giao diện hiển thị cây đồ thị của TBox đã chuẩn hóa 62
Hình 4.25. Giao diện hiển thị cây đồ thị của TBox sau chuẩn hóa 62
Hình 4.26. Nội dung TBox của bài toán “Gia đình” 64
Hình 4.27. Nội dung ABox của bài toán gia đình 64
Hình 4.29. Khử phép bao hàm trong TBox của bài toán “Gia đình” 65
Hình 4.30. Các khái niệm nguyên thủy mới của TBox trong bài toán “Gia
đình” sau khi khử phép bao hàm 66
Hình 4.31. Các luật của TBox trong bài toán “Gia đình” sau khi thực hiện
phép khử phép bao hàm 66
Hình 4.32. Kết quả thu được sau khi chuẩn hóa TBox trong bài
toán “Gia đình” 67
Hình 4.33. Cây đồ thị mô tả EL 68
Hình 4.34. Cây đồ thị mô tả của TBox đã chuẩn hóa 68
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
4
Tìm hiểu Logic mô tả EL
DANH MỤC CÁC BẢNG
Bảng 1.1 Cú pháp của ngôn ngữ mô tả FL0 9
Bảng 1.2 Cú pháp của Logic mô tả ALC 10
Bảng 1.3 Các khái niệm trong gia đình của ngôn ngữ ALC 10
Bảng 1.4 Cú pháp của Logic mô tả EL 12
Bảng 1.5 Mô tả khái niệm gia đình trong Logic mô tả EL 12
Bảng 1.6 Cú pháp và ngữ nghĩa của Logic mô tả EL 13
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
5
Tìm hiểu Logic mô tả EL

Chương 2 Các thủ tục suy diễn trong Logic mô tả EL 18
2.1 Bài toán suy diễn trong Logic mô tả EL 18
2.1.1 Suy diễn cho EL-TBox 18
2.1.2 Suy diễn cho EL-ABox 19
2.2 Luật chuẩn hóa trong Logic mô tả EL 20
2.3 Chuẩn hóa EL-TBox 23
2.4 Đồ thị mô tả -EL 24
2.5 Tổng kết chương 26
Chương 3 Các thuật toán cho Logic mô tả EL 26
3.1 Giới thiệu chung 26
3.2 Thuật toán bao hàm cho ELgfp 27
3.3 Thuật toán cho bao hàm ELgci 31
3.3.1 Chuẩn hóa EL-TBox với GCI 31
3.3.2 Các luật chuẩn hóa-GCI 31
3.3.3 Thể thức mô tả-ELgci 33
3.4 Thuật toán cho bao hàm ELdesc 35
3.5 Thực nghiệm của bao hàm khái niệm EL trên Gene Ontology 38
3.5.1 Ontology 38
3.5.2 Gene Ontology 38
3.5.3 Các kết quả thực nghiệm trên Gene Ontology 38
3.6 Tổng kết chương 39
Chương 4 Phân tích thiết kế chương trình ứng dụng 40
4.1. Đặc tả yêu cầu 40
4.1.1. Tác nhân và yêu cầu của tác nhân 40
4.1.2. Đặc tả chức năng của hệ thống 41
4.2. Phân tích hệ thống 43
4.3. Thiết kế hệ thống 48
4.3.1. Thiết kế định dạng file lưu trữ cơ sở tri thức 48
4.3.2. Thiết kế khối hiển thị cơ sở tri thức ban đầu 49
4.3.3. Thiết kế khối khử phép bao hàm 50

Ngày nay bên cạnh việc xem xét làm giàu thêm ngôn ngữ mô tả cho Logic mô
tả, các nghiên cứu tập trung vào việc sử dụng tối ưu khả năng biểu diễn của Logic
mô tả nhằm đạt được cải tiến trong độ phức tạp tính toán cũng nhận được nhiều
quan tâm. Việc tìm kiếm đã hướng tới các ngôn ngữ như ALCNR [21] và SHIQ
[22] mà thời gian quyết định cho thủ tục bao hàm với TBox tổng quát là
EXPTIME hard. Cụ thể hơn, ngay đối với Logic mô tả ALC là Logic mô tả cơ bản
nhất thỏa mãn tính chất đúng mệnh đề (propositionally closed), thì các thủ tục suy
diễn trên ngôn ngữ Logic mô tả ALC nếu không xét tới TBox đã là PSpace-
complete, và khi xét tới TBox tổng quát ( chứa các tiên đề thuật ngữ dạng tổng quát
GCI-General Concept Inclusion) thì độ phức tạp tính toán trở thành ExpTime-
Complete. Chính vì lý do độ phức tạp tính toán lớn của các bài toán suy diễn trong
ngôn ngữ Logic mô tả cũng hạn chế phần nào khả năng ứng dụng của ngôn ngữ
Logic mô tả trong thực tế, trong khi đó trong nhiều bài toán ta chỉ cần một Logic
con của Logic mô tả ALC cũng đủ để mô tả và giải quyết các bài toán đó.
Trong thời gian gần đây, việc tìm kiếm đã chỉ ra rằng đối với Logic mô tả EL
là một Logic con của Logic mô tả ALC thì bài toán bao hàm cho thuật ngữ có chứa
chu trình hay không có chu trình đều có thể quyết định trong thời gian đa thức
[Baader 2003-5]. Và Kết quả cho bài toán bao hàm trong Logic mô tả EL có chứa
các tiên đề thuật ngữ-GCIs (hay TBox tổng quát) cũng vẫn được duy trì trong thời
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
8
Tìm hiểu Logic mô tả EL
gian đa thức [Brandt 2004-6]. Logic mô tả EL đã được sử dụng rộng rãi trong thuật
ngữ y học SNOMED[23] (Systematized Nomenclature of Medicine [Spackman
2000]), và là ngôn ngữ cơ bản đại diện cho thuật ngữ y học GaLen-[24] [Rector and
Horrocks, 1997] mà TBox chứa các GCIs hay TBox tổng quát. Logic mô tả EL đã
được thi hành trong Common LISP, Allegro và thu được hiệu quả lớn trong việc sử
dụng Gene Ontology[10] như là một tiêu chuẩn đánh giá.
1.2 Cú pháp của Logic mô tả
Cơ sở của một Logic mô tả là các mô tả khái niệm và các mô tả vai trò,

C ⊓ D Giao khái niệm
∀r.C
Lượng từ với mọi
Bảng 1.1 Cú pháp của ngôn ngữ mô tả FL
0
Ngôn ngữ mô tả FL
0
ban đầu có thủ tục quyết định với TBox tổng quát là
PSpace-Complete[2]. Sau đó với ba loại ngữ nghĩa mô tả được đưa ra bởi Nebel đã
đưa thủ tục quyết định cho bài toán bao hàm trong ngôn ngữ mô tả FL
0
có chứa chu
trình thuật ngữ với thời gian quyết định trên ngôn ngữ mô tả FL
0
là PSpace-hard
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
9
Tìm hiểu Logic mô tả EL
[20]. Vì vậy ngôn ngữ FL
0
không chỉ mang khả năng biểu diễn tri thức hạn chế mà
thời gian tính toán trên ngôn ngữ mô tả FL
0
cũng khá phức tạp, chính vì vậy trong
quá trình cải tiến của ngôn ngữ mô tả, các toán tử mới (các tập luật) đã được thêm
vào và đã xây dựng nên các ngôn ngữ mô tả khác nhau. Tập hợp các toán tử khác
nhau tạo nên các ngôn ngữ Logic mô tả khác nhau. Trong đó có Logic mô tả ALC
đã thể hiện khả năng biểu diễn tri thức khá mạnh mẽ bởi các luật cú pháp của ALC.
1.2.2 Ngôn ngữ Logic mô tả ALC
Ngôn ngữ Logic mô tả ALC (Attributive Language with Complements) [15]

Me
≡
Nu ⊓ ∃Cocon.ConNguoi
Cha
≡ Nam ⊓ ∃Cocon.ConNguoi
Ba
≡ Me ⊓ ∃Cocon.ChaMe
Ong
≡ Cha ⊓ ∃Cocon.ChaMe
Bảng 1.3 Các khái niệm trong gia đình của ngôn ngữ ALC
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
10
Tìm hiểu Logic mô tả EL
Logic mô tả ALC có khả năng biểu diễn tri thức khá mạnh mẽ nhờ một tập lớn
các cú pháp của ALC. Trong khi đó khả năng biểu diễn tri thức tỉ lệ thuận với độ
phức tạp tính toán của các dịch vụ suy diễn trong các hệ Logic mô tả tương ứng.
Các thủ tục suy diễn trong Logic mô tả ALC khi không xét tới TBox đã là PSpace-
Complete, TBox có chứa chu trình là PSpace-Complete và khi xét tới TBox tổng
quát thì độ phức tạp tính toán trở thành ExpTime-Complete [Tommie Meyer].
Chính vì lý do độ phức tạp tính toán lớn của các bài toán suy diễn trong Logic mô tả
ALC đã hạn chế phần nào khả năng ứng dụng của Logic mô tả ALC trong thực tế.
Trong thực tế thời gian suy diễn cho các bài toán là rất quan trọng và việc cải
tiến trong độ phức tạp tính toán đã và đang nhận được khá nhiều quan tâm. Và thực
tế cũng đã chứng minh được rằng trong nhiều bài toán ta chỉ cần một Logic con của
ALC cũng đủ để mô tả và giải quyết chúng. Một trong những Logic con của ALC
chính là Logic mô tả EL.
1.3 Logic mô tả EL
Logic mô tả EL là một Logic con của Logic mô tả ALC. Đặc điểm nổi bật
của Logic mô tả EL so với các Logic mô tả con khác của Logic mô tả ALC là suy
diễn trên Logic mô tả EL luôn có độ phức tạp tính toán đa thức, bất chấp sự có mặt

┬ Khái niệm đỉnh
C ⊓ D Giao khái niệm
∃r.C
Lượng từ tồn tại
Bảng 1.4 Cú pháp của Logic mô tả EL
Ví dụ 1.2 Sử dụng các luật cú pháp của Logic mô tả EL ta xây dựng các khái
niệm phức hợp, đó là các khái niệm trong gia đình. Trong đó, có sử dụng ba khái
niệm nguyên thủy là con người "ConNguoi", giống cái "GiongCai", giống đực
“GiongDuc” và sử dụng một quan hệ nguyên thủy là có con "Cocon".
Nu
≡
ConNguoi ⊓ GiongCai
Nam
≡
ConNguoi ⊓ GiongDuc
Me
≡
Nu ⊓ ∃Cocon.ConNguoi
Cha
≡ Nam ⊓ ∃Cocon.ConNguoi
Bảng 1.5 Mô tả khái niệm gia đình trong Logic mô tả EL
1.3.2 Ngữ nghĩa và cú pháp của Logic mô tả EL
Các mô tả khái niệm được định nghĩa quy nạp từ một tập các toán tử kết
hợp với tên các khái niệm và các vai trò. Ngữ nghĩa của các mô tả khái niệm trong
Logic mô tả EL có được nhờ vào các phép thông dịch.
Mỗi phép thông dịch, ký hiệu là I, là một cặp (∆
I
, .
I
). Trong đó, ∆

Cho (∆
I
, .
I
) là một mô hình của Cha ⊓ ∃Cocon.ChaMe với :
Một tập khác rỗng: ∆
I
={ Peter, Harry, Raul}
Khi đó Hàm dịch .
I
được định nghĩa như sau:
Cha(Peter)
Cocon(Peter, Raul)
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
12
Tìm hiểu Logic mô tả EL
Cha(Raul)
Cocon(Raul, Harry)
Ta có:
(Cha ⊓ ∃Cocon.ChaMe)
I
= (Cha)
I
∩ (∃Cocon.ChaMe)
I
(Cha)
I
= {Peter, Raul}
(∃Cocon.ChaMe)
I

I
Lượng từ tồn tại r.C
{x ∈ ∆
I
| y : (x, y) ∈ r
I
y ∈ C
I
}
Định nghĩa khái niệm
C ≡ D
C
I
= D
I
Khái niệm riêng a ∈ N
I
a
a
I
∈ ∆
I
Khẳng định khái niệm C(a)
a
I
∈ C
I
Khẳng định vai trò r(a, b)
(a
I

1
, D
2
khác nhau cùng thỏa mãn C ≡ D
1
và C ≡ D
2
.
Ví dụ 1.4: Các định nghĩa khái niệm sau sẽ tạo nên một EL-TBox.
Nu ≡ ConNguoi ⊓ GiongCai
Nam ≡ ConNguoi ⊓ GiongDuc
ChaMe ≡ ConNguoi ⊓ ∃coCon.ConNguoi
Thuật ngữ chu trình trong EL-TBox. Một EL-TBox T được gọi là có chứa chu
trình thuật ngữ nếu trong EL-TBox đó có chứa một tập các định nghĩa khái niệm là
{ C
1
≡ D
1
, . . . , C
n
≡ D
n
} mà trong đó D
i
chứa C
i+1
và D
n
chứa C
1

), các vai trò (ký hiệu N
role
) và các định nghĩa khái niệm
(ký hiệu N
def
). Khi đó J gọi là phép thông dịch nguyên thủy đối với T nếu:
1. Một phép thông dịch nguyên thủy (ký hiệu là J) là một cặp (∆
J
, .
J
). Trong đó
∆
J
là một tập khác rỗng, còn .
J
là một hàm dịch. Hàm dịch .
J
biến mỗi khái
niệm nguyên thủy P thành một tập P
J
⊆ ∆
J
, biến mỗi quan hệ hai ngơi r
thành một quan hệ nhị phân r
I
⊆ ∆
J
x ∆
J
.

Khi đó I
1
được gọi là mô hình lớn nhất của T dựa trên J. Ta gọi mô hình này là
mô hình điểm cố định lớn nhất của T [Nebel 1991].
Ví dụ 1.5: Xác định phép thông dịch nguyên thủy cho TBox gồm các khái
niệm sau.
TopDoanhnghiep ≡ Doanhnghiep ⊓ Giau ⊓ ∃quanhe.TopDoanhnghiep
Giả sử ta có :
∆
J
= {Mai, Mơ, Mây}
Doanhnghiep
J
= {Mai, Mơ, Mây}
Giau
J
= {Mai, Mơ}
quanhe
J
= {(Mai, Mơ), (Mơ, Mây), (Mây, Mai)}.
Ta thấy Mây không phải là người nằm trong TopDoanhnghiep do Mây không
phải là một người giàu có, trong khí đó Mai và Mơ thì có thể. Từ đó ta có 2 phép
thông dịch dựa trên J như sau:
1. I thông dịch định nghĩa khái niệm TopDoanhnghiep đối với tập
{Mai, Mơ}.
2. I thông dịch định nghĩa khái niệm với tập rỗng.
Khi đó I là mô hình điểm cố định lớn nhất dựa trên J.
1.3.3.2 Bộ thuật ngữ với GCIs-TBox tổng quát
Tổng quát, các tiên đề thuật ngữ thường có dạng:
C D (r s) hoặc C ≡ D (r ≡ s)

ConNguoi ⊓ ∃Cocha.NguoiDuc ⊓ ∃Come.NguoiDuc NguoiDuc.
Bao hàm khái niệm: Cho T là một EL-TBox và C, D là các mô tả khái
niệm. Khi đó ta có
• C được gọi là bao hàm bởi D (C D) nếu C
I
⊆ D
I
• D được gọi là bao hàm bởi C (D C) nếu D
I
⊆ C
I
.
Một cách khác nếu C D và D C thì C ≡ D được gọi là một tương đương
khái niệm, là sự ước lược của C D và D C.
Một tương đương khái niệm nếu vế trái là tên một khái niệm mới, chỉ xuất
hiện không quá một lần bên vế trái (được gọi là ký hiệu tên) trong các tiên đề của
TBox và vế phải là một biểu thức chứa các khái niệm (ký hiệu gốc) thì được gọi là
một định nghĩa khái niệm.
1.3.3.3 Bộ khẳng định – ABox
Một cơ sở tri thức (Knowledge Base-KB) bao gồm một bộ thuật ngữ TBox và
một bộ khẳng định ABox. Một bộ khẳng định ABox chứa những thông tin chi tiết
mô tả về các thông tin trong miền ứng dụng được nhập vào từ trước được gọi là các
khẳng định.
Một ABox A là một tập hữu hạn các khẳng định C(a), được gọi là một khẳng
định khái niệm và r(a,b), được gọi là một khẳng định vai trò, trong đó C là tên một
khái niệm, r là tên một vai trò và a, b là tên các cá thể độc lập. Các mệnh đề trong A
được gọi là các khẳng định.
Ví dụ 1.7 Sử dụng hệ thống khái niệm gia đình. Giả sử hệ thống bao gồm các
phần tử Tuân, Hồng, Đào, là tên các cá thể. Khi đó ta có 3 khẳng định sau:
Me(Hồng)

I
, b
I
) ∈ r
I
với mọi khẳng định vai trò r(a, b) trong A.
1.4 Tổng kết chương
Chương 1 đã trình bày quá trình phát triển của Logic mô tả để dẫn tới sự ra
đời của Logic mô tả EL, những khái niệm cơ bản về Logic mô tả EL như:
Cú pháp của ngôn ngữ mô tả: Trong đó, trình bày cú pháp của Logic cơ bản
đầu tiên FL
0
, các cú pháp cho ALC và sự ra đời của EL. Ngôn ngữ này cho phép
xây dựng các khái niệm phức hợp từ các khái niệm và vai trò nguyên thuỷ. Ngôn
ngữ thông dụng nhất mà suy diễn trên nó luôn có độ phức tạp tính toán chỉ là đa
thức.
Ngữ nghĩa của Logic mô tả EL: Phần này trình bày về phép thông dịch
nguyên thủy J và phép thông dịch I. Phép thông dịch I gồm hai thành phần, một tập
khác rỗng và một hàm dịch I. Hàm dịch này tác động lên các khái niệm, các vai trò
và các cá thể trong cơ sở tri thức của hệ Logic mô tả EL tạo nên ngữ nghĩa mô tả
khái niệm trong EL.
Kiến trúc hệ Logic mô tả: Thể hiện được kiến trúc một hệ thống thông tin mô
tả gồm cơ sở tri thức K=(T, A) thông qua một hệ thống lập luận mới đến giao diện
người sử dụng.
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
17
Tìm hiểu Logic mô tả EL
Chương 2 Các thủ tục suy diễn trong Logic mô tả EL
2.1 Bài toán suy diễn trong Logic mô tả EL
Như ta đã biết mục đích của các thủ tục quyết định trong bài toán bao hàm

I
⊆ D
I
. Khi đó khái niệm C bị bao bởi khái
niệm D sẽ được kí hiệu là C
T
D hoặc T |= C D. Sử dụng bài toán bao hàm
các khái niệm trong TBox có thể được sắp xếp theo thứ tự bao hàm giữa chúng
dựa trên quan hệ bao hàm trực tiếp hay bao hàm gián tiếp.
 Khái niệm C bị bao hàm trực tiếp bởi khái niệm D đối với T nếu như
khái niệm C bị bao hàm bởi khái niệm D và không tồn tại một khái
niệm E mà khái niệm C bị bao hàm bởi khái niệm E và khái niệm E bị
bao hàm bởi khái niệm D.
 Khái niệm C bị bao hàm gián tiếp bởi khái niệm D đối với T nếu như
khái niệm C bị bao hàm bởi khái niệm D và khái niệm C không bị bao
hàm trực tiếp bởi khái niệm D.
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
18
Tìm hiểu Logic mô tả EL
Tính toán thứ bậc bao hàm là một trong các bài toán suy diễn chính của các
hệ thống Logic mô tả hiện nay.
2. Bài toán tương đương khái niệm: Hai khái niệm C và D gọi là
tương đương đối với T nếu như C
I
= D
I
với mọi mô hình I của T. Khi đó ta viết C
≡
T
D hoặc T |= C ≡ D.

1. Kiểm tra thể hiện: Xác định một khẳng định có phải được suy diễn
từ ABox A hay không. Logic mô tả EL không chứa bất cứ xây dựng luật vai trò
nào ở dạng phức tạp, nên bài toán kiểm tra khẳng định vai trò rất đơn giản, chỉ là
tìm sự xuất hiện của khẳng định vai trò cần kiểm tra trong ABox. Như vậy chúng
ta chỉ cần quan tâm tới kiểm tra khẳng định khái niệm. Để kiểm tra một khẳng
định khái niệm, chúng ta phải kiểm tra khẳng định có được suy diễn từ ABox hay
không. Một khẳng định được suy diễn từ ABox (A |= C(a)) nếu với mọi mô hình
I của A cũng thỏa mãn C(a).
2. Nhất quán của ABox: ABox A là nhất quán khi và chỉ khi nó nhất
quán đối với TBox T, tức là tồn tại một phép thông dịch là mô hình của cả TBox
và ABox. Do đó, chúng ta phải sử dụng TBox trong dịch vụ suy diễn này của
ABox, tức là mở rộng ABox với các khái niệm TBox mở rộng. Khái niệm mở
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
19
Tìm hiểu Logic mô tả EL
rộng E thu được bằng cách thay thế các tên trong mô tả của khái niệm ban đầu C
bằng các mô tả của chúng ở trong T. C là thỏa đối với T khi và chỉ khi E là thỏa
đối với T. Do đó, mở rộng ABox đối với T (ABox A’) có thể thu được bằng cách
thay thế mỗi khẳng định khái niệm C(a) trong A bằng khẳng định khái niệm E(a).
Trong mọi mô hình của T, một khái niệm C và mở rộng E được thông dịch theo
cùng một cách và A’ không chứa các kí hiệu tên được định nghĩa trong T. Vì
vậy, A là nhất quán đối với T khi và chỉ khi A’ là nhất quán. A’ nhất quán khi và
chỉ khi nó thỏa, tức là tồn tại một mô hình không rỗng của A’. Bây giờ A’ cũng
biểu diễn toàn bộ cơ sở tri thức .
Bài toán bao hàm khái niệm cũng có thể chuyển về bài toán kiểm tra thể
hiện: Khái niệm C bị bao hàm bởi khái niệm D khi và chỉ khi khẳng định khái niệm
D(a) được suy ra từ cơ sở tri thức {C(a)}, tức là {C(a)} |= D(a).
Trong các ứng dụng, thường xuyên phải sử dụng các suy diễn phức tạp hơn
bài toán nhất quán và kiểm tra thể hiện. Nếu chúng ta xem xét một cơ sở tri thức
theo nghĩa lưu trữ thông tin về các cá thể, chúng ta sẽ muốn biết mọi cá thể là thể

Với m, k 0.
• P
1
, . . . , P
m
là các khái niệm nguyên thủy (ký hiệu N
prim
)
• r
1
, . . . , r
k
là các vai trò (ký hiệu N
role
)
• B
1
, . . . , B
k
là các định nghĩa khái niệm (ký hiệu N
def
).
Cho T là một EL-TBox chứa các khái niệm nguyên thủy, định nghĩa khái
niệm và các vai trò. Các Luật chuẩn hóa được định nghĩa như sau:
Trong các luật chuẩn hóa có A, Â, A
i
là ký hiệu tên các khái niệm, C và C
i
là
các mô tả khái niệm (có thể là khái niệm phức hoặc khái niệm đỉnh), Ĉ là một khái

…⊓ C
k
∶ → cho 1 i k
với P là một tên khái niệm mới
A
k
≡ A
1
⊓ C
k

NF2
gfp
(ngữ nghĩa với điểm cố định lớn nhất(fixpoint))
A
1
≡ A
2
⊓ C
1
,
A
2
≡ A
3
⊓ C
2
, A
i
≡ C

Me ≡ Nu ⊓ ∃Cocon.ConNguoi
Nu ≡ ConNguoi ⊓ GiongCai
ta được
{Bà, Me, Nu} ≡ ConNguoi GiongCai ⊓ ⊓ ∃Cocon.ConNguoi ⊓ ∃Cocon.ChaMe
Nguyễn Đức Vượng - HTTT - K48 - ĐHBK Hà Nội.
21
Tìm hiểu Logic mô tả EL
Tương tự với luật NF2
gfp
ta có:
{Bà, Me, Nu} ≡ ConNguoi GiongCai ⊓ ⊓ ∃Cocon.ConNguoi ⊓ ∃Cocon.ChaMe
Luật NF3 với định nghĩa khái niệm
Me ≡ Nu ⊓ ∃Cocon.ConNguoi
sẽ được chuyển thành: Me ≡ ConNguoi ⊓ GiongCai ⊓ ∃Cocon.ConNguoi
Ví dụ 2.2. Cho T là một EL-TBox chỉ bao gồm định nghĩa khái niệm, với
các tập định nghĩa như sau:
1. Boss(Ông chủ), GiamDoc(Giám đốc), DoanhNghiep(Doanh nghiệp)
là các mô tả khái niệm.
2. ĐôLa(DoLa), Vàng(Vang), Giàu(Giau) là các khái niệm nguyên thủy.
3. coTien(có tiền), coQuanhe(có quan hệ) là các vai trò.
4. TopDoanhnghiep là những doanh nghiệp lớn.
DoanhNghiep ≡ Vang GiamDoc ⊓ ⊓ ∃coTien.∃coQuanhe.DoanhNghiep
GiamDoc ≡ DoLa Boss ⊓ ⊓ ∃coQuanhe.∃coTien.Boss
Boss ≡ Giau GiamDoc ⊓ ⊓ ∃coTien.(DoLa Vang)⊓
Bằng cách định nghĩa các khái niệm mới từ khái niệm phức hợp trong TBox
trên ta được:
DoanhNghiep ≡ Vang GiamDoc ⊓ ⊓ ∃coTien.TopDoanhNghiep
TopDoanhNghiep ≡ ∃coQuanhe.DoanhNghiep
GiamDoc ≡ DoLa Boss ⊓ ⊓ ∃coQuanhe.ThuongGia
ThuongGia ≡ ∃coTien.Boss

thay thế cho định nghĩa GiamDoc trong DoanhNghiep. Ta thu được EL-TBox sau
khi đã chuẩn hóa là T
desc
như sau:
DoanhNghiep ≡ Vang DoLa Giau ⊓ ⊓ ⊓ ∃coQuanhe.ThuongGia ⊓
∃coTien.TuBan ⊓ ∃coTien.TopDoanhNghiep
TopDoanhNghiep ≡ ∃coQuanhe.DoanhNghiep
GiamDoc ≡ P DoLa Giau ⊓ ⊓ ⊓ ∃coQuanhe.ThuongGia ⊓ ∃coTien.TuBan
ThuongGia ≡ ∃coTien.Boss
Boss ≡ P DoLa ⊓ Giau ⊓ ∃coQuanhe.ThuongGia ⊓ ∃coTien.TuBan
TuBan ≡ DoLa Vang⊓
Áp dụng gfp-ngữ nghĩa (luật NF2
gfp
), khi đó GCIs có thể tách biệt theo thứ tự
để thay thế bởi định nghĩa
GiamDoc ≡ DoLa Giau ⊓ ⊓ ∃coQuanhe.ThuongGia ⊓ ∃coTien.TuBan và
Boss ≡ DoLa Giau ⊓ ⊓ ∃coQuanhe.ThuongGia ⊓ ∃coTien.TuBan
Ký hiệu T
gfp
là EL-TBox thu được trong trường hợp này. Áp dụng luật NF3
thay thế cho định nghĩa GiamDoc trong DoanhNghiep. Ta thu được EL-TBox sau
khi đã chuẩn là T
gfp
như sau:
DoanhNghiep ≡ Vang ⊓ DoLa ⊓ Giau ⊓ ∃coQuanhe.ThuongGia ⊓
∃coTien.TuBan ⊓ ∃coTien.TopDoanhNghiep
TopDoanhNghiep ≡ ∃coQuanhe.DoanhNghiep
GiamDoc ≡ DoLa ⊓ Giau ⊓ ∃coQuanhe.ThuongGia ⊓ ∃coTien.TuBan
ThuongGia ≡ ∃coTien.Boss
Boss ≡ DoLa ⊓ Giau ⊓ ∃coQuanhe.ThuongGia ⊓ ∃coTien.TuBan

1
là một EL-TBox chứa đựng các định nghĩa khái niệm:
A
1
≡ A
2
⊓

P
1
,
A
2
≡ A
3
⊓

P
2
,
∶
A
n
≡ A
1
⊓

P
n
,

1
P⊓
2
… P⊓ ⊓
n
,
A
2
≡

P
1
P⊓
2
… P⊓ ⊓
n
,
∶
A
n
≡

P
1
P⊓
2
… P⊓ ⊓
n
.
Kích thước của T

= {(x, y) | (x, y) : r ∈ N
role
), là tập các cạnh gán nhãn là tên các vai trò
• L
T
(A)={P
1
, . . . ,P
m
} là các khái niệm nguyên thủy của A. Với A là một định
nghĩa khái niệm: P
1
P⊓
2
… P⊓ ⊓
m
⊓ r
1
.B
1
⊓ r
2
.B
2
… ⊓ ⊓ r
k
.A
k
trong
T (A là tập các cạnh (A, r

= (V
T
, E
T
, L
T
) là đồ thị mô tả-EL
tương ứng của T. Khi đó
1. Tổng số các nút |V
T
| là kích thước theo chiều dài của T, và tổng số các cạnh
|E
T
| là bậc 2 trong kích thước của T.
2. Kích thước của G
T
là bậc 2 trong kích thước của T.
Chứng minh:
Ta có số các nút trong G
T
là các định nghĩa khái niệm trong EL-TBox đã
được chuẩn hóa. Một định nghĩa khái niệm mới sẽ được thêm vào T mỗi khi áp
dụng luật NF1, do đó chỉ làm tăng kích thước của T theo chiều dài.
Mỗi cạnh (A, r, B) trong G
T
là một khái niệm con r.B xuất hiện trong định
nghĩa khái niệm ban đầu của định nghĩa khái niệm A trong EL-TBox đã được chuẩn
hóa T’. Khi đó theo Bổ đề 2.1 thì kích thước của T’ sẽ là bậc 2 theo kích thước của
T.
Ví dụ 2.4 Cho các định nghĩa khái niệm trong gia đình của TBox T như sau: