Reza Asrizal

I'm Binusian

First Order Logic

March31

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.

First order logic adalah sebuah bahasa formal yang digunakan di ilmu matematika, philosophy, bahasa dan ilmu komputer. Disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. 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 masalah dalam berbagai keadaan umum yang telah membingungkan sebagian besar ahli-ahli logika abad pertengahan.

Filsuf berkebangsaan Jerman yang bernama Gottlob Frege menebitkan The Begriffsschrift, dianggap sebagai asal muasal dari teori logika modern. Akan tetapi, dalam risalat milik Friege ini masih terdapat banyak kekurangan dalam beberapa bagian dan janggal dalam penotasiannnya. Walaupun demikian, penemuan Frege ini tetap diakui. Selain penemuan dari Frege, formulasi dari logika predikat yang sering digunakan sekarang adalah firstorder logic atau yang biasa dikenal dengan kalkulus predikat yang tercatat dalam Principle of Theorical Logic yang ditulis oleh David Hilbert dan Wilhelm Ackerman pada tahun 1928. First order logic dalam hal ini merupakan dasar pendiri logika matematika modern.

Beberapa poin penting yang membedakan kalkulus predikat dengan logika Aristotle diantaranya:

  1. Di dalam kalkulus predikat didefinisikan bahwa subjek adalah hanya sebuah individu tidak pernah merupakan sekelompok individu. Karena subjek dalam kalkulus predikat ini hanyalah sebuah individu, maka subjek di sini lebih umum untuk disebutkan sebagai individual.
  2. Kalkulus predikat memakai banyak simbol-simbol khusus untuk menotasikan sesuatu. Huruf kecil a, b, c, d, …, z digunakan untuk menyatakan individual. Huruf kapital M, N, P, Q, R, … digunakan untuk menyatakan predikat. Jika terdapat notasi seperti Ma, maka dikatakan bahwa adalah argument untuk M.
  3. Selain huruf kecil dan huruf kapital, kalkulus predikat juga menggunakan beberapa simbol khusus untuk menotasikan operator-operator logika. Beberapa simbol khusus itu adalah: ∧ ∨ ~ ⊃ ≡
  4. Sebuah formula adalah ekpresi yang memiliki arti dan dibangun oleh atom-atomnya dan digabungkan dengan menggunakan operatoroperator logika.
  5. Kalkulus predikat memiliki kapabilitas yang besar dalam mengekspresikan suatu hal. Banyak pernyataan dalam natural languageyang bisa direpresentasikan dengan baik oleh kalkulus predikat. Hal inilah yang kurang dimiliki oleh logika Aristoteles.

Dalam first-order logic yang paling utama adalah bahwa dunia berisi objek-objek yaitu identitas (ciri-ciri individu) dan sifat (properties) yang membedakan mereka dengan objek yang lain. Diantara objek tersebut, akan dibuat bermacam-macam relasi. Beberapa relasi adalah fungsi yaitu hubungan dimana hanya ada satu nilai untuk satu input. Jadi pada first-order logic mengasumsikan “world” memuat :

– Objek : hal-hal yang berhubungan dengan identitas individu, misalnya : manusia, rumah, teori-teori, warna, mobil, dan lain-lain.

– Sifat (properties): sifat benda yang membedakannya dari benda lain, misalnya: merah, bulat, tipis, dan lain-lain

– Relasi : hubungan antara benda yang satu dengan benda yang lainnya, misalnya: lebih besar dari, lebih kecil dari, memiliki, terjadi setelah, dan lain-lain.

– Fungsi (Functions): merupakan subset dari hubungan di mana hanya ada satu “nilai” untuk setiap “input” yang diberikan, misalnya: ayah dari, teman baik, dan lain-lain.

First Order Logic sangat penting dalam ilmu matematika, filsafat, kecerdasan buatan, karena ruang lingkupnya, sebab keberadaan manusia sehari-hari selalu berhubungan dengan obyek dan hubungan antar manusia sendiri. Sehingga kita tidak dapat menyangkal bahwa dunia ini terdiri dari obyek dan hubungan (relasi).

 

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, yaituuniversal 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}

 

Binus

posted under Uncategorized

Email will not be published

Website example

Your Comment: