LOGIKA INFORMATIKA
Bahan Ajar Digunakan sebagai salah satu bahan ajar mata kuliah Logika Informatika
Oleh Achmad Fauzan
TEKNIK INFORMATIKA POLITEKNIK HARAPAN BERSAMA TEGAL 2016
Daftar Isi
Daftar Isi
ii
Daftar Gambar
iii
Daftar Tabel
iv
1 Pengantar Logika Proposisional & Operator Logika 1.1
Definisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Kesetaraan Logis Dan Relasi Ekivalensi 2.1
Pernyataan dan Bukan Pernyataan . . . . . . . . . . . . . . . .
1 1 7 7
3 Argumen & Validitas
8
4 Pohon Semantik
9
5 Kuantor Pernyataan Dan Induksi Matematika
10
6 Logika Predikat
11
7 Aljabar Boolean
12
8 Gerbang Logika
13 ii
Daftar Isi 9 Penyederhanaan Fungsi Boolean Secara Aljabar & Peta Karnaugh 14 10 Penyederhanaan Fungsi Boolean Dengan Metode Quine-Mccluskey 15 A Perhitungan Mean dan Variansi Pada Model
17
Daftar Pustaka
17
iii
Daftar Gambar
iv
Daftar Tabel
1.1
Tabel kebenaran Inclusive or
. . . . . . . . . . . . . . . . . . .
2
1.2
Tabel kebenaran Exclusive or . . . . . . . . . . . . . . . . . . .
3
1.3
Tabel kebenaran Exclusive or . . . . . . . . . . . . . . . . . . .
5
v
Bab 1 Pengantar Logika Proposisional & Operator Logika 1.1
Definisi
• Logika adalah suatu sistem berbasis proposisi. • Sistem adalah kesatuan yang terdiri dari komponen atau elemen yang dihubungkan bersama untuk memudahkan aliran informasi, materi, atau energi untuk mencapai suatu tujuan. • Proposisi adalah suatu pernyataan (statement) yang dapat bernilai benar (true) atau salah (false), tetapi tidak keduanya. • Dikatakan bahwa nilai kebenaran suatu proposisi adalah salah satu dari Benar (True) disajikan dengan T atau Salah (False) disajikan dengan F. • Dalam untaian digital (digital circuits) disajikan dengan 0 dan 1. • Jika proposisi-proposisi akan dikombinasikan untuk memperoleh proposisi baru maka diperlukan operator logika yang dilambangkan sebagai berikut. 1. ¬ : ’not’ tau negasi 2. ∧ : ’and’ atau konjungsi 1
BAB 1 : Pengantar Logika Proposisional & Operator Logika 3. ∨ : ’or’ atau disjungsi atau ’inclusive or’ 4. −→ : implies, atau ’Jika . . . maka . . .’, atau ’implikasi kondisional’ 5. ←→ : ’jika dan hanya jika’, atau ’bikondisional’ 1. Negasi Jika p sebarang proposisi, penyataan ”not p” atau ”negasi daripada p” akan bernilai F jika p bernailai T dan sebaliknya. Ditulis dengan ¬p 2. Konjungsi / conjunction (and ) Konjungsi adalah suatu operator binary atau diadika (diadic). Jika p dan q suatu proposisi, pernyataan p dan q akan benilai kebenaran T jika dan hanya jika kedua p dan q mempunyai nilai kebenaran T, dan ditulis dengan p∧q. Sifat: (a) Komutatif (p ∧ q = q ∧p) (b) Asosiatif ((p ∧q)∧r = p ∧ (q ∧ r)) 3. Disjungsi (or ) Pernyataan ”p or q” bernilai T jika dan hanya jika salah satu p atau q (atau keduanya) bernilai T ditulis dengan p ∨ q. Sifat: (a) Komutatif (p ∨ q = q ∨ p) (b) Asosiatif ((p ∨ q) ∨ r = p ∨ (q ∨ r)) Terdapat dua pengertian or yaitu inclusive or dan exclusive or. Inclusive or peristiwanya dapat terjadi keduanya bersamaan. Exclusive or peristiwanya tidak dapat terjadi keduanya bersamaan. Tabel 1.1: Tabel kebenaran Inclusive or p
∨
q
T T F F
T T T F
T T T F
2
BAB 1 : Pengantar Logika Proposisional & Operator Logika Tabel 1.2: Tabel kebenaran Exclusive or p
Y
q
T T F F
F T T F
T F T F
4. Implikasi (Implication) Arti daripada pernyataan ”if p then q” atau ”q if p” atau ”p hanya jika q” atau ”q syarat perlu untuk p” atau ”p syarat cukup untuk q” adalah T jika salh satu dari p bernilai T dan q bernilai T atau jika p benilai F. Ilustrasi dari implikasi adalah sebagai berikut ”Jika Anita pergi keluar negeri maka ia mempunyai passport” Penjelasannya adalah sebagai berikut. (a) Jika Anita keluar negeri (T) dan Ia mempunyai passport (T), maka legal (T) (b) Jika Anita keluar negeri (T) dan Ia tidak mempunyai passport (F), maka ilegal (F) (c) Jika Anita tidak keluar negeri (F) dan Ia mempunyai passport (T), maka legl (T) (d) Jika Anita tidak keluar negeri (F) dan Ia tidak memiliki passport (F), maka legal (T) Pernyataan p → q selalu mempunyai tabel kebenaran (¬p) ∨ q dan juga dengan ¬ (p ∧ ¬ q) 5. Ekuivalensi Pernyataan ”p ekuivalen dengan q” mempunyai nilai kebenaran T jika dan hanya jika p dan q mempunyai nilai kebenaran yang sama ditulis dengan simbol p↔q. Sifat:
3
BAB 1 : Pengantar Logika Proposisional & Operator Logika (a) Komutatif (p ↔ q = q ←→ p) (b) Asosiatif ((p ↔ q) ↔r = p ↔ (q ↔ r)) (c) Pernyataan ¬ (p ↔ q) mempunyai tabel kebenaran yang sama dengan pernyataan p Y q (d) Perhatikam bahwa ia juga dapat dipikirkan sebagai pernyataan ”p jika dan hanya jika q” (e) Bikondisial : p ↔ q = (p → q) ∧ (q → p) Prioritas Operator Seperti pada ungkapan dalam ilmu hitung, maka operator logika pun terdapat prioritas sebagai berikut. 1. Operator (¬) prioritas tertinggi 2. Operator (∧) berprioritas berikutnya 3. Operator (∨) berprioritas berikutnya 4. Operator (→) berprioritas berikutnya 5. Operator (↔) berprioritas berikutnya 6. dan seterusnya operator yang lain Contoh: 1. ”Saya lapar” dan ”Saya malas” atau ”Saya bahagia” dan ”Saya telah makan enak”, berarti (Saya lapar dan saya malas) atau (Saya bahagia dan saya telah makan enak) 2. ”Saya lapar ∧ saya sedih ∨ saya bahagia ∧ saya telah kekenyangan”, berarti (Saya lapar ∧ saya sedih) ∨ (Saya bahagia ∧ saya telah kekenyangan)
4
BAB 1 : Pengantar Logika Proposisional & Operator Logika 3. p ∧ ¬q ∨ r → s ↔ p ∨ ¬r ∧ t Diartikan sebagai (((p ∧ (¬q)) ∨ r) → s) ↔ (p ∨ (¬r)) ∧ t Kalimat yang bukan pernyataan diantaranya kalimat perintah, kaimat pertanyaan, kalimat keheranan, kalimat harapan Logika Proporsional (Notasi Operator logis/ functor) Tabel 1.3: Tabel kebenaran Exclusive or
Operator Konjungsi Disjungsi Negasi Implikasi Bi-implikasi
Prof. Suhakso Peano Russel p&q p∨q p ;p p→q p↔q
p. q p∨q p p⊃q p≡q
Hilbert
Burke
p&q p∨q p p→q pq
p∧q p∧q p∨q p∨q ¬p ¬p p⇒q p→q p⇔q p↔q
Contoh
1. Notasi Polandia: E p q Disajikan dalam notasi yag lain: p ↔ q = p ≡ q = p q 2. Polandia: C K p q r Disajikan dalam notasi lain: C (p & q) r = (p & q) → r 3. Notasi Operator logika biasa: ¬(p ∨ q) Disajikan dalam notasi polandia : N A p q 4. Notasi Operator Logika Biasa : ¬((p ∨ q) → r) Disajikan dalam notasi polandia : N C A p q r 5. Notasi operator logika biasa: ((p∨ q)→ r ↔ (p ∧ q ) Disajikan dalam notasi polandia” E C A p q r K p q
5
Kuliah
Polandia Kpq p∨q Np Cpq Epq
BAB 1 : Pengantar Logika Proposisional & Operator Logika 6. Notasi opertaor logika biasa : ((p ∨ q) → (q ∨ r)) ↔ ¬ (p ∨¬ r ) Disajikan dalam notasi polandia: E C A p q K q r N C A p N r q 7. Notasi Operator Logika Biasa: ((p ∧ q) → r) ↔ ((p ∧ ¬r) → ¬q) ((Kpq) → r) ↔ ((p ∧ ¬r) →)¬q) C(Kpq)r ↔ ((p ∧ ¬r) → ¬q) C(Kpq)r ↔ ((p ∧ (N r)) → ¬q) C(kpq)r ↔ (Kp(N r) → ¬q) C(Kpq)r ↔ (Kp(N r) → (N q)) C(Kpq)r ↔ (C(Kp(N r)(N q)) ECKpqrCKpN rN q
6
Bab 2 Kesetaraan Logis Dan Relasi Ekivalensi 2.1
Pernyataan dan Bukan Pernyataan
Mana yang pernyataan dan mana yang bukan pernyataan: 1. Ngawi adalah ibukota propinisi Jawa Timur 2. Dilarang merokok 3. Sesama Cabup tidak boleh saling mendahului
7
Bab 3 Argumen & Validitas
8
Bab 4 Pohon Semantik
9
Bab 5 Kuantor Pernyataan Dan Induksi Matematika
10
Bab 6 Logika Predikat
11
Bab 7 Aljabar Boolean
12
Bab 8 Gerbang Logika
13
Bab 9 Penyederhanaan Fungsi Boolean Secara Aljabar & Peta Karnaugh
14
Bab 10 Penyederhanaan Fungsi Boolean Dengan Metode Quine-Mccluskey
15
Daftar Pustaka 1. Heri Sismoro. 2005. Pengantar Logika Informatika, Algoritma dan Pemrograman Komputer. Penerbit ANDI : Yogyakarta 2. Program Studi Teknik Informatika (2014). Bahan Ajar Logika Informatika. Universitas Negeri Semarang 3. Retno Hendrowati dan Bambang Hariyanto. 2000. Logika Matematika. Penerbit Informatika : Bandung 4. Setiadji. 2007. Logika Informatika. Penerbit Graha Ilmu : Yogyakarta. 5. Soesianto, F & Djoni Dwijono. 2010. Logika Matematika untuk Ilmu Komputer. Andi. Yogyakarta
16
Lampiran A Perhitungan Mean dan Variansi Pada Model
17
