BAB
5
Metode Pencarian dan
Pelacakan2(HEURISTIK)
• Hal penting dalam menentukan
keberhasilan sistem cerdas adalah kesuksesan dalam pencarian.
• Pencarian = suatu proses mencari solusi
dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state
space).
• Ruang keadaan = merupakan suatu ruang yang berisi
semua keadaan yang mungkin.
• Untuk mengukur perfomansi metode
pencarian, terdapat 4 kriteria yang dapat digunakan :
1.
Completeness :
apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?
2.
Time complexity : berapa lama waktu yang
diperlukan? [semakin cepat, semakin baik]
3.
Space complexity : berapa banyak memori yang
diperlukan
4.
Optimality :
apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat
beberapa solusi berbeda?
• Dua teknik pencarian dan
pelacakan
– Pencarian buta (blind search)
• Pencarian melebar pertama (Breadth –
First Search)
• Pencarian mendalam pertama (Depth –
First Search)
– Pencarian terbimbing (heuristic
search)
• Pendakian Bukit (Hill Climbing)
• Pencarian Terbaik Pertama (Best First
Search)
PENCARIAN HEURISTIK
Heuristik adalah sebuah teknik yang
mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan
mengorbankan kelengkapan (completeness). Fungsi dari heuristik digunakan intuk
mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh
hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis
heuristik yaitu :
-
Generate And Test
-
Hill Climbing
-
Best First Search
-
Problem Reduction
-
Constraint Statisfaction
-
Means End Analysis
5.1
BEST FIRST SEARCH (PENCARIAN TERBAIK PERTAMA )
Metode
ini merupakan kombinasi dari metode depthfirst search dan breadth-first search.
Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang
ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi
ternyata memiliki nilai heuristic yang lebih buruk.
Fungsi
Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state
ke goal state, yang dinyatakan dengan :
f’(n) = g(n) + h’(n)
dimana
f’ = Fungsi
evaluasi
g = cost dari initial state ke current
state
h’
= prakiraan cost dari current state ke goal state
Contoh :
Misalkan kita
memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan
awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M
dengannode A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota
A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node
A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk
sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara
node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap
node.
5.2 Problem Reduction
Problem
reduction atau yang biasa dikenal dengan constraint, intinya adalah berusaha
mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah
diselesaikan. Sekarang ini sudah diketahui teknik konsistensi ini sangat
penting dalam penyelesaian constraint
satisfactionproblem yang
sangat berat sehingga semua aplikasi komersial penyelesaian constraint satisfactionproblem menggunakan teknik konsistensi ini sebagai
langkah dasar. Sejarah konsistensi constraint dapat ditlusuri dari peningkatan
efisiensi program pengenalan gambar oleh peneliti di intelejensi semu.
Pegenalan gambar melibatkan pemberian label kepada semua garis pada gambar
dengan cara yang konsisten. Jumlah kombinasi pemberian label pada garis yang
memungkinkan dapat menjadi sangat besar, sementara hanya sedikit yang konsisten
pada tahap awal. Dengan demikian memperpendek pencarian untuk pembeian nilai
yang konsisten.Untuk mengilustrasikan teknik konsistensi ini akan diberikan
sebuah contoh constraint
satisfaction problem yang sangat
sederhana.
Anggap
A < B adalah constraint antara variabel A dengan domainDA = { 3..7} dan variabel B dengan domain DB = { 1..5}. dengan jelas tampak bahwa
bahwa untuk sebagian nilai pada DA tidak ada nilai yang konsisten di DB yang memenuhi constraint A < B dan sebaliknya. Niai yang
demikian dapat dibuang dari domain yang berkaitan tanpa kehilangan solusi
apapun. Reduksi itu aman. Didapatkan domain yang tereduksi DA = {3,4} dan DB = {4,5}.
Perhatikan
bahwa reduksi ini tidak membuang semua pasangan yang tidak konsisten. Sebagai
contoh kumpulan label (<A, 4>, <B, 4>) masihh dapat dihasilkan dari domain, tetapi untuk setiap
nilai A dari DAadalah
mungkin untuk mencari nilai B yang konsisten dan sebaliknya.
Walaupun
teknik konsistensi ini jarang digunakan sendirian untuk menghasilkan solusi,
teknik konsistensi ini membantu menyelesaikan constraint
satisfactionproblem dalam
beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian maupun
pada saat pencarian.
Constraint sering
direpresentasikan dengan gambar graf (gambar 1) di mana setiap verteks mewakili
variabel dan busur antar verteks mewakili constraint binari yang mengikat variabel-variabel
yan dihubungkan dengan busur tersebut. Constraint unari diwakilkan dengan busur
melingkar.
Kebanyakan
solusi menggunakan pohonOR,dimana lintasan dari awal sampai tujuan tidak
terletak pada satu cabang. Bila lintasan dari keadaan awal sampai tujuan dapat
terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.
Graf
AND-OR
Pada
dasarnya sama dengan algoritma Best First Search, dengan mempertimbangkan
adanya arc AND. Gambar berikut menunjukkan bahwa untuk mendapatkan TV orang
bisa dengan cara singkat yaitu mencuri atau membeli asal mempunyai uang.Untuk
mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk biaya solusi.
Untuk mendeskripsikan algoritma Graph AND-OR kita
menggunakan nilai F_UTILITY, yaitu biaya solusi.
Algoritma:
1. Inisialisasi graph ke node awal.
2. Kerjakan langkah-langkah di bawah ini hingga node awal
SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY:
a. Telusuri graph, mualai dari node awal dan ikuti jalur
terbaik. Akumulasikan kumpulan node yang ada pada lintasan tersebut dan belum pernah
diekspansi atau diberi label SOLVED.
b. Ambil satu node dan ekspansi node tersebut. Jika tidak
ada successor, maka set F_UTILITY sebagai nilai dari node tersebut. Bila tidak
demikian, tambahkan successor-successor dari node tersebut ke graph dan hitung
nilai setiap f’ (hanya gunakan h’ dan abaikan g). Jika f’ = 0, tandai node
tersebut dengan SOLVED.
c. Ubah f’ harapan dari node baru yang diekspansi.
Kirimkan perubahan ini secara backward sepanjang graph. Jika node berisi suatu
arc suatu successor yang semua descendant-nya berlabel SOLVED maka tandai node
itu dengan SOLVED.
Pada Gambar 2.33, pada langkah-1 semula hanya ada satu
node yaitu A. Node A diekspansi hasilnya adalah node B, C, dan D. Node D memiliki biaya yang lebih
rendah (6) jika dibandingkan dengan B dan C (9). Pada langkah-2 node D terpilih
untuk diekspansi, menjadi E dan F dengan biaya estimasi sebesar 10. Sehingga
kita harus memperbaiki nilai f’ dari D menjadi 10. Kembali ke level sebelumnya,
node B dan C memiliki biaya yang lebih rendah daripada D (9 < 10). Pada
langkah-3, kita menelusuri arc dari node A, ke B dan C bersama-sama. Jika B
dieksplore terlebih dahulu, maka akan menurunkan node G dan H. Kita perbaiki
nilai f’ dari B menjadi 6 (nilai G=6 lebih baik daripada H=8), sehingga biaya
AND-arc B-C menjadi 12 (6+4+2). Dengan demikian nilai node D kembali menjadi
lebih baik (10 < 12). Sehingga ekspansi dilakukan kembali terhadap D.
Demikian seterusnya.
Algoritma AO* menggunakan struktur Graph. Tiap-tiap
node pada graph tersebut akan memiliki nilai h’ yang merupakan biaya estimasi
jalur dari node itu sendiri sampai suatu solusi.
Algoritma :
1. Diketahui GRAPH yang hanya berisi node awal (sebut saja node INIT).
Hitung h’(INIT).
2. Kerjakan langkah-langkah di bawah ini hingga INI
bertanda SOLVED atau samoai nilai h’(INIT) menjadi lebih besar daripada
FUTILITY:
a. Ekspand INIT dan ambil salah satu node yang belum
pernah diekspand (sebut NODE).
b. Bangkitkan successor-successor NODE. Jika tida
memiliki successor maka set FUTULITY dengan nilai h’(NODE). Jika ada successor,
maka untuk setiap successor (sebut sebagai SUCC) yang bukan merupakan ancestor
dari NODE, kerjakan:
i.
Tambahkan
SUCC ke graph.
ii.
Jika
SUCC adalah terminal node, tandai dengan SOLVED dan set nilai h’-nya sama
dengan 0.
iii.
Jika
SUCC bukan terminal node, hitung nilai h’.
c. Kirimkan informasi baru tersebut ke graph, dengan
cara: tetapkan S adalah node yang ditandai dengan SOLVED atau node yang nilai
h’-nya baru saja diperbaiki, dan sampaikan nilai ini ke parent-nya.
Inisialisasi S = NODE. Kerjakan langkah-langkah berikut ini hingga S kosong:
i.
Jika
mungkin, seleksi dari S suatu node yang tidak memiliki descendant dalam GRAPH
yang terjadi pada S. Jika tidak ada, seleksi sebarang node dari S (sebut:
CURRENT) dan hapus dari S.
ii.
Hitung
biaya tiap-tiap arc yang muncul dari CURRENT. Biaya tiap-tiap arc ini sama
dengan jumlah h’ untuk tiap-tiap node pada akhir arc ditambah dengan biaya arc
itu sendiri. Set h’(CURRENT) dengan biaya minimum yang baru saja dihitung dari
stiap arc yang muncul tadi.
iii.
Tandai
jalur terbaik yang keluar dari CURRENT dengan menandai arc yang memiliki biaya
minimum.
iv.
Tandai
CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga arc
yang baru saja ditandai tadi telah ditandai dengan SOLVED.
v.
Jika
CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah,
maka status baru ini harus disampaikan ke GRAPH. Kemudian tambahkan semua
ancestor dari CURRENT ke S.
Sebagai contoh, pada Gambar 2.34 Jelas bahwa jalur
melalui C selalu lebih baik daripada melalui B. Tetapi jika biaya node E
muncul, dan pengaruh perubahan yang diberikan ke node B tidak sebesar
pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik. Sebagai
contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11 (10+1),
dengan demikian biaya node A apabila memilih jalur lewat C adalah 12 (11+1).
Tentu saja akan lebih baik memilih jalur melalui node B (11). Tapi tidak
demikian halnya apabila kemudian node D diekspan. Bisa jadi jalur dengan
melalui node B akan lebih buruk lagi ketimbang jalur dengan melalui node C.
5.3
Constraint Satisfaction
Problem
search standard :
state adalah
"black box“ setiap struktur data yang mendukung fungsi successor,
fungsi heuristik dan tes goal.
CSP:
state
didefinisikan sebagai variabel Xi dengan nilai dari domain Di – Tes goal adalah
sekumpulan constraint yang menspesifikasikan kombinasi dari nilai subset
variabel.
Contoh sederhana adalah bahasa representasi formal.
CSP ini merupakan algoritma general-purpose dengan
kekuatan lebih daripada algoritma pencarian standar. Contoh : Pewarnaan Peta
§ Variabel WA,
NT, Q, NSW, V, SA, T
§ Domain Di =
{red,green,blue}
§ Constraints
: daerah yang bertetangga dekat harus memiliki warna yang berbeda.
§ Contoh WA ≠
NT, atau (WA,NT) {(red,green),(red,blue),(green,red),
(green,blue),(blue,red),(blue,green)}
§ Solusi
lengkap dan konsisten, contoh : WA = red, NT = green,Q = red,NSW = green,V =
red,SA = blue,T = green
Constraint Graf
§ Binary CSP
biner : setiap constraint merelasikan dua variabel
§ Graf
Constraint : node adalah variabel, arc adalah constraint
5.4
MEA (Means-Ends Analysis)
MEA adalah
strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General
Problem Solver) [Newell & Simon, 1963]. Proses pencarian berdasarkan ruang
masalah yang menggabungkan aspek penalaran forward dan backward. Perbedaan
antara state current dan goal digunakan untuk mengusulkan operator yang
mengurangi perbedaan itu. Keterhubungan antara operator dan perbedaan tsb
disajikan sebagai pengetahuan dalam sistem (pada GPS dikenal dengan Table of
Connections) atau mungkin ditentukan sampai beberapa pemeriksaan operator jika
tindakan operator dapat dipenetrasi.
Contoh
OPERATOR first-order predicate calculus dan operator2 tertentu mengijinkan
perbedaan korelasi task-independent terhadap operator yang menguranginya. Kapan
pengetahuan ada tersedia mengenai pentingnya perbedaan, perbedaan yang paling
utama terpilih pertama lebih lanjut meningkatkan rata-rata capaian dari MEA di
atas strategi pencarian Brute-Force.
Bagaimanapun,
bahkan tanpa pemesanan dari perbedaan menurut arti penting, MEA meningkatkan
metode pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan
masalah pada perbedaan yang nyata antara current state dengan goal-nya.
Sumber
:
http://ichaajja212.blogspot.co.id/2012/10/heuristic-search-techniques-problem.html
BAB 6
REPRESENTASI
PENGETAHUAN
6.1
Arti pengetahuan
Pengetahuan adalah Informasi yang telah diproses dan diorganisasikan untuk
memperoleh pemahaman, pembelajaran dan pengalaman yang terakumulasi sehingga
bisa diaplikasikan ke dalam masalah/proses bisnis tertentu .
6.2
Produksi
Produksi
adalah
suatu kegiatan untuk menciptakan/menghasilkan atau menambah nilai guna terhadap
suatu barang atau jasa untuk memenuhi kebutuhan oleh orang atau badan
(produsen). Orang atau badan yang melakukan kegiatan produksi dikenal dengan
sebutan produsen. Sedangkan barang atau jasa yang dihasilkan dari melakukan
kegiatan produksi disebut dengan produk. Istilah Produksi berasal dari bahasa inggris to produce yang berarti menghasilkan.
Sedangkan
dalam arti ekonomi, Pengertian
Produksi adalah sebagai
kegiatan mengenai penciptaan dan penambahan atau utilitas terhadap suatu barang
dan jasa. Pengertian
kegiatan produksi dalam menghasilkan barang dan jasa adalah menghasilkan barang
dan jasa yang belum ada sehingga bertambah jumlahnya atau memperbesar
ukurannya. Contohnya adalah usaha pertanian, peternakan dan perikanan.
Faktor-Faktor Produksi
Faktor
produksi adalah segala sesuatu yang perlukan dalam kegiatan produksi terhadap
suatu barang dan jasa. Faktor-faktor produksi terdiri dari alam (natural
resources), tenaga kerja (labor), modal (capital), dan keahlian (skill) atau
sumber daya pengusaha (enterpreneurship). Faktor-faktor produksi alam dan
tenaga kerja adalah faktor produksi utama (asli), sedangkan modal dan tenaga
kerja merupakan faktor produksi turunan.
-
Faktor Produksi Alam, adalah semua
kekayaan yang ada di alam semesta digunakan dalam proses produksi. Faktor
produksi alam disebut faktor produksi utama atau asli. Faktor produksi alam
terdiri dari tanah, air, udara, sinar matahari, dan barang tambang.
-
Faktor Produksi Tenaga Kerja,
adalah faktor produksi insani yang secara langsung maupun tidak langsung dapat
menjalankan kegiatan produksi. Faktor produksi tenaga kerja sebagai faktor
produksi asli. Walaupun kini banyak kegiatan proses produksi diperankan oleh
mesin, namun keberadaan manusia wajib diperlukan.
-
Faktor Produksi Modal, adalah faktor
penunjang yang mempercepat dan menambah kemampuan dalam memproduksi. Faktor
produksi dapat terdiri dari mesin-mesin, sarana pengangkutan, bangunan, dan
alat pengangkutan.
-
Faktor Produksi Keahlian, adalah keahlian
atau keterampilan individu mengkoordinasikan dan mengelola faktor produksi untuk
menghasilkan barang dan jasa.
Proses Produksi
Proses
produksi adalah tahap-tahap yang harus dilewati dalam memproduksi barang atau
jasa. Ada proses produksi membutuhkan waktu yang lama, misalnya dalam pembuatan
gedung pencakar langit, pembuatan pesawat terbang, dan pembuatan kapal serta
lain-lainnya. Dalam proses produksi membutuhkan waktu yang berbeda-beda ada
yang sebentar, misalnya pembuatan kain, pembuatan televisi, dan lain-lain.
Tetapi, ada juga proses produksi yang dapat dinikmati langsung hasilnya oleh
konsumen, misalnya pentas hiburan, pijat dan produksi lain-lainnya.
Proses produksi ada 3 macam :
a.
Proses Produksi Pendek adalah proses produksi yang pendek
atau cepat dan langsung dalam menghasilkan barang atau jasa yang dapat
dinikmati konsumen. Contohnya adalah proses produksi makanan, seperti pisang
goreng, bakwan, singkong goreng. dan lain-lain.
b.
Proses Produksi Panjang adalah
proses produksi yang memakan waktu lama. Contohnya adalah proses produksi
menanam padi dan membuat rumah.
c.
Proses Terus Menerus/Kontinu adalah proses produksi
yang mengolah bahan-bahan secara berurutan dengan beberapa tahap dalam
pengerjaan sampai menjadi suatu barang jadi. Jadi bahan tersebut melewati
tahap-tahap dari proses mesin secara terus-menerus untuk menjadi suatu barang
jadi. Contohnya adalah proses memproduksi gula, kertas, karet, dan lain-lain
d.
Proses Produksi Berselingan/Intermitten adalah
proses produksi yang mengolah bahan-bahan dengan cara menggabungkan menjadi
barang jadi. Seperti, proses produksi mobil dimana bagian-bagian mobil dibuat
secara terpisah, mulai dari kerangkanya, setir, ban, mesin, kaca, dan
lain-lain. Setelah semua bagian dari mobil tersebut selesai atau lengkap maka
selanjutnya bagian-bagian mobil tersebut digabungkan menjadi mobil.
Tujuan Produksi
1. Menghasilkan
barang atau jasa
2.
Meningkatkan nilai guna barang atau jasa
3.
Meningkatkan kemakmuran masyarakat
4.
Meningkatkan keuntungan
5.
Meningkatkan lapangan usaha
6.
Menjaga kesinambungan usaha perusahaan
Representasi pengetahuan adalah
cara untuk menyajikan pengetahuan yang diperoleh ke dalam suatu skema/diagram
tertentu sehingga dapat diketahui relasi antara suatu pengetahuan dengan
pengetahuan yang lain dan dapat dipakai untuk menguji kebenaran penalarannya.
Secara teknik kita akan membahas representasi
pengetahuan menjadi lima kelompok:
1. Representasi
Logika
2. Jaringan
Semantik
3. Frame
4. Script
(Naskah)
5. Aturan
Produksi (Kaidah Produksi)
1. Representasi
Logika
Logika didefinisikan sebagai ilmu
untuk berpikir dan menalar dengan benar sehingga didapatkan kesimpulan yang
absah.
Tujuan dari logika: memberikan aturan-aturan penalaran
sehingga orang dapat menentukan apakah suatu kalimat bernilai benar atau salah.
Representasi Logika dibagi menjadi dua:
a.
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
Dengan menggunakan operator logika:
Tabel Kebenaran Logika
b.
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:
Predikat (argumen-1, argumen-2,..., argumen-3)
Contoh:
Proposisi: “Bu Atika mencintai Pak Agus Setiawan”
Dalam logika predikat disajikan dalam bentuk:
Mencintai (Bu Atika, Pak
Agus Setiawan)
P Argumen-1 Argumen-2
Contoh Silsilah Keluarga yang dipresentasikan dalam
Prolog
Jika silsilah di atas dibentuk dalam
Representasi Logika, sebagai berikut:
Orangtua (Komarudin, Andika)
Orangtua (Komarudin, Atika)
Orangtua (Komarudin, Agus)
Orangtua (Andika, Rika)
Orangtua (Atika, Anjar)
5.3 Jaringan Semantik
Pengetahuan disusun dalam sebuah jaringan yang
memiliki komponen utama:
- Node: menyatakan
obyek, konsep, atau situasi. Dinyatakan dengan kotak atau lingkaran
- Arcs/Link: Menyatakan
hubungan antar node. Dinyatakan dengan tanda panah.
6.5 Frame
dan Script
Frame
Frames: merupakan semantic net dilengkapi dengan
properties. Suatu Frame menggambarkan entitas sebagai set dari attribute
dan nilai yang bersesuaian.Suatu frame dapat berelasi dengan frame yang
lainnya.
Tiga komponen utama dari frame
• frame
name
• attributes
(slots)
• values
(subslots)
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
|
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
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.
http://www.temukanpengertian.com/2013/07/pengertian-pengetahuan.html
BAB 7
Logika dan Set Himpunan
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-
–
Konklusi : Socrates adalah makhluk hidup
Cara
lain merepresentasikan pengetahuan adalah dengan Diagram Venn.
Diagram
Venn merepresentasikan sebuah himpunan yang merupakan kumpulan objek. 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
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
Logika Proposisi
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 :
Tautologi
: pernyataan gabungan yang selalu bernilai benar.
Kontradiksi
: pernyataan gabungan yang selalu bernilai salah.
Contingent
: pernyataan yang bukan tautology ataupun kontradiksi.
Tabel
Kebenaran untuk logika konektif :
Tabel kebenaran untuk negasi
konektif :
Sumber :
https://www.google.co.id/search?q=representasi+pengetahuan+logika+proposisi&source=lnms&tbm=isch&sa=X&ved=0ahUKEwi8zfns7KvQAhVLqo8KHTf3DloQ_AUICSgC&biw=1366&bih=662
Bab 8
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). 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
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 domain fungsi ke dalam sebuah elemen unik pada himpunan lain yang
disebut range fungsi. 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
Universal Quantifier dan
Existensial Quantifier
–
Operator logika konektif : ∧,∨, ~, Æ, ≡.
– Logika kalkulus orde pertama mencakup symbol
universal quantifier ∀
dan existensial quantifier ∃.
Universal Quantifier
Menunjukkan
semua kalimat adalah benar untuk semua nilai variabelnya. Direpresentasikan
dengan symbol ∀
diikuti satu atau lebih argument untuk suatu domain variable. Symbol ∀ diinterpretasikan
“untuk setiap” atau “untuk semua”.
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
binantang” ditulis : (∀x)
(p) (Jika x adalah seekor kucing Æ ~x adalah binatang) dan dibaca :
“setiap kucing adalah bukan binantang”
“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
Digambar
dalam jaringan semantic :
Existensial Quantifier
Menunjukkan
semua kalimat adalah benar untuk suatu nilai tertentu dalam sebuah domain.
Direpresentasikan dengan symbol ∃
diikuti satu atau lebih argument. Symbol
∃ diinterpretasikan
“terdapat” atau “ada”, “paling sedikit satu”, “terdapat satu”, “beberapa”.
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)
Quantifier dan Sets
Relasi
A proper subset dari B ditulis A ⊂
B, dibaca “semua elemen A ada pada B”, dan “paling sedikit satu elemen B bukan
bagian dari A”. Hukum de Morgan berlaku
untuk analogi himpunan dan bentuk logika :
Quantifier dan Sets
Contoh
:
Diketahui
:
E
= elephant
R
= reptile
G
= gray
F
= four legged
D
= dogs
M
= mammals
