BAB V
5.1. BEST FIRST SEARCH
Pengertian Best-first Search
Best-First Search merupakan sebuah metode yang membangkitkan
simpul dari simpul sebelumnya. Best-first search memilih simpul baru yang
memiliki biaya terkecil diantara semua
leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan.
Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang
disebut fungsi evaluasi f(n). fungsi evaluasi best-first search dapat berupa
biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya
sebenarnya dan biaya perkiraan tersebut.
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. Fungsi heuristic merupakan suatu strategi untuk
melakukan proses pencarian ruang keadaan suatu problema secara selektif, yang
memandu proses pencarian yang kita lakukan sepanjang jalur yang memiliki
kemungkinan sukses paling besar.
Ada beberapa istilah yang sering digunakan pada metode
best-first search, yaitu:
1. Start node adalah sebuah terminology untuk posisi awal
sebuah pencarian
2. Curret node adalah simpul yang sedang dijalankan dalam
algoritma pencarian jalan terpendek
3. Suksesor adalah simpul-simpul yang yang akan diperiksa
setelah current node
4. Simpul (node) merupakan representasi dari area pencarian
5. Open list
adalah tempat menyimpan data simpul yang mungkin diakses dari starting node
maupun
simpul yang sedang dijalankan
6. Closed
list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur
terpendek
yang telah berhasil didapatkan
7. Goal node yaitu simpul tujuan
8. Parent adalah curret node dari suksesor.
5.2 PROBLEM REDUCTION
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
satisfaction problem 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 DA
adalah 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.
5.3 Constraint satisfaction
Dalam kecerdasan buatan dan riset operasi, constraint
satisfaction adalah proses menemukan solusi untuk satu set kendala yang
memaksakan kondisi bahwa variabel harus memuaskan. Solusi Oleh karena itu
vektor dari variabel yang memenuhi semua kendala.
Teknik yang digunakan dalam constraint satisfaction
tergantung pada jenis kendala yang dipertimbangkan. Sering digunakan adalah
kendala pada domain yang terbatas, ke titik yang kendala masalah kepuasan
biasanya diidentifikasi dengan masalah berdasarkan kendala pada domain yang
terbatas.
Masalah seperti ini biasanya dipecahkan melalui pencarian,
khususnya bentuk kemunduran atau pencarian lokal. Kendala propagasi metode lain
digunakanpada masalah tersebut, kebanyakan dari mereka tidak lengkap pada
umumnya, yaitu, mereka dapat memecahkan masalah atau membuktikannya
unsatisfiable, tetapi tidak selalu. Kendala metode propagasi juga digunakan
dalam hubungannya dengan pencarian untuk membuat soal yang diberikan sederhana
untuk memecahkan.
Jenis lain dianggap kendala berada pada bilangan real atau
rasional; pemecahan masalah pada kendala-kendala dilakukan melalui eliminasi
variabel atau algoritma simpleks permasalahan pada Constraint satisfaction.
Sebagai awalnya didefinisikan dalam kecerdasan buatan,
kendala menghitung nilai yang mungkin satu set variabel dapat mengambil.
Informal, domain terbatas adalah himpunan berhingga elemen sewenang-wenang.
Sebuah kepuasan kendala masalah pada domain seperti berisi satu set variabel
yang nilainya hanya dapat diambil dari domain, dan satu set kendala, kendala
masing-masing menetapkan nilai diperbolehkan untuk sekelompok variabel. Sebuah
solusi untuk masalah ini adalah evaluasi dari variabel-variabel yang memenuhi
semua kendala. Dengan kata lain, solusi adalah cara untuk menetapkan nilai
untuk setiap variabel sedemikian rupa sehingga semua kendala dipenuhi oleh
nilai-nilai ini.
Dalam praktek, kendala yang sering diekspresikan dalam
bentuk yang kompak, daripada enumerasi semua nilai dari variabel yang akan
memuaskan kendala. Salah satu kendala yang paling sering digunakan adalah salah
satu menetapkan bahwa nilai-nilai dari variabel-variabel yang terkena harus
semua berbeda.
Masalah yang dapat dinyatakan sebagai masalah kepuasan
kendala adalah teka-teki ratu Delapan, pemecahan masalah Sudoku, masalah
satisfiability Boolean, masalah penjadwalan dan berbagai masalah pada grafik
seperti masalah pewarnaan graf.
Meskipun biasanya tidak termasuk dalam definisi di atas dari
masalah kepuasan kendala, aritmatika persamaan dan ketidaksetaraan terikat
nilai-nilai dari variabel yang
dikandungnya dan karenanya dapat dianggap sebagai bentuk kendala. Domain mereka
adalah himpunan nomor (baik bilangan bulat, rasional, atau nyata),yang tak
terbatas: oleh karena itu, hubungan ini kendala mungkin tak terbatas serta,
misalnya, X = Y 1 memiliki jumlah tak terbatas pasangan nilai memuaskan .
Aritmatika persamaan dan ketidaksamaan sering tidak dianggap
dalam definisi "masalah kepuasan kendala", yang terbatas pada domain
yang terbatas. Namun mereka sering digunakan dalam pemrograman kendala.
5.4 Means Ends Analysis
Pengertian Means-Ends Analysis
Means-Ends Analysis terdiri dari tiga unsur kata yakni;
Mean, End dan Analysis. Mean menurut bahasa yakni berarti, banyaknya cara.
Sedangkan End adalah akhir atau tujuan, dan Analysis berarti analisa atau
penyelidikan secara sistematis.
Means-Ends Analysis pertama kali diperkenalkan oleh Newell
dan Simon (wikipedia, 2007) dalam General Problem Solving (GPS), yang
menyatakan bahwa Means-Ends Analysis adalah suatu teknik pemecahan masalah di
mana pernyataan sekarang dibandingkan dengan tujuan, dan perbedaan di antaranya
dibagi ke dalam sub-subtujuan untuk memperoleh tujuan dengan menggunakan
operator yang sesuai.
Beberapa pengertian Means-Ends Analysis menurut para tokoh
antara lain:
Yang mengandung pengertian bahwa MEA (Means-Ends Analysis)
merupakan metode pemikiran sistem dalam penerapannya merencanakan tujuan
keseluruhan, dimana tujuan tersebut dijadikan kedalam beberapa tujuan yang pada
akhirnya menjadi beberapa langkah atau tindakan berdasarkan konsep yang
berlaku. Dan pada setiap akhir tujuan akan berakhir pada tujuan yang lebih
umum. Sedangkan menurut Kamran Zaheer (2006): “Means-Ends Analysis merupakan
salah satu yang penting dalam mencari algoritma matematika dan digunakan pada
semua aplikasi yang dibutuhkan seluruh pencarian untuk mendapatkan hasil. Dan
MEA juga digunakan untuk keefektifan dalam pencarian distribusi dari sebuah
pemikiran. Eeden (2003) suatu pemecahan masalah mempunyai beberapa situasi
dengan menentukan hasil, mengidentifikasi perbedaan diantara masalah tersebut
dan menentukan tindakan untuk menemukan kesamaan dari perbedaan tersebut”.
Selanjutnya Erman Suherman (2007) menyatakan Means-Ends
Analysis merupakan model pembelajaran variasi antara metode pemecahan masalah
dengan sintaks yang menyajikan materinya pada pendekatan pemecahan masalah
berbasis heuristik, mengelaborasi menjadi sub-sub masalah yang lebih sederhana,
mengidentifikasi perbedaan, menyususun sub-sub masalahnya sehingga terjadi
koneksivitas. Kemudian Jacob (2005) menyatakan bahwa Means-Ends Analysis
merupakan suatu proses untuk memecahkan suatu masalah ke dalam dua atau lebih
subtujuan.
Dari uraian di atas jelas bahwa metode Means-Ends Analysis
merupakan suatu model pembelajaran bervariasi antara metode pemecahan masalah
dengan sintaks dalam penyajian materinya menggunakan pendekatan pemecahan
masalah berbasis heuristik, yaitu memecahkan suatu masalah ke dalam dua atau
lebih subtujuan. Di mana MEA mengelaborasi menjadi sub-sub masalah yang lebih
sederhana, mengidentifikasi perbedaan, dan menyusun sub-sub masalahnya sehingga
terjadi koneksivitas.
Adapun dalam menerapkan langkah-langkah dalam strategi
Means-Ends Analysis Glass & Holyoak (Jacob C, 2005), menyatakan bahwa
komponen utama dari Means-Ends Analysis memuat dua langkah yang digunakan
berulang-ulang. Yang dalam hal ini mengidentifikasi perbedaan diantara
pernyataan sekarang dan tujuan yang ditentukan. Kemudian menggunakan suatu
tindakan untuk mengurangi satu dari perbedaan
Kemudian Herbert Simon (Eeden, 2003)9 menyatakan bahwa
langkah-langkah yang dimiliki oleh metode Means-Ends Analysis hampir memiliki
persamaan dengan model pemecahan masalah (Problem Solving) karakteristik
permasalahannya yakni: pertama, Problem Space (all possible configuration),
dimana masalah dibagi ke dalam suatu konfigurasi beberapa
kemungkinan-kemungkinan, yang kedua yakni, Problem State (the particular
configuration) dimana inti dari suatu masalah tersebut di buat ke dalam
beberapa bagian konfigurasi particular masalah, kemudian yang ketiga yakni, Key
to solving is a problem is to choose the right operators (processes applied to
change the configuration), dimana kunci untuk suatu pemecahan adalah suatu
masalah yang harus dipilih dalam proses perubahan dari masalah tersebut, dan
yang keempat yakni, Problem solving is a search process: Each action takes us
front one part of the problem space to another, dimana suatu pemecahan masalah
adalah proses pemilihan satu tindakan dari beberapa masalah yang ada.
Sedangkan Kamran (2006), menyatakan bahwa langkah-langkah
dalam mempergunakan metode Means-Ends Analysis adalah sebagai berikut:
1. Mentransfer inti masalah ke dalam beberapa bagian dari masalah
tersebut
2. Bagian tersebut diolah
3. Bagian masalah tersebut dikirimkan untuk mencari kesamaan
dari beberapa perbedaan.
Jacob (2005) menambahkan, apabila kita mempergunakan metode
Means-Ends Analysis agar dapat menyelesaikan masalah dengan cepat dan mudah,
kita dapat memulainya dengan cara:
1. Mendahulukan petunjuk/arahan, dari pernyataan awal sampai
pernyataan tujuan, atau,
2. Terbalik mulai dari pernyataan tujuan sampai kepada
pernyataan awal.
Metode Means-Ends Analysis berdasarkan konsep di atas jelas
bahwa setiap tujuan yang dicapai ada dalam cara/langkah itu sendiri untuk
mendapatkan tujuan yang lebih umum dan rinci. Metode Means-Ends Analysis juga
dapat mengembangkan berpikir reflektif, kritis, logis, sistematis dan kreatif.
BAB VI
6.1 ARTI PENGETAHUAN
Pengertian Representasi pengetahuan yaitu suatu teknik untuk
merepresentasikan basis pengetahuan yang diperoleh ke dalam suatu skema/diagram
tertentu sehingga dapat diketahui relasi/keterhubungan antara suatu data dengan
data yang lain sehingga dapat diuji kebenaran penalarannya.
6.2 PRODUKSI
Aturan Produksi (Production Rule)
Aturan produksi adalah jenis representasi pengetahuan yang
paling umum digunakan karena memiliki keuntungan yang lebih dibandingkan dengan
kekurangannya.
6.3 Jaringan Semantik (Semantic nets)
Jaringan Semantik adalah tehnik representasi dalam
artificial intelligence klasik untuk informasi proposional, sehingga sering
kali disebut sebagai poporsional network. Proposisi adalah pernyataan yang
dapat bernilai benar atau salah dan merupakan bentuk pengetahuan deklaratif.
Semantic network pertama kali dikembangkan untuk AI sebagai
cara untuk mempresentasikan memory dan pemahaman bahasa manusia. Struktur
semantic nets berupa grafik dengan node (simpul) dan arc (ruas) yang
menghubungkannya.
Contoh jaringan semantic:
6.4 TRIPLE OBJEK-ATRIBUT-NILAI
Object dapat berupa bentuk fisik atau konsep. Attribute
adalah karakteristik atau sifat dari object tersebut. Value (nilai) –
besaran/nilai/takaran spesifik dari attribute tersebut pada situasi tertentu,
dapat berupa numerik, string dan boelan.
Sebuah object dapat memiliki beberapa attribute, biasa
disebut OAV Multi-Attribute.
Contoh representasi pengetahuan dengan OAV ditunjukan pada
table.
Table . representasi pengetahuan dengan OAV.
6.5 SCHEMATA: FRAME AND SCRIPT
• Frame
Frame (Minsky, 1975) dipandangsebagaistrukturdata static
yang digunakan untuk merepsentasikan situasi situas iyang telah dipahami dan
stereotype. Frame digunakan untuk merepresentasikan pengetahuan stereo type
atau pengetahuan yang didasarkan kepada karakteristik yang sudah dikenal yang
merupakan pengalaman masalalu. Frame berupa kumpulan slot-slot (representasi
entitas sebagai struktru objek) yang merupakan atribut untuk mendeskrip sikan
pengetahuan berupa kejadian, lokasi, situasi ataupun elemen-elemenlain. Frame
digunakan untuk representasi pengetahuan deklaratif.
.JPG)
• Script
Script (Schank& Abelson, Yale univ) merupakan
representasi terstruktur yang menggambarkan urutan stereotip dari
kejadian-kejadian dalam sebuah kontek skhusus. Script mirip dengan frame,
perbedaannya : Frame menggambarkan objek, sedangkan Script menggambarkan urutan
peristiwa. Dalam menggambarkan urutan peristiwa, script menggunakan serangkaian
slot yang berisi informasi tentang orang, objek dan tindakan-tindakan yang
terjadi dalam suatu peristiwa.
Elemenscript yang tipikal:
Kondisi masukan: menggambarkan situasi yang harus di penuhi
sebelum terjadi suatu peristiwa yang ada dalam script.
Prop : mengacu kepada objek yang digunakan dalam urutan
peristiwa yang terjadi.
Role : mengacu kepada orang-orang yang terlibat dalam
script.
Hasil: kondisi yang ada sesudah peristiwa dalam script
berlangsung.
Track : mengacu kepada variasi yang mungkin terja didalam
script tertentu.
Scene : menggambarkan urutan peristiwa aktural yang terjadi.
Disini kami mengimplemeatsikanya dengan langkah memulai
bermain pyromaster seperti dibawah ini :
Bermain Pyromaster
Jalur : bermain games
Peran : pemain, computer
Pendukung : perangkat komputer, keyboard, mouse
Kondisi masuk : pemain mengakses games- pemain bermain.
Adegan 1 : Masuk
· Pemain menyalakan komputer
· Pemain membuka games
· Menunggu loading
Adegan 2 : Memilih menu
· Pemain memilih pilihan play more games untuk memilih
permainan jenis lain
· Pemain memilih option untuk menseting grafis, suara, dan
music
· Pemian memilih istrucsion untuk pemebritahuan element pada
games
· Pemian memilih play game untuk memulai permainan
· Computer memunculkan tampilan untuk menseting level,
victory, player, com AI, tombol Back, tombol Start
Adegan 3 : Memulai permainan
· Pemain bermain permainan pyromaster
· Pemain menang
· Pemain kalah
· Pemain memilih bermain
· Pemain berhenti
Adegan 4 : Selesai
· Pemain keluar dari games
· Pemain mematikan computer
Hasil
· Pemain merasa senang
· Pemain merasa kecewa
BAB VII
7.1 LOGIKA DAN SET
Logika dan Set Jaringan
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.
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
7.2 OPERATOR LOGIKA
Dalam logika, dua kalimat dapat digabungkan dengan operator
logika untuk membentuk kalimat gabungan. Nilai kebenaran kalimat gabungan ini
ditentukan oleh nilai kebenaran kalimat-kalimat pembentuknya. Operator logika
di sini bertindak sebagai fungsi.
Dalam bahasa sehari-hari, dua kalimat dapat digabungkan
dengan konjungsi gramatik. Misalnya:
A: Hari ini cuaca mendung
B: Hari ini akan hujan
C: Hari ini cuaca mendung dan hari ini akan hujan
D: Hari ini cuaca mendung karena itu hari ini akan hujan
Kata dan dan karena itu adalah konjungsi gramatik yang
menggabungkan kalimat (A) dan (B) untuk membentuk kalimat (C) dan (D).
7.3 TAUTOLIGI, KONTRADIKSI DAN CONTINGENT
Tautologi adalah suatu proporsi majemuk yang selalu bernilai
benar untuk semua kemungkinan kombinasi nilai kebenaran dari proporsi-proporsi
pembentuknya
Contoh pada table kebenaran:
|
p
|
 p |
p
 p |
|
B
S
|
S
B
|
B
B
|
Definisi 2.
Kontradiksi adalah suatu proporsi majemuk yang selalu
bernilai salah untuk semua kemungkinan kombinasi nilai kebenaran dari
proporsi-proporsi pembentuknya.
Contoh pada table kebenaran:
|
p
|
p |
p
 p |
|
B
S
|
S
B
|
S
S
|
Definisi 3.
Kontingensi adalah suatu proporsi
majemuk yang bukan termasuk tautologi dan bukan juga kontradiksi
Contoh pada table kebenaran:
|
p
|
q
|
p
 q |
|
B
B
S
S
|
B
S
B
S
|
B
B
B
S
|
7.4 RESOLUSI LOGIKA PROPOSISI
Definisi Logika
Ilmu logika lebihmengarah pada bentuk
kalimat (sintaks) daripada arti kalimat itu sendiri(semantik). Ilmu logika
selalu berhubungan dengan kalimat-kalimat (argument) dan hubungan yang ada
diantarakalimat-kalimat tersebut. Argumentasi adalah kumpulan sebuah
kesimpulanbeserta fakta-faktanya. Kesimpulan dikatakan benar apabila
merupakanakibat dari fakta-fakta yang diajukan. Apabila semua fakta-fakta yang
diajukanberikut kesimpulan adalah benar dan terdapat hubungan logis di
antarakeduannya, maka argumentasi tersebut adalah benar atau valid. Akan
tetapi,terkadang meskipun fakta-fakta yang diajukan tidak diragukan lagi
kebenarannya,bisa saja kesimpulan yang diambil menjadi salah akibat dari cara
berfikir yangtidak logis dan akhirnya menyebabkan suatu argumentasi menjadi
tidak valid. Tujuanmempelajari logika adalah untuk mampu mengidentifikasi valid
atau tidaknyasuatu argumentasi.
Dasar Logika Proposisi
- Proposisi adalah ekspresi yangmengandung variabel (yaitu
variableproposisional) berupa pernyataan
dan operator (yaitu operator logika)
sebagaikonektor.
- Pernyataan (Statement) adalah
kalimatdeklaratif yang memiliki nilai kebenaran (True dan False)
- Syntactics Rule (AturanSintaktik)
adalah aturan yang diperlukan untuk mengkombinasikan antara propositions dan propositional
connectives untuk menghasilkan sentences(kalimat logika). Dapat dibuat alurnya
sebagai berikut Propositions + Propositional Connectives à Sentences
Propositional connective yang digunakan: Not, And, Or, If-Then,If-Then-Else,
dan If-And-Only-If
- Interpretasi adalah pemberiannilai
kebenaran (true atau false) pada setiap symbol proposisi dari suatu
kalimat logika.
- Semantic Rule (Aturan Semantik)adalah
suatu aturan yang digunakan untuk menentukan “truth
value” dari suatusentence.
Logika
proposisimemiliki bentuk berupa kalimat deklaratif (atau pernyataan).
Proposisididefinisikan sebagai kalimat deklaratif yang memiliki hanya satu
nilaikebenaran yaitu benar saja, salah saja, tetapi tidak keduanya, benar
sekaligus salah. Pada umumnyabentuk proposisi adalah kalimat berita yang bisa
ditentukan nilai kebenarannya(benar/salah).
BAB VIII
8.1 Logika dan set order 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 .
Sebuah teori tentang beberapa topik
biasanya logika orde pertama bersama-sama dengan yang ditentukan domain wacana
dimana variabel diukur berkisar, finitely banyak fungsi yang memetakan dari
domain yang ke dalamnya, finitely banyak predikat didefinisikan pada domain
tersebut, dan satu set rekursif dari aksioma yang diyakini terus untuk hal-hal.
Kadang-kadang "teori" dipahami dalam arti yang lebih formal, yang
hanya satu set kalimat dalam logika orde pertama.
Kata sifat "orde pertama"
membedakan orde pertama logika dari logika tingkat tinggi di mana ada predikat
yang memiliki predikat atau fungsi sebagai argumen, atau di mana salah satu
atau kedua bilangan predikat atau fungsi bilangan diizinkan. Dalam first teori
order, predikat sering dikaitkan dengan set. Dalam ditafsirkan tingkat tinggi
teori, predikat dapat ditafsirkan sebagai set set.
Ada banyak sistem deduktif untuk orde
pertama logika yang sehat (semua laporan dapat dibuktikan benar dalam semua
model) dan lengkap (semua pernyataan yang benar dalam semua model yang dapat
dibuktikan). Meskipun konsekuensi logis hubungan hanya semidecidable , banyak
kemajuan telah dibuat dalam teorema otomatis dalam logika orde pertama. Logika
orde pertama juga memenuhi beberapa metalogical teorema yang membuatnya setuju
untuk analisis dalam teori bukti , seperti teorema Löwenheim-Skolem dan teorema
kekompakan .
Logika orde pertama adalah standar
untuk formalisasi matematika menjadi aksioma dan dipelajari di dasar matematika
. Teori matematika, seperti nomor teori dan teori himpunan , telah diresmikan
menjadi orde pertama aksioma skema seperti Peano aritmatika dan
Zermelo-Fraenkel teori himpunan masing-masing (ZF).
Tidak ada teori orde pertama,
bagaimanapun, memiliki kekuatan untuk menggambarkan sepenuhnya dan kategoris
struktur dengan domain yang tak terbatas, seperti bilangan asli atau garis
nyata . Sistem aksioma kategoris untuk struktur ini dapat diperoleh dalam
logika kuat seperti logika orde kedua .
8.2 QUATNTIFIER UNIVERSAL
Dalam logika predikat , kuantifikasi
universal merupakan jenis quantifier , sebuah konstanta logis yang ditafsirkan
sebagai "diberi" atau "untuk semua". Ini mengungkapkan
bahwa fungsi proposisi dapat dipenuhi oleh setiap anggota dari domain wacana.
Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setiap
anggota domain. Ini menegaskan bahwa 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
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
8.3 RESOLUSI LOGIKA PREDIKAT
Resolusi pada logika predikat pada
dasarnya sama dengan resolusi pada logika proposisi, hanya saja ditambah dengan
unufikasi. 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 ke himpunan klausa
yang telah ada pada langkah 1.
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 dinamakan resolvent. Jika ada
pasangan literal T1 dan T2 sedemikian hingga keduanya dapat dilakukan
unifikasi, maka salah satu T1 atau T2 tidak muncul lagi dalam resolvent. 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 :
Misalkan terdapat pernyataan-pernyataan
sebagai berikut :
1. Andi adalah seorang mahasiswa.
2. Andi 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. Andi tidak pernah hadir kuliah
matakuliah kalkulus.
Kedelapan pernyataan di atas dapat dibawa
ke bentuk logika predikat, dengan menggunakan operator-operator logika
predikat, sebagai berikut :
9. mahasiswa(Andi).
10. Elektro(Andi).
11. ∀x:Elektro(x)→Teknik(x).
12. sulit(Kalkulus).
13. ∀x:Teknik(x) →
suka(x,Kalkulus) ∨
benci(x,Kalkulus).
14. ∀x:∃y:suka(x,y).
15. ∀x:∀y:mahasiswa(x)∧sulit(y) ∧ ￢hadir(x,y)→
￢suka(x,y).
16. ￢hadir(Andi,Kalkulus).
Kita dapat membawa
pernyataan-pernyataan yang ada menjadi bentuk klausa (CNF) sebagai berikut:
1. mahasiswa(Andi).
2. Elektro(Andi).
3. ￢Elektro(x1) ∨ Teknik(x1).
4. sulit(Kalkulus).
5. ￢Teknik(x2) ∨ suka(x2,Kalkulus) ∨ benci(x2,Kalkulus).
6. suka(x3,fl(x3)).
7. ￢mahasiswa(x4) ∨ ￢sulit(y1)
∨
hadir(x4,y1) ∨
￢suka(x4,y1).
8. ￢hadir(Andi,Kalkulus).
SUMBER:
http://deisyamalia.blogspot.co.id/2012/03/best-first-search.html
https://aimprof08.wordpress.com/2012/04/24/tautologi-kontradiksi-dan-kontingensi/
Tidak ada komentar:
Posting Komentar