LOGIKA Ratna Wardani Pendidikan Teknik Informatika
2 September 2007
Pertemuan-1 - 2
1
Materi Perkuliahan
Logical Connectives Tabel Kebenaran
2 September 2007
Pertemuan-1 - 2
2
Arti Kalimat
Arti kalimat = nilai kebenaran Setiap kalimat pada logika proposisi memiliki salah satu dari nilai {true, false} Arti kalimat kompleks yang terdiri atas n variabel merupakan fungsi dari nilai kebenaran n variabel tersebut Perlu tahu nilai kebenaran masing-masing variabel Perlu aturan untuk menghitung fungsi tersebut
2 September 2007
Pertemuan-1 - 2
3
Interpretasi Interpretasi pada logika proposisi = pemberian nilai kebenaran pada semua variabel Contoh : P ∨ ¬Q I1 : P true dan Q true I2 : P true dan Q false I3 : P false dan Q false I4 : P false dan Q true
2 September 2007
Pertemuan-1 - 2
4
Aturan Semantik
kalimat true bernilai true untuk semua interpretasi kalimat false bernilai false untuk semua interpretasi kalimat P,Q,R,… bernilai sesuai interpretasinya not F bernilai true jika F false dan bernilai false jika F true F ∧ G bernilai true jika F dan G keduanya true dan bernilai false jika tidak demikian F ∨ G bernilai false jika F dan G keduanya false dan bernilai true jika tidak demikian F ⇒ G bernilai false jika F true dan G false dan bernilai true jika tidak demikian
2 September 2007
Pertemuan-1 - 2
5
Tabel Kebenaran Dengan aturan semantik dapat ditentukan nilai kebenaran suatu kalimat kompleks untuk semua interpretasi yang mungkin Biasanya ditabelkan dan disebut tabel kebenaran Jika terdapat n variabel, maka terdapat 2n baris tabel kebenaran
2 September 2007
Pertemuan-1 - 2
6
Operator / Logical Connectives
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 (contoh −3); Operator biner bekerja pada 2 operand (contoh 3 × 4).
Operator Proposisi atau Boolean bekerja pada proposisiproposisi atau nilai kebenaran, bukan pada suatu angka
2 September 2007
Pertemuan-1 - 2
7
Operator / Boolean Umum Nama Resmi
Istilah
Arity
Operator Negasi
NOT
Unary
Operator Konjungsi
AND
Binary
Operator Disjungsi
OR
Binary
Operator Exclusive-OR
XOR
Binary
Operator Implikasi
IMPLIES (jika-maka)
Binary
Simbol ¬ ∧ ∨ ⊕ →
Operator Biimplikasi (Biconditional)
IFF (jika dan hanya jika)
Binary
↔
2 September 2007
Pertemuan-1 - 2
8
Operator Negasi
Operator negasi uner “¬” (NOT) mengubah suatu proposisi menjadi proposisi lain yang bertolak belakang nilai kebenarannya Contoh: Jika p = Hari ini hujan maka ¬p = Tidak benar hari ini hujan Tabel kebenaran untuk NOT:
p T F 2 September 2007
¬p
F T
T = True; F = False ≡ Diartikan “didefinisikan sebagai” Pertemuan-1 - 2
9
Operator Konjungsi
Operator konjungsi biner “∧” (AND) menggabungkan dua proposisi untuk membentuk logika konjungsinya Cth: p = Galih naik sepeda q = Ratna naik sepeda p∧q = Galih dan Ratna naik sepeda
2 September 2007
ΛND
Pertemuan-1 - 2
10
Tabel Kebenaran Konjungsi
p q Perhatikan bahwa p∧q F F Konjungsi p1 ∧ p2 ∧ … ∧ pn F F T F dari n proposisi akan T F F memiliki 2n baris T T T pada tabelnya Operasi ¬ dan ∧ saja cukup untuk mengekspresikan semua tabel kebenaran Boolean!
2 September 2007
Pertemuan-1 - 2
11
Operator Disjungsi Operator biner disjungsi “∨” (OR) menggabungkan dua proposisi untuk membentuk logika disjungsinya p=“Mesin mobil saya rusak” q=“Karburator mobil saya rusak” p∨q=“Mesin atau karburator mobil saya rusak.”
2 September 2007
Pertemuan-1 - 2
12
Tabel Kebenaran Disjungsi
Perhatikan bahwa p∨q p q p∨q berarti p benar, atau q benar, atau keduanya benar! F F F Jadi, operasi ini juga disebut F T T Lihat bedanya inclusive or, karena mencakup T F T dengan kemungkinan bahwa both p AND T T T dan q keduanya benar. “¬” dan “∨” keduanya membentuk opearator universal.
2 September 2007
Pertemuan-1 - 2
13
Proposi Bertingkat
Gunakan tanda kurung untuk mengelompokkan sub-ekspresi: “Saya baru saja bertemu teman lama, dan anaknya sudah dua atau tiga.” = f ∧ (g ∨ s) – (f ∧ g) ∨ s artinya akan berbeda – f ∧ g ∨ s artinya akan ambigu
Menurut perjanjian, “¬” presedensinya lebih tinggi dari “∧” dan “∨”. – ¬s ∧ f artinya (¬s) ∧ f , bukan ¬ (s ∧ f)
2 September 2007
Pertemuan-1 - 2
14
Latihan Misalkan p=“Tadi malam hujan”, q=“Tukang siram tanaman datang tadi malam,” r=“Pagi ini kebunnya basah.” Terjemahkan proposisi berikut dalam bahasa Indonesia:
¬p r ∧ ¬p
= “Tadi malam tidak hujan.” = “Pagi ini kebunnya basah dan tadi malam tidak hujan.”
¬r∨p∨q=
2 September 2007
“Pagi ini kebun tidak basah, atau tadi malam hujan, atau tukang siram tanaman datang tadi malam.” Pertemuan-1 - 2
15
Operator Exclusive OR Operator biner exclusive-or “⊕” (XOR) menggabungkan dua proposisi untuk membentuk logika “exclusive or”-nya p = “Saya akan mendapat nilai A di kuliah ini,” q = “Saya akan drop kuliah ini,” p ⊕ q = “Saya akan mendapat nilai A atau saya akan drop kuliah ini (tapi tidak dua-duanya!)”
2 September 2007
Pertemuan-1 - 2
16
Tabel Kebenaran Exclusive OR Perhatikan bahwa p⊕q p q p⊕q berarti p benar, atau q F F F benar tapi tidak duaF T T duanya benar! Disebut exclusive or, T F T karena tidak memungkinkan T T F p dan q keduanya benar “¬” dan “⊕” tidak membentuk operator universal
2 September 2007
Pertemuan-1 - 2
17
Bahasa Alami sering Ambigu
Perhatikan bahwa kata “atau” dapat bermakna ambigu berkenaan dengan kasus keduanya benar. “Tia adalah penulis atau p q p "or" q Tia adalah aktris.” F F F “Tia perempuan atau F T T Tia laki-laki” – T F T
T T
?
Perlu diketahui konteks pembicaraannya!
2 September 2007
Pertemuan-1 - 2
18
Operator Implikasi
Implikasi p → q menyatakan bahwa p mengimplikasikan 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”
2 September 2007
Pertemuan-1 - 2
19
Implikasi p → q (a) Jika p, maka q (b) Jika p, q (c) p mengakibatkan q (d) q jika p (e) p hanya jika q (f) p syarat cukup agar q (g) q syarat perlu bagi p (i) q bilamana p 2 September 2007
(if p, then q) (if p, q) (p implies q) (q if p) (p only if q) (p is sufficient for q) (q is necessary for p) (q whenever p) Pertemuan-1 - 2
20
Tabel Kebenaran Implikasi p → q salah hanya jika p q p→q p benar tapi q tidak benar F F T p → q tidak mengatakan F T T bahwa hanya p yang menyeT F F babkan q! T T T p → q tidak mensyaratkan bahwa p atau q harus benar! Cth. “(1=0) → kucing bisa terbang” BENAR!
2 September 2007
Pertemuan-1 - 2
Satusatunya kasus SALAH!
21
Contoh Implikasi “Jika saya rajin kuliah hari ini, matahari akan bersinar esok hari” True / False? “Jika hari ini Selasa, maka saya adalah seekor pinguin.” True / False? “Jika 1+1=6, Maka SBY adalah presiden.” True / False? “Jika bulan dibuat dari keju, maka saya lebih kaya dari Bill Gates.” True or False?
2 September 2007
Pertemuan-1 - 2
22
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? 2 September 2007
Pertemuan-1 - 2
23
Bagaimana Menunjukkannya? Membuktikan eqivalensi antara p → q dan contrapositive-nya dengan tabel kebenaran:
p F F T T
q F T F T
2 September 2007
¬q T F T F
¬p T T F F
p→q ¬q →¬p T T T T F F T T
Pertemuan-1 - 2
24
Operator Biimplikasi
Operator biimplikasi p ↔ q menyatakan bahwa p benar jika dan hanya jika (jikka) q benar p = “SBY menang pada pemilu 2004” q = “SBY akan menjadi presiden mulai tahun 2004.” p ↔ q = “Jika dan hanya jika SBY menang pada pemilu 2004 maka dia akan menjadi presiden mulai tahun 2004.”
2 September 2007
Pertemuan-1 - 2
25
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 conversely) (d) p jikka q (p iff q) 2 September 2007
Pertemuan-1 - 2
26
Tabel Kebenaran Biimplikasi p ↔ q benar jika p dan q p memiliki nilai kebenaran F yang sama. F Perhatikan bahwa tabelnya T adalah kebalikan dari tabel T exclusive or ⊕!
q p ↔q F T T F F F T T
– p ↔ q artinya ¬(p ⊕ q) 2 September 2007
Pertemuan-1 - 2
27
Perhatikan Nyatakan pernyataan berikut dalam ekspresi logika : “Anda tidak dapat terdaftar sebagai pemilih dalam Pemilu jika anda berusia di bawah 17 tahun kecuali kalau anda sudah menikah” 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 ditulis sebagai (p Λ ~ q) → ~ r
2 September 2007
Pertemuan-1 - 2
28
Ringkasan
p F F T T
q F T F T
¬p T T F F
2 September 2007
p∧q F F F T
p∨q p⊕q p→q p↔q F F T T T T T F T T F F T F T T Pertemuan-1 - 2
29
Latihan - 1
1) 2) 3) 4) 5)
Gunakan konstanta proposisional A untuk “Bowo kaya raya” dan B untuk “Bowo hidup bahagia”.Lalu ubahlah pernyataan-pernyataan berikut menjadi bentuk logika : Bowo tidak kaya raya Bowo kaya raya dan hidup bahagia Bowo kaya raya atau tidak hidup bahagia Jika Bowo kaya raya, maka ia hidup bahagia Bowo hidup bahagia jika dan hanya jika ia kaya raya
2 September 2007
Pertemuan-1 - 2
30
Latihan - 2
1)
2) 3) 4)
5)
Berilah konstanta proposisional, dan ubahlah pernyataan-pernyataan berikut menjadi bentuk logika : Jika Bowo berada di Malioboro, maka Dewi juga berada di Malioboro Pintu rumah Dewi berwarna merah atau coklat Berita itu tidak menyenangkan Bowo akan datang, jika ia mempunyai kesempatan Jika Dewi rajin kuliah, maka ia pasti pandai
2 September 2007
Pertemuan-1 - 2
31
Latihan - 3 1) 2) 3) 4) 5)
Jawablah dengan tabel kebenaran : Apakah nilai kebenaran dari (A ∧ A)? Apakah nilai kebenaran dari (A ∨ A)? Apakah nilai kebenaran dari (A ∧ ¬A)? Apakah (A⇒B) ekivalen dengan (B⇒A) Apakah (A⇒B)⇒C ekivalen dengan A⇒(B⇒C)
2 September 2007
Pertemuan-1 - 2
32
Latihan - 4 1) 2) 3) 4) 5)
Buat tabel kebenaran untuk pernyataan berikut: ¬(¬A ∧ ¬A) A ∧(A ∨ B) ((¬A ∧ (¬B ∧ C)) ∨ (B ∧ C)) ∨ (A ∧ C) (A ∧ B) ∨ ((( ¬A ∧B) ⇒A) ∧ ¬B) (A⇒B)⇔ (¬B⇒¬A)
2 September 2007
Pertemuan-1 - 2
33
