Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Logika Informatika : Semantik Logika Predikat dan Contoh Soal

 

 

INTERPRETASI

Interpretasi harus memberi arti pada semua simbol bebas. 

Artinya: 

• Domain untuk semua konstanta dan variabel bebas 
• Definisi fungsi 
• Relasi untuk setiap predikat

CONTOH

Interpretasi I dengan domain bilangan integer dan: 

• a = 0 
• f(x) = x + 1 
• p(x,y) menyatakan relasi x > y 

p(a,f(a)) bernilai false 

Perlu aturan quantifier untuk menentukan interpretasi p(x,y)

DEFINISI

D adalah sebuah himpunan tak kosong. Interpretasi I pada domain D memberi nilai pada setiap konstanta, variabel, fungsi dan predikat:

• Untuk setiap konstanta a, elemen aI pada D 
• Untuk setiap variabel x, elemen xI pada D
• Untuk setiap simbol fungsi f berarity n, fungsi fI(d1,d2,…,dn) yang terdefinisi di D 
• Untuk setiap simbol predikat p berarity n, relasi pI(d1,d2,…,dn) yang terdefinisi di D

CONTOH

CONTOH 2

I2 : domain manusia 

a = Ratu Elizabeth, x = George Washington 

fI(d) adalah fungsi ibu dari d 

p(x,y) adalah relasi x anak dari y 

ATURAN SEMANTIK

1. Aturan konstanta 
2. Aturan variabel 
3. Aturan aplikasi (fungsi) 
4. Aturan true dan false 
5. Aturan proposisi 
6. Aturan operator

CONTOH

LATIHAN

INTERPRETASI DIPERLUAS

Jika I adalah interpretasi pada domain D dan d elemen D, <x<=d>○I adalah interpretasi di mana : 

• x diberi nilai d 
• Semua simbol bebas lain diberi nilai sesuai I 
• x bisa berupa variabel, konstanta, fungsi atau predikat

Jika I adalah interpretasi pada domain integer di mana : x =1 dan y = 2 maka <x<=3>○I adalah x =3 dan y = 2

<f<=+>○I adalah interpretasi di mana f adalah fungsi penjumlahan

SIFAT INTERPRETASI DIPERLUAS

Jika I interpretasi untuk kalimat "x F atau $x F maka <x<=d>○I adalah interpretasi untuk F 

Perhatikan: pada "x F atau $x F, x bukan variabel bebas, tetapi pada F, x mungkin variabel bebas 

Interpretasi diperluas bisa bertingkat : 

<xn<=d>○<xn-1<=d>○… <x1<=d>○I

ATURAN QUANTIFIER

• Aturan for-all
• Aturan for-some

ATURAN FOR-ALL

Jika kita memiliki formula F dalam konteks interpretasi I dan domain D, maka F dianggap benar (true) dalam interpretasi I jika, untuk setiap elemen d dalam domain D, nilai F benar pada titik tertentu di dalam domain yang lebih besar (x <= d) yang dinotasikan sebagai <x <= d> pada interpretasi I. Sebaliknya, F dianggap salah (false) dalam interpretasi I jika ada suatu elemen d dalam domain D sehingga nilai F menjadi salah pada titik tertentu di dalam domain yang lebih besar (x <= d) yang dinotasikan sebagai <x <= d> pada interpretasi I.

ATURAN FOR-SOME

Aturan ini berkaitan dengan pernyataan dalam logika matematika. Jika kita memiliki pernyataan $x F yang berlaku untuk suatu domain D, maka kita dapat menginterpretasikannya sebagai berikut:

1. Pernyataan $x F dianggap benar (true) dalam interpretasi (I) tertentu jika ada elemen d di dalam domain D sehingga nilai F benar pada x yang memiliki nilai d dalam interpretasi I. Artinya, ada setidaknya satu elemen dalam domain D yang memenuhi kondisi F dalam pernyataan $x F.

2. Sebaliknya, pernyataan $x F dianggap salah (false) dalam interpretasi (I) jika untuk setiap elemen d di dalam domain D, nilai F salah pada x yang memiliki nilai d dalam interpretasi I. Ini berarti tidak ada elemen dalam domain D yang memenuhi kondisi F dalam pernyataan $x F.

Dalam konteks ini, $x adalah variabel yang mewakili elemen-elemen dalam domain D, dan F adalah formula atau kondisi yang harus dipenuhi oleh elemen-elemen ini.

CONTOH 1

CONTOH 2

LATIHAN

KESEPAKATAN

Kesepakatan mengacu pada persetujuan dalam menafsirkan simbol atau ekspresi tertentu, dengan kriteria sebagai berikut:

1. Interpretasi Kesepakatan Simbol: Dua interpretasi dianggap sepakat pada suatu simbol jika keduanya memberikan nilai yang sama pada simbol tersebut, atau jika keduanya tidak memberikan nilai pada simbol tersebut.

2. Interpretasi Kesepakatan Ekspresi: Dua interpretasi dianggap sepakat pada suatu ekspresi jika nilai dari ekspresi tersebut sama dalam kedua interpretasi, atau jika keduanya bukan interpretasi untuk ekspresi tersebut.

Jika kedua interpretasi tersebut sepakat pada semua simbol bebas yang ada dalam ekspresi 'e', maka kedua interpretasi tersebut juga dianggap sepakat pada ekspresi 'e' itu sendiri.

CONTOH KESEPAKATAN

Berikut adalah contoh pernyataan kekesepakatan dalam konteks interpretasi I dan J pada domain integer:

I adalah interpretasi pada domain integer:

• Pernyataan ini menjelaskan bahwa kita memiliki interpretasi I pada domain integer, yang berisi informasi berikut ini:
  • a=0: Konstanta a dalam interpretasi I diberikan nilai 0.
  • b=2: Konstanta b dalam interpretasi I diberikan nilai 2.
  • x=-1: Variabel x dalam interpretasi I diberikan nilai -1.
  • f(d)=d+1: Ekspresi f(d) dalam interpretasi I diberikan definisi d+1, yang berarti jika kita memasukkan nilai d ke dalam f, hasilnya akan menjadi d+1.

J adalah interpretasi pada domain integer:

• Pernyataan ini menjelaskan bahwa kita memiliki interpretasi J pada domain integer, yang berisi informasi berikut ini:
  • a=0: Konstanta a dalam interpretasi J diberikan nilai 0.
  • x=1: Variabel x dalam interpretasi J diberikan nilai 1.
  • f(d)=d-1: Ekspresi f(d) dalam interpretasi J diberikan definisi d-1, yang berarti jika kita memasukkan nilai d ke dalam f, hasilnya akan menjadi d-1.

I dan J sepakat pada konstanta a:

• Ini menunjukkan bahwa baik dalam interpretasi I maupun J, konstanta a diberikan nilai 0. Dalam kedua interpretasi, a adalah 0.

I dan J sepakat pada predikat p:

• Teks ini menyiratkan bahwa terdapat sebuah predikat p yang ada dalam interpretasi I dan J, tetapi tidak ada informasi tambahan yang disediakan tentang definisi atau nilai p dalam konteks ini.

I dan J sepakat pada ekspresi f(x):

• Ini menunjukkan bahwa baik dalam interpretasi I maupun J, ekspresi f(x) memiliki nilai yang sama. Dalam kasus ini, f(x) adalah x+1 dalam interpretasi I dan x-1 dalam interpretasi J.

I dan J sepakat pada ekspresi f(y):

• Teks ini menyatakan bahwa dalam kedua interpretasi, I dan J, ekspresi f(y) memiliki nilai yang sama. Namun, tidak ada informasi lebih lanjut yang disediakan tentang definisi f(y) dalam teks ini.

 

LATIHAN