Contoh Pencarian Generate and Test

Metode ini merupakan pemggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal. Algoritma;

1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal)
2. Uji untuk melihat apakah node tersebut benar-benar merupak solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diaharapkan
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama

Contoh:

“Travelling Salesman Problem (TSP)” Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana setiap kota hanya boleh dikunjungin tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar dibawah ini:

Penyelesaian dengan metode Generate and Test

 

REPRESENTASI LOGIKA PREDIKAT

Logika Predikat adalah perluasan dari logika proposisi dimana objek yang di bicarakan dapat berupa anggota kelompok. Misalkan P(x) merupakan sebuah pernyataan yang mengandung variabel x dan D adalah sebuah himpunan. Kita sebut P sebuah fungsi proposisi (dalam D) jika untuk setiap x di D, P(x) adalah proposisi. Kita sebut D daerah asal pembicaraan (domain of discourse) dari P.

8.1. FUNGSI FUNGSI LOGIKA PREDIKAT

Berikut ini beberapa contoh fungsi proposisi:

1. n² + 2n adalah bilangan ganjil, dengan daerah asal himpunan bilangan bulat.
2. x² – x – 6 = 0, dengan daerah asal himpunan bilangan real.
3. Seorang pemain bisbol memukul bola melampaui 300 pada tahun 1974, dengan daerah asal himpunan pemain bisbol.

Sebuah predikat seringkali menyatakan sebuah hubungan relasional antara: konstanta, variabel dan fungsi.

8.2. LOGIKA DAN SET ORDER PERTAMA

Logika Predikat Order Pertama disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form).

Logika orde pertama adalah sistem resmi yang digunakan dalam matematika , filsafat ,linguistik , dan ilmu komputer . Hal ini juga dikenal sebagai orde pertama predikat kalkulus, semakin rendah kalkulus predikat, teori kuantifikasi, dan logika predikat. Logika orde pertama dibedakan dari logika proposisional oleh penggunaan variabel terukur .

Syarat-syarat symbol dalam logika predikat :

• himpunan huruf, baik huruf kecil maupun huruf besar dalam abjad.
• Himpunan digit (angka) 0,1,2,…9
• Garis bawah “_”
• Symbol-simbol dalam logika predikat dimulai dengan sebuah huruf dan diikuti oleh sembarang rangkaian karakter-karakter yang diijinkan.
• Symbol-simbol logika predikat dapat merepresentasikan variable, konstanta, fungsi atau predikat

 Logika Predikat Order Pertama terdiri dari :

Konstanta: objek atau sifat dari semesta pembicaraan. Penulisannya diawali dengan huruf kecil, seperti : pohon, tinggi. Konstanta true(benar) dan false(salah) adalah symbol kebenaran (truth symbol).

Variable : digunakan untuk merancang kelas objek atau sifat-sifat secara umum dalam semesta pembicaraan. Penulisannya diawali dengan huruf besar, seperti : Bill, Kate.

Fungsi : pemetaan (mapping) dari satu atau lebih elemen dalam suatu himpunan yang disebut domainfungsi ke dalam sebuah elemen unik pada himpunan lain yang disebut rangefungsi. Penulisannya dimulai dengan huruf kecil. Suatu ekspresi fungsi merupakan symbol fungsi yang diikuti argument.

Argument adalah elemen-elemen dari fungsi, ditulis diapit tanda kurung dan dipisahkan dengan tanda koma.

Predikat: menamai hubungan antara nol atau lebih objek dalam semesta pembicaraan. Penulisannya dimulai dengan huruf kecil, seperti : equals, sama dengan, likes, near.

Contoh kalimat dasar :

teman(george,allen)

teman(ayah_dari(david),ayah_dari(andrew))

dimana:

argument : ayah_dari(david) adalah george

argument : ayah_dari(andrew) adalah allen

predikat : teman

8.3. QUANTIFIER UNIVERSAL

Dalam logika predikat , quantifieri universal merupakan jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “diberi” atau “untuk semua”. Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setiapanggota dari domain wacana. Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setiap anggota domain. Ini menegaskanbahwa predikat dalam lingkup dari quantifier universal benar dari setiap nilai dari variabel predikat .

Hal ini biasanya dilambangkan dengan berbalik A (∀) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier universal  (“∀x”, “∀ (x)”, atau kadang-kadang dengan “(x) “saja). Kuantifikasi Universal berbeda dari kuantifikasi eksistensial (“ada ada”), yang menegaskan bahwa properti atau relasi hanya berlaku untuk setidaknya satu anggota dari domain.

Contoh 1 :

(∀x) (x + x = 2x)

“untuk setiap x (dimana x adalah suatu bilangan), kalimat x + x = 2x adalah benar.”

Contoh 2 :

(∀x) (p) (Jika x adalah seekor kelinci -> x adalah binatang).

Kebalikan kalimat “bukan kelinci adalah binatang” ditulis :

(∀x) (p) (Jika x adalah seekor kelinci -> ~x adalah binatang)

dan dibaca :

– “setiap kelinci adalah bukan binatang”

“semua kelinci adalah bukan binantang”

8.4. QUANTIFIER EXISTENSIAL

Dalam logika predikat , suatu quantifier eksistensial adalah jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “ada ada,” “ada setidaknya satu,” atau “untuk beberapa.” Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setidaknya satu anggota dari domain wacana . Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setidaknya satu anggota dari domain. Ini menegaskan bahwa predikat dalamlingkup dari quantifier eksistensial adalah benar dari setidaknya satu nilai darivariabel predikat .

Hal ini biasanya dilambangkan dengan E berubah (∃) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier eksistensial (“∃x” atau “∃ (x)”) Kuantifikasi eksistensial.

Contoh 1 :

(∃x) (x . x = 1)

Dibaca : “terdapat x yang bila dikalikan dengan dirinya sendiri hasilnya sama dengan 1.”

Contoh 2 :

(∃x) (panda(x) ∧ nama(Clyde))

Dibaca : “beberapa panda bernama Clyde”.

Contoh 3 :

(∀x) (jerapah(x) -> berkaki empat(x))

Dibaca : “semua jerapah berkaki empat”.

Universal quantifier dapat diekspresikan sebagai konjungsi.

(∃x) (jerapahh(x) ∧ berkaki tiga(x))

Dibaca : “ada jerapah yang berkaki tiga”

Existensial quantifier dapat diekspresikan sebagai disjungsi dari

urutan ai. P(a1) ∨ P(a2) ∨ P(a3) …∨ P(aN)

8.5. RESOLUSI LOGIKA PREDIKAT

Resolusi pada logika predikat pada dasarnya sama dengan resolusi pada logika proposisi, hanya saja ditambah dengan unifikasi.Pada logika predikat, prosedur untuk membuktikan pernyataan P dengan beberapa pernyataan F yang telah diketahui, dengan menggunakan resolusi, dapat dilakukan melalui algoritma sebagai berikut :

1.      Konversikan semua proposisi F ke bentuk klausa

2.      Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa.Tambahkan   kehimpunan klausa yang telah ada pada langkah

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

·         Seleksi 2 klausa sebagai klausa parent

·         Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut  resolvent. Jika ada pasangan literal T dan ¬T2 sedemikian hingga keduanya dapat dilakukan unifikasi, maka salah satu T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari 1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent

·         Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada

Contoh kasus :

Misalkan terdapat pernyataan-pernyataan sebagai berikut :

1.      Fajar adalah seorang mahasiswa

2.      Fajar masuk Jurusan Elektro

3.      Setiap mahasiswa elektro pasti mahasiswa Teknik

4.      Kalkulus adalah matakuliah yang sulit

5.      Setiap mahasiswa teknik pasti akan suka kalkulus atau akan membencinya

6.      Setiap mahasiswa pasti akan suka terhadap suatu matakuliah

7.      Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka terhadap matakuliah tersebut

8.      Fajar tidak pernah hadir kuliah matakuliah kalkulus

Maka harus terlebih dahulu diubah ke dalam bentuk klausa sebagai berikut :

1. Mahasiswa (Fajar)

2. Elektro (Fajar)

3.¬ Elektro (x1) v Teknik (v1)

4. Sulit (Kalkulus)

5.¬ Teknik (x2) v suka (x2, Kalkulus) v benci (x2, Kalkulus)

6. Suka (x3, f1 (x3))

7.¬ Mahasiswa (x4) v ¬ sulit (y1) v hadir (x4, y1) v ¬ suka (x4, y1)

8.¬ Hadir (Fajar, Kalkulus)

 

 

Daftar Pustaka

https://ismailakbar12.wordpress.com/2015/06/25/makalah-artifical-intellegent-representasi-pengetahuan/

http://pakarbelajar.blogspot.co.id/2009/08/5-fungsi-predikat-dan-kalimat.html

http://afifrahma.blogspot.co.id/2013/01/resolusi-untuk-logika-predikat.html