Cây hợp giải. Hợp giải tuyến tính

Phương pháp hợp giải như đã trình bày trên đây có nhược điểm là ở các bước có thể xuất hiện những resolvent không cần thiết đối với việc đi đến kết luận.

Khi áp dụng quy tắc hợp giải vào tất cả các cặp công thức có thể áp dụng được, số lượng các resolvent tăng lên rất nhanh chóng, có thể bùng nổ tổ hợp. Để tránh điều này, R.A. Kowalski đưa ra phương pháp hợp giải tuyến tính. Ở đây, khác với hợp giải thông thường, trước hết ta xác định một công thức từ tập {A₁, A₂, … , A_n, ¬B}

có thể cùng với ¬ B áp dụng quy tắc hợp giải. Được resolvent B1 , thêm nó vào tập công thức đã có, lại xác định một công thức từ tập {A1, A2, … , An, ¬B, B1} có thể cùng B1 áp dụng quy tắc này. Cứ tiếp tục như thế cho đến khi được resolvent rỗng, hoặc không thể tiếp tục vì không tìm ra công thức cần tìm, hoặc việc tiếp tục chỉ lặp lại các kết quả đã có. Kowalski đã chứng minh được định lý: Từ tập tiền đề không mâu thuẫn {A1, A2, … , An} và kết luận B phương pháp hợp giải tuyến tính làm xuất hiện resolvent rỗng khi và chỉ khi phương pháp hợp giải thông thường làm xuất hiện resolvent rỗng. Nghĩa là hoàn toàn có thể dùng hợp giải tuyến tính thay cho hợp giải thông thường.

Các lời giải bài toán bằng phương pháp hợp giải có thể biểu diễn dưới dạng hình vẽ dạng cây, trong đó chỉ nêu ra các công thức cần thiết để đi đến kết luận, những công thức khác không cần nêu lên. Chẳng hạn, lời giải trên đây và một lời giải khác của ví dụ (i) được biểu diễn dưới dạng cây thành:

Dạng biểu diễn cây của các lời giải như thế được gọi là cây hợp giải. Mỗi lời giải của bài toán tương ứng với một cây hợp giải.

Ví dụ (i) trên kia có các cây hợp giải tuyến tính sau :

Để tìm lời giải của bài toán, nghĩa là để xây dựng cây hợp giải tuyến tính, người ta sử dụng kỹ thuật quay lui (backtracking).

Dãy liên tục các resolvent trong hợp giải tuyến tính gọi là một nhánh. Nhánh này gọi là nhánh cụt, hay nhánh thất bại, nếu nó kết thúc bằng một công thức nào đó khác . Nhánh này gọi là nhánh tuần hoàn, nếu đến một lúc nào đó bắt đầu lặp lại các resolvent đã có từ trước. Nhánh tuần hoàn cũng là nhánh thất bại. Nhánh kết thúc bằng gọi là nhánh thành công.

Giả sử việc áp dụng quy tắc hợp giải vào cặp công thức Bi-1 với một công thức khác cho ta kết quả Bi. Khi đó từ tập các công thức đang khảo sát ở bước này xác định một tập con các công thức có thể cùng với Bi tạo thành cặp để áp dụng quy tắc hợp giải. Ta chọn trong tập con này một công thức, áp dụng quy tắc hợp giải cho cặp công thức vừa chọn và Bi, được resolvent Bi+1. Với Bi+1 lại xác định tập con công thức có thể tạo cặp để áp dụng quy tắc hợp giải. Quá trình cứ vậy tiếp diễn.

Nếu tất cả các nhánh con bắt đầu từ Bi+1 đều thất bại thì quay trở lại với Bi. Bây giờ ta chọn công thức khác tạo cặp với Bi để áp dụng quy tắc hợp giải. Nếu tất cả các nhánh con bắt đầu từ B_i cũng đều thất bại, thì tiếp tục quay lui đến B_i-1. Bằng cách này sẽ tìm được nhánh thành công, tức là xây dựng được cây hợp giải tuyến tính, nếu nó tồn tại.

Ví dụ 4. Xây dựng cây hợp giải tuyến tính rút ra r từ tập công thức {¬ s ∨ r, ¬ p ∨ q, ¬ q ∨ r, p, u ∨ r, w ∨ s }

Giải. Sơ đồ tìm kiếm lời giải như sau, trong sơ đồ này các dấu chấm chấm vòng cung chỉ các quay lui.

Sơ đồ trên đây cho thấy lúc đầu ta đi từ ¬ r đến u. Đây là nhánh cụt, vì thế quay trở lại ¬ r. Từ đây đi đến ¬ s, từ ¬ s đi đến w, rồi lại quay về s vì là nhánh cụt. Từ

¬ s đi theo hướng khác đến u, đây cũng là nhánh cụt, nên quay về ¬ s. Vì các khả năng khác đi từ ¬ s đã hết, nên quay tiếp về ¬ r. Từ đây đi đến ¬ q. Từ ¬ q đi đến p, đi tiếp đến , đây là nhánh thành công. Cây hợp giải tuyến tính cần xây dựng được biểu diễn bằng các đường kẻ liền trong hình.

Lưu ý : Vì các quy tắc hợp giải chỉ áp dụng cho các công thức dạng tuyển (các công thức chỉ chứa dấu phủ định và dấu tuyển, không có dấu nào khác, hơn nữa, không có phủ định của các công thức tuyển) nên để áp dụng phương pháp hợp giải, các công thức trong tập {A₁, A₂, … , A_n , ¬ B} trước hết phải được đưa về dạng tuyển. (Công thức dạng A & B được tách thành các công thức A, B, các dạng khác biến đổi như đã biết).

Chương 10

SUY LUẬN QUY NẠP

I. ĐỊNH NGHĨA VÀ CẤU TRÚC 1. Định nghĩa

Suy luận quy nạp là suy luận trong đó từ việc nhận thấy sự lặp đi lặp lại của một tính chất nào đó ở một số đối tượng thuộc một lớp nhất định người ta rút ra kết luận chung rằng toàn bộ các đối tượng thuộc lớp đó đều có tính chất đã nêu.

Trong suy luận quy nạp người ta đi từ nhiều cái riêng đến cái chung. Điều này giúp con người có thể khái quát được các trường hợp riêng rẽ quan sát thấy trong khoa học và trong cuộc sống thành các quy luật chung, nghĩa là phát hiện ra các quy luật khách quan sau khi quan sát thấy nhiều biểu hiện cụ thể của chúng. Suy luận quy nạp và suy luận diễn dịch không loại trừ nhau, mà chúng bổ sung cho nhau. Vai trò của suy luận quy nạp đặc biệt quan trọng trong các khoa học thực nghiệm, chẳng hạn như sinh vật học, vật lý học, hoá học, xã hội học, tâm lý học, … . Ngay cả trong toán học, ngành khoa học bao giờ cũng sử dụng diễn dịch để chứng minh các định lý của mình, thì suy luận quy nạp cũng có một vị trí quan trọng. Có nhiều kết luận được các nhà toán học tìm ra nhờ sử dụng suy luận quy nạp, và chỉ sau đó họ mới chứng minh chúng bằng diễn dịch.

2. Cấu trúc

Suy luận quy nạp có cấu trúc như sau:

Đối tượng a1 có tính chất P Đối tượng a₂ có tính chất P

…

Đối tượng a_n có tính chất P

Các đối tượng a1, a2, … , an thuộc lớp S Vậy mọi đối tượng thuộc lớp S đều có tính chất P

Trong cấu trúc trên đây, nếu ngoài các đối tượng a₁, a₂, … , a_n ra lớp S không còn đối tượng nào khác, thì suy luận là quy nạp hoàn toàn. Ngược lại, nếu ngoài các đối tượng đã nói lớp S còn có thêm các đối tượng khác thì suy luận là quy nạp không hoàn toàn.

Trong quy nạp hoàn toàn ta thấy kết luận không nêu lên điều gì mới mẻ so với các tiền đề, các thông tin có trong tiền đề được phát biểu lại ở kết luận dưới

dạng gọn hơn mà thôi, ở đây không có sự khái quát hoá, không có sự vượt ra bên ngoài các thông tin đã có. Chính vì vậy mà quy nạp hoàn toàn còn được gọi là quy nạp hình thức. Cũng vì tính chất này nên quy nạp hoàn toàn còn được một số nhà triết học và logic học cho rằng về thực chất không là quy nạp, mà là diễn dịch.

Trong suy luận quy nạp hoàn toàn nếu các tiền đề đều đúng thì kết luận chắc chắn đúng. Với quy nạp không hoàn toàn thì tình hình khác hẳn. Ở đây kết luận khái quát hoá các thông tin đã có trong các tiền đề, làm cho nó trở nên phong phú hơn.

Có những thông tin có trong kết luận mà không hề có trong các tiền đề.

Ví dụ 1:

Trái đất quay quanh mặt trời theo quỹ đạo hình elip Sao Hoả quay quanh mặt trời theo quỹ đạo hình elip Sao Mộc quay quanh mặt trời theo quỹ đạo hình elip Sao Thủy quay quanh mặt trời theo quỹ đạo hình elip Vậy tất cả các hành tinh trong hệ mặt trời quay quanh mặt trời theo quỹ đạo hình elip

Ví dụ 2:

6 = 3 + 3 ( = tổng của hai số nguyên tố lẻ) 8 = 3 + 5 (= tổng của hai số nguyên tố lẻ) 10 = 5 + 5 (= tổng của hai số nguyên tố lẻ) 12 = 5 + 7 (= tổng của hai số nguyên tố lẻ) 14 = 3 + 11 (= tổng của hai số nguyên tố lẻ) 16 = 3 + 13 (= tổng của hai số nguyên tố lẻ)

6, 8, 10, 12, 14, 16 là các số chẵn không phải là số nguyên tố, cũng không là bình phương của một số nguyên tố

Vậy mọi số chẵn không phải là số nguyên tố, cũng không là bình phương của một số nguyên tố đều biểu diễn được dưới dạng tổng của hai số nguyên tố lẻ

Trong suy luận quy nạp không hoàn toàn (từ đây về sau, để cho ngắn gọn, ta nói quy nạp thay vì nói quy nạp không hoàn toàn), khác với suy luận diễn dịch, các tiền đề đúng và suy luận hợp quy tắc chưa đảm bảo kết luận chắc chắn đúng. Chẳng hạn, suy luận trong ví dụ 1 đảm bảo tính đúng đắn của kết luận, trong ví dụ 2, mặc dù các tiền đề đều đúng, nhưng cho đến nay vẫn chưa biết kết luận có đúng hay không.

Trong khi đó suy luận sau đây theo đúng các quy tắc logic và có các tiền đề đều đúng, nhưng kết luận vẫn sai.

Ví dụ 3:

Hổ đẻ con Mèo đẻ con Ngựa đẻ con

Bò đẻ con Chuột đẻ con

Hổ, mèo, ngựa, bò, chuột đều nuôi con bằng sữa Vậy tất cả các động vật nuôi con bằng sữa đều đẻ con

II. MỘT SỐ PHƯƠNG PHÁP NÂNG CAO ĐỘ TIN CẬY CỦA KẾT LUẬN