Logika Orde Pertama (First-Order Logic)

Nama : Ananto Dwicahyo
NPM : 10115651
Kelas : 3KA10
Dosen : Essy Malays Sari Sakti

Logika orde pertama yang juga dikenal sebagai kalkulus predikat orde pertama dan predikat logika adalah kumpulan sistem formal yang digunakan dalam matematika, filsafat, linguistik, dan ilmu komputer. Logika orde pertama menggunakan variabel terukur daripada objek non-logis dan memungkinkan penggunaan kalimat yang mengandung variabel, sehingga daripada proposisi seperti Socrates adalah orang dapat memiliki ungkapan dalam bentuk "ada X sedemikian rupa sehingga X adalah Socrates dan X adalah seorang pria "dan ada ada quantifier sementara X adalah variabel.
Komponen-komponen penting yang ada pada first order logic yaitu :

Objects : merupakan sesuatu yang dikenai logika-logika yang memiliki identitas untuk masing-masing individual (komputer, rumah, mobil, ...).

a.       Properties : sifat yang dimiliki oleh objek dan merupakan pembeda dengan objek lainnya (merah, besar, lingkaran, ...).

b.      Relations : aksi atau aktifitas yang menjadi penghubung antar objek dalam berelasi (saudara dari, lebih tinggi dari, bagian dari).

c.       Functions : merupakan relation yang memiliki satu nilai (ayah dari, teman baik,...).
 Sintaks First Order Logic

Tata bahasa pada first order logic meliputi :

1. Terms
Merupakan ekspresi logika yang mengacu pada sebuah objek. Terms bisa berupa constant, variable, atau function.

2. Atomic sentences
Merupakan komponen yang dapat terbentuk dari Predicate(Term, ...) atau Term=Term. Atomic sentence merupakan kalimat paling sederhana dan belum memiliki komponen logika lainnya.
3. Complex sentences
Merupakan kalimat kompleks yang tersusun dari beberapa atomic sentence yang saling terhubung berdasarkan logika dengan menggunakan connective.

Semantik First Order Logic
Pada first order logic sama halnya dengan propositional logic sebuah kalimat first order logic dikatakan true terhadap sebuah model, artinya kalimat first order logic memiliki nilai kebenaran tertentu sehingga dianggap true atau false. Satu kalimat dalam first order logic dapat diinterpretasikan banyak cara dalam sebuah model. Model dalam first order logic terdiri dari :
1.Objects : elemen-elemen yang nyata ada pada permasalahan (domain elements)
2.Relations : hubungan antara elemen-elemen / objek-objek tertentu.

Quantifiers
Universal quantifiers Universal menyatakan logika yang digunakan untuk menunjuk sesuatu yang bersifat umum. Simbol
∀
 yang memiliki makna "untuk semua atau setiap" atau "for all" terhadap sebuah variabel x yang disimbolkan dengan∀x berarti bahwa kalimat tersebut  berlaku untuk setiap objek x. Contoh permasalahan pada first order logic yang menggunakan Universal Quantifiers adalah sebagai berikut : Misalkan ada kalimat "Ikhsan adalah anak kecil", kalimat ini akan dinyatakan sebagai AnakKecil(Ikhsan), dan ada kalimat "Andi suka permen" dinyatakan sebagai Suka(Andi,Permen). Jika kita ingin membuat kalimat "Untuk setiap objek x, jika x adalah anak kecil maka x suka  permen". Maka kalimat dapat kita tuliskan pada bentuk first order logic sebagai:∀x AnakKecil(x)⇒Suka(x,Permen) kalimat tersebut akan bernilai benar jika dan hanya  jika semua kalimat di bawah ini benar. AnakKecil(Budi)⇒Suka(Budi,Permen)∧AnakKecil(Rahmad)⇒Suka(Rahmad,Permen)∧
 AnakKecil(Anton)⇒Suka(Anton,Permen)∧

Existential menyatakan logika yang digunakan untuk menunjuk sesuatu yang bersifat khusus. Artinya hanya beberapa bagian atau sebagian saja dari keseluruhan himpunan.Logika ini merupakan kebalikan dari logika Universal. Logika ini disimbolkan dengan∃ yang memiliki makna "There Exist" atau (ada satu atau beberapa). Kita dapat menyatakan kalimat "Ada objek x, jika x adalah anak kecil maka x suka permen" menjadi first order logic sebagai berikut:∃
x AnakKecil(x)∧SukaPermen(x).

Equality merupakan pembandingan terhadap dua kalimat atau term yang memiliki nilai logika true atau false. Kedua kalimat dianggap sama jika memiliki nilai logika yang sama. Term1 =Term2 akan diinterpretasikan benar jika dan hanya jika memiliki nilai yang sama.

Mengubah Logika Order Pertama Menjadi Logika Proposisi
Representasi 4 kategori silogisme menggunakan logika predikat

 

Kaidah Universal Instatiation merupakan state dasar, dimana suatu individual dapat digantikan (disubsitusi) ke dalam sifat universal.

Contoh :
Misal, φ merupakan fungsi proposisi :
(∀ x) φ(x)
∴ φ(a)
merupakan bentuk yang valid, dimana a menunjukkan spesifik individual, sedangkan x adalah suatu variabel yang berada dalam jangkauan semua individu (universal)

Contoh lain : (∀ x) H(x)
∴ H(Socrates)
• Berikut ini adalah contoh pembuktian formal silogisme
All men are mortal
Socrates is a man
Therefore, Socrates is mortal
Misal : H = man, M = mortal, s = Socrates
1. (∀ x) (H (x) -> M(x))
2. H(s) / ∴ M(s)
3. H(s) -> M(s) 1 Universal Instatiation
4. M(s) 2,3 Modus Ponens

Rekayasa pengetahuan pada logika orde pertama

1.      Identify the task.

2.      Assemble the relevant knowledge.

3.      Decide on a vocabulary of predicates, functions, and constants.

4.      Encode general knowledge about the domain

5.      Encode a description of the specific problem instance.

6.      Pose queries to the inference procedure and get answers.

7.      Debug the knowledge base.

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 :

Dua atom (konstanta atau peubah) adalah identik.
Dua daftar identik, atau ekspresi dikonversi ke dalam satu buah daftar.
Sebuah konstanta dan satu peubah terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.
Sebuah peubah tak terikat dipersatukan dengan sebuah peubah terikat.
Sebuah peubah terikat dipersatukan dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta tidak ada konflik.
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).
Dua peubah terikat disatukan jika keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah atau konstanta).

Cara backward chaining
Pada backward chaining, kita memulai pengecekan dengan menggunakan pertanyaan tadi sebagai awal chain. Lalu dilakukan chaining dengan premis-premis lain hingga menghasilkan nilai null.

Cara proof by resolution

Proof by resolution menggunakan teknik kontradiksi, dimana kita menggunakan premis yang berlawanan nilainya untuk membuktikan sesuatu.
Untuk melakukan proof by resolution, semua premis harus dibuat menjadi clause normal form (CNF) terlebih dahulu. Dalam CNF, semua premis tidak boleh menggunakan kuantor,  implikasi (jika X maka Y) dan biimplikasi (X jika dan hanya jika Y). Lalu, jawaban dari pertanyaan dianggap salah dan dijadikan premis. Premis baru ini dijadikan awal dari pembuktian.

Referensi
Ebook Artifical Intelligence A Modern Approach(3rd Edition)
https://id.scribd.com/document/356627886/Bab-6-First-Order-Logic
http://www.binus.ac.id