Representasi Pengetahuan : Logika Predikat

1.      Fungsi-fungsi Logika Predikat

Logika predikat diperkenalkan oleh Sir William Hamilton (1788-1856) dengan doktrinnya dinamakan “Quantification Theory”. Oleh karena itu, logika predikat sebenarnya adalah logika proposisional yang ditambah dengan hal-hal baru, yaitu pengkuantoran.

Logika adalah pada pembuktian validitas suatu argument logika proposional dengan berbagai teknik yang relevan. Yaitu menggunakan table kebenaran sebagai dasar pembuktian dan dan juga menggunakan hukum-hukum logika. Logika proposisional sudah cukup untuk menangani pernyataan-pernyataan yang sederhana dan banyak dijumpai dalam peristiwa sehari-hari. Akan tetapi logika proposisional saja ternyata belum mampu menangani argumen-argumen yang berisi pernyataan-pernyataan yang rumit dan sering dijumpai dalam peristiwa sehari-hari. Sebagai contoh, perhatikan argumen berikut:

Contoh 1:

1)      Semua gajah mempunyai belaka

2)      Dumbo seekor gajah

3)      Dengan demikian, Dumbo memiliki belalai.

Tanpa perlu dibuktikan validitasnya, orang-orang pasti mengatakan argumen tersebut valid karena dengan jelas kesimpulan mengikuti premis-premisnya. Akan tetapi bagaimana cara membuktikannya? Tentunya menggunakan logika proposisional.

ARGUMEN PADA LOGIKA PREDIKAT

Validitas sebuah argumen dapat dibuktikan dengan contoh yang mirip dengan contoh perhatikan contoh argumen berikut:

Contoh 2:

1)      Semua mahasiswa pasti pandai

2)      Badu seorang mahasiswa

3)      Dengan demikian, Badu pandai

Secara nalar, kebanyakkan orang akan menilai bahwa argumen di atas mempunyai validitas yang kuat. Akan tetapi, saat validitas tersebut ingin dibuktikan dengan logika proposisional, ternyata tidak bisa diselesaikan. Pembuktiannya dapat dilakukan dengan mengikuti prosedur logika proposisional dengan menentukan terlebih dahulu proposisi-proposisinya :

A = Semua mahasiswa pasti pandai

B = Badu seorang mahasiswa

C = Badu pasti pandai

Selanjutnya akan menjadi seperti berikut :

A

B

_____

:. C

Dalam ekspresi logika : (A ˄ B)=>C

Dalam bentuk ekspresi logika diatas, tidak ada hukum-hukum logika proposisional yang dapat digunakan  untuk membuktikan validitas argumen tersebut karena tidak ada yang mampu menghubungkan antara ketiga proposisi yang digunakan diatas. Atau tidak mungkin suatu kesimpulan yang berbeda dapat  dihasilkan dari premis-premis yang berbeda. Dengan kata lain, tidak mungkin suatu kesimpulan berupa C dapat dihasilkan dari premis A dan premis B.

Jika argumen diatas masih ingin dibuktikan dengan logika proposisional, maka kalimatnya harus diperbaiki. Misal seperti berikut:

Contoh 3:

1)      Jika Badu seorang mahasiswa, maka ia pasti pandai

2)      Badu seorang mahasiswa

3)      Dengan demikian, ia pasti pandai

Jika diubah dalam bentuk ekspresi logika :

1)      B=>C     premis 1

2)      B             premis 2

3)      C             kesimpulan

Atau dapat juga ditulis : [(B=>C) ˄ B] => C

Dalam logika proposisional, ekspresi logika diatas sudah benar karena kesimpulan diambil dari premispremis. Persoalan yang terjadi adalah pernyataan tersebut tidak sepenuhnya mampu menangkap ide pada argumen yang pertama yaitu “Semua mahasiswa pandai”. Ide pada pernyataan tersebut tidak tertangkap pada argumen kedua karena hanya mampu menunjuk seorang mahasiswa yaitu Badu, bukan semua mahasiswa. Persoalan lain juga terjadi, yakni kesulitan menentukan objek. Misalnya orang yang dimaksudkan jika diganti dengan kata ganti orang.

2.      Logika dan Set Order Pertama

Logika First-Order digunakan dalam ilmu IntelejensiBuatan sebagai Representasi Pengetahuan. Persolan yang ada memiliki pernyataanlebih kompleks lagi tapi dapat diselesaikan dengan Pelacakan Terbalik(Backward)

Contoh:

Diberikanpernyataan sebagai berikut:

1)      Andi adalah seorang mahasiswa

2)      Andi masuk jurusan Informatika

3)      Setiap mahasiswa Informatikapasti mahasiswa Teknik

4)      Kalkulus adalah matakuliah yangsulit

5)      Setiap mahasiswa teknik pastiakan suka kalkulus atau akan membencinya

6)      Setiap mahasiswa pasti akansuka terhadap suatu matakuliah

7)      Mahasiswa yang tidak pernahhadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka terhadapmatakuliah tersebut

8)      Andi tidak pernah hadir kuliahmatakuliah kalkulus.

Buktikan Apakah Andi suka matakuliah kalkulus?

Jawab:

Ubah pernyataan menjadi bentuk formula:

1)      mahasiswa(Andi)

2)      Informatika(Andi)

3)      x: Informatika(x)Teknik(x)

4)      sulit(kalkulus)

5)      x: Teknik(x)suka(x, kalkulus)  benci(x, kalkulus)

6)      x: y: suka(x,y)

7)      x: y: mahasiswa(x)sulit(y)hadir(x,y) suka(x,y)

8)      hadir(Andi,kalkulus)

Pernyataan Apakah Andi suka matakuliah kalkulus = suka(Andi,kalkulus)

Dilakukan Backward /Pelacakan dari belakang seperti yang biasa diterapkan pada ilmu ArtificialIntelegence atau Intelejensi Buatan dengan cara berikut:

suka(Andi,kalkulus)

Substitusi

mahasiswa(Andi)

sulit(kalkulus)

hadir(Andi,kalkulus)

3.      Quantifier Universal

Dalam logika predikat , quantifieri universal merupakan jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “diberi” atau “untuk semua”. Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setiapanggota dari domain wacana. Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setiap anggota domain. Ini menegaskanbahwa predikat dalam lingkup dari quantifier universal benar dari setiap nilai dari variabel predikat .

Hal ini biasanya dilambangkan dengan berbalik A (∀) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier universal  (“∀x”, “∀ (x)”, atau kadang-kadang dengan “(x) “saja). Kuantifikasi Universal berbeda dari kuantifikasi eksistensial (“ada ada”), yang menegaskan bahwa properti atau relasi hanya berlaku untuk setidaknya satu anggota dari domain.

Contoh 1 :

(∀x) (x + x = 2x)

“untuk setiap x (dimana x adalah suatu bilangan), kalimat x + x = 2x adalah benar.”

Contoh 2 :

(∀x) (p) (Jika x adalah seekor kucing -> x adalah binatang).

Kebalikan kalimat “bukan kucing adalah binatang” ditulis :

(∀x) (p) (Jika x adalah seekor kucing -> ~x adalah binatang)

dan dibaca :

– “setiap kucing adalah bukan binatang”

“semua kucing adalah bukan binantang”

Contoh 3:

(∀x) (Jika x adalah segitiga -> x adalah polygon)

Dibaca : “untuk semua x, jika x adalah segitiga, maka x adalah polygon”.

Dapat pula ditulis : (∀x) (segitiga(x) -> polygon(x))

(∀x) (T(x) -> P(x))

Contoh 4 :

(∀x) (H(x) -> M(x))

Dibaca : “untuk semua x, jika x adalah manusia (human), maka x melahirkan (mortal)”.

Ditulis dalam aturan : IF x adalah manusia THEN x melahirkan.

4.      Quantifier Existensial

Dalam logika predikat , suatu quantifier eksistensial adalah jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “ada ada,” “ada setidaknya satu,” atau “untuk beberapa.” Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setidaknya satu anggota dari domain wacana . Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setidaknya satu anggota dari domain. Ini menegaskan bahwa predikat dalamlingkup dari quantifier eksistensial adalah benar dari setidaknya satu nilai darivariabel predikat .

Hal ini biasanya dilambangkan dengan E berubah (∃) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier eksistensial (“∃x” atau “∃ (x)”) Kuantifikasi eksistensial.

Contoh 1 :

(∃x) (x . x = 1)

Dibaca : “terdapat x yang bila dikalikan dengan dirinya sendiri hasilnya sama dengan 1.”

Contoh 2 :

(∃x) (gajah(x) ∧ nama(Clyde))

Dibaca : “beberapa gajah bernama Clyde”.

Contoh 3 :

(∀x) (gajah(x) -> berkaki empat(x))

Dibaca : “semua gajah berkaki empat”.

Universal quantifier dapat diekspresikan sebagai konjungsi.

(∃x) (gajah(x) ∧ berkaki tiga(x))

Dibaca : “ada gajah yang berkaki tiga”

Existensial quantifier dapat diekspresikan sebagai disjungsi dari

urutan ai. P(a1) ∨ P(a2) ∨ P(a3) …∨ P(aN)

5.      Resolusi Logika Predikat

Tujuan dasar resolusi adalah membuat infer klausa baru yang disebut “revolvent” dari dua klausa lain yang disebut parent clause.

Contoh :

A Ú B

A Ú ~B

\ A

Premis dapat ditulis :   (A Ú B) Ù (A Ú ~B)

Ingat Aksioma Distribusi :

p Ú (q Ù r) º (p Ú q) Ù (p Ú q)

Sehingga premis di atas dapat ditulis :

(A Ú B) Ù (A Ú ~B) º A Ú (B Ù ~B) º A

dimana B Ù ~B selalu bernilai salah

Tabel Klausa dan Resolvent

Parent Clause	Resolvent	Arti
p à q   , p atau ~p Ú q, p	Q	Modus Pones
p à q , q à r atau ~p Ú q, ~ q Ú r	p à r atau ~p Ú r	Chaining atau Silogisme Hipotesis
~p Ú q, p Ú q	Q	Penggabungan
~p Ú ~q,  p Ú q	~p Ú p atau ~q Ú q	TRUE (tautology)
~p, p	Nill	FALSE (kontradiksi)

SISTEM RESOLUSI DAN DEDUKSI

Refutation adalah pembuktian teorema dengan menunjukkan negasi atau pembuktian kontradiksi melalui reductio ad absurdum.

Melakukan refute berarti membuktikan kesalahan.

Contoh :

A à B

B à C

C à D

A à D

Untuk membuktikan konklusi A à D  adalah suatu teorema melalui resolusi refutation, hal yang dilakukan :

p à q    º    ~p Ú q

sehingga 

Aà D    º    ~A Ú D

dan langkah terakhir adalah melakukan negasi

             ~(~A Ú D) º     A Ù ~D

Penggunaan konjungsi dari disjunctive form pada premis dan negasi pada konsklusi, memberikan conjuctive normal form yang cocok untuk resolusi refutation.

Dari contoh di atas, penulisannya menjadi :

(~A Ú B) Ù (~B Ú C) Ù (~C Ú D) Ù A Ù ~D

Akar bernilai nill, menunjukkan kontradiksi. Sehingga melalui refutation dapat ditunjukkan konklusi asli (awal) adalah teorema dengan peran kontradiksi.

RESOLUSI PADA PROPOSISI DAN PREDIKAT

1)      Resolusi pada Logika Proposisi

Menggunakan resolusi yaitu suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang sering disebut dengan nama klausa.Pembuktian suatu pernyataan menggunakan resolusi ini dilakukan dengan cara menegasikan pernyataan tersebut, kemudian dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.

Algoritma konversi ke bentuk klausa :

a.       Eliminir a → b menjadi ¬ a v b

b.      Reduksi skope dari ¬ sebagai berikut :

¬ (¬ a ^ b) ¬ a v ¬ b   

¬ (¬ a v b) ¬ a ^ ¬ b

¬ x : P(x) x : ¬ P(x)

¬ x : P(x) x : ¬ P(x)

2)      Resolusi pada Logika Predikat

Logika predikat sebenarnya adalah logika proposional ditambah dengan hal-hal baru seperti kuantor, universe of discourse, term, predikat dan fungsi.

Resolusi pada logika predikat pada dasarnya sama dengan resolusi pada logika proposisi, hanya saja ditambah dengan unifikasi.Pada logika predikat, prosedur untuk membuktikan pernyataan P dengan beberapa pernyataan F yang telah diketahui, dengan menggunakan resolusi, dapat dilakukan melalui algoritma sebagai berikut :

a.       Konversikan semua proposisi F ke bentuk klausa

b.      Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa.Tambahkan   kehimpunan klausa yang telah ada pada langkah

c.       Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :

-          Seleksi 2 klausa sebagai klausa parent

-          Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut  resolvent. Jika ada pasangan literal T dan ¬T2 sedemikian hingga keduanya dapat dilakukan unifikasi, maka salah satu T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari 1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent

-          Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada

Sumber            :

-          http://sandimcs.blogspot.co.id/2014/05/logika-predikat.html

-          https://ismailakbar12.wordpress.com/2015/06/25/makalah-artifical-intellegent-representasi-pengetahuan/

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

-          http://afifrahma.blogspot.co.id/2013/01/resolusi-untuk-logika-predikat.html

Read More

Representasi Pengetahuan : Logika Proposisi

1.      Logika dan  Set

Logika didefinisikan sebagai ilmu untuk berpikir dan menalar dengan benar sehingga didapatkan kesimpulan yang absah.

Tujuan dari logika: memberikan aturan-aturan penalaran sehingga orang dapat menentukan apakah suatu kalimat bernilai benar atau salah.

Representasi Logika dibagi menjadi dua:

·         Propositional Logic (Logika Proposisi)

Suatu Proposisi merupakan suatu statemen atau pernyataan yang menyatakan benar (TRUE) atau salah (FALSE).

·         Predicate Logic (Logika Predikat)

Pada logika predikat proposisi dibedakan menjadi argumen (obyek) dan predikat (keterangan). Secara umum penulisan proposisi dalam logika predikat dapat dinyatakan sebagai berikut:

Predikat (argumen-1, argumen-2,..., argumen-3)

Contoh:

Proposisi: “Bu Atika mencintai Pak Agus Setiawan”

Dalam logika predikat disajikan dalam bentuk:

Mencintai (Bu Atika, Pak Agus Setiawan)

P         Argumen-1            Argumen-2

Contoh Silsilah Keluarga yang dipresentasikan dalam Prolog

Jika silsilah di atas dibentuk dalam Representasi Logika, sebagai berikut:

Orangtua (Komarudin, Andika)

Orangtua (Komarudin, Atika)

Orangtua (Komarudin, Agus)

Orangtua (Andika, Rika)

Orangtua (Atika, Anjar)

2.      Operator Logika

Dalam Propositional Logic fakta dilambangkan dengan simbol misalnya P, Q dan R. Lambang-lambang tersebut dihubungkan dengan relasi-relasi logika. Dengan menggunakan operator logika:

Tabel Kebenaran Logika

3.      Tautologi, Kontradiksi dan Contingent

·         Tautologi

Suatu ekspresi logika yang selalu bernilai benar di dalam tabel kebenarannya, tanpa memedulikan nilai kebenaran dari proposisi yang berada di dalamnya. Jika tautologi dipakai pada suatu argumen, berarti argumen harus mempunyai nilai T pada seluruh pasangan pada tabel kebenaran yang ada membuktikan argumen tadi valid.

Argumen berarti memiliki premis-premis dan mempunyai kesimpulan.

Jika premis-premis benar, maka kesimpulan juga harus benar.

Jika Tono pergi kuliah, maka Tini juga pergi kuliah. Jika Siska tidur, maka Tini pergi kuliah. Dengan demikian, jika Tono pergi kuliah atau Siska tidur, maka Tini pergi kuliah.Diubah ke variabel proposisional:

A = Tono pergi kuliah.

B = Tini pergi kuliah.

C = Siska tidur.

Diubah menjadi ekspresi logika yang terdiri dari premis-premis dan kesimpulan. Ekspresi logika 1 dan 2 adalah premis-premis, sedangkan ekspresi logika 3 adalah kesimpulan.

A->B (premis)

C->B (premis)

(A V C)->B (kesimpulan)

Selanjutnya dapat ditulis sebagai berikut:

((A->B)^(C->B))->((A V C)->B)

Setelah itu membuat tabel kebenaran dari ekspresi logika tersebut. Jadi, jika tabel kebenaran menunjukkan hasil tautologi, maka argumen tersebut valid. Dalam logika, tautologi dapat ditulis T atau 1 saja. Jadi jika A adalah tautologi, maka A = T atau A = 1

Pemanfaatan Tautologi

Ada beberapa hal penting yang diakibatkan oleh tautologi, yakni:

a.       Implikasi secara logis. Misalnya A dan B adalah dua buah ekspresi logika, maka jika dikatakan A secara logis mengimplementasikan B dapat ditulis dengan A ->B

b.      Ekuivalen secara logis. Misalnya A dan B adalah dua buah ekspresi logika, maka jika dikatakan A ekuivalen secara logis dengan B, dapat ditulis dengan: A = B. di sini disyaratkan A = B, jika dan hanya jika A <-> B adalah tautologi.

·         Kontradiksi

Suatu ekspresi logika yang selalu bernilai salah di dalam tabel kebenarannya, tanpa memedulikan nilai kebenaran dari proposisi-proposisi yang berada di dalamnya.

Pada argumen, suatu kontradiksi dapat dijumpai jika antara premis-premis bernilai T, sedangkan kesimpulan bernilai F. Hal ini tentunya tidak mungkin terjadi, karena premis-premis yang benar harus menghasilkan kesimpulan benar.

Dalam bahasa logika konjungsi dari semua premis-premis dengan negasi dari kesimpulan selalu bernilai F, dan terjadi kontradiksi. Negasi kesimpulan berarti memberi nilai F pada negasi kesimpulan.

Dalam logika, kontradiksi dapat ditulis F atau 0 saja. Oleh karena itu, jika A adalah kontradiksi, maka A = F atau A = 0

·         Contingent

Suatu ekspresi logika yang mempunyai nilai benar dan salah di dalam tabel kebenarannya, tanpa memedulikan nilai kebenaran dari proposisi-proposisi yang berada di dalamnya.

·         Ekuivalen Logis

Proposisi A dan B disebut ekuivalen secara logis jika A ekuivalen B adalah tautologi. Notasi atau simbol A ekuivalen B menandakan bahwa A dan B adalah ekuivalen secara logis. Proposisi dapat diganti dengan ekspresi logika berupa proposisi majemuk.

Pada tautologi dan juga kontradiksi dapat dipastikan bahwa jika dua buah ekspresi logika adalah tautologi, maka kedua buah ekspresi logika tersebut ekuivalen secara logis, demikian juga jika keduanya kontradiksi.

Pada contingent, jika urutan T dan F atau sebaliknya pada tabel kebenaran tetap pada urutan yang sama, maka tetap disebut ekuivalen secara logis.

4.      Resolusi Logika Proposisi

Sebelum resolusi dapat diterapkan, wff harus diletakkan dalam bentuk casual

Contoh :

Some programmers hate all failures

No programmer hates any success

\ No failure is a success

P(x) = x is a progammer

F(x) = x is a failure

S(x) = x is a success

H(x,y) = x hates y

Premise dan kesimpulannya

(1)   ($x) [P(x) Ù ("y) (F(y) à H(x,y))]

(2)   ("x) (P(x) à ("y) (S(y) à ~H(x,y))]

(3)   ~("y) (F(y) à ~S(,y))

Konversi ke bentuk clausal :

·         Hilangkan kondisional,   (p à q) º ~p v q

·         Geser negasi ke dalam (reduksi skope ~). Negasi digeser hanya berlaku untuk atomik formula

·         Hilangkan quantifier eksistensial

-          Jika $ tidak ada dalam skope ", ganti variabel dengan suatu konstanta baru ($x)   P(x)  diganti P(a)

-          Jika $ berada dalam skope ", ganti variabel dengan suatu fungsi yang memiliki argumen semua variabel dari " tersebut  "x ,"y , $z   P(x,y,z) diganti menjadi "x,"y, P(x,y,F(x,y))

·         Standarisasi variabel (jika perlu) sehingga tiap quantifier memiliki variabel yang berbeda

·         Geser semua " ke kiri (karena semua quantifier punya nama yang berbeda, pergeseran tidak mempengaruhi hasil) Bentuk ini disebut prenex normal form terdiri atas prefix quantifier yang diikuti matriks.Hilangkan "." tidak perlu ditulis, diasumsikan semua variabel terkuantifikasi universa.l Geser disjungsi (V) kedalam, sehingga terbentuk conjungsi normal formBuang konjungsi dan uraikan menjadi klausa-klausa

·         Standarisasi variabel (jika perlu) sehingga tidak ada variabel yang muncul pada lebih dari 1 klausa.

Lakukan langkah-langkah resolusi pada CNF (BP Ù Øα), α adalah pernyataan yang harus dibuktikan Resolusi adalah teknik untuk membuktikan sebuah pernyataan pada logika proposional atau kalkulus predikat. Refutasi=resolusi, membuktikan teorema dengan menegasikan pernyataan yang harus dibuktikan dan menambahkannya ke kumpulan aksioma yang diketahui benar, Semua aksioma dalam bentuk normal yaitu sebuah kalimat atau disjungsi beberapa kalimat, pernyataan terbukti benar jika refutasi menghasilkan kalimat kosong

Sumber            :

-          http://yanworks.blog.binusian.org/2010/03/09/tugas-intelegensia-semu-forum/

-          http://fajarnoverdi.blogspot.co.id/2011/01/tautologi-kontradiksi-contingent-dan.html

-          http://lutfiatulm.blogspot.co.id/2013/03/representasi-pengetahuan.html

Read More