Bài viết sưu tầm

chứng minh bằng luật phân giải trên logic vị từ

  Trong phần logic mệnh đề, ta đã đưa ra các luật suy diễn quan trọng như: luật Modus Ponens, luật Modus Tolens, luật bắc cầu,..., luật phân giải. Chúng ta đã chỉ ra rằng luật phân giải là luật đầy đủ cho bác bỏ. điều đó có nghĩa là bằng phương pháp chứng minh bác bỏ, chỉ sử dụng luật phân giải ta có thể chứng minh được một công thức có là hệ quả logic của một tập các công thức cho trước hay không. Kết quả quan trọng này sẽ được mở rộng sang logic vị từ.

  Giả sử ta có một cơ sở tri thức (CSTT) gồm các câu trong logic vị từ. Chúng ta luôn luôn xem CSTT đều đúng. Chẳng hạn minh họa đó là thế giới thực của vấn đề mà chúng ta đang quan tâm và CSTT gồm các câu mô tả sự hiểu biết của chúng ta về thế giới hiện thực đó.

  Không mất tính tổng quát, ta có thể xem các câu trong CSTT là các câu tuyển. Chúng ta có thể sử dụng luật phân giải để suy ra các câu mới là hệ quả logic của CSTT.

Ví dụ: Giả sử CSTT gồm các câu tuyển sau:

                                           Ø P(w) Ú Q(w)                (1)

                                           P(x) Ú R(x)                      (2)

                                           Ø Q(y) Ú S(y)`                 (3)

                                           Ø R(z) Ú S(z)                    (4)

  Sau đây chúng ta sẽ đưa ra một chứng minh của câu S(a) từ CSTT trên bằng luật phân giải. áp dụng luật phân giải cho câu (2) và (4) với phép thế [X/a, Z/a], ta suy ra câu sau:

                                           P(a) Ú S(a)                        (5)

áp dụng luật phân giải cho câu (1) và (3) với phép thế [w/a, y/a] ta nhận được câu:

                                           Ø P(a) Ú S(a)                    (6)

áp dụng luật phân giải cho câu (5) và (6), ta suy ra câu S(a) Ú S(a). Câu này tương đương với câu S(a).

  Chứng minh bằng cách áp dụng các luật suy diễn để dẫn tới điều cần phải chứng minh (như chứng minh trên) được gọi là chứng minh diễn dịch (deduction proof). Nhưng cần biết rằng luật phân giải không phải là luật đầy dủ cho diễn dịch, tức là từ một tập tiên đề, chỉ sử dụng luật phân giải chúng ta không thể sinh ra tất cả các câu là hệ quả logic của tiên đề đã cho.

  Tuy nhiên định lý phân giải (trong mục logic mệnh đề) vẫn còn đúng trong logic vị từ cấp một là thỏa được hay không thỏa được. Nếu một tập câu là không thỏa được thì qua một số bước áp dụng luật phân giải sẽ sinh ra một câu rỗng (tức là dẫn tới mâu thuẫn).

  để chứng minh câu H là hệ quả logic của tập các câu {G₁, G₂,..., G_n} (các tiên đề), ta có thể áp dụng phương pháp chứng minh bác bỏ, tức là chứng minh tập câu {G₁, G₂,..., G_n, Ø H} không thỏa được. Mặt khác, ở trên ta đã chỉ ra rằng luật phân giải cho phép ta xác định được một tập câu là thỏa được hay không thỏa được. Vì vậy luật phân giải được xem là luật đầy đủ cho bác bỏ.