Logika Predikat (Kalkulus Predikat)

Logika Predikat (Kalkulus Predikat) Kuliah (Pengantar) Metode Formal Semester Ganjil 2015-2016

M. Arzaki Fakultas Informatika Telkom University FIF Tel-U

November 2015

MZI (FIF Tel-U)

Logika Predikat (Kalkulus Predikat)

November 2015

1 / 46

Acknowledgements

Slide ini disusun berdasarkan materi yang terdapat pada sumber-sumber berikut: Buku: 1

Logic in Computer Science: Modelling and Reasoning about Systems, Edisi 2, 2004, oleh M. Huth dan M. Ryan (acuan utama).

2

Mathematical Logic for Computer Science, Edisi 2, 2000, oleh M. Ben-Ari. The Essence of Logic, 1997, oleh J. Kelly.

3 4

Discrete Mathematics and Its Applications, Edisi 7, 2012, oleh K. H. Rosen.

MZI (FIF Tel-U)


November 2015

2 / 46

Slide kuliah: 1

Slide kuliah Metode Formal dan Topik dalam Logika Komputasional di Fasilkom UI oleh B. H. Widjaja.

2

Slide kuliah Metode Formal di University of Bozen-Bolzano oleh Enrico Franconi.

3

Slide kuliah Metode Formal dari Veri…ed Software Systems.

4

Slide kuliah Computational Logic di TU Dresden.

Beberapa gambar dapat diambil dari sumber-sumber di atas. Slide ini ditujukan untuk keperluan akademis di lingkungan FIF Telkom University. Jika Anda memiliki saran/ pendapat/ pertanyaan terkait materi dalam slide ini, silakan kirim email ke @telkomuniversity.ac.id.

MZI (FIF Tel-U)


November 2015

3 / 46

Bahasan

1

Sintaks Logika Predikat

2

Semantik Logika Predikat

3

Bentuk Normal Prenex (Prenex Normal Form, PNF)

4

Ketakterputusan (Undecidability) dari Logika Predikat

5

Batas Keekspresifan (Expressiveness) dari Logika Predikat

MZI (FIF Tel-U)


November 2015

4 / 46

Bahasan

1


2


3


4


5


MZI (FIF Tel-U)


November 2015

5 / 46

Term pada Logika Predikat Formula logika predikat dibangun dari term yang dide…nisikan sebagai berikut.

Term 1

Setiap variabel adalah term. Variabel biasanya ditulis dengan huruf u; v; w; x; y; z, u1 ; u2 ; : : :, v1 ; v2 ; : : :, w1 ; w2 ; : : :, x1 ; x2 ; : : :, y1 ; y2 ; : : :, z1 ; z2 ; : : :.

2

Setiap konstanta pada domain (atau semesta pembicaraan) adalah term. Konstanta biasanya ditulis dengan huruf a; b; c, a1 ; a2 ; : : :, b1 ; b2 ; : : :, c1 ; c2 ; : : :, atau secara kongkrit. Contohnya konstanta dapat ditulis dengan bilangan 0; 1; 2 (jika domain adalah himpunan bilangan), dengan nama manusia seperti Alex, Bob, atau Charlie (jika domain adalah himpunan manusia), atau yang lainnya.

3

Jika t1 ; t2 ; : : : ; tn adalah term dan f adalah fungsi dengan ariti n 1, maka f (t1 ; t2 ; : : : ; tn ) juga merupakan term. Dalam hal ini f dapat dipadang sebagai fungsi n variabel yang hasilnya adalah sebuah term.

MZI (FIF Tel-U)


November 2015

6 / 46

Subterm Subterm 1

Sebuah term t adalah subterm dari t itu sendiri.

2

Jika s dan t adalah dua term yang dipakai untuk membangun term u yang lebih kompleks, maka s dan t dikatakan subterm sejati (atau subterm murni) dari term u.

3

Subterm bersifat transitif: jika s subterm dari t dan t subterm dari u, maka s subterm dari u.

Contoh Misalkan 1 dan 2 adalah konstanta, x adalah variabel, f adalah fungsi uner, serta + dan adalah fungsi biner. Misalkan t adalah term 1 + (2 f (x)), maka subterm dari t adalah (1)

MZI (FIF Tel-U)


November 2015

7 / 46

Subterm Subterm 1


2


3


Contoh Misalkan 1 dan 2 adalah konstanta, x adalah variabel, f adalah fungsi uner, serta + dan adalah fungsi biner. Misalkan t adalah term 1 + (2 f (x)), maka subterm dari t adalah (1) 1 + (2 f (x)),

MZI (FIF Tel-U)


November 2015

7 / 46

Subterm Subterm 1


2


3


Contoh Misalkan 1 dan 2 adalah konstanta, x adalah variabel, f adalah fungsi uner, serta + dan adalah fungsi biner. Misalkan t adalah term 1 + (2 f (x)), maka subterm dari t adalah (1) 1 + (2 f (x)), (2) 2 f (x),

MZI (FIF Tel-U)


November 2015

7 / 46

Subterm Subterm 1


2


3


Contoh Misalkan 1 dan 2 adalah konstanta, x adalah variabel, f adalah fungsi uner, serta + dan adalah fungsi biner. Misalkan t adalah term 1 + (2 f (x)), maka subterm dari t adalah (1) 1 + (2 f (x)), (2) 2 f (x), (3) f (x),

MZI (FIF Tel-U)


November 2015

7 / 46

Subterm Subterm 1


2


3


Contoh Misalkan 1 dan 2 adalah konstanta, x adalah variabel, f adalah fungsi uner, serta + dan adalah fungsi biner. Misalkan t adalah term 1 + (2 f (x)), maka subterm dari t adalah (1) 1 + (2 f (x)), (2) 2 f (x), (3) f (x), (4) 1,

MZI (FIF Tel-U)


November 2015

7 / 46

Subterm Subterm 1


2


3


Contoh Misalkan 1 dan 2 adalah konstanta, x adalah variabel, f adalah fungsi uner, serta + dan adalah fungsi biner. Misalkan t adalah term 1 + (2 f (x)), maka subterm dari t adalah (1) 1 + (2 f (x)), (2) 2 f (x), (3) f (x), (4) 1, (5) 2, dan (6)

MZI (FIF Tel-U)


November 2015

7 / 46

Subterm Subterm 1


2


3


Contoh Misalkan 1 dan 2 adalah konstanta, x adalah variabel, f adalah fungsi uner, serta + dan adalah fungsi biner. Misalkan t adalah term 1 + (2 f (x)), maka subterm dari t adalah (1) 1 + (2 f (x)), (2) 2 f (x), (3) f (x), (4) 1, (5) 2, dan (6) x.

MZI (FIF Tel-U)


November 2015

7 / 46

Pohon Urai (Parse Tree) untuk Term Pohon urai (parse tree) dapat digunakan untuk menggambarkan struktur suatu term dalam logika predikat. Sebagai contoh, jika 2 adalah konstanta, x dan y adalah variabel, s adalah fungsi uner, serta , +, adalah fungsi biner, maka pohon urai untuk term (2 (s (x) + y)) x adalah

Pohon Urai (Parse Tree) untuk Term Pohon urai (parse tree) dapat digunakan untuk menggambarkan struktur suatu term dalam logika predikat. Sebagai contoh, jika 2 adalah konstanta, x dan y adalah variabel, s adalah fungsi uner, serta , +, adalah fungsi biner, maka pohon urai untuk term (2 (s (x) + y)) x adalah

Formula Logika Predikat Formula Logika Predikat Formula (atau kalimat) logika predikat dibentuk dari: 1

konstanta proposisi: T (benar) atau F (salah)

2

ekspresi P (t1 ; t2 ; : : : ; tn ) dengan t1 ; t2 ; : : : ; tn adalah term dan P adalah predikat n ari dengan n 1

3

operator logika proposisi: :; ^; _; ; !; $

dengan aturan sebagai berikut: 1

2

3

setiap ekspresi P (t1 ; t2 ; : : : ; tn ) yang terde…nisi dengan baik adalah formula logika predikat, apabila dan adalah dua formula logika predikat, maka : , ^ , _ , , ! , $ , masing-masing juga merupakan formula logika predikat, apabila adalah formula logika predikat dan x adalah variabel, maka 8x maupun 9x keduanya adalah formula logika predikat. MZI (FIF Tel-U)


November 2015

9 / 46

Subformula Subformula 1

Sebuah formula

2

Jika dan adalah dua formula logika predikat yang dipakai untuk membangun formula yang lebih kompleks, maka dan dikatakan subformula sejati (atau subformula murni) dari .

adalah subformula dari

itu sendiri.

3

Subformula bersifat transitif: jika , maka subformula dari .

subformula dari

dan

subformula dari

Contoh Misalkan adalah formula 8x9y (P (x) ^ Q (y; z) ! R (x; z)), maka subformula dari adalah (1)

MZI (FIF Tel-U)


November 2015

10 / 46


Sebuah formula

2



itu sendiri.

3


subformula dari

dan

subformula dari

Contoh Misalkan adalah formula 8x9y (P (x) ^ Q (y; z) ! R (x; z)), maka subformula dari adalah (1) 8x9y (P (x) ^ Q (y; z) ! R (x; z)), (2)

MZI (FIF Tel-U)


November 2015

10 / 46


Sebuah formula

2



itu sendiri.

3


subformula dari

dan

subformula dari

Contoh Misalkan adalah formula 8x9y (P (x) ^ Q (y; z) ! R (x; z)), maka subformula dari adalah (1) 8x9y (P (x) ^ Q (y; z) ! R (x; z)), (2) 9y (P (x) ^ Q (y; z) ! R (x; z)), (3)

MZI (FIF Tel-U)


November 2015

10 / 46


Sebuah formula

2



itu sendiri.

3


subformula dari

dan

subformula dari

Contoh Misalkan adalah formula 8x9y (P (x) ^ Q (y; z) ! R (x; z)), maka subformula dari adalah (1) 8x9y (P (x) ^ Q (y; z) ! R (x; z)), (2) 9y (P (x) ^ Q (y; z) ! R (x; z)), (3) P (x) ^ Q (y; z) ! R (x; z), (4)

MZI (FIF Tel-U)


November 2015

10 / 46


Sebuah formula

2



itu sendiri.

3


subformula dari

dan

subformula dari

Contoh Misalkan adalah formula 8x9y (P (x) ^ Q (y; z) ! R (x; z)), maka subformula dari adalah (1) 8x9y (P (x) ^ Q (y; z) ! R (x; z)), (2) 9y (P (x) ^ Q (y; z) ! R (x; z)), (3) P (x) ^ Q (y; z) ! R (x; z), (4) P (x) ^ Q (y; z), (5)

MZI (FIF Tel-U)


November 2015

10 / 46


Sebuah formula

2



itu sendiri.

3


subformula dari

dan

subformula dari

Contoh Misalkan adalah formula 8x9y (P (x) ^ Q (y; z) ! R (x; z)), maka subformula dari adalah (1) 8x9y (P (x) ^ Q (y; z) ! R (x; z)), (2) 9y (P (x) ^ Q (y; z) ! R (x; z)), (3) P (x) ^ Q (y; z) ! R (x; z), (4) P (x) ^ Q (y; z), (5) P (x), (6)

MZI (FIF Tel-U)


November 2015

10 / 46


Sebuah formula

2



itu sendiri.

3


subformula dari

dan

subformula dari

Contoh Misalkan adalah formula 8x9y (P (x) ^ Q (y; z) ! R (x; z)), maka subformula dari adalah (1) 8x9y (P (x) ^ Q (y; z) ! R (x; z)), (2) 9y (P (x) ^ Q (y; z) ! R (x; z)), (3) P (x) ^ Q (y; z) ! R (x; z), (4) P (x) ^ Q (y; z), (5) P (x), (6) Q (y; z), dan (7)

MZI (FIF Tel-U)


November 2015

10 / 46


Sebuah formula

2



itu sendiri.

3


subformula dari

dan

subformula dari

Contoh Misalkan adalah formula 8x9y (P (x) ^ Q (y; z) ! R (x; z)), maka subformula dari adalah (1) 8x9y (P (x) ^ Q (y; z) ! R (x; z)), (2) 9y (P (x) ^ Q (y; z) ! R (x; z)), (3) P (x) ^ Q (y; z) ! R (x; z), (4) P (x) ^ Q (y; z), (5) P (x), (6) Q (y; z), dan (7) R (x; z).

MZI (FIF Tel-U)


November 2015

10 / 46

Formula yang Terbentuk dengan Baik (Well-Formed Formula, WFF)

De…nisi (Formula yang terbentuk dengan baik (well-formed formula, WFF))

MZI (FIF Tel-U)


November 2015

11 / 46

Formula yang Terbentuk dengan Baik (Well-Formed Formula, WFF)

De…nisi (Formula yang terbentuk dengan baik (well-formed formula, WFF)) Suatu formula dikatakan sebagai formula yang terbentuk dengan baik (well-formed formula) bila dapat dikonstruksi dengan berhingga langkah (…nite step) melalui aturan konstruksi formula logika predikat yang telah dijelaskan sebelumnya.

Catatan Untuk selanjutnya, istilah formula akan selalu berarti well-formed formula, kecuali bila disebutkan selain itu.

MZI (FIF Tel-U)


November 2015

11 / 46

BNF untuk Term dan Formula Logika Predikat BNF (Backus Naur Form) untuk Term Logika Predikat Misalkan x adalah simbol yang mewakili variabel, c adalah simbol yang mewakili konstanta, dan f adalah fungsi dengan ariti n 1. Sembarang term t pada logika predikat dibangkitkan oleh Backus Naur Form (BNF) berikut: t ::= x j c j f (t; : : : ; t) .

BNF (Backus Naur Form) untuk Formula Logika Predikat Misalkan t1 ; t2 ; : : : ; tn menyatakan term, x simbol yang mewakili variabel, dan P adalah predikat dengan ariti n 1. Sembarang formula pada logika predikat dibangkitkan oleh BNF berikut: ::= P (t1 ; t2 ; : : : ; tn ) j : j

^

j

_

Kita akan menulis > sebagai ringkasan dari juga akan menulis ? sebagai ringkasan dari MZI (FIF Tel-U)

j

j

!

j

$

j 8x j 9x

_ : atau : _ . Kemudian kita ^ : atau : ^ .


November 2015

12 / 46

Catatan Penulisan > dan ? biasanya hanya digunakan ketika kita meninjau formula logika predikat secara sintaks saja. Jika kita meninjau formula logika predikat secara sematik, maka kita akan menggunakan notasi T dan F, B dan S, atau 0 dan 1.

MZI (FIF Tel-U)


November 2015

13 / 46

Cakupan (Scope) dari Kuantor Cakupan (Scope) Misalkan P (x; y; z) adalah sebuah predikat terner. Dalam ekspresi logika predikat 9z8y9x P (x; y; z) kita memiliki 9z8y9x P (x; y; z) | {z } |

MZI (FIF Tel-U)

|

cakupan 9x

{z

cakupan 8y

{z

cakupan 9z

} }


November 2015

14 / 46


|

cakupan 9x

{z

cakupan 8y

{z

cakupan 9z

} }

9x mencakup P (x; y; z), pada subformula 9x P (x; y; z) variabel y dan z adalah variabel bebas, variabel x adalah variabel terikat.

MZI (FIF Tel-U)


November 2015

14 / 46


|

cakupan 9x

{z

cakupan 8y

{z

cakupan 9z

} }

9x mencakup P (x; y; z), pada subformula 9x P (x; y; z) variabel y dan z adalah variabel bebas, variabel x adalah variabel terikat. 8y mencakup 9x P (x; y; z), pada subformula 8y9x P (x; y; z) variabel z adalah variabel bebas, variabel x dan y adalah variabel terikat.

MZI (FIF Tel-U)


November 2015

14 / 46


|

cakupan 9x

{z

cakupan 8y

{z

cakupan 9z

} }

9x mencakup P (x; y; z), pada subformula 9x P (x; y; z) variabel y dan z adalah variabel bebas, variabel x adalah variabel terikat. 8y mencakup 9x P (x; y; z), pada subformula 8y9x P (x; y; z) variabel z adalah variabel bebas, variabel x dan y adalah variabel terikat. 9z mencakup 8y9x P (x; y; z), pada subformula 9z8y9x P (x; y; z) variabel x, y, dan z adalah variabel terikat. MZI (FIF Tel-U)


November 2015

14 / 46

Presedens Operator Logika Predikat Presedens operator logika memberikan suatu aturan operator mana yang harus lebih dulu dioperasikan (dikenakan pada suatu operand). Dari kuliah Logika Matematika, tabel urutan pengerjaan (presendens) operator logika adalah Operator Urutan 8 1 2 9 : 3 ^ 4 _ 5 6 ! 7 $ 8 Kita dapat menggunakan tanda kurung “(” dan “)” untuk memperjelas operasi yang harus didahulukan.

MZI (FIF Tel-U)


November 2015

15 / 46

Pohon Urai (Parse Tree) untuk Formula Pohon urai (parse tree) dapat digunakan untuk menggambarkan struktur suatu formula logika predikat. Sebagai contoh, pohon urai untuk formula 8x ((P (x) ! Q (x)) ^ S (x; y)) adalah

MZI (FIF Tel-U)


November 2015

16 / 46

Pohon Urai (Parse Tree) untuk Formula Pohon urai (parse tree) dapat digunakan untuk menggambarkan struktur suatu formula logika predikat. Sebagai contoh, pohon urai untuk formula 8x ((P (x) ! Q (x)) ^ S (x; y)) adalah

MZI (FIF Tel-U)


November 2015

16 / 46

Bahasan

1


2


3


4


5


MZI (FIF Tel-U)


November 2015

17 / 46

Variabel Terikat dan Formula Tertutup Variabel Terikat Misalkan P adalah suatu predikat uner, variabel x pada P (x) disebut variabel terikat (bound variable) apabila 1 2

x telah digantikan oleh sebuah elemen tertentu dari domain D, atau x diikat oleh sebuah kuantor (8x atau 9x)

Variabel yang tidak terikat disebut variabel bebas (free variable). Terminologi variabel terikat dan variabel bebas tidak hanya terdapat pada predikat uner saja, tetapi juga pada predikat lain dengan ariti n > 1.

Formula Tertutup Suatu formula logika predikat dikatakan sebagai formula tertutup bila seluruh variabel yang terdapat pada formula tersebut adalah variabel terikat. Sebagai contoh, bila P adalah predikat biner, x dan y adalah variabel, serta a dan b adalah elemen pada domain yang ditinjau, maka formula 8x9y P (x; y), 8x P (x; b), dan P (a; b) adalah formula tertutup, sedangkan 8x P (x; y), P (x; b), dan P (a; y) bukan formula tertutup. MZI (FIF Tel-U)


November 2015

18 / 46

Substitusi Variabel

Substitusi Variabel Misalkan adalah suatu formula logika predikat yang ditinjau pada semesta pembicaraan D dan d adalah suatu elemen pada D. Notasi [x d] berarti formula baru yang diperoleh dengan mengganti semua kemunculan variabel x dengan d pada formula .

MZI (FIF Tel-U)


November 2015

19 / 46

Aturan Semantik Logika Predikat Aturan Semantik Logika Predikat Misalkan adalah sebuah formula, D adalah domain pembicaraan yang ditinjau, dan I adalah interpretasi yang terde…nisi untuk setiap formula atom yang muncul di . Interpretasi untuk pada domain D dide…nisikan sebagai berikut

MZI (FIF Tel-U)


November 2015

20 / 46

Aturan Semantik Logika Predikat Aturan Semantik Logika Predikat Misalkan adalah sebuah formula, D adalah domain pembicaraan yang ditinjau, dan I adalah interpretasi yang terde…nisi untuk setiap formula atom yang muncul di . Interpretasi untuk pada domain D dide…nisikan sebagai berikut Jika = P (d1 ; d2 ; : : : ; dn ) untuk di (1 i n) pada domain yang ditinjau, maka ID ( ) = ID (P (d1 ; d2 ; : : : ; dn )) = T bila d1 ; d2 ; : : : ; dn berrelasi dan memberikan nilai kebenaran sesuai dengan de…nisi predikat P .

MZI (FIF Tel-U)


November 2015

20 / 46

Aturan Semantik Logika Predikat Aturan Semantik Logika Predikat Misalkan adalah sebuah formula, D adalah domain pembicaraan yang ditinjau, dan I adalah interpretasi yang terde…nisi untuk setiap formula atom yang muncul di . Interpretasi untuk pada domain D dide…nisikan sebagai berikut Jika = P (d1 ; d2 ; : : : ; dn ) untuk di (1 i n) pada domain yang ditinjau, maka ID ( ) = ID (P (d1 ; d2 ; : : : ; dn )) = T bila d1 ; d2 ; : : : ; dn berrelasi dan memberikan nilai kebenaran sesuai dengan de…nisi predikat P . Jika = T, maka ID ( ) = ID (T) = T. Kemudian jika ID ( ) = ID (F) = F.

MZI (FIF Tel-U)


= F, maka

November 2015

20 / 46


= F, maka

Jika = 8x untuk suatu formula , maka ID ( ) = ID (8x ) = T apabila ID ( [x d]) = T untuk setiap d pada domain pembicaraan D.

MZI (FIF Tel-U)


November 2015

20 / 46


= F, maka

Jika = 8x untuk suatu formula , maka ID ( ) = ID (8x ) = T apabila ID ( [x d]) = T untuk setiap d pada domain pembicaraan D. Jika = 9x untuk suatu formula , maka ID ( ) = ID (9x ) = T apabila ID ( [x d]) = T untuk suatu d pada domain pembicaraan D.

MZI (FIF Tel-U)


November 2015

20 / 46

Jika

= : , untuk suatu formula , maka T, jika I ( ) = F . I ( ) = I (: ) = :I ( ) = F, jika I ( ) = T

MZI (FIF Tel-U)


November 2015

21 / 46

Jika

= : , untuk suatu formula , maka T, jika I ( I ( ) = I (: ) = :I ( ) = F, jika I ( Jika = ^ , untuk suatu formula dan T, I( )=I( ^ )=I( )Î( )= F,

MZI (FIF Tel-U)

)=F . )=T , maka jika I ( ) = I ( ) = T . lainnya


November 2015

21 / 46

Jika

= : , untuk suatu formula , maka T, jika I ( I ( ) = I (: ) = :I ( ) = F, jika I ( Jika = ^ , untuk suatu formula dan T, I( )=I( ^ )=I( )Î( )= F, Jika = _ , untuk suatu formula dan F, I( )=I( _ )=I( )_I( )= T,

MZI (FIF Tel-U)

)=F . )=T , maka jika I ( ) = I ( ) = T . lainnya , maka jika I ( ) = I ( ) = F lainnya


November 2015

21 / 46

Jika

= : , untuk suatu formula , maka T, jika I ( I ( ) = I (: ) = :I ( ) = F, jika I ( Jika = ^ , untuk suatu formula dan T, I( )=I( ^ )=I( )Î( )= F, Jika = _ , untuk suatu formula dan F, I( )=I( _ )=I( )_I( )= T, Jika = , untuk suatu formula dan T, I( )=I( )=I( ) I( )= F,

MZI (FIF Tel-U)

)=F . )=T , maka jika I ( ) = I ( lainnya , maka jika I ( ) = I ( lainnya , maka jika I ( ) 6= I ( jika I ( ) = I (


)=T

.

)=F

) . )

November 2015

21 / 46

Jika

= : , untuk suatu formula , maka T, jika I ( I ( ) = I (: ) = :I ( ) = F, jika I ( Jika = ^ , untuk suatu formula dan T, I( )=I( ^ )=I( )Î( )= F, Jika = _ , untuk suatu formula dan F, I( )=I( _ )=I( )_I( )= T, Jika = , untuk suatu formula dan T, I( )=I( )=I( ) I( )= F, Jika


)=T

.

)=F

) . )

! , untuk suatu formula dan , maka I ( ) = I ( ! ) = F, jika I ( ) = T namun I ( ) = F I( )!I( )= . T, lainnya =

MZI (FIF Tel-U)


November 2015

21 / 46

Jika

= : , untuk suatu formula , maka T, jika I ( I ( ) = I (: ) = :I ( ) = F, jika I ( Jika = ^ , untuk suatu formula dan T, I( )=I( ^ )=I( )Î( )= F, Jika = _ , untuk suatu formula dan F, I( )=I( _ )=I( )_I( )= T, Jika = , untuk suatu formula dan T, I( )=I( )=I( ) I( )= F, Jika

! , untuk F, I( )!I( )= T, Jika = $ , untuk


)=T

.

)=F

) . )

suatu formula dan , maka I ( ) = I ( ! ) = jika I ( ) = T namun I ( ) = F . lainnya suatu formula dan , maka T, jika I ( ) = I ( ) I( )=I( $ )=I( )$I( )= . F, jika I ( ) 6= I ( ) =

MZI (FIF Tel-U)


November 2015

21 / 46

Sifat-sifat Formula Berdasarkan Semantiknya De…nisi Misalkan 1

2

3

4

5

adalah sebuah formula logika predikat:

formula dikatakan absah (valid) atau tautologi apabila selalu bernilai benar untuk setiap interpretasi I pada sembarang domain D formula dikatakan terpenuhi (satis…able) apabila untuk suatu interpretasi I pada suatu domain D

dapat bernilai benar

formula dikatakan kontradiksi (contradictory ) apabila salah untuk setiap interpretasi I pada setiap domain D

formula dikatakan tersalahkan (falsi…able) apabila untuk suatu interpretasi I pada suatu domain D

selalu bernilai

dapat bernilai salah

formula dikatakan kontingensi (contingency ) apabila bukan formula yang bersifat absah dan bukan pula formula yang bersifat kontradiksi.

MZI (FIF Tel-U)


November 2015

22 / 46

Masalah Keabsahan dan Keterpenuhan

Masalah Keabsahan (Validity Problem) Diberikan suatu formula logika predikat . Apakah

bersifat absah (valid)?

Masalah Keterpenuhan (Satis…ability Problem) Diberikan suatu formula logika predikat . Apakah (satis…able)?

MZI (FIF Tel-U)


bersifat terpenuhi

November 2015

23 / 46

Beberapa Teorema Penting

Teorema Misalkan

adalah sebuah formula logika predikat, maka berlaku:

1

formula

2

absah (valid) jika dan hanya jika : kontradiksi,

formula terpenuhi (satis…able) jika dan hanya jika : tersalahkan (falsi…able),

3

formula valid),

terpenuhi (satis…able) jika dan hanya jika : tidak absah (tidak

4

formula

absah (valid) jika dan hanya jika : tidak terpenuhi.

MZI (FIF Tel-U)


November 2015

24 / 46

Konsekuensi Logis dan Kesetaraan Logika De…nisi Misalkan dan Formula dan formula

adalah dua formula logika predikat: dikatakan setara atau ekuivalen (logically equivalent) jika $

merupakan tautologi. Hal ini dituliskan dengan atau , . Formula dikatakan sebagai konsekuensi logis (logical consequence) dari formula ! merupakan tautologi. Hal ini dituliskan dengan

jika

) .

Tidak seperti pada logika proposisi, untuk menunjukkan konsekuensi logis maupun kesetaraan logika antar dua formula pada logika predikat kita tidak dapat menggunakan tabel kebenaran.

MZI (FIF Tel-U)


November 2015

25 / 46

Beberapa Ekuivalensi Terkait Kuantor Misalkan dan adalah dua formula logika predikat dan x adalah sebuah variabel. Hukum De Morgan untuk Kuantor

MZI (FIF Tel-U)


November 2015

26 / 46

Beberapa Ekuivalensi Terkait Kuantor Misalkan dan adalah dua formula logika predikat dan x adalah sebuah variabel. Hukum De Morgan untuk Kuantor :8x :9x

9x : 8x :

Bila variabel x bukan variabel bebas pada

MZI (FIF Tel-U)

, maka berlaku:


November 2015

26 / 46

Beberapa Ekuivalensi Terkait Kuantor Misalkan dan adalah dua formula logika predikat dan x adalah sebuah variabel. Hukum De Morgan untuk Kuantor :8x

9x :

:9x

8x :

Bila variabel x bukan variabel bebas pada 8x

^

8x ( ^ )

9x

^

9x ( ^ )

8x 9x

_ _

, maka berlaku:

8x ( _ ) 9x ( _ )

Karena kuantor 8 merupakan generalisasi dari ^ dan kuantor 9 merupakan generalasiasi dari _, maka berlaku:

MZI (FIF Tel-U)


November 2015

26 / 46

Beberapa Ekuivalensi Terkait Kuantor Misalkan dan adalah dua formula logika predikat dan x adalah sebuah variabel. Hukum De Morgan untuk Kuantor :8x

9x :

:9x

8x :

Bila variabel x bukan variabel bebas pada 8x

^

8x ( ^ )

9x

^

9x ( ^ )

8x 9x

_ _

, maka berlaku:

8x ( _ ) 9x ( _ )

Karena kuantor 8 merupakan generalisasi dari ^ dan kuantor 9 merupakan generalasiasi dari _, maka berlaku: 8x 9x

^ 8x _ 9x MZI (FIF Tel-U)

8x ( ^ )

9x ( _ )


November 2015

26 / 46

Ekuivalensi yang Melibatkan Dua Kuantor Misalkan x dan y adalah dua variabel,

MZI (FIF Tel-U)

dan

adalah dua formula logika predikat.


November 2015

27 / 46

Ekuivalensi yang Melibatkan Dua Kuantor Misalkan x dan y adalah dua variabel, 1 2

8x8y 9x9y

dan


8y8x 9y9x

MZI (FIF Tel-U)


November 2015

27 / 46


3

8x8y 9x9y 8x

dan


8y8x 9y9x ^ 8y

8x8y ( ^ )

9x ^ 9y 9x9y ( ^ ), apabila x bukan variabel bebas di bukan variabel bebas di

dan y

5


dan y

6


dan y

4

Aturan nomor 3–4 dapat ditulis:

MZI (FIF Tel-U)


November 2015

27 / 46


3

8x8y 9x9y 8x

dan


8y8x 9y9x ^ 8y

8x8y ( ^ )


dan y

5


dan y

6


dan y

4

Aturan nomor 3–4 dapat ditulis: (Q1 x) ^ (Q2 y) (Q1 x) (Q2 y) ( ^ ), dengan Q1 dan Q2 adalah kuantor yang dapat berupa 8 atau 9.

MZI (FIF Tel-U)


November 2015

27 / 46

7 8

9

10

9x

_ 9y

9x9y ( _ )

8x8y ( _ ), apabila x bukan variabel bebas di bebas di 8x9y ( _ ), apabila x bukan variabel bebas di bebas di

dan y

9x _ 8y 9x8y ( _ ), apabila x bukan variabel bebas di bukan variabel bebas di

dan y

8x _ 8y bukan variabel 8x _ 9y bukan variabel

dan y

Aturan nomor 7–10 dapat ditulis:

MZI (FIF Tel-U)


November 2015

28 / 46

7 8

9

10

9x

_ 9y

9x9y ( _ )

8x8y ( _ ), apabila x bukan variabel bebas di bebas di 8x9y ( _ ), apabila x bukan variabel bebas di bebas di

dan y

9x _ 8y 9x8y ( _ ), apabila x bukan variabel bebas di bukan variabel bebas di

dan y

8x _ 8y bukan variabel 8x _ 9y bukan variabel

dan y

Aturan nomor 7–10 dapat ditulis: (Q1 x) _ (Q2 y) y (Q1 x) (Q2 y) ( _ ), dengan Q1 dan Q2 adalah kuantor yang dapat berupa 8 atau 9.

MZI (FIF Tel-U)


November 2015

28 / 46

Bahasan

1


2


3


4


5


MZI (FIF Tel-U)


November 2015

29 / 46

Bentuk Normal Prenex (Prenex Normal Form, PNF) Bentuk Normal Prenex (Prenex Normal Form, PNF) Sebuah formula logika predikat dikatakan berada dalam bentuk normal prenex (prenex normal form, PNF) apabila berbentuk (Q1 x1 )

(1)

(Qn xn )

dengan Qi 2 f8; 9g untuk 1 i n dan tidak ada kuantor yang muncul di . Biasanya juga direpresentasikan dalam CNF. Ekspresi kumpulan kuantor (Q1 x1 ) (Qn xn ) pada (1) disebut sebagai pre…ks (pre…x) dan formula yang tidak mengandung kuantor dinamakan matriks (matrix). BNF untuk PNF dijelaskan sebagai berikut: ::= P (t1 ; t2 ; : : : ; tn ) j : j

::=

j 8x j 9x

Dalam BNF ini, ti untuk 1

MZI (FIF Tel-U)

i

^

j

_

j

j

!

j

$

n adalah term dan simbol x mewakili variabel.


November 2015

30 / 46

Contoh Misalkan P dan Q adalah predikat uner, R adalah predikat biner. Formula 8xP (x) ! 8x9y (Q (y) ^ R (x; y)) tidak berada dalam PNF, begitu pula dengan formula 8x (P (x) ! 9y (Q (y) ^ R (x; y))). Formula 8x9y (P (x) ! Q (y) ^ R (x; y)) adalah contoh formula dalam PNF. Formula 8xP (x) _ 8xQ (x) dan 9xP (x) ^ 9xQ (x) keduanya tidak berada dalam PNF. PNF dari formula 8xP (x) _ 8xQ (x) bukan 8x (P (x) _ Q (x)) dan PNF dari formula 9xP (x) ^ 9xQ (x) bukan 9x (P (x) ^ Q (x)).

MZI (FIF Tel-U)


November 2015

31 / 46

Konversi Formula Ke PNF Untuk mengkonversi suatu formula ke dalam bentuk PNF, kita dapat melakukan hal-hal berikut:

MZI (FIF Tel-U)


November 2015

32 / 46

Konversi Formula Ke PNF Untuk mengkonversi suatu formula ke dalam bentuk PNF, kita dapat melakukan hal-hal berikut: 1

Ubah formula dengan operator selain :, ^, dan _ ke dalam formula yang hanya boleh memakai tiga operator tersebut. Sebagai contoh, bila formula yang ditinjau memakai operator , !, dan $ kita dapat memanfaatkan ekuivalensi berikut: ( ^ : ) _ (: _ ), ! : _ , dan $ (: _ ) ^ ( _ : ).

MZI (FIF Tel-U)


November 2015

32 / 46


2


Jika menemukan subformula dengan bentuk : ( ^ ), maka subformula tersebut diubah ke dalam bentuk : _ : . Kemudian jika menemukan subformula dengan bentuk : ( _ ), maka subformula tersebut diubah ke dalam bentuk : ^ : .

MZI (FIF Tel-U)


November 2015

32 / 46


2

3



Jika menemukan subformula dengan bentuk :: , maka subformula tersebut diubah ke dalam bentuk .

MZI (FIF Tel-U)


November 2015

32 / 46


2

3

4



Jika menemukan subformula dengan bentuk :: , maka subformula tersebut diubah ke dalam bentuk . Gunakan hukum De Morgan untuk kuantor, yaitu :8x 9x : dan :9x 8x : untuk mengeliminasi negasi yang muncul di depan kuantor.

MZI (FIF Tel-U)


November 2015

32 / 46

5

Ubah nama variabel terikat bila diperlukan.

MZI (FIF Tel-U)


November 2015

33 / 46

5


6

Gunakan ekuivalensi terkait logika predikat terkait operator ^ dan _ untuk membawa semua kuantor ke bagian depan (pre…ks).

MZI (FIF Tel-U)


November 2015

33 / 46

5


6

Gunakan ekuivalensi terkait logika predikat terkait operator ^ dan _ untuk membawa semua kuantor ke bagian depan (pre…ks).

7

Gunakan sifat distributif secara tepat dan sesuai.Kita memiliki ^ ( _ ) ( ^ ) _ ( ^ ) dan _ ( ^ ) ( _ ) ^ ( _ ).

MZI (FIF Tel-U)


November 2015

33 / 46

Beberapa Contoh Konversi ke PNF

Misalkan P dan Q adalah predikat uner, konversi dari PNF dapat dilakukan sebagai berikut: =

MZI (FIF Tel-U)

:= 8xP (x) _ 8xQ (x) ke

8xP (x) _ 8xQ (x)


November 2015

34 / 46



MZI (FIF Tel-U)

8xP (x) _ 8xQ (x) 8xP (x) _ 8yQ (y)

:= 8xP (x) _ 8xQ (x) ke

(ubah nama variabel)


November 2015

34 / 46



8xP (x) _ 8xQ (x) 8xP (x) _ 8yQ (y) 8x8y (P (x) _ Q (y))

:= 8xP (x) _ 8xQ (x) ke

(ubah nama variabel) (ekuivalensi kuantor dan _)

Jadi PNF dari adalah 8x8y (P (x) _ Q (y)). Dengan cara serupa, PNF dari := 9xP (x) ^ 9xQ (x) adalah 9x9y (P (x) ^ Q (y)).

MZI (FIF Tel-U)


November 2015

34 / 46

Misalkan P dan Q adalah predikat uner, konversi dari ke PNF dapat dilakukan sebagai berikut: =

MZI (FIF Tel-U)

:= 9xP (x) ! 8xQ (x)

9xP (x) ! 8xQ (x)


November 2015

35 / 46


MZI (FIF Tel-U)

9xP (x) ! 8xQ (x) :9xP (x) _ 8xQ (x)

(ekuivalensi


:= 9xP (x) ! 8xQ (x)

! )

November 2015

35 / 46


MZI (FIF Tel-U)

9xP (x) ! 8xQ (x) :9xP (x) _ 8xQ (x) 8x:P (x) _ 8xQ (x)

:= 9xP (x) ! 8xQ (x)

(ekuivalensi ! ) (De Morgan untuk kuantor)


November 2015

35 / 46


MZI (FIF Tel-U)

9xP (x) ! 8xQ (x) :9xP (x) _ 8xQ (x) 8x:P (x) _ 8xQ (x) 8x:P (x) _ 8yQ (y)

:= 9xP (x) ! 8xQ (x)

(ekuivalensi ! ) (De Morgan untuk kuantor) (ubah nama variabel)


November 2015

35 / 46


MZI (FIF Tel-U)

9xP (x) ! 8xQ (x) :9xP (x) _ 8xQ (x) 8x:P (x) _ 8xQ (x) 8x:P (x) _ 8yQ (y) 8x8y (:P (x) _ Q (y))

:= 9xP (x) ! 8xQ (x)

(ekuivalensi ! ) (De Morgan untuk kuantor) (ubah nama variabel) (ekuivalensi kuantor dan _)


November 2015

35 / 46

Misalkan P adalah predikat biner dan Q adalah predikat uner, konversi dari :9x8yP (x; y) ^ 8xQ (x) ke PNF dapat dilakukan sebagai berikut: =

:9x8yP (x; y) ^ 8xQ (x)

MZI (FIF Tel-U)


November 2015

36 / 46


:9x8yP (x; y) ^ 8xQ (x) 8x:8yP (x; y) ^ 8xQ (x)

MZI (FIF Tel-U)

(De Morgan untuk kuantor)


November 2015

36 / 46


:9x8yP (x; y) ^ 8xQ (x) 8x:8yP (x; y) ^ 8xQ (x) 8x9y:P (x; y) ^ 8xQ (x)

MZI (FIF Tel-U)

(De Morgan untuk kuantor) (De Morgan untuk kuantor)


November 2015

36 / 46


:9x8yP 8x:8yP 8x9y:P 8x9y:P

MZI (FIF Tel-U)

(x; y) ^ 8xQ (x) (x; y) ^ 8xQ (x) (x; y) ^ 8xQ (x) (x; y) ^ 8zQ (z)

(De Morgan untuk kuantor) (De Morgan untuk kuantor) (ubah nama variabel)


November 2015

36 / 46


:9x8yP (x; y) ^ 8xQ (x) 8x:8yP (x; y) ^ 8xQ (x) 8x9y:P (x; y) ^ 8xQ (x) 8x9y:P (x; y) ^ 8zQ (z) 8x9y8z (:P (x; y) ^ Q (z))

MZI (FIF Tel-U)

(De Morgan untuk kuantor) (De Morgan untuk kuantor) (ubah nama variabel) (ekuivalensi kuantor dan _)


November 2015

36 / 46

Bahasan

1


2


3


4


5


MZI (FIF Tel-U)


November 2015

37 / 46

Kelas-kelas Kompleksitas Komputasional Dalam teori komputasi, kita mengenal beberapa kelas kompleksitas komputasi sebagai berikut: P (kelas polinomial):

MZI (FIF Tel-U)


November 2015

38 / 46

Kelas-kelas Kompleksitas Komputasional Dalam teori komputasi, kita mengenal beberapa kelas kompleksitas komputasi sebagai berikut: P (kelas polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. N P (kelas non-deterministik polinomial):

MZI (FIF Tel-U)


November 2015

38 / 46

Kelas-kelas Kompleksitas Komputasional Dalam teori komputasi, kita mengenal beberapa kelas kompleksitas komputasi sebagai berikut: P (kelas polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. N P (kelas non-deterministik polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma non-deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. Hingga saat ini belum diketahui apakah P 6= N P . EXP T IM E (kelas eksponensial):

MZI (FIF Tel-U)


November 2015

38 / 46

Kelas-kelas Kompleksitas Komputasional Dalam teori komputasi, kita mengenal beberapa kelas kompleksitas komputasi sebagai berikut: P (kelas polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. N P (kelas non-deterministik polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma non-deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. Hingga saat ini belum diketahui apakah P 6= N P . EXP T IM E (kelas eksponensial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O ( n ) untuk suatu > 0. N EXP T IM E (kelas non-deterministik eksponensial):

MZI (FIF Tel-U)


November 2015

38 / 46

Kelas-kelas Kompleksitas Komputasional Dalam teori komputasi, kita mengenal beberapa kelas kompleksitas komputasi sebagai berikut: P (kelas polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. N P (kelas non-deterministik polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma non-deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. Hingga saat ini belum diketahui apakah P 6= N P . EXP T IM E (kelas eksponensial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O ( n ) untuk suatu > 0. N EXP T IM E (kelas non-deterministik eksponensial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma non-deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O ( n ) untuk suatu > 0. Hingga saat ini belum diketahui apakah EXP T IM E 6= N EXP T IM E. DECIDABLE (terputuskan):

MZI (FIF Tel-U)


November 2015

38 / 46

Kelas-kelas Kompleksitas Komputasional Dalam teori komputasi, kita mengenal beberapa kelas kompleksitas komputasi sebagai berikut: P (kelas polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. N P (kelas non-deterministik polinomial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma non-deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O nk untuk suatu k > 0. Hingga saat ini belum diketahui apakah P 6= N P . EXP T IM E (kelas eksponensial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O ( n ) untuk suatu > 0. N EXP T IM E (kelas non-deterministik eksponensial): kelas-kelas permasalahan yang dapat dipecahkan oleh algoritma non-deterministik yang kompleksitas asimtotik untuk waktu komputasinya adalah O ( n ) untuk suatu > 0. Hingga saat ini belum diketahui apakah EXP T IM E 6= N EXP T IM E. DECIDABLE (terputuskan): kelas-kelas permasalahan yang dapat dipecahkan dengan suatu algoritma yang sifatnya seragam (uniform) untuk setiap masukan (input) yang mungkin. MZI (FIF Tel-U)


November 2015

38 / 46

Dari teori komputasi, kita memiliki hubungan

MZI (FIF Tel-U)


November 2015

39 / 46

Dari teori komputasi, kita memiliki hubungan P

NP

P

EXP T IM E, N P

MZI (FIF Tel-U)

EXP T IM E

N EXP T IM E

DECIDABLE

N EXP T IM E


November 2015

39 / 46

Masalah Keterpenuhan pada Logika Proposisi dan Logika Predikat Permasalahan Diberikan sembarang formula logika proposisi yang memuat n proposisi atom berbeda. Apakah kita dapat membuat suatu algoritma (yang seragam untuk setiap masukan) untuk memeriksa apakah bersifat terpenuhi atau tidak?

MZI (FIF Tel-U)


November 2015

40 / 46

Masalah Keterpenuhan pada Logika Proposisi dan Logika Predikat Permasalahan Diberikan sembarang formula logika proposisi yang memuat n proposisi atom berbeda. Apakah kita dapat membuat suatu algoritma (yang seragam untuk setiap masukan) untuk memeriksa apakah bersifat terpenuhi atau tidak? Masalah keterpenuhan formula pada logika proposisi merupakan masalah yang terpenuhi. Untuk sembarang formula logika proposisi yang memuat n proposisi atom berbeda, kita dapat membuat algoritma yang kompleksitas asimtotik untuk waktu terburuknya adalah O (2n ).

Permasalahan

MZI (FIF Tel-U)


November 2015

40 / 46

Masalah Keterpenuhan pada Logika Proposisi dan Logika Predikat Permasalahan Diberikan sembarang formula logika proposisi yang memuat n proposisi atom berbeda. Apakah kita dapat membuat suatu algoritma (yang seragam untuk setiap masukan) untuk memeriksa apakah bersifat terpenuhi atau tidak? Masalah keterpenuhan formula pada logika proposisi merupakan masalah yang terpenuhi. Untuk sembarang formula logika proposisi yang memuat n proposisi atom berbeda, kita dapat membuat algoritma yang kompleksitas asimtotik untuk waktu terburuknya adalah O (2n ).

Permasalahan Diberikan sembarang formula logika predikat atas sembarang domain D. Apakah kita dapat membuat suatu algoritma (yang seragam untuk setiap masukan) untuk memeriksa apakah bersifat terpenuhi atau tidak?

MZI (FIF Tel-U)


November 2015

40 / 46

Teorema Tidak terdapat algoritma yang dapat memeriksa apakah sembarang formula logika predikat yang ditinjau pada sembarang domain D bersifat absah atau tidak.

Bukti Lihat bukti Teorema 2.22 pada buku Logic in Computer Science: Modelling and Reasoning about Systems, Edisi 2, 2004.

Akibat

MZI (FIF Tel-U)


November 2015

41 / 46

Teorema Tidak terdapat algoritma yang dapat memeriksa apakah sembarang formula logika predikat yang ditinjau pada sembarang domain D bersifat absah atau tidak.


Akibat Masalah keterpenuhan untuk formula logika predikat bersifat tak terputuskan (undecidable). Artinya tidak ada algoritma (program komputer) apapun yang dapat dipakai untuk memeriksa apakah sembarang formula logika predikat yang ditinjau pada sembarang domain D bersifat terpenuhi.

MZI (FIF Tel-U)


November 2015

41 / 46

Bahasan

1


2


3


4


5


MZI (FIF Tel-U)


November 2015

42 / 46

Aplikasi Logika Predikat dan Keterbatasannya

Logika predikat merupakan logika yang lebih ekspresif dari logika proposisi. Dengan logika predikat, kita mampu mendeskripsikan sifat dari suatu objek dengan lebih jelas dan menjelaskan relasi yang mungkin dipenuhi oleh dua atau lebih objek. Logika predikat telah diterapkan pada beberapa tools dan bahasa pemrograman, contohnya adalah SQL pada basis data, XQuery pada XML, dan Prolog.

Permasalahan

MZI (FIF Tel-U)


November 2015

43 / 46

Aplikasi Logika Predikat dan Keterbatasannya

Logika predikat merupakan logika yang lebih ekspresif dari logika proposisi. Dengan logika predikat, kita mampu mendeskripsikan sifat dari suatu objek dengan lebih jelas dan menjelaskan relasi yang mungkin dipenuhi oleh dua atau lebih objek. Logika predikat telah diterapkan pada beberapa tools dan bahasa pemrograman, contohnya adalah SQL pada basis data, XQuery pada XML, dan Prolog.

Permasalahan Apakah semua masalah dalam computer science/ software engineering dapat diformalisasikan dalam logika predikat?

MZI (FIF Tel-U)


November 2015

43 / 46

Ketercapaian (Reachability) pada Graf Misalkan G = (V; E) adalah suatu graf berarah dengan V = fs0 ; s1 ; s2 ; s3 g dan E = f(s0 ; s1 ) ; (s1 ; s0 ) ; (s1 ; s1 ) ; (s1 ; s2 ) ; (s2 ; s0 ) ; (s3 ; s0 ) ; (s3 ; s2 )g. Diberikan sembarang pasangan (sa ; sb ) dengan sa ; sb 2 V , kita katakan sb dapat dicapai (reachable) dari sa bila terdapat suatu lintasan (path) yang menghubungkan sa ke sb . Suatu lintasan merupakan barisan berhingga simpul (verteks), v1 ; v2 ; : : : ; vr , dengan sifat (vi ; vj ) 2 E untuk setiap 1 i < j r.

MZI (FIF Tel-U)


November 2015

44 / 46

Ketercapaian (Reachability) pada Graf Misalkan G = (V; E) adalah suatu graf berarah dengan V = fs0 ; s1 ; s2 ; s3 g dan E = f(s0 ; s1 ) ; (s1 ; s0 ) ; (s1 ; s1 ) ; (s1 ; s2 ) ; (s2 ; s0 ) ; (s3 ; s0 ) ; (s3 ; s2 )g. Diberikan sembarang pasangan (sa ; sb ) dengan sa ; sb 2 V , kita katakan sb dapat dicapai (reachable) dari sa bila terdapat suatu lintasan (path) yang menghubungkan sa ke sb . Suatu lintasan merupakan barisan berhingga simpul (verteks), v1 ; v2 ; : : : ; vr , dengan sifat (vi ; vj ) 2 E untuk setiap 1 i < j r.

MZI (FIF Tel-U)


November 2015

44 / 46

Pada graf yang telah ditunjukkan, kita mengetahui bahwa s2 dapat dicapai dari s0 dengan lintasan s0 ; s1 ; s2 , tetapi s3 tidak dapat dicapai dari s0 karena tidak terdapat barisan s0 ; : : : ; s3 .

Permasalahan

MZI (FIF Tel-U)


November 2015

45 / 46


Permasalahan Misalkan x; y 2 V dan N (x; y) adalah predikat yang bernilai benar (T) bila (x; y) 2 E. Untuk sembarang u; v 2 V , apakah pernyataan: “v dapat dicapai dari u” dapat ditranslasikan ke dalam formula dalam logika predikat dengan memakai predikat N (x; y)? Pada graf yang telah ditunjukkan kita memiliki N (s0 ; s1 )

MZI (FIF Tel-U)


November 2015

45 / 46


Permasalahan Misalkan x; y 2 V dan N (x; y) adalah predikat yang bernilai benar (T) bila (x; y) 2 E. Untuk sembarang u; v 2 V , apakah pernyataan: “v dapat dicapai dari u” dapat ditranslasikan ke dalam formula dalam logika predikat dengan memakai predikat N (x; y)? Pada graf yang telah ditunjukkan kita memiliki N (s0 ; s1 )

MZI (FIF Tel-U)


T, N (s1 ; s0 )

November 2015

45 / 46


Permasalahan Misalkan x; y 2 V dan N (x; y) adalah predikat yang bernilai benar (T) bila (x; y) 2 E. Untuk sembarang u; v 2 V , apakah pernyataan: “v dapat dicapai dari u” dapat ditranslasikan ke dalam formula dalam logika predikat dengan memakai predikat N (x; y)? Pada graf yang telah ditunjukkan kita memiliki N (s0 ; s1 ) N (s3 ; s1 )

MZI (FIF Tel-U)


T, N (s1 ; s0 )

November 2015

F,

45 / 46


Permasalahan Misalkan x; y 2 V dan N (x; y) adalah predikat yang bernilai benar (T) bila (x; y) 2 E. Untuk sembarang u; v 2 V , apakah pernyataan: “v dapat dicapai dari u” dapat ditranslasikan ke dalam formula dalam logika predikat dengan memakai predikat N (x; y)? Pada graf yang telah ditunjukkan kita memiliki N (s0 ; s1 ) N (s3 ; s1 ) F.

MZI (FIF Tel-U)


T, N (s1 ; s0 )

November 2015

F,

45 / 46


Permasalahan Misalkan x; y 2 V dan N (x; y) adalah predikat yang bernilai benar (T) bila (x; y) 2 E. Untuk sembarang u; v 2 V , apakah pernyataan: “v dapat dicapai dari u” dapat ditranslasikan ke dalam formula dalam logika predikat dengan memakai predikat N (x; y)? Pada graf yang telah ditunjukkan kita memiliki N (s0 ; s1 ) T, N (s1 ; s0 ) F, N (s3 ; s1 ) F. Salah satu cara untuk menyatakan bahwa “v dapat dicapai dari u” adalah dengan menuliskan ekspresi berikut: := (v = u) _

MZI (FIF Tel-U)


November 2015

45 / 46


Permasalahan Misalkan x; y 2 V dan N (x; y) adalah predikat yang bernilai benar (T) bila (x; y) 2 E. Untuk sembarang u; v 2 V , apakah pernyataan: “v dapat dicapai dari u” dapat ditranslasikan ke dalam formula dalam logika predikat dengan memakai predikat N (x; y)? Pada graf yang telah ditunjukkan kita memiliki N (s0 ; s1 ) T, N (s1 ; s0 ) F, N (s3 ; s1 ) F. Salah satu cara untuk menyatakan bahwa “v dapat dicapai dari u” adalah dengan menuliskan ekspresi berikut: := (v = u) _ 9x1 (N (u; x1 ) ^ N (x1 ; v)) _

MZI (FIF Tel-U)


November 2015

45 / 46



9x1 9x2 (N (u; x1 ) ^ N (x1 ; x2 ) ^ N (x2 ; v)) _

MZI (FIF Tel-U)


November 2015

45 / 46



9x1 9x2 (N (u; x1 ) ^ N (x1 ; x2 ) ^ N (x2 ; v)) _ : : : . Namun ekspresi ini bukan formula logika predikat (mengapa?).

MZI (FIF Tel-U)


November 2015

45 / 46

Teorema Ketercapaian (reachability ) pada graf berarah G = (V; E) tidak dapat diekspresikan dalam formula logika predikat menggunakan predikat N (x; y) yang berarti (x; y) 2 E.


MZI (FIF Tel-U)


November 2015

46 / 46

Logika Predikat (Kalkulus Predikat)

Recommend Documents