Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Kita menggunakan pendekatan pemecahan masalah untuk mempelajari matematika diskret: Kita akan menelaah beragam pertanyaan yang berciri diskret dan memikirkan cara menjawabnya (serta membuktikan bahwa jawaban kita benar). Ini bukan satu-satunya cara mempelajari matematika diskret. Pendekatan lain adalah mempelajari alat-alat yang digunakan untuk menyelesaikan masalah. Seandainya kita mahasiswa seni, kita dapat mempelajari kuas, kuda-kuda, dan komposisi cat, yang tentu menarik, tetapi menurut saya melukis sendiri pohon-pohon kecil yang ceria itu lebih menyenangkan.

Meskipun demikian, memahami alat memang membantu kita menggunakannya. Karena itu, dalam bagian ini kita akan menelaah beberapa alat dasar yang digunakan dalam matematika diskret. Kita akan kembali membahasnya sepanjang pembelajaran dan memahaminya lebih baik ketika diperlukan.

Alat-alat dalam bidang kita disebut struktur diskret. Struktur diskret adalah objek matematika yang kita gunakan untuk merepresentasikan bagian-bagian dari masalah yang sedang kita selesaikan. “Struktur” merupakan kata yang tepat di sini karena “benda-benda” ini memiliki batasan cukup kaku yang menjadikannya sebagaimana adanya, sama seperti gedung apartemen akan memiliki karakteristik yang berbeda dari hanggar pesawat atau jembatan gantung (semuanya merupakan jenis struktur fisik, bukan struktur matematika—sekadar untuk memperjelasnya secara berlebihan dan merusak metafora tadi).

Struktur yang paling sering kita gunakan dalam matematika diskret adalah himpunan, fungsi, barisan, relasi, dan graf. Sekarang kita akan meninjau masing-masing secara singkat. Seiring kemajuan pembelajaran kita, masing-masing akan dikaji secara lebih terperinci.

Himpunan adalah kumpulan elemen yang tidak terurut. Definisi ini memang agak samar, tetapi cukup untuk keperluan kita, kecuali jika kita ingin menghabiskan satu buku penuh untuk memahami himpunan secara lebih tepat. Seluruh matematika dapat didefinisikan hanya dengan menggunakan himpunan (bahkan bilangan pun dapat dipandang sebagai himpunan), tetapi itu juga bukan yang akan kita lakukan. Sebaliknya, kita ingin dapat membicarakan kumpulan bilangan dan objek lain, lalu mengumpulkannya dalam sesuatu yang kita sebut himpunan.

Kita dapat mendeskripsikan himpunan dengan menyatakan secara tepat elemen mana saja yang menjadi anggota himpunan tersebut. Keanggotaan ini dapat kita nyatakan dengan kata-kata (misalnya, misalkan \(A\) adalah himpunan semua bilangan asli yang kurang dari 10), dengan mencantumkan semua elemennya secara eksplisit (misalnya, \(A = \{3, 5, 7\}\)), atau dengan menggunakan apa yang disebut deskripsi pembentuk himpunan (juga disebut notasi pembentuk himpunan). Contohnya adalah \(A = \{x \in \N \st x \lt 10\}\text{.}\) Kita membacanya sebagai “\(A\) adalah himpunan bilangan asli yang memenuhi sifat kurang dari 10.” Secara lebih tepat, simbol \(\N\) menyatakan bilangan asli, yang juga merupakan suatu himpunan: \(\N = \{0, 1, 2, 3, \ldots\}\) (ini menunjukkan cara lain untuk mendeskripsikan himpunan). Simbol \(\in\) berarti “merupakan elemen dari”. Simbol \(\st\) dibaca “sedemikian sehingga” dan memberi tahu kita bahwa bagian sesudahnya merupakan syarat yang harus dipenuhi oleh elemen-elemen himpunan tersebut.

Ada banyak hal yang dapat kita lakukan dengan himpunan, yang akan kita bahas lebih terperinci saat diperlukan. Kita akan melihat bahwa sering kali bermanfaat untuk membentuk himpunan baru dari himpunan yang sudah ada (misalnya dengan mengambil gabungan atau irisan himpunan), membandingkan himpunan (menanyakan apakah suatu himpunan merupakan himpunan bagian dari himpunan lain), dan mencari banyaknya elemen suatu himpunan (yang disebut kardinalitas). Kita mungkin juga ingin memasangkan elemen suatu himpunan dengan elemen himpunan lain. Untuk melakukannya, kita dapat menggunakan fungsi, yang akan dibahas berikutnya. Hebatnya, kita juga dapat menggunakan himpunan itu sendiri untuk mendeskripsikan fungsi. Mari kita lihat.

Salah satu cara mendefinisikan fungsi adalah sebagai aturan yang memasangkan setiap masukan dengan tepat satu keluaran. Keluaran tersebut disebut citra dari masukan. Fungsi juga dilengkapi dengan domain, yaitu himpunan semua masukan, dan kodomain, yaitu himpunan semua keluaran yang diperbolehkan. Kita juga dapat membicarakan daerah hasil fungsi, yaitu himpunan semua keluaran yang benar-benar dihasilkan, atau dengan kata lain, himpunan semua citra elemen-elemen domain.

Kita menulis \(f:X \to Y\) untuk mendeskripsikan fungsi bernama \(f\) dengan domain \(X\) dan kodomain \(Y\text{.}\) Namun, ini belum memberi tahu kita fungsi yang mana yang merupakan \(f\text{.}\) Untuk mendefinisikan fungsi tersebut, kita harus mendeskripsikan aturannya. Hal ini sering dilakukan dengan rumus (misalnya, \(f(x) = x^2\) menyatakan bahwa setiap elemen domain dipetakan ke kuadratnya), atau dengan kata-kata (seperti ketika kita baru saja mendeskripsikan fungsi pengkuadratan). Kita juga dapat mendefinisikan fungsi dengan tabel atau grafik.

Hal utama yang menjadikan suatu aturan sebagai fungsi adalah bahwa setiap masukan memiliki tepat satu keluaran. Dengan kata lain, aturan tersebut harus terdefinisi dengan baik. Keluaran apa yang kita pasangkan dengan masukan 7? Untuk suatu fungsi tertentu, hanya boleh ada satu jawaban.

Karena fungsi memetakan suatu himpunan (domain) ke himpunan lain (kodomain), terdapat hubungan yang jelas antara himpunan dan fungsi. Namun, ada hubungan lain yang patut diperhatikan: grafik suatu fungsi sering dideskripsikan sebagai himpunan titik. Berikut ini contohnya.

Tentu saja, di sini kita menggunakan sebuah objek matematika: pasangan terurut. Objek ini bukan himpunan (karena himpunan tidak terurut). Bagaimana seharusnya kita membicarakan objek-objek terurut? Kita akan membahas pertanyaan ini dalam bagian berikutnya.

Ada satu pertimbangan penting lagi tentang cara kita mendefinisikan fungsi dengan suatu aturan. Rumus tertutup adalah rumus yang memberikan setiap keluaran melalui aturan eksplisit yang hanya didasarkan pada masukannya. Inilah yang biasanya kita bayangkan sebagai rumus. Sebagai contoh, \(f(n) = 3n + 1\) adalah rumus tertutup karena untuk mencari \(f(5)\text{,}\) misalnya, kita mengambil masukan 5 dan melakukan sesuatu terhadapnya: mengalikannya dengan 3, lalu menambahkan 1.

Lalu, bentuk lain suatu rumus itu apa? Definisi rekursif suatu fungsi memberi tahu kita cara menghitung keluaran untuk suatu masukan berdasarkan keluaran-keluaran lain dari fungsi tersebut. Sebagai contoh, kita dapat menetapkan bahwa \(f(n) = 2\cdot f(n-1)\text{.}\) Jika kita juga menetapkan syarat awal bahwa \(f(0) = 3\text{,}\) kita dapat memperoleh \(f(1) = 2\cdot 3 = 6\text{,}\) lalu \(f(2) = 2\cdot 6 = 12\text{,}\) dan seterusnya. Berapakah \(f(5)\) di sini? Satu-satunya cara menjawabnya adalah dengan mencari \(f(4)\text{,}\) yang berarti kita perlu mencari \(f(3)\text{,}\) dan itu dapat kita lakukan karena kita telah menghitung \(f(2)\text{.}\)

Definisi rekursif fungsi mungkin kurang berguna untuk mencari keluaran tertentu, tetapi sering kali lebih mudah ditetapkan bagi suatu penerapan tertentu. Kita akan mengkaji fenomena ini lebih jauh ketika mempelajari barisan. Omong-omong soal barisan...

Terkadang kita tidak hanya tertarik pada kumpulan bilangan, tetapi juga pada urutan kemunculan bilangan-bilangan tersebut. Dalam kasus seperti itu, kita tidak dapat menggunakan himpunan karena himpunan tidak membedakan urutan elemennya. Sebagai gantinya, kita menelaah barisan.

Kita akan menelaah barisan hingga maupun tak hingga. Barisan hingga dapat berupa sesuatu yang sederhana seperti \((1,2,3)\text{;}\) ini adalah barisan dengan 3 elemen dalam urutan tertentu tersebut. Kita juga dapat menyebutnya tripel terurut, sebagaimana \((7,3)\) merupakan pasangan terurut. Secara umum, kita dapat menyebutnya \(n\)-tupel jika memiliki \(n\) elemen (kita mengasumsikan bahwa tupel terurut).

Perbedaan utama antara barisan \((1,2,3)\) dan himpunan \(\{1,2,3\}\) adalah bahwa dalam barisan kita “memedulikan” urutan. Artinya, barisan \((1,2,3)\) berbeda dari barisan \((2,3,1)\text{,}\) sedangkan himpunan \(\{1,2,3\}\) identik dengan \(\{2,3,1\}\text{.}\)

Kita akan sering menggunakan barisan sebagai alat pencacahan. Sebagai contoh, pertanyaan pencacahan yang sangat sederhana adalah, “Berapa banyak roda yang dimiliki 100 mobil?” Alih-alih hanya menjawab satu pertanyaan ini, kita dapat menggeneralisasikannya dan menanyakan berapa banyak roda yang dimiliki \(n\) mobil, lalu memperoleh barisan jawaban. Hasilnya adalah barisan tak hingga \((4, 8, 12, \ldots )\text{.}\) Urutan kemunculan kelipatan 4 ini penting karena setiap bilangan dalam barisan bersesuaian dengan versi tertentu dari pertanyaan tersebut.

Jika ingin sedikit lebih tepat dan abstrak, kita dapat memandang barisan sebagai fungsi. Domainnya adalah bilangan asli atau suatu himpunan bagian yang terdiri atas bilangan-bilangan asli berurutan (seperti \(\{1,2,3,4\}\)). Kodomainnya adalah suatu himpunan. Kita memandang domain sebagai posisi-posisi dalam barisan dan citra dari masukan-masukan tersebut sebagai suku-suku barisan.

Sebagai contoh, kita dapat menelaah barisan Fibonacci \((f_n)_{n\ge 1}\text{,}\) yang dimulai dengan \(1, 1, 2, 3, 5, 8,\ldots\text{.}\) Berapakah suku ke-4 barisan tersebut? Kita dapat mengatakan \(f_4 = 3\) (dengan asumsi bahwa angka 1 yang pertama adalah suku pertama, bukan suku ke-0). Perhatikan bahwa hanya boleh ada satu suku ke-4. Untuk setiap nilai \(n\) tertentu, hanya boleh ada satu suku ke-\(n\text{.}\) Jadi, untuk setiap masukan (posisi suku), hanya ada satu keluaran (suku tersebut). Menulis \(f(4) = 3\) sepenuhnya masuk akal, dan bentuk itu memang tampak seperti fungsi. Namun, kita lebih suka menggunakan subskrip.

Kita juga dapat mendeskripsikan suku-suku suatu barisan dengan menggunakan tabel. Kita dapat menuliskan sesuatu seperti berikut:

Bentuk ini persis seperti cara merepresentasikan fungsi, meskipun tabel tersebut mendeskripsikan barisan bilangan segitiga (nanti kita akan melihat mengapa bilangan-bilangan itu disebut demikian).

Sebagian besar upaya kita dalam memahami barisan akan digunakan untuk mengambil suatu definisi rekursif dan mencari rumus tertutup bagi barisan tersebut. Kita akan mempelajari hal ini, beserta semua hal lain yang berkaitan dengan barisan, dalam Bab 4.

Bagaimana bilangan \(2\) dan \(6\) saling berhubungan? Ah, saya tahu: \(2 \lt 6\text{.}\) Selain itu, \(6\) merupakan kelipatan dari \(2\text{.}\) Kedua bilangan tersebut juga sama-sama genap. Dan inilah fakta lainnya: Keduanya tidak sama. Keempat hal ini merupakan contoh relasi: kurang dari, kelipatan dari, sama-sama genap, tidak sama. Masih ada banyak lagi (tak terhingga banyaknya) relasi untuk pasangan bilangan.

Semua contoh di atas merupakan relasi biner karena menghubungkan dua elemen. Kita juga dapat menelaah relasi antara lebih dari dua elemen. Sebagai contoh, kita dapat menelaah relasi “tripel Pythagoras” pada tiga bilangan, yang berlaku tepat ketika ketiga bilangan itu merupakan panjang sisi-sisi suatu segitiga siku-siku. Jadi, relasi tersebut berlaku untuk tripel \((3,4,5)\text{,}\) tetapi tidak untuk \((4,5,6)\) (karena \(3^2 + 4^2 = 5^2\text{,}\) sedangkan \(4^2 + 5^2 \ne 6^2\)).

Perhatikan bahwa kita dapat membicarakan suatu pasangan atau tripel yang memenuhi suatu relasi. Kita dapat mengatakan bahwa suatu pasangan termasuk dalam relasi tersebut. Cara yang cermat dan formal untuk mendefinisikan relasi adalah sebagai himpunan pasangan terurut (atau tripel, dan seterusnya). Perhatikan himpunan (tak hingga) semua pasangan terurut \((a,b)\) sedemikian sehingga \(a \lt b\text{.}\) Setiap elemen himpunan ini memuat bilangan-bilangan yang memenuhi relasi “kurang dari”, dan setiap pasangan bilangan yang memenuhi relasi tersebut merupakan pasangan di dalam himpunan itu. Jadi, kita dapat mengatakan bahwa himpunan pasangan ini adalah relasi tersebut.

Relasi dapat memiliki beberapa sifat baku, dan menentukan apakah suatu relasi memiliki sifat tertentu sering kali dapat membantu kita memahami relasi itu dengan lebih baik. Sebagai contoh, relasi kurang dari bersifat irrefleksif karena tidak ada elemen yang kurang dari dirinya sendiri. Relasi ini juga antisimetris karena tidak ada bilangan berbeda \(a\) dan \(b\) sedemikian sehingga \(a \lt b\) dan \(b \lt a\text{.}\) Relasi ini juga transitif karena jika \(a \lt b\) dan \(b \lt c\text{,}\) maka harus berlaku \(a \lt c\text{.}\) Namun, ini hanyalah beberapa contoh sifat relasi.

Mengapa kita perlu memedulikan sifat-sifat ini? Ternyata beberapa kelompok sifat sering muncul bersama-sama, dan untuk kumpulan sifat semacam itu kita dapat membuktikan hasil umum tentang relasi-relasi yang memenuhinya. Jadi, jika kita dapat membuktikan bahwa suatu relasi bersifat refleksif, simetris, dan transitif (apa pun arti istilah-istilah itu), kita tahu bahwa relasi tersebut merupakan relasi ekuivalensi, sehingga kita juga tahu bahwa relasi itu memiliki banyak sifat lain. Sebagian besar matematika diskret membahas kajian jenis-jenis relasi tertentu. Salah satu favorit saya adalah relasi yang menghasilkan graf.

Perhatikan himpunan \(V = \{1, 2, 3, 4, 5, 6\}\text{.}\) Pasangan bilangan mana dari himpunan tersebut yang jumlahnya 7? Kita dapat memiliki \(\{1,6\}\text{,}\) \(\{2, 5\}\text{,}\) atau \(\{3,4\}\text{.}\) Kita dapat menggambarkan himpunan dan pasangan-pasangan (tak terurut) yang menarik itu (yakni, himpunan bagian beranggota dua) sebagai gambar yang disebut graf:

Di sisi lain, kita mungkin ingin menelaah pasangan bilangan yang jumlahnya genap. Dengan demikian, kita akan memperoleh gambar berikut.

Kita menyebut struktur diskret ini graf. Graf merupakan suatu jenis relasi yang bersifat simetris (jika \(a\) berelasi dengan \(b\text{,}\) maka \(b\) berelasi dengan \(a\)) dan irrefleksif (tidak ada elemen yang berelasi dengan dirinya sendiri).

Namun, kita umumnya memandang graf sebagai gambar titik-titik dan garis-garis, atau secara lebih tepat sebagai himpunan simpul bersama dengan himpunan sisi, dengan setiap sisi merupakan himpunan bagian beranggota dua dari himpunan simpul. Perhatikan bahwa bahkan di sini kita menggunakan struktur himpunan untuk mendefinisikan struktur graf.

Graf muncul dalam segala macam penerapan di dunia nyata: Di suatu kelas, beberapa mahasiswa saling berteman, jadi anggaplah para mahasiswa sebagai simpul dan hubungan pertemanan sebagai sisi. Dalam geografi, beberapa negara berbagi perbatasan, jadi anggaplah negara-negara sebagai simpul dan hubungkan sepasang simpul dengan suatu sisi jika kedua negara tersebut berbagi perbatasan. Mungkin Anda sedang merencanakan perjalanan dan ingin terbang dari Denver ke Paris. Apakah ada penerbangan langsung, atau Anda harus singgah di Newark? Dengan kata lain, apakah graf penerbangan memiliki sisi antara Denver dan Paris, atau hanya antara Denver dan Newark serta antara Newark dan Paris? Ketika kurir Amazon mengantar paket ke 10 rumah di lingkungan Anda, bagaimana aplikasinya mengetahui urutan pengantaran paket? Teori graf!

Kajian graf merupakan bidang tersendiri; banyak matematikawan meraih gelar doktor dalam bidang ini dan menulis ratusan makalah setiap tahun. Kita akan mulai menyelami permukaan bidang yang menarik ini dalam Bab 2.

Daftar struktur kita dapat terus berlanjut, tetapi kita akan berhenti di sini. Kita hanya akan meluangkan sedikit waktu untuk menelaah multihimpunan, yang serupa dengan himpunan, kecuali bahwa multihimpunan dapat memiliki elemen berulang. Karena ini bukan kelas geometri, kita tidak akan menelaah geometri hingga atau desain (yang berada di antara graf dan geometri). Struktur diskret berguna dalam ilmu komputer, tetapi kita tidak akan sampai mempelajari senarai berantai atau pohon merah-hitam. Walaupun aljabar abstrak merupakan bidang yang menarik, kita tidak akan sampai membahas grup, gelanggang, matroid, poset, aljabar Boolean, atau .... Semuanya merupakan contoh himpunan yang padanya kita mendefinisikan operasi tambahan dan mengkaji struktur aljabar dari cara himpunan dan operasi tersebut berinteraksi.

Intinya, matematika diskret itu luar biasa, dan Anda dapat menghabiskan beberapa masa hidup untuk mempelajarinya. Jadi, tunggu apa lagi? Mari kita terjun dan menyelesaikan sejumlah masalah.