Selamat Datang di
MA 2251 Matematika Diskrit Semester II, 2016/2017 Rinovia Simanjuntak & Saladin Uttunggadewa
1
Referensi Pustaka Kenneth H. Rosen, Discrete Mathematics and its Applications, 7th edition, 2007.
On the Web http://rinosimanjuntak.wordpress.com/teaching (Berisi informasi perkuliahan, slide, bahan kuliah, dan tugas.)
2
Evaluasi • Ujian: Test 1 dan Test 2
50%
• Diskusi Kelompok: 3 kali
15%
• Kuis/Tugas Individu: 3 kali
15%
• Tugas Pemrograman (Kelompok): 2 kali
20%
3
Matematika Diskrit? Cabang matematika yang mempelajari tentang obyek diskrit. (Diskrit berarti memuat elemen yang berbeda dan tak terhubung). Berbagai masalah yang dapat dipecahkan dengan menggunakan matematika diskrit: – Ada berapa cara untuk memilih password yang valid untuk suatu sistem komputer? – Berapa peluang untuk menang dalam suatu undian? – Apakah ada link antara dua komputer dalam suatu jaringan komputer? – Bagaimana mengenali e-mail spam? – Bagaimana cara mengenkripsi pesan sehingga hanya orang tertentu dapat membacanya? – Bagaimana menentukan lintasan terpendek antara dua kota dengan menggunakan sistem angkutan umum? – Bagaimana mengurutkan suatu kumpulan data? – Berapa langkah yang diperlukan untuk melakukan pengurutan tersebut? – Ada berapa alamat internet yang valid? – Bagaimana memetakan genetik manusia? (Genome project) – Bagaimana mengatur jadwal take-off/landing/parkir pesawat-pesawat di bandara? 4
Mengapa Belajar Matematika Diskrit ? • Dapat dibangun kedewasaan dalam bermatematika, yaitu kemampuan untuk memahami dan membuat argumen matematis.
• Merupakan landasan berbagai bidang matematika: logika, teori himpunan, teori bilangan, aljabar linier dan abstrak, kombinatorika, teori graf, teori peluang (diskrit). • Merupakan landasan ilmu komputer: struktur data, algoritma, teori basis data, bahasa formal, teori automata, teori compiler, sistem operasi, dan pengamanan komputer (computer security). • Memuat latar belakang matematis yang diperlukan untuk memecahkan masalah dalam riset operasi (optimasi diskrit), kimia, ilmu rekayasa, biologi, dsb. 5
Silabus • Logika (1.1-1.5) • Bukti (1.6-1.8) • Struktur Disktrit – – – –
Himpunan (2.1-2.2, 2.5) Fungsi (2.3) Barisan dan Deret (2.4) Matriks (2.6)
• Algoritma (3.1-3.3) • Induksi (5.1-5.2) • Rekursi (5.3)
• Counting – – – –
Dasar counting (6.1) Prinsip Sarang Merpati (6.2) Permutasi dan Kombinasi (6.3) Koefisien Binomial (6.4)
• Peluang Diskrit (7.1-7.2) • Teknik Counting Lanjut – Relasi recurrence (8.1-8.2) – Fungsi pembangkit (8.4) – Inklusi-Ekslusi (8.5-8.6)
• Relasi (9.1, 9.3-9.6)
6
Bab 1 The Foundations: Logic and Proofs 1.1. PROPOSITIONAL LOGIC
7
Logika dan Proposisi • Logika merupakan dasar dari semua penalaran matematis. • Aturan logika memberikan arti pada pernyataan matematika dan digunakan untuk membedakan pernyataan yang valid dan tidak valid. • Blok pembangun logika adalah proposisi.
Proposisi: pernyataan yang bernilai benar atau salah, tapi tidak keduanya. • Untuk menotasikan proposisi, digunakan alfabet seperti p, q, r, s • Kita katakan bahwa nilai kebenaran dari suatu proposisi adalah benar (T) atau salah (F). • Berkorespondensi dengan 1 dan 0 dalam dunia digital. 8
Contoh Proposisi “Gajah lebih besar daripada kucing.”
Ini suatu pernyataan ?
ya
Ini suatu proposisi ?
ya
Apa nilai kebenaran dari proposisi ini ?
T 9
Contoh Proposisi (2) “1089 < 101”
Ini pernyataan ?
ya
Ini proposisi ?
ya
Apa nilai kebenaran dari proposisi ini ?
F 10
Contoh Proposisi (3) “y > 15”
Ini pernyataan ?
ya
Ini proposisi ?
tidak
Nilai kebenaran bergantung pada nilai y yang tidak spesifik. Pernyataan seperti ini kita sebut fungsi proposisi atau kalimat terbuka. 11
Contoh Proposisi (4) “Bulan ini Februari dan 24 < 5.”
Ini pernyataan ?
ya
Ini proposisi ?
ya
Nilai kebenaran dari proposisi tersebut ?
F 12
Contoh Proposisi (5) “Jangan tidur di kelas.”
Ini pernyataan ?
tidak
Ini permintaan. Ini proposisi ?
tidak
Hanya pernyataan yang dapat menjadi proposisi. Perintah dan pertanyaan bukanlah proposisi. 13
Contoh Proposisi (6) “Jika gajah berwarna merah, mereka dapat berlindung di bawah pohon cabe.”
Ini pernyataan ?
ya
Ini proposisi ?
ya
Apa nilai kebenaran proposisi tersebut ?
F (?) 14
Contoh Proposisi (7) “x < y jika dan hanya jika y > x.”
Ini pernyataan ? ya Ini proposisi ? ya … sebab nilai kebenarannya tidak bergantung pada nilai x dan y.
Apa nilai kebenaran dari proposisi tsb ?
T 15
Proposisi Majemuk Satu atau lebih proposisi dapat digabung membentuk sebuah proposisi majemuk dengan menggunakan beberapa operator logika. – – – – – –
Negasi (NOT) Konjungsi - Conjunction (AND) Disjungsi - Disjunction (OR) Eksklusif Or (XOR) Implikasi (IF-THEN) Bikondisional (IF AND ONLY IF)
Tabel kebenaran dapat digunakan untuk menunjukkan nilai kebenaran dari proposisi majemuk. 16
Negasi (NOT) Operator Uner, Simbol: p
p
true
false
false
true
17
Konjungsi (AND) Operator Biner, Simbol: p
q
pq
true
true
true
true
false
false
false
true
false
false
false
false
18
Disjungsi (OR) Operator Biner, Simbol: p
q
pq
true
true
true
true
false
true
false
true
true
false
false
false
19
Exclusive Or (XOR) Operator Biner, Simbol: p
q
pq
true
true
false
true
false
true
false
true
true
false
false
false
20
Implikasi (IF-THEN) Implikasi p q adalah proposisi yang bernilai salah jika p benar dan q salah, dan bernilai benar jika lainnya. p
q
pq
true
true
true
true
false
false
false
true
true
false
false
true 21
Implikasi p q • • • • • •
Jika p, maka q Jika p, q p mengakibatkan q p hanya jika q p cukup untuk q Syarat perlu untuk p adalah q
• • • • • •
q jika p q ketika p q diakibatkan p q setiap kali p q perlu untuk p Syarat cukup untuk q adalah p
22
Contoh Implikasi Implikasi “Jika hari ini hari Jumat maka 2+3 > 7.” bernilai benar untuk semua hari kecuali hari Jumat, walaupun 2+3 > 7 bernilai salah.
Kapan pernyataan berikut bernilai benar? “Jika hari tidak hujan maka saya akan pergi ke Lembang.”
23
Konversi, Kontrapositif, dan Invers • q p disebut konversi dari p q • q p disebut kontrapositif dari p q • p q disebut invers dari p q Contoh. Berikan konversi, kontrapositif, dan invers dari pernyataan berikut: “Persib menang setiap kali hari hujan.” 24
Bikondisional (IF AND ONLY IF)
Operator Biner, Simbol: p
q
pq
true
true
true
true
false
false
false
true
false
false
false
true
25
Bikondisional pq • p perlu dan cukup untuk q • jika p maka q, dan sebaliknya • p iff q Contoh. Seseorang dapat naik pesawat jika dan hanya jika ia membeli tiket. 26
Soal 1.1.5 1.1.6 1.1.10 1.1.39
27
1.2. APPLICATIONS OF PROPOSITIONAL LOGIC 28
Bahasa dalam Ekspresi Logika (1) Contoh. Ubah ke dalam ekspresi logika: “Anda mempunyai akses internet hanya jika anda mahasiswa Matematika ITB atau anda bukan mahasiswa TPB” Solusi. Misal a : “Anda punya akses internet” m: “Anda mhs Matematika ITB” f: “Anda mhs TPB” a (m f)
29
Bahasa dalam Ekspresi Logika (2) Soal 1. Ubah kedalam ekspresi logika.
“Anda tidak boleh naik roller coaster jika tinggi anda kurang dari 100 cm, kecuali usia anda sudah melebihi 16 th.” “Saya akan ingat tentang kuliah besok hanya jika kamu mengirim sms.” “Pantai akan erosi ketika ada badai”
30
Spesifikasi Sistem Contoh. “The automated reply cannot be sent when the file system is full.” Spesifikasi sistem disebut konsisten jika spesifikasi tersebut tidak memuat pernyataan yang mengakibatkan kontradiksi. Contoh. Tentukan apakah spesifikasi sistem berikut konsisten. “The diagnostic message is stored in the buffer or it is retransmitted.” “The diagnostic message is not stored in the buffer.” “If the diagnostic message is stored in the buffer, then it is retransmitted.” “The diagnostic message is not retransmitted” 31
Puzzle Logika (1) (Smullyan, ‘98) Suatu pulau mempunyai dua macam penghuni, yaitu penjujur (orang yg selalu berkata benar) dan pembohong (orang yg selalu berkata salah/bohong). Anda bertemu dua orang A dan B di pulau itu. Jika A berkata bhw “B penjujur” dan B berkata bhw “kami berdua mempunyai tipe yg berlainan”, maka apa yang dapat anda simpulkan tentang A dan B.
32
Puzzle Logika (2) §1.1 No. 60 Alice: Carlos did it. Carlos: Diana did it. Diana: Carlos is lying. John: I didn’t do it. Oracle: Only one of them is telling the truth. Problem: Who did it?
33
Dengan menggunakan tabel kebenaran, cari baris di mana hanya 1 pernyataan yang benar
34
Latihan 1.2.5 1.2.17 1.2.34
35
1.3. PROPOSITIONAL EQUIVALENCES
36
Salah satu langkah penting dalam argumentasi matematis adalah mengganti suatu pernyataan dengan pernyataan lain yang memiliki nilai kebenaran yang sama.
37
Tautologi Tautologi adalah suatu pernyataan majemuk yang selalu benar. Contoh: • R(R) • (PQ)(P)(Q) Jika ST suatu tautologi, kita tulis ST. Jika ST suatu tautologi, kita tulis ST.
38
Kontradiksi Kontradiksi adalah pernyataan majemuk yang selalu bernilai salah. Contoh: • R(R) • ((PQ)(P)(Q)) Negasi dari suatu tautologi adalah suatu kontradiksi, negasi dari kontradiksi adalah suatu tautologi.
39
Pernyataan yang Ekivalen (1)
P
Q
PQ
(PQ)
(P)(Q)
true
true
true
false
false
true
false
false
true
true
false
true
false
true
true
false
false
false
true
true
40
Pernyataan yang Ekivalen (2) Dua pernyataan majemuk yang memiliki nilai kebenaran yang sama untuk semua kasus yang mungkin disebut ekivalen secara logika. Notasi p ≡ q berarti p dan q ekivalen secara logika. P
Q
(PQ)
(P)(Q)
(PQ)(P)(Q)
true
true
false
false
true
true
false
true
true
true
false
true
true
true
true
false
false
true
true
true
Pernyataan (PQ) dan (P)(Q) ekivalen
(Note: (PQ)(P)(Q) selalu benar)
41
Ekivalen secara Logika
42
Contoh Tunjukkan bahwa￢(p ∨ (￢p ∧ q)) dan ￢p ∧￢q adalah ekivalen secara logika. Solusi. METODA 1 dengan menggunakan Tabel Kebenaran METODA 2 dengan menggunakan sekumpulan ekivalensi 43
Solusi dengan Metoda 2 ￢(p ∨ (￢p ∧ q)) ≡ ￢p ∧￢(￢p ∧ q) ≡ ￢p ∧ [￢(￢p)∨￢q] ≡ ￢p ∧ (p ∨￢q) ≡ (￢p ∧ p) ∨ (￢p ∧￢q) ≡ F ∨ (￢p ∧￢q) ≡ (￢p ∧￢q) ∨ F ≡ ￢p ∧￢q
Hukum De Morgan Hukum De Morgan Sifat distributif ￢p ∧ p ≡ F
Sifat komutatif
44
1.4. PREDICATES AND QUANTIFIERS
45
Predikat dan Kuantifier Pernyataan “x > 3” punya 2 bagian, yakni “x” sebagai subjek dan “ adalah lebih besar 3” sebagai predikat P. Kita dpt simbolkan pernyataan “x > 3” dengan P(x). Sehingga kita dapat mengevaluasi nilai kebenaran dari P(4) dan P(1). Subjek dari suatu pernyataan dapat berjumlah lebih dari satu. Contoh. Q(x,y): x - 2y > x + y 46
Kuantifikasi Universal “P(x) benar untuk semua nilai x dalam domain pembicaraan” x P(x).
Soal 2. Tentukan nilai kebenaran x (x2 x) jika:
x bilangan real x bilangan bulat Untuk menunjukkan x P(x) salah, cukup dengan mencari satu nilai x dalam domain shg P(x) salah. Nilai x tersebut dikatakan contoh penyangkal (counter example) dari pernyataan x P(x).
47
Kuantifikasi Eksistensi “Ada nilai x dalam domain pembicaraan sehingga P(x) bernilai benar” x P(x). Soal 3. Tentukan nilai kebenaran dari x P(x) bila P(x) menyatakan “x2 > 12” dan domain pembicaraan meliputi semua bilangan bulat positif tidak lebih dari 4.
48
Negasi “Setiap mhs dalam kelas ini telah mengambil Kalkulus IA” x P(x) Apakah negasi dari pernyataan ini….? “Ada seorang mhs dalam kelas ini yang belum mengambil Kalkulus IA” x P(x)
Jadi, x P(x) x P(x).
49
Negasi (2) Soal 4. Carilah negasi dari pernyataan berikut: “Ada politikus yang jujur” “Semua orang Indonesia makan pecel lele” Soal 5. Tentukan negasi dari: x(x2 > x) x (x2 = 2) 50
1.5. NESTED QUANTIFIERS
51
Kuantifier Bersusun x y (x+y = y+x) berarti x+y = y+x berlaku untuk semua bilangan real x dan y.
x y (x+y = 0) berarti untuk setiap x ada nilai y sehingga x+y = 0. x y z (x+(y+z) = (x+y)+z) berarti untuk setiap x, y dan z berlaku hukum asosiatif x+(y+z) = (x+y)+z.
52
Soal Soal 6. Artikan kalimat ini dalam bhs Indonesia: x (C(x) y ( C(y) F(x,y))), bila C(x) : “x mempunyai komputer”, F(x,y): “x dan y berteman”, dan domainnya adalah semua mhs di kampus. Soal 7. Bagaimana dengan berikut ini: x y z((F(x,y) F(x,z) (y z) F(y,z)) Soal 8. Nyatakan negasi dari pernyataan x y (xy=1). 53
