Logika Proposisional Ema Utami STMIK AMIKOM Yogyakarta
Logika proposisional merupakan ilmu dasar untuk mempelajari algoritma dan logika yang terkait di dalamnya yang berperanan sangat penting dalam pemrograman. Proses kerja komputer tidak dapat dilepaskan dari program-program, di mana komputer akan menerjemahkan programprogram tersebut dengan sistem logika. Dengan alasan di atas maka belajar logika proporsisional sebagai dasar logika algoritma sangat diperlukan dalam belajar pemrograman maupun belajar bahasa pemrograman.
Proposisi Proposisi atau pernyataan merupakan komponen penyusun logika dasar yang dilambangkan dengan huruf kecil (p, q, r, ...). Proposisi hanya dapat diiwakili oleh kalimat deklaratif. Kalimat deklaratif adalah kalimat yang mengandung nilai kebenaran yaitu dapat bernilai benar atau salah tetapi tidak mungkin memiliki kedua nilai tersebut. Lawan kalimat deklaratif adalah kalimat terbuka, artinya kalimat yang nilai kebenarannya tidak bisa ditentukan.
Relasi Proposisional Untuk mengkombinasikan dua buah proposisi atau lebih diperlukan connective atau penghubung. Propositions + Propositional Connectives → Sentences Untuk menggabungkan proposisi-proposisi dan penghubungnya diperlukan Syntactics Rules yaitu suatu aturan yang diperlukan untuk mengkombinasikan antara propositions dan propositional connectives untuk menghasilkan sentences (kalimat logika). 1.Setiap proposition adalah sentence tanpa ada propositional connectives. 2.Jika p suatu sentence maka negasinya not p juga sentence. Negasi atau ingkaran adalah proposisi yang nilai kebenarannya berlawanan dengan proposisi semula. Suatu proposisi yang disertai dengan kata-kata 'tidak', 'bukan' dan sebagainya. Misalkan terdapat proposisi p maka negasinya adalalah - p atau ~p. 3.Jika p dan q sentences maka conjunction-nya yaitu 'p and q' juga sentences. Conjunction yaitu dua proposisi atau lebih yang dihubungkan dengan kata 'dan' atau 'and'. Lambang yang digunakan adalah ^, &. 4.Jika p dan q sentences maka disjunction-nya yaitu 'p or q' juga sentences. Disjunction yaitu dua proposisi atau lebih yang dihubungkan dengan kata 'atau' atau 'or'. Lambang yang digunakan adalah v, +. 5.Jika p dan q sentences maka implication-nya yaitu 'if p then q' juga sentences. Implication adalah penggabungan dua proposisi dengan bentuk 'jika p maka q'.
Lambang yang digunakan adalah →. Proposisi pertama (p) disebut anteseden sedangkan proposisi kedua (q) disebut konsekuen. 6.Jika p dan q sentences maka equivalence-nya yaitu 'p if and only if q' juga sentences. Equivalence atau biimplikasi adalah penggabungan dua proposisi dengan bentuk 'p jika dan hanya jika q'. Kata penghubung yang lain adalah iof, iff, jika dan hanya jika (jhj). Lambang yang digunakan adalah ↔. 7.Jika p, q dan r sentences maka conditional-nya yaitu 'if p then q else r' juga sentences.
Interpretasi Interpretasi adalah pemberian nilai kebenaran (benar atau salah) pada setiap simbol proposisi dari suatu kalimat logika. Semantic Rules adalah suatu aturan yang digunakan untuk menentukan truth value (nilai kebenaran) dari suatu sentence. Untuk mempermudah penyajiannya dibuatlah tabel kebenaran. 1.Negation Rule (Aturan NOT) Negasi bernilai benar jika proposisi mula-mula bernilai salah dan sebaliknya apabila proposisi mula-mula bernilai benar maka negasinya mempunyai nilai kebenaran salah. P True False
not p False True Tabel 1 Aturan NOT
2.Conjunction Rule (Aturan AND) Konjungsi bernilai benar jika setiap proposisi penyusunnya benar. P True True False False
Q True False True False
p and q True False False False Tabel 2 Aturan AND
3.Disjunction Rule (Aturan OR) Minimal satu proposisi penyusunnya benar maka disjungsi bernilai benar. P True True False False
Q True False True False
p or q True True True False Tabel 3 Aturan OR
Untuk relasi konjungsi dan disjungsi berlaku sifat-sifat aljabar logika sebagai berikut : a.Hukum Idempoten pvp
= p
p∧p
= p
b.Hukum Komutatif pvq p∧q
= qvp = q∧p
c.Hukum Assosiatif (pvq)v r = pv(qvr) (p∧q)∧r = p∧(q∧r) d.Hukum Distributif pv(q∧r) = p∧(qvr) =
(pvq) ∧ (pvr) (p∧q) v (p∧r)
e.Hukum Identitas p v False p ∧ True f.Hukum Ikatan p v True p ∧ False
= =
p p
= =
True False
g.Hukum Komplemen/Negasi p v not p = True p ∧ not p = False h.Hukum Negasi Ganda not(not p) =
p
i.Hukum De Morgan Negasi dari konjungsi dan disjungsi: ~ (pvq) = ~p ∧ ~q ~ (p∧q) = ~p v ~q j.Hukum Absorbsi p v (p ∧ q ) = p p ∧ (p v q ) = p k.Negasi True dan False ~True = False ~False = True 4.Implication Rule (Aturan IF-THEN) Implikasi bernilai salah bila anteseden benar dan konsekuen salah. Misalkan kita mempunyai sebuah bentuk implikasi seperti berikut: p→q Bentuk implikasi tersebut dapat dibaca: a. Jika P maka Q b. P Jika Maka Q c. P Syarat cukup untuk Q d. Q Syarat perlu untuk P e. Q hanya jika P
P
q
True True False False
True False True False
if p then q TRUE False True True Tabel 4 Aturan IF – THEN
Terdapat beberapa definisi: a)Jika (p→q) adalah implikasi maka (q→p) adalah konvers b)Jika (p→q) adalah implikasi maka (~p → ∼q) adalah invers c)Jika (p→q) adalah implikasi maka (~q→ ∼p) adalah kontraposisi d)Jika (p→q) bernilai benar maka (q→p), (~p → ~q), dan (~q → ~p) belum tentu bernilai benar. 5.Equivalence Rule (Aturan IF AND ONLY IF) Jika penyusun proposisi mempunyai nilai yang sama maka biimplikasi bernilai benar, p True True False False
q True False True False
p if and only if q True False False True Tabel 5 Aturan IF AND ONLY IF
6.Conditional Rule (Aturan IF - THEN - ELSE) Jika p bernilai benar maka q berlaku. Jika p bernilai salah maka r berlaku p True True True True False False False False
q True True False False True True False False
r True False True False True False True False
if p then q else r True True False False True False True False Tabel 6 Aturan IF-THEN-ELSE
Sifat-Sifat Kalimat Logika 1.Valid/Tautologi Suatu sentence f disebut valid, jika untuk setiap interpretation I for f maka f true. 2.Satisfiable Suatu sentence f disebut satisfiable, jika untuk suatu interpretation I for f maka f true. 3.Kontradiksi Suatu sentence f disebut kontradiksi, jika untuk setiap interpretation I for f maka f false.
Daftar Pustaka Ema Utami, Suwanto Raharjo, 2004, Belajar C Di GNU/Linux, ISSN 979-3289-55-4, Penerbit Graha Ilmu Yogyakarta Ema Utami, Suwanto Raharjo, 2004, Struktur Data Menggunakan C di GNU/Linux, ISSN 979-731395-6, Penerbit Andi Offset Yogyakarta Ema Utami, 2004, Logika, Algoritma dan Implementasinya dalam Bahasa Python di GNU/Linux, ISSN 979-731-443-X, Penerbit Andi Offset Yogyakarta Ema Utami, Sukrisno, 2005, 10 Langkah Mudah Memahami Logika Algoritma Menggunakan Bahasa C/C++ di GNU/Linux, ISSN 979-763-020-X, Penerbit Andi Offset Yogyakarta Ema Utami, Sukrisno, 2005, 101 Tips dan Trik Bahasa C untuk Pemula di GNU/Linux, ISSN 979763-010-2, Penerbit Andi Offset Yogyakarta Ema Utami, Sukrisno, Suwanto Raharjo, 2007, Struktur Data : Konsep dan Implementasinya dalam Bahasa C dan Free Pascal di GNU/Linux, ISSN 979-756-292-2, Penerbit Graha Ilmu Yogyakarta
