Sign In Sign-Up

Welcome!

Close

Would you like to make this site your homepage? It's fast and easy...

Yes, Please make this my home page!

No Thanks

  Don't show this to me again.

Close

VIII Dasar Logika Predikat

VIII.1 Pendahuluan

Pada logika proposisional sebuah kalimat dapat ditentukan nilai kebenarannya dengan hanya memperhatikan struktur kalimat tersebut. Seperti kalimat

Kalimat 1 :

Andi suka makan bakso atau Andi tidak suka makan bakso

adalah benar tanpa harus tanya kepada Andi apakah dia suka bakso atau tidak karena kalimat itu merupakan perwujudan (Instance) kalimat logika proposional valid

P or (not P)

Ada beberapa kalimat, sayangnya, tidak dapat dikatakan benar berdasarkan struktur karena bukan perwujudan (Instance) dari sembarang kalimat valid logika proposisional. Sebagai contoh, kalimat- kalimat

Kalimat 2 :	Ada manusia yang jujur di Indonesia atau Semua manusia di Indonesia tidak jujur
Kalimat 3 :	Ada bilangan ganjil yang merupakan bilangan prima atau Semua bilangan prima bukan merupakan bilangan ganjil

adalah benar tanpa harus menyelidiki manusia indonesia atau definisi bilangan prima. Bahasa logika proposisional terlalu kasar dan primitif untuk mengekspressikan konsep objek (seperti : manusia atau bilangan), properti objek (seperti : jujur, ganjil atau prima), dan relasi antar objek.

Logika Predikat merupakan kembangan (perluasan) logika proposisi sehingga konsep objek dan relasi antar objek dapat diekspressikan dalam bahasa logika.

Dalam bahasa logika predikat kalimat 2 dan 3 merupakan perwujudan (instance) kalimat abstrak

F :	( ∃ x)[p(x) and q(x) ]     or ( ∀ x)[if p(x) then not q(x) ]

Untuk kalimat 2, diinterpretasikan objek adalah manusia, dengan p(x) manusia jujur dan q(x) manusia indonesia. Berdasarkan interpretasi ini kalimat F dapat dibaca

Terdapat manusia x yang memenuhi x itu jujur dan x adalah orang Indonesia atau Untuk semua manusia x, jika x jujur maka x adalah bukan orang Indonesia.

Dengan motivasi agar konsep objek dan relasi antar objek dapat diekspresikan dalam suatu bahasa logika dibuatlah aturan-aturan tata bahasa logika yang disebut logika predikat.

VIII.2 Sintaksis

Bahasa logika predikat memiliki tata aturan. Sintaksis hanya membicarakan tata aturan pembentukan kalimat dalam logika predikat yang benar tanpa memperhatikan arti kalimat tersebut.

VIII.2.1 Simbol

Bahasa logika predikat menggunakan simbol-simbol yang merupakan unsur pembentuk kalimat logika predikat. Simbol-simbol itu adalah :

• Simbol Kebenaran
      true dan false
• Simbol Konstan
      a,b,c
• Simbol Variabel
      x,y,z
• Simbol Fungsi
      f,g,h
  Tiap simbol fungsi berasosiasi dengan sebuah bilangan integer disebut arity yang merupakan jumlah argumen simbol fungsi.
• Simbol Predikat
      p,q,r
  Tiap simbol predikat berasosiasi dengan sebuah bilangan integer disebut arity yang merupakan jumlah argumen simbol predikat.

Secara intuiftif, simbol konstan dan simbol variabel mendenotasikan suatu objek sedangkan simbol fungsi dan simbol relasi mendenotasikan relasi dan fungsi antar objek.

Untuk membentuk kalimat logika predikat digunakan tiga tahap yaitu : pembentukan term, pembentukan proposisi dan akhirnya pembentukan kalimat

VIII.2.2 Term

terms pada logika predikat adalah ekspresi yang mendenotasikan objek. Terms dibangun dengan aturan berikut.

• Konstan a,b,c, .. adalah terms.
• Variabel x,y,z, .. adalah terms.
• Jika t1,t2,t3,..,tn adalah terms, dengan n >= 1 dan f adalah simbol fungsi dengan arity n maka pengaplikasian
  nbsp;nbsp; f(t1,t2,t3,..,tn )
  adalah sebuah term.

VIII.2.3 Proposisi

Proposisi pada logika predikat dimaksudkan untuk merepresentasikan relasi antar objek. Proposisi dibentuk dengan aturan berikut :

• Simbol Kebenaran : true dan false adalah proposisi
• Jika t1,t2,t3,..,tn adalah terms, dengan n >= 1 dan p adalah simbol predikat dengan arity n maka pengaplikasian
  nbsp;nbsp; p(t1,t2,t3,..,tn )
  adalah sebuah proposisi.

VIII.2.4 Kalimat

Kalimat dalam logika predikat dibangun oleh proposisi dengan menggunakan aturan berikut seperti pada logika proposisional

• Setiap proposisi adalah sebuah kalimat
• Jika F adalah sebuah kalimat, maka negasi F adalah kalimat
  (not F)
• Jika F dan G adalah kalimat, maka konjungsi F dan G adalah kalimat
  (F and G)
• Jika F dan G adalah kalimat, maka disjungsi F dan G adalah kalimat
  (F or G)
• Jika F dan G adalah kalimat, maka implikasi F dan G adalah kalimat
  (if F then G)
• Jika F dan G adalah kalimat, maka ekivalensi F dan G adalah kalimat
  (F G)
• Jika F,G dan H adalah kalimat, maka kondisional F,G dan H adalah kalimat
  (if F then G else H)
• Jika x adalah sembarang variabel dan F adalah kalimat, maka
  ((∀ x) F)
  dan
  ((∃ x) F)
  adalah kalimat. Prefik "∀" disebut kuantifier universal dan "∃" disebut kuantifier exitensial.

VIII.2.5 Sub Term, Sub Kalimat dan Sub Ekspressi

Setiap term yang dipakai untuk membangun term t (termasuk t) atau membangun sebuah kalimat F disebut subterm dari t atau F.
Setiap kalimat yang dipakai untuk membangun term t atau membangun sebuah kalimat F (termasuk F) disebuat subkalimat dari t atau F.
Subterm dan subkalimat sebuah term t atau kalimat F disebut sub ekspressi.
Sebuah subterm sejati, subkalimat sejati atau sub ekspressi sejati adalah dari sebuah ekspressi E adalah subterm, subkalimat atau sub ekspressi yang berbeda dengan E.

Contoh. Dalam kalimat F : p(a,x,f(a,x)) and (∃ y)q(g(b,x),y)

subterm dari F adalah : a, x, f(a,x), b, g(b,x) dan y
subkalimat dari F adalah : p(a,x,f(a,x)), q(g(b,x),y), (∃ y)q(g(b,x),y), dan F.

VIII.3 Variabel Bebas dan Terikat

Dalam kalimat :

    ( ∀ x) ((p(x,y) and (∃ y) q(y,x))
Terdapat kejadian x pada scope kuantifier ( ∀ x); kejadian x ini disebut terikat (bound) oleh kuantifier ( ∀ x). Kejadian y pada ekpressi p(x,y) tidak didalam scope kuantifier dalam bentuk ( ∀ y) atau (∃ y) sehingga disebut bebas (free). Namun, kejadian y pada (∃ y) q(y,x)) merupakan terikat (bound). Kejadian x dan y pada ( ∀ x) dan (∃ y) tidak dikatakan terikat atau bebas.

Misal x adalah variabel, E adalah ekspressi dalam logika predikat.

Kejadian x dalam kuantifier (∀ x) dan (∃ x) tidak dikatakan bebas atau terikat.

Kejadian x disebut bound in E jika x berada di dalam scope kuantifier (∀ x) atau (∃ x) di E. x terikat oleh kuantifier yang terdekat dengannya.

Kejadian x disebut free in E jika x tidak berada di dalam scope kuantifier (∀ x) atau (∃ x) di E.

Contoh. Dalam kalimat
(∀ x) (( p(x,y) and (∃ x) ( ∀ y) q(y,x)) Kejadian x pada subekspressi terakhir terikat oleh kuantifier (∃ x) sedangkan kejadian x pada subekspressi pertama terikat oleh kuantigier (∀ x).

VIII.4 Soal Latihan

1.	Temukan kalimat abstrak dalam bahasa logika predikat untuk kalimat bahasa manusia berikut ini : a. Untuk semua manusia, tidak ada manusia yang abadi b. Socrates adalah manusia c. Jika socrates adalah manusia dan Untuk semua manusia, tidak ada manusia yang abadi maka socrates tidak abadi. d. Jika semua bilangan prima adalah bilangan ganjil maka beberapa bilangan genap adalah bilangan prima. [Jawaban]
2.	Temukan subterm, subkalimat dan subekspressi kalimat berikut ini a. (∃ x) (if (p(a,f(g(a,x)),x) and q(x)) then (∀ y) q(y)) b. (∀ x) (∃ y) [if p(y) then p(x)] c if (∀ x,y) p(x,y) then (∀ x) p(x,f(x)) [Jawaban]
3.	Tentukan sifat free atau bound variabel pada tiap kejadian variabel di soal no.2

VIII.5 Jawaban Soal Latihan