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
  1. Konsep
  2. Rumus
  3. Contoh soal
  4. Kesalahan umum
  5. Coba sendiri
  6. Kuis 5 soal
  7. Tanya jawab
  8. Topik terkait
  9. Untuk guru

Konsep Matematika Diskrit

Logika, metode pembuktian, dan induksi

Logika proposisi memakai penghubung ¬,∧,∨,→,↔\neg, \wedge, \vee, \to, \leftrightarrow. Implikasi p→qp \to q setara dengan kontraposisinya ¬q→¬p\neg q \to \neg p, tetapi tidak setara dengan konversnya q→pq \to p. Hukum De Morgan: ¬(p∧q)≡¬p∨¬q\neg(p \wedge q) \equiv \neg p \vee \neg q. Dalam logika predikat, negasi kuantor berbunyi ¬∀x P(x)≡∃x ¬P(x)\neg\forall x\,P(x) \equiv \exists x\,\neg P(x).

Metode pembuktian: langsung (asumsikan pp, turunkan qq), kontraposisi, kontradiksi (asumsikan negasi kesimpulan sampai muncul pertentangan), dan contoh penyangkal untuk membantah pernyataan universal.

Induksi matematika: untuk membuktikan P(n)P(n) bagi semua n≥n0n \ge n_{0}, buktikan (1) basis P(n0)P(n_{0}) dan (2) langkah induksi P(k)⇒P(k+1)P(k) \Rightarrow P(k + 1). Induksi kuat mengasumsikan P(n0),…,P(k)P(n_{0}), \ldots, P(k) sekaligus.

Himpunan, relasi, dan fungsi

Operasi himpunan: gabungan, irisan, selisih, komplemen, dan hasil kali Kartesius A×BA \times B. Himpunan kuasa P(A)\mathcal{P}(A) dari himpunan berukuran nn memiliki 2n2^{n} anggota.

Relasi pada AA adalah himpunan bagian A×AA \times A. Relasi bisa refleksif, simetris, antisimetris, dan transitif. Relasi yang refleksif, simetris, dan transitif disebut relasi ekivalensi dan mempartisi AA menjadi kelas-kelas ekivalensi; relasi yang refleksif, antisimetris, dan transitif disebut urutan parsial.

Fungsi f:A→Bf: A \to B 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 rr objek dari nn adalah P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n - r)!}, dan banyak kombinasi (nr)=n!r!(n−r)!\binom{n}{r} = \frac{n!}{r!(n - r)!}. Permutasi dengan unsur sama: n!n1!n2!⋯nk!\frac{n!}{n_{1}!n_{2}!\cdots n_{k}!}. Banyak solusi bulat tak negatif x1+⋯+xk=nx_{1} + \cdots + x_{k} = n adalah (n+k−1k−1)\binom{n + k - 1}{k - 1} (metode bintang dan sekat).

Prinsip inklusi–eksklusi: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|, dan untuk tiga himpunan ditambah suku ∣A∩B∩C∣|A \cap B \cap C|.

Prinsip sarang merpati: jika nn objek dimasukkan ke kk kotak, ada kotak berisi minimal ⌈nk⌉\left\lceil \frac{n}{k} \right\rceil objek. Akibatnya, k×m+1k \times m + 1 objek menjamin ada kotak berisi m+1m + 1 objek.

Relasi rekurensi dan teori graf

Rekurensi linear homogen berkoefisien konstan an=c1an−1+c2an−2a_{n} = c_{1}a_{n - 1} + c_{2}a_{n - 2} diselesaikan lewat persamaan karakteristik r2=c1r+c2r^{2} = c_{1}r + c_{2}. Jika akarnya r1≠r2r_{1} \ne r_{2}, maka an=Ar1n+Br2na_{n} = Ar_{1}^{n} + Br_{2}^{n}; jika kembar rr, maka an=(A+Bn)rna_{n} = (A + Bn)r^{n}. Konstanta ditentukan dari syarat awal.

Graf G=(V,E)G = (V, E) terdiri atas simpul dan sisi. Lemma jabat tangan: ∑vdeg⁡(v)=2∣E∣\sum_{v} \deg(v) = 2|E|, 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 nn simpul memiliki tepat n−1n - 1 sisi. Graf lengkap KnK_{n} memiliki (n2)\binom{n}{2} sisi. Rumus Euler untuk graf planar terhubung: V−E+F=2V - E + F = 2.

Aljabar Boolean dan aritmetika modulo

Aljabar Boolean bekerja pada {0,1}\{0, 1\} dengan operasi ++ (OR), ⋅\cdot (AND), dan komplemen x‾\overline{x}. Hukum pentingnya: identitas, komplemen (x+x‾=1x + \overline{x} = 1, xx‾=0x\overline{x} = 0), absorpsi (x+xy=xx + xy = x), dan De Morgan (x+y‾=x‾ y‾\overline{x + y} = \overline{x}\,\overline{y}). Fungsi Boolean ditulis dalam bentuk jumlah hasil kali (minterm) lalu disederhanakan, misalnya dengan peta Karnaugh, untuk merancang rangkaian logika.

Kongruensi a≡b(modm)a \equiv b \pmod{m} berarti mm membagi a−ba - b. Invers aa modulo mm ada jika dan hanya jika FPB⁡(a,m)=1\operatorname{FPB}(a, m) = 1, dan dicari dengan algoritma Euclid yang diperluas. Teorema kecil Fermat: untuk pp prima dan p∤ap \nmid a, ap−1≡1(modp)a^{p - 1} \equiv 1 \pmod{p}. Aritmetika modulo menjadi dasar kriptografi RSA, fungsi hash, dan digit pemeriksa (seperti pada ISBN).

Rumus

Kombinasi
(nr)=n!r!(n−r)!\binom{n}{r} = \frac{n!}{r!(n - r)!}
Inklusi–eksklusi tiga himpunan
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|
Lemma jabat tangan
∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|
Teorema kecil Fermat
ap−1≡1(modp),p∤aa^{p - 1} \equiv 1 \pmod{p}, \quad p \nmid a

Contoh soal matematika diskrit dan pembahasan

Contoh 1 · Mudah

Memilih panitia

Dari 10 mahasiswa akan dipilih 3 orang sebagai panitia (tanpa jabatan). Ada berapa cara?

Lihat langkah penyelesaian
  1. Urutan tidak penting, jadi gunakan kombinasi.
  2. (103)=10!3! 7!=10×9×86=120\binom{10}{3} = \frac{10!}{3!\,7!} = \frac{10 \times 9 \times 8}{6} = 120.

Ada 120 cara.

Contoh 2 · Sedang

Inklusi–eksklusi

Berapa banyak bilangan bulat dari 1 sampai 100 yang habis dibagi 3 atau 5?

Lihat langkah penyelesaian
  1. Habis dibagi 3: ⌊1003⌋=33\left\lfloor \frac{100}{3} \right\rfloor = 33. Habis dibagi 5: 20.
  2. Habis dibagi keduanya berarti habis dibagi 15: ⌊10015⌋=6\left\lfloor \frac{100}{15} \right\rfloor = 6.
  3. ∣A∪B∣=33+20−6=47|A \cup B| = 33 + 20 - 6 = 47.

Ada 47 bilangan.

Contoh 3 · Sedang

Menyelesaikan relasi rekurensi

Selesaikan an=5an−1−6an−2a_{n} = 5a_{n - 1} - 6a_{n - 2} dengan a0=1a_{0} = 1, a1=4a_{1} = 4, lalu tentukan a5a_{5}.

Lihat langkah penyelesaian
  1. Persamaan karakteristik r2−5r+6=0r^{2} - 5r + 6 = 0 memberi r=2r = 2 dan r=3r = 3, jadi an=A×2n+B×3na_{n} = A \times 2^{n} + B \times 3^{n}.
  2. Syarat awal: A+B=1A + B = 1 dan 2A+3B=42A + 3B = 4, sehingga B=2B = 2 dan A=−1A = -1.
  3. an=2×3n−2na_{n} = 2 \times 3^{n} - 2^{n}. Cek: a2=18−4=14=5×4−6×1a_{2} = 18 - 4 = 14 = 5 \times 4 - 6 \times 1.
  4. a5=2×243−32=454a_{5} = 2 \times 243 - 32 = 454.

an=2×3n−2na_{n} = 2 \times 3^{n} - 2^{n} dan a5=454a_{5} = 454.

Contoh 4 · Mudah

Lemma jabat tangan

Sebuah graf memiliki 10 simpul dan setiap simpul berderajat 3. Berapa banyak sisinya?

Lihat langkah penyelesaian
  1. Jumlah derajat =10×3=30= 10 \times 3 = 30.
  2. Menurut lemma jabat tangan, 2∣E∣=302|E| = 30, sehingga ∣E∣=15|E| = 15.

Graf itu memiliki 15 sisi.

Contoh 5 · Sedang

Pangkat besar modulo prima

Tentukan sisa pembagian 31003^{100} oleh 7.

Lihat langkah penyelesaian
  1. Menurut teorema kecil Fermat, 36≡1(mod7)3^{6} \equiv 1 \pmod{7}.
  2. 100=6×16+4100 = 6 \times 16 + 4, sehingga 3100=(36)16×34≡34(mod7)3^{100} = (3^{6})^{16} \times 3^{4} \equiv 3^{4} \pmod{7}.
  3. 34=81=7×11+43^{4} = 81 = 7 \times 11 + 4.

Sisanya 4.

Contoh 6 · Penalaran

Bukti dengan induksi

Buktikan 1×2+2×3+⋯+n(n+1)=n(n+1)(n+2)31 \times 2 + 2 \times 3 + \cdots + n(n + 1) = \frac{n(n + 1)(n + 2)}{3} untuk semua n≥1n \ge 1, lalu hitung jumlahnya untuk n=10n = 10.

Lihat langkah penyelesaian
  1. Basis n=1n = 1: ruas kiri 1×2=21 \times 2 = 2 dan ruas kanan 1×2×33=2\frac{1 \times 2 \times 3}{3} = 2.
  2. Hipotesis: rumus benar untuk n=kn = k. Tambahkan suku (k+1)(k+2)(k + 1)(k + 2) pada kedua ruas.
  3. Ruas kanan menjadi k(k+1)(k+2)3+(k+1)(k+2)=(k+1)(k+2)(k+3)3\frac{k(k + 1)(k + 2)}{3} + (k + 1)(k + 2) = \frac{(k + 1)(k + 2)(k + 3)}{3}, yaitu rumus untuk n=k+1n = k + 1.
  4. Untuk n=10n = 10: 10×11×123=440\frac{10 \times 11 \times 12}{3} = 440.

Rumus terbukti untuk semua n≥1n \ge 1, dan untuk n=10n = 10 jumlahnya 440.

Contoh 7 · Penalaran

Prinsip sarang merpati

Berapa mahasiswa minimal yang harus berkumpul agar pasti ada 4 orang yang lahir pada bulan yang sama?

Lihat langkah penyelesaian
  1. Bulan adalah kotak (k=12k = 12). Kasus terburuk: setiap bulan berisi 3 orang, yaitu 12×3=3612 \times 3 = 36 orang tanpa ada 4 orang sebulan.
  2. Orang ke-37 pasti masuk ke bulan yang sudah berisi 3 orang.

Minimal 37 mahasiswa.

Kesalahan yang sering terjadi

Menganggap implikasi p→qp \to q setara dengan konversnya q→pq \to p.
Yang setara dengan p→qp \to q adalah kontraposisinya ¬q→¬p\neg q \to \neg p. Konvers dan invers belum tentu benar.
Dalam induksi, hanya membuktikan langkah induksi tanpa basis.
Tanpa basis, rantai implikasi tidak punya titik awal. Kedua langkah wajib dibuktikan.
Memakai permutasi untuk memilih anggota tim tanpa jabatan.
Jika urutan atau jabatan tidak penting, gunakan kombinasi (nr)\binom{n}{r}; permutasi menghitung setiap tim sebanyak r!r! kali.
Menulis x+y‾=x‾+y‾\overline{x + y} = \overline{x} + \overline{y} dalam aljabar Boolean.
Hukum De Morgan memberi x+y‾=x‾ y‾\overline{x + y} = \overline{x}\,\overline{y} dan xy‾=x‾+y‾\overline{xy} = \overline{x} + \overline{y}.

Coba sendiri

Tulis jawabanmu, tekan Periksa. Jika belum tepat, buka petunjuk satu per satu.

Soal 1Aplikasi
Berapa banyak susunan berbeda dari huruf-huruf kata MATEMATIKA?
Soal 2Aplikasi
Tentukan invers 7 modulo 26, yaitu bilangan xx dengan 0≤x<260 \le x < 26 dan 7x≡1(mod26)7x \equiv 1 \pmod{26}.
Soal 3Penalaran
Barisan memenuhi an=an−1+2an−2a_{n} = a_{n - 1} + 2a_{n - 2} dengan a0=0a_{0} = 0 dan a1=1a_{1} = 1. Tentukan a6a_{6}.

Kuis 5 soal

Kerjakan semua soal, lalu periksa sekaligus.

Soal 1Pemahaman
Negasi dari ∀x P(x)\forall x\,P(x) adalah …
Soal 2Aplikasi
Banyak relasi berbeda pada himpunan A={a,b,c}A = \{a, b, c\} adalah …
Soal 3Pemahaman
Pernyataan: "Graf terhubung yang semua simpulnya berderajat genap memiliki sirkuit Euler." Benar atau salah?
Soal 4Aplikasi
Tentukan sisa pembagian 2502^{50} oleh 5.
Soal 5Penalaran
Pilih semua identitas aljabar Boolean yang benar.
Pilih semua jawaban yang benar.

Latihan tanpa batas

Soal kembar dengan angka baru, petunjuk bertingkat, dan catatan penguasaanmu.

Mulai latihan

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 P(k+1)P(k + 1) cukup diturunkan dari P(k)P(k). 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

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.

Bagikan latihan ke kelas dengan kode tugas