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 โˆˆ Dx dan y โˆˆ Dy,

โˆ€x โˆ€y P(x, y) bernilai F apabila P(x, y) bernilai F untuk suatu pasang x โˆˆ Dx dan y โˆˆ Dy.

โˆ€y โˆ€x P(x, y) bernilai T apabila P(x, y) bernilai T untuk setiap pasang y โˆˆ Dy dan x โˆˆ Dx,

โˆ€y โˆ€x P(x, y) bernilai F apabila P(x, y) bernilai F untuk suatu pasang y โˆˆ Dy dan x โˆˆ Dx.

โˆ€x โˆƒy P(x, y) bernilai T apabila untuk setiap x โˆˆ Dx terdapat y โˆˆ Dy, sehingga P(x, y) bernilai T,

โˆ€x โˆƒy P(x, y) bernilai F apabila untuk suatu x โˆˆ Dx , sehingga P(x, y) bernilai F untuk setiap y โˆˆ Dy.

โˆ€y โˆƒx P(x, y) bernilai T apabila untuk setiap y โˆˆ Dy terdapat x โˆˆ Dx, sehingga P(x, y) bernilai T,

โˆ€y โˆƒx P(x, y) bernilai F apabila untuk suatu y โˆˆ Dy , sehingga P(x, y) bernilai F untuk setiap x โˆˆ Dx.

โˆƒx โˆ€y P(x, y) bernilai T, apabila terdapat suatu x โˆˆ Dx sehingga P(x, y) bernilai T untuk setiap y โˆˆ Dy,

โˆƒx โˆ€y P(x, y) bernilai F, apabila untuk setiap x โˆˆ Dx terdapat suatu y โˆˆ Dy, sehingga P(x, y) bernilai F.

โˆƒy โˆ€x P(x, y) bernilai T, apabila terdapat suatu y โˆˆ Dy sehingga P(x, y) bernilai T untuk setiap x โˆˆ Dx,

โˆƒy โˆ€x P(x, y) bernilai F, apabila untuk setiap y โˆˆ Dy terdapat suatu x โˆˆ Dx, sehingga P(x, y) bernilai F.

โˆƒx โˆƒy P(x, y) bernilai T apabila terdapat suatu pasang x โˆˆ Dx dan y โˆˆ Dy sehingga P(x, y) bernilai T

โˆƒx โˆƒy P(x, y) bernilai F, apabila untuk setiap pasang x โˆˆ Dx dan y โˆˆ Dy, P(x, y) bernilai F.

โˆƒy โˆƒx P(x, y) bernilai T apabila terdapat suatu pasang y โˆˆ Dy dan x โˆˆ Dx sehingga P(x, y) bernilai T

โˆƒy โˆƒx P(x, y) bernilai F, apabila untuk setiap pasang y โˆˆ Dy dan x โˆˆ Dx, 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

\[ \frac{\forall x \space P(x) }{\therefore \space P(c) \space untuk \space sembarang \space elemen \space c} \]

Universal generalization

\[ \frac{P(c) \space untuk \space sembarang \space elemen \space c }{\therefore \space \forall x \space P(x) \space \space \space \space \space \space} \]

Existential instantiation

\[ \frac{ \exists x \space P(x) }{\therefore \space P(c) \space untuk \space suatu \space elemen \space c } \]

Existential generalization

\[\frac{ P(c) \space untuk \space suatu \space elemen \space c }{\therefore \space \exists x \space P(x) } \]

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:

1. โˆ€x (K(x) โ†’ M(x))

2. K(Marla)

3. K(Marla) โ†’ M(Marla)

4. M(Marla)

hipotesa (i)

hipotesa (ii)

universal instantiation diterapkan pada step 1

modus ponen diterapkan pada step 2 dan step 3

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:

โˆƒx (K(x) โˆง ยฌR(x))

โˆ€x (K(x) โ†’ P(x))

K(a) โˆง ยฌR(a)

K(a) โ†’ P(a)

K(a)

ยฌR(a)

P(a)

P(a) โˆง ยฌ R(a)

โˆƒx (P(x) โˆง ยฌ R(x))

hipotesa (i)

hipotesa (ii)

existential instantiation diterapkan pada step 1

universal instantiation diterapkan pada step 2

simplification diterapkan pada step 3

simplification diterapkan pada step 3

modus ponen diterapkan pada step 4 dan step 5

conjunction diterapkan pada step 7 dan step 6

existential generalization diterapkan pada step 8

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

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up