LOGIKA PREDIKAT

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.

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.

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

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
  f(t1,t2,t3,..,tn )
  adalah sebuah term.

Contoh. Asumsikan simbol fungsi f adalah biner,i.e memiliki arity 2 dan simbol fungsi g adalah ternier, i.e memiliki arity 3 maka
a adalah term (karena a adalah konstan)
x adalah term (karena x adalah variabel)
f(a,x) adalah term (karena a dan x adalah term dan f adalah simbol fungsi biner)
g(x,f(a,x),a) adalah term (karena x,f(a,x) dan a adalah term dan g adalah simbol fungsi ternier )

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
  p(t1,t2,t3,..,tn )
  adalah sebuah proposisi.

Contoh. Bila p adalah simbol predikat ternier (dengan arity = 3) maka
p(a,x,f(a,x)) adalah proposisi (karena a,x dan f(a,x) adalah term).

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.

Contoh. Dengan asumsi a,b adalah konstan, x,y adalah variabel, f dan g adalah simbol fungsi biner, q adalah simbol predikat biner dan p adalah simbol predikat ternier. Buktikan bahwa
      ((∀ x)(p(a,x,f(a,x)) and ((∃ y)q(g(b,x),y))))
adalah kalimat dalam logika predikat.
p(a,x,f(a,x)) adalah kalimat (karena merupakan proposisi i.e predikat dengan argumen term)
q(g(b,x),y) adalah kalimat (karena merupakan proposisi)
((∃ y) q(g(b,x),y) ) adalah kalimat (dengan aturan kuantifier)
(p(a,x,f(a,x)) and ((∃ y) q(g(b,x),y) )) adalah kalimat (dengan aturan konjungsi)
((∀ x)(p(a,x,f(a,x)) and ((∃ y)q(g(b,x),y)))) adalah kalimat (dengan aturan kuantifier)

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) disebut subkalimat dari t atau F.
Subterm dan subkalimat sebuah term t atau kalimat F disebut sub ekspressi.

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

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)