Kuantifikasi

Ada kalimat yang pasti benar, misal "Bilangan genap adalah bilangan yang habis dibagi 2", kita bisa memastikan bahwa bilangan genap pasti habis dibagi 2.

Ada kalimat yang pasti salah, misal "x + 1 < x", kita bisa memastikan bahwa bilangan berapapun ditambah 1 pasti lebih besar dari bilangan itu sendiri, tidak mungkin lebih kecil.

Ada kalimat yang bisa benar dan bisa salah tergantung input yang diberikan, misal "x - 1 > 3", kalimat ini benar untuk x > 4, dan salah untuk selainnya. Dengan memberikan kuantor kita bisa menentukan nilai kebenaran dari kalimat yang bisa benar dan bisa salah.

A. Kuantor

Terdapat 2 macam kuantor, yaitu universal (∀) dan eksistensial (∃). Kuantor universal menyatakan keseluruhan, misal "Semua, Seluruh". Sedangkan kuantor eksistensial menyatakan sebagian, misal "Ada, Sebagian, Terdapat".

Nilai kebenaran dari kuantor universal: Pernyataan dengan kuantor universal "Semua x" bernilai benar ketika bisa dipastikan semua x memenuhi, dan bernilai salah ketika ada x yang tidak memenuhi.

Sedangkan nilai kebenaran dari kuantor eksistensial: Pernyataan dengan kuantor eksistensial "Ada x" bernilai benar ketika dapat ditemukan x yang memenuhi, dan bernilai salah ketika tidak ada x yang memenuhi.

B. Bentuk kalimat berkuantor

Contoh untuk kuantor universal:

Misalkan ada kalimat "Semua orang menyukai matematika", dapat dinyatakan sebagai berikut:

(∀x).O(x) ⇒ S(x)

Dengan O(x) adalah "orang", dan S(x) adalah "menyukai matematika".

Contoh untuk kuantor eksistensial:

Misalkan ada kalimat "Ada bilangan real yang kuadratnya sama", dapat dinyatakan sebagai berikut:

(∃x).R(x) ∧ S(x)

Dengan R(x) adalah "bilangan real", dan S(x) adalah "kuadratnya sama".

Simbol yang digunakan untuk kuantor universal adalah huruf A besar terbalik, sedangkan simbol yang digunakan untuk kuantor eksistensial adalah huruf E besar terbalik.

Operator logika yang digunakan untuk kuantor universal biasanya implikasi, sedangkan operator logika yang digunakan untuk kuantor eksistensial biasanya konjungsi.

C. Negasi dari kalimat berkuantor

Di dalam menegasikan kalimat berkuantor, banyak digunakan hukum De Morgan, berikut hukum-hukum negasi dari kalimat berkuantor:

Negasi dari "Semua" adalah "Ada", dan negasi dari "Ada" adalah "Semua".

Contoh:

Perlu diketahui bahwa kalimat "Tidak semua x bersifat S" itu semakna dengan kalimat "Ada x yang tidak bersifat S", sebagaimana "Tidak semua lampu berwarna putih" semakna dengan "Ada lampu yang tidak berwarna putih". Ketahui juga bahwa kalimat "Tidak ada x yang bersifat S" itu semakna dengan kalimat "Semua x tidak bersifat S", sebagaimana "Tidak ada lampu yang berwarna hitam" semakna dengan "Semua lampu tidak berwarna hitam".

D. Kalimat dengan lebih dari satu variabel

Kalimat yang memiliki lebih dari 1 variabel, perlu untuk diberikan kuantor pada setiap variabelnya. Misal "Untuk semua x, terdapat y, sehingga (x, y) mempunyai sifat P", yang dapat disimbolkan sebagai berikut:

(∀x)(∃y).P(x,y); catatan: (∀x)(∃y) ≢ (∃x)(∀y)

Perlu diketahui bahwa "Untuk semua x terdapat y" berbeda dengan "Terdapat x untuk semua y", menukar kuantor dapat merubah makna kalimat, oleh karena itu perlu berhati-hati dalam memberi kuantor.

Untuk kalimat dengan variabelnya berkuantor sama, kita dapat menyederhanakan penulisannya dengan menggabung kuantornya. Berikut contohnya:

(∀x)(∀y) dapat disederhanakan menjadi (∀x,y)

(∃x)(∃y) dapat disederhanakan menjadi (∃x,y)

E. Penukaran tempat variabel

Telah diketahui bahwa menukar kuantor tanpa menukar tempat variabel dapat merubah makna kalimat, pada bagian ini kita membahas tentang menukar tempat variabel dan dampaknya terhadap makna kalimat. Berikut aturannya:

• Untuk kuantor sejenis, penukaran tempat variabel tidak merubah makna, disimbolkan sebagai:

            (∀x)(∀y) ≡ (∀y)(∀x)

            (∃x)(∃y) ≡ (∃y)(∃x)

• Untuk kuantor tidak sejenis, penukaran tempat variabel merubah makna, disimbolkan sebagai:

            (∀x)(∃y) ≢ (∃y)(∀x)

            (∃x)(∀y) ≢ (∀y)(∃x)

Jika kita perhatikan, kita mendapati penukaran tempat tanpa menukar kuantor, hal ini juga merubah makna kalimat.

F. Jaminan atau pembatasan

Pernyataan berkuantor dapat menjadi jaminan atau pembatasan. Kuantor universal digunakan untuk membatasi maksimalnya, sedangkan kuantor eksistensial digunakan untuk membatasi minimalnya.

Contoh kuantor eksistensial:

(∃x).P(x)
"Ada paling sedikit satu x yang bersifat P", kalimat ini menjamin adanya x yang mempunyai sifat P, paling sedikit satu.

Contoh kuantor universal:

(∀x,y).P(x) ∧ P(y) ⇒ x = y
"Untuk semua x dan y, jika x dan y bersifat P, maka x sama dengan y", kalimat ini menjamin banyaknya x yang mempunyai sifat P tidak lebih dari satu, jaminannya adalah jika ada y (yang merupakan variabel lain) maka variabel itu sama dengan x.

Jika kita menjaminkankan keduanya menjadi:

(∃x).P(x) ∧ (∀x,y).P(x) ∧ P(y) ⇒ x = y

Ada 2 jaminan sekaligus, yaitu jaminan minimal satu, dan jaminan maksimal satu. Kedua jaminan ini secara bersamaan mengakibatkan jaminan tepat satu, tidak kurang dan tidak lebih menjadi "Ada tepat satu x yang mempunyai sifat P". Khusus untuk tepat satu kita dapat menggunakan kuantor eksistensial diberi tanda seru:

(∃!x).P(x)
Ada tepat satu x yang mempunyai sifat P.

Contoh untuk minimal dua:

(∃x,y).P(x) ∧ P(y) ∧ x ≠ y

"Ada paling sedikit dua x yang mempunyai sifat P", jaminannya paling sedikit ada dua variabel x dan y, dengan x tidak sama dengan y. Hal ini menjamin bahwa tidak kurang dari dua.

Contoh untuk maksimal dua:

(∀x,y,z).P(x) ∧ P(y) ∧ P(z) ⇒ x = y ∨ x = z ∨ y = z

"Ada paling banyak dua x yang mempunyai sifat P", jaminannya adalah jika ada tiga x yang mempunyai sifat P maka diantaranya ada yang sama. Jika kita memberikan jaminan minimal dan maksimal sekaligus, didapatkan jaminan tepat.

Jika kita lihat memang panjang, apalagi untuk yang lebih banyak. Untuk banyak variabel, bentuk minimalnya sebagai berikut:

(∃x₁,x₂,…,x_n).P(x₁) ∧ P(x₂) ∧… ∧P(x_n) ∧(∀i,j).x_i ≠ x_j untuk i, j = 1, 2, …, n

"Ada paling sedikit n x yang mempunyai sifat P", terdapat variabel x sebanyak n, dengan jaminan masing-masing tidak sama.

Adapun bentuk maksimal untuk banyak variabel:

(∀x₁,x₂,…,x_n,x_n+1).P(x₁) ∧ P(x₂) ∧ … ∧ P(x_n) ∧ P(x_n+1) ⇒ (∃i,j).x_i = x_j untuk i, j = 1, 2, …, n, n+1

"Ada paling banyak n x yang mempunyai sifat P", jaminannya adalah jika ada variabel x sebanyak

n + 1 maka diantaranya ada yang sama.

Contoh soal dan pembahasan:

Tonton video quantifier: