teori himpunan - tatagyes.files.wordpress.com · 2 teori himpunan • himpunan: kumpulan objek...

1

TeoriTeori HimpunanHimpunanBagianBagian IIIIII

2

TeoriTeori HimpunanHimpunan•• HimpunanHimpunan: : KumpulanKumpulan objekobjek ((konkritkonkrit

atauatau abstrakabstrak) yang ) yang mempunyaimempunyai syaratsyarattertentutertentu dandan jelasjelas, , bisanyabisanya dinyatakandinyatakandengandengan hurufhuruf besarbesar..

•• aa∈∈AA ““a a anggotaanggota daridari AA””

•• aa∉∉AA ““a a bukanbukan anggotaanggota daridari AA””•• A = {aA = {a11, a, a22, , ……, a, ann} } ““A A memuatmemuat…”…”

3

Cara Cara menyatakanmenyatakan himpunanhimpunan

a.a. MendaftarMendaftarb.b. MenyatakanMenyatakan sifatsifat--sifatsifat yang yang

dipenuhidipenuhi oleholeh anggotaanggota..c.c. NotasiNotasi pembentukpembentuk himpunanhimpunan

4

NotasiNotasi PembentukPembentuk HimpunanHimpunanFormat: Format: ““sedemikiansedemikian hinggahingga””

{[{[strukturstruktur keanggotaankeanggotaan] ] || [[syaratsyarat perluperlu untukuntuk menjadimenjadianggotaanggota]}]}

ContohContoh::Q = {m/n : m,n Q = {m/n : m,n ∈∈ Z, nZ, n≠≠0}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}

5

ContohContoh 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. .

6

ContohContoh HimpunanHimpunan•• A = A = ∅∅ ““empty set/null setempty set/null set””•• A = {z}A = {z} Note: zNote: z∈∈A, 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 | x∈∈NN ∧∧ x > 7} = {8, 9, 10, x > 7} = {8, 9, 10, ……}}

““set builder notationset builder notation””

7

RelasiRelasi 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

8

HimpunanHimpunan 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

9

HimpunanHimpunan BagianBagianA A ⊆⊆ BB ““A A adalahadalah himpunanhimpunan bagianbagian daridari BB””A A ⊆⊆ B B jikajika setiapsetiap anggotaanggota A A jugajuga merupakanmerupakan

anggotaanggota B.B.

A A ⊆⊆ B B ⇔⇔ ∀∀x (xx (x∈∈A A →→ xx∈∈B)B)

ContohContoh::

A = {3, 9}, B = {5, 9, 1, 3}, A A = {3, 9}, B = {5, 9, 1, 3}, A ⊆⊆ B ?B ? benarbenar

A = {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 B””A A ⊂⊂ B B ⇔⇔ ∀∀x (xx (x∈∈A A →→ xx∈∈B) B) ∧∧ ∃∃x (xx (x∈∈B B ∧∧ xx∉∉A)A)ororA A ⊂⊂ B B ⇔⇔ ∀∀x (xx (x∈∈A A →→ xx∈∈B) B) ∧∧ ¬∀¬∀x (xx (x∈∈B B →→ xx∈∈A) 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, A∼∼B, 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 || xx∈∈U U ∧∧ xx∉∉B}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 || xx∈∈A A ∨∨ xx∈∈B}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 || xx∈∈A A ∧∧ xx∈∈B}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 || xx∈∈A A ∧∧ xx∉∉B}B}•• AA--B = AB = A∩∩BB

AA⊕⊕B (symmetric difference)B (symmetric difference)•• {x {x || xx∈∈A A ⊕⊕ xx∈∈B} = (AB} = (A∪∪B) B) -- ((AA∩∩B)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 || nn∈∈P P ∧∧ nn≤≤4} = {1,4,9,16}4} = {1,4,9,16}Let B = {nLet B = {n44 || nn∈∈P P ∧∧ nn≤≤4} = {1,16,81,256}4} = {1,16,81,256}AA∪∪B = {1,4,9,16,81,256}B = {1,4,9,16,81,256}AA∩∩B = {1,16}B = {1,16}AA--B = {4,9}B = {4,9}BB--A = {81, 256}A = {81, 256}AA⊕⊕B = {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, n∈∈NN,,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 = { x∈∈N N | x | x ≤≤ 7000 }7000 } |D| = 7001|D| = 7001E = { xE = { x∈∈N 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 A””P(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 22××22××2 = 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:AA××B = {(a, b) | aB = {(a, b) | a∈∈A A ∧∧ bb∈∈B}B}Example:Example: A = {x, y}, B = {a, b, c}A = {x, y}, B = {a, b, c}AA××B = {(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: AA××B = {(a, b) | aB = {(a, b) | a∈∈A A ∧∧ bb∈∈B}B}Example:Example:A = {good, bad}, B = {student, A = {good, bad}, B = {student, profprof}}

AA××B = {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)}}BB××A = {A = {

23

Cartesian ProductCartesian ProductNote that:Note that:•• AA×∅×∅ = = ∅∅•• ∅×∅×A = A = ∅∅•• For nonFor non--empty sets A and B: Aempty sets A and B: A≠≠B B ⇔⇔ AA××B B ≠≠ BB××AA•• |A|A××B| = |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:AA11××AA22××……××AAnn = {(a= {(a11, a, a22, , ……, a, ann) | ) | aaii∈∈AA for 1 for 1 ≤≤ i i ≤≤ n}n}

24

Set OperationsSet Operations

Union: AUnion: A∪∪B = {x | xB = {x | x∈∈A A ∨∨ xx∈∈B}B}

Example:Example: A = {a, b}, B = {b, c, d}A = {a, b}, B = {b, c, d}AA∪∪B = {a, b, c, d} B = {a, b, c, d}

Intersection: AIntersection: A∩∩B = {x | xB = {x | x∈∈A A ∧∧ xx∈∈B}B}

Example:Example: A = {a, b}, B = {b, c, d}A = {a, b}, B = {b, c, d}AA∩∩B = {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:AA∩∩B = 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 | x∈∈A A ∧∧ xx∉∉B}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(B∩∩C) = (AC) = (A∪∪B)B)∩∩(A(A∪∪C)?C)?

Method I:Method I:xx∈∈AA∪∪(B(B∩∩C)C)

⇔⇔ xx∈∈A A ∨∨ xx∈∈(B(B∩∩C)C)⇔⇔ xx∈∈A A ∨∨ (x(x∈∈B B ∧∧ xx∈∈C)C)⇔⇔ (x(x∈∈A A ∨∨ xx∈∈B) B) ∧∧ (x(x∈∈A A ∨∨ xx∈∈C)C)

(distributive law for logical expressions)(distributive law for logical expressions)⇔⇔ xx∈∈(A(A∪∪B) B) ∧∧ xx∈∈(A(A∪∪C)C)⇔⇔ xx∈∈(A(A∪∪B)B)∩∩(A(A∪∪C)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 set””0 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(A∪∪B) B) ∩∩((AA∪∪C)C)AA∪∪CCAA∪∪BBAA∪∪((BB∩∩C)C)BB∩∩CCA B CA B C

29

SifatSifat OperasiOperasi HimpunanHimpunan1.1. AsosiatifAsosiatif: (A: (A∪∪B) B) ∪∪ C =C = AA∪∪(B (B ∪∪ C)C)

(A(A∩∩B) B) ∩∩C =C = AA∩∩(B(B∩∩C)C)

2.2. IdempotenIdempoten: A: A∪∪A = A; AA = A; A∩∩ A = AA = A

3. 3. IdentitasIdentitas: A: A∪∪S = S; AS = S; A∩∩ S = AS = AAA∪∪ ∅∅ = A; A= A; A∩∩ ∅∅ = = ∅∅

4.4. DistributifDistributif: A: A∪∪(B (B ∩∩ C) =C) = ((AA∪∪B) B) ∩∩(A (A ∪∪ C)C)A A ∩∩(B (B ∪∪ C) =C) = ((AA∩∩B)B)∪∪(A (A ∩∩ C)C)

5. 5. KomplementerKomplementer: A: A∪∪AA’’ = S; A = S; A ∩∩ AA’’ = = ∅∅

6.6. De Morgan: (ADe Morgan: (A∪∪B)B)’’ = A= A’’∩∩BB’’(A(A∩∩B)B)’’ = A= A’’ ∪∪ BB’’

7. 7. PenyerapanPenyerapan: A: A∪∪(A(A∩∩B) = AB) = AAA∩∩(A(A∪∪B) =B) = AA

30

LatihanLatihan

1.1. BuktikanBuktikan AA∩∩(B(B∪∪C) = (AC) = (A∩∩B)B)∪∪(A (A ∩∩ C)C)2.2. BuktikanBuktikan AA--(B(B∪∪C) = (AC) = (A--B)B)∩∩(A(A--C)C)3.3. BilaBila A A ⊂⊂ B, B, buktikanbuktikan AA∩∩B = A B = A dandan

AA∪∪B = BB = B4.4. BuktikanBuktikan (A(A∪∪B) x C = (B) x C = (AxC)AxC)∪∪(BxC(BxC))