Taufiq Hidayat

Hidup (incl. Informatika) hanyalah untuk Allah Ta’ala

Bookmark and Share

First Order Logic

Posted by Taufiq Hidayat on August 3rd, 2010

Logika Proposisi (Propositional Logic) menawarkan logika dalam bentuk sederhana sehingga mudah dipahami. Meskipun begitu, Logika Proposisi sudah mampu membantu menarik kesimpulan. Namun, banyak kasus yang muncul akan menjadi terlihat panjang dan rumit saat diwujudkan dalam bentuk Logika Proposisi. Dan itu bisa lebih panjang dan rumit dibandingkan problem itu sendiri.

Saya ambil contoh berikut ini. Di sebuah kelas II SD, terdapat 35 siswa. Setiap hari Senin sampai dengan Kamis, mereka mengenakan seragam merah-putih. Sedangkan hari lain, mereka mengenakan seragam pramuka. Anak tetanggaku yang bernama Amin, ada salah satu siswa kelas II SD tersebut. Hari Rabu pagi kami bertemu saat dia berangkat sekolah. Seragam apa yang dia kenakan?

Bagaimana menyelesaikan contoh tersebut dengan menggunakan Logika Proposisi?
Solusi:

Misalkan:

p : amin adalah siswa kelas II SD
q : amin mengenakan seragam merah putih
r : hari rabu

Kalimat yang bisa kita nyatakan dari cerita tersebut adalah

1 : p Λ r → q
2 : p
3 : r

Dengan ekpresi seperti itu, kita sudah bisa menarik kesimpulan tentang Amin. Tetapi banyak informasi yang tidak dinyatakan dan terlewatkan. Akibatnya,  ekspresi tersebut tidak bisa digunakan untuk membuat kesimpulan tentang seragam yang dipakai Ali pada hari Rabu jika diketahui bahwa Ali juga seorang siswa kelas SD tersebut. Agar bisa membuat kesimpulan tentang Ali, kita bisa mengubahnya menjadi seperti di bawah ini:

1 : p1 Λ r → q
2 :
p1
3 : r
4 : p2 Λ r → q
5 :
p2

dengan p1 berarti "amin adalah anak kelas II SD" dan p2 berarti "ali adalah anak kelas II SD". Bagaimana jika untuk semua siswa? Kita harus menambahkan lagi kalimat nomor 1 dan 2 dengan sebelumnya mengubah p1 menjadi p3. Demikian seterusnya sampai p35. Maka akan diperoleh 71 kalimat. Padahal, solusi ini hanya untuk hari Rabu saja, belum hari-hari yang lain.

Predicate: Simbol dengan Parameter

First order Logic menawarkan penggunaan simbol dengan parameter. Simbol ini dikenal sebagai predikat. Sebuah predikat didefinisikan sebagai atribut(sifat) sebuah obyek atau relasi antar obyek. Obyek-obyek tersebutlah yang dijadikan sebagai parameter predikat tersebut.

Sebagai contoh, kita kembali ke contoh sebelumnya. Untuk menyelesaikan contoh tersebut, kita menggunakan simbol p untuk menyatakan atribut seorang siswa kelas II SD, r untuk menyatakan atribut nama hari, dan q untuk menyatakan relasi mengenakan seragam. Definisi lengkap setiap simbol, termasuk parameternya, adalah sebagai berikut:

p(x) : x adalah seorang siswa kelas II SD
r(x) : x adalah nama hari
q(x,y) : x mengenakan seragam y.

Dengan definisi tersebut, jika kita ingin mengungkapkan kalimat amin adalah seorang siswa kelas II SD, hari rabu, dan amin mengenakan seragam pramuka maka dapat dinyatakan sebagai berikut:

p(amin)
r(rabu)
q(amin,pramuka)

Quantifier

Selain penggunaan predikat, First Order Logic juga menawarkan quantifier untuk membuat kalimat logika yang lebih sederhana. Ada 2 jenis quantifier, yaitu universal dan existential. Quatifier ini berlaku terhadap parameter yang muncul di sebuah kalimat masih dalam bentuk variabel. Universal quantifier terhadap sebuah variabel x (disimbolkan dengan ∀x) berarti bahwa kalimat tersebut berlaku untuk setiap obyek x, sedangkan existential quantifier (disimbolkan dengan x) berarti berlaku untuk sebagian obyek saja.

Contoh: Menggunakan definisi untuk p(x), r(x), dan q(x,y), berikut adalah kalimat-kalimat logika dengan menggunakan quantifier dan artinya:

∀x(p(x) Λ r(rabu) → q(x,merah-putih)) : untuk setiap x, jika x adalah seorang siswa kelas II SD dan pada hari Rabu maka x akan mengenakan seragam merah-putih.

x(p(x) ¬q(x,merah-putih)) : ada x, jika x adalah seorang siswa kelas II SD maka x tidak mengenakan seragam merah putih.

Contoh First Order Logic dan Penarikan Kesimpulan

Lihat kembali contoh seragam Amin di atas. Solusi untuk problem di atas adalah sebagai berikut.

Solusi:

Misalkan:

p(x) : x adalah seorang siswa kelas II SD
r(x) : x adalah nama hari
q(x,y) : x mengenakan seragam y.

Kalimat yang bisa kita nyatakan dari cerita tersebut adalah

1 : ∀x(p(x) Λ r(senin) → q(x,merah-putih))
2 : ∀x(p(x) Λ r(selasa) → q(x,merah-putih))
3 : ∀x(p(x) Λ r(rabu) → q(x,merah-putih))
4 : ∀x(p(x) Λ r(kamis) → q(x,merah-putih))
5 : ∀x(p(x) Λ r(jumat) → q(x,pramuka))
6 : ∀x(p(x) Λ r(jumat) → q(x,pramuka))

Jika diketahui bahwa Amin adalah seorang siswa kelas II SD dan hari rabu, maka ditambahkan kalimat berikut:

7 : p(amin) Λ r(rabu)

Proses penarikan kesimpulan untuk menjawab pertanyaan apa seragam yang dipakai oleh Amin pada hari Rabu adalah sebagai berikut:

8 : p(amin) Λ r(rabu) → q(amin,merah-putih) {Instansiasi x dengan Amin pada kalimat 3}
9 :
q(amin,merah-putih) {Modus Ponens antara 7 dan 8}

Arti kalimat 9 adalah Amin mengenakan seragam merah-putih.

—————- []

Instansiasi: membuang quantifier dan mengganti kemunculan setiap variabel yang terkait dengan quantifier tersebut dengan sebuah obyek.

Contoh yang lain: Menggunakan contoh seragam siswa kelas II SD di atas, tetapi yang ditanyakan adalah apakah Taufiq seorang siswa kelas II SD jika diketahui dia tidak mengenakan seragam pramuka pada hari Jumat.

Solusi:

Menggunakan definisi sebelumnya, kita tetap memperoleh kalimat logika sebagai berikut:

1 : ∀x(p(x) Λ r(senin) → q(x,merah-putih))
2 : ∀x(p(x) Λ r(selasa) → q(x,merah-putih))
3 : ∀x(p(x) Λ r(rabu) → q(x,merah-putih))
4 : ∀x(p(x) Λ r(kamis) → q(x,merah-putih))
5 : ∀x(p(x) Λ r(jumat) → q(x,pramuka))
6 : ∀x(p(x) Λ r(jumat) → q(x,pramuka))

Diketahui bahwa taufiq tidak mengenakan seragam pramuka pada hari Jumat. Ditambahkan kalimat-kalimat berikut:

7 : ¬q(taufiq,pramuka)
8 : r(jumat)

Proses penarikan kesimpulan untuk menjawab pertanyaan apa Taufiq seorang siswa kelas II SD adalah sebagai berikut:

9 : p(taufiq) Λ r(jumat) → q(taufiq,pramuka) {Instansiasi x dengan taufiq pada kalimat 5}
10 :
¬(p(taufiq) Λ r(jumat)) {Modus Tollens antara 7 dan 9}
11 : ¬p(taufiq) V ¬r(jumat) {Hukum de Morgan untuk 10}
12 : p(taufiq) ¬r(jumat) {Ekuivalensi implikasi dengan 11}
13 : ¬p(taufiq) {Modus Tollens antara 8 dan 12}

Arti kalimat 14 adalah Taufiq bukan seorang siswa kelas II SD.

—————- []

19 Responses to “First Order Logic”

  1. va Says:

    dear mas taufik,
    ada temen saya yg kasih soal,.
    " aq mau beli mobil seharga 100 jt. tapi belum pnya uang.
    aq minjem ke si A 50jt sm ke si B 50 jt.
    harga mobil 97 juta, jadi sisa tinggal 3 juta.
    untuk mengurangi hutang aq balikin ke si A 1jt ke s B 1jt.
    dan sisanya 1 jt aq kantongin.
    jadi total hutang aq ke s A dan S B masing2 49 jt.

    anehnya klw dijumlahkan seluruhnya 49jt (ke s A) + 49jt (ke s B) + 1jt (yg aq kantongi) = 99 jt.
    padahal kan uang nya ada 100jt.
    nah yg 1jt nya kmn?

  2. Taufiq Hidayat Says:

    @Va
    Tidak tahu, mas, karena persoalannya saja begitu susah dipahami. Sebenarnya ini mau membandingkan apa (nilai 49 + 49 + 1) dengan apa (nilai 100)? Kalau itu 2 hal yang berbeda, kenapa harus diinginkan menjadi sama?

    Sebagai contoh, misal dalam keuangan ada perhitungan harta dan ada perhitungan kas. Jelas keduanya adalah 2 hal yang berbeda. Kalau kemudian kita tanyakan “kenapa saldo harta dan saldo kasnya berbeda”, itu berarti pertanyaan yang aneh.

  3. Toar Says:

    kyknya soal dari sodara Va salah deh. tp kl mau di bagi sama rata knp ngga di bagi 1jt\2 = 500rb/org.

  4. dhani Says:

    ini maksudnya first order logic = propositional logic? ==a

  5. Taufiq Hidayat Says:

    @Dhani.
    Tidak, Mas Dhani. First order logic berbeda dengan propositional logic. Bagian awal tulisan ini hanya sekedar menjelaskan salah satu sebab kenapa harus ada first order logic yang disebabkan oleh adanya kelemahan pada propositional logic.

  6. rian Says:

    Assalamualaikum,
    Pak, first order logic bisa memecahkan masalah menyusun angka dalam permainan 8 puzzle gak?

  7. Taufiq Hidayat Says:

    wa 'alaykumussalaam,

    Insya Allah, bisa, Mas. Dalam hal ini, first order logic digunakan untuk representasi pengetahuan. Sedangkan strategi penyelesaiannya dipelajari di Artificial Intelligence, khususnya di bagian Planning.
    Itu sepengetahuan saya.

  8. Mebel Says:

    bingung saya mas kalau sudah masuk ke kode kode seperti tersebut

  9. Sukron Hidayatullah Says:

    Terima kasih, saya sekarang lebih paham..
    lebih mudah ini daripada yg diterangkan dosen.. ^_^

  10. Helmi Kurniawan Says:

    Assalamualaikum,
    Pak Taufik, saya ada pertanyaan, jika saya memiliki kalimat FOL seperti ini

    A^B^C^D^E^F^G^H^I^J^K^L^M => N

    maka bagaimanakah bentuk konversinya dalam bentul CL (Clausal Form) ?

    Terima kasih

  11. Helmi Kurniawan Says:

    Assalamualaikum,
    Pak Taufik, saya ada tambahan pertanyaan 1 lagi, untuk kasus kalimat FOL berikut

    (A^B=>C)^(D^E^F=>G)=>H

    jika dikonversi ke bentuk CL, bagaimana Pak?

    Terima kasih

  12. Taufiq Hidayat Says:

    to Helmi:
    Wa 'alaykumussalaam wa rahmatullaah...

    Saya coba menjawab pertanyaan Mas Helmi.

    Soal 1:
    AΛBΛCΛDΛEΛFΛGΛHΛIΛJΛKΛLΛM => N
    > ¬(AΛBΛCΛDΛEΛFΛGΛHΛIΛJΛKΛLΛM)VN
    > ¬AV¬BV¬CV¬DV¬EV¬FV¬GV¬HV¬IV¬JV¬KV¬LV¬MVN

    Soal 2:
    (AΛB=>C)Λ(DΛEΛF=>G)=>H
    > ¬((AΛB=>C)Λ(DΛEΛF=>G)) V H
    > ¬(¬(AΛB) V C) Λ (¬(DΛEΛF) V G)) V H
    > ¬((¬A V ¬B V C) Λ (¬D V ¬E V ¬F V G)) V H
    > (¬(¬A V ¬B V C) V ¬(¬D V ¬E V ¬F V G)) V H
    > (A Λ B Λ ¬C) V (D Λ E Λ F Λ ¬G) V H
    > (A V (D Λ E Λ F Λ ¬G) V H) Λ (B V (D Λ E Λ F Λ ¬G) V H) Λ (¬C V (D Λ E Λ F Λ ¬G) V H)

    saya tulis dalam bentuk susunan konjungsi ke bawah, hasil berikutnya menjadi:

    (A V D V H)
    Λ (A V E V H)
    Λ (A V F V H)
    Λ (A V ¬G V H)
    Λ (B V D V H)
    Λ (B V E V H)
    Λ (B V F V H)
    Λ (B V ¬G V H)
    Λ (¬C V D V H)
    Λ (¬C V E V H)
    Λ (¬C V F V H)
    Λ (¬C V ¬G V H)

  13. Helmi Kurniawan Says:

    Terima kasih banyak Pak Taufiq,ini sangat membantu saya 🙂
    Semoga Bapak tidak keberatan kalau nanti saya ada pertanyaan lain lagi.

    Semoga semakin sukses Pak.

  14. Helmi Kurniawan Says:

    Assalamualaikum,

    Pak Taufiq, saya ingin tanya lagi.
    Apakah bentuk kalimat FOL berikut ini diperbolehkan? Jika tidak, maka bagaimana alternatif bentuk kalimat FOL yang benar untuk mengakomodir pernyataan dalam kalimat berikut?

    (A=>B)=>C

    Terima kasih

  15. Taufiq Hidayat Says:

    Wa 'alaykumussalaam...

    Boleh.

    Jadi muncul pertanyaan, apa yang menyebabkan kalimat tersebut "meragukan"?

  16. Helmi Kurniawan Says:

    Sebenarnya saya tidak menemukan ada aturan yg melarang bentuk kalimat itu, tapi saya masih merasa ragu, jadi saya tanyakan ke Bapak.

  17. Tugas GSLC-1 Intelegensia Semu | BLOG BINUS Says:

    [...] Referensi : http://taufiq.staff.uii.ac.id/2010/08/03/first-order-logic/ [...]

  18. Helmi Kurniawan Says:

    Assalamualaikum,
    Pak Taufik saya ingin tanya lagi, tapi kali ini menyinggung topik Confusion matrix dalam Machine Learning. Apakah ada ukuran dan judgement mengenai False Positive Rate (FPR), Pak? Misalkan jika FPR > 0,5 maka model/metode tidak baik atau misal jika FPR < 0,2 maka model/metode sudah cukup baik. Atau bagaimanakah interpretasi yang baik terhadap nilai FPR dari suatu model/metode?

    Terima kasih

  19. Taufiq Hidayat Says:

    To: Helmi Kurniawan.

    Wa 'alaykumussalaam wa rahmatullah...
    Sebelumnya mohon maaf karena keterlambatan reply saya.

    Tentang pertanyaan Mas Helmi, saya belum menemukan standar angka untuk FPR.
    Pada umumnya angka itu digunakan untuk membandingkan 2 model/metode sehingga bisa menentukan metode yang lebih baik.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>