METODE INFERENS11

KESIMPULAN

3.1. PENGENALAN.

Dalam bab ini kita akan mendiskusikan beberapa metode pemikiran atau Inferensi. Topik ini secara khusus penting dalam expert system karena pemberilan alasan merupakan teknik yang umum dimana expert system memecahkan suatu problem. Expert system pada umumnya digunakan jika algoritma yang tidak rnemadai atau tidak ada pemecahan algoritma yang muncul dan pemberian alasan menawarkan kemungkinan pemecahannya.

3.2. TREES, LATTICES, DAN GRAF.

Tree adalah struktur data herarkhi yang berisi "node" yang menyimpan informasi atau pengetahuan dan "branches"/cabang yang menghubungkan node. Cabang kadang-kadang disebut dengan "link" atau "edges" dan node kadailg-kadang disebut dengan "vertices". Gambar 3.1 menunjukkan binary tree/po�on

yang umum yang mempunyai 0, 1, atau 2 cabang pere node. Dalam "oriented tree", "root node" merupakan node tertinggi dalam "hierarchy" dan "leaves" adalah terendah. Tree dapat disebut type jaringan semantik khusus dimana set ap

node kecuali akar/root mempunyai satu "parent"/orang tua dan nol atau 1 ih

mode "child"/anak. Untuk type tree binary yang biasanya, ada maksimum ua

anak per node, dan node anak sebelah kin' dan kanan dibedakan.

Gambar 3-1

Pohon Biner

132

Jika node mempunyai lebih dari satu orang tua/induk maka akan ada dalam suatu jaringan. Dalam Gambar 3.1 , perhatikan bahwa ada hanya satu rangkaian edge atau path dari akar ke beberapa node sejk tidak mungkin memindahkan lagi anak panah. Dalam tree yang diorientasikan, anak panati mengambil seluruh downward.

Tree merupakan kasus khusus dari struktur matematika umum yang debut "Graf'/Graf. Bentuk jaringan atau jaringan sederhana sering digunakan secara sinonim dengan Graf jika menjelaskan contoh tertentu dari Graf seperti jaringan telpon. Suatu Graf dapat mempunyai nol atau lebih link antara node dan tidak ada perbedaan antara induk dan anak. Contob sederhana dari Graf adalah feapl peta dimana kota adalah node dan link adalah jalan. Link mungkin mempunyai anakan panah atau tujuan yang digabungkan dengannya dan, "weight" ke karakterisasi beberapa aspek link. Analogi adalah salah satu cara jalan dengan weight terbatas paada berapa banyak truk dapat membawa hingga Plan. Weight dalam Graf dapat berupa suatu type informasi, Jika Graf menunjukkari rout_P pesawat, maka weight dapat bermil-mil antar kota, harga penerbangan, kcrosur»si bahan baakar dan sebagainya.

Artificial neural system adalah contoh lain dari Graf dengan lingkararn selama training ada feedbback informasi dari satu peletak dari jaringan ke yang lainnya yangmenentukan weight. Graf sederhana tidak mempunyai link yang segera datang kembali pada node itu sendiri, seperti ditunjukkan dalam Gamabr 3.2 (a). "Cir-cuit" atau "cycle"/Iingkaran adalah path melalui Graf yang memulai dan berakhir pada node yang sama, seperti path ABCA dalam Gambar 3.2 (a). Graf "Acyclic" tidak mempunyai cycle/lingkaran. "Connected Graf' mempunyai link ki: seiuru.i nodenya. Graf dengan link Ian-sung, disebut dengan "digraf" dan "elf-"oop" ditunjukkan dalam Gambar 3,2 (d). Tree dengan hanya path tunggal dari ?k;:r ,.c satu leaf-nya adalah "degenerate tree". Tree binary degenerate dari tiga node ditunjukkan dalam Gambar 3.2 (e). PAda umumnya dalam tree, anak pans l,= t idk asecara eksplisit menunjukkan karena dianggap pointing down.

Tree dan lattics sangat berguna untuk mengklasi_fikasikan obyek karF

herarkhinya dengan induk atas anak. Suatu contoh adalah fami!i tree yaa, menunjukkan hubungan dan nenek moyang dari orang yang berht : bersaudara. Aplikasi tree alinnya dan lattics membuat keputusan denga, "decision trees" atau "decision lattices". ita akan nienggunakii z bunt "structure" untuk menyebut kedua tree dan lattices. Struktur ke')utusaT ;;dale;; skema representasi pengetahuan dan metode pemberian alasan tentan' pengetahuannya. Suatu contoh adalah untuk permainan klasik dari tebakan suatu binatang. Node berisi pertanyaan cabang "ya" atau "tidak" menjawab ke

133

pertanyaan dan leaves berisi tebakan binatang tersebut.

Porsi yang kecil dari pohon keputusan untuk mengklasifikasikan raspberries ditunjukkan dalam Gambar 3.4. Tree Unlike Computer Science, klasifikasi tree mungkin digambarkan dengan akar ke bawah. Tidak ditunjukkan akar yang mempunyai cabang ke node "Leaves Simple" dan cabang lain pada node "Leavees Compound". Proses leaves bermula pada bagian bawah dengan mengidentifikasi gross feature, seperti apakah leaves/daun sederhana atau compound. Yang lebih detail memerlukan observasi yang lebih dekat digunakan sebagai perjalanan ke tree. Yaitu, jaringan yang lebih besar dari alternatif diuji pertama kali dan kemudian proses keputusan mulai mempersempit kemungkinan ke jaringan yang lebih kecil. Ini merupakan cara yang bbaik dari pengorganisasian keputusan dalam bentuk waktu dan usaha untuk melaksanakan observasi yang lebih detail.

Jika suatu keputusan adalah binary, maka tree keputusan binary mudah dibuat dan sangat efisien. Setiap pertanyaan turun satu tingkar dalam tree. Salu pertanyaan dapat memutuskan satu atau dua kemungkinan jawaban. Dta pertanyaan dapat memutuskan satu atau empat kemungkinan jawaban. Tiga per'.anyaan dapat memutuskan satu atau delapan kemungkinan jawaban d*tn seterusnya. Jika tree binary dibuat seperti itu seluruh leaves adalah jawaban d*n seluruh node yang turun adalah pertanyaan, ada maksimum 2 pangkat n untuk jawaban untuk pertanyaan N. Misalnya, 10 pertanyaan dapat mengklasifikasik$n satu atau 1,024 binatang sementara20 pertanyaan dapat mengkalisfikasikan sajtu atau 1,048,576 kemungkinan jawaban.

Feature berguna lainnya dari keputusan tree adalah bahwa tree tersebut dal#at dibuat "self-learning". Jika tebakan salah, suat prosedur dapat dipanggil untk meminta pemakai yang baru, pertanyaan klasifikasi yang benar dan jawabaan "ya" atau "tidak". Node baru, cabang dan daun dapat secara dinamis dibent3k dan ditambahkan ke tree. Dalam program animal/binatang ash dituliskan dal am BASIC, pengetahuan disimpan dalam pernyataan DATA. Jika pemalai memikirkan program binatang barn, pelajaran otomatis akan terjadi seperti pto-gram yang dibuat pernyataan DATA bare yang berisi informasi tentang binatang yang barn. Dalam Pascal atau bahasa lainnya dengan kemampuan pengambiln, pengetahuan binatang dapat disimpan dalam tree. Dengan menggunakan expert system shell OPS5, baris barn dapat dibuat secara otomatis sebagai program yang mempelajari pengetahuan barn. "Automated knowledge acquisition" sana berguna jika dapat (circumvent) pengetahuan acquistion bottleneck seperti dijelaskan dalam Bab-01.

134

I

A B Ds

\C

(a) A non-connected graph

A \/�

C

(c) A Digraph with a Self-Loop and Circuit

/

(h) A connected graph

(d) A Lattice

N 9

% 0/19 %r (e) Degenerate Binary Trees of Three Nodes

Gambar 3-2

Is it very big?

No Yes

Doe., it squeak? Does it baveYa long seek?-

No

Guess -;eli Omnessouse Does it have s trunk?

No Yes

Does it like to be in water? Guess e out

Own rhino Guess hippo

Gambar 3-3 Pohon keputusan yang menunjukkan Pengetahuan tentang binatang

135

Red

BlackRaspberry

Stems very waxy;fruit black

FloweringRaspberry I

Wineberry

Some hairs havean enlarged end

RaspberryIBristly,

non-enlarged hairs

Lower leafsurface green

Leaves SimpleLeaves Compound

Gambar 3-4 Bagian dan Pohon keputusan untuk Species Rasberries

Struktur keputusan dapat secara mekanis diterjemahkan ke dalam baris produksi. Hal ini dapat dilakukan dengan mudah dengan penelitian (breadth-first) daari struktur dan pembuatan bans IF...THEN pada setiap node. Misalr>Aya keputusan tree dari Gambar 3.3 dapat diterjemahkan ke dalam baris sebiga berikut :

IF QUESTION = 'IS IT VERY BIG?- AND RESPONSE = -NO

THEN QUESTION : _ "DOES IT SQUEAK?"

IF QUESTION = "IS IT VERY BIG?" AND RESPONSE = "YIDS

THEN QUESTION "DOES IT HAVE A LONG NECK?'

dan seterusnya untuk node yang lainnya. Node leaf akan membuat res n ANSWER bukannya suatu pertanyaan. Pembuatan yang semestinya jugs a menanyakan pemakai untuk input dan membuat node baru jika salah.

136

Meskipun struktur keputusan merupakan peralaan kiasifikasi yang sangat handal, strukaur tersebut terbatas karena tidak dapat be;hubun gar.? dengan variabel seperti yang dapat drlal ukan oleo expert system. Expert : y iein merup at an peralatan dengan to uan umum buk atnr'ya peneniL, ede' kan `.

3,3. SPASI PERNYATAAN DAN PROBLEM.

Graf dapat diterapkan pada beberapa problem praktis. Metode yang sanA,. berguna dari penjelasan kelakukan obyek adalah dalam nenentukan disebut dengan "state space". "State" adalah koleksi l arakte,istil yang dapat digunakan untuk menentukan status atau "state"t menyatakan suatu oily State space meruapakan rangkaian pernyataan yang menunjukkan ' transisi" aiit :-a pernyataan dimana obyek dapat di-experience. Suatu transisi akan rnemperlakukan obyek dari satu pernyataan ke pernyataa yang lainnya.

Contoh State Space.

Seperti contoh state space sederhana, perhatikan peinbelian soft drink dari suatu mesin. Karma kita memasukkan coin ke dalam mesin, tuaka akan mernhu= t transisi dari satu pernyataan ke pernyataan yang lain. Garnbar 3.5 rneng lus rasi Kan state space yang menganggap bahwa hanya seperempat dan nikel telah tersedia dan 55¢ diperlukan untuk suatu minuman. Penambahan coin lair seperti (dimes) dan limapulub sen akan mernbuat diagram lebih komplek dan tidak ditunjukkan.

Permulaan dan pernyataan yang berhasil digambarkan sebagai lingkaran dobel untuk membuatnya lebih mudah dalam mngidentifikasi. Pernya(aan ditunjukkan sebagai lingkaran dan kemungkinan transisi ke pernyataan yang fain digambarkan dengan tanda panah. Perhatikan bahwa diagram ini merupakan Graf (weighted), dimana weight adalah kemungkinan coin yang dapat dimasukkan ke dalam mesin dalam setiap pernyataan/state.

Diagram ini juga disebut dengan diagram "finite state machine" karena menggambarkan jumlah terbatas dari pernyataan mesin. Bentuk rnesin digunakan dalam arti yang sangat umum. Mesin dapat berupa obyek riil, algortma, konsep, dan sebagainya. Digabungkan dengan setiap pernyataan merupakan aksi yang melakukannya ke pernyataan yang lain. Pada suatu waktu, mesin hanya merupakan satu pernyataan. Karena mesin meneriman input pada state/pernyataan, maka akan meningkatkan dari pemyataan tersebut ke pernyataan yang lain. Jika input

137

benar diberikan, maka mesin akan meningkat dari permulaan ke sukses atau pernyataan akhir. Jika suatu pernyataan tidak di-design untuk menerima input tertentu, mesin akan tetap berada dalam pernyataan tersebut. Misalnya, mesin softdrink tidak mempunyai provisi untuk menerima dimes. Jika seseoragg meletakkan dime ke dalam mesin, maka respondnya tidak ditentukan. Design yang baik akan mencakup kemungkinan input yang tidak valid dari setiap pernyataan dan menyediakan untuk transisi ke pernyataan yang salah. Pernyataan yang salah di-design untuk memberikan pesan salah yang semestinya dsn melakukan aksi yang diperlukan.

Gambar 3-5

Diagram keadaan untuk. Vending Machine yang menjual Soft Drink yang menerima Quarter (Q) dan Nikel (N)

138

Mesin finite state (mesin dengan pernyataan terbatas) sering digunakan di dalam compiler dan program lain untuk menentukan validitas input. Misalnya, Gambar 3.6 menunjukkan bagian dari mesin dengan pernyataan terbatas untuk menge-test string input untuk validitas. Karakter dari input akan diuji satu kali.

Hanya string karakater WHILE, WRITE, dan BEGIN akan diterima. Anak panah ditunjukkan dari pemyataaan BEGIN untuk input yang sukses, dan juga untuk input (erroneous) yang berjalan ke pernyataan yang salah. Untuk efisiensi, beberapa pernyataan seperti satu yang diambil oleh "L" dan "T" digunakan untuk testing WHILE dan WRITE.

Error

Gambar 3-6 Bagian dari Mesin keadaan yang terbatas untuk menentukan string valid

WHILE, WRITE.

Hanya beberapa Transisi Keadaan Kesalahan yang ditunjukkan.

Diagram state juga berguna di dalam menjelaskan solusi dari problem. Dalam macam aplikasi ini, kits dapat memikirkan state space sebagai "problem space" dimana beberapa pernyataan berhubungan ke tahap lanjutan dalam pemecahan masalah dan beberapa pernyataan berhubungan ke jawaban. Dalam problem space, ada multiple pernyataan sukses yang berhubungan dengan kemungkinan

139

pemecahan/solusi. Derigan menemukan solusi pada suatu problem di dalam prob-lem space mencakup penemuan path yang valid dari permulaan (pernyataan problem) ke sukses (jawaban). (Animal decision tree) dapat dilihat sebagai prob-lem space dimana respon ya/tidak ke pertanyaan menentukan state transisi.

Contoh lain dari problem space terjadi di dalam problem klasik Monkey don Bananas yang ditunjukkan di dalam Gambar 3.7. Problemnya adalah memberikan instruksi kepada kera dengan mengatakan bagaimana mengambil beberapa pisang yang digantungkan di langit-langit. Pisang tersebut berada di luar jangkauan. ti dalam ruangan ada senter dan tangga. Susunan permulaan secara tipikal krra akan memegang senter. Instruksi akan berupa :

jump off couch

move to ladder

move ladder under bananas' position

climb ladder grab bananas

Instruksi ini akan bervariasi tergantung kepada susunan awal kera, senter, dan tangga. Jika ada sejumlah pernyataan permulaan, maka lingkaran dobel khu�us untuk permulaan tidak ditunjukkan. Misalnya, kemungkinan pernyatalan permuulaan lainnya adalah dengan kera pada senter dibawah pisang. Kra kemudian akan menekan senter sebelum memindahkan tangga ke bawah pisang. Dalam pernyataan permulaan yang paling sederhana, kera telah berada di tangga di bawah pisang.

Meskipun problem ini kelihatan nyata pada manusia, tetapi mencakup sejumlah pertimbangan pemberian alasan. Aplikasi praktis dari system pemberfian alasan seperti ini adalah memberikan instruksi ke robot yang berhubungan dengan solusi tugas. Bukannya menganggap bahwa seluruh obyek di dalam lingkuntan telah tersusun di tempat, solusi umum merupakan system pemberian alasan yin dapat berhubungan dengan berbagai situasi. Solusi yang berdasarkan pada bon

ke problem Monkey dan Bananas didistribusi dengan disk CLIPS. ,

Aplikasi Graf lain yang berguna adalah mengeksplorasi path untu menenmukan solusi problem. Gambar 3.8 (a) menunjukkan jaringan sederh n untuk problem Traveling Salesman. Dalam contoh ini, anggap problem ad la untuk menemukan path yang lengkap dari node A yang mengunjungi seluru node yang lain. Seperti biasa di dalam problem Traveling Salesman, tidak dad node yang dikunjungi dua kali. Gambar 3.8 (b) menunjukkan seluruh kemungki�

140

I

path dimulai dari node A dalam bentuk tree/akar. Path yang benar ABDCA dan

ACDBA ditunjukkan dengan garis tebal dalam Graf ini.

Berdasarkan pada penelitian algoritma, eksplorasi path untuk menemukan yang benar mungkin mencakup sejumlah backtracking yang dapat dipertimbangkan. Miisalnya, path ABA mungkin pertama kali diteliti dengan tidak sukses, dan kemudian di-backtracked ke B. Dari B, path CA, CB, CDB, dan CDC akan diteliti dengan tidak sukses. Path berikutnya BDB akan diteliti dengan tidak sukses hingga path benar pertama ABDCA ditemukan.

Problem Space yang terstruktur jelek.

Aplikasi state space yang berguna adalah di dalam karakterisasi problem yang terstruktur dengan jelek (pople 82). Dalam Bab-O 1, problem yang terstruktur dengan jelek ditentukan untuk mempunyai ketidak tentuan yang digabungkan dengannya. Ketidaktentuan ini dapat ditentukan dengan lebih baik dengan problem spacee.

Seperti contoh dari problem yang terstruktur jelek, mari perhatikan lagi kasus seseorang yang memikirkan tentang perjalanan dan kunjungan agen perjalanan, seperti didiskusikan di dalam Bab-01. Tabel 3.1 memberikan daftar beberapa karakteristik problem yang terstruktur jelek ini sebagai problem space, ditunjukkan dengan respond seseorang ke pertanyaan agen perjalanan.

Jika kita membandingkan Tabel 3.1 ke Tabel 1.10 dalam Bab-01, kits akan melihat bahwa konsep problem dari problem space memungkinkan yang lebih teliti karakterstik problem yang terstruktur jelek. lni sangat pokok untuk karakterisasi parameter dengan teliti untuk menentukan jika solusi dapat dipercaya, dengan apa yang diperlukan untuk suatu solusi. Suatu problem tidak perlu terstruktur jelek karena mempunyai satu, beberapa , atau bahkan seluruh karakteristik tersebut jika banyak berdasarkan pada kehebatan. Misalnya, seluruh teori membuktikan problem yang mempunyai angka terbatas dari solusi potensial, tetapi tidak akan membuat teori membuktikan problem yang terstruktur jelek.

141

Gambar 3-7

Ruang keadaan untuk masalah Kera dan Pisang

142

(a) Graph of a Traveling Salesman Problem

A

A ti ' ll

/ p�i�B D B AC

151

Gambar 3-8 Masalah Perjalanan Salesman

Seperti yang dapat kita lihat dari tabel ini, ada banyak ketidaktentuan dan manusia yang belum seperti agen perjalanan mengatasi dengannya setiap hari. Ketika tidak semua kasus sejelek ini, ini menunjukkan mengapa solusi algoritma akan sangat sukar.

143

Karakteristik

Tujuan tidak eksplisit

Ruang masalah tidak terikat

Masalah tidak diskrit

Keadaan lanjutan sukar didapat

Operator keadaan tak dikenal

Hambatan waktu

Respon

Saya sedang berpikir untuk pergi ke

suatu tempat.

Saya tidak yakin kemana untuk pergi

Saya mau berpergian; tujuan bukan hal

yang penting

Saya tak punya uang untuk pergi

Saya tak tahu cara mendapatkan uang

Saya harus pergi segera

Tabel 3-1

Contoh masalah tak terstruktur - III untuk berpergian

Problem yang terbentuk dengan baik merupakan salah satu dimana kita tabu problem eksplisit, tujuan, dan operator yang dapat diterapkan untuk dijalankan dari satu pemyataan ke pemyataan yang lain. Problem yang terbentuk dengn baik merupakan "deterministic" karena jika operator diterapkan pada state, khta yakin akan state berikutnya. Problem space digabungkan dan state mempun}yai ciri tersendiri. Hal ini berarti bahwa ada jumlah terbatas dari state dan setijap state ditentukan dengan baik.

Dalam problem perjalanan, state tidak digabungkan karena ada banyak kemungkinan tujuan infinit dimana traveler melakukan perjalanan. Situasi yang analogous terjadi dengan analog meter yang mungkin menunjukkan jumlah tidak terbatas dari kemungkinan membaca. Jika kita perhatikan setiap membaca meter menjadi state/pernyataan, maka ada sejumlah pernyataan yang tidak terbatas clan pernyataan tersebut tidak ditentukan dengan baik karena digabungkan ke an4k riil, state tidak memiliki ciri tersendiri karena state berikutnya berbeda sedan

infinit. Sebaliknya, mambaca dari digital meter akan digabungkan dan memilik' ciri tersendiri.

144

3.4. AKAP'PDHON DAN TUJUAN AND-OR.

Beberapa type expert system menggunakan rangkaian backward untuk menemukan solusi problem. PROLOG merupakan contoh yang balk dari system rangkaian backward yang mencoba memecahkan problem dengan memecahnya ke dalam sub problem yang lebih kecil dan memecahkannya. Pemecahan problem dipertimbangkan dengan optimis sebagai tujuan yang harus dicapai. Untuk menyelesaikan tujuan, nol atau lebih sub tujuan mungkin diperlukan untuk diselesaikan.

Satu type tree atau lattice yang berguna di dalam menurijukkan p.oblerrt rangkaian backward adalah tree AND-OR. Garnbar 3.9 menunjukkan contoh sederhana dari lattice AND-OR untuk memecahkan tujuan dari perolehan tingkar college. Untuk menyelesaikan tujuan ini, kita dapat cenderung college dalam seseorang atau melalui kursus korespondensi. Denbgan kursus korespondensi, pekerjaan dapat ditunjukkan dengan pengirman tanda tangan atau secara elektrinok dengan menggunakan home komputer dan modern.

Untuk memenuhi persyaratan untuk degree, tiga subtujuan harus diselesaikan : (1) menerapkan hak masuk/pengakuan, (2) menjalankan kursus dan (3) menerapkan lulusan. Perhatikan bahwa ada arc melalui edges yang menunjukkan bahwa tujuan Satisfy Requirements merupakan node AND yang hanya dapat dipenuhi jika seluruh tiga sub tujuannya dipenuhi. Tujuan tanpa arc seperti Mail, Computer, dan Modern, dan In Person adalah node-oR dimana penyelesaian sub tujuan tersebut memenuhi induk tujuannya dari Get a College Degree.

Diagram ini adalah lattice karena Satisfy Requirements sub tujuan mempunyai tiga node induk : (1) Mail, (2) Computer dan Modern, dan (3) In Person. Perhatikan bahwa ini akan mungkin menggambarkan diagram ini sebagai pohon/tree dengnan, duplikasi sederhana sub tujuan Satisfy Requirements dan sub tree tujuan untuk Mail, Computer dan Modern, dan tujuan In Person. Namun demikian, jika Satisfy Requirements sama untuk masing-masing induknya, tidak: ada keuntungan riil dan menggunakan paper yang lebih untuk menggambarkan tree.

Seperti contoh sederhana lainnya, Gambar 3.10 n;enun 'jkkan tree AND-OR untuk problem dari perolehan ke dalam lattice. Misalnya, edge dapat ditambahkan dari node Drive ke Train Station ke node Car dan dari Walk ke Train Station ke node Walk. Gambar 3.11 menunjukkan lattice type OR AND-ekslusif.

145

Gambar 3-9 Latrice AND-OR yang menunjukkan cara mendapatkan Ijazah Akademi

Cara lain untuk menggambarkan solusi problem adalah lattice ND-OR-NOT yang menggunakan simbol logika sebagaia pengganti notasi type tree AND-OR. Symbol gerbang logika untuk AND, OR, dan , NOT ditunjukkan dalam Gambar 3.12. limplement gate/gerbang ini tabel jujur untuk AND, OR, dan NOT didiskusikan dalam Bab-02. Gambar 3.13 menunjukkan Gambar 3.9 yaing diimplementasikan dengan gerbang AND dan OR.

Pohon/tree ND-OR dan pohon keputusan mempunyai keuntungan clan

kerugian pokok yang sama. Keuntungan utama dari lattice AND-OR-NOT adalah

146

implementasi potensialnya dalam hardware untuk kecepatan pemrc ,esan yang

cepat. Lattice teisebut dapat di-design b .sa untuk p_.inbuL'an sereri: circuit yang digabungkan. Pada praktiknya, satu type gerbang iogika seperti NOT-AND atau NAND digunakan untuk alasan pembuatan ekonomi bukannya memisahkan gerbang NAD, OR, dan NOT. Dari logika, ini dapat dibuktikan bahwa fungsi logika dapat diimplementasikan dengan gerbang NAND. Circuit yang digabungkan dengan satu type bagian akan lebih murah dibuat dibandingkan dengan satu type gerbang logika multipel.

Chip yang menggunakan rangkaian dapat menghitung jawaban sangat cepat seperti fungsi inputnya jika pemrosesan mendahului dalarn parallel. Chic seperti ini dapat digunakan untuk waktu riil denganonitoring sensor data dan membuat respon yang semestinya berdasakan pada input. Keuntungan utama adalah seperti struktur keputusan lainnya, chip yang di-design untuk logika tidak dapat menangani situasi yang di-design untuknya. Namun demikian, ANS yang diimplementasikan pada chip dapat menangani input yang tidak diharapkan.

3.5. LOGIKA DEDUKTIF DAN SYLLOGISM.

Dalam bab-02, kita telah mendiskusikan representasi pengetahuan dengan logika. Sekarang kita akan melihat bagaimana Inferensi/kesimpulan dibuat untuk mendapatkan pengetahuan atau informasi yan g baru. Dalam bab ini juga, kita akan mendiskusikan metode Inferensi/kesimpulan yang berbeda. Gambar 3.14 merupakan pandangan metode Inferensi. Ringkasan yang singkat adalah sebagai berikut :

• "Deduction". Pemberian alasan logikal dimana kesimpulan harus mengikutidari premises-nya.

• "Induction".Inferensi dari kasus khusus ke yang umum.

• "Intuition". Tidak ada teori yang manjmain. Jawabaanya hanya muncul,mungkin dengan penentuan pola yang ada secara tidak disadari. Expert system belum mengimplementasikan type Inferensi ini. ANS mungkin berisi janji untuk type Inferensi ini jika dapat meng-ekstrapolasi dari trainingya bukannya hanya menyediakan respond kondisional atau interpolasi. Yaitu, jaringan neural akan selalu memberikan tebakan terbaiknya untuk suatu solusi.

147

• "Heeuristics". Baris thumb didasarkan pada suatu pengalaman.

• "Abduction". Pemberian alasan kembali dari kesimpulan yang benar kepremises yang mungkin menyebabkan kesimpulan.

• "Default". Dalam kekurangan pengetahuan khusus, anggap pengetahuanumum oleh default.

• "Autoepistemic'. Self-knowledge.

• "Nonmonotomic". Pengetahuan sebelumnya mungkin tidak benar jika bukti

bare didapatkan.

• "Analogy". Infering kesimpulan berdasarkan pada persamaan pada situasilainnya.

Meskipun non eksplisit ditunjukkan dalam Gambar 3.14, "commonsense knowledge" mungkin menjadi kombinasi type tersebut. Pemberian alasain commonsense merupakan type dimana orang menggunakan di dalam situasi ordinar, dan sangat sukar bagi komputer. Aplikasi logika fuzzy untuk pember� an alasan commonsense didiskusikan dalam Bab-05.

Satu dari yang paling sering digunakan metode penggambaran Infereisi dlaah "deductive logic", yang telah digunakan sejak jaman dulu untuk menentulkan validitas "argument". Meskipun orang secara umum menggunakan kata arguren untuk menjelaskan suatu kemarahan "eexchange of vews", sangat berbeda *rti dalam logika. Argumen logika merupakan kelompok pernyatan dimana yang terakhir diklaim untuk memenuhi pada basis pernyataan sebelumnya dal rangkaian pemberin alasan. Satu type argumen logika adalah syllogism, yang

secar singkat telh didiskusikan. dalam Bab-02. Seperti contoh syllogism :

Premise: Anyone who can program is intelligent

Premise: John can program-Conclusion: Therefore, John is inteligent

148

Gambar 3-10

Pohon AND-OR sederhana yang menunjukkan Metode bekerja

149

Gambar 3-11

Littice AND-OR untuk Keputusan Perbaikan/Penjualan Mobil

A AND BB

150

AORB A \_ NOTA

D

Gambar 3-12

Simbol gerbang logika AND, OR, dan NOT

APPLY FORADWMANC E

ENROLL IN COURSESTAKE COURSES

SATISFYREQLMWIAM I'S

MAR.

IN FER3.?;1 1

PASS COURSES

I-,) - CCOMPUTER

APPLY TO GRADUATE

Gambar 3-13

AND MODEM

Representasi Logika AND-OR untuk gambar 3-9

Deduction I Intuition I Generate I Default 1 Nonmonotonic IInduction Heudatica and Test Abduction Autoepistemic Analogy

Gambar 3-14 Tipe inferensi

Dalam argumen, premises digunakan sebagai bukti untuk mendukung suatu kesimpulan. Premises juga disebut dengan "antecedent" dan kesimpulan disebut dengan "consequent". Karakteristik pokok dari logika deduktif adalah bahwa kesimpulan benar "harus" mengikuti dari premises yang benar. Suatu baris pada umumnya menggambarkan untuk memisahkan premises dari kesimpulan, seperti ditunjukkan di atas, sehingga tidak perlu secara eksplisit label premises dan kesimpulan.

151

Argumen harus dituliskan lebih singkat seperti :

Anyone who can program is intelligent'

John can program

John is intelligent

dimana tiga titik, .•. berarti "oleh karena itu" (therefore).

Mari kita lihat lebih dekat pada logika syllogistic sekarang. Keuntungan utama dari mempelajari syllogism adalah bawa syllogism tersebut sederhan, caban$ logika dapat dipahami dengan baik yang dapat di buktikan secara lengkap. Jugab syllogism sering berguna sejak syllogism dapat diekspresikan dalam bentuk bari$ IF THEN. Misalnya, syllogism sebelumnya dapat di phrase-kan kembali sebagai :

IF Anyone who can program is intelligent and

John can program

THEN John is intelligent

Pada umumnya, syllogism merupakan argumen deduktif yang valid yan$ mempunyai dua premises dan satu kesimpulan. Syllogism klasik merupakan type yang disebut dengan "catagorical syllogism". Premises dan kesimpulan ditentukah sebagai pernyataan catagorical dari empat bentuk berikut ini, seperti ditunjukkandalam Tabel 3.2.

Perhatikan bahwa di dalam logika, skema bentuk menentukan bentuk logilda dari pernyataan. Hal ini juga mengilustrasikan penggunaan skema kata yang lai , yang berbeda dengan penggunaan AI seperti didiskusikandalam Bab-02. Dal* logika, skema kata digunakan untuk menunjukkan bentuk esensial dari argume>h. Skemata juga menentukan bentuk logika dari seluruh syllogism seperti dalami :

All M is p

All S is M

All S is P

152

Form Schema Meaning

A All S is P universal affirmative

E No S is P universal negativeI Some S is P particular affirmative0 Some S is not P particular negative

Tabel 3-2

Statement Kategori

Subyek kesimpuin, S, disebut "minor term" sementara predikat dari kesimpulan, P, disebut dengan "major term". Premises yang berisi bentuk major disebut dengan "major premise" dan premise yang berisi bentuk minor disebut dengan "minor premise". Misalnya :

Major Premise: All M is P

Minor Premise: All S is m

Conclusion: All S is P

adalah syllogism yang disebut menjadi "standard form", dengan premises major dan minor yang ditentukan. "Subject" merupakan obyek yang digambarkan sementara "predicate" menggambarkan beberapa property dari subyek. Misalnya, dalampernyataan :

All microcomputers are computers

subyek adalah :microcomputer" dan predikat adalah "computer". Dalampernyataan :

All microcomputers with 8 megabytesare computers with a lot of memory

subyek adalah "microcomputer with 8 megabytes" dan predikat adalah "computer with a lot of memory".

Bentuk pernyataan catagorical telah diidentifikasikan sejak jaman duliu dengan huruf A, E, I dan 0. A dan I menunjukkan afirmatif dan dianggap berasal dari dua vokal pertama dari kata Latin "affirmo" (I affirm), sementara : E dan 0

153

berasal dari "nego" (I negate). Bentuk A dan I disebut dengan `affirmatif in quality" dengan meng-afirmasi bahwa subyek dimasukkan dalam jenis pred' E dan 0 merupakan "negative in quality" karena subyek tidak masuk dari jan s predikat.

KAta kerja "is" disebut dengan "copula" dari bahasa Latin yang berarti menghubungkan. Copula menghubungkan dua bagian pernyataan. Dalai syllogism catagorical standard, copula menunjukkan bentuk tense dari kata ker$a "to be". Sehingga versi lain adalah :

All S are P

Bentuk ketiga dari sylloogism, M, disebut dengan "middle term" dan pa4a umumnya untuk kedua premises. Middle term adalah pokok karena syllogi didefinisikan sehingga kesimpulan taidak dapat di-infere dari premises sendin Sehingga argumen :

All A is B

All B is C

All A is B

tidak merupakan syllogism valid jika mengikuti dari premise pertama sendii.

"Quantity" atau "quantifier", menjelaskan porsi jenis yang ada. Quantifier

"All" dan "No" adalah "universal" karena quantifier tersebut mengecu ke sselluruh

jenis. Quantifier "Some" disebut dengan "particular" karena mengacu pada h a

bagian jenis.

"Mood" dari syllogism ditentukan dengan tiga huruf yang memberikan bentuk premise pokok, minor premise dan kesimpulan, secara respektif. Misalnva, syllogism :

All M is P

All S is M

All S is B

154

adalah mood AAA.

Ada aempat pola kemungkinan dari penyusunan bentuk S, P, dan M seperti ditunjukkan dalam Tabel 3.3. Setiap pola disebut dengan "figure' dengan angka figure yang menentukan typenya.

Figure 1 Figure 2 Figure 3 Figure 4

Premis

Major MP PM MP PM

Premis

Minor SM SM MS MS

Tabel 3-3 Pola Statement Kategori

Sehingga contoh sebelumnya telah lengkap dijelaskan sebagai type syllo-gism AAA-l. Hanya karena argumen mempunyai bentuk syllogism bukan berarti bahwa argument tersebut syllogism valid. Perhatikan bentuk syllogism AEE-1 berikut ini :

All M is p

No S is m

No S is P

bukan syllogism valid seperti dapat dilihat dari contoiu :

All microcomputers are computers

No mainframe is a microcomputer

•• No mainframe is a computer

155

Bukannya mencoba memikirkan contoh-contoh untuk membuktikan validitas argumen syllogism, ada "decision procedure" yang dapat digunakan. Decision Procedure merupakan metode pembuktian validitas. Decision procedure, merupakan metode mekanik umum atau algoritma diimana algortima yang memproses penentuan validitas dapat di-otomatisasi. Sementara ada decisioi procedure untuk logika syllogic dan logika proportional, Church yang ditunjukkati pada tahun 1936, tidak ada untuk logika predikat. Sebagai pengganti, orang-orang harus menerapkan kreatifitas untuk membuat suatu pembuktian.

Decision procedure untuk proporsi ini merupakan konstruksi sederhana dart tablel kebenaran dan mengujinya untuk tautology. Decision procedure untuk syllogism dapat dikerjakan dengan mengganakan diagram Venn derigan tiga lingkaran overlapping yang menunjukkan S, P, dan M seperti ditunjukkan dalarip Gambar 3.15 (a). Untuk bentuk syllogism AEE-1 :

All M is P

No S is M

No S is P

premise pokok diilustrasikan dalam Gambar 3.15 (b). Bagian M yang dibe#i baris menunjukkan bahwa tidak ada elemen di dalam porsi tersebut. Dalm () premise minor dimasukkan dengan pembuatan baris porsinya dengan tanpa elemeti. Dari (c), dapat dilihat bahwa kesimpulan AEE-1 adalah salah jika ada beberapa S dalam P.

Seperti contoh lain, perhatikan EAE-I

All M is P

All S is M

No S is P

Ini valid karena dapat dilihat dari Gambar 3.16 (c).

Diagram Venn yang mencakup quantifier "Some" adalah sedikit lebih stlit untuk digambarkan. Baris umum untuk inenggambarkan syllogism catagorcal di bawah pandangan Boolean hares tidak ada anggota dalam pernyataan A d E yaitu :

156

I

1. Jika kelas kosong, dinaungkan.

2. Perenyataan universal, A dan E, selalu digambarkan sebelum yang khusus.

3. Jika kelas mempunyai minimal satu anggota, tandailah dengan *.

4. Jika pernyataan tidak menentukan dimana dua jenis (adjacent) obyek muncul,tempatkan * pada baris antara jenis-jenis.

5. Jika are telah dinaungkan/ditempatkan, tidak ada * dapat diletakkan didalamnya.

Seperti dalam contoh :

Some computers are laptops

All laptops are transportable

Some transportables are computers

yang dapat diletakkan dalam type IAI-4 :

Some P are M

All M are s

Some S are P

s P s P s P

M M M

(a) Vain Dlmmn (b) After Major P,emhe (c) After lrBrar Poendae

Gambar 3-15 Prosedur Keputusan untuk Silogisme AEE-1

157

Figure 3-15 Decision Procedure for Syllogism AEE-1

M M M

(a) Van Diagram (b) After Major Tenn (c) After Minor Tam

Gambar 3-16 Prosedur Keputusan untuk Silogisme EAE-1

Mengikuti baris 2 dan 1 untuk diagram Venn, kita mulai dengan pemyataan universal untuk premise minor dan menempatkannya seperti ditunjukkan dal to Gambar 3.17 (a). BAris 3 berikutnya diterapkan untuk premise pokok tertentu dan * digambarkan seperti ditunjukkan dalam Gambar 3.17 (b). Jika kesimpulitn "Some transportable are computer" ditunjukkan dalam diagram, maka akin mengikuti bahwa argumen IAI-4 adalah syllogism yang valid.

S P S P

M

(a)MIMseS (b) Some P an M

Gambar 3-17 Silogisme Tipe IAI-4

158

3.6.BARIS INFERENCE.

Meskipun diagram Venn merupakan prosedur keputusan untuk syllogism, diagram merupakan yang tidak sesuaii untuk argumen yang!ebih komplek karena diagram menjadi lebih sulit untuk dibaca. Namun demikian, ada problem yang lebih fundamental dengan syllogism karena syllogism tersebut mengalamatkan hanya porsi kecil dari kemungkinan pernyataan logical. Khusunya, syllogism catagorcal hanya mengalamatkan pernyataan catagorical dari bentuk A, E, I, dan 0.

Logika proporsioanl menawarkan arti penjelasan argumen yanglain. Sesungguhnya, kita sering menggunakan logika proporsional tanpa merealisaskannya. Misalnya, perhatikan argumen proporsional berikut ini :

If there is power, the computer will work There is power

The computer will work

Argumen ini dapat adiekspresikan dengan cara formal dengan menggunakan huruf untuk menunjukkan proporsi sebagai berikut :

A = There is powerB = The computer will work

dan sehingga argumen dapat dtuliskan seperti

A -3 BA

B

Argumen seperti ini sering terjadi. Skema umum untuk menunjukkan argumen dari type ini adalah

p -4 qp

q

dimana p dan q adalah variabel logikal yang dapat menunjukkan suatu pemyataan. Penggunaaan variabel logikal dalam logika proporsional memungkinkan type

159

yang lebih komplek dari pernyataan dibandingkan dengan bentuk emp tt asyllogistic A, E, I, dan O. Skema inference bentuk proporsional ini diseblrt dengan berbagai nama "Direct reasoning, modus ponens, law of detachment" dan "assuming the antecedent".

Perhatikan bahwa contoh ini dapat juga diekspresikan dalam bentuk syllogistic :

All computers with power will work

This computer has power

This computer will work

yang mendemonstrasikan bahwa "modus ponen" sebenarnya kasus khusus dari logika syllogistic. "Modus ponen" sangat penting akrena membentuk ba4s dari expert system yang berdasarkan bans. Proporsi gabungan p -4 q, berhubungajn dengan bans sementara p berhubungan dengan pola yang harus menggabungk�n antecedent (kejadian sebelumnya) untuk baris agar dipenuhi. Namun demikiaf, seperti didiskusikan dlam Bab-02, kondisional p -4 q benar-benar tidak san a dengan bans karena kondsonal adalah definisi logikal yang ditentukan oleh tabol kebenaran dan ada beberapa kemungkinan definisi dan kondisional.

Pada umumnya kita akan mengikuti konvensi teori logika dengajn

menggunakan huruf kapital seperti A, B, C, untuk menunjukkon proporsikonstanta seperti "There is power". Huruf kecil seperti p, q, r, ... akajn menunjukkan variabel logika. yang dapat berdiri untuk proporsi konstanta yag berbeda.Perhatikan bahwa konvensi ini kebalikan dari PROLOG yaig inenggunakan huruf besar untuk variabel.

Skema "modus ponens" juga dapat dituliskan dengan vanabel logika yang d

beri nama seperti :

r s

rs

dan skema akan tetap mempunyai arti sama.

Notasi lain untuk skema ini adalah :

r, r -+ s; s

160

dimana yang umum digunakan untuk memisahkan satu premise dari premise lain dan titik koma menunjukkan akhir dari premse. Meskipun sejauh ini hanya dilihat pada argumen dengan dua premises, bentuk argumen yang lebih umum adalah :

11 D 2' PN; C

dimana huruf besar P, menunjukkan premses seperti r, r -4 dan C adalah kesimpulan. Perhatikan bagaimana mempersamakan pernyataan pemenuhan tujuan dari PROLOG yang didiskusikan dalam Bab-02.

P P1, P2,

Tujuan, p, dipenuhi jika seluruh sub tujuan p1, p21 p3, ... dipenuhi. Argumen

enalogus untuk bans produksi dapat dituliskan dalam bentuk umum,

cl A C2 A C

yang berarti bahwa jika setiap kondisi, C1, dari suatu baris dipenuhi, maka aksi dari suatu baris akan dikerjakan. Seperti didiskusikan sebelumnya, pernyataan logika dan kondisional tidak sama dengan baris produksi. Namun demikian, bentuk logika ini merupakan tambahan intuitif yang berguna dalam memikirkan tentang baris.

Notasi untuk operator logika AND dan OR mempunyai bentuk yang berbeda dalm PROLOG dibandingkan dengan A dan v (3tasa. Koma antara sub tujuan dalam PROLOG berarti konjungsi, A, sedangkan diskonjunction, v, ditunjukkan dengan titik koma. Misalnya :

P P1. P2.

berarti bahwa p dipenuhi jika p1 dan p2 dipenuhi. Konjungsi dan diskonjungsidapat digabungkan. Misalnya :

P P1, P2. P3 1 P4.

sama dengark dua pernyataan PROLOG :

161

p :- Pl, P2

p p3, p4

Pada umumnya, jika premises dan kesimpulan seluruhnya adalah skemata,

maka argumen :

p1• P2, PN; A

secara formal argumen deduktif yang valid jika dan hanya jika :

p1 A P2 A PN; -4 C

adalah tautology. Seperti dalam contoh :

(P A q) -> P

adalah tautology karena benar untuk suatu angka, T, atau F, dari p dan q. Kitadapat menentukan dengan membuat tabel kebenaran.

Argumen dari "modus ponens",

P -3 q

P

q

adalah valid karena dapat diekspresikan sebagi tautology.

(P A q) A -* q

162

Perhatikan bahwa kita menganggap bahwa anak penah mempunyai hak yang lebih rendah dibandingkan dengan konjungsi dan dis-konjungsi. Hal ini akan menghemat penulisan tambahan tanda kurung seperti :

((P --4 q) A -* P) -+ q

Tabel benar untuk "modus ponens" ditunjukkan dalam Tabel 3.4. Ini

merupakan tautology jika angka argumen, ditunjukkan dalam kolom sebelah kanan, seluruhnya tidak masalah angka dari premisesny. Perhatikan bahwa dalam kolom ketiga, keempat, dan kelima, angka benar ditulsikan dibawah operator tertentu seperti - dan A. Ini disebut dengan "main connectives" karena tidak dapat menghubungkan dua bagian utama dari proposisi yang disusun.

P q P-4q (P -4 q) A P (P ---> q) A P -- q

TT T T T

TF F F T

F T T F T

F F T T

Tabel 3-4 Tabel Kebenaran untuk Poner Modus

Meskipun metode penentuan valid argumen ini bekerja, tetapi tidak memerlukan checking setiap baris dari tabel kebenaran. Jumlah tanda panah adalah 2N dimana N adalah angka promises dan sehingga bans inference sangat cepat dengan sejumlah premises. Misalnya, lima premises akan emerlukan 32 kaata untuk di-check sementara sepuluh premises memerlukan 1024 bans. Metode yang lebih pendek dari penentuan argumen valid adalah hanya mempertimbangkan baris dari tabel benar dimana premises seluruhnya benar. Definisi yang lama dan argumen valid menyatakan bahwa itu valid jika dan hanya jika kesimpulan benar untuk masing-masing baris tersebut. Yaitu, kesimpulan ditunjukkan secara tautology oleh premises. Untuk "modus ponens" premise p -* q dan premise p

keduanya hanya benar di dalam baris pertama, dan demikian dalam kesimpulan.

163

Dengan demikian, "modus ponens" adalah argumen valid. Jika ada bans lain dimana premise seluruhnya benar dan kesimpulan salah, maka argumen akan tidak valid.

Cara yang lebih pendek dari peng-ekspresi-an tabel benar untuk "modus ponens" ditunjukkan dalam Tabel 3.5 dimana seleuruh bans secara eksplisit ditunjukkan. Pada praktiknya, hanya bans yang mempunyai premises benar seprd bans pertama diperlukan utnuk dipertimbangkan.

Premises Conclusion

p q p -- q p q

T T T T T

T F F T F

F T T F T

F F T F F

Tabel benar untuk "modus ponens" menunjukkan bahwa itu valid karega bans pertama mempunyai premise benar dan kesimpulan benar, dan tidak ada bans lain yang mempunyai premise benar dan kesimpulan salah.

Argumen dapat palsu. Untuk menunjukkan hal ini, pertama perhatikan contch valid berikut ini dari "modus ponens"

If there are no bugs, then the program compiles

There are no bugs

The pgorgram compiles.

Bandingkan dengan argumen berikut ini dimana ada sedikit persamaan

"modus ponens"

If there are no bugs,. then the program compiles

There program compiles

The are no bugs

164

Apakah itu merupakan argumen valid ? Skema untuk argumen dari type ini

adalah :

p p - q

q p

dan tabel benar dengan bentuk pendek ditunjukkan dalam Tabel 3.6.

Perhatikan bahwa argumen ini tidak valid. Meskipun baris pertama menunjukkan bahwa kesimpulan benar jika seluruh premise benar, baris ketiga menunjukkan jika premise benar, kesimpulan salah. Dengan demikian argurnen gagal jika dan hanya jika kriteria argumen valid. Meskipun beberapa program ingin argumen seperti ini benar, tetapi logika (dan pengalaman) membuktikannya "fallacy" atau argumen yang tidak valid. Argumen fallacious ini disebut dengan "fallacy of the converse".

Premises Conclusion

p q p-* q q p

T T T T T

T F F F T

F T T T F

F F T F F

Tabel 3-6

Tabel Kebenaran bentuk pendek dari p - q, q; .. p

Seperti contoh lain, skema argumen :

p -4 q

-q

wp

165

adalah valid jika Tabel 3.7 menunjukkankesimpulan benar hanya jika premise benar.

Premis Kesimpulan

p q p > - q - -q -PTT T F F

TF F T T

FT T F T

FF T T T

Tabel 3-7 Tabel Kebenaran bentuk-pendek p -4 q, -q; .% -p

Sekema khusus ini disebut dengan berbagai nama : "indirect reasoning; modus tollens," dan "law of contraposition".

"Modus ponens" dan "modus tollens" adalah baris inference. kadang-kadang

disebut "lawa of inference". Tabel 3.8 menunjukkan law of inference.

Nama Latin modus berarti "car" sedangkan "ponere" berarti "penyisipan" dan "tollere" berarti "mengingkari". Nama riil dari baris "modus" dan anti literalnya adalah ditunjukkan dalam Tabel 3.9. "Modus ponens" dan "modus tollens" adalall pendek untuk dua type pertama (Stebbing 50). Angka Rule of Inferenc$ berhubungan dengannya dalam Tabel 3.8.

166

Hukum Inferensi

1. Hokum Data Skema

2.Hukum kontra positif

3. Hukum Modus Tollen

4.Aturan Rangkaian(Hukum Silogisme)

5. Hukum Inferensi Disjunletif

6.Hukum Negasi Dobel

7. Hukum De Morgan

8. Hukum Penyederhanaan

9. Hukum Konjungsi

Skema

p -* qp

q

p - q-q -> -p

p -> q-q

-q

p -* qq -4 r

per

p v q p v q _p -q

q . p

_(_p) p

-(p v q) - - (p v q) -p v -q -p A -q

P A q p v q p .q

p

q PA q

10.Hukum Konjungsi ppv q

11. Hukum De Morgan --(p A q) -(p A q)p q

-q P

Tabel 3-8 Beberapa aturan Inferensi untuk logika yang benar

167

HukumBilangan Nama

Interferensi

1 modus ponendo ponens

3 modus tollendo tollens

5 modus tollendo ponens

11 modus ponendo tollens

Table 3-9Arti Modus

Meaning"mood which by... "

penguatan, menguatkan

penolakan, menolak

penolakan, menguatkan

penguatan, menolak

Baris inference dapat diterapkan pada argumen dengan lebih dari dua premise. Misalnya, perhatikan argumen berikut ini :

Chip prices rise only if the yen rises.

The yen rises only if the dollar falls and if the dollar falls then the yen rises.

Since chip prices have risen,

the dollar must have fallen.

Proporsi dapat ditentukan sebagai berikut

C = chip princes rise

Y = yen risesD = dollar falls

Panggil kembali dari bagian 2.12 dimana salah satu arti kondisional adalah "p, only if q". Proposisi seperti "The yen rises only if dollar falls" mempunytai arti ini sehingg ditunjukkan sebagai C - Y. Seluruh argumen mempunyai bent>ik berikut ini :

C -4 -Y

(Y -� D) A (D -- Y)

C

D

168

Premise kedua mempunyai bentuk menarik yang dapat lebih lanjut dikurangi dengan menggunakan varian kondisional. Kondisional p -+ q mempunyai beberapa yang "converse" inverse, dan contrapositive". Ini diberikan dalam daftar dengan kondisional, untuk kelengkapan dalam Tabel 3.10.

Kondisional p -3 q

Konversi q-*p

Inversi -P -q-q

Kontra Positif * - -p

Tabel 3-10 Kondisional dan Variant-nya

Seperti biasanya, dianggap bahwa operator negation/perundingan mempunyai prioritas lebih tinggi dibandingkan dengan operator logika dan sehingga tidak ada tanda kurung yang digunakan sekitar -p dan -q.

Jika kondisional p -) q dan kebalikannya q -* p keduanay benar, maka p dan q sama. Yaitu p ---� q A q --> p sama dengan dua kondisional p t* q atau sama =-. Dengan kata lain, p dan q selalu mempunyai angka yang smaa. Jika p adalah T dan q adlaah benar dan jika p adalah F mak q adalah juga F. Argumen akan menjadi :

(1) C -* Y

(2) Y = D( 3) C

D

dimana angka sekarang digunakan untuk menunjukkan premises. Jika Y dan D sma dari (2), kita dapat mengganti D untuk Y dalam (1) untuk bidang :

(4) C -4 D

dimana (4) merupkan inference yang dibuat pada basis (1) dan (2). Premises (3) dan (4) dan kesimpulan adalah :

169

(4) C p - D(3) C

D

yang dapat ditentukan sebagai skema "modus ponens". Dengan demikian argumen akan valid.

Penggantian dari satu variabel yang sama ke yang lain adalah baris inference yang disebut "rule of substitution". Bans "modus ponens" dan penggantin adalah dua bans pokok dari logika deduktif.

Bukti logika formal biasanya dituliskan dengan pembuatan angka premises, kesimpulan dan inference seperti ditunjukkan berikut ini :

1. C -*Y

2 . (Y --�D) A (Dn Y)

3. C / D

4. Y =- D 2 Equivalence

5. C --* D 1 Substitution

6. D 3,5 Modus Ponens

Bans 1, 2 dan 3 adalah premises dan kesimpulan sementara 4, 5, dan 6 adalah infere yang didapatkan. Kolom sebelah kanan memberikan daftar baps inference dan angka bans digunakan untuk mengatur inference.

3x7 BATASAN DARI LOGIKA PROPORSIONAL.

Perhatikan argumen klasik yang kita kenal ini,

All men are mortal

Socrates is a man

Therefore, Socrates is mortal

170

Kita tahu bahwa argumen tersebut adalah argumen valid jika berupa syllogism valid. dapatkah kita membuktikan ke-valid-an tersebut dengan menggunakan logika proporsional ?. Untuk menjawab pertanyaan ini, pertama kali marl kita menuliskan argumen sebagia skema.

p = All men are mortalq = Socrates is a manr = Socrates is mortal

dan sehingga skema argumen adlah :

P q

r

Perhatikan bahwa tidak ada hubungan di dalam premises atau kesimpulan sehingga setiap premises dan setiap kesimpulanharts mempunyai variabel logikal yang berbeda. Juga, logika preposisional tidak mempunyai provisi untuk quantifier sehingga tidak ada cara untuk menunjukkan quantifier "semua" di dalam premise pertama. Satu-satunya representasi argumen ini di dalam logika proporsional adalah. skema di atas dari tiga variabel yang bebas.

Untuk menentukan jika argumen tersebut valid, perhatikan tabel benar dari tiga variabel bebas untuk seluruh kemungkinan kombinasi dari T dan F yang ditunjukkan dalam Tabel 3.11.

p q r

T T TT T FT F TT F FF T TF T FF F TF F F

Tabel 3-1-1 Tabel Kebenaran untuk skema p, q; .. r

171

Baris kedua dari tabel benar ini menunjukkan argumen untuk tidak valid karena premises benar sementara kesimpulan salah.

Validitas dari argumen ini harus "tidak" diintepretasikan seperti apti kesimpulan yang tidak benar. Seseorang akan menentukannya sebagai argumen yang benar. Ketidak-valid-an sederhana berarti bahwa "argument tidak daplat dibuktikan di bawah logika proporsional". Misalnya, kita akan memberi atribut pada beberapa arti "semua" dan mempertimbangkan "men" sebagai bentuk jam8n dari "man". Namun demikian, syllogism dan kalkulus proporsional tidak memungkinkan struktur preposisi internal untuk diuji. Batasan ini diatasi olth logika predikat dan argumen ini adalah merupakan argumen valid di bawwh logika predikat. Kenyataannya, selluruh logika syllogistic merupakan subset ya�n

valid dari order pertama logika predikat dana dapat dibuktikan dengan valid dibawhanya.

Satu-satunya bentuk syllogistic yang valid dan preposisi adalah

If Socrates is a man, then Socrates is mortal. Socrates is a man.

Therefore, Socrates is mortal.

Lihat :

p = Socrates is a man

q = Socrates is mortal

Argumen ini akan menjadi :

p� q p

q

yang merupakan bentuk "modus ponens" syllogism yang valid.

Seperti contoh lain, perhatikan argumen klasik berikut ini

All horses are animals

Therefore, the. head of a horse is the head of animal

172

String di atas merupakan teori dari formal system tersebut (Minsky 67).

Meskipun string seperti 11111 tidak terlihat seperti type teori yang kita

gunakan untuk melihat, apakah merupakan teori logika yang valid. Teori khusus ini juga mempunyai arti semantik karena teori tersebut merupakan angka aneh yang diekspresikan dalam "unary number system" drai symbol tunggal 1. Hanya sebagai system angka binary yang hanya mempunyai symbol aalphabet 0 dan 1, system angka unary hanya mempunyai symbol tunggal 1. Angka di dalam unary dan system desimal diekspresikan sebagai :

Unary Decimal

I

11 2

111 3

1111 4

11111 5

dan seterusnya.

Perhatikan bahwa karena bans inferece dan aksioma, string 11, 1111, dan seterusnya tidak dapat diekspresikan dalam system formal. Yaitu, 11, dan 1111 adalah string dari alphabet formal, tetapi bukan teori atau wffs karena tidak dapat dibuktikan dengan menggunakan hanya bans inference dan aksioma. System formal ini memungkinkan hanya derivasi - dari angka aneh, bukannya angka. Aksioma "11" hares ditambahkan aagar dapat memperoleh angka.

Property system formal lainnya adalah "completeness". Rangkaian aksioma merupakan "complete" jika setiap wff dapat dibuktikan atau "refuted". Bentuk refute berarti untuk membuktikan beberapa penyisipan/assertion salah. Dalam system lengkap, setiap eff vlid secara logikal merupakan teori. Namun demikian, jika logika predikat tidak dapat diputuskan, maka akandatang dengan pembuktian yang berdasarkan pada keberuntungan dan kepandaian. Tentu saja, kemungkinan lain adalah penulisan program komputer yang akan mencoba mendapatkan pembuktian dan membiarkannya (grind away).

Property yang dapat diinginkan lebih lanjut dari system logika adalah dapat di-"sound". Sound systemberarti bahwa setiap teori adalah merupakan wff valid secara logikal. Dengan kata lain, sound system tidak akan memungkinkan kesimpulan untuk di-infered yang bukan konsekuensi premses logikal. Tidak ada argumen yang tidak valid yang akan di-infered sebagai valid.

179

Ada perbedaan "order" logika. Bahasa "first order" ditentukan sehingga quantifier akan mengoperasikan pada obyek variabel seperti V x. Bahasa "second order" harus mempunyai feature tambahan seperti dua macam variabel dan quantifier. Sebagai tambahan pada variabel dan quantifier ordering, logika second-order dapat mempunyai quantifier yang mengatur atas fungsi dan symbol predikat. Contoh dari logika second order adalah "equality axiom", yang menunjukkan bahwa dua obyek akan lama jika seluruh predikatnya sama. Jika P adalah predikat dari satu argumn, maka :

x = y (b' P) [P (x) H P(Y)1

merupakan pernyataan dari aksioma yang sama dengan menggunakan order quanr

tifier, V p, yang mengatur seluruh predikat.

3.10. RESOLUSI.

Resolusi baris inference yang sangat handal diperkenalkan oleh Robinson pada tahun 1965 adalah pada umumnya diimplementasikann dalaam teori untuk membuktikan program Al (Robinson 65). Kenyataantlya, resolusi merupakaon bans inference yang utama dalam PROLOG. Sebagai penganti beberapa inference bans yang berbeda dari kemampuan yang terbatas seperti "modus ponens, models tollens, merging, chaining" dan sebagainya, PROLOG menggunakan satu inference bans resolusi untuk tujuan umum. Aplikasi resolusi ini membuat teori secara otomatis membuktikan seperti PROLOG peralatan praktis untuk pemecah4n problem. Sebagai pengganti dari keharusan mencoba bans inference yang berbeda dan mengharapkan sate keberhasilan, bans resolusi tunggal dapat diterapkan. Pendekatan ini dapat secara besar mengurangi spasi penelitian.

Sebagai cara dari pengenalan resolusi, pertama kali maxi kita perhatikan syllogism tentang Socrates yang diekspresikan dalam PROLOG sebagai berikat, dimana perintah/komentar ditunjukkan dengan tanda %.

mortial(x) man W.

man(socrates).mortal (cocrates).

yes

180

% All men are mortal

% Socrates is a man

% Query - is Socrates mortal?% PROLOG answers yes

PROLOG menggunakan notasi "quantifier-free". Perhatikan quantifier uivresal, V, diimplikasikan dalam pernyataan yang semua orang laki-laki adalah mortal.

PROLOG didasarkan pada logika predikat first-order. namun demikian juga mempunyai angka ekstensi unntuk membuatnya lebih mudah untuk aplikasi pemrograman. Feature pemrograman khusus ini melanggar logika predikat Yang jelek dan disebut dengan "extralogical feature" input/output, cut (yang mengubah spasi penelitian) dan assert/retract (untuk mengubah angka benar tanpa dasar kebenaran logikal).

Sebelum resolusi dapat diterapkan, wff hdrus berada dalam "normal" atau

bentuk standard. Tiga type utama dari bentuk formal adalah "conjunctive normal

form", bentuk clausal, dan subset klause Horn. Idee pokok dari bentuk formal adalah untuk mengekspresikan wffs dalam bentuk standard yang hanya menggunakan n, v, dan mungkin -. Metode resolusi kemudian diterapkan untuk bentuk wffs normal dimana seluruh hubungan lain dan quantifier telah dihilangkan. Konversi ke bentuknormal ini perlu karena resolusi merupakan suatu operasi pasangan dari (disjunct) yang membuat (disjuncts) baru, yang menyederhanakan wff.

Berikut ini mengilustrasikan wff dalam bentuk konjungtif, yang ditentukan sebagai konjungsi dari (disjunctions) yang "literal".

p1 v p2 v • ) A (Q1 V Q2 v ) n.. (Z1 V Z2 V

Bentuk semacam Pi harus berupa literal, yang berarti bahwa bentuk tersebut tidak berisi hubungan logikal seperti kondisional dan bocondisional, aatau quantifier. Literal merupakan formula atomik atau formula atomik yang dirundingkan. Misalnya, wff berikut ini :

(A v B) v (-B v c)

adalah bentuk normal konjungtif. Bentuk di dalam kurung adalah klause.

A V B v -B v C

181

Seperit yang akan diperlihatkan nanti, suatu wff logika predikat, yang mencakup logika proporsional sebagai kasus khusus, dapat dituliskan sebagai klause. "Clausal form" penuh dapat mengekspresikan formula logika predikat

tetapi tidak sebagai natural atau dapat dibaca untukorang (Kowalski 79). Syntak PROLOG adalah subset klause Horn yang membuat teori mekanik yang dibuktikan dengan Iebh mudah dengan PROLOG dan efisien untuk mengimplementasikan dibandingkan dengan notasi logika predikat standar atau bentuk klausal penuh. Seperti disebutkan di dalam Bab-01, PROLOG mmungkinkan hanya satu head/ kepala. Ekspresi bentuk klausal penuh pada umumnya dituliskan dalam bentuk khusus yang disbeut Kowalski bentuk klausal :

A,, A2 , ... AN --> Bl, :B2 , BM

yang diintepreasikan bahwa jika seluruh sub tujuan A1, A2, ... AN adalah benar, maka satu atau lebih B 1 atau B2, ... atau BM adalah juga benar. Perhatikan bahwa kadang-kadang tujuan anak panah dibalik dalam notasi ini. Klause ini dituliskan dalam notasi predikat standard adalah :

Al v A2 AN -4 Bl v B2 BM

Ini dapat diekspresikan dalam "disjunctive form" sebagai disjungsi literal yangmenggunakan persamaan

p --3 q - = --p v q

sehingga

Al v A2 AN -* B1

(A

v B2 BM

AN) V (Bi V B2 BM) l A A2

_ _ -(Al v

=-A1

dimana hukum Morgan

-(P A q) = -p v -q

182

-A2 "AN v Bl v B2 BM.

digunakan untuk mempermudah ekspresi terakhir.

Seperti didiskusikan dalam Bab-01, PROLOG menggunakan type bentuk klausal terbatas. Klause Horn, dimana hanya satu head/kepala dimungkinkan

A,,A2, ... AN -3 B

yang ditulsikan dalam syntak PROLOG sebagai

B : - A,,A2, ... AN

Problem dengan percobaan untuk membuktikan teori secara langsung adalah sukar dalam menguranginya dengan hanya menggunakan baris inference dan aksioma system. Hal ini akan memakan waktu yang sangat lama untuk mendapatkan teori atau kita mungkin tidak cukup pandai untuk mendapatkannya sama sekali. Untuk membuktikan teori benar, metode klasikal dari "reductio ad absurdum" atau metode kontradiksi, digunakan. Dalam metod ini, kita mencoba membuktikn wff yang dirundingkan/negated adalah teori. Jika basil kontradiksi, mka wff non-negated ash adalah teori.

Tujuan resolusi pokok adalah untuk meng-infer klause barn, "resolvent" dari dua klause yang disebut "parent cluses". Resolvent akan mempunyai bentuk yang lebih sedikit dibandingkan dengan induk. Dengan melanjutkan proses resolusi, kontradiksi secara kebetulan akan diperoleh atau proses akan berakhir karena tidak ada kemajuan yang dibuat. Contoh sederhana dari resolusi ditunjukkan dalam argumen berikut ini.

A v B

A v -B

.V A

Satu cara. untuk melihat bagaimana kesimpulan mengikuti adalah dengan menuliskan premises sebagai :

(A V B) A (A v -B)

183

Salah satu Aksioma distribusi adalah :

p v (q n r) _ (p v q) A (p v r)

Dengan menerapkan ini ke premises akan memberikan

(A v B) A (A v --B) = A v (B A -B) = A

dimana langkah terakhir yang mengikuti sejak (B A -B) selalu salah. Ini mengikuti dari hukum Excluded Middle yang menyatakan bahw segalanya tidak dapat benar San salah. Dalam logika fuzzy yang didiskusikan dalam Bab-05, kita akan melihat hukum ini tidk ada. Cara lain dari penulisan ini menggunakan benti k "nit" atau "null", yang berarti kosong, tidak ada atau salah. Misalnya, pointer nill dalam Pascal akan tidak mengambil apa-apa, sementara Hukum Excluded Middle menyatakan (B A -B) = nil.

Contoh resolusi menunjukkan bagaimana klause induk (A v B) dan (Av-'B)' dapat disederhanakan ke dalam resolvent A. Tabel 3.13 memberikan ringkasan beberapa klause induk pokok dan resolventnya dalam notasi klause, dimana koma memisahkan klause berarti A.

Clause sekarang Resolven Arti

p -+ q, p q Ponen Modusor

_pvq,p

p -4 q, q - r p -4 r Rangkaian atau silogismeor or Hipotetis

-pvq,-qvr -pvr

-p v q p v q Penggabungan

-p v --4, p v q -p v p Benar (Ulangan)or

�qvq

-p, p nil Salah (Kontradiksi)

Tabel 3-13 Klausa dan Resolven

184

3.11.SYSTEM RESOLUSI DAN DEDUKSI.

Dengan diberkan wffs Ap A2, ... An dan kesimpulan logika atau teori C,kita tahu :

A,,A2 . AN + C

lama dengan menyatakan

( 1 ) Al A A2 AN - C -- (A1 A A2 AN) V C

---A1 v A2 -A N v C

adalah valid. Anggap kita mengambil (negation) sebagai berikut

[A, A A2 AN -> C]

Sekarang

p -� q = -p v q

sehingga di atas akan menjadi

--[Al A A2 ANA C] = - --[-A1 A A2 AN)V C]

Dari hukum morgan

(p A q) = -P A q

sehingga di atas akan menjadi

( 2 ) --[Al A A2 A N C] [--(Al A A2 AN) A C

Al A A2 --AN .A -C

185

Sekarang jika (1) valid, maka (negation)-nya (2) hares tidak valid. Dengas kata lain jika (1) tautology maka (2) hares kontradiksi. Formula (1) dan (25 menunjukkan dua cars persamaan dalam pembuktian bahwa formula C adalab teori. Formula (1) dapat digunakan untuk membuktikan teori dengan checking untuk melihat apakah benar dalam semua kasus. Demikian pula, formula (2) dapat digunakan untuk membuktikan teori dengan menunjukkan (2) yang menuntun ke kontradiksi.

Seperti disebutkan dalam bagian depan, pembuktian teori dengan menunjukkan (negation)-nya menuntun ke kontradiksi adalah membuktikandengan "reductio ad absurdum". Bagian pokok dari type pembuktian ini adalah"refutation". Untuk (revute) sesuatu berarti membuktikan salah. Resolusi adalah suara bans inference yang juga "refitation complete" karena klause kosong akan selalu menghasilkan jika ada kontradiksi di dalam set klause. Pada pokoknya, ini berarti bahwa "resolution refutation" akan berakhir dalam angka langkah terbatas jika ada kontradiksi. Meskipun resolusi refutation tidak dapat mengatakan kith bagaimana membuat teori, tetapi akan secara definit mengatakan jika wff adalah teori.

Contoh sedeerhana dari pembuktian dengan resolusi refutation, perhatikan argumen :

A -4 B

B -4 C

C -� D

A -+ D

Untuk membuktikan bahwa kesimpulan A - D adalah teori dengan resolusi refutation, pertama kali mengubahnya ke dalam bentuk disjungtif dengan menggunakan persamaan :

p > q = -p v q

Sehingga

A - D = -A v D

dan negation-nya adalah

186

-(-- v D) - A A -D

Konjungsi dari bentuk disjungtif dari premises dan kesimpulan yang di-negated memberikan bentuk konjungtif normal yang sesuai untuk resolusi refutation.

(-A v B) A (--B v C) A (--C v D) A A A -D

Metode resolusi sekarang dapat diterapkan pada premises dankesimpulan. Gambar 3.18 menunjukkan metode yang menunjukkan resolusi refutation dalam bentuk diagram "resolution refutation tree", dimana klause pada alevel yang sama akan dipecahkan. Akar, yang merupakan resolvent akhir, adalah nol seperti yang bisa diperoleh dari bans terakhir dari Tabel 3.13 untuk -p, p dan sehingga kesimpulan asli A -* D adalah teori.

�AvB -Svc

nil

Gambar 3-18 Pohon Penolakan Resolusi

187

3.12. PEMBERIAN ALASAN CASUAL (TIDAK FORMAL) DAN

TIDAK SERIUS.

System resolusi dan system bans produksi adalah dua paradigma yang populet untuk pembuktian teori. Meskipun banyak orang memikirkan teori di dalam anti matematika, kita telah melihat bahwa teori sebenarnya kesimpulan dari argumen logika yang valid. Sekarang perhatikan expert system yang menggunakan rangkaian inference. Pada umumnya, rangkaian yang lebih panjang menunjukkan pengetahuan yang dalam atau yang lebih tidak formal (casual), sementara pemberian alasan yang tidak seerius pada umumnya menggunakan bans tunggal atau sedikit inference. Disamping itu, panjang rangkaian inference, kualitas pengetahuan dalam bans juga merupakn faktor pokok dalam menentukan dalam dan dangkalnya pemberian alasan. Kadang-kadang definisi lain dari pengetahuati

dangkal digunakan, disebut dengan "exprimental knowledge", yang merupakan pengetahuan yang berdasarkan pengalaman.

Kesimpulan dari rangkaian inference adalah teori karena dibuktikan oleh

rangkaian inference, seperti didemonstraskan oleh contoh sebelumnya.

A -+ B, B --� C, C -+ D I A -+ D

Kenyataannya, expert system yang menggunakan rangkaian inference untuk membuat kesimpulan, menggunakan teori. Hasilnya sangat penting karena kita tidak dapat menggunakan expert system untuk inference casual. Sebagai pengganti, expert system akan dibatasi pada inference dangkal dari baris tunggal yang tdk mempunyai rangkaian.

Mari kita lihat pada beberapa baris untuk kontrask dangkal dan dalamnya pembenarr alasan yang lebih baik. Seperti dalam contoh pertama kali, perhatikan baris benkut ini, dimana jumlah tanda kurung merupakan tujuan identifikasi saja.

(1) IF a car hasa good battery good sparkplugs

gas

good tires

THEN the car can move

188

Hal ini merupakan basis yang sungguh bagus yang dapat digunakan di dalam expert system.

Salah satu feature penting dari expert system adalah fasilitas keterangan, seperti didiskusikan di dalam Bab-01. Baris didasarkan pads expert system akan membuatnya mudah bagi system untuk menerangkan pemberian alasannya. Dalam hal ini, jika pemakai menanyakan mengapa mobil dapat berpindah, expert system dapat menjawab dengan membuat daftar elemen kondisional :

a good battery good sparkplugs

gas

good tires

Ini merupakan type fasilitas penjelasan dasar sejak system hanya memberikan daftar elemen kondisional dari suatu bans. Fasilitas penjelasan yang lebih canggih dapat di-design untuk daftar bans sebelumnya yang telah dibuat dan dihasilkan dalam firing basis tertentu. Fasilitas penjelasan lainnya mungkin memungkinkan pemakai untuk menanyakan type pertanyaan "What if' untuk mengeksplore alternatif path pemberian alasan.

Bans ini jugs merupakan contoh dari "shallow reasoning". Yaitu, ada sedikit atau tidak ada pemahaman penyebab dan efek dalam pemberian alasan yang dangkal karena ada sedikit atau tidak ada rangkaian infrence. Baris sebelumnya pada pokoknya heuristik dimana seluruh pengetahuan diisi dalam basis. Baris kemudian akan diaktifkan jika elemen kondisionalnya dipenuhi dan tidak karena ada pemahaman oleh expert system atas apa fungsi perform elemen kondisional. Dalam pemberian alasan yang dangkal, ada sedikit atau tidak ada "causal chain" dari penyebab dan efek dari satu bans ke baris lainnya. Dalam kasus yang sederhana, penyebab dan efek berisi di dalam satu atau tanpa hubungan ke bans lainnya. Jika kita memikirkan basis di dalam bentuk (chunk) pengetahuan yang didiskusikan dalam Bab-01, pemberian alasan yang dangkal tidak akan membuat hubungan antara (chunk) dan akan menjadi seperti reaksi reflek sederhana.

Keuntungan dari pemberian alasan yang dangkal dibandingkan dengan pemberian alasan casual adalah mudah dalam pemrograman. Pemrograman yang mudah berarti waktu pengembangan lebih pendek, program lebih kecil, lebih cepat dan harga lebih rendah untuk dikembangkan. Janngan frame dan semantik adalah dua model yang berguna untuk pemberian alasan casual dan dalam. Bentuk "dalam" sering digunakan secara sinonim untuk pemberian alasan casual untuk

189

menunjukkan pemahaman yang dalam dari subyek. Namun demikian, pemahaman yang dalam menunjukkan bahwa disamping pemahaman rangkaian casual dimana terjadi proses, kita juga memahami proses dalam arti absrtak.

Satu expert system klasik menggunakan frame dan mempunyai pemahaman casual adalah system Steamer yang dibuat oleh US Navy untuk mengajarka:n operasi rencana dorongan kapal (Hollan 84). Expert system yang dalam merup.Acan LISP Tutor yang di-design untuk beraksi seperti intelligent tutor untuk mengajari murid LISP (Reiser 85).

Kita dapat menambahkan pemberian alasan casual untuk basis kita dengan menentukan basis tambahan seperti :

(2) IF the battery is good

THEN there is electricity

(3) IF there is electricity and the sparkplugs are good

THEN the sparkplugs will fire

(4) IF the sparkplugs fire and there is gas

THEN the engine will run

(5) IF the engine runsand there are good tires

THEN the car will move

Perhatikan bahwa pemberian alasan casual, fasilitas keterangan/penjelasan dapat memberikan keterangan yang baik dari apa masing-masing komponen mobil sejak tiap elemen ditentukan dengan basis. System casual semacam itu juga membuat lebih mudah menuliskan system diagnostik untuk menentukan efek apa komponen yang jelek. Pemberian alasan casual mungkin digunakan untuk penyaringan operasi system yang dibatasi dengan pembuatan kecepatan, ukuran memory dan peningkatan harga pengembangan.

Pemberian alasan casual digunakan untuk membuat "model" system nil yang dimiliki dalam seluruh respek seperti system riil. Model semacam itu dapat digunakan untuk simulasi untuk menjelajahi pemberian alasan hipotesa dari type pertanyaan "What if'. Namun demikian, model casual tidak selalu perlu din

190

diperlukan. Misalnya, system MUD melayani seperti konsultan dalam melatih insinyur perminyakan dan mud (Kahn 85). Pelatihan fluid, disebut mud karena persamaannya dengan mud, adalah tambahan penting dalam latihan untuk jumlah alasan, seperti cooling dan lubrikasi bit. Problem diagnosa MUD dengan mud dan perkiraan perawatan.

System casual tidak akan banyak digunakan karenna drilling enginer tidak dapat secara normal mengobservasi rangkaian casual dari kejadian yang terjadi jauh di bawah tanah. Sebagai pengganti, engineer hanya dapat mengobservasi gejala pada permukaan dan bukan kejadian lanjutan yang tidak dapat diteliti dari dialog potensial yang penting.

Situasi ini sangat berbeda dalam kesehatan dimana phisik mempunyai rentangan test diagnostik yang luas yang dapat digunakan untuk menentukan suatu kejadian. Misalnya, jika seseorang meng-komplai (mengeluh) atas perasaan

sakit, maka ahli phisik akan mengecheck sedikit. Jika ada yang lebih sedikit, akan ada infeksi sehingga test darah mungkin dilakukan. Jika test darah menyatakan infeksi tetanus, maka ahli phisik mungkin menge-check orang untuk memotong segera karena obyek yang banyak. Sebaliknya, jika pelatihan fluid menjadi garam, maka pelatihan insinyur mungkin akan mencurigai pelatihan yang telah pergi melalui domegaram. Namun demikian, tidak ada cara sederhana untuk menge-chek ini jika tidak mungkin masuk ke dalam lubangnya, dan test seismik (yang berhubungan dengan gempa) mahal dan tidak selalu dapat dipercaya. Oleh karena pelatihan engineer tidak dapat secara normal menge-test hipotesa lanjutan cara dimana ahli phisik dapat melakukan, mereka tidak mendekati problem diagnostik cara dimana ahli phisik mengerjakannya, dan MUD merefleksi pendekatan ini.

Alasan lain untuk tidak menggunakan pemberian alasan casual dalam MUD adalah bahwa ada angka terbatas dari kemungkinan diagnostik dan gejala. Hampir semua test relevan yang digunakan oleh MUD dihubungkan secara routine dan input dalam lanjutan. Ada sedikit kemungkinan dalam session pertanyaan interaktif dengan engineer untuk menjelajahi alternatif path diagnostik jika system mengetahui seluruh test relevan dan path diagnostik. Jika banyak kemungkinan path diagnostik mengikuti dengan hipotesa lanjutan yang dapat diuji, maka akan ada keuntungan pada pengetahuan casual karena engineer dapat bekerja dengan system untuk (prune) penelitian seperti path.

Karena persyaratan yang ditingkatkan untuk pemberian alasan casual, maka akan perlu mengkombinasikan bans tertentu ke dalam pemberian alasan yang dangkal. Metode resolus dalam refutasi dapat digunakan untuk membuktikan bahwa bans tunggal adalah merupakan kesimpulan benar dari bans multiple.

191

Bans tunggal merupakan teori yang akan dibuktikan oleh resolusi.

Seperti dalam contoh, anggap kita ingin membuktikan bahwa bans (1) adalah kesimpulan logikal dari bans (2) - (5). Dengan menggunakan definisi proporsional berikut ini, baris dapat diekspresikan sebagai berikut :

B = battery is good c

E = there is electricity FG = there is gas R

S = sparkplugs are good T

(1) B n S n G n T C

(2) B -* E

(3) E A S -4 F

(4) F A G -4 R

(5) R A T 9 - C

= car will move= sparkplugs will fire= engine will run

= there are good tires

Langkah pertama dalam menerapkan resolusi refutation adalah merundingkankesimpulan atau bans tujuan.

(1') -(B A S A G A T --> C) _ -[-(B A S A G A T) v Cl

-- [--B v -S v -G v -T v C)

Sekarang setiap baris lain diekspresikan dalam bentuk disjunctive dengap menggunakan persamaan seperti :

P -)q p vgand-(PAq)=-P-

untuk meletakkan versi baru berikut ini dari (2) - (5).

(2 ' )

(3' )

( 4 ' )

(5')

192

-B v E

--(E A S) v F = -E v -S v F-(F n G) v R = -F v -G v R

--(R n T) v 'C = -R v -T v C

-BvE v-SvF

nil

Gambar 3-19 Pohon Penolakan Resolusi untuk Contoh Mobil

Seperti digambarkan dalam bagian sebelumnya, cars yang tepat untuk menunjukkan resolvent yang sukses dari (1) - (5) adalah dengan resolusi refutation pohon/tree, seperti ditunjukkan dalam Gambar 3.19. Dengan dimulai darii bagian atas pohon/akar, clause ditunjukkan sebagai node yang di-(resolved) untuk membuat resolvent di bawahnya. Misalnya :

-B v E and -E v -S v F

di-resolved untuk menghubungkan

-B v -S v F

yang kemudian di-resolved dengan

-F v -G v R

193

untuk menghubungkan

-B v -S v -G v R

dan seterusnya. Untuk menyederhanakan penggambaran, resolvent terakhir

ditunjukkan bukannya digambarkan dalam setiap resolvent tunggal.

Jika akar potion nol, ini merupakan kontradiksi. Dengan refutation, kesimpulan asli :

B A S A G A T -4 C

adalah teori jika perundingannya menuntun ke kontradiksi. Baris (1) secara logikal mengikuti dari bans (2 - (5).

3.13. RESOLUSI DAN LOGIKA PREDIKAT FIRST ORDER.

Metode resolusi juga digunakan dengan logika predikat first order. Kenyataannya, hal ini merupakan mekanisme inference yang pokok dari PROLOG. Namun demikian, sebelum resolusi dapat diterapkan, wff harus diletakkan dalanfi bantuk casual. Seperti dalam contoh :

Some programmers hate all failures No programmer hates any success

No failure is a success

Menentukan predikat berikut,

P(X) = XISA PROGRAMMER

F(x) = xisa failureS(x) = xisa successH(x,y) = x hates y

194

Premises dan kesimpulan yang dirundingkan dituliskan sebagai

(1) (3 x) [P(x)A (V y) (F (y) - H(x,y)))

(2) (V X) [P(x) -+ (V Y) (S(Y) -* -H(x,Y)))

(3) -(Vy) (F (y) 4 - -S(Y))

dimana kesimpulan telah dirundingkan dalam persiapan tintuk resolusi.

Konversi ke Bentuk Clausal

Sembilan langkah berikut ini merupakan algoritma untuk mengkonversikan predikat first order wffs ke bentuk clausal. Prosedur ini diilustrasikan dengan menggunakan wff (1) dari halaman sebelumnya.

1. Penghapusan kondisional, -*, dengan menggunakan persamaan

p -9 q = -P A q

sehingga wff (1) akan menjadi

(3 x) [P(x) A (V y) (-F (y) v H(x,Y) ) )

2. Jika mungkin, penghapusan perundingan atau mengurangi skope perundinganke satu atom. Menggunakan persamaan yang ditunjukkan dalam AppendixA seperti :

_--p = p

"(P A q) _ -p v -q(3 x) P(x) _ (V x) -P(x)(V x) P(x) _ (3 x) -P(x)

3. Standarisasi variabel dalam wff sehingga gabungan atau variabel dummy dari setiap quantifier mempunyai nama unik. Perhatikan bahwa nama quantifier variabel adalah dummy. Yaitu :

195

(V X) P(x) = (V Y) P(Y) = (V Z) P(z)

sehingga bentuk standarisasi dari

(3 x) --p (x) v (V x) p (x)

adalah :

(3 x) --p(x) v (V Y) P(x)

4. Penghapusan eksistensi quantifier,', dengan menggunakan "Skolen function",diberi nama setelah logika orang Norwegia Thoralf Skolen,.Perhatikan wff :

(3 x) L (x)

dimana L(x) ditentukan sebagai predikat yang benar jika x adalah < 0. wff inidapat diganti dengan :

L(a)

dimana a adalah konstanta seperti -1 yang membuat L(a) benar. a disebut dengan konstanta Skolen yangmerupakan kasus khusus dari fungsi Skolen. Untuk kasus dimana ada quantifier universal di depan yang telah ada :

(V x) (3 y) L(x,Y)

dimana L(x,y) adalah benar jika integer x adalah kurang dari integer y. wff W berarti bahwa untuk setiap integer x ada integer y yang lebih benar dari x. Perhatikan bahwa formula tidak mengatakan bagaimana menghitung y, dengan diberikan angka untuk x. Anggap fungsi f(x) muncul dan membuat y lebih besar dari x. Sehingga wff di atas akan menjadi Skolenmized seperti :

196

(V X) L(x,f(x))

Fungsi Skolen dari eksistensi variabel dalam skope quantifier universal adalah fungsi seluruh quantifier sebelah kiri. Misalnya,

(3 u) (V v) (V w) (3 x) (t1 y) (3 z) P(u,v,w,x,y,z)

adalah Skolemized seperti

(V V) (V W) (V Y) P(a,v,W,f(v,w),Y,J(v,w,Y))

dimana a adalah beberapa konstanta dan fungsi Skolen kedua , g, harus berbedadengan fungsi pertama, f. Contoh wff kita akan menjadi :

P(a) A (V y) (-F(Y) A H(a,Y) )

5. Konversikan wff ke "prenex form"yang merupakan rangkaian quantifier, Q,diikuti dengan "matrix M". Pada umumnya, quantifier dapat berupa

V maupun 3. Namun demikian, dalam hal ini, langkah ke-4 telah

menghilangkan seluruh eksistensi quantifier sehingga Q hanya dalan berupa

V. Juga jika setiap V mempunyai variabel dummmy sendiri, seluruh V dapat dipindahkan ke sebelah kiri dari wff dan skope setiap V dapat berupa seluruh wff.

Contoh kits akan menjadi

(V y) [P(a) A (-F(y) v H(a,y)]

dimana matrik merupakan bentuk di dalam kurung.

6. Konversikan matrik ke konjungtif bentuk normal, yang merupakan konjungtif klause. Setiap klause merupakan disjungtif. Contoh kita telah ada dalam

bentuk konjungtif normal dimana satu klause P(a) dan lainnya adalah,(-F(y)

197

v H(a,y)). Jika perlu, distribusi berikut ini dapat digunakan seperlunya untuk

meletakkan matrik dalam bentuk konjungtif normal.

p v (q A r) = (p v q) A (p v r)

7. Letakkan quantifier universal sebagai seperlunya jika seluruh variabel didalam wff pada tahap ini harus digabungkan. wff sekarang adalah matrik.contoh wff kita akan menjadi :

P(a) A (-F (y) v H(a,Y))

8. Hilangkan tanda ^ dengan menuliskan wff sebagai set klause. Contoh kitaadalah :

{ P(a) , --F(y) v H(a,y) )

yang biasanya dituliskan tanpa tanda kurung seperti klause

P(a)

-F(Y) v H(a,Y)

9. Beri nama kembali variabel dalam klause, jika perlu, sehingga nama variabel yang sama hanya digunakan dalam satu klause. Misalnya, jika kits mempunyai klause :

P(x) A Q(x) v L(x,Y)

-P(x) v Q(Y)

--Q(z) v L(z,y)

ini dapat diberi nama kembali dengan :

P(x1) A Q(xI) v L(xl,yl) --P(x2) v Q(y2) -Q(z) v L(z,y3)

198

Jika kita melaksanakan prosedur untuk mengkonversikan bentuk klause premise kedua dan kesimpulan yang dirundingkan dari contoh kita, kita akhirnya mendapatkan klause :

(la) P(a)

(lb) --F(y) v H(a,y)(2a) -P(x) v S(Y) v -H(x,Y)

(3a) F (b) (3b) S(b)

dimana angka mengacu ke premises asli dan kesimpulan yang dirundingkan. Dengan demikian, premises (1) dan (3) dikonversikan ke dua klause dengan suffik (a) dan (b), sementara premise (2) dikonversikan ke klause tunggal (2a).

Penyatuan dan Baris.

Satu kali wff dikonversikan ke bentuk klausal, maka biasanya perlu mnemukan "substitution instance" yang semestinya untuk variabel. Yaitu, klause seperti

-F(y) v H(a,y)

F (b)

tidak dapat di-resolved pada predikat F hingga argumeen F bersatu. Proses penemuan substitusi bagi variabel untuk argumen bersatu disebut dengan "unification".

Penggabungan/penyatuan merupakan satu feature yang membedakan expert system dengan pohon/tree keputusan sederhana. Tanpa penyatuan, elemen kondisional dari bans hanya dapat menyatukan konstanta. Hal ini berarti bahwa bans khusus hares dituliskan untuk setiap kemungkinan fakta. Misalnya, anggap seseorang ingin menyuarakan api alarm jika sensor menunjukkan asap. Jika ada sensor N, kita perlu bans untuk setiap sensor sebagai berikut :

IF sensor 1 indicates smoke THEN sound fire alarm 1IF sensor 2 indicates smoke THEN sound fire alarm 2

IF sensor N indicates smoke THEN sound fire alarm N

199

Namun demikian, dengan penyatuan, variabel dapat disebut ?N dapat digunakan untuk sensor identifier sehingga satu baris dapat dituliskan sebagai bereikut :

IF sensor ?N indicates smoke THEN sound fire alarm ?N

Jika dua complementary literal digabungkan, maka keduanya dapat dihilangkan dengan resolusi. Untuk dua klause sebelumnya, pengganti dari y oleh b akan memberikan :

--F(b) v H(a,b) F (b)

Predikat F sekarang telah digabungkan dan dapat di-resolusi ke dalam :

H(a,b)

Substitusi ditentukan sebagai pengganti simultan dari variabl-variabel dengaln bentuk yang berbeda dengan variabel. Bentuknya mungkin konstanta, varabel, atau fungsi. Substitusi dari bentuk untuk variabel ditunjukkan dengan set

{ tl/V1, t2/v2 tN/VN }

Jika 0 adalah set semacam itu dan A adalah argumen, maka AO ditentukan sebagai sunstitusi jarak A. Misalnya, jika

= { a/x, f(Y)/Y, x/z }

A = P(x) v Q(y) v R(z)

maka

A0 = P(a) v Q(f(y)) v R(x)

200

Perhatikan bahwa substitusi adalah simultan, sehingga kita mendapatkan R(x) dan bukan R(a).

Anggap ada dua klause CI dan C2 ditentukan sebagai

C1 = --P (x)

C2 = P(f (x) )

Satu kemungkinan penyatuan/penggabungan P adalah :

C '1 = C1 {f(x)/x } = -P(f'x))

Kemungkinan penggabungan P yang lain adalah dua substitusi denganmenggunakan konstanta a.

C1 = C1 { f (a)/x }/x } = --P(f(a))

C2' = C2 { a/x } = P(f(a))

Perhatikan bahwa P(f9x)) adalah lebih umum dibandingkan dengan P(f(a)) jika ada beberapa jarak yang tidak terbatas dari P(f(x)) yang dapat dibuat dengan mengganti konstanta untuk x. Klause seperti C1 disebut dengan "most general clause".

Pada umumnya, substitusi 0 disebut dengan "unifier" untuk set klause {A1,A2... . An} jika dan hanya jika A10 = A20 = ... An0. Set yang mempunyai unifier disebut dengan "unifiable" . "Most general unifier (mgu)" adalah "mgu" yang seluruh unifier lainnya adalah instance/jarak. Ini dapat diekspresikan lebih formal dengan menentukan bahwa 0 adalah unifier yang paling umum jika dan hanya jika untuk setiap unifier a, ada pengganti 0 seperti

a=0b

dimana 00 adalah substitusi gabungan yang dibuat dengan penerapan 0 pertama dan kemudian P. "Unification Algorithm" adalah metode penemuan unifier yang paling umum untuk set unifiable terbatas dari argumen (Chang 73, Nilson 80).

Contoh dalam klause (la) - (3b), hasil substitusi dan penggabungan ditunjukkan dalam resolusi refutasi pohon dari Gambar 3.20. Jika akarnya adalah nol, maka kesimpulan yang dirundingkan akan salah sehingga kesimpulan valid bahwa "No failure is a success".

201

Contoh yang digunakan sejauh ini adalah sangat sederhana dan resolusinya sangat maju (straighforward), meskipun membingungkan bagi manusia. Namun demikian, dalam beberapa situasi lain proses resolusi mungkin menyebabkan selesai sehingga backtracking perlu untuk mencoba secara alternatif klause untuk resolusi. Meskipun resolusi sangat handal dan merupakan basis dari PROLOG, tetapi mungkin tidak memadai untuk beberapa problem. Salah satu problem dalam resolusi adalah bahwa problem tersebut tidak akan mempunyai efisiensi pembuatan strategi penelitian sehingga programmer harus men-supply heuristik, seperti pemotongan PROLOG, untuk efisiensi penelitian.

Sejumlah versi resolusi yang telah dimodifikasi telah ditemukan, seperti "unit preference, input resolution, liniar resolution" dan set of support" (Amble 87). Keuntungan resolusi utama adalah bahwa ini merupakan teknik powerful tunggal yang sesuai untuk beberapa kasus. Hal ini akan membuat lebib mudah di dalam membuat system mekanik seperti PROLOG dibandingkan dengan system yang mencoba untuk mengimplementasikan beberapa bans inference yang berbeda. Keuntungan resolusi yang lain adalah bahwa jika berhasil, resolusi secara otomatis akan menyediakan pembuktian dengan menunjukkan rangkaian langkah ke nol

-F(y) v H(a,y) F(b) P(a) -P(x) v -S(y) v -H(X,Y)

nil

Gambar 3-20 Pohon pembantahan Resolusi untuk membuktikan tidak adanya kesalahan

adalah suatu keberhasilan

202

3.14. RANGX41AN FORWARD DAN BACKWARD.

Sekelomppk multiple inference yang menghubungkan problem dengan solusinya disebut dengan "chain". Chain yang diteliti atau di Iintangkan/disilangkan dari problem ke solusinya disebut dengan rangkaian chain. Cara lain dalam menjelaskan rangkaian forward adalah pemberian alasan dari fakta ke kesimpulan yang mengikuti dari fakta tersebut. Rangkaian yang disilangkan dari hipotesa kembali ke fakta yang mendukung hipotesa adalah rangkaian backward. Cara lain dalam menjelaskan rangkaian backward adalah dalam bentuk tujuan yang dapat disusun dengan pemenuhan sub tujuan. Seperti ditunjukkan, terminologi yang digunakan untuk menjelaskan rangkaian forward dan backward tergantung pada problem yang didiskusikan.

Rangkaian dapat dengan mudah diekspresikan dalam bentuk inference.

Misalnya, anggap kita mempunyai bans type "modus ponens"

p v q

P q

yang membentuk rangkaian inference, seperti berikut ini.

elephant (x) -* mammal(x) mamal(x) -4 animal (x)

Bans yang digunakan dalam rangkaian casual dari inference forward yang mengurangi Clyde adalah binatang yang diberikan bahwa Clyde adalah gajah. Rangkaian inference diilustrasikan dalam Gambar 3.21. Perhatikan bahwa diagram yang sama juga mengilustrasikan rangkaian backward.

gajah

I gajah -4 binatang menyusui

I binatang menyusui -+ binatang

binatang

Gambar 3-21 Rangkaian maju kasual

Dalam Gambar 3.21, rangkaian casual ditunjukkan dengan rangkaian bar, f, yang menghubungkan konsekuensi satu baris ke sesudah berikutnya. Bar juga menunjukkan penyatuan variabel ke fakta. Misalnya, variabel x dalam predikat gajah (x) peitama kali hares digabungkan dengan fakta gajah(Clyde) sebelum baris gajah dapat diterapkan. Rangkaian casual sebenarnya merupakan rangkaian implikasi dan penyatuan, seperti ditunjukkan dalam Gambar 3.22.

gajah

Unifikasi

Memplementasi

Unifikasi

Memplementasi

gajah -+ binatang menyusui

Ibinatang menyusui -+ binatang

Gambar 3-22Rangkaian Kasual yang jelas

Rangkaian backward adalah proses reverse (membalikkan). Yaitu, anggap kita ingin membuktikan hipotesa binatang (Clyde). Problem pusat dari rangkaian backward adalah menemukan rangkaian yang menyembunyikan bukti ke hipotesa. Fakta gajah(Clyde) disebut dengan "evidence" dalam rangkaian backward unttlk

204

menunjukkan bahwa itu digunakan untuk mendukung hipotesa, seperti cara bahwa bukti ada dalam pengadilan digunakan untuk membuktikan kesalahan pembela.

Sebagai contoh sederhana dari rangkaian forward dan backward, anggap kita sedang mengendarai mobil dan tiba-tiba melihat polisi dengann lampu flash dan sirine. Dengan rangkaian forward, kita dapat menyimpulkan bahwa polisi menginginkan kita atau orang lain untuk berhenti. Yaitu, fakta pokok yang mendukung dua kemungkinan kesimpulan. Jika polisi ada disebelah kanan kita atau polisi menyalip kita, kesimpulan lain adalah bahwa mereka menginginkan kita bukannya orang lain. Dengan mengambil hal ini sebagai kerja hipotesa, kita dapat menerapkan rangkaian backward untuk memberi alasan mengapa.

Beberapa kemungkinan hipotesa lanjutan adalah littering, percepatan, pembuatan peralatan dan menggunakan (stolen vehicle). Sekarang kita menguji bukti untuk mendukung hipotesa ini. Apakah botol bir yang kita buang ke jendela, melaju 100 dalam 30 mil per jam zone kecepatannya, sinar yang rusak atau ijin yang menunjukkan mobil curian yang kita pakai?. Dalam hal ini, setiap bukti mendukung hipotesa lanjutan sehingga semuanya benar. Beberapa atau semua hipotesa lanjutan ini adalah kemungkinan alasan untuk membuktikan kerja hipotesa dimana polisi menginginkan kita.

Ini sangat berguna untuk menvisualkan rangkaian forward dan backward dalaam bentuk path melalui spasi problem dimana kelanjutannya menunjukkan hubungan ke hipotesa lanjutan di bawah rangkaian backward atau kesimpulan lanjutan di bawah rangkaian forward. Tabel 3.14 memberikan ringkasan beberapa karakteristik umum dari rangkaian forward dan backword. Perhatikan bahwa karakteristik dalam tabel ini berarti hanya sebagai penuntun. Sangat mungkin mengerjakan diagnosa dalam system rangkaian forward dan perencanaan di dalam rangkaian backward. Khususnya, keterangan diberi fasiltas dalam rangkaian backward karena system dapat dengan mudah menjelaskan tujuan yang dicoba untuk dipenuhi. Dalam rangkaian forward, keterangan tidak mudah diberi fasilitas karena sub tujuan tidak diketahui secara eksplisit hingga dapat ditemukan.

205

Rangkaian kedepan Rangkaian kebelakang

Perencanaan Pemantauan, kontrol saat sekarang keDiagnosismasa depan.

Antisident terhadap akibat

Data yang digerakkan, Penalaran atas dasar

Kerja maju untuk menemukanPemecahan yang mengikuti fakta

Pencarian melebar pertama yang di permudah

Aritisident menentukan pencarian

Penjelasan yang tak dipermudah.

Sekarang ke masa lalu

Akibat terhadap antisidentTujuan yang digerakkan, Penal= atas bawab

Kerja mundur untuk menemukan fakta yang mendukung hipotesa

Pencarian mendalam yang dipermudah

Akibat menentukan pencarian

Penjelasan yang dipermudah

Tabel 3-14

Ciambar 3-23 menjelaskan konsep dasar aturan diambil dari fakta-fakta yang memenuhi anticident

mereka atau sisi tangan kiri

Gambar 3.23 mengilustrasikan konsep pokok dari rangkaian forward dal,*n system yang berdasarkan pada bans. Bans di-(triggered) oleh fakta yang mementhi kejadian sebelumnya atau sisi sebelah kiri (LHS). Misalnya, bans RI, hatlus dipenuhi oleh fakta B dan C untuk diaktifkan. Namun demikian, hanya fakta! C ditunjukkan sehingga Rt tidak diaktifkan. Bans R2 diaktifkan oleh fakta C djin D yang ditunjukkan sehingga R2 akan membuat fakta H lanjutan. Baris yang dipenuhi lainnya adalah R3, R6, R7, R8, dan R9. Pembuatan baris R8 dna R9 akan menghasilkan kesimpulan proses rangkaian forward. Kesimpulan ini mungkin berupa fakta lain, output dan sebagainya.

206

CON CLUSIONS

INFERRED FACTS

FACTS

Gambar 3-23 Rangkaian kedepan/maju

Rangkaian forward disebut dengan "bottom-up reasoning" karena memberi alasan dari bukti level rendah, fakta, ke kesimpulan level tinggi yang berdasarkan pada fakta. Pemberian alasan bottom-up dalam expert system adalah analogous ke pemrograman konvensional bottom-up yang didiskusikan dalam Bab-01. Fakta merupakan unit dasar dari paradigma yang berdasarkan pengetahuan jika tidak dapat diuraikan ke dalam unit yang lebih kecil yang mempunyai arti. Misalnya, fakta "duck" mempunyai arti terbatas sebagai kata benda dan sebagai kata kerja. Namun demikian, jika diuraikan lebih lanjut, hasilnya adalah huruf d, u, c, dan k yang tidak mempunyai arti khusus. Dalam program konvensional, unit pokok dan arti adalah data.

Biasanya, konstruksi dengan level lebih tinggi yang menyusun dari konstruksi level rendah diletakkan di bagian atas. Sehingga pemberian alasan dari konstruksi level lebih tinggi seperti hipotesa akan turun ke fakta level rendah yang mungkin mendukung hipotesa disebut dengan "top-down reasoning", atau rangkaian backward. Gambar 3.24 mengilustrasikan konsep rangkaian backward. Untuk membuktikan atau tidak membuktikan hipotesa H, minimal satu hipotesa lanjutan

207

H1, H2, atau H3, harus dibuktikan. Perhatikan bahwa diagram ini digambarkan sebagai pohon AND-OR untuk menunjukkan bahwa dalam beberapa kasus sepetlti H2, seluruh hipotesa level rendah hares ditunjukkan untuk mendukung H2. Dalatn kasus lain, seperti hipotesa level atas, H, hanya satu hipotesa level rendah yang diperlukan. Dalam rangkaian backward, system akan secara umum mengeluarkan bukti dari pemakai untuk menambahkan dalam persetujuan atau tidak persetujuan hipotesa. Hal ini kebalikan dengan system rangkaian forward dimana seluruh fakta relevan biasanya dikenal dalam lanjutan.

INEEIAL HYPOTHESIS (GOAL)

1 NTERMEDIATE

HYPOTHESES

(SUBGOALS)

0 - Elicited Evidence

I O (m ay sapper)

%> - Missing Evidence

True Hypothesis

_ False Hypothesis 0

Gambar 3-24 Rangkaian mundur/kebelakang

208

Jika kita melihat kembali pada Gambar 3.4 dalam bagian 3.2, kita akan melihat bahwa jaringan keputusan diorganisasikan sangat baik untuk rangkaian backward. Hipotesa dengan level atas merupakan type (raspberries) yang berbeda seperti "flowering raspberry, back raspberry, wineberry, dan red raspberry". Bukti untuk mendukung hipotesa ini, diturunkan. Baris untuk menunjukkan raspberry dapat dengan mudah dituliskan. Misalnya,

IF the leaves are simple THEN flowering raspberry

Salah satu aspek pengeluaran bukti yang penting adalah menanyakan pertanyaan yang benar. Pertanyaan yang benar adalah yang meningkatkan efisiensi dalam menentukan jawaban yang benar. Satu persyaratan yang mutlak untuk ini adalah bahwa expert system hanya harus menanyakan pertanyaan yang berhubungan dengan hipotesa yang mencoba untuk membuktikan. Sementara mungkin ada beratus-ratus atau beribu-ribu pertanyaan dimana system dapat menany.akannya, ada harga waktu dan uang untuk mendapatkan bukti untuk menjawab pertanyaan. Juga, akumulasi type bukti tertentu seperti hasil test kesehatan mungkin tidak sesuai dan mungkin berbahaya bagi pasien (kenyataannya, sukar memikirkan test kesehatan yang menyenangkan).

Secara ideal, expert system harus juga memungkinkan pemakai untuk secara suka rela mempercepat bukti proses rangkaian backward dan membuat system lebih sesuai bagi pemakai. Bukti yang disukarelakan mungkin memungkinkan system melompat beberapa link dalam rangkaian casual atau mengejar pendekatan bare yang lengkap. Keuntungannya adalah bahwa pemrograman yang lebih komplek dari expert system dimasukkan jika system tidak mengikuti rangkaian link per link.

Aplikasi yang baik untuk rangkaian forward dan backward ditunjukkan dalam Gambar 3.25. Untuk sederhananya, diagram tersebut digambarkan sebagai pohon/ tree sebagai pengganti jaringan umum. Aplikasi yang baik untuk rangkaian forward terjadi jika pohon/tree lebar/luas dan tidak dalam. Hal ini karena arangkaian forward memberikan fasilitas penelitian "nafas pertama". Yaitu, rangkaian forward akan baik jika penelitian untuk kesimpulan mendahului level pere level. Sebaliknya, rangkaian backward memberikan fasilitas penelitian (depth-first). Pohon yang baik untuk penelitian depth-first adalah sempit dan dalam. Perhatikan bahwa struktur bans menentukan penelitian untuk solusi. Yiatu, aktivasi bans berdasarkan pola dimana baris di-design untuk bergabung. Pola pada LHS akan menentukan apakah bans dapat diaktifkan oleh fakta. Aksi pada RHS akan menentukan fakta yang disisipkan dan dihilangkan sehingga memberi akibat

209

pada bans lain. Situasi yang analogous terjadi untuk rangkaian backward kecuali. bahwa hipotesa digunakan sebagai pengganti bans. Tentu saja, hipotesa lanjutah mungkin berupa bans sederhana yang digabungkan pada konsekuensi/rangkaian sebagai pengganti yang sebelumnya.

Contoh yang sangat sederehana, perhatikan type baris IF THEN berikut ini

IF A THEN B

IF B THEN C

IF C THEN D

Kenyataan, A diberikan dan inference engine di-design untuk menggabungkan fakta terhadap yang sebelumnya, ' kemudian fakta berikutnya B dan C akin disisipkan dan kesimpulan D. Proses ini berhubungan dengan rangkaian forward.

Sebaliknya, jika fakta (sebenarnya hipotesa) D disisipkan dan inference engine menggabungkan fakta terhadap konsekuen, hasilnya berhubungan dengan rangkaian backward. Dalam system yang di-design untuk rangkaian backward, seperti PROLOG, mekanisme rangkaian backward berisi angka feature seperti backtracking otomatis untuk memberi fasilitas rangkaian backward.

(a) Aplikasi yang baik dari rangkaian kebelakang

210

(a) Good Application of Backward Chaining

(b) Aplikasi yang balk tentang rangkaian kedepan

Gambar 3-25 Rangkaian kedepan dan kebelakang

Rangkaian backward dapat diselesaikan dalam system rangkaian forward dan seebaliknya dengan men-design kembali bans. Misalnya, bans sebelumnya untuk rangkaian forward dapat dituliskan sebagai berikut :

IF D THEN C

IF C THEN B

IF B THEN A

Sekarang C dan B dipertimbangkan sebagai sub tujuan atau hipotesa lanjutan yang harus dipenuhi untuk memenuhi hipotesa D. Bukti A adalah fakta yang menunjukkan akhir dari pembuatan sub tujuan. Jika ada fakta A, maka D didukungkan dan dipertimbangkan benar di bawah rangkaian inference backward ini. Jika tidak ada A, maka hipotesa D tidak didukungkan dan dipertimbangkan salah.

Salah satu kesulitan dengan pendekatan ini adalah efisiensi. System rangkaian backward memberikan fasilitas penelitian depth-first, sementara system rangkaian

211

forward memberikan fasilitas penelitian breadth-first. Meskipun kita dapat menuliskan aplikasi rangkaian backward dalam system rangkaian forward daft sebaliknya, system tidak ada se-efisien dalam penelitiannya untuk solusi. Kesulitaln kedua adalah konseptual. Pengetahuan yang dikeluarkan dari expert hares dialternatif untuk menjumpai permintaan inference engine. Misalnya, inference engine rangkaian forward menggabungkan kejadian sebelumnya dari baris,

sementara rangkaan backward menggabungkan konsekeuensi. Yaitu, jika pengetahuan expert system secara natural rangkaian backward, maka hares secara total distruktur kembalii untuk rnembalutnya dalam mode rangkaian forward dan sebaliknya.

3.15. METODE LAIN DARI INFERENCEIKESIMPULAN.

Sejumlah type inference lain kadang-kadang digunakan dengan expetet system. Sementara metode ini tidak se-tujuan umum dengan deduksi, type terseout sangat berguna.

Analogi.

Dismping deduksi dan induksi, metode inference lain yang handal adalah "analogy". Ide pokok dari pemberian alasan dengan analogi adalah mencoba dan menhubungkan situasi lama sebagi penuntun ke situasi yang barn. Seluruh pembiiat sangat baik pada penerapan pemberian alasan analogikal dalam hidupnya, yang pada pokoknya karena sejumlah situasi bare yang sangat hebat yang dijumpai dalam dunia nyata, Bukannya memperlakukan setiap situasi barn sebagai yang unik, ini sering membantu untuk mencoba dan melihat persamaan dari sittlasi bare dan situasi lama yang kita ketahui bagaimana menghubungkannya. Pemberjan alasan analogis berhubungan dengan induksi. Sementara induksi membu iat

inference dari khusus ke yang umum dari situasi yang sama, analogi berusahal mencoba untuk membuat inference dari situasi yang tidak sama. Analogi tidals dapat membuat pembuktian formula seperti deduksi. Sebagai pengganti, analogi merupakan pemberian alasan peralatan heuristik yang mungkin kadang-kadng bekerja.

Contob pemberian alasan dengan analogi adalah diagnosa kesehatan. Jik, kita menjumpai dokter karena problem kesehatan, dokter akan mengeluarcar informasi dari kita dan mencatat gejala problem. Jika gejala kita sama atai

212

sangat sama dengan orang lain dengan problem X, maka dokter mungkin menyimpulkan dengan analogi dimana kita mempunyai problem X. Tentu saja, rangkaian backward mungkin juga digunakan.

Perhatikan bahwa diagnosis ini tidak/bukan merupakan deduksi, karena kita mungkin unik. Hanya karena orang lain dengan problem gejala tertentu tidak berarti bahwa kita akan menunjukkan gejala yang sama. Sebagai pengganti, dokter menganggap bahwa gejala kita membuat kita analogous bagi seseorang dengan gejala yang sama dan problem diketahui. Diagnosa awal adalah hipotesa bahwa test kesehatan mungkin benar atau salah. Ini penting untuk mempunyai kerja hipotesa awal karena menyempitkan beribu=ribu problem potensial. Ini sungguh mahal dan mengkonsumsi waktu hanya untuk memulai memberikan setiap test kemungkinan tanpa hipotesa awal.

Seperti contoh peralatan pemberian alasan dengan analogi, anggap dua orang bermain game yang disebut 15 game (Fischler 87). Mereka bergantian dalam mengambil angka dari 1 hingga 9 dengan konstraint bahwa angka yang sama tidak dapat digunakan dua kali. Orang pertama yang angkanya ditambahkan hingga 15 akan menang. Meskipun pertama kali kelihatannya seperti permainan/ game aneh yang memerlukan beberapa pemikiran, analogi dapat membuatnya sangat mudah untuk dimainkan.

Perhatikan papan tic-tac-toe berikut ini dengan angka yang disusun pada masing-masing cell seperti ditunjukkan,

6 7

2

Ini merupakan "magic square" karena jumlah angka dalam bans, kolom, dan diagonal adalah konstant/sama. Board tic-tac-toe dengan angka square magic dapat dipertimbangkan sebagai analogi pada Game 15. Permainan Game 15 sekarang sangat mudah jika kita memikirkan dalam bentuk tic-tac-toe kemudian menterjemahkan strategi kemenangan pada Gambe 15.

Magic square tertentu ini disebut dengan "standard square of order 3". Bentuk order mengacu pada angka bans atau kolom square. Hanya ada satu square unik dari order 3. Magic square yanglain dapat dibuta dengan membuat rotasi atau refleksi standard square. Cara lain untuk membuat magic square adalah dengan menambahkan konstanta yang sama pada setiap cell. Dengan mengetahui informasi

213

ini memungkinkan kita untuk mengurangi strategi kemenangan untuk Game 24 dimana angka harus dipilih dari set :

{2, 3, 4, 5, 6, 7, 8, 9, 10)

atau Game 33 dengan menggunakan set :

{3, 4, 5, 6, 7, 8, 9, 10, 11}

Sekarang kita menggunakan induksi untuk menyimpulkan strategi kemenangan untuk Game 15 + 9N, dimana N adalah angka natural 1, 2, 3, ... dengan memikirkan game sebagai analogoues pada board tic-tac-toe yang analogous terhadap angka square

{1+N, 2+N, 3+N, 4+N, 5+N, 6+N, 7+N, 8+N, 9+N)

Dengan menggunakan analogi order 3 square untuk game dari tiga

perpindahan, dengan induksi kita dapat menyimpulkan bahwa magic square dari order yang lebih tinggi dapat digunakanuntuk gam dengan mmasukkan lebih dari tiga perpindahan. Misalnya, magic square dari 4 order

16 3 2 13

5 10 11 8

9 6 7 12

4 15 14 1

memungkinkan kita untuk memainkan strategi kemenangan dari empat perpindahan - 34 Game dengan memikirkan dalam bentuk tic-tac-toe. Sebaliknya pada satu standare order 3 square, ada 880 standar square dari 4 order, yang memungkinkan pertimbangan game yang lebih (Smith 84).

Pembrian alasan dengan analogi adalah merupakan bagian yang penting dari pemberian alasan commonsense, yang sukar bagi komputer (dan anak-anak). Aplikasi lain dari analogi telah dipelajari (Carbonell 82).

214

Pembuatan dan Test.

Metode inference yang lain adalah strategi Al klasik dari "generate-and-test",

kadang-kadang disebut dengan pembuatan dan test, yang mencakup pembuatan

seperti solusi kemudian penge-test-an untuk melihat jika solusi yang diajukan

menjumpai seluruh persyaratan. Jika solusi memenuhi, maka akan berhenti, yang lain membuat solusi yang baru, test lagi, dan seterusnya. Metode ini digunakan dalam expert system pertama kali, DENDRAL, disusun pada tahun 1965, untuk menambahkan dalam penentu struktur molekul organik (Buchanan 78). Data dari

contoh yang tidak dikenal diterapkan dengan spektometer masa dan input ke DENDRAL yang membuat seluruh struktur molekul potensial yang dapat membuat spektogram yang tidak diketahui. DENDRAL kemudian menge-test seperti molekul calon dengan simulasi spektogram masanya dan membandingkannya dengan yang tidak diketahui aslinya. Program lain yang menggunakan pembuatan-dan-test adalah program AM (Artificial Mathematician) untuk menyimpulkan konsep matematika yang Baru (Lenat 82).

Untuk mengurangi jumlah yang besar dari solusi yang potensial, pembuatan-dan-test secara normal digunakan dengan program perencanaan untuk membatasi solusi potensial untuk pembuatan. Variasi ini disebut dengan

"plan-generate-test" dan digunakan untuk efisiensi dalam beberapa system. Misalnya, diagnosa matematika dari expert system MYCIN juga mempunyai kemampuan perencanaan perawatan obat/drug terapi setelah penyakit pasien telah di-diagnosa (Chancey 85). "Plan" pada pokoknya menemukan rangkaian bans atau inference yang menghubungkan problem dengan solusi, atau tujuan, dengan bukti untuk mendukungnya. Perencanaan merupakan yang paling efisien dilakukan dengan penelitian forward secara simultan dari fakta dan kembali dari tujuan.

Perencana MYCIN pertama kali membuat daftar prioritas dari obat terapi untuk pasien yang sensitif. Untuk mengurangi interaksi obat yang tidak diinginkn, lebih baik membatasi angka obat dimana pasien menerima, bahkan jika pasien dianggap menderita atas beberapa infeksi yang berbeda. Pembuat/generator akan mengambil daftar prioritas dari perencana dan membuat sub daftar dari satu atau dua obatjika mungkin. Sub daftar ini kemudian di-test untuk kemanjuran terhadap infeksi, alergi pasien, dan pertimbangan lain sebelum keputusan dibuat untuk pengurusannya ke pasien.

Pembuatan-dan-test juga dapat dipertimbangkan paradigma inference basic dari ban's. Jika elemen kondisional dari baris dipenuhi, maka akan membuat aksi yang lama seperti fakta baru. Inference engine ini akan menge-test fakta terhadap elemen kondisional dari baris dalam basis pengetahuan. Baris yang dipenuhi

215

tersebut diletakkan pada agenda dan diletakkan pada baris prioritas atas yang membuat aksinya, yang kemudian di-test dan seterusnya. Dengan demikian, pembuatan dan test akan membuat rangkaian inference yang menuntun ke solusi yang benar.

Abduksi/pengambilan.

Inference dengan "abduction" adalah metode lain yang pada umumnya digunakan dalam diagnosa pemecahan masalah. Skema abduksi sama dengan "modus ponens", tetapi sebenarnya sangat berbeda seperti yang ditunjukkan dalam Tabel 3.15.

Abduction Modus ponens

p -> q p e - q

q p

p q

Abduksi merupakan nama lain untuk argumen yang keliru yang didiskusikan dalam bagian 3.6 seperti Fallacy dari Converse. Meskipun abduksi bukah merupakan argumen deduksi yang valid, tetapi merupakan metode yang sangat berguna dari inference dan telah digunakan dalam expert system. Seperti halnya analogi, yang juga bukan merupakan argumen deduksi yang valid, abduksi mungkin berguna sebagai baris heuristik inference. Yaitu, jika kita tidak mempunyai metode deduktif dari inference, abduksi mungkin berguna tetapi tidak dijamin kerjanya. Analogi, pembuatan-dan-test, dan abduksi seluruhnya adalah metode yang bukan deduktif dan tidak dijamin bekerja full time. Dai i premises yang benar, metode ini tidak dapat membuktikan kesimpulan yapg benar. Namun demikian, teknik ini sangat berguna dalam pengurangan spasi

penelitian dengan pembuatan hipotesa yang dapat diberi alasan yang kemudian

dapat digunakan dengan deduksi.

Abduksi kadang-kadang disebut sebagai pemberian alasan dari fakta yang di-observasi ke keterangan yang paling balk (Reggia 85). Seperti contoh abduksi, perhatikan berikut ini,

IF x is an elephant THEN x is an animal

IF x is an animal THEN x is a mammal

216

jika kita tahu bahwa Clyde adalah mamalia, dapatkah kita menyimpulkan bahwa Clyde adalah gajah ?.

Jawabannya atas pertanyaan ini tergantung pada apakah kita membicarakan tentang dunia nyata atau expert system. Dalam dunia nyata, kita tidak dapat membuat kesimpulan ini dengan tingkat tertentu. Clyde dapat berupa anjing, kucing, sapi, atau macam binatang lainnya yang berupa mamalia tetapi bukan gajah. Kenyataannya, perhatikan berupa banyak jenis binatang yang ada, kemungkinan Clyde adalah gajah yang agak pendek tanpa mengetahui informasi lainnya tentang Clyde.

Namun demikian, dalam expert system dengan hanya baris awal, kita dapat mengatakan dengan abduksi dengan 100 % tentu bahwa jika Clyde adalah mamalia, kemudian Clyde adalah berupa gajah. Inference ini mengikuti dari "closed world assuption" dimana kita menganggap bahwa tidak ada yang lainnya yang muncul di luar dunia nyata dari expert system yang terdiri hanya atas dua baris dan hanya gajah yang berupa binatang mamalia, kemudian jika Clyde adalah mamalia, maka dia adalah gajah.

Anggap kita menambahkan baris ketiga, seperti berikut ini

IF x is a dog THEN X is an animal

Kita tetap dapat mengoperasikan expert systm di bawah asumsi dunia tertutup. Namun demikian, sekarang kita tidak dapat menyimpulkan dengan 100 % benar bahwa Clyde adalah gajah. Kita semua dapat yakin bahwa Clyde adalah gajah atau anjing.

Untuk memutuskan diantara dua, informasi yang lebih, diperlukan. Misalnya, ada bans lain :

IF x is a dog THEN x barks

dan bukti bahwa Clyde menggonggong, baris ini dapat direvisi sebagai berikut:

(1) IF x is an animal THEN x is a mammal(2) IF x barks THEN x is an animal

(3) IF x is a dog THEN x barks(4) IF x is an elephant THEN x is an animal

217

Sekarang rangkaian backward dari inference abduksi menggunakan baris

(1), (2), dan (3) dapat dibuat untuk menunjukkan bahwa Clyde adalah anjing.

Rangkaian backward dari abduksi tidaklah sama dengan arti umum/yang biasanya dari rangkaian backward. Bentuk "backward chaining" berarti bahwa kita mencoba untuk membuktikan hipotesa dengan mencari bukti untuk mendukungnya. Rangkaian backward akan digunakan dalam percobaan untuk membuktikan bahwa Clyde adalah binatang mamalia. Tentu raja, dalam system kecil kita, tidak ada kemungkinan lain. Namun demikian, klasifikasi kita dapat ditambahkan untuk reptil, burung, dan sebagainya.

Jika diketahui bahwa Clyde adalah mamalia, abduksi dapat digunakan untuk menentukan jika Clyde adalah binatang atau anjing. Rangkaian forward dapat digunakan jika diketahui bahwa pilihan metode inference tergantung pada apa yang hares dipertimbangkan. Jika rangkian forward adalah deduktif, hanya kseimpulannya selalu dijamin valid. Tabel 3.16 memberikan ringkasan tujuan setiap tiga teknik inference.

Inferensi Start

Rangkaian kedepan Fakta

Rangkaian kebelakangKesimpulan tak pasti

Abduksi Kesimpulan benar

Tabel 3-16

Tujuan

Kesimpulan yang harus mengikuti

Fakta pendukung kesimpulan Fakta

yang dapat mengikuti

Ringkasan dari tujuan Rangkaian ke depan Rangkaian ke belakang dan abduksi

Jumlah Al dan expert systm telah digunakan abduksi yang berdasarkan frame untuk diagnosa pemecahan masalah (Basili 85) (Miller 82) (Pople 82) (Reggia 83). Dalarn system ini, basis pengetahuan berisi "casual associations" antara kekacauan dan gejala. Inference dibuat dengan inenggunakan pembuatan-dari-test dari hipotesa untuk kekacauan.

218

Pemberian alasan Non monotonik.

Secara normal, tambahan aksiorna yang barn pada system logika berarti bahwa banyak teori yang dapat dibuktikan jika ada banyak aksioma dari teori yang didapatkan. Properti peningkatan teori ini dengan peningkatan aksioma dikenal dengan "monotonicity" dan system seperti logika deduktif disebut dengan "monotonic system".

Namun demikian, problem dapat terjadi jika aksioma yang diperkenalkan secara bagian atau seluruhnya berkontradiksi dengan aksioma sebelumnya. Dalam hal ini, teori yang telah dibuktikan tidak akan lama valid. Dengan demikian, dalam system monitinik, teori tidak perlu meningkat sebagai angka peningkatan aksioma.

Konsep non-monotinicity mempunyai aplikasi yang penting dalam expert system. Karena fakta yang barn dibuat, yang analogous pada teori yang dibuktikan, monotonik expert system akan tetap membuat fakta. Problem utama dapat terjadi jika satu atau lebih fakta menjadi salah karena system monotonik tidak dapat

berhubungan dengan perubahan di dalam kebenaran aksioma dan teori. Seperti contoh yang sangat sederhana, anggap ada fakta yang meenyisipkan waktu. Segera setelah waktu berubah dalam detik, fakta yang lama tidak akan lama valid. System monotonik tidak akan dapat berhubungan dengan situasi semacam ini. Seperti contoh lain, anggap fakta disisipkan dengan system identifikasi pesawat udara yang targetnya bertentangan. Kemudian, bukti barn yang membuktikan target sangat "friendly". Dalam system monotonik, identifikasi asli dari pertentangan ini tidak dapat diubah. System non monotonik memungkinkan adanya pembatasan fakta.

Seperti aplikasi lain, anggap kita ingin menuliskan fasilitas penjelasan untuk expert system yang akan memungkinkan pemakai untuk kembali pada inferenc sebelumnya dan menjelajahi path inference alternatif dari type pertanyaan `What

if'. Seluruh inference dibuat setelah yang sebelumnya didapatkan harus ditarik kembali dari system. Disamping fakta, bans juga dikeluarkan dari system sehingga hares diletakkan kembali dalam basis pengetahuan untuk non monotonik. Komplikasi lain muncul dalam system sernacam OPS5 dimana bans dapat dibuat secara otomatis pada sisi sebelah kanan baris selama dalam pembuatan. Untuk non monotonik, bans yang di-infer dibuat setelah inferencesebelumnya diperoleh hares dikeluarkan dari system. Dengan memelihara track dan seluruh inference yang dibuat dapat mengkonsumsi banyak memory dan slow down system secara significant.

Untuk menyediakan bagi non monotonik, perlu mendekati kebenaran atau

219

ketergantungan pada setiap fakta dan baris yang menjelaskan alasan untuk mempercayainya. Jika keputusan non monotonik dibuat, maka inference engine dapat menguji kebenaran dari setiap fakta dan bans untuk dilihat jika tetap dipercaya, dan juga untuk memungkinkan penyimpanan kembali baris yang dikeluarkan dan fakta yang dibatasi yang dipercayai lagi.

Problem kebenaran data pertama kali diambil dalam "frame problem" yang

tidak sama konsep seperti frame yang didiskusikan dalam Bab-02 (McCarthy 69). Frame problem merupakan bentuk deskriptif yang diberi nama setelati prob. lem dari identifikasi apa yang seharusnya dan tidak seharusnya diubah dalarn frame movie. Gambar gerakan di-photograp sebagai suksesi gambar yang disebut dengan frame. Jika dimainkan kembali pada 24 frame per detik atau lebih cepat, mata manusia tidak akan dapat melihat perbedaan frame individual sehingga ilusi gerakan akan dihasilkan. Frame problem Al adalah menentukan untuk merubah dalam lingkungan waktu. Seperti dalam contoh, perhatikan Problem Monkey dan Bananas yang didiskusikan dalam Bab-02. Anggap kera harus berjalan pada kotak merah untuk mendapatkan pisang sehingga aksinya adalah "push red box under bananas". Sekarang problem frame adalah - Bagaimana kita mengetahui kotak masih tetap merah setelah aksi tersebut ?. Dengan menekan kotak, jangan mengubah lingkungan. Dalam beberapa peralatan expert system, lingkungan disebut dengan "world"/dunia dan berisi serangkaian hipotesa pemberian alasan secara simultan. Problem perawatan kebenaran atau kebenaran system disebut dengan "truth maintenance" (Doyle 79). Perawatan kebenaran atau variasi disebut dengan "assumption-bases truth maintenance" yang pada pokoknya untuk menjaga setiap dunia asli dengan membatasi fakta yang tidak benar (de Kleer 860.

Seperti contoh sederhana dari pemberian alasan non monotonik, maxi perhatikan contoh klasik dari Twenty burung. Dalam kekurangan beberap4 informasi, kita menganggap bahwa jika Twenty adalah burung, maka Twenty dapat terbang. Ini merupakan contoh dari "default reasoning". sangat mirip dengan default yang digunakan dalam frame lots. Pemberian alasan default dapat dipertimbangkan sebagai baris yang membuat inference tentang baris, "metarule" yang menunjukkan :

IF X is not known for certain, and there is no evidence contradicting x

THEN tentatively conclude Y

Metarules didiskusikan lebih ekstensif dalam bagian yang akan datang.

220

Dalam kasus kita metarul mempunyai bentuk yang iebih spesifik

X is the rule "All birds can fly," and

fact "Tweety is a bird" Y is the inference "Tweety can fly"

dalam bentuk bans produksi, ini dapat diekspresikan sebagai bans dalam basis pengetahuan yang mengatakan :

IF X is a bird THEN x can fly

dan fakta yang muncul dalam memory yang bekerja.

Tweety is a bird

Dengan menggabungkan fakta dengan yang sebelumnya dari bans-bans akan memberikan inference dimana Twenty dapat terbang.

Sekarang kita masuk ke problem. Anggap fakta tambahan ditambahkan untuk memory yang bekerja yang mengatakan bahwa Twenty adalah penguin. Kita tahu bahwa penguin tidak dapat terbang dan sehingga inference dimana Twenty dapat terbang akan salah. Tentu saja, harus ada bans dalam system yang juga menyatakan pengetahuan ini atau fakta lain akan diabaikan.

Untuk menjaga kebenaran system kita, inference yang tidak benar harus dipindah. Namun demikian, ini tidak akan mencukupi jika inference lain didasarkan pada inference yang tdak benar. Yaitu, bans lain yang mungkin telah digunakan inference yang tidak benar sebagai bukti untuk menggambarkan in-ference tambahan dan seterusnya. Ini merupakan problem kebenaran perawatan. Inference dimana Twenty dapat terbang adalah "plausible inference" yang didasarkan pada pemberian alasan. Bentuk "plausible" berarti tidak tidak mungkin, dan akan didiskusikan lebih lanjut dalam Bab-04

Satu cara untuk memungkinkan inferencee non monotonik adalah dengan menentukan operator M per kalimat, yang secara ina• f=:.J dapat diitentukan sebagai "konsisten" (McDermott 82). Misalnya,

(" x) [Bird(x) " M(Can fly(x)) -4 Can fly(x)]

yang dapat ditentukan sebagai "Untuk setiap x, jika x adalah burung dankonsisten bahwa burung dapat terbang, maka x dapat terbang". Cara yang lebih informal

221

dalam menentukan ini adalah "Hampir semua burung dapat trebang". Bentuk "konsisten" berarti bahwa tidak ada kontradiksi dengan pengetahuan lain. Namun demikian, intepretasi ini telah dikritik sebagai pernyataan rid dimana hanya burung yang tidak dapat terbang adalah yang di-infer (disimpulkan) tidak dapat terbang (Moore 85). Ini merupakan contoh dari "autoepistemic reasoning", yang secara literal berarti pemberian alasan tentang pengetahuan kita sendiri. Default dart pemberian alasan autoepistemic digunakan di dalam "commonsense reasoning", dimana manusia pada umumnya melakukan dengan baik tetapi sangat sulit bagi komputer.

Pemberian alasan autoepistemik adalah pemberian alasan tentang pengetahuan kita sendiri sebagai pembeda dari pengetahuan pada umumnya. Pada umumnya, kita dapat melakukan hal ini dengan sangat baik karena kita mengetahui batasan pengetahuan kita. Misalnya, anggap total asing datang dan menyatakan pada kita yang bukan (spouse)-nya. Kita segera akan mengetahui (kecuali jika kits

mempunyai amnesia) bahwa kita bukan (spouse)-nya karena kita tidak mempunyai pengetahuan dari yang acing tersebut. Metarule umum dari pemberian alasan autoepistemik adalah

IF I have no knowledge of X

THEN X is false

Perhatikan bagaimana pemberian alasan autoepistemik terletak pada asumsi dunia tertutup. Fakta yang tidak diketahui dianggap salah. Dalam pemberiah alasan autopistemik, dunia tertutup adalah pengetahuan kita sendiri.

Autoepistemik dan pemberian alasan default, keduanya adalah non monotonik. Namun demikian, alasannya berbeda. Pemberian alasan default adalah non monotonik karena merupakan "defeasible". Bentuk defeasible berarti bahwa inference merupakan tentatif dan harus berupa wirtdrawn sebagai informasi baru yang ada. Namun demikian, pemberian alasan autoepistemik ash bukanlal`h defesiable karena asumsi dunia tertutup yang membuat seluruh pengetahuan kebenaran telah kita kenal. Misalnya, jika orang yang menikah mengetahui (spouse)-nya (kecuali jika mereka ingin melupakan), prang yang menikah tidak akan menerima bahwa total asing adalah (spouse)-nya jika mereka mengatakannya. Oleh karena hampir semua orang menentukan bahwa mereka mempunyai memory yang tidak sempurna, mereka tidak melekatkan pada pemberian alasan autoepistemik asli. Tentu raja, komputer tidak mempunyai problem ini.

Pemberian alasan autoepisternik adalah non monotonik karena arti pernyataan

autoepistemik adalah "context-sensitive". Bentuk "context-sensitive" berarti bahwa

222

arti berubah dengan di dalam koonteks. Seperti contoh sederhana dari konteks-sensitif, perhatikan bagaimana kata "read" / membaca diucapkan dalam dua kalimat :

I have read the book I will read the book

Ucapan "read" adalah "context-sensitive".

Sekarang perhatikan system yang berisi dua aksioma berikut ini

(V x) [Bird(x) A M(Can fly(x)) + - Can fly(x))Bird(Tweety)

Dalam system logika, Can_fly (Tweety) adalah teori yang diperoleh dengan penggabungkan Tweety dengan variabel x dan implikasi.

Sekarang ganggap aksioma baru ditambahkan yang menyatakan bahwa Tweety tidak dapat terbang dan berkontradiksi dengan teori yang didapatkan sebelumnya.

-Can_fly(Tweety)

Operator-M harus mengubah operasinya pada argumennyta karena M(Can_fly(Tweety)) tidak konsisten dengan aksioma baru. Dalam konteks baru dari tiga aksioma ini, operator M tidak akan memberikan hasil TRUE untuk Can-fly (Tweety) karena konflik dengan aksioma baru. Angka yang dikembalikan dengan operator M harus FALSE dalarn konteks yang baru ini, sehingga konjungsi adalah FALSE. Dengan demkian, tidak ada implikasi untuk membuat teori Can-fly (Tweety) dan tidak ada konflik.

Satu cara untuk mengimplementasikan ini adalah dengan bans sebagai berikut :

IF x is a bird AND x is typical

THEN x can fly

IF x is a bird AND x is nontypical

THEN x cannot fly

223

Perhatikan bahwa system ini tidak invalidasi kesimpulan Can-fly (Tweety), tetapi mencegah bans yang tidak benar dari (firing) sama sekali. Hal ini merupakap metode yang lebih efisien dari perawatan kebenaran dibandingkan jika kite mempunyai satu baris dan aksioma khusus -Can_fly(Tweety). Sekarang kita mempunyai system yang lebih umum yang dapat dengan mudah menangani burung yang tidak dapat terbang seperti (ostriches) tanpa kita harus secara kontinue menambahkan inference bare, yang harus dilakukan oleh system.

3.16. METAKNOWLEDGE.

Program Meta-DENDRAL menggunakan induksi untuk mneyimpulkan baris baru dari struktur kimia. Meta-DENDRAL merupakan suatu usaha untuk menanggulangi knowledge-bottleneck atas percobaan menyaring bans struktur molekul dari manusia ahli. Meta-DENDRAL telah berhasil, dengan menemukan kembali baris yang dikerahui dan penyimpulkan bans yang baru.

Seperti dalam contoh, metarule berikut ini diambil dari program tambahan/ penerimaan pengetahuan TEIRESIAS untuk MYCIN, expert system untuk mendiagnosa infeksi darah dan meningitis (Feigenbaum 79).

METARULE 2

IF

The patient is a compromised host, and There are rules which mention in their premise

pseudomonas, and There are rules which mention in their premise

klebsiellas THEN

There is suggestive evidence ( 4) that the former

should be done before the latter

Angka 4 dalam aski bans adalah tingkat tertentu dan akan didiskusikan dalarn bab selanjutnya nanti.

TEIRESIAS akan menambah pengetahuan secara interaktif dan expert. Jika diagnosa yang salah dibuat oleh MYCIN, maka TEIRESIAS akan membantu expert kembali melalui rangkaian pemberian alasan yang tidak benar hingga expert/ahhi

224

menyatakan dimana permulaan pemberian alasan yang tidak benar. Sementara dalam perjalanan kembali melalui rangkaian pemberian alasan, TEIRESIAS juga akan berakasi dengan expert untuk memodifikasi baris yang tidak benar atau menambah bans baru.

Pengetahuan tentang baris bare tidak diletakkan segera dalam MYCIN. Sebagai pengganti, TEIRESIAS akan menge-check untuk melihat apakah bans bare sesuai untuk bans yang sama. Misalnya, jika bans bare menjel4kan bagaimana infeksi masuk ke body dan baris lain yang diterima mempunyai elemen kondisional penentu portal dari entry/masukan ke body, maka bans yang bare juga demikian. Jika baris bare tidak menunjukkan portal entry, maka TEIRASIAS akan meminta pemakai tentang ketidak sesuaian ini. TEIRESIAS mempunyai pola "rule model" dan bans yang sama yang mengetahuinya, dan mencoba untuk menyesuaikan bans bare ke dalam model barisnya. Dengan kata lain, model bans merupakan pengetahuan dimana TEIRESAS mempunyai tentang pengetahuannya. Situasi analogous bagi manusia akan terjadi jika kita pergi ke dealer mobil untuk membeli mobil baru dan dealer mencoba untuk menjual mobilnya kepada kita dengan tiga roda.

Metaknowledge dari TEIRESIAS adalah dua type. METARULE-2 yang dijelaskan sebelumnya adalah strategi kontrol yang mengatakan kepada kita bagaimana suatu bans diterapkan. Sebaliknya, type model bans dari metaknowledge akan menentukan jika baris baru ada dalam bentuk yang semestinya untuk diamasukkan ke dalarn. basis pengetahuan. Dalam expert system yang berdasarkan baris akan menentukan jika bans bare ada dalam bentuk yang benar adalah "verification" dari suatu baris. Dengan menentukan bahwa rangkaian inference yang benar akan menyebabkan ke jawaban yang benar disebut dengan "validation". Validasi dan verifikasi adalah saling bergantung dimana akronim V & V pada umumnya digunakan untuk menyebut keduanya. Definisi yang lebih umum digunakan sehari-hari atas bentuk dari software engineering adalah (Boehm 84).

Verification: "Am I building the product right?"

Validation: "Am I building the right product?"

V & V akan didiskusikan lebih mendalam lagi dalam bab berikutnya nanti.

225

3.17. RINGKASAN.

Dalam bab ini, metode yang digunakan pada umumnya atas pembua* kesimpulan (infering) untuk expert system telah didiskusikan. Pembuatan kesimpu* sangatlah penting dalam expert system karena mecupakan teknik dimana expe�t system memecahkan problem. Aplikasi pohon/tree, graft, dan lattices pa4a representasi pengetahuan telah didiskusikan. Keuntungan struktur inference juga telah diilustrasikan.

Logika deduktif mencakup permulaan dengan logika syllogistik yang sederhana. Berikutnya, logika predikat yang proporsional dan logika predikat first-order telah didiskusikan. Tabel benar dan bans inference dijelaskan sebagai cara dala n pembuktian teori dan pernyataan. Karakteristik system logika seperti kelengkapa4, bunyian, dan decidability telah disebutkan.

Metode resolusi dalam pembuktian teori telah didiskusikan untuk logilka proporsional, dan logika predikat first-order. Sembilan langkah yang ada dalain peng-konversi-an formula yang dibentuk dengan baik pads bentuk klausa telah diilustrasikan dengan contoh. Skolemazation, bentuk prenex-normal, don penggabungan/penyatuan telah didiskusikan dalam konteks yang meng-konversikin wff ke bentuk klausa.

Metode lain yang handal dari inference, analogi, telah didiskusikan. Meskipun tidak secara luas digunakan dalam expert system karena kesulitan di dalain mengimplementasikannya, analogi sering digunakan oleh orang dan hares dipertimbangkan dalam design expert system. Pembuatan-dan-test juga telah didiskusikan dengan contoh penggunaannya di dalam MYCIN. Aplikasi metaknowledge dalam TEIRESAIS telah dijelaskan dan hubungannnya pada verifikasi dan validasi dari expert system.

226