9. Inferensi Dalam Logika Order Pertama

January 02, 2017

9. Inferensi Dalam Logika Order Pertama

9.1 Mengubah Inferensi Order Pertama Menjadi Inferensi Proposisi

Inferensi pada logika proposisi dapat dilakukan dengan menggunakan resolusi. RESOLUSI adalah suatu aturan untuk melakukan inferensi yg dapat berjalan secara efisien dalam suatu bentuk khusus yg disebut Conjunctive Normal Form (CNF).

• CNF ini memiliki ciri-ciri sebagai berikut :

– Setiap kalimat merupakan disjungsi literal

– Semua kalimat terkonjungsi secara implisit

• Dua atau lebih proposisi dapat digabungkan dengan menggunakan operator logika :

a. Negasi : Ø (NOT)

b. Konjungsi : Ù (AND)

c. Disjungsi : Ú (OR)

d. Implikasi : ® (IF-THEN)

e. Ekuivalen : Û

• Operator NOT : Digunakan untuk memberikan nilai negasi (lawan) dari pernyataan yang telah ada.

• Langkah-langkah mengubah kalimat ke dalam bentuk CNF, sebagai berikut :

> Hilangkan implikasi dan ekuivalensi

mis. X ® Y menjadi ØX Ú Y (hukum implikasi)

X Û Y menjadi (X=>Y) Ù (Y=>X) (hukum bi-implikasi)

(ØX Ú Y)Ù(ØY Ú X) (hukum implikasi)

> Kurangi lingkup semua negasi menjadi satu negasi saja

mis. Ø(Ø X) menjadi X (hukum negasi ganda)

Ø(X Ú Y) menjadi (ØX Ù ØY) (hukum de’Morgan)

Ø(X Ù Y) menjadi (ØX Ú ØY) (hukum de’Morgan)

> Gunakan aturan assosiatif dan distributif untuk mengkonversi menjadi conjunction of disjunction

mis. Assosiatif : (A Ú B) Ú C = A Ú (B Ú C)

Distributif : (A Ù B) Ú C = (A Ú C) Ù (B Ú C)

• Algoritma Resolusi

Input : Serangkaian clauses yang disebut axioma dan tujuannya.

Output : Uji apakah tujuan diturunkan dari axioma

Begin

1. Kembangkan serangkaian pernyataan axioma termasuk tujuan yang dinegasikan.

2. Representasikan tiap elemen statemen ke dalam Conjunctive Normal Form (CNF)

berdasarkan langkah-langkah berikut :

Ø Hilangkan operator “if-then” dengan operasi NEGATION dan OR berdasarkan hukum logika.

Algoritma Resolusi

Input : serangkaian clauses yang disebut axioma dan tujuannya.

Output :uji apakah tujuan diturunkan dari axioma

3. Repeat

a) Pilih dua clauses mana saja dari S, sehingga satu clause berisi literal yang dinegasikan dan clause yang lainnya berisi literal positif yang berhubungan (literal yang tidak dinegasikan).

b) Pisahkan dua clauses ini dan panggil clause yang dihasilkan (resolvent). Hapus parent clause dari S.

Until sebuah clause null dihasilkan atau tidak ada progress lebih lanjut yang bisa dibuat.

4. Jika sebuah clause null dihasilkan, maka “tujuan terbukti” atau pernyataan “valid”.

9.2. Unifikasi

Unifikasi adalah usaha untuk mencoba membuat dua ekspresi menjadi identik (mempersatukan keduanya) dengan mencari substitusi-substitusi tertentu untuk mengikuti peubah-peubah dalam ekspresi mereka tersebut. Unifikasi merupakan suatu prosedur sistematik untuk memperoleh peubah-peubah instan dalam wffs. Ketika nilai kebenaran predikat adalah sebuah fungsi dari nilai-nilai yang diasumsikan dengan argumen mereka, keinstanan terkontrol dari nilai-nilai selanjutnya yang menyediakan cara memvalidasi nilai-nilai kebenaran pernyataan yang berisi predikat. Unifikasi merupakan dasar atas kebanyakan strategi inferensi dalam Kecerdasan Buatan. Sedangkan dasar dari unifikasi adalah substitusi.

Suatu substitusi (substitution) adalah suatu himpunan penetapan istilah-istilah kepada peubah, tanpa ada peubah yang ditetapkan lebih dari satu istilah. Sebagai pengetahuan jantung dari eksekusi Prolog, adalah mekanisme unifikasi.

Aturan-aturan unifikasi :

1. Dua atom (konstanta atau peubah) adalah identik.

2. Dua daftar identik, atau ekspresi dikonversi ke dalam satu buah daftar.

3. Sebuah konstanta dan satu peubah terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.

4. Sebuah peubah tak terikat diperssatukan dengan sebuah peubah terikat.

5. Sebuah peubah terikat dipersatukan dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta tidak ada konflik.

6. Dua peubah tidak terikat disatukan. Jika peubah yang satu lainnya menjadi terikat dalam upa-urutan langkah unifikasi, yang lainnya juga menjadi terikat ke atom yang sama (peubah atau konstanta).

7. Dua peubah terikat disatukan jika keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah atau konstanta).

9.3. Generalized Modus Ponens (GMP)

Kaidah dasar dalam menarik kesimpulan dari dua nilai logika tradisional adalahmodus ponens, yaitu kesimpulan tentang nilai kebenaran pada B diambil berdasarkan kebenaran pada A. Sebagai contoh, jika A diidentifikasi dengan “tomat itu merah” danB dengan “tomat itu masak”, kemudian jika benar kalau “tomat itu merah” maka “tomat itu masak”, juga benar. Konsep ini digambarkan sebagai berikut:

Premis 2 (kenyataan)	:	x adalah A,
Premis 2 (kaidah)	:	jika x adalah A maka y adalah B.
Consequence (kesimpulan)	:	y adalah B.

Secara umum dalam melakukan penalaran, modus ponens digunakan dengan cara pendekatan. Sebagai contoh, jika ditemukan suatu kaidah implikasi yang sama dengan “jika tomat itu merah maka tomat itu masak”, misalnya “tomat itu kurang lebih merah,” maka dapat disimpulkan “tomat itu kurang lebih masak”, hal ini dapat dituliskan seperti berikut:

Premis 1 (kenyataan)	:	x adalah A’,
Premis 2 (kaidah)	:	jika x adalah A maka y adalah B.
Consequence (kesimpulan)	:	y adalah B’.

Dengan A’adalah dekat ke A dan B’adalah dekat ke B. Ketika A, B, A’ dan B’adalah himpunan fuzzy dari semesta yang berhubungan, maka penarikan kesimpulan seperti tersebut dinamakan penalaran dengan pendekatan (approximate reasoning) yang disebut juga dengan generalized modus ponens (GMP).

9.4. Rangkaian Forward dan backward

Forward chaining merupakan metode inferensi yang melakukan penalaran dari suatu masalah kepada solusinya. Jika klausa premis sesuai dengan situasi (bernilai TRUE), maka proses akan menyatakan konklusi. Forward chaining adalah data-driven karena inferensi dimulai dengan informasi yang tersedia dan baru konklusi diperoleh. Jika suatu aplikasi menghasilkan tree yang lebar dan tidak dalam, maka gunakan forward chaining.

Contoh :

Terdapat 10 aturan yang tersimpan dalam basis pengetahuan yaitu :

R1 : if A and B then C

R2 : if C then D

R3 : if A and E then F

R4 : if A then G

R5 : if F and G then D

R6 : if G and E then H

R7 : if C and H then I

R8 : if I and A then J

R9 : if G then J

R10 : if J then K

Fakta awal yang diberikan hanya A dan E, ingin membuktikan apakah K bernilai benar. Proses penalaran forward chaining terlihat pada gambar dibawah :

Backward Chaining

Menggunakan pendekatan goal-driven, dimulai dari harapan apa yang akan terjadi (hipotesis) dan kemudian mencari bukti yang mendukung (atau berlawanan) dengan harapan kita. Sering hal ini memerlukan perumusan dan pengujian hipotesis sementara. Jika suatu aplikasi menghasilkan tree yang sempit dan cukup dalam, maka gunakan backward chaining.

Contoh :

Seperti pada contoh forward chining, terdapat 10 aturan yang sama pada basis pengetahuan dan fakta awal yang diberikan hanya A dan E. ingin membuktikan apakah K bernilai benar. Proses penalaran backward chaining terlihat pada gambar berikut :