🔙 Quay lại trang tải sách pdf ebook Giáo trình hệ chuyên gia Ebooks Nhóm Zalo ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN GIÁO TRÌNH HỆ CHUYÊN GIA PGS.TS. PHAN HUY KHÁNH ĐÀ NẴNG 9-2004 Mục lục CHƯƠNG 1 Mở ĐầU ........................................................................................................................7 I. GIớI THIệU Hệ CHUYÊN GIA ............................................................................................7 I.1. Hệ chuyên gia là gì ?......................................................................................7 I.2. Đặc trưng và ưu điểm của hệ chuyên gia.......................................................9 I.3. Sự phát triển của công nghệ hệ chuyên gia....................................................9 I.4. Các lĩnh vực ứng dụng của hệ chuyên gia ...................................................10 II. KIếN TRÚC TổNG QUÁT CủA CÁC Hệ CHUYÊN GIA .........................................................12 II.1. Những thành phần cơ bản của một hệ chuyên gia .......................................12 II.2. Một số mô hình kiến trúc hệ chuyên gia.......................................................14 a. Mô hình J. L. Ermine ...................................................................................14 b. Mô hình C. Ernest ........................................................................................14 c. Mô hình E. V. Popov....................................................................................15 II.3. Biểu diễn tri thức trong các hệ chuyên gia ..................................................15 II.3.1. Biểu diễn tri thức bởi các luật sản xuất ........................................................15 II.3.2. Bộ sinh của hệ chuyên gia............................................................................17 II.3.3. «Soạn thảo kết hợp» các luật........................................................................18 II.3.4. Các phương pháp biểu diễn tri thức khác.....................................................19 a. Biểu diễn tri thức nhờ mệnh đề logic ...........................................................19 b. Biểu diễn tri thức nhờ mạng ngữ nghĩa........................................................20 c. Biểu diễn tri thức nhờ ngôn ngữ nhân tạo....................................................21 II.4. Kỹ thuật suy luận trong các hệ chuyên gia ..................................................21 II.4.1. Phương pháp suy diễn tiến ...........................................................................22 II.4.2. Phương pháp suy diễn lùi.............................................................................22 II.4.3. Các hệ thống sản xuất (production systems)................................................23 a. Các hệ thống sản xuất Post...........................................................................23 b. Các thuật toán Markov .................................................................................24 c. Thuật toán mạng lưới (rete algorithm) .........................................................25 III. THIếT Kế Hệ CHUYÊN GIA.............................................................................................25 III.1. Thuật toán tổng quát ....................................................................................25 III.2. Các bước phát triển hệ chuyên gia ..............................................................26 a. Quản lý dự án (Project Management) ..........................................................26 b. Tiếp nhận tri thức .........................................................................................28 c. Vấn đề phân phối (The Delivery Problem) ..................................................28 d. Bảo trì và phát triển......................................................................................28 III.3. Sai sót trong quá trình phát triển hệ chuyên gia..........................................29 BÀI TậP CHƯƠNG 1 ..............................................................................................................31 BIểU DIễN TRI THứC NHờ LOGIC Vị Từ BậC MộT ........................................................33 I. NGÔN NGữ Vị Từ BậC MộT.............................................................................................33 I.1. Các khái niệm...............................................................................................33 I.1.1. Cú pháp của ngôn ngữ vị từ bậc một............................................................33 I.1.2. Các luật suy diễn (inference rule) ................................................................35 I.1.3. Ngữ nghĩa của ngôn ngữ vị từ bậc một ........................................................36 a. Diễn giải (Interpretation)..............................................................................36 Mục lục 3 b. Giá trị một công thức theo diễn giải ............................................................ 37 I.2. Các tính chất................................................................................................ 38 I.2.1. Tính hợp thức / không hợp thức, tính nhất quán / không nhất quán............ 38 I.2.2. Tính không quyết định được và tính nửa quyết định được.......................... 39 I.2.3. Công thức tương đương ............................................................................... 39 I.2.4. Hậu quả logic ............................................................................................... 40 I.3. Quan hệ giữa định lý và hậu quả logic........................................................ 40 I.3.1. Nhóm các luật suy diễn «đúng đắn» (sound)............................................... 40 I.3.2. Nhóm các luật suy diễn «đầy đủ»................................................................ 40 I.3.3. Vì sao cần «đúng đắn» hay «đầy đủ» ?........................................................ 41 II. PHÉP HợP GIảI.............................................................................................................. 41 II.1. Biến đổi các mệnh đề ................................................................................... 41 II.1.1. Dạng chuẩn trước của một công thức chỉnh ................................................ 41 a. Loại bỏ các phép nối → và ↔..................................................................... 41 b. Ghép các phép nối ← với các nguyên tử liên quan ...................................... 41 c. Phân biệt các biến ........................................................................................ 41 d. Dịch chuyển các dấu lượng tử ..................................................................... 42 II.1.2. Chuyển qua “dạng mệnh đề” của công thức chỉnh ...................................... 42 a. Loại bởi các dấu lượng tử tồn tại ................................................................. 42 b. Loại bỏ tất cả các dấu lượng tử.................................................................... 43 c. Chuyển qua «dạng chuẩn hội»..................................................................... 43 d. Loại bỏ tất cả các dấu phép toán logic......................................................... 44 e. Phân biệt các biến của các mệnh đề............................................................. 44 II.1.3. Quan hệ giữa CTC và các dạng mệnh đề của chúng.................................... 44 II.1.4. Phép hợp giải đối với các mệnh đề cụ thể ................................................... 46 II.2. Phép hợp nhất (unification) ......................................................................... 46 II.2.1. Khái niêm..................................................................................................... 46 a. Phép thế........................................................................................................ 47 b. Bộ hợp nhất (unifier).................................................................................... 47 c. Thuật toán hợp nhất ..................................................................................... 48 II.2.2. Hợp giải các mệnh đề bất kỳ........................................................................ 50 II.2.3. Một cách trình bày khác của phép hợp giải ................................................. 51 II.3. Các tính chất tổng quát của phép hợp giải.................................................. 52 a. Một luật đúng đắn ........................................................................................ 52 b. Tính hoàn toàn của phép hợp giải đối với phép bác bỏ ............................... 52 III. CÁC Hệ THốNG BÁC Bỏ BởI HợP GIảI.............................................................................. 53 III.1. Thủ tục tổng quát bác bỏ bởi hợp giải......................................................... 53 III.2. Chiến lược hợp giải ..................................................................................... 54 III.2.1. Đồ thị định hướng, đồ thị tìm kiếm và đồ thị bác bỏ................................... 54 III.2.2. Chiến lược hợp giải bởi bác bỏ theo chiều rộng .......................................... 55 III.2.3. Chiến lược hợp giải bởi bác bỏ với «tập hợp trợ giúp»............................... 57 III.2.4. Chiến lược hợp giải bởi bác bỏ dùng «khoá» .............................................. 58 III.2.5. Chiến lược hợp giải bởi bác bỏ là «tuyến tính»........................................... 59 III.2.6. Chiến lược bác bỏ bởi hợp giải là «tuyến tính theo đầu vào» ............................... 62 III.2.7. Chiến lược hợp giải «LUSH» ...................................................................... 63 III.3. Ví dụ minh hoạ : bài toán tìm người nói thật............................................... 64 BÀI TậP CHƯƠNG 2 .............................................................................................................. 69 MÁY SUY DIễN 71 I. NGUYÊN LÝ HOạT ĐộNG CủA CÁC MÁY SUY DIễN......................................................... 71 I.1. Giai đoạn đánh giá EVALUATION ............................................................. 72 a. Bước thu hẹp (RESTRICTION)...................................................................72 b. Bước so khớp (PATTERN−MATCHING) ..................................................73 c. Giải quyết xung đột (CONFLICT-RESOLUTION) ....................................73 I.2. Giai đoạn thực hiện EXECUTION...............................................................73 II. MộT Số SƠ Đồ CƠ BảN Để XÂY DựNG MÁY SUY DIễN ......................................................74 II.1. Một ví dụ về cơ sở tri thức............................................................................74 II.2. Tìm luật nhờ suy diễn tiến với chế độ bắt buộc đơn điệu.............................76 a. Sơ đồ PREDIAGRAM−1 : lấy ngay kết luận của mỗi luật..........................76 b. Sơ đồ PREDIAGRAM : tạo sinh và tích luỹ sự kiện theo chiều rộng......77 II.3. Tìm luật nhờ suy diễn lùi với chế độ thăm dò đơn điệu ...............................79 a. Sơ đồ BACKDIAGRAM −1 : sản sinh các bài toán con theo chiều sâu .....79 b. Một vài biến dạng của BACKDIAGRAM−1...............................................81 c. 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 ............................................................................82 II.4. Tìm các luật nhờ liên kết hỗn hợp, với chế độ thăm dò không đơn điệu......83 a. Liên kết hỗn hợp...........................................................................................84 b. Lập hay «tạo sinh kế hoạch» ........................................................................84 c. Không đơn điệu ............................................................................................85 d. Khởi động ưu tiên theo độ sâu .....................................................................86 e. Giải thích sơ đồ MIXEDIAGRAM..............................................................88 f. Một vài biến tấu đơn giản khác của MIXEDIAGRAM ...............................89 II.5. Sơ đồ máy sử dụng biến ...............................................................................90 a. Hoạt động của BACKDIAGRAM−3 ...........................................................90 b. BACKDIAGRAM−3 : sơ đồ máy suy diễn kiểu Prolog..............................93 c. Giải thích sơ đồ máy BACKDIAGRAM−3 .................................................94 BÀI TậP CHƯƠNG 3 ..............................................................................................................95 Hệ CHUYÊN GIA MYCIN VÀ NGÔN NGữ OPS5 .............................................................97 I. Hệ CHUYÊN GIA MYCIN.............................................................................................97 I.1. Giới thiệu MYCIN ........................................................................................97 I.2. Biểu diễn tri thức trong MYCIN...................................................................99 a. Ngữ cảnh ......................................................................................................99 b. Các tham biến...............................................................................................99 c. Độ tin cậy (Certain Factor).........................................................................100 d. Biểu diễn luật .............................................................................................100 I.3. Kỹ thuật suy diễn của MYCIN....................................................................101 a. Thủ tục MONITOR....................................................................................101 b. Thủ tục FINDOUT.....................................................................................101 c. Hệ thống giao tiếp của MYCIN .................................................................101 II. Hệ SảN XUấT OPS5 ....................................................................................................103 II.1. Giới thiệu OPS5 .........................................................................................103 II.2. Các thành phần của OPS5 .........................................................................104 II.2.1. Các đặc trưng chính của ngôn ngữ.............................................................104 II.2.2. Kiểu dữ liệu OPS5......................................................................................105 II.2.3. Cơ sở luật (rb) ............................................................................................106 a. Thành phần bên trái luật : left-member......................................................107 b. Thành phần bên phải luật right-member ....................................................108 II.2.4. Cơ sở sự kiện (fb).......................................................................................109 II.2.5. Bộ nhớ làm việc .........................................................................................110 a. Cấu trúc bộ nhớ làm việc ...........................................................................110 b. Khởi tạo bộ nhớ làm việc ...........................................................................110 Mục lục 5 II.3. Làm việc với OPS5..................................................................................... 111 II.3.1. Hoạt động của máy suy diễn...................................................................... 111 II.3.2. Tập xung đột và cách giải quyết xung đột ................................................. 112 a. Chiến lược giải quyết xung đột LEX ......................................................... 112 b. Chiến lược giải quyết xung đột MEA........................................................ 113 c. Lựa chọn chiến lược giải quyết xung đột................................................... 113 II.3.3. Lệnh và phép toán của OPS5..................................................................... 114 a. Một số lệnh OPS5 ...................................................................................... 114 b. Các phép toán của OPS5............................................................................ 114 c. Yếu tố chắc chắn........................................................................................ 114 II.4. Đánh giá và phát triển của OPS5.............................................................. 115 II.4.1. Đánh giá..................................................................................................... 115 II.4.2. Phát triển của ngôn ngữ OPS5................................................................... 115 PHụ LụC A HƯớNG DẫN Sử DụNG OPS5................................................................ 117 PHUÛ LUÛC B MÄÜT SÄÚ HÃÛ CHUYÃN GIA ......................................................... 123 PHUÛ LUÛC C THAM KHAÍO ........................................................................................ 133 TÀI LIệU THAM KHảO....................................................................................................... 135 TÀI LIệU THAM KHảO ......................................................................................................... 150 CHƯƠNG 1 Mở đầu « When I examine myself and my methods of thought, I come to the conclusion that the gift of fantasy has meant more to me than my talent for absorbing positive knowledge ». Albert Einstein I. Giới thiệu hệ chuyên gia I.1. Hệ chuyên gia là gì ? Theo E. Feigenbaum : «Hệ chuyên gia (Expert System) là một chương trình máy tính thông minh sử dụng tri thức (knowledge) và các thủ tục suy luận (inference procedures) để giải những bài toán tương đối khó khăn đòi hỏi những chuyên gia mới giải được». Hệ chuyên gia là một hệ thống tin học có thể mô phỏng (emulates) năng lực quyết đoán (decision) và hành động (making abilily) của một chuyên gia (con người). Hệ chuyên gia là một trong những lĩnh vực ứng dụng của trí tuệ nhân tạo (Artificial Intelligence) như hình dưới đây. Artificial Intelligence Robotic Speech Vision Artificial Natural Neural Systems Language Expert System Understanding Hình 1.1. Một số lĩnh vực ứng dụng của trí tuệ nhân tạo Hệ chuyên gia sử dụng các tri thức của những chuyên gia để giải quyết các vấn đề (bài toán) khác nhau thuộc mọi lĩnh vực. Tri thức (knowledge) trong hệ chuyên gia phản ánh sự tinh thông được tích tụ từ sách vở, tạp chí, từ các chuyên gia hay các nhà bác học. Các thuật ngữ hệ chuyên gia, hệ thống dựa trên tri thức (knowledge−based system) hay hệ chuyên gia dựa trên tri thức (knowledge−based expert system) thường có cùng nghĩa. Một hệ chuyên gia gồm ba thành phần chính là cơ sở tri thức (knowledge base), máy suy diễn hay môtơ suy diễn (inference engine), và hệ thống giao tiếp với người sử dụng (user PGS. TS. Phan Huy Khánh biên soạn 7 interface). Cơ sở tri thức chứa các tri thức để từ đó, máy suy diễn tạo ra câu trả lời cho người sử dụng qua hệ thống giao tiếp. Người sử dụng (user) cung cấp sự kiện (facts) là những gì đã biết, đã có thật hay những thông tin có ích cho hệ chuyên gia, và nhận được những câu trả lời là những lời khuyên hay những gợi ý đúng đắn (expertise). Hoạt động của một hệ chuyên gia dựa trên tri thức được minh họa như sau : Người sử dụng (User) Hệ thống giao tiếp (User interface) Cơ sở tri thức (Knowledge Base) Máy suy diễn (Inference Engine) Hình 1.2. Hoạt động của hệ chuyên gia Mỗi hệ chuyên gia chỉ đặc trưng cho một lĩnh vực vấn đề (problem domain) nào đó, như y học, tài chính, khoa học hay công nghệ, v.v..., mà không phải cho bất cứ một lĩnh vực vấn đề nào. Tri thức chuyên gia để giải quyết một vấn đề đặc trưng được gọi là lĩnh vực tri thức (knowledge domain). Lĩnh vực vấn đề (Problem Domain) Lĩnh vực tri thức (Knowledge Domain) Hình 1.3. Quan hệ giữa lĩnh vực vấn đề và lĩnh vực tri thức Ví dụ : hệ chuyên gia về lĩnh vực y học để phát hiện các căn bệnh lây nhiễm sẽ có nhiều tri thức về một số triệu chứng lây bệnh, lĩnh vực tri thức y học bao gồm các căn bệnh, triệu chứng và chữa trị. Chú ý rằng lĩnh vực tri thức hoàn toàn nằm trong lĩnh vực vấn đề. Phần bên ngoài lĩnh vực tri thức nói lên rằng không phải là tri thức cho tất cả mọi vấn đề. Tùy theo yêu cầu người sử dụng mà có nhiều cách nhìn nhận khác nhau về một hệ chuyên gia. Loại người sử dụng Vấn đề đặt ra Người quản trị Tôi có thể dùng nó để làm gì ? Kỹ thuật viên Làm cách nào để tôi vận hành nó tốt nhất ? Mở đầu 9 Nhà nghiên cứu Làm sao để tôi có thể mở rộng nó ? Người sử dụng cuối Nó sẽ giúp tôi cái gì đây ? Nó có rắc rối và tốn kém không ? Nó có đáng tin cậy không ? I.2. Đặc trưng và ưu điểm của hệ chuyên gia Có bốn đặc trưng cơ bản của một hệ chuyên gia : • Hiệu quả cao (high performance). Khả năng trả lời với mức độ tinh thông bằng hoặc cao hơn so với chuyên gia (người) trong cùng lĩnh vực. • Thời gian trả lời thoả đáng (adequate response time). Thời gian trả lời hợp lý, bằng hoặc nhanh hơn so với chuyên gia (người) để đi đến cùng một quyết định. Hệ chuyên gia là một hệ thống thời gian thực (real time system). • Độ tin cậy cao (good reliability). Không thể xảy ra sự cố hoặc giảm sút độ tin cậy khi sử dụng. • Dễ hiểu (understandable). Hệ chuyên gia giải thích các bước suy luận một cách dễ hiểu và nhất quán, không giống như cách trả lời bí ẩn của các hộp đen (black box). Những ưu điểm của hệ chuyên gia : • Phổ cập (increased availability). Là sản phẩm chuyên gia, được phát triển không ngừng với hiệu quả sử dụng không thể phủ nhận. • Giảm giá thành (reduced cost). • Giảm rủi ro (reduced dangers). Giúp con người tránh được trong các môi trường rủi ro, nguy hiểm. • Tính thường trực (Permanance). Bất kể lúc nào cũng có thể khai thác sử dụng, trong khi con người có thể mệt mỏi, nghỉ ngơi hay vắng mặt. • Đa lĩnh vực (multiple expertise). chuyên gia về nhiều lĩnh vực khác nhau và được khai thác đồng thời bất kể thời gian sử dụng. • Độ tin cậy (increased relialility). Luôn đảm bảo độ tin cậy khi khai thác. • Khả năng giảng giải (explanation). Câu trả lời với mức độ tinh thông được giảng giải rõ ràng chi tiết, dễ hiểu. • Khả năng trả lời (fast reponse). Trả lời theo thời gian thực, khách quan. • Tính ổn định, suy luận có lý và đầy đủ mọi lúc mọi nơi (steady, une motional, and complete response at all times). • Trợ giúp thông minh như một người hướng dẫn (intelligent -tutor). • Có thể truy cập như là một cơ sở dữ liệu thông minh (intelligent database). I.3. Sự phát triển của công nghệ hệ chuyên gia Sau đây là một số sự kiện quan trọng trong lịch sử phát triển của công nghệ hệ chuyên gia (expert system technology). Nă m Các sự kiện 1943 D ịch vụ bưu điện ; mô hình Neuron của (Mc Culloch and Pitts Model) 1954 Thu ật toán Markov (Markov Algorithm) điều khiển thực thi các luật 1956 H ội thảo Dartmouth ; lý luận logic ; tìm kiếm nghiệm suy (heuristic search) ; thống nhất thuật ngữ trí tuệ nhân tạo (AI: Artificial Intelligence) 1957 Rosenblatt phát minh khả năng nhận thức ; Newell, Shaw và Simon đề xuất giải bài toán tổng quát (GPS: General Problem Solver) 1958 Mc Carthy đề xuất ngôn ngữ trí tuệ nhân tạo LISA (LISA AI language) 1962 Nguyên lý Rosenblatt’s về chức năng thần kinh trong nhận thức (Rosenblatt’s Principles of Neurodynamicdynamics on Perceptions) 1965 Ph ương pháp hợp giải Robinson. Ưng dụng logic mờ (fuzzy logic) trong suy luận về các đối tượng mờ (fuzzy object) của Zadeh. Xây dựng hệ chuyên gia đầu tiên về nha khoa DENDRAL (Feigenbaum , Buchanan , et.al) 1968 M ạng ngữ nghĩa (semantic nets), mô hình bộ nhớ kết hợp (associative memory model) của Quillian 1969 H ệ chuyên gia về Toán học MACSYMA (Martin and Moses) 1970 Ưng dụng ngôn ngữ PROLOG (Colmerauer, Roussell, et, al.) 1971 H ệ chuyên gia HEARSAY I về nhận dạng tiếng nói (speech recognition). Xây dựng các luật giải bài toán con người (Human Problem Solving popularizes rules (Newell and Simon) 1973 H ệ chuyên gia MYCIN về chẩn trị y học (Shortliffe, et,al.) 1975 Lý thuyết khung (frames), biểu diễn tri thức (knowledge representation) (Minsky) 1976 Toán nhân tạo (AM: Artificial Mathematician) (Lenat). Lý thuyết Dempster−Shafer về tính hiển nhiên của lập luận không chắc chắn (Dempster−Shafer theory of Evidence for reason under uncertainty). Ứng dụng hệ chuyên gia PROSPECTOR trong khai thác hầm mỏ (Duda, Har) 1977 S ử dụng ngôn ngữ chuyên gia OPS (OPS expert system shell) trong hệ chuyên gia XCON/R1 (Forgy) 1978 H ệ chuyên gia XCON/R1 (McDermott, DEC) để bảo trì hệ thống máy tính DEC (DEC computer systems) 1979 Thu ật toán mạng về so khớp nhanh (rete algorithm for fast pattern matching) của Forgy ; thương mại hoá các ứng dụng về trí tuệ nhân tạo 1980 Ký hiệu học (symbolics), xây dựng các máy LISP (LISP machines) từ LMI. 1982 H ệ chuyên gia về Toán học (SMP math expert system) ; mạng nơ-ron Hopfield (Hopfield Neural Net) ; Dự án xây dựng máy tính thông minh thế hệ 5 ở Nhật bản (Japanese Fifth Generation Project to develop intelligent computers) 1983 B ộ công cụ phục vụ hệ chuyên gia KEE (KEE expert system tool) (intelli Corp) 1985 B ộ công cụ phục vụ hệ chuyên gia CLIPS (CLIPS expert system tool (NASA) I.4. Các lĩnh vực ứng dụng của hệ chuyên gia Cho đến nay, hàng trăm hệ chuyên gia đã được xây dựng và đã được báo cáo thường xuyên trong các tạp chí, sách, báo và hội thảo khoa học. Ngoài ra còn các hệ chuyên gia được sử dụng trong các công ty, các tổ chức quân sự mà không được công bố vì lý do bảo mật. Bảng dưới đây liệt kê một số lĩnh vực ứng dụng diện rộng của các hệ chuyên gia. Lĩnh vực Ứng dụng diện rộng Cấu hình (Configuration) Tập hợp thích đáng những thành phần của một hệ thống theo cách riêng Chẩn đoán (Diagnosis) Lập luận dựa trên những chứng cứ quan sát được Truyền đạt Dạy học kiểu thông minh sao cho sinh viên có thể hỏi Mở đầu 11 (Instruction) vì sao (why?), như thế nào (how?) và cái gì nếu (what if?) giống như hỏi một người thầy giáo Giải thích (Interpretation) Giải thích những dữ liệu thu nhận được Kiểm tra (Monitoring) So sánh dữ liệu thu lượm được với dữ liệu chuyên môn để đánh giá hiệu quả Lập kế hoạch (Planning) Lập kế hoạch sản xuất theo yêu cầu Dự đoán (Prognosis) Dự đoán hậu quả từ một tình huống xảy ra Chữa trị (Remedy) Chỉ định cách thụ lý một vấn đề Điều khiển (Control) Điều khiển một quá trình, đòi hỏi diễn giải, chẩn đoán, kiểm tra, lập kế hoạch, dự đoán và chữa trị Sau đây là một số hệ chuyên gia (xem thêm phần phụ lục C cuối giáo trình) : Bảng 1 Ngành hoá học (Chemistry) CRYSALIS Interpret a protein’n 3-D structure DENDRAL Interpret molecular structure TQMSTUNE Remedy Triple Quadruple Mass Spectrometer (keep it tuned) CLONER Design new biological molecules MOLGEN Design gene - cloning experiments SECS Design complex organic molecules SPEX Plan molecular biology experiments Bảng 2 Ngành điện tử (Electronics) ACE Diagnosis telephone network faults IN -ATE Diagnosis oscilloscope faults NDS Diagnosis national communication net EURISKO Design 3-D micro-electronics PALLADIO Design and test new VLSI cicuits REDESIGN Redesign digital circuits to new CADHELP Instruct for computer aided design SOPHIE Instruct circuit fault diagnosis Bảng 3 Ngành địa chất (Geology) DIPMETER Interpret dipmeter logs LITHO Interpret oil well log data MUD Diagnosis / remedy drilling problems PROSPECTOR Interpret geologic data for minerals Bảng 4 Công nghệ (Engineering) REACTOR Diagnosis / remedy reactor accidents DELTA Diagnosis / remedy GE locomotives STEAMER Instruct operation - steam power-plant Bảng 5 Ngành y học (Medicine) PUFF Diagnosis lung disease VM Monitors intensive - care patients ABEL Diagnosis acid - base / electrolytes AI/COAG Dianosis blood disease AI/ RHEUM Diagnosis rheumatoid disease CADUCEUS Diagnosis internal medicine disease ANNA Monitor digitalis therapy BLUE BOX Diagnosis / remedy depression MYCIN Diagnosis / remedy bacterial infections ONCOCIN Remedy / manage chemotherapy patient ATTENDING Instruct in anesthetic manegement GUIDON Instruct in bacterial infections Bảng 6 Máy tính điện tử (Computer systems) PTRANS Prognosis for managing DEC computers BDS Diagnosis bad parts in switching net XCON Configune DEC computer systems XSEL Configure DEC computer sales order XSITE Configure customer site for DEC computers YES/MVS Monitor / control IBM MVS opeating system TIMM Diagnosis DEC computer II. Kiến trúc tổng quát của các hệ chuyên gia II.1. Những thành phần cơ bản của một hệ chuyên gia Một hệ chuyên gia kiểu mẫu gồm bảy thành phần cơ bản như sau : Cơ sở tri thức Các luật Khả năng giải thích Máy suy diễn Lịch công việc Bộ nhớ làm việc Khả năng thu nhận tri thức Giao diện người sử dụng Hình 1.4. Những thành phần cơ bản của một hệ chuyên gia • Cơ sở tri thức (knowledge base). Gồm các phần tử (hay đơn vị) tri thức, thông thường được gọi là luật (rule), được tổ chức như một cơ sở dữ liệu. • Máy duy diễn (inference engine). Công cụ (chương trình, hay bộ xử lý) tạo ra sự suy luận bằng cách quyết định xem những luật nào sẽ làm thỏa mãn các sự kiện, các đối tượng. , chọn ưu tiên các luật thỏa mãn, thực hiện các luật có tính ưu tiên cao nhất. • Lịch công việc (agenda). Danh sách các luật ưu tiên do máy suy diễn tạo ra thoả mãn các sự kiện, các đối tượng có mặt trong bộ nhớ làm việc. Mở đầu 13 • Bộ nhớ làm việc (working memory). Cơ sở dữ liệu toàn cục chứa các sự kiện phục vụ cho các luật. • Khả năng giải thích (explanation facility). Giải nghĩa cách lập luận của hệ thống cho người sử dụng. • Khả năng thu nhận tri thức (explanation facility). Cho phép người sử dụng bổ sung các tri thức vào hệ thống một cách tự động thay vì tiếp nhận tri thức bằng cách mã hoá tri thức một cách tường minh. Khả năng thu nhận tri thức là yếu tố mặc nhiên của nhiều hệ chuyên gia. • Giao diện người sử dụng (user interface). Là nơi người sử dụng và hệ chuyên gia trao đổi với nhau. Cơ sở tri thức còn được gọi là bộ nhớ sản xuất (production memeory) trong hệ chuyên gia. Trong một cơ sở tri thức, người ta thường phân biệt hai loại tri thức là tri thức phán đoán (assertion knowledge) và tri thức thực hành (operating knowledge). Các tri thức phán đoán mô tả các tình huống đã được thiết lập hoặc sẽ được thiết lập. Các tri thức thực hành thể hiện những hậu quả rút ra hay những thao tác cần phải hoàn thiện khi một tình huống đã được thiết lập hoặc sẽ được thiết lập trong lĩnh vực đang xét. Các tri thức thực hành thường được thể hiện bởi các biểu thức dễ hiểu và dễ triển khai thao tác đối với người sử dụng. Máy suy diễn Tri thức phán đoán Tri thức thực hành Cơ sở tri thức Hình 1.5. Quan hệ giữa máy suy diễn và cơ sở tri thức Từ việc phân biệt hai loại tri thức, người ta nói máy suy diễn là công cụ triển khai các cơ chế (hay kỹ thuật) tổng quát để tổ hợp các tri thức phán đoán và các tri thức thực hành. Hình trên đây mô tả quan hệ hữu cơ giữa máy suy diễn và cơ sở tri thức. II.2. Một số mô hình kiến trúc hệ chuyên gia Có nhiều mô hình kiến trúc hệ chuyên gia theo các tác giả khác nhau. Sau đây là một số mô hình. a. Mô hình J. L. Ermine Cơ sở tri thức Người sử dụng yêu cầu Hệ thống thu nhận tri thức Bộ nhớ làm việc Giao diện Dữ liệu vấn đề cần giải quyết Tri thức mới Hình 1.6. Kiến trúc hệ chuyên gia theo J. L. Ermine b. Mô hình C. Ernest Tri thức Chuyên gia Người sử dụng Cấu trúc máy suy diễn Dữ liệu • Lời giải • Giải thích • Theo dõi Cơ sở tri thức Máy suy diễn Hình 1.7. Kiến trúc hệ chuyên gia theo C. Ernest Mở đầu 15 c. Mô hình E. V. Popov Khả năng giải thích Chuyên gia Người sử dụng Giao diện người sử dụng Bộ nhớ làm việc Diễn dịch Sở hữu tri thức Cơ sở tri thức Hình 1.8. Kiến trúc hệ chuyên gia theo E. V. Popov II.3. Biểu diễn tri thức trong các hệ chuyên gia Tri thức của một hệ chuyên gia có thể được biểu diễn theo nhiều cách khác nhau. Thông thường người ta sử dụng các cách sau đây : • Biểu diễn tri thức bởi các luật sản xuất • Biểu diễn tri thức nhờ mệnh đề logic • Biểu diễn tri thức nhờ mạng ngữ nghĩa • Biểu diễn tri thức nhờ ngôn ngữ nhân tạo Ngoài ra, người ta còn sử dụng cách biểu diễn tri thức nhờ các sự kiện không chắc chắn, nhờ bộ ba : đối tượng, thuộc tính và giá trị (O-A-V: Object-Attribute-Value), nhờ khung (frame), v.v... Tuỳ theo từng hệ chuyên gia, người ta có thể sử dụng một cách hoặc đồng thời cả nhiều cách. II.3.1. Biểu diễn tri thức bởi các luật sản xuất Hiện nay, hầu hết các hệ chuyên gia đều là các hệ thống dựa trên luật, bới lý do như sau : • Bản chất đơn thể (modular nature). Có thể đóng gói tri thức và mở rộng hệ chuyên gia một cách dễ dàng. • Khả năng diễn giải dễ dàng (explanation facilities). Dễ dàng dùng luật để diễn giải vấn đề nhờ các tiền đề đặc tả chính xác các yếu tố vận dụng luật, từ đó rút ra được kết quả. • Tương tự quá trình nhận thức của con người. Dựa trên các công trình của Newell và Simon, các luật được xây dựng từ cách con người giải quyết vấn đề. Cách biểu diễn luật nhờ IF THEN đơn giản cho phép giải thích dễ dàng cấu trúc tri thức cần trích lọc. Luật là một kiểu sản xuất được nghiên cứu từ những năm 1940. Trong một hệ thống dựa trên luật, công cụ suy luận sẽ xác định những luật nào là tiên đề thỏa mãn các sự việc. Các luật sản xuất thường được viết dưới dạng IF THEN. Có hai dạng : IF < điều kiện > THEN < hành động > hoặc IF < điều kiện > THEN < kết luận > DO < hành động > Tuỳ theo hệ chuyên gia cụ thể mà mỗi luật có thể được đặt tên. Chẳng hạn mỗi luật có dạng Rule: tên. Sau phần tên là phần IF của luật. Phần giữa IF và THEN là phần trái luật (LHS: Left - Hand -Side), có nội dung được gọi theo nhiều tên khác nhau, như tiền đề (antecedent), điều kiện (conditional part), mẫu so khớp (pattern part), Phần sau THEN là kết luận hay hậu quả (consequent). Một số hệ chuyên gia có thêm phần hành động (action) được gọi là phần phải luật (RHS: Right - Hand -Side). Ví dụ : Rule: Đèn đỏ IF Đèn đỏ sáng THEN Dừng Rule: Đèn-xanh IF Đèn xanh sáng THEN Đi Trong ví dụ trên, Đèn đỏ sáng và Đèn xanh sáng là những điều kiện, hay những khuôn mẫu. Sau đây là một số ví dụ khác : Rule: Điều trị sốt IF Bệnh nhân sốt THEN cho uống thuốc Aspirin Hệ thống chẩn đoán xe máy (OPS5) IF Máy xe không nổ khi khởi động THEN Dự đoán: Xe bị panne sức nén. Pittong, bạc xéc-măng và lòng xy lanh sai tiêu chuẩn, dễ tạo thành những khe hở nhỏ làm cho pittong không còn kín nên hoà khí không được nén lên đầy đủ. Xử lý : nên điều chỉnh hoặc thay mới pittong, bạc xéc-măng và lòng xy lanh cho đúng tiêu chuẩn IF máy xe nổ không ổn định, OR máy xe nổ rồi lại tắt, AND bugi khô THEN Dự đoán : Xe đã bị nghẹt xăng. Xử lý : nên xúc rửa bình xăng và bộ khoá xăng của xe. MYCIN hệ thống chẩn đoán bệnh viêm màng não và hiện tượng có vi khuẩn bất thường trong máu (nhiễm trùng) IF Tại vị trí vết thương có máu, AND Chưa biết chắc chắn cơ quan bị tổn thương, AND Mở đầu 17 Chất nhuộm màu âm tính, AND Vi khuẩn có dạng hình que, AND Bệnh nhân bị sốt cao THEN Cơ quan có triệu chứng (0.4) nhiễm trùng II.3.2. Bộ sinh của hệ chuyên gia Bộ sinh của hệ chuyên gia (expert-system generator) là hợp của : − một máy suy diễn, − một ngôn ngữ thể hiện tri thức (bên ngoài) − và một tập hợp các cấu trúc và các quy ước thể hiện các tri thức (bên trong). Theo cách nào đó, các cấu trúc và các quy ước này xác định một cơ sở tri thức rỗng (hay rỗng bộ phận). Nhờ các tri thức chuyên môn để định nghĩa một hệ chuyên gia, người ta đã tạo ra bộ sinh để làm đầy cơ sở tri thức. Chẳng hạn, EMYCIN là tên của bộ sinh của hệ chuyên gia MYCIN và được tiếp tục áp dụng cho một số lĩnh vực. Hệ chuyên gia R1 được xây dựng từ bộ sinh OPS (là hệ thống luật được phát triển bởi Charles Forgy năm 1975 tại Carnegie-Mellon University). Sau đây là một số hậu duệ của EMYCIN và OPS : EMYCIN PUFF bệnh lý phổi HEADMED dược học tâm thần (psycho-pharmacology) SACON xây dựng cơ khí DART hỏng hóc máy tính SECOFOR khoan dầu mỏ TOM bệnh lý cà chua ... OPS R1/XCON cấu hình máy tính ACE bảo vệ đường dây điện thoại AIRPLAN cất cánh và hạ cánh máy bay AI-SPEAR theo dõi máy tính YES / MVS điều khiển máy tính ... Nhờ bộ sinh, mỗi hệ hệ chuyên gia có thể chứa từ hàng trăm đến hàng ngàn luật. Bảng dưới đây thống kê số luật của một số hệ chuyên gia : Hệ chuyên gia Lĩnh vực Năm xuất hiện Số luật MYCIN PROSPECTOR R1/XCON LITHO SPHINX TOM Y học Địa chất Tin học Địa chất Y học Nông học 1974 1979 1980 1982 1984 1984 500 1 600 > 7 000 500 400 200 Một trong những nét hấp dẫn của tiếp cận hệ chuyên gia là khả năng «học» (learn) của hệ thống nhằm thường xuyên sửa đổi và hoàn thiện cơ sở tri thức vốn có. Sơ đồ dưới đây cho biết sự tiến triển của hai hệ chuyên gia nổi tiếng của Mỹ là MYCIN và R1 : MYCIN 1974 : 200 luật hiện nay : 500 luật R1 1980 : 800 1981 : 1 000 1982 : 1 500 1983 : 2 000 1984 : > 3 000 1985 : > 7 000 II.3.3. «Soạn thảo kết hợp» các luật Nói chung, tuỳ theo hệ chuyên gia mà những quy ước để tạo ra luật cũng khác nhau. Sự giống nhau cơ bản giữa các hệ chuyên gia về mặt ngôn ngữ là cách soạn thảo kết hợp (associative writing) các luật. Ở đây, thuật ngữ soạn thảo kết hợp được chọn để gợi lên khái niệm về chế độ truy cập kết hợp (associative access) liên quan đến chế độ lưu trữ kết hợp (associative memory) là chế độ mà thông tin cần tìm kiếm được đọc không chỉ căn cứ vào địa chỉ đơn vị nhớ cụ thể mà còn căn cứ vào một phần nội dung của thông tin cần tìm kiếm chứa trong đó. Soạn thảo kết hợp các luật gồm những quy ước như sau : 1. Mỗi luật do chuyên gia cung cấp phải định nghĩa được các điều kiện khởi động (tác nhân) hay tiền đề của luật, nghĩa là các tình huống (được xác định bởi các quan hệ trên tập hợp dữ liệu đã cho) và hậu quả của luật, để luật này có thể áp dụng. Theo cách dùng thông thường, người ta đặt tên riêng cho luật để chọn áp dụng, hoặc cung cấp một nhóm các sự kiện (fact) tương thích với điều kiện khởi động của luật. 2. Trong luật, không bao giờ người ta chỉ định một luật khác bởi tên riêng. Ví dụ : luật R sau đây tuân thủ hai đặc trưng : IF bệnh nhân sốt AND tốc độ lắng huyết cầu trong máu tăng lên THEN bệnh nhân nhiễm bệnh virut Từ nội dung luật R, người ta có thể vận dụng như sau : − Khi xảy ra tình huống bệnh nhân bị sốt và tốc độ lắng huyết cầu trong máu tăng lên, thì “bệnh nhân sốt” và “tốc độ lắng huyết cầu trong máu tăng lên” là những điều kiện để khởi động luật. Hậu quả của luật là “bệnh nhân nhiễm bệnh virut”. Như vậy, việc áp dụng luật sẽ dẫn đến một sự kiện mới được thiết lập từ đây trở đi : “bệnh nhân nhiễm bệnh virut”. − Khi muốn tạo sự kiện “bệnh nhân bị nhiễm bệnh virut”, thì điều kiện khởi động luật là “bệnh nhân nhiễm bệnh virut”. Hậu quả của luật sẽ là “bệnh nhân sốt” và “tốc độ lắng huyết cầu trong máu tăng lên”. Từ đây, luật sẽ khởi động các sự kiện mới vừa được thiết lập “bệnh nhân sốt” và “tốc độ lắng huyết cầu trong máu tăng lên”. Cách biểu diễn các điều kiện khởi động trong luật phù hợp với cách tư duy tự nhiên của các chuyên gia. Do vậy, người ta dễ dàng thể hiện cũng như sửa đổi các tri thức tiếp nhận. Như vậy, người ta không nhất thiết phải đặt tên cho luật để có thể gọi đến khi cần, mà có thể khai thác thông tin từ các điều kiện khởi động của luật. Chẳng hạn từ luật R trên đây : − Nếu tìm được các luật có khả năng thiết lập sự kiện “bệnh nhân nhiễm bệnh virut”, người ta sẽ để ý đến phần then của chúng như là các điều kiện khởi động. Luật R là một trong các luật có điều kiện khởi động tương ứng với lời gọi “bệnh nhân nhiễm bệnh virut”. Mở đầu 19 − Nếu tìm được các luật có khả năng đưa ra sự kiện “bệnh nhân sốt”, chỉ cần để ý đến phần if của chúng như là các điều kiện khởi động. Luật R là một trong các luật có điều kiện khởi động tương ứng với lời gọi “bệnh nhân sốt”. Việc so sánh giữa điều kiện khởi động các luật và các sự kiện được xét tại một thời điểm đã cho (tuỳ theo trường hợp, các sự kiện giả sử đã được thiết lập hay sẽ thiết lập) cho phép lọc (filter) các luật để giữ lại một số luật nào đó. Phần điều kiện khởi động của luật thường được gọi là bộ lọc, hay mẫu so khớp của luật đó. Trong Tin học cổ điển, mỗi thủ tục (đóng vai trò là một đơn vị tri thức) thường được xác định và được gọi bởi tên của thủ tục. Lúc này, nếu muốn thêm vào hay lấy ra một thủ tục, người ta cần dự kiến các thay đổi trong toàn bộ thủ tục khác sử dụng đến thủ tục muốn thêm vào hay lấy ra này. Ngược lại, về nguyên tắc, việc soạn thảo kết hợp cho phép tạo ra một luật mà không cần để ý đến sự hiện diện của các luật khác. Với mỗi luật, dù là của ai, một khi được đưa vào trong cơ sở tri thức, thì chỉ cần để ý đến các biểu thức điều kiện để xác định nếu luật đó là áp dụng được và do vậy, có thể gọi tới nó hay không. Người ta cũng xem rằng các sự kiện được đưa vào như là hậu quả của một luật có thể giúp để gọi đến các luật khác nhờ các bộ lọc của chúng. Như vậy, phương pháp soạn thảo kết hợp cho phép bổ sung và loại bỏ dễ dàng các luật mà không cần xem xét hậu quả của việc bổ sung và loại bỏ đó. Phương pháp soạn thảo kết hợp có vị trí quan trọng trong các hệ thống dựa trên luật của các hệ chuyên gia. Đó là các hệ thống suy diễn định hướng bởi các bộ lọc (PDISPattern-Directed Inference Systems). II.3.4. Các phương pháp biểu diễn tri thức khác a. Biểu diễn tri thức nhờ mệnh đề logic Người ta sử dụng các ký hiệu để thể hiện tri thức và các phép toán lôgic tác động lên các ký hiệu để thể hiện suy luận lôgic. Kỹ thuật chủ yếu thường được sử dụng là lôgic vị từ (predicate logic) mà ta sẽ đề cập đến ở chương sau. Các ví dụ dưới đây minh hoạ cách thể hiện các phát biểu (cột bên trái) dưới dạng vị từ (cột bên phải) : Phát biểu Vị từ Tom là đàn ông MAN(tom) Tom là cha của Mary FATHER(tom, mary) Tất cả mọi người đều chết MAN(X) → MORTAL(X) với quy ước MAN(X) có nghĩa «X là một người» và MORTAL(X) có nghĩa «X chết». MAN và MORTAL được gọi là các vị từ đối với biến X. Các vị từ thường có chứa hằng, biến hay hàm. Người ta gọi các vị từ không chứa biến (có thể chứa hằng) là các mệnh đề (preposition). Mỗi vị từ có thể là một sự kiện (fact) hay một luật. Luật là vị từ gồm hai vế trái và phải được nối nhau bởi một dấu mũi tên (→). Các vị từ còn lại (không chứa mũi tên) được gọi là các sự kiện. Trong ví dụ trên đây, MAN và FATHER là các mệnh đề và là các sự kiện. Còn MAN(X) → MORTAL(X) là một luật. Ví dụ : Từ các tri thức sau : Marc có tóc vàng hoe, còn Jean có tóc màu nâu. Pierre là cha của Jean. Marc là cha của Pierre. Jean là cha của René. Marc là con của Georges. Giả sử X, Y và là Z những người nào đó, nếu Y là con của X thì X là cha của Y. Nếu X là cha của Z và Z là cha của Y thì X là ông của Y. ta có thể biểu diễn thành các sự kiện và các luật như sau : 1. BLOND (marc) 2. BROWN (jean) 3. FATHER (pierre, jean) 4. FATHER (marc, pierre) 5. FATHER (jean, rené) 6. SON (marc, georges) 7. FATHER (X, Y) ← SON (Y, X) 8. GRANDFATHER (X, Y) ← FATHER (X, Z), FATHER (Z, Y) Người ta gọi tập hợp các sự kiện và các luật là một cơ sở tri thức. b. Biểu diễn tri thức nhờ mạng ngữ nghĩa Trong phương pháp này, người ta sử dụng một đồ thị gồm các nút (node) và các cung (arc) nối các nút để biểu diễn tri thức. Nút dùng để thể hiện các đối tượng, thuộc tính của đối tượng và giá trị của thuộc tính. Còn cung dùng để thể hiện các quan hệ giữa các đối tượng. Các nút và các cung đều được gắn nhãn. Ví dụ để thể hiện tri thức “sẻ là một loài chim có cánh và biết bay”, người ta vẽ một đồ thị như sau : có là sẻ loài chim biết cánh bay Hình 1.9. Biểu diễn tri thức nhờ mạng ngữ nghĩa Bằng cách thêm vào đồ thị các nút mới và các cung mới, người ta có thể mở rộng một mạng ngữ nghĩa. Các nút mới được thêm thể hiện các đối tượng tương tự (với các nút đã có trong đồ thị), hoặc tổng quát hơn. Chẳng hạn để thể hiện “chim là một loài động vật đẻ trứng” và “cánh cụt là loài chim biết lặn“, người ta vẽ thêm như sau : Một trong những tính chất quan trọng của mạng ngữ nghĩa là tính thừa kế. Khi sử dụng mạng ngữ nghĩa để biểu diễn tri thức, người ta phải xây dựng các phép toán tương ứng. có cánh là là đẻ sẻ loài chim là biết động vật trứng bay cánh cụt biết lặn Hình 1.10. Mở rộng mạng ngữ nghĩa biểu diễn tri thức Mở đầu 21 c. Biểu diễn tri thức nhờ ngôn ngữ nhân tạo Nói chung, theo quan điểm của người sử dụng, ngôn ngữ tự nhiên sẽ là phương cách thuận tiện nhất để giao tiếp với một hệ chuyên gia, không những đối với người quản trị hệ thống (tư cách chuyên gia), mà còn đối với người sử dụng cuối. Hiện nay đã có những hệ chuyên gia có khả năng đối thoại trên ngôn ngữ tự nhiên (thông thường là tiếng Anh) nhưng chỉ hạn chế trong lĩnh vực ứng dụng chuyên môn của hệ chuyên gia Hình dưới đây thể hiện một đơn vị tri thức (luật) trong hệ chuyên gia MYCIN dùng để chẩn đoán các bệnh virut. Cột bên trái là một luật được viết bằng tiếng Anh, cột bên phải là mã hoá nhân tạo của luật đó. Nếu 1) Màu của cơ thể là gram dương và nếu 2) Hình thái của cơ thể là bị nhiễm trùng và nếu 3) Kiểu phát triển của cơ thể là khuẩn lạc thì tồn tại một khả năng (0.7) là cơ thể bị nhiễm khuẩn cầu chùm (($AND (SAME CNTXT GRAM GRAM+) (SAME CNTXT MORPH COCCI) (SAME CNTXT DEVEL COLONY) (CONCLUDE CNTXT IDENT STAPHYLOCOCCUS MEASURE 0.7)) Hình 1.11. Biểu diễn tri thức nhờ ngôn ngữ nhân tạo trong MYCIN II.4. Kỹ thuật suy luận trong các hệ chuyên gia Có nhiều phương pháp tổng quát để suy luận trong các chiến lược giải quyết vấn đề của hệ chuyên gia. Những phương pháp hay gặp là suy diễn tiến (foward chaining), suy diễn lùi (backward chaining) và phối hợp hai phương pháp này (mixed chaining). Những phương pháp khác là phân tích phương tiện (means-end analysis), rút gọn vấn đề (problem reduction), quay lui (backtracking), kiểm tra lập kế hoạch (plan-generate-test), lập kế hoạch phân cấp (hierachical planning)... Dưới đây là nền tảng của công nghệ hệ chuyên gia hiện đại (foundation of modern rele based expert system). Hệ chuyên gia dựa trên luật Luật Máy suy diễn Sự kiện Luật sản xuất Post So khớp hiệu quả Thuật toán mạng lưới Thuật toán Markov Hợp giải xung đột Suy diễn bên phải luật (RHS) Hình 1.12. Nền tảng của công nghệ hệ chuyên gia dựa trên luật hiện đại II.4.1. Phương pháp suy diễn tiến Suy diễn tiến ( forward charning) là lập luận từ các sự kiện, sự việc để rút ra các kết luận. Ví dụ : Nếu thấy trời mưa trước khi ra khỏi nhà (sự kiện) thì phải lấy áo mưa (kết luận). Trong phương pháp này, người sử dụng cung cấp các sự kiện cho hệ chuyên gia để hệ thống (máy suy diễn) tìm cách rút ra các kết luận có thể. Kết luận được xem là những thuộc tính có thể được gán giá trị. Trong số những kết luận này, có thể có những kết luận làm người sử dụng quan tâm, một số khác không nói lên điều gì, một số khác có thể vắng mặt. Các sự kiện thường có dạng : Atthibute = value Lần lượt các sự kiện trong cơ sở tri thức được chọn và hệ thống xem xét tất cả các luật mà các sự kiện này xuất hiện như là tiền đề. Theo nguyên tắc lập luận trên, hệ thống sẽ lấy ra những luật thoã mãn. Sau khi gán giá trị cho các thuộc tính thuộc kết luận tương ứng, người ta nói rằng các sự kiện đã được thoã mãn. Các thuộc tính được gán giá trị sẽ là một phần của kết quả chuyên gia. Sau khi mọi sự kiện đã được xem xét, kết quả được xuất ra cho người sử dụng. II.4.2. Phương pháp suy diễn lùi Phương pháp suy diễn lùi tiến hành các lập luận theo chiều ngược lại (đối với phương pháp suy diễn tiến). Từ một giả thuyết (như là một kết luận), hệ thống đưa ra một tình huống trả lời gồm các sự kiện là cơ sở của giả thuyết đã cho này. Ví dụ nếu ai đó vào nhà mà cầm áo mưa và áo quần bị ướt thì giả thuyết này là trời mưa. Để củng cố giả thuyết này, ta sẽ hỏi người đó xem có phải trời mưa không ? Nếu người đó trả lời có thì giả thuyết trời mưa đúng và trở thành một sự kiện. Nghĩa là trời mưa nên phải cầm áo mưa và áo quần bị ướt. Suy diễn lùi là cho phép nhận được giá trị của một thuộc tính. Đó là câu trả lời cho câu hỏi « giá trị của thuộc tính A là bao nhiêu ? » với A là một đích (goal). Để xác định giá trị của A, cần có các nguồn thông tin. Những nguồn này có thể là những câu hỏi hoặc có thể là những luật. Căn cứ vào các câu hỏi, hệ thống nhận được một cách trực tiếp từ người sử dụng những giá trị của thuộc tính liên quan. Căn cứ vào các luật, hệ thống suy diễn có thể tìm ra giá trị sẽ là kết luận của một trong số các kết luận có thể của thuộc tính liên quan, v.v... Ý tưởng của thuật toán suy diễn lùi như sau. Với mỗi thuộc tính đã cho, người ta định nghĩa nguồn của nó : • Nếu thuộc tính xuất hiện như là tiền đề của một luật (phần đầu của luật), thì nguồn sẽ thu gọn thành một câu hỏi. • Nếu thuộc tính xuất hiện như là hậu quả của một luật (phần cuối của luật), thì nguồn sẽ là các luật mà trong đó, thuộc tính là kết luận. • Nếu thuộc tính là trung gian, xuất hiện đồng thời như là tiền đề và như là kết luận, khi đó nguồn có thể là các luật, hoặc có thể là các câu hỏi mà chưa được nêu ra. Nếu mỗi lần với câu hỏi đã cho, người sử dụng trả lời hợp lệ, giá trị trả lời này sẽ được gán cho thuộc tính và xem như thành công. Nếu nguồn là các luật, hệ thống sẽ lấy lần lượt các luật mà thuộc tính đích xuất hiện như kết luận, để có thể tìm giá trị các thuộc tính thuộc tiền đề. Nếu các luật thoã mãn, thuộc tính kết luận sẽ được ghi nhận. Mở đầu 23 II.4.3. Các hệ thống sản xuất (production systems) a. Các hệ thống sản xuất Post Hệ thống sản xuất được Post sử dụng trong logic ký hiệu (symbolic logic) từ những năm 1943. Theo ông, rất nhiều hệ thống toán học và logic được viết dưới dạng các luật sản xuất (production rule). Các luật còn được gọi là quy tắc viết lại (rewrite rules) thường được dùng để định nghĩa văn phạm của một ngôn ngữ. Các ngôn ngữ lập trình thường được định nghĩa từ dạng Backus - Naur (BNF). Ý tưởng cơ bản của Post là xuất phát từ một xâu vào (input string), được gọi là tiền đề (antecedent), sản xuất ra một xâu kết quả mới khác (consequent). Mỗi sản xuất có dạng : < xâu tiền đề > → < xâu kết quả > Dấu mũi tên → chỉ ra rằng xâu vào bên trái được chuyển (transformation) thành xâu kết quả bên phải. Ví dụ : Để đi qua các ngã ba, ngã tư trong thành phố : Đèn đỏ sáng → Dừng Đèn xanh sáng → Đi Để chữa trị bệnh sốt : Bệnh nhân sốt → Cho uống thuốc Aspirin Các luật có thể có nhiều tiền đề : Bệnh nhân sốt AND Sốt trên 39 0C → Đi khám bác sĩ Chú ý phép AND không phải là một phần của xâu mà cho phép nối kết nhiều tiền đề lại với nhau. Một hệ thống sản xuất Post gồm một nhóm các luật sản xuất, chẳng hạn (chú ý các số thứ tự đặt trong dấu ngoặc chỉ dùng để trình bày) : (1) Car won’t start → Check battery (2) Car won’t start → Check gas (3) Check battery AND Battery bad → Replace battery (4) Check gas AND No gas → Fill gas tank Nếu đưa vào xâu Car won’t start, thì các luật (1) và (2) có thể được áp dụng để sinh ra các xâu Check battery và Check gas. Tuy nhiên, không tồn tại cơ chế để có thể áp dụng đồng thời cả hai cho xâu vào này. Chỉ có thể áp dụng được một luật trong hai, hoặc không. Nếu đưa vào xâu Battery bad và Check battery thì luật 3 có thể được áp dụng để sinh ra xâu Replace battery. Không đặt ra thứ tự các luật trong hệ thống. Sau khi đảo thứ tự, chẳng hạn (4) (2) (1) (3) thì hệ thống giữ nguyên giá trị : (4) Check gas AND No gas → Fill gas tank (2) Car won’t start → Check gas (1) Car won’t start → Check battery (3) Check battery AND Battery bad → Replace battery Mặc dù các sản xuất Post được sử dụng trong hệ chuyên gia nhưng chúng không thuận tiện cho việc viết các trình ứng dụng. Hạn chế chủ yếu của các sản xuất Post khi lập trình là không có các chiến lược điều khiển (control strategy) để định hướng sử dụng luật... Một hệ thống Post cho phép áp dụng luật cho một xâu vào theo cách tuỳ ý mà không chỉ ra cụ thể làm thế nào để luật được áp dụng. Chính sự lựa chọn luật một cách ngẫu nhiên như vậy làm thời gian tìm kiếm trở nên đáng kể trong các hệ thống có nhiều luật. b. Các thuật toán Markov Để cải tiến việc áp dụng các luật sản xuất, năm 1954, Markov đã đề xuất một cấu trúc điều khiển cho hệ thống sản xuất. Một thuật toán Markov (Markov algorithm) là một nhóm các sản xuất có thứ tự được áp dụng theo một thứ tự ưu tiên cho một xâu vào. Nếu luật có ưu tiên cao nhất không được áp dụng, thì qui tắc tiếp theo sẽ được áp dụng và cứ thế tiếp tục. Thuật toán Markov dừng nếu : (1) sản xuất cuối cùng không được áp dụng cho xâu, hoặc (2) nếu sản xuất đó là cuối một giai đoạn được áp dụng. Thuật toán Markov cũng có thể được áp dụng cho một xâu con (substring) của một xâu, bắt đầu từ bên trái : Ví dụ : Cho luật AB → HIJ Khi đó, áp dụng cho xâu vào GABKAB sẽ tạo ra xâu mới GHIJKAB. Từ đó, ta nhận được tiếp tục xâu mới GHIJKHIJ. Ký tự đặc biệt ε biều diễn xâu rỗng (null string), là xâu không có ký tự nào. Ví dụ : Luật A → ε Là xóa tất cả các xuất hiện của A trong một xâu. Các ký hiệu đặc biệt khác có vai trò như biến biểu diễn một ký tự bất kỳ được viết bởi các chữ cái thường a, b, c... Ví dụ , luật A x B → B x A Cho phép nghịch đảo các ký tự A và B. Các chữ cái Hy lạp α, β dùng để chỉ các dấu đặc biệt của xâu. Ở đây, các chữ cái Hy lạp dùng để phân biệt với bảng chữ cái đang sử dụng. Một ví dụ về thuật toán Markov là di chuyển chữ cái đầu tiên đến vị trí cuối cùng của một xâu vào. Những luật được ưu tiên áp dụng cao nhất là (1), thấp hơn là (2), rồi (3), v.v... Các luật được cho lần lượt theo độ ưu tiên giảm dần như sau : (1) xy → y x (2) → (3) → Cho xâu vào ABC, quá trình di chuyển được cho trong bảng sau : Luật Thành công (S) hoặc thất bại (F) Xâu kết quả 1 F ABC 2 F ABC 3 S ABC 1 S B AC 1 S BC A 1 F BC A 2 S BCA Chú ý rằng ký hiệu hoạt động như là một biến trung gian trong ngôn ngữ lập trình. Tuy nhiên, thay vì nhận một giá trị, biến đóng vai trò giữ vị trí đánh dấu quá trình thay đổi xâu vào. Một khi công việc kết thúc, bị loại bỏ bởi luật 2. Mở đầu 25 c. Thuật toán mạng lưới (rete algorithm) Chú ý rằng thuật toán Markov sử dụng chiến lược điều khiển tất định (definite control strategy) để áp dụng các luật có độ ưu tiên cao hơn trước tiên. Chừng nào mà luật có độ ưu tiên cao nhất không được áp dụng, thì thuật toán Markov sẽ tìm một luật khác có độ ưu tiên thấp hơn để áp dụng. Mặc dù thuật toán Markov có thể được sử dụng chủ yếu trong một hệ chuyên gia, nó vẫn không có hiệu quả trong những hệ thống có nhiều luật. Vấn đề về hiệu suất (efficient) trở nên quan trọng khi người ta cần tạo ra các hệ chuyên gia giải quyết các bài toán thực tiễn chứa từ hàng trăm đến hàng ngàn luật. Một hệ chuyên gia là không hiệu quả nếu người sử dụng phải chờ đợi rất nhiều thời gian để nhận được một câu trả lời từ hệ thống. Vấn đề là cần có một thuật toán biết được tất cả các luật và có thể chọn ra các luật cần thiết để áp dụng thay vì thử lần lượt các luật. Một giải pháp cho vấn đề này là thuật toán mạng lưới do Charles L. Forgy đề xuất tại trường Đại học Carnegie, Mellon, Hoa Kỳ vào năm 1979 trong luận văn tiến sĩ của ông về OPS (Official Production System). Thuật toán mạng lưới cho phép so khớp (pattern mattching) rất nhanh để nhận được câu trả lời tức thời bằng cách lưu giữ thông tin của các luật trong một mạng lưới (network). Thay vì so khớp lặp đi lặp lại các sự kiện mỗi lần áp dụng một luật trong mỗi chu trình nhận thức (recognize-act cycle), thuật toán mạng lưới chỉ nhìn những thay đối khi so khớp trong mỗi chu trình. III. Thiết kế hệ chuyên gia III.1. Thuật toán tổng quát Thuật toán tổng quát để thiết kế một hệ chuyên gia gồm các bước như sau : Begin Chọn bài toán thích hợp Phát biểu và đặc tả bài toán If Hệ chuyên gia giải quyết thoả mãn bài toán và có thể sử dụng Then While Bản mẫu chưa được phát triển hoàn thiện Do Begin Thiết kế bản mẫu Biểu diễn tri thức Tiếp nhận tri thức Phát triển hoàn thiện bản mẫu End Hợp thức hoá bản mẫu Triển khai cài đặt Hướng dẫn sử dụng Vận hành Bảo trì và phát triển Else Tìm các tiếp cận khác thích hợp hơn EnIf Kết thúc End Hình 1.13. Thiết kế một hệ chuyên gia Để thiết kế một hệ chuyên gia, trước tiên cần có sự lựa chọn một bài toán thích hợp (selecting the appropriate problem). Tương tự các dự án phần mềm, để triển khai thiết kế một hệ chuyên gia, cần phải có các yếu tố về nhân lực, tài nguyên và thời gian. Những yếu tố này ảnh hưởng đến giá thành của một hệ chuyên gia. Người ta thường đặt ra các câu hỏi sau đây : Tại sao cần xây dựng (building) một hệ chuyên gia ? Câu hỏi này thường xuyên được đặt ra cho bất kỳ dự án nào. Có thể trả lời ngay là do những đặc trưng và ưu điểm của các hệ chuyên gia. Trước khi bắt đầu, cần xác định rõ đâu là bài toán, ai là chuyên gia, và ai là người sử dụng. Trả tiền (pay-off) là gì ? Khi quyết định xây dựng một hệ chuyên gia (câu hỏi 1) cần một sự đầu tư về nhân lực, tài nguyên, thời gian và tiền bạc. Do vậy người sử dụng hệ chuyên gia phải trả tiền, tuỳ theo tính hiệu quả hay ưu điểm của hệ chuyên gia sử dụng. Tuy nhiên, nếu không có ai sử dụng hệ chuyên gia, thì sẽ không có ai trả tiền để bù lại chi phí và có lãi. Do hệ chuyên gia là một công nghệ mới, câu hỏi này khó trả lời hơn và có nhiều rủi ro hơn so với lập trình thông thường. Sử dụng những công cụ (tools) nào để xây dựng một hệ chuyên gia ? Hiện nay có rất nhiều công cụ để xây dựng các hệ chuyên gia. Mỗi công cụ đều có những ưu điểm và nhược điểm nhất định. Những công cụ phổ biến là CLIPS và OPS5, ngoài ra có ART, ART-IM, Eclipse, Cognate... Chi phí (cost) để xây dựng một hệ chuyên gia là bao nhiêu ? Chi phí hay giá thành để xây dựng một hệ chuyên gia phụ thuộc vào nguồn nhân lực, tài nguyên và thời gian hoàn thiện nó. Bên cạnh chi phí về phần cứng, phần mềm, còn chi phí về đào tạo (training). Ví dụ ở Mỹ, chi phí để đào tạo sử dụng thành thạo một hệ chuyên gia có thể lên tới 2.500USD/tuần lễ/người. Sau bước lựa chọn, phát biểu và đặc tả bài toán là các bước phát triển hệ chuyên gia. Sau đây ta sẽ xem xét các hệ chuyên gia được phát triển như thế nào. III.2. Các bước phát triển hệ chuyên gia Hệ chuyên gia được phát triển như thế nào ? Trong phạm vi rộng (large extent), việc phát triển một hệ chuyên gia phụ thuộc vào nguồn tài nguyên cung cấp. Tuy nhiên, giống như các dự án khác, việc phát triển còn phụ thuộc vào cách tổ chức quản lý quá trình phát triển như thế nào. a. Quản lý dự án (Project Management) Quản lý dự án, chủ đề tiếp cận hệ chuyên gia, bao gồm các công đoạn như sau : Quản lý hoạt động (Activity Management), gồm : • Lập kế hoạch - định nghĩa các hoạt động (define activities) (planning) - xác định hoạt động ưu tiên (specify priority of activities) -nhu cầu tài nguyên (resource requirement) -ghi nhớ các sự kiện (milestones) -xác định thời gian (duration) -phân công trách nhiệm (responsabilities) • Lập biểu công việc - ấn định điểm bắt đầu và điểm kết thúc dự án (scheduling) - giải quyết xung đột khi gặp các việc cùng mức ưu tiên Mở đầu 27 • Phân bổ thời gian - kiểm tra thực hiện dự án (chronicling) (monitor project performance) • Phân tích - phân tích các hoạt động về lập kế hoạch, (analysis) lập biểu công việc và phân bổ thời gian hoạt động Quản lý cấu hình sản phẩm (Product Configuration Management) : • Quản lý sản phẩm - quản lý các phiên bản khác nhau của các sản phẩm (product management) • Quản lý thay đổi - quản lý các giải pháp sửa đổi sản phẩm và ước lượng (change ảnh hưởng của thay đổi sản phẩm management) - phân công người sửa đổi hệ thống - cài đặt phiên bản mới Quản lý tài nguyên (Resource Management) : • Dự báo nhu cầu tài nguyên (forecast needs for resource) • Thu nhận tài nguyên (acquire resources) • Phân công trách nhiệm để sử dụng tối ưu nguồn tài nguyên (assign responsabilities for optimium use of resources) • Phân bổ tài nguyên để giảm thiểu tắc nghẽn (provide critical resources to minimize bottle-necks) Hình dưới đây mô tả quá trình quản lý dự án phát triển một hệ chuyên gia. Quản lý dự án (project management) Quản lý hoạt động Quản lý cấu hình sản phẩm Quản lý tài nguyên Lập kế hoạch Lên lịch công tác Ghi chép sự kiện Phân tích Quản lý sản phẩm Quản lý thay đổi Giảm thiểu trì trệ tài nguyên Tiếp nhận tài nguyên Phân công trách nhiệm tài nguyên Dự báo tài nguyên cần thiết Hình 1.14. Quản lý dự án phát triển một hệ chuyên gia b. Tiếp nhận tri thức Các bước tiếp nhận tri thức cho một hệ hệ chuyên gia như sau : Đầu tiên, công nghệ tri thức thu nhận tri thức nhờ đối thoại trực tiếp với tri thức con người (chuyên gia). Sau đó, tri thức được biểu diễn (theo một cách nào đó) tường minh trong cơ sở tri thức. Các chuyên gia đánh giá hệ chuyên gia, trao đổi qua lại với công nghệ tri thức cho đến khi hệ chuyên gia hoàn toàn thỏa mãn yêu cầu. Tri thức chuyên gia (human expert) Đối thoại (dialog) Công nghệ tri thức (knowledge engineer) Tri thức tường minh (explicit knowledge) Cơ sở tri thức hệ chuyên gia (knowledge base of expert system) Hình 1.15. Tiếp nhận tri thức trong một hệ chuyên gia c. Vấn đề phân phối (The Delivery Problem) Hệ thống được phân phối như thế nào ? Vấn đề phân phối một hệ thống phụ thuộc chủ yếu vào số lượng các hệ chuyên gia sẽ được phát triển. Tốt nhất là hệ chuyên gia có thể chạy trên các thiết bị phần cứng chuẩn. Tuy nhiên, một số hệ chuyên gia đòi hỏi phải có bộ xử lý LISP, từ đó làm tăng giá thành sản phẩm. Nói chung, một hệ chuyên gia cần phải được tích hợp (integrated) với những chương trình đã có sẵn để có thể dùng lời gọi thủ tục từ một ngôn ngữ lập trình thông thường và hệ thống có thể hỗ trợ quá trình này. d. Bảo trì và phát triển Hệ thống được bảo trì (maintenance) và tiến triển (evolve) như thế nào ? Các hệ chuyên gia đòi hỏi các hoạt động bảo trì và phát triển không hạn chế (open-ended) so với các chương trình thông thường. Bởi vì các hệ chuyên gia không dựa trên các thuật toán, mà thành tích (performance) của chúng phụ thuộc vào tri thức. Vấn đề là phải thường xuyên bổ sung tiếp nhận các tri thức mới và thay đổi các tri thức cũ để đổi mới hệ thống (system improves). Trong một sản phảm có chất lượng thương mại (commercial quality product), cần phải thu thập một cách có hệ thống và có hiệu quả các báo cáo sai sót hệ thống do người sử dụng phát hiện. Nếu việc thu thập và khắc phục lỗi không được ưu tiên trong quá trình nghiên cứu thì phải được ưu tiên trong hệ thống chất lượng thương mại. Việc bảo trì chỉ được thực hiện tốt khi thu thập đầy đủ các báo cáo sai sót. Hình 1.16. trình bày các giai đoạn cơ bản để phát triển một hệ chuyên gia. Mở đầu 29 Nghiên cứu khả thi Thuyết trình hay báo cáo kết quả so sánh chỉ ra tính (feasibility study) khả thi của dự án Hệ chuyên gia thể hiện ý tưởng, khởi động sự nhiệt Phác thảo nhanh bản mẫu tình và đặt nền móng quản lý ở mức cao (rapid prototype) Kiểm thử hệ thống cho bài toán thực tế nhờ công nghệ tri thức và chuyên gia Làm mịn hệ thống (Refined system : a-test) Lựa chọn người sử dụng để kiểm thử hệ thống, không nhờ công nghệ tri thức và chuyên gia Kiểm thử (β -test) Hợp thức hóa và thử nghiệm, viết tài liệu hướng dẫn sử (field testable) dụng, đào tạo, hỗ trợ khách hàng qua đện thoại, email kịp thời Chất lượng sản phẩm Tìm lỗi sai (fix bugs) và tìm những khả năng mở rộng (commercial quality) (enhance capabilities) Bảo trì và phát triển (maintenance&evolution) Hình 1.16. Các giai đoạn phát triển một hệ chuyên gia Sự phát triển một hệ hệ chuyên gia cũng tác động nhiều trong một hệ thống chất lượng thương mại. Người ta luôn mong muốn nhận được những thành công một khi hệ chuyên gia được phân phối đến người dùng. III.3. Sai sót trong quá trình phát triển hệ chuyên gia Các sai sót chủ yếu trong quá trình phát triển hệ chuyên gia được phân ra thành nhiều giai đoạn (hình 1.17.). Sai sót trong tri thức chuyên gia. Chuyên gia là nguồn tri thức của một hệ chuyên gia. Nếu tri thức chuyên gia không đúng và không đầy đủ, hậu quả sai sót sẽ ảnh hưởng suốt quá trình phát triển hệ thống. Ví dụ : để hạn chế những sai sót có thể, NASA đã sử dụng bảng kỹ thuật bay (Flight Technique Panels) trong các chuyến bay vũ trụ. Các bảng này gồm những người sử dụng hệ thống, các chuyên gia lĩnh vực độc lập, những người phát triển hệ thống, những người quản trị nhằm bảo đảm tính đầy đủ và bao trùm hết mọi lĩnh vực phát triển. Sai sót ngữ nghĩa. Xảy ra do hiểu sai tri thức đưa vào hệ chuyên gia. Ví dụ, giả sử một chuyên gia nói : « You can extinguish a fire with water » và công nghệ tri thức lại hiểu câu này là « All fires can be extinguished by water ». Sai sót cú pháp. Do biểu diễn sai dạng các luật và các sự kiện, hoặc do sai sót ngữ nghĩa, hoặc sai sót trong tri thức chuyên gia ở các bước trước. Sai sót máy suy diễn. Là một chương trình nên máy suy diễn có thể gặp lỗi khi thực hiện và có thể xác định được nguyên nhân. Tuy nhiên, việc xác định lỗi trong một số hệ chuyên gia vẫn gặp khó khăn do công cụ phần mềm sử dụng. Ngoài ra, người ta cũng gặp phải sai sót khi suy diễn và những sai sót không biết được. • Sai sót trong tri thức của chuyên gia : thiếu sót Chuyên gia nhầm lẫn... (expert) • Sai sót về mặt ngữ nghĩa giữa công nghệ tri thức và chuyên gia. Công nghệ tri thức • Suy luận (elicitation) không đầy đủ về tri thức từ (knowledge engineer) chuyên gia • Sai sót về mặt cú pháp • Sai sót do thiếu sót và nhầm lẫn tri thức trong các Cơ sở tri thức luật và các sự kiện, tính không chắc chắn (knowledge base) • Lỗi của máy suy diễn, lỗi phần mềm công cụ hệ chuyên gia Máy suy diễn • Lỗi suy diễn do xác định sai độ ưu tiên của các luật, (inference engine) tương tác giữa các luật, sai trong cơ sở tri thức, suy luận không nhất quán... Phép suy diễn (inference chain) Hình 1.17. Sai sót và nguyên nhân sai sót trong các hệ chuyên gia Mở đầu 31 Bài tập chương 1 1. Đọc kỹ giáo trình và tài liệu tham khảo để hiểu cac khái niệm đã trình bày. 2. Tự cho một số ví dụ về các phương pháp biểu diễn tri thức. Nhận xét. CHƯƠNG 2 Biểu diễn tri thức nhờ logic vị từ bậc một “ The most important thing I have learned over the years is the difference between taking one's work seriously and taking one's self seriously. The first is imperative, and the second disastrous ”. Margaret Fontey I. Ngôn ngữ vị từ bậc một I.1. Các khái niệm I.1.1. Cú pháp của ngôn ngữ vị từ bậc một Trong ngôn ngữ vị từ bậc một (first−order predicate language), bằng cách sử dụng một bảng ký hiệu đặc biệt, người ta đưa vào các khái niệm hạng (term), nguyên tử (atom), trực kiện (literal) và công thức chỉnh (well−formed formula) để xây dựng các biểu thức đúng (correct expressions). 1. Bảng ký hiệu Bảng ký hiệu để xây dựng các biểu thức đúng gồm : • Các dấu phân cách (separator signs) là dấu phẩy ( , ), dấu mở ngoặc ( ( ) và dấu đóng ngoặc ( ) ). • Các hằng (constant) có dạng chuỗi sử dụng các chữ cái in thường a..z. Ví dụ : a, block. • Các biến (variable) có dạng chuỗi sử dụng các chữ cái in hoa A..Z. Ví dụ : X, NAME. • Các vị từ (predicate) được viết tương tự các biến, là các chuỗi sử dụng các chữ cái in hoa A..Z. Ví dụ : ISRAINING, ON(table), P(X, blue), BETWEEN(X, Y, Z). Khi cần thao tác trên một vị từ nào đó, cần phải ghi rõ bậc (arite) hay số các đối (argument) của vị từ đó. Bậc là một số nguyên dương. Ví dụ, trong một ứng dụng nào đó, bậc của các vị tự ISRAINING, ON, P và BETWEEN lần lượt là 0, 1, 2 và 3. Khi bậc có giá trị cố định là 0, vị từ còn được gọi là mệnh đề (proposition). Chẳng hạn ISRAINING, EMPTY là các mệnh đề. • Các hàm (function), có cách viết tương tự các hằng, sử dụng các chữ in thường a..z. Mỗi hàm cũng có bậc (hay số lượng các đối) cố định, là một số nguyên dương. Ví dụ f(X), weight(elephan), successor(M, N) là các hàm có bậc lần lượt là 1, 1, và 2. Người ta quy ước rằng các hằng là những hàm bậc không (nil). Ví dụ a, elephan, block là các hằng. • Các phép nối logic (logical connector) là ←, ∧, ∨, → và ↔ tương ứng với các phép phủ định, và, hoặc, kéo theo và kéo theo lẫn nhau. PGS. TS. Phan Huy Khánh biên soạn 33 • Dấu ∃ là lượng tử tồn tại (existential quantifier) và ∀ là lượng tử toàn thể (universal quantifier). 2. Hạng (term) Hạng được tạo thành từ hai luật sau : • Các hằng và các biến là các hạng. • Nếu f là một hàm có bậc n ≥ 1 và nếu t1,..., tn đều là các hạng, thì hàm f (t1,..., tn) cũng là một hạng. Ví dụ : Các hàm successor(X, Y) hay weight(b) hay successor(b, wight(Z)) đều là các hạng, nhưng P(X, blue) không phải là hạng vì P là một vị từ hay weight (P(b)) cũng không phải là hạng vì P(b) không phải là một hạng (không thể làm đối cho một hàm). 3. Nguyên tử (atom) Nguyên tử được tạo thành từ hai luật sau : • Các mệnh đề (vị từ bậc 0) là các nguyên tử. • Nếu P là một vị từ bậc n (n ≥ 1) và nếu t1,..., tn đều là các hạng, thì P(t1,..., tn) cũng là một nguyên tử. Ví dụ : P(X, blue), EMPTY, BETWEEN(table, X, sill(window)) là các nguyên tử. Còn successor (X, Y), sill (window) ây thì không phải nguyên tử. 4. Các công thức chỉnh Các công thức chỉnh (viết tắt CTC) được tạo thành từ ba luật sau : • Các nguyên tử là các CTC. • Nếu G và H biểu diễn các CTC, thì (←G), (G ∧ H), (G ∨ H), (G → H) và (G ↔ H) cũng là các CTC do được tạo thành từ các phép nối lôgich giữa G và H. • Nếu G là một CTC và X là một biến, thì (∃X)G và (∀X)G cũng là các CTC. (∃X)G được đọc là tồn tại một biến X sao cho G được thoả mãn. (∀X)G được đọc là với mọi biến X thì G đều được thoả mãn. Ví dụ : Các công thức sau đây là chỉnh : (∃X) (∀Y) ((P(X, Y) Q(X, Y) → R(X)) ((←(P(a) → P(b))) → ←P(b)) còn (←(f(a)) : phủ định của một hàm, và f (P(a)) : hàm có đối là một vị tư, đều không phải là CTC. Chú ý : • Một CTC được gọi là một trực kiện (literal) hay một trị đúng nếu nó là một nguyên tử hay có dạng (←G), với G là một nguyên tử. • Trong một CTC, trước hoặc sau các ký tự nối, ký tự phân cách, các hằng, các biến, các hàm, các vị từ, người ta có thể đặt tùy ý các dấu cách (space hay blank). Biểu diễn tri thức nhờ logic vị từ bậc một 35 Từ nay về sau ta quy ước rằng, trong một công thức, nếu có một biến được lượng tử hóa, tức là biến xuất hiện ngay theo sau ký hiệu ∃ hay ∀ thì từ đó trở đi, tất cả các vị trí đứng sau của cùng biến này cũng được lượng tử hóa. Một CTC có thể chứa các biến không được lượng tử hóa, chúng được gọi là những biến tự do (free variable). Ví dụ : P(X) và (∃Y) Q(X, Y) là các CTC có chứa biến tự do X. • Logic vị từ được gọi là «bậc một» (first−order) vì trong định nghĩa các CTC không chứa các lượng tử cho vị từ hay cho hàm. Ví dụ : (∀P)P(a) và (∀f) (∀f) (∀X) P(f (X), b) không phải là những CTC logic vị từ bậc một, mà có bậc cao hơn (higher-order). 5. Biểu diễn và sử dụng tri thức (knowledge) Thực tế, các CTC dùng để diễn tả các nghĩa. Ví dụ CTC dưới đây : (∀X) (MAN(X) → M (X)) thể hiện câu «tất cả mọi người đều chết» bằng cách quy ước rằng MAN(X) có nghĩa «X là một người» và M (X) có nghĩa «X chết». Không phải luôn luôn dễ dàng dùng một CTC để biểu diễn một tri thức diễn tả theo ngôn ngữ tự nhiên (natural language). Chẳng hạn, để diễn tả rằng «nếu hai vật bằng nhau thì chúng có cùng tính chất», người ta có thể viết : (∀P) (∀X) (∀Y) (EQUAL(X, Y) → (P(X) ↔ P(Y))) Nhưng biểu thức trên không phải là logic vị từ bậc một vì có lượng tử ∀ áp dụng cho một ký tự vị từ là P. I.1.2. Các luật suy diễn (inference rule) Một luật suy diễn là cách biểu diễn sao cho từ một hoặc nhiều CTC, có thể suy dẫn (derive) thành các CTC khác. Chẳng hạn các luật suy diễn sau đây : • Luật suy diễn modus ponens : Từ hai CTC lần lượt là G và (G → H), có thể suy dẫn ra CTC H (ở đây vẫn quy ước rằng các tên như G, H phải được thay thế bởi các CTC mà chúng biểu diễn). • Luật suy diễn modus tollens : Từ các CTC là (←H) và (G → H), ta suy dẫn ra được (←G). Người ta viết quy ước hai luật suy diễn trên như sau : G → H G ←H G → H ∴H ∴←G modus ponens modus tollens • Luật suy diễn chuyên dụng (universal specialization), nếu từ một CTC có dạng : (∀X) G(X) và từ một hằng bất kỳ, chẳng hạn «a», có thể suy dẫn thành CTC : G(a) nghĩa là mọi vị trí X trong G được thay thế bởi a. Cho trước một tập hợp cố định các luật suy diễn, người ta có thể xem xét họ các bài toán sau : Từ một tập hợp các CTC đã chọn, bằng cách áp dụng một số hữu hạn lần nào đó các luật suy diễn, có thể nhận được một CTC đã cho trước hay không ? Các CTC được chọn lúc đầu được gọi là các tiên đề (axiom). Các CTC nhận được bằng cách áp dụng các luật suy diễn được gọi là các định lý (theorem). Một dãy các áp dụng các luật suy diễn từ các tiên đề dẫn đến định lý là một phép chứng minh (proving) của định lý. Một số kỹ thuật hợp giải vấn đề (problem resolution) thuộc lĩnh vực «Trí tuệ nhân tạo» như tìm kiếm trong không gian các trạng thái, có thể được xem như việc tìm kiếm một chứng minh cho một định lý đã cho. Theo nghĩa không gian các trạng thái, tập hợp các tiên đề có thể xem là một trạng thái đầu, các luật suy diễn đóng vai trò là các phép chuyển trạng thái, các trạng thái đích sẽ là tập hợp các CTC trong đó có chứa định lý cần chứng minh. I.1.3. Ngữ nghĩa của ngôn ngữ vị từ bậc một Sau đây, ta sẽ nghiên cứu cách sử dụng các CTC để biểu diễn và suy luận trên các giá trị chân (truth value) của các tri thức đã có để tìm được giá trị chân của các tri thức khác. a. Diễn giải (Interpretation) Một diễn giải của một CTC G, ký hiệu I, được xác định từ năm bước sau đây : • Chọn một miền diễn giải (interpretation domaim) ký hiệu là D với D ≠ ∅, nghĩa là một tập hợp khác rỗng các phần tử. • Gán (assignation) cho mỗi hằng của G một phần tử của D. • Gán cho mỗi mệnh đề (hay vị từ có bậc 0) một phần tử của tập hợp giá trị {true, false}. Để đơn giản ta ký hiệu F là trị false và T là trị true. • Gán cho mỗi vị từ bậc n (n ≥ 1) một ánh xạ từ Dn lên { T, F } : P( X1,... Xn ) : Dn → { T, F } • Gán cho mỗi hàm bậc n (n ≥ 1) một ánh xạ từ Dn lên D : P( X1,... Xn ) : Dn → D. Người ta nói rằng đã có một diễn giải I từ G lên D : I G ⎯→ D, D ≠ ∅ Ví dụ : Cho các miền diễn giải D1, D2, D3 và các CTC G1 : (∀X) P(X) G2 : (∀X) (∃Y) Q(X, Y) G3 : (∀X) (R(X) → T (f (X), a)) Ta xây dựng các diễn giải Ii của Gi lên Di, i = 1.. 3, như sau : P(1) P(2) I1 : D1 = {1, 2} F T Q(1, 1) Q(1, 3) Q(3, 1) Q(3, 3) I2 : D2 = {1, 3} F T F F a f(4) f(5) I3 : D3 = {4, 5} 4 5 4 R(4) R(5) T(4, 4) T(4, 5) T(5, 4) T(5, 5) T F T F T T Chú ý : Đôi khi, người ta nói một diễn giải là không đầy đủ nếu trong đó, các phép gán cần thiết chỉ được đặc tả từng phần. Biểu diễn tri thức nhờ logic vị từ bậc một 37 b. Giá trị một công thức theo diễn giải Cho một diễn giải I của một miền D cho một công thức G. • Nếu G là một mệnh đề, khi đó, giá trị gán cho G do định nghĩa của I được gọi là giá trị của G theo I. • Nếu G là một trực kiện mà không phải là một mệnh đề, khi đó, với mỗi phép lựa chọn C các giá trị trong D cho các biến của G (nếu tồn tại), ta nhận được một giá trị true hay false theo cách định nghĩa I. Giá trị này được gọi là giá trị của G theo I đối với lựa chọn C các giá trị của các biến. Chẳng hạn, trong công thức G3 ở trên được diễn giải theo I3, nguyên tử T(f(X), a) nhận giá trị T nếu X được gán phần tử 4 của D3, và cũng nhận giá trị T nếu X nhận một giá trị khác (giả sử 5) của D3. • Nếu G có dạng (∀X)G’, ta định nghĩa giá trị của G theo I là T (true) nếu giá trị của G’ theo I cho mọi giá trị của biến X (trong D) là T, nếu không là F (false). Chẳng hạn, giá trị của G1 được diễn giải theo I là F. • Nếu G có dạng (∃X)G’, ta định nghĩa giá trị của G theo I là T (true) nếu giá trị của G’ theo I đối với ít nhất một giá trị của biến X (trong D) là T, nếu không là F (false). Chẳng hạn, giá trị của Q(X, Y) được diễn giải theo I2 là T khi gán 1 cho X và 3 cho Y. Từ đó suy ra rằng giá trị của (∃Y)Q(X, Y) theo I2, khi X nhận giá trị 1, là T. Ngược lại, giá trị của G2 theo I2 là F. • Nếu G có dạng (←G’), người ta định nghĩa giá trị của ← G’ theo I, khi giá trị này của G’ theo I được định nghĩa, căn cứ theo bảng sau : Giá trị của G’ theo I Giá trị của (←G’) theo I (giả sử G) T F F T • Nếu G có dạng (G’ ∨ G’’), hoặc (G’ ∧ G’’), hoặc (G’ → G’’), hoặc (G’ ↔ G’’), người ta định nghĩa giá trị của G theo I, khi các giá trị của G’ và G’’ theo I được định nghĩa, căn cứ theo các bảng chân lý (truth table) tương ứng sau : G’ G’’ (G’ ∨ G’’) F F F F T T T F T T T T G’ G’’ (G’ ∧ G’’) F F F F T F T F F T T T G’ G’’ (G’ → G’’) F F T F T T T F F T T T Chẳng hạn, giá trị của G3 theo I3 là T. G’ G’’ (G’ ↔ G’’) F F T F T F T F F T T T Khi một công thức G là T theo một diễn giải I, người ta nói rằng diễn giải I là một mô hình của G. Chú ý rằng giá trị của một công thức theo một diễn giải đã cho được định nghĩa theo cách qua lại tương hỗ ngay khi tất cả các biến được lượng tử hoá. I.2. Các tính chất I.2.1. Tính hợp thức / không hợp thức, tính nhất quán / không nhất quán Một công thức được gọi là hợp thức (valid) nếu và chỉ nếu mọi diễn giải đều cho giá trị T. Nếu không, nó được gọi là không hợp thức (non−valid). Một công thức được gọi là không nhất quán (inconsistent) nếu và chỉ nếu với mọi diễn giải đều cho giá trị F. Nếu không, nó được gọi là nhất quán (inconsistent). Ví dụ : Cho G1 : (∀X) (P(X) ∨ (←Q(X))) G2 : (∀X) (P(X) ∨ (←P(X))) G3 : ((∀X) (P(X)) ∧ ((∃Y) (←P(Y))) Công thức G1 là nhất quán vì diễn giải I’1 sau đây trả về cho nó giá trị T : I’1 : D = {1} P(1) T Q(1) T Tuy nhiên, nó là không hợp thức vì diễn giải I’’1 sau đây trả về giá trị F : I’’1 : D = {1} P(1) F Q(1) T Công thức G2 là hợp thức vì nếu không, giả sử I là một diễn giải thuộc miền D làm sai G2, khi đó tồn tại một giá trị «a» của X, lấy trong D, sao cho (P(a) ∨ (←P(a))) là F, mà điều này không thể xảy ra do cách định nghĩa các phép ∨ và ∧. Như vậy, G2 phải là hợp thức. Công thức G3 là không hợp thức vì nếu không, giả sử I là một mô hình của G, I phải làm thoả mãn (∃Y) (←P(Y)), khi đó tồn tại một giá trị «a» trong D, sao cho P(a) có giá trị F, nhưng (∀X) (P(X) không thể thoả mãn trên D. Như vậy, G3 phải là không hợp thức. Chú ý : • Một số tác giả gọi các công thức hợp thức là các hằng đúng (tautology) và các công thức không nhất quán là các mâu thuẫn (contradiction). • Cách viết công thức có thể gây nhầm lẫn. Chẳng hạn công thức : (∀X) (MAN(X) → MORTAL(X)). gợi ý rằng « tất cả mọi người đều chết » và công thức là hợp thức. Thực tế, công thức này là nhất quán, nhưng không hợp thức, vì giá trị trả về của công thức phụ thuộc vào diễn giải theo biến X. Biểu diễn tri thức nhờ logic vị từ bậc một 39 I.2.2. Tính không quyết định được và tính nửa quyết định được Khi một công thức không chứa các biến, người ta có thể sử dụng các bảng chân lý để tiến hành một số hữu hạn các phép toán nhằm xác định một công thức đó là hợp thức hay không, có nhất quán hay không. Vấn đề trở nên vô cùng phức tạp khi các công thức có chứa biến và các dấu lượng tử. Người ta đã chỉ ra rằng trong logic vị từ bậc một, không thể tìm được một thuật toán tổng quát để quyết định xem với chỉ một số hữu hạn phép toán, một công thức bất kỳ nào đó đã cho có là hợp thức hay không. Do vậy, người ta gọi logic vị từ bậc một là không quyết định được (indecidability) (theo định lý về tính không quyết định được của A. Church xây dựng năm 1936). Tuy nhiên, người ta có thể xây dựng các thuật toán tổng quát để quyết định tính hợp thức của một số họ các CTC. Đặc biệt, tồn tại các thuật toán đảm bảo tính hợp thức ngay từ đầu khi ứng dụng một CTC hợp thức nào đó, bằng cách dừng lại sau khi áp dụng một số hữu hạn (nhưng không bị chặn trên) các phép toán để kết luận rằng công thức đã cho là hợp thức. Một thuật toán như vậy khi áp dụng cho một công thức không hợp thức có thể không bao giờ dừng. Chính vì vậy mà người ta nói logic vị từ bậc một là nửa quyết định được (half− decidability). I.2.3. Công thức tương đương Hai CTC G và H được gọi là tương đương nếu và chỉ nếu chúng có cùng giá trị (T hoặc F) cho mọi diễn giải. Người ta viết : với mọi diễn giải I, I(G) = I(H). Ví dụ : (P(a) → Q(b)) và ((←P(a) ∨ Q(b)) là tương đương. Có thể kiểm tra lại kết quả bằng bảng chân lý. Hình 2.1 dưới đây là danh sách các công thức tương đương với quy ước rằng : − G, H, K là các CTC bất kỳ, − G(X), H(X) là các CTC với X là biến tự do, − biểu diễn một CTC hợp thức, ∇ biểu diễn một CTC không nhất quán. Công thức tương đương Được gọi là (G → H) ((←G) ∨ H) (G ↔ H) ((G → H) ∧ (H → G)) (← (←G)) G (←(G ∧ H)) ((←G) ∨ (←H)) (←(G ∨ H)) ((←G) ∧ (←H)) Luật De Morgan ((G ∧ (H ∨ K)) ((G ∧ H) ∨ (G ∧ K)) ((G ∨ (H ∧ K)) ((G ∨ H) ∧ (G ∨ K)) Luật phân phối (G ∧ H) (H ∧ G) (G ∨ H) (H ∨ G) Luật giao hoán ((G ∨ H) ∨ K) (G ∨ (H ∨ K)) ((G ∧ H) ∧ K)) (G ∧ (H ∧ K)) Luật kết hợp cho phép loại bỏ dấu ngoặc (G → H) ((←H) → (←G)) Luật đối vị Công thức tương đương Được gọi là (G ∧ ) G (G ∧ ∇) ∇ (G ∨ ) (G ∨ ∇) G (G ∨ (←G)) (G ∧ (←G)) ∇ (∀X)(G(X)) (∀Y)(G(Y)) (∃X)(G(X)) (∃Y)(G(Y)) Luật dùng chung các biến ←((∀X)G(X)) (∃Y)(←G(Y)) ←((∃X)G(X)) (∀Y)(←G(Y)) (∀X)(G(X) ∧ H(X)) ((∀X)G(X) ∧ (∀Y)H(Y)) (∃X)(G(X)) ∨ H(X)) ((∃X)G(X) ∨ (∃Y)H(Y)) Hình 2..1 Bảng các công thức tương đương I.2.4. Hậu quả logic Công thức G được gọi là hậu quả logic từ các công thức H1,..., Hn nếu và chỉ nếu mọi mô hình của H1,..., Hn là một mô hình của G. Ví dụ : P(a) là hậu quả logic của (∀X) P(X) (∀X) Q(X) là hậu quả logic của (∀X) ((←P(X)) ∨ Q(X)) và (∀X) P(X) Dễ dàng chỉ ra rằng G là hậu quả logic của H1,..., Hn nếu và chỉ nếu : ((H1 ∧... ∧ Hn) → G) là hợp thức, hay nếu và chỉ nếu (H1 ∧... ∧ Hn) ∨ (←G)) là không nhất quán. I.3. Quan hệ giữa định lý và hậu quả logic Ta thấy rằng việc định nghĩa các luật suy diễn, rồi đưa ra các định lý và chứng minh là độc lập với các khái niệm diễn giải (đưa vào các giá trị true và false), tương đương và hậu quả logic. I.3.1. Nhóm các luật suy diễn «đúng đắn» (sound) Khi các định lý, nhận được bằng cách áp dụng một nhóm các luật suy diễn đã cho, là hậu quả logic một cách hệ thống từ một tập hợp các tiên đề bất kỳ nào đó, người ta nói rằng nhóm các luật suy diễn này là đúng đắn. Ví dụ, dễ dàng chỉ ra rằng các luật suy diễn modus ponens và chuyên dụng đã nói trước đây là đúng đắn. I.3.2. Nhóm các luật suy diễn «đầy đủ» Một nhóm các luật suy diễn đã cho là đầy đủ đối với phép suy diễn (deduction complete) nếu với bất kỳ một tập hợp các CTC, mọi hậu quả logic của chúng đều được dẫn đến từ chúng như những định lý, nghĩa là bởi áp dụng một số hữu hạn lần các luật suy diễn của nhóm. Biểu diễn tri thức nhờ logic vị từ bậc một 41 Ví dụ, nhóm các luật suy diễn chỉ được rút ra từ luật modus ponens sẽ không là đầy đủ đối với phép suy diễn, (∀X) (G(X) ∨ H(X)) là một CTC hậu quả logic của hai CTC (∀X) G(X) và (∀X) H(X). Nhưng công thức đầu tiên chỉ có thể được suy diễn từ hai công thức này bởi modus ponens mà thôi. I.3.3. Vì sao cần «đúng đắn» hay «đầy đủ» ? Trong hệ thống hợp giải càc bài toán, logic vị từ bậc một thường dùng để biểu diễn những khẳng định là đúng hay sai trong những miền ứng dụng chuyên biệt. Người ta quan tâm đến phép suy diễn các CTC. Nếu ta lấy các luật suy diễn trong những hệ thống này, thì một cách tự nhiên, chúng phải tạo thành nhóm «đúng đắn». Rõ ràng người ta mong muốn nhóm các luật phải đầy đủ. Nghĩa là mọi hậu quả logic của các tiên đề phải là một định lý và do vậy phải được làm rõ bởi dẫn xuất các luật suy diễn. Tuy nhiên trong thực tế, không phải luôn luôn như vậy. Sau đây ta sẽ chỉ ra một luật suy diễn quan trọng là phép hợp giải (principle of resolution), hay nói gọn là hợp giải (resolution). II. Phép hợp giải Phép hợp giải là một luật suy diễn áp dụng vào một tập hợp các CTC hay một tập hợp các mệnh đề (clauses) đã cho. II.1. Biến đổi các mệnh đề Mệnh đề là tất cả các CTC được xây dựng từ phép hoặc (disjonction) của các trực kiện (literals). Ví dụ : R(Z, a, g(X)) ∨ (←T(U)) ∨ (←V(b, k(c)). II.1.1. Dạng chuẩn trước của một công thức chỉnh Dạng chuẩn trước (prenex normal form) của một CTC đã cho được suy ra bởi áp dụng liên tiếp bốn phép biến đổi sau đây : a. Loại bỏ các phép nối → và ↔ Sử dụng các luật tương đương : (G → H) và ((←G) ∨ H) (G ↔ H) và ((G → H) ∧ (H → G)) b. Ghép các phép nối ← với các nguyên tử liên quan Sử dụng các luật tương đương : (← (←G)) và G (←(G ∨ H)) và ((←G) ∧ (←H)) Luật De Morgan (←(G ∧ H)) và ((←G) ∨ (←H)) ←((∃X) P(X)) và (∀X) (←P(X)) ←((∀X) P(X)) và (∃X) (←P(X)) c. Phân biệt các biến Dùng luật tương đương để tác động dấu lượng tử lên một biến sơ khởi : (∀X) P(X) và (∀Y) P(Y) (∃X) P(X) và (∃Y) P(Y) Luật dùng chung các biến Chú ý : Các phép biến đổi a, b, c dẫn CTC đã cho thành một CTC mới tương đương. d. Dịch chuyển các dấu lượng tử Khi dịch chuyển các dấu lượng tử trong một CTC, ta nhận được một CTC mới tương đương. Bởi vì sau bước c, không còn sự xung đột giữa các nhãn biến được lượng tử hoá. Sau bốn bước biến đổi, ta nhận được công thức có dạng chuẩn trước tương đương với CTC đã cho. Phần tiếp theo của các dấu lượng tử được gọi là tiền tố (prefix) và phần còn lại được gọi là ma trận (matrix). Có nhiều dạng chuẩn trước khác nhau cho cùng một CTC bằng cách áp dụng các luật tương đương nhưng vẫn tuân theo nội dung của các bước a, b, c, d. Ví dụ : Cho CTC G : ((∀X) ((P(X) ∧ Q(X, a)) → (R(X, b) ∧ ((∀Y) ((∀Z) R(Y, Z) → T(X, Y)))))) ∨ ((∀X) S(X)) Sau bước a, ta nhận được : ((∀X) (←(P(X) ∧ Q(X, a)) ∨ (R(X, b) ∧ ((∀Y) (← (∀Z) R(Y, Z) ∨ T(X, Y)))))) ∨ ((∀X) S(X)) Sau các bước b và c, ta nhận được (với quy ước dấu ← áp dụng cho nguyên tử theo sau) : ((∀X) (←P(X) ∧ ←Q(X, a)) ∨ (R(X, b) ∧ ((∀Y) (((∃Z) ←R(Y, Z) ∨ T(X, Y)))))) ∨ ((∀U) S(U)) Sau bước d, ta nhận được dạng chuẩn trước của G : ((∀X) (∀Y) (∃Z) (∀U) (((←P(X) ∨ ←Q(X, a)) ∨ (R(X, b) ∧ (←R(Y, Z) ∨ T(X, Y)))) ∨ (S(U)) hay áp dụng tính chất kết hợp của phép hoặc ∨ : ((∀X) (∀Y) (∃Z) (∀U) (←P(X) ∨ ←Q(X, a) ∨ (R(X, b) ∧ (←R(Y, Z) ∨ T(X, Y))) ∨ (S(U)) II.1.2. Chuyển qua “dạng mệnh đề” của công thức chỉnh Từ dạng chuẩn trước G’ của CTC G, ta có thể tạo ra dạng mệnh đề (form of clauses) G” từ G bằng cách áp dụng 5 bước chuyển đổi sau đây. Trước tiên cần chú ý rằng nếu các công thức G và G’ luôn luôn tương đương với nhau thì các công thức G và G’’ có thể không tương đương với nhau. Ta chỉ xét G không nhất quán tương đương với G” không nhất quán. Quan hệ này vẫn đủ cho phép tạo cơ sở cho việc chứng minh tự động sau này. a. Loại bởi các dấu lượng tử tồn tại Cho công thức dạng (∃X) G(X) và giả sử G(X) được tạo thành từ một hoặc nhiều công thức chỉ được lượng tử hoá toàn thể (∀) đối với các biến Y1,..., Yn mà thôi. Ta sẽ loại bỏ lượng tử tồn tại (∃X), sau đó thay thế mỗi vị trí của X trong G(X) bởi một hàm có dạng f(Y1,..., Yn). Chú ý rằng hàm này phải chứa tất cả các biến được lượng tử hoá toàn thể nằm bên trái lượng tử tồn tại trong công thức (∃X) G(X). Đây là một hàm cho biết có sự tương ứng giữa Biểu diễn tri thức nhờ logic vị từ bậc một 43 các nhóm giá trị của Y1,..., Yn và các giá trị của X. Giá trị của X được chỉ định bởi lượng tử tồn tại ∃. Những hàm như vậy được gọi là các hàm Skolem (Skolem functions). Vì rằng ta không biết gì khác ngoài các tham biến của các hàm này, ta phải sử dụng một ký hiệu gốc để biểu diễn chúng mỗi lần cần thay thế một lượng tử toàn thể khi nó xuất hiện. Khi không có dấu «∀» nào bên trái của «∃» đã cho, hàm Skolem sẽ không có tham biến, và được gọi là một hằng Skolem (Skolem constant). Ví dụ : (∃X) P(X) trở thành P(a) (∀X) (∃Y) FOLLOW(Y, X) trở thành (∀X) FOLLOW(f(X), X) Dạng chuẩn trước của công thức cho trong ví dụ ở mục II.1.1 trở thành : ((∀X) (∀Y) (∀U) (←P(X) ∧ ←Q(X, a) ∨ (R(X, b) ∧ (←R(Y, g(X, Y)) ∨ T(X, Y))) ∨ (S(U)) b. Loại bỏ tất cả các dấu lượng tử Sau bước a trên đây, công thức chỉ còn các dấu lượng tử toàn thể. Với giả thiết rằng tất cả các biến đều được lượng tử hoá toàn thể, ta có thể loại bỏ chúng. Ví dụ sau cùng ở mục trên đây trở thành : (←P(X) ∨ ←Q(X, a) ∨ (R(X, b) ∧ (←R(Y, g(X, Y)) ∨ T(X, Y))) ∨ (S(U)) c. Chuyển qua «dạng chuẩn hội» Trong bước này, người ta sử dụng các luật kết hợp và phân phối đối với các phép toán logic ∧ và ∨ để rút gọn CTC nhận được chỉ còn toàn là phép hội (conjonction) của các phép hoặc (disjonction) của các mệnh đề hay các trực kiện (literal). Ví dụ : ←P(X) ∨ Q(X, a) ∧ ←R(Y, f(X), b) trở thành (←P(X) ∨ Q(X, a)) ∧ (←P(X) ∨ ←R(Y, f(X), b)) Ví dụ ở mục trên đây trở thành : (←P(X) ∨ ←Q(X, a) ∨ R(X, b) ∨ S(U)) ∧ (←P(X) ∨ ←Q(X, a) ∨ ←R(Y, g(X, Y)) ∨ T(X, Y) ∨ (S(U)) d. Loại bỏ tất cả các dấu phép toán logic Phép hội của các mệnh đề nhận được từ bước trên đây được xem như một tập hợp của các mệnh đề một cách truyền thống. Chẳng hạn trong bước trên, ta nhận được tập hợp hai mệnh đề là : { (←P(X) ∨ ←Q(X, a) ∨ R(X, b) ∨ S(U)), (←P(X) ∨ ←Q(X, a) ∨ ←R(Y, g(X, Y)) ∨ T(X, Y) ∨ (S(U)) } e. Phân biệt các biến của các mệnh đề Các mệnh đề trong tập hợp trên đây phải được đặt lại tên biến sao cho không có sự trùng tên. Muốn vậy, ta sử dụng các luật tương đương tổng quát : (∀X) (G(X) ∧ H(X)) và ((∀X) G(X) ∧ (∀Y) H(Y)) Chẳng hạn ta có : { (←P(X) ∨ ←Q(X, a) ∨ R(X, b) ∨ S(U)), (←P(Y) ∨ ←Q(Y, a) ∨ ←R(Z, g(Y, Z)) ∨ T(Y, Z) ∨ (S(V)) } II.1.3. Quan hệ giữa CTC và các dạng mệnh đề của chúng Cho các CTC G1,..., Gp. Giả sử G”1,..., G”p là các dạng mệnh đề tương ứng với G1,..., Gp nhận được từ các bước a.. e trong mục II.1.2 trên đây, hoặc nhận được từ các bước a.. d trong mục II.1.1 để tạo ra các dạng chuẩn trước G’1,..., G’p. Giả sử mỗi G”i có dạng : G”i = { C’1,..., Ciki } Ta thấy rằng { G1,..., Gp } là không nhất quán nếu và chỉ nếu : U " Gi là không nhất quán. i 1, p = Một kết quả khác tương tự là mọi công thức là hậu quả logic của { G1,..., Gp } thì cũng là hậu quả logic của U " Gi . i 1, p = Biểu diễn tri thức nhờ logic vị từ bậc một 45 Chú ý : 1) Trong trường hợp tổng quát, người ta có thể biến đổi một CTC đã cho thành nhiều dạng mệnh đề khác nhau. Người ta có thể loại bỏ một lần các lượng tử tồn tại (bước II.1.2.a) trước khi chuyển qua trái tất cả các lượng tử (bước II.1.1.d). Cách này có thể làm giảm số lượng tham đối của các hàm Skolem xuất hiện. Chẳng hạn, giả sử sau bước II.1.1.c, ta được CTC : ((∀X) P(X) ∧ (∃Y) Q(Y)), bước II.1.1.d dẫn đến : (∀X) (∃Y) (P(X) ∧ Q(Y)), tiếp theo, bước II.1.2.a dẫn đến : (∀X) (P(X) ∧ Q(f(X))), cuối cùng, ta được tập hợp dạng mệnh đề : { P(X), Q(f(Z)) } trong khi đó, nếu thực hiện bước II.1.2.a rồi bước II.1.1.d, ta nhận được : (∀X) (P(X) ∧ Q(a)), từ đó ta được tập hợp : { P(X), Q(a) } Các kết quả trên đây có nghĩa dù dạng mệnh đề nhận được là như thế nào. 2) Khi áp dụng logic vị từ bậc một, thông thường người ta muốn một CTC H là hậu quả logic của các CTC G1,..., Gn. Trong mục I.2.3, ta đã chỉ ra rằng điều này tương đương với sự không nhất quán của CTC : K = G1 ∧... ∧ Gn ∧ ←H Từ các kết quả trước đây, ta muốn tìm kiếm các dạng mệnh đề G1,..., Gn và ←H một cách độc lập, sau đó tích hợp chúng lại, thay vì tìm kiếm trực tiếp một dạng mệnh đề của K theo các bước II.1.1 rồi các bước a.. e trong II.1.2. 3) Nếu G” là một dạng mệnh đề của G, thì G chỉ tương đương với G” khi G và G” là không nhất quán. Nếu G là nhất quán, thì khi đó, một cách tổng quát, G không tương đương với G”. Ví dụ : Cho G là CTC : (∃X) P(X) và giả sử G” là mệnh đề P(a). Nếu ta diễn giải trên miền D = {1, 2} cho bởi : P(1) P(2) a 1 và F T thì ta nhận thấy rằng diễn giải này làm G đúng và làm G” sai. Từ nhận xét này, người ta đặt CTC dưới dạng mệnh đề G và ←H, mà không phải dưới dạng G và H, để chứng minh rằng H là hậu quả logic của G. II.1.4. Phép hợp giải đối với các mệnh đề cụ thể Người ta nói một trực kiện là cụ thể (concrete) nếu nó không chứa các biến. Chẳng hạn, ←P(a), Q(a, f(b)) là các trực kiện cụ thể, nhưng ←P(X), Q(a, f(Y)) không phải là các trực kiện cụ thể. Một mệnh đề cụ thể là phép hoặc của các trực kiện cụ thể. Cho hai mệnh đề cụ thể : G = G1 ∨... ∨ Gn và H = ←G1∨ H2 ∨... ∨ Hm với Gi và Hi là các trực kiện cụ thể. Các trực kiện G1 và ←G1 có mặt trong G và H tương ứng, được gọi là các trực kiện bù nhau (complementary literals). Xuất phát từ các mệnh đề cha (parent clauses) là G và H, luật suy diễn, hay phép hợp giải, sẽ tạo ra một mệnh đề: K = G2 ∨... ∨ Gn ∨ H2 ∨... ∨ Hm K được gọi là mệnh đề kết quả (resolvent clause) hay kết quả hợp giải (resolvent) của G và H. Người ta cũng nói rằng G và H được hợp giải với nhau (resolved) để tạo thành K. Một kết quả hợp giải là sự loại bỏ các trực kiện bù nhau và tuyển với tất cả các trực kiện khác của các mệnh đề cha. Một số trường hợp đặc biệt : • Q là một kết quả hợp giải của các mệnh đề cụ thể P và ←P ∨ Q(hay P và P→Q). Phép hợp giải này thực chất là luật suy diễn modus ponens (trên các mệnh đề cụ thể). • ←G ∨ K (hay G→K) là kết quả hợp giải của các mệnh đề cụ thể ←G ∨ H và ←H ∨ K (hay G→H và H→K). Quy tắc suy diễn này là một trường hợp đặc biệt của phép hợp giải còn được gọi là phép liên kết (chỉ đối với các mệnh đề cụ thể). • Các mệnh đề cụ thể G và ←G được hợp giải với nhau để tạo thành mệnh đề rỗng (empty clause) Chú ý : − Hai mệnh đề cụ thể không có kết quả hợp giải. Chẳng hạn G và ←H, với G và H là các nguyên tử khác nhau. − Hai mệnh đề cụ thể có thể có nhiều kết quả hợp giải. Chẳng hạn hai mệnh đề G∨H∨K và ←G∨←H∨L được hợp giải thành H∨←H∨K ∨L hay thành G∨←G∨K ∨L là những mệnh đề tương đương. − ←P là một kết quả hợp giải của các mệnh đề cụ thể ←Q và ←P ∨ Q(hay ←Q và P→Q). Phép hợp giải này thực chất là luật suy diễn modus tollens. Trước khi định nghĩa tổng quát phép hợp giải áp dụng cho các mệnh đề không phải luôn luôn cụ thể, cần phải định nghĩa một cơ chế tạo sinh các mệnh đề. Đó là phép hợp nhất. II.2. Phép hợp nhất (unification) II.2.1. Khái niêm Giả sử cho các mệnh đề ←G(X) ∨ H(X) và G(f(Y)). Nếu mệnh đề thứ nhất được thay thế bởi ←G(f(Y)) ∨ H(f(Y)), thì ta có thể mở rộng phép hợp giải cho các mệnh đề cụ thể : loại bỏ các trực kiện bù nhau ←G(f(Y)) và G(f(Y)) để nhận được mệnh đề H(f(Y)). Như vậy, phép Biểu diễn tri thức nhờ logic vị từ bậc một 47 hợp nhất cho phép biến đổi các mệnh đề sao cho có dạng trực kiện bù nhau bằng cách áp dụng các phép thế (substitutions). a. Phép thế Phép thế là một tập hợp hữu hạn các cặp ti Vi, trong đó ti là các hạng, còn Vi là các biến phân biệt. Nếu I = 0, ta nói phép thế là rỗng. Người ta nói áp dụng một phép thế s = { ti Vi } cho một biểu thức bất kỳ E (E là một hạng hoặc một CTC) cho trước là xác định một trường hợp của E theo s. Đó là việc thay thế tất cả các vị trí ban đầu của mỗi biến Vi trong E bởi ti. Ví dụ : Cho E = G(f(X), a, Y) và các phép thế : s1 = { Z|X, U|Y } s2 = { b|X } s3 = { Y|X, g(X)|Y } s4 = { a|X, k(c) Y } Ta có : Es1 = G(f(Z), a, U) Es2 = G(f(b), a, Y) Es3 = G(f(Y), a, g(X)) Es4 = G(f(a), a, k(c)) Chú ý : − Để chuyển E thành Es3, chỉ có các vị trí ban đầu của X và Y trong E là được thay thế (không phải các vị trí xuất hiện trong khi áp dụng s3). Kết quả của phép thế này là độc lập với thứ tự áp dụng các phần tử của phép thế. − Es4 là một trường hợp cụ thể của E bởi phép thế s4. − Các hạng ti và các biến Vi được gọi lần lượt là hạng và biến của phép thế. Phép tổ hợp hai phép thế s1và s2, người ta viết quy ước s1°s2, là phép thế nhận được bằng cách như sau : a) Ap dụng s2 cho các hạng của s1. b) Loại bỏ khỏi s2 các cặp tj Vj sao cho Vj là một biến của s1 (hay sao cho ∃ti với ti Vj ∈ s1). c) Tập hợp tất cả các cặp nhận được từ hai bước a) và b) trên đây. Ví dụ : { a X, g(Y, Z, U) V } ° { b X, c Y, f(X) Z, k(d) V, f(X) W } = { a X, g(c, f(X), U) V, c Y, f(X) Z, f(X) W } Người ta chứng minh được rằng : (Es1) s2 = E(s1 ° s2) Người ta cũng chứng minh được rằng phép thế có tính kết hợp, hay : (s1°s2)°s3 = s1°(s2°s3) Trong trường hợp tổng quát, s1°s2 ≠ s2°s1. b. Bộ hợp nhất (unifier) Người ta nói rằng một tập hợp {Ei}i các biểu thức (hạng hay công thức) là hợp nhất được (unifiable) bởi s hay nói rằng s là bộ hợp nhất của {Ei}i nếu và chỉ nếu mọi phép thế s cho Ei, ký hiệu Eis, là giống nhau. Khi đó, ta ký hiệu biểu thức (duy nhất) sinh ra bởi bộ hợp nhất s là {Ei}s. Ví dụ : s = { a X, c Y, c V, b Z, b U, g(b) W } là một hợp nhất của : {Ei}i = { G(X, f(Y), g(b)), G(X, f(c), g(Z)), G(X, f(c), g(U)), G(X, f(V), W) } vì rằng mọi biểu thức đều trở thành : G(a, f(c), g(b)) Có thể có nhiều bộ hợp nhất cho cùng một tập hợp các biểu thức đã cho. Người ta gọi r là bộ hợp nhất tổng quát hơn (mgu − more general unifier) của một tập hợp các biểu thức {Ei}i sao cho với mọi bộ hợp nhất s khác của {Ei}i, tồn tại một phép thế s’ sao cho s = r°s’. Người ta chứng minh được rằng với mọi tập hợp E hợp nhất được, sẽ tồn tại một mgu và, nếu r1 và r2 là hai mgu của {Ei}, thì {Ei}r1và {Ei}r2 là giống nhau cho tên các biến. Ví dụ : Trong ví dụ trên đây, mgu của { E1, E2, E3 } là : r = { c Y, c V, b Z, b U, g(b) W } Chú ý rằng s = r°{ a X }. c. Thuật toán hợp nhất Sau đây ta xây dựng thuật toán đệ quy UNIFY(E, ) với là phép thế rỗng. Thuật toán tạo ra một mgu cho một tập hợp hữu hạn E các biểu thức hợp nhất được. Nếu E không là hợp nhất được, thuật toán dừng và thông báo. UNIFY( , ) 1. if là một phần tử duy nhất (mọi phần tử giống hệt nhau) then begin write(‘ là mgu’); stop end else 2. Tạo tập hợp D các xung đột của 3. If tồn tại hai phần tử V và t của D sao cho V là một biến, t là một hạng và V không có mặt trong t then begin ← ° { t V } ← { t V } UNIFY( , ) end 4. write(‘Tập hợp đã cho không là hợp nhất được’); stop Hình 2.2. Thuật toán hợp nhất Thuật toán sử dụng tập hợp các xung đột, ký hiệu D, của một tập hợp các biểu thức (hạng hay công thức). Tập hợp D này được xây dựng bằng cách quét đồng thời từ trái qua phải mọi phần tử của cho đến khi gặp ký hiệu ở vị trí đầu tiên làm xuất hiện sự sai khác Biểu diễn tri thức nhờ logic vị từ bậc một 49 giữa các phần tử này. Sau đó, bằng cách trích mỗi phần tử của một biểu thức (cần phải là hạng hay công thức ngay khi tất cả các hàm và tất cả các vị từ được viết bởi các ký hiệu phân biệt). Biểu thức này bắt đầu từ vị trí xung đột của ký hiệu. Tập hợp các biểu thức như vậy tạo thành D. Chẳng hạn, cho = { G(X, f(a, Y), G(X, b), G(X, f(a, G(Z))) } Một xung đột xuất hiện ở vị trí ký hiệu thứ năm. Như vậy : D = { f(a, Y), b, f(a, g(Z)) } Ví dụ 1 : Cho E = { P(a, X, f(g(Y))), P(Z, f(Z), f(U)) }. Gọi UNIFY(E, ), khi đó ← E, ← Bước 1 và 2 : D ← { a, Z } Bước 3 : với V ← Z, t ← a ← ° { a | Z } = { a | Z } ← { a | Z } = { P(a, X, f(g(Y))), P(a, f(a), f(U)) }. Gọi UNIFY( , ) Bước 1 và 2 : D ← { X, f(a) } Bước 3 : với V ← X, t ← f(a) ← { a | Z } ° { f(a) X} = { a | Z, f(a) X } ← { f(a) | X } = { P(a, f(a), f(g(Y))), P(a, f(a), f(U)) } Gọi : UNIFY( , ) Bước 1 và 2 : D ← { U, g(Y) } Bước 3 : với V ← U, t ← g(Y) ← { a | Z, f(a) | X } ° { g(Y) U} = { a | Z, f(a) X, g(Y) U } ← { P(a, f(a), f(g(Y))) } Gọi : UNIFY( , ) Bước 1: Tìm thấy mgu là = { a | Z, f(a) X, g(Y) U } Ví dụ 2 : Cho E = { Q(f(a), g(X)), Q(Y, Y) }. Gọi UNIFY(E, ), khi đó ← E, ← Bước 1 và 2 : D ← { f(a), Y } Bước 3 : với V ← Y, t ← f(a) ← ° { f(a) | Y } = { f(a) | Y } ← { f(a) | Y } = { Q(f(a), g(X)), Q(f(a), f(a)) } Gọi : UNIFY( , ) Bước 1 và 2 : D ← { g(X), f(a) } Bước 4: Tập hợp E không là hợp nhất được. Ví dụ 3 : Cho E = { G(X, f(b, X)), G(X, f(Z, g(X)))} Ta phân biệt các biến để có : E’ = { G(X, f(b, X)), G(Y, f(Z, g(Y))) } Sau phép thế { X Y } ta được : E’ ° { X Y } = { G(X, f(b, X)), G(X, f(Z, g(X))) } Ap dụng phép thế { b Z } ta được : E’ ° { X Y, b Z } = { G(X, f(b, X)), G(X, f(b, g(X))) } Nhưng ta không thể thế g(X) cho X : phép hợp nhất không thực hiện được. Chú ý trong thuật toán hợp nhất : − Ở bước 3 trong thuật toán hợp nhất UNIFY( , ), đòi hỏi V phải không xuất hiện trong t : phép thế t cho V sẽ trở nên phức tạp không xác định được, không có kết quả, các biểu thức vẫn luôn phải hợp nhất. Chẳng hạn : { f(X), X } được áp dụng cho G(X, a) và G(f(X), a) sẽ chuyển chúng thành G(f(X), a) và G(f(f(X)), a), v.v... − Việc kiểm tra «V có mặt trong t không ?» làm cho độ phức tạp tính toán của thuật toán trở nên đáng kể. Trong trường hợp xấu nhất, là có bậc luỹ thừa đối với số phần tử của E. Chẳng hạn : E = { P(X1, X2,..., Xn), P(f(X0, X0), f(X1, X1), f(X2, X2),..., f(Xn−1, Xn−1)) } Với lời gọi đệ quy thứ nhất : = { f(X0, X0) X1 } = { P(f(X0, X0), X2,..., Xn), P(f(X0, X0), f(f(X0, X0), f(X0, X0)), f(X2, X2),..., f(Xn−1, Xn−1)) } Với lời gọi đệ quy thứ hai : = { f(X0, X0) X1, f(f(X0, X0), f(X0, X0)) X2 } Với lời gọi đệ quy thứ ba, tập hợp được thêm phần tử : f(f(f(X0, X0), f(X0, X0)), f(f(X0, X0), f(X0, X0))) X3 và cứ thế tiếp tục... Với lời gọi đệ quy thứ n, tham đối cuối cùng của phần tử thứ hai của sẽ có 2n+1−1 xuất hiện của hàm f. Việc kiểm tra «V có mặt trong t không ?» sẽ cần vượt qua tất cả các xuất hiện của f với thới gian là O(2n). − Tồn tại các thuật toán hợp nhất có độ phức tạp tính toán nhỏ, có thời gian tuyến tính. Tuy nhiên, những thuật toán này chỉ có ý nghĩa nếu bậc của các vị từ và của các hạng cần hợp nhất là lớn. II.2.2. Hợp giải các mệnh đề bất kỳ Giả sử cho hai mệnh đề cha G và H không có biến chung (theo bước e, mục II.1.2) và có thể tiến hành hợp giải. Khi đó, tồn tại kết quả hợp giải của G và H. Gọi G, H và kết quả hợp giải của chúng là các tập hợp các trực kiện {Gi} và {Hj}. Giả sử tồn tại một tập hợp con {Gi’} của {Gi} (i’ nhận một số giá trị của i), và một tập hợp con { Hj’} của {Hj } sao cho tập hợp các trực kiện : L = { Gi’} ∪ { ←Hj’ } là hợp nhất được. Giả sử r là một mgu của L, một kết quả hợp giải của G và H là một tập hợp các trực kiện được xác định như sau : ({Gi}− {Gi’}) r ∪ ({Hj}− {Hj’}) r Ví dụ : Gỉa sử G = P(X, f(a)) ∨ P(X, f(Y)) ∨ Q(Y) và H = ←P(Z, f(a)) ∨ ←Q(Z) − Một mgu của G1= P(X, f(a)) và ←H1=P(Z, f(a)) là r1 = {X Z} Từ đó kết quả hợp giải là P(X, f(Y)) ∨ Q(Y) ∨ ←Q(X) − Một mgu của G2 = P(X, f(Y)) và ←H1 là r2 = {X Z, a Y} Từ đó kết quả hợp giải là P(X, f(a)) ∨ Q(a) ∨ ←Q(X) Biểu diễn tri thức nhờ logic vị từ bậc một 51 − Một mgu của G3 = Q(Y) và ←H2 = Q(Z) là r3 = {Y Z } Từ đó kết quả hợp giải là P(X, f(a))∨P(X, f(Y))∨P(Y, f(a)) − Một mgu của G1, G2 và ←H1 là r4 = {X Z, a Y} = r2 Từ đó kết quả hợp giải là Q(a) ∨ ←Q(X). Ta thấy có bốn kết quả hợp giải khác nhau. Trong các trường hợp khác, không tồn tại kết quả hợp giải. Tuy nhiên, trước khi kết luận rằng không tồn tại kết quả hợp giải, ít ra cũng phải kiểm tra các mệnh đề đã cho có các biến phân biệt nhau. Chẳng hạn : G(X, a) và ←G(f(X), X) không có kết quả hợp giải. Nếu viết lại mệnh đề thứ hai thành ←G(f(Y), Y) thì xuất hiện một mpu { f(X) X, a Y}, từ đó có thể suy ra tồn tại một kết quả hợp giải là mệnh đề rỗng. Như vậy, sự phân biệt các tên biến của các mệnh đề cha chỉ hợp pháp lúc gọi thuật toán hợp nhất. Việc tìm một kết quả hợp giải giữa G(X, X) và ←G(f(X), X) đòi hỏi phải viết lại mệnh đề thứ hai thành ←G(f(Y), Y). Lúc này, phép thế { f(X) X } dẫn đến kết quả là hai mệnh đề G(f(Y), f(Y)) và ←G(f(Y), Y) không hợp nhất được. II.2.3. Một cách trình bày khác của phép hợp giải Phép hợp giải còn được trình bày theo một cách khác, gọi là phép nhân tử hoá (factorisation). Trước tiên, người ta đưa vào phép hợp giải nhị phân (binary resolution principle) như sau. Cho G và H là hai mệnh đề có các biến phân biệt, được ký hiệu bởi các tập hợp các trực kiện {Gi} và {Hj}. Giả sử Gp và Hp là hai trực kiện của {Gi} và {Hj} một cách tương ứng sao cho Gp và ←Hq là hợp nhất được. Giả sử r là một mgu của Gp và ←Hq. Người ta định nghĩa kết quả hợp giải nhị phân (binary resolvent) của {Gi} và {Hj} là tập hợp các trực kiện : ({Gi}− {Gp}) r ∪ ({Hj}− {Hq}) r Ta thấy rằng kết quả hợp giải nhị phân là một trường hợp đặc biệt của phép hợp giải đã giới thiệu ở mục II.2.2 trên đây. Bây giờ ta đưa vào một luật suy diễn thứ hai được gọi là phép nhân tử hoá. Giả sử G là một mệnh đề gồm một tập hợp các trực kiện. Giả sử {Li}i = 1.. p là hai hay nhiều trực kiện của G hợp nhất được bởi một mgu r. Xuất phát từ G, bởi phép nhân tử hoá, người ta có thể suy ra mệnh đề nhân tử (factor) của G như sau : (G − {Li}i = 2.. p) r Nghĩa là ta đã cho phát sinh Gr nhưng trộn lẫn tất cả các trực kiện Lir thành một trực kiện duy nhất. Ví dụ : Từ G = P(X) ∨ P(Y) ∨ Q(b), ta cho phát sinh nhân tử P(X) ∨ Q(b). Cuối cùng, ta đưa vào phép hợp giải (không nhị phân) như là một luật suy diễn mới bằng cách tổ hợp các phép triển khai trong luật hợp giải nhị phân và trong luật nhân tử hoá. Xuất phát từ hai mệnh đề G và H, phép hợp giải cho phép phát sinh, hoặc một kết quả hợp giải nhị phân của G và H, hoặc một kết quả hợp giải nhị phân của G và một nhân tử của H, hoặc một kết quả hợp giải nhị phân của H và một nhân tử của G, hoặc một kết quả hợp giải nhị phân của một nhân tử của G và một nhân tử của H. Các kết quả hợp giải nhận được theo định nghĩa thứ nhất (mục II.2.2) cũng có thể nhận được theo định nghĩa thứ hai vừa trình bày. II.3. Các tính chất tổng quát của phép hợp giải a. Một luật đúng đắn Ta có thể chứng minh dễ dàng rằng phép hợp giải là một luật đúng đắn. Nghĩa là mọi kết quả hợp giải là hậu quả logic của hai mệnh đề cha. Từ đó suy ra rằng, nếu một dãy các hợp giải dẫn đến một mệnh đề rỗng, thì tập hợp G đã cho ban đầu là không nhất quán. Nếu không, sẽ tồn tại một diễn giải I làm thoả mãn G và do đó, các mệnh đề cha H1 và H2 là rỗng và vừa là hậu quả logic. Nếu r là mgu dùng để hợp giải H1 và H2, thì diễn giải I phải thoả mãn H1r và H2r, và do H1r sẽ là phần bù của H2r nên diễn giải I không thể tồn tại. Vậy G là không nhất quán. Chú ý : Cho G là tập hợp các mệnh đề và giả sử dãy G’1,..., G’p là các mệnh đề phân biệt sao cho : G’p là mệnh đề rỗng, ∀i = 1..p, hoặc G’ithuộc về G, hoặc G’ilà một kết quả hợp giải của hai mệnh đề cha đứng trước đó trong dãy. Một dãy {G’i} như vậy để chứng minh tính không nhất quán của G được gọi là một bác bỏ (refutation) bởi hợp giải của G. b. Tính hoàn toàn của phép hợp giải đối với phép bác bỏ Người ta chỉ ra rằng nếu một tập hợp các mệnh đề là không nhất quán, thì sẽ tồn tại một dãy hữu hạn các áp dụng của phép hợp giải cho các mệnh đề này và cho các kết quả hợp giải xuất hiện, để từ đó dẫn đến mệnh đề rỗng. Thật vậy, khi một CTC là hậu quả logic của một tập hợp G các CTC, điều này tương đương với tính không nhất quán của một dạng mệnh đề G ∧ ←H. Như vậy, nếu một CTC H là hậu quả logic của một tập hợp G các CTC, thì sẽ tồn tại một phép bác bỏ cho tất cả các dạng G ∧ ←H. Đây là tính hoàn toàn (complétude) đối với phép bác bỏ : nhóm các luật suy diễn được rút gọn thành một luật duy nhất, như vậy phép hợp giải là đầy đủ đối với phép bác bỏ. Ta có thể giải thích tính hoàn toàn của phép hợp giải đối với phép bác bỏ theo cách sau : Gọi R (G) là hợp của một tập hợp mệnh đề G với tất cả các kết quả hợp giải của mọi cặp các mệnh đề có thể. R p+1(G) là tập hợp các mệnh đề R(R p(G)). Tính hoàn toàn của phép hợp giải đối với phép bác bỏ có nghĩa rằng : ∀G tập hợp không nhất quán các mệnh đề, ∃n là một số nguyên dương sao cho mệnh đề rỗng thuộc về R n (G). Chú ý : • Thông thường, người ta rút gọn khi nói về tính hoàn toàn của phép hợp giải. Chú ý rằng không phải là tính hoàn toàn đối với sự suy diễn mà ta đã định nghĩa trước đây (nếu H là một hậu quả logic của một nhóm G các CTC, tính chất được thoả mãn bởi hợp giải Biểu diễn tri thức nhờ logic vị từ bậc một 53 sẽ không là «tồn tại một một dãy hữu hạn các áp dụng của luật suy diễn xuất phát từ G để tạo ra H». Trước tiên, luật chỉ áp dụng đối với các mệnh đề có dạng G ∧ ←H mà không phải đối với CTC bất kỳ của G, để từ đó dẫn đến mệnh đề rỗng, mà không phải là H). • Phép hợp giải nhị phân không là hoàn toàn đối với phép bác bỏ. Thật vậy, xét tập hợp không nhất quán các mệnh đề : E = { P(X) ∨ P(Y), ←P(W) ∨ ←P(Z) } Từ đây ta áp dụng phép hợp giải nhị phân và nhận được các kết quả hợp giải nhị phân luôn luôn có hai trực kiện : ta sẽ không bao giờ nhận được mệnh đề rỗng. • Trái lại, tập hợp các đôi luật hợp giải nhị phân và nhân tử hoá tạo thành một hệ thống đầy đủ đối với phép bác bỏ. Trong ví dụ trên, tính không nhất quán của E có thể được chứng minh bởi áp dụng hai luật này. Chẳng hạn, thực hiện hai phép bác bỏ rồi một phép hợp giải. Cần nhớ rằng tính không nhất quán của E cũng có thể được chứng minh bởi áp dụng chỉ mỗi phép hợp giải (không phải nhị phân). • Sau đây là một ví dụ chỉ ra rằng không phải phép hợp giải nhị phân, cũng không phải hệ thống hai luật hợp giải nhị phân và nhân tử hoá, cũng không phải phép hợp giải (không phải nhị phân) là đầy đủ đối với phép suy diễn : Cho G(X) và H(X) là hậu quả logic của { G(X), H(X) }, nhưng không có luật nào trong hệ thống ba luật suy diễn trên đây áp dụng được cho { G(X), H(X) }. Do vậy không có luật nào là đầy đủ đối với phép suy diễn. III. Các hệ thống bác bỏ bởi hợp giải Nếu G là một tập hợp các mệnh đề và phép hợp giải là một luật suy diễn đúng đắn và đầy đủ (đối với phép bác bỏ), ta có thể khẳng định rằng : «G không nhất quán» cũng có nghĩa là «tồn tại một phép bác bỏ của G bởi hợp giải». Tương tự, nếu G là tập hợp các CTC : «CTC H là hậu quả logic của G» tương đương với «tồn tại một phép bác bỏ của tất cả các dạng mệnh đề G ∧ ←H». Ví dụ : Xét các CTC : (∀X) (∃Y) (←P(X) → Q(Y) et (∀Z) (P(b) → R(a, z)), nếu ta muốn chứng minh rằng : ←R(a, b) → (∃U) Q(U), thì ta có thể tìm kiếm phép hợp giải từ tập hợp các mệnh đề : { P(X) Q(f(X)), ←P(b) R(a, Z), ←R(a, b), ←Q(U) } Sau đây ta sẽ tìm các phương pháp luận của nguyên lý hợp giải để xây dựng phép bác bỏ. III.1. Thủ tục tổng quát bác bỏ bởi hợp giải Giả sử rằng ta muốn chứng minh rằng CTC H là hậu quả lôgic của tập hợp các mệnh đề : G = { Gi } Thủ tục bác bỏ tổng quát không đơn định (non-deterministic) như sau : CHỨNG−MINH−BỞI−HỢP−GIẢI (G, H) 1. Tạo C là tập hợp các dạng mệnh đề đối với các CTC của G 2. Thêm vào tập hợp C một dạng mệnh đề ←H 3. while C ≠ do ; là mệnh đề rỗng begin Chọn hai mệnh đề phân biệt p và q của C (3.1) if p và q là các kết quả hợp giải (3.2) then chọn p hoặc q de thêm vào C end Hình 2.3. Thủ tục tổng quát bác bỏ bởi hợp giải Chú ý : − Căn cứ vào các tính chất của tính hoàn toàn đối với phép bác bỏ của nguyên lý hợp giải, nếu H thực sự hậu quả lôgic của G, thì sẽ tồn tại ít nhất một dãy các lựa chọn (bước 3.1) dẫn đến mệnh đề rỗng và do đó thủ tục dừng. − Thủ tục trên đây không đảm bảo rằng một dãy như vậy nếu quả thật tồn tại thì sẽ tìm thấy. Các giai đoạn 3.1 và 3.2 sẽ không đơn định và rất thô sơ. Chẳng hạn, thủ tục này giải nhiều lần cùng một cặp mệnh đề từ cùng trực kiện. III.2. Chiến lược hợp giải Thủ tục tổng quát CHỨNG−MINH−BỞI−HỢP−GIẢI có thể được làm mịn hơn tại các bước 3.1 và 3.2. Theo cách chọn lựa các mệnh đề và các trực kiện của chúng, người ta có thể định nghĩa nhiều chiến lược bác bỏ bởi hợp giải. Một trong những chiến lược này lả hạn chế hay sắp xếp các lựa chọn mệnh đề và trực kiện để hợp giải tuỳ theo tiêu chuẩn đặc thù của chúng. Một chiến lược hợp giải được gọi là đầy đủ đối với phép bác bỏ nếu tồn tại một phép bác bỏ bởi hợp giải của tập hợp G ban đầu, nghĩa là tồn tại một dãy hợp giải dẫn đến mệnh đề rỗng, thì cũng tồn tại một hợp giải làm thoả mãn các tiêu chuẩn lựa chọn hay thứ tự riêng cho chiến lược này. Người ta cũng biểu diễn tính hoàn toàn đối với phép bác bỏ của một chiến lược hợp giải S theo cách sau. Ký hiệu : R c(G) phép hợp của tập hợp mệnh đề G với tất cả các kết quả hợp giải (resolvent) của tất cả các cặp mệnh đề của G, có thể nhận được bằng cách tuân theo các tiêu chuẩn biểu diễn bởi C, gắn với chiến lược S. R cp 1(G) = R c(R cp (G)) Chiến lược hợp giải S là đầy đủ nếu và chỉ nếu với mọi tập hợp không nhất quán các mệnh đề, tồn tại một số nguyên dương n sao cho mệnh đề rỗng thuộc R cp (G) : Chú ý : − Tính hoàn toàn của một chiến lược hợp giải (đối với phép bác bỏ) không đồng nghĩa với tính hoàn toàn của một nguyên lý hợp giải (đối với phép bác bỏ). − Các chiến lược không đầy đủ có thể có ích lợi thực tiễn. − Một chiến lược là đầy đủ không có nghĩa là khi làm thoả mãn các tiêu chuẩn lựa chọn hay thứ tự tìm thấy một cách tất yếu, với một số hữu hạn các mệnh đề, mệnh đề rỗng xuất phát từ tất cả tập hợp G không nhất quán các mệnh đề. Sau đây, khi một chiến lược có tính chất này, người ta nói là đầy đủ trực tiếp. III.2.1. Đồ thị định hướng, đồ thị tìm kiếm và đồ thị bác bỏ Với mọi hệ thống các luật suy diễn, cho trước một hệ tiên đề, người ta có thể biểu diễn tập hợp các định lý được suy ra (và cách suy ra chúng) dưới dạng một đồ thị được gọi là đồ thị định hướng. Biểu diễn tri thức nhờ logic vị từ bậc một 55 Trong trường hợp của nguyên lý hợp giải, các đỉnh là các mệnh đề và các cung nối các mệnh đề cha đến các mệnh đề kết quả resolvents. Ví dụ, cho tập hợp các mệnh đề : { P(X) Q(f(X)), ←P(b) R(a, Y), ←R(a, b), ←Q(Z) } ta có thể vẽ đồ thị định hướng như sau : P(X)Q(f(X)) ←P (b)R(a, Y) ←R (a, b) ←Q(Z) Q(f(b)) R(a, Y) P(X) ←P(b) Q(f(b)) Q(f(b)) R(a, Y) R(a, Y) Hình 2.4. Đồ thị định hướng Ký hiệu chỉ mệnh đề rỗng . Để đồ thị được rõ ràng, người ta đặt song song các kết quả hợp giải được dẫn đến từ nhiều cặp mệnh đề cha và không vẽ mũi tên cho các cung. Từ đồ thị định hướng này, ta có thể trích ra các đồ thị bác bỏ, chẳng hạn đồ thị sau : P(X)Q(f(X)) ←P (b)R(a, Y) ←R (a, b) ←Q(Z) Q(f(b)) R(a, Y) Q(f(b)) Hình 2.5. Đồ thị bác bỏ Sau đây ta sẽ xem xét một cách ngắn gọn một số chiến lược tương ứng với nhiều cách tìm kiếm các đồ thị bác bỏ bên trong một đồ thị định hướng. Phần đồ thị định hướng rõ ràng để tìm ra một đồ thị bác bỏ được gọi là đồ thị tìm kiếm. III.2.2. Chiến lược hợp giải bởi bác bỏ theo chiều rộng (breadth first resolution) Trong chiến lược này, người ta gán cho mỗi mệnh đề một độ sâu có giá trị : 0 đối với các mệnh đề ban đầu, 1 đối với các kết quả hợp giải của các cặp mệnh đề có độ sâu 0, ... n đối với các kết quả hợp giải của các cặp mệnh đề có độ sâu n−1. Cách người ta đặt độ sâu là làm sao cho không tạo ra một mệnh đề có độ sâu p khi mà có khả năng tạo ra một mệnh đề có độ sâu p1. Rõ ràng rằng khi một kết quả hợp giải xuất hiện lần đầu tiên, thì nó sẽ có độ sâu sâu nhất có thể nhận được từ hai mệnh đề cha. Ví dụ trên đây có thể áp dụng chiến lược hợp giải bởi bác bỏ theo chiều rộng để dẫn đến tại thời điểm dừng một đồ thị tìm kiếm như sau : P(X)Q(f(X)) ←P (b)R(a, Y) ←R (a, b) ←Q(Z) Q(f(b)) R(a, Y) P(X) ←P(b) Q(f(b)) Q(f(b)) R(a, Y) R(a, Y) Hình 2.6. Đồ thị tìm kiếm Từ đồ thị tìm kiếm này, ta có thể trích ra đồ thị bác bỏ sau : P(X)Q(f(X)) ←P (b)R(a, Y) ←R (a, b) ←Q(Z) P(X) ←P(b) Hình 2.7. Đồ thị bác bỏ Biểu diễn tri thức nhờ logic vị từ bậc một 57 Cần chú ý rằng : − Chiến lược này không cấm việc tạo ra một phần tử nào đó của đồ thị định hướng của tập hợp mệnh đề G, nhưng chi phối tính rõ ràng của đồ thị định hướng bằng cách làm xuất hiện tập hợp R p(G) trước R p1(G). Chiến lược này là đầy đủ. − Mặt khác, từ G hữu hạn, người ta suy ra rằng R p(G) là hữu hạn, ∀p = 1..n. Như vậy, chiến lược hợp giải bởi bác bỏ theo chiều rộng là đầy đủ trực tiếp : nếu G không nhất quán, thì chiến lược này sẽ làm xuất hiện mệnh đề rỗng. − Người ta nhận được một phép bác bỏ với mệnh đề rỗng có độ sâu sâu nhất có thể. III.2.3. Chiến lược hợp giải bởi bác bỏ với «tập hợp trợ giúp» Cho G là một tập hợp không thoả mãn các mệnh đề và T là một tập hợp con của G, sao cho tập hợp các mệnh đề GT là nhất quán. Theo định nghĩa, tập hợp trợ giúp của G quan hệ với T (giả thiết thoả mãn tính chất trước đây) gồm các mệnh đề của đồ thị định hướng,hoặc thuộc về T, hoặc là con cháu của T. Một chiến lược hợp giải (đối với một tập hợp mệnh đề G đã cho) sử dụng tập hợp trợ giúp (set of support resolution) quan hệ với T (GT giả sử nhất quán) sao cho với mỗi hợp giải, ta lấy một mệnh đề cha trong tập hợp trợ giúp quan hệ với T. Một chiến lược như vậy không hạn chế tính rõ ràng của đồ thị định hướng như chiến lược theo chiều rộng, làm thu hẹp đồ thị tìm kiếm được sinh ra. Ta chứng minh được rằng các chiến lược này là đầy đủ. Ta có thể tạo ra các kết quả hợp giải mà không thu hẹp đồ thị hơn nữa, bằng cách kiểm tra độ sâu theo cách của chiến lược theo chiều rộng. Trong những điều kiện như vậy, các chiến lược hợp giải với tập hợp trợ giúp là đầy đủ trực tiếp. Sau đây, ta sẽ biểu diễn một đồ thị tìm kiếm nhận được theo cách này. ←R(a, b) ←Q(Z) P(X)Q(f(X)) ←P(b)R(a, Y) ←P(b) P(X) Q(f(b) Hình 2.8. Đồ thị tìm kiếm Xuất phát từ ví dụ đầu mục III.2.1. Lúc đầu, tập hợp trợ giúp chỉ có các mệnh đề ←R(a, b) và ←Q(Z). Các mệnh đề của đồ thị tìm kiếm thuộc về tập hợp trợ giúp được gạch chân. Từ đó, đồ thị bác bỏ được trích ra như sau : ←R(a, b) ←Q(Z) P(X)Q(f(X)) ←P(b)R(a, Y) ←P(b) P(X) Hình 2.9. Đồ thị bác bỏ Chú ý rằng trong ví dụ này, đồ thị tìm kiếm được chứa trong đồ thị nhận được bởi chiến lược theo chiều rộng, và cũng là đồ thị bác bỏ. Để tiến hành chiến lược tập hợp trợ giúp, cần chọn T sao cho GT là nhất quán. Sau đây là ba phương pháp đơn giản : 1. Định nghĩa T như là tập hợp các mệnh đề không chứa các trực kiện phủ định hay trực kiện âm (một trực kiện phủ định, negative literal, là một nguyên tử có dấu phủ định ← đặt trước). G không thể rỗng, nếu không một diễn giải làm cho các trực kiện của T có giá trị T (true) sẽ là một mô hình của G, mô hình này không nhất quán. Mỗi mệnh đề của G-T sẽ chứa một trực kiện phủ định. Tập G-T sẽ nhất quán vì rằng một diễn giải làm cho tất cả các trực kiện phủ định của G-T có giá trị T sẽ là một mô hình của G-T. 2. Định nghĩa T như là tập hợp các mệnh đề không chứa các trực kiện khẳng định (hay trực kiện dương). Như vậy G là nhất quán theo cách suy luận tương tự trên đây. 3. Định nghĩa T như là tập hợp các mệnh đề nhận được bằng cách phủ định CTC cần chứng minh. Trong trường hợp này, G là tập hợp các tiên đề mà dễ dàng được xem là nhất quán. Nếu một tập hợp mệnh đề G là không nhất quán, thì G phải chứa ít nhất một mệnh đề mà các trực kiện đều dương (nếu không, mọi trực kiện của G sẽ chứa ít nhất một trực kiện âm, ta có thể xây dựng một mô hình của G như đã chỉ ra ở phương pháp 1). Từ đó, ta có thể áp dụng chiến lược tập hợp trợ giúp theo phương pháp 1 trên đây. Tương tự như vậy, G phải chứa ít nhất một mệnh đề mà các trực kiện đều âm, và do đó, ta có thể áp dụng chiến lược tập hợp trợ giúp theo phương pháp 2. Ta có thể kiểm tra trong ví dụ trên đây rằng tập hợp T đã chọn thoả mãn phương pháp 2 và cả phương pháp 3. III.2.4. Chiến lược hợp giải bởi bác bỏ dùng «khoá» (lock resolution) Người ta đánh số một cách ngẫu nhiên tất cả các trực kiện của các mệnh đề cho trước. Phép hợp giải của hai mệnh đề chỉ có thể thực hiện được khi số thứ tự của chúng là nhỏ nhất. Các trực kiện của các mệnh đề kết quả (resolvents) thừa kế số thứ tự của các mệnh đề cha (trong trường hợp xảy ra trùng khả năng, người ta lấy lại số thấp nhất). Chiến lược dùng khoá là đầy đủ. Mặt khác, có thể sắp đặt, mà không thu hẹp hơn nữa, việc tạo sinh các kết quả hợp giải bằng cách kiểm tra độ sâu của chúng nhờ chiến lược theo chiều rộng. Trong những điều kiện như vậy, các chiến lược khoá là đầy đủ trực tiếp. Tiến hành đánh số một cách ngẫu nhiên các trực kiện của các mệnh đề đã cho trong ví dụ đầu mục III, ta xây dựng được đồ thị tìm kiếm như sau : P1 (X)Q2(f(X)) ←P3(b)R4(a, Y) ←R5(a, b) ←Q6(Z) Q2 (f(b)) v R4(a, Y) R4(a, Y) Hình 2.10. Đồ thị tìm kiếm Biểu diễn tri thức nhờ logic vị từ bậc một 59 Ở đây, ta thấy đồ thị bác bỏ phủ hoàn toàn lên đồ thị tìm kiếm. III.2.5. Chiến lược hợp giải bởi bác bỏ là «tuyến tính» Cho G là tập hợp mệnh đề không nhất quán, chọn C0 là mệnh đề sao cho G{Co} tạo thành tập hợp mệnh đề nhất quán, khi đó C0 được gọi là mệnh đề trung tâm xuất phát. Mọi kết quả hợp giải cho phép sẽ có C0 là tổ tiên và được gọi là các mệnh đề trung tâm (central clauses). Chiến lược tuyến tính (linear resolution) chỉ cho phép tiến hành hợp giải giữa một mệnh đề trung tâm CC (lúc đầu C0 là trung tâm) và một mệnh đề biên CB được chọn từ : − Hoặc trong số các mệnh đề của G (được gọi là các mệnh đề vào). − Hoặc trong số kết quả hợp giải tổ tiên (là các mệnh đề trung tâm) của CC. Chú ý rằng một mệnh đề trung tâm chỉ có thể được hợp giải với một mệnh đề trung tâm khác nếu một trong chúng là tổ tiên của mệnh đề kia. Phép bác bỏ được vẽ theo sơ đồ sau : Mệnh đề trung tâm... xuất phát C0 Gi ... CC1 .......... CCp Gj CCq Gk ... ............ Mệnh đề biên thứ nhất (cũng là mệnh đề vào) mệnh đề trung tâm thứ hai thứ p+1 mệnh đề biên (hoặc là mệnh đề vào, (hoặc là tổ tiên của CCp) tương tự đối với Gi Hình 2.11. Sơ đồ bác bỏ Hay, bằng cách thay thế tên các mệnh đề biên trên các cung nối các mệnh đề trung tâm, ta nhận được đồ thị như sau : C0 Gi CC1 CCp Gj CCq Gk Hình 2.12. Sơ đồ chiến lược tuyến tính Do đồ thị có dáng một đường thẳng nên người ta gọi đây là chiến lược tuyến tính (linear strategy). Tính chất tuyến tính ở chỗ hai mệnh đề trung tâm chiều có thể được hợp giải khi một trong chúng là tổ tiên của mệnh đề kia. Ví dụ : − Đồ thị tìm kiếm cho ở mục III.2.2 bởi áp dụng chiến lược theo chiều rộng không thể sinh ra bởi chiến lược tuyến tính, dù với cách chọn C0 nào trong số các mệnh đề ban đầu. Đồ thị bác bỏ cũng không phải là tuyến tính. − Tương tự như vậy đối với đồ thị tìm kiếm và đồ thị bác bỏ cho ở mục III.2.3 bởi áp dụng chiến lược tập hợp trợ giúp. − Đồ thị tìm kiếm ở mục III.2.4 được tạo bởi áp dụng chiến lược dùng khoá được xem là kết quả của việc áp dụng chiến lược tuyến tính xuất phát từ mệnh đề : C0 = P(X) ∨ Q(f(X)) hay C0 = ←P(b) ∨ R(a, Y) Lúc này, đồ thị bác bỏ nhận được là lẫn lộn với đồ thị tìm kiếm. − Sau đây là đồ thị tìm kiếm nhận được từ một chiến lược tuyến tính xuất phát từ mệnh đề C0 = P(X) ∨ Q(f(X)) nhưng không lẫn lộn với đồ thị bác bỏ : P(X) Q(f(X)) ←P(b) R(a, Y) ←Q(Z) ←R(a, b) Q(f(b)) R(a, Y) P(X) R(a, Y) R(a, Y) Q(f(b)) đồ thị bác bỏ ứng với đường kẻ đậm Hình 2.13. Đồ thị tìm kiếm chiến lược tuyến tính Đồ thị tìm kiếm trên đây nhận được bằng cách lái theo chiều rộng việc áp dụng chiến lược tuyến tính xuất phát từ P(X) Q(f(X)). Các chiến lược tuyến tính là đầy đủ. Nếu ta sắp đặt việc tạo ra các mệnh đề trung tâm nhờ chiến lược theo chiều rộng, thì chúng là đầy đủ trực tiếp. Nhớ lại rằng tính hoàn toàn căn cứ vào giả thiết mệnh đề trung tâm xuất phát C0 sao cho G −{C0} là nhất quán. Thông thường, người ta chọn C0 là một trong các mệnh đề lấy ra từ phép phủ định của CTC mà người ta muốn chứng minh, nghĩa là phủ định của sự giả định hay sự phỏng đoán (conjecture). Ta có thể giả thiết rằng G −{C0} là một tập hợp mệnh đề nhất quán, chỉ gồm các mệnh đề dạng tiên đề và chỉ có một số mệnh đề có tính phỏng đoán. Nếu phủ định sự phỏng đoán chỉ nhận biết được một mệnh đề, thì G −{C0} phải là nhất quán vì rằng đó là tập hợp các tiên đề. Bây giờ giả thiết rằng phủ định sự phỏng đoán chỉ nhận biết được hai mệnh đề, chẳng hạn C1 và C2. Sự phỏng đoán sẽ có dạng : ←C1 ∨ ←C2. Nếu G −{C0} là không nhất quán, ta có ←C2 là hậu quả logic của các tiên đề, có nghĩa rằng sự phỏng đoán ←C1 ∨ ←C2 là không chính xác : ta có thể đề nghị sự phỏng đoán ←C2 là thích hợp hơn cả. Nếu vẫn còn hoài nghi về kết quả khắc phục này, người ta có thể vận dụng chiến lược tuyến tính xuất phát từ, một cách liên tiếp, mỗi mệnh đề có được từ phỏng đoán. Biểu diễn tri thức nhờ logic vị từ bậc một 61 Quay lại ví dụ vừa rồi, từ 4 mệnh đề ban đầu đã cho : { P(X) Q(f(X)), ←P(b) R(a, Y), ←R(a, b), Q(Z) } ta thấy hai mệnh đề cuối cùng là kết quả của phép phủ định phỏng đoán : ←R(a, b) → (∃U) Q(U) Nếu lấy mệnh đề xuất phát là C0 = ←R(a, b) và nếu ta áp dụng chiến lược tuyến tính và theo chiều rộng, thì ta nhận được : ←R(a, b) ←P(b) R(a, Y) P(X) Q(f(X)) ←Q(Z) ←P(b) Q(f(b)) Tương tự, xuất phát từ C0 = ←Q(Z), ta có : ←Q(Z) P(X) Q(f(X)) ←P(b) R(a, Y) ←R(a, b) P(X) R(a, Y) Hình 2.14. Đồ thị tìm kiếm chiến lược tuyến tính Chú ý : Trên đây ta đã giới thiệu một bác bỏ tuyến tính xuất phát từ mệnh đề : C0 = P(X) ∨ Q(f(X)) mà mệnh đề này không là kết quả của phép phủ định phỏng đoán. Thành công của bác bỏ, ngay cả khi tính đến tính không nhất quán của G đã không được bảo đảm ngay từ đầu. Thực tế, người ta có thể kiểm tra sau đó rằng tập hợp G của bốn mệnh đề ban đầu được cho là nhất quán một cách tối thiểu, nghĩa là dù bất kỳ mệnh đề C nào của G, tập hợp G −{C0} là nhất quán. Từ nhận định này, ta có thể tìm thấy một bác bỏ tuyến tính xuất phát từ mệnh đề cuối cùng như sau : ←P(b) R(a, Y) P(X) Q(f(X)) ←Q(Z) ←R(a, b) R(a, Y) Q(f(b)) R(a, Y) Hình 2.15. Đồ thị bác bỏ chiến lược tuyến tính III.2.6.Chiến lược bác bỏ bởi hợp giải là «tuyến tính theo đầu vào» Chiến lược bác bỏ bởi hợp giải là «tuyến tính theo đầu vào» (linear input resolution) thực chất là chiến lược tuyến tính (chọn một mệnh đề C0 sao cho tập hợp G −{C0} là nhất quán), nhưng người ta yêu cầu thêm điều kiện chỉ lấy các mệnh đề biên trong số các mệnh đề vào đã cho. Ví dụ, bốn phép bác bỏ tuyến tính trong mục III.2.5 vừa rồi cũng là bác bỏ tuyến tính theo đầu vào. Nói chung, chiến lược tuyến tính theo đầu vào không là đầy đủ. Ví dụ sau đây là một minh chứng. Cho G là tập hợp các mệnh đề vào : G = {P(a) Q(X), P(Y) ←Q(Y), ←P(Z) ←Q(Z), ←P(U) Q(U)} Sử dụng chiến lược tuyến tính theo đầu vào, xuất phát từ ←P(Z) ←Q(Z), ta nhận được đồ thị bác bỏ như sau : 4 P(Z) ←Q(Z) ←P(U) Q(U) P(Y) ←Q(Y) P(a) Q(X) 3 2 1 5 ←P(Z) (với nhân tử hoá) 6 ←Q(Y) ←P(Z) (tổ tiên) ♐ 7 P(a) hoặc : 3 ♑ 2 ♒ 1 ♓ 5 Hình 2.16. Đồ thị bác bỏ chiến lược tuyến tính theo đầu vào Trong ví dụ này, ta không thể nhận được phép bác bỏ tuyến tính theo đầu vào. Mỗi mệnh đề vào thuộc G đều có hai trực kiện. Để từng đôi trực kiện cùng được loại bỏ với nhau đối với phép hợp giải, cần thực hiện phép nhân tử hoá trong quá trình hợp giải, điều này là không thể xảy ra đối với mỗi một trong bốn mệnh đề vào. Tuy nhiên, chiến lược tuyến tính theo đầu vào là đầy đủ (chỉ với hợp giải nhị phân mà không nhân tử hoá) nếu áp dụng cho tập hợp không nhất quán các mệnh đề Horn (người ta sẽ Biểu diễn tri thức nhờ logic vị từ bậc một 63 nói : đầy đủ đối với mệnh đề Horn). Các mệnh đề Horn là những mệnh đề chỉ chứa nhiều nhất một trực kiện dương, như : ←R(a, b), ←P(b) ∨ R(a, Y). Chú ý rằng cả 4 mệnh đề trong ví dụ ở mục III.2.5 đều không phải là mệnh đề Horn. Dẫu sao ta cũng đã tạo ra 4 phép bác bỏ tuyến tính theo đầu vào : các chiến lược không đầy đủ theo lý thuyết, nhưng thực tiễn, chúng vẫn có hiệu quả. III.2.7. Chiến lược hợp giải «LUSH» Chiến lược hợp giải «LUSH» là sự vận dụng của «chiến lược tuyến tính theo đầu vào» với ưu điểm thu hẹp các hợp giải cho phép. Trong mệnh đề trung tâm hiện hành, người ta chọn một cách ngẫu nhiên một trực kiện và chỉ để ý đến những hợp giải chứa trực kiện cố định này. Chiến lược hợp giải «LUSH» là đầy đủ (chỉ với hợp giải nhị phân) đối với các mệnh đề Horn. Chú ý : «LUSH» viết tắt từ cụm từ «Linear resolution with Unrestricted Selection function for Horn clauses». Ở đây, «Unrestricted» có nghĩa là việc chọn trực kiện trong mỗi mệnh đề trung tâm là tuỳ ý (nhưng không phải là tuỳ tiện). Ví dụ : Xét các tiên đề sau đây : a1 : (∀X) EQUAL(X, X) thể hiện phép phản xạ của quan hệ EQUAL. a2 : (∀U) (∀V) (∀W) ((EQUAL(U, V) ∧ EQUAL (WV)) → EQUAL (U, W) thể hiện phép nửa−phản xạ (half−transitivity). Ta muốn chứng minh rằng : (∀X) (∀Y) EQUAL (X, Y) → EQUAL (Y, X) có nghĩa là đối xứng (symmetry). Thật vậy, ta có thể chứng minh trực tiếp : từ a2, bằng cách lấy V=U, ta có : (∀U) (∀W) (EQUAL (U, U) ∧ EQUAL (W, U)) → EQUAL (U, W)). Nhưng từ a1, ta được : (∀U) (∀W) EQUAL (W, U) → EQUAL (U, W) dpcm. Bây giờ ta có thể dùng phép bác bỏ để chứng minh. Ta cần chứng minh tính không nhất quán của : a'1 : EQUAL (X, X) a'2 : ←EQUAL (U, V) ←EQUAL (W, V) EQUAL (U, W) c'1 : EQUAL (a, b) c'2 : ←EQUAL (b, a) Sau đây là đồ thị hợp giải nhị phân theo đầu vào : c'2 a'2 ←EQUAL (b, V) ←EQUAL (a, V) a'1 ←EQUAL (a, b) c'1 Hình 2.17. Đồ thị hợp giải nhị phân theo đầu vào Chú ý : − Trong mục III.2.3, ta đã chỉ ra rằng khi một tập hợp mệnh đề đã cho là không nhất quán thì phải tồn tại một mệnh đề không có trực kiện dương, và cần phải có một mệnh đề không có trực kiện dương tham gia vào mọi phép chứng minh tính không nhất quán bằng hợp giải. Trong ví dụ trên đây, ta đã phải chọn mệnh đề xuất phát là c'2 vì tập hợp các mệnh đề còn lại tạo thành một tập hợp nhất quán : toàn bộ trực kiện đều dương. − Khi áp dụng các mệnh đề Horn, xuất phát từ một mệnh đề không có trực kiện dương, ta chỉ có thể tạo ra được các kết quả hợp giải cũng không có trực kiện dương. − Khi một tập hợp các mệnh đề Horn là không nhất quán, thì cần phải có một mệnh đề đơn vị (unitary) (là mệnh đề chỉ có một trực kiện duy nhất) trong chúng là dương. Trong trường hợp này, nói chung sẽ tồn tại một phép bác bỏ (bởi hợp giải nhị phân) sao cho mỗi lần hợp giải, một trong các mệnh đề cha phải là một mệnh đề đơn vị dương. III.3. Ví dụ minh hoạ : bài toán tìm người nói thật Trên một hòn đảo nọ có hai loại người : những người thành thật luôn luôn chỉ nói sự thật và những người dối trá luôn luôn chỉ nói dối. Mỗi người dân của đảo hoặc là một người thành thật, hoặc là một người dối trá. Một người nước ngoài đến đảo và gặp ba người dân của đảo là A, B và C. Ông ta hỏi A : «Ông là một người thành thật hay là một người dối trá ?». A trả lời ấp úng nên người nước ngoài nọ không hiểu gì. Ông ta quay sang hỏi B : «Anh ta đã nói gì vậy ?». B trả lời : «Anh ta đã nói rằng anh ta là người dối trá». Lúc này, C nói xen vào : «Ông đừng tin B, anh ta nói dối đấy !». Hãy xác định xem B và C là những người thành thật hay là dối trá ? Lời giải : Ta sẽ biểu diễn các câu hỏi và câu trả lời trên đây bởi các công thức logic. Gọi S (sincere), L (lie) và SAY là các vị từ với quy ước như sau : − S(X) chỉ rằng X luôn là người thành thật, − L(X) chỉ rằng X luôn là người dối trá, − SAY(X, Y) chỉ rằng X nói Y. Ta có : 1. Mọi người dân trên đảo là thành thật hoặc dối trá : (∀X) S(X)) ∨ L(X) Biểu diễn tri thức nhờ logic vị từ bậc một 65 2. Không có người nào lại vừa thành thật lại vừa dối trá : (∀X) ←S(X) ∨ ←L(X) 3. Nếu X là thành thật và nếu anh ta nói Y, thì Y là đúng : (∀X) (∀Y) (S(X) ∧ SAY(X, Y)) → Y) 4. Nếu X là dối trá và nếu anh ta nói Y, thì Y là sai : (∀X) (∀Y) (L(X) ∧ SAY(X, Y)) → ←Y) 5. Nếu Y là đúng và nếu X nói Y, thì X là thành thật : (∀X) (∀Y) (Y ∧ SAY(X, Y)) → S(X) 6. Nếu Y là sai và nếu X nói Y, thì X là dối trá : (∀X) (∀Y) (←Y) ∧ SAY(X, Y)) → L(X) 7. Câu trả lời của A : SAY(a, không_thể_hiểu_được)) 8. Câu trả lời của B : SAY(b, SAY(a, L(a))) 9. Câu trả lời của C : SAY(c, L(b)) Các hằng a, b, c biểu diễn ba người dân trên đảo ; hằng không_thể_hiểu_được biểu diễn câu nói lắp của A. Ta thấy có thể có nhiều cách để biểu diễn các vị từ. Trong các công thức 3, 4, 5, 6 biến Y có thể được xem như là một ký hiệu vị từ. Trong công thức 8, các ký hiệu vị từ SAY và L được xem như các ký hiệu hàm, tương tự đối với L trong công thức 9. Để làm việc với logic các vị từ bậc một, ta sẽ chỉ dùng một ký hiệu vị từ duy nhất là C. Ký hiệu C(X) có nghĩa đúng (Correct) là X. Có thể bỏ các vị từ S, L và SAY bằng cách thay vào các hàm là s, l và say (tuy nhiên vẫn có thể giữ vị từ S mà không thay nó bởi hàm s). Lúc này ta nhận được 9 công thức mới như sau : 1. (∀X) C(s(X)) ∨ C(s(X)) 2. (∀X) ←C(s(X)) ∨ ←C(s(X)) 3. (∀X) (∀Y) (C(s(X)) ∧ C(say(X, Y))) → C(Y) 4. (∀X) (∀Y) (C(l(X)) ∧ C(say(X, Y))) → ←C(Y) 5. (∀X) (∀Y) (C(Y) ∧ C(say(X, Y))) → C(s(X)) 6. (∀X) (∀Y) (←C(Y) ∧ C(say(X, Y))) → C(s(X)) 7. C(say(a, không_thể_hiểu_được)) 8. C(SAY(b, say(a, l(a)))) 9. C(SAY(c, l(b))) Bây giờ ta chuyển 9 công thức này thành các mệnh đề, trừ mệnh đề đầu tiên đã là mệnh đề Horn, lần lượt được đánh số như sau : 1. C(s(X)) C(l(X)) 2. ←C(s(X)) ←C(l(X)) 3. ←C(s(X)) ←C(say(X, Y)) C(Y) 4. ←C(l(X)) ← C(say(X, Y)) ←C(Y) 5. ←C(Y) ←C(say(X, Y)) C(s(X)) 6. C(Y) ←C(say(X, Y))) C(l(X)) 7. C(say(a, không_thể_hiểu_được)) 8. C(say(b, say(a, l(a)))) 9. C(say(c, l(b))) Để tiến hành quá trình bác bỏ, ta cần chọn một phỏng đoán và thêm các mệnh đề nhận được bởi phủ định phỏng đoán này vào 9 mệnh đề trên. Trước hết, ta phỏng đoán rằng B là một người dối trá, nghĩa là C(l(b)), khi đó cần thêm vào mệnh đề phủ định ←C(l(b)). Tiếp theo, ta cần chọn một chiến lược tổng quát để tiến hành bác bỏ bởi hợp giải từ các chiến lược : − xây dựng tập hợp trợ giúp (tập hợp nào ?), − dùng khoá (cách đánh số các trực kiện như thế nào ?), − tuyến tính (mệnh đề nào được chọn làm mệnh đề xuất phát ?), v.v... Mặt khác, cần chỉ rõ chiến lược hợp giải là theo chiều rộng hay chiều sâu ? Dù chọn chiến lược nào và với lý do nào, việc tổ hợp các hợp giải cũng gặp rất khó khăn. Giả sử mệnh đề ←C(l(b)) được đánh số là 0, sau đây là một quá trình bác bỏ : 1. Hợp giải 7 với 3, rồi lấy kết quả hợp giải với 1 : C(say(a, không_thể_hiểu_được))7 ←C(s(X))←C(say(X, Y))(C(Y) 3 ←C(s(a))C(không_thể_hiểu_được) C(s(X))C(l(X)) 1 C(không_thể_hiểu_được) C(l(a))10 2. Hợp giải 9 với 4, lấy kết quả hợp giải với 1, rồi tiếp tục hợp giải với 1 : C(say(c, l(b)))9 ←C(l(X))←C(say(X, Y))←C(Y) 4 ←C(l(c))←C(l(b)) C(s(X))C(l(X)) 1 ←C(l(c))C(s(b)) C(s(X))C(l(X)) 1 C(s(b)) C(s(c)) 11 3. Hợp giải 8 với 3, lấy kết quả hợp giải với 1 : C(say(b, say(a, l(a))))8 ←C(s(X))←C(say(X, Y)) C(Y)3 ←C(s(b)) C(say(a, l(a))) C(s(X))C(l(X)) 1 C(say(a, l(a)))C(l(b)) 12 4. Hợp giải 12 với 3, lấy kết quả hợp giải với 1 (sử dụng nhân tử hoá) : C(say(a, l(a)))C(l(b)) 12 ←C(s(X))←C(say(X, Y)) C(Y)3 C(l(b))←C(s(a)) C(l(a)) C(s(X))C(l(X)) 1 C(l(b)) C(l(a)) 13 5. Hợp giải 12 với 4, lấy kết quả hợp giải với 10 : C(say(a, l(a)))C(l(b)) 12 ←C(l(X))←C(say(X, Y))←C(Y) 4 C(l(b))←C(l(a)) C(không_thể_hiểu_được) C(l(a)) 10 C(l(b)) C(không_thể_hiểu_được) 14 Biểu diễn tri thức nhờ logic vị từ bậc một 67 6. Hợp giải 13 với 4, lấy kết quả hợp giải với 7, rồi với 4 (nhân tử hoá) : C(l(b)) C(l(a)) 13 ←C(l(X))←C(say(X, Y))←C(Y) 4 C(l(b))∨ ←C(say(a, Y)) ←C(Y) C(say(a, không_thể_hiểu_được))7 C(l(b))∨ ←C(không_thể_hiểu_được) C(l(b)) C(không_thể_hiểu_được) 14 15 7. Hợp giải 15 với 0, tức C(l(b)) với ←C(l(b)), ta nhận được mệnh đề rỗng . Vậy ta đã chứng minh được rằng B là một người dối trá. Ta nhận thấy rằng chiến lược bác bỏ trên đây không là tuyến tính, mà tương thích với chiến lược tập hợp trợ giúp. Các mệnh đề 2, 5 và 9 đã không được sử dụng. Chẳng hạn để xác định B là người như thế nào thì mệnh đề 9 với sự có mặt của C sẽ trở nên thừa. Việc đưa ra các hợp giải khác nhau và các kết quả hợp giải khác nhau để có được phép bác bỏ cuối cùng là bổ ích. Chẳng hạn, kết quả hợp giải từ 8 và 3 có nghĩa rằng hoặc B không phải là người thành thật, hoặc quả đúng A đã nói rằng anh ta là người nói dối. Phép hợp giải của 15 với 2, rồi lấy kết quả hợp giải với 11 dẫn đến C(s(c)). Nếu tiếp tục phỏng đoán rằng C là người nói dối, thì ta cần thêm vào mệnh đề ←C(s(c) để hợp giải với C(s(c)), kết quả là một mệnh đề rỗng. Việc chứng minh C là người nói dối không sử dụng đến mệnh đề 5. Cũng cần chú ý rằng thay vì sử dụng phép bác bỏ với phỏng đoán đã cho, ta có thể đưa ra các hợp giải bằng cách theo dõi sự không xuất hiện mệnh đề rỗng mà xuất hiện một trong bốn trực kiện C(l(c)), C(s(b)), ←C(l(c)), ←C(s(b)). Thực tế, dạng thức vừa vận dụng trên đây không trung thành với phát biểu liên quan đến cách biểu diễn thái độ của A. Theo mệnh đề 7 thì ta đã xử lý câu trả lời của A như là một hằng, là không_thể_hiểu_được. Để tuân thủ điều này, ta đã cố tình không nói «A đã nói rằng anh ta là người thành thật», tức s(a), hay không nói «A đã nói rằng anh ta là người nói dối», tức l(a), vì rằng hằng không_thể_ hiểu_được không tương thích với các hạng s(a) hay l(a). Tuy nhiên, mặc dù với hạn chế bổ sung như vậy, ta vẫn có thể nhận được mệnh đề rỗng, tức chứng minh được điều phỏng đoán. Để biểu diễn câu phát biểu một cách sát thực hơn, ta có thể thay thế mệnh đề 7 bởi mệnh đề 7’ : 7’. C(say(a, l(a))) ∨ C(say(a, s(a))) với giả thiết rằng dù là người thành thật hay là người nói dối, A chỉ trả lời trực tiếp vào câu hỏi của người lạ, mà không trả lời thật thà hay dối trá khác với kiểu «tôi là người thành thật», hay «tôi là người người nói dối», như là «ông là nước ngoài», hay «ông không phải là nước ngoài», hay là một câu nào đó đại loại như «B là người này người kia». Nếu cải chính mệnh đề 7 bởi mệnh đề 7’ và thay vì dùng mệnh đề : C(say(a, không_thể_hiểu_được)) mà dùng một trong các trực kiện C(say(a, l(a))) hay C(say(a, s(a))), thì phép bác bỏ trên đây không còn duy nhất : mệnh đề rỗng không được sinh ra. Sau đây là một phép bác bỏ khác không dùng đến mệnh đề 7’ : 1. Hợp giải 2 và 3 với phép nhân tử hoá : ←C(s(X)) ∨ ←C(say(X, l(X))) 10’ 2. Hợp giải 1 và 4, rồi lấy kết quả hợp giải với 2 (nhân tử hoá) : ←C(l(X)) ∨ ←C(say(X, l(X))) 11’ 3. Hợp giải 10’ và 1, rồi lấy kết quả hợp giải với 11’ (nhân tử hoá) : ←C(say(X, l(X))) 12’ 4. Hợp giải 6 và 8, rồi lấy kết quả hợp giải với 12’ : C(l(b)) 13’ 4. Hợp giải 13’ và 0, ta nhận được mệnh đề rỗng . Vậy B là một người nói dối. Phép hợp giải đã không dùng đến mệnh đề 9 (có sự tham gia của C), 5 và 7’. Đây là kết quả của một chiến lược tuyến tính, tuy nhiên vẫn có thể áp dụng chiến lược tập hợp trợ giúp. Hợp giải 5 với 13’, cho kết quả hợp giải với 9 để nhận được C(s(c)), cuối cùng hợp giải C(s(c)) với ←C(s(c)) nhận được mệnh đề rỗng, vậy C là người thành thật. Các giai đoạn bác bỏ hình thức trên đây liên quan đến việc xác định B và C rất gần gũi với việc suy luận theo ngôn ngữ tự nhiên như sau : «Không thể nào một người thành thật hay một người nói dối lại nói : “Tôi là người nói dối”, vì rằng một người thành thật thì không thể nói dối, còn một người dối trá thì không khi nào dám nói lên sự thật. Do vậy, A không nói rằng anh ta là một người nói dối và B nói dối khi nói rằng A đã khẳng định rằng anh ta là người nói dối. Do vậy, B là một người nói dối. Vì C đã nói rằng B đã nói dối, nên C đã nói lên điều đúng, nên C là một người thành thật». Biểu diễn tri thức nhờ logic vị từ bậc một 69 Bài tập chương 2 3. Cho các ví dụ sử dụng cú pháp của ngôn ngữ vị từ bậc một : a. Bảng ký hiệu b. Hạng (term) c. Nguyên tử (atom) d. Các công thức chỉnh 4. Thế nào là tính hợp thức và không hợp thức, tính nhất quán và không nhất quán của một công thức ? Thế nào làt ính không quyết định được và tính nửa quyết định được của logic vị từ bậc một 5. Cho các ví dụ về công thức chỉnh và phép biến đổi mệnh đề 6. Từ các ví dụ đã cho trong giáo trình, tự cho các ví dụ về các chiến lược hợp giải tìm kiếm và bác bỏ. 7. Tìm một ví dụ khác tương tự bài toán tìm người nói thật. CHƯƠNG 3 Máy suy diễn “ I am only one, but still I am one. I cannot do everything, but still I can do something; and because I cannot do everything, I will not refuse to do something I can do “. Edward Everett Hale Chương trước, ta đã vận dụng logic hình thức để hợp giải bài toán đã cho, nghĩa là nghiên cứu những phương pháp phán đoán và khẳng định các lời giải, đồng thời đánh giá những tính chất và những hạn chế của các phương pháp này. Trong chương này, dựa trên các khái niệm công thức, tiên đề, luật suy diễn và các mối quan hệ giữa chúng, ta sẽ nghiên cứu các máy suy diễn (inference engine) trong các hệ thống dùng luật hay dựa trên luật (Rules−Based Systems). I. Nguyên lý hoạt động của các máy suy diễn Trong các hệ thống dùng luật, mỗi luật bao gồm thông tin về bộ khởi động (starter), hay điều kiện khởi động của luật, và thân (body) của luật, hay thông tin về kết quả khởi động luật : Luật = + Máy suy diễn liên kết các chu kỳ (cycle), mỗi chu kỳ gồm hai giai đoạn (phase) là EVALUATION (đánh giá) và EXECUTION (thực hiện). Khi máy được khởi động, cơ sở tri thức chứa các thông tin liên quan đến phát biểu bài toán cần giải : − Các sự kiện đã được xác nhận và các sự kiện sẽ được thiết lập (biểu diễn bài toán hay đích), − Những tri thức thực hành thuộc lĩnh vực tạo nên cơ sở luật. Theo sơ đồ, ở giai đoạn EVALUATION, máy suy diễn xác định trong cơ sở luật có tồn tại các luật sẽ được khởi động căn cứ vào trạng thái hiện hành của cơ sở sự kiện không, nếu có, thì là những luật nào. Trong giai đoạn EXECUTION, máy suy diễn khởi động các luật đã được tìm thấy ở giai đoạn EVALUATION. Hình 3.1 dưới đây mô tả chu kỳ cơ bản của một máy suy diễn. Ta quy ước gọi RB là cơ sở luật (Rules Base) và FB là cơ sở sự kiện (Facts Base) tại thời điểm bắt đầu của EVALUATION. Máy suy diễn điều khiển liên kết các bước (step) của giai đoạn EVALUATION, của các giai đoạn EVALUATION và EXECUTION, rồi các chu kỳ đầy đủ giữa chúng. PGS. TS. Phan Huy Khánh biên soạn 71 Giai đoạn 1 : ĐÁNH GIÁ THU HẸP cung cấp : R1 bao gồm trong RB F1 bao gồm trong FB SO KHỚP so sánh giữa R1 và F1 cung cấp : R2 bao gồm trong R1 GIẢI QUYẾT XUNG ĐỘT cung cấp : R3 bao gồm trong R2 Giai đoạn 2 : THỰC HIỆN Thực hiện các tiên đề Các quy tắc của R3 FB và có thể RB được thay đổi Các kết quả khác có thể (hướng về môi trường của hệ thống chẳng hạn) Tuỳ theo điều khiển của máy : Tuỳ theo điều khiển của máy : dừng hay quay lại dừng hay quay lại Hình 3.1 Chu kỳ cơ bản của một máy suy diễn Máy suy diễn được điều khiển dừng ở giai đoạn EVALUATION hoặc ở giai đoạn EXECUTION : − Căn cứ vào trạng thái hiện hành của cơ sở sự kiện, máy dừng ở giai đoạn EVALUATION khi không tìm thấy các luật khởi động trong cơ sở luật. − Máy dừng ở giai đoạn EXECUTION khi một trong các luật khởi động cho kết quả dừng. I.1. Giai đoạn đánh giá EVALUATION Giai đoạn EVALUATION gồm ba bước : RESTRICTION (hay SELECTION), PATTERN−MATCHING (hay FILTERING) và CONFLICT-RESOLUTION. a. Bước thu hẹp (RESTRICTION) RESTRICTION (thu hẹp) là bước đầu tiên của giai đoạn EVALUATION, để xác định từ một trạng thái hiện hành hay quá khứ của cơ sở sự kiện (ký hiệu FB) và từ một trạng thái hiện hành hay quá khứ của cơ sở luật (ký hiệu RB), một tập hợp con F1 của FB và một tập hợp con R1 của RB sao cho có thể tiến hành so sánh được trong bước FILTERING tiếp theo. Người ta thường dùng kỹ thuật khai thác các tri thức dựa trên sự phân bố các sự kiện và các luật theo các họ riêng biệt. Đôi khi, các tri thức cho phép phân biệt các sự kiện và các luật liên quan trực tiếp đến lĩnh vực. Ví dụ, trong một ngữ cảnh chẩn đoán bệnh, người ta có thể phân biệt được ngay các luật liên quan đến các bệnh trẻ em với các luật khác, hay phân biệt được các sự kiện liên quan đến phân tích máu với các sự kiện khác. Như vậy, bước RESTRICTION là ưu tiên cho một nhóm nào đó các luật hay các sự kiện Máy suy diễn 73 đối với một hoặc nhiều chu kỳ. Thông thường, những tri thức để phân biệt các sự kiện và các luật là rất tổng quát. Chẳng hạn, nhiều hệ thống phân biệt được các sự kiện đã thiết lập (coi như đã được xác nhận) với các sự kiện sẽ thiết lập (biểu diễn bài toán ban đầu hay đích, hay giả thuyết). Việc thu hẹp sẽ ưu tiên các sự kiện−bài toán so với các sự kiện−bài toán khác, hay ưu tiên bài toán xuất hiện gần đây nhất so với các bài toán trước đó. Sự phân biệt theo họ các sự kiện hay theo họ các luật thường được cụ thể hoá bởi định nghĩa các cấu trúc phân biệt. b. Bước so khớp (PATTERN−MATCHING) PATTERN−MATCHING (so khớp hay lọc) là bước thứ hai của giai đoạn EVALUATION. Máy suy diễn so sánh phần khởi động của mỗi quy tắc của R1 với tập hợp các sự kiện F1. Một tập hợp con R2 của R1 nhóm các luật tương thích với F1, nghĩa là những luật có điều kiện khởi động thoả mãn các trạng thái của F1 (tuỳ theo mỗi hệ thống mà có những tiêu chuẩn thoả mãn khác nhau). R2 được gọi là tập hợp xung đột (conflict set). c. Giải quyết xung đột (CONFLICT-RESOLUTION) Bước thứ ba của giai đoạn EVALUATION là CONFLICT-RESOLUTION. Máy suy diễn xác định các luật, giả sử là một tập hợp con R3 của R2, cần phải được khởi động. Nếu tập hợp R3 rỗng, thì giai đoạn EXECUTION của chu kỳ này không được thực thi. Thông thường, người ta lựa chọn các luật dựa trên những tiêu chuẩn không liên quan đến nghĩa (meaning/signification) của luật có mối quan hệ với bối cảnh áp dụng. Ví dụ, cơ sở luật được sắp xếp ngẫu nhiên thành một danh sách và người ta chọn những luật đứng đầu tiên, hoặc chọn ưu tiên những luật ít sử dụng hơn, hoặc có thể chọn trước tiên những luật ít phức tạp nhất : ít điều kiện cần kiểm tra, ít biến (variable) cần xác định trước khi khởi động, v.v... Đôi khi, người ta dựa trên những tiêu chuẩn liên quan đến nghĩa để chọn các luật có mối quan hệ với bối cảnh áp dụng. Chẳng hạn, một số luật có thể được chọn do có những dấu hiệu giải bài toán tốt hơn, hay có thể đáng tin cậy hơn, hay ít tốn kém về chi phí hơn so với những luật khác, v.v... I.2. Giai đoạn thực hiện EXECUTION Khi R3 rỗng, một số máy suy diễn tự động dừng : người ta nói những máy này có một chế độ điều khiển bắt buộc (irrevocable control regime). Một số máy khác thì lại xem xét lại tập hợp tương tranh R2 của một chu kỳ trước đó và kiểm tra khả năng khởi động của các luật khác của R2. Tuy nhiên, nếu không có một khởi động nào cho luật được thực thi kể từ phép chọn trước đó trong R2, nghĩa là nếu kết quả của các luật này không được huỷ bỏ, trước khi khởi động các luật khác, thì người ta cũng nói rằng những máy này hoạt động theo chế độ điều khiển bắt buộc. Ngược lại, người ta nói chúng hoạt động theo chế độ điều khiển bởi thăm dò (tentative control regime) khi có sự thay thế các khởi động luật bởi các khởi động khác. Để thể hiện một máy quay lại giải quyết các xung đột trước đó, bằng cách khởi động lại các luật, người ta nói máy hoạt động quay lui (to backtrack). Sự quay lui hay không quay lui của máy lúc đầu được điều khiển ở giai đoạn RESTRICTION, tiếp theo, bởi giai đoạn CONFLICT-RESOLUTION. Trong mục tiếp theo, ta sẽ giới thiệu chi tiết hoạt động của một số máy đơn giản ở chế độ điều khiển bắt buộc hay ở chế độ điều khiển bởi thăm dò. Trên thực tế, mỗi giai đoạn của chu kỳ cơ bản của một máy có thể dẫn đến những cách sắp đặt rất khác nhau. Hình 3.1 trên đây mô tả hoạt động của một chu kỳ. Để giải quyết một bài toán đã cho, có thể cần đến hàng ngàn chu kỳ. Mỗi chu kỳ cơ bản của một máy suy diễn làm ta liên tưởng đến chu kỳ-lệnh của một máy tính. Nhưng mỗi chu kỳ của máy suy diễn, hay chu kỳ suy diễn, đòi hỏi hàng trăm, thậm chí hàng ngàn các chu kỳ-lệnh này. Chính vì vậy, cần có những máy tính có tốc độ lớn để có thể đạt được hàng trăm chu kỳ suy diễn trong một giây. Dự án máy tính thế hệ 5 của Nhật đề xuất những kiến trúc đặc trưng cho phép đạt được tốc độ hàng triệu hay hàng tỷ lips (Logical Inference Per Second, mỗi chu kỳ là một suy diễn). II. Một số sơ đồ cơ bản để xây dựng máy suy diễn Sau đây ta sẽ trình bày một số chiến lược liên kết các luật trong các máy suy diễn. Ta sẽ giới thiệu các «sơ đồ» (diagram) của máy hoạt động theo kiểu suy diễn tiến (pre-chaining), hay theo kiểu suy diễn lùi (back-chaining), theo chiều sâu (depth-first), hay theo chiều rộng (breadth-first), tuỳ theo chế độ bắt buộc hay theo chế độ bởi thăm dò. Một vấn đề cũng được đặt ra là lập kế hoạch hành động (actions planning). Riêng máy hoạt động theo chế độ bởi thăm dò sử dụng đến các biến (variable). 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 DIAGRAM2, 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. II.1. Một ví dụ về cơ sở tri thức Để 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 : RULESBASE là danh sách các luật sau đây : 1 K, L, M → I 2 I, L, J → Q 3 C, D, E → B 4 A, B → Q 5 L, N, O, P → Q 6 C, H → R 7 R, J, M → S 8 F, H → B 9 G → F FACTSBASE là danh sách : A, C, D, E, G, H, K Hình 3.2 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. Máy suy diễn 75 «Đồ thị VÀ-HOẶC» sau đây biểu diễn mọi liên kết có thể của các luật : G * = E * D * C * H * F * C * * H = = M * L * * K = O * N * B * * A J * L * = J * * R * M P * * L * I = = = = * * Q S Hình 3.3 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. E * D * C * = B * * A = * Q Hình 3.4. Đồ thị VÀ-HOẶC thiết lập Q khi A, C, D và E được thiết lập II.2. Tìm luật nhờ suy diễn tiến với chế độ bắt buộc đơn điệu a. 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’). procedure SETUP-A-FACT (FACT) 1. if FACT in FACTSBASE then return ‘success’ 2. return RUN-A-CYCLE (RULESBASE) procedure RUN-A-CYCLE (RULES, FACT, ARULE) 1. if RULES = ∅ then return ‘failure’ 2. ARULE ← chọn một luật nào đó từ RULES (chẳng hạn luật gặp đầu tiên) 3. RULES ← RULES − { ARULE } 4. if (∀) (ARULE.premise) in FACTSBASE then 4.1 begin 4.2 if ARULE.conclusion = FACT then return ‘success’ 4.3 if not (ARULE.conclusion in FACTSBASE) then FACTSBASE ← FACTSBASE + { ARULE.conclusion } 4.4 RULESBASE ← RULESBASE − { ARULE } 4.5 return RUN-A-CYCLE (RULESBASE) 4.6 end 5. return RUN-A-CYCLE (RULES) Hình 3.5. 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 suy diễn 77 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.4. 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 3.8 dưới đây biểu diễn đồ thị trạng thái của thủ tục. A C D E G H K Luật 3 A C D E G H K B Luật 4 success Xuất hiện Q trong phần kết luận của luật 4 Hình 3.6. Đồ 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. b. 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 PREDIAGRAM2 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 PREDIAGRAM2, 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 n1 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 PREDIAGRAM2 chỉ tạo ra các sự kiện ở mức n1 khi tất cả các sự kiện ở mức n đã được tạo ra. Người ta nói rằng PREDIAGRAM2 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). procedure SETUP-A-FACT (FACT) 1. if FACT in FACTSBASE then return ‘success’ 2. return RUN-A-CYCLE (FACTSBASE, emptylist, FACT) procedure RUN-A-CYCLE (RULES, NEWFACTS, FACT, ARULE) 1. if RULES = ∅ then 1.1 begin 1.2 if NEWFACTS = ∅ then return ‘failure’ 1.3 FACTSBASE ← FACTSBASE + NEWFACTS 1.4 return RUN-A-CYCLE (FACTSBASE, emptylist, FACT) 1.5 end 2. ARULE ← chọn một luật nào đó từ RULES (chẳng hạn luật gặp đầu tiên) 3. RULES ← RULES − { ARULE } 4. if (∀) (ARULE.premise) in FACTSBASE then 4.1 begin 4.2 if kết luận của ARULE = FACT then return ‘success’ 4.3 if not (ARULE.conclusion in FACTSBASE) or not (ARULE.conclusion in NEWFACTS) then NEWFACTS ← NEWFACTS + { ARULE.conclusion } 4.4 RULESBASE ← RULESBASE − { ARULE } 4.5 end 5. return RUN-A-CYCLE (RULES, NEWFACTS, FACT) Hình 3.7. Sơ đồ máy PREDIAGRAM2 Thủ tục PREDIAGRAM2 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 3.2. Để có thể thiết lập sự kiện Q, người ta khởi động máy PREDIAGRAM2 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 : Mức 0 : A * D * E * C * H * G * K * Luật 3 = = Luật 6 = Luật 9 (khởi động 1) (khởi động 2) (khởi động 3) Mức 1 : * B * R * F Luật 4 = (khởi động 4) Mức 2 : * Q Hình 3.8. Đồ thị VÀ-HOẶC biểu diễn hoạt động của máy PREDIAGRAM2 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 n1 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 Máy suy diễn 79 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. II.3. Tìm luật nhờ suy diễn lùi với chế độ thăm dò đơn điệu a. 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 3.9. 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. Ví dụ, 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. procedure SETUP-A-FACT (FACT) 1. if FACT in FACTSBASE then return ‘success’ 2. return SETUP1 (FACTSBASE) procedure SETUP1 (RULES) 1. if RULES = ∅ then return ‘failure’ 2. ARULE ← chọn một luật nào đó từ RULES (chẳng hạn luật gặp đầu tiên) 3. RULES ← RULES − { ARULE } 4. if (FACT in ARULE.conclusion) then if SETUP2 (ARULE) = ‘success’ then return ‘success’ 5. return SETUP1 (RULES) procedure SETUP2 (RULE, THEFACTS) 1. THEFACTS ← { F | F in ARULE.premise } 2. return FACTS-CONJUNCTION-SETUP (THEFACTS) procedure FACTS-CONJUNCTION-SETUP (FACTS) 1. if FACTS = ∅ then return ‘success’ 2. AFACT ← chọn một sự kiện nào đó từ FACTS (chẳng hạn luật gặp đầu tiên) 3. FACTS ← FACTS − { AFACT } 4. if SETUP-A-FACT (AFACT) = ‘failure’ then return ‘failure’ 5. return FACTS-CONJUNCTION-SETUP (FACTS) Hình 3.9. 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 3.2. Để 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 : E * D * C * M * L * * K Luật 3 Luật 1 = = (khởi động 4) (khởi động 2) * B * A * J * L * I Luật 4 Luật 2 = = (khởi động 3) (khởi động 1) * Q Hình 3.10. Đồ 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 3.11. 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.