Kuliah · Kuliah · Aljabar
Matematika Diskrit
Matematika Diskrit mempelajari objek yang terpisah dan dapat dicacah: proposisi, himpunan, bilangan bulat, susunan, dan graf. Mata kuliah ini menjadi bahasa dasar ilmu komputer. Sepuluh babnya dikelompokkan menjadi logika dan pembuktian, struktur (himpunan, relasi, fungsi), pencacahan (kombinatorika, sarang merpati, rekurensi), serta struktur terapan (graf, aljabar Boolean, aritmetika modulo).
Daftar isi
Konsep Matematika Diskrit
Logika, metode pembuktian, dan induksi
Logika proposisi memakai penghubung . Implikasi setara dengan kontraposisinya , tetapi tidak setara dengan konversnya . Hukum De Morgan: . Dalam logika predikat, negasi kuantor berbunyi .
Metode pembuktian: langsung (asumsikan , turunkan ), kontraposisi, kontradiksi (asumsikan negasi kesimpulan sampai muncul pertentangan), dan contoh penyangkal untuk membantah pernyataan universal.
Induksi matematika: untuk membuktikan bagi semua , buktikan (1) basis dan (2) langkah induksi . Induksi kuat mengasumsikan sekaligus.
Himpunan, relasi, dan fungsi
Operasi himpunan: gabungan, irisan, selisih, komplemen, dan hasil kali Kartesius . Himpunan kuasa dari himpunan berukuran memiliki anggota.
Relasi pada adalah himpunan bagian . Relasi bisa refleksif, simetris, antisimetris, dan transitif. Relasi yang refleksif, simetris, dan transitif disebut relasi ekivalensi dan mempartisi menjadi kelas-kelas ekivalensi; relasi yang refleksif, antisimetris, dan transitif disebut urutan parsial.
Fungsi bisa injektif (satu-satu), surjektif (pada), atau bijektif (keduanya). Hanya fungsi bijektif yang memiliki invers.
Kombinatorika dan prinsip sarang merpati
Aturan penjumlahan untuk pilihan yang saling lepas dan aturan perkalian untuk pilihan bertahap. Banyak permutasi objek dari adalah , dan banyak kombinasi . Permutasi dengan unsur sama: . Banyak solusi bulat tak negatif adalah (metode bintang dan sekat).
Prinsip inklusi–eksklusi: , dan untuk tiga himpunan ditambah suku .
Prinsip sarang merpati: jika objek dimasukkan ke kotak, ada kotak berisi minimal objek. Akibatnya, objek menjamin ada kotak berisi objek.
Relasi rekurensi dan teori graf
Rekurensi linear homogen berkoefisien konstan diselesaikan lewat persamaan karakteristik . Jika akarnya , maka ; jika kembar , maka . Konstanta ditentukan dari syarat awal.
Graf terdiri atas simpul dan sisi. Lemma jabat tangan: , sehingga banyak simpul berderajat ganjil selalu genap. Graf terhubung memiliki sirkuit Euler jika dan hanya jika semua simpulnya berderajat genap, dan lintasan Euler jika tepat dua simpul berderajat ganjil. Pohon dengan simpul memiliki tepat sisi. Graf lengkap memiliki sisi. Rumus Euler untuk graf planar terhubung: .
Aljabar Boolean dan aritmetika modulo
Aljabar Boolean bekerja pada dengan operasi (OR), (AND), dan komplemen . Hukum pentingnya: identitas, komplemen (, ), absorpsi (), dan De Morgan (). Fungsi Boolean ditulis dalam bentuk jumlah hasil kali (minterm) lalu disederhanakan, misalnya dengan peta Karnaugh, untuk merancang rangkaian logika.
Kongruensi berarti membagi . Invers modulo ada jika dan hanya jika , dan dicari dengan algoritma Euclid yang diperluas. Teorema kecil Fermat: untuk prima dan , . Aritmetika modulo menjadi dasar kriptografi RSA, fungsi hash, dan digit pemeriksa (seperti pada ISBN).
Rumus
Contoh soal matematika diskrit dan pembahasan
Memilih panitia
Dari 10 mahasiswa akan dipilih 3 orang sebagai panitia (tanpa jabatan). Ada berapa cara?
Lihat langkah penyelesaian
- Urutan tidak penting, jadi gunakan kombinasi.
- .
Ada 120 cara.
Inklusi–eksklusi
Berapa banyak bilangan bulat dari 1 sampai 100 yang habis dibagi 3 atau 5?
Lihat langkah penyelesaian
- Habis dibagi 3: . Habis dibagi 5: 20.
- Habis dibagi keduanya berarti habis dibagi 15: .
- .
Ada 47 bilangan.
Menyelesaikan relasi rekurensi
Selesaikan dengan , , lalu tentukan .
Lihat langkah penyelesaian
- Persamaan karakteristik memberi dan , jadi .
- Syarat awal: dan , sehingga dan .
- . Cek: .
- .
dan .
Lemma jabat tangan
Sebuah graf memiliki 10 simpul dan setiap simpul berderajat 3. Berapa banyak sisinya?
Lihat langkah penyelesaian
- Jumlah derajat .
- Menurut lemma jabat tangan, , sehingga .
Graf itu memiliki 15 sisi.
Pangkat besar modulo prima
Tentukan sisa pembagian oleh 7.
Lihat langkah penyelesaian
- Menurut teorema kecil Fermat, .
- , sehingga .
- .
Sisanya 4.
Bukti dengan induksi
Buktikan untuk semua , lalu hitung jumlahnya untuk .
Lihat langkah penyelesaian
- Basis : ruas kiri dan ruas kanan .
- Hipotesis: rumus benar untuk . Tambahkan suku pada kedua ruas.
- Ruas kanan menjadi , yaitu rumus untuk .
- Untuk : .
Rumus terbukti untuk semua , dan untuk jumlahnya 440.
Prinsip sarang merpati
Berapa mahasiswa minimal yang harus berkumpul agar pasti ada 4 orang yang lahir pada bulan yang sama?
Lihat langkah penyelesaian
- Bulan adalah kotak (). Kasus terburuk: setiap bulan berisi 3 orang, yaitu orang tanpa ada 4 orang sebulan.
- Orang ke-37 pasti masuk ke bulan yang sudah berisi 3 orang.
Minimal 37 mahasiswa.
Kesalahan yang sering terjadi
Coba sendiri
Tulis jawabanmu, tekan Periksa. Jika belum tepat, buka petunjuk satu per satu.
Pembahasan
susunan.
Pembahasan
, jadi .
Pembahasan
Suku-sukunya . Rumus tertutup: .
Kuis 5 soal
Kerjakan semua soal, lalu periksa sekaligus.
Pembahasan
.
Pembahasan
Banyak himpunan bagian dari himpunan berukuran 9 adalah .
Pembahasan
Benar. Ini teorema Euler: graf terhubung memiliki sirkuit Euler jika dan hanya jika semua simpulnya berderajat genap.
Pembahasan
.
Pembahasan
A benar lewat distributif. B adalah hukum absorpsi. D benar (dominasi). C salah menurut De Morgan, dan E salah karena .
Latihan tanpa batas
Soal kembar dengan angka baru, petunjuk bertingkat, dan catatan penguasaanmu.
Tanya jawab
Mengapa mahasiswa informatika wajib belajar Matematika Diskrit?
Algoritma, struktur data, basis data, jaringan, dan kriptografi dibangun di atas logika, kombinatorika, graf, dan aritmetika modulo. Analisis kompleksitas juga memakai relasi rekurensi.
Kapan memakai induksi biasa dan kapan induksi kuat?
Pakai induksi biasa bila cukup diturunkan dari . Pakai induksi kuat bila butuh beberapa kasus sebelumnya, misalnya pada rekurensi dua suku atau faktorisasi prima.
Apa hubungan aljabar Boolean dengan rangkaian digital?
Setiap gerbang logika (AND, OR, NOT) adalah operasi Boolean. Menyederhanakan ekspresi Boolean berarti mengurangi banyak gerbang pada rangkaian.
Topik terkait
Pelajari dulu (prasyarat)
- Tidak ada prasyarat khusus.
Topik lanjutan
- Belum ada.
Ringkasan untuk guru
Tujuan pembelajaran
- Mahasiswa menerjemahkan pernyataan ke logika proposisi dan predikat serta menyusun bukti langsung, kontraposisi, kontradiksi, dan induksi.
- Mahasiswa mengidentifikasi sifat relasi dan fungsi.
- Mahasiswa memecahkan masalah pencacahan dengan aturan dasar, permutasi, kombinasi, inklusi–eksklusi, sarang merpati, dan rekurensi.
- Mahasiswa menerapkan teori graf, aljabar Boolean, dan aritmetika modulo pada masalah komputasi.
Ide aktivitas kelas
- Detektif logika: kelompok menerima teka-teki kesatria dan pembohong, lalu menyelesaikannya dengan tabel kebenaran.
- Peta jalan kota: mahasiswa memodelkan rute angkot di kotanya sebagai graf dan memeriksa apakah ada rute Euler yang melewati setiap ruas jalan tepat sekali.
- Sandi Caesar dan RSA mini: mahasiswa mengenkripsi pesan pendek dengan aritmetika modulo bilangan kecil lalu saling memecahkan sandinya.
Acuan: Silabus umum mata kuliah Matematika Diskrit untuk program studi matematika dan informatika (disusun tim redaksi), elemen Aljabar.