pdm2005_himpunan
description
Transcript of pdm2005_himpunan
-
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))