himpunan - ee.unsoed.ac.idstwn/kul/tke132107/matdis-2013-3+1.pdfmatematika diskret (tke132107) -...

Tahun Ajaran 2013/2014

HimpunanMatematika Diskret (TKE132107)

Program Studi Teknik Elektro, Unsoed

Iwan Setiawan <stwn at unsoed.ac.id>

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

Obyek-obyek diskret ada di sekitar kita.

Obyek diskret padaperangkat digital?


Sekumpulan obyek.


Semua mahasiswa Teknik Elektro Unsoed.

Definisi Himpunan


Himpunan adalah kumpulanobyek-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 anggota-anggotanya, 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-himpunandi atas dapat disebut sebagaihimpunan?


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


x ∈ Ax ∉ 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 dalamdiagram Venn!


Teorema untuk himpunan A:

(1) A ⊆ A,(2) ⊘ ⊆ A,(3) Jika A ⊆ B dan B ⊆ C, maka A ⊆ C.


Proper subset dan subset.

Himpunanyang 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, pengu- langan 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 yangEkivalen


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?

HimpunanSaling 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 kuasadari F = {5,7,9}!

Himpunan kuasa darihimpunan 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 atauhimpunan 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 Himpunandapat dibaca di buku referensi.

Hukum-HukumAljabar 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 dipertukarkantetapi 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 dalamhukum aljabar himpunan.


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


Prinsip dualitas pentingdalam aljabar himpunan.


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


..atau untuk membuktikan dualdari kesamaan himpunan lain.


Dualitas hukum aljabar himpunandapat 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 terdapatelemen 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 hasiloperasi beda setangkup?


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

Berapa banyak bilangan bulatdari 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 pembuktiankebenaran 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 - ee.unsoed.ac.idstwn/kul/tke132107/matdis-2013-3+1.pdfmatematika diskret (tke132107) -...

Documents