Matematika Diskrit
Matematika diskrit adalah matematika tentang hal-hal yang terpisah dan bisa dihitung: benar atau salah, di dalam himpunan atau di luarnya, jalur ini atau jalur itu. Inilah matematika yang menjalankan komputer, dan semuanya dimulai dari logika yang bisa kamu nyalakan dan matikan.
Terakhir diperbarui
Matematika diskrit adalah matematika tentang hal-hal yang terpisah dan bisa dihitung. Sebuah pernyataan bernilai benar atau salah, sebuah anggota ada di dalam himpunan atau tidak, sebuah jaringan punya hubungan antara dua titik atau tidak. Tidak ada yang di tengah-tengah, dan itulah arti "diskrit". Begitu pula persis cara komputer memandang dunia.
Mata kuliah pengantarnya membahas enam topik: logika, himpunan, pencacahan, graf, teori bilangan, dan pembuktian. Logika datang lebih dulu, karena semua topik lain ditulis dengan bahasanya. Pilih sebuah perangkai di bawah ini, lalu ubah nilai p dan q.
Tabel kebenaran untuk p ∧ q
| p | q | p ∧ q |
|---|---|---|
| B | B | B |
| B | S | S |
| S | B | S |
| S | S | S |
Ubah nilai p dan q, atau klik sebuah baris. Baris yang disorot adalah baris yang dipilih oleh nilai-nilai itu.
Baca p sebagai "x ada di A" dan q sebagai "x ada di B". Daerah yang diarsir adalah tempat pernyataannya benar; titiknya adalah baris yang sedang dipilih.
p ∧ q
Cara membaca p dan q
Dengan nilai-nilai ini, p ∧ q bernilai benar.
Benar hanya ketika p dan q sama-sama benar.
Sebagai himpunan AND adalah irisan: x ada di A ∩ B tepat ketika x ada di A dan x ada di B.
Logika: pernyataan dan perangkai
Pernyataan adalah kalimat yang bernilai benar atau salah, seperti "7 adalah bilangan prima" atau "sedang hujan". Logika membangun pernyataan yang lebih besar dari pernyataan yang lebih kecil dengan beberapa perangkai, dan tabel kebenaran mendaftar hasilnya untuk setiap kombinasi input.
| simbol | nama | cara membaca | benar ketika |
|---|---|---|---|
| ∧ | AND, konjungsi | "p dan q" | keduanya benar |
| ∨ | OR, disjungsi | "p atau q" | setidaknya satu benar |
| ¬ | NOT, negasi | "tidak p" | p salah |
| ⊕ | XOR, disjungsi eksklusif | "p atau q, tetapi tidak keduanya" | tepat satu yang benar |
| → | IMPLIES, implikasi | "jika p, maka q" | semua kasus kecuali p benar dan q salah |
| ↔ | IFF, biimplikasi | "p jika dan hanya jika q" | p dan q bernilai sama |
Dua di antaranya sering mengejutkan. OR dalam logika bersifat inklusif: "p atau q" bernilai benar ketika keduanya benar, tidak seperti "teh atau kopi?" dalam percakapan sehari-hari. Versi eksklusifnya punya nama sendiri, XOR.
Yang satu lagi adalah IMPLIES. p → q bernilai salah hanya di satu baris, yaitu ketika p benar dan q salah. Anggap saja sebagai janji: "kalau hujan, aku akan membawa payung". Janji itu hanya dilanggar kalau hujan turun dan tidak ada payung. Pada hari yang kering, janjinya tidak dilanggar, apa pun yang kamu bawa, jadi pernyataannya dihitung benar.
Pernyataan yang ekuivalen
Dua pernyataan ekuivalen kalau tabel kebenarannya cocok di setiap baris. Di widget, pilih OR dan negasikan p: kolom untuk ¬p ∨ q identik dengan kolom untuk p → q, jadi keduanya menyatakan hal yang sama.
Ekuivalensi yang paling berguna adalah hukum De Morgan, yang menjelaskan bagaimana NOT melewati AND dan OR:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Dengan kata-kata: "tidak keduanya" sama dengan "salah satunya salah", dan "tidak satu pun" sama dengan "keduanya salah". Programmer memakai hukum ini setiap hari untuk menulis ulang kondisi seperti "tidak (sudah masuk dan sudah terverifikasi)".
Logika dan himpunan adalah satu gagasan
Baca p sebagai "x ada di A" dan q sebagai "x ada di B". Maka AND adalah irisan, OR adalah gabungan, dan NOT adalah komplemen, dan setiap tabel kebenaran adalah diagram Venn yang diarsir. Itulah sebabnya widget menggambar diagram itu di samping tabelnya. Hukum De Morgan menjadi aturan tentang himpunan:
(A ∩ B)′ = A′ ∪ B′
Halaman notasi himpunan mengarsir masing-masing operasi ini pada diagram yang bisa kamu klik.
Pencacahan
Pencacahan dalam matematika diskrit berarti menghitung tanpa mendaftar. Dua aturan mengerjakan sebagian besar pekerjaannya.
Aturan perkalian. Kalau satu pilihan bisa dibuat dengan m cara dan pilihan kedua dengan n cara, pasangan pilihan itu bisa dibuat dengan m × n cara. PIN 4 digit punya 10 pilihan untuk setiap digit, jadi ada 10^4 = 10000 PIN yang mungkin.
Kombinasi. Banyaknya cara memilih k benda dari n benda, ketika urutan tidak penting, ditulis C(n, k). Memilih 3 topping dari 8:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
Bagian atas menghitung pilihan yang berurutan, dan membagi dengan 3 × 2 × 1 menghapus 6 urutan berbeda yang bisa menghasilkan tiga topping yang sama.
Jawabannya 6 × 5 dibagi 2, yaitu 15. Kalau kamu mendapat 30, kamu menghitung setiap pasangan dua kali, sekali untuk setiap urutan.
Graf
Graf adalah sekumpulan titik, yang disebut simpul, yang dihubungkan oleh garis, yang disebut sisi. Graf memodelkan apa saja yang tersusun dari hubungan: jalan antarkota, pertemanan di media sosial, tautan antarhalaman web.
Satu hasil awal: kalau 5 orang masing-masing berjabat tangan satu kali dengan semua yang lain, ada C(5, 2) = 10 jabat tangan. Setiap orang menjabat 4 tangan, sehingga ada 5 × 4 = 20 ujung jabat tangan, dan setiap jabat tangan punya dua ujung, jadi 20 / 2 = 10. Argumen itu adalah lemma jabat tangan: jumlah derajat semua simpul sama dengan dua kali banyaknya sisi.
Teori bilangan dan pembuktian
Aritmetika modular adalah aritmetika pada jam. 17 mod 5 sama dengan 2, yaitu sisa ketika 17 dibagi 5. Sembilan jam setelah pukul 8, waktunya pukul 5, karena 17 mod 12 sama dengan 5. Gagasan yang sama, dengan bilangan yang sangat besar, adalah cara kerja enkripsi RSA di balik situs web yang aman.
Pembuktian dengan induksi menunjukkan bahwa sebuah pernyataan berlaku untuk setiap bilangan asli n dalam dua langkah: periksa untuk n = 1, lalu tunjukkan bahwa kalau pernyataan itu berlaku untuk suatu n, ia juga berlaku untuk n + 1. Begitulah cara membuktikan, misalnya, bahwa
1 + 2 + ... + n = n(n + 1) / 2
untuk setiap n, bukan hanya untuk nilai-nilai yang sudah kamu coba.
Kegunaan matematika diskrit
- Pemrograman: setiap pernyataan if adalah logika, dan hukum De Morgan menulis ulang kondisi.
- Database: query yang menggabungkan atau menyaring tabel adalah operasi himpunan.
- Algoritma: pencacahan memberi tahu berapa langkah yang dijalankan sebuah program saat input-nya membesar.
- Jaringan dan peta: rute terpendek dan jaringan media sosial adalah masalah graf.
- Keamanan: enkripsi bertumpu pada teori bilangan dan aritmetika modular.
- Perangkat keras: prosesor dibangun dari gerbang logika, yaitu tabel kebenaran dalam bentuk silikon.
Apakah matematika diskrit sulit?
Sulitnya berbeda dengan aljabar dan kalkulus. Hanya ada sedikit rumus yang perlu dihafal dan hitungannya kecil, tetapi banyak soal memintamu membuktikan sesuatu, bukan menghitungnya, dan menulis argumen yang meyakinkan adalah keterampilan baru bagi kebanyakan siswa.
Yang paling membantu adalah mengerjakan kasus-kasus kecil dengan tangan sebelum mencari polanya: gambar diagram Venn-nya, tulis tabel kebenarannya, daftarkan setiap kasus. Notasinya terasa berat pada awalnya, tetapi sebagian besar hanya simbol-simbol di halaman ini dan di halaman notasi himpunan.
Pertanyaan umum
Apa itu matematika diskrit?
Matematika diskrit adalah cabang matematika yang mempelajari objek-objek yang terpisah dan bisa dihitung, bukan besaran yang berubah secara mulus. Topik utamanya adalah logika, himpunan, pencacahan, graf, teori bilangan, dan pembuktian. Kalkulus bertanya bagaimana sesuatu berubah secara kontinu; matematika diskrit bertanya berapa banyak, yang mana saja, dan apakah sebuah pernyataan benar.
Apakah matematika diskrit sulit?
Sulitnya berbeda dengan kalkulus. Rumus yang perlu diterapkan lebih sedikit dan argumen yang perlu dibangun lebih banyak, dan bagi banyak mahasiswa ini adalah mata kuliah pertama yang berpusat pada menulis pembuktian. Aljabarnya biasanya ringan. Mahasiswa yang merasa kesulitan kebanyakan sedang menyesuaikan diri dengan pembuktian, dan itu cepat membaik kalau dilatih dengan contoh-contoh kecil.
Untuk apa matematika diskrit dipakai?
Hampir semua hal dalam ilmu komputer. Logika adalah cara kerja sirkuit dan pernyataan if, himpunan mendasari query database, pencacahan memberi tahu berapa lama sebuah algoritma berjalan, graf memodelkan jaringan dan peta, dan teori bilangan menjadi dasar enkripsi yang melindungi pembayaran online.
Topik apa saja yang dibahas dalam matematika diskrit?
Mata kuliah pengantar biasanya membahas logika proposisi dan tabel kebenaran, himpunan dan diagram Venn, fungsi dan relasi, teknik pembuktian termasuk induksi, pencacahan dengan permutasi dan kombinasi, peluang dasar, graf dan pohon, serta aritmetika modular. Sebagian mata kuliah menambahkan relasi rekurensi dan aljabar Boolean.
Apakah ilmu komputer butuh matematika diskrit?
Ya. Hampir setiap program studi ilmu komputer mewajibkannya, biasanya di tahun pertama atau kedua, karena algoritma, struktur data, dan teori komputasi semuanya mengandalkannya. Untuk belajar pemrograman saja kamu bisa mulai tanpanya, tetapi logika, himpunan, dan pencacahan muncul dalam kode sehari-hari lebih cepat daripada yang diduga kebanyakan orang.
Apa bedanya matematika diskrit dan matematika kontinu?
Matematika diskrit membahas nilai-nilai yang bisa kamu daftarkan satu per satu, seperti bilangan bulat, benar dan salah, atau simpul dalam sebuah jaringan. Matematika kontinu, seperti kalkulus, membahas besaran yang bisa bernilai berapa pun dalam suatu rentang, seperti waktu, jarak, atau suhu.
Apa itu tabel kebenaran?
Tabel yang mendaftar setiap kombinasi benar dan salah untuk input sebuah pernyataan logika, beserta nilai pernyataan itu untuk masing-masing kombinasi. Dengan dua input p dan q ada empat baris. Tabel kebenaran adalah cara membuktikan bahwa dua pernyataan ekuivalen: kalau kolom keduanya cocok di setiap baris, keduanya selalu sepakat.
