Rabu, 01 Februari 2012

KALIMAT BERKUANTOR

 Pada materi Dasar-Dasar Logika telah dibahas kalimat-kalimat yang dihubungkan dengan kata penghubung tertentu. Akan tetapi, kalimat yang dibicarakan tidak memandang banyaknya objek yang terlibat di dalamnya. Dalam bab ini, konsep-konsep logika akan diperluas dengan cara mengikutsertakan jumlah (kuantitas) objek yang terlibat di dalamnya.
 1.  Predikat dan Kalimat Berkuantor
Dalam tata bahasa, predikat menunjuk pada bagian kalimat yang memberi informasi tentang subjek. Sebagai contoh perhatikan kalimat :
“... lebih tebal dari kamus”
 “... terbang ke bulan”
Keduanya merupakan kalimat yang tidak lengkap. Agar menjadi suatu kalimat yang lengkap, haruslah disustitusikan suatu subjek di bagian depan kalimat. Misalnya, jika subjek “Buku ini” disubstitusikan pada kalimat “... lebih tebal dari kamus”, maka kalimat tersebut menjadi “Buku ini lebih tebal dari kamus.”
Dalam ilmu logika, kalimat-kalimat yang memerlukan subyek di sebut Predikat. Jadi, misalkan p:” terbang ke bulan” dan q : “lebih tebal dari kamus”, baik p maupun q adalah predikat-predikat. Untuk menyatakan perlunya substitusi subjek (yang tidak diketahui), maka dituliskan p(x) dan q(y).
Salah satu cara untuk mengubah predikat menjadi suatu kalimat adalah dengan mensubstitusi semua variabelnya dengan nilai-nilai tertentu. Misalkan p(x) : “x habis dibagi 5” dan x disubstitusi dengan 35, maka p(x) menjadi kalimat benar karena 35 habis dibagi 5. Cara lain adalah dengan menambahkan kuantor pada kalimat. Kuantor adalah kata-kata seperti “beberapa”, “semua”, dan lain-lain yang menunjukkan banyaknya elemen yang dibutuhkan agar predikat menjadi benar.
Ada 2 macam kuantor untuk menyatakan jumlah objek yang terlibat, yaitu kuantor universal (simbol ) dan kuantor Eksistensial (simbol ). Kuantor  universal menunjukkan bahwa setiap objek dalam semestanya memiliki sifat kalimat yang menyatakannya.                                  
Misalkan p(x)`: “x dapat mati”. Oleh karena semua manusia dapat mati, maka hal tersebut dinyatakan dengan (x) x manusia x p(x). Jika semestanya sudah jelas, maka objek dapat dihilangkan. Jadi  semesta pembicaraannya sudah jelas, yaitu himpunan manusia-manusia di bumi, maka dituliskan (x) p(x).
(x) p(x) bernilai benar bila dan hanya bila p(x) benar untuk semua x dalam semesta D. (x) p(x) bernilai salah apabila ada x D yang menyebabkan p(x) salah. Harga x yang menyebabkan p(x) salah disebut Contoh Penyangkal (Counter Example).
Kuantor eksistensial menunjukkan bahwa diantara objek-objek dalam semestanya paling sedikit ada satu objek (atau lebih, asal tidak semua) yang memenuhi sifat kalimat yang menyatakannya. Beberapa kata yang digunakan untuk menyebut Kuantor Eksistensial adalah “Terdapat ...”, Beberapa x bersifat ...”, “Ada ...”, Paling sedikit ada satu x ...”.
(x D) q(x) kadang-kadang disingkat (x) q(x)) bernilai benar bila dan hanya bila paling sedikit ada satu x dalam D yang menyebabkan q(x) benar, dan bernilai salah jika untuk semua x D, q(x) bernilai salah.
Variabel  x dalam (x) p(x) disebut variabel bebas karena jika x berubah, maka nilai kebenaran p(x) pada umumnya juga berubah. Sebaliknya, variabel x dalam (x) p(x) merupakan variabel terikat karena nilai (x) p(x) tidak lagi tergantung dari nilai x. Variabel x terikat oleh kuantor .
Contoh :
a.       Misalkan D adalah himpunan bulat.
Buktikan bahwa kalimat ( m D) m2 = m bernilai benar.
b.      Misalkan E adalah himpunan bilangan bulat antara 5 dan 10.
Buktikan bahwa kalimat ( m E) m2 = m bernilai salah.

Penyelesaian :
Kalimat (x) p(x) bernilai benar bila kita dapat menunjukkan bahwa ada satu x (atau lebih) yang memenuhi sifat p.
a.       Untuk m = 1 D, m2 = 12 = 1 = m
Jadi, kalimat (mD) m2 = m benar untuk m = 1
Terbukti bahwa kalimat (m D) m2 = m benar.
b.      Untuk 5 ≤ m ≤ 10, 52 = 25 5 ; 62 = 36 6 ; ... ; 102 = 100 10.
Berarti tidak ada satupun m E yang memenuhi relasi m2 = m. Jadi kalimat (m E) m2 = m salah.

Contoh 2.
Nyatakan kalimat berkuantor di bawah ini dalam bahasa sehari-hari!
a. ( bilangan riil x) x2 0
b. ( bilangan riil x) x2 – 1
c. ( bilangan bulat m) m2 = m
Penyelesaian :
Berikut diberikan beberapa cara untuk menyatakannya:
a.         Semua bilangan riil memiliki kuadrat tak negatif.
Setiap bilangan riil memiliki kuadrat tak negatif.
Sembarangan bilangan riil memiliki kuadrat tak negatif.
x memiliki kuadrat tak negatif untuk setiap bilangan riil x.
Kuadrat dari sembarang bilangan riil tidaklah negatif.
b.        Semua bilangan riil memiliki kuadrat yang tidak sama dengan – 1 .
Tidak ada bilangan riil yang kuadratnya = - 1.
c.         Ada bilangan bulat yang kuadratnya sama dengan bilangan itu sendiri.
Kita dapat menemukan paling sedikit satu bilangan bulat yang sama dengan kuadratnya sendiri.
m2 = m untuk bilangan bulat m.
Beberapa bilangan bulat sama dengan kuadratnya sendiri.
Terdapat bilangan bulat yang kuadratnya sama dengan bilangan itu sendiri.

TUGAS :
Tentukan kebenaran kalimat berikut (semesta pembicaraannya adalah himpunan bilangan bulat)
1.       (x) x2 – 2 0
2.       ( x) x2 – 10x + 21 = 0
3.       ( x) x2 – 10x + 21 = 0
4.       ( x) x2 – 9x + 18 = 0
5.       (x) x2 – 3 = 0
Terjemahkan kalimat berikut menggunakan kuantor atau !
6.       Beberapa orang rajin beribadah.
7.       Semua bayi memiliki wajah yang berbeda.
8.       Setiap bilangan adalah negatif atau memiliki akar riil.
9.       Ada bilangan yang tidak riil.
10.   Tidak semua mobil memiliki karburator.
Untuk tugas dapat mengerjakan semua nomor ganjil atau nomor genap!!!!!
2.  Ingkaran Kalimat Berkuantor
Perhatikan kalimat ini, “Semua penumpang dalam bus yang bertabrakan selamat”. Sering kali orang berpikir bahwa ingkaran/negasi kalimat tersebut adalah “Semua penumpang dalam bus yang bertabrakan tidak selamat” atau “Tidak ada penumpang yang selamat dalam bus yang bertabrakan itu”. Padahal kenyataannya, “Semua penumpang dalam bus yang bertabrakan selamat” dianggap salah (diingkar) apabila ada penumpang yang meninggal (tidak perlu semuanya meninggal). Jadi, sebenarnya ingkaran kalimat mula-mula adalah ”Ada/beberapa penumpang dalam bus yang bertabrakan meninggal”.
Sebaliknya kalimat “Ada penumpang yang selamat dalam kecelakaan bus itu” dikatakan salah (diingkar) jika “Semua penumpang meninggal dalam kecelakaan bus itu”. Secara umum, ingkaran kalimat “Semua x bersifat p(x)” adalah “Ada x yang tidak bersifat p(x)”, dan ingkaran kalimat “Ada x yang bersifat q(x)” adalah “Semua x tidak bersifat q(x)”.

Ø ((xD) p(x))             (xD) Øp(x)
Ø((xD)q(x))      (xD) Øq(x)

Contoh :
Tulislah ingkaran kalimat-kalimat berikut :
a.       Terdapatlah bilangan bulat x sedemikian hingga x2 = 9
b.      Semua dinosaurus telah musnah.
c.       Tidak ada ahli matematika yang malas.
d.      Beberapa bilangan riil adalah rasional.
e.      Semua program Cobol memiliki panjang lebih dari 20 baris.

Penyelesaian :
Untuk lebih memudahkan penyelesaian, terlebih dahulu kalimat ditulis ulang menggunakan kuantor, kemudian barulah dituliskan ingkarannya.
a.       Kalimat mula-mula : ( x bulat) x2 = 9
Ingkaran                     : (x bulat) x2 9
Atau                             : Kuadrat semua bilangan bulat tidak sama dengan 9.
b.      Kalimat mula-mula : (x Dinosaurus) (x telah musnah)
Ingkaran                     :(x Dinosaaurus) (x belum musnah)
Atau                             : Ada Dinosaurus yang belum musnah.
c.       Kalimat mula-mula dapat ditulis “Semua ahli matematika tidak malas” atau (x ahli matematika) (x tidak malas)
Ingkaran                     : (x ahli matematika) (x malas)
Atau                             : Ada ahli matematika yang malas.
d.      Kalimat mula-mula : (x riil)(x = rasional)
Ingkaran                     : (x riil) (x rasional)
Atau                             : Semua bilangan riil tidak rasional
e.      Kalimat  mula-mula: (x program Cobol) (panjang x > 20 baris)
Ingkaran                     : ( x program Cobol) (panjang x 20 baris)
Atau                             : Ada program Cobol yang panjangnya kurang atau sama dengan 20 baris.
TUGAS :
Tulislah kalimat-kalimat di bawah ini dalam simbol logika berkuantor, kemudian tulislah ingkarannya (semestanya adalah himpunan bilangan bulat)!
a.       Untuk setiap x, jika x bilangan genap, maka x2 + x juga genap.
b.      Terdapatlah x sedemikian hingga x bilangan genap dan x bilangan prima.
c.       Untuk setiap x, x2 + 3 > 5 atau x < 2.
d.      Terdapatlah x yang memenuhi relasi x2 = 25 dan x > 0.
e.      Tidak ada x sedemikian sehingga x bilangan prima dan (x + 6) bilangan prima.
 Tugas : pilih dan kerjakan dua soal yang tidak berurutan
3.  Kalimat Berkuantor Ganda
Kalimat berkuantor yang dibahas pada subbab 3.1. dapat diperluas dengan menambahkan beberapa kuantor sekaligus pada kalimat yang sama.
Contoh :
Nyatakan kalimat berikut menggunakan kuantor!
a.       Ada bintang film yang disukai oleh semua orang.
b.      Untuk setiap bilangan positif, terdapatlah bilangan positif lain yang lebih kecil darinya.
c.       Terdapatlah bilangan positif  x  sedemikian hingga untuk semua bilangan positif y, berlakulah y < x.
Penyelesaian :
a.      Misalkan semestanya adalah himpunan semua manusia dan p(x,y) = y menyukai x, maka kalimat dapat dituliskan sebagai (x)(y) p(x,y)
b.      Kalimat mula-mula bisa dinyatakan “Untuk setiap bilangan positif x, terdapatlah bilangan positif y sedemikian sehingga y < x.”
Dalam simbol logika ( bilangan x) ( bilangan positif y) y < x.
Jika semestanya bilangan riil, kalimat tersebut menyatakan bahwa tidak ada bilangan riil positif yang terkecil.
c.       Seperti pada soal (b), dalam simbol logika, kalimat mula-mula dapat dinyatakan sebagai:
( bilangan positif x) ( bilangan positif y) y < x.
Ada 8 cara berbeda dalam menggunakan kuantor dan dalam 2 variabel x dan y, masing-masing adalah :
1.       (x)( y),
2.       (y)( x),
3.       (x)( y),
4.       (y)( x),
5.       (x)( y),
6.       (y)( x),
7.       (y)( x),
8.       (x)( y),
Contoh 2 :
Misalkan p(x,y) : “y adalah ibu dari x”.
Nyatakan arti simbol logika di bawah ini dalam bahasa sehari-hari dan tentukan nilai kebenarannya!
a.       (x)(y) p(x,y)
b.      (y)(x) p(x,y)
Penyelesaian :
a.       Untuk setiap orang x, terdapatlah seorang y sedemikian hingga y adalah ibu dari x. Dengan kata lain, setiap seorang memiliki ibu.
b.      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.

         Jelaslah bahwa kedua pernyataan tersebut memiliki arti yang berbeda. Nilai kebenaran (a) adalah benar, sedangkan (b) adalah salah.
Secara umum, hubungan antara penempatan kuantor ganda adalah :
(x)(y) p(x,y)              Û           (y)( x) p(x,y)
(x)(y) p(x,y)              Û           (y)(x) p(x,y)
(x)(y) p(x,y)              Û           (y)(x) p(x,y)
Ingkaran kalimat berkuantor ganda dilakukan dengan cara yang sama seperti pada ingkaran kalimat berkuantor tunggal.
Ø (x)(y) p(x,y)                     (x)( y) Ø p(x,y)
Ø (x)(y) p(x,y)                     (x)(y) Ø p(x,y)
4.   Aplikasi Logika Matematika dalam Bahasa Pemrogaman
Logika matematika banyak digunakan dalam program-program logika, seperti bahasa prolog. Pelacakan program dalam bahasa Prolog dilakukan secara analog dengan penelusuran logika.
Contoh 1.
Perhatikan tumpukan kotak-kotak berwarna berikut ini!
g

w2
b1

b2
w1

b3

               g    = kotak abu-abu                         ; b1 = kotak biru ke-1
w1 = kotak putih ke – 1                 ; b2 = kotak biru ke – 2
w2 = kotak putih ke – 2                 ; b3 = kotak biru ke – 3
Statemen berikut menggambarkan keadaan tumpukan kotak dan warnanya dalam bahasa Prolog:
Atas (g,b1)         ;               Warna (g,abu-abu)          ;               Warna (b1, biru)
Atas (b1,w1)     ;               Warna (b2,biru)                                ;               Warna (b3, biru)
Atas (w2,b2)     ;               Warna (w1,putih)            ;               Warna (w2, putih)
Atas (b2,b3)     
Atas (x,z)            if             Atas  (x,y)            and        Atas  (y,z)
Statemen Atas (x,y) digunakan untuk menyatakan bahwa dalam tumpukan, kotak x berada di atas kotak y. Statemen warna (x,y) menyatakan bahwa  x berwarna y.
Statemen Atas (x,z) if Atas (x,y) and Atas (y,z) analog dengan pernyataan dalam simbol logika : (Atas (x,y))Ù (Atas (y,z)) Þ Atas (x,z)
Atau dengan kata lain  : Jika x berada di atas y dan y berada di atas z maka x berada di atas z.
LATIHAN :
Apakah jawaban program terhadap pertanyaan-pertanyaan di bawah ini?
a.       ? Warna (b1, biru)
b.      ? Atas (x,w1)
Penyelesaian :
Prolog akan melacak jawaban berdasarkan fakta-fakta yang ada :
a.       Jawaban yes karena sesuai dengan fakta (b1 berwarna biru).
b.      Program menanyakan, untuk blok x yang manakah sehingga predikat “x di atas w1” bernilai benar.
Jawaban yang dikeluarkan adalah x = b1 dan x = g.
Jawaban x = b1 didapatkan dari kenyataan langsung pada blok Atas (b1,w1)
Jawaban x = g didapatkan dari statement:
Atas (g, b1)
Atas (b1, w1)
Atas (x,z) if Atas (x,y) and Atas (y,z)
  TUGAS :
Apakah jawaban program terhadap pertanyaan-pertanyaan di bawah ini?
a.        ? Warna (b3, putih)
b.      ? Warna (g, abu-abu)
c.       ? Atas (x,b3)