Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Logika Informatika : Logika Predikat Sintaks dan Contoh Soal

LOGIKA PREDIKAT

Lebih general dengan adanya predikat. Mampu menyatakan relasi antar objek. Hukum logika proposisi masih berlaku dengan perluasan. Hanya membahas Logika Predikat Tingkat Pertama

Kuantor : 

Universal : "

Eksistensial : $

SIMBOL

Simbol kebenaran : true dan false 

Konstanta 

Variabel 

Simbol fungsi 

Simbol predikat

FUNGSI

Fungsi memetakan sekumpulan objek ke objek lainnya. 

Contoh : mother(Andi)=Tesi, son(Adam,Eva)=Abel

PREDIKAT

Predikat menyatakan relasi antar objek/fungsi dengan keluaran boolean

Contoh : motherof(Tesi,Andi), sonof(Abel,Adam,Eva), man(Adam)

TERM

Konstanta 

Variabel

Jika t1,t2,…,tn adalah term, f adalah fungsi dengan arity n dan n³1 maka f(t1,t2,…,tn) adalah term

PROPOSISI

Menyatakan relasi antar objek 

Simbol kebenaran ATAU

Jika t1,t2,…,tn adalah term, p adalah predikat dengan arity n dan n³1 maka p(t1,t2,…,tn) adalah proposisi

KALIMAT

Proposisi 

Jika F adalah kalimat maka ØF juga kalimat 

Jika F dan G adalah kalimat maka : 

• F Λ G 
• F V G 
• F => G 

Jika x variabel dan F kalimat maka 

• "x F 
• $x F

EKSPRESI

Setiap kalimat atau term dalam logika predikat adalah ekspresi

OPERATOR PRECEDENCE

CONTOH 1

Nani adalah ibu dari Ratna. 

Term : nani, ratna 

Predikat : adalah ibu dari 

Fungsi : ibu(ratna)= nani 

Predikat : ibu_dari(nani, ratna) 

F(n,r)

CONTOH 2

Misalkan : 

Apakah nilai kebenaran untuk Q(3, 4, 5) ? 

CONTOH 3

M(x): x adalah mahasiswa 

P(x): x harus mengambil kuliah Struktur Diskret 

Q(x): x adalah mahasiswa Jurusan Informatika

Kalimat: setiap mahasiswa Jurusan Informatika harus mengambil kuliah Struktur Diskret

LATIHAN 1

Nyatakan kalimat berikut dalam sintaks logika predikat 

1. Setiap dosen suka membaca 
2. Setiap dosen suka membaca beberapa buku 
3. Setiap mahasiswa harus mengambil kuliah Struktur diskret atau ia adalah mahasiswa jurusan Informatika

CONTOH 4

P(x,y): x + y = 5 

Dalam sintaks logika predikat: 

LATIHAN 2

1 Tuliskan dalam sintaks logika predikat: 

Everybody loves somebody 

There is someone loved by everyone 

Note: anda dapat menggunakan predikat 

Love()

2. Untuk setiap bilangan bulat positif jika habis dibagi dengan 6 maka juga habis dibagi dengan 3

3. Evaluasilah apakah proposisi berikut benar atau salah: 

dengan Q(x,y) mempunyai interpretasi 2x = y dan x,y mempunyai daerah asal himpunan bilangan ganjil.

SUBTERM, SUBKALIMAT DAN SUBEKSPRESI

Semua term yang dipakai untuk membentuk term t atau kalimat F (termasuk t atau F) adalah subterm dari t atau dari F

Semua kalimat yang dipakai untuk membentuk kalimat F (termasuk F) adalah subkalimat dari F

Semua subterm atau subkalimat dari ekspresi e (termasuk e) adalah subekspresi dari e

Proper subterm, proper subkalimat dan proper subekspresi dari e adalah subterm, subkalimat dan subekspresi dari e yang bukan e 

CONTOH 1

KEMUNCULAN BEBAS DAN TERIKAT

Kemunculan suatu variabel x di dalam ekspresi e disebut terikat bila berada dalam scope suatu quantifier dan disebut bebas jika sebaliknya.

Jika terdapat lebih dari satu quantifier yang mengikat suatu variabel, maka quantifier terdalam yang mengikatnya. Kemunculan x dalam "x atau $x tidak bebas dan tidak terikat 

VARIABEL BEBAS DAN TERIKAT

Suatu variabel x disebut variabel terikat pada ekspresi e bila minimal ada satu kemunculan terikat x pada e 

Suatu variabel x disebut variabel bebas pada ekspresi e bila minimal ada satu kemunculan bebas x pada e

Kalimat tertutup adalah kalimat yang tidak memiliki variabel dengan kemunculan bebas 

SIMBOL BEBAS

Simbol bebas pada suatu ekspresi adalah semua variabel bebas, simbol konstanta, simbol fungsi dan simbol predikat pada ekspresi tersebut

CONTOH 1

Kemunculan x pada p(x,y) terikat maka x variabel terikat pada e 

Kemunculan y pada p(x,y) bebas dan pada q(y,z) terikat maka y variabel bebas dan terikat pada e 

Kemunculan z pada q(y,z) bebas maka z variabel bebas pada e 

e bukan kalimat tertutup

Simbol bebas : y,z,p,q

CONTOH 2

Kalimat tertutup karena x dan y variabel terikat

Kemunculan x pada subkalimat $y p(x,y) bebas

LATIHAN

1. Setiap anak suka semua permen 
2. Beberapa anak suka semua permen 
3. Ada anak yang suka beberapa permen 
4. Setiap anak suka beberapa permen
5. Setiap anak suka semua permen dan semua coklat 
6. Setiap anak suka semua permen dan beberapa coklat 
7. Tidak benar bahwa setiap anak suka beberapa permen dan semua coklat 

Translate the following into logical notation.

1. Somebody cried out for help and called the police 
2. Every philosopher trusts some lawyer who has sued one of his (the philosopher’s) students. 
3. Not all lawyers and philosophers are rich.
4. It is not both the case that Jon is taller than Frank and Frank is taller than Jon. 
5. Every teacher like some books and scientific papers 
6. Every teacher and some students like some books 
7. If Mary loves some places then she visits those places often and she tells everyone 

Sumber

Slide Logif : Logika Predikat Sintaks

http://informatika.unpar.ac.id/