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 (∃m∊D) 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)”.
Ø
((∀x∊D) p(x)) ≡ (∃x∊D) Øp(x)
Ø((∃x∊D)q(x)) ≡ (∀x∊D) Ø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)