Negasi Kuantor dan Kuantor Bersarang: ∀x∃y Beda dengan ∃y∀x

Negasi kuantor dikerjakan dengan dua aturan saja: $\neg \forall xP\left(x\right)$ setara dengan $\exists x\neg P\left(x\right)$, dan $\neg \exists xP\left(x\right)$ setara dengan $\forall x\neg P\left(x\right)$. Pada kuantor bersarang, aturan itu dipakai berulang dari kiri ke kanan, sehingga setiap kuantor berganti jenis dan tanda negasi berakhir tepat di depan predikat. Yang paling sering membuat nilai UTS matematika diskrit hilang bukan aturan negasinya, melainkan urutan kuantor: $\forall x\exists y$ dan $\exists y\forall x$ terlihat mirip, tetapi isinya berbeda.

Semua contoh di artikel ini memakai satu predikat, yaitu $S(x,y)$: "x menyukai y", dengan domain tiga orang yang diberi nomor 1, 2, dan 3.

#Apa bedanya ∀x∃y dengan ∃y∀x?

Bacaan masing-masing:

• $\forall x\exists yS(x,y)$: setiap orang menyukai paling sedikit satu orang. Orang yang disukai boleh berbeda untuk tiap x.
• $\exists y\forall xS(x,y)$: ada satu orang yang disukai oleh semua orang. Kali ini y dipilih lebih dulu dan harus sama untuk semua x.

Cara mengingatnya sederhana. Kuantor yang ditulis lebih dulu memilih lebih dulu. Pada $\forall x\exists y$, x dipilih dulu, lalu y boleh menyesuaikan diri dengan x. Pada $\exists y\forall x$, y dikunci dulu dan harus tahan terhadap semua x. Karena itu $\exists y\forall x$ adalah pernyataan yang lebih kuat. Kalau ia benar, $\forall x\exists y$ pasti benar, sebab y yang sama bisa dipakai untuk setiap x. Arah sebaliknya tidak berlaku.

Contoh dengan bilangan: di himpunan bilangan bulat, $\forall x\exists y(x+y=0)$ benar karena setiap x punya lawan $y=-x$. Sebaliknya $\exists y\forall x(x+y=0)$ salah. Tidak ada satu bilangan yang menjadi lawan dari semua bilangan sekaligus.

Dua variabel dan dua jenis kuantor memberi delapan susunan. Empat di antaranya memakai kuantor sejenis ($\forall x\forall y$, $\forall y\forall x$, $\exists x\exists y$, $\exists y\exists x$), dan urutannya tidak berpengaruh. Empat sisanya memakai kuantor campuran, dan keempatnya punya arti yang berbeda:

Baris kedua dan keempat menempatkan y sebagai pihak yang disukai. Posisi variabel di dalam $S(x,y)$ tidak pernah berubah. Yang berubah hanya kuantor mana yang mengikat variabel mana, dan dalam urutan apa.

#Menghitung nilai kebenaran di domain {1, 2, 3}

Misalkan hubungan suka-menyukai di antara tiga orang itu seperti tabel berikut. Baca per baris: baris x, kolom y.

Jadi $S$ benar tepat untuk pasangan (1,1), (1,2), (1,3), (2,1), dan (3,2). Sekarang periksa keempat pernyataan.

1. $\forall x\exists yS(x,y)$. Setiap baris harus punya minimal satu "ya". Baris 1 punya tiga, baris 2 punya di kolom 1, baris 3 punya di kolom 2. Pernyataan ini benar.
2. $\exists y\forall xS(x,y)$. Harus ada satu kolom yang isinya "ya" semua. Kolom 1 gagal di baris 3, kolom 2 gagal di baris 2, kolom 3 gagal di baris 2 dan 3. Pernyataan ini salah.
3. $\exists x\forall yS(x,y)$. Harus ada satu baris yang isinya "ya" semua. Baris 1 memenuhi. Pernyataan ini benar.
4. $\forall y\exists xS(x,y)$. Setiap kolom harus punya minimal satu "ya". Ketiga kolom punya "ya" di baris 1. Pernyataan ini benar.

Pola tabel ini berlaku untuk domain kecil mana pun. $\forall x\exists y$ berarti tiap baris punya "ya". $\exists y\forall x$ berarti ada kolom yang penuh "ya". $\exists x\forall y$ berarti ada baris yang penuh "ya". $\forall y\exists x$ berarti tiap kolom punya "ya".

Pernyataan 1 benar sementara pernyataan 2 salah, padahal keduanya hanya bertukar urutan kuantor. Itu bukti langsung bahwa kuantor campuran tidak boleh ditukar seenaknya.

Coba ubah satu sel. Misalkan orang 3 ternyata tidak menyukai orang 2. Baris 3 menjadi kosong, sehingga pernyataan 1 berubah menjadi salah. Pernyataan 3 dan 4 tetap benar, karena keduanya hanya bergantung pada baris 1 yang tidak disentuh.

#Cara menegasikan kuantor bersarang langkah demi langkah

Dorong tanda negasi ke kanan, satu kuantor setiap langkah. Setiap kali negasi melewati sebuah kuantor, $\forall$ berubah menjadi $\exists$ dan sebaliknya. Berikut negasi pernyataan 2:

Bacaannya: "untuk setiap orang, ada seseorang yang tidak menyukainya". Cek di tabel. Kolom 1 punya "tidak" di baris 3, kolom 2 punya "tidak" di baris 2, kolom 3 punya "tidak" di baris 2. Negasinya benar, cocok dengan pernyataan 2 yang salah. Lakukan pengecekan seperti ini setiap kali domainnya kecil, karena pernyataan dan negasinya harus selalu punya nilai kebenaran yang berlawanan.

Untuk tiga kuantor polanya sama. Ambil definisi kontinuitas fungsi f di titik 0 pada bilangan real, dengan $f\left(0\right)=0$:

Negasinya, yaitu pernyataan bahwa f tidak kontinu di 0:

Tiga hal terjadi sekaligus. Ketiga kuantor berganti jenis. Implikasi $p\to q$ berubah menjadi $p\wedge \neg q$. Tanda pada bagian akhir berubah menjadi $\ge$. Syarat $\epsilon >0$ dan $\delta >0$ tidak ikut dinegasikan, karena syarat itu bagian dari kuantor terbatas, bukan bagian dari klaim yang dibantah.

#Kuantor terbatas: kenapa ∀ berpasangan dengan → dan ∃ dengan ∧

Dengan domain semua orang, kalimat "semua mahasiswa lulus kalkulus" ditulis $\forall x\left(M\right(x)\to L(x\left)\right)$. Kalimat "ada mahasiswa yang lulus kalkulus" ditulis $\exists x\left(M\right(x)\wedge L(x\left)\right)$. Pasangan ini bukan kebiasaan penulisan. Ini keharusan, dan alasannya terlihat kalau pasangannya ditukar:

• $\exists x\left(M\right(x)\to L(x\left)\right)$ langsung bernilai benar begitu ada satu orang yang bukan mahasiswa, sebab implikasi dengan hipotesis salah selalu benar. Kalimatnya jadi tidak mengatakan apa-apa tentang mahasiswa.
• $\forall x\left(M\right(x)\wedge L(x\left)\right)$ mengklaim bahwa semua orang di domain adalah mahasiswa. Jelas bukan itu maksudnya.

Negasinya mengikuti hukum yang sama: $\neg \forall x\left(M\right(x)\to L(x\left)\right)\equiv \exists x\left(M\right(x)\wedge \neg L(x\left)\right)$, yaitu "ada mahasiswa yang tidak lulus kalkulus". Saat $\forall$ berubah menjadi $\exists$, tanda $\to$ ikut berubah menjadi $\wedge$, sehingga pasangan yang benar terjaga dengan sendirinya.

#Menerjemahkan kalimat sehari-hari ke notasi formal

Urutan kerjanya: tentukan domain, beri nama predikat, tandai kata yang menunjukkan kuantor ("setiap", "semua", "ada", "seseorang", "tidak ada"), lalu tentukan siapa yang dipilih lebih dulu. Pada tabel di bawah, domainnya semua orang, $M\left(x\right)$ berarti x mahasiswa, $D\left(y\right)$ berarti y dosen, dan $S(x,y)$ berarti x menyukai y.

Kalimat ketiga biasanya diminta dalam bentuk tanpa negasi di depan. Dorong negasinya masuk:

Baris ketiga memakai ekuivalensi $\neg (p\wedge q)\equiv p\to \neg q$. Hasil akhirnya terbaca "setiap mahasiswa punya paling sedikit satu dosen yang tidak ia sukai". Artinya memang sama dengan kalimat awal, hanya diucapkan dari sisi lain.

Waspadai juga kalimat yang ambigu. "Semua mahasiswa tidak hadir" bisa berarti $\forall x\left(M\right(x)\to \neg H(x\left)\right)$, yaitu tidak ada yang hadir. Bisa juga berarti $\neg \forall x\left(M\right(x)\to H(x\left)\right)$, yaitu tidak semua hadir. Di lembar ujian, tuliskan tafsiran mana yang kamu pakai.

#Kenapa domain bisa mengubah jawaban?

Pernyataan yang sama bisa benar di satu domain dan salah di domain lain:

1. $\forall x\exists y(y>x)$ benar di bilangan bulat, cukup pilih $y=x+1$. Di domain {1, 2, 3} pernyataan ini salah, karena untuk x = 3 tidak ada y yang lebih besar.
2. $\exists x\forall y(x\le y)$ benar di bilangan asli (x = 1, kalau bilangan asli dimulai dari 1). Di bilangan bulat pernyataan ini salah, karena tidak ada bilangan bulat terkecil.
3. $\forall x\exists y(y^2=x)$ salah kalau x dan y sama-sama bilangan real, sebab x = -1 tidak punya akar real. Pernyataan ini menjadi benar kalau x dibatasi pada bilangan real tak negatif.

Jadi soal yang tidak menyebut domain sebenarnya belum lengkap. Kalau soalnya memang tidak menyebutkan, tulis asumsi domainmu di jawaban.

#Kesalahan yang sering terjadi saat ujian

1. Hanya mengganti kuantor pertama. $\neg \forall x\exists yP(x,y)$ ditulis menjadi $\exists x\exists y\neg P(x,y)$. Negasi harus melewati semua kuantor, jadi jawaban yang benar $\exists x\forall y\neg P(x,y)$.
2. Menukar urutan variabel saat menegasikan. Urutan x lalu y harus tetap. Yang berubah hanya jenis kuantornya.
3. Ikut menegasikan syarat kuantor terbatas, misalnya mengubah $\forall \epsilon >0$ menjadi $\exists \epsilon \le 0$.
4. Menegasikan $p\to q$ menjadi $\neg p\to \neg q$ atau $p\to \neg q$. Yang benar $p\wedge \neg q$.
5. Membaca $\exists$ sebagai "tepat satu". $\exists$ berarti paling sedikit satu. Kalau soal meminta tepat satu, pakai $\exists !$ atau tuliskan syarat keunikannya.
6. Menyimpulkan $\exists y\forall x$ dari $\forall x\exists y$. Tabel di atas sudah menunjukkan bahwa yang kedua bisa benar sementara yang pertama salah.

Logika kuantor dipakai lagi di bab himpunan. Membuktikan $A\subseteq B$ pada dasarnya adalah membuktikan $\forall x(x\in A\to x\in B)$, dan langkahnya dibahas di cara membuktikan identitas himpunan. Untuk berlatih menyusun langkah logis dalam bentuk algoritma, lihat flowchart dan pseudocode tugas algoritma. Kalau UTS matematika diskrit tinggal beberapa hari, strategi belajar UTS dan UAS bisa membantu membagi waktunya.

#FAQ

#Apakah ∀x∀y sama dengan ∀y∀x?

Ya. Dua kuantor sejenis yang berurutan boleh ditukar. Hal yang sama berlaku untuk $\exists x\exists y$ dan $\exists y\exists x$. Larangan menukar hanya berlaku untuk kuantor campuran.

#Apa negasi dari "setiap orang punya teman"?

Dengan $T(x,y)$ berarti y teman x, kalimatnya $\forall x\exists yT(x,y)$. Negasinya $\exists x\forall y\neg T(x,y)$, yaitu "ada orang yang tidak berteman dengan siapa pun".

#Kenapa ∃y∀x mengakibatkan ∀x∃y, tetapi tidak sebaliknya?

Kalau ada satu y yang cocok untuk semua x, y itu juga bisa dipakai sebagai jawaban untuk setiap x secara terpisah. Sebaliknya, tiap x boleh punya pasangan y yang berbeda-beda, sehingga belum tentu ada satu y yang cocok untuk semuanya.

#Bagaimana menulis "tepat satu" dengan kuantor biasa?

$\exists !xP\left(x\right)$ setara dengan $\exists x\left(P\right(x)\wedge \forall y(P\left(y\right)\to y=x\left)\right)$. Bagian pertama menjamin ada, bagian kedua menjamin bahwa semua yang memenuhi P adalah x itu sendiri.

#Apakah negasi dari ∀x P(x) sama dengan ∀x ¬P(x)?

Tidak. $\neg \forall xP\left(x\right)$ berarti tidak semua memenuhi P, cukup ada satu pengecualian. $\forall x\neg P\left(x\right)$ berarti tidak ada satu pun yang memenuhi P. Kalimat "tidak semua mahasiswa hadir" dan "semua mahasiswa tidak hadir" berbeda karena alasan ini.

#Bolehkah huruf variabel yang sama dipakai di dua kuantor?

Secara formal boleh. $\forall xP\left(x\right)\wedge \exists xQ\left(x\right)$ sah karena kedua x terikat pada kuantor yang berbeda. Namun lebih aman ganti salah satunya menjadi y, supaya kamu tidak salah membaca saat menegasikan.