Bài giảng Trí tuệ nhân tạo - Logic mệnh đề

Nội dung text: Bài giảng Trí tuệ nhân tạo - Logic mệnh đề

1. TRÍ TU NHÂN TO Logic Mnh ð
2. Ni dung trình bày 2
   Gii thiu v logic
   Logic mnh đ
   Cú pháp logic mnh đ
   Ng nghĩa logic mnh đ
   Suy dn trong logic mnh đ
   Chng minh trong logic mnh đ
3. Logic 3
   Cn mt cơng c đ biu din và s dng tri thc ca con ngưi
   Logic: “khoa hc v lp lun, chng minh, suy nghĩ hay suy din”
   S dng logic làm mt cơng c đ biu din và x lý tri thc
4. Logic là gì? 4
   Mt ngơn ng hình thc
   Cú pháp: Biu thc nào là hp l
   Ng nghĩa: Biu thc hp l cĩ ý nghĩa gì
   H chng minh: mt cách x lý các biu thc cĩ cú pháp đ cĩ đưc các biu thc cĩ cú pháp khác (cho ta bit đưc thơng tin mi )
   Chng minh đ làm gì:
   T các quan sát => kt lun v th gii
   Trng thái hin ti & hành đng => thuc tính ca trng thái k tip
   Hai loi logic : logic mnh đ (đơn gin) và logic v t (phc tp hơn).
5. Cú pháp Logic Mnh đ 5
   Cú pháp: Là nhng gì đưc cho phép vit
   (C++): for (int i=0; i< n; i++)
   (Ting Vit): Cơm ăn tơi rt ngon.
   Câu (sentence) trong logic mnh đ:
   true và false là các câu
   Các bin mnh đ là các câu: P, Q, R, Z
   Nu α, β là các câu thì ¬α, α ∧ β, α ∨ β, α ⇒ β, α ⇔ β cũng là các câu
   Ngồi ra, khơng cĩ mt câu nào na
6. ð ưu tiên 6 ¬¬¬ Cao nht A ∨ B ∧ C A ∨ (B ∧ C) ∧∧∧ ∨∨∨ A ∧ B ⇒ C ∨ D (A ∧ B) ⇒ (C ∨ D) ⇒⇒⇒ A ⇒ B ∨ C ⇔ D (A ⇒ (B ∨ C)) ⇔ D ⇔ Thp nht
   Lut ưu tiên cho phép các dng vit tt ca các câu, nhưng chính thc ch cĩ dng đy đ du ngoc mi hp l.
   Các dng nhp nhng v cú pháp đưc cho phép vit tt ch khi chúng tương đương ng nghĩa: A ∧ B ∧ C tương đương vi (A ∧ B) ∧ C và A ∧ (B ∧ C)
7. Ng nghĩa 7
   Nghĩa ca mt câu là mt chân tr {t, f}
   Th hin là vic gán mt các chân tr cho các bin mnh đ
   holds (α,i) [câu α là t trong th hin i] [câu α đúng trong th hin i]
   fails (α,i) [câu α là f trong th hin i] [câu α sai trong th hin i]
8. Các lut ng nghĩa 8
   holds(true , i) vi mi i
   fails(false , i) vi mi i
   holds( ¬α, i) nu và ch nu ( iff ) fails(α,i)
   holds(α∧β,i) iff holds(α,i) và holds(β,i) ni lin
   holds(α∨β,i) iff holds(α,i) hay holds(β,i) ni ri Th hin i dưi dng bng tra, P là bin mnh đ:
   holds(P,i) iff i(P) = t
   fails(P,i) iff i(P) = f
9. Mt s dng vit tt quan trng 9
   α ⇒ β ≡ ¬α ∨ β (điu kin, kéo theo) tin đ ⇒ kt lun
   α ⇔ β ≡ (α ⇒ β) ∧ (β ⇒ α) (tương đương)
10. Bng chân tr 10 PQ ¬PP∧QP∨Q P⇒QQ⇒PP⇔Q f f t f f t t t f t t f t t f f t f f f t f t f t t f t t t t t
11. Tính hp l và tha mãn đưc 11
    Mt câu là hp l nu và ch nu chân tr ca nĩ là t trong tt c th hin Câu hp l: true , ¬false , P ∨ ¬P
    Mt câu là tha mãn đưc nu và ch nu chân tr ca nĩ là t trong ít nht mt th hin Câu tha mãn đưc: P, true , ¬P
    Mt câu là khơng tha mãn đưc nu và ch nu chân tr ca nĩ là f trong tt c th hin Câu khơng tha mãn đưc: P ∧ ¬P, false , ¬true
12. Ví d 12 Th hin làm cho Câu Hp l? chân tr ca câu = f k ⇒ k hp l k ∨ ¬k tha mãn đưc, ⇒ k= t, l = f k l nhưng khơng hp l tha mãn đưc, k= f, l= t ⇒ ¬ ⇒ ¬ k ⇒ l ⇒ (¬k ⇒ ¬l) nhưng khơng hp l k l = t, k l = f phn chng hp l k ⇒ l ⇒ (¬l ⇒ ¬k)
13. Tính tha mãn đưc 13
    Cho trưc mt câu S, c gng tìm mt th hin i sao cho holds (S, i)
    Tương t vic tìm mt phép gán các giá tr cho các bin sao cho các ràng buc tha
    Các phương pháp vét cn: lit kê tt c các th hin và kim tra
    Các phương pháp tt hơn:
    tìm kim heuristic
    lan truyn ràng buc
    tìm kim ngu nhiên
14. Mt ví d: Bài ging tt? 14 Gi s ta bit rng:
    Nu hơm nay tri nng, thì Tomas s vui v (S ⇒ H)
    Nu Tomas vui v, bài ging s tt (H ⇒ G)
    Hơm nay tri nng (S) Ta cĩ th kt lun rng bài ging s tt?
15. Kim tra các Th hin 15 SHG Vi 3 bin, ta cĩ tt c t t t 8 th hin cĩ th t t f t f t t f f f t t f t f f f t f f f
16. Kim tra các Th hin 16 SHG S ⇒ H H ⇒ GS Trong đĩ, ch cĩ 1 t t t t t t th hin tha tt c các câu trong cơ s t t f t f t tri thc: t f t f t t S ⇒ H = true t f f f t f H ⇒ G = true f t t t t f S = true f t f t f f f f t t t f f f f t t f
17. Kim tra các Th hin 17 SHG S ⇒ H H ⇒ GS Và G cũng đúng trong t t t t t t th hin đĩ t t f t f t t f t f t t t f f f t f f t t t t f f t f t f f f f t t t f f f f t t f
18. Thêm mt bin 18 Gi s ta thêm mt bin: L SHG S ⇒ H H ⇒ GS Leslie vui v (L) t t t t t t t t t t f t f t Cĩ 2 th hin tha KB t t f t f t t t t f f f t f t f t t t t f Và chúng cũng tha G t f t f t f f t f f t t t f t f f f t t f f t t t t t t f t t f t f t
19. Thêm mt bin 19 L SHG S ⇒⇒⇒ H H ⇒⇒⇒ GS Gi s ta thêm mt bin: Leslie vui v (L) t t t t t t t t t t f t f t Cĩ 2 th hin tha KB t t f t f t t t t f f f t f t f t t t t f Và chúng cũng tha G t f t f t f f t f f t t t f t f f f t t f f t t t t t t f t t f t f t
20. Suy dn (Entailment) 20
    Mt cơ s tri thc (KB) suy dn (entails) mt câu α nu và ch nu mi th hin làm cho KB đúng cũng làm cho α đúng. Ký hiu: KB╞ α KB Suy dn α ðúng ðúng Th hin Tp con Th hin
21. Suy dn bng cách lit kê 21
    Lit kê tt c th hin
    Chn nhng th hin mà tt c thành phn ca KB là đúng
    Kim tra xem α cĩ đúng trong tt c các th hin này khơng
    Vi n bin, đ phc tp thi gian là O(2 n), đ phc tp khơng gian là O(n)
22. Suy dn và chng minh 22
    Chng minh là cách kim tra xem mt KB cĩ suy dn mt câu α hay khơng mà khơng cn lit kê tt c các th hin cĩ th Chng minh KB Suy dn α ðúng ðúng Th hin Tp con Th hin
23. Chng minh 23
    Mt chng minh là mt chui các câu
    Câu đu tiên là các tin đ (KB)
    Sau đĩ, ta cĩ th vit đưc dịng k tip là kt qu ca vic áp dng mt lut suy dn lên dịng trưc
    Khi α xut hin trên dịng, ta đã chng minh α t KB
    Nu các lut suy dn là đúng , thì bt kỳ α cĩ th chng minh t KB cũng suy dn đưc bi KB
    Nu các lut suy dn là đ , thì bt kỳ α nào cĩ th đưc suy dn bi KB cũng cĩ th đưc chng minh t KB
24. Suy din t nhiên 24
    Mt s lut suy din α ⇒ β α ⇒ β α α ∧ β α ¬β β β ¬α α ∧ β α Modus Modus And And ponens tolens Introduction Elimination
25. Ví d suy din t nhiên 25 Chng minh S Bưc Cơng thc Ngun gc 1 P ∧ Q Cho trưc 2 P ⇒ R Cho trưc 3 Q ∧ R ⇒ S Cho trưc
26. Ví d suy din t nhiên 26 Chng minh S Bưc Cơng thc Ngun gc 1 P ∧ Q Cho trưc 2 P ⇒ R Cho trưc 3 Q ∧ R ⇒ S Cho trưc 4 P 1 AndElim
27. Ví d suy din t nhiên 27 Chng minh S Bưc Cơng thc Ngun gc 1 P ∧ Q Cho trưc 2 P ⇒ R Cho trưc 3 Q ∧ R ⇒ S Cho trưc 4 P 1 AndElim 5 R 4,2 Modus Ponens
28. Ví d suy din t nhiên 28 Chng minh S Bưc Cơng thc Ngun gc 1 P ∧ Q Cho trưc 2 P ⇒ R Cho trưc 3 Q ∧ R ⇒ S Cho trưc 4 P 1 AndElim 5 R 4,2 Modus Ponens 6 Q 1 AndElim
29. Ví d suy din t nhiên 29 Chng minh S Bưc Cơng thc Ngun gc 1 P ∧ Q Cho trưc 2 P ⇒ R Cho trưc 3 Q ∧ R ⇒ S Cho trưc 4 P 1 AndElim 5 R 4,2 Modus Ponens 6 Q 1 AndElim 7 Q ∧ R 5,6 AndIntro
30. Ví d suy din t nhiên 30 Chng minh S Bưc Cơng thc Ngun gc 1 P ∧ Q Cho trưc 2 P ⇒ R Cho trưc 3 Q ∧ R ⇒ S Cho trưc 4 P 1 AndElim 5 R 4,2 Modus Ponens 6 Q 1 AndElim 7 Q ∧ R 5,6 AndIntro 8 S 3,7 Modus Ponens
31. Các h thng chng minh 31
    Cĩ nhiu h thng suy din t nhiên; chúng thưng là các “chương trình kim tra chng minh”, đúng nhưng khơng đ
    Suy din t nhiên dùng nhiu lut suy din gây nên mt h s phân nhánh ln trong vic tìm mt chng minh.
    Thơng thưng, ta cn dùng “chng minh theo trưng hp” thm chí cịn phân nhánh nhiu hơn VD: cn chng minh R t (P ∨ Q), (P ⇒ R) và (Q ⇒ R).
32. Hp gii mnh đ 32
    Lut hp gii: α ∨ β ¬β ∨ γ α ∨ γ
    Lut hp gii đơn l là mt h chng minh đúng và đ
    ðịi hi tt c các câu đưc chuyn sang dng chun hi
33. Các h thng logic 33
    H thng suy din tin
    H thng suy din lùi
    H thng da trên hp gii s tip tc trong bài sau
34. Thc mc 34