1. HIMPUNAN HIMPUNAN dan OPERASINYA
1.1 Pendahuluan dan notasi . Pengertian :Himpunan adalah kumpulan elemen yang Pengertian tak beraturan. Contoh. {1, 2, 3} adl himpunan yang memuat “1” dan “2” dan “3.” {1, 1, 2, 3, 3} = {1, 2, 3} krn pengulangan tidak penting. {1, 2, 3} = {3, 2, 1} krn himpunan tidak berurutan. {0,1, 2, 3, …} adl himpunan bilangan asli tak terbatas. = {} adl himpunan kosong, karena tidak mmpunyai elemen.
Catatan: {}
1.1 Pendahuluan dan Notasi 1.2 Cardinality 1.3 Power Set 1.4 Cartesian Products
1.1 Pendahuluan dan notasi x S artinya “x artinya “x adl sebuah elemen dalam himpunan S adl sebuah elemen dalam himpunan S.” x S artinya “x artinya “x bukan sebuah elemen dalam himpunan S.” A B artinya “A artinya “A adl himpunan bagian (subset) dari B adl himpunan bagian (subset) dari B.”
atau, “B mengandung A.” atau, “setiap elemen A juga terdapat dalam B.” atau, x ((x A) (x B)). A B
Diagram Venn
1.1 Pendahuluan dan notasi A B artinya “A adl himpunan bagian dari B.” A B artinya “A adl superset dari B.” A = B jika dan hanya jika A dan B mempunyai elemen yang tepat sama iff, A B dan B A iff, A B dan A B iff, x ((x A) (x B)). Untuk menunjukkan kesamaan himp A dan B, tunjukkan: A B
1.1 Pendahuluan dan notasi A B artinya “A adl himpunan bagian layak dari B.” A B, dan A B. x ((x A) (x B)) x ((x B) (x A))
A
B A
1.1 Pendahuluan dan notasi Contoh: ● {1,2,3} {1,2,3,4,5} ● {1,2,3} {1,2,3,4,5} Is {1,2,3}? Ya! x (x ) (x {1,2,3}) terpenuhi, krn (x ) tidak benar. Tidak! Is {1,2,3}? Is {,1,2,3}? Ya! Is {,1,2,3}? Ya!
B
1.1 Pendahuluan dan notasi Quiz time: Apakah {x} {x}?
Ya
Apakah {x} {x,{x}}?
Ya
Apakah {x} {x,{x}}?
Ya
Apakah {x} {x}?
Tidak
Mendefinisikan Himpunan ● ● ●
●
Explicit: {John, Paul, George, Ringo} Implicit: {1,2,3,…}, atau {2,3,5,7,11,13,17,…} Pembangun Himpunan: { x : x adl bil prima }, { x | x adl bil ganjil }. Umum { x : P(x)}, dimana P(x) adl semacam sebutan.
Mendefinisikan Himpunan Cont. Jika D(x,y) merupakan sebutan= “x bisa dibagi oleh y” dan P(x) merupakan sebutan y ((y > 1) (y < x)) D(x,y) Maka { x : y ((y > 1) (y < x)) D(x,y) }. adl himpunan semua bil prima
1.2 Kardinalitas (Cardinality) Jika S terbatas, maka cardinality dari S, |S|, adl banyaknya elemen berbeda dalam S. |S| = 3.
S = {1,2,3} S = {3,3,3,3,3} S =
We say, “P(S) is the set of all subsets of S.” 2S = {, {a}}.
If S = {a,b}
|S| = 0.
S = {0,1,2,3,…}, |S| terbatas
If S S is If S is a set, then the power is a set, then the power set of set of S P(S) = 2 = 2S = { x x : x x S }. = { :
If S = {a}
|S| = 1.
S = { , {}, {,{}} }
1.3 Power sets
If S = 2S = {}. |S| = 3.
If S = {,{}}
2S = {, {a}, {b}, {a,b}}. 2S = {, {}, {{}}, {,{}}}.
Fact: if S is finite, |2S| = 2|S|. (if |S| = n, |2S| = 2n)
1.4 Perkalian Kartesian Perkalian Cartesian dari dua himpunan A dan B adl: A B = { (a, b) : a A b B} Jika A = {Charlie, Lucy, Linus}, dan B = {Brown, VanPelt}, maka A B = {(Charlie, Brown), (Lucy, Brown), (Linus, Brown), (Charlie, VanPelt), (Lucy, VanPelt), (Linus, VanPelt)}
2. Operasi pada Himpunan 2.1 Pendahuluan 2.2 Identitas Himpunan 2.3 Operasi umum pada himpunan 2.4 Representasi Computer terhadap himpunan
A1 A2 … An = = {(a1, a2,…, an): a1 A1, a2 A2, …, an An} A,B terbatas |A B| = |A||B|
2.1 Pendahuluan Gabungan (union) dari dua himpunan A dan B adl: A B = { x : x A x B} Jika A = {Charlie, Lucy, Linus}, dan B = {Lucy, Desi}, maka
A B = {Charlie, Lucy, Linus, Desi} B
A
2.1 Pendahuluan Irisan (intersection) dari dua himpunan A dan B adl: A B = { x : x A x B} Jika A = {Charlie, Lucy, Linus}, dan B = {Lucy, Desi}, maka A B = {Lucy} B
A
2.1 Pendahuluan Irisan dari dua himpunan A dan B adl: A B = { x : x A x B} Jika A = {x : x adl presiden Indonesia}, dan B = {x : x sesiapa dalam ruangan ini}, maka
2.1 Pendahluan Komplemen (complement) dari himpunan A adl:
A {x : x A}
If A = {x : x tdk diarsir}, maka
A ={x: x yang diarsir}
A B = {x : x adl pres. Ind dlm ruangan ini} = B
A
U
Himpunan yg irisannya kosong disebut himp. lepas
A
2.1 Pendahuluan Beda Simetri (symmetric difference), A B, adl:
●
Identitas
AU=A A = A
Dominasi
AU=U A =
U A – B
B – A
= U dan U =
2.2 Himpunan Identitas
A B = { x : (x A x B) (x B x A)}
= (A – B) (B – A) = { x : x A x B}
A
Idempotent
AA=A AA=A
2.2 Himpunan Identitas ●
2.2 Himpunan Identitas
A A U
Excluded Middle
●
A A
complement
DeMorgan’s I
DeMorgan’s
II
(A B) C = A (B C)
Distributif A (B C) = (A B) (A C) A (B (B C) = (A ) = (A B) (A (A C)
A A
4 cara membuktikan identitas
2.2 Set Identities ●
Associatif
(A B) C =A (B C) ●
Double
AB=BA
AB=BA ●
Uniqueness
Commutatif
perlihatkan bhw A B dan bhw A B.
A B A B
●
A B A B
●
Gunakan tabel anggota.
●
Gunakan bukti identitas sebelumnya.
●
Gunakan persamaan logika.
4 cara membuktikan identitas Prove that
A B A B
x A B x A B x A xB x A xB x A B
4 cara membuktikan identitas Prove that
A B A B
Menggunakan persamaan logika (A B) = {x : (x A x B)} = {x : (x A) (x B)} = {x : (x A) (x B)} = A B
4 cara membuktikan identitas Prove that
A B A B
Menggunakan tabel anggota 0 : x terdapat dalam himpunan yg disebut 1 : lainnya
A B
A
B
1 1 0 0
0 0 1 1
0 1 0 1
1 0 1 0
A B A B A B 0 0 0 1
1 1 1 0
0 0 0 1
4 cara membuktikan identitas Prove that
A ( B C ) (C B ) A
Menggunakan identitas yang telah dibuktikan A (B C) A (B C) A (B C ) (B C ) A (C B ) A
2.3 Operasi Umum pd Himpunan Gabungan Umum
n
Irisan Umum
n
A A A i
2
{x : x A1 x A2 x An }
∪ Ai = A 1 ∪ A 2∪∪ A n
contoh. Jika U = N, dan:
contoh. Jika U = N, dan:
Ai={i, i+1, i+2, …} n
i=1
i=1
Ai={i, i+1, i+2, …} Maka n
A {n,n 1,n 2,...}
Maka n
An
i 1
i=1
={x : x ∈ A 1 ∨x ∈ A 2 ∨∨ x∈ A n }
1
i
∪ Ai = ∪ {i ,i1,i2,. . .}={1,2,3,. . .}
2.4 Representasi Computer Diberikan U = {x1, x2,…, xn}, dan pilih sebarang elemen U, misal x1, x2,…, xn Jika A U. Maka bit string representation dari A adl the bit string dgn panjang n : a1 a2… an sdh ai =1 jika xi A, dan 0 untuk lainnya.
i 1
Himpunan sbg bit strings cont. Jika U = {x1, x2,…, x6}, A = {x1, x3, x5, x6}, dan B = {x2, x3, x6}. Maka cara mendapatkan A B dan A B adl sbb:
Cont. Jika U = {x1, x2,…, x6}, dan A = {x1, x3, x5, x6}, maka bit string representation dari A adl (101011)
Bit-wise OR Bit-wise AND
A 1 0 1 B 0 1 1 AB 1 1 1 AB 0 0 1
0 0 0 0
1 0 1 0
1 1 1 1
