Himpunan Matematika Diskret (TKE132107) Program Studi Teknik Elektro, Unsoed

Himpunan Matematika Diskret (TKE132107) Program Studi Teknik Elektro, Unsoed Iwan Setiawan <stwn at unsoed.ac.id>

Tahun Ajaran 2013/2014

Obyek-obyek diskret ada di sekitar kita.

Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed

Obyek diskret pada perangkat digital?

Sekumpulan obyek.


Semua mahasiswa Teknik Elektro Unsoed.


Definisi Himpunan

Himpunan adalah kumpulan obyek-obyek yang berbeda.


Elemen/unsur/anggota.


Struktur diskret dasar yang mendasari struktur diskret lain seperti relasi, kombinasi, graf, ...


Penyajian Himpunan

Ada 4 cara menyajikan himpunan.


(1) Enumerasi (menuliskan semua elemen)


Simbol huruf kapital.


Kurung kurawal.


Himpunan A berisi anggota 5,3,7,9. Sajikan dengan cara enumerasi!

Himpunan B berisi enam bilangan ganjil positif pertama. Sajikan dengan cara enumerasi!

Himpunan ditentukan oleh anggotaanggotanya, bukan urutan anggotanya.


Mengandung anggota yang berbeda.


Himpunan C berisi Badu, 45, kayu, kucing, g. Sajikan dengan cara enumerasi!

T = {a, b, {a,b,c}, {a,c}} U = {a, {a}, {{a}}} V = {{}} Apakah himpunan-himpunan di atas dapat disebut sebagai himpunan?

W = {a,b,c,...,x,y,z} X = {1,2,...,100}


x∈A x∉A


A = {1, 2, 3, 4} Z = {{}} Tuliskan elemen dengan notasi anggota!

P1 = {a, b} P2 = {{a,b}} Tuliskan elemen dengan notasi anggota!

(2) Simbol-simbol baku


P = himpunan bilangan bulan positif = {1,2,3,...} R = himpunan bilangan nyata ...


Himpunan yang universal. (semesta)


U = {1,2,3,4}. A = {2,3}. (A adalah himpunan bagian dari U)


(3) Notasi pembentuk himpunan Notasi: { x | syarat yang harus dipenuhi oleh x}


A adalah himpunan bilangan bulat positif lebih kecil dari 7. Tulis dengan cara notasi pembentuk himpunan!

M adalah himpunan mahasiswa yang mengambil mata kuliah Matematika Diskret. Tulis dengan cara notasi pembentuk himpunan!

(4) Diagram Venn


Secara Grafis. John Venn. 1881. (segi empat, lingkaran)


U = {7, 8, 9, 10, ..., 15} A = {9, 10, 15} B = {8, 9, 12, 13, 14} Gambarkan dalam diagram Venn!

Kardinalitas

A merupakan himpunan berhingga, maka jumlah elemen berbeda di dalam A disebut kardinal dari himpunan A.


Notasi: n(A) atau |A|


A = { x | x merupakan bilangan prima lebih kecil dari 18} Jadi |A|?

Himpunan Kosong

Himpunan yang tak memiliki satupun elemen. (atau himpunan dengan kardinal = 0)

Notasi: ⊘ atau { }


F = { z | z < z} Kardinal F?

O = {orang Purwokerto yang pernah ke Pluto} Kardinal O?

Himpunan Bagian

Himpunan A merupakan himpunan bagian dari himpunan B jika dan hanya jika setiap elemen A merupakan elemen B.


A subset dari B, B superset dari A.


A⊆B


Gambarkan dalam diagram Venn!

Teorema untuk himpunan A: (1) A ⊆ A, (2) ⊘ ⊆ A, (3) Jika A ⊆ B dan B ⊆ C, maka A ⊆ C.


Proper subset dan subset.


Himpunan yang Sama

Himpunan A dikatakan sama dengan himpunan B jika dan hanya jika keduanya memiliki elemen yang sama.


Notasi: A = B ↔ A ⊆ B dan B ⊆ A


Catatan: urutan elemen tidak penting, pengulangan elemen tidak berpengaruh, aksioma himpunan.


Aksioma 3 himpunan A, B, dan C. 1. A = A, B = B, C = C. 2. Jika A = B, B = A. 3. Jika A = B dan B = C, A = C.


Himpunan yang Ekivalen

Dua himpunan dikatakan ekivalen, jika dan hanya jika keduanya berkardinal sama.


Notasi: A ~ B ↔ |A| = |B|


A = {3, 4, 5} dan B = {beruang, gajah, penguin} Apakah A dan B adalah himpunan yang ekivalen?

Himpunan Saling Lepas

Himpunan dikatakan saling lepas jika kedua himpunan tidak memiliki elemen yang sama.


Kita berbeda dalam semua, kecuali dalam cinta. – Gie (Sebuah Tanya, 1969)

Notasi: A // B



Himpunan Kuasa

Himpunan kuasa dari himpunan dari A adalah himpunan yang elemennya merupakan semua himpunan bagian dari A. (termasuk himpunan kosong dan himpunan A itu sendiri)


Notasi: P(A) atau 2A


Tulis himpunan kuasa dari F = {5,7,9}!

Himpunan kuasa dari himpunan kosong?

Operasi Terhadap Himpunan

(1) Irisan


Irisan himpunan A dan B adalah himpunan yang setiap anggotanya merupakan elemen dari himpunan A dan B.


Notasi: A ∩ B = { x | x ∈ A dan x ∈ B}



(2) Gabungan


Himpunan A dan B yang setiap anggotanya merupakan anggota himpunan A atau himpunan B.


Notasi: A ∪ B = { x | x ∈ A atau x ∈ B}



(3) Komplemen


Komplemen A terhadap himpunan semesta U adalah himpunan yang elemennya merupakan elemen U tapi bukan elemen himpunan A.


Notasi: A = { x | x ∈ U dan x ∉ A}



(4) Selisih


Himpunan yang elemennya merupakan elemen dari A tetapi bukan elemen dari B.


A – B = { x | x ∈ A dan x ∉ B } = A ∩ B



(5) Beda Setangkup


Himpunan yang elemennya ada pada himpunan A atau B, tetapi tidak pada keduanya.


A ⊕ B = (A ∪ B) – (A ∩ B) = (A-B) ∪ (B-A)



Hukum komutatif dan asosiatif pada beda setangkup dapat dibaca di buku referensi.


(6) Perkalian kartesian


Himpunan yang elemennya semua pasangan berurutan yang dibentuk dari komponen pertama dari himpunan A dan komponen kedua dari himpunan B.


Notasi: A x B = { (a,b) | a ∈ A dan b ∈ B}


Berapa banyak kombinasi makanan dan minuman yang dapat disusun dari kedua himpunan di bawah ini? A = {g = gethuk, c = coto, m = mie rebus} B = {s = susu, k = kopi, d = dawet }

Catatan ●

●

●

●

Jika A dan B merupakan himpunan berhingga, maka |A x B| = |A| . |B|. Pasangan berurutan (a,b) berbeda dengan (b,a); Dengan kata lain (a,b) ≠ (b,a). Perkalian kartesian tidak komutatif, A x B ≠ B x A, dengan syarat himpunan A dan B tidak kosong. Jika A = ⊘ atau B = ⊘ maka A x B = B x A = ⊘.


Perampatan Operasi Himpunan dapat dibaca di buku referensi.


Hukum-Hukum Aljabar Himpunan

Kesamaan himpunan (set identities).


Identitas, null/dominasi, komplemen, idempoten, involusi, penyerapan, komutatif, asosiatif, distributif, De Morgan, 0/1* * Hukum komplemen 2


Notasi pada hukum logika: ∧, ∨, B, S. Notasi pada himpunan: ∩, ∪, ⊘, dan U.


Prinsip Dualitas

Dua konsep yang berbeda dapat dipertukarkan namun tetap memberikan jawaban yang benar.


Contoh?

Letak kemudi. (keharusan berjalannya kendaraan, lajur untuk mendahului, “belok jalan terus”?)


Konsep “kiri dan kanan” dapat dipertukarkan tetapi tetap dapat berlaku di masing-masing tempat.


Prinsip dualitas juga terdapat pada himpunan.


Beberapa sifat himpunan merupakan analog satu sama lain.


A ∪ A = U analog dengan A ∩ A = ⊘


Ada lagi?

Semua pasangan dalam hukum aljabar himpunan.


Tinggal mengganti operatornya saja. (himpunan kosong ditukar dengan semesta, dan sebaliknya)


Prinsip dualitas penting dalam aljabar himpunan.


Kita dapat menggunakan prinsip ini untuk menurunkan kesamaan himpunan yang mengandung ∪ dan ∩, serta ⊘ dan U.


..atau untuk membuktikan dual dari kesamaan himpunan lain.


Dualitas hukum aljabar himpunan dapat dibaca di buku referensi.


Prinsip Inklusi-Eksklusi

Penggabungan 2 buah himpunan.


Penggabungan 2 himpunan, A dan B.


Hasilnya adalah himpunan baru yang elemen-elemennya berasal dari himpunan A dan B.


Kardinal himpunan irisan A dan B.


Pada 2 himpunan yang beririsan terdapat elemen yang dihitung 2 kali jika digabungkan.


Jadi, seharusnya elemen yang berada di dalam irisan kedua himpunan dihitung sekali saja.


Karena itu jumlah elemen hasil penggabungan kedua himpunan adalah total jumlah gabungan elemen masing-masing himpunan dikurangi jumlah elemen di dalam irisannya.


“Total gabungan” dikurangi irisannya.


|A∪B|=|A|+|B|-|A∩B|


Perkecualian jika A // B, |A∪B|=|A|+|B|


Jumlah elemen hasil operasi beda setangkup?

| A ⊕ B | = | A | + | B | – 2 (A ∩ B)


Berapa banyak bilangan bulat dari 1 sampai 1000 yang habis dibagi 5 dan 10?

Prinsip Inklusi-Eksklusi ●

●

●

Definisikan dulu himpunan dan operasinya dengan penyajian sesuai data yang diberikan. Definisikan permasalahan dalam notasi himpunan. Selesaikan permasalahan dengan konsep-konsep himpunan. ●

Kardinal tiap-tiap himpunan dan operasinya.

●

Kardinal permasalahan.

●

Kesimpulan.


3 himpunan. A, B, dan C.


|A∪B∪C|=|A|+|B|+|C|-|A∩B||A∩C|-|B ∩C|+|A∩B∩C|


Pelajari Contoh 2.36.


Pembuktian Proposisi Himpunan

Proposisi himpunan?

Proposisi yang menggunakan notasi himpunan.


A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)


Jika A ∩ B = ⊘ dan A ⊆ (B ∪ C), selalu berlaku bahwa A ⊆ C.


Terdapat 4 metode pembuktian kebenaran proposisi himpunan.


(1) Pembuktian dengan diagram Venn


Dengan cara menggambar diagram Venn untuk masing-masing ruas pada kesamaan himpunan.


Buktikan dengan diagram Venn: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Daerah arsiran yang sama.


Kekurangannya?

(2) Pembuktian dengan tabel keanggotaan


Mirip seperti tabel kebenaran dengan penggunaan nilai 0 untuk bukan anggota dan 1 untuk anggota.


Ingat operator logika dan himpunan!


Buktikan dengan tabel keanggotaan untuk: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

(3) Pembuktian dengan aljabar himpunan


Menggunakan hukum aljabar himpunan, termasuk teorema, definisi operasi himpunan, dan prinsip dualitas.


Terdapat 2 himpunan A dan B. Tunjukkan bahwa: ( A – B) – C = (A – C) – B!

(4) Pembuktian dengan menggunakan definisi


Digunakan untuk membuktikan proposisi himpunan yang tidak berbentuk kesamaan.


Sila membacanya di buku referensi :-)

Hash Milhan, CC BY, http://flic.kr/p/2qKgwi

Daftar Bacaan ●

Munir, R. 2010. Matematika Diskrit, Revisi Keempat, Penerbit Informatika.


Himpunan Matematika Diskret (TKE132107) Program Studi Teknik Elektro, Unsoed

Recommend Documents