LOGIKA: Disjungsi eksklusif, operasi logika di dalam komputer, proposiisi bersyarat (implikasi), bikondisional dan inferensi
LOGIKA
Baca juga: LOGIKA (Matematika Diskrit) : Proposisi, Kombinasi proposisi, dan Hukum-hukum logika proposisi
A. Disjungsi Eksklusif
Kata “atau” (or) dalam operasi logika digunakan dalam dua cara. Cara pertama, “atau” digunakan secara inklusif (inclusive or) yaitu dalam bentuk “p atau q atau keduanya”. Artinya, disjungsi dengan operator “atau bernilai benar jika salah satu proporsi atomiknya bernilai benar atau keduanya benar.
Cara kedua,”atau” digunakan secara eksklusif (exclusive or) yaitu dalam bentuk “p atau q tetapi bukan keduanya”. Artinya, disjungsi p dengan q bernilai benar hanya jika salah satu proposisi atomiknya benar (bukan keduanya). Contoh pada sebuah ajang perlombaan pemenang dijanjikan mendapat hadiah. Hadiahnya adalah sebuah televisi 20 inchi. Jika pemenang tidak menginginkan membawa Tv, panitia menggatinya dengan senilai uang. Proposisi untuk masalah ini ditulis sebagai berikut:
“Pemenang lomba mendapat hadiah berupa Tv atau uang”. Artinya, hadiah yang dibawa pulang oleh pemenang hanya salah satu dari uang atau Tv tetapi tidak bisa keduanya
Khusus untuk disjungsi eksklusif kita menggunakan operator logika xor, untuk membedakannya dengan inclusive or, yang definisinya adalah sebagai berikut:
Definisi A.1.1. Misalkan p dan q adalah proposisi. Exclusive or p dan q, dinyatakan dengan notasi p ⨁ q, adalah proposisi yang bernilai benar bila hanya salah satu dari p dan q, selain itu nilainya salah.
Tabel kebenaran untuk operasi exclusive or ditunjukkan pada tabel kebenaran XOR. Dari tabel tersebut dapat dibaca proposisi p ⨁ q hanya jika salah satu, tapi tidak keduanya, dari proposisi atomiknya benar.
Tabel kebenaran XOR
B. Operasi Logika di dalam Komputer
Bahasa pemrograman umumnya menyediakan tipe data boolean untuk data yang bertipe logika, misalnya tipe boolean dalam Bahasa Pascal, logical dalam Bahasa Fortran, dan sebagainya. Tipe data boolean hanya mempunyai dua buah konstanta nilai saja, yaitu true dan false. Peubah yang bertipe boolean disebut peubah boolean (boolean variable). Nilai peubah tersebut hanya true atau false.
Operasi boolean sering digunakan dalam pemrograman. Operasi boolean dinyatakan dalam ekspresi logika (atau dinamakan juga ekpresi boolean).Operator boolean yang digunakan adalah AND, OR, XOR, dan NOT. Ekspresi boolean tersebut hanya menghasilkan salah satu dari dua nilai, true atau false. Misalkan x1, x2, x3, dan x4 adalah peubah boolean di bawah ini adalah valid:
x1 and x2
x1 or (not (x2 and x3))
yang bersesuaian dengan ekspresi logika
x1 ∧ x2
x1 ∨ ∼(x2 ∧ x3)
Operasi lain dalam pemrograman yang bersesuaian dengab operasi logika adalah operasi bit. Komputer merepresentasikan informasi dengan menggunakan bit. Sebuah bit hanya mempunyai dua nilai, yaitu 1 atau 0. Sebuah bit dapat digunakan untuk merepresentasikan true (T) dan 0 untuk merepresentasikan false (F). kita menggunakan notasi ∼,∧,∨, dan ⨁ (disjungsi eksklusif atau setangkup) masing-masing untuk melambangkan operator NOT, AND, OR, dan XOR. Dengan demikian, operasi bit
∼0
1 ∧ 0
0 ∨ 0
1 ⨁ 0
Bersesuaian dengan operasi logika
∼F
T ∧ F
F ∨ F
T ⨁ F
Operasi bit dapat diperluas untuk rangkaian bit yang panjanygnya tetap, misalnya 100110111 dioperasikan dengan 01010101. Operasi ini dinamakan bitwise, dan operasi semacam ini digunakan untuk memanipulasi informasi. Duah buah rangkaian bit yang panjangnya sama dapat dioperasikan dengan salah satu dari operator bitwise di atas, maka setiap bit yang bersesuaian pada masing-masing operand dikenai operasi yang sama. Misalnya,
10011011
01010101
00010001 bitwise AND
11011111 bitwise OR
11001110 bitwise XOR
Aplikasi operasi logika lainnya ditemukan pada mesin pencarian (search engine) di internet. Salah satu mesin pencarian yang terkenal dan banyak digunakan orang adalah Google (www.google.com). Mesin pencarian adalah aplikasi yang sangat penting di internet, karena mesin pencarian mampu menampilkan semua informasi yang kita butuhkan dalam waktu yang cepat.
C. Proposisi Bersyarat (Implikasi)
Selain dalam bentuk konjungsi, disjungsi, dan negasi, proposisi majemuk juga dapat muncul berbentuk “jika p, maka q” seperti pada contoh-contoh berikut:
a. Jika adik lulus, maka ia mendapat hadiah dari ayah.
b. Jika suhu mencapai 90˚C, maka alarm berbunyi.
c. Jika anda tidak mendaftar ulang, maka anda dianggap mengundurkan diri
Pernyataan berbentuk “jika p, maka q” semacam itu disebut proposisi bersyarat atau kondisional atau implikasi.
Definisi C.1.1. Misalkan p dan q adalah proposisi. Proposisi majemuk “jika p, maka q” disebut proposisi bersyarat (implikasi) dan dilambangkan dengan
p → q
Proposisi p disebut hipotesis (atau antesenden atau premis atau kondisi) dan proposisi q disebut konklusi (atau konsekuen).
Implikasi p → q memainkan peranan penting dalam penalaran. Implikasi ini tidak hanya diekspresikan dalam pernyataan standard “jika p, maka q” tetapi juga dapat diekpresikan dalam berbagai cara, antara lain:
a. Jika p, maka q (if p, then q)
b. Jika p, q (if p, q)
c. p mengakibatkan q (p implies q)
d. q jika p (q jika p)
e. p hanya jika q (p only if q)
f. p syarat cukup agar q (p is sufficient for q)
g. q syarat perlu bagi p (q is necessary for p)
h. q bilamana p (q whenever p)
Contoh-contoh berikut memperlihatkan implikasi dalam berbagai ekpsresi serta bagaimana mengubah berbagai bentuk implikasi menjadi bentuk standard “jika p, maka q”.
Contoh C.1
Proposisi-proposisi berikut adalah implikasi dalam berbagai bentuk:
a. Jika hari hujan, maka tanaman akan tumbuh subur.
b. Jika tekanan gas diperbesar, mobil melaju kencang.
c. Es yang mencair di kutub mengakibatkan permukaan air laut naik.
d. Orang itu mau berangkat jika ia diberi ongkos jalan.
e. Ahmad bisa mengambil matakuliah Teori Bahasa Formal hanya jika ia sudah lulus matakuliah Matematika Diskrit.
f. Syarat cukup agar pom bensin meledak adalah percikan api dari rokok.
g. Syarat perlu bagi Indonesia agar ikut Piala Dunia adalah dengan mengontrak pemain asing kenamaan.
h. Banjir bandang terjadi bilamana hutan ditebangi.
Contoh C.2
Ubahlah proposisi c sampai h di dalam contoh G.1 ke dalam bentuk proposisi “jika p, maka q”. Coba kerjakan!
Contoh C.3
x : Anda berusia 17 tahun
y : Anda dapat memperoleh SIM
Nyatakan proposisi berikut ke dalam notasi implikasi:
a. Hanya jika anda berusia 17 tahun, maka anda dapat memperoleh SIM.
b. Syarat cukup agar anda dapat memperoleh SIM adalah anda berusia 17 tahun.
c. Syarat perlu bagi anda dapat memperoleh SIM adalah anda berusia 17 tahun.
d. Jika anda tidak dapat memperoleh SIM, maka anda tidak berusia 17 tahun.
e. Anda tidak dapat memperoleh SIM bilamana anda belum berusia 17 tahun.
Penyelesaian:
a. Pernyataan yang diberikan ekivalen dengan “Anda dapat memperoleh SIM hanya jika anda berusia 17 tahun”. Ingat kembali bahwa p → q bisa dibaca “p hanya jika q”. Jadi, pernyataan yang diberikan dilambangkan dengan y → x.
b. Pernyataan yang diberikan ekivalen dengan “Anda berusia 17 tahun adalah syarat cukup agar anda dapat memperoleh SIM”. Ingat kembali bahwa p → q, bisa dibaca “ p syarat cukup agar q”. Jadi, pernyataan yang diberikan dilambangkan dengan x → y.
c. Pernyataan yang diberikan ekivalen dengan “Anda berusia 17 tahun adalah syarat perlu untuk dapat memperoleh SIM”. Ingat kembali bahwa p → q bisa dibaca “ q syarat perlu bagi p”. Jadi, pernyataan yang diberikan dilambangkan dengan y → x. Dalam konteks ini q adalah x dan p adalah y sehingga dilambangkan y(p) maka x (q).
d. ∼y → ∼x
e. Ingat kembali bahwa p → q bisa dibaca “q bilaman p”. Jadi, pernyataan yang diberikan dilambangkan dengan ∼x → ∼y
Banyak orang bingung mengapa bentuk “p hanya jika q” sama dengan “jika p, maka q”. Untuk menjelaskan hal ini kita harus mengingat bahwa “p hanya jika q” menyatakan bahwa p tidak dapat benar bila q salah. Dengan kata lain, pernyataan “p hanya jika q” salah jika p benar, tetapi q salah. Bila p salah, q dapat salah satu dari benar atau salah, karena pernyataan tersebut tidak menyatakan apa-apa tentang nilai kebenaran q .
Terdapat bentuk lain yang berkaitan dengan p → q, yaitu proposisi sederhana yang merupakan varian dari implikasi. Ketiga variasi proposisi bersyarat tersebut adalah konvers, invers, dan konttraposisi dari proposisi asal p → q.
• Konvers : q → p
• Invers : ∼p → ∼q
• Kontrapoisi : ∼q → ∼p
D. Bikondisional (Bi-implikasi)
Proposisi bersyarat penting lainnya adalah berbentuk “p jika dan hanya jika q” yang dinamakan bikondisional atau bi-implikasi. Definisi bikondisional dikemukakan sebagai berikut:
Definisi D.1.1. Misalkan p dan q adalah proposisi. Proposisi majemuk “p jika dan hanya jika q” disebut bikondisional (bi-implikasi) dan dilambangkan dengan p ↔ q.
Pernyataan p ↔ q adalah benar bila p dan q mempunyai nilai kebenaran yang sama, yakni p ↔ q benar jika p dan q keduanya benar atau p dan q keduanya salah.
Terdapat sejumlah cara untuk menyatakan bikondisional p ↔q dalam kata-kata, yaitu:
a. p jika dan hanya jika q (p if and only if q)
b. p adalah syarat perlu dan cukup untuk q (p is necessary and sufficient for q)
c. Jika p maka q, dan sebaliknya (if p then q, and conversely)
d. p iff q
Contoh D.1
Proposisi majemuk berikut adalah bi-implikasi:
a. 1 + 1 = 2 jika dan hanya jika 2 + 2 = 4
b. Syarat cukup dan syarat perlu agar hari hujan adalah kelembaban udara tinggi
c. Jika anda orang kaya maka anda mempunyai banyak uang, dan sebaliknya
d. Bandung terletak di Jawa Barat iff Jawa Barat adalah sebuah provinsi di Indonesia
Contoh D.2
Tuliskan setiap proposisi berikut ke dalam bentuk “p jika dan hanya jika q”:
a. Jika udara di luar panas maka anda membeli es krim, dan jika anda membeli es krim maka udara di luar panas.
b. Syarat cukup dan perlu agar anda memenangkan pertandingan adalah anda melakukan banyak latihan.
c. Anda naik jabatan jika anda punya koneksi, dan anda punya koneksi jika anda naik jabatan.
d. Jika anda lama menonton televisi maka mata anda lelah,begitu sebaliknya.
e. Kereta api datang terlambat tepat pada hari-hari ketika saya membutuhkannya.
Penyelesaian:
a. Anda membeli es krim jika dan hanya jika udara di luar panas
b. Anda melakukan banyak latihan adalah syarat perlu dan cukup untuk anda memenangkan pertandingan
c. Anda naik jabatan jika dan hanya jika anda punya koneksi.
d. Mata anda lelah jika dan hanya jika anda lama menonton televisi
e. Kereta api datang terlambat jika dan hanya jika saya membutuhkan kereta hari itu
Ingatlah bahwa bikondisional bernilai benar jika kedua proposisi atomiknya mempunyai nilai kebenaran sama. Oleh karena itu, bila kedua proposisi majemuk yang ekivalen di-bikondisional, maka hasilnya adalah tautologi ( Tautologi adalah sebuah keadaan pada proposisi majemuk bernilai benar untuk semua kasus, sedangkan kontradiksi jika salah untuk semua kasus). Hal ini kita nyatakan pada definisi D.1.2 berikut ini.
Definisi D.1.2. Dua buah proposisi majemuk, P(p,q,....) dan Q(p,q,....) disebut ekivalen secara logika, dilambangkan dengan P(p,q,.....)↔ Q(p,q,....), jika p ↔ q adalah tautologi.
Definisi D.1.2 di atas mudah dimengerti. Jika dua proposisi majemuk mempunyai tabel kebenaran yang sama, maka bikondisional terhadap kedua proposisi majemuk tersebut menghasilkan nilai yang semuanya benar, dengan kata lain tautologi.
E. Inferensi
Proses penarikan kesimpulan dari beberapa proposisi disebut inferensi (inference). Di dalam kalkulus proposisi, terdapat sejumlah kaidah inferensi, beberapa di antaranya adalah sebagai berikut:
1. Modus ponen atau law of detachment
Kaidah ini didasarkan pada tautologi (p ∧ (p → q)) → q, yang dalam hal ini, p dan p → q adalah hipotesis, sedangkan q adalah konklusi. Kaidah modus ponen dapat ditulis dengan cara:
p → q
p
∴ q
Simbol ∴ dibaca sebagai “jadi” atau “karena itu”. Modus ponen menyatakan bahwa jika hipotesis p dan implikasi p → q benar, maka konklusi q benar.
Contoh E.1
Misalkan implikasi “Jika 20 habis dibagi 2, maka 20 adalah bilangan genap” dan hipotesis “20 habis dibagi 2” keduang benar. Maka menurt modus ponen, inferensi berikut:
adalah benar. Kita juga dapat menuliskan inferensi di atas sebagai:
∴ 20 adalah bilangan genap
2. Modus Tollen
Kaidah ini didasarkan pada tautologi (∼q ∧ (p → q)) → ~p, kaidah ini modus tollens ditulis dengan cara
P → q
~q
∴ ~p
Contoh E.2
Misalkan implikasi “Jika n bilangan ganjil, maka n2 bernilai ganjil” dan hipotesis “n2 bernilai genap” keduanya benar. Maka menurut modus tollen, inferensi berikut:
∴ n bukan bilangan ganjil
adalah benar
3. Silogisme Hipotesis
Kaidah ini didasarkan pada tautologi ((p → q) ∧ ( q → r)) → (p → r). kaidah silogisme ditulis dengan cara:
p → q
q → r
∴ p → r
Contoh E.3
Misalkan implikasi “Jika saya belajar dengan giat maka saya lulus ujian” dan implikasi “Jika saya lulus ujian, maka saya cepat menikah” adalah benar. Maka menurut kaidah silogisme, inferensi berikut:
∴ Jika saya belajar dengan giat, maka saya cepat menikah
adalah benar
4. Silogisme Disjungtif
Kaidah ini didasarkan pada tautologi ((p ∨ q) ∧ ∼p) → q. kaidah silogisme disjungtif ditulis dengan cara:
p∨ q
∼p
∴ q
Contoh E.4
Inferensi berikut:
menggunakan kaidah silogisme disjungtif, atau dapat ditulis dengan cara:
∴ Saya menikah tahun depan
5. Simplifikasi
Kaidah ini didasarkan pada tautologi (p ∧ q) → p, yang dalam hal ini, p dan q adalah hipotesis, sedangkan p adalah konklusi, kaidah simplifikasi ditulis dengan cara:
p ∧ q
∴ p
Contoh E.5
Penarikan kesimpulan seperti berikut ini:
“Hamid adalah mahasiswa ITB dan mahasiswa Unpar. Karena itu, Hamid adalah mahasiswa ITB.”
menggunakan kaidah simplifikasi, atau dapat juga dengan cara:
Hamid adalah mahasiswa ITB dan mahasiswa Unpar.
∴ Hamid adalah mahasiswa ITB
Simplifikasi berikut juga benar:
“Hamid adalah mahasiswa ITB dan mahasiswa Unpar. Karena itu, Hamid adalah mahasiswa Unpar”
Karena urutan di dalam konjungsi p ∧ q tidak mempunyai pengaruh apa-apa.
6. Penjumlahan
Kaidah ini didasarkan pada tautologi p → (p ∨ q). Kaidah penjumlahan ditulis dengan cara:
p
∴ p ∨ q
Contoh E.6
Penarikan kesimpulan seperti berikut ini:
“Taslim mengambil kuliah Matematika Diskrit. Karena itu, Taslim mengambil kuliah Matematika Diskrit atau mengulang kuliah Algoritma.”
menggunakan kaidah penjumlahan, atau dapat juga ditulis dengan cara:
∴ Taslim mengambil kuliah Matematika Diskrit atau mengulang kuliah Algoritma
7. Konjungsi
Kaidah ini didasarkan pada tautologi ((p) ∧ (q)) → (p ∧ q). kaidah konjungsi ditulis dengan cara:
p
q
Contoh E.7
Penarikan kesimpulan seperti berikut ini:
“Taslim mengambil kuliah Matematika Diskrit. Taslim mengulang kuliah Algoritma. Karena itu, Taslim mengambil kuliah Matematika Diskrit dan mengulang kuliah Algoritma”
menggunakan kaidah konjungsi, atau dapat juga ditulis dengan cara:
Comments
Post a Comment