SISTEM CERDAS
POKOK BAHASAN : METODE PENCARIAN DAN PELACAKAN 2 (HEURISTIK)
5.1 BEST FIRST SEARCH
Pencarian terbaik pertama (Best First Search)
merupakan suatu cara yang menggabungkan keuntungan atau kelebihan dari
pencarian Breadth-First Search dan Depth-First Search.
Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node
dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang
kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan
penggantinya.
5.2 Problem Reduction
Ketika masalah
dapat dibagi menjadi serangkaian sub masalah, di mana masing-masing sub masalah
dapat diselesaikan secara terpisah dan kombinasi ini akan menjadi solusi,
DAN-OR grafik atau AND - OR pohon digunakan untuk mewakili solusi. Dekomposisi
masalah atau masalah pengurangan menghasilkan DAN busur. Satu DAN yang mungkin
menunjukkan sejumlah node penggantinya. Semua ini harus diselesaikan sehingga
busur akan naik ke banyak busur, menunjukkan beberapa solusi yang mungkin. Maka
grafik ini dikenal sebagai DAN - OR bukannya DAN. Gambar menunjukkan DAN - OR
grafik.
5.3 Constraint Satisfaction
Merupakan masalah
matematika didefinisikan sebagai satu set objek yang negara harus memenuhi
sejumlah kendala atau keterbatasan. CSP mewakili entitas dalam masalah karena
koleksi homogen kendala terbatas lebih variabel, yang diselesaikan dengan
metode kepuasan kendala. CSP adalah subjek penelitian intensif di kedua
kecerdasan dan riset operasi buatan, karena keteraturan dalam formulasi mereka
memberikan dasar umum untuk menganalisis dan memecahkan masalah dari banyak
keluarga yang tampaknya tidak berhubungan. CSP sering menunjukkan kompleksitas
tinggi, membutuhkan kombinasi heuristik dan metode pencarian kombinasi yang
harus diselesaikan dalam waktu yang wajar. Masalah satisfiability Boolean
(SAT), teori-teori satisfiability modulo (SMT) dan menjawab mengatur
pemrograman (ASP) secara kasar dapat dianggap sebagai bentuk tertentu dari
masalah kepuasan kendala.
5.4 Means End Analysis
Sarana-Ends
Analysis (MEA) adalah teknik pemecahan masalah yang umum digunakan dalam
Artificial Intelligence (AI) untuk membatasi pencarian dalam program AI.
Ini juga
merupakan teknik yang digunakan setidaknya sejak tahun 1950-an sebagai alat
kreativitas, paling sering disebutkan dalam buku rekayasa pada metode desain.
MEA juga terkait dengan Sarana-Ends Pendekatan Rantai digunakan umumnya dalam
analisis perilaku konsumen. Ini juga merupakan cara untuk memperjelas
pikiran seseorang ketika memulai sebuah bukti matematis.
POKOK BAHASAN : RESPRESENTASI PENGETAHUAN
6 REPRESENTASI PENGETAHUAN
- Propositional Logic (Logika
Proposisi)
Suatu
Proposisi merupakan suatu statemen atau pernyataan yang menyatakan benar (TRUE)
atau salah (FALSE). Dalam PropositionalLogic fakta dilambangkan
dengan simbol misalnya P, Q dan R.Lambang-lambang
tersebut dihubungkan dengan relasi-relasi logika
Tabel
Kebenaran Logika
- Predicate Logic (Logika Predikat)
Pada logika
predikat proposisi dibedakan menjadi argumen (obyek) dan predikat (keterangan).
Secara umum penulisan proposisi dalam logika predikat dapat dinyatakan sebagai
berikut:
Contoh
Silsilah Keluarga yang dipresentasikan dalam Prolog
Jika silsilah di
atas dibentuk dalam Representasi Logika, sebagai berikut:
|
Book Frame
|
|
Slot à Subslots
|
|
Title à AI. A modern
Approach
Author à Russell & Norvig
Year à 2003
|
Contoh di atas
dibentuk dalam Frame:
|
Nama Frame:
Burung
|
|
|
Orangtua
|
Hewan
|
|
Anak
|
Kenari, Pipit
|
|
Mempunyai
|
Sayap
|
|
Cara Berpindah
tempat
|
Terbang
|
4. . Script (Naskah)
Conceptual
Dependency (ketergantungan
konseptual) adalah teori tentang bagaimana mempresentasikan pengetahuan tentang
event (kejadian) yang biasanya terkandung dalam kalimat bahasa natural.
Contoh:
representasi Conceptual Dependency
“Budi memberi
Atika sebuah buku”
Script adalah skema representasi pengetahuan yang
menggambarkan urutan-urutan kejadian (sequence of events). Script dilengkapi
dengan elemen-elemen agar lebih memudahkan dalam memahami urutan kejadian.
a. Track/Jalur: variasi yang mungkin terjadi
dalam script
b. Kondisi Input: situasi yang harus dipenuhi
sebelum sesuatu kejadian terjadi
c. Prop/Pendukung: objek pendukung yang
digunakan dalam urutan peristiwa yang
terjadi
d. Role/Peran: orang-orang yang terlibat
dalam suatu peran
e. Scene/Adegan: urutan peristiwa aktual
f. Hasil: kondisi akhir yang terjadi setelah
urutan peristiwa dalam script terjadi
5. Aturan Produksi (Kaidah Produksi)
Pengetahuan dalam kaidah produksi direpresentasikan dalam
bentuk
JIKA [kondisi]
MAKA [Aksi]
JIKA [premis] MAKA
[Konklusi]
Aturan
Produksi (kaidah produksi) adalah salah satu representasi pengetahuan yang menghubungkan premis
dengan konklusi.
Bentuknya: If Premis Then Konklusi
Konklusi pada
bagian then bernilai benar jika premis pada bagian if bernilai
benar.
Contoh:
If hari ini hujan then saya
tidak kuliah.
1. LOGIKA DAN SET
Representasi pengetahuan dengan symbol logika merupakan
bagian dari penalaran eksak. Bagian yang paling penting dalam penalaran adalah
mengambil kesimpulan dari premis. Logika dikembangkan oleh filusuf Yunani,
Aristoteles (abad ke 4 SM) didasarkan pada silogisme, dengan dua premis dan
satu konklusi.
Contoh :
- Premis
: Semua laki-laki adalah makhluk hidup
- Premis
: Socrates adalah laki-laki
- Konklusi
: Socrates adalah makhluk hidup
Cara lain merepresentasikan pengetahuan adalah dengan
Diagram Venn.
Objek dalam himpunan disebut elemen.
- A
={1,3,5,7}
- B =
{….,-4,-2,0,2,4,…..}
- C =
{pesawat, balon}
Symbol epsilon ε menunjukkan bahwa suatu elemen merupakan
anggota dari suatu himpunan, contoh : 1 ε A . Jika suatu elemen bukan anggota
dari suatu himpunan maka symbol yang digunakan ∉, contoh : 2 ∉
A.
Jika suatu himpunan sembarang, misal X dan Y didefinisikan
bahwa setiap elemen X merupakan elemen Y, maka X adalah subset dari Y,
dituliskan : X ⊂ Y atau Y ⊃ X.
Operasi-operasi Dasar dalam Diagram Venn:
- Interseksi
(Irisan)
C = A ∩ B C = {x ∈ U | (x ∈ A) ∧
(x ∈
B)}
Dimana :
∩ menyatakan irisan himpunan
| dibaca “sedemikian hingga”
∧ operator logika AND
Dimana :
∩ menyatakan irisan himpunan
| dibaca “sedemikian hingga”
∧ operator logika AND
- Union
(Gabungan)
C = A ∪ B C = {x ∈ U | (x ∈ A) ∨ (x ∈ B)}
Dimana :
∪ menyatakan gabungan himpunan
∨ operator logika OR
- Komplemen
A’ = {x ∈ U | ~(x ∈ A) }
Dimana :
’ menyatakan komplemen himpunan
~ operator logika NOT
2. OPERATOR LOGIKA
Operator Boolean atau Operator Logika adalah operator yang digunakan untuk melakukan operasi logika yaitu operator yang menghasilkan nilai TRUE (benar) atau FALSE (salah).
Bebarapa macam operator logika antara lain:
- and :
menghasilkan nilai TRUE jika kedua operand bernilai TRUE
- or :
menghasilkan nilai TRUE jika salah satu operand bernilai TRUE
- xor :
menghasilkan nilai TRUE jika salah satu operand bernilai TRUE tetapi bukan
keduaduanya bernilai TRUE
- ! :
mengasilkan nilai tidak TRUE
- &&
: menghasilkan nilai TRUE jika kedua operand bernilai TRUE
- || :
menghasilkan nilai TRUE jika salah satu operand bernailai TRUE
3. TAUTOLOGI, KONTRADIKSI DAN CONTINGENT
- Tautologi
Tautologi adalah pernyataan majemuk yang selalu benar untuk
semua kemungkinan nilai kebenaran dari pernyataan-pernyataan komponennya.
Sebuah Tautologi yang memuat pernyataan Implikasi disebut Implikasi Logis.
Untuk membuktikan apakah suatu pernyataan Tautologi, maka ada dua cara yang
digunakan. Cara pertama dengan menggunakan tabel kebenaran, yaitu jika semua
pilihan bernilai B (benar) maka disebut Tautologi, dan cara kedua yaitu dengan
melakukan penjabaran atau penurunan dengan menerapkan sebagian dari 12 hukum-hukum
Ekuivalensi Logika.
Contoh:
Lihat pada argumen berikut:
Jika Tono pergi kuliah, maka Tini juga pergi kuliah. Jika
Siska tidur, maka Tini pergi kuliah. Dengan demikian, jika Tono pergi kuliah
atau Siska tidur, maka Tini pergi kulah.
Diubah ke variabel proposional:
- Tono
pergi kuliah
- Tini
pergi kuliah
- Siska
tidur
Diubah lagi menjadi ekspresi logika yang terdiri dari
premis-premis dan kesimpilan. Ekspresi logika 1 dan 2 adalah premis-premis,
sedangkan ekspresi logika 3 adalah kesimpulan.
- A → B
(Premis)
- C → B
(premis)
- (A V
C) → B (kesimpulan)
Maka sekarang dapat ditulis: ((A → B) ʌ (C → B)) → ((A V C)
→ B
|
A
|
B
|
C
|
A → B
|
C → B
|
(A → B) ʌ (C → B)
|
A V C
|
(A V C) → B
|
|
|
B
B
B
B
S
S
S
S
|
B
B
S
S
B
B
S
S
|
B
S
B
S
B
S
B
S
|
B
B
S
S
B
B
B
B
|
B
B
S
B
B
B
S
B
|
B
B
S
S
B
B
S
B
|
B
B
B
B
B
S
B
S
|
B
B
S
S
B
B
S
B
|
B
B
B
B
B
B
BB
|
Dari tabel kebenaran diatas menunjukkan bahwa pernyataan
majemuk:
Contoh tautologi dengan menggunakan tabel kebenaran:
- (p ʌ
~q) p
Pembahasan:
|
p
|
q
|
~q
|
(p ʌ ~q)
|
(p ʌ ~q) p
|
|
B
B
S
S
|
B
S
B
S
|
S
B
S
B
|
S
B
S
S
|
B
B
B
B
|
Ini adalah tabel kebenaran yang menunjukkan Tautologi dengan
alasan yaitu semua pernyataannya bersifat benar atau True (T). maka dengan
perkataan lain pernyataan majemuk (p ʌ ~q) p selalu benar.
- [(p
q) ʌ p] p q
Pembahasan:
|
p
|
q
|
(p q)
|
(p q) ʌ p
|
[(p q) ʌ p] p q
|
|
B
B
S
S
|
B
S
B
S
|
B
S
B
B
|
B
S
S
S
|
B
B
B
B
|
(1)
(2)
(3)
(4) (5)
Berdasrkan tabel diatas pada kolom 5, nilai kebenaran
pernyataan majemuk itu adalah BBBB. Dengan perkataan lain, pernyataan majemuk
[(p q) ʌ p] p q selalu benar
Pembuktian dengan cara kedua yaitu dengan penjabaran atau
penurunan dengan menerapkan sebagian dari 12 hukum-hukum ekuivalensi logika.
Contoh:
(p ʌ q) q
Penyelesaian:
(p ʌ q) q ~(p ʌ q) v q
~p v ~q v q
~p v T
T .............(Tautologi)
Dari pembuktian diatas telah nampaklah bahwa pernyataan
majemuk dari (p ʌ q) q adalah tautologi karena hasilnya T (true) atau benar.
Pembuktian dengan menggunakan tabel kebenaran dari
pernyataan majemuk (p ʌ q) q yaitu:
|
P
|
q
|
(p ʌ q)
|
(p ʌ q) q
|
|
B
B
S
S
|
B
S
B
S
|
B
S
S
S
|
B
B
B
T
|
Pada tabel diatas nampaklah bahwa kalimat majemuk (p ʌ q) q
merupakan Tautologi.
q (p v q)
penyelesaian:
q (p v q) ~q v (p v q)
~q v (q v p)
T v p
T ............(Tautologi)
- Kontradiksi
Kontradiksi adalah kebalikan dari tautologi yaitu suatu
bentuk pernyataan yang hanya mempunyai contoh substansi yang salah, atau sebuah
pernyataan majemuk yang salah dalam segala hal tanpa memandang nilai kebenaran
dari komponen-komponennya. Untuk membuktikan apakah suatu pernyataan tersebut
kontradiksi, maka ada dua cara yang digunakan. Cara pertama dengan menggunakan
tabel kebenaran, yaitu jika semua pilihan bernilai F atau salah maka disebut
kontradiksi, dan cara kedua yaitu dengan melakukan penjabaran atau penurunan
dengan menerapkan sebagian dari 12 hukum-hukum Ekuivalensi Logika.
Contoh dari Kontradiksi:
- (A ʌ
~A)
Pembahasan:
|
A
|
~A
|
(A ʌ ~A)
|
|
B
S
|
S
B
|
S
S
|
Dari tabel kebenaran diatas dapatlah disimpulkan bahwa
pernyataan majemuk (A ʌ ~A) selalu salah.
- P ʌ
(~p ʌ q)
Pembahasan:
|
p
|
q
|
~p
|
(~p ʌ q)
|
P ʌ (~p
ʌ q)
|
|
B
B
S
S
|
B
S
B
S
|
S
S
B
B
|
S
S
B
S
|
S
S
S
S
|
Ini adalah tabel kebenaran yang menunjukkan kontradiksi
dengan alasan yaitu semua pernyataan bernilai salah (F).
- Contingent
Contingent (Kontingensi) adalah semua pernyataan majemuk
yang bukan merupakan tautologi atau kontradiksi. Dengan kata lain, pada kontingensi
nilai kebenarannya ada yang benar dan ada yang salah. Berikut sebuah contoh
pernyataan majemuk kontingensi
Pada tabel di atasdapat dilihat bahwa:
~(p => 1)^ (p ^ ~q = S B S S
Dengan demikian, pernyataan bukan tautologi dan bukan
kontradiksi melainkan sebuah kontingensi.
4. RESOLUSI LOGIKA PROPSISI
Disebut juga kalkulus proposisi yang merupakan logika simbolik
untuk memanipulasi proposisi. Proposisi merupakan pernytaan yang dapat bernilai
benar atau salah.
Operator logika yang digunakan :
Kondisional merupakan operator yang analog dengan production
rule.
- •
Contoh 1 : “ Jika hujan turun sekarang maka saya tidak pergi ke pasar”
Kalimat di atas dapat ditulis : p Æ q Dimana : p = hujan turun q = saya
tidak pergi ke pasar
- •
Contoh 2 : p = “Anda berusia 21 atau sudah tua” q = “Anda mempunyai hak
pilih”
Kondisional p Æ q dapat ditulis/berarti :
POKOK BAHASAN : REPRESENTASI PENGETAHUAN, LOGIKA PREDIKAT
1. Fungsi-fungsi Logika
Predikat
Logika predikat diperkenalkan oleh Sir William Hamilton
(1788-1856) dengan doktrinnya dinamakan “Quantification Theory”. Oleh karena
itu, logika predikat sebenarnya adalah logika proposisional yang ditambah
dengan hal-hal baru, yaitu pengkuantoran.
Logika adalah pada pembuktian validitas suatu argument
logika proposional dengan berbagai teknik yang relevan. Yaitu menggunakan table
kebenaran sebagai dasar pembuktian dan dan juga menggunakan hukum-hukum logika.
Logika proposisional sudah cukup untuk menangani pernyataan-pernyataan yang
sederhana dan banyak dijumpai dalam peristiwa sehari-hari. Akan tetapi logika
proposisional saja ternyata belum mampu menangani argumen-argumen yang berisi
pernyataan-pernyataan yang rumit dan sering dijumpai dalam peristiwa sehari-hari.
Sebagai contoh, perhatikan argumen berikut:
Contoh 1:
1) Semua gajah mempunyai
belaka
2) Dumbo seekor gajah
3) Dengan demikian, Dumbo
memiliki belalai.
Tanpa perlu dibuktikan validitasnya, orang-orang pasti
mengatakan argumen tersebut valid karena dengan jelas kesimpulan mengikuti
premis-premisnya. Akan tetapi bagaimana cara membuktikannya? Tentunya
menggunakan logika proposisional.
ARGUMEN PADA LOGIKA PREDIKAT
Validitas sebuah argumen dapat dibuktikan dengan contoh yang
mirip dengan contoh perhatikan contoh argumen berikut:
Contoh 2:
1) Semua mahasiswa pasti
pandai
2) Badu seorang mahasiswa
3) Dengan demikian, Badu
pandai
Secara nalar, kebanyakkan orang akan menilai bahwa argumen
di atas mempunyai validitas yang kuat. Akan tetapi, saat validitas tersebut
ingin dibuktikan dengan logika proposisional, ternyata tidak bisa diselesaikan.
Pembuktiannya dapat dilakukan dengan mengikuti prosedur logika proposisional
dengan menentukan terlebih dahulu proposisi-proposisinya :
A = Semua mahasiswa pasti pandai
B = Badu seorang mahasiswa
C = Badu pasti pandai
Selanjutnya akan menjadi seperti berikut :
A
B
_____
:. C
Dalam ekspresi logika : (A ˄ B)=>C
Dalam bentuk ekspresi logika diatas, tidak ada hukum-hukum
logika proposisional yang dapat digunakan untuk membuktikan validitas
argumen tersebut karena tidak ada yang mampu menghubungkan antara ketiga
proposisi yang digunakan diatas. Atau tidak mungkin suatu kesimpulan yang
berbeda dapat dihasilkan dari premis-premis yang berbeda. Dengan kata
lain, tidak mungkin suatu kesimpulan berupa C dapat dihasilkan dari premis A
dan premis B.
Jika argumen diatas masih ingin dibuktikan dengan logika
proposisional, maka kalimatnya harus diperbaiki. Misal seperti berikut:
Contoh 3:
1) Jika Badu seorang
mahasiswa, maka ia pasti pandai
2) Badu seorang mahasiswa
3) Dengan demikian, ia
pasti pandai
Jika diubah dalam bentuk ekspresi logika :
1) B=>C
premis 1
2) B
premis 2
3) C
kesimpulan
Atau dapat juga ditulis : [(B=>C) ˄ B] => C
Dalam logika proposisional, ekspresi logika diatas sudah
benar karena kesimpulan diambil dari premispremis. Persoalan yang terjadi adalah
pernyataan tersebut tidak sepenuhnya mampu menangkap ide pada argumen yang
pertama yaitu “Semua mahasiswa pandai”. Ide pada pernyataan tersebut tidak
tertangkap pada argumen kedua karena hanya mampu menunjuk seorang mahasiswa
yaitu Badu, bukan semua mahasiswa. Persoalan lain juga terjadi, yakni kesulitan
menentukan objek. Misalnya orang yang dimaksudkan jika diganti dengan kata
ganti orang.
2. Logika dan Set Order
Pertama
Logika First-Order digunakan dalam ilmu IntelejensiBuatan
sebagai Representasi Pengetahuan. Persolan yang ada memiliki pernyataanlebih
kompleks lagi tapi dapat diselesaikan dengan Pelacakan Terbalik(Backward)
Contoh:
Diberikanpernyataan sebagai berikut:
1) Andi adalah seorang
mahasiswa
2) Andi masuk jurusan
Informatika
3) Setiap mahasiswa
Informatikapasti mahasiswa Teknik
4) Kalkulus adalah
matakuliah yangsulit
5) Setiap mahasiswa
teknik pastiakan suka kalkulus atau akan membencinya
6) Setiap mahasiswa pasti
akansuka terhadap suatu matakuliah
7) Mahasiswa yang tidak
pernahhadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka
terhadapmatakuliah tersebut
8) Andi tidak pernah
hadir kuliahmatakuliah kalkulus.
Buktikan Apakah Andi suka matakuliah kalkulus?
Jawab:
Ubah pernyataan menjadi bentuk formula:
1) mahasiswa(Andi)
2) Informatika(Andi)
3) x:
Informatika(x)Teknik(x)
4) sulit(kalkulus)
5) x: Teknik(x)suka(x,
kalkulus) benci(x, kalkulus)
6) x: y: suka(x,y)
7) x: y:
mahasiswa(x)sulit(y)hadir(x,y) suka(x,y)
8) hadir(Andi,kalkulus)
Pernyataan Apakah Andi suka matakuliah kalkulus =
suka(Andi,kalkulus)
Dilakukan Backward /Pelacakan dari belakang seperti yang
biasa diterapkan pada ilmu ArtificialIntelegence atau Intelejensi Buatan dengan
cara berikut:
suka(Andi,kalkulus)
Substitusi
mahasiswa(Andi)
sulit(kalkulus)
hadir(Andi,kalkulus)
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 kucing -> x adalah
binatang).
Kebalikan kalimat “bukan kucing adalah binatang” ditulis :
(∀x) (p) (Jika x adalah seekor kucing -> ~x adalah
binatang)
dan dibaca :
– “setiap kucing adalah bukan binatang”
“semua kucing adalah bukan binantang”
Contoh 3:
(∀x) (Jika x adalah segitiga -> x adalah polygon)
Dibaca : “untuk semua x, jika x adalah segitiga, maka x
adalah polygon”.
Dapat pula ditulis : (∀x) (segitiga(x) -> polygon(x))
(∀x) (T(x) -> P(x))
Contoh 4 :
(∀x) (H(x) -> M(x))
Dibaca : “untuk semua x, jika x adalah manusia (human), maka
x melahirkan (mortal)”.
Ditulis dalam aturan : IF x adalah manusia THEN x
melahirkan.
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) (gajah(x) ∧ nama(Clyde))
Dibaca : “beberapa gajah bernama Clyde”.
Contoh 3 :
(∀x) (gajah(x) -> berkaki empat(x))
Dibaca : “semua gajah berkaki empat”.
Universal quantifier dapat diekspresikan sebagai konjungsi.
(∃x) (gajah(x) ∧ berkaki tiga(x))
Dibaca : “ada gajah yang berkaki tiga”
Existensial quantifier dapat diekspresikan sebagai disjungsi
dari
urutan ai. P(a1) ∨ P(a2) ∨ P(a3)
…∨ P(aN)
5. Resolusi Logika
Predikat
Tujuan dasar resolusi adalah membuat infer klausa baru yang
disebut “revolvent” dari dua klausa lain yang disebut parent
clause.
Contoh :
A Ú B
A Ú ~B
\ A
Premis dapat ditulis :
(A Ú B) Ù (A Ú ~B)
Ingat Aksioma Distribusi :
p Ú (q Ù r) º (p Ú q) Ù (p Ú q)
Sehingga premis di atas dapat ditulis :
(A Ú B) Ù (A Ú ~B) º A Ú (B Ù ~B) º A
dimana B Ù ~B selalu bernilai salah
Tabel Klausa dan Resolvent
|
Parent Clause
|
Resolvent
|
Arti
|
|
p à q , p
atau
~p Ú q, p
|
Q
|
Modus Pones
|
|
p à q , q à r
atau
~p Ú q, ~ q Ú r
|
p à r atau
~p Ú r
|
Chaining atau Silogisme Hipotesis
|
|
~p Ú q, p Ú q
|
Q
|
Penggabungan
|
|
~p Ú ~q, p Ú q
|
~p Ú p atau
~q Ú q
|
TRUE (tautology)
|
|
~p, p
|
Nill
|
FALSE (kontradiksi)
|
SISTEM RESOLUSI DAN DEDUKSI
Refutation adalah pembuktian teorema dengan
menunjukkan negasi atau pembuktian kontradiksi melalui reductio ad absurdum.
Melakukan refute berarti membuktikan kesalahan.
Contoh :
A à B
B à C
C à D
A à D
Untuk membuktikan konklusi A à D adalah
suatu teorema melalui resolusi refutation, hal yang dilakukan :
p à q º
~p Ú q
sehingga
Aà D º
~A Ú D
dan langkah terakhir adalah melakukan negasi
~(~A Ú D) º A Ù ~D
Penggunaan konjungsi dari disjunctive form pada premis dan
negasi pada konsklusi, memberikan conjuctive normal form yang cocok untuk
resolusi refutation.
Dari contoh di atas, penulisannya menjadi :
(~A Ú B) Ù (~B Ú C) Ù (~C Ú D) Ù A Ù ~D
Akar bernilai nill, menunjukkan kontradiksi. Sehingga
melalui refutation dapat ditunjukkan konklusi asli (awal) adalah teorema dengan
peran kontradiksi.
RESOLUSI PADA PROPOSISI DAN PREDIKAT
1) Resolusi
pada Logika Proposisi
Menggunakan resolusi yaitu suatu teknik pembuktian yang
lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa
ke bentuk standar yang sering disebut dengan nama klausa.Pembuktian suatu
pernyataan menggunakan resolusi ini dilakukan dengan cara menegasikan
pernyataan tersebut, kemudian dicari kontradiksinya dari pernyataan-pernyataan
yang sudah ada.
Algoritma konversi ke bentuk klausa :
a. Eliminir a → b
menjadi ¬ a v b
b. Reduksi skope dari ¬
sebagai berikut :
¬ (¬ a ^ b) ¬ a v ¬ b
¬ (¬ a v b) ¬ a ^ ¬ b
¬ x : P(x) x : ¬ P(x)
¬ x : P(x) x : ¬ P(x)
2) Resolusi
pada Logika Predikat
Logika predikat sebenarnya adalah logika proposional
ditambah dengan hal-hal baru seperti kuantor, universe of discourse, term,
predikat dan fungsi.
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 :
a. Konversikan
semua proposisi F ke bentuk klausa
b. Negasikan P, dan
konversikan hasil negasi tersebut ke bentuk klausa.Tambahkan
kehimpunan klausa yang telah ada pada langkah
c. 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
