LOGIKA PREDIKAT

Altien Jonathan Rindengan, S.Si, M.Kom

Logika Predikat

Seringkali kita harus memeriksa argumen yang

berisi proposisi-proposisi yang berkenaan dengan

kumpulan objek.

Misalkan, memeriksa kebenaran dari proposisi

“Semua bilangan asli yang habis dibagi 4 adalah

habis dibagi 2”.

Pada proposisi ini mengandung suatu pernyataan

yang berkenaan dengan himpunan bilangan asli.

Misalkan ada rangkaian proposisi :

Setiap manusia pasti mati. Karena Furlan adalah

manusia maka dia pasti mati.

Pada logika proporsional :

p : setiap manusia pasti mati

q : Furlan adalah manusia

r : Furlan pasti mati

Karena q anggota dari p maka struktur ini tidak

dikenal dalam logika proposisi

Logika Predikat ….

Definisi 2.5

Suatu predikat (proposisi terbuka) adalah suatu

pernyataan yang melibatkan peubah yang nilainya

tidak ditentukan.

Logika Predikat ….

Misalnya :

Predikat : P(x) : bilangan bulat x habis dibagi 3

dan 4.

Proposisi : P(24) : 24 habis dibagi 3 dan 4.

Peubah dalam predikat hanya bisa diganti oleh

nilai yang merupakan anggota semesta

pembicaraan.

Logika Predikat ….

Definisi 2.6

Himpunan nilai-nilai yang mungkin menggantikan

peubah dalam suatu predikat disebut sebagai

semesta bagi peubah tersebut.

Logika Predikat ….

Untuk menyatakan nilai-nilai apa saja yang akan

menjadi peubah dalam suatu predikat, digunakan

kata:

semua, setiap, selalu, dll, disebut suku pengkuatifikasi

umum,

disimbolkan

ada, terdapat, beberapa, minimal satu, dll, disebut

suku pengkuatifikasi khusus,

disimbolkan

Logika Predikat ….

Misalkan x [P(x)] = untuk setiap x berlaku P(x)

x [P(x)] = ada x sehingga P(x)

P(x) bisa berupa proposisi tunggal atau majemuk.

Logika Predikat ….

Contoh 1

Nyatakan dalam lambang logika predikat dari proposisi :

a. Untuk semua bilangan bulat, jika habis dibagi 4 maka

habis dibagi 2

b. Ada bilangan asli yang habis dibagi 3 dan 4.

Jawab

a. P(x) : x habis dibagi 4

Q(x) : x habis dibagi 2

xZ [P(x) Q(x)]

b. P(x) : x habis dibagi 3

Q(x) : x habis dibagi 4

xN [P(x) Q(x)]

Logika Predikat ….

Contoh 2

Jika semesta dinyatakan U = {3,5,17,120}, x adalahpeubah dalam U. Buatlah suatu logika predikatdengan menggunakan proposisi, P(x) = x > 2.

Jawab

xU [P(x)] = semua x di U adalah lebih besar 2

-[xU (-P(x))] = tidak ada x di U yang tidak lebih

besar 2

xU [P(x)] = ada x di U yang lebih besar 2

-[xU (-P(x))] = tidak semua x di U adalah tidak

lebih besar 2.

Logika Predikat ….

Contoh 3

Tidak ada orangtua menginginkan anaknya menjadi

penjahat

Jawab

Kalimat tersebut ekivalen dengan “Jika x adalah orang

tua maka x tidak ingin anaknya menjadi penjahat”

P(x) = x adalah orang tua

Q(x) = x ingin anaknya menjadi penjahat

xU [P(x) - Q(x)]

U = himpunan orang tua

Logika Predikat ….

Jika suatu logika predikat dibuat

negasi/ingkarannya, maka tanda ingkaran itu akan

berlaku pada suku kuantifikasi dan predikatnya.

-[x (P(x))] =(-x )[-P(x)] = x[-P(x)]

-[x (P(x))] =(-x )[-P(x)] = x [-P(x)]

Negasi Logika Predikat

Dari bentuk ingkaran ini diperoleh 4 dasar kesetaraan padalogika predikat yaitu :

1. Semua benar sama artinya dengan tidak ada yang salah

x [P(x)] = -[x (-P(x))]

2. Semua salah sama artinya dengan tidak ada yang benar

x [-P(x)] = -[x (P(x))]

3. Tidak semua benar sama artinya dengan ada yang salah

-[x (P(x))] = x [-P(x)]

4. Tidak semua salah sama artinya dengan ada yang benar

-[x (-P(x))] = x [P(x)]

Negasi Logika Predikat ….

Contoh 4

Buatlah ingkaran dari logika predikat berikut :

a. x [P(x) Q(x)]

b. x[y [P(y) Q(x,y)]

c. xy[z(P(x) R(y,z)) (P(y) z R(x,z))]

Jawab

a. -[x [P(x) Q(x)]] = -(x)(-(P(x) Q(x)))

= x[-(-P(x) Q(x))]

= x[P(x) -Q(x)]

Negasi Logika Predikat ….

Contoh 5

Buatlah ingkaran dari logika predikat berikut :

a. x [P(x) Q(x)]

b. x[y [P(y) Q(x,y)]

c. xy[z(P(x) R(y,z)) (P(y) z R(x,z))]

Negasi Logika Predikat ….

Jawab

a. -[x [P(x) Q(x)]]= -(x)(-(P(x) Q(x)))

= x[-(-P(x) Q(x))]

= x[P(x) -Q(x)]

b. -[x[y [P(y) Q(x,y)]] = -(x)[-(y P(y) Q(x,y))]

= x[-(-y P(y) Q(x,y))]

= x[y P(y) -Q(x,y)]

Negasi Logika Predikat ….

c. -[xy[z(P(x) R(y,z)) (P(y) z R(x,z))]]

= -(xy)(-[z(P(x) R(y,z)) (P(y) z R(x,z))])

= xy[-(z(-P(x) R(y,z))) -(P(y) z R(x,z))]

= xy[z(-(P(x) R(y,z))) (-P(y) -(z R(x,z)))]

= xy[z (P(x) -R(y,z)) (-P(y) z (-R(x,z)))]

Kesetaraan Logika Predikat

1. a. x y P(x,y) y x P(x,y)

b. x y P(x,y) y x P(x,y)

2. a. x y P(x,y) y x P(x,y)

b. x y P(x,y) y x P(x,y)

3. a. -x P(x) x [-P(x,y)]

b. -x P(x) x [-P(x,y)]

a. x P(x) -x [-P(x,y)]

b. x P(x) -x [-P(x,y)]

Kesetaraan Logika Predikat ….

4. a. xP(x) Q x [P(x) Q]

b. xP(x) Q x [P(x) Q]

5. a. xP(x) Q x [P(x) Q]

b. xP(x) Q x [P(x) Q]

Kesetaraan Logika Predikat ….

6. a. xP(x) zQ(z) x z[P(x) Q(z)]

b. xP(x) zQ(z) x z[P(x) Q(z)]

c. xP(x) zQ(z) x z[P(x) Q(z)]

d. xP(x) zQ(z) x z[P(x) Q(z)]

7. a. xP(x) zQ(z) x z[P(x) Q(z)]

b. xP(x) zQ(z) x z[P(x) Q(z)]

c. xP(x) zQ(z) x z[P(x) Q(z)]

d. xP(x) zQ(z) x z[P(x) Q(z)]

Definisi

Bentuk logika predikat dengan proposisi

penyusunnya disebut normal prenex jika dan

hanya jika bentuk tersebut hanya mengandung

perangkai negasi, konjungsi dan disjungsi.

Bentuk Normal Prenex

Menggunakan semua aturan kesetaraan dan

kesamaan logika proposisi dan logika predikat

Contoh 6

Ubahlah bentuk x P(x) x Q(x) dalam bentuk

normal prenex

Penyelesaian

x P(x) x Q(x) = -(x P(x)) x Q(x)

= x (-P(x)) x Q(x)

= x (-P(x)) Q(x))

Bentuk Normal Prenex ….

Soal

Ubahlah bentuk

x y (z (P(x,z) P(y,z)) u Q(u,x,y))

dalam bentuk normal prenex

Bentuk Normal Prenex ….