1TeoriTeori HimpunanHimpunanBagianBagian IIIIII
2TeoriTeori HimpunanHimpunan HimpunanHimpunan: : KumpulanKumpulan objekobjek ((konkritkonkrit
atauatau abstrakabstrak) yang ) yang mempunyaimempunyai syaratsyarattertentutertentu dandan jelasjelas, , bisanyabisanya dinyatakandinyatakandengandengan hurufhuruf besarbesar..
aaAA a a anggotaanggota daridari AA
aaAA a a bukanbukan anggotaanggota daridari AA A = {aA = {a11, a, a22, , , a, ann} } A A memuatmemuat
3Cara Cara menyatakanmenyatakan himpunanhimpunan
a.a. MendaftarMendaftarb.b. MenyatakanMenyatakan sifatsifat--sifatsifat yang yang
dipenuhidipenuhi oleholeh anggotaanggota..c.c. NotasiNotasi pembentukpembentuk himpunanhimpunan
4NotasiNotasi PembentukPembentuk HimpunanHimpunanFormat: Format: sedemikiansedemikian hinggahingga{[{[strukturstruktur keanggotaankeanggotaan] ] || [[syaratsyarat perluperlu untukuntuk menjadimenjadi
anggotaanggota]}]}ContohContoh::Q = {m/n : m,n Q = {m/n : m,n Z, nZ, n0}0}
Q Q adalahadalah himpunanhimpunan bilanganbilangan rasionalrasional ElemenElemen--elemennyaelemennya berstrukturberstruktur m/n; m/n; harusharus
memenuhimemenuhi sifatsifat setelahsetelah tandatanda :: untukuntuk menjadimenjadianggotaanggota..
{x {x R | xR | x22 = 1} = {= 1} = {--1,1}1,1}
5ContohContoh HimpunanHimpunan::N N himpunanhimpunan bilbil. . CacahCacah = {0,1,2,3,4, }= {0,1,2,3,4, }P P atauatau Z+ Z+ -- himphimp. . BilBil. . BulatBulat positifpositif = {1,2,3,4, = {1,2,3,4,
}}Z Z himpunanhimpunan bilbil. . bulatbulatR R himpunanhimpunan bilbil. real. real or {} or {} himpunanhimpunan kosongkosongU U himpunanhimpunan semestasemesta, , himphimp. yang . yang memuatmemuat
semuasemua element yang element yang dibicarakandibicarakan. .
6ContohContoh HimpunanHimpunan A = A = empty set/null setempty set/null set A = {z}A = {z} Note: zNote: zA, but z A, but z {z}{z} A = {{b, c}, {c, x, d}}A = {{b, c}, {c, x, d}} A = {{x, y}} A = {{x, y}}
Note: {x, y} Note: {x, y} A, but {x, y} A, but {x, y} {{x, y}}{{x, y}} A = {x | P(x)}A = {x | P(x)}
set of all x such that P(x)set of all x such that P(x) A = {x | xA = {x | xNN x > 7} = {8, 9, 10, x > 7} = {8, 9, 10, }}
set builder notationset builder notation
7RelasiRelasi AntarAntar HimpunanHimpunan
1.1. HimpunanHimpunan yang yang SamaSama2.2. HimpunanHimpunan BagianBagian3.3. HimpunanHimpunan yang yang berpotonganberpotongan4.4. HimpunanHimpunan SalingSaling LepasLepas5.5. HimpunanHimpunan yang yang EkuivalenEkuivalen
8HimpunanHimpunan yang yang SamaSama( Set Equality)( Set Equality)
HimpHimp. A and B . A and B dikatakandikatakan samasama jikajika keduanyakeduanya memuatmemuat anggotaanggota--anggotaanggota yang yang tepattepat samasama. . A = B A = B { x | x { x | x A A x x B} B} atauatau A = B A = B A A B B B B AAContohContoh::
A = {9, 2, 7, A = {9, 2, 7, --3}, B = {7, 9, 3}, B = {7, 9, --3, 2} :3, 2} : A = BA = B
A = {dog, cat, horse}, A = {dog, cat, horse}, B = {cat, horse, squirrel, dog} :B = {cat, horse, squirrel, dog} : A A BB
A = {dog, cat, horse}, A = {dog, cat, horse}, B = {cat, horse, dog, dog} :B = {cat, horse, dog, dog} : A = BA = B
9HimpunanHimpunan BagianBagianA A BB A A adalahadalah himpunanhimpunan bagianbagian daridari BBA A B B jikajika setiapsetiap anggotaanggota A A jugajuga merupakanmerupakan
anggotaanggota B.B.
A A B B x (xx (xA A xxB)B)ContohContoh::
A = {3, 9}, B = {5, 9, 1, 3}, A A = {3, 9}, B = {5, 9, 1, 3}, A B ?B ? benarbenarA = {3, 3, 3, 9}, B = {5, 9, 1, 3}, A A = {3, 3, 3, 9}, B = {5, 9, 1, 3}, A B ?B ?
SalahSalah
benarbenar
A = {1, 2, 3}, B = {2, 3, 4}, A A = {1, 2, 3}, B = {2, 3, 4}, A B ?B ?
10
HimpunanHimpunan BagianBagianSifatSifat:: A = B A = B (A (A B) B) (B (B A) A) (A (A B) B) (B (B C) C) A A C C ((LihatLihat Venn Diagram)Venn Diagram)
UU
AABB CC
11
HimpunanHimpunan BagianBagianUseful rules:Useful rules: A for any set A A for any set A AA A for any set AA for any set A
Proper subsets (Proper subsets (HimpunanHimpunan BagianBagian SejatiSejati):):A A B B A is a proper subset of BA is a proper subset of BA A B B x (xx (xA A xxB) B) x (xx (xB B xxA)A)ororA A B B x (xx (xA A xxB) B) x (xx (xB B xxA) A)
12
DuaDua himpunanhimpunan A A dandan B B dikatakandikatakan berpotonganberpotongan, , ditulisditulisA)(B, A)(B, jikajika adaada anggotaanggota A yang A yang menjadimenjadi anggotaanggota B.B.
A)(B A)(B x (x x (x A A x x B)B)
HimpunanHimpunan A A dandan B B dikatakandikatakan salingsaling lepaslepas (A//B), (A//B), jikajikaA A , , B B , , x (x x (x A A x x B)B)HimpunanHimpunan A A dandan B yang B yang EkuivalenEkuivalen, A, AB, B, jikajika setiapsetiapanggotaanggota A A dapatdapat dipasangkandipasangkan ((dikorespondensikandikorespondensikan) ) satusatu--satusatu dengandengan anggotaanggota BB
BuatBuat ContohContoh MasingMasing--masingmasing!!!!!!
13
LatihanLatihan
1.1. BuktikanBuktikan jikajika M M , , makamaka M =M =..
2.2. A = {1,2,3,4}; B = A = {1,2,3,4}; B = himpunanhimpunanbilanganbilangan ganjilganjil. . BuktikanBuktikan A A B.B.
3.3. BuktikanBuktikan A A B, B B, B C C A A C.C.4.4. BuktikanBuktikan K K L, L L, L M, M M, M K K
K = M.K = M.
14
Interval Notation Interval Notation -- Special Special notation for subset of Rnotation for subset of R
[a,b] = {x [a,b] = {x R | a R | a x x b}b}(a,b) = {x (a,b) = {x R | a < x < b}R | a < x < b}[a,b) = {x [a,b) = {x R | a R | a x < b}x < b}(a,b] = {x (a,b] = {x R | a < x R | a < x b}b}How many elements in [0,1]? How many elements in [0,1]? In (0,1)? In (0,1)? In {0,1}In {0,1}
15
B (B complement)B (B complement) {x {x || xxU U xxB}B} Everything in the Universal set that is Everything in the Universal set that is
not in Bnot in B
A A B (A union B)B (A union B) {x {x || xxA A xxB}B} Like inclusive or, can be Like inclusive or, can be
in A or B or bothin A or B or both
OperasiOperasi HimpunanHimpunan
B
A B
16
A A B (A intersect B)B (A intersect B) {x {x || xxA A xxB}B} A and B are disjoint if A A and B are disjoint if A B = B =
A A -- B (A minus B or difference)B (A minus B or difference) {x {x || xxA A xxB}B} AA--B = AB = ABB
AAB (symmetric difference)B (symmetric difference) {x {x || xxA A xxB} = (AB} = (AB) B) -- ((AAB)B) We have overloaded the symbol We have overloaded the symbol . Used in . Used in
logic to mean exclusive or and in sets to logic to mean exclusive or and in sets to mean symmetric differencemean symmetric difference
17
ContohContohLet A = {nLet A = {n22 || nnP P nn4} = {1,4,9,16}4} = {1,4,9,16}Let B = {nLet B = {n44 || nnP P nn4} = {1,16,81,256}4} = {1,16,81,256}AAB = {1,4,9,16,81,256}B = {1,4,9,16,81,256}AAB = {1,16}B = {1,16}AA--B = {4,9}B = {4,9}BB--A = {81, 256}A = {81, 256}AAB = {4,9,81,256}B = {4,9,81,256}
18
Cardinality of SetsCardinality of SetsIf a set S contains n distinct elements, nIf a set S contains n distinct elements, nNN,,we call S a we call S a finite setfinite set with with cardinality ncardinality n..
Examples:Examples:A = {Mercedes, BMW, Porsche}, |A| = 3A = {Mercedes, BMW, Porsche}, |A| = 3
B = {1, {2, 3}, {4, 5}, 6}B = {1, {2, 3}, {4, 5}, 6} |B| = 4|B| = 4C = C = |C| = 0|C| = 0D = { xD = { xN N | x | x 7000 }7000 } |D| = 7001|D| = 7001E = { xE = { xN N | x | x 7000 }7000 } E is infinite!E is infinite!
19
The Power SetThe Power Set
P(A) P(A) power set of Apower set of AP(A) = {B | B P(A) = {B | B A} A} (contains all subsets of A)(contains all subsets of A)Examples:Examples:
A = {x, y, z}A = {x, y, z}P(A)P(A) = {= {, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}A = A = P(A) = {P(A) = {}}Note: |A| = 0, |P(A)| = 1Note: |A| = 0, |P(A)| = 1
20
The Power SetThe Power SetCardinality of power sets:Cardinality of power sets:| P(A) | = 2| P(A) | = 2|A||A| Imagine each element in A has an Imagine each element in A has an onon//offoff switchswitch Each possible switch configuration in A Each possible switch configuration in A
corresponds to one element in 2corresponds to one element in 2AA
zzzzzzzzzzzzzzzzzzyyyyyyyyyyyyyyyyyyxxxxxxxxxxxxxxxxxx8877665544332211AA
For 3 elements in A, there are For 3 elements in A, there are 22222 = 8 elements in P(A)2 = 8 elements in P(A)
21
Cartesian ProductCartesian ProductThe The ordered ordered nn--tupletuple (a(a11, a, a22, a, a33, , , a, ann) is an ) is an ordered collectionordered collection of objects.of objects.Two ordered Two ordered nn--tuplestuples (a(a11, a, a22, a, a33, , , a, ann) and ) and (b(b11, b, b22, b, b33, , , , bbnn) are equal if and only if they ) are equal if and only if they contain exactly the same elements contain exactly the same elements in the same in the same orderorder, i.e. , i.e. aaii = b= bii for 1 for 1 i i n.n.The The Cartesian productCartesian product of two sets is defined as:of two sets is defined as:AAB = {(a, b) | aB = {(a, b) | aA A bbB}B}Example:Example: A = {x, y}, B = {a, b, c}A = {x, y}, B = {a, b, c}AAB = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}B = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}
22
Cartesian ProductCartesian ProductThe The Cartesian productCartesian product of two sets is defined as: of two sets is defined as: AAB = {(a, b) | aB = {(a, b) | aA A bbB}B}Example:Example:A = {good, bad}, B = {student, A = {good, bad}, B = {student, profprof}}
AAB = {B = {(good, student),(good, student), (good, (good, profprof),), (bad, student),(bad, student), (bad, (bad, profprof))}}
(student, good),(student, good), ((profprof, good),, good), (student, bad),(student, bad), ((profprof, bad), bad)}}BBA = {A = {
23
Cartesian ProductCartesian ProductNote that:Note that: AA = = A = A = For nonFor non--empty sets A and B: Aempty sets A and B: AB B AAB B BBAA |A|AB| = |A|B| = |A||B||B|
The Cartesian product of The Cartesian product of two or more setstwo or more sets is is defined as:defined as:AA11AA22AAnn = {(a= {(a11, a, a22, , , a, ann) | ) | aaiiAA for 1 for 1 i i n}n}
24
Set OperationsSet Operations
Union: AUnion: AB = {x | xB = {x | xA A xxB}B}Example:Example: A = {a, b}, B = {b, c, d}A = {a, b}, B = {b, c, d}
AAB = {a, b, c, d} B = {a, b, c, d}
Intersection: AIntersection: AB = {x | xB = {x | xA A xxB}B}Example:Example: A = {a, b}, B = {b, c, d}A = {a, b}, B = {b, c, d}
AAB = {b}B = {b}
25
Set OperationsSet Operations
Two sets are called Two sets are called disjointdisjoint if their intersection if their intersection is empty, that is, they share no elements:is empty, that is, they share no elements:AAB = B = The The differencedifference between two sets A and B between two sets A and B contains exactly those elements of A that are contains exactly those elements of A that are not in B:not in B:AA--B = {x | xB = {x | xA A xxB}B}Example: Example: A = {a, b}, B = {b, c, d}, AA = {a, b}, B = {b, c, d}, A--B = {a}B = {a}
26
Set OperationsSet Operations
The The complementcomplement of a set A contains exactly of a set A contains exactly those elements under consideration that are not those elements under consideration that are not in A: in A: AAcc = U= U--AA
Example: Example: U = U = NN, B = {250, 251, 252, , B = {250, 251, 252, }}BBcc = {0, 1, 2, = {0, 1, 2, , 248, 249}, 248, 249}
27
Set OperationsSet OperationsTable 1 in Section 1.5 shows many useful equations.Table 1 in Section 1.5 shows many useful equations.How can we prove AHow can we prove A(B(BC) = (AC) = (AB)B)(A(AC)?C)?Method I:Method I:
xxAA(B(BC)C) xxA A xx(B(BC)C) xxA A (x(xB B xxC)C) (x(xA A xxB) B) (x(xA A xxC)C)
(distributive law for logical expressions)(distributive law for logical expressions) xx(A(AB) B) xx(A(AC)C) xx(A(AB)B)(A(AC)C)
28
Set OperationsSet OperationsMethod II: Method II: Membership tableMembership table1 means 1 means x is an element of this setx is an element of this set0 means 0 means x is not an element of this setx is not an element of this set
11111111111 1 11 1 111111111001 1 01 1 011111111001 0 11 0 111111111001 0 01 0 011111111110 1 10 1 100001100000 1 00 1 000110000000 0 10 0 100000000000 0 00 0 0
(A(AB) B) ((AAC)C)AACCAABBAA((BBC)C)BBCCA B CA B C
29
SifatSifat OperasiOperasi HimpunanHimpunan1.1. AsosiatifAsosiatif: (A: (AB) B) C =C = AA(B (B C)C)
(A(AB) B) C =C = AA(B(BC)C)2.2. IdempotenIdempoten: A: AA = A; AA = A; A A = AA = A3. 3. IdentitasIdentitas: A: AS = S; AS = S; A S = AS = A
AA = A; A= A; A = = 4.4. DistributifDistributif: A: A(B (B C) =C) = ((AAB) B) (A (A C)C)
A A (B (B C) =C) = ((AAB)B)(A (A C)C)5. 5. KomplementerKomplementer: A: AAA = S; A = S; A AA = = 6.6. De Morgan: (ADe Morgan: (AB)B) = A= ABB
(A(AB)B) = A= A BB7. 7. PenyerapanPenyerapan: A: A(A(AB) = AB) = A
AA(A(AB) =B) = AA
30
LatihanLatihan
1.1. BuktikanBuktikan AA(B(BC) = (AC) = (AB)B)(A (A C)C)2.2. BuktikanBuktikan AA--(B(BC) = (AC) = (A--B)B)(A(A--C)C)3.3. BilaBila A A B, B, buktikanbuktikan AAB = A B = A dandan
AAB = BB = B4.4. BuktikanBuktikan (A(AB) x C = (B) x C = (AxC)AxC)(BxC(BxC))