Một số sơ đồ cơ bản để xây dựng máy suy diễn
Dưới đây ta sẽ trình bày sáu sơ đồ máy. Khi khởi động một trong bốn máy đầu tiên là PREDIAGRAM-1, PREDIAGRAM-2, BACKDIAGRAM-1 và BACK DIAGRAM2, hai biến toàn cục FACTSBASE và RULESBASE được giả thiết là biểu diễn các tập hợp sự kiện và tập hợp luật tương ...
Dưới đây ta sẽ trình bày sáu sơ đồ máy. Khi khởi động một trong bốn máy đầu tiên là PREDIAGRAM-1, PREDIAGRAM-2, BACKDIAGRAM-1 và BACK DIAGRAM2, hai biến toàn cục FACTSBASE và RULESBASE được giả thiết là biểu diễn các tập hợp sự kiện và tập hợp luật tương ứng.
Để minh hoạ hoạt động của bốn máy vừa nói trên, ta xây dựng một cơ sở tri thức ví dụ như sau :
Một cơ sở tri thức ký hiệu
Thành phần bên trái của mỗi luật còn được gọi là phần tiền đề (premise trong luật ba đoạn) của luật, là phép hội (conjunction) của các sự kiện ký hiệu. Thành phần bên phải còn được gọi là phần kết luận (conclusion) của luật. Ta giải thích luật 1 như sau :
- Hoặc : nếu K và L và M là các sự kiện được thiết lập, thì kết luận rằng sự kiện I được thiết lập.
- Hoặc : nếu thiết lập I, cần phải thiết lập K và L và M.
«Đồ thị VÀ-HOẶC» sau đây biểu diễn mọi liên kết có thể của các luật :
Một đồ thị VÀ-HOẶC từ cơ sở tri thức ký hiệu
Trong đồ thị VÀ-HOẶC trên đây (cũng còn được gọi là đồ thị các bài toán con), khi một nhánh HOẶC được thiết lập từ H VÀ F, một nhánh HOẶC được thiết lập từ E VÀ D VÀ C, thì B được thiết lập. Sự kiện F được thiết lập do G được thiết lập. Để cho tiện trình bày, ta đã lặp lại các nút sự kiện C, H, J và M.
Dưới đây, ta xây dựng một đồ thị con VÀ-HOẶC từ đồ thị VÀ-HOẶC trên đây để thiết lập sự kiện Q khi các sự kiện A, C, D và E được thiết lập.
Đồ thị VÀ-HOẶC thiết lập Q khi A, C, D và E được thiết lập
Sơ đồ PREDIAGRAM-1 : lấy ngay kết luận của mỗi luật
PREDIAGRAM- 1 là sơ đồ máy suy diễn gồm hai thủ tục SETUP-A-FACT và RUN-A- CYCLE. Máy suy diễn được khởi động khi thủ tục SETUP-A-FACT được gọi. Ví dụ, để thiết lập Q, người ta gọi : SETUP-A-FACT (‘Q’).
Sơ đồ máy PREDIAGRAM－1
Thủ tục SETUP-A-FACT gây ra sự suy diễn tiến của các luật, bằng cách so sánh các phần tử thuộc tiền đề của các luật với các phần tử của cơ sở sự kiện, xem chúng như những sự kiện đã được thiết lập. Người ta cũng nói trong thủ tục SETUP-A-FACT, phần tiền đề của các luật (giả sử là các thành phần bên trái) cũng là phần khởi động.
Khi một luật được khởi động, phần tử kết luận được thiết lập và ngay lập tức được đưa vào trong cơ sở sự kiện FACTSBASE. Trong suốt quá trình thực hiện thủ tục, FACTSBASE chỉ chứa các sự kiện đã được thiết lập.
Chẳng hạn ta xét cơ sở sự kiện và luật đã cho trong ví dụ hình 3.2. Để có thể thiết lập sự kiện Q, ta khởi động máy PREDIAGRAM－1 ở thủ tục 3.7 bởi lời gọi SETUP-A-FACT(‘Q’).
Máy hoạt động như sau : luật 3 được khởi động để bổ sung B vào FACTSBASE, luật 4 được khởi động để bổ sung Q. Lời gọi thủ tục trả về kết quả «success».
Hình 3 biểu diễn việc liên kết các luật 3 và 4 như là một đồ thị VÀ-HOẶC. Hình 7 dưới đây biểu diễn đồ thị trạng thái của thủ tục.
Đồ thị trạng thái của PREDIAGRAM－2 để thiết lập Q
Vị trí của PREDIAGRAM- 1 đối với chu kỳ cơ bản tổng quát
Bước RESTRICTION loại trừ tất cả những luật đã sử dụng : xem lệnh 4.3 trong thủ tục RUN-A-CYCLE ở hình 3.5. Các bước FILTERING và CONFLICT-RESOLUTION đan xen nhau trong các lệnh từ 1 đến 4 của RUN-A-CYCLE.
Sơ đồ PREDIAGRAM : tạo sinh và tích luỹ sự kiện theo chiều rộng
Tương tự PREDIAGRAM-1, sơ đồ máy suy diễn PREDIAGRAM2 cũng gây ra sự suy diễn tiến của các luật và được gọi bởi thủ tục SETUP-A-FACT ().
Cho E là một sự kiện của cơ sở sự kiện. Trong PREDIAGRAM2, ngược lại với những gì đã xảy ra trong PREDIAGRAM-1, máy tìm kiếm ưu tiên lần lượt từng luật đối với các luật tương thích với E, trước khi bổ sung các kết luận vào trong E và trước khi sử dụng chúng để khởi động các luật mới.
Ta gọi các sự kiện ở mức 0 là các sự kiện khởi đầu, các sự kiện ở mức 1 là các kết luận của các luật có thể được khởi động xuất phát từ các sự kiện khởi đầu, và một cách tổng quát, các sự kiện ở mức n1 là các sự kiện nhận được xuất phát từ các sự kiện mà ít nhất một sự kiện ở mức n, trong khi đó, các sự kiện khác ở mức nhỏ hơn hoặc bằng n. Thủ tục PREDIAGRAM2 chỉ tạo ra các sự kiện ở mức n1 khi tất cả các sự kiện ở mức n đã được tạo ra. Người ta nói rằng PREDIAGRAM2 tạo ra các sự kiện ưu tiên theo chiều rộng.
Những kết luận mới của tất cả các luật tương thích với E được tích luỹ liên tiếp nhờ biến NEWFACTS (lệnh 4.3). Khi tất cả các luật đã được xem xét, NEWFACTS trở nên rỗng trong FACTSBASE (lệnh 1.3).
Sơ đồ máy PREDIAGRAM2
Thủ tục PREDIAGRAM2 gây ra các sự suy diễn tiến của các luật và và tạo ra các sự kiện theo chiều rộng. Để minh hoạ, ta xét cơ sở sự kiện và luật đã cho trong ví dụ ở hình 1. Để có thể thiết lập sự kiện Q, người ta khởi động máy PREDIAGRAM2 bởi lời gọi SETUP-A- FACT(‘Q’).
Đồ thị VÀ-HOẶC trong hình sau đây biểu diễn hoạt động của máy :
Đồ thị VÀ-HOẶC biểu diễn hoạt động của máy PREDIAGRAM2
Xuất phát từ trạng thái đầu của cơ sở sự kiện {A, C, D, E, G, H, K}, luật 3 được khởi động làm cho NEWFACTS = {B}. Sau đó, lần lượt luật 6 rồi luật 9 được khởi động xuất phát từ cùng trạng thái đầu làm cho NEWFACTS = {B, R, F}. Lúc này không còn trạng thái nào được khởi động xuất phát từ trạng thái đầu. Sau đó, tập hợp NEWFACTS trở nên rỗng trong FACTSBASE và FACTSBASE trở thành {A, C, D, E, G, H, K, B, R, F}. Xuất phát từ trạng thái này, luật 4 được khởi động và tạo ra sự kiện Q.
Vị trí của PREDIAGRAM-2 đối với chu kỳ cơ bản tổng quát
Bước RESTRICTION một mặt, loại trừ tất cả những luật đã sử dụng, nhưng mặt khác, không cho phép sử dụng các sự kiện có mức n1 chừng nào mà tất cả các sự kiện có mức nhỏ hơn hoặc bằng n chưa được tạo ra. Các bước FILTERING và CONFLICT-RESOLUTION đan xen nhau trong RUN-A-CYCLE.
Các máy ở chế độ bắt buộc, đơn điệu
Cả hai máy PREDIAGRAM-1 và PREDIAGRAM-2 đều hoạt động theo chế độ bắt buộc, vì rằng việc khởi động của một luật không bao giờ được thay thế bởi một khởi động khác và kết quả tạo ra bởi một luật trong cơ sở sự kiện không bao giờ được xét lại. Mặt khác, các lệnh trong PREDIAGRAM-1 và PREDIAGRAM-2 chỉ cho phép bổ sung các sự kiện đã thiết lập (lệnh 4.2), vì rằng các sự kiện đã thiết lập vẫn còn đó để tiếp tục. Người ta nói rằng những máy này là đơn điệu.
Sơ đồ BACKDIAGRAM -1 : sản sinh các bài toán con theo chiều sâu
Máy suy diễn BACKDIAGRAM-1 cho trong hình 8. dưới đây gồm bốn thủ tục là SETUP-A-FACT, SETUP1, SETUP2 và FACTS-CONJUNCTION-SETUP.
Máy được khởi động bằng cách gọi một trong các thủ tục SETUP-A-FACT hay FACTS- CONJUNCTION-SETUP. Chẳng hạn, để thiết lập Q, ta có lời gọi : SETUP-A FACT(‘Q’).
Thủ tục BACKDIAGRAM-1 tạo ra sự suy diễn lùi của các luật bằng cách so sánh phần kết luận của các luật với các sự kiện cần thiết lập tại thời điểm đang xét. Đối với BACKDIAGRAM-1, phần kết luận của các luật (thành phần bên phải) là phần khởi động của chúng. Chú ý rằng tại mỗi thời điểm, thủ tục duy trì tập hợp các sự kiện cần thiết lập.
Lúc đầu, khi gọi SETUP-A-FACT(‘Q’), tập hợp các sự kiện cần thiết lập chỉ chứa Q. Nếu luật 2 được sử dụng và được khởi động thì sự kiện cần thiết lập Q sẽ được thay thế bởi I, J và L. Người ta nói rằng I, J và L là những bài toán con của bài toán Q hay bài toán Q là cha của các bài toán I, J và L.
Sơ đồ máy BACKDIAGRAM-1
Ta gọi các bài toán ban đầu ở mức 0 và các bài toán mà một cha của chúng là ở mức n, còn các cha khác có thể ở mức nhỏ hơn hoặc bằng n. Để thiết lập một sự kiện Q, BACKDIAGRAM-1 tạo sinh và giải các bài toán con tuỳ theo một chiến lược là trường hợp đặc biệt của họ các chiến lược ưu tiên theo chiều sâu : thủ tục sẽ giải các bài toán con có mức ưu tiên cao nhất.
Phân biệt giữa khởi động một luật và rút ra kết luận của một luật
Khi một luật được sử dụng để thiết lập một sự kiện có mặt trong phần kết luận xuất phát từ các sự kiện có mặt trong phần tiền đề, giả sử đã được thiết lập, người ta nói rằng đã rút ra kết luận của một luật.
Khi một luật được sử dụng theo kiểu suy diễn lùi để thay thế các sự kiện có mặt trong phần tiền đề bởi sự kiện có mặt trong phần kết luận, người ta nói rằng đã khởi động một luật. Vấn đề là không nên nhầm lẫn việc khởi động một luật và rút ra kết luận của một luật.
Ví dụ hoạt động của thủ tục BACKDIAGRAM-1
Ta tiếp tục xét cơ sở sự kiện và luật đã cho trong ví dụ ở hình 1. Để có thể thiết lập sự kiện Q, người ta khởi động máy BACKDIAGRAM-1 bởi lời gọi SETUP-A-FACT (‘Q’).
Đồ thị các bài toán con dưới đây biểu diễn hoạt động của máy :
Đồ thị các bài toán con thiết lập Q của máy BACKDIAGRAM - 1
Khi luật 2 được khởi động, dẫn đến các sự kiện J, L và I cần được thiết lập. Trước tiên, sự kiện I được xem xét, từ đó luật 1 được khởi động dẫn đến các sự kiện M, L và K. Mặc dù sự kiện K được thiết lập, nhưng không có luật nào chứa L hay M trong phần khởi động, nên sự kiện cần được thiết lập lại quay trở lại I. Do không có luật nào chứa I trong phần khởi động,sự kiện cần được thiết lập bây giờ quay trở lại Q. Luật 4 được khởi động, dẫn đến các sự kiện
A và B. Do A đã được thiết lập, máy xem xét sự kiện cần được thiết lập B. Từ đó, luật 3 được khởi động dẫn đến các sự kiện C, D và E. Do C, D và E đã được thiết lập, luật 3 ngay lập tức được ghi nhận : B được thiết lập và do đó, Q được thiết lập.
Vị trí của BACKDIAGRAM-1 đối với chu kỳ cơ bản tổng quát
Do suy diễn lùi, việc khởi động một luật dẫn đến một sự kiện Q, là sự kiện cần được thiết lập (hay giả thuyết cần truy cập, hay bài toán, hay đích) được thay thế bởi nhiều sự kiện khác cần thiết lập, chẳng hạn L, N, O và P.
Tuy nhiên, các bài toán con không có mặt một cách tường minh (explicit) trong cơ sở sự kiện : chúng chỉ được ghi nhớ trong quá trình gọi thủ tục. Những bài toán con chưa được giải quyết làm thành một phần tiềm ẩn (implicit) trong cơ sở sự kiện mà các sự kiện này có vai trò xác định lựa chọn các luật sẽ được sử dụng cho chu kỳ tiếp theo.
Hình 10 dưới đây biểu diễn quá trình khởi động các luật của thủ tục BACKDIAGRAM-1 bởi một đồ thị trạng thái để thiết lập Q.
Phần bên phải của mỗi ô tương ứng với phần tường minh của cơ sở sự kiện, gồm các sự kiện đã thiết lập. Phần bên trái tương ứng với phần ẩn, gồm các sự kiện cần thiết lập hay các bài toán chưa được giải quyết, được in chữ đậm trong hình). Các kết luận cuối cùng kéo theo bởi các luật 3 rồi 2 không được biểu diễn trong hình.
Đồ thị trạng thái thiết lập Q của BACKDIAGRAM－1
Trong BACKDIAGRAM－1, giai đoạn RESTRICTION trước tiên được cụ thể hoá bởi sự phân biệt giữa một bên là các sự kiện đã thiết lập và một bên là các bài toán. Chỉ có các bài toán là được so sánh với các luật, để có thể khởi động chúng. Nghĩa là việc RESTRICTION một mặt vào lúc đầu của mỗi chu kỳ cơ bản, chỉ đến bài toán phải được giải quyết trong chu kỳ này và một mặt, thu hẹp tập hợp các luật cần sử dụng (lệnh 3 của thủ tục SETUP1).
Về nguyên tắc, bài toán này sẽ được xem xét trong số các bài toán xuất hiện từ chu kỳ trước đó (lệnh 2 của FACTS-CONJUNCTION-SETUP, hình 3.9), loại trừ hai trường hợp sau:
- Mọi bài toán xuất hiện từ chu kỳ trước đó bây giờ được coi là đã thiết lập (trả về thông báo ‘success’ bởi lệnh 1 rồi lệnh 5 của thủ tục FACTS-CONJUNCTION- SETUP). Trong trường hợp này, bài toán đã làm khởi động một luật ở chu kỳ trước đó được coi là đã thiết lập (trả về lần cuối cùng thông báo ‘failure’ bởi thủ tục SETUP-A-FACT).
-Có thể xảy ra rằng một bài toán xuất hiện từ chu kỳ trước đó không thể được thiết lập (không thực hiện thủ tục FACTS-CONJUNCTION-SETUP do lệnh 4). Trong trường hợp này, bài toán đã làm khởi động chu kỳ trước đó vẫn còn phải được thiết lập (trả về lần cuối cùng thông báo ‘failure’ bởi thủ tục SETUP-A-FACT).
Trong cả hai trường hợp, về nguyên tắc, việc RESTRICTION sẽ đưa đến một bài toán lấy từ chu kỳ trước trực tiếp và cứ thế tiếp tục.
Thủ tục BACKDIAGRAM-1 dừng, hoặc do tất cả các bài toán lúc đầu được coi là đã được thiết lập, hoặc do một trong chúng không thể được thiết lập.
Tuy nhiên, BACKDIAGRAM-1 có thể không bao giờ dừng, nếu ta thêm vào cơ sở luật RULESBASE ở ví dụ (hình 1) một luật thứ 10 là Q → L.
Các bước GIẢI_QUYẾT_TRANH_ CHẤP và FILTERING trong chu kỳ cơ bản của BACKDIAGRAM-1 đan xen nhau trong các lệnh từ 1 đến 4 của thủ tục SETUP1. Giai đoạn EXECUTION được biểu diễn bởi thủ tục SETUP2.
Một vài biến dạng của BACKDIAGRAM-1
BACKDIAGRAM-1 có thể được mở rộng bằng nhiều cách, chẳng hạn :
- Ghi nhớ các sự kiện đã được thiết lập và hiển thị các thông báo mỗi khi các sự kiện mới xuất hiện.
- Tránh các vòng lặp bằng cách để riêng ra tất cả những luật đã được khởi động một lần.
- Cho phép hệ thống ước lượng một số sự kiện nhờ các câu hỏi của người dùng, thay vì liên kết các luật.
Sơ đồ BACKDIAGRAM - 2 : tạo sinh các bài toán con theo chiều sâu trừ khi có một luật được kết luận ngay
Từ sơ đồ BACKDIAGRAM-1, bằng cách thay đổi chiến lược theo chiều sâu, ta nhận được sơ đồ BACKDIAGRAM-2 cho trong hình 11.
Các thủ tục SETUP1, SETUP2 và FACTS-CONJUNCTION-SETUP của BACKDIAGRAM-2 và BACKDIAGRAM-1 là giống hệt nhau.Giả sử ta có tập hợp các luật kết thúc tại sự kiện FACT (lệnh 2 của thủ tục SETUP-A- FACT), ta mong muốn chỉ xét trước tiên nếu một trong các luật này là kết thúc ngay lập tức, nghĩa là nếu các sự kiện của tiền đề của luật này đã có mặt trong FACTSBASE (lệnh 3 của thủ tục SETUP-A-FACT).
Ta xét các luật kết thúc tại sự kiện FACT tương ứng với một di chuyển theo chiều rộng trên đồ thị của hình... Đó là sau khi xem xét theo chiều rộng không thành công, người ta có xu hướng thiết lập các sự kiện thiếu từ một đến nhiều luật. Điều này tương ứng với một sự tăng tiến từ mức theo chiều sâu so với đỉnh biểu diễn FACT.
Chiến lược này được nhìn nhận như là một bước đầu tiên kể từ các chiến lược ưu tiên theo chiều sâu đến các chiến lược ưu tiên theo chiều rộng. Chiến lược này cũng tương ứng với một dạng thức giải quyết xung đột đặc biệt.
Sơ đồ BACKDIAGRAM －2
Các máy chế độ thăm dò nhưng đơn điệu
Cả hai thủ tục BACKDIAGRAM-2 và BACKDIAGRAM- 1 đều hoạt động theo chế độ thăm dò vì rằng dãy các khởi động luật mà vô ích có thể bị loại bỏ và được thay thế bởi các khởi động khác : các sự kiện cần thiết lập được thay thế bởi các sự kiện khác. Mặc dù có sụ quay lui tác động lên các sự kiện cần thiết lập, nhưng ta thấy rằng cả hai thủ tục BACKDIAGRAM-2 và BACKDIAGRAM- 1 đều không lấy đi, và cũng không thêm vào, các sự kiện đã thiết lập. Cả hai thủ tục đều hoạt động theo chế độ đơn điệu.
Hình 12 dưới đây thể hiện một cơ sở tri thức ký hiệu dùng để tạo ra các kế hoạch hành động (action plan) và phục vụ cho sơ đồ máy ví dụ MIXEDIAGRAM ở hình 14. Luật R1 được giải thích như sau : «để giải bài toán P1, cần thực hiện các hành động A1 rồi A2». Luật R4 được giải thích như sau : «để giải bài toán P3, biết rằng sự kiện F1 đã được thiết lập, chỉ cần thực hiện hành động A5 rồi giải bài toán P4».
Một cơ sở tri thức khởi đầu của sơ đồ máy MIXEDIAGRAM
Liên kết hỗn hợp
Các luật được gọi bằng cách kiểm tra thành phần bên trái của chúng. Mỗi phần tử thuộc thành phần bên trái luật là một bộ lọ, rút gọn thành một ký hiệu trong ví dụ đang xét. Rõ ràng rằng bộ lọc đầu tiên dựa trên một phần đặc biệt của cơ sở sự kiện, chỉ chứa các sự kiện cần thiết lập (hay các bài toán cần giải) được gọi là PROBLEMSTACK (viết tắt PRS). Các bộ lọc khác, thông thường thuộc thành phần bên trái của luật dựa trên một phần của cơ sở sự kiện, theo quy ước, chỉ chứa các sự kiện đã thiết lập, là FACTSBASE.
Thành phần bên trái của luật tạo nên bộ khởi động của luật đó. Các luật được gọi theo liên kết hỗn hợp theo nghĩa rằng các bộ lọc của bộ khởi động có thể quan hệ đồng thời đến các sự kiện đã thiết lập và các sự kiện cần thiết lập. Khi không có các bộ lọc liên quan đến FACTSBASE (các bộ lọc sự kiện), máy hoạt động theo kiểu suy diễn lùi.
Thành phần bên phải của luật là thân của luật đó. Nó xác định các hành động cần thực hiện trên PRS và sau đó là trên FACTSBASE. Chẳng hạn, nếu phần tử đầu tiên của PRS là P1, luật R1 có thể được khởi động : A1 và A2 được đặt một cách tương ứng ở các vị trí đầu tiên và vị trí thứ hai của PRS, trong khi đó, P1 được lấy ra.
Lập hay «tạo sinh kế hoạch»
Các hành động A1, A2, A5, v.v... có thể được xem như là những bài toán giải được ngay, được gọi là các bài toán sơ khởi (primitive problem). Chúng cũng biểu diễn các hành động sơ cấp có thể có mặt trong một kế hoạch hành động, được gọi là các hành động kết thúc (terminal act). Khi một hành động như vậy được chèn vào trong một kế hoạch đang xây dựng, cần biểu diễn các kết quả của nó : thêm vào hay lấy các sự kiện ra. Thêm một sự kiện vào được giải thích như là thiết lập một sự kiện. Lấy ra một sự kiện được giải thích như là không còn được thiết lập nữa.
Một ký hiệu được xem là biểu diễn một hành động kết thúc nếu nó có mặt trong bảng các hành động kết thúc. Khi đó, luật R4 tương đương với :
P3, F1 ← ADD F2, MOVE F4, R4
Sau khi khởi động một luật, khi một hành động có mặt tại vị trí đầu tiên (hay là đỉnh) của PRS, thì nó được lấy ra ngay (từ đỉnh) để đặt vào cuối danh sách PLAN. Tại thời điểm này, quá trình đặt vào, lấy ra mô tả trong bảng các hành động kết thúc ở hình trên đây được thực hiện. Chẳng hạn, khi A5 được lấy ra, F2 được thêm vào trong FACTSBASE và F4 được lấy ra.
Không đơn điệu
Sự khác nhau cơ bản của MIXEDIAGRAM so với các sơ đồ máy trước đây là ở khả năng điều khiển, bởi việc khởi thảo ra một luật (cùng với những thông tin liên quan như trong bảng các hành động kết thúc), việc lấy ra các kết luận trước đó đã được thiết lập bởi áp dụng các luật khác.
Khi một máy suy diễn xét lại các sự kiện đã được thiết lập, người ta nói rằng máy đó là không đơn điệu. Như vậy, MIXEDIAGRAM là máy không đơn điệu.
Khởi động ưu tiên theo độ sâu
Sơ đồ MIXEDIAGRAM
Máy MIXEDIAGRAM được mô tả trong hình 13 trên đây. Xuất phát từ cơ sở tri thức cho trong hình 12, ta có thể sử dụng lời gọi :
SOLVE-A-PROBLEM (P2)
Máy khởi động luật đầu tiên của RULESBASE có bộ khởi động tương thích với PRS và FACTSBASE. Luật này được khởi động và sẽ là luật đầu tiên của RULESBASE tương thích với tình huống được tạo ra bởi việc khởi động của luật trước đó : quá trình khởi động ưu tiên theo chiều sâu.
Nếu PRS trở nên rỗng, máy dừng lại : bài toán ban đầu đã được giải, trạng thái hiện hành của PLAN được cung cấp. Nếu PRS không rỗng, nhưng nếu không còn một luật nào khởi động được, MIXEDIAGRAM sẽ có khuynh hướng quay lui : nghĩa là nó sẽ áp dụng một luật mới cho bài toán cuối cùng không là sơ khởi đã được lấy ra từ PRS, và cứ thế tiếp tục.
Các máy BACKDIAGRAM-1 và BACKDIAGRAM-2 cũng có cơ chế quay lui. Tuy nhiên, đối với MIXEDIAGRAM, điều mới ở đây là khi xem xét lại cách một bài toán được phân tách ra, MIXEDIAGRAM lại được dẫn đến thiết lập lại bối cảnh (trạng thái của PRS, FACTSBASE, PLAN) giống hệt bối cảnh đã tồn tại ở thời điểm bài toán này được xem xét, trước khi xem xét lại lần nữa, nếu có thể, bởi luật phân tách khác. Do vậy, sơ đồ MIXEDIAGRAM dẫn đến một chương trình khác hẳn.
Đồ thị tìm kiếm tạo sinh bởi máy MIXEDIAGRAM
Hình 14 trên đây là đồ thị VÀ-HOẶC biểu diễn sự kết nối các luật tạo ra từ cơ sở tri thức cho trong ví dụ ở hình 12.
Ta có:
| Cácbước | Kết quảhành động | Nội dungPROBLEMSTACK | Nội dungFACTSBASE | Nội dungPLAN |
| 1 | Khởi động luật R3 | (P1 A4 P3) | không thay đổi | rỗng |
| 2 | Khởi động luật R1 | (A1 A2 A4 P3) | không thay đổi | rỗng |
| 3 | Lấy A1, A2, A4 từ đỉnh PRS | (P3) | {F2 F3 F4} | (A1 A2 A4) |
| 4 | Khởi động luật R5 | (P5) | không thay đổi | không thay đổi |
| 5 | Không còn luật nào được khởiđộng, quay lại giải P3 | |||
| (P3) | {F2 F3 F4} | (A1 A2 A4) | ||
| RULES={R6 R7} | ||||
| 6 | Khởi động luật R6 | (A4 P6) | không thay đổi | không thay đổi |
| 7 | Lấy A4 từ đỉnh PRS | (P6) | không thay đổi | (A1 A2 A4 A4) |
| 8 | Không còn luật nào được khởiđộng, quay lại giải P3 | |||
| (P3) | {F2 F3 F4} | (A1 A2 A4) | ||
| RULES = {R7} | ||||
| 9 | Không còn luật nào được khởiđộng, quay lại giải P1 | |||
| (P1 A4 P3) | {F3 F4} | rỗng | ||
| RULES = {R4 R3 R4 R5 R6 R7} | ||||
| 10 | Khởi động luật R2 | (A3 A4 P3) | không thay đổi | rỗng |
| 11 | Lấy A3 và A4 từ đỉnh PRS | (P3) | {F1 F3 F4} | (A3 A4) |
| 12 | Khởi động luật R4 | (A5 A4) | không thay đổi | không thay đổi |
| 13 | Lấy A5 từ đỉnh PRS | (P4) | {F1 F2 F3} | (A3 A4 A5) |
| 14 | Khởi động luật R7 | (A2) | không thay đổi | không thay đổi |
| 15 | Lấy A2 từ đỉnh PRS | rỗng | {F1 F2 F3} | (A3 A4 A5 A2) |
| 16 | Máy dừng |
Giải thích sơ đồ MIXEDIAGRAM
Thủ tục SOLVE để rút gọn bài toán đầu (gọi là PB) khỏi PROBLEMSTACK khi thủ tục RUN-A-CYCLE được gọi. Có bốn trường hợp xảy ra :
Trường hợp 1 :
Thủ tục RUN-A-CYCLE trả về ‘failure’ khi PB không tương ứng với một hành động kết thúc và không được phân tách bởi một luật nào từ danh sách RULES. Trong trường hợp này, thủ tục hiện hành SOLVE dừng và trả về ‘failure’ ở mức cao hơn.
Tham đối thứ hai của RUN-A-CYCLE là RULE-INDIC nhận được giống như là tham đối thứ hai của SOLVE. Tại lời gọi đầu tiên của SOLVE bởi SOLVE-A-PROBLEM (lệnh 4), tham đối này có giá trị của RULESBASE. Tương tự như vậy đối với một số lời gọi của SOLVE bởi chính nó (lệnh 5). Đối với các lời gọi khác (lệnh 11 của SOLVE), tham đối này không còn là một danh sách con của RULESBASE.
Nếu RUN-A-CYCLE không trả về ‘failure’ là vì, hoặc PB là một hành động kết thúc, hoặc PB là một bài toán phân tách được bởi một trong các luật của danh sách cung cấp cho lời gọi RUN-A-CYCLE. Trong hai tình huống này, người ta gọi ngay lập tức thủ tục SOLVE với tham đối thứ nhất là bối cảnh của việc xử lý PB (tiến triển của FACTSBASE và/hoặc của PROBLEMSTACK) bởi RUN-A-CYCLE, và tham đối thứ hai là toàn bộ RULESBASE. Sau đây, ta gọi R là lời gọi này đối với thủ tục SOLVE.
Trường hợp 2 :
Nếu lời gọi cuối cùng R này đối với SOLVE trả về ‘success’, thủ tục SOLVE hiện hành trả về ‘success’ ở mức cao hơn. Nếu không, việc xử lý phải phân biệt tuỳ theo thủ tục RUN-A-CYCLE đã nhận biết PB như là một hành động kết thúc, nghĩa là một bài toán sơ khởi không thể phân tách được, hoặc đã được dự kiến phân tách.
Trường hợp 3 :
Thủ tục RUN-A-CYCLE sẽ trả về ‘primitive’ nếu PB là một hành động kết thúc. Trong trường hợp này, sự thất bại của lời gọi R đối với SOLVE có nghĩa cần phải xem xét lại việc đặt PB vào đầu danh sách PROBLEMSTACK : lúc này, thủ tục SOLVE hiện hành trả về ‘failure’ ở mức cao hơn.
Trường hợp 4 :
Nếu PB không là một hành động kết thúc, thì PB phải phân tách được. Như vậy, thủ tục RUN-A-CYCLE đã khởi động một luật để phân tách PB, đặt kết quả phân tách của PB vào đầu danh sách PROBLEMSTACK và trả về danh sách con của RULESBASE có phần tử đầu tiên là luật vừa được khởi động. Trong trường hợp này, lời gọi R đối với SOLVE không thành công do có sự xuất hiện các bài toán con của PB. Vì vậy, cần thử tìm một phân tách khác đối với PB : bối cảnh đã tồn tại trước lời gọi RUN-A-CYCLE được khôi phục và xuất hiện một lời gọi mới đối với SOLVE. Tham đối thứ nhất của lời gọi này đối với SOLVE là danh sách các luật nhận được từ tham đối của SOLVE hiện hành, sau khi lấy đi luật đã thử.
Một vài biến tấu đơn giản khác của MIXEDIAGRAM
Dãy các bài toán. Tương tác
Trên nhiều điểm khác nhau, người ta có thể phỏng theo sơ đồ BACK DIAGRAM－1. Để đưa ra một dãy có thứ tự các bài toán, chỉ cần xem xét lại thủ tục SOLVE-A-PROBLEM sao cho dãy này được nạp vào PROBLEMSTACK khi mới khởi động. Ta có thể dự kiến một hoạt động tương tác : khi không có một luật nào áp dụng được cho bài toán nằm trên đỉnh của PROBLEMSTACK (xem lệnh 2 của RUN-A- CYCLE), người ta có thể quyết định, trước khi quay lui, hỏi người sử dụng xem có cần hiển thị phần tử đỉnh của PROBLEMSTACK, và hiển thị, hoặc tất cả hoặc một phần của FACTSBASE hay không ? Người sử dụng cũng có thể chỉ ra bài toán có thể giải được trong điều kiện đã định.
Điều khiển theo độ sâu
Vì các sự kiện đã thiết lập có thể được xem xét lại, người ta cần phải khởi động một luật nhiều lần, trong cùng một bối cảnh, nên có thể dẫn đến nguy cơ xoay vòng. Để điều khiển sự tiến triển tìm kiếm theo độ sâu, người ta có thể gắn mỗi phần tử PB của PROBLEMSTACK với một «mức» bằng mức của bài toán là bài toán đã được phân tách để xuất hiện PB cộng thêm 1. Bài toán khởi đầu sẽ được gắn mức 0. Người ta không cho phép giải quyết bài toán có mức vượt quá một giá trị gíới hạn đã được ấn định trước. Chú ý rằng mức của một bài toán có thể giảm dần theo quá trình tìm kiếm.
Tìm kiếm tất cả các lời giải
Có thể có nhiều kế hoạch hành động cùng biểu diễn lời giải của một bài toán đã cho. Trong ví dụ ở hình 12, người ta có thể tìm thấy hai kế hoạch để giải P là kế hoạch (A1 A2) và kế hoạch (A3).
Nếu ta thêm một luật thứ tám là P1←A1, ta sẽ tìm thấy hai kế hoạch để giải P2 là (A3 A4 A5 A2) và kế hoạch (A1 A4 A5 A2).
Lúc này ta có thể thay đổi MIXEDIAGRAM sao cho khi cần, nó có thể tìm được các kế hoạch khác nhau này. Muốn vậy, ta sẽ bỏ dòng lệnh 5 của SOLVE-A-PROBLEM và thay thế lệnh 1 của SOLVE bởi :
1 if PROBLEMSTACK = Ø then
1.1 begin
1.2 Soạn thảo PLAN
1.3 Yêu cầu người sử dụng lập PLAN khác (Y/N?)
1.4 if đồng ý (Y) then return ‘failure’
1.5 return ‘success’
1.6 end
Ở lệnh 1.4, người ta đã tạo ra một ‘failure’ để bắt buộc máy tìm kiếm một lời giải khác có thể, xuất phát từ bối cảnh hiện hành.
Hình 15 trình bày một ví dụ về tri thức và các bài toán sẽ được giải bởi máy BACKDIAGRAM- 3 . Chú ý rằng trong hình 15, các thể hiện tri thức có chứa các biến, các biến được đặt tên quy ước là x, y, z, u và v. Các ký hiệu C1, C2, C3, C4, C5, C8 biểu diễn các sự kiện đã được thiết lập, C6, C7, C9 biểu diễn luật.
Sự kiện C3 trong cơ sở thể hiện pierre là cha của jean. Sự kiện C6 nói lên rằng dù x hay y là như thế nào, ngay khi SON(y, x) được thiết lập, nghĩa là khi đã thiết lập y là con của x, thì có thể thiết lập FATHER(x, y), nghĩa là x là cha của y. Hay ngược lại : dù x hay y là như thế nào, để thiết lập FATHER(x, y), chỉ cần thiết lập SON(y, x). Sự kiện C6 thể hiện dù x, y và z là như thế nào, để thiết lập rằng x là ông của y, chỉ cần thiết lập x là cha của z và z là cha của y.
Ở đây, ta quy ước rằng các thành phần bên trái luật là kết luận của luật, các thành phần bên phải luật là tiền đề. Các luật luôn luôn chỉ chứa một kết luận duy nhất và có một hoặc nhiều tiền đề.
Cơ sở tri thức và PROBLEMSTACK của BACKDIAGRAM- 3
Cần «tìm x và y sao cho x là ông của y, x có tóc hoe». Trạng thái ban đầu của PROBLEMSTACK (viết tắt PBS) cho trong hình 5 trên đây.
Hoạt động của BACKDIAGRAM - 3
Hoạt động của máy BACKDIAGRAM - 3 để tìm lời giải cho ví dụ 1 như sau :
- Chu kỳ đầu tiên
Máy lần lượt giải các bài toán đã được sắp xếp trong PBS. Trước tiên, máy ghép đôi biểu thức GRANDFATHER (u, v) lần lượt với các tri thức từ C1 đến C8 theo thứ tự này. Nếu C1 là một luật, thì việc ghép đôi chỉ tác động lên phần kết luận của luật. Việc ghép đôi giữa GRANDFATHER (u, v) với kết luận của C7 thành công : thật vậy, bằng cách áp dụng các thay thế «u bởi x» và «v bởi y» trong GRANDFATHER (u, v), ta nhận được hai biểu thức giống hệt nhau.
Ta nói là đã hợp nhất (unified) GRANDFATHER (u, v) và GRANDFATHER (x, y) bởi phép hợp nhất (unifier) ký hiệu UNIF như sau :
UNIF = «u bởi x» và «v bởi y» hay được viết tắt là :
UNIF = (x □ u ; y □ v)
Trong trường hợp đặc biệt này, sẽ có một trong các biểu thức không bị thay đổi bởi áp dụng phép hợp nhất. Trong khi ghép đôi, máy sẽ biến đổi PBS bằng cách thay thế GRANDFATHER (u, v) bởi phần tiền đề của C7, sau khi đã áp dụng phép hợp nhất cho phần tiền đề này. Có thể phần tiền đề không bị thay đổi bởi đã áp dụng phép hợp nhất.
UNIF tiếp tục được áp dụng cho phần còn lại của PBS, hay BLOND (u). Ta nhận được : PBS = (FATHER (x, z) FATHER (z, y) BLOND (x))
Như vậy, ta đã dẫn bài toán ban đầu («hãy xác định nếu tồn tại u, v sao cho u hoặc là ông của v, hoặc v có tóc hoe») thành bài toán «hãy xác định nếu tồn tại x, y và z sao cho x là cha của z và z là cha của y và x có tóc hoe».
Hình 16 dưới đây biểu diễn các chu kỳ thực hiện của BACKDIAGRAM - 3 :
Cơ sở tri thức và PROBLEMSTACK của BACKDIAGRAM－3
Xuất phát từ các biểu thức (GRANDFATHER (u, v) BLOND (u)) và GRANDFATHER (x, y) ← FATHER (x, z), FATHER (z, y), ta đã suy diễn được : PBS = (FATHER (x, z), FATHER (z, y) BLOND (x))
Nội dung mới của PBS chính là kết quả hợp giải (resolvant) từ các biểu thức của PBS và của luật C7 theo nguyên lý hợp giải đã giới thiệu trước đây.
- Chu kỳ thứ 2
Phần tử đầu tiên của PBS là FATHER (x, z) sẽ được so sánh với các tri thức từ C1 đến C8 theo thứ tự này.
Máy phát hiện ra phép hợp nhất UNIF = (pierre x, jean z) giữa FATHER (x, z) và C3. Khi đó, sẽ tồn tại x (x = pierre) và z (z = jean) sao cho x phải là cha của z. Bài toán đầu tiên của PBS xem như đã được giải và được lấy ra khỏi PBS. Những bài toán cần giải còn lại của PBS tiếp tục được hợp nhất bởi UNIF và dẫn đến kết quả :
PBS = (FATHER (jean, y) BLOND (pierre))
- Chu kỳ thứ 3
FATHER (jean, y) được ghép đôi với C5 nhờ phép hợp nhất UNIF = (rené y) để nhận được :
PBS = (BLOND (pierre))
- Chu kỳ thứ 4
BLOND (pierre) không thể được ghép đôi với tri thức nào trong các tri thức từ C1 đến C8. Chu kỳ thứ tư thất bại (dừng không qua giai đoạn EXECUTION).
- Chu kỳ thứ 5
Bước RESTRICTION yêu cầu máy quay lui. Lúc này, PBS được khôi phục lại tình trạng ở thời điểm đầu chu kỳ trước đó là không thể tiếp tục (chu kỳ thứ ba) : PBS = (FATHER (jean, y) BLOND (pierre))
Việc ghép đôi được duy trì trong chu kỳ thứ ba này (tương ứng với bước CONFLICT- RESOLUTION). Máy chuẩn bị ghép đôi lại (bước FILTERING) đối với FATHER (jean, y) xuất phát từ C6. Việc ghép đối với C6 thành công, do có phép hợp nhất UNIF = (jean x),từ đó :
PBS = (SON (y, jean) BLOND (pierre))
- Chu kỳ thứ 6
SON (y, jean) không thể ghép đôi với tri thức nào trong các tri thức từ C1 đến C8. Chu kỳ thứ sáu không thể kết thúc bình thường (dừng không qua giai đoạn EXECUTION).
- Chu kỳ thứ 7
Bước RESTRICTION yêu cầu máy tiếp tục quay lui. PBS khôi phục lại tình trạng ở thời điểm đầu chu kỳ trước đó là không thể tiếp tục (chu kỳ năm) : PBS = (FATHER (jean, y) BLOND (pierre))
Việc ghép đôi được duy trì trong chu kỳ thứ năm này (tương ứng với bước CONFLICT- RESOLUTION). Máy chuẩn bị ghép đôi lại (bước FILTERING) đối với FATHER (jean, y) xuất phát từ C7. Việc ghép đôi với C7 thất bại, do đó chu kỳ thứ bảy không thể chuyển qua giai đoạn EXECUTION.
- Chu kỳ thứ 8
Máy tiếp tục quay lui. PBS được khôi phục lại tình trạng ở thời điểm đầu chu kỳ hai, nghĩa là :
PBS = (FATHER (x, z), FATHER (z, y) BLOND (x))
Việc ghép đôi được duy trì trong chu kỳ thứ hai này. Máy chuẩn bị ghép đôi lại đối với FATHER (x, z) xuất phát từ C4. Việc ghép đối với C6 thành công, do có phép hợp nhất UNIF = (marc x ; pierre z), từ đó :
PBS = (FATHER (pierre, y) BLOND (marc))
- Chu kỳ thứ 9
Máy có thể ghép đôi FATHER (pierre, y) với C3 nhờ phép hợp nhất : UNIF = (jean y)
Từ đó :
PBS = BLOND (marc)
- Chu kỳ thứ 10
Máy có thể ghép đôi BLOND (marc) với C1 mà không cần dùng một phép hợp nhất nào. Do PBS trở nên rỗng, nên dãy các phép thế đưa vào đối với các biến khởi động của PBS không được sử dụng đến (không quay lui) tạo thành một lời giải cho bài toán ban đầu : tồn tại u (u = marc) và v (v = jean) sao cho u là ông của jean và u có tóc hoe. Kết quả xử lý của sơ đồ máy BACKDIAGRAM - 3 đối với bài toán trên đây chính là dãy các phép thế như sau :
UNIF = (x u ; y v ; marc x ; jean y)
Từ các tri thức đã cho ở hình 15, ta muốn «tìm kiếm u sao cho u là ông của pierre». Từ đó, nội dung ban đầu của PROBLEMSTACK sẽ là :
PBS = GRANDFATHER (u, pierre)
Bằng cách nhại lại (bắt chước) y hệt các bước vừa trình bày trên đây, ta nhận được kết quả hợp giải cho trong hình 17 dưới đây. Câu trả lời được đưa ra ở nhánh thứ tư : tồn tại u, u = georges, sao cho u là ông của pierre.
Các con số trong hình tương ứng với thứ tự của các hợp nhất.
Đồ thị hợp nhất của BACKDIAGRAM－3
BACKDIAGRAM - 3 : sơ đồ máy suy diễn kiểu Prolog
Sơ đồ máy BACKDIAGRAM - 3 sử dụng các tri thức kiểu suy diễn lùi và ưu tiên theo độ sâu. Sơ đồ này không thiết lập các sự kiện mới mà chỉ đơn giản là biến đổi PBS, danh sách có thứ tự các sự kiện đang còn phải thiết lập. Do không bao giờ lấy ra các sự kiện đã thiết lập, nên cách hoạt động của máy là đơn điệu. Mặt khác, do các trạng thái trước của PBS có thể được khôi phục (quay lui), máy hoạt động theo chế độ thăm dò.
Giai đoạn SELECTION/RESTRICTION nhằm tập trung sử dụng các tri thức (luật và sự kiện) đối với phần tử đầu tiên của PBS. Tuỳ theo sự quay lui của máy, trạng thái của PBS có thể xác định được.
Ngôn ngữ thể hiện tri thức cho trong hình 15 và được sử dụng trong sơ đồ máy BACKDIAGRAM - 3 tương tự ngôn ngữ Prolog. Các biểu thức biểu diễn tri thức là những «mệnh đề Horn». Chú ý rằng thông thường, các hệ chuyên gia chỉ thừa nhận các biến trong các luật, mà không thừa nhận các biến trong các sự kiện như trong hai ví dụ trên.
Việc tạo sinh các kết quả hợp giải ưu tiên theo độ sâu có thể dẫn đến vòng lặp, nhưng có thể tránh được trong chiến lược ưu tiên theo chiều rộng. Chẳng hạn, vòng lặp gây ra bởi chiến lược ưu tiên theo độ sâu : nếu ta thêm phần tử C9 vào cuối danh sách các tri thức KNOWLEDGESBASE như sau :
C9 : SON (x, y) ← FATHER (y, x)
Và nếu xét lại bài toán GRANDFATHER (u, pierre) ở ví dụ 2, máy sẽ áp dụng vô hạn lần các luật C6-C9-C6-C9-...
Giải thích sơ đồ máy BACKDIAGRAM－3
Có hai tham đối trong lời gọi thủ tục JUSTIFY. Tham đối thứ nhất là một danh sách có thứ tự các bài toán cho trước. Chú ý rằng sự xuất hiện của một biến trong biểu diễn bài toán, chẳng hạn biến x trong P(x), tương ứng với một câu hỏi về giá trị của x để có P(x). Tham đối thứ hai là một danh sách có thứ tự các tri thức cho trước lúc khởi động thủ tục. Lời gọi thủ tục có dạng :
JUSTIFY (PBS, KNOWLEDGESBASE)
trong đó PBS và KNOWLEDGESBASE có giá trị cho trong ví dụ 1 hình 15.
Khi thủ tục JUSTIFY kết thúc (có thể không kết thúc), JUSTIFY trả về hoặc giá trị ‘failure’, hoặc lời giải là một danh sách (có thể rỗng) các phép thế trên các biến của bài toán ban đầu. Ví dụ, trong ví dụ 1 hình 3.16, thủ tục JUSTIFY trả về lời giải là danh sách có thứ tự (x □ u ; y □ v ; marc □ x ; jean □ y).
Rằng lệnh 4 của thủ tục JUSTIFY dùng để kiểm tra nếu các biến có mặt trong AKNOWLEDGE là khác với các biến có mặt trong APROBLEM. Nếu có sự bằng nhau, người ta đổi tên những biến cần thiết trong AKNOWLEDGE cho đến khi thoả mãn.Nếu:
AKNOWLEDGE = P(x, a) ←Q(x) và nếu APROBLEM = P(b, x)
thì người ta đổi tên biến x thành một biến gốc, giả sử y, trong AKNOWLEDGE, để nhận được : P(y, a) ← Q(y). Sự đổi tên biến là hợp lệ vì biến x (tương ứng với lượng tử toàn thể) trong AKNOWLEDGE thực tế là một biến câm, độc lập với các biến x có mặt trong các thể hiện bài toán hay trong các biểu diễn tri thức khác. Sự đổi tên biến là cần thiết để P(x, a) và P(b, x) có thể hợp nhất được.
Trong chương trước, ta đã giới thiệu chi tiết thuật toán hợp nhất hai trực kiện. Thủ tục UNIFICATION được sử dụng trên đây có thể được lập trình dựa theo thuật toán này. Ta giả thiết rằng lời gọi thủ tục chứa ba tham đối : hai tham đối là hai biểu thức cần hợp nhất, tham đối thứ ba là một danh sách rỗng. Thủ tục trả về ‘failure’ nếu không tồn tại phép hợp nhất giữa hai biểu thức. Thủ tục trả về kết quả là phép hợp nhất dưới dạng một danh sách (có thể rỗng) các phép thế nếu tồn tại phép hợp nhất.
Bài tập:
Cho các câu sau :
- Jhon thích tất cả các loại thức ăn.
- Táo là một loại thức ăn.
- Thịt gà là một loại thức ăn.
- Bất cứ thứ gì mà bất cứ người nào ăn mà không chết đều là thức ăn.
- Bill ăn lạc rang và anh ta vẫn sống.
- Sue bất cứ thứ gi mà Bill ăn.
Yêu cầu :
a. Chuyển các câu trên thành các công thức chỉnh (wff) theo vị từ bậc một.
b. Chuyển các công thức chỉnh câu a. thành dạng mệnh đề.
c. Sử dụng hợp giải để chứng minh rằng Jhon thích lạc rang.
d. Sử dụng hợp giải để trả lời câu hỏi “Sue ăn thức gì ?”
Cho các sự kiện sau :
- Các thành viên của câu lạc bộ Đồng hương là Joe, Sally, Bill và Ellen.
- Joe là chồng của Sally.
- Bill là anh trai của Ellen.
- Vợ của mỗi thành viên đã lập gia đình trong câu lạc bộ cũng là thành viên của câu lạc bộ.
- Buổi họp mặt câu lạc bộ Đồng hương gần nhất là ở tại nhà Joe. Yêu cầu :
a. Chuyển các sự kiện trên thành các vị từ bậc một.
b. Sử dụng hợp giải để chứng minh tính đúng đắn của hai mệnh đề dưới đây. Chú ý nếu không thể chứng minh đúng, thì hãy thêm vào các sự kiện mới để có thể chứng minh :
- Buổi họp mặt câu lạc bộ Đồng hương gần nhất là ở tại nhà Sally.
- Ellen chưa lập gia đình.
Cho các sự kiện sau :
- Steve chỉ thích các môn dễ học.
- Các môn học về lập trình đều khó.
- Tất cả những môn học trong bộ môn thể dục đều dễ học.
- Bóng chuyền là một môn thể dục
Sử dụng hợp giải để trả lời câu hỏi “Steve thích học môn gì ?“
Cho một cơ sở tri thức như sau :
R1. B, D, E → F
R2. D, G → A
R3. C, F → A
R4. B → X
R5. D → E
R6. A, X → H
R7. C → D
R8. X, C → A
R9. X, B → D
Yêu cầu :
a. Vẽ đồ thị và-hoặc từ cơ sở tri thức trên.
b. Vẽ đồ thị và-hoặc minh hoạ thuật toán suy diễn tiến theo chiều sâu.
c. Vẽ đồ thị và-hoặc minh hoạ thuật toán suy diễn tiến theo chiều rộng.
d. Vẽ đồ thị và-hoặc minh hoạ thuật toán suy diễn lùi
Làm tất cả các câu hỏi đã cho trong bài tập 4. cho các cơ sở tri thức đã cho ở các bài tập 1, 2, 3 trên đây.
