matematika diskrit 1 - himpunan - official site of ahmad ...sabri.staff. diskrit 1 himpunan...

Click here to load reader

Post on 01-May-2018

229 views

Category:

Documents

4 download

Embed Size (px)

TRANSCRIPT

  • Matematika Diskrit 1Himpunan

    Dr. Ahmad Sabri

    Universitas Gunadarma

  • Matematika Diskrit 1

    Pendahuluan

    Apakah Matematika Diskrit itu?

    Matematika diskrit adalah kajian terhadap objek/strukturmatematis, di mana objek-objek tersebut diasosiasikan sebagainilai-nilai diskrit.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Himpunan

    Definisi

    Himpunan adalah kumpulan objek dengan karakteristik yang telahdidefinisikan sebelumnya.

    Contoh

    Himpunan mahasiswa UG.

    Himpunan bilangan genap.

    Himpunan untai biner panjang 5 yang memiliki 3 simbol 1.

    dsb.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Himpunan

    Definisi

    Himpunan adalah kumpulan objek dengan karakteristik yang telahdidefinisikan sebelumnya.

    Contoh

    Himpunan mahasiswa UG.

    Himpunan bilangan genap.

    Himpunan untai biner panjang 5 yang memiliki 3 simbol 1.

    dsb.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Notasi pada himpunan

    Simbol himpunan dinyatakan dalam huruf besar miring,anggota-anggotanya ditulis di antara kurung kurawal {}, dansetiap anggotanya dipisahkan oleh koma. Urutan simbol tidakberpengaruh. Contoh A = {a, i, u, e, o} = {i, o, a, e, u}Relasi: , 3, , , , .Negasi dari relasi: /, 63, 6, *, 6, 6.Operasi: ,

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Contoh

    A = {1, 3, 5, 7, . . .} dapat dinyatakan sebagaiA = {x|x bilangan ganjil}B = {x|x2 + 3x 10 = 0}, C = { 5, 2},D = {5, 2, 2,5}. Maka, B = C = D.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Subhimpunan

    Definisi

    Diberikan dua himpunan A dan B. Jika untuk sebarangx A berlaku x B, maka dikatakan A adalah subhimpunandari B. Secara matematis, A B, atau B A.A = B jika dan hanya jika A B dan B A.Jika A B dan A 6= B, maka A dikatakan sebagaisubhimpunan sejati (proper subset) dari B, dan dinotasikansebagai A B.

    Untuk seterusnya, istilah subhimpunan mengacu pada simbol .

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Beberapa himpunan yang sering digunakan

    N: himpunan bilangan natural (asli) 1, 2, 3, . . ..

    Z: himpunan bilangan integer (bulat) . . . ,2,1, 0, 1, 2, . . ..Q: himpunan bilangan rasional.

    R: himpunan bilangan riil.

    C: himpunan bilangan kompleks.

    Perhatikan bahwa N Z Q R C.

    U: himpunan semesta

    atau {}: himpunan kosong

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Himpunan disjoin

    Definisi

    Himpunan A dan B dikatakan disjoin jika tidak terdapat elemenanggota A yang juga menjadi anggota B.

    Contoh

    Diberikan A = {2, 4, 6, 8, 10}, B = {2, 4, 8, 16}, C = {1, 3, 5, 7, 9}.A dan B tidak disjoin. Namun, A dan C disjoin, demikian pulahalnya denga B dan C.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Diagram Venn

    Diagram Venn adalah representasi himpunan secara visual, di manareprsentasi himpunan tersebut berada dalam sua-tu daerah persegi panjang sebagai representasi himpunan semesta U.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Operasi pada himpunan

    : operasi gabung. A B = {x|x A atau x B}: operasi iris. A B = {x|x A dan x B}

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Jika A dan B disjoin, maka A B = .Jika S = A B dan A B = , maka S dikatakan sebagaigabungan disjoin dari A dan B.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Teorema

    Diberikan sebarang dua himpunan A dan B. Maka berlaku:

    A B A A B, danA B B A B.

    Teorema

    Ketiga pernyataan berikut ekivalen:

    A B,A B = A,A = B.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Teorema

    Diberikan sebarang dua himpunan A dan B. Maka berlaku:

    A B A A B, danA B B A B.

    Teorema

    Ketiga pernyataan berikut ekivalen:

    A B,A B = A,A = B.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Generalisasi operasi himpunan

    Diberikan sejumlah hingga himpunan A1, A2, . . . , Am. Operasigabung dan iris untuk semua himpunan tersebut didefinisikansebagai berikut:

    A1A2. . .Am =m

    i=1Ai = {x|x Ai untuk beberapa i}A1 A2 . . . Am =

    mi=1Ai = {x|x Ai untuk semua i}

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Komplemen mutlak

    Definisi

    Komplemen mutlak (selanjutnya disebut komplemen) darihimpunan A, dinotasikan sebagai AC atau A, adalah himpunanelemen semesta yang bukan merupakan elemen himpunan A.Secara matematis, A = {x|x U, x / A}.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Komplemen relatif

    Definisi

    Komplemen relatif dari himpunan B terhadap himpunan A,dinotasikan sebagai A \B (dibaca A kurang B), adalah himpunanelemen anggota A yang bukan merupakan elemen anggota B.Secara matematis, A = {x|x A, x / B}.

  • Matematika Diskrit 1

    Himpunan

    Konsep-konsep dasar

    Perbedaan simetris

    Definisi

    Perbedaan simetris (symmetric difference) dari himpunan A danB, dinotasikan sebagai AB, terdiri dari elemen-elemen anggotaA atau anggota B, namun tidak keduanya. Secara matematis:

    AB = (A B) \ (A B),

    atauAB = (A \B) (B \A).

  • Matematika Diskrit 1

    Himpunan

    Aljabar himpunan

    Aljabar himpunan

  • Matematika Diskrit 1

    Himpunan

    Himpunan hingga dan prinsip pencacahan

    Himpunan hingga

    Himpunan A dikatakan hingga jika A adalah atau|A| = c > 0, c integer (A memuat tepat sejumlah hinggaelemen). Dalam kasus lain, A dikatakan tak-hingga.

    Himpunan A dikatakan terhitung (countable) jika A hingga,atau jika elemen-elemen pada A dapat disusun dalam polabarisan. Dalam kasus yang terakhir ini A dikatakan terhitungtak-hingga (countably infinite). Dalam hal yang lainnya, Adikatakan tak terhitung (uncountable).

  • Matematika Diskrit 1

    Himpunan

    Himpunan hingga dan prinsip pencacahan

    Prinsip pencacahan

    Kardinalitas (banyak elemen) dari himpunan A dinotasikan sebagain(A), |A|, #(A), atau card(A).Jika A dan B himpunan hingga dan disjoin, maka:

    n(A B) = n(A) + n(B).n(A \B) = n(A) n(A B).n(A) = n(U) n(A).

  • Matematika Diskrit 1

    Himpunan

    Himpunan hingga dan prinsip pencacahan

    Prinsip pencacahan

    Jika A dan B himpunan hingga dan tidak disjoin, maka:

    n(A B) = n(A) + n(B) n(A B).

    Prinsip di atas di sebut sebagai Prinsip inklusi-eksklusi.

  • Matematika Diskrit 1

    Himpunan

    Himpunan hingga dan prinsip pencacahan

    Prinsip pencacahan

    Jika A dan B himpunan hingga dan tidak disjoin, maka:

    n(A B) = n(A) + n(B) n(A B).

    Prinsip di atas di sebut sebagai Prinsip inklusi-eksklusi.

  • Matematika Diskrit 1

    Himpunan

    Kelas, partisi, dan himpunan kuasa

    Kelas himpunan

    Himpunan-himpunan yang memiliki beberapa kesamaankarakteristik objek membentuk sebuah kelas himpunan.

    Kelas himpunan pada dasarnya adalah himpunan yangberanggotakan himpunan.

  • Matematika Diskrit 1

    Himpunan

    Kelas, partisi, dan himpunan kuasa

    Himpunan pangkat

    Definisi

    Diberikan sebuah himpunan hingga A. Himpunan pangkat dari A,dinotasikan sebagai P (A), adalah sebuah himpunan yangberanggotakan semua subhimpunan dari A.

    Kardinalitas P (A) dinotasikan sebagai 2A, dan diberikan oleh2n(A).

  • Matematika Diskrit 1

    Himpunan

    Kelas, partisi, dan himpunan kuasa

    Himpunan pangkat

    Definisi

    Diberikan sebuah himpunan hingga A. Himpunan pangkat dari A,dinotasikan sebagai P (A), adalah sebuah himpunan yangberanggotakan semua subhimpunan dari A.

    Kardinalitas P (A) dinotasikan sebagai 2A, dan diberikan oleh2n(A).

  • Matematika Diskrit 1

    Himpunan

    Kelas, partisi, dan himpunan kuasa

    Himpunan partisi

    Sebuah k-partisi dari himpunan S adalah himpunan{A1, A2, . . . , Ak} di mana:

    Ai Aj = , untuk i 6= j (Ai dan Aj disjoin).ki=1Ai = S

    PendahuluanHimpunanKonsep-konsep dasarAljabar himpunanHimpunan hingga dan prinsip pencacahanKelas, partisi, dan himpunan kuasa