2. LOGIKA PROPOSISI2.1. Definisi Logika ProposisiLogika proposisi adalah logika pernyataan
majemuk yang disusun dari pernyataan-pernyataan sederhana yang dihubungkan dengan penghubung Boolean (Booleanconnectives)
Atomic proposition adalah propos ition yang tidak dapat dibagi lagi
Kombinasi dari a.p dengan berbagai penghubung membentuk compound proposition(proposition majemuk)
Aplikasi Logika Proposisi
Beberapa apl ikasinya dalam ilmu komputer:§ Menyatakan kondi si/ syarat pada program§ Query untuk basisdata dan § search engine
Definisi ProposisiSebuah proposisi (p, q, r, …) adalah suatu
kalimat (sentence) yang memiliki nilai kebenaran ( truth value) benar (true), dengan notas i T, atau ni lai kebenaran salah (false) dengan notas i F tetapi tidak kedua-duanya
Perhatikan !!a) 6 adalah bilangan genap.b) x + 3 = 8.c) Ibukota Provinsi Jawa Barat adalah Semarang.d) 12 ≥ 19.e) Soekarno adalah Presiden Indonesia yang
pertama. f) Jam berapa kereta api Argo Bromo tiba di Gambir? g) Kemarin hari hujan.h) Kehidupan hanya ada di planet Bumi.i) 1+2j) Siapkan kertas ujian sekarang! k) x + y = y + x untuk setiap x dan y bilangan riil
2.2. Operator / Penghubung
Sebuah operator atau penghubung menggabungkan satu atau lebih ekspresi operand ke dalam ekspresi yang lebih besar. (seperti tanda “+” di ekspresi numerik.)§ Operator Uner bekerja pada satu operand (cth, −3);§ Operator biner bekerja pada 2 operand (cth 3 × 4);§ Operator Proposisi atau Boolean bekerja pada
proposisi-proposisi atau nilai kebenaran, bukan pada suatu angka
Nama Resmi Istilah Arity SimbolOperator Negasi NOT Unary ¬Operator Konjungsi AND Binary ∧
Operator Disjungsi OR Binary ∨
Operator Exclusive-OR XOR Binary ⊕
Operator Implikasi IMPLIES(jika-maka)
Binary →
Operator Biimplikasi (Biconditional)
IFF (jikka –jika dan hanya jika)
Binary ↔
Operator Boolean Umum
2.2.1. Operator Negasi
• Operator negasi uner “¬” (NOT) mengubah suatu proposisi menjadi proposisi lain yang bertolak belakang nilai kebenarannya
• Contoh: Jika p = Hari ini hujanmaka ¬p = Tidak benar hari ini hujan
• Tabel kebenaran untuk NOT:p ¬p
T FF T
2.2.2. Operator Konjungsi
Operator konjungsi biner “∧” (AND) menggabungkan dua proposisi untuk membentuk logika konjungs inya
Cth: p = Galih naik sepeda q = Ratna naik sepedap∧q = Galih dan Ratna naik sepeda
ΛND
Tabel Kebenaran Konjungsi
p q p Λ q
T T T
T F F
F T F
F F F
2.2.3. Operator Disjungsi
• Operator biner disjungsi “V” (OR) menggabungkan dua proposisi untuk membentuk logika dis jungsinya
Cth : p = Tommy ingin membeli sepatuq = Tommy ingin membeli baju
p V q = Tommy ingin membeli sepatu atau baju
∨∨
Maknanya seperti “dan/atau” dalam bahasa Indonesia
Tabel Kebenaran Disjungsi
p q p V q
T T T
T F T
F T T
F F F
2.2.4.Operator Exclusive Or• Operator biner exclusive-or “⊕” (XOR)
menggabungkan dua proposisi untuk membentuk logika “exclusive or”-nya
• Contoh :p = Saya akan mendapat nilai A di kuliah iniq = Saya akan drop kuliah inip ⊕ q = Saya akan mendapat nilai A atau saya akan drop kuliah ini (tapi tidak dua-duanya!)
Tabel Kebenaran Exclusive-Or
Perhatikan bahwa Perhatikan bahwa pp⊕⊕q q berarti berarti pp benar, atau benar, atau qq benar benar tapi tapi tidak duatidak dua--duanya benarduanya benar!!
p q p ⊕⊕ qT T FT F TF T TF F F
2.2.5. Operator Implikasi• Implikasi p → q menyatakan bahwa p
mengimplikas ikan q.• p disebut antecedent dan q disebut consequent• Jika p benar, maka q benar; tapi jika p tidak
benar, maka q bisa benar - bisa tidak benar• Contoh :
p = Nilai ujian akhir anda 80 atau lebih q = Anda mendapat nilai A p → q = “Jika nilai ujian akhir anda 80 atau lebih, maka anda mendapat nilai A”
Implikasi p → q
• (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 if 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)• (i) q bilamana p (q whenever p)
Tabel Kebenaran Implikasi
p q p → q
T T T
T F F
F T T
F F T
p p →→ q q salahsalah hanya jikahanya jika pp benar tapi benar tapi qq tidak benartidak benar
Converse, Inverse, Contrapositive
Beberapa terminologi dalam implikasi p → q:• Converse-nya adalah: q → p.• Inverse-nya adalah: ¬p → ¬q.• Contrapositive-nya adalah: ¬q → ¬ p.
Salah satu dari ketiga terminologi di atas memiliki makna yang sama (memiliki tabel kebenaran yang sama) dengan p → q. Bisa Anda sebutkan yang mana?
Bagaimana menunj ukkannya?
Membuktikan eqivalensi antara p → q dan contrapositive-nya dengan tabel kebenaran:
p q ¬q ¬p p→q ¬q →¬pF F T T T TF T F T T TT F T F F FT T F F T T
2.2.6. Operator Biimplikasi• Operator biimplikasi p ↔ q menyatakan bahwa p
benar jika dan hanya jika (ji kka) q benar• Contoh :
p = saya selalu menyatakan kebenaran q = ada emas di pulau ini p ↔ q = Jika dan hanya jika saya selalu
mengatakan kebenaran maka ada emas di pulau ini
Biimplikasi p ↔ q
(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 conversel y)
(d) p jikka q(p iff q)
Tabel Kebenaran Biimplikasi
p p ↔ q q benar jika benar jika pp dan dan q mq memiliki nilai kebenaran yang samaemiliki nilai kebenaran yang sama
p q p ↔ q
T T T
T F F
F T F
F F T
Perhatikan !!Nyatakan pernyataan berikut dalam ekspresi logika :
“Anda tidak dapat terdaftar sebagai pemilih dalam Pemilu jika anda berusi a di bawah 17 tahun kecual i kalau anda sudah meni kah”
Misalkan : p : Anda berusia di bawah 17 tahun.q : Anda sudah menikah.r : Anda dapat terdaftar sebagai pemilih dalam
Pemilu.maka pernyataan di atas dapat di tulis sebagai(p Λ ~ q) → ~ r
2.2.7. Precendence Rules
untuk menjaga kebenaran sebuah pernyataan maka setiap operator/ penghubung diberikan aturan yang lebih tinggi
¬ →⊕V
V ↔
Contoh :
¬p V q ≡ (¬p ) V q
p Λ q V r ≡ (p Λ q) V r
p → q V r ≡ p → (q V r)
p ↔ q → r ≡ p ↔ (q → r)
2.2.8. Left Associate Rules
untuk operator/ penghubung yang setara digunakan lef t associate rule dimana operator sebelah kiri punya precedence lebih tinggi
Contoh :
p V q V r ≡ (p V q) V r
p → q → r ≡ (p → q) → r
Ringkasan Operator Boolean
p q ¬p pVq pΛq p⊕⊕q p→q p↔q
T T F T T F T T
T F F T F T F F
F T T T F T T F
F F T F F F T T
Notasi Alternatif
Name: not and or xor implies iffPropositional logic: ¬ ∧ ∨ ⊕ → ↔Boolean algebra: p pq + ⊕C/C++/Java (wordwise): ! && || != ==C/C++/Java (bitwise): ~ & | ^Logic gates:
If …then
2.3. Tautologi dan Kontradiksi
• Tautology adalah proposisi majemuk yang selalu bernilai true tidak peduli apa nilai kebenaran proposisi penyusunnya!Contoh: p ∨ ¬p
• Kontradiksi adalah proposisi majemuk yang selalu bernilai false tidak peduli apapun! Contoh: p ∧ ¬p
2.4. Ekivalensi Logika
Proposisi majemuk p ekivalen dengan proposisi majemuk q, ditulis p ⇔ q, JIKKAproposisi majemuk p↔q adalah tautologi.
Proposisi majemuk p dan q ekivalen satu sama lain JIKKA p dan q memiliki nilai kebenaran yang sama pada semua barisnya di tabel kebenaran
Contoh. Buktikan p∨q ⇔ ¬(¬p ∧ ¬q).
Membuktikan ekivalensi dengan Tabel Kebenaran
p q pp∨∨qq ¬¬pp ¬¬qq ¬¬pp ∧∧ ¬¬qq ¬¬((¬¬pp ∧∧ ¬¬qq))F FF TT FT T
FT
TT
T
T
T
TTT
FF
F
F
FFF
F
TT
Hukum Ekivalensi - Contoh
• Identity: p ∧ T ⇔ p p ∨ F ⇔ p
• Domination: p ∨ T ⇔ T p ∧ F ⇔ F
• Idempotent: p ∨ p ⇔ p p ∧ p ⇔ p
• Commutative: p ∨ q ⇔ q ∨p p ∧ q ⇔ q ∧ p
• Double negat ion: ¬¬p ⇔ p
Hukum Ekivalensi lainnya
• Associat ive: (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)(p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
• Distributif: p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
• De Morgan: ¬(p ∧ q) ⇔ ¬p ∨ ¬q¬(p ∨ q) ⇔ ¬p ∧ ¬q
• Trivial tautology/contradiction:p ∨ ¬p ⇔ Tp ∧ ¬p ⇔ F
Definisi Operator dengan Ekivalensi
Menggunakan ekivalens i, kita dapat mendefinisikan operator dengan operator lainnya
• Exclusive or: p⊕q ⇔ (p V q) Λ ¬(p Λ q)p⊕q ⇔ (p Λ ¬q) V (q Λ ¬p)
• Implikasi: p→q ⇔ ¬p V q• Biimplikasi: p↔q ⇔ (p→q) Λ (q→p)
p↔q ⇔ (p Λ q) V (¬p Λ ¬q) p↔q ⇔ (¬p V q) Λ (p V¬q) p↔q ⇔ ¬(p⊕q)
• Buktikan dengan symbolic derivat ion apakah (p ∧ ¬q) → (p ⊕ r) ⇔ ¬p ∨ q ∨ ¬r ?(p ∧ ¬q) → (p ⊕ r) ⇔
• [Expand definition of →] ¬(p ∧ ¬q) ∨ (p ⊕ r)• [Defn. of ⊕] ⇔ ¬(p ∧ ¬q) ∨ ((p ∨ r) ∧ ¬(p ∧ r))• [DeMorgan ’s Law]
⇔ (¬p ∨ q) ∨ ((p ∨ r) ∧ ¬(p ∧ r))⇔ cont.
Membuktikan ekivalensi dengan Symbolic Derivation
(¬p ∨ q) ∨ ((p ∨ r) ∧ ¬(p ∧ r)) ⇔ [∨ commutes]⇔ (q ∨ ¬p) ∨ ((p ∨ r) ∧ ¬(p ∧ r)) [∨ associative]⇔ q ∨ (¬p ∨ ((p ∨ r) ∧ ¬(p ∧ r))) [distrib. ∨ over ∧]⇔ q ∨ (((¬p ∨ (p ∨ r)) ∧ (¬p ∨ ¬(p ∧ r)))[assoc.] ⇔ q ∨ (((¬p ∨ p) ∨ r) ∧ (¬p ∨ ¬(p ∧ r)))[trivial taut.] ⇔ q ∨ ((T ∨ r) ∧ (¬p ∨ ¬(p ∧ r)))[domination] ⇔ q ∨ (T ∧ (¬p ∨ ¬(p ∧ r)))[identity] ⇔ q ∨ (¬p ∨ ¬(p ∧ r))
⇔ cont.
• q ∨ (¬p ∨ ¬(p ∧ r))• [DeMorgan ’s] ⇔ q ∨ (¬p ∨ (¬p ∨ ¬r))• [Assoc.] ⇔ q ∨ ((¬p ∨ ¬p) ∨ ¬r)• [Idempotent] ⇔ q ∨ (¬p ∨ ¬r)• [Assoc.] ⇔ (q ∨ ¬p) ∨ ¬r • [Commut.] ⇔ ¬p ∨ q ∨ ¬r
2.5. INFERENSI
• Misalkan kepada kita diberikan beberapa proposisi.
• Kita dapat menari k kesimpulan baru dari deret proposisi tersebut.
• Proses penarikan kesimpulan penarikan kesimpulan dari beberapa propos isi disebut inferensi (inference).
2.5.1. Modus Ponen
• Kaidah Modus Ponens ditulis dengan cara :
• Modus ponen menyatakan bahwa jika hipotesis p dan dan implikas i p → q benar, maka konklus i q benar.
2.5.2. Modus Tollen
• Kaidah ini didasarkan pada tautologi [~q Λ (p → q)] → ~p,
• Kaidah ini modus tollens ditulis dengan cara:
2.5.3. Silogisme Hipotetis
• Kaidah ini didasarkan pada tautologi [(p → q) Λ (q → r)] → (p → r).
• Kaidah silogisme ditulis dengan cara:
2.5.4. Silogisme Disj ungtif
• Kaidah ini didasarkan pada tautologi [(p V q) Λ ~p] → q .
• Kaidah silogisme disjungtif ditulis dengan cara:
Operasi Logika di dalam Komputer
• Operasi boolean sering dibutuhkan dalam pemrograman.
• Operasi boolean dinyatakan dalam ekspresi logika (atau dinamakan juga ekspresi boolean).
• Operator boolean yang digunakan adalah AND, OR, XOR, dan NOT.
• Ekspresi boolean hanya menghas ilkan salah satu dari dua nilai, true atau false.
• Misalkan : x1, x2, x3, dan x4 adalah peubah boolean dalam Bahasa Pascal, maka ekspresi boolean di bawah ini adalah valid:x1 and x2x1 or (not(x2 and x3))yang bersesuaian dengan ekspresi logikax1 Λ x2x1 V (¬(x2 V x3))
Review : Logika Proposisi
• Proposisi atomik: p, q, r, … • Operator Boolean: ¬ ∧ ∨ ⊕ → ↔• Proposisi majemuk: s :≡ (p ∧ ¬q) ∨ r• Ekivalensi: p∧¬q ⇔ ¬(p → q)• Membuktikan ekivalensi dengan:
– Tabel kebenaran.– Symbolic derivat ions. p ⇔ q ⇔ r …