RESOLUSITEKNIK INFERENSI

• Inferensi pada logika proporsional dapat menggunakan resolusi

• Harus dirubah dalam bentuk khusus: Conjunctive Normal Form (CNF)

• Ciri-ciri CNF:• Setiap kalimat adalah disjungsi literal• Semua kalimat terkonjungsi secara implisit

Konversi ke CNF

• Hilangkan implikasi dan ekuivalensi• x -> y menjadi x V y• x <-> y menjadi ( x V y) ( y V x)

• Kurangi lingkup semua negasi menjadi satu negasi saja (x) menjadi x (x V y) menjadi ( x y) (x y) menjadi (x V y)

• Gunakan aturan assosiatif dan distributif mengkonversi menjadi conjunction of disjunction• Asosiatif: (A V B) V C = A V (B V C)• Distributif: (A B) V C = (A V C) (B V C)

RESOLUSI

1. Konversi semua proposisi ke bentuk CNF2. Negasikan P (Goal), dan konversikan hasil negasi

tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yg telah ada pada langkah 1.

3. Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan lagi:

1. Seleksi 2 klausa sebagai klausa parent2. Bandingkan (resolve) secara bersama-sama. Klausa hasil

resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan –L, eliminir dari resolvent

3. Jika resolvent berupa klausa kosong, maka ditermukan kontradiksi. Jika tidak, tambahkan ke klausa yang telah ada

4. Kontradiksi -> Goal terbukti!

Contoh

Diketahui basis pengetahuan adalah:1. JIKA Budi anak yang cerdas DAN Budi rajin

belajar MAKA Budi menjadi juara kelas 2. JIKA Budi boleh main Playstation ATAU Budi

istirahatnya cukup MAKA Budi rajin belajar Fakta1. Budi anak yang cerdas2. Budi boleh main Playstation

• Buktikan apakah Budi bisa menjadi Juara Kelas!

• P = Budi anak yang cerdas• Q = Budi rajin belajar• R = Budi menjadi juara kelas• S = Budi boleh main Playstation• T = Budi istirahatnya cukup

1. P2. (P Q) -> R3. (S V T) -> Q4. S

Konversi logika ke bentuk CNF

Diketahui basis pengetahuan adalah:1. P2. (P Q) -> R : (P Q) V R

P V Q V R

3. (S V T) -> Q: (S V T) V Q (S T) V Q = (S V Q) ( T V Q)

4. SBuktikan kebenaran R!

Latihan

1. Andi adalah seorang mahasiswa2. Andi mahasiswa Paket B3. Setiap mahasiswa Paket B adalah mahasiswa elektro4. RE adalah mata kuliah yang sulit5. Setiap mahasiswa elektro pasti akan suka RE atau benci RE6. Setiap mahasiswa pasti akan suka suatu mata kuliah 7. Mahasiswa yang tidak pernah hadir pada kuliah mata kuliah

sulit, maka mereka pasti tidak suka mata kuliah tersebut8. Andi tidak pernah hadir matakuliah RE

Goal: Buktikan apakah Andi benci RE?

Logika Predikat

1. Mahasiswa(Andi)2. PaketB(Andi) 3. x: paketB(x) -> elektro(x)4. Mk_sulit(RE)5. x: elektro(x) -> suka(x,RE) V benci (x,RE)6. x: y: suka(x,y)7. x: y: mahasiswa(x)MK_sulit(y) hadir(x,y)

-> benci(x,y)8. hadir(Andi, RE) 9. Goal: benci (Andi, RE)

Rubah ke bentuk CNF dan buktikan Goal dengan teknik resolusi

CNF

1. Mahasiswa(Andi)2. PaketB(Andi)3. ~PaketB(X) V Elektro(X)4. MKsulit(RE)5. ~elektro(X) V MKsulit(Y) V benci(X,RE)6. Suka(X,Y)7. ~Mahasiswa(X) V ~MKsulit(Y) V hadir(X,Y) V

~suka(X,Y)8. ~hadir(Andi,RE)9. ~benci(Andi,RE)?

CNF

Resolusi