๐ Daftar Isi
Logika
Ilmu logika berhubungan dengan kalimat-kalimat (argumen-argumen) dan hubungan yang ada di antara kalimat-kalimat tersebut.
Hukum-hukum logika membantu kita membedakan antara argumen yang valid dan tidak valid. Logika juga digunakan untuk membuktikan teorema-teorema di dalam matematika.
Dalam ilmu komputer, logika diaplikasikan dalam bidang pemrograman, analisis kebenaran algoritma, kecerdasan buatan, perancangan komputer, dan sebagainya.
Proposisi
Proposisi (proposition) adalah kalimat deklaratif yang bernilai benar (true) atau salah (false), tetapi tidak dapat sekaligus keduanya. Kebenaran atau kesalahan dari sebuah kalimat disebut nilai kebenaran (truth value).
Secara simbolik, proposisi biasanya dilambangkan dengan huruf kecil seperti p, q, r, โฆ.
Misalnya :
p : 6 adalah bilangan genap.
q : Jakarta adalah ibukota Indonesia.
r : 1 + 1 = 2
Contoh 1
Tentukan nilai dari proposisi di bawah ini:
a) Soekarno adalah Presiden Indonesia yang pertama.
b) Ibukota Provinsi Jawa Barat adalah Semarang.
c) 2 + 2 = 4
d) 25 + 2 = 26
Penyelesaian
Proposisi a) dan proposisi c) bernilai true, sedangkan proposisi b) dan proposisi d) bernilai false.
Contoh 2
Tentukan apakah proposisi atau tidak
a) Siapakah namamu?
b) Serahkan uangmu sekarang!
c) x + 3 = 8
d) x > 3
Penyelesaian
Kalimat a) dan kalimat b) masing-masing bukan pernyataan, jadi keduanya bukan proposisi. Kalimat c) merupakan pernyataan tetapi bukan suatu proposisi, karena variabel x dalam kalimat tersebut belum ada nilainya, jadi masih dapat bernilai true (bila x bernilai 5) juga dapat bernilai false (bila x โ 5). Begitu pula dengan kalimat (d).
Operator Logika
Operator yang digunakan untuk mengkombinasikan proposisi disebut operator logika atau penghubung logika (logical connectives).
Proposisi baru yang diperoleh dari pengkombinasian tersebut dinamakan proposisi majemuk (compound proposition). Proposisi yang bukan merupakan kombinasi proposisi lain disebut proposisi atomik.
Operator Negasi ยฌ
Jika p adalah sebuah proposisi, maka ยฌp adalah sebuah proposisi pula. ยฌp disebut negasi (negation) dari p, atau tidak p (not p).
Nilai kebenaran dari ยฌp adalah true bila p bernilai false, dan bernilai false bila p bernilai true.
Hubungan antara nilai kebenaran dari p dan negasinya ยฌp dapat pula dinyatakan dalam suatu tabel yang disebut Tabel Kebenaran.
p | ยฌp |
T | F |
F | T |
Contoh:
(a) Negasi proposisi โJakarta adalah ibu kota Indonesiaโ adalah โJakarta bukan ibu kota Indonesiaโ atau โTidak benar bahwa Jakarta adalah ibu kota Indonesiaโ.
(b) Jika p mewakili proposisi โLuas ruang kuliah ini lebih dari 16 m2โ,
maka ยฌp mewakili proposisi โLuas ruang kuliah ini kurang dari atau sama dengan 16 m2โ atau
โTidak benar bahwa luas ruang kuliah ini lebih dari 16 m2โ.
Operator Konjungsi โง
Jika p dan q adalah proposisi maka โp dan qโ atau p โง q adalah sebuah proposisi pula, yang disebut sebagai konjungsi (conjunction) dari p dan q.
Dan nilai kebenaran dari p โง q adalah true pada saat p dan q kedua-duanya bernilai true, dan false bila salah satu atau kedua-duanya dari p dan q bernilai false.
p | q | p โง q |
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Contoh
Jika
p : Hari ini adalah hari Selasa.
q : Hari ini hujan.
Maka
p โง q : Hari ini adalah hari Selasa dan hari ini hujan
atau
Hari ini adalah hari Selasa dan hujan
p โง q bernilai T hanya pada hari Selasa yang hujan, dan bernilai F pada hari lainnya atau pada hari Selasa yang tidak hujan.
Operator Disjungsi โจ
Jika p dan q adalah proposisi maka โp atau qโ atau p โจ q adalah sebuah proposisi pula, yang disebut sebagai disjungsi (disjunction) dari p dan q.
Dan nilai kebenaran dari p โจ q adalah false pada saat p dan q kedua-duanya bernilai false, dan true bila salah satu atau kedua-duanya dari p dan q bernilai true.
p | q | p โจ q |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Contoh
Jika
p : Hari ini adalah hari Selasa
q : Hari ini hujan
Maka p โจ q : Hari ini adalah hari Selasa atau hari ini hujan p โจ q bernilai F apabila harinya bukan hari Selasa dan pada hari itu tidak hujan, dan bernilai T apabila harinya adalah hari Selasa atau apabila harinya hujan.
Operator Exclusice Or โ
Jika p dan q adalah proposisi maka exclusive or dari p dan q atau p โ q adalah sebuah proposisi pula.
Nilai kebenaran dari p โ q adalah true pada saat p dan q memiliki nilai kebenaran yang berbeda, dan false bila p dan q memiliki nilai kebenaran yang sama.
p | q | p โ q |
T | T | F |
T | F | T |
F | T | T |
F | F | F |
Contoh
Jika
p : Hari ini adalah hari Selasa
q : Hari ini hujan
Maka
p โ q : Hari ini adalah hari Selasa yang tidak hujan atau hari ini bukan hari Selasa tetapi hujan.
p โ q bernilai F pada setiap hari Selasa yang hujan atau pada hari-hari bukan hari Selasa yang tidak hujan, dan bernilai T pada hari Selasa yang tidak hujan atau pada hari lainnya yang hujan.
Operator Implikasi โ
Jika p dan q adalah proposisi maka Implikasi (Implication) p โ q, dibaca โJika p maka qโ, adalah sebuah proposisi pula.
p disebut hipotesa atau antecedent atau premise, q disebut konklusi (conclusion) atau konsekuensi (consequence).
Dan nilai kebenaran dari p โ q adalah false hanya pada saat p bernilai true dan q bernilai false, selainnya p โ q akan bernilai true.
p | q | p โ q |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Contoh
Jika
p : Hari ini adalah hari Selasa
q : Hari ini hujan
maka
p โ q : Jika hari ini adalah hari Selasa maka hari ini hujan.
p โ q bernilai F hanya pada hari Selasa yang tidak hujan, dan bernilai T pada hari Selasa yang hujan atau pada hari yang bukan hari Selasa.
โJika p maka qโ dapat pula dikatakan sebagai โp mengakibatkan qโ
atau โp hanya jika qโ
atau โp adalah syarat cukup untuk qโ
atau โq jika pโ
atau โq apabila pโ
atau โq adalah syarat perlu untuk pโ.
Operator Bi-implikasi (Biconditional)
Jika p dan q adalah proposisi maka biconditional p โ q juga sebuah proposisi, dibaca โp jika dan hanya jika qโ, atau โp adalah syarat perlu dan cukup untuk qโ.
Dan nilai kebenaran dari p โ q adalah true pada saat p dan q memiliki nilai kebenaran yang sama, dan false bila p dan q memiliki nilai kebenaran yang berbeda.
p | q | p โ q |
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Contoh
Jika
p : Hari ini adalah hari Selasa
q : Hari ini hujan
maka
p โ q : Hari ini adalah hari Selasa jika dan hanya jika hari ini hujan, atau Hari ini adalah hari Selasa adalah syarat perlu dan cukup agar hari ini hujan.
p โ q bernilai F hanya pada hari Selasa yang tidak hujan atau hari lain yang hujan, dan bernilai T pada hari Selasa yang hujan atau pada hari lain yang tidak hujan.
Tabel Kebenaran
Nilai kebenaran dari proposisi majemuk ditentukan oleh nilai kebenaran dari proposisi atomiknya dan cara mereka dihubungkan oleh operator logika.
Satu cara praktis untuk menentukan nilai kebenaran proposisi majemuk adalah menggunakan tabel kebenaran (truth table).
Tabel kebenaran menampilkan hubungan antara nilai kebenaran dari proposisi atomik.
Contoh 1
Bentuklah tabel kebenaran dari ekspresi logika p โจ ยฌ(p โง q)
p | q | p โง q | ยฌ(p โง q) | p โจยฌ(p โง q) |
T | T | T | F | T |
T | F | F | T | T |
F | T | F | T | T |
F | F | F | T | T |
Contoh 2
p | q | p โง q | p โจ q | ยฌ(p โจ q) | (p โง q) โง ยฌ(p โจ q) |
T | T | T | T | F | F |
T | F | F | T | F | F |
F | T | F | T | F | F |
F | F | F | F | T | F |
Contoh 3
p | q | r | p โง q | ยฌq | ยฌq โง r | (p โง q) โจ (ยฌq โง r) |
T | T | T | T | F | F | T |
T | T | F | T | F | F | T |
T | F | T | F | T | T | T |
T | F | F | F | T | F | F |
F | T | T | F | F | F | F |
F | T | F | F | F | F | F |
F | F | T | F | T | T | T |
F | F | F | F | T | F | F |
Definisi Valid, Terpenuhi, dan Kontradiksi
Sebuah proposisi majemuk disebut absah/valid/tautologi jika bernilai true untuk semua baris pada tabel kebenaran, tidak peduli bagaimana pun nilai kebenaran masing-masing kalimat
penyusunnya.
Sebuah proposisi majemuk disebut terpenuhi/satisfiable jika terdapat nilai true pada pada tabel kebenaran.
Sebuah proposisi majemuk disebut kontradiksi (contradictory/unsatisfiable) jika bernilai false untuk semua baris pada tabel kebenaran.
Contoh 1 adalah suatu proposisi yang valid/tautologi.
Contoh 2 adalah suatu proposisi yang contradictory.
Contoh 3 adalah suatu proposisi yang satisfiable.
Materi Lengkap
Silakan baca juga beberapa artikel menarik kami tentang Matematika Diskrit – Logika, daftar lengkapnya adalah sebagai berikut.