Biểu diễn tri thức và suy luận
Đại Học Quốc Gia TPHCM
Trường Đại Học Công Nghệ Thông Tin
***
BÀI THU HOẠCH MÔN
BIỂU DIỄN TRI THỨC VÀ ỨNG DỤNG
TÌM HIỂU VỀ:
BIỂU DIỄN TRI THỨC VÀ SUY LUẬN
Giảng viên Phụ trách: TS. Đỗ Văn Nhơn
Học viên thực hiện: Nguyễn Đình Tấn
Mã số học viên: CH1101039
Thành Phố Hồ Chí Minh – 1/2013
Trang 1
Biểu diễn tri thức và suy luận
MỤC LỤC
CHƯƠNG 1: TỔNG QUAN 3
1.1 Mở đầu 3
1.2 Nội dung thực hiện 3
1.3 Dự kiến kết quả đạt được 4
CHƯƠNG 2: BIỂU DIỄN TRI THỨC VÀ SUY LUẬN 4
2.1 Biểu diễn tri thức 4
2.2 Bài báo “Knowledge Representation and Reasoning” về nghiên cứu của Grigoris Antoniou và
Pavlos Peppas (Đại học University of Crete và University of Patras, Hy Lạp) 5
2.2.1 Giới thiệu 5
2.2.2 Suy luận không đơn điệu (Non-Monotonic Reasoning) 6
2.2.3 Suy luận về hành động (Reasoning about Action) 8
2.2.4 Duyệt lại tín nhiệm (Belief Revision) 10
2.2.5 Logic tri thức (Epistemic Logics) 11
2.3 Logic 12
2.4 Logic mệnh đề 13
2.4.1 Cú pháp 13

1.2 Nội dung thực hiện
Nội dung thực hiện đề tài:
 Tìm hiểu các kiến thức về Biểu diễn tri thức và suy luận.
Trang 3
Biểu diễn tri thức và suy luận
 Nghiên cứu nội dung bài báo “Knowledge Representation and Reasoning” về
các công trình nghiên cứu trong lĩnh vực Biểu diễn tri thức và suy luận của
Grigoris Antoniou và Pavlos Peppas.
1.3 Dự kiến kết quả đạt được
 Đưa ra được những kiến thức về biểu diễn tri thức và suy luận.
 Hiểu được và trình bày lại một phần nội dung bài báo “Knowledge
Representation and Reasoning” của Grigoris Antoniou và Pavlos Peppas.
CHƯƠNG 2: BIỂU DIỄN TRI THỨC VÀ SUY LUẬN
2.1 Biểu diễn tri thức
Để có thể sử dụng tri thức, tri thức cần được biểu diễn dưới dạng thuận tiện cho
việc mô tả và suy diễn. Nhiều ngôn ngữ và mô hình biểu diễn tri thức đã được thiết kế
để phục vụ mục đích này. Ngôn ngữ biểu diễn tri thức phải là ngôn ngữ hình thức để
tránh tình trạng nhập nhằng như thường gặp trong ngôn ngữ tự nhiên. Một ngôn ngữ
biểu diễn tri thức tốt phải có những tính chất sau:
• Ngôn ngữ phải có khả năng biểu diễn tốt, tức là cho phép biểu diễn mọi tri thức
cần thiết cho bài toán.
• Cần đơn giản và hiệu quả, tức là cho phép biểu diễn ngắn gọn tri thức, đồng thời
cho phép đi đến kết luận với khối lượng tính toán thấp.
• Gần với ngôn ngữ tự nhiên để thuận lợi cho người sử dụng trong việc mô tả tri
thức.
Sau khi đã có ngôn ngữ biểu diễn tri thức, tri thức về thế giới của bài toán được
biểu diễn dưới dạng tập hợp các câu và tạo thành cơ sở tri thức. Thủ tục suy diễn
được sử dụng để tạo ra những câu mới nhằm trả lời cho các vấn đề của bài toán. Thay
vì trực tiếp hành động trong thế giới thực của bài toán, hệ thống có thể suy diễn dựa
trên cơ sở tri thức được tạo ra.

Rondogiannis và đã cho những kết quả nghiên cứu quan trọng về Lập trình logic theo
thời gian, lập trình logic ngữ nghĩa tổng quát, lập trình Datalog.
Các ứng dụng của biểu diễn tri thức và suy luận trong mạng ngữ nghĩa thu hút sự
quan tâm của nhiều nhà nghiên cứu Hy Lạp như: Nastasia Analyti, Nikos Bassiliades,
Antonis Bikakis, Vassilis Christophides, Panos Constantopoulos, Yiannis Tzitzikas,
Ioannis Vlahavas. Và những nhà nghiên cứu được đề cập ở trên là Antoniou,
Gergatsoulis, Kakas, and Plexousakis đã có những đóng góp quan trọng về hệ luật và
ngôn ngữ mạng ngữ nghĩa, nguyên tắc phân loại các mặt, mô hình dữ liệu bán cấu
trúc và sự tiến hóa Ontology.
Trong những ứng dụng trước đó, một phương pháp mô hình khai báo đối với Sinh
học tính toán (computational biology) được phát triển bởi Kakas, Papatheodorou và
các cộng sự đã cho những kết quả đầy triển vọng. Cuối cùng, Ioannis
Hatzilygeroudis, Jim Prentzas, Basilis Boutsinas, Mihalis Vrahatis và các cộng sự đã
tích hợp phương pháp không ký hiệu và luật ký hiệu (symbolic rules and non-
symbolic methods) để cho ra các hệ thống siêu năng lượng (powerful hybrid
systems).
Khảo sát nhỏ này cho chúng ta cái nhìn thoáng qua về những công trình nghiên
cứu của các tác giả tại Hy Lạp về Biểu diễn tri thức và suy luận. Nó cũng cho thấy sự
xuất hiện cộng đồng nghiên cứu chưa phát triển mạnh và còn khá trẻ.
2.2.2 Suy luận không đơn điệu (Non-Monotonic Reasoning)
Suy luận có thể hủy bỏ là một phương pháp nghiên cứu kết hợp khả năng biểu
diễn cải tiến để đạt được suy luận với những thông tin trái ngược và không đầy đủ có
độ phức tạp tính toán thấp. Bao gồm những đặc trưng chính:
2.2.2.1 Phương pháp dựa vào luật, không phân biêt
Trang 6
Biểu diễn tri thức và suy luận
2.2.2.2 Sự phủ định cổ điển (classical negation) được dùng ở phần đầu và phần
thân của luật.
2.2.2.3 Các luật có thể hỗ trợ những kết luật đối lập (conficting conclusions)
2.2.2.4 Các suy luận được hoài nghi theo chiều hướng các luật mâu thuẫn không

thuyết cũng như mức độ ứng dụng trong ngữ cảnh môi trường tính toán thông minh.
Lĩnh vực môi trường thông minh cung cấp một ngữ cảnh thích hợp bởi vì nó được
đặc trưng hóa bởi sự thay đổi trong tính toán theo hướng đa thiết bị liên lạc di động
và tĩnh ẩn vào nền, cung cấp một môi trường gia tố, thông minh. Các thiết bị tự vận
hành theo cách tương tác, lấy thông tin từ các cảm biến và liên lạc với những các
khác, để phân phối nguồn lực và cộng tác trong suốt kế hoạch vận hành. Lý thuyết
vận hành có thể cung cấp công cụ để tạo ra các mô hình chính thức kiểm tra các đặc
tả của hệ thống xung quanh và để chứng minh các tính chất đúng của chúng. Môi
trường thông minh đặt ra thực tế thách thức cho việc lập kế hoạch, và việc xử lý tri
thức và các hành động cảm biến chứng minh nó là một sự thúc đẩy quan trọng.
Việc giải quyết những thách thức đó, công trình nghiên cứu của Plexousakis đi
theo 2 hướng chính:
• Đề cập đến vấn đề phân nhánh trong ngữ cảnh theo thời gian mà các hành động
và thời gian tác động đến các sự việc ở quá khứ, hiện tại hoặc tương lai.
• Đặt ra lý thuyết thống nhất của tri thức, hành động và thời gian cho các hệ thống
động
Trang 8
Biểu diễn tri thức và suy luận
Hướng thứ nhất dựa trên phần mở rộng của tính toán tình huống (Situation
Calculus) và mục tiêu là các ứng dụng hỗ trợ trong cơ sở dữ liệu theo thời gian và
máy học.
Hướng thứ hai là dựa trên chủ nghĩa hình thức được lấy cảm hứng từ tính toán sự
kiện (Event Calculus) và mục đích là hỗ trợ các ứng dụng môi trường thông minh.
Các nghiên cứu gần đây của Kakas trong suy luận về các hành động tập trung chủ
yếu vào vấn đề chất lượng và nó liên quan đến các tính chất ra sao của sức chịu đựng
của thuyết hành động. Cùng với các cộng sự của mình, Kakas đã mở rộng ngôn ngữ E
thành ngôn ngữ mới gọi là Modular E, trong đó các giải pháp được tích hợp thành ba
vấn đề chính trong biểu diễn tri thức và suy luân (frame,ramification and qualification
problems) được đặt ra. Ngôn ngữ mới thể hiện mức độ cao của tính cấu thành và tạo
nên sức chịu đựng. Kakas cũng học cách thức mà ngôn ngữ E có thể chuyển sang

mô hình AGM và các ứng dụng của ý tưởng của nó và kết quả của các lĩnh vực khác.
Bắt đầu từ trường đại học University of Crete, chúng ta thấy những kết quả quan
trọng của Plexousakis, Flouris, và Antoniou. Tập trung vào các vấn đề của việc rút lại
tri thức từ hệ cơ sở tri thức, cũng như các vấn đề của việc cập nhật kiến thức cơ bản
dựa trên Logic mệnh đề và mô tả, Plexousakis đã đóng góp một số kết quả lý thuyết
là quan trọng hàng đầu để có những thay đổi trong việc phát triển các hệ thống dựa
trên tri thức. Chính xác hơn, họ đã đề xuất tổng quát của lý thuyết nổi bật nhất về
duyệt lại tín nhiệm và cập nhật, đặt tên là lý thuyết AGM của sự thay đổi. Sụ tổng
quát hóa này tập trung vào hình thức hóa một toán tử rút gọn tri thức và tiên đề của
thuyết thay đổi tri thức hỗ trợ các hoạt động rút gọn. Khả năng ứng dụng của việc tiên
đề hóa được đề xuất trong trường hợp của logic Mô tả cập nhật cũng đã được kiểm
tra. Plexousakis đã khám phá các giới hạn của sự khái quát hóa này, đã chỉ ra một
khía cạnh khác của AGM đặt ra và đã cung cấp qui tắc biểu diễn tri thức mới cho các
Trang 10
Biểu diễn tri thức và suy luận
toán tử rút gọn thỏa mãn các yêu cấu AGM. Các kết quả khác, bao gồm nghiên cứu
về các liên kết của lý thuyết AGM với mô hình cơ bản, vai trò của những giả thuyêt
khác nhau của lý thuyết AGM trong các ứng dụng của nó ý tưởng sơ bộ về sự duyệt
lại. Theo một trường hợp nghiên cứu, Plexousakis đã khảo sát khả năng ứng dụng lý
thuyết khái quát hóa của nó trong ngữ cảnh của ngôn ngữ được sử dụng cho việc biểu
diễn Ontology trong mạng ngữ nghĩa. Plexousakis lập luận rằng, ứng dụng này có thể
giải quyết một số vấn đề hóc búa hiện tại đang gặp phải của những nhà nghiên cứu sự
phát triển Ontology.
Tại trường đại học Patras University, những công trình nghiên cứu gần đây về sự
duyệt lại tín nhiệm, đã tập trung chủ yếu vào các ngữ nghĩa thế giới khả hữu cho các
hàm duyệt lại. Cùng với các cộng sự, Peppas đã nghiên cứu số lượng các hạn chế
trong ngữ cảnh của các hệ thống của các lĩnh vực, và hàm ý rằng những hạn chế này
trên các chức năng duyệt lại AGM cũng như duyệt lại phức tạp. Trong số các hạn chế
đó, tập trung cụ thể vào đánh giá sự tương đồng của Winslett. Như đã được chứng
minh bởi Peppas, hạn chế này đặc trưng hóa một cách chính xác yêu cầu của Parikh

• Ngữ nghĩa của ngôn ngữ cho phép ta xác định ý nghĩa của các câu trong một
miền nào đó của thế giới hiện thực, xác định các sự kiện hoặc sự vật phản ánh thế
giới thực của câu mệnh đề. Đối với logic, ngữ nghĩa cho phép xác định câu là
đúng hay sai trong thế giới của bài toán đang xét.
• Thủ tục suy diễn là phương pháp cho phép sinh ra các câu mới từ các câu đã có
hoặc kiểm tra liệu các câu có phải là hệ quả logic của nhau.
Logic đã cung cấp cho các nhà nghiên cứu một công cụ hình thức để biểu diễn và
suy luận tri thức.
Trang 12
Biểu diễn tri thức và suy luận
2.4 Logic mệnh đề
2.4.1 Cú pháp
Logic mệnh đề là logic rất đơn giản, tuy khả năng biểu diễn của nó còn một số
hạn chế nhưng thuận tiện cho ta đưa vào nhiều khái niệm quan trọng trong logic.
Cú pháp của logic mệnh đề bao gồm tập các ký hiệu và tập các quy tắc kết hợp
các ký hiệu tạo thành công thức.
a) Các ký hiệu
Các ký hiệu được dùng trong logic mệnh đề bao gồm:
•Các ký hiệu chân lý: True (ký hiệu T) và False (ký hiệu F).
•Các ký hiệu mệnh đề (còn được gọi là các biến mệnh đề và thường được ký hiệu
bằng các chữ cái): P, Q,
Biểu diễn tri thức và suy diễn logic
•Các kết nối logic ∧, ∨, ¬, ⇒, ⇔
•Các dấu ngoặc.
b) Các câu hay công thức
Mọi ký hiệu chân lý và ký hiệu mệnh đề là câu.
Ví dụ: True, P
Thêm ngoặc ra ngoài một câu sẽ được một câu.
Kết hợp các câu bằng phép nối logic sẽ tạo ra câu mới. Cụ thể là:
Nếu A và B là câu thì:

False) thì ta nói mệnh đề A đúng/sai trong minh họa đó.
Trong một minh họa, ý nghĩa của các câu phức hợp được xác định bởi ý nghĩa
của các kết nối logic. Phép nối logic cho phép quy giá trị câu phức về giá trị các câu
đơn giản hơn. Ý nghĩa các kết nối logic được cho bởi bảng chân lý, trong đó liệt kê
giá trị của câu phức cho tất cả tổ hợp giá trị các thành phần của câu. Bảng chân lý cho
năm kết nối logic được cho trong bảng sau:
Sử dụng bảng chân lý, ta có thể tính được giá trị bất cứ câu phức nào bằng cách
thực hiện đệ quy những kết nối thành phần.
Các công thức tương đương
Các phép biến đổi tương đương giúp đưa các công thức về dạng thuận lợi cho
việc lập luận và suy diễn. Hai công thức A và B được xem là tương đương nếu chúng
có cùng một giá trị chân lý trong mọi minh họa.
Ký hiệu: Để chỉ A tương đương với B ta viết A ≡ B.
Trang 15
Biểu diễn tri thức và suy luận
Bằng phương pháp bảng chân lý, dễ dàng chứng minh được sự tương đương của
các công thức sau đây :
• A =>B ≡ ¬ A Ú B
• A<=> B ≡ (A=>B) ∧ (B=>A)
• ¬ (¬ A) ≡ A
Luật De Morgan
• ¬ (A ∨ B) ≡ ¬ A ∧ ¬ B
• ¬ (A ∧ B) ≡ ¬ A ∨ ¬ B
Luật giao hoán
• A v B ≡ B v A
• A ∧ B ≡ B ∧ A
Luật kết hợp
• (A ∨ B) ∨ C ≡ A ∨ ( B ∨ C)
• (A ∧ B) ∧ C ≡ A ∧ ( B ∧ C)
Luật phân phối

đúng”. Ở đây, công thức □(□P →P) → □P đóng vai trò quan trọng nhất trong các
chứng minh logic.
Lý thuyết các mô hình, lý thuyết điểm bất động và thuật giải SLD của lập trình
logic modal hoàn toàn dựa trên các lý thuyết tương ứng và thuật giải SLD của lập
trình logic cổ điển.
Bài toán đặt ra của lập trình logic modal cũng tương tự bài toán của lập trình
logic cổ điển. Tuy nhiên, có một khác biệt là nó luôn phải được giải trong một hệ
logic modal cụ thể nào đó.
2.5.2 Khung làm việc của lập trình logic Modal
Tương tự như trong lập trình logic cổ điển, lập trình logic modal cũng có những
nguyên lý cơ bản là: ngữ nghĩa mô hình, ngữ nghĩa điểm bất động và thuật giải SLD.
Các nguyên lý này được xây dựng và thừa kế từ lập trình logic cổ điển.
Tuy nhiên, khác với lập trình logic cổ điển, các mô hình, điểm bất động và thuật
giải SLD của lập trình logic modal luôn gắn cùng với một hệ logic modal cụ thể. Chỉ
có một số ít khái niệm là chung cho mọi hệ logic modal.
2.5.2.1 Logic modal cấp 1
Một bộ các ký hiệu của logic modal bao gồm: biến; ký hiệu hằng; ký hiệu hàm;
ký hiệu vị từ; các toán tử: ∧, ∨, ¬, →; các toán tử modal □, ◊; các lượng từ ∀, ∃; các
ký hiệu dấu ngoặc “(, )”, dấu phẩy “,”.
Các toán tử □, ◊ có ngữ nghĩa đa dạng, tùy thuộc vào ngữ cảnh. Tuy nhiên, lớp
nghĩa phổ biến nhất là: □ có nghĩa là “cần thiết / nhất thiết”, ◊ có nghĩa là “khả năng /
có thể”.
Định nghĩa: (Công thức)
Trang 18
Biểu diễn tri thức và suy luận
Một công thức trong logic modal được định nghĩa quy nạp như sau:
+ Nếu p là một ký hiệu vị từ n-ngôi và t1, t2, … tn là các hạng thức thì p(t1, t2,
…, tn) là một công thức. Và được gọi là nguyên tố cổ điển (classical atom).
+ Nếu φ và ψ là các công thức thì (¬φ), (ψ ∨ φ), (ψ∧ φ), (ψ→ φ), (□ψ), (◊φ)
cũng là các công thức.

(n > 0). Trong đó:
+ x1, …, xk là các biến xuất hiện trong B1, …, Bn
+ mỗi Bi là một nguyên tố đích MProlog.
Một câu đích MProlog (G) là ¬Q.
Ký hiệu: ¬∃x1, …, ∃xk(B1 ∧ … ∧ Bn) là ← B1, …, Bn.
Do đó, câu đích MProlog G = ← B1, …, Bn (n>0).
- Ví dụ: ← □p1(a), p2(a). ← ◊p1(a). là các câu đích Mprolog
Định nghĩa: (Chương trình Mprolog [4])
Một chương trình MProlog là một tập các câu chương trình.
2.5.2.3 Mô hình và khung làm việc
Trang 20
Biểu diễn tri thức và suy luận
Với một công thức φ, tính thỏa được (satisfaction) và tính xác đáng (validity) là
quan trọng. Tính thỏa được hay đúng đắn của công thức phải gắn với một mô hình
nào đó còn tính xác đáng phải gắn với một khung (frame) nào đó. Sau đây chúng ta sẽ
định nghĩa mô hình và frame.
Định nghĩa: (Khung làm việc (Frame))
Một frame của ngôn ngữ modal cơ bản là một cặp F = (W, R) thỏa mãn:
+ W là một tập khác rỗng
+ R là một quan hệ nhị phân trên W
Nghĩa là, frame đơn giản là một cấu trúc quan hệ bao gồm một miền giá trị khác
rỗng và một quan hệ nhị phân.
Định nghĩa: (Mô hình (Model) )
Một mô hình (model) của ngôn ngữ modal cơ bản là một cặp M=(F, V). Trong
đó, F là một frame, V là một hàm gán mỗi ký hiệu vị từ p trong tập công thức một tập
con V(p) Φ⊆ W. V(p) là tập các điểm trong mô hình mà p là đúng (true). Hàm V
được gọi là hàm lượng giá (valuation). Khi đó, chúng ta nói mô hình m dựa trên
frame F.
Như vậy, cả frame F và mô hình m dựa trên nó đơn giản là các mô hình quan hệ
dựa trên cùng một miền giá trị (vũ trụ), mô hình chính là frame được bổ sung thêm

Biểu diễn tri thức và suy luận
+ Nếu t là một ký hiệu hằng a thì V(t) = aM
+ Nếu t là một biến x thì V(t) = V(x)
+ Nếu t là một hàm f(t1, …, tn) thì V(t) = fM(V(t1), …, V(tn)).
Sau đây là các định nghĩa về tính thỏa được và tính xác đáng của một công thức
trong mô hình Kripke
Định nghĩa: (Tính thỏa được (satisfaction) của công thức)
Cho một mô hình Kripke M = (D, W, , R, m), một phép gán biến V và một phần
tử w τ ∈ W. Khi đó, một công thức φ là thỏa được trong mô hình M tại w với phép
gán biến V (ký hiệu M, V, w ╞ ) được định nghĩa như sau:
- M, V, w ╞ p(t1, …, tn) nếu và chỉ nếu pM, w(V(t1), …, V(tn))
- M, V, w ╞ ¬φ nếu và chỉ nếu M, V, w ⊭φ
- M, V, w ╞ φ ∧ ϕ nếu và chỉ nếu M, V, w ╞ φ và M, V, w ╞ ϕ
- M, V, w ╞ φ ∨ ϕ nếu và chỉ nếu M, V, w ╞ φ hoặc M, V, w ╞ ϕ
- M, V, w ╞ φ → ϕ nếu và chỉ nếu M, V, w ⊭ φ hoặc M, V, w ╞ ϕ
- M, V, w ╞ □φ nếu và chỉ nếu với mọi v ∈ W sao cho R(w, v) thì M, V, v ╞ φ
- M, V, w ╞ ◊φ nếu và chỉ nếu tồn tại v ∈ W sao cho R(w, v) thì M, V, v ╞ φ
- M, V, w ╞ ∀xφ nếu và chỉ nếu với mọi a ∈ D sao cho M, V’, w ╞ φ. Ở đây,
V’(x) = a và V’(y) = V(y) với x ≠ y
- M, V, w ╞ ∃xφ nếu và chỉ nếu tồn tại a ∈ D sao cho M, V’, w ╞ φ. Ở đây,
V’(x) = a và V’(y) = V(y) với x ≠ y.
Nếu M, V, w ╞ φ thì ta nói φ đúng tại w trong W với phép gán biến V.
Trang 23
Biểu diễn tri thức và suy luận
Chúng ta viết M, w╞ φ thay vì viết M, V, w╞ φ với mọi phép gán biến V.
Chúng ta nói M thỏa mãn φ (hay φ đúng trong M) và viết M ╞ φ nếu M, τ╞ φ.
Với tập T các công thức, chúng ta gọi M là mô hình của T và viết M╞ T nếu M ╞
φ với ∀φ∈ T.
Một hệ logic có thể định nghĩa là một tập các công thức được thiết lập đúng đắn
(well formed fomulae - wwf), một lớp các thể hiện có thể chấp nhận và một quan hệ

vào hệ K một số tiên đề (trong bảng trên). Các hệ mới này cũng đã được chứng minh
là đúng đắn & đầy đủ. Các hệ logic modal khác K sẽ phải có những hạn định nhất
định trên R.
Sau đây là quy ước một số ký hiệu dùng trong MProlog
+ T: ký hiệu hằng giá trị đúng (true).
Trang 25