ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC Giáo trình TRÍ TUỆ NHÂN TẠO Huế, 2004 Lời nói đầu Trong năm qua, nhiều tài liệu ngành công nghệ thông tin giới thiệu nhiều cho cán nghiên cứu, ứng dụng sinh viên bậc đại học Tuy nhiên giáo trình ngành học chưa đáp ứng dược nhu cầu sinh viên trường đại học, đặc biệt sinh viên khu vực miền Trung Vì vậy, chúng tơi biên soạn giáo trình “Trí tuệ nhân tạo”, mơn sở chuyên ngành chương trình đào tạo Cử nhân Tin học, ngồi mục đích xây dựng nhiều giáo trình khung chương trình đào tạo, mà cịn giúp cho sinh viên có tài liệu học tập phù hợp với hoàn cảnh thực tế Đại học Huế Trong sách này, sinh viên làm quen với số kiến thức phương pháp tìm kiếm lời giải phương pháp xử lý tri thức Ngoài ra, sách giới thiệu số chương trình cài đặt, nhằm giúp sinh viên hiểu cách tường tận giải thuật, đồng thời tin tưởng giải thuật áp dung thực tế cài đặt máy tính cách dễ dàng Các nội dung trình bày sách giảng cho sinh viên ngành Công nghệ Thông tin Đại học Huế năm vừa qua Cuốn sách đời giúp đỡ mặt vật chất tinh thần Đại học Huế, Trường Đại học Khoa học đặc biệt Ban chủ nhiệm Khoa Công nghệ Thông tin đồng nghiệp thuộc Bộ môn Khoa học Máy tính Chúng tơi xin gửi tới họ lịng biết ơn Xin chân thành cám ơn bạn bè cổ cũ gíup cho sách sớm hồn thành Mặc dù cố gắng, nhiên sách khơng tránh khỏi thiếu sót Chúng tơi mong góp ý độc giả, đặc biệt đồng nghiệp sinh viên để sách ngày hoàn thiện Huế, tháng năm 2004 Tác giả Tài liệu tham khảo Bạch Hưng Khang, Hồng Kiếm Trí tuệ nhân tạo: Các phương pháp ứng dụng Nhà xuất Khoa học Kỹ thuật, 1989 Đinh Mạnh Tường Giáo trình Trí tuệ nhân tạo, Đại học Quốc gia Hà nội Nguyễn Thanh Thuỷ Trí tuệ nhân tạo: Các phương pháp giải vấn đề kỹ thuật xử lý tri thức Nhà xuất Giáo dục, 1996 N Nilson Artificial Intelligence Ed McGrawhill, 1971 Patrick Henry Winston Artificial Intelligence Ed Addison Wesley, 1992 Mục lục Chương Mở đầu Tổng quan Khoa học Trí ruệ nhân tạo Lịch sử phát triển Trí tuệ nhân tạo Một số vấn đề Trí tuệ nhân tạo quan tâm Các khái niêm 2 10 Chương Biểu diễn tốn khơng gian trạng thái Đặt vấn đề Mơ tả trạng thái Tốn tử chuyển trạng thái Khơng gian trạng thái tốn Biểu diễn không gian trạng thái dạng đồ thị Bài tập 12 12 12 14 17 18 21 Chương Các phương pháp tìm kiếm lời giải khơng gian trạng thái Phương pháp tìm kiếm theo chiều rộng Phương pháp tìm kiếm theo chiều sâu Phương pháp tìm kiếm sâu dần Phương pháp tìm kiếm tốt Tìm kiếm đường có giá thành cực tiểu - Thuật tốn AT Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật tốn A* Phương pháp tìm kiếm leo đồi Phương pháp sinh thử Phương pháp thoả mãn ràng buộc 10 Cài đặt số giải thuật 11 Bài tập 23 23 30 34 36 39 43 46 49 51 53 72 Chương Phân rã tốn – Tìm kiếm lời giải đồ thị Và/Hoặc Đặt vấn đề Đồ thị Và/Hoặc Các phương pháp tìm kiếm lời giải đồ thị Và/Hoặc Cây tìm kiếm đấu thủ 90 90 92 94 104 Chương Biểu diễn toán logic phương pháp chứng minh 107 Biểu diễn vấn đề hờ logic hình thức Một số giải thuật chứng minh Ví dụ tập 108 130 138 Chương Tri thức phương pháp suy diễn Tri thức liệu Các dạng mô tả tri thức Suy diễn luật sản xuất 148 148 149 152 Tài liệu tham khảo 163 Chương MỞ ĐẦU Tổng quan khoa học Trí tuệ nhân tạo Trong Cơng Nghệ Thơng Tin, Trí Tuệ Nhân Tạo (Artificial Intelligence) ngành mới, phát triển mạnh mẽ đem lại nhiều kết to lớn Con người thường tự cho sinh vật thơng minh khả trí tuệ đóng vai trị quan trong sống Trong văn học có câu chuyện đề cao trí thơng minh người Trí Tuệ Nhân Tạo hình thành từ năm 1956 Tuy nhiên, việc nghiên cứu trí tuệ có từ lâu Trên 2000 năm trước, nhà triết học tìm hiểu cách thức nhìn nhận, học tập, nhớ suy lý Việc đời máy tính điện tử vào năm 50 kỷ 20 sinh khuynh hướng đưa lĩnh vực nghiên cứu trí tuệ vấn đề lý thuyết thực nghiệm máy 1.1 Đối tượng mục tiêu nghiên cứu trí tuệ nhân tạo Trí tuệ nhân tạo nghiên cứu cách hành xử thông minh (intelligent behaviour) với mục tiêu xây dựng lý thuyết đầy đủ thơng minh để giải thích hoạt động thông minh sinh vật áp dụng hiểu biết vào máy móc nói chung, nhằm phục vụ cho người - Về mặt kỹ thuật: Tạo máy thông minh để giải vấn đề thực tế dùng kỹ thuật AI - Khoa học: Phát triển khái niệm thuật ngữ để hiểu hành xử thông minh sinh vật 1.2 Vai trị Trí Tuệ Nhân Tạo Trí tuệ nhân tạo bao quát nhiều lĩnh vực nghiên cứu hẹp Nó nghiên cứu từ lĩnh vực tổng quát máy nhận biết, suy luận logic, đến tốn chơi cờ, chứng minh định lý Thường nhà khoa học lĩnh vực   khác tìm đến với trí tuệ nhân tạo kỹ thuật hệ thống hoá tự động hoá xử lý tri thức phương pháp thuộc lĩnh vực mang tính người Trí tuệ nhân tạo nghiên cứu kỹ thuật làm cho máy tính “suy nghĩ cách thơng minh” mơ q trình suy nghĩ người đưa định, lời giải Trên sở đó, thiết kế chương trình cho máy tính để giải tốn Sự đời phát triển Trí tuệ nhân tạo tạo bước nhảy vọt chất kỹ thuật kỹ nghệ xử lý thông tin Trí tuệ nhân tạo sở cơng nghệ xử lý thông tin mới, độc lập với công nghệ xử lý thông tin truyền thống dựa văn giấy tờ Điều thể qua mặt sau: - Nhờ cơng cụ hình thức hố (các mô hinh logic ngôn ngữ, logic mờ, ), tri thức thủ tục tri thức mơ tả biểu diễn máy Do trình giải toán tiến hành hữu hiệu - Mơ hình logic ngơn ngữ mở rộng khả ứng dụng máy tính lĩnh vực địi hỏi tri thức chun gia trình độ cao, khó như: y học, sinh học, địa lý, tự động hóa - Một số phần mềm trí tuệ nhân tạo thể tính thích nghi tính mềm dẻo lớp toán thuộc nhiều lĩnh vực khác - Khi máy tính trang bị phần mềm trí tuệ nhân tạo ghép mạng cho phép giải toán cỡ lớn phân tán 1.3 Các kỹ thuật Trí tuệ nhân tạo Có nhiều kỹ thuật nghiên cứu, phát triển ngành khoa học Trí tuệ nhân tạo Tuy vậy, kỹ thuật Trí tuệ nhân tạo thường phức tạp cài đặt cụ thể, lý kỹ thuật thiên xử lý ký hiệu tượng trưng đòi hỏi phải sử dụng tri thức chuyên môn thuộc nhiều lĩnh vực khác Do vậy, kỹ thuật Trí tuệ nhân tạo hướng tới khai thác tri thức lĩnh vực quan tâm mã hoá máy cho đạt mức độ tổng quát; dễ hiểu, dễ diễn đạt thông qua ngôn ngữ chuyên môn gần gũi với ngôn ngữ   tự nhiên; dễ sửa đổi, hiệu chỉnh, dễ sử dụng, khai thác nhằm thu hẹp khả cần xét để tới lời giải cuối Các kỹ thuật Trí tuệ nhân tạo bao gồm : - Lý thuyết giải tốn suy diễn thơng minh: Lý thuyết giải tốn cho phép viết chương trình giải câu đố, chơi trị chơi thơng qua suy luận mang tính người; hệ thống chứng minh định lý Ngồi hệ thống hỏi đáp thơng minh cịn cho phép lưu trữ xử lý khối lượng lớn thơng tin - Lý thuyết tìm kiếm may rủi: Lý thuyết bao gồm phương pháp kỹ thuật tìm kiếm với hỗ trợ thơng tin phụ để giải tốn cách có hiệu - Các ngơn ngữ Trí tuệ nhân tạo: Để xử lý tri thức người ta không sử dụng ngơn ngữ lập trình dùng cho xử lý liệu số, mà cần có ngơn ngữ khác Các ngôn ngữ chuyên dụng cho phép lưu trữ xử lý thông tin ký hiệu Một số ngôn ngữ nhiều người biết đến IPL.V,LISP, PROLOG - Lý thuyết thể tri thức hệ chuyên gia: Trí tuệ nhân tạo khoa học thể sử dụng tri thức Mạng ngữ nghĩa, lược đồ, logic vị từ, khung phương pháp thể tri thức thông dụng Việc gắn liền cách thể sử dụng tri thức sở hình thành hệ chuyên gia - Lý thuyết nhận dạng xử lý tiếng nói: Giai đoạn phát triển đầu Trí tuệ nhân tạo gắn với lý thuyết nhận dạng Các phương pháp nhận dạng gồm: nhận dạng hình học, nhận dạng dùng tâm lý học, nhận dạng theo phương pháp hàm thế, dùng máy nhận dạng ứng dụng phương pháp việc nhận dạng chữ viết, âm - Người máy: Cuối năm 70, người máy công nghiệp đạt nhiều tiến Người máy có phận cảm nhận chế hoạt   động nối ghép theo điều khiển thơng minh Khoa học học Trí tuệ nhân tạo tích hợp khoa học người máy - Tâm lý học xử lý thông tin : Các kết nghiên cứu tâm lý học giúp Trí tuệ nhân tạo xây dựng chế trả lời theo hành vi, có ý thức; giúp cho việc thực suy diễn mang tính người - Ngồi ra, xử lý danh sách, kỹ thuật đệ quy, kỹ thuật quay lui xử lý cú pháp hình thức kỹ thuật tin học truyền thống có liên quan trực tiếp đến Trí tuệ nhân tạo Lịch sử phát triển Trí Tuệ Nhân Tạo Lịch sử Trí tuệ nhân tạo cho thấy ngành khoa học có nhiều kết đáng ghi nhận Theo mốc phát triển, người ta thấy Trí tuệ nhân tạo sinh từ năm 50 với kiện sau:  Turing coi người khai sinh ngành Trí tuệ nhân tạo phát ơng máy tính lưu trữ chương trình liệu  Tháng 8/1956 J.Mc Carthy, M Minsky, A Newell, Shannon Simon ,… đưa khái niêm “trí tuệ nhân tạo”  Vào khoảng năm 1960 Đại học MIT (Massachussets Institure of Technology) ngôn ngữ LISP đời, phù hợp với nhu cầu xử lý đặc trưng trí tuệ nhân tạo - ngơn ngữ lập trình dùng cho trí tuệ nhân tạo  Thuật ngữ Trí tuệ nhân tạo dùng vào năm 1961 MIT  Những năm 60 giai đoạn lạc quan cao độ khả làm cho máy tính biết suy nghĩ Trong giai đoạn người ta chứng kiến máy chơi cờ chương trình chứng minh định lý tự động   Cụ thể: 1961: Chương trình tính tích phân bất định 1963: Các chương trình Heuristics: Chương trình chứng minh định lý hình học khơng gian có tên “tương tự”, chương trình chơi cờ Samuel 1964: Chương trình giải phương trình đại số sơ cấp, chương trình trợ giúp ELIZA (có khả làm việc giống chuyên gia phân tich tâm lý) 1966: Chương trình phân tích tổng hợp tiếng nói 1968: Chương trình điều khiển người máy (Robot) theo đồ án “Mát – tay”, chương trình học nói  Vào năm 60, giới hạn khả thiết bị, nhớ đặc biệt yếu tố thời gian thực nên có khó khăn việc tổng qt hố kết cụ thể vào chương trình mềm dẻo thơng minh  Vào năm 70, máy tính với nhớ lớn tốc độ tính tốn nhanh phương pháp tiếp cận Trí tuệ nhân tạo cũ thất bại (do bùng nổ tổ hợp q trình tìm kiếm lời giải tốn đặt ra)  Vào cuối năm 70 vài kết xử lý ngôn ngữ tự nhiên, biểu diễn tri thức giải vấn đề Những kết tạo điều kiện cho sản phẩm thương mại Trí tuệ nhân tạo đời Hệ chuyên gia, đem áp dụng lĩnh vực khác (Hệ chuyên gia phần mềm máy tính chứa thơng tin tri thức lĩnh vực cụ thể đó, có khả giải yêu cầu người sử dụng mức độ đó, trình độ chuyên gia người có kinh nghiệm lâu năm)  Một kiện quan trọng vào năm 70 đời ngôn ngữ Prolog, tương tự LISP có sở liệu kèm   Chương TRI THỨC VÀ CÁC PHƯƠNG PHÁP SUY DIỄN Như ta biết người sống mơi trường nhận giới nhờ giác quan sử dụng tri thức tích luỹ nhờ khả lập luận, suy diễn, người đưa hành động hợp lý cho công việc mà người làm Trong mục tiêu trí tuệ nhân tạo ứng dụng thiết kế tác nhân thông minh (intelligent agent) có khả người (Tác nhân thơng minh nhận thức môi trường thông qua cảm nhận (sensors) đưa hành động hợp lý đáp ứng lại môi trường thông qua phận hành động (effectors) Ví dụ: robots, softrobot (software robot), hệ chuyên gia, tác nhân thông minh) Tri thức liệu - Tri thức hiểu biết miền chủ đề (lĩnh vực) Ví dụ - Hiểu biết y học, văn học, tri thức - Thu thập thông tin ta liệu vào tri thức ta có dịnh phán đoán Đối với cam ta xét liệu vỏ, cuống, màu sắc, nào? dựa vào hiểu biết ta mà xác định xem cam ngon hay không ngon, ngon vừa, Như vậy, tri thức dạng liệu bậc cao Khó phân biệt tri thức liệu (khơng có ranh giới rõ ràng chúng) Tuy nhiên ta phân biệt theo bảng sau: Dữ liệu - Định lượng - Có cấu trúc đơn giản - Ở dạng đơn giản   Tri thức - Định tính - Khơng có cấu trúc có cấu trúc phức hợp - Ở dạng phức hợp 148 Các dạng mô tả tri thức (các phương pháp biểu diễn tri thức) (Để máy tính sử dụng tri thức, xử lý tri thức, cần phải biểu diễn tri thức dạng thuận tiện cho máy tính Đó mục tiêu biểu diễn tri thức) Sau nhiều cố gắng, nhà TTNT phát triển số cách biểu diễn (thể hiện) tri thức có hiệu máy 2.1 Biểu diễn tri thức logic Như ta nghiên cứu phần trước, ta biểu diễn toán biểu thức logic (logic mệnh đề, logic vị từ) 2.2 Biểu diễn tri thức mạng ngữ nghĩa Phương pháp biểu diễn tri thức cách dùng đồ thị G = (V, E) gồm tập đỉnh V tập cung E Trong đỉnh ứng với đối tượng, khái niệm hay kiện cụ thể, cung thể quan hệ đối tượng Có cung nối hai đối tượng a đối tượng b, ký hiệu a b có quan hệ hai đối tượng a, b Có loại quan hệ đặc biệt - "a b" nghĩa đối tượng a thuộc vào tập đối tượng biểu diễn khái niệm b tập đối tượng biểu diễn khái niệm a tập tập đối tượng biểu diễn khái niệm b (quan hệ is-a) Ví dụ Yến chim - Ngược lại với quan hệ "là" quan hệ "bao gồm" Khi có " a b" (hoặc "b bao gồm a"), thông tin đối tượng cho b truyền lại cho a (nghĩa a thừa hưởng b có)   149 Ví dụ   cánh Yến is‐a  Chim is‐a Cánh cụt thở   có is‐a Chíp chíp Khơng khí is‐a Con vật hoạt động bay hoạt động Ưu điểm: - Cho phép biểu diễn cách trực quan kiện mối liên hệ chúng - Tính mơ đun cao theo nghĩa tri thức thêm vào hoàn toàn độc lập với tri thức cũ - Có thể áp dụng số chế suy diễn mạng: chế truyền thừa hưởng thông tin đối tượng, chế "cháy" mạng Nhược điểm: - Khơng có phương pháp suy diễn chung cho loại mạng ngữ nghĩa - Khó kiểm sốt q trình cập nhật tri thức để dẫn đến mâu thuẫn sở tri thức 2.3 Biểu diễn tri thức khung (Frame) Khung thực chất tổng quát hoá cấu trúc ghi Pascal tương tự cấu trúc đối tượng C++ Một khung mô tả cấu trúc: - Tên khung: Định danh đối tượng mô tả - Các khe (slot): khe lưu trữ thơng tin, n\miền giá trị, thuộc tính chiều mũi tên đến khung khác   150 Ví dụ Xét khung (frame) mơ tả tập học sinh HOCSINH Frame HOCSINH IS-A: PART-OF: NGUOI-DI-HOC A KIND OF: (HOCSINHCOSO, HOCSINHTRUNGHOC) Cân nặng: 10-60kg Chiều cao: 80-170cm Cấu trúc frame cho ta "khung liệu" để khoanh vùng đối tượng học sinh Trường hợp gặp người cao 175cm, nặng 45kg ta khẳng định khơng phải học sinh khơng thỗ mãn ràng buộc có Ngồi ra, đặc trưng quan trọng frame khả thừa kế thơng tin khe có tên đối tượng bậc Ví dụ Trong frame HOCSINHCOSO, HOCSINHTRUNGHOC có khe chiều cao với giá trị mơ tả miền, sau thừa kế thơng tin mức Frame HOCSINH, khe cần phải lấy giá trị khoảng 80-170cm 2.4 Biểu diễn tri thức luật sản xuất Phương pháp biểu diễn tri thức nhờ logic (logic mệnh đề logic vị từ) trực quan song phù hợp nhiều luật suy diễn Một tri thức thể câu Horn dạng chuẩn: p1  p2   pn  q (Các câu Horn dạng gọi luật if- then biểu diễn sau: if P1 and and Pm then Q) Một câu Horn dạng tổng quát: p1  p2   pn  q1  q2   qm   151 Lưu ý: Nếu có luật dạng: p1  p2   pn  q1  q2   qm tương đương với m luật sau: p1  p2   pn   q2   qm  q1 p1  p2   pn   q1   q3  qm  q2 p1  p2   pn   q1  qm-1  qm Tuy nhiên ta xét câu Horn dạng chuẩn (m=1) - Nếu n=0, m=1: câu Horn có dạng  q: gọi kiện (fact) q - Nếu n>0, m=1: câu Horn có dạng: p1  p2   pn  q: gọi luật (rule) Trong hệ chuyên gia, sở tri thức gồm phần: tập kiện (facts) tập luật (rules) Ví dụ 1) Ta có luật kinh nghiệm dự báo thời tiết: "Chuồn chuồn bay thấp mưa, bay cao nắng, bay vừa râm" a: chuồn chuồn bay thấp, b: chuồn chuồn bay cao, c: chuồn chuồn bay vừa d: trời mưa, e: trời nắng, f: trời râm lúc ta có luật sau: ad be cf 2) Nhiều định lý tốn học biểu diễn luật, ví dụ: Nếu tam giác có góc 600 tam giác có hai cạnh tam giác tam giác Suy diễn luật sản xuất 3.1 Khái niệm Suy diễn trình suy luận dựa vào quy luật cho, thiết lập thông tin từ thông tin biết Suy diễn sử dụng tập kiện làm tiên đề   152 Các phương pháp suy diễn chuyển từ giả thiết kết luận cách thêm vào giả thiết kiện khẳng định đúng, dựa phương thức: - Modus ponens: A, AB B nghĩa A AB B - Modus tollens B, AB A nghĩa B sai biết AB A sai Trong trình suy diễn, ta cần quan tâm đến vấn đề sau: - Xây dựng tập luật, câu hỏi chọn để người sử dụng trả lời - Chọn trình tìm kiếm - Thơng tin nhận có ảnh hưởng đến q trình tìm kiếm khơng 3.2 Bài tốn Cho tập kiện F= {f1, f2, ,fn} tập luật R= {r1, r2, ,rm} Chứng minh tập kết luận G 3.3 Các phương pháp suy diễn Quá trình suy diễn hệ luật sản xuất bao gồm phương pháp bản: suy diễn tiến suy diễn lùi a) Suy diễn tiến (lập luận tiến - forward chaining forward reasoning) (Tư tưởng suy diễn tiến áp dụng luật suy diễn Modus Ponens tổng quát) Là trình suy diễn tập kiện biết, rút kiện có kiện cần chứng minh khơng có luật sinh kiện (tập kiện cực đại) - Phương pháp GỌi T tập kiện thời điểm xét (khởi tạo tập T=F: tập kiện ban đầu )   153 Xét luật ri có dạng: p1  p2   pn  q pjT  j  1, n nghĩa left (ri) T T= T+ right (ri) trình lặp lại G T khơng có luật sinh thêm kiện - Giải thuật Procedure suydientien; Begin T:= F; S:= loc(R, T); { S: tập luật có dạng p1  p2   pn  q cho pjT  j  1, n } While G  T and S Begin r := get(S); T:= T + right(r); R:=R \ {r}; S:= loc(R,T); End; If G  T then write (“thành công”) Else write (“không thành công”); End; Ví dụ 1) Cho trước tập kiện F={a,b} Sử dụng luật: r1: a  c r2: b  d r3: c  e r4: a  d  e   154 r5: b  c  f r6: e  f  g cần suy g r T S R a, b r1 , r , r r1, r2, r3, r4, r5, r6 r1 a, b, c r2 , r3 , r5 r2, r6 r2 a, b, c, d r3 , r4 , r5 r3, , r6 r3 a, b, c, d, e r4 , r5 r4 , r5 , r6 r4 a, b, c, d, e r5 r5 , r6 r5 a, b, c, d, e, f r6 r6 r6 a b, c, d, e, f, g gT nên toán chứng minh (g: true) Chú ý - Quá trình suy diễn tiến trình xem xét luật, với luật ta xét phần điều kiện (ở vế trái) tới phần kết luận (ở vế phải) mà tất đièu kiện luật thỗ mãn ta suy kiện phần kết luận Chính lẽ mà có tên suy diễn tiến - Trong bước thủ tục, người ta xét luật tập luật So sánh điều kiện (ở vế trái) tập luật với kiện sở kiện, tất điều kiện luật thỗ mãn kiện phần kết luận xem kiện suy kiện kiện (khơng có nhớ làm việc) đưa vào nhớ làm việc Quá trình lặp lại khơng có luật sinh kiện   155 - Quá trình suy diễn tiến không định hướng tới giải vấn đề cả, khơng hướng tới tìm câu trả lời cho câu hỏi Suy diễn tiến trình suy kiện từ kiện có nhớ làm việc b) Suy diễn lùi (lập luận lùi - backward chaining backward reason) Là trình xuất phát từ kiện cần chứng minh thay vào kiện vế trái luật có vế phải kiện cần chứng minh Quá trình thực đưa kiện tập kiện tập kiện giả thiết (Nghĩa là: để đưa kết luận b, ta thử tìm tất luật có dạng: a1   an  b, để có b, phải đưa kết luận a1, ,an Quá trình xác định tương tự b, đến lúc phát có khơng dẫn xuất từ giả thiết quay lui sang luật sản xuất khác sinh b có dạng b1 bm  b Ngược lại, dẫn xuất giả thiết trình dẫn xuất b đúng) - Giải thuật GỌi T tập kiện cần chứng minh thời điểm xét (khởi tạo T= G, G tập kết luận) S(p) ={riR / right(ri) = p} ( tập luật R cho vế phải chứa p) Procedure suydienlui (g); Begin T:= {g}; If T F then write (‘g chứng minh ‘) Else Begin p:=get(T); If S(p) = {} then write (‘g không chứng minh ‘)   156 Else For ri S(p) Begin T:= T \ right(ri); T:= T + left(ri); For lT \ F suydienlui(l); End; End; Ví dụ 1) Cho tập kiện F={p, r}, tập luật R: r1) p  q r2) q  r  s Chứng minh s p r T S(p) s s r2 q, r r2 q r1 r, p r Nhận xét - Suy diễn tiến: Ưu điểm: i) Làm việc tốt tốn có chất thu thập thông tin thấy điều cần suy diễn ii) Cho khối lượng lớn thông tin từ số thơng tin ban đầu Nó sinh nhiều thông tin iii) Suy diễn tiến tiếp cận lý tưởng loại toán cần giải nhiệm vụ lập kế hoạch, điều hành, điều khiển diễn dịch   157 Nhược điểm: i) Không cảm nhận cần vài thông tin quan trọng Hệ thống hỏi câu hỏi hỏi mà khơng biết câu đến kết luận ii) Hệ thống hỏi câu hỏi khơng liên quan Có thể câu trả lời quan trọng làm người dùng lúng túng phải trả lời câu chẳng dính đến chủ đề - Suy diễn lùi: Ưu điểm: i) Phù hợp với toán đưa giả thuyết liệu giả thuyết có hay khơng? ii) Tập trung vào đích cho Nó tạo loạt câu hỏi liên quan đến vấn đề xét, thuận tiện người dùng iii) Khi suy diễn điều từ thơng tin biết , tìm phần sở tri thức thích đáng tốn xét iv) Suy diễn lùi đánh giá cao tốn chẩn đốn, dự đốn tìm lỗi Nhược điểm: Nhược điểm loại suy diễn thường dịng suy diễn thay phải dừng mà sang nhánh khác - Như vậy, dựa vào ưu nhược điềm loại suy diễn mà ta nên chọn kỹ thuật suy diễn để áp dụng vào toán Trước tiên, ta xem xét chuyên gia giải nào? Nếu cần thu thập liệu định suy diễn ta chọn suy diễn tiến cịn có giử thuyết cần chứng minh đích ta dùng suy diễn lùi Ví dụ Một bác sĩ hiểu hàng trăm vấn đề xảy với cá nhân, phải tìm hiểu trạng bệnh nhân, lúc cần suy diễn   158 tiến Nguợc lại bác sĩ thấy bệnh ( ví dụ viêm họng) ơng ta dùng suy diễn lùi Bài tập Cho biểu thức logic mệnh đề sau: 1) ac 2) ab f 3) (d +b)f  i 4) h + a + f 5) fgh  i 6) (a + d + c ) 7) ad  gh Chứng minh bác bỏ mệnh đề i phương pháp suy diễn tiến suy diễn lùi Lời giải - Biểu diễn biểu thức cho luật sản xuất (xác định tập luật, tập kiện ban đầu, tập kiện cần chứng minh) Quá trình biến đổi 3) (d+b)f  i  ((d+b)f )+i (d+b)+f+i  (db)+f+i  (d+f+i)(b+f+i)  (df i )(bf i) 4) h + a + f  (ha)+f   f 1) (a + d + c )  (ac)+d  ac  d 2) ad  gh )  (ad)+(gh) )  ((ad)+g) ((ad)+h)  (ad  g)(ad  h) Tập kiện F={a, c}, tập kiện cần chứng minh G={i} Tập luật R:   r1) ab f r5) fgh  i r2) (df i ) r6) ac  d r3) (bf i ) r7) ad  g r4)  f r8) ad  h 159 - Suy diễn tiến (tiến hành lập bảng sau) r T S R a, c r6 r1, r2, r3, r4, r5, r6, r7, r6 a, c, d r7 , r r8 r7 a, c, d, g r8 r1, r5, r7, r8 r8 a, c, d, g, h r4 r1, r5, r8 r4 a, c, d, g, h, f r2 , r r1, r5 r2 a, c, d, g, h, f, i r1, r2, r3,r5 (trong đó: r: luật xét, T: tập kiện thời điểm xét, S: tập luật có dạng mệnh đề vế trái thuộc T R tập luật thời điểm xét) Vì iT (là tập kiện đúng) Vậy i chứng minh - Suy diễn lùi (tiến hành lập bảng sau) p r T S(p) i i r2 d, f r2, r3, r5 f r1 d, b r1 , r2 d  b quay lui f r2 d, h r2 h r8 d r8 d r6  r6 Vậy i chứng minh   160 Bài tập Cho sở tri thức biểu diễn biểu thức logic sau 1) pt  a 5) p  t 2) qt  s 6) apq  c 3) pq  b 7)bc  t 4) b st 8) pq Biểu diễn tri thức cho dạng luật sản xuất dùng phương pháp suy diễn tiến suy diễn lùi để chứng minh bác bỏ kiện s1 Bài tập Cho sở tri thức biểu diễn biểu thức logic sau 1) (a+c)b  f 2) e +f + a 3) gfh  i 4) (e+ f)b  gi 5) (a+ e +c)abc Dùng phương pháp suy diễn tiến suy diễn lùi để chứng minh bác bỏ kiện i1 Bài tập Cho sở tri thức biểu diễn biểu thức logic sau 1) efh 2) a + g + d 3) h + c + d 4) af  bg 5) ke  d 6) (ef  a )(c+ e +f ) - Biểu diễn tri thức cho dạng luật sản xuất - Dùng phương pháp suy diễn tiến để chứng minh kiện d1 Cho biết luật dư thừa vết suy diễn   161 Bài tập Trong lớp học, có nhóm học sinh gồm 10 bạn có tên là: A, B, C, D, E, F, G, H, I J Giữa bạn học sinh có mối quan hệ gọi quan hệ ảnh hưởng Ví dụ: ta viết AB>C có nghĩa hai bạn đồng thời thuyết phục bạn C tham gia hoạt động Giả sử ban đầu có bốn bạn E, F, H, I tham gia dự thi sản phẩm phần mềm nhà trưòng tổ chức ta biết rằng: 1) ACH>B 2) BH>ACD 3) ABCI>BDI 4) ADEI>BCG 5) CGI>AJE 6) H>BC Hãy dùng phương pháp suy diễn tiến để chứng minh 10 bạn nhóm tham gia dự thi sản phẩm phần mềm   162 ... đặt trí tuệ nhân tạo, làm rõ ngành khoa học Trí tuệ nhân tạo tiến hành nghiên cứu mới, đặc biệt nghiên cứu chế suy lý, Trí tuệ nhân tạo phân tạo, mơ hình tương tác Những đặc trưng Trí tuệ nhân tạo. .. tiếp đến Trí tuệ nhân tạo Lịch sử phát triển Trí Tuệ Nhân Tạo Lịch sử Trí tuệ nhân tạo cho thấy ngành khoa học có nhiều kết đáng ghi nhận Theo mốc phát triển, người ta thấy Trí tuệ nhân tạo sinh... hướng Trí tuệ nhân tạo cài đặt hệ Trí tuệ nhân tạo hệ thống khác, đặc biệt hệ thống tin học Những vấn đề chưa giải Trí tuệ nhân tạo Những thành tựu nghiên cứu ứng dụng kỹ thuật Trí tuệ nhân tạo