Matematika Diskrit : Kalimat Berkuantor

Kalimat Berkuantor Ganda

Yaitu terdapat beberapa kuantor sekaligus pada kalimat yang sama.

Ada 8 cara berbeda dalam menggunakan 2 kuantor ∀ dan ∃ dalam 2 variabel x dan y. Masing-masing adalah (∀x)(∀y), (∀y)(∀x), (∃x)(∃y), (∃y)(∃x), (∀x)(∃y), (∃y)(∀x), (∀y)(∃x), (∃x)(∀y).

Jika kuantornya sama, maka urutan penulisan kuantor-kuantor tersebut bisa dibalik. Akan tetapi, jika kuantornya berbeda, urutan penulisannya tidak selalu dapat dibalik.

Misalkan p(x,y):= y adalah ibu dari x.

Maka (∀x)(∃y) P(x,y) dapat berarti untuk setiap orang x, terdapatlah seorang y, hingga y adalah ibu dari x. Dengan kata lain, setiap orang mempunyai ibu.

Sedangkan (∃y)(∀x) P(x,y) terdapatlah seorang y sehingga untuk semua orang x, y adalah ibu dari x. Dengan kata lain, ada seseorang yang merupakan ibu dari semua orang di dunia ini.

---

Contoh 1

1. Ada bintang film yang disukai oleh semua orang
2. Untuk setiap bilangan positif, terdapat bilangan positif lain yang lebih kecil darinya
3. Terdapat bilangan positif x sedemikian hingga untuk semua bilangan positif y berlaku y < x.

Kalimat tersebut bila dituliskan menggunakan kuantor menjadi sebagai berikut :

1. Misalkan semestanya adalah himpunan semua manusia dan P(x,y) := y menyukai x. Maka kalimat dapat dituliskan menjadi (∃x)(∀y) P(x,y)
2. D = {x | x adalah bilangan positif} sebagai domain untuk variabel x, juga untuk variabel y. P(x,y) := y < x → (∀x)(∃y) P(x,y)
3. D = {x | x adalah bilangan positif} sebagai domain untuk variabel x, juga untuk variabel y. P(x,y) := y < x → (∃x)(∀y) P(x,y)

---

Contoh 2

Ubah kalimat ‘Setiap orang memiliki teman akrab’ menjadi kalimat logika predikat.

Karena teman merupakan sebuah hubungan antara dua orang, maka di sini dibutuhkan dua variabel x dan y.

Ambil D = {x | x adalah orang} sebagai domain untuk variabel x, juga untuk variabel y, dan predikat A(x, y) := y adalah teman akrab dari x.

Jadi, kalimat logika predikat untuk kalimat tersebut adalah :

∀x∈D(∃y∈D A(x, y)) atau ∀x (∃y A(x, y)) atau ∀x ∃y A(x, y)

dengan A(x, y) sebagai scope untuk ∃y, dan x masih berupa variabel bebas.

∃y A(x, y) sebagai scope untuk ∀x, dan tidak ada lagi variabel bebas.

---

Contoh 3

Ubah kalimat ‘Jika ia adalah seorang wanita dan ia memiliki anak, maka ia adalah seorang ibu’
menjadi kalimat logika predikat.

Ambil D = {x | x adalah orang}, dan predikat

W(x) := x adalah seorang wanita,

A(x) := x memiliki anak,

I(x) := x adalah seorang ibu,

Maka kalimat di atas dapat diubah menjadi kalimat berikut:

∀x ((W(x) ∧ A(x)) → I(x)).

Atau ambil predikat A(y, x) := y adalah anak dari x,

Kalimat di atas dapat diubah menjadi kalimat logika predikat berikut:
∀x ((W(x) ∧ ∃y A(y, x)) → I(x)).

---

Kebenaran Kalimat Berkuantor

∀x P(x) bernilai T, apabila P(x) bernilai T untuk setiap x ∈ D,

∀x P(x) bernilai F, apabila P(x) bernilai F untuk suatu x ∈ D.

∃x P(x) bernilai T, apabila P(x) bernilai T untuk suatu x ∈ D,

∃x P(x) bernilai F, apabila P(x) bernilai F untuk setiap x ∈ D.

∀x ∀y P(x, y) bernilai T apabila P(x, y) bernilai T untuk setiap pasang x ∈ D_x dan y ∈ D_y,

∀x ∀y P(x, y) bernilai F apabila P(x, y) bernilai F untuk suatu pasang x ∈ D_x dan y ∈ D_y.

∀y ∀x P(x, y) bernilai T apabila P(x, y) bernilai T untuk setiap pasang y ∈ D_y dan x ∈ D_x,

∀y ∀x P(x, y) bernilai F apabila P(x, y) bernilai F untuk suatu pasang y ∈ D_y dan x ∈ D_x.

∀x ∃y P(x, y) bernilai T apabila untuk setiap x ∈ D_x terdapat y ∈ D_y, sehingga P(x, y) bernilai T,

∀x ∃y P(x, y) bernilai F apabila untuk suatu x ∈ D_x , sehingga P(x, y) bernilai F untuk setiap y ∈ D_y.

∀y ∃x P(x, y) bernilai T apabila untuk setiap y ∈ D_y terdapat x ∈ D_x, sehingga P(x, y) bernilai T,

∀y ∃x P(x, y) bernilai F apabila untuk suatu y ∈ D_y , sehingga P(x, y) bernilai F untuk setiap x ∈ D_x.

∃x ∀y P(x, y) bernilai T, apabila terdapat suatu x ∈ D_x sehingga P(x, y) bernilai T untuk setiap y ∈ D_y,

∃x ∀y P(x, y) bernilai F, apabila untuk setiap x ∈ D_x terdapat suatu y ∈ D_y, sehingga P(x, y) bernilai F.

∃y ∀x P(x, y) bernilai T, apabila terdapat suatu y ∈ D_y sehingga P(x, y) bernilai T untuk setiap x ∈ D_x,

∃y ∀x P(x, y) bernilai F, apabila untuk setiap y ∈ D_y terdapat suatu x ∈ D_x, sehingga P(x, y) bernilai F.

∃x ∃y P(x, y) bernilai T apabila terdapat suatu pasang x ∈ D_x dan y ∈ D_y sehingga P(x, y) bernilai T

∃x ∃y P(x, y) bernilai F, apabila untuk setiap pasang x ∈ D_x dan y ∈ D_y, P(x, y) bernilai F.

∃y ∃x P(x, y) bernilai T apabila terdapat suatu pasang y ∈ D_y dan x ∈ D_x sehingga P(x, y) bernilai T

∃y ∃x P(x, y) bernilai F, apabila untuk setiap pasang y ∈ D_y dan x ∈ D_x, P(x, y) bernilai F.

---

Contoh 1

Misalkan Q(x, y) := x + y = y + x, tentukan nilai kebenaran dari ∀x ∀y Q(x, y).

Di sini, dimisalkan bahwa domain untuk variabel x maupun y adalah himpunan bilangan real.

∀x ∀y Q(x, y) berbunyi:

‘ Untuk setiap pasang bilangan real x dan y berlaku x + y = y + x ’, maka berdasarkan sifat penjumlahan bilangan real diperoleh, ∀x ∀y Q(x, y) bernilai T.

---

Contoh 2

Misalkan Q(x, y) := x + y = 0, tentukan nilai kebenaran dari ∀x ∃y Q(x, y) dan ∃y ∀x Q(x, y).

Di sini, dimisalkan bahwa domain untuk variabel x maupun y adalah himpunan bilangan real.

∀x ∃y Q(x, y) berbunyi: ‘ Untuk setiap bilangan real x terdapat bilangan real y sehingga x + y = 0 ’,

Maka berdasarkan sifat penjumlahan bilangan real diperoleh,

∀x ∃y Q(x, y) bernilai T.

Sedangkan ∃y ∀x Q(x, y) berbunyi: Terdapat bilangan real y sehingga untuk setiap bilangan real x berlaku x + y = 0,

Maka berdasarkan sifat penjumlahan bilangan real diperoleh, ∃y ∀x Q(x, y) bernilai F.

---

Contoh 3

Misalkan Q(x, y, z) := x + y = z, tentukan nilai kebenaran dari ∀x ∀y ∃z Q(x, y, z) dan ∃z ∀x ∀y Q(x, y, z).

Di sini, dimisalkan bahwa domain untuk variabel x, y maupun z adalah himpunan bilangan real.

∀x ∀y ∃z Q(x, y, z) berbunyi: ‘Untuk setiap pasang bilangan real x dan y terdapat z sehingga berlaku x + y = z’.

Maka berdasarkan sifat penjumlahan bilangan real diperoleh, ∀x ∀y ∃z Q(x, y, z) bernilai T.

Sedangkan ∃z ∀x ∀y Q(x, y, z) berbunyi: ‘Terdapat bilangan real z, sehingga untuk setiap pasang bilangan real x dan y berlaku x + y = z’.

Maka berdasarkan sifat penjumlahan bilangan real, diperoleh ∃z ∀x ∀y Q(x, y, z) bernilai F.

---

Ingkaran Kalimat Berkuantor

¬ ∀x P(x) ⇔ ∃x ¬ P(x)

¬ ∃x P(x) ⇔ ∀x ¬ P(x)

---

Contoh

Kalimat “Semua penumpang dalam bis yang bertabrakan selamat”.

Ingkarannya “Ada/beberapa penumpang dalam bis yang bertabrakan itu tidak selamat”.

Sebaliknya, “Ada penumpang yang selamat dalam kecelakaan bis itu”

Ingkarannya “Semua penumpang meninggal dalam kecelakaan bis itu”.

---

Ingkaran Kalimat Berkuantor Ganda

~(∀𝑥 ∃𝑦 𝑃(𝑥, 𝑦)) ≡ ∃𝑥∀𝑦~𝑃(𝑥, 𝑦)

~(∃𝑥∀𝑦 𝑃(𝑥, 𝑦)) ≡ ∀𝑥∃𝑦~𝑃(𝑥, 𝑦)

---

Contoh

Kalimat “Untuk setiap persegi x, terdapat lingkaran y sehingga x dan y memiliki warna sama.”

Ingkarannya “Terdapat sebuah persegi x sedemikian sehingga untuk setiap lingkaran y, x dan y memiliki warna yang berbeda.”

Sebaliknya, “Terdapat sebuah segitiga x sehingga untuk setiap persegi y, x berada di kanan y.”

Ingkarannya “Untuk setiap segitiga x, terdapat suatu persegi y dimana x tidak berada di kanan y.”

---

Aturan Inferensi Kalimat Berkuantor

Sebagaimana aturan inferensi (rule of inference) untuk kalimat-kalimat logika proposisi, terdapat pula aturan inferensi untuk kalimat-kalimat yang berkuantifikasi.

Universal instantiation

Universal generalization

Existential instantiation

Existential generalization

---

Contoh 1

Tunjukkan bahwa argumentasi berikut adalah absah:

Hipotesa:

(i) Semua mahasiswa di kelas ini sudah pernah belajar Kalkulus.

(ii) Marla adalah mahasiswa di kelas ini.

Konklusi:

Marla sudah pernah belajar Kalkulus.

Solusi:

Tuliskan argumentasi tersebut dalam kalimat predikat. Misalkan

K(x) := x adalah mahasiswa di kelas ini.

M(x) := x sudah pernah belajar Kalkulus.

dengan domain untuk x adalah himpunan semua orang.

Maka

hipotesa (i) menjadi ∀x (K(x) → M(x))

hipotesa (ii) menjadi K(Marla)

konklusi M(Marla).

Jadi harus ditunjukkan bahwa apabila ∀x (K(x) → M(x)) dan K(Marla) bernilai benar maka konklusi M(Marla) juga benar.

Hal ini ditunjukkan sebagai berikut:

Jadi konklusinya, yaitu M(Marla), adalah benar

---

Contoh 2

Tunjukkan bahwa argumentasi berikut adalah absah:

Hipotesa:

(i) Seorang murid di kelas ini belum membaca buku.

(ii) Setiap orang di kelas ini lulus UTS.

Konklusi:

Seseorang yang sudah lulus UTS belum membaca buku.

Solusi:

Tuliskan argumentasi tersebut dalam logika predikat. Misalkan

K(x) := x adalah murid di kelas ini
R(x) := x sudah membaca buku
P(x) := x lulus UTS

dengan domain untuk x adalah himpunan semua orang.

Maka

hipotesa (i) menjadi ∃x (K(x) ∧ ¬R(x))

hipotesa (ii) menjadi ∀x (K(x) → P(x))

konklusi ∃x (P(x) ∧ ¬ R(x))

Jadi harus ditunjukkan bahwa apabila

∃x (P(x) ∧ ¬ R(x)) dan ∀x (K(x) → P(x)) bernilai benar

maka konklusi ∃x (P(x) ∧ ¬R(x)) juga benar.

Hal ini ditunjukkan sebagai berikut:

Jadi konklusinya, yaitu ∃x (P(x) ∧ ¬R(x)), adalah benar.

---

Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Matematika Diskrit – Logika, daftar lengkapnya adalah sebagai berikut.

---

Tonton juga video pilihan dari kami berikut ini