MSH1B3 Logika Matematika Dosen: Aniq A Rohmawati, M.Si Kalkulus Proposisi [Definisi] Metode yang digunakan untuk meninjau nilai kebenaran suatu proposisi atau kalimat Contoh • Jika Anda belajar di Tel-U maka Anda mahasiswa Jika Anda mahasiswa maka Anda punya buku Jika Anda belajar di Tel-U maka ... Penggantian Proposisi (Simbol) • Misalkan A adalah Anda belajar di Tel-U, B adalah Anda mahasiswa, C adalah Anda punya buku Diperoleh: Jika A maka B. Jika B maka C. Jika A maka ... Subkalimat Setiap kalimat antara, yang dipakai untuk membangun kalimat A, termasuk kalimat A itu sendiri. Sedangkan, subkalimat murni adalah setiap kalimat antara, yang dipakai untuk membangun kalimat A tetapi tidak termasuk kalimat A itu sendiri. Contoh Misalkan p dan q merupakan kalimat, dengan E: Not (p or q) if only if (not p) and (not q). Terdapat 8 subkalimat dari E. Sebutkan! Silogisme Hipotesis Ekspresi Jika A maka B. Jika B maka C. Diperoleh, jika A maka C Silogisme Disjungtif Contoh Dia nilainya A atau tidak lulus. Dia lulus. Dengan demikian, ... Modus Ponens Contoh Jika Anda mahasiswa maka sudah lulus SMA. Dina mahasiswa. Dengan demikian, ...
1
Modus Tollens Contoh Jika Anda mahasiswa maka sudah lulus SMA. Dina tidak lulus SMA. Dengan demikian, ... Penghubung Logika (Aturan Semantik) • Konjungsi, (∧). Contoh: Didu suka makan dan tidur. • Disjungsi, (∨). Contoh: Didu suka makan atau tidur. • Negasi, (¬). Contoh: Didu tidak makan. Apakah ’lapar’ negasi dari ’kenyang’ ? • Implikasi, (→). Contoh: Jika hari mendung maka saya membawa payung. • Biimplikasi, (↔). Contoh: Saya akan membawa payung jika hanya jika hari mendung • Tunjukkan bentuk Konvers, Invers dan Kontraposisi dari contoh Implikasi! Latihan Ubahlah kalimat berikut menjadi kalimat dengan simbol proposisi! Sore hari ini mendung dan lebih dingin dari kemarin. Jika Ipin akan pergi bermain maka cuaca cerah. Jika Ipin tidak bermain maka Ipin akan pergi tidur. Jika Ipin pergi tidur maka Ipin akan berada dirumah tepat pada saat matahari terbenam. [Try again] Orang tua tidak perlu gelisah akan musibah jika anaknya dapat menjaga diri, akan tetapi kalau anaknya tidak bisa menjaga diri dan terjadi kecelakaan, maka mereka harus waspada mengawasinya. [Try again and again] Jika penawaran emas dibiarkan konstan dan permintaan emas bertambah maka harga emas naik. Jika permintaan emas bertambah yang menyebabkan harga emas naik maka ada keuntungan bagi spekulator. Penawaran emas dibiarkan konstan.
2
Hierarki (Prioritas) Penghubung 1. Negasi 2. Konjungsi 3. Disjungsi 4. Implikasi 5. Biimplikasi Contoh: • (¬A ∧ B), dibaca ((¬A) ∧ B) • A → B ∧ C, dibaca A → (B ∧ C) Latihan 1. A ∧ B ∧ C → D 2. A ∨ B ∨ C ↔ ¬D 3. ¬A ∧ B → ¬C ∨ D 4. A → B ↔ ¬C → ¬D Interpretasi Pemberian nilai kebenaran (true or false) pada setiap argumen atau kumpulan kalimat. Untuk menghindari ambiguitas maka proposisi majemuk yang akan dikerjakan terlebih dahulu harus diberi tanda kurung. Contoh: A: if x and not y then not x or z Jika x bernilai true, y bernilai false, z bernilai false. Diperoleh nilai kebenaran A adalah ... Latihan Jika nilai A, B adalah True, sedangkan C, D adalah False. Tentukan nilai kebenaran: (a) A ∧ (B ∨ C); (b) (¬(A ∧ B) ∨ ¬C) ∨ (((¬A ∧ B) ∨ ¬D) ∧ B)
3
Tautologi Ekspresi logika yang selalu memberikan nilai benar untuk semua kemungkinan nilai kebenaran dari variabel proposional. Bagaimana dengan Kontradiksi? Hukum - Hukum Logika 1. A → B ≡ ¬A ∨ B 2. A ↔ B ≡ (A → B) ∧ (B → A) 3. ¬¬A ≡ A 4. ¬(A ∧ B) ≡ ¬A ∨ ¬B 5. ¬(A ∨ B) ≡ ¬A ∧ ¬B 6. ¬(A → B) ≡ A ∧ ¬B 7. ¬(A ↔ B) ≡ (A ∧ ¬B) ∨ (¬A ∧ B) [Try] Buktikan dengan menggunakan tabel kebenaran bahwa ekspresi di bawah ini ekuivalen. • (A ∨ ¬B) → C ≡ (¬A ∧ B) ∨ C • A → B ≡ ¬(A ∧ ¬B)
Nilai Kebenaran Untuk membuktikan validitas sebuah kalimat diperlukan pembuktian nilai true untuk semua interpretasi yang mungkin. Penentuan nilai kebenaran suatu kalimat dapat dilakukan dengan 4 cara: if (p and q) then (p or (not r)) 1. Tabel Kebenaran 2. Tabel Jarang p
q
r
p and q
p or (not r)
if-then
T F
-
-
F
T -
T T
4
3. Pohon Semantik
4. Falsification - Pembuktian Terbalik Akan lebih mudah untuk membuktikan validasi kalimat, jika ada satu interpretasi kalimat benilai false maka kalimat tersebut tidak valid. A: (if (not x) or (not y)) then (not (x and y)) Misalkan A bernilai false, sehingga A: (if (not x) or (not y)) then (not (x and y)) → False diperoleh asumsi awal: (a) Antisenden: (not x) or (not y) → True (b) Konsekuen: not (x and y) → False diperoleh • Berdasarkan Konsekuen diperoleh: x and y bernilai True, sehingga Antisenden bernilai False (*) • Berdasarkan asumsi awal Antisenden: (not x) or (not y) bernilai True. Namun, bernilai False berdasarkan (*). Terdapat KONTRADIKSI (ketidaksesuaian) antara asumsi awal dengan interpretasi yang diperoleh maka kalimat A adalah VALID
5
• (Try) Tentukan validasi kalimat berikut ini dengan Tabel Kebenaran dan Tabel Jarang 1. p and (p or q) 2. (p and q) or ((if not p and q then p) or not q) 3. not (not p and not q) • (Try Again) Tentukan validasi kalimat berikut ini dengan Pohon Semantik if (if x then y) then (if (not x) then (not y)) • (Try Again and Again) Tentukan validasi kalimat berikut ini dengan Falsification (if x then y) if only if ((not x) or y) (Ekivalensi Logik) Dua buah kalimat A dan B merupakan ekivalensi logik jika hanya jika memiliki nilai yang sama pada semua interpretasi yang diberikan. (Teorema) A ekivalensi logik B untuk A iff B merupakan Tautologi. (Konsekuensi Logik) B adalah konsekuensi logik dari A jika untuk setiap pemberian nilai kebenaran ke A dan B, sehingga jika A bernilai TRUE maka B juga TRUE (Teorema) A konsekuensi logik B untuk if A then B merupakan Tautologi. (Catatan) Jika pernyataan lebih dari satu, misalkan A1, A2, A3 maka bentuk konsekuensi logiknya: If (A1 and A2 and A3) then B (Periksa) Apakah B merupakan kesimpulan dari 6 argumen dibawah ini. • A1: if P then (Q and R and S) • A2: if T then (if U then (if not Y then not S)) • A3: if Q then T 6
• A4: if R then (if X then U) • A5: if Y then not X • A6: X • B: not P Akan ditunjukkan: if (A1 and A2 and A3 and A4 and A5 and A6) then B Valid. (Konjungsi Disjungsi Jamak) Misalkan diberikan kalimat yang mengandung operator konjungsi/disjungsi lebih dari satu. Urutan pengerjaan operasi pada kalimat tersebut dari kiri ke kanan sesuai aturan. • Konjungsi Jamak bernilai TRUE jika setiap conjuct-nya adalah TRUE • Disjungsi Jamak bernilai TRUE jika setidaknya salah satu dari disjuctnya adalah TRUE (Substitusi Total) (x and (y or x)) J (x ← (if w then z)) menghasilkan (if w then z) and (y or (if w then z)) if x then (y and z) J ((y and z) ← w) menghasilkan if x then w (Catatan) 1. Substitusi total dikerjakan dalam satu langkah 2. Substitusi total tidak memiliki efek jika subkalimat yang akan diganti tidak muncul dalam kalimat 3. Subtitusi total untuk konjungsi dan disjungsi jamak (Substitusi Parsial) (x or x) / (x ← y) akan menghasilkan, x or x, y or x, x or y, y or y (Catatan) Substitusi parsial bersifat invertible, salah satu kalimat yang mungkin dihasilkan adalah kalimat semula. (A / (B ← C)) / (C ← B) hasilnya adalah ... 7
