Thuật Toán Và Thuật Giải 16

Ví dụ : { p Ú Ø q , Ø r Ú s Ú q , w Ú r, s Ú q } Þ { p Ú Ø r Ú s , w Ú r, s Ú q } B7 : Nếu không xây dựng được thêm một mệnh đề mới nào và trong danh sách mệnh đề không có 2 mệnh đề nào đối ngẫu nhau thì vấn đề không được chứng minh.
Nội dung trích xuất từ tài liệu:
Thuật Toán Và Thuật Giải 16Ví dụ :{ p Ú Ø q , Ø r Ú s Ú q , w Ú r, s Ú q }Þ { p Ú Ø r Ú s , w Ú r, s Ú q }B7 : Nếu không xây dựng được thêm một mệnh đề mới nào và trong danh sách mệnh đềkhông có 2 mệnh đề nào đối ngẫu nhau thì vấn đề không được chứng minh.Ví dụ : Chứng minh rằngØ p Ú q, Ø q Ú r, Ø r Ú s, Ø u Ú Ø s ® Ø p, Ø uB3: { Ø p Ú q, Ø q Ú r, Ø r Ú s, Ø u Ú Ø s, p, u }B4 : Có tất cả 6 mệnh đề nhưng chưa có mệnh đề nào đối ngẫu nhau.B5 : Þ tuyển một cặp mệnh đề (chọn hai mệnh đề có biến đối ngẫu). Chọn hai mệnh đềđầu : ØpÚqÚØqÚrÞØpÚrDanh sách mệnh đề thành :{Ø p Ú r , Ø r Ú s, Ø u Ú Ø s, p, u }Vẫn chưa có mệnh đề đối ngẫu.Tuyển hai cặp mệnh đề đầu tiênØpÚrÚØrÚsÞØpÚsDanh sách mệnh đề thành {Ø p Ú s, Ø u Ú Ø s, p, u }Vẫn chưa có hai mệnh đề đối ngẫuTuyển hai cặp mệnh đề đầu tiênØ p Ú s ÚØ u Ú Ø s Þ Ø p Ú Ø uDanh sách mệnh đề thành : {Ø p Ú Ø u, p, u }Vẫn chưa có hai mệnh đề đối ngẫuTuyển hai cặp mệnh đề :ØpÚØuÚuÞØpDanh sách mệnh đề trở thành : {Ø p, p }Có hai mệnh đề đối ngẫu nên biểu thức ban đầu đã được chứng minh.VIII. BIỂU DIỄN TRI THỨC SỬ DỤNG LUẬT DẪN XUẤT (LUẬT SINH)VIII.1. Khái niệmPhương pháp biểu diễn tri thức bằng luật sinh được phát minh bởi Newell và Simon tronglúc hai ông đang cố gắng xây dựng một hệ giải bài toán tổng quát. Đây là một kiểu biểudiễn tri thức có cấu trúc. Ý tưởng cơ bản là tri thức có thể được cấu trúc bằng một cặpđiều kiện – hành động : NẾU điều kiện xảy ra THÌ hành động sẽ được thi hành.Chẳng hạn : NẾU đèn giao thông là đỏ THÌ bạn không được đi thẳng, NẾU máy tính đãmở mà không khởi động được THÌ kiểm tra nguồn điện, …Ngày nay, các luật sinh đã trở nên phổ biến và được áp dụng rộng rãi trong nhiều hệthống trí tuệ nhân tạo khác nhau. Luật sinh có thể là một công cụ mô tả để giải quyết cácvấn đề thực tế thay cho các kiểu phân tích vấn đề truyền thống. Trong trường hợp này,các luật được dùng như là những chỉ dẫn (tuy có thể không hoàn chỉnh) nhưng rất hữu íchđể trợ giúp cho các quyết định trong quá trình tìm kiếm, từ đó làm giảm không gian tìmkiếm. Một ví dụ khác là luật sinh có thể được dùng để bắt chước hành vi của nhữngchuyên gia. Theo cách này, luật sinh không chỉ đơn thuần là một kiểu biểu diễn tri thứctrong máy tính mà là một kiểu biễu diễn các hành vi của con người.Một cách tổng quát luật sinh có dạng như sau : P1 Ù P2 Ù ... Ù Pn ® QTùy vào các vấn đề đang quan tâm mà luật sinh có những ngữ nghĩa hay cấu tạo khácnhau :Trong logic vị từ : P1, P2, ..., Pn, Q là những biểu thức logic.Trong ngôn ngữ lập trình, mỗi một luật sinh là một câu lệnh.IF (P1 AND P2 AND .. AND Pn) THEN Q.Trong lý thuyết hiểu ngôn ngữ tự nhiên, mỗi luật sinh là một phép dịch :ONE ® một.TWO ® hai.JANUARY ® tháng mộtĐể biễu diễn một tập luật sinh, người ta thường phải chỉ rõ hai thành phần chính sau :(1) Tập các sự kiện F(Facts)F = { f1, f2, ... fn }(2) Tập các quy tắc R (Rules) áp dụng trên các sự kiện dạng như sau :f1 ^ f2 ^ ... ^ fi ® qTrong đó, các fi , q đều thuộc FVí dụ : Cho 1 cơ sở tri thức được xác định như sau :Các sự kiện : A, B, C, D, E, F, G, H, KTập các quy tắc hay luật sinh (rule)R1 : A ® ER2 : B ® DR3 : H ® AR4 : E Ù G ® CR5 : E Ù K ® BR6 : D Ù E Ù K ® CR7 : G Ù K Ù F ® AVIII.2. Cơ chế suy luận trên các luật sinh Suy diễn tiến : là quá trình suy luận xuất phát từ một số sự kiện ban đầu, xác định cácsự kiện có thể được sinh ra từ sự kiện này.Sự kiện ban đầu : H, KR3 : H ® A {A, H. K }R1 : A ® E { A, E, H, H }R5 : E Ù K ® B { A, B, E, H, K }R2 : B ® D { A, B, D, E, H, K }R6 : D Ù E Ù K ® C { A, B, C, D, E, H, K } Suy diễn lùi : là quá trình suy luận ngược xuất phát từ một số sự kiện ban đầu, ta tìmkiếm các sự kiện đã sinh ra sự kiện này. Một ví dụ thường gặp trong thực tế là xuấtphát từ các tình trạng của máy tính, chẩn đoán xem máy tính đã bị hỏng hóc ở đâu.Ví dụ :Tập các sự kiện : • Ổ cứng là hỏng hay hoạt động bình thường • Hỏng màn hình. • Lỏng cáp màn hình. • Tình trạng đèn ổ cứng là tắt hoặc sáng • Có âm thanh đọc ổ cứng. • Tình trạng đèn màn hình xanh hoặc chớp đỏ • Không sử dụng được máy tính. • Điện vào máy tính có hay khôngTập các luật :R1. Nếu ( (ổ cứng hỏng) hoặc (cáp màn hình lỏng)) thì không sử dụng được máytính.R2. Nếu (điện vào máy là có) và ( (âm thanh đọc ổ cứng là không) hoặc tình trạngđèn ổ cứng là tắt)) thì (ổ cứng hỏng).R3. Nếu (điện vào máy là có) và (tình trạng đèn màn hình là chớp đỏ) thì (cáp mànhình lỏng).Để xác định được các nguyên nhân gây ra sự kiện không sử dụng được máy tính, taphải xây dựng một cấu trúc đồ thị gọi là đồ thị AND/OR như sau : ...