Free Web Hosting Provider - Web Hosting - E-commerce - High Speed Internet - Free Web Page
Search the Web

Diktat Logika Matematika
Sebelum Ini Dasar Logika Predikat Setelah Ini


VIII Dasar Logika Predikat

Daftar Isi
VIII.1 Pendahuluan
VIII.2 Sintaksis
VIII.2.1 Simbol
VIII.2.2 Term
VIII.2.3 Proposisi
VIII.2.4 Kalimat
VIII.2.5 Subterm, Subkalimat, dan Subekspressi
VIII.3 Variabel Bebas dan Terikat (free and bound variables )
VIII.4 Soal Latihan


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.

[Kembali ke Atas]

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.

[Kembali ke Atas]

VIII.2.1 Simbol

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

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

[Kembali ke Atas]

VIII.2.2 Term

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

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 )

[Kembali ke Atas]

VIII.2.3 Proposisi

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


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

[Kembali ke Atas]

VIII.2.4 Kalimat

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


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)

[Kembali ke Atas]

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.

[Kembali ke Atas]

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

1. a. (∀ x) (if p(x) then (not q(x)))
  p merupakan simbol predikat dengan arity 1 merepresentasikan relasi manusia, q merupakan simbol predikat dengan arity 1 merepresentasikan relasi abadi.
b. p(a)
  a adalah simbol konstan yang merepresentasikan socrates, p sama dengan soal 1.a

c. if (p(a) and (∀ x) (if p(x) then (not q(x))) ) then (not q(a))

d. if (∀ x) (if prime(x) then ganjil(x)) then (∃ x) (if genap(x) then prime(x))
2. a. (∃ x) (if (p(a,f(g(a,x)),x) and q(x)) then (∀ y) q(y))
Subterms : x,y,a,g(a,x),f(g(a,x))
Subkalimat : q(x),q(y),p(a,f(g(a,x)),x),p(a,f(g(a,x)),x) and q(x), (∀ y) q(y), if (p(a,f(g(a,x)),x) and q(x)) then (∀ y) q(y), dan (∃ 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)]
Subterms : x,y
Subkalimat : p(y),p(x),if p(y) then p(x),(∃ y) [if p(y) then p(x)] dan (∀ x) (∃ y) [if p(y) then p(x)]

c. if (∀ x,y) p(x,y) then (∀ x) p(x,f(x))
Subterms : x,y,f(x)
Subkalimat : p(x,y), p(x,f(x)), (∀ x) p(x,f(x)),(∀ x,y) p(x,y) dan if (∀ x,y) p(x,y) then (∀ x) p(x,f(x))


Sebelum Ini Daftar Isi Setelah Ini
  Interpretasi Logika Predikat