Kang Nur


Suka main, njajan, dan data
Rabu, 29 Nov 2023
Share: 

Diperbarui Rabu, 06 Des 2023

Ditulis oleh Kang Nur

Teori Himpunan

Daftar Isi

Apa itu himpunan?

Mungkin kita sudah pernah belajar himpunan sejak bangku SMP, namun tahukah kamu himpunan ini adalah teori yang fundamental di bidang Ilmu Komputer. Himpunan adalah kumpulan objek atau elemen yang memiliki karakteristik tertentu. Setiap objek atau elemen dalam himpunan bersifat unik; artinya, tidak ada duplikasi elemen dalam himpunan. Objek atau elemen dalam himpunan juga tidak memiliki urutan tertentu; artinya, tidak peduli dalam urutan mana elemen-elemen tersebut ditulis. Himpunan biasanya dinotasikan dengan kurung kurawal $$\{\}$$. Dalam pemrograman komputer, himpunan sering disebut struktur data set.

Contoh pada bahasa python:

  

    A = {1, 2, 3} # Himpunan A
    B = {3, 4, 5} # Himpunan B

Cara penulisan himpunan

Ada berbagai macam cara ketika kita mau menyajikan atau menuliskan himpunan. Berikut cara-caranya:

  1. Enumerasi

    Penulisan himpunan dengan enumerasi adalah dengan menyebutkan elemen-elemen himpunan tersebut secara eksplisit.

    • Himpunan tradisi Banyuwangi

      $$A = \{Kebo-Keboan, Seblang, Puter\ Kayun\}$$

    • Himpunan makanan Banyuwangi

      $$B = \{Rujak \ Soto, Sego\ Tempong, Sego\ Cawuk\}$$

    Keanggotaan

    • $$x \in A$$ : $$x$$ anggota dari himpunan $$A$$

    • $$x \notin A $$: $$x$$ bukan anggota dari himpunan $$A$$

  1. Simbol-simbol Baku

    Penulisan himpunan dengan simbol baku adalah dengan melibatkan beberapa notasi standar.

    • Himpunan bilangan bulat

      $$\mathbb{Z} = \{...,-3,-2,-1,0,1,2,3,...\}$$

    • Himpunan bilangan rasional

      $$\mathbb{Z} = \{\frac{a}{b}|a \in \mathbb{Z},b \notin \mathbb{Z} ,b \neq 0 \}$$

    • Himpunan bilangan real

      $$\mathbb{R}^+=\{ x \in \mathbb{R} | x \geq 0 \}$$

    • Himpunan bilangan kompleks

      $$\mathbb{C}=\{ a + bi | a,b \in \mathbb{R} \}$$

  2. Deskripsi

    Penulisan himpunan dengan deskripsi dilakukan dengan memberikan kriteria atau kondisi yang harus dipenuhi oleh elemen-elemen himpunan. Bentuk ini juga dikenal dengan notasi predikat.

    • Himpunan bilangan ganjil

      $$A=\{x|x \ adalah \ bilangan \ ganjil \ dan \ x<10\}$$

      Cara membacanya: "Himpunan $$A$$ adalah himpunan semua bilangan bulat $$x$$, dimana $$x$$ merupakan bilangan ganjil dan kurang dari 10."

      Atau : $$A=\{x|x\in\mathbb{Z},x\in P,x<10\}$$

      Atau: $$A=\{1,3,5,7,9\}$$

    • Himpunan huruf konsonan

      $$B=\{z|z \ adalah \ huruf \ konsonan\}$$

      Cara membacanya: "Himpunan $$B$$ adalah himpunan semua huruf $$z$$, dimana $$z$$ merupakan huruf konsonan."

      Atau: $$B=\{z|z\in \ Huruf \ Konsonan\}$$

      Atau: $$B=\{b,c,d,f,g,h,j,k,l,m,n,p,q,r,s,t,v,w,x,y,z\}$$

    • Himpunan angka prima

      $$C=\{p|p \ adalah \ angka \ prima\}$$

      Cara membacanya: "Himpunan $$C$$ adalah himpunan semua angka $$p$$, dimana $$p$$ merupakan bilangan prima."

      Atau: $$C=\{p|p\in \mathbb{N},p \ adalah \ angka \ prima\}$$

      Atau: $$C=\{2,3,5,7,...\}$$

    • Himpunan bilangan genap negatif

      $$D=\{y|y \ adalah \ bilangan \ genap \ dan \ y<0\}$$

      Cara membacanya: "Himpunan $$D$$ adalah himpunan semua bilangan bulat $$y$$, dimana $$y$$ merupakan bilangan genap dan kurang dari 0."

      Atau: $$D=\{y|y\in \mathbb{Z} , y \ genap, y<0\}$$

      Atau: $$D=\{-2,-4,-6,-8,...\}$$

  3. Diagram Venn

    Diagram venn adalah representasi grafis dari himpunan yang menggunakan lingkaran untuk memperlihatkan hubungan antar himpunan.

    • Himpunan A dan B dengan intersect

      Misalkan $$A=\{1,2,3,4\}$$ dan $$B=\{3,4,5,6\}$$.

      Diagram venn akan memiliki dua lingkaran yang tumpang tindih masing-masing.

      Elemen yang tumpang tindih merupakan elemen yang ada di kedua himpunan (intersect).

      Gambar 1. diagram venn berbentuk intersect

    • Himpunan A dan B dengan disjoint

      Misalkan $$A=\{1,2,3\}$$ dan $$B=\{4,5,6\}$$.

      Diagram venn akan memiliki dua lingkaran yang tidak tumpang tindih (disjoint).

      Elemen yang berada di dalam satu lingkaran tetapi tidak di lingkaran lain adalah elemen unik dari masing-masing himpunan.

      Gambar 2. diagram venn berbentuk disjoint

    • Himpunan A, B, dan C dengan intersect tiga himpunan:

      Misalkan $$A={1,2,3}$$, $$B={3,4,5}$$, dan $$C={5,6,7}$$.

      Diagram Venn akan memiliki tiga lingkaran yang tumpang tindih.

      Elemen yang tumpang tindih bagian utama merupakan elemen yang ada di semua himpunan.

      Gambar 3. diagram venn berbentuk intersect tiga himpunan

Apa itu kardinalitas?

Kardinalitas adalah ukuran atau jumlah elemen dalam sebuah himpunan.

Apa saja jenis himpunan?

Ada beberapa jenis himpunan, dan masing-masing memiliki karakteristik. Berikut adalah beberapa jenis himpunan:

  1. Himpunan semesta

    • Definisi : Merupakan himpunan dari semua objek yang berbeda.

    • Notasi : $$U$$

    • Contoh : $$U=\{1,2,3,4,5\}$$

  2. Himpunan kosong

    Definisi : Merupakan himpunan yang tidak memiliki elemen.

    Notasi : $$\phi$$ atau $$\{\}$$

    Contoh : $$P=\{y|y<y\}$$, maka $$|P|=0$$

  3. Himpunan singleton

    Definisi : Merupakan himpunan yang hanya memiliki satu elemen.

    Notasi : $$\{a\}$$

    Contoh : $$P=\{2\}$$, maka $$|P|=1$$

  4. Himpunan bagian (subset)

    • Definisi : Himpunan B dikatakan sebagai subset dari $$A$$ jika setiap elemen dari $$B$$ juga merupakan elemen dari $$A$$.

    • Notasi : $$B\subseteq A$$ atau $$B \subset A$$

    • Contoh : Jika $$A=\{1,2,3\}$$ dan $$B=\{1,2\}$$, maka $$B \subseteq A$$, karena setiap elemen di $$B$$ (1 dan 2) juga terdapat di $$A$$.

    5. Ada dua jenis himpunan bagian, proper subset dan improper subset :

    Proper subset

    • Definisi : Himpunan $$B$$ dikatakan sebagai proper subset dari $$A$$ jika setiap elemen dari $$B$$ juga elemen dari $$A$$, dan $$B$$ bukanlah himpunan yang sama dengan $$A$$.

    • Notasi : $$B\subset A$$ dengan $$B\ne A$$

    • Contoh : Jika $$A=\{1,2,3\}$$ dan $$B=\{1,2\}$$, maka $$B\subset A$$, karena $$B$$ adalah subset dari $$A$$ dan $$B$$ tidak sama dengan $$A$$.

    Improper subset

    • Definisi : Himpunan $$B$$ dikatakan sebagai improper subset dari $$A$$ jika setiap elemen dari $$B$$ juga terdapat di $$A$$. Dalam hal ini, $$B$$ memang setara dengan $$A$$.

    • Notasi : $$B\subseteq A$$

    • Contoh : Jika $$A=\{1,2,3\}$$ dan $$B=\{1,2,3\}$$, maka $$B\subseteq A$$, karena setiap elemen di $$B$$ juga terdapat di $$A$$. Dalam hal ini, $$B$$ adalah himpunan yang sama dengan $$A$$.

  1. Himpunan yang sama

    • Definisi : Dua himpunan $$A$$ dan $$B$$ dianggap setara jika setiap elemen dari $$A$$ juga merupakan elemen dari $$B$$ dan sebaliknya.

    • Notasi : $$A=B\leftrightarrow A\subseteq B \ dan \ B \subseteq A$$

    • Contoh : Jika $$A=\{1,2,2,3,3\}$$ dan $$B=\{3,2,1,1\}$$, maka $$A=B$$, karena keduanya memiliki elemen yang sama, meskipun urutannya berbeda dan jumlah elemennya tidak sama.

  2. Himpunan yang ekuivalen

    • Definisi : Dua himpunan $$A$$ dan $$B$$ dikatakan ekuivalen, jika dan hanya jika jumlah elemennya sama.

    • Notasi : $$|A| = |B|$$

    • Contoh : Jika $$X=\{1,2,3\}$$ dan $$Y=\{a,b,c\}$$, maka $$|X|=|Y|$$, karena keduanya memiliki jumlah elemen yang sama.

  3. Himpunan saling lepas (disjoint)

    • Definisi : Dua himpunan $$A$$ dan $$B$$ dikatakan saling lepas (disjoint) jika tidak memiliki elemen yang sama.

    • Notasi : $$A\cup B=\phi$$

    • Contoh : Jika $$X=\{1,2,3\}$$ dan $$Y=\{4,5,6\}$$, maka $$X\cup Y=\phi$$, karena keduanya tidak memiliki elemen yang sama.

  4. Himpunan kuasa (powerset)

    • Definisi: Himpunan kuasa $$(\mathcal{P}(A))$$ dari suatu himpunan $$A$$ adalah himpunan dari semua himpunan bagian yang mungkin dari $$A$$, termasuk himpunan kosong dan $$A$$ itu sendiri. Dan untuk jumlah elemennya $$2^{|A|}$$, di mana $$|A|$$ adalah kardinalitas atau jumlah elemen dari $$A$$.

    • Notasi : $$\mathcal{P}(A)$$ atau $$2^A$$. Jika $$|A|=n$$, maka $$|\mathcal{P}(A)|=n(\mathcal{P}(A))=2^n$$

    • Contoh : Jika $$A=\{a,b\}$$, maka $$\mathcal{P}(A)=2^A=\{\phi,\{a\},\{b\},\{a,b\}\}$$, dan $$|\mathcal{P}(A)|=2^2=4$$

Apa saja operasi himpunan?

Sebelum membahas lebih lanjut, setiap pembahasan pada operasi himpunan, akan dipraktikkan menggunakan kode python. Oleh karena itu, silakan dicoba pada kode editor masing-masing untuk melihat keluarannya.

  

    # Himpunan Semesta
    universal_set = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    # Himpunan A dan B
    set_a = {1, 2, 3, 4, 5}
    set_b = {3, 4, 5, 6, 7}

  1. Gabungan (union)

    • Definisi : Gabungan dari dua himpunan $$A$$ dan $$B$$ adalah himpunan yang berisi semua elemen yang termasuk dalam $$A$$ atau $$B$$ atau keduanya.

    • Notasi : $$A\cup B=\{x|x\in A \ atau\ x\in B\}$$

    • Contoh : Jika $$A=\{1,2,3,4,5\}$$ dan $$B=\{3,4,5,6,7\},$$ maka $$A\cup B=\{1,2,3,4,5,6,7\}.$$

    2. Kode python:

      

    # Union (gabungan) dari A dan B
    union_result = set_a.union(set_b)
    print("Union (A ∪ B):", union_result)

  1. Irisan (intersection)

    • Definisi : Irisan dari dua himpunan $$A$$ dan $$B$$ adalah himpunan yang berisi semua elemen yang dimiliki oleh kedua himpunan $$A$$ dan $$B.$$

    • Notasi : $$A\cap B= \{x|x\in A \ dan \ x\in B\}$$

    • Contoh : Jika $$A=\{1,2,3,4,5\}$$ dan $$B=\{3,4,5,6,7\},$$ maka $$A\cap B = \{3,4,5\}.$$

    2. Kode python:

      

    # Intersection (irisan) dari A dan B
    intersection_result = set_a.intersection(set_b)
    print("Intersection (A ∩ B):", intersection_result)

  1. Komplemen (complement)

    • Definisi : Komplemen dari himpunan $$A$$ adalah himpunan yang berisi semua elemen di himpunan semesta $$U$$ tetapi tidak termasuk di dalam $$A.$$

    • Notasi : $$\bar{A}=\{x|x\in U, x\notin A\}$$

    • Contoh : Jika $$U=\{1,2,3,4,5,6,7,8,9,10\}$$ dan $$A=\{1,2,3,4,5\},$$ maka $$\bar{A}=\{6,7,8,9,10\}.$$

    2. Kode python:

      

    # Complement (komplemen) dari A terhadap himpunan semesta
    complement_a = universal_set.difference(set_a)
    print("Complement (A'): ", complement_a)

  1. Selisih (difference)

    • Definisi : Selisih dari himpunan $$A$$ dan $$B$$ adalah himpunan yang berisi elemen-elemen yang terdapat di $$A$$ tetapi tidak ada di $$B.$$

    • Notasi : $$A-B=\{x|x\in A\ dan\ x\notin B\}$$

    • Contoh : Jika $$A=\{1,2,3,4,5\}$$ dan $$B=\{3,4,5,6,7\},$$ maka $$A-B=\{1,2\}.$$

    2. Kode python:

      

    # Difference (selisih dengan setiap elemen dalam set_a) dari A terhadap B
    difference_result = set_a.difference(set_b)
    print("Difference (A - B):", difference_result)

  1. Beda setangkup (symmetric difference)

    • Definisi : Beda setangkup dari dua himpunan $$A$$ dan $$B$$ adalah himpunan yang berisi elemen-elemen yang hanya terdapat di $$A$$ atau hanya terdapat di $$B$$, tetapi tidak keduanya.

    • Notasi : $$A\oplus B=(A\cup B)-(A\cap B)=(A-B)\cup(B-A)$$

    • Contoh : $$A=\{1,2,3,4,5\}$$ dan $$B=\{3,4,5,6,7\},$$ maka $$A\oplus B=\{1,2,6,7\}.$$

    2. Kode python:

      

    # Symmetric Difference (elemen yang hanya ada di satu himpunan) dari A dan B
    symmetric_difference_result = set_a.symmetric_difference(set_b)
    print("Symmetric Difference (A Δ B):", symmetric_difference_result)

  1. Perkalian kartesian (cartesian product)

    • Definisi : Perkalian kartesian dari dua himpunan $$A$$ dan $$B$$ adalah himpunan dari semua pasangan terurut, di mana $$a\in A$$ dan $$b\in B.$$

    • Notasi : $$A\times b=\{(a,b)|a\in A\ dan\ b\in B\}$$

    • Contoh : Jika $$A=\{1,2,3,4,5\}$$ dan $$B=\{3,4,5,6,7\},$$ maka $$A\times B=\{(1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7)\}.$$

    2. Kode python:

      

    # Cartesian Product (perkalian kartesian) dari A dan B
    cartesian_product_result = [(x, y) for x in set_a for y in set_b]
    print("Cartesian Product (A × B):", cartesian_product_result)

Apa saja hukum-hukum himpunan?

  1. Identitas

    • Notasi : $$A\cup \phi=A$$ dan $$A\cap U=A$$

    • Arti : Gabungan dengan himpunan kosong adalah himpunan itu sendiri, dan irisan dengan himpunan universal adalah himpunan itu sendiri.

  2. Null/Dominasi

    • Notasi : $$A\cap \phi=\phi$$ dan $$A\cup U=U$$

    • Arti : Irisan dengan himpunan kosong adalah himpunan kosong, dan gabungan dengan himpunan universal adalah himpunan universal.

  3. Komplemen

    • Notasi : $$A\cap \bar{A}= \phi$$ dan $$A\cup \bar{A}=U$$

    • Arti : Irisan dengan komplemen adalah himpunan kosong, dan gabungan dengan komplemen adalah himpunan universal.

  4. Idempoten

    • Notasi : $$A\cap A=A$$ dan $$A\cup A=A$$

    • Arti : Irisan atau gabungan dengan dirinya sendiri adalah himpunan itu sendiri.

  5. Involusi

    • Notasi : $$\bar{(\bar{A})} = A$$

    • Arti : Komplemen dari komplemen adalah himpunan itu sendiri.

  6. Absorpsi

    • Notasi : $$A\cap (A\cup B)=A$$ dan $$A\cap (A\cup B)=A$$

    • Arti : Irisan dengan gabungan atau gabungan dengan irisan menghasilkan himpunan yang lebih besar.

  7. Komutatif

    • Notasi : $$A\cap B=B\cap A$$ dan $$A\cup B=B\cup A$$

    • Arti : Urutan himpunan dalam operasi irisan atau gabungan tidak mempengaruhi hasil.

  8. Asosiatif

    • Notasi : $$A\cap (B\cap C)=(A\cap B)\cap C$$ dan $$A\cup (B\cup C)=(A\cup B)\cup C$$

    • Arti : Hubungan antara tiga himpunan dalam operasi irisan atau gabungan tidak bergantung pada cara pengelompokan.

  9. De Morgan

    • Notasi : $$\bar{(A\cap B)}= \bar{A}\cup \bar{B}$$ dan $$\bar{(A\cup B)}= \bar{A}\cap \bar{B}$$

    • Arti : Komplemen dari irisan adalah gabungan dari komplemen, dan sebaliknya.

  10. Distributif

    • Notasi : $$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$$ dan $$A\cup (B\cap C)=(A\cup B)\cap(A\cup C)$$

    • Arti : Distribufitas irisan terhadap gabungan dan sebaliknya.

  11. Hukum 0/1

    • Notasi : $$\bar{\phi}=U$$ dan $$\bar{U}=\phi$$

    • Arti : komplemen himpunan kosong adalah himpunan semesta, dan komplemen himpunan semesta adalah himpunan kosong.

Apa itu prinsip dualitas?

Prinsip dualitas adalah ketika ada dua konsep yang berbeda dapat saling dipertukarkan, tetapi tetap memberikan jawaban yang benar.

Dualitas seringkali memberikan perspektif yang berbeda atau sudut pandang alternatif terhadap suatu fenomena atau struktur matematika.

Sebagai contoh dalam kehidupan sehari-hari ada senang dan sedih. Kehidupan seringkali dipenuhi dengan momen senang dan sedih. Konsep dualitas di sini mencerminkan bahwa kedua perasaan ini adalah bagian alami dari kehidupan manusia dan satu tidak bisa ada tanpa yang lain.

Prinsip dualitas dalam teori himpunan

Anggaplah terdapat suatu kesetaraan (identity) yang melibatkan himpunan serta operasi-operasi himpunan seperti $$\cap$$, $$\cup$$, dan komplemen. Jika kita membentuk $$S^*$$ dari $$S$$ dengan menukar:

$$\cup \to \cap$$

$$\cap \to \cup$$

$$\phi \to U$$

$$U\to \phi$$

dan mempertahankan operasi komplemen seperti semula, maka prinsip kesetaraan $$S^*$$ juga berlaku dan dikenal sebagai dual dari prinsip kesetaraan $$S$$.

  1. Identitas

    • Notasi : $$A\cup \phi=A$$ dan $$A\cap U=A$$

    • Dualnya : $$A\cap U=A$$ dan $$A\cup \phi=A$$

  2. Null/Dominasi

    • Notasi : $$A\cap \phi=\phi$$ dan $$A\cup U=U$$

    • Dualnya : $$A\cup U=U$$ dan $$A\cap \phi=\phi$$

  3. Komplemen

    • Notasi : $$A\cap \bar{A}= \phi$$ dan $$A\cup \bar{A}=U$$

    • Dualnya : $$A\cup \bar{A}=U$$ dan $$A\cap \bar{A}=\phi$$

  4. Idempoten

    • Notasi : $$A\cap A=A$$ dan $$A\cup A=A$$

    • Dualnya : $$A\cup A=A$$ dan $$A\cap A=A$$

  5. Absorpsi

    • Notasi : $$A\cap (A\cup B)=A$$ dan $$A\cap (A\cup B)=A$$

    • Dualnya : $$A\cup(A\cap B)=A$$ dan $$A\cup(A\cap B)=A$$

  6. Komutatif

    • Notasi : $$A\cap B=B\cap A$$ dan $$A\cup B=B\cup A$$

    • Dualnya : $$A\cup B=B\cup A$$ dan $$A\cap B=B\cap A$$

  7. Asosiatif

    • Notasi : $$A\cap (B\cap C)=(A\cap B)\cap C$$ dan $$A\cup (B\cup C)=(A\cup B)\cup C$$

    • Dualnya : $$A\cup (B\cup C)=(A\cup B)\cup C$$ dan $$A\cap (B\cap C)=(A\cap B)\cap C$$

  8. De Morgan

    • Notasi : $$\bar{(A\cap B)}= \bar{A}\cup \bar{B}$$ dan $$\bar{(A\cup B)}= \bar{A}\cap \bar{B}$$

    • Dualnya : $$\bar{(A\cup B)}=\bar{A}\cap \bar{B}$$ dan $$\bar{(A\cap B)}= \bar{A}\cup \bar{B}$$

  9. Distributif

    • Notasi : $$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$$ dan $$A\cup (B\cap C)=(A\cup B)\cap(A\cup C)$$

    • Dualnya : $$A\cup (B\cap C)=(A\cup B)\cap(A\cup C)$$ dan $$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$$

  10. Hukum 0/1

    • Notasi : $$\bar{\phi}=U$$ dan $$\bar{U}=\phi$$

    • Duanya : $$\bar{U}=\phi$$ dan $$\bar{\phi}=U$$

Apa itu prinsip inklusi-eksklusi?

Prinsip inklusi-eksklusi adalah suatu metode dalam teori himpunan yang digunakan untuk menghitung jumlah elemen digabungkan beberapa himpunan dengan mempertimbangkan pengulangan elemen-elemen tersebut. Metode ini berguna ketika kita memiliki beberapa himpunan yang tumpang tindih (overlapping) dan ingin menghitung total elemen unik dalam gabungan semua himpunan tersebut.

Prinsip inklusi-eksklusi dapat dinyatakan dengan rumus sebagai berikut:

$$|A_{1}\cup A_{2}\cup \cdots\cup A_{n}|=\sum_{i=1}^{n}|A_{i}|-\sum_{1\leq i<j\leq n} |A_{i}\cap A_{j}|+ \sum_{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|+\cdots+(-1)^{n-1}|A_{1}\cap A_{2}\cap\cdots\cap A_{n}|$$

Dimana:

Pola ini dilanjutkan hingga $$n-$$himpunan dengan menggunakan aturan inklusi-eksklusi, dengan tanda positif dan negatif secara bergantian. Tanda negatif digunakan untuk memperhitungkan pengurangan elemen yang tumpang tindih, dan tanda positif digunakan untuk menambahkan elemen-elemen yang mungkin telah dikurangkan berlebihan.

Studi kasus:

Sebuah kelas memiliki 30 siswa yang mengambil mata pelajaran Matematika, 25 siswa yang mengambil mata pelajaran Bahasa Inggris, dan 20 siswa yang mengambil keduanya. Jika setiap siswa mengambil setidaknya satu mata pelajaran, berapa jumlah total siswa yang ada di kelas tersebut?

Jadi, terdapat 35 siswa secara total di kelas tersebut.

Di sebuah sekolah, terdapat 80 siswa yang mengikuti klub Matematika, 60 siswa yang mengikuti klub Sains, dan 40 siswa yang mengikuti kedua-duanya. Jika jumlah total siswa di sekolah tersebut adalah 150, berapa banyak siswa yang tidak mengikuti klub Matematika atau Sains?

Jadi, terdapat 50 siswa yang tidak mengikuti klub matematika atau sains.

Di suatu sekolah, terdapat 120 siswa yang mengambil pelajaran Matematika, 90 siswa yang mengambil pelajaran Fisika, 60 siswa yang mengambil pelajaran Kimia, 40 siswa yang mengambil Matematika dan Fisika, 30 siswa yang mengambil Matematika dan Kimia, 20 siswa yang mengambil Fisika dan Kimia, dan 10 siswa yang mengambil ketiga pelajaran sekaligus. Berapa jumlah total siswa yang mengambil salah satu atau ketiganya dari pelajaran Matematika, Fisika, atau Kimia?

Jadi, terdapat 190 siswa yang mengambil salah satu atau ketiganya dari pelajaran matematika, fisika, atau kimia.

Apa itu partisi?

Partisi pada himpunan adalah pembagian himpunan ke dalam beberapa sub-himpunan yang disebut bagian, sedemikian sehingga setiap elemen himpunan terletak tepat dalam satu bagian. Dengan kata lain, partisi mengelompokkan elemen-elemen himpunan sedemikian rupa sehingga setiap elemen hanya terdapat dalam satu kelompok (bagian).

Secara formal, partisi dari himpunan $$A$$ adalah himpunan bagian $$P$$ dari $$A$$ sedemikian sehingga:

  1. $$P$$ tidak boleh kosong, artinya tidak ada bagian yang kosong.

  2. Gabungan dari semua bagian $$P$$ sama dengan himpunan asal $$A$$, yaitu $$\cup_{B\in P}B=A$$.

  3. Setiap dua bagian yang berbeda harus saling lepas (tidak ada irisan), artinya jika $$B_{1}$$ dan $$B_{2}$$ adalah dua bagian yang berbeda, maka $$B_{1}\cap B_{2}=\phi$$.

Contoh:

Partisi dari himpunan $$A=\{1,2,3,4\}$$ dapat diberikan sebagai berikut:

  1. $$P_{1}=\{\{1,2\},\{3\},\{4\}\}$$

  2. $$P_{2}=\{\{1,2,3\},\{4\}\}$$

  3. $$P_{3}=\{\{1\},\{2,3\},\{4\}\}$$

Contoh di atas adalah partisi dari himpunan $$A$$ karena memenuhi syarat-syarat di atas. Pada setiap kasus, setiap elemen dari himpunan $$A$$ terdapat dalam satu dan hanya satu bagian dari partisi tersebut.

Studi kasus sehari-hari

Misalkan kita memiliki himpunan $$X$$ yang berisi semua buku-buku yang tersedia di perpustakaan suatu sekolah. Kita ingin mengorganisir buku-buku tersebut ke dalam beberapa kategori sehingga setiap buku hanya terletak di satu kategori. Ini adalah contoh penerapan konsep partisi.

Himpunan asal:

$$X=\{Buku\ 1, Buku\ 2, Buku\ 3,\cdots,Buku\ N\}$$

Partisi berdasarkan kategori

Kita dapat membuat partisi berdasarkan kategori buku, misalnya:

$$P_{1}=\{Buku-buku\ Matematika\},$$

$$P_{2}=\{Buku-buku\ Fisika\},$$

$$P_{3}=\{Buku-buku\ Sejarah\},$$

$$\vdots$$

$$P_{k}=\{Buku-buku\ kategori\ ke-k\}$$

Setiap buku akan masuk ke dalam satu kategori, Gabungan dari semua kategori akan mencakup semua buku di perpustakaan.

Manfaat konsep partisi:

Dengan menerapkan konsep partisi, perpustakaan dapat diorganisir dengan lebih baik dan pengunjung dapat dengan mudah menemukan buku-buku yang mereka cari.

Apa itu himpunan ganda (multiset)?

Himpunan ganda, atau yang lebih dikenal sebagai multiset, adalah bentuk khusus dari himpunan di mana elemen-elemen tertentu dapat muncul lebih dari satu kali. Dalam himpunan konvensional, setiap elemen hanya dapat muncul sekali atau tidak muncul sama sekali, tetapi dalam multiset, elemen-elemen dapat memiliki multiplisitas yang berbeda, artinya elemen-elemen tersebut dapat muncul lebih dari satu kali.

Sebagai contoh multiset berikut:

$$\{1,2,2,3,3,3,4\}$$

Di sini, elemen 2 muncul dua kali, elemen 3 muncul tiga kali, dan elemen- elemen lain muncul satu kali. Dalam multiset, urutan elemen tidak penting; yang penting adalah jumlah kemunculan masing-masing elemen.

Sifat-sifat multiset melibatkan penghitungan berdasarkan kemunculan elemen, dan operasi-operasi seperti penambahan, pengurangan, dan penggabungan multiset memperhitungkan jumlah elemen yang sama. Sebagai contoh, jika kita mengurangkan multiset $$\{1,2,2,3,3,3,4\}$$ dengan multiset $$\{2,3,3,5\}$$, hasilnya akan menjadi $$\{1,2,3,4\}$$.

Multiset sering digunakan dalam konteks di mana kita perlu melacak jumlah kemunculan setiap elemen, seperti dalam analisis statistik, pengolahan kata, atau struktur data tertentu. Multiset dapat diimplementasikan menggunakan berbagai struktur data, seperti list atau tabel hash.

Bagaimana menghitung kardinalitas pada multiset?

Kardinalitas pada multiset mengacu pada jumlah elemen yang ada dalam himpunan tersebut, termasuk pengulangan elemen. Berbeda dengan himpunan konvensional yang tidak memperhatikan pengulangan, multiset mencatat berapa kali setiap elemen muncul.

Untuk menghitung kardinalitas sebuah multiset, kita cukup menjumlahkan jumlah kemunculan setiap elemen dalam multiset tersebut. Misalkan $$|A|$$ menyatakan kardinalitas multiset $$A$$, dan $$n(a)$$ menyatakan jumlah kemunculan elemen $$a$$ dalam multiset. Maka,

$$|A|=\sum_{a\in A^{n(a)}}$$

Kita cukup menjumlahkan jumlah kemunculan masing-masing elemen dalam multiset untuk mendapatkan kardinalitas total.

Contoh

Misalkan $$A=\{a,a,b,c,b,a\}$$

∣$$A∣=n(a)+n(b)+n(c)=3+2+1=6$$

Jadi, kardinalitas multiset $$A$$ adalah 6.

Bagaimana membuktikan proposisi perihal himpunan?

Pembuktian proposisi perihal himpunan melibatkan langkah-langkah logis dan argumentasi yang benar untuk menunjukkan kebenaran pernyataan tersebut. Berikut adalah beberapa metode yang dapat digunakan dalam pembuktian proposisi:

  1. Pembuktian dengan tabel kebenaran

    Pada metode ini, kita menggunakan tabel kebenaran untuk menguji kebenaran proposisi dengan memeriksa semua kemungkinan nilai kebenaran dari elemen tersebut yang terlibat.

    Contoh :

    Proposisi : $$A\cap (B\cup C)=(A\cap B)\cup(A\cap C)$$

    Pembuktian :

    $$A$$ $$B$$ $$C$$ $$B\cup C$$ $$A\cap(B\cup C)$$ $$A\cap B$$ $$A\cap C$$ $$(A\cap B)\cup(A\cap C)$$
    1 1 1 1 1 1 1 1
    1 1 0 1 1 1 0 1
    1 0 1 1 1 0 1 1
    1 0 0 0 0 0 0 0
    0 1 1 1 0 0 0 0
    0 1 0 1 0 0 0 0
    0 0 1 1 0 0 0 0
    0 0 0 0 0 0 0 0

    Di mana:

    • $$1\in dari\ himpunan\ ini$$

    • $$0\notin dari\ himpunan\ ini$$

    2. Hasil :

    Pada contoh di atas, kita membuktikan bahwa kedua proposisi tersebut sama. Karena kolom $$A\cap(B\cup C)$$ dan kolom $$(A\cap B)\cup(A\cap C)$$ sama, maka $$A\cap (B\cup C)=(A\cap B)\cup(A\cap C).$$

  1. Pembuktian dengan aljabar himpunan

    Pada metode ini, kita menggunakan hukum-hukum aljabar himpunan untuk membuktikan proposisi.

    Contoh :

    Proposisi : $$A\cap (B\cup C)=(A\cap B)\cup(A\cap C)$$

    Pembuktian (hukum distributif) :

    $$A\cap (B\cup C)=(A\cap B)\cup(A\cap C)$$

    Misal : $$A=\{1,2,3\},$$ $$B=\{2,3,4\},$$ dan $$C=\{3,4,5\}$$

    $$A\cap (B\cup C)=\{1,2,3\}\cap(\{2,3,4\}\cup\{3,4,5\})$$

    $$A\cap (B\cup C) = \{1,2,3\}\cap \{2,3,4,5\}$$

    $$A\cap (B\cup C) = \{2,3\}$$

    $$(A\cap B)\cup(A\cap C)=(\{1,2,3\}\cap\{2,3,4\})\cup(\{1,2,3\}\cap\{3,4,5\})$$

    $$(A\cap B)\cup(A\cap C)=\{2,3\}\cup\{3\}$$

    $$(A\cap B)\cup(A\cap C)=\{2,3\}$$

    Hasil :

    Pada contoh di atas, kita membuktikan bahwa kedua proposisi tersebut sama. Karena hasil dari $$A\cap(B\cup C)$$ dan $$(A\cap B)\cup(A\cap C)$$ sama, maka $$A\cap (B\cup C)=(A\cap B)\cup(A\cap C).$$

  2. Pembuktian dengan definisi

    Pada metode ini, kita menggunakan definisi formal dari himpunan dan operasi-operasi himpunan.

    Contoh :

    Proposisi : $$A\cup \phi=A$$

    Pembuktian :

    $$A\cup \phi=\{x|x\in A\ atau\ x\in \phi\}$$

    Hasil :

    Karena $$\phi$$ adalah himpunan kosong, maka elemen-elemen dalam $$A\cup \phi$$ hanya akan menjadi elemen-elemen dalam $$A$$. Oleh karena itu, $$A\cup \phi=A.$$

Penggunaan himpunan pada teori bahasa formal

Teori himpunan memiliki aplikasi yang luas, termasuk dalam teori bahasa. Dalam konteks ini, alfabet, string, dan bahasa dapat direpresentasikan menggunakan konsep-konsep himpunan. Berikut contoh penggunaan himpunan dalam teori bahasa:

  1. Alfabet

    Alfabet dalam teori bahasa adalah himpunan simbol-simbol atau karakter yang dapat digunakan untuk membentuk string atau kata. Misalnya, jika kita memiliki alfabet bahasa Inggris, kita dapat menggambarkan sebagai himpunan:

    $$\sum=\{a,b,c,d,\cdots,z\}$$

    Pada Natural Language Processing (NLP), alfabet dapat berupa himpunan huruf latin, angka, atau karakter khusus yang digunakan dalam suatu bahasa.

  2. String

    String dalam bahasa dapat direpresentasikan sebagai himpunan substring atau urutan simbol dari alfabet. Misalnya, kita memiliki string "cat", kita dapat menggambarkannya sebagai himpunan substring:

    $$\{c,a,t,ca,at,cat\}$$

    Pada NLP, himpunan string dapat digunakan untuk merepresentasikan kumpulan kata atau kalimat dalam suatu teks. Misalnya, himpunan string yang berisi kalimat-kalimat dari dokumen.

  3. Bahasa

    Bahasa dalam teori bahasa adalah himpunan string atau kata-kata yang dapat dihasilkan oleh suatu aturan atau tata bahasa. Misalnya, jika kita memiliki bahasa yang terdiri dari string-string yang hanya mengandung huruf "a" dan "b" dengan panjang tertentu, kita dapat menggambarkannya sebagai himpunan:

    $$L\{\in,a,b,aa,ab,ba,b,aaa,\cdots\}$$

    Di sini, $$\in$$ adalah himpunan kosong.

    Pada NLP, Sebuah bahasa dapat direpresentasikan sebagai himpunan string yang valid dalam bahasa tersebut. Contohnya, himpunan kalimat-kalimat yang valid dalam bahasa Inggris.

Dalam teori bahasa, operasi himpunan seperti gabungan, irisan, dan komplemen dapat diaplikasikan untuk string atau bahasa. Misalnya, jika $$L_{1}$$​ dan $$L_{2}$$​ adalah dua bahasa, kita dapat membentuk gabungan $$L_{1}\cup L_{2}$$​, irisan $$L_{1}\cap L_{2}$$​, atau komplemen $$\bar{L_{1}}$$ dari bahasa $$L_{1}​.$$

matematika, matematika diskrit
© 2022 - Kang Nur