Dasar-dasar Logika (Review)
Intro Logika berhubungan dengan kalimat-kalimat dan hubungan antar kalimat. Tujuan: menentukan apakah suatu kalimat / masalah bernilai benar (TRUE) atau salah (FALSE) Kalimat Deklaratif (proposition): bernilai benar atau salah, tapi tidak keduanya. Dilambangkan dengan (p, q, r.....) Contoh: a. 2 + 2 = 4 (benar) b. 4 adalah bilangan prima (salah) Lawan kalimat deskriptif adalah Kalimat Terbuka contoh: x + y = 2 (nilai kebenaran tergantung x dan y) Di manakah letak pulau Bali? (kalimat tanya)
Connectivity Connective (penghubung): menghubungkan dua buah propositions syntactics rule (aturan sintaktik): aturan yang diperlukan untuk menggabungkan propositions dan connectives, sehingga menghasilkan sentences (kalimat logika) Propositions + connectives = sentences
Syntactics Rule (Aturan Sintaktik) Simbol
¬ atau ~ ∧ ∨ →
↔
Arti
Bentuk
Tidak / not / negasi
NOT.....
Dan / And / Konjungsi
...... AND / BUT .....
Atau / Or / Disjungsi
...... OR .....
Implikasi
IF ..... THEN .....
Bi-implikasi / Equivalence
..... IF AND ONLY-IF .....
Note: bentuk “tetapi” mempunyai arti sama dengan “dan”
Contoh p : “hari ini panas” (proposition # 1) q: “hari ini cerah” (proposition # 2) Hari ini tidak panas tetapi cerah: ~p q Hari ini tidak panas dan tidak cerah: ~p ~q Tidak benar bahwa hari ini panas dan cerah: ~(p q)
Semantic Rules (Aturan Semantik) Interpretasi: pemberian “truth value” (TRUE atau FALSE) pada penghubung (connective) dari suatu kalimat logika (sentences). Semantic Rules: suatu aturan yang digunakan untuk menentukan truth value dari suatu sentence, yaitu : 1. Negation Rule (Aturan NOT) 2. Conjunction Rule (Aturan AND) 3. Disjunction Rule (Aturan OR) 4. Implication Rule (Aturan IF-THEN) 5. Bi-implication/Equivalence Rule (Aturan IF -AND ONLY IF -) 6. Conditional Rule (Aturan IF–THEN-ELSE)
Semantic Rule (Aturan Semantik) Negation Rule (Aturan NOT) p
not p
true
false
false
true
Semantic Rule (Aturan Semantik) Conjunction Rule (Aturan AND) Conjunction bernilai “benar” bila dua buah penyusunnya bernilai benar p
q
p and q
true
true
true
true
false
false
false
true
false
false
false
false
Semantic Rule (Aturan Semantik) Disjunction Rule (Aturan OR) Disjunction bernilai “salah” bila dua buah penyusunnya bernilai salah p
q
p or q
true
true
true
true
false
true
false
true
true
false
false
false
Sifat aljabar logika untuk conjunction dan disjunction Hukum Idempoten p or p = p p and p = p Hukum Komutatif p or q = q or p p and q = q and p Hukum Assosiatif (p or q) or r = p or (q or r) (p and q) and r = p or (q or r)
Sifat aljabar logika untuk conjunction dan disjunction Hukum Distributif p or (q and r) = (p or q) and (p or r) p and (q or r) = (p and q) or (p and r) Hukum Identitas p or false = p p and true = p p or true = true p and false = false
Sifat aljabar logika untuk conjunction dan disjunction Hukum Komplemen p or not p = true p and not p = false not (not p) = p Hukum De Morgan negasi dari konjungsi dan disjungsi not (p or q) = not p and not q not (p and q) = not p or not q
Semantic Rule (Aturan Semantik) Implication Rule (Aturan IF-THEN) Implikasi bernilai “salah” bila anteseden (p) benar dan konsekuen (q) salah.
p
q
if p then q
true
true
true
true
false
false
false
true
true
false
false
true
Semantic Rule (Aturan Semantik) Implication Rule (Aturan IF-THEN) Jika ( p → q ) adalah implikasi, maka :
( q → p ) adalah konvers ( ¬p → ¬q ) adalah invers ( ¬q → ¬p ) adalah kontraposisi Jika ( p → q ) bernilai benar, maka: belum tentu ( q → p ) , ( ¬p → ¬q ) , ( ¬q → ¬p ) bernilai benar.
Semantic Rule (Aturan Semantik) Bi-Implication/Equivalence Rule (Aturan IF -AND ONLY IF -) Bi-implication bernilai “benar”, jika penyusun proposisi bernilai sama
p
q
p if and only if q
true
true
true
true
false
false
false
true
false
false
false
true
Semantic Rule (Aturan Semantik) Conditional Rule (Aturan IF–THEN-ELSE) Jika p bernilai benar maka q berlaku; Jika p bernilai salah maka r berlaku
p true true true true false false false false
q true true false false true true false false
r true false true false true false true false
if p then q else r true true false false true false true false
Inferensi Logika (Pengambilan Kesimpulan)
Logika selalu berhubungan dengan pernyataaan-pernyataan yang ditentukan nilai kebenarannya Untuk menentukan sebuah kesimpulan, didasarkan pada sejumlah kalimat yang diketahui nilai kebenarannya
Inferensi Logika (Pengambilan Kesimpulan) Argumen: rangkaian kalimat-kalimat Semua kalimat-kalimat tersebut disebut hipotesa (asumsi/premise), kecuali kalimat kesimpulan Argumen valid: semua hipotesa BENAR, kesimpulan BENAR Argumen tidak valid: semua hipotesa BENAR, kesimpulan SALAH p1 ⎫ ⎪ p2 ⎪ ⎬ hipotesa .... ⎪ pn ⎪ ⎭ ____________ ∴q
}
kesimpulan
dibaca : “jadi q”
Prosedur Inferensi: Tentukan hipotesa dan kesimpulan kalimat Buat tabel yang menunjukkan nilai kebenaran untuk semua hipotesa dan kesimpulan (jumlah kombinasi 2n di mana n = jumlah proposisi ) Carilah baris kritis, baris di mana semua hipotesa bernilai benar Dalam baris kritis tersebut, jika semua nilai kesimpulan benar, maka argumen valid. Jika di antara baris kritis tersebut ada baris dengan nilai kesimpulan yang salah, maka argumen invalid
Contoh Soal Tentukan apakah argumen di bawah ini valid:
p ∨ (q ∨ r ) ¬r ∴p∨q
Jawaban Soal Ada dua hipotesa, masing-masing dan . Kesimpulannya ¬r
Baris ke-
p
q
r
q∨r
p ∨ (q ∨ r )
1
T
T
T
T
T
F
T
2
T
T
F
T
T
T
T
3
T
F
T
T
T
F
T
4
T
F
F
F
T
T
T
5
F
T
T
T
T
F
T
6
F
T
F
T
T
T
T
7
F
F
T
T
T
F
F
8
F
F
F
F
F
T
F
p∨q
Maka, argumen tersebut valid
baris kritis baris kritis baris kritis
Metode Inferensi Logika (1) Modus Ponens p→q p ∴q
Contoh: Jika seseorang itu adalah pengusaha ia pasti kaya Pak Jalal adalah seorang pengusaha Pak Jalal pasti kaya
Metode Inferensi Logika (2) Modus Tollens p→q ¬q ∴ ¬p
Contoh: Jika Pak Jalal adalah pengusaha yang baik maka ia pasti tidak bangkrut Pak Jalal bangkrut Pak Jalal bukan pengusaha yang baik
Metode Inferensi Logika (3) Penambahan Disjungtif p ∴p∨q
q ∴p∨q
Contoh: Udin adalah siswa SMA (Sekolah Menengah Atas) Jadi, Udin adalah siswa sekolah menengah (SMP atau SMA)
Metode Inferensi Logika (4) Penyederhanaan Konjungtif p∧q ∴p
p∧q ∴q
Contoh: Asrul menguasai bahasa C dan PHP Asrul menguasai bahasa C
Metode Inferensi Logika (5) Silogisme Disjungtif p∨q ¬p
p∨q ¬q
∴q
∴p
Contoh: Kunci kamarku ada di sakuku atau tertinggal di rumah Kunci kamarku tidak ada di saku Kunci kamarku pasti tertinggal di rumah
Metode Inferensi Logika (6) Silogisme Hipotesis p→q q→r ∴p→r
Contoh: Jika ia rajin maka ia pasti pandai Jika ia pandai maka ia pasti sukses Jika ia rajin maka ia pasti sukses
Metode Inferensi Logika (7) Dilema p∨q p→r q→r ∴r Contoh:
Nanti malam, pertandingan bola dimenangkan oleh Barcelona atau Manchester United Jika Barcelona menang, saya akan senang Jika Manchester United menang, saya akan senang Nanti malam saya akan senang
Metode Inferensi Logika (8) Konjungsi p q ∴p∧q
Contoh: Saya adalah seorang mahasiswa Saya adalah seorang pengusaha Saya adalah seorang mahasiswa sekaligus pengusaha
Tugas #1 http://te.ugm.ac.id/~wibirama/notes Cek di mata kuliah Algoritma dan Struktur Data Download file TugasASD250211.pdf Jawaban dikirim ke
[email protected] dengan format nama file dan subject pada email Anda sesuai petunjuk di file tugas Deadline : Kamis, 03 Maret 2011 pkl.23.59 WIB
Catatan Re-scheduling jadwal dari kantor S2: ASD akan dilaksanakan hari Jum’at jam 08.15 di ruang E3 (karena jam 10.00 ruang kelas dialokasikan untuk Pak Ridi) Bahan-bahan kuliah ASD akan kami upload di PAPIRUS S2 mulai minggu depan
Terima Kasih
