Câu 3: Thuật toán suy diễn tiến.

1.Suy diễn

Là cơ chế liên kết các tri thức đã có để suy ra các tri thức mới

Cơ chế suy diễn phụ thuộc rất nhiều vào phương thức biểu diễn tri thức. Một phương pháp biểu diễn cụ thể sẽ quy định phương pháp suy diễn tương ứng tức là ko có 1 phương pháp chung cho mọi loại tri thức.,,

2.Suy diễn trong logic mệnh đề

Khác hẳn với phương pháp giải quết vấn đề của Vương Hạo và Robinson phương pháp suy diễn sẽ lần lượt chuyển từ các giải thuật về các kết luận bằng cách thêm vào giả thiết các sự kiện đã được khẳng định là đúng để làm được điều đó ta áp dụng một trong 2 phương pháp sau:

Pt1: (A,A=>B)/B  : Nếu A đúng và A kéo theo B đúng thì suy ra B đúng.

Nếu {A} thấy có mệnh đề A=>B trong tập luận thì bổ sung thêm A vào trong tập ban đầu.

Pt2: (7B,A=>B)/7A : Nếu B sai và A kéo theo B đúng thì suy ra A sai.

Nếu {7B} có mệnh đề A=>B trong tập luận thì bổ sung thêm 7A vào vào tập ban đầu.

3.Thuật toán

Input: GT và tập luận R chứa các luật có dạng P1^P2….^Pnà Q (luật khả hợp)

Output: kết quả suy diễn là thành công nếu mọi qi đều có thể suy diễn được nhờ áp dụng các tập luật

* thuật toán:

Procedure    suydien_tien;

Begin

     Tg:=GT;

     S:=lọc (R,Tg);{lọc từ trong R các luật P1^P2^..PnàQ sao cho P1,P2…Pn thuộc tg}

  While (KL không thuộc Tg)and(s# rỗng) do

            Begin

              Sàr;{Lấy luận r từ S, r có dạng}

              P1^P2^…^Pn àa                                 Tg:=Tg hợp {q};

              R:=R-{r}; S:=lọc (R,Tg);

            End;

   If KL thuộc Tg then Thanh cong

   Else

            That bai

End;

*VD:

GT={a,b}           KL={k}

R= r1:aàd                                           

      r2:a^b^dàc

      r3:b^càe

      r4:aàc

      r5:d^càf

      r6:e^fàk

      r7:e^a^càg

Cm       GTàKL:

Bo: Tg={a,b}; S={r1,r4}                       

B1: Áp dụng r1 à Tg{a,b,d}

R={r2,r3,r4,r5,r6,r7}

S={r2,r4}

B2: Áp dụng r2àTg{a,b,d,c}

            R={r3,r4,r5,r6,r7}

            S={r3,r4,r5}

B3: Áp dụng r3àTg(a,b,c,d,e}

            R={r4,r5,r6,r7}

            S={r4,r5,r7}

B4: Áp dụng r4àTg(a,b,c,d,e}

            R={r5,r6,r7}

            S={r5,r7}

B5: Áp dụng r5àTg(a,b,c,d,e,f}

            R={r6,r7}

            S={r6,r7}

B6: Áp dụng r6àTg(a,b,c,d,e,f,k}

            R={r7}

            S={r7}

KL thuộc Tg => đfcm

{a,b}-r1->{a,b,d}-r2->{a,b,c,d}-r3->{a,b,c,d,e}-r4->{a,b,c,d,e}-r5->{a,b,c,d,e,f}-r6->{a,b,c,d,e,f,k}=>KLà