Selamat Datang
Semester I 2007/2008
oleh :
Noorca Agus W.
DIV-KOMPUTER AKUNTANSI
POLITEKNIK NEGERI SEMARANG
Referensi
Pustaka
------------------
Samuel Wibisono, Matematika Diskrit, 2004, Penerbit Graha Ilmu.
Soesianto F. dan Djoni Dwijono, Logika Matematika untuk Ilmu Komputer, Penerbit Andi Yogyakarta.
Theresia MH. Tirta Saputro, Pengantar Dasar Matematika (Logika dan Teori Himpunan), Penerbit Erlangga, Jakarta.
Matematika Diskrit ?
Cabang matematika yang mempelajari tentang obyek-obyek diskrit.
Berbagai masalah yang dapat dipecahkan dengan menggunakan matematika diskrit:
Ada berapa cara untuk menentukan password yang valid untuk suatu sistem komputer?
Ada berapa alamat internet yang valid?
Bagaimana memetakan genetik manusia? (Genome project)
Berapa peluang untuk menang dalam suatu undian?
Apakah ada link antara dua komputer dalam suatu jaringan komputer?
Bagaimana mengatur jadwal take-off/landing/parkir pesawat-pesawat di bandara?
Bagaimana menentukan lintasan terpendek antara dua kota dengan menggunakan sistem angkutan umum?
Bagaimana mengurutkan suatu kumpulan data?
Evaluasi
Test regular: 4 kali (50%)
Tugas Individu 10 kali (30%)
Tugas kelompok: 4 kali (20%)
Kenapa belajar Matematika Diskrit ?
Landasan berbagai bidang matematika: logika, teori bilangan, aljabar linier dan abstrak, kombinatorika, teori graf, teori peluang (diskrit).
Landasan ilmu komputer: struktur data, algoritma, teori database, bahasa formal, teori automata, teori compiler, sistem operasi, dan pengamanan komputer (computer security).
Mempelajari latar belakang matematis yang diperlukan untuk memecahkan masalah dalam riset operasi (optimasi diskrit), kimia, ilmu teknik, ekonomi, dll.
Logika
Penting untuk bernalar matematis
Logika: sistem yg didasarkan atas proposisi.
Proposisi: pernyataan yang bernilai benar atau salah, tapi tidak kedua-duanya.
Kita katakan bahwa nilai kebenaran dari suatu proposisi adalah benar (T) atau salah (F).
Berkorespondensi dengan 1 dan 0 dalam dunia digital.
Contoh Proposisi
“Gajah lebih besar daripada kucing.”
Ini suatu pernyataan ? yes
Ini suatu proposisi ? yes
Apa nilai kebenaran dari
proposisi ini ? true
Contoh Proposisi (2)
“1089 <> 15”
Ini pernyataan ? yes
Ini proposisi ? no
Nilai kebenarannya bergantung pada nilai y, tapi nilai ini tidak spesifik.
Kita katakan tipe pernyataan ini adalah fungsi proposisi atau kalimat terbuka.
Contoh proposisi (3)
“Bulan ini Februari dan 24 <> x.”
Ini pernyataan ? yes
Ini proposisi ? yes
Apa nilai kebenaran dari proposisi tsb ? true
… sebab nilai kebenarannya tidak bergantung pada nilai x dan y.
Menggabungkan proposisi
Seperti dalam contoh sebelumnya, satu atau lebih proposisi dapat digabung membentuk sebuah proposisi majemuk (compound proposition).
Selanjutnya, notasi proposisi diformalkan dengan menggunakan alfabet seperti p, q, r, s, dan dengan memperkenalkan beberapa operator logika.
Operator Logika
Negasi (NOT)
Konjungsi - Conjunction (AND)
Disjungsi - Disjunction (OR)
Eksklusif Or (XOR)
Implikasi (JIKA – MAKA)
Bikondisional (JIKA DAN HANYA JIKA)
Tabel kebenaran dapat digunakan untuk menunjukkan bagaimana operator-operator tsb menggabungkan proposisi-proposisi.
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
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.”
false
false
true
false
true
false
true
false
false
true
true
true
P«Q
Q
P
Bikondisional (JIKA DAN HANYA JIKA)
Operator Biner, Simbol: «
true
true
true
false
Ø (PÙQ)
false
false
false
true
PÙQ
true
false
true
true
true
false
true
false
false
false
true
true
(ØP)Ú(ØQ)
Q
P
Pernyataan dan Operasi
Pernyataan-pernyataan dapat digabungkan dengan operasi untuk membentuk pernyataan baru.
true
true
true
false
(ØP)Ú(ØQ)
true
true
true
false
Ø(PÙQ)
true
false
true
true
true
false
true
false
false
true
true
true
Ø(PÙQ)«(ØP)Ú(ØQ)
Q
P
Pernyataan yang Ekivalen
Pernyataan Ø(PÙQ) dan (ØP)Ú(ØQ) ekivalen secara logika, karena Ø(PÙQ)«(ØP)Ú(ØQ) selalu benar.
true
true
true
false
(ØP)Ú(ØQ)
true
true
true
false
Ø(PÙQ)
true
false
true
true
true
false
true
false
false
true
true
true
Ø(PÙQ)«(ØP)Ú(ØQ)
Q
P
Pernyataan yang Ekivalen
Pernyataan Ø(PÙQ) dan (ØP)Ú(ØQ) ekivalen secara logika, karena Ø(PÙQ)«(ØP)Ú(ØQ) selalu benar.
Tautologi dan Kontradiksi
Kontradiksi adalah pernyataan yang selalu bernilai salah.
Contoh:
l RÙ(ØR)
l Ø(Ø(PÙQ)«(ØP)Ú(ØQ))
Negasi dari suatu tautologi adalah suatu kontradiksi, negasi dari kontradiksi adalah suatu tautologi.
Konversi, Kontrapositif, & Invers
l q ® p disebut konversi dari p ® q
l Øq ® Øp disebut kontrapositif dari p ® q
l Øp ® Øq disebut invers dari p ® q
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 DIV KOMPAK POLINES”
f : “Anda mhs UNDIP”
a ® (m Ú Ø f)
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”
Predikat & 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).
Subyek dari suatu pernyataan dapat berjumlah lebih dari satu.
Misalkan Q(x,y): x - 2y > x + y
Negasi
“Setiap mhs dalam kelas ini telah mengambil Kalkulus I” ["x P(x)]
Apakah negasi dari pernyataan ini….?
“Ada seorang mhs dalam kelas ini yang belum mengambil Kalkulus I” [ $x Ø P(x)]
Jadi, Ø "x P(x) º $x Ø P(x).
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)
Soal-soal
"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.
Bagaimana dengan berikut ini:
$x "y "z((F(x,y) Ù F(x,z) Ù (y ¹ z) ® ØF(y,z))
Nyatakan negasi dari pernyataan
"x $y (xy=1).
Implikasi (JIKA - MAKA)
false
false
true
true
true
false
true
false
false
true
true
true
P®Q
Q
P
Negasi (NOT)
Operator Uner, Simbol: Ø
Catatan : Modul Presentasi pada pertemuan ke-1 s.d pertemuan ke-8.
