Penyelesaian masalah melalui proses pencarian atau searching

Nama:Rendy Noviantono 

NPM:15115757

Kelas:3KA10

Dosen: Essy Malays Sari Sakti

Logika Orde Pertama (First-Order Logic)

First-order logic itu salah satu jenis sistem formal, yang digunakan untuk membuktikan kebenaran dari sebuah pernyataan.

Dalam first-order logic, setiap pernyataan dianggap memiliki predikat. Predikat itu dapat menghubungkan pernyataan yang satu dengan yang lain.

Kalimat-kalimat dalam first-order-logic dibuat dengan format P( X,  Y). P adalah predikat dan X adalah subjek. Y adalah objek, yang merupakan variabel yang opsional.

Contoh kalimatnya adalah sebagai berikut:

Kalimat asli: James makan apel.

Kalimat FOL: makan(James, apel)

Kalimat FOL dapat juga diberikan kuantor dan tanda-tanda logika lain, seperti berikut:

Kalimat asli: James suka daging dan Daisy suka sayur.

Kalimat FOL: suka(James, daging) ^ suka(Daisy, sayur)

Pembuktian

Ada dua cara untuk melakukan pembuktian menggunakan FOL, yaitu backward chaining dan proof by resolution.

Untuk lebih jelasnya, langsung saja dijelaskan melalui contoh soal.

Misalkan ada kalimat-kalimat berikut:

1.       Thomas adalah seorang raja Inggris.

2.      Tina tinggal di kerajaan Inggris.

3.      Semua orang yang tinggal di kerajaan bahagia ketika raja baik.

4.      Thomas baik.

Lalu ditanyakan apakah Tina bahagia.

Pertama-tama, dibuat dulu bentuk FOL-nya, yaitu seperti berikut:

1.       Raja(Thomas, Inggris)

2.      Tinggal(Tina, Inggris)

3.      ∀X, ∃Y, ∃Z: Tinggal(X, Y) ^ Raja(Z, Y) ^ Baik(Z) -> Bahagia(X)

4.      Baik(Thomas)

1. 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.

Hasilnya adalah sebagai berikut:

2. 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.

CNF dari premis-premis tadi adalah sebagai berikut:

1.       Raja(Thomas, Inggris)

2.      Tinggal(Tina, Inggris)

3.      ~Tinggal(X1, Y1) v ~Raja(Z1, Y1) v ~Baik(Z1) v Bahagia(X1)

4.      Baik(Thomas)

5.      ~Bahagia(Tina)

Selanjutnya cara pengerjaan mirip dengan backward chaining, tetapi yang dihubungkan adalah premis dengan hasil yang berlawanan. Hasil kerjanya adalah sebagai berikut:

Propositional logic dalam menyelesaikan permasalahan dengan menggunakan fakta-fakta yang diproses menggunakan logika-logika sederhana saja. Sedangkan pada first order logic permasalahan diselesaikan dengan sentence yang merepresentasikan fakta dan term yang merepresentasikan objek. 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,...).

Komponen-komponen yang sudah dijelaskan diatas disebut sebagai ontological commitment atau hal-hal apa saja yang diketahui dan dijelaskan di dalam logic yang digunakan dalam menyelesaikan permasalahan. Selanjutnya akan ditunjukkan beberapa jenis logic lain yang memiliki ontological commitment dan epistemological commitment (kebenaran apa yang dapat dinyatakan tentang sebuah sentence). Contoh beberapa logic lain adalah sebagai berikut :

Logic

Ontologi

Epistemological

Propositiona l logic

Facts

True/false/unk nown

First-order logic

Facts, objects, relations

True/false/unk nown

Temporal logic

Facts, objects, relations, times

True/false/unk nown

Probability theory

Facts

Degree of believe 0...1

Fuzzy logic

Degree of truth

Degree of believe 0...1

Elemen-elemen dasar terkecil yang dimiliki oleh first order logic adalah sebagai berikut :

·         Constants

Dituliskan dalam huruf besar seperti A, X, NAMA. Pada simbol konstanta ini, setiap simbol harus menyatakan secara spesifik objek yang dimaksud. Tetapi, mungkin saja satu simbol mengacu pada beberapa nama berbeda. Misalnya, MOBIL bisa mengacu pada MOBIL SEDAN, MOBIL JEEP, dan sebagainya. Oleh karena itu penulisan simbol konstanta harus dilakukan secara hati-hati agar tidak terjadi kerancuan atau ambiguitas.

·         Predicates

Menyatakan relasi khusus dalam suatu model yang menghubungkan antar objek yang memiliki hubungan. Misalkan Berwarna adalah suatu predicate yang memiliki beberapa nilai. Contoh : Berwarna(Mobil, Biru), Berwarna(Mobil, Merah), dan sebagainya.

·         Functions

Menyatakan relasi yang hanya membutuhkan satu nilai. Karena setiap orang hanya memiliki satu ayah, maka Ayah merupakan suatu function. Misalkan Ayah(Boediono, Zaki).

·         Variables

Dituliskan dalam huruf kecil seperti a, x, s dan sebagainya. Variable ini menyatakan simbol yang dapat digantikan oleh konstanta apapun dan bersifat dinamis.

·         Connectives

Merupakan logika yang menghubungkan di dalam suatu kalimat kompleks seperti : ∧∨ ¬ ⇒⇔

·         Equality

Merupakan logika yang membandingkan kesamaan antara dua atau lebih kalimat yang memiliki kesamaan nilai logika. Equality disimbolkan dengan tanda =

·         Quantifiers

Terdapat dua quantifier secara umum yaitu Universal quantifier (∀) yang menyatakan sesuatu yang bersifat umumdan Existential quantifier (∃) yang menyatakan sesuatu yang berlaku sebagian saja.

B.     Sintaks First Order Logic

Tata bahasa pada first order logic meliputi :

Ø  Terms

Merupakan ekspresi logika yang mengacu pada sebuah objek. Terms bisa berupa constant, variable, atau function. Penulisan term dapat dilihat pada contoh di bawah ini :

Text Box: function(term1,....,termn)

atau

constant

atau

variable          

Ø  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. Bentuk penulisan atomic sentences adalah sebagai berikut :

Text Box: predicate(term1,....,termn)

atau

term1 = term2

Contoh penggunaan adalah sebagai berikut :

Sepatu(Budi), Saudara(Ahmad, Anton), Memberi(Andi,Budi,KueCoklat), Saudara(Andi)=Budi, dan sebagainya.

Ø  Complex sentences

Merupakan kalimat kompleks yang tersusun dari beberapa atomic sentence yang saling terhubung berdasarkan logika dengan menggunakan connective. Bentuk penulisan dari complex sentences adalah sebagai berikut :

Complex Text Box: predicate1(term1,term2) ⇒ perdicate2(term3)

Contoh penggunaan dari complex sentence adalah sebagai berikut:

o   Belajar(Andi)⇒ Pintar(Andi)

o   ¬S,S1∧S2,S1∨S2,S1⇒ S2,S1⇔  S2

o   Saudara(Ahmad,Andi)⇒ Saudara(Andi,Ahmad)

o   >(1, 2) ∨ ≤ (1, 2)

o   >(1, 2) ∧ ¬ > (1, 2)

o   Belajar(x, SC) ⇒ Mengerti(x, AI)

C.    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 :

o   Objects : elemen-elemen yang nyata ada pada permasalahan (domain elements)

o   Relations : hubungan antara elemen-elemen / objek-objek tertentu

Sebuah interpretasi mendefinisikan referent (yang dipetakan) sebagai berikut : 


o   Constant symbols        : objects

o   Predicate symbols       : relations

o   Functions symbols      : functional relations

Kalimat first order logic memiliki maksud kalimat atomik predicate(term1,...,term2) dikatakan bernilai true dalam model m di bawah unterpretasi i jika dan hanya jika object yang di-refer (term1, ... , term2) di bawah i terhubung oleh relation yang di refer oleh predicate dalam m.

Ilustrasi pada gambar diatas menggambarkan komponen-komponen yang ada pada first order logic. Pada ilustrasi digambarkan bahwa terdapat orang dan raja. Hubungan keduanya adalah sebagai saudara satu dengan lainnya. Dari gambar tersebut dapat dilihat masing-masing komponen adalah sebagai berikut :

·      Object

Ilustrasi menggambarkan ada seorang raja dan orang biasa, dapat kita ambil contoh objek yang ada adalah orang, raja, kaki raja dan kaki orang. Objek memiliki identitas tertentu yang nantinya akan melalui proses logika.

·      Function

function merupakan hubungan yang hanya membutuhkan satu nilai untuk satu objek, contoh pada ilustrasi adalah kaki digunakan oleh orang untuk berjalan.

·      Relation

menyatakan hubungan antar objek yang memiliki relasi tertentu, pada gambar ilustrasi terdapat relasi saudara antara orang dan raja.

2.4 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)∧

Hal-hal yang harus dihindari pada penggunaan Quantifier Universal adalah penggunaan logika ∧ pada kalimat utama karena akan menimbulkan pengertian yang ambigu.

·      Existential quantifiers

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).

Hal-hal yang harus dihindari pada penggunaan Quantifier Universal adalah penggunaan logika⇒pada kalimat utama karena akan menimbulkan pengertian yang ambigu.

2.5Equality

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. Contoh bentuk dari equality adalah sebagai berikut :

Equality

x,ySaudara(x,y) ⇔  [¬ (x = y) ∧ m,f ¬ (m = f) ∧ OrangTua(m,x) ∧ OrangTua(f,x)  ∧ OrangTua (m,y) ∧ OrangTua (f,y)]

2.6 Inferensi pada First Order Logic

Proses Inferensi pada First Order Logic menggunakan 7 aturan inferensi yang digunakan pada Propositional Logic, dengan ditambah aturan yang lebih kompleks sehubungan dengan quantifiers, sebagai berikut :

1. Inference Rules Involving Quantifiers

SUBST(Ѳ,α): untuk menotasikan hasil dari pengaplikasian operasi subsitusi Ѳ terhadap sentence α.

SUBST({x/Andi, y/Budi}, Saudara(x,y)) = Saudara(Andi, Budi).

2. UniversalElimination:

Untuk setiap sentence α,variable v,dan ground erm(term yang tidak berisi variabel) g :

Dari ∀x Suka(x, Membaca), dapat digunakan substitusi {x/Andi} dan melakukan inferensi bahwa Suka(Andi, Membaca)

3. Existential Elimination:

untuk setiap sentence , variabel v, dan simbol konstanta k yang tidak tampak dimanapun di dalam basis pengetahuan:

Dari x Membunuh(x, Korban), kita dapat menyimpulkan Membunuh{Penjahat, Korban}, selama Penjahat tidak tidak tampak dimanapun di dalam basis pengetahuan.

1.    Existential Introduction:

untuk setiap sentence , variabel v yang tidak terjadi pada , dan ground term g yang terjadi pada :

Dari Suka(Budi, Membaca) kita dapat menyimpulkan xSuka(x, Membaca).

6.1          Percobaan/ Review / Contoh Kode Program (Jika memang ada)

terdapat pernyataan-pernyataan sebagai berikut :

-          Andi adalah seorang mahasiswa

-          Andi masuk Jurusan elektro

-          Setiap mahasiswa elektro pasti mahasiswa Teknik

-          Kalkulus adalah matakuliah yang sulit

-          Setiap mahasiswa Teknik pasti akan suka kalkulus atau akan membencinya

-          Setiap mahasiswa pasti akan suka terhadap suatu matakuliah

-          Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka terhadap matakuliah tersebut.

-          Andi tidak pernah hadir kuliah matakuliah kalkulus

• Kedelapan pernyataan di atas dapat dibawa ke bentuk logika predikat :

a.    mahasiswa(Andi)

b.    Elektro(Andi)

c.    ∀x: Elektro(x) ->Teknik(x)

d.    sulit(Kalkulus)

e.    ∀x: Teknik(x) -> suka(x, Kalkulus) ∨benci(x, Kalkulus)

f.     ∀x:∃y : suka(x,y)

g.    ∀x: ∀y: mahasiswa(x) ∧sulit(y) ∧~hadir(x,y) ->~suka(x,y)

h.    ~hadir(Andi, Kalkulus)

• Kemudian dibuat dalam bentuk klausa :

1.    mahasiswa(Andi)

2.    Elektro(Andi)

3.    ~Elektro(x1) ∨ Teknik(x1)

4.    sulit(Kalkulus)

5.    ~Teknik(x2) ∨suka(x2, Kalkulus) ∨benci(x2, Kalkulus)

6.    suka(x3,f1(x3))

7.     ~mahasiswa(x4) ∨~sulit(y1) ∨hadir(x4,y1) ∨~suka(x4,y1)

8.    ~hadir(Andi,Kalkulus)

• Akan dibuktikan apakah “Andi benci kalkulus” atau dapat ditulis benci(Andi,Kalkulus) ­

Penggunaan logika orde pertama

1.      Assertions and queries in first-order logic

2.      The kinship domain

3.      Numbers, sets, and lists

Penggunaan logika orde pertama

1.      Assertions and queries in first-order logic

2.      The kinship domain

3.      Numbers, sets, and lists

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.

Logika proposisi vs. Inferensi Logika Orde Pertama

        Bagian ini dan selanjutnya mengenalkan ide-ide yang mendasari sistem inferensi logis modern.

Kita mulai dengan beberapa aturan inferensi sederhana yang bisa diterapkan pada kalimat dengan

quantifiers untuk mendapatkan kalimat tanpa tanda pengenal. Aturan ini secara alami mengarah

pada gagasan bahwa pesanan pertama Kesimpulan dapat dilakukan dengan mengubah basis

pengetahuan menjadi logika dan penggunaan proposisional Inferensi proposisional,

yang sudah kita ketahui bagaimana melakukannya.Bagian selanjutnya menunjukkan sebuah

 jalan pintas yang jelas, mengarah ke metode inferensi yang memanipulasi kalimat orde pertama

secara langsung.

Unifikasi dan Lifting

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)

First-order logic itu salah satu jenis sistem formal, yang digunakan untuk membuktikan kebenaran dari sebuah pernyataan.

Dalam first-order logic, setiap pernyataan dianggap memiliki predikat. Predikat itu dapat menghubungkan pernyataan yang satu dengan yang lain.

Kalimat-kalimat dalam first-order-logic dibuat dengan format P( X,  Y). P adalah predikat dan X adalah subjek. Y adalah objek, yang merupakan variabel yang opsional.

Contoh kalimatnya adalah sebagai berikut:

Kalimat asli: James makan apel.

Kalimat FOL: makan(James, apel)

Kalimat FOL dapat juga diberikan kuantor dan tanda-tanda logika lain, seperti berikut:

Kalimat asli: James suka daging dan Daisy suka sayur.

Kalimat FOL: suka(James, daging) ^ suka(Daisy, sayur)

Pembuktian

Ada dua cara untuk melakukan pembuktian menggunakan FOL, yaitu backward chaining dan proof by resolution.

Untuk lebih jelasnya, langsung saja dijelaskan melalui contoh soal.

Misalkan ada kalimat-kalimat berikut:

1.       Thomas adalah seorang raja Inggris.

2.      Tina tinggal di kerajaan Inggris.

3.      Semua orang yang tinggal di kerajaan bahagia ketika raja baik.

4.      Thomas baik.

Lalu ditanyakan apakah Tina bahagia.

Pertama-tama, dibuat dulu bentuk FOL-nya, yaitu seperti berikut:

1.       Raja(Thomas, Inggris)

2.      Tinggal(Tina, Inggris)

3.      ∀X, ∃Y, ∃Z: Tinggal(X, Y) ^ Raja(Z, Y) ^ Baik(Z) -> Bahagia(X)

4.      Baik(Thomas)

1. 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.

Hasilnya adalah sebagai berikut:

2. 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.

CNF dari premis-premis tadi adalah sebagai berikut:

1.       Raja(Thomas, Inggris)

2.      Tinggal(Tina, Inggris)

3.      ~Tinggal(X1, Y1) v ~Raja(Z1, Y1) v ~Baik(Z1) v Bahagia(X1)

4.      Baik(Thomas)

5.      ~Bahagia(Tina)

Selanjutnya cara pengerjaan mirip dengan backward chaining, tetapi yang dihubungkan adalah premis dengan hasil yang berlawanan. Hasil kerjanya adalah sebagai berikut:

Propositional logic dalam menyelesaikan permasalahan dengan menggunakan fakta-fakta yang diproses menggunakan logika-logika sederhana saja. Sedangkan pada first order logic permasalahan diselesaikan dengan sentence yang merepresentasikan fakta dan term yang merepresentasikan objek. 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,...).

Komponen-komponen yang sudah dijelaskan diatas disebut sebagai ontological commitment atau hal-hal apa saja yang diketahui dan dijelaskan di dalam logic yang digunakan dalam menyelesaikan permasalahan. Selanjutnya akan ditunjukkan beberapa jenis logic lain yang memiliki ontological commitment dan epistemological commitment (kebenaran apa yang dapat dinyatakan tentang sebuah sentence). Contoh beberapa logic lain adalah sebagai berikut :

Logic

Ontologi

Epistemological

Propositiona l logic

Facts

True/false/unk nown

First-order logic

Facts, objects, relations

True/false/unk nown

Temporal logic

Facts, objects, relations, times

True/false/unk nown

Probability theory

Facts

Degree of believe 0...1

Fuzzy logic

Degree of truth

Degree of believe 0...1

Elemen-elemen dasar terkecil yang dimiliki oleh first order logic adalah sebagai berikut :

·         Constants

Dituliskan dalam huruf besar seperti A, X, NAMA. Pada simbol konstanta ini, setiap simbol harus menyatakan secara spesifik objek yang dimaksud. Tetapi, mungkin saja satu simbol mengacu pada beberapa nama berbeda. Misalnya, MOBIL bisa mengacu pada MOBIL SEDAN, MOBIL JEEP, dan sebagainya. Oleh karena itu penulisan simbol konstanta harus dilakukan secara hati-hati agar tidak terjadi kerancuan atau ambiguitas.

·         Predicates

Menyatakan relasi khusus dalam suatu model yang menghubungkan antar objek yang memiliki hubungan. Misalkan Berwarna adalah suatu predicate yang memiliki beberapa nilai. Contoh : Berwarna(Mobil, Biru), Berwarna(Mobil, Merah), dan sebagainya.

·         Functions

Menyatakan relasi yang hanya membutuhkan satu nilai. Karena setiap orang hanya memiliki satu ayah, maka Ayah merupakan suatu function. Misalkan Ayah(Boediono, Zaki).

·         Variables

Dituliskan dalam huruf kecil seperti a, x, s dan sebagainya. Variable ini menyatakan simbol yang dapat digantikan oleh konstanta apapun dan bersifat dinamis.

·         Connectives

Merupakan logika yang menghubungkan di dalam suatu kalimat kompleks seperti : ∧∨ ¬ ⇒⇔

·         Equality

Merupakan logika yang membandingkan kesamaan antara dua atau lebih kalimat yang memiliki kesamaan nilai logika. Equality disimbolkan dengan tanda =

·         Quantifiers

Terdapat dua quantifier secara umum yaitu Universal quantifier (∀) yang menyatakan sesuatu yang bersifat umumdan Existential quantifier (∃) yang menyatakan sesuatu yang berlaku sebagian saja.

B.     Sintaks First Order Logic

Tata bahasa pada first order logic meliputi :

Ø  Terms

Merupakan ekspresi logika yang mengacu pada sebuah objek. Terms bisa berupa constant, variable, atau function. Penulisan term dapat dilihat pada contoh di bawah ini :

Text Box: function(term1,....,termn)

atau

constant

atau

variable          

Ø  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. Bentuk penulisan atomic sentences adalah sebagai berikut :

Text Box: predicate(term1,....,termn)

atau

term1 = term2

Contoh penggunaan adalah sebagai berikut :

Sepatu(Budi), Saudara(Ahmad, Anton), Memberi(Andi,Budi,KueCoklat), Saudara(Andi)=Budi, dan sebagainya.

Ø  Complex sentences

Merupakan kalimat kompleks yang tersusun dari beberapa atomic sentence yang saling terhubung berdasarkan logika dengan menggunakan connective. Bentuk penulisan dari complex sentences adalah sebagai berikut :

Complex Text Box: predicate1(term1,term2) ⇒ perdicate2(term3)

Contoh penggunaan dari complex sentence adalah sebagai berikut:

o   Belajar(Andi)⇒ Pintar(Andi)

o   ¬S,S1∧S2,S1∨S2,S1⇒ S2,S1⇔  S2

o   Saudara(Ahmad,Andi)⇒ Saudara(Andi,Ahmad)

o   >(1, 2) ∨ ≤ (1, 2)

o   >(1, 2) ∧ ¬ > (1, 2)

o   Belajar(x, SC) ⇒ Mengerti(x, AI)

C.    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 :

o   Objects : elemen-elemen yang nyata ada pada permasalahan (domain elements)

o   Relations : hubungan antara elemen-elemen / objek-objek tertentu

Sebuah interpretasi mendefinisikan referent (yang dipetakan) sebagai berikut : 


o   Constant symbols        : objects

o   Predicate symbols       : relations

o   Functions symbols      : functional relations

Kalimat first order logic memiliki maksud kalimat atomik predicate(term1,...,term2) dikatakan bernilai true dalam model m di bawah unterpretasi i jika dan hanya jika object yang di-refer (term1, ... , term2) di bawah i terhubung oleh relation yang di refer oleh predicate dalam m.

Ilustrasi pada gambar diatas menggambarkan komponen-komponen yang ada pada first order logic. Pada ilustrasi digambarkan bahwa terdapat orang dan raja. Hubungan keduanya adalah sebagai saudara satu dengan lainnya. Dari gambar tersebut dapat dilihat masing-masing komponen adalah sebagai berikut :

·      Object

Ilustrasi menggambarkan ada seorang raja dan orang biasa, dapat kita ambil contoh objek yang ada adalah orang, raja, kaki raja dan kaki orang. Objek memiliki identitas tertentu yang nantinya akan melalui proses logika.

·      Function

function merupakan hubungan yang hanya membutuhkan satu nilai untuk satu objek, contoh pada ilustrasi adalah kaki digunakan oleh orang untuk berjalan.

·      Relation

menyatakan hubungan antar objek yang memiliki relasi tertentu, pada gambar ilustrasi terdapat relasi saudara antara orang dan raja.

2.4 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)∧

Hal-hal yang harus dihindari pada penggunaan Quantifier Universal adalah penggunaan logika ∧ pada kalimat utama karena akan menimbulkan pengertian yang ambigu.

·      Existential quantifiers

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).

Hal-hal yang harus dihindari pada penggunaan Quantifier Universal adalah penggunaan logika⇒pada kalimat utama karena akan menimbulkan pengertian yang ambigu.

2.5Equality

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. Contoh bentuk dari equality adalah sebagai berikut :

Equality

x,ySaudara(x,y) ⇔  [¬ (x = y) ∧ m,f ¬ (m = f) ∧ OrangTua(m,x) ∧ OrangTua(f,x)  ∧ OrangTua (m,y) ∧ OrangTua (f,y)]

2.6 Inferensi pada First Order Logic

Proses Inferensi pada First Order Logic menggunakan 7 aturan inferensi yang digunakan pada Propositional Logic, dengan ditambah aturan yang lebih kompleks sehubungan dengan quantifiers, sebagai berikut :

1. Inference Rules Involving Quantifiers

SUBST(Ѳ,α): untuk menotasikan hasil dari pengaplikasian operasi subsitusi Ѳ terhadap sentence α.

SUBST({x/Andi, y/Budi}, Saudara(x,y)) = Saudara(Andi, Budi).

2. UniversalElimination:

Untuk setiap sentence α,variable v,dan ground erm(term yang tidak berisi variabel) g :

Dari ∀x Suka(x, Membaca), dapat digunakan substitusi {x/Andi} dan melakukan inferensi bahwa Suka(Andi, Membaca)

3. Existential Elimination:

untuk setiap sentence , variabel v, dan simbol konstanta k yang tidak tampak dimanapun di dalam basis pengetahuan:

Dari x Membunuh(x, Korban), kita dapat menyimpulkan Membunuh{Penjahat, Korban}, selama Penjahat tidak tidak tampak dimanapun di dalam basis pengetahuan.

1.    Existential Introduction:

untuk setiap sentence , variabel v yang tidak terjadi pada , dan ground term g yang terjadi pada :

Dari Suka(Budi, Membaca) kita dapat menyimpulkan xSuka(x, Membaca).

6.1          Percobaan/ Review / Contoh Kode Program (Jika memang ada)

terdapat pernyataan-pernyataan sebagai berikut :

-          Andi adalah seorang mahasiswa

-          Andi masuk Jurusan elektro

-          Setiap mahasiswa elektro pasti mahasiswa Teknik

-          Kalkulus adalah matakuliah yang sulit

-          Setiap mahasiswa Teknik pasti akan suka kalkulus atau akan membencinya

-          Setiap mahasiswa pasti akan suka terhadap suatu matakuliah

-          Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka terhadap matakuliah tersebut.

-          Andi tidak pernah hadir kuliah matakuliah kalkulus

• Kedelapan pernyataan di atas dapat dibawa ke bentuk logika predikat :

a.    mahasiswa(Andi)

b.    Elektro(Andi)

c.    ∀x: Elektro(x) ->Teknik(x)

d.    sulit(Kalkulus)

e.    ∀x: Teknik(x) -> suka(x, Kalkulus) ∨benci(x, Kalkulus)

f.     ∀x:∃y : suka(x,y)

g.    ∀x: ∀y: mahasiswa(x) ∧sulit(y) ∧~hadir(x,y) ->~suka(x,y)

h.    ~hadir(Andi, Kalkulus)

• Kemudian dibuat dalam bentuk klausa :

1.    mahasiswa(Andi)

2.    Elektro(Andi)

3.    ~Elektro(x1) ∨ Teknik(x1)

4.    sulit(Kalkulus)

5.    ~Teknik(x2) ∨suka(x2, Kalkulus) ∨benci(x2, Kalkulus)

6.    suka(x3,f1(x3))

7.     ~mahasiswa(x4) ∨~sulit(y1) ∨hadir(x4,y1) ∨~suka(x4,y1)

8.    ~hadir(Andi,Kalkulus)

• Akan dibuktikan apakah “Andi benci kalkulus” atau dapat ditulis benci(Andi,Kalkulus) ­

Penggunaan logika orde pertama

1.      Assertions and queries in first-order logic

2.      The kinship domain

3.      Numbers, sets, and lists

Penggunaan logika orde pertama

1.      Assertions and queries in first-order logic

2.      The kinship domain

3.      Numbers, sets, and lists

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.

Logika proposisi vs. Inferensi Logika Orde Pertama

        Bagian ini dan selanjutnya mengenalkan ide-ide yang mendasari sistem inferensi logis modern.

Kita mulai dengan beberapa aturan inferensi sederhana yang bisa diterapkan pada kalimat dengan

quantifiers untuk mendapatkan kalimat tanpa tanda pengenal. Aturan ini secara alami mengarah

pada gagasan bahwa pesanan pertama Kesimpulan dapat dilakukan dengan mengubah basis

pengetahuan menjadi logika dan penggunaan proposisional Inferensi proposisional,

yang sudah kita ketahui bagaimana melakukannya.Bagian selanjutnya menunjukkan sebuah

 jalan pintas yang jelas, mengarah ke metode inferensi yang memanipulasi kalimat orde pertama

secara langsung.

Unifikasi dan Lifting

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)

Referensi :

Ebook Artifical Intelligence A Modern Approach(3rd Edition)

Download:

http://web.cecs.pdx.edu/~mperkows/CLASS_479/2017_ZZ_00/02__GOOD_Russel=Norvig=Artificial%20Intelligence%20A%20Modern%20Approach%20(3rd%20Edition).pdf

http://imamcs.lecture.ub.ac.id/tag/logika-order-pertama-first-order-logic/

http://dinus.ac.id/repository/docs/ajar/slide_8_log_inf.pptx

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

http://www.binus.ac.id

Ebook Artifical Intelligence A Modern Approach(3rd Edition)

Download:

http://web.cecs.pdx.edu/~mperkows/CLASS_479/2017_ZZ_00/02__GOOD_Russel=Norvig=Artificial%20Intelligence%20A%20Modern%20Approach%20(3rd%20Edition).pdf

http://imamcs.lecture.ub.ac.id/tag/logika-order-pertama-first-order-logic/

http://dinus.ac.id/repository/docs/ajar/slide_8_log_inf.pptx

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

http://www.binus.ac.id