LOGIKA FIRST ORDER

First order logic adalah sebuah bahasa formal yang digunakan di ilmu matematika, philosophy, bahasa dan ilmu computer. Disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form). 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 problem of multiple generality (masalah dalam berbagai keadaan umum) yang telah membingungkan sebagian besar ahli-ahli logika abad pertengahan. Dengan menggunakan logika predikat ini, untuk pertama kalinya, para ahli-ahli logika bisa memberikan quantifier yang cukup umum untuk merepresentasikan semua argumen yang terdapat pada natural language.

Sintak dan semantik logika orde pertama

Syntax pada FOL: Elemen dasar

•Constants KingJohn, 2, NUS,...

•Predicates Brother, >,...

•Functions Sqrt, LeftLegOf,...

•Variables x, y, a, b,...

•Connectives , , , , 

•Equality =

•Quantifiers , 

Kamliat Atom

Atomic sentence = predicate (term1,...,termn) or term1 = term2

Term = function (term1,...,termn) or constant or variable

•Misal: Brother(KingJohn,RichardTheLionheart) > (Length(LeftLegOf(Richard)),                                 Length(LeftLegOf(KingJohn)))

12/10/2012

6

First-

 Kalimat Komplek

•Kalimat komplek dibuat dari kalimat atommenggunakan konektivitas

S, S1  S2, S1  S2, S1  S2, S1  S2,

Misal: Sibling(KingJohn,Richard)  Sibling(Richard,KingJohn)

>(1,2)  ≤ (1,2)

>(1,2)   >(1,2)

UniversalQuantifier

Definisi: Jika Asuatu ekspresi logika dan x adalah variable, maka jika ingin menentukanbahwa A adalah bernilai benar untuk semua nilai yang dimungkinkan untuk x,maka akan ditulis. Disini  disebut kuantoruniversal, dengan A adalah scope dari kuantor tersebut. Variabel xdisebut terikat (bound) dengan kuantor.

Simbol UniversalQuantifier menggantikan kata ‘untuksemua’, ‘untuk seluruh’.Dan digunakan pada pembentukan formula dengan bentuk:

                  (x)  P(x)

(x)  P(x) bernilai benar apabila predikat P(x)bernilai benar. Formula tersebut dapat dibaca sebagai ‘Seluruh x untuk P(x)’ atau ‘Setiap x untuk P(x)’

Contoh:

“Semua Gajah mempunyai belalai”Jika G adalah gajahdan B adalah belalai maka ditulis dalam kuantor universal menjadi , dibaca “Jika x adalah Gajah maka, x mempunyai belalai”.Belum bisa dibuktikan secara predikat karena jumlah gajah bisa banyak bisa sajacuma satu, maka diperluas menjadi , dibaca “Untuk semua x, jika x seekor gajah, maka xmempunyai belalai”.

“Semua mahasiswa harus rajin belajar”Langkah1: Cari lingkupatau scope dari kuantor universal, pada argument diatas menjadi “Jika x adalahmahasiswa, maka x harus rajin belajar” ditulis menjadi .

Langkah2: Beri kuantoruniversal didepannya, dari hasil yang didapat pada langkah pertama menjadi

Langkah3: Ubah menjadisuatu fungsi, menjadi

ExistentialQuantifier

Definisi: Jika Asuatu ekspresi logika dan x adalah variable, maka jika ingin menentukanbahwa A adalah bernilai benar untuk sekurang-kurangnya satu dari x,maka akan ditulis . Disini  disebut kuantoreksistensial, dengan A adalah scope dari kuantor tersebut. Variabel xdisebut terikat (bound) dengan kuantor.

Simbol ExistentialQuantifier  menggantikan kata ‘ada’, ‘beberapa’, ‘tidaksemua’, ‘terdapat’.Dan digunakan pada pembentukan formula dengan bentuk:

                  (x)  P(x)

(x)  P(x) bernilai benar apabila ada x yang menyebabkan P(x)bernilai benar. Formula tersebut dapat dibaca sebagai ‘Ada x untuk P(x)’

Contoh:

“Ada bilangan prima yang genap”Jika P adalah bilangan‘prima’ dan G adalah ‘genap’, argumen tersebut dapat dibaca “Ada x, yang xadalah bilangan prima dan x adalah genap”, sehingga disimbolkan menjadi .

“Ada pelajar memperoleh beasiswa prestasi”Langkah1: Cari lingkupatau scope dari kuantor eksistensial, pada argument diatas menjadi “Ada x, yang x adalahpelajar, dan x memperoleh beasiswa prestasi”, sehingga ditulis menjadi

Langkah2: Berilahkuantor eksistensial  di dari hasil yangdidapat pada langkah pertama menjadi  

Langkah3: ubah menjadisuatu fungsi, menjadi

6.3            Transformasi Pernyataan Kedalam FormulaFirst-Order

Langkah-langkahmen-transformasi penyataan kedalam formula First-Order adalah sebagai berikut:

1.      Buat penafsiran mengenaipernyataan tersebut

2.      Tentukan dan deklarasikanpredikat-predikat yang digunakan

3.      Tentukan quantifier yangdiperlukan

Hal yang perludiperhatikan adalah penafsiran atau cara pandang kita dalam menafsirkanpernyataan tersebut. Penafsiran yang berbeda akan menghasilkan  formula yang berbeda. Kadang dalammentransformasikan sebuah pernyataan kedalam formula first-order diperlukanquantifier lebih dari satu.

Contoh:

1.      Tentukan nilai dari Plus(Plus(3,2), Plus (2,1)).

Jawab:

PLUS (PLUS (3,2), PLUS (2,1))       

= PLUS (5, PLUS (2,1))

                                    =PLUS (5,3)

                                    =8

2.      Tuliskan pernyataan berikutkedalam bentuk formula

a.   Setiap bilangan Rasional adalahbilangan Real

b.   Ada bilangan yang merupakan bilangan prima

c.   Untuk setiap bilangan x, ada bilangan y dimana x < y

Jawab:

Langkahpertama definisikan dulu predikat-predikat

P(x)                  : x adalah bilangan prima

Q(x)                 : x adalah bilangan rasional

R(x)                 : x adalah bilangan real

KECIL(x)        :x lebih kecil dari y

a.       (x)  (Q(x)  R(x))

b.      (x)  P(x)

c.       (x) (y) KECIL (x,y)

3.      Ubahlah pernyataan “Tidak ada orang tua menginginkan anaknyajadi penjahat” kedalam bentuk formula first-order.

Jawab:

Kalimattersebut ekuivalen dengan:

“Jika x adalah orang tua, maka x tidakingin anaknya jadi penjahat”

Predikatyang digunakan:

P(x) : xadalah orang tua

Q(x) :xingin anaknya jadi penjahat (gunakan operator Negasi)

FormulaFirst-Order:  (x) (P(x) Q(x))

4.      Tuliskan dalam bentuk formulapernyataan berikut “x lebih besar dari y”

Jawab:

Interpretasi ke-1:Jika ditafsirkan bahwa “untuk setiap xada y yang lebih kecil” maka kita bisa menyatakan x > y, makaPredikatnya: BESAR(x,y) maka formulanya menjadi: (x) ((y) BESAR(x,y)

Interpretasi ke-2: Jikaditafsirkan “untuk sembarang x dan y,jika x lebih besar dari y, maka tidak benar pernyataan y lebih besar dari x”maka formulanya menjadi: (x) (y) (BESAR(x,y)  BESAR(y,x))

6.4            Pembuktian pada Logika First-Order

Pembuktian LogikaFirst-Order hampir sama dengan pembuktan pada Logika Proposisi. Hanya saja padaLogika First-Order pembuktian menggunakan Aturan Inferensi lebih mungkin untukdilakukan.

Contoh:

Buktikan bahwa “Setiap manusia pasti mati. Sayuti adalahmanusia, Karenanya Sayuti  pasti mati.”

Jawab:

Misal dideklarasikanpredikat berikut:

MAN(x)           :x adalah manusia

MORTAL(x)    :x pasti mati

Maka pernyataan padasoal menjadi:

P1                    :(x) (MAN(x) MORTAL(x))

P2                    :MAN(Sayuti)

Untuk membuktikanbahwa kesimpulan “Sayuti pasti mati”harus dibuktian bahwa MORTAL(Sayuti) adalah konsekuensi logis dari P1dan P2. Maka;

Dilakukan pembuktianlangsung:

P1P2            : (x) (MAN(x) MORTAL(x)) MAN(Sayuti)

Karena              (MAN(x)  MORTAL(x))bernilai Benar untuk semua x maka;

  (MAN(Sayuti)  MORTAL(Sayuti))juga Benar

    (x) (MAN(x)MORTAL(x))

     MAN(Sayuti)

(MAN(Sayuti)MORTAL(Sayuti))

MORTAL(Sayuti)

Premis P1

Premis P2

Langkah 1 dan 2

P1: x Sayuti

Persoalan Logika First-Order dalam AI

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)

ARGUMEN PADA LOGIKA PREDIKAT

Validitas sebuah argumen dapat dibuktikan dengan contoh yang mirip dengan contoh 1. 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. Perhatikan pernyataan-pernyataan pada contoh argumen berikut:

Contoh 4:

1.       Jika Badu seorang mahasiswa, maka ia pasti pandai

2.       Dewi seorang mahasiswa

3.       Dengan demikian, ia pasti pandai