	Sign In Sign-Up

Diktat Logika Matematika
Sebelum Ini	Interpretasi Logika Predikat

IX. Interpretasi Logika Predikat

Daftar Isi
IX.1	Motivasi
IX.2	Interpretasi
IX.3	Aturan Semantik
IX.4	Interpretasi Termodifikasi
IX.5	Aturan untuk Kuantifier
IX.6	Latihan

IX.1 Motivasi

Interpretasi menugaskan makna untuk tiap simbol pada logika predikat yakni : konstan, fungsi dan predikat. Interpretasi menugaskan suatu nilai pada domain atau disebut objek kepada konstan dan variabel, fungsi atas domain kepada simbol fungsi dan relasi atas domain pada simbol predikat.

Contoh : terdapat kalimat logika predikat tertutup seperti berikut

G : if (∀ x)(∃ y) p(x,y) then p(a,f(a))

Sembarang interpretasi atas G harus menentukan domain dan menugaskan nilai ke tiap simbol dan terutama ke konstan a, fungsi f dan predikat p.
Misal sekarang terdapat interpretasi I dengan domain D adalah bilangan integer dan diinterpretasikan untuk tiap simbol a adalah 0;
f adalah fungsi suksessor yaitu fungsi f(d) adalah d + 1.
p adalah relasi lebih besar dari yaitu relasi p(d1,d2) adalah d1 > d2

Berdasarkan interpretasi I, maka kalimat G dapat ditentukan nilai kebenaranya. Perhatikan sub kalimat p(a,f(a)) berdasarkan interpretasi I adalah pertidaksamaan berikut

0 > 0 + 1
Oleh karena 0+1 adalah 1, dan karena 0 > 1 adalah bernilai false maka predikat p(a,f(a)) dalam interpretasi I adalah bernilai false

Kalimat G dapat diketahui nilai kebenarannya apabila bagian anteseden diketahui yaitu kalimat :
(∀ x)(∃ y) p(x,y)
Berdasarkan interpretasi I anteseden itu dapat diterjemahkan menjadi :
Untuk semua integer d, terdapat integer d' sehingga d > d'
kalimat ini bernilai true (ambil d adalah d dan d' adalah d-1).
Karena bagian anteseden dan konsekwen kalimat G telah diketahui makna kebenarannya, kalimat G dapat diketahui dengan aturan implikasi yaitu
if true then false false

[Kembali ke Atas]

IX.2 Interpretasi

Definisi.
Didefinisikan D adalah himpunan elemen sembarang.
Sebuah interpretasi I atas domain D memberikan nilai ke tiap simbol konstan, variabel, fungsi dan predikat sebagai berikut

Untuk tiap konstan a, sebuah elemen a(I) di D.
Untuk tiap variabel x, sebuah elemen x(I) di D.
Untuk tiap fungsi f dengan arity n f(d1,d2,...,dn) dengan d1,d2,..,dn di D dan nilai fungsi f(d1,d2,...,dn) juga di D.
Untuk tiap predikat p dengan arity n p(d1,d2,...,dn) dengan d1,d2,..,dn di D dan nilai predikat p(d1,d2,...,dn) adalah true atau false .

Contoh. Perhatikan kalimat logika predikat ini :

F : if p(x,f(x)) then (∃ y)p(a,y)

Tetapkan I sebagai interpretasi dalam domain bilangan real, kemudian ditetapkan
a dalam interpretasi I sebagai 2.5
x dalam interpretasi I sebagai π (perhatikan x adalah variabel bebas)
f dalam interpretasi I sebagai fungsi dengan arity 1. f(d) = d / 2
p dalam interpretasi I sebagai relasi lebih besar atau sama dengan (>=)

Maka arti intuitif kalimat F dengan interpretasi I adalah :

Jika π >= π/2 Maka ada bilangan d sehingga 2.5 >= d

Misalkan terdapat interpretasi lain terdapat kalimat F sebut J. Pada interpretasi J ditentukan domain adalah himpunan manusia
dan ditetapkan.
a dalam interpretasi J sebagai Ratu Balqis
x dalam interpretasi J sebagai Albert Einstein(perhatikan x adalah variabel bebas)
f dalam interpretasi J sebagai fungsi ibu. f(d) adalah ibu d
p dalam interpretasi J sebagai relasi anak p(d1,d2) adalah d1 anak d2

Maka arti intuitif kalimat F dengan interpretasi I adalah :

Jika Albert Einstein anak ibunya Albert Einstein Maka terdapat seseorang y sehingga Ratu Balqis adalah anak y.

[Kembali ke Atas]

IX.3 Aturan Semantik

Aturan semantik pada logika predikat mengadopsi semua aturan semantik pada logika proposisi dengan ditambah sebagai berikut :

Aturan Konstan Nilai konstan a adalah sebuah elemen domain aI
Aturan Variabel Nilai variabel x adalah sebuah elemen domain xI
Aturan Aplikasi Nilai aplikasi fungsi f(t1,t2,..,tn) adalah elemen domain fI(t1,t2,..,tn) dengan fI adalah nilai dari pengaplikasian fungsi f dengan nilai argumen term t1,t2,...,tn
Aturan term if then else Nilai term kondisional atau dalam bentuk if F then t else s [dengan s dan t adalah term] adalah t apabila F bernilai true dan s apabila F bernilai false.

Contoh. Perhatikan kalimat

E : not p(y,f(y)) or p(a,f(f(a)))
Terdapat interpretasi I dalam domain integer non-negatif dan ditetapkan
a bernilai 0
y bernilai 2
f adalah fungsi suksessor f(d) : d + 1 dan
p adalah relasi <

E dalam interpretasi I memiliki makna intuitif :
not (2 < 2+1) or 0 < (0+1)+1

Nilai p(y,f(y)) dapat ditetapkan berdasar interpretasi I yaitu
2 < 2+1
2 < 3
0leh karena 2 lebih kecil dari 3 adalah benar maka nilai p(y,f(y)) dalam interpretasi I adalah true. Oleh karena itu, (not p(y,f(y))) bernilai false

Nilai p(a,f(f(a))) dapat ditetapkan berdasarkan interpretasi I yaitu
0 < (0+1)+1
0 < 1+1
0 < 2
Oleh karena 0 memang lebih kecil dari 2 maka nilai p(a,f(f(a))) adalah true.
Berdasarkan penelusuran sebelum ini, nilai kalimat E dapat ditetapkan yaitu
E : not p(y,f(y)) or p(a,f(f(a)))
] : not true or true
: false or true
: true

[Kembali ke Atas]

IX.4 Interpretasi termodifikasi

Iterpretasi termodifikasi atas domain D untuk Interpretasi I untuk sembarang variabel x ditulis sebagai :

< x <-- d > o I

adalah

Variabel x bernilai elemen domain d, bukan pada nilai pada interpretasi I
Tiap variabel y selain x diberi nilai elemen domain yI pada interpretasi I
Tiap konstan a, fungsi f, predikat p diberi nilai sesuai dengan interpretasi I

Contoh. Misalnya terdapat interpretasi I adalah interpretasi pada domain integer dan ditugaskan
x bernilai 1
y bernilai 2

maka interpretasi termodifikasi
< x <-- 3 > o I

Tetap menugaskan nilai 2 pada variabel y tapi memberi nilai 3 pada variabel x.

[Kembali ke Atas]

IX.5 Aturan untuk Kuantifier

Aturan ∀
Terdapat I adalah interpretasi pada domain D
maka nilai dari kalimat terkuantifikasi universal
(∀ x) F
adalah true dalam interpretasi I jika
untuk semua elemen d di domain D
nilai kalimat F adalah true dalam interpretasi termodifikasi
< x <-- d > o I

bernilai false dalam interpretasi I jika
ada elemen d di domain D
sehingga nilai F adalah false dalam interpretasi termodifikasi
< x <-- d > o I
Aturan ∃ Terdapat I adalah interpretasi pada domain D
maka nilai dari kalimat terkuantifikasi universal
(∃ x) F
adalah true dalam interpretasi I jika
ada elemen d di domain D
nilai kalimat F adalah true dalam interpretasi termodifikasi
< x <-- d > o I

bernilai false dalam interpretasi I jika
untuk semua elemen d di domain D
sehingga nilai F adalah false dalam interpretasi termodifikasi
< x <-- d > o I

[Kembali ke Atas]

IX.6 Latihan

Perhatikan kalimat logika predikat berikut ini

(a) p(a,x)

(b) p(x,a) and p(x,f(x))

(c) (∃ y) p(y,x)

(d) (∃ y) [ p(y,a) or p(f(y),y)]

(e) (∀ x)(∃ y) p(x,y)

(f) (∃ y)(∀ x) p(x,y)

Tentukan nilai kebenaran kalimat tersebut dalam interpretasi I dalam domain integer nonnegatif dan
a adalah 0
x adalah 1
f adalah fungsi f(d) : d+1
p adalah relasi < p(d1,d2) : d1 < d2;

[Jawaban]

[Kembali ke Atas]

IX.7 Jawaban Soal Latihan

Berdasarkan interpretasi I maka kalimat tersebut dapat ditentukan nilai kebenarannya yaitu

(a) p(a,x) dalam interpretasi I dapat digantikan dengan kalimat biasa
0 < 1
Oleh karena 0 lebih kecil dari 1 adalah true maka
Nilai p(a,x) pada interpretasi I adalah true

(b) p(x,a) and p(x,f(x)) dalam interpretasi I dapat digantikan dengan kalimat biasa
1 < 0 and 1 < (1+1)
1 < 0 and 1 < 2
Oleh karena 1 tidak lebih kecil dari 0, maka p(x,a) bernilai false
Oleh karena 1 lebih kecil dari 2, maka p(x,f(x)) bernilai true

Sehingga kalimat (b) dapat diubah menjadi
false and true
yang ekivalen dengan false

(c) (∃ y) p(y,x) dalam interpretasi I dapat diganti dengan kalimat biasa
Ada integer y, sehingga y < 1
Berdasarkan aturan ∃ terdapat interpretasi termodifikasi sehingga y < 1 bernilai true, yaitu
< y <-- 0 > o I sehingga (∃ y) (y < 1) bernilai true

(d) (∃ y) [ p(y,a) or p(f(y),y)] dalam interpretasi I dapat diganti dengan kalimat biasa yaitu :
Ada integer y sehingga (y < 0) atau ((y+1) < y)
Berdasarkan aturan ∃, agar
bernilai true harus ada bilangan d yang merupakan bilangan nonnegatif yang memenuhi interpretasi termodifikasi < y <-- d > o I Sehingga
(d < 0) atau ((d+1) < d)
bernilai true

Untuk subkalimat pertama (d < 0) tidak ada bilangan d pada non negatif yang memenuhi (d < 0)
sedangkan subkalimat kedua ((d+1) < d) tidak ada bilangan d pada non negatif yang memenuhi ((d+1) < d)
Sehingga tidak ada bilangan d di integer non negatif yang memenuhi
(d < 0) atau ((d+1) < d)
Jadi, nilai
(∃ y) [ p(y,a) or p(f(y),y)]
dalam interpretasi I adalah bernilai false

(e) (∀ x)(∃ y) p(x,y)
dalam interpretasi I dapat diterjemahkan menjadi kalimat biasa yaitu
Untuk semua integer nonnegatif x
terdapat integer nonnegatif y
    sehingga berlaku x < y
Berdasarkan aturan ∀ nilai kalimat (e) bernilai true apabila untuk semua bilangan d1 di noninteger
ada bilangan d2 di noniteger sehingga interpretasi termodifikasi
< x <-- d1 > o < y <-- d2 > o I
bernilai true
Sekarang bila dimodifikasi d2 sebagai d1+1 maka kalimatnya menjadi
untuk semua bilangan d1 di noninteger ada bilangan d1+1 sehingga (d1 < (d1+1)).
Kalimat ada bilangan d1+1 sehingga (d1 < (d1+1))
bernilai true untuk semua bilangan d1 sehingga
Kalimat
(∀ x)(∃ y) p(x,y)
bernilai true pada interpretasi I

(f) (∃ y)(∀ x) p(x,y)
Dalam interpretasi I dapat dibaca sebagai
Ada bilangan integer non negatif y sehingga
Semua bilangan integer non negatif x berlaku      (x < y )

Berdasarkan aturan ∃ kalimat (f) bernilai true apabila
Terdapat bilangan d1 di integer nonnegatif dan
Semua bilangan d2 di integer nonnegatif yang mengakibatkan interpretasi termodifikasi x <-- d2 dan y <-- d1
     (d2 < d1 )
bernilai true.

Perhatikan untuk semua d1 pada bilangan integer non negatif
Apabila d2 = d1, maka (d2 < d1) benilai false
maka kalimat
(∃ y)(∀ x) p(x,y) dalam interpretasi I adalah bernilai false

Sebelum Ini	Daftar Isi
Dasar Logika Predikat

(a)	p(a,x)
(b)	p(x,a) and p(x,f(x))
(c)	(∃ y) p(y,x)
(d)	(∃ y) [ p(y,a) or p(f(y),y)]
(e)	(∀ x)(∃ y) p(x,y)
(f)	(∃ y)(∀ x) p(x,y)

(a)	p(a,x) dalam interpretasi I dapat digantikan dengan kalimat biasa 0 < 1 Oleh karena 0 lebih kecil dari 1 adalah true maka Nilai p(a,x) pada interpretasi I adalah true
(b)	p(x,a) and p(x,f(x)) dalam interpretasi I dapat digantikan dengan kalimat biasa 1 < 0 and 1 < (1+1) 1 < 0 and 1 < 2 Oleh karena 1 tidak lebih kecil dari 0, maka p(x,a) bernilai false Oleh karena 1 lebih kecil dari 2, maka p(x,f(x)) bernilai true Sehingga kalimat (b) dapat diubah menjadi false and true yang ekivalen dengan false
(c)	(∃ y) p(y,x) dalam interpretasi I dapat diganti dengan kalimat biasa Ada integer y, sehingga y < 1 Berdasarkan aturan ∃ terdapat interpretasi termodifikasi sehingga y < 1 bernilai true, yaitu < y <-- 0 > o I sehingga (∃ y) (y < 1) bernilai true
(d)	(∃ y) [ p(y,a) or p(f(y),y)] dalam interpretasi I dapat diganti dengan kalimat biasa yaitu : Ada integer y sehingga (y < 0) atau ((y+1) < y) Berdasarkan aturan ∃, agar bernilai true harus ada bilangan d yang merupakan bilangan nonnegatif yang memenuhi interpretasi termodifikasi < y <-- d > o I Sehingga (d < 0) atau ((d+1) < d) bernilai true Untuk subkalimat pertama (d < 0) tidak ada bilangan d pada non negatif yang memenuhi (d < 0) sedangkan subkalimat kedua ((d+1) < d) tidak ada bilangan d pada non negatif yang memenuhi ((d+1) < d) Sehingga tidak ada bilangan d di integer non negatif yang memenuhi (d < 0) atau ((d+1) < d) Jadi, nilai (∃ y) [ p(y,a) or p(f(y),y)] dalam interpretasi I adalah bernilai false
(e)	(∀ x)(∃ y) p(x,y) dalam interpretasi I dapat diterjemahkan menjadi kalimat biasa yaitu Untuk semua integer nonnegatif x terdapat integer nonnegatif y sehingga berlaku x < y Berdasarkan aturan ∀ nilai kalimat (e) bernilai true apabila untuk semua bilangan d1 di noninteger ada bilangan d2 di noniteger sehingga interpretasi termodifikasi < x <-- d1 > o < y <-- d2 > o I bernilai true Sekarang bila dimodifikasi d2 sebagai d1+1 maka kalimatnya menjadi untuk semua bilangan d1 di noninteger ada bilangan d1+1 sehingga (d1 < (d1+1)). Kalimat ada bilangan d1+1 sehingga (d1 < (d1+1)) bernilai true untuk semua bilangan d1 sehingga Kalimat (∀ x)(∃ y) p(x,y) bernilai true pada interpretasi I
(f)	(∃ y)(∀ x) p(x,y) Dalam interpretasi I dapat dibaca sebagai Ada bilangan integer non negatif y sehingga Semua bilangan integer non negatif x berlaku (x < y ) Berdasarkan aturan ∃ kalimat (f) bernilai true apabila Terdapat bilangan d1 di integer nonnegatif dan Semua bilangan d2 di integer nonnegatif yang mengakibatkan interpretasi termodifikasi x <-- d2 dan y <-- d1 (d2 < d1 ) bernilai true. Perhatikan untuk semua d1 pada bilangan integer non negatif Apabila d2 = d1, maka (d2 < d1) benilai false maka kalimat (∃ y)(∀ x) p(x,y) dalam interpretasi I adalah bernilai false