2 Power set → P ( S ) adalah set dari semua subset dari set S = 2n elemen.
Resume Kuliah Matematika Diskrit Lanjut (EC6001)
10.
DR. Ir. Yoga Priyana
→ P ( S ) dari set {0,1, 2} adalah P ({0,1, 2} ) = {∅ , {0} ,{1} ,{ 2} ,{0,1} ,{0, 2} ,{1, 2} ,{ 0,1, 2}}
Contoh :
Tanggal 24 Agustus 2006 11. 1.
SET adalah kelompok obyek-obyek dengan sifat serupa (Cantour). Obyek = elemen = anggota
Ordered collection n-tuple atau kumpulan terurut. Posisi sangat menentukan dan tidak dapat
diubah. 2 (dua) n-tuple sama jika dan hanya jika setiap pasang elemen-elemennya sama.
→ Set mengandung (contain) elemen-elemen atau anggota-anggota. Contoh : V = {a , i , u, e , o} 12. 2.
2 (dua) set dikatakan sama jika dan hanya jika elemen-elemennya sama → {1, 3, 5} = {3, 5,1}
3.
Cara penulisan set → SET BUILDER (elemen-elemen dengan ciri-ciri sama (common)).
{
A = {1, 2} ; B = {a , b} →
}
A × B = {(1, a ) , (1, b ) , ( 2, a ) , ( 2, b )} .
dapat dipertukarkan namun urutannya dapat dipertukarkan
n-tuple →
Dua definisi :
13.
a∈ A
a ∉ A → a bukan elemen A
Empty Set = Null Set = ∅ , {
}.
{
Contoh : ∅ = x x > x
}
A⊆ B →
{(1, b ) , ( 2, b ) , (1, a ) , ( 2, a )}
Operasi Set a.
Union
(∪) → A ∪ B →
set
yang
berisi
semua
elemen
A
dan
B
atau
DAN
B
atau
{ x x ∈ A ∨ x ∈ B} U
x adalah bilangan positif. B
∅ ⊆ S atau empty set adalah subset dari setiap set.
6.
Isi elemen ini tidak
A1 × A2 × .................... × An
A
5.
dimana
B × A = {( a ,1) , ( a , 2 ) , ( b,1) , ( b, 2 )}
Penggambaran SET dalam bentuk grafik (Venn) → U = Semesta (Universe).
2
( a, b )
a ⊆ A, b ⊆ B
Contoh : A = x x ..................
4.
Product Cartesian dari A dan B → A × B ≠ B × A → set ordered pairs
set A adalah subset set B, jika dan hanya jika elemen set A adalah elemen set B.
Contoh : {1, 3, 5} ⊆ {1, 2, 3, 4, 5, 6}
b.
Intersection
(∩) → A ∩ B →
set
yang
berisi
elemen
A
{ x x ∈ A ∧ x ∈ B}
set A adalah proper subset dari set B karena A ≠ B (subset sejati).
7.
A⊂ B →
8.
S dikatakan finite set bila terdapat n elemen yang berbeda dimana n adalah integer tidak
negatif. n adalah kardinalitas dari S dinotasikan dengan S . c. 9.
Disjoint bila A ∩ B = ∅
S dikatakan infinite set bila ia not finite.
Arwin@23206008 Arwin@23206008
3
d.
4
{
}
Difference atau pengurangan → A − B = x x ∈ A ∧ x ∉ B
15.
Union dari sekumpulan set adalah set yang mengandung elemen-elemen yang merupakan
anggota dari sedikitnya
satu set
dalam
kumpulan set
tersebut.
Dinotasikan
dengan
n
A1 ∪ A2 ∪ ......... ∪ An = U Ai i =1
e.
{
}
Komplemen (bukan anggota dari) → A = x x ∉ A atau U − A
16.
Intersection dari sekumpulan set adalah set yang mengandung elemen-elemen yang merupakan
anggota
dari
semua
set
dalam
kumpulan
set
tersebut.
Dinotasikan
dengan
n
A1 ∩ A2 ∩ ......... ∩ An = I Ai i =1
f.
{
}
Symmetric Difference → A ⊕ B = x x ∈ A ∧ x ∉ B ∨ x ∉ A ∧ x ∈ B .
A = {1, 3, 5} ; B = {1, 2, 3} →
Contoh :
A ⊕ B = {5, 2}
17.
Representasi komputer Set adalah dalam bentuk urutan bilangan biner.
{1, 3, 5, 7, 9} = 1010101010 → 18.
Contoh :
1 merepresentasikan elemen yang ada dan 0 untuk yang sebaliknya.
Operasi set dalam representasi komputer.
Contoh :
{1, 3, 5, 7, 9} = 1010101010;
{1, 2, 3, 4, 5} = 1111100000 .
14.
a.
Union → 1010101010 ∨ 1111100000 = 1111101010 ↔ {1, 2, 3, 4, 5, 7, 9}
b.
Intersection → 1010101010 ∧ 1111100000 = 1010100000 ↔ {1, 3, 5}
Set Identities
Identitas
A∪∅ = A A∩U = A A∪U = U A∩∅ = ∅ A∪ A = A
A∩ A = A
( A) = A
A∪ B = B ∪ A A∩ B = B ∩ A A ∪ ( B ∪ C ) = ( A ∪ B) ∪ C A ∩ ( B ∩ C ) = ( A ∩ B) ∩ C A ∩ ( B ∪ C ) = ( A ∩ B) ∪ ( A ∩ C ) A ∪ ( B ∩ C ) = ( A ∪ B) ∩ ( A ∪ C ) A∪ B = A∩ B A∩ B = A∪ B
Nama 19. Hukum Identitas
Urutan proses Matematika Diskrit yakni Permutasi → Fungsi → Pigeon Nest →
Partial Order Set → Lattice Theory → Aljabar Boolean → Group → Coding Theory
Hukum Dominasi 20.
Permutasi dan kombinasi. Relasi set (antar set dan antar elemen di dalam set).
Hukum Idempotent 21.
Hukum Komplementasi
f ⊆ R ⊆ A× B
Hukum Komutatif Tanggal 31 Agustus 2006 Hukum Asosiatif 1.
Permutasi dan Kombinasi
Hukum Distributif
A = {1, 2, 3} , berapa banyak subset dengan 2 elemen yang dapat dibentuk ? Hukum De Morgan
Arwin@23206008
Arwin@23206008
5
→
6
A1 = {1, 2} = { 2,1} A2 = {1, 3} = {3,1}
C rn ⇒ Prn = C rn r !
A3 = { 2, 3} = {3, 2}
⇓ C rn =
Berapa barisan (sequence) dengan panhang 2 elemen yang dapat dibentuk ?
1 1 2 → 2 3
2 3 1 3 1
2.
n! Prn ( n − r ) ! n! = = r! r! r !( n − r ) !
Bilangan Bulat dan Pembagian •
Teorema 1 : m dan n bilangan bulat tak negatif dan n ≠ 0 , dapat ditulis m = qn + r untuk q dan r bilangan bulat tak negatif dan 0 ≤ r < n .
3 2 m adalah yang dibagi; n adalah pembagi; q adalah hasil bagi; r adalah sisa. Bila r = 0 maka dikatakan bahwa “ n membagi m ” dituliskan dengan n m . Jadi
A = n elemen, berapa barisan dengan panjang r dapat dibentuk dimana r < n ?
n m bila ada bilangan bulat a sehingga m = an . Bila r ≠ 0 maka dikatakan bahwa “ n tidak membagi m ” dituliskan dengan n | m .
•
Permutasi yang dapat dibuat dari anggota-anggota set dengan n elemen bila diambil sebanyak
Teorema 2 : ambil a , b dan c bilangan bulat.
9
Jika a b dan a c , maka a ( b + c )
9
Jika a b dan a c , dimana b > c , maka a ( b − c )
9
Jika a b atau a c , maka a bc
9
Jika a b dan b c maka a c
r adalah : P = n. ( n − 1) ................................ ( n − r + 1) n r
= n. ( n − 1) ................................ ( n − r + 1)( n − r ) ......1 = ( n − r ) ......1 sehingga Prn =
Bukti :
a c → bilangan bulat → k2 → c = ak2
n!
( n − r )!
Berapa banyak subset dengan n elemen dapat dibentuk dari set dengan n elemen ? Subset r elemen →
a b → bilangan bulat → k1 → b = ak1
Maka :
Prr = r !
Arwin@23206008
( b + c ) = ak1 + ak2 = a ( k1 + k2 )
→ a (b + c)
= ak
Arwin@23206008
7
•
8
Bilangan bulat positif P yang hanya dapat dibagi dengan 1 atau P (inclusive !) disebut
Contoh :
Bilangan Prima.
10,17, 21 → gcd (10,17 ) = 1 gcd (10, 21) = 1
m = 2 P − 1 bilangan Prima Mersenne ! ( P adalah bilangan prima dan m adalah bilangan
maka 10,17, 21 adalah “pairwise relatively prime”
gcd (17, 21) = 1 1 4 4 4 4 4 2 4 4 4 4 43
bulat positif)
cryptography(RSA)
Bagaimana dengan bilangan 11 ? bila P = 3 maka m = 23 − 1 = 7 → benar, bila P = 5 maka m = 25 − 1 = 31 → benar, lalu dimanakah posisi 11, 13, 17, 23 dan 29 ?
•
Algoritma Euclidean → sisa perhitungan dibagi oleh sisa berikutnya hingga diperoleh sisa = 0. Sisa terakhir sebelum sisa = 0 adalah gcd .
m = P P ................. P a1 1
an n
a2 2
dengan P1 P2 ......... Pn = bilangan prima dan a1a2 .........an = •
bilangan bulat tak positif.
min a ,b min a ,b gcd ( a , b ) = p1 ( 1 1 ) ................... pk ( k k ) .
Contoh : 12 = 22 .3 = 2.2.3 Contoh : •
gcd (190, 34 ) = 2
GCD (greatest common divisor)
min (1,1)
min (1,0 )
.5
= 2 .5 .17 .19 1
.17
min ( 0 ,1)
.19
min (1,0 )
0
Bilangan k terbesar ( d ) disebut pembagi persekutuan
190 : 2 = 95 : 5 = 19 → 190 = 2.5.19
terbesar. Contoh : gcd ( 24, 36 ) = 1, 2, 3, 4, 6, (12 ) → gcd = d
•
0
=2
Jika a dan b bilangan bulat positif; kalau k a dan k b dikatakan k adalah pembagi persekutuan (common divisor).
0
34 : 2 = 17 → 34 = 2.17
Teorema : 9
Jika d = gcd ( a , b ) , maka d = sa + tb untuk s dan t bilangan bulat.
9
Jika c adalah common divisor dari a dan b , maka c d .
•
LCM (least common multiple)
Jika a , b dan k bilangan bulat positif; bila a k dan b k , dikatakan bahwa k adalah “common multiple” dari a dan b , untuk bilangan k yang terkecil (sebut c ), maka
•
Bila a dan b bilangan bulat positif dan gcd ( a , b ) = 1 , maka a dan b dikatakan
k disebut lcm dari a dan b → lcm ( a , b ) = c .
“relatively prime” Contoh : 10 dan 17 → relatively prime; 10 dan 21 → relatively prime •
Bila a1a2 .........an bilangan-bilangan bulat positif, dikatakan “pairwise relatively prime”
(
)
bila gcd ai , a j = 1 untuk 1 ≤ i < j ≤ n .
•
Teorema : a dan b bilangan bulat positif; gcd ( a , b ) .lcm ( a , b ) = a .b
•
max a ,b max a ,b lcm ( a , b ) = p1 ( 1 1 ) ................... pk ( k k )
Contoh :
lcm (190, 34 ) = 2
max(1,1)
max (1, 0 )
.5
.17
max( 0 ,1)
.19
max(1,0 )
= 21.51.171.191 = 3.230
Arwin@23206008
Arwin@23206008
9
10 Maka joint A dan B ditulis A ∧ B adalah matriks C = cij dengan elemen-elemen
190 : 2 = 95 : 5 = 19 → 190 = 2.5.19 34 : 2 = 17 → 34 = 2.17
3.
seperti tersebut di atas. Contoh :
Matriks •
⎡1 ⎢0 A= ⎢ ⎢1 ⎢ ⎣0
Matriks Boolean adalah matriks dengan elemen “0” dan “1”.
⎡1 0 1 ⎤ A = ⎢⎢ 0 1 1 ⎥⎥ → ⎣⎢ 1 1 0 ⎥⎦
A = ( mxn ) B = ( nxp ) A = ( mxn ) B = ( mxn )
A. B = ( mxp ) A + B = ( mxn) )
•
Operasi-operasi pada Matriks Boolean 9
1 0⎤ 0 1 ⎥⎥ → 0 1⎥ ⎥ 1 0⎦
⎡1 ⎢0 A∧ B = C = ⎢ ⎢0 ⎢ ⎣0
0 0⎤ 0 1 ⎥⎥ 0 0⎥ ⎥ 0 0⎦
Boolean Product
Bila •
0 1⎤ ⎡1 ⎢1 1 1 ⎥⎥ ; B=⎢ ⎥ ⎢0 1 0 ⎥ ⎢ 0 0⎦ ⎣1
A = ( mxp ) ) = ⎡⎣ aij ⎤⎦ B = ( pxn) ) = ⎡⎣ bij ⎤⎦
(
) (
)
(
cij = ai1 ∧ b1 j ∨ ai 2 ∧ b2 j ........... ∨ aip ∧ b pj
)
Maka A e B = C = ⎡⎣ cij ⎤⎦ adalah matriks dengan elemen-elemen seperti tersebut di atas. “Joint of A and B”
⎡1 1 0⎤ ⎢1 0 1⎥ ⎥e Ae B = ⎢ ⎢0 0 1⎥ ⎢ ⎥ 1 1 0 1⎣ 4 2 4 3 ⎦
A = ( mxn) ) = ⎡⎣ aij ⎤⎦
⎪⎧ 1 bila aij = 1 atau bij = 1 cij = ⎨ B = ( mxn) ) = ⎡⎣ bij ⎤⎦ ⎪⎩ 0 bila aij dan bij = 0
T
Maka joint A dan B ditulis A ∨ B adalah matriks C = cij dengan elemen-elemen
( 4 x 3)
⎡1 1 0 1⎤ ⎢ 1 1 ⎥ 0 1⎥ = ⎢ ⎢0 1 ⎥ 1 0⎦ ⎢ 4 43 ⎣11 4412 ( 3 x 4)
⎡1 1 ⎢1 0 ⎢ ⎢⎣ 0 1 1 44 2
0 1⎤ 1 1 ⎥⎥ 1 0⎥ ⎥ 0 1⎦ 4 43
( 4 x 4)
seperti tersebut di atas. 4.
Relasi
Contoh : •
⎡1 ⎢0 A= ⎢ ⎢1 ⎢ ⎣0 9
0 1 1 0
1⎤ ⎡1 ⎢1 1 ⎥⎥ ; B=⎢ ⎢0 0⎥ ⎥ ⎢ 0⎦ ⎣1
1 0 0 1
0⎤ 1 ⎥⎥ → 1⎥ ⎥ 0⎦
⎡1 ⎢1 A∨ B = C = ⎢ ⎢1 ⎢ ⎣1
1 1 1 1
1⎤ 1 ⎥⎥ 1⎥ ⎥ 0⎦
Relasi R dari set A ke set B adalah subset A × B Contoh :
A = { Ahmad Albar, Sundari Sukoco, Erni Johan, Titik Puspa} B = {Rock, Keroncong, Pop}
“Meet of A and B” A = ( mxn) ) = ⎡⎣ aij ⎤⎦ B = ( mxn) ) = ⎡⎣ bij ⎤⎦
⎪⎧ 1 bila aij dan bij = 1 cij = ⎨ ⎩⎪ 0 bila sebaliknya
Arwin@23206008
Arwin@23206008
11
12
R = {(1, a ) , (1, c ) , ( 2, b ) , ( 2, c ) , ( 3, c ) , ( 4, a ) , ( 4, b ) , ( 4, c )} atau 1Ra; 1 Rb ⎧⎪(1, a ) , (1, b ) , (1, c ) , ( 2, a ) , ( 2, b ) , ( 2, c ) , ⎫⎪ A× B = ⎨ ⎬ ⎩⎪( 3, a ) , ( 3, b ) , ( 3, c ) , ( 4, a ) , ( 4, b ) , ( 4, c ) ⎭⎪ •
Set-set yang timbul dari Relasi →
R: A→ B ⇒
}
Relasi set → relative set of x . R ( x ) = y ∈ B x R y , contoh : R (1) = {a , b}
•
Bila A1 ⊆ A maka R adalah relative set of A .
R ( A1 ) = { y ∈ B x R y untuk ∀x ∈ A1}
R ⊆ A× B
9
Domain R adalah set dari elemen A yang mempunyai relasi ke B .
9
Range R adalah set dari elemen B yang mempunyai relasi dengan elemen A .
•
Contoh :
A = {1, 2, 3, 4} ; B = {a , b, c , d , e} dimana R = {(1, a ) , (1, b ) , ( 2, e ) , ( 3, a ) , ( 3, c )} maka Dom R = {1, 2, 3} ;
{
•
Contoh : A1 = {1, 3} ⇒
R ( A1 ) = {a , b, c}
Teorema : R : A → B;
A1 , A2 ⊆ A , maka :
o
Jika A1 ⊆ A2 maka R ( A1 ) ⊆ R ( A2 )
o
R ( A1 ∪ A2 ) = R ( A1 ) ∪ R ( A2 )
o
R ( A1 ∩ A2 ) = R ( A1 ) ∩ R ( A2 )
Range R = {a , b, c , e} Contoh :
•
Relasi pada set A adalah R : A → A ⇒
R ⊆ A× A
•
Relasi juga dapat direpresentasikan dengan Matriks Boolean atau Digraph.
A = {1, 2, 3, 4} ; B = {a , b, c , d , e}
a ⎡1 ⎢0 MR = ⎢ ⎢1 ⎢ ⎣0 •
b
c
d
R = {(1, a ) , (1, b ) , ( 2, e ) , ( 3, a ) , ( 3, c )}
e A1 = {1, 2} A2 = {1, 3} A3 = {1, 2, 3}
1 0 0 0⎤ 1 0 0 0 1 ⎥⎥ 2 0 1 0 0⎥ 3 ⎥ 0 0 0 0⎦ 4
Relasi pada set A →
didefinisikan sebagai R =
a ⎡1 ⎢0 MR = ⎢ ⎢0 ⎢ ⎣0
Maka :
A1 ∪ A2 = {1, 2, 3} = A3
M R square. Contoh : A = {a , b, c , d } . Relasi R : A → A
R ( A1 ) ∪ R ( A2 ) = {a , b, c , e} = R ( A3 ) A1 ∩ A2 = {1}
{( a, a ) , ( a , b ) , ( a , c ) , ( b, c ) , ( c, c ) , ( b, d ) , ( d , d )} , maka : b
c
R ( A1 ) ∩ R ( A2 ) = {a , b} R ( A1 ∩ A2 ) = {a , b}
d
1 1 0⎤ a 0 1 1 ⎥⎥ b 0 1 0⎥ c ⎥ 0 0 1⎦ d
Tanggal 7 September 2006
1. Matriks
R ( A1 ) = {a , b, e} R ( A2 ) = {a , b, c} R ( A3 ) = {a , b, c , e}
Relasi (continued ….)
Digraph
Arwin@23206008
Arwin@23206008
13
R: A→ B ⊆
14
A× B
5.
Path dalam Relasi dan Digraph
Set-set yang dengan relasi R adalah : •
Dom ( R ) = { x ∈ A x R y} → Dom ( R ) ⊆ A
R : A → A . Sebuah path dengan panjang n dalam R dari a ke b adalah sebuah
elemen hingga π = a1 x1 , x2 , ......................., xn −1 , b yang bermula dari a dan berakhir di b
Ran ( R ) = { y ∈ B x R y} → Ran ( R ) ⊆ B
sehingga a R x1 , x1 R x2 , .........................., xn− 2 R xn −1 , xn−1 R b 2.
R -relative set of x = { x ∈ B x R y}
Contoh :
A1 = { y ∈ B x R y untuk x ∈ A} dengan A1 ⊆ A
A = {1, 2, 3, 4, 5} ; R : A → A = {(1, 2 ) , ( 2, 2 ) , ( 2, 3) , ( 2, 4 ) , ( 2, 5 ) , ( 4, 3) , ( 5,1) , ( 5, 4 )}
A1 ⊆ A2 → R ( A1 ) ⊆ R ( A2 ) R ( A1 ∪ A2 ) ⊆ R ( A1 ) ∪ R ( A2 )
Matriks
Digraph
R ( A1 ∩ A2 ) ⊆ R ( A1 ) ∩ R ( A2 )
3.
⎡0 ⎢0 ⎢ M R = ⎢0 ⎢ ⎢0 ⎢⎣ 1
Relasi R : A → B dimana :
A = {a , b, c , d } ; R = {( a , a ) , ( b, b ) , ( a , c ) , ( b, c ) , ( c , c ) , ( b, d ) , ( d , d )} a
⎡1 ⎢0 MR = ⎢ ⎢0 ⎢ ⎣0
b
c
d
0 1 0⎤ a 1 1 1 ⎥⎥ b 0 1 0⎥ c ⎥ 0 0 1⎦ d
1 0 0 0⎤ 1 1 1 1 ⎥⎥ 0 0 0 0⎥ ⎥ 0 1 0 0⎥ 0 0 1 0 ⎦⎥
Maka : π 1 = 1, 2, 5, 4, 3 atau 1R 2, 2 R5, 5 R 4, 4 R3 = 4 , dapat disingkat dengan 1R 4 3
Matriks
•
R n adalah x R n y yang berarti terdapat path dengan panjang n dari x ke y .
•
R ∞ adalah connectivity relation. x R∞ y bermakan ada path dari x ke y .
Digraph Contoh : 4.
“Restriction of R to B ” adalah R ∩ ( B × B ) dengan R : A → A, B ⊆ A Contoh :
A = {1, 2, 3, 4, 5, 6} ; R : A → A = {(1, 2 ) , (1, 3) , ( 2, 2 ) , ( 2, 4 ) , ( 2, 5 ) , ( 3, 4 ) , ( 4, 5 ) , ( 5, 6 )}
A = {a , b, c , d , e , f } ; B = {a , b, c}
Digraph
Matriks
R = {( a , a ) , ( a , c ) , ( b, c ) , ( a , e ) , ( b, e ) , ( c , e )}
⎡0 ⎢0 ⎢ ⎢0 MR = ⎢ ⎢0 ⎢0 ⎢ ⎣0
Manakah “restriction of R to B ” ?
( B × B ) = {( a , a ) , ( a , b ) , ( a , c ) , ( b, a ) , ( b, b ) , ( b, c ) , ( c, a ) , ( c, b ) , ( c, c )}
0⎤ 0 ⎥⎥ 0⎥ ⎥ 0⎥ 0 0 0 0 1⎥ ⎥ 0 0 0 0 0⎦
1 1 0 0
1 0 0 0
0 1 1 0
0 1 0 1
maka :
R ∩ ( B × B ) = {( a , a ) , ( a , b ) , ( b, c )}
Arwin@23206008
Arwin@23206008
15
16
Tentukan R 2 pada A !
Contoh :
R 2 = {(1, 2 ) , (1, 4 ) , (1, 5 ) , ( 2, 2 ) , ( 2, 4 ) , ( 2, 5 ) , ( 2, 6 ) , ( 3, 5 ) , ( 4, 6 )}
A = {3, 2,1} . R relasi " ≤ " sehingga R = {(1,1) , (1, 2 ) , (1, 3) , ( 2, 2 ) , ( 2, 3) , ( 3, 3)} , maka :
Matriks
M R2
⎡0 ⎢0 ⎢ ⎢0 =⎢ ⎢0 ⎢0 ⎢ ⎣0
⎡1 1 1⎤ M R = ⎢⎢0 1 1⎥⎥ ⎢⎣0 0 1⎥⎦
0⎤ 1 ⎥⎥ 0⎥ ⎥ 1⎥ 0 0 0 0 0⎥ ⎥ 0 0 0 0 0⎦
1 1 0 0
0 0 0 0
1 1 0 0
1 1 1 0
•
Symmetric, Asymmetric dan Antisymmetric disebut “symmetric” bila a R b → b R a
R: A→ A
M R2 = M R e M R ⎡0 ⎢0 ⎢ ⎢0 =⎢ ⎢0 ⎢0 ⎢ ⎣0
1 1 0 0 0⎤ 1 0 1 1 0 ⎥⎥ 0 0 1 0 0⎥ ⎥e 0 0 0 1 0⎥ 0 0 0 0 1⎥ ⎥ 0 0 0 0 0⎦
disebut “asymmetric” bila a R b → b R a
⎡0 ⎢0 ⎢ ⎢0 ⎢ ⎢0 ⎢0 ⎢ ⎣0
1 1 0 0 0⎤ ⎡0 1 0 1 1 0 ⎥⎥ ⎢⎢ 0 0 0 1 0 0⎥ ⎢0 ⎥=⎢ 0 0 0 1 0⎥ ⎢0 0 0 0 0 1⎥ ⎢0 ⎥ ⎢ 0 0 0 0 0⎦ ⎣0
1 0 1 1 0⎤ 1 0 1 1 0 ⎥⎥ 0 0 0 1 0 ⎥ terbukti ! ⎥ 0 0 0 0 1⎥ 0 0 0 0 0⎥ ⎥ 0 0 0 0 0⎦
disebut “antisymmetric” bila a R b dan b R a
•
→ a=b
Transitive dan Intransitive
R: A→ A
adalah “transitive” bila a R b dan b R c
→ a Rc
Contoh : 6.
Digraph R
A = {1, 2, 3, 4} ; R = {(1, 2 ) , (1, 3) , ( 4, 2 )}
∞
⎡0 1 1 ⎧(1, 2 ) , (1, 3) , (1, 4 ) , (1, 5 ) , (1, 6 ) , ⎫ ⎢0 0 1 ⎪ ⎪ ⎢ , , , , , , , , 2 3 2 4 2 5 2 6 )( )( ) ⎪( ) ( ⎪ ⎢0 0 0 ⎪ ⎪ ∞ R = ⎨( 3, 4 ) , ( 3, 5 ) , ( 3, 6 ) , ⎬ → M R∞ = ⎢ ⎪ ⎪ ⎢0 0 0 ⎪( 4, 5 ) , ( 4, 6 ) , ⎪ ⎢0 0 0 ⎪( 5, 6 ) ⎪ ⎢ ⎩ ⎭ ⎣0 0 0 7.
1 1 1⎤ 1 1 1 ⎥⎥ 1 1 1⎥ ⎥ 0 1 1⎥ 0 0 1⎥ ⎥ 0 0 0⎦
1 0 0 0
1 0 0 1
0⎤ 0 ⎥⎥ 0⎥ ⎥ 0⎦
transitive ? Tidak !
A = ( a , b, c ) ; R = {( a , a ) , ( a , b ) , ( a , c ) , ( b, c ) , ( c , c )} ⎡1 1 1⎤ M R = ⎢⎢0 0 1⎥⎥ transitive ? Ya ! Buktikan ! ⎢⎣0 0 1⎥⎦
Sifat-sifat Relasi •
⎡0 ⎢0 MR = ⎢ ⎢0 ⎢ ⎣0
Reflexive dan Irreflexive
R : A → A disebut “reflexive” bila ( a , a ) ∈ R ∀a ∈ A → matriks diagonal = 1 disebut “irreflexive” bila ( a , a ) ∈R ∀a ∈ A → matriks diagonal = 0
Arwin@23206008
⎡1 1 1⎤ M R2 = M R → ⎢⎢0 0 1⎥⎥ e ⎢⎣0 0 1⎥⎦
a, a a, a a, b a, c
a, b → a, a a, c → a, c b, c → a , c c, c → a, c
b, c c , c → b, c
⎡1 1 1⎤ ⎡1 1 1⎤ ⎢ 0 0 1⎥ = ⎢0 0 1⎥ ⎢ ⎥ ⎢ ⎥ ⎢⎣ 0 0 1⎥⎦ ⎢⎣0 0 1⎥⎦
terbukti !
Arwin@23206008
17
8.
18
•
Relasi Ekivalen
Relasi yang reflexive, symmetric dan transitive
Complementary relation Bila R : A → B maka R : A → B dengan a R b jika a R b → b R a Contoh :
Contoh :
A = {1, 2, 3, 4} ; B = {a , b, c}
A = {1, 2, 3, 4} ; R : A → A = {(1,1) , (1, 2 ) , ( 2,1) , ( 2, 2 ) , ( 3, 4 ) , ( 4, 3) , ( 3, 3) , ( 4, 4 )}
R : A → B = {(1, a ) , (1, c ) , ( 2, b ) , ( 3, a )}
↓
R : A → B = {(1, b ) , ( 2, a ) , ( 2, c ) , ( 3, b ) , ( 3, c ) , ( 4, a ) , ( 4, b ) , ( 4, c )}
R ekivalen
9.
Partisi dan Relasi Ekivalen •
Sebuah Partisi adalah kumpulan dari subset-subset dari sebuah set yang masing-
masingnta tak kosong dan disjoint. •
Inversion
A1 = {a , b, c , d } A2 = {a , c , e , f , g , h}
R −1 : B → A dengan b R −1 a jika dan hanya jika a R b
A = {a , b, c , d , e , f , g , h} → A3 = {a , c , e , g}
Contoh : Lihat set di atas, maka R −1 : B → A =
A4 = {b, d } A5 = { f , h} partisi adalah vertex tidak bersentuhan. Maka Ρ = { A3 , A4 , A5 } adalah partisi dari A .
11.
Teorema-teorema •
•
Teorema 1 :
Ambil Ρ adalah partisi dari A . Definisi relasi R pada A adalah a R b jika dan hanya
Jika R ⊆ S , maka R −1 ⊆ S −1 Jika R ⊆ S , maka S ⊆ R
jika a dan b anggota dari partisi yang sama, maka R → ekivalen. Contoh : A = {1, 2, 3, 4} ; Ρ =
{( a ,1) , ( a , 3) , ( b, 2 ) , ( c,1)}
Jika ( R ∩ S ) , maka R −1 ∩ S −1 −1
Jika ( R ∪ S ) , maka R −1 ∪ S −1 −1
{{1, 2, 3} , {4}} maka
( ) Jika ( R ∪ S ) , maka R ∩ S Jika R ∩ S , maka R ∪ S
R = {(1,1) , (1, 2 ) , (1, 3) , ( 2,1) , ( 2, 2 ) , ( 2, 3) , ( 3,1) , ( 3, 2 ) , ( 3, 3) , ( 4, 4 )}
• 10.
Operasi pada Relasi
Teorema 2 :
R dan S , relasi pada A adalah Jika R reflexive, maka R −1 juga demikian
Karena Relasi adalah set dari pasangan berurut maka semua operasi set juga dapat diberlakukan
R reflexive jika dan hanya jika R irreflexive
pada relasi.
Bila R reflexive maka demikian juga R ∩ S dan R ∪ S
Arwin@23206008
Arwin@23206008
19
•
20
R ∪ Δ = {( a , a ) , ( a , b ) , ( a , c ) , ( b, b ) , ( b, c ) , ( c , c ) , ( c , d ) , ( d , d )} Teorema 3 :
R relasi pada A
R −1 = {( b, a ) , ( c , a ) , ( c , b ) , ( d , c )}
R simetri jika dan hanya jika R = R R antisimetri jika dan hanya jika R ∩ R ⊆ relasi satuan, relasi satuan. → M R = 1
2.
R asimetri jika dan hanya jika R ∩ R = ∅ •
Teorema 4 :
Teorema 5 :
Komposisi Relasi.
f : A → B dan g : B → C maka g D f : A → C
Contoh :
A = {1, 2, 3, 4} , relasi R pada A adalah R = {(1, 2 ) , (1,1) , (1, 3 ) , ( 2, 4 ) , ( 3, 2 )} dan S ,
R dan S relasi pada A
relasi pada A adalah S =
Jika R simetri, demkian pula dengan R −1 dan R
•
R ∪ R −1 = {( a , b ) , ( b, a ) , ( a , c ) , ( c , a ) , ( b, c ) , ( c , b ) , ( c , d ) , ( d , c )}
V adalah
{(1, 4 ) , (1, 3 ) , ( 2, 3 ) , ( 3,1) , ( 4,1)} , maka :
Jika R dan S simetri, demikian pula R ∩ S dan R ∪ S .
S D R = {(1, 3 ) , (1, 4 ) , (1,1) , ( 2,1) , ( 3, 3 )}
R dan S relasi pada A
dan
(R∩ S)
R D S = {(1, 2 ) , ( 2, 2 ) , ( 3, 2 ) , ( 3,1) , ( 3, 3 ) , ( 4, 2 ) , ( 4,1) , ( 4, 3 )}
2
……..
Tanggal 28 September 2006
1.
Closure.
Ada sebuah relasi R sebarang. Kita menginginkan suatu sifat tertentu pada R
tersebut. Jadi perlu kita tambahkan elemen-elemen (tuple-tuple) pada R tersebut sehingga sifat yang diinginkan terpenuhi. Relasi yang baru terbentuk dengan penambahan elemen tersebut, sebut R1 , ini disebut dengan CLOSURE dari R bila elemen yang kita tambahkan seminimal mungkin.
a.
A = {1, 2, 3} dan R = {(1,1) , (1, 2 ) , ( 2,1) , (1, 3 ) , ( 3,1)} . Agar R bersifat Reflexive
harus ditambahkan elemen-elemen seminimal mungkin yakni
( 2, 2 )
dan
( 3, 3 )
menjadi
R1 = {(1,1) , (1, 2 ) , ( 2,1) , ( 2, 2 ) , (1, 3 ) , ( 3,1) , ( 3, 3 )} sehingga berdampak pada R ⊆ R1 . R1 adalah reflexive closure untuk relasi R .
b.
Representasi matriks adalah sebagai berikut :
⎡0 ⎢0 MS = ⎢ ⎢1 ⎢ ⎣1
R pada set A dan R tidak reflexive. R1 = R ∪ Δ dimana Δ adalah relasi “=”. Agar
R1 symmetric maka R1 = R ∪ R −1 maka R1 adalah symmetric closure dari R . Contoh : A = {a , b, c , d } ; R = {( a , b ) , ( b, c ) , ( a , c ) , ( c , d )} ;
Δ = {( a , a ) , ( b, b ) , ( c , c ) , ( d , d )}
Arwin@23206008
M SDR
⎡1 ⎢1 =⎢ ⎢0 ⎢ ⎣0
0 1 1⎤ ⎡1 ⎢0 0 1 0 ⎥⎥ ; MR = ⎢ ⎢0 0 0 0⎥ ⎥ ⎢ 0 0 0⎦ ⎣0
1 1 0⎤ ⎡1 ⎢1 0 0 1 ⎥⎥ ; M R: S = ⎢ ⎢0 1 0 0⎥ ⎥ ⎢ 0 0 0⎦ ⎣0
0 1 1⎤ 0 0 0 ⎥⎥ sedangkan 0 1 0⎥ ⎥ 0 0 0⎦
0 1 1⎤ 0 0 0 ⎥⎥ maka M R: S = M S D R 0 1 0⎥ ⎥ 0 0 0⎦
Dengan cara yang sama akan ditemukan bahwa M S : R = M RD S
Arwin@23206008
21
⎡0 ⎢0 MR = ⎢ ⎢1 ⎢ ⎣1
3.
0 1 1⎤ ⎡1 ⎢0 0 1 0 ⎥⎥ ; MS = ⎢ ⎢0 0 0 0⎥ ⎥ ⎢ 0 0 0⎦ ⎣0
22
1 1 0⎤ ⎡0 ⎢0 0 0 1 ⎥⎥ ; M R: S = ⎢ ⎢1 1 0 0⎥ ⎥ ⎢ 0 0 0⎦ ⎣1
1 0 0⎤ 1 0 0 ⎥⎥ 1 1 0⎥ ⎥ 1 1 0⎦
Transitive closure R ∞ .
A = {1, 2, 3, 4} ; R = {(1, 2 ) , ( 2, 3 ) , ( 3, 4 ) , ( 2,1)} → (1,1) , (1, 3 ) , ( 2, 2 ) , ( 2, 4 ) R ∞ = {(1,1) , (1, 2 ) , (1, 3 ) , (1, 4 ) , ( 2,1) , ( 2, 2 ) , ( 2, 3 ) , ( 2, 4 ) , ( 3, 4 )} R ⊆ R∞
→
1 0 0⎤ ⎡1 0 1 0⎥⎥ ⎢⎢0 = 0 0 1 ⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
0 1 0⎤ 1 0 1 ⎥⎥ → M R4 = M R 2 0 0 0⎥ ⎥ 0 0 0⎦
M R5 = M R4 : R
⎡1 ⎢0 =⎢ ⎢0 ⎢ ⎣0
0 1 0⎤ ⎡0 1 0 1 ⎥⎥ ⎢⎢1 x 0 0 0⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
1 0 0⎤ ⎡0 0 1 0 ⎥⎥ ⎢⎢1 = 0 0 1⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
1 0 1⎤ 0 1 0 ⎥⎥ → M R5 = M R3 dst. 0 0 0⎥ ⎥ 0 0 0⎦
M R∞ = M R ∨ M R2 ∨ ................. akan diperoleh : ⎡0 ⎢1 ⎢ ⎢0 ⎢ ⎣0 4.
1 0 0⎤ 0 1 0 ⎥⎥ → 0 0 1⎥ ⎥ 0 0 0⎦
tidak transitive.
Agar bersifat transitive, lakukan perkalian
⎡0 ⎢1 =⎢ ⎢0 ⎢ ⎣0
1 0 0⎤ ⎡0 0 1 0 ⎥⎥ ⎢⎢1 x 0 0 1 ⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
R ∪ R 2 = M R2
⎡1 ⎢0 ∨ MR = ⎢ ⎢0 ⎢ ⎣0
M R3 = M R2 : R
⎡1 ⎢0 =⎢ ⎢0 ⎢ ⎣0
1 0 0 ⎤ ⎡1 0 1 0 ⎥⎥ ⎢⎢0 ∨ 0 0 1 ⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
0 1 0⎤ ⎡0 1 0 1 ⎥⎥ ⎢⎢1 ∨ 0 0 0⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
1 0 1⎤ ⎡1 ⎢1 0 1 0 ⎥⎥ ∨ .... = ⎢ ⎢0 0 0 0⎥ ⎥ ⎢ 0 0 0⎦ ⎣0
1 1 1⎤ 1 1 1 ⎥⎥ → transitive 0 0 1⎥ ⎥ 0 0 0⎦
Algoritma Warshall
a.
Langkah 1 – Wk diperoleh dari Wk −1 dengan mentransfer semua “1”.
b.
Langkah 2 – Daftar posisi-posisi dalam kolom k dari Wk −1 dimana entry-nya adalah
“1”, demikian pula dengan posisi-posisi baris k dari Wk −1 dimana entry-nya adalah “1”.
hingga level tertentu dan joint-kan dengan matriks pada level yang lebih rendah :
M R 2 = M R: R
1 0 1 ⎤ ⎡0 0 1 0 ⎥⎥ ⎢⎢1 x 0 0 0⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
transitive
Representasi graph untuk relasi R di atas adalah :
⎡0 ⎢1 MR = ⎢ ⎢0 ⎢ ⎣0
M R4 = M R 3 : R
⎡0 ⎢1 =⎢ ⎢0 ⎢ ⎣0
1 0 0 ⎤ ⎡1 0 1 0 ⎥⎥ ⎢⎢ 0 = 0 0 1⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
0 1 0⎤ ⎡0 1 0 1 ⎥⎥ ⎢⎢1 ∨ 0 0 0⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
0 1 0⎤ ⎡0 1 0 1 ⎥⎥ ⎢⎢1 x 0 0 0⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
0 1 0⎤ 1 0 1 ⎥⎥ 0 0 0⎥ ⎥ 0 0 0⎦
1 0 0 ⎤ ⎡1 0 1 0 ⎥⎥ ⎢⎢1 = 0 0 1 ⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
1 0 0⎤ ⎡0 0 1 0 ⎥⎥ ⎢⎢1 = 0 0 1 ⎥ ⎢0 ⎥ ⎢ 0 0 0⎦ ⎣0
c.
Langkah 3 – Letakkan “1” pada posisi
( j , i ) yang diperoleh pada langkah 2
Contoh : Matriks pada contoh sebelumnya.
↓ ⎡0 ⎢1 W0 = M R = ⎢ ⎢0 ⎢ ⎣0
1 1 0⎤ 1 1 1 ⎥⎥ 0 0 1⎥ ⎥ 0 0 0⎦
1 0 0⎤ ← 0 1 0 ⎥⎥ terdapat “1” pada baris 1 (2) dan kolom 1 (2). 0 0 1⎥ ⎥ 0 0 0⎦
↓ ⎡0 ⎢1 W1 = ⎢ ⎢0 ⎢ ⎣0
1 0 1⎤ 0 1 0 ⎥⎥ 0 0 0⎥ ⎥ 0 0 0⎦
Arwin@23206008
1 1 0 0
0 1 0 0
0⎤ 0 ⎥⎥ ← terdapat “1” pada baris 2 (1, 2, 3) dan kolom 2 (1, 2). 1⎥ ⎥ 0⎦
Arwin@23206008
23
24
↓
5.
Tanggal 5 Oktober 2006
⎡1 ⎢1 W2 = ⎢ ⎢0 ⎢ ⎣0
1 1 0⎤ terdapat “1” pada baris 3 (4) dan kolom 3 (1, 2). 1 1 0 ⎥⎥ 0 0 1⎥ ← ⎥ 0 0 0⎦
⎡1 ⎢1 W3 = ⎢ ⎢0 ⎢ ⎣0
1 1 0 0
W4 = W3
→
Fungsi.
1 1 0 0
1.
Prinsip Sangkar Merpati Contoh : Ambil n + 1 bilangan bulat sebarang maka sekurang-kurangnya ada 2 yang selisihnya
↓
dapat dibagi n .
1⎤ terdapat “1” pada kolom 4 (1, 2, 3). 1 ⎥⎥ 1⎥ ⎥ 0⎦ ←
Misal : n = 10
tidak ada perubahan lagi.
5
7
5
1
6
1
7
0
9
1
7
1
2
3
4
5
6
7
8
9
10
11
5
7
15
21
26
31
37
40
59
101 217
n + 1 bilangan; maka bilangan tersebut akan masuk pada salah satu dari n kelas kongruen.
f : A → B . Contoh : fungsi Nilai sebagai berikut :
a mod b →
sisa bila a dibagi b
a ≡ b mod n → a mod m = b mod n atau a − b dapat dibagi n - f tidak onto - surjection - f -nya surjective
Contoh : Angie mempunyai waktu 3 minggu untuk mempersiapkan diri guna mengikuti turnamen tennis. Dia memutuskan untuk berlatih tiap hari selama 3 minggu dengan sekurang-kurangnya memainkan 1 set dan sebanyak-banyaknya 3 set, tetapi secara keseluruhan dalam 3 minggu tersebut tidak lebih dari 36 set yang dimainkan. Tunjukkan bahwa terdapat periode (hari berturut-turut) dimana dia memainkan pasti 21 set.
- onto = surjective Jawab : Set latihan : a1 , a2 , ........................, a21 dimana 1 ≤ ai ≤ 3; 1 ≤ i ≤ 21 maka : -
one-to-one dan onto one-to-one correspondence bijective
A= B
Arwin@23206008
Hari ke
Jumlah Set
Total
∑ set
1st
2nd
1 2 3 4 5 6 7 8 9 10
||| | || ||| | | ||| || | ||
3 1 2 3 1 1 3 2 1 2
3 4 6 9 10 11 14 16 17 19
1 3 6 7 8 11 13 14 16
3 4 5 8 10 11 13
1 2 5 7 8 10
3 4 6 7 9
Arwin@23206008
25 11 12 13 14 15 16 17 18 19 20 21
1 1 2 1 3 2 1 1 2 1 2
| | || || | ||| || | || | ||
20 21 23 24 27 29 30 31 33 34 36
26 17 18 20 21
0 2 3 6 8 9 10 12 13 15
14 15 17 18 21
11 12 14 15 18 20 21
⎛1 1A = ⎜ ⎝1 ⎛1 P1 = ⎜ ⎝1
10 11 13 14 17 19 20 21
2 3⎞ ⎟ 2 3⎠ 2 3⎞ ⎟ 3 2⎠
⎛1 P2 = ⎜ ⎝2 ⎛1 P3 = ⎜ ⎝2
2 3⎞ ⎟ 1 3⎠ 2 3⎞ ⎟ 3 1⎠
⎛1 P4 = ⎜ ⎝3 ⎛1 P5 = ⎜ ⎝3
2 3⎞ ⎟ 1 2⎠ 2 3⎞ ⎟ 2 1⎠
P4 = {(1, 3 ) , ( 2,1) , ( 3, 2 )} → P4−1 = {( 3,1) , (1, 2 ) , ( 2, 3 )} = {(1, 2 ) , ( 2, 3 ) , ( 3,1)} ⎛1 2 3⎞ P4−1 = ⎜ ⎟ = P3 ⎝2 3 1⎠
Kesimpulan :
Permutation product-nya adalah :
Hari latihan adalah hari 1 s.d. 12, 2 s.d. 14, 4 s.d 15, 5 s.d 17 dan 6 s.d 18.
2.
⎛1 2 3⎞ ⎛ 1 2 3⎞ ⎛ 1 2 3⎞ P2 o P3 = ⎜ ⎟ o⎜ ⎟=⎜ ⎟ = P1 ⎝ 2 1 3⎠ ⎝ 2 3 1⎠ ⎝ 1 3 2⎠
Fungsi bijection : one-to-one dan onto, A = B .
f :A→B
(lakukan dari belakang ke depan atau P3 → P2 )
f : A → A . Permutasi dapat direpresentasikan dengan fungsi bijection. 3.
A = {a1 , a2 , .................., an } . r elemen dari A yang berbeda b1 , b2 , ..................., br Permutasi P : A → A adalah p ( b1 ) = b2 , p ( b2 ) = b3 , ............., p ( br −1 ) = b, p ( br ) = b1
p ( x ) = x untuk x ∈ A dan x ∉ {b1 , b2 , ..........., br } disebut dengan cyclic permutation atau cycle dan dinyatakan dengan ( b1 , b2 , ........, br )
{( a , c ) , ( b, a ) , ( c, b ) , ( d , d ) , ( e, e )}
{( a, a ) , ( b, b ) , ( c, c ) , ( d , d ) , ( e, e )} ⎛ a A = {a , b, c , d , e} → ⎜ ⎝ p (a )
b
c
d
p (b)
p (c )
p (d )
e ⎞ ⎟ p (e ) ⎠
b
c
d
b
c
d
e⎞ ⎟ e⎠
;
Contoh : A = {1, 2, 3} maka P33 =
⎛a P2 = ⎜ ⎝c
b
c
d
a
b d
⎛1 2 3 4 5⎞ P =⎜ ⎟ = (1, 3, 5 ) → cycle ⎝3 2 5 4 1⎠ Penulisan cycle tidak secara eksplisit menyatakan set-nya, kecuali bila :
(1, 3, 5 )
Maka
⎛a P1 = ⎜ ⎝a
Contoh : A = {1, 2, 3, 4, 5}
→
A = {1, 2, 3, 4, 5, 6, 7, 8, 9}
⎛1 2 3 4 5 6 7 8 9⎞ ⎜ ⎟ = (1, 3, 5 ) set-nya perlu dinyatakan. ⎝ 3 2 5 4 1 6 7 8 9⎠
e⎞ ⎟ e⎠
Contoh : A = {1, 2, 3, 4, 5, 6}
⎛1 2 3 4 5 6⎞ ⎟ → cycle dengan panjang 4 ⎝ 3 2 5 1 4 6⎠
( 4,1, 3, 5 ) = ⎜
3! 1.2.3 = = 6 dan diperoleh : ( 3 − 3 ) ! 0!
⎛1 2 3 4 5 6⎞ ⎟ → cycle dengan panjang 3 ⎝1 2 5 4 6 3⎠
( 5, 6, 3 ) = ⎜
Arwin@23206008
Arwin@23206008
27
28
⎛1 2 3 4 5 6⎞ ⎟ ⎝ 3 2 4 1 6 5⎠ ⎛1 2 3 4 5 6⎞ ( 5, 6, 3 ) o ( 4,1, 3, 5 ) = ⎜ ⎟ ⎝ 5 2 6 1 4 3⎠
( 4,1, 3, 5 ) o ( 5, 6, 3 ) = ⎜
Contoh : A = {1, 3, 4, 6,12} dan R : relasi dapat membagi, maka :
tidak sama.
⎪⎧(1,1) , (1, 3 ) , (1, 4 ) , (1, 6 ) , (1,12 ) , ( 3, 3 ) , ( 3, 6 ) , ( 3,12 ) , ⎪⎫ R=⎨ ⎬ ⎩⎪( 4, 4 ) , ( 4,12 ) , ( 6, 6 ) , ( 6,12 ) , (12,12 ) ⎭⎪
Pada umumnya c1 o c2 ≠ c2 o c1 .
4.
1 3 4 6 12 ⎡1 ⎢0 ⎢ M R = ⎢0 ⎢ ⎢0 ⎣⎢0
2 cycle dari set A disebut disjoint jika tidak ada elemen A yang muncul bersama pada kedua
cycle. Contoh : A = {1, 2, 3, 4, 5, 6}
⎛1 2 3 4 5 6⎞ ⎟ ; ⎝ 2 4 3 1 5 6⎠
( 4,1, 2 ) = ⎜
⎛1 2 3 4 5 6⎞ ⎟ ⎝ 1 2 5 4 6 3⎠
( 5, 6, 3 ) = ⎜
⎛1 2 3 4 5 6⎞ ⎟ ⎝ 2 4 5 1 6 3⎠ ⎛1 2 3 4 5 6⎞ ( 5, 6, 3 ) o ( 4,1, 2 ) = ⎜ ⎟ ⎝ 2 4 5 1 6 3⎠
1 1 1 1⎤ 1 0 1 1 ⎥⎥ 0 1 0 1⎥ ⎥ 0 0 1 1⎥ 0 0 0 1 ⎥⎦
1 3 4 → 6 12
perhatikan segitiga atas.
Elemen-elemennya reflexive,
antisymmetric dan transitive.
( 4,1, 2 ) o ( 5, 6, 3 ) = ⎜
7.
Relasi
c1 o c2 = c2 o c1 bila c1 dan c2 disjoint. A = {1, 2, 3} ; R = ≤ = {(1,1) , (1, 2 ) , (1, 3 ) , ( 2, 2 ) , ( 2, 3 ) , ( 3, 3 )} R = ≥ = {(1,1) , ( 2,1) , ( 2, 2 ) , ( 3,1) , ( 3, 2 ) , ( 3, 3 )}
5.
Cycle dengan panjang 2 disebut dengan transposisi. Contoh : A = {1, 2, 3, 4, 5, 6}
⎛1 2 3 4 5 6⎞ (1, 2 ) = ⎜ ⎟ ; ⎝ 2 1 3 4 5 6⎠
⎛1 2 3 4 5 6⎞ ( 2, 6 ) = ⎜ ⎟ ⎝1 6 3 4 5 2⎠
⎡ 1 1 1⎤ M R ≤ = ⎢⎢0 1 1⎥⎥ ⎣⎢0 0 1⎥⎦
Permutasi dapat ditentukan dari product of transposition sebagai berikut :
Contoh :
⎛1 2 3 4 5 6⎞ ⎟ ⎝1 2 5 4 6 3⎠ 1 2 3 4 5 6⎞ ⎛1 2 3 4 5 6⎞ ⎛ ( 3, 6 ) o ( 3, 5 ) = ⎜ ⎟ o⎜ ⎟ ⎝ 1 2 6 4 5 3⎠ ⎝1 2 5 4 3 6⎠ ⎛1 2 3 4 5 6⎞ =⎜ ⎟ ⎝1 2 5 4 6 3⎠
A = {1, 2, 3, 4,12} R = dapat membagi
( 3, 5, 6 ) = ⎜
;
⎧⎪(1,1) , (1, 2 ) , (1, 3 ) , (1, 4 ) , (1,12 ) , ( 2, 2 ) , ( 2, 4 ) , ⎫⎪ P = ( A,|) maka : R = ⎨ ⎬ ⎪⎩( 2,12 ) , ( 3, 3 ) , ( 3,12 ) , ( 4, 4 ) , ( 4,12 ) , (12,12 ) ⎪⎭
sama.
(1, 3, 5, 4 ) = (1, 3 ) o (1, 5 ) o (1, 4 ) 6.
⎡1 0 0 ⎤ M R≥ = ⎢⎢1 1 0 ⎥⎥ ⎣⎢1 1 1 ⎥⎦
→
Partially Ordered Set (Poset) Sebuah set A dan relasi R pada A yang mempunyai sifat reflexive, antisymmetric dan Hilangkan loop path
transitive disebut dengan Poset. Digraph
Arwin@23206008
Arwin@23206008
29
30
12
9.
Sebuah Poset sekurang-kurangnya mempunyai 1 maximal element dan 1 minimal element.
Sebuah elemen a ∈ A disebut greatest element jika x ⊆ a∀x ∈ A . Sebuah elemen a ∈ A disebut 4
3
least element jika a ⊆ x∀x ∈ A . Jadi sebuah Poset mempunyai sebanyak-banyaknya 1 greates element dan 1 least element. Contoh : A = {2, 4, 6, 8,12,18, 24, 36, 72} ;
→ 2
R = dapat membagi
1
Hilangkan transitive path
Hilangkan tanda panah dan jadilah
Elemen 2 dan 3 tidak comparable
Hash diagram yang menyatakan
P = ( A,|)
Bila setiap pasang elemen dalam suatu Poset adalah comparable, maka Poset tersebut disebut dengan linearly ordered atau linear order atau chain. Contoh : A = {1, 2, 3, 4,12}
10.
P = ( A, ≤ ) dan B ⊆ A . a ∈ A disebut upper bound dari B jika b ≤ a ∀b ∈ B . a ∈ A
disebut lower bound dari B jika a ≤ b ∀b ∈ B . Contoh : B = {24,12}
8.
Sebuah elemen a ∈ A disebut maximal element jika tidak ada elemen c ∈ A hingga a < c .
Sebuah elemen a ∈ A disebut minimal element jika tidak ada elemen c ∈ A hingga c < a . Contoh : A = {2, 3, 4, 6,12,18, 24, 36} ;
R = dapat dibagi
Poset tanpa greatest dan least elements.
Arwin@23206008
Least upper bound (lub) adalah 24 dan greates lower bound (glb) adalah 12.
Arwin@23206008
31
32
Tanggal 6 Oktober 2006
Tanggal 12 Oktober 2006
1.
1.
Perhatikan gambar berikut ini :
B⊆ A
Distributive Lattice, contoh :
Ambil elemen a , b, c
B1 = {a , b} ; B2 = {c , d , e}
a ∧ (b ∨ c ) = (a ∧ b) ∨ (a ∧ c )
glb B1 tidak ada, lub B1 = c glb B2 = c , lub B2 = h (?)
a∧I
=
a
=
∨
a
O
a
Sifat : distributif
B1 tidak mempunyai lower bound dan mempunyai upper bound c , d , e , f , g , h
Ambil elemen a , b, c
a ∧ (b ∨ c ) = (a ∧ b) ∨ (a ∧ c ) B2 mempunyai lower bound a , b, c dan
a∧I
mempunyai upper bound f , g , h
= ≠
a
∨
b
O
b
Sifat : tidak distributif
B⊆ A B = {6, 7,10}
Ambil elemen a , b, c
a ∧ (b ∨ c ) = (a ∧ b) ∨ (a ∧ c )
upper bound {10,11} maka lub 10 lower bound {4,1} maka glb 4
a∧I
=
a
≠
∨
O
O
O
Sifat : tidak distributif
2. 2.
Teorema : Sebuah lattice, L , non distributive jika dan hanya jika mengandung sublattice yang
isomorphic dengan salah satu dari lattice di atas, yakni :
Lattice Sebuah lattice adalah sebuah Poset dimana setiap subset dengan 2 elemen {a , b} , mempunyai “lub” dan “glb”, kita tuliskan LUB {a , b} dengan a ∨ b (joint) dan
I
GLB {a , b} dengan
a ∧ b (meet). Contoh : A = {1, 2, 4, 5,10, 20} ; R = dapat membagi maka :
⎧⎪(1,1) , (1, 2 ) , (1, 4 ) , (1, 5 ) , (1,10 ) , (1, 20 ) , ( 2, 2 ) , ( 2, 4 ) , ( 2,10 ) , ( 2, 20 ) , ⎫⎪ R=⎨ ⎬ ⎪⎩( 4, 4 ) , ( 4, 20 ) , ( 5, 5 ) , ( 5,10 ) , ( 5, 20 ) , (10,10 ) , (10, 20 ) , ( 20, 20 ) ⎪⎭
Arwin@23206008
a
b
c
O
Arwin@23206008
33 3.
34
Lattice hingga dengan greatest element I dan least element O dimana a ∈ L . Sebuah elemen
a ' ∈ L disebut komplemen a jika a ∨ a ' = I dan a ∧ a ' = O didapat pula bahwa O ' = I dan
I ' = O . Contoh :
4.
Finite Boolen Algebra.
(
Contoh : S = {a , b, c} ; P ( S ) , ⊆
)
(
dan T = {2, 3, 5} ; P (T ) , ⊆
maka : {a,b,c}
{2,3,5}
{b,c}
{3,5}
⇔
{5}
{2,5}
a' = c b' = c a∧c =O b∧c =O a∨c = I
)
isomorphic
{3} {2,3}
{c}
{a,c}
{b}
{a,b}
b∨c = I ∅
{2}
∅
{a}
f : S → T didefinisikan sebagai berikut :
({a}) = {2} ({b}) = {3} f ({c} ) = {5}
S = {a , b, c} ⎧⎪∅, {a} , {b} , {c} , {a , b} , ⎫⎪ P(S) = ⎨ ⎬ ⎩⎪{a , c} , {b, c} , {a , b, c} ⎭⎪
{a} ' = {b, c} = A {a} ∨ {b, c} = {a , b, c} {a} ∧ {b, c} = ∅
∅
15 5
10
3
6
2
1
f f
({∅}) = {∅} ({a , b, c}) = {2, 3, 5}
∅ = 000 {a , b} = 110 {a} = 100 {a , c} = 101 {b} = 010 {b, c} = 011 {c} = 001 {a , b, c} = 111
D20 = ({1, 2, 4, 5,10, 20} ,|)
30
f f
⎧1; if a ∈ S fA = ⎨ ⎩0; if a ∉ S
2∧5 =1 tidak komplemen 2 ∨ 5 = 10 4∧5 = O 4∨5 = I
({a , b}) = {2, 3} ({a , c}) = {2, 5} f ({b, c} ) = {3, 5}
f
f
4' = 5 5' = 4
5.
Lattice Bn . Jika x = a1 , a2 , ............, an dan y = b1 , b2 , ............., bn elemen dari Bn , maka :
a.
D30 = ({1, 2, 3, 5, 6,10,15, 30} ,|)
∅
a≤b
jika
dan
hanya
jika
ak ≤ bk
(sehingga
bilangan
0
dan
1)
untuk
k = 1, 2, ............., n
1' = 30 2' = 15 3' = 10
b.
x ∧ y = c1c2 .......cn dengan ck = min {ak , bk } . Contoh : 010 ∧ 101 = 000
c.
x ∨ y = c1c2 .......cn dengan ck = max {ak , bk } . Contoh : 010 ∨ 101 = 111
d.
x mempunyai sebuah komplemen x ' = y1 y2 ....... yn dengan yk = 0 bila xk = 1 dan
5' = 6
yk +1 = 1 bila xk = 0 . Contoh : 010' = 101 Bila lattice-nya distributif, maka setiap elemen mempunyai sebuah komplemen yang unik.
Arwin@23206008
Arwin@23206008
35
36 6.
Teorema : Ambil n = p1 p2 ........ pn , dengan pi bilangan-bilangan prima yang berbeda, maka
Dn adalah sebuah aljabar Boolean. Contoh :
2 | 210 6 | 210 210 = 2.3.5.7 → D210 0
1
( P ( S ) , ⊆) ≅ B
n
Contoh : D6 =
n=3
2
66 = 2.3.11 →
dengan S = n
30 | 210
3 | 210 10 | 210 70 | 210 dstnya 5 | 210 21 | 210 105 | 210 7 | 210 35 | 210 210 | 210
{1, 2, 3,11, 22, 33, 66}
({1, 2, 3, 6} ,|)
≅ isomorphic
≅ isomorphic
D66
D6
B2
7.
f : D6 → B2
B3
Teorema : Suatu rumus yang mendekatkan ∪, ∩ atau yang berlaku untuk subset-subset
sebarang dari sebuat set S akan tetap berlaku untuk elemen sebarang dari sebuah aljabar Boolean L
f (1) = 00
f ( 3 ) = 10
f ( 2 ) = 01
f ( 6 ) = 11
jika ∧ disubstitusikan untuk ∩ dan ∨ untuk ∪ .
Contoh : L aljabar Boolean sebarang dan X , Y dalam L maka :
D20 = ({1, 2, 4, 5,10, 20} ,|) diperoleh bahwa D20 ≠ 2 maka D20 bukan aljabar Boolean. n
D30 = ({1, 2, 3, 5, 6,10,15, 30} ,|) diperoleh bahwa D30 = 2n maka D30 aljabar Boolean, B3
( X ') ' = X ( X ∧ Y ) = X '∨ Y ' ( X ∨ Y ) = X '∧ Y '
dimana n = 3 . Bagaimana dengan A = {1, 2, 3, 6,12, 24, 36, 72} dimana P ( A,|) ?
( 010 ∧ 011) = ( 010 ) '∨ ( 01 = 101 ∨ 100 = 101
Setiap Dm mempunyai kemungkinan menjadi aljabar Boolean. Untuk melihat suatu set adalah aljabar Boolean, gunakan aturan di atas.
8.
Arwin@23206008
( L, ⊆ ) ⇔ ( P ( S ) , ⊆ ) adalah aljabar Boolean bila memiliki sifat-sifat 1 – 14 (hal. 219-220).
Arwin@23206008
37
38
Contoh :
c ' = a, b →
c∧a =O c∨a= I c∧b=O c∨b= I
B2 = B × B
B1
Karena c ' tidak unik yakni a , b maka lattice ini bukan aljabar Boolean.
9.
Contoh : Tunjukkan jika a bilangan bulat positif dan p 2 | n dengan p bilangan prima adalah
aljabar Boolean.
1=∅
6 = {2, 3}
35 = {5, 7}
B4 = B × B × B × B
2 = {2} 10 = {2, 5} 30 = {2, 3, 5} 210 = 2.3.5.7 →
3 = {3} 14 = {2, 7} 42 = {2, 3, 7}
210 = {2, 3, 5, 7}
5 = {5} 15 = {3, 5} 70 = {2, 5, 7} 7 = {7} 21 = {3, 7} 105 = {3, 5, 7} S = {2, 3,5,7} = P ( S )
10.
12.
Pelajari aljabar Boolean hal. 223-237.
13.
Group → Himpunan dan Operasi (harus punya sifat Tertutup)
Contoh : * = + , Z + = { x | x bilangan positif }
Jika | n → n = p 2Q bilangan bulat positif. p juga membagi n . bn bukan aljabar Boolean
3* 5 = 3 + 5 = 8 → 8∈ Z+
maka D elemen Dn . Contoh :
A = {0,1}
n = 40 → D40 = ? D40 = 23 .5
11.
∧ = meet
2 | 40 2 | 20
∧ 0 1 0 0 0
∨ 0 1 0 0 1
1
1
0 1
2 | 10 5
*
a b
c d
Karena ada pangkat, maka bukan aljabar Boolean.
a
a c
b d
b
b c
b a
Teorema : Untuk n ≥ 1, Bn = B × B × ................ × B sebanyak n kali merupakan product Poset.
A = {a , b, c , d }
c
c
d
b c
d
a a
b b
1 1
Bukan komutatif karena
a*b = c b*a = b
Arwin@23206008
*
a
b
c
a b
a c
c d
b d b a
d
c
b
b
a c
d
d
a
c
d
Komutatif karena symmetric pada diagonalnya
Arwin@23206008
39
40 Himpunan penjumlahan pada bilangan bulat positif
Z + = {0,1, 2,............................}
Tanggal 16 Nopember 2006
A* A → A 1.
(1 + 2 ) + 3 = 1 + ( 2 + 3 )
Group dan Semigroup. Misalkan suatu mesin penjual dengan pilihan koin 200 dan 500.
(
Permen karet - 400
(200, 200) → permen karet
A = {200,500}
Permen biasa - 700
(200, 500) → permen biasa
B = {karet , biasa , coklat }
Permen coklat - 1000
(500, 200) → permen biasa
+
contoh : 1 + 2 = 3 → 3 ∈ A
− asosiatif (tidak peduli urutan pengerjaannya)
)
Maka : Z ,* adalah semigroup.
2.
(500, 500) → permen coklat
e ∈ A sehingga e * x = x * e dimana x∀x ∈ A , maka e disebut elemen identitas (satuan).
0 ∈ Z + elemen identitas untuk operasi + Contoh :
f : A× A → B
0+5=5+0 5 + 6 = 6 + 5 − komutatif
Onto bila setiap elemen dalam Range tercover oleh elemen dari Domain
3.
y ∈ A dimana y * x = x * y = e maka y adalah invers x , dituliskan dengan x −1
4.
Flow chart group dan semigroup.
5.
Himpunan bilangan bulat Z dan operasi +. Buktikan bahwa ( Z , + ) adalah abelian group !
Definisi : Operasi biner → fungsi
Tabel multiplikasi menyatakan sebuah operasi biner
Koin yang dimasukkan
Barang yang dikeluarkan
f
200
500
(200, 200)
Karet
200
Karet
Biasa
(200, 500)
Biasa 500
Karet
Coklat
(500, 200)
Biasa
(500, 500)
Coklat
Himpunan dan sebuah operasi biner pada elemen-elemen himpunan tersebut sehingga sifat operasi tersebut tertutup (pada satu himpunan) dan asosiatif disebut semigroup → himpunan
( A,*)
2 → −2 − invers 0 → elemen identitas
Warna rambut : orang asing (sifat → tertutup, f : A × A → A )
Gelap Gelap
Terang Gelap
( 2 + ( −5 ) ) + 10 = 7 2 + ( ( −5 ) + 10 ) = 7
− asosiatif
Warna Gelap Terang
Gelap
Terang
( −5 ) + 7 = 7 + ( −5 )
− komutatif
Arwin@23206008
maka ( Z , + ) adalah abelian group.
Arwin@23206008
41
42
Sedangkan ( Z , • ) bukan abelian group.
*
a
b
a
a
b
b
b
a
8.
a*b = b*a
a * a = a; b * a = b a * b = b; a * a = a a * a −1 = a b * b −1 = a
⎛1 f2 = ⎜ ⎝2 ⎛1 f3 = ⎜ ⎝3
− komutatif
(a * a ) * b = a * (a * b)
Lihat dan pelajari contoh 18 hal. 312 dan contoh 6 hal. 331.
− asosiatif − identitas
2 3⎞ ⎟ 3 1⎠ 2 3⎞ ⎟ 1 2⎠
⎛1 2 3⎞ f1 = ⎜ ⎟ ⎝1 2 3⎠
− invers
⎛1 2 3⎞ f1 o f 2 = ⎜ ⎟ ⎝2 3 1⎠ Group permutasinya adalah
A = { f1 , f 2 , f 3 , g1 , g2 , g3 }
( A, o)
permutation group bersifat
- tertutup Elemen invers adalah dirinya sendiri a*a = a b*b = a 6.
A = {a1 , a2 ,....................., an } .
- asosiatif - elemen satuan
A * adalah himpunan dari string yang dibangun dari elemen-
elemen A sehingga A* = {a1 , a2 , a1a2 , a2 a2 } .
⎛1 2 3⎞ f2 = ⎜ ⎟ ⎝1 3 2⎠
- invers
Operasi • (penggandengan) “concatenation” pada
elemen-elemen A * menghasilkan :
a3 • a 2 a2 = a 3 a 2 a2
α = a1a2 a2 a2 β = a1a2 a3 a3 a1 γ = a1a2 a3 α gβ = a1a2 a2 a2 a1a2 a3 a3 a1
( A*,g)
adalah semigroup → free semigroup generated by A
λ gβ = β β gλ = β
dimana λ adalah string kosong
Maka A* = {λ , a1 , a2 ,........., a1a1 , a2 a2 ,............} dapat menjadi monoid namun tidak abelian karena α gβ ≠ β gα
7.
Himpunan A boleh mempunyai himpunan bagian ( B ⊆ A ) . Contoh : a , b ∈ B dan a * b ∈ B
maka ( B ,* ) semigroup karena mempunyai sifat asosiatif. Misal : A = {1, 2, 3,...........} dan B = {1,4} dimana * adalah perkalian biasa, bila ( A,* ) semigroup maka ( B ,* ) adalah subsemigroup dan monoid dimana e = 1 .
Arwin@23206008
Arwin@23206008
