BAB
I
PEMBAHASAN
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 (∃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)
a.
(∀x) x2 – 2 ≥ 0
b.
(∃ x) x2 – 10x + 21 = 0
c.
(∀ x) x2 – 10x + 21 = 0
d.
(∀ x) x2 – 9x + 18 = 0
e.
(∃x) x2 – 3 = 0
Terjemahkan kalimat berikut
menggunakan kuantor ∀ atau ∃ !
a.
Beberapa
orang rajin beribadah.
b.
Semua
bayi memiliki wajah yang berbeda.
c.
Setiap
bilangan adalah negatif atau memiliki akar riil.
d.
Ada
bilangan yang tidak riil.
e.
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)
Tidak ada komentar:
Posting Komentar