Matematika Diskrit : Predikat dan Kuantifikasi

📋 Daftar Isi

Predikat

“James adalah mahasiswa Politeknik Statistika STIS” adalah sebuah proposisi.

Kalimat tersebut dapat diubah menjadi predikat/fungsi proposisi/kalimat terbuka.

𝑃(𝑥) : 𝑥 adalah mahasiswa Politeknik Statistika STIS.

𝑄(𝑥, 𝑦) : 𝑥 adalah mahasiswa 𝑦.

𝑃 𝑑𝑎𝑛 𝑄 disebut simbol predikat. 𝑥 𝑑𝑎𝑛 𝑦 disebut variabel predikat.

Predikat adalah kalimat yang berisi sejumlah variabel predikat dan menjadi proposisi ketika nilai tertentu disubstitusi ke variabel predikat. Himpunan semua nilai yang dapat digunakan sebagai pengganti variabel predikat disebut domain variabel predikat.

Contoh

Jika P(x):= x > 3 dengan himpunan bilangan bulat sebagai domain D, maka P(4) bernilai T dan P(2) bernilai F.
Jika Q(x, y):= x = y + 3 dengan domain R x R, maka Q(1, 2) bernilai F dan Q(3,0) bernilai T.
Jika R(x, y, z):= x + y = z dengan domain R x R x R, maka R(1, 2, 3) bernilai T dan R(0, 0, 3) bernilai F.
Jika S(x, y):= x mengambil matakuliah y dengan domain Mhs x MK, maka S(A, MD) bernilai T bila mahasiswa A mengambil matakuliah MD, dan S(A, MD) bernilai F bila mahasiswa A tidak mengambil matakuliah MD.

Kuantifikasi

Cara lain adalah dengan menambahkan kuantor, yaitu kata-kata seperti “beberapa”, “semua”, dan lain-lain yang menunjukkan berapa banyak elemen yang dibutuhkan agar predikat menjadi benar.

Ada dua macam kuantifikasi untuk setiap variabel dalam sebuah predikat, yaitu:

Kuantifikasi universal (universal quantification)
Kuantifikasi eksitensi (exsistential quantification)

Definisi

Kuantifikasi universal untuk predikat P(x) adalah proposisi berikut:

‘P(x) bernilai T untuk setiap (semua) elemen x di domain D‘

Ditulis: ∀x∈D P(x) atau ∀x P(x) saja, bila D sudah jelas.

P(x) disebut sebagai scope untuk kuantifikasi ∀x tersebut.

Dibaca: Untuk setiap (semua) x di D, berlaku P(x) atau P(x) bernilai true

Definisi

Kuantifikasi eksistensi untuk predikat P(x) adalah proposisi berikut

‘P(x) bernilai T untuk suatu elemen x di domain D’.

Ditulis: ∃x∈D P(x) atau ∃x P(x) saja, bila domain D sudah jelas.

P(x) disebut sebagai scope untuk kuatifikasi ∃x tersebut.

Dibaca: Terdapat suatu x sehingga berlaku P(x), atau

Paling sedikit ada satu x sehingga P(x).

Variabel terikat (bind variable) dan variabel bebas (free variable)
Variabel x pada P(x) disebut sebagai variabel terikat bila

x telah diikat oleh suatu kuantifikasi ∀x atau ∃x, atau
x telah digantikan oleh sebuah elemen tertentu dari domain D.

Variabel x pada P(x) disebut sebagai variabel bebas bila x tidak terikat

Definisi

Sebuah predikat P(x, y, z) pada sebuah domain D_x x D_y x D_z, akan menjadi sebuah proposisi apabila semua variabel padanya, yaitu x, y, dan z merupakan variabel terikat. Jadi, proposisi-proposisi yang mungkin adalah:

∀x∈D_x ∀y∈D_y ∀z∈D_z P(x, y, z) atau

∀x∈D_x ∀y∈D_y ∃z∈D_z P(x, y, z) atau

∀x∈D_x ∃y∈D_y ∀z∈D_z P(x, y, z) atau

∃x∈D_x ∀y∈D_y ∀z∈D_z P(x, y, z) atau

∃x∈D_x ∃y∈D_y ∀z∈D_z P(x, y, z) atau

∃x∈D_x ∀y∈D_y ∃z∈D_z P(x, y, z) atau

∀x∈D_x ∃y∈D_y ∃z∈D_z P(x, y, z) atau

∃x∈D_x ∃y∈D_y ∃z∈D_z P(x, y, z)

Contoh 1

Dengan domain D = {x | x adalah bilangan real} dan

P(x) := x + 1 > x,

Maka ∀x P(x) berbunyi sebagai ‘ Untuk setiap bilangan real x berlaku x + 1 > x ’. Dan ∀x P(x) bernilai T.

Contoh 2

Dengan domain D = {x | x adalah bilangan real} dan P(x) := 2 > x

Maka ∀x P(x) berbunyi sebagai ‘Untuk setiap bilangan real x, berlaku 2 > x’.

Jadi ∀x P(x) bernilai F.

Bila domainnya adalah D = {x | x adalah bilangan real negatif}, maka ∀x P(x) berbunyi sebagai

‘Untuk setiap bilangan real negatif x, berlaku 2 > x’.

Jadi ∀x P(x) bernilai T.

Catatan : Bila domain untuk variabel x berhingga, yaitu D = {x₁, x₂, … … , x_n}, maka ∀x P(x) sama artinya dengan P(x₁) ∧ P(x₂) ∧ …… ∧ P(x_n).

Contoh 3

Misalkan D = {x | x domain untuk variabel x adalah adalah bilangan bulat positif yang lebih kecil dari 5}, dan P(x) : x²< 10

Maka ∀x P(x) sama artinya dengan P(1) ∧ P(2) ∧ P(3) ∧ P(4),

P(1) := 1² < 10 bernilai T, P(2) := 2² < 10 bernilai T,

P(3) := 3² < 10 bernilai T, P(4) := 4² < 10 bernilai F,

maka ∀x P(x) bernilai F.

Contoh 4

Misalkan P(x) := x > 3 dengan domain D = {x | x adalah bilangan real},

maka ∃x P(x) berbunyi ‘ Terdapat bilangan real x sehingga x > 3 ’.

Karena P(4) bernilai T, maka ∃x P(x) bernilai T.

Contoh 5

Misalkan P(x) := x = x + 1 dengan domain D = {x | x = bilangan real},

Maka ∃x P(x) berbunyi ‘ Terdapat bilangan real x sehingga x = x + 1 ’.

Karena x = x + 1 bernilai F untuk setiap bilangan real x, maka ∃x P(x) bernilai F.

Catatan: Bila domain untuk variabel x berhingga, yaitu D = {x₁, x₂, … … , x_n}, maka ∃x P(x) sama artinya dengan P(x₁) ∨ P(x₂) ∨ …… ∨ P(x_n)

Contoh 6

Misalkan domain untuk variabel x adalah D = {x | x adalah bilangan bulat positif yang lebih kecil dari 5}, dan P(x) := x²< 10

Maka ∃x P(x) sama artinya dengan P(1) ∨ P(2) ∨ P(3) ∨ P(4)

Karena P(1) := 1² < 10 bernilai T, maka ∃x P(x) bernilai T.

Contoh 7

Nyatakan proposisi berikut sebagai predikat: ‘Setiap mahasiswa dalam kelas ini mengambil mata kuliah Matematika Diskret’.

Jawaban:
Pertama-tama tentukan dahulu variabel-variabel yang dibutuhkan beserta domainnya, kemudian tentukan predikat dalam variabel-variabel tersebut, dan terakhir berikan kuatifikasi yang sesuai.

(a) Ambil x sebagai variabel, dan domain

D = {x: x adalah mahasiswa dalam kelas ini}

P(x) := x mengambil mata kuliah Matematika Diskret

Maka kalimat di atas dapat dinyatakan dalam bentuk ∀x P(x).

Atau

(b) Ambil

D = {x : x adalah mahasiswa}

Q(x) := x berada dalam kelas ini

P(x) := x mengambil mata kuliah Matematika Diskret

Maka kalimat di atas dapat dinyatakan ∀x (Q(x) → P(x)).