pengantar logika - 2 · pdf fileurutan pengerjaan logika: ... •contoh operasi bitwise...
TRANSCRIPT
![Page 1: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/1.jpg)
1
Pengantar Logika - 2
Matematika Komputasional
PTIIK - UB
Oleh: M. Ali Fauzi
![Page 2: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/2.jpg)
2
Tingkat Presedensi
• Urutan pengerjaan logika:
![Page 3: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/3.jpg)
3
Tingkat Presedensi
Urutan pengerjaan logika:
Jadi, jika ada p ∧ q ∨ r berarti lebih benar (p ∧ q) ∨ r,
dibanding p ∧ (q ∨ r)
Jika ada ¬p ∧ q berarti lebih benar (¬p) ∧ q, bukan berarti
¬ (p ∧ q)
Jika ada p ∨ q → r berarti lebih benar (p ∨ q) → r, bukan p
∨ (q → r)
![Page 4: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/4.jpg)
• Komputer merepresentasikan informasi
menggunakan bit. Bit adalah simbol dengan dua
kemungkinan nilai, yaitu 0 dan 1.
• Operasi bit dalam komputer menggunakan
operator logika konektif seperti ∧, ∨, and⊕
Operasi Bitwise
4
![Page 5: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/5.jpg)
• Contoh operasi bitwise pada bit string dengan
panjang 9
01 1011 0110
11 0001 1101
Bitwise OR ?
Bitwise AND ?
Bitwise XOR ?
Operasi Bitwise
5
![Page 6: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/6.jpg)
• Contoh operasi bitwise pada bit string dengan
panjang 9
01 1011 0110
11 0001 1101
11 1011 1111 Bitwise OR
01 0001 0100 Bitwise AND
10 1010 1011 Bitwise XOR
Operasi Bitwise
6
![Page 7: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/7.jpg)
Dua proposisi yang tabel kebenarannya identik
disebut ekivalen (logically equivalent)
Proposisi
7
p q p q (p q) ^ (q p)
0 0 1
0 1 0
1 0 0
1 1 1
![Page 8: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/8.jpg)
Dua proposisi yang tabel kebenarannya identik
disebut ekivalen (logically equivalent)
p q ⇔ (p q) ^ (q p)
Atau p q ≡ (p q) ^ (q p)
Proposisi
8
p q p q (p q) ^ (q p)
0 0 1 1
0 1 0 0
1 0 0 0
1 1 1 1
![Page 9: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/9.jpg)
Dua proposisi yang tabel kebenarannya identik
disebut ekivalen (logically equivalent)
p q ⇔ p q
Proposisi
9
p q p q p q
0 0 1 1
0 1 1 1
1 0 0 0
1 1 1 1
![Page 10: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/10.jpg)
Konvers dari p q adalah q p
Invers dari p q adalah p q
Konvers dan Invers
10
![Page 11: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/11.jpg)
Jika hari ini hujan, maka anak-anak libur sekolah
Konvers nya adalah :
Jika anak-anak libur sekolah, maka hari ini hujan
Invers nya adalah :
Jika hari ini tidak hujan, maka anak-anak tidak libur
sekolah
Konvers dan Invers
11
![Page 12: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/12.jpg)
Konvers dari p q adalah q p
Invers dari p q adalah p q
Apakah konvers dan invers ekivalen?
p q ekivalen q p?
p q ekivalen p q?
Konvers dan Invers
12
![Page 13: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/13.jpg)
p q tidak ekivalen q p
p q tidak ekivalen p q
Konvers dan Invers
13
p q p q q p p q
0 0 1 1 1
0 1 1 0 0
1 0 0 1 1
1 1 1 1 1
![Page 14: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/14.jpg)
Kontraposisi dari p q adalah q p
Kontraposisi
14
![Page 15: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/15.jpg)
Kontraposisi dari p q adalah q p
Jika hari ini hujan, maka anak-anak libur sekolah
Kontraposisinya nya adalah :
Jika anak-anak tidak libur sekolah, maka hari ini
tidak hujan
Kontraposisi
15
![Page 16: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/16.jpg)
p q ekivalen q p
Kontraposisi
16
p q p q q p
0 0 1 1
0 1 1 1
1 0 0 0
1 1 1 1
![Page 17: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/17.jpg)
Tautology adalah Proposisi yang selalu bernilai
benar (true) dalam keadaan apapun
Contoh: p p v q
Tautology
17
p q p p v q
0 0 1
0 1 1
1 0 1
1 1 1
![Page 18: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/18.jpg)
Kontradiksi adalah Proposisi yang selalu bernilai
salah (false) dalam keadaan apapun
Contoh: p ^ p
Kontradiksi
18
p p ^ ( p)
0 0
1 0
![Page 19: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/19.jpg)
Latihan
19
Dua pedagang barang kelontong mengeluarkan moto jitu
untuk menarik pembeli. Pedagang pertama mengumbar
motto
“Barang bagus tidak murah”
Pedagang kedua punya motto
“Barang murah tidak bagus”
Apakah kedua motto itu bermakna sama?
![Page 20: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/20.jpg)
Ekivalensi Logika
20
Ekivalensi Nama
p T p
p F p
Identity laws
p T T
p F F
Domination laws
p p p
p p p
Idempotent laws
(p) p Double negation laws
p q q p
p q q p
Commutative laws
(p q) r p (q r)
(p q) r p ( q r)
Associative laws
![Page 21: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/21.jpg)
Ekivalensi Logika
21
Ekivalensi Nama
p (q r) (p q) (p r)
p (q r) (p q) (p r)
Distributive laws
(p q) ( p) ( q)
(p q) ( p) ( q)
De Morgan’s laws
p (p q) p
p (p q) p
Absorption laws
p p T
p p F
Negation laws
![Page 22: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/22.jpg)
Ekivalensi Logika
![Page 23: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/23.jpg)
Ekivalensi Logika
23
Ekivalensi
p q p q
p q q p
p q p q
p q (p q)
(p q) p q
(p q) (p r) p (q r)
(p r) (q r) (p q) r
(p r) (q r) (p q) r
(p r) (q r) (p q) r
(p q) (p r) p (q r)
(p r) (q r) (p q) r
Ekivalensi
p q (p q) (q p)
p q p q
p q (p q) (p q)
(p q) p q
![Page 24: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/24.jpg)
Contoh. Tunjukkan bahwa p ~(p q) dan p ~q keduanya
ekivalen secara logika.
Ekivalensi dengan Hukum Logika
24
![Page 25: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/25.jpg)
Contoh. Tunjukkan bahwa p ~(p q) dan p ~q keduanya
ekivalen secara logika.
Penyelesaian:
p ~(p q ) p (~p ~q) (Hukum De Morgan)
(p ~p) (p ~q) (Hukum distributif)
T (p ~q) (Hukum negasi)
p ~q (Hukum
identitas)
Ekivalensi dengan Hukum Logika
25
![Page 26: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/26.jpg)
Ekivalensi dengan Hukum Logika
26
Contoh . Buktikan hukum penyerapan: p (p q) p
![Page 27: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/27.jpg)
Propositional Satisfiability
27
Sebuah proposisi majemuk dikatakan satisfiable jika ada
minimal satu nilai tabel kebenaranya yang bernilai TRUE
(benar)
Jika proposisi majemuk tersebut tidak memiliki nilai TRUE
(benar) sama sekali dalam tabel kebenarannya, maka
proposisi majemuk tersebut disebut tidak satisfiable
![Page 28: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/28.jpg)
p q satisfiable?
q p satisfiable?
Propositional Satisfiability
28
p q p q q p
0 0 1 1
0 1 1 1
1 0 0 0
1 1 1 1
![Page 29: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/29.jpg)
p p v q satisfiable?
Propositional Satisfiability
29
p q p p v q
0 0 1
0 1 1
1 0 1
1 1 1
![Page 30: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/30.jpg)
p ^ p satisfiable?
Propositional Satisfiability
30
p p ^ ( p)
0 0
1 0
![Page 31: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/31.jpg)
Latihan
31
Tunjukkan bahwa (p ( p q)) and p q ekivalen.
![Page 32: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/32.jpg)
Latihan
32
Tunjukkan bahwa (p q) (p q) tautology.
![Page 33: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/33.jpg)
Latihan
33
Tunjukkan bahwa (p q) ekivalen dengan
( ) ( )( ) ( ) qrqprpr
![Page 34: Pengantar Logika - 2 · PDF fileUrutan pengerjaan logika: ... •Contoh operasi bitwise pada bit string dengan panjang 9 01 1011 0110 11 0001 1101 11 1011 1111 Bitwise OR 01 0001 0100](https://reader031.vdokumen.com/reader031/viewer/2022020104/5aba6ccd7f8b9ad1768b78d7/html5/thumbnails/34.jpg)
34
Credit :
Slide ini sebagian besar diambilkan dari materi
Pengantar Logika oleh Bapak Rinaldi Munir dan
Materi Logika oleh Ibu Rekyan Regasari serta
materi The Foundations : Logic and Proofs pada
buku Discrete Mathematics and Its Applications
oleh Kenneth H. Rosen dengen beberapa
penyesuaian perubahan