Pertemuan 1 Minggu ke 5, Pengetahuan dan penalaran Logika Orde Pertama

1. Pengenalan logika orde pertama

First order logic adalah sebuah bahasa formal yang digunakan di ilmu matematika, philosophy, bahasa dan ilmu computer. Disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form). Kalkulus predikat bisa menganalisakan kalimat-kalimat ke dalam subjek dan argumen dalam berbagai cara yang berbeda-beda, yang pada akhirnya kalkulus predikat bisa digunakan untuk memecahkan problem of multiple generality (masalah dalam berbagai keadaan umum) yang telah membingungkan sebagian besar ahli-ahli logika abad pertengahan. Dengan menggunakan logika predikat ini, untuk pertama kalinya, para ahli-ahli logika bisa memberikan quantifier yang cukup umum untuk merepresentasikan semua argumen yang terdapat padanatural language.

2. Sintak dan semantik logika orde pertama

1. simbol dan interpretasi

Interpretasi atau penafsiran adalah proses komunikasi melalui lisan atau gerakan antara dua atau lebih pembicara yang tak dapat menggunakan simbol-simbol yang sama, baik secara simultan (dikenal sebagai interpretasi simultan) atau berurutan (dikenal sebagai interpretasi berurutan). Menurut definisi, interpretasi hanya digunakan sebagai suatu metode jika dibutuhkan. Jika suatu objek (karya seni, ujaran, dll) cukup jelas maknanya, objek tersebut tidak akan mengundang suatu interpretasi. Istilah interpretasi sendiri dapat merujuk pada proses penafsiran yang sedang berlangsung atau hasilnya. Suatu interpretasi dapat merupakan bagian dari suatu presentasi atau penggambaran informasi yang diubah untuk menyesuaikan dengan suatu kumpulan simbol spesifik. Informasi itu dapat berupa lisan, tulisan, gambar, matematika, atau berbagai bentuk bahasa lainnya. Makna yang kompleks dapat timbul sewaktu penafsir baik secara sadar ataupun tidak melakukan rujukan silang terhadap suatu objek dengan menempatkannya pada kerangka pengalaman dan pengetahuan yang lebih luas.

b. Tujuan dan Penjelasan Interpretasi

Tujuan interpretasi biasanya adalah untuk meningkatkan pengertian, tapi kadang, seperti pada propaganda atau cuci otak, tujuannya justru untuk mengacaukan pengertian dan membuat kebingungan.

2. Istilah, kalimat atomic

Proposisi atomik ~> proposisi yang hanya terdiri atas satu peryataan dan mengacu kepada nama diri atau juka menggunakan kata ganti, maka akan menggunakan penunjuk ini atau itu.

Contoh :

-       Agus Sudrajat adalah mahasiswa Fisip UNSIL.

-       Orang ini adalah pencopet

3. Kalimat kompleks

Kalimat kompleks adalah kalimat yang memiliki lebih dari satu struktur dan satu verba utama karena di dalam kalimat ini terkandung lebih dari satu aksi (Predikat), peristiwa, atau keadaan.

      Macam-macam kalimat kompleks:

     - Kalimat Komplek Paratatik

     - Kalimat Kompleks Hipotaktik

4. Quantifier

Quantifier adalah kata atau kelompok kata yang digunakan untuk menyatakan jumlah (how many atau how much).

Bentuk quantifier mungkin simple, hanya terdiri dari satu kata (contoh: few, little, many), atau complex, berupa frasa (contoh: a lot of, none of, a couple of).

Quantifier umumnya digunakan sebagai determiner yang berfungsi membatasi noun. Posisinya di depannoun membentuk noun phrase. Namun, quantifier dapat pula berdiri sendiri sebagai pronoun, tepatnya indefinite pronoun.

3. Penggunaan logika orde pertama

1.  assertion dan  query

Assertion adalah Domain constraint dan Referential integrity constraint. Assertion digunakan untuk mengekspresikan suatu kondisi basis data sesuai dengan yang kita inginkan. Seperti halnya prosedur, assertion diberikan nama tertentu sehingga bisa dibatalkan apabila ada kondisi tertentu yang menuntut perubahan struktur basis data. Pada beberapa basis data penggunaan kunci primer dan kunci tamu sudah cukup untuk menjaga integritas data. Tetapi pada beberapa kasus basis data diperlukan suatu constraint ataupun aturan yang lebih baik.  

Query adalah semacam kemampuan untuk menampilkan suatu data dari database dimana mengambil dari table-tabel yang ada di database, namun tabel tersebut tidak semua ditampilkan sesuai dengan yang kita inginkan. data apa yang ingin kita tampilkan, misal : data peminjam dengan buku yang dipinjam, maka nanti akan mengambil data dari table peminjam dan tabel buku.

4. Rekayasa pengetahuan pada logika orde pertama

Dalam akuisisi pengetahuan, perekayasa (engineer) bertindak sebagai jembatan antara pakar (expert) dengan basis pengetahuan. Perekayasa mendapatkan pengetahuan dari pakar, dan bersamanya menaruhnya pengetahuan tersebut dalam basis pengetahuan.

Ada beberapa cara untuk melakukan akuisisi pengetahuan. Yang pertama adalah dengan cara manual, di mana dalam cara ini perekayasa mendapatkan pengetahuan dari sumber, dan lalu mengkodekannya ke dalam basis pengetahuan. Cara ini merupakan cara yang mahal dan tidak efisien, serta juga kadangkala tidak akurat.

Cara yang kedua adalah cara semi-otomatik. Di sini terdapat peran komputer untuk mendukung pakar, di mana pakar diizinkan untuk membangun basis pengetahuan tanpa (atau dengan sedikit) bantuan dari perekayasa. Komputer di sini juga berperan untuk membantu perekayasa dalam kerjanya membangun basis pengetahuan.

Sementara yang ketiga adalah cara otomatik. Di sini peran pakar, perekayasa, maupun pembangun basis pengetahuan atau sistem (system builder) digabung. Contohnya adalah metode induksi.

Kesulitan dalam proses akuisisi pengetahuan adalah kesulitan pakar untuk mengkomunikasikan pengetahuan-pengetahuan dasarnya. Ini berkaitan dengan sifat pengetahuan itu sendiri (yang seperti telah dijelaskan di atas, adalah eksplisit sekaligus terbatinkan). Seperti yang dikatakan oleh Waterman (1981): “… suatu pengetahuan dasar diasumsikan dan dikombinasikan begitu cepatnya sehingga sulitlah baginya (pakar) untuk mengambarkan prosesnya”[6]. Beberapa teknik canggih telah dikembangkan untuk memfasilitasikan proses untuk mendapatkan dasar pengetahuan, seperti AQUINAS, Boose dan Bradsaw 1987; dan NEXTRA dari Neuron Data, Rappaport dan Gaines 1988.

5. Logika Proposisi vs Inferensi Logika Orde Pertama

Contoh Permasalahan

Pembuktian Logika Proposisi

Setiap hewan pasti mati. Karena Kucing adalah Hewan, maka dia pasti mati.

Secara intuisi kalimat tersebut bernilai Benar. Berdasarkan logika proposisi kalimat tersebut dapat

disimbolkan sebagai:

p : Setiap hewan pasti mati

q : Kucing adalah hewan

r : Kucing pasti mati

Berdasarkan kerangka berfikir Logika Proposisi bukanlah konsekuensi Logis dari pdan q. Pernyataan

‘Setiap hewan pasti mati’ mengandung pernyataan Himpunan, yaitu Himpunan ‘hewan’, dimana

individu yang merupakan bagian dari himpunan hewan jumlahnya tidak terhingga. Sedangkan

pernyataan ‘Kucing adalah hewan’ secara implisit menyatakan anggota dari himpunan ‘hewan’/

universal of discourse.

Struktur sepertidiatas tidak dikenali oleh Logika Proposisi, karena apabila ingin membuktikan

kebenaran dari pernyataan ‘Setiap hewan pasti masti’ maka harus dicari nilai kebenaran dari seluruh

elemen himpunan hewan yang jumlahnya tak terhingga. Ini tidak mungkin dilakukan.

Untuk mengatasi permasalahan diatas diperlukan kerangka berfikir lain selain Logika Proposisi yaitu

Logika First-Order (Kalkulus Predikat). Maka dapat didefinisikan bahwa Logika First-Order adalah

perluasan dari konsep Logika Proposisi untuk mengatasi permasalahan yang tidak dapat dipecahkan

melalui kerangka berfikir Logika Proposisi dengan penambahan 3 komponen logika yaitu: Term

(suku), Predicate dan Quantifier.

Pembuktian pada Logika First-Order

Pembuktian Logika First-Order hampir sama dengan pembuktian pada Logika Proposisi. Hanya saja

pada Logika First-Order pembuktian menggunakan Aturan Inferensi lebih mungkin untuk dilakukan.

Contoh:

Buktikan bahwa “Setiap hewan pasti mati. Kucing adalah hewan, Karenanya Kucing pasti mati.”

Jawab:

Misal dideklarasikan predikat berikut:

ANM(x)         adalah hewan

MORTAL(x)  pasti mati

Maka pernyataan pada soal menjadi:

P1                  :(x) (ANM(x) MORTAL(x))

P2                  :ANM(Kucing)

Untuk membuktikan bahwa kesimpulan “Kucing pasti mati”harus dibuktian bahwa MORTAL(Kucing)

adalah konsekuensi logis dari P1dan P2. Maka;

Dilakukan pembuktian langsung:

P1P2             : (x) (ANM(x) MORTAL(x)) ANM(Kucing)

Karena (ANM(x)  MORTAL(x)) bernilai Benar untuk semua x maka;

(ANM(Kucing)  MORTAL(Kucing)) juga Benar

(x) (ANM(x)MORTAL(x))

ANM(Kucing)

(ANM(Kucing)MORTAL(Kucing))

MORTAL(Kucing)

Premis P1

Premis P2

Langkah 1 dan 2

P1: x Kucing

6. Unifikasi dan Lifting

Unifikasi

Unifikasi adalah usaha untuk mencoba membuat dua ekspresi menjadi identik (mempersatukan keduanya) dengan mencari substitusi-substitusi tertentu untuk mengikuti peubah-peubah dalam ekspresi mereka tersebut. Unifikasi merupakan suatu prosedur sistematik untuk memperoleh peubah-peubah instan dalam wffs. Ketika nilai kebenaran predikat adalah sebuah fungsi dari nilai-nilai yang diasumsikan dengan argumen mereka, keinstanan terkontrol dari nilai-nilai selanjutnya yang menyediakan cara memvalidasi nilai-nilai kebenaran pernyataan yang berisi predikat. Unifikasi merupakan dasar atas kebanyakan strategi inferensi dalam Kecerdasan Buatan. Sedangkan dasar dari unifikasi adalah substitusi.

Suatu substitusi (substitution) adalah suatu himpunan penetapan istilah-istilah kepada peubah, tanpa ada peubah yang ditetapkan lebih dari satu istilah. Sebagai pengetahuan jantung dari eksekusi Prolog, adalah mekanisme unifikasi.

Aturan-aturan unifikasi :

1. Dua atom (konstanta atau peubah) adalah identik.

2. Dua daftar identik, atau ekspresi dikonversi ke dalam satu buah daftar.

3. Sebuah konstanta dan satu peubah terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.

4. Sebuah peubah tak terikat diperssatukan dengan sebuah peubah terikat.

5. Sebuah peubah terikat dipersatukan dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta tidak ada konflik.

6. Dua peubah tidak terikat disatukan. Jika peubah yang satu lainnya menjadi terikat dalam upa-urutan langkah unifikasi, yang lainnya juga menjadi terikat ke atom yang sama (peubah atau konstanta).

7. Dua peubah terikat disatukan jika keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah atau konstanta).

7. Forward dan Backward Chaining

Metode forward chaining dan backward chaining merupakan dua teknik penalaran yang biasa digunakan dalam sistem pakar. Metode backward chaining adalah pelacakan kebelakang yang memulai penalarannya dari kesimpulan (goal), dengan mencari sekumpulan hipotesa-hipotesa yang mendukung menuju fakta-fakta yang mendukung sekumpulan hipotesa-hipotesa tersebut. Sedangkan metode forward chaining adalah pelacakan ke depan yang memulai dari sekumpulan fakta-fakta dengan mencari kaidah yang cocok dengan dugaan/hipotesa yang ada menuju kesimpulan.

8. Resolusi

Pendekatan resolusi menghasilkan klausa-klausa baru dari sebuah himpunan inisial. Implementasi resolusi mempunyai tujuan untuk mengembangkan suatu prosedur sistematis pada sebuah basis data, dimana wffs-nya tidak memuaaskan, dengan kata lain tidak ada interpretasi wffyang masuk akal. Untuk itu, hal pertama yang perlu dilakukan adalah mengonversi pernyataan dalam basis data logika dan hipotesis ke dalam bentuk klausa (clause) yang melibatkan disjungsi literal.

Resolusi diproses dengan menambahkan basis data dengan negasi hipotesis yang diinginkan. Kemudian klausa diselesaikan dalam basis data tambahan sampai kontradiksinya ditemukan. Jika tidak ditemukan, kita simpulkan bahwa keadaannya konsisten, dan berarti hipotesisnya, pada kenyataannya salah (false).

Sumber :

http://megaapril429.blogspot.com/2017/10/logika-orde-pertama-first-order-logic.html

https://www.scribd.com/document/356627886/Bab-6-First-Order-Logic

https://niftakul.wordpress.com/2017/10/19/logika-orde-pertama-first-order-logic/

http://ulungsatria.webs.com/apps/blog/show/10671951-logika-predikat-

Pertemuan 1 Minggu ke 4, Pengetahuan dan penalaran agen logika

1. Pengetahuan Berbasis Agen

Agen Berbasis Pengetahuan, Knowledge Base (KB) menyatakan apa yang “diketahui” oleh si agent Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB. Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB. Maka sebuah agen berbasis pengetahuan harus bisa mereprentasikan world, state, action, dst. Menerima informasi baru (dan meng-update representasinya). Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property). q Menyimpulkan action apa yang perlu diambil.

Agen Berbasis Pengetahuan atau Knowledge Base (KB) merupakan Himpunan representasi fakta yang diketahui tentang lingkungannya. Tiap fakta disebut sebagai sentence. Fakta tersebut dinyatakan dalam bahasa formal sehingga bisa diolah, menambahkan sentence baru ke KB. Inference Engine merupakan menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB.

Agen Berbasis Pengetahuan dalam representasi, agent dapat dipandang dari knowledge level. Apa saja informasi yang diketahui? Misal sebuah robot “mengetahui” bahwa gedung B di antara gedung A dan gedung C. Agent dapat dipandang dari implementation level Bagaimana representasi informasi yang diketahuinya? Logical sentence di_antara(gdB, gdA, gdC). Natural language “Gedung B ada di antara gedung A dan gedung C”.

Agen Berbasis Pengetahuan, pilihan representasi berpengaruh terhadap apa yang bisa dilakukan inference engine. Pada pendekatan deklaratif programmer memberitahu agent informasi tentang environment. Kalau informasi kurang, agen bisa melengkapinya sendiri. Jika dibandingkan dengan pendekatan prosedural programmer secara eksplisit memrogram agen untuk bertindak. Sehingga bagaimana jika program tidak benar, maka akan besar kemungkinan menyebabkan kesalahan.

Agen Berbasis Pengetahuan, permasalahannya adalah bagaimana representasi yang tepat, sehingga ada dua hal yang harus diperhatikan expressive bisa menyatakan fakta tentang environment, Tractable bisa mengolah/ memproses inference engine (dengan cepat). Knowledge merupakan power atau kekuatan dari pemrograman secara deklaratif. Representasi dan penalaran membentuk suatu Intelligence.

2. Logika

Secara etimologis, logika adalah istilah yang dibentuk dari kata logikosyang berasal dari kata benda logos. Kata logos, berarti sesuatu yang diutarakan, suatu pertimbangan akal (pikiran), kata, percakapan, atau ungkapan lewat bahasa. Kata logikos, berarti mengenal kata, mengenai percakapan atau yang berkenaan dengan ungkapan lewat bahasa. Dengan demikian, dapatlah dikatan bahwa logika adalah suatu pertimbangan akal atau pikiran yang diutrakan lewat kata dan dinyatakan dalam bahasa.

3. Logika Proposi / Logika Sederhana

• Sintaks

Sintaks merupakan kumpulan aturan yang mendefinisikan suatu bentuk bahasa. Sintaks mendefinisikan bagaimana suatu kalimat dibentuk sebagai barisan/urutan dari pemilihan suatu kata dasar. Sintaks dari bahasa pemrograman didefinisikan dengan dua kumpulan aturan, yaitu aturan lexical dan aturan syntactic.

Sintaks berfungsi menyediakan bentuk-bentuk notasi untuk komunikasi antar programmer dan pemroses bahasa pemrograman sehingga dapat mempermudah pembuatan suatu program.

Suatu bahasa pemrograman juga dibangun berdasarkan elemen-elemen syntactic, yang dapat membentuk suatu statement-statement dalam bahasa pemrograman. Elemen-elemen tersebut antara lain :

Himpunan Karakter

Himpunan karakter yang sering dijumpai dan digunakan adalah himpunan karakter ASCII, yang berisi dasar karakter-karakter angka dan huruf.

Identifier

Sintaks dasar dari identifier yang sering digunakan adalah string dari huruf dan angka yang dimulai dengan huruf. Namun, banyak juga variasi dari bahasa pemrograman yang menggunakan suatu identifier dengan tanda “.” Atau “-“.

Simbol untuk operator

Kebanyakan bahasa pemrograman menggunakan karakter “+” dan “-“ untuk merepresentasikan dua buah operasi dasar aritmetika, dan menggunaka kombinasi serta memanfaatkan karakter-karakter spesial untuk suatu operator, atau menggunakan string untuk operator seperti pada FORTRAN dengan .EQ. untuk membandingkan kesamaan dan ** untuk perpangkatan.

Keyword dan reserved word

Keyword merupakan merupakan suatu identifier yang digunakan sebagai bagian tetap dari sintaks suatu statement, misalnya IF untuk memulai suatu statement kondisi atau DO untuk memulai suatu perulangan dalam bahasa FORTRAN.

Noise word

Merupakan kata pilihan yang disisipkan dalam statemen untuk meningkatkan readibility. Sebagai contoh adalah statemen GO TO label. GO merupakan keyword yang harus ada, sedangkan TO merupakan optional yang akan meningkatkan readibility.

Komentar

Penambahan komentar dalam suatu program merupakan hal penting dari dokumentasi suatu program. Bahasa pemrograman mengijinkan komentar dalam beberapa bentuk.

a. Baris komentar yang terpisah di dalam program seperti pada FORTRAN.

b. Penggunaan karakter khusus yang tidak memedulikan baris seperti /* dan */ di bahasa C.

c. Dimulai dari sembarang tempat disuatu baris dengan diawali suatu karakter khusus, seperti “-“ di Ada, “//” di C++ atau “!” di FORTRAN.

Blank

Aturan penggunaan spasi pada bahasa pemrograman sangat beragam. Sebagai contoh adalah bahasa C. Biasanya spasi diabaikan, kecuali jika ada simbol “=+” yang merupakan operator tunggal. Bila dipisahkan dengan spasi maka akan terjadi kesalahan sintaks.

Delimiter dan tanda kurung

Delimiter merupakan elemen syntactic yang digunakan untuk menandai suatu awalan atau akhiran dari suatu syntactic unit seperti statemen atau ekspresi. Tanda kurung biasanya berpasangan dengan delimiter, misalnya kurung kurawal atau pasangan kata begin … end. Delimiter berguna untuk meningkatkan readability suatu program dan juga dapat menghilangkan ambiguitas suatu statemen karena dapat digunakan secara eksplisit untuk memisahkan statemen-statemen yang mirip.

Ekspresi

Merupakan suatu fungsi yang mengakses data dalam suatu program dan mengembalikan suatu nilai. Ekspresi merupakan dasar dari blok syntactic dari statemen yang dibangun.

• Semantik

Sintak mendifinisikan suatu bentuk program yang benar dari suatu bahasa. Semantic mendefinisikan arti dari program yang benar secara sintak dari bahasa tersebut. Semantic suatu bahasa membutuhkan semacam ekspresi untuk mengirimkan suatu nilai kebenaran (TRUE, FALSE, NOT atau nilai integer). Dalam banyak kasus, program hanya dapat dieksekusi jika benar, serta mengikuti aturan sintak dan semantic.

Semantic suatu bahasa pemrograman mempunyai banyak potensial / keunggulan, beberapa diantaranya adalah :

Standarisasi bahasa pemrograman.

Banyak usaha yang dilakukan untuk menstandarisasi bahasa pemrograman seperti FORTRAN, COBOL, dan PL/1, untuk lebih memudahkan programmer menggunakannya.

Referensi untuk user.

Programmer membutuhkan suatu dokumentasi yang pasti supaya user dapat mengoperasikan program yang dibuat dengan baik.

Pembuktian dari program yang benar.

Secara matematis, program tidak mungkin bekerja dan berjalan jika tidak ada semantic.

Referensi untuk implementor.

Semantic akan mencegah suatu gaya bahasa yang tidak kompetibel yang diwujudkan dalam suatu implementasi berbeda walaupun dengan bahasa yang sama.

Implementasi otomatis.

Suatu tool/alat dapat secara otomatis membuatu translasi bahasa yang melebihi parsing. Hal ini dapat dilakukan jika semantic sudah dirumuskan. f. Pemahaman yang lebih baik dari desain bahasa. Jika suatu rumusan semantic sulit untuk di deskripsikan secara formal maka rumusan semantic tersebut juga akan sulit digunakan oleh programmer.

Operational semantic

Pendekatan ini mendefinisikan suatu mesin buatan (abstrak) dengan instruksi-instruksi primitive, tidak perlu realistic, tetapi cukup sederhana supaya tidak muncul kesalahpahaman. Deskripsi semantic dari bahasa pemrograman menentukan suatu translasi ke kode.

Detonational semantic.

Pada pendekatan ini, diberikan suatu fungsi yang memetakan program-program computer yang di tunjuk ke dalam bentuk nilai-nilai abstrak secara matematika (angka, nilai kebenaran, fungsi matematika, dsb).

Axiomatic semantic.

Pada pendekatan ini di definisikan suatu tindakan program yang di bangun dengan property logika yang menyimpan status computer sebelum dan sesudah dieksekusi.

Algebraic semantic.

Pada pendekatan ini dipertimbangkan suatu objek komputasi yang menjadi syarat-syarat dalam aljabar multi stored. Program mengimplementasikan fungsi yang dapat di wujudkan dengan suatu persamaan di antara syarat-syarat tersebut.

Structured operational semantic atau natural semantic.

Seperti dalam pengambilan keputusan secara alamiah dengan logika, program di beri suatu arti dari aturan yang diturunkan yang menggambarkan penilaian gagasan suatu bahasa.

Proses analisa sintak dan analisa semantic merupakan 2 proses yang sangat erat kaitannya dan sulit untuk dipisahkan.

Contoh :

A:= (A+B) * (C+D)

Parser hanya akan mengenali symbol-simbol „:=”, “+”, “*”, parser tidak mengetahui makna dari symbol-simbol tersebut. Untuk mengenali makna dari symbol-simbol tersebut maka compiler memanggil routin semantics.

Untuk mengetahui makna, maka routin ini akan memeriksa :

– Apakah variable yang ada telah didefinisikan sebelumnya.

– Apakah variable-variabel terserbut tipenya sama.

– Apakah operand yang akan di operasikan terserbut ada nilainya, dst.Menggunakan table symbol.

– Pemeriksaan bisa dilakukan pada table identifier, table display, dan table block.

• Inferensi

Metode inferensi adalah suatu teknik/metode untuk menurunkan kesimpulan berdasarkan hipotesa yang diberikan, tanpa harus menggunakan table kebenaran. Beberapa metode inferensi untuk menentukan validitas adalah sebagai berikut :

Modus Ponens

Pada suatu implikasi “jika p maka q” yang diasumsikan bernilai benar, dan apabila juga diketahui bahwa nilai dari anteseden (p) bernilai benar, maka nilai q juga harus benar.

p —> q

p

q

Contoh :

Jika suatu bilangan habis dibagi 2 maka bilangan tersebut adalah bilangan genap.

Suatu bilangan habis dibagi 2.

Bilangan tersebut adalah bilangan genap.

Modus Tollens

Suatu implikasi “jika p maka q” akan selalu ekuivalen dengan kontraposisinya, yaitu “jika bukan q maka bukan p”. dengan demikian, hipotesa kedua dan kesimpulan merupakan kontraposisi hipotesa pertama pada modus ponens.

p –> q

~q

~p

Contoh :

Jika hasil jual lebih dari hasil beli maka penjual itu untung.

Penjual itu tidak untung.

Hasil jual tidak lebih dari pembelian.

Silogisme

Prinsip Silogisme adalah sifat transitif dari implikasi. Artinya, jika suatu implikasi p à q dan q à r keduanya bernilai benar maka implikasi p à q pasti bernilai benar.

p –> q

q –> r

p –> r

Contoh :

Jika ia belajar dengan baik maka ia akan pandai.

Jika ia pandai maka ia akan lulus dalam ujian.

Jika ia belajar dengan baik ia akan lulus dalam ujian.

• Validitas

Menurut Azwar (1986) validitas berasal dari kata validity yang mempunyai arti sejauh mana ketepatan dan kecermatan suatu alat ukur dalam melakukan fungsi ukurnya. Menurut Arikunto (1999) validitas adalah suatu ukuran yang menunjukkan tingkat kesahihan suatu tes. Menurut Nursalam (2003) validitas adalah suatu ukuran yang menunjukkan tingkat kevalidan atau kesahihan suatu instrumen. Berdasarkan beberapa pendapat tentang pengertian validitas di atas, maka dapat diambil kesimpulan bahwa validitas adalah suatu standar ukuran yang menunjukkan ketepatan dan kesahihan suatu instrumen.

Suatu Kalimat logika f bersifat valid jika untuk setiap interpretasinya I for f, f bernilai true.

Contoh :

Ø  (f and g) if and only if (g and f)

Ø  f or not f

Ø  [p and (if r then s)] if only if [(if  r then s ) and p]

Ø  [p or q) or not (p or q)

Ø  (if p then not q) if and only if not (p and q)

• Satisfiability

Sebuah proposisi majemuk dikatakan satisfiable jika ada minimal satu nilai tabel kebenarannya yang bernilai TRUE (benar), Jika proposisi majemuk tersebut tidak memiliki nilai TRUE (benar) sama sekali dalam tabel kebenarannya, maka proposisi majemuk tersebut disebut tidak satisfiable.

Contoh:

Dengan menggunakan table kebenaran, buktikan bahwa : (p ˄ (p q)) adalah satisfiable.

4. Pola Penalaran Pada Logika Proposisi

• RESOLUSI

Resolusi merupakan suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang sering disebut dengan nama klausa.

Resolusi adalah suatu aturan untuk melakukan inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus conjunctive normal form (CNF). Pada logika proposisi, prosedur untuk membuktikan proposisi P dengan beberapa aksioma F yang telah diketahui, dengan menggunakan resolusi.

Algoritma resolusi :

• Konversikan semua proposisi F ke bentuk CNF.
• Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.
• Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
• Seleksi 2 klausa sebagai klausa parent.
• Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.
• Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.

• Forward Chaining

Forward chaining merupakan metode inferensi yang melakukan penalaran dari suatu masalah kepada solusinya. Jika klausa premis sesuai dengan situasi (bernilai TRUE), maka proses akan menyatakan konklusi. Forward chaining adalah data-driven karena inferensi dimulai dengan informasi yang tersedia dan baru konklusi diperoleh. Jika suatu aplikasi menghasilkan tree yang lebar dan tidak dalam, maka gunakan forward chaining.

Contoh :

Terdapat 10 aturan yang tersimpan dalam basis pengetahuan yaitu :

R1 : if A and B then C

R2 : if C then D

R3 : if A and E then F

R4 : if A then G

R5 : if F and G then D

R6 : if G and E then H

R7 : if C and H then I

R8 : if I and A then J

R9 : if G then J

R10 : if J then K

Fakta awal yang diberikan hanya A dan E, ingin membuktikan apakah K bernilai benar. Proses penalaran forward chaining terlihat pada gambar dibawah :

• Backward Chaining

Menggunakan pendekatan goal-driven, dimulai dari harapan apa yang akan terjadi (hipotesis) dan kemudian mencari bukti yang mendukung (atau berlawanan) dengan harapan kita. Sering hal ini memerlukan perumusan dan pengujian hipotesis sementara. Jika suatu aplikasi menghasilkan tree yang sempit dan cukup dalam, maka gunakan backward chaining.

Contoh :

Seperti pada contoh forward chining, terdapat 10 aturan yang sama pada basis pengetahuan dan fakta awal yang diberikan hanya A dan E. ingin membuktikan apakah K bernilai benar. Proses penalaran backward chaining terlihat pada gambar berikut :

5. Inferensi Proposisi yang Efektif

• ALGORITMA BACKTRACKING

Algoritma Backtracking mempunyai prinsip dasar yang sama seperti brute-force yaitu mencoba segalakemungkinan solusi. Perbedaan utamanya adalah pada ide dasarnya, semua solusi dibuat dalam bentuk  pohon solusi (pohon ini tentunya berbentuk abstrak) dan algoritma akan menelusuri pohon tersebu secara DFS (depth field search) sampai ditemukansolusi yang layak. Nama backtrack didapatkan dari sifat algoritma iniyang memanfaat karakteristik himpunan solusinya yang sudah disusun menjadi suatu pohon solusi.Agar lebih jelas bisa dilihat pada pohon solusi berikut:

Misalkan pohon diatas menggambarkan solusi darisuatu permasalahan. Untuk mecapai solusi (5), maka jalan yang ditempuh adalah (1,2,5), demikian jugadengan solusi-solusi yang lain. Algoritma backtrack akan memeriksa mulai dari solusi yang pertamayaitu solusi (5). Jika ternyata solusi (5) bukan solusiyang layak maka algoritma akan melanjutkan ke solusi (6). Jalan yang ditempuh ke solusi (5) adalah (1,2,5) dan jalan untuk ke solusi (6) adalah (1,2,6). Kedua solusi ini memiliki jalan awal yang sama yaitu (1,2). Jadi daripada memeriksa ulang dari (1) kemudian (2) maka hasil (1,2) disimpan dan langsung memeriksa solusi (6). Pada pohon yang lebih rumit, cara ini akan jauh lebih efisien daripada brute-force. Pada beberapa kasus, hasil perhitungan sebelumnya harus disimpan, sedangkan pada kasus yang lainnya tidak perlu.

6. Agen Berbasis Logika Proposisi

• LOGICAL AGENTS

Logic merupakan jantung dari program, para pemrogram mempunyai keyakinan bahwa sebuah computer dapat dibuat mengerti logika, maka computer dapat dibuat untuk berfikir, karena logika kelihatannya menjadi inti dari kecerdasan.

• Problem solving agent hanya bisa menyelesaikan masalah yang lingkungannya accessible
• Kita membutuhkan agen yang dapat menambah pengetahuan dan menyimpulkan keadaan
• Agent yang akan membantu seperti ini kita beri nama knowledge based agent

• LOGIKA PROPOSISI

Logika Proposisi berupa kalimat-kalimat lengkap dari fakta atau kenyataan, atau bisa dikatakan sebuah propositional logic bisa merupakan sebuah proposisi adalah kalimat yang berbentuk dengan sendirinya, apakah kalimat itu bernar atau kalimat itu salah. Propositional logic merupakan operator-operator untuk menghubungkan proposisi-proposisi dalam bentuk, ungkapan dan ekspresi, sebagai kata penyambung logika.

Contoh:

• Tanda “^” artinya “AND”
• Tanda “v” artinya “OR”
• Tanda “ “ artinya “IF THEN”
• Tanda “ “ artinya “IF and only IF then”
• Tanda “=” artinya “assignment”
• Tanda “ “ artinya “NOT (negation)”

Penggunaan dari propositional logic sebagai langkah atau cara mempresentasikan dari pengetahuan dunia yang diperlukan dari sebuah sistem yang sudah terorganisir (AI). Ekspresi-ekspresi dibentuk menurut semua tata bahasa sederhana, dan ekspresi yang sesuai dengan tata bahasa ini disebut well formed formulae (wffs). Tanda kurung digunakan untuk membuat kelas urutan dari penempatan nilai kebenaran, jika tidak yang lain jelas.

Pertemuan 1 Materi 3, Pencarian berbentuk/heuristic search dan eksplorasi

3.1. Strategi pencarian berbentuk/heuristic search stragegy

            Pencarian Heuristik adalah salah satu teknik pencarian pada sistem kecerdasan buatan yang mengembangkan efisiensi dalam proses pencarian. Pada fungsinya, Heuristic akan melihat dan mengevaluasi algoritma pencarian. Pada setiap percabangan pengambilan keputusan, Fungsi heuristic ini akan menilai ketersediaan informasi dan menentukan cabang mana yang akan dipilih dan dapat digunakan untuk mendapatkan solusi yang diinginkan. Heuristic search ini memiliki beragam jenis seperti greedy best first search, A* search, dan memory bounded heuristic search.

3.1.1. Greedy best-first search

          Metode best first search menggunakan fungsi evaluasi yang terdiri atas dua bagian, yaitu fungsi heuristik h(n) dan perkiraan biaya g(n), dimana

f(n) = g(n) + h(n)

Algoritma Greedy Best First Search atau disingkat algoritma greedy merupakan metode yang cukup populer untuk memecahkan masalah optimasi. Secara harfiah, greedy berarti tamak atau rakus. Algoritma greedy menggunakan fungsi evaluasi dengan meniadakan perkiraan biaya g(n), dimana

f(n) = h(n)

Prinsip dari algoritma greedy (Russel dan Norvig, 2003) adalah mengambil setiap kesempatan yang ada saat itu juga, tanpa  memperhatikan  konsekuensi  kedepannya. Algoritma  greedy  membentuk solusi dari langkah demi  langkah, dan pada  setiap langkah  harus dibuat  keputusan yang  terbaik  dalam menentukan  pilihan. Di  setiap langkahnya algoritma greedy mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan. Setiap keputusan yang diambil diharapkan merupakan langkah optimum pada langkah tersebut, dikenali sebagai solusi optimum lokal, kemudian dengan setiap langkah yang ditempuh diharapkan dapat memperoleh solusi optimum di akhir proses, yaitu solusi optimum global. Skema umum algoritma greedy adalah:

a. himpunan kandidat, himpunan ini berisi seluruh elemen pembentuk solusi;

b. himpunan solusi, berisi kandidat-kandidat yang terpilih sebagai solusi persoalan;

c. fungsi  seleksi,  fungsi  yang  pada  setiap  langkah  memilih  kandidat  yang  paling  memungkinkan  mencapai  solusi optimal;

d. fungsi kelayakan, fungsi yang memeriksa apakah suatu kandidat yang terpilih dapat memberikan solusi yang layak, yaitu kandidat bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada;

e. fungsi objektif, fungsi yang memaksimumkan atau meminimumkan nilai solusi. 

3.1.2. A* Search

          Terdapat banyak algoritma pencarian lintasan terpendek, algoritma Dijsktra merupakan salah satu dari algoritma tersebut. Dengan menggunakan fungsi biaya g(n) setiap simpul, algoritma Dijkstra memeriksa kelayakan biaya yang diperlukan untuk mencapai suatu simpul dari sebuah simpul lain. Proses ini dilakukan berulang sampai simpul tujuan diperiksa.

Algoritma Dijkstra memang menjamin didapatkannya jalur optimal, tetapi algoritma ini mempunyai kelemahan. Pemeriksaan simpul akan dilakukan ke segala arah yang dimungkinkan dan pada akhirnya seluruh simpul pada sebuah graf akan diperiksa. Hal ini menyebabkan algoritma ini bekerja dengan lambat, sehingga waktu yang dibutuhkan untuk menemukan solusi akan semakin besar pula.

Algoritma A* adalah algoritma yang menggabungkan Dijkstra dan algoritma Greedy Best First Search. Selain menghitung biaya yang diperlukan untuk berjalan dari simpul satu ke simpul lainnya, algoritma A* juga menggunakan fungsi heuristic untuk memprioritaskan pemeriksaan simpul-simpul pada arah yang benar, sehingga algoritma A* mempunyai efisiensi waktu yang baik dengan tidak mengorbankan perhitungan biaya sebenarnya.

Algoritma A juga membutuhkan dua antrian, yaitu OPEN dan CLOSED. Selain itu, ada juga fungsi heuristik yang memprediksi keuntungan tiap node yang di buat. Yang akan memungkinkan algoritma untuk melakukan pencarian-pencarian lintasan yang lebih di harapkan. Fungsi ini di sebut f’(n) sebagai pendekatan dari fungsi f(n) yang merupakan fungsi evaluasi yang sebenarnya terhadap node n. dalam banyak penarapan, akan lebih baik jika fungsi di definisikan sebagai kombinasi atau jumlah dua komponen yaitu g(n) dan h(n). Fungsi g(n) merupakan ukuran biaya yang di keluarkan dari keadaan awal sampai ke node n. Nilai yang didapat g(n) merupakan jumlahan biaya penerapan setiap aturan yang dilakukan pada sepanjang lintasan trbaik menuju suatu simpul dan bukan merupakan hasil estimasi.

Fungsi h(n) merupakan pengukur biaya tambahan yang harus dikeluarkan dari node n sampai mendapatkan tujuan. Perlu diketahui bahwa g(n), tidak negatif karena bila negatif maka lintasan yang membalik siklus pada graf akan tampak lebih baik dengan semakin panjangnya lintasan.

Secara matematis, fungsi F sebagai estimasi fungsi evaluasi terhadap  node ndapat di tuliskan :

f’(n) = g(n) + h’(n)

Dengan   f’(n) = fungsi evaluasi, g(n) = biaya yang sudah di keluarkan dari keadaan awal sampai keadaan n, h’(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n. Dari fungsi di atas maka ada beberapa kondisi yang perlu diperhatikan, yaitu:

Jika h = h’, berarti proses pencarian telah sampai ke tujuan ( goal ).

Jika g = h’ = 0 maka f’ random, artinya system tidak dapat di kendalikan.  

Jika g = k, k adalah konstanta dan biasanya bernilai 1, h’ = 0, artinya system menggunakan breadth first search.

3.1.3. Memory-bounded heuristic search

            SMA* atau Simplified Memory Bounded A* adalah algoritma pencarian jalur terpendek berdasarkan dari algoritma A*. Keuntungan utama dari algoritma SMA* adalah dia menggunakan bounded memory, sementara algoritma A* mungkin membutuhkan memori exponensial. Semua karakteristik di algoritma SMA* diturunkan dari A*.

3.2. Fungsi Heuristic

            Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

3.3. Algoritma pencarian local dan masalah optimisasi

            Algoritma pencarian lokal untuk masalah optimisasi kombinatorik biasanya digunakan pada pseudopolynomial running time dan algoritma polynomial-time sering tidak dapat menemukan solusi optimum lokal untuk masalah optimisasi NP −hard. Penelitian ini bertujuan mengenalkan konsep optimalitas ε-lokal dan menunjukkan bahwa optimum ε-lokal dapat diidentifikasi dengan waktu polynomial pada masalah ukuran dan 1/ε bilamana hubungan ketetanggan dapat dicari dengan polynomial time untuk ε > 0. Akibatnya, masalah optimisasi kombinatorial memiliki banyak pola pendekatan polynomial-time jika dan hanya jika memiliki fully polynomial-time pola tambahan (augmentation).

3.3.1. Hill Climbing Search

            Hill Climbing ( HC ) atau pendakian bukit merupakan salah satu metode yang masuk dalam kategori metode pencarian heuristik. Dinamakan Hill Climbing ( HC ) atau pendakian bukit karena mempunyai aturan produksi dengan cara menukar dua posisi kota yang saling berdekatan seperti orang yang mendaki bukit. Hill Climbing ( HC ) dibagi menjadi dua jenis yaitu Simple HC ( HC sederhana ) dan Steepest-Ascent HC ( HC dengan memilih kemiringan yang paling tajam/curam ).

Simple HC ( SHC ) bekerja dengan cara memilih secara langsung new state yang memiliki keadaan lebih baik dari pada keadaan sebelumnya  tanpa memperhitungkan keadaan lain yang lebih “curam”.

3.3.2. Simulated Annealing Search

            Simulated Annealing adalah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir kristal atau logam. Algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu.

3.3.3. Local Beam Search

            Dalam ilmu komputer, beam search  adalah algoritma pencarian heuristik yang mengeksplorasi grafik dengan memperluas simpul yang paling menjanjikan dalam rangkaian terbatas. Penelusuran beam adalah optimalisasi pencarian terbaik pertama yang mengurangi kebutuhan memori. Pencarian terbaik-pertama adalah pencarian grafik yang memerintahkan semua solusi parsial (goal). Tapi dalam pencarian balok, hanya sejumlah solusi parsial terbaik yang telah ditentukan dijaga sebagai kandidat.

3.3.4. Genetic Algorithm

            Genetic Algorithm(atau GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dancrossover.

GA diimplementasikan sebagai proses simulasi yang dijabarkan sebagai berikut: Populasi dari representasi abstrak (disebut kromosom, genotip, atau genom) dari candidate solution(disebut individual, atau fenotip) dari optimasi yang berevolusi ke solusi yang lebih baik. Biasanya solusi direpresentasikan ke dalam string biner. Evolusi dimulai dari populasi dari individu yang dihasulkan secara random dan terjadi dalam generasi. Di setiap generasi, fitnessdari setiap individu dalam populasi dievaluasi, beberapa individu dipilih secara stokastik(berdasarkan fitness) dan dimodifikasi(crossover dan kemungkinan mutasi) untuk membentuk populasi baru. Populasi baru lalu dimanfaatkan untuk iterasi selanjutnya. Secara umum, algoritma selesai jika telah menghasilkan generasi maksimum atau hasil dalam populasi dirasa memuaskan (berdasarkan berbagai parameter).

3.4. Agen pencarian online dan lingkungan yang tidak diketahui

- Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian

- Pencarian melebar pertama (Breadth – First Search)

- Pencarian mendalam pertama (Depth – First Search)

Sumber :

https://data-flair.training/blogs/heuristic-search-ai/

https://www.researchgate.net/publication/275659782_Implementasi_Algoritma_Greedy_Best_First_Search_pada_Aplikasi_Permainan_Congklak_untuk_Optimasi_Pemilihan_Lubang_dengan_Pola_Berfikir_Dinamis

https://pdfs.semanticscholar.org/6458/3063f4bd659498aa0c2f4c4f7712217e9fe9.pdf

http://xninexozar.blogspot.com/2017/10/penyelesaian-masalah-pencarian.html

http://ristyindriastuti.blogspot.com/2017/10/email-ristyindriastuti17gmail.html