resume kuliah matematika diskrit lanjutarwins2.tripod.com/ec6001_files/publikasi/mdlresume.pdfresume...
TRANSCRIPT
Arwin@23206008
Resume Kuliah Matematika Diskrit Lanjut (EC6001)
DR. Ir. Yoga Priyana
Tanggal 24 Agustus 2006
1. SET adalah kelompok obyek-obyek dengan sifat serupa (Cantour). Obyek = elemen = anggota
→ Set mengandung (contain) elemen-elemen atau anggota-anggota. Contoh : { }, , , ,V a i u e o=
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)).
Contoh : { }..................A x x=
4. Penggambaran SET dalam bentuk grafik (Venn) U→ = Semesta (Universe).
Dua definisi :
a A∈
a A∉ → a bukan elemen A
5. Empty Set = Null Set = { },∅ . Contoh : { }2x x x x∅ = > adalah bilangan positif.
S∅ ⊆ atau empty set adalah subset dari setiap set.
6. A B⊆ → 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, , , , , , ,⊆
7. A B⊂ → set A adalah proper subset dari set B karena A B≠ (subset sejati).
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 .
9. S dikatakan infinite set bila ia not finite.
Arwin@23206008
2
10. Power set ( )P S→ adalah set dari semua subset dari set S = 2n elemen. Contoh :
( )P S→ dari set { }0 1 2, , adalah { }( ) { } { } { } { } { } { } { }{ }0 1 2 0 1 2 0 1 0 2 1 2 0 1 2, , , , , , , , , , , , , ,P = ∅
11. 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.
12. Product Cartesian dari A dan B A B B A→ × ≠ × → set ordered pairs ( ),a b dimana
,a A b B⊆ ⊆
{ } { } ( ) ( ) ( ) ( ){ }1 2 1 1 2 2, ; , , , , , , , ,A B a b A B a b a b= = → × = . Isi elemen ini tidak
dapat dipertukarkan namun urutannya dapat dipertukarkan ( ) ( ) ( ) ( ){ }1 2 1 2, , , , , , ,b b a a
( ) ( ) ( ) ( ){ }1 2 1 2, , , , , , ,B A a a b b× =
n-tuple 1 2 .................... nA A A→ × × ×
13. Operasi Set
a. Union ( ) A B∪ → ∪ → set yang berisi semua elemen A dan B atau
{ }x x A x B∈ ∨ ∈
AU
B
b. Intersection ( ) A B∩ → ∩ → set yang berisi elemen A DAN B atau
{ }x x A x B∈ ∧ ∈
c. Disjoint bila A B∩ = ∅
Arwin@23206008
3
d. Difference atau pengurangan { }A B x x A x B→ − = ∈ ∧ ∉
e. Komplemen (bukan anggota dari) { }A x x A→ = ∉ atau U A−
f. Symmetric Difference { }A B x x A x B x A x B→ ⊕ = ∈ ∧ ∉ ∨ ∉ ∧ ∈ . Contoh :
{ } { } { }1 3 5 1 2 3 5 2, , ; , , ,A B A B= = → ⊕ =
14. Set Identities
Identitas Nama
A A
A U A
∪∅ =∩ =
Hukum Identitas
A U U
A
∪ =∩∅ = ∅
Hukum Dominasi
A A A
A A A
∪ =∩ =
Hukum Idempotent
( )A A= Hukum Komplementasi
A B B A
A B B A
∪ = ∪∩ = ∩
Hukum Komutatif
( ) ( )( ) ( )
A B C A B C
A B C A B C
∪ ∪ = ∪ ∪
∩ ∩ = ∩ ∩ Hukum Asosiatif
( ) ( ) ( )( ) ( ) ( )
A B C A B A C
A B C A B A C
∩ ∪ = ∩ ∪ ∩
∪ ∩ = ∪ ∩ ∪ Hukum Distributif
A B A B
A B A B
∪ = ∩
∩ = ∪ Hukum De Morgan
Arwin@23206008
4
15. Union dari sekumpulan set adalah set yang mengandung elemen-elemen yang merupakan
anggota dari sedikitnya satu set dalam kumpulan set tersebut. Dinotasikan dengan
1 21
.........n
n ii
A A A A=
∪ ∪ ∪ = U
16. Intersection dari sekumpulan set adalah set yang mengandung elemen-elemen yang merupakan
anggota dari semua set dalam kumpulan set tersebut. Dinotasikan dengan
1 21
.........n
n ii
A A A A=
∩ ∩ ∩ = I
17. Representasi komputer Set adalah dalam bentuk urutan bilangan biner. Contoh :
{ }1 3 5 7 9 1010101010, , , , = → 1 merepresentasikan elemen yang ada dan 0 untuk yang sebaliknya.
18. Operasi set dalam representasi komputer. Contoh : { }1 3 5 7 9 1010101010, , , , ;=
{ }1 2 3 4 5 1111100000, , , , = .
a. Union { }1010101010 1111100000 1111101010 1 2 3 4 5 7 9, , , , , ,→ ∨ = ↔
b. Intersection { }1010101010 1111100000 1010100000 1 3 5, ,→ ∧ = ↔
19. Urutan proses Matematika Diskrit yakni Permutasi → Fungsi → Pigeon Nest →
Partial Order Set → Lattice Theory → Aljabar Boolean → Group → Coding Theory
20. Permutasi dan kombinasi. Relasi set (antar set dan antar elemen di dalam set).
21. f R A B⊆ ⊆ ×
Tanggal 31 Agustus 2006
1. Permutasi dan Kombinasi
{ }1 2 3, ,A = , berapa banyak subset dengan 2 elemen yang dapat dibentuk ?
Arwin@23206008
5
{ } { }{ } { }{ } { }
1
2
3
1 2 2 1
1 3 3 1
2 3 3 2
, ,
, ,
, ,
A
A
A
→ = =
= =
= =
Berapa barisan (sequence) dengan panhang 2 elemen yang dapat dibentuk ?
1 2
1 3
2 1
2 3
3 1
3 2
→
A n= elemen, berapa barisan dengan panjang r dapat dibentuk dimana r n< ?
Permutasi yang dapat dibuat dari anggota-anggota set dengan n elemen bila diambil sebanyak
r adalah :
( ) ( )( ) ( ) ( )
( )
1 1
1 1 1
1
. ................................
. ................................ ......
......
nrP n n n r
n n n r n r
n r
= − − +
= − − + −
= −
sehingga ( )
!
!n
r
nP
n r=
−
Berapa banyak subset dengan n elemen dapat dibentuk dari set dengan n elemen ?
Subset r elemen !rrP r→ =
Arwin@23206008
6
( )( )
!
!! !
! ! ! !
n n nr r r
nn rr
C P C r
nn rP n
Cr r r n r
⇒ =
⇓
−= = =
−
2. Bilangan Bulat dan Pembagian
• Teorema 1 : m dan n bilangan bulat tak negatif dan 0n ≠ , dapat ditulis m qn r= +
untuk q dan r bilangan bulat tak negatif dan 0 r n≤ < .
m adalah yang dibagi; n adalah pembagi; q adalah hasil bagi; r adalah sisa.
Bila 0r = maka dikatakan bahwa “ n membagi m ” dituliskan dengan n m . Jadi
n m bila ada bilangan bulat a sehingga m an= .
Bila 0r ≠ maka dikatakan bahwa “ n tidak membagi m ” dituliskan dengan |n m .
• Teorema 2 : ambil ,a b dan c bilangan bulat.
Jika a b dan a c , maka ( )a b c+
Jika a b dan a c , dimana b c> , maka ( )a b c−
Jika a b atau a c , maka a bc
Jika a b dan b c maka a c
Bukti : a b → bilangan bulat 1 1k b ak→ → =
a c → bilangan bulat 2 2k c ak→ → =
Maka :
( )( ) ( )1 2
1 2
b c ak ak
a k k a b c
ak
+ = +
= + → +
=
Arwin@23206008
7
• Bilangan bulat positif P yang hanya dapat dibagi dengan 1 atau P (inclusive !) disebut
Bilangan Prima.
2 1Pm = − bilangan Prima Mersenne ! ( P adalah bilangan prima dan m adalah bilangan
bulat positif)
Bagaimana dengan bilangan 11 ? bila 3P = maka 32 1 7m = − = → benar, bila 5P =
maka 52 1 31m = − = → benar, lalu dimanakah posisi 11, 13, 17, 23 dan 29 ?
1 21 2 ................. naa a
nm P P P= dengan 1 2 ......... nP P P = bilangan prima dan 1 2 ......... na a a =
bilangan bulat tak positif.
Contoh : 212 2 3 2 2 3. . .= =
• GCD (greatest common divisor)
Jika a dan b bilangan bulat positif; kalau k a dan k b dikatakan k adalah pembagi
persekutuan (common divisor). Bilangan k terbesar ( d ) disebut pembagi persekutuan
terbesar. Contoh : ( ) ( )24 36 1 2 3 4 6 12gcd , , , , , , gcd d= → =
• Teorema :
Jika ( )gcd ,d a b= , maka d sa tb= + untuk s dan t bilangan bulat.
Jika c adalah common divisor dari a dan b , maka c d .
• Bila a dan b bilangan bulat positif dan ( ) 1gcd ,a b = , maka a dan b dikatakan
“relatively prime”
Contoh : 10 dan 17 → relatively prime; 10 dan 21 → relatively prime
• Bila 1 2 ......... na a a bilangan-bilangan bulat positif, dikatakan “pairwise relatively prime”
bila ( ) 1gcd ,i ja a = untuk 1 i j n≤ < ≤ .
Arwin@23206008
8
Contoh :
( )( )( )
10 17 21 10 17 1
10 21 1
17 21 1
cryptography(RSA)
, , gcd ,
gcd ,
gcd ,
→ =
=
=1 4 4 4 4 4 2 4 4 4 4 43
maka 10 17 21, , adalah “pairwise relatively prime”
• Algoritma Euclidean → sisa perhitungan dibagi oleh sisa berikutnya hingga diperoleh
sisa = 0. Sisa terakhir sebelum sisa = 0 adalah gcd .
• ( ) ( ) ( )1 1
1min ,min ,gcd , ................... k ka ba bka b p p= .
Contoh :
( ) ( ) ( ) ( ) ( )1 1 1 0 0 1 1 0
1 0 0 0
190 34 2 5 17 19
2 5 17 19
2
min , min , min , min ,gcd , . . .
. . .
=
==
190 2 95 5 19 190 2 5 19
34 2 17 34 2 17
: : . .
: .
= = → == → =
• 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
k disebut lcm dari a dan b ( ),lcm a b c→ = .
• Teorema : a dan b bilangan bulat positif; ( ) ( )gcd , . , .a b lcm a b a b=
• ( ) ( ) ( )1 1
1max ,max ,, ................... k ka ba bklcm a b p p=
Contoh :
( ) ( ) ( ) ( ) ( )1 1 1 0 0 1 1 0
1 1 1 1
190 34 2 5 17 19
2 5 17 19
3 230
max , max , max , max ,, . . .
. . .
.
lcm =
==
Arwin@23206008
9
190 2 95 5 19 190 2 5 19
34 2 17 34 2 17
: : . .
: .
= = → == → =
3. Matriks
• Matriks Boolean adalah matriks dengan elemen “0” dan “1”.
( )( )( )( )
( )( )
1 0 1
0 1 1
1 1 0
.
)
A mxn
B nxp A B mxpA
A mxn A B mxn
B mxn
=⎡ ⎤
= =⎢ ⎥= →⎢ ⎥ = + =⎢ ⎥⎣ ⎦ =
• Operasi-operasi pada Matriks Boolean
“Joint of A and B”
( )( )
1 1 1
0 0
bila atau
bila dan
)
)
ij ij ij
ijij ijij
A mxn a a bc
a bB mxn b
⎡ ⎤= = = =⎧⎣ ⎦ ⎪= ⎨ =⎡ ⎤= = ⎪⎩⎣ ⎦
Maka joint A dan B ditulis A B∨ adalah matriks ijC c= dengan elemen-elemen
seperti tersebut di atas.
Contoh :
1 0 1 1 1 0 1 1 1
0 1 1 1 0 1 1 1 1
1 1 0 0 0 1 1 1 1
0 0 0 1 1 0 1 1 0
;A B A B C
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = → ∨ = =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
“Meet of A and B”
( )( )
1 1
0
bila dan
bila sebaliknya
)
)
ij ij ij
ij
ij
A mxn a a bc
B mxn b
⎡ ⎤= = =⎧⎣ ⎦ ⎪= ⎨⎡ ⎤ ⎪= = ⎩⎣ ⎦
Arwin@23206008
10
Maka joint A dan B ditulis A B∧ adalah matriks ijC c= dengan elemen-elemen
seperti tersebut di atas.
Contoh :
1 0 1 1 1 0 1 0 0
0 1 1 1 0 1 0 0 1
1 1 0 0 0 1 0 0 0
0 0 0 1 1 0 0 0 0
;A B A B C
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = → ∧ = =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
• Boolean Product
Bila ( )( )
( ) ( ) ( )1 1 2 2
)...........
)
ij
ij i j i j ip pj
ij
A mxp ac a b a b a b
B pxn b
⎡ ⎤= = ⎣ ⎦ = ∧ ∨ ∧ ∨ ∧⎡ ⎤= = ⎣ ⎦
Maka ijA B C c⎡ ⎤= = ⎣ ⎦e adalah matriks dengan elemen-elemen seperti tersebut di atas.
( )( )
( )3 4
4 3 4 4
1 1 0 1 1 0 11 1 0 1
1 0 1 1 1 1 11 0 0 1
0 0 1 0 1 1 00 1 1 0
1 1 0 1 1 0 1
T
xx x
A B
⎡ ⎤ ⎡ ⎤⎡ ⎤⎢ ⎥ ⎢ ⎥⎢ ⎥⎢ ⎥ ⎢ ⎥= =⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦
⎣ ⎦ ⎣ ⎦
e e
1 44 2 4 431 4 2 4 3 1 44 2 4 43
4. Relasi
• Relasi R dari set A ke set B adalah subset A B×
Contoh : { }{ }Ahmad Albar, Sundari Sukoco, Erni Johan, Titik Puspa
Rock, Keroncong, Pop
A
B
=
=
Arwin@23206008
11
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1 1 2 2 3 4 4 4, , , , , , , , , , , , , , ,R a c b c c a b c= atau 1 1;Ra Rb
( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )1 1 1 2 2 2
3 3 3 4 4 4
, , , , , , , , , , , ,
, , , , , , , , , , ,
a b c a b cA B
a b c a b c
⎧ ⎫⎪ ⎪× = ⎨ ⎬⎪ ⎪⎩ ⎭
• Set-set yang timbul dari Relasi :R A B R A B→ → ⇒ ⊆ ×
Domain R adalah set dari elemen A yang mempunyai relasi ke B .
Range R adalah set dari elemen B yang mempunyai relasi dengan elemen A .
Contoh :
{ } { }1 2 3 4, , , ; , , , ,A B a b c d e= = dimana ( ) ( ) ( ) ( ) ( ){ }1 1 2 3 3, , , , , , , , ,R a b e a c=
maka { } { }1 2 3, , ; , , ,Dom R Range R a b c e= =
• Relasi pada set A adalah :R A A R A A→ ⇒ ⊆ ×
• Relasi juga dapat direpresentasikan dengan Matriks Boolean atau Digraph.
1 1 0 0 0 1
0 0 0 0 1 2
1 0 1 0 0 3
0 0 0 0 0 4
R
a b c d e
M
⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦
• Relasi pada set RA M→ square. Contoh : { }, , ,A a b c d= . Relasi :R A A→
didefinisikan sebagai ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }, , , , , , , , , , , , ,R a a a b a c b c c c b d d d= , maka :
1 1 1 0
0 0 1 1
0 0 1 0
0 0 0 1
R
a b c d
a
bM
c
d
⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦
Matriks
Digraph
Arwin@23206008
12
• Relasi set → relative set of x . ( ) { }R x y B x R y= ∈ , contoh : ( ) { }1 ,R a b=
• Bila 1A A⊆ maka R adalah relative set of A .
( ) { }1 1untukR A y B x R y x A= ∈ ∀ ∈
Contoh : { } ( ) { }1 11 3, , ,A R A a b c= ⇒ =
• Teorema : 1 2: ; ,R A B A A A→ ⊆ , maka :
o Jika 1 2A A⊆ maka ( ) ( )1 2R A R A⊆
o ( ) ( ) ( )1 2 1 2R A A R A R A∪ = ∪
o ( ) ( ) ( )1 2 1 2R A A R A R A∩ = ∩
Contoh :
{ } { }( ) ( ) ( ) ( ) ( ){ }
{ } ( ) { }{ } ( ) { }{ } ( ) { }
1 1
2 2
3 3
1 2 3 4
1 1 2 3 3
1 2
1 3
1 2 3
, , , ; , , , ,
, , , , , , , , ,
, , ,
, , ,
, , , , ,
A B a b c d e
R a b e a c
A R A a b e
A R A a b c
A R A a b c e
= =
=
= == == =
Maka :
{ }( ) ( ) { } ( )
{ }( ) ( ) { }( ) { }
1 2 3
1 2 3
1 2
1 2
1 2
1 2 3
1
, ,
, , ,
,
,
A A A
R A R A a b c e R A
A A
R A R A a b
R A A a b
∪ = =
∪ = =
∩ =
∩ =
∩ =
Tanggal 7 September 2006
1. Relasi (continued ….)
Arwin@23206008
13
:R A B A B→ ⊆ ×
Set-set yang dengan relasi R adalah :
( ) { } ( )( ) { } ( )
Dom R x A x R y Dom R A
Ran R y B x R y Ran R B
= ∈ → ⊆
= ∈ → ⊆
2. R -relative set of { }x x B x R y= ∈
{ }1A y B x R y untuk x A= ∈ ∈ dengan 1A A⊆
( ) ( )( ) ( ) ( )( ) ( ) ( )
1 2 1 2
1 2 1 2
1 2 1 2
A A R A R A
R A A R A R A
R A A R A R A
⊆ → ⊆
∪ ⊆ ∪
∩ ⊆ ∩
3. 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= =
1 0 1 0
0 1 1 1
0 0 1 0
0 0 0 1
R
a b c d
a
bM
c
d
⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦
Matriks
Digraph
4. “Restriction of R to B ” adalah ( )R B B∩ × dengan : ,R A A B A→ ⊆
Contoh : { } { }( ) ( ) ( ) ( ) ( ) ( ){ }
, , , , , ; , ,
, , , , , , , , , , ,
A a b c d e f B a b c
R a a a c b c a e b e c e
= =
=
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× =
maka :
( ) ( ) ( ) ( ){ }, , , , ,R B B a a a b b c∩ × =
Arwin@23206008
14
5. Path dalam Relasi dan Digraph
• :R A A→ . Sebuah path dengan panjang n dalam R dari a ke b adalah sebuah
elemen hingga 1 1 2 1, , ......................., ,na x x x bπ −= yang bermula dari a dan berakhir di b
sehingga 1 1 2 2 1 1, , .........................., ,n n na R x x R x x R x x R b− − −
Contoh :
{ } ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1 2 3 4 5 1 2 2 2 2 3 2 4 2 5 4 3 5 1 5 4, , , , ; : , , , , , , , , , , , , , , ,A R A A= → =
Matriks
0 1 0 0 0
0 1 1 1 1
0 0 0 0 0
0 0 1 0 0
1 0 0 1 0
RM
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
Digraph
Maka : 1 1 2 5 4 3, , , ,π = atau 1 2 2 5 5 4 4 3 4, , ,R R R R = , dapat disingkat dengan 41 3R
• nR adalah nx R 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 .
Contoh :
{ } ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1 2 3 4 5 6 1 2 1 3 2 2 2 4 2 5 3 4 4 5 5 6, , , , , ; : , , , , , , , , , , , , , , ,A R A A= → =
Matriks
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
RM
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥
= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
Digraph
Arwin@23206008
15
Tentukan 2R pada A !
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }2 1 2 1 4 1 5 2 2 2 4 2 5 2 6 3 5 4 6, , , , , , , , , , , , , , , , ,R =
Matriks
2
0 1 0 1 1 0
0 1 0 1 1 1
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
RM
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥
= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
2
0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0
0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0
0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
R RRM M M=
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥
= =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
e
e terbukti !
6. Digraph R∞
( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( )( ) ( )( )
0 1 1 1 1 11 2 1 3 1 4 1 5 1 60 0 1 1 1 12 3 2 4 2 5 2 60 0 0 1 1 1
3 4 3 5 3 60 0 0 0 1 1
4 5 4 60 0 0 0 0 1
5 6 0 0 0 0 0 0
, , , , , , , , , ,
, , , , , , , ,
, , , , , ,
, , , ,
,
RR M ∞
∞
⎡ ⎤⎧ ⎫⎢ ⎥⎪ ⎪⎢ ⎥⎪ ⎪⎢ ⎥⎪ ⎪= → =⎨ ⎬ ⎢ ⎥
⎪ ⎪ ⎢ ⎥⎪ ⎪ ⎢ ⎥⎪ ⎪ ⎢ ⎥⎩ ⎭ ⎣ ⎦
7. Sifat-sifat Relasi
• 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
16
Contoh :
{ }3 2 1, ,A = . R relasi " "≤ sehingga ( ) ( ) ( ) ( ) ( ) ( ){ }1 1 1 2 1 3 2 2 2 3 3 3, , , , , , , , , , ,R = ,
maka :
1 1 1
0 1 1
0 0 1RM
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦
• Symmetric, Asymmetric dan Antisymmetric
:R A A→ disebut “symmetric” bila a R b b R a→
disebut “asymmetric” bila a R b b R→ a
disebut “antisymmetric” bila a Rb dan b Ra a b→ =
• Transitive dan Intransitive
:R A A→ adalah “transitive” bila a R b dan b R c a R c→
Contoh :
{ } ( ) ( ) ( ){ }1 2 3 4 1 2 1 3 4 2, , , ; , , , , ,A R= =
0 1 1 0
0 0 0 0
0 0 0 0
0 0 1 0
RM
⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦
transitive ? Tidak !
( ) ( ) ( ) ( ) ( ) ( ){ }, , ; , , , , , , , , ,A a b c R a a a b a c b c c c= =
1 1 1
0 0 1
0 0 1RM
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦
transitive ? Ya ! Buktikan !
, , ,
, , ,
, , ,
, , ,
, , ,
a a a b a a
a a a c a c
a b b c a c
a c c c a c
b c c c b c
→→→→→
2
1 1 1 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1
0 0 1 0 0 1 0 0 1RR
M M
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥= → =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
e terbukti !
Arwin@23206008
17
8. Relasi Ekivalen
Relasi yang reflexive, symmetric dan transitive
Contoh :
{ } ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1 2 3 4 1 1 1 2 2 1 2 2 3 4 4 3 3 3 4 4, , , ; : , , , , , , , , , , , , , , ,A R A A
R ekivalen
= → =
↓
9. Partisi dan Relasi Ekivalen
• Sebuah Partisi adalah kumpulan dari subset-subset dari sebuah set yang masing-
masingnta tak kosong dan disjoint.
{ }, , , , , , ,A a b c d e f g h= →
{ }{ }{ }{ }{ }
1
2
3
4
5
, , ,
, , , , ,
, , ,
,
,
A a b c d
A a c e f g h
A a c e g
A b d
A f h
=
=
=
=
=
partisi adalah vertex tidak bersentuhan. Maka { }3 4 5, ,A A AΡ = adalah partisi dari A .
• Ambil Ρ adalah partisi dari A . Definisi relasi R pada A adalah a R b jika dan hanya
jika a dan b anggota dari partisi yang sama, maka R → ekivalen.
Contoh : { } { } { }{ }1 2 3 4 1 2 3 4, , , ; , , ,A = Ρ = maka
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 4 4, , , , , , , , , , , , , , , , , , ,R =
10. Operasi pada Relasi
Karena Relasi adalah set dari pasangan berurut maka semua operasi set juga dapat diberlakukan
pada relasi.
Arwin@23206008
18
• Complementary relation
Bila :R A B→ maka :R A B→ dengan a R b jika a R b b R→ a
Contoh :
{ } { }( ) ( ) ( ) ( ){ }( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }
1 2 3 4
1 1 2 3
1 2 2 3 3 4 4 4
, , , ; , ,
: , , , , , , ,
: , , , , , , , , , , , , , , ,
A B a b c
R A B a c b a
R A B b a c b c a b c
= =
→ =
→ =
• Inversion
1 :R B A− → dengan 1b R a− jika dan hanya jika a Rb
Contoh : Lihat set di atas, maka ( ) ( ) ( ) ( ){ }1 1 3 2 1: , , , , , , ,R B A a a b c− → =
11. Teorema-teorema
• Teorema 1 : Jika R S⊆ , maka 1 1R S− −⊆
Jika R S⊆ , maka S R⊆
Jika ( ) 1R S
−∩ , maka 1 1R S− −∩
Jika ( ) 1R S
−∪ , maka 1 1R S− −∪
Jika ( )R S∩ , maka R S∪
Jika ( )R S∪ , maka R S∩
• Teorema 2 : R dan S , relasi pada A adalah
Jika R reflexive, maka 1R− juga demikian
R reflexive jika dan hanya jika R irreflexive
Bila R reflexive maka demikian juga R S∩ dan R S∪
Arwin@23206008
19
• Teorema 3 : R relasi pada A
R simetri jika dan hanya jika R R=
R antisimetri jika dan hanya jika R R∩ ⊆ relasi satuan, V adalah
relasi satuan. 1RM→ =
R asimetri jika dan hanya jika R R∩ =∅
• Teorema 4 : R dan S relasi pada A
Jika R simetri, demkian pula dengan 1R− dan R
Jika R dan S simetri, demikian pula R S∩ dan R S∪ .
• Teorema 5 : R dan S relasi pada A
( )2R S∩ ……..
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 1R , ini
disebut dengan CLOSURE dari R bila elemen yang kita tambahkan seminimal mungkin.
a. { }1, 2, 3A = dan ( ) ( ) ( ) ( ) ( ){ }1,1 , 1, 2 , 2,1 , 1, 3 , 3,1R = . Agar R bersifat Reflexive
harus ditambahkan elemen-elemen seminimal mungkin yakni ( )2,2 dan ( )3,3 menjadi
( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1 1,1 , 1, 2 , 2,1 , 2, 2 , 1, 3 , 3,1 , 3,3R = sehingga berdampak pada 1R R⊆ .
1R adalah reflexive closure untuk relasi R .
b. R pada set A dan R tidak reflexive. 1R R= ∪Δ dimana Δ adalah relasi “=”. Agar
1R symmetric maka 11R R R−= ∪ maka 1R 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
20
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }, , , , , , , , , , , , , , ,R a a a b a c b b b c c c c d d d∪Δ =
( ) ( ) ( ) ( ){ }( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }
1
1
, , , , , , ,
, , , , , , , , , , , , , , ,
R b a c a c b d c
R R a b b a a c c a b c c b c d d c
−
−
=
∪ =
2. Komposisi Relasi. :f A B→ dan :g B C→ maka :g f A C→
Contoh :
{ }1,2,3,4A = , relasi R pada A adalah ( ) ( ) ( ) ( ) ( ){ }1, 2 , 1,1 , 1,3 , 2,4 , 3, 2R = dan S ,
relasi pada A adalah ( ) ( ) ( ) ( ) ( ){ }1,4 , 1,3 , 2,3 , 3,1 , 4,1S = , maka :
( ) ( ) ( ) ( ) ( ){ }1, 3 , 1,4 , 1,1 , 2,1 , 3, 3S R =
dan
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1, 2 , 2, 2 , 3, 2 , 3,1 , 3,3 , 4,2 , 4,1 , 4, 3R S =
Representasi matriks adalah sebagai berikut :
0 0 1 1 1 1 1 0 1 0 1 1
0 0 1 0 0 0 0 1 1 0 0 0; ;
1 0 0 0 0 1 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0
S R R SM M M
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
sedangkan
1 0 1 1
1 0 0 0
0 0 1 0
0 0 0 0
S RM
⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦
maka R S S RM M=
Dengan cara yang sama akan ditemukan bahwa S R R SM M=
Arwin@23206008
21
0 0 1 1 1 1 1 0 0 1 0 0
0 0 1 0 0 0 0 1 0 1 0 0; ;
1 0 0 0 0 1 0 0 1 1 1 0
1 0 0 0 0 0 0 0 1 1 1 0
R S R SM M M
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
3. Transitive closure R∞ .
{ } ( ) ( ) ( ) ( ){ } ( ) ( ) ( ) ( )1, 2,3,4 ; 1,2 , 2,3 , 3,4 , 2,1 1,1 , 1,3 , 2,2 , 2,4A R= = →
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,1 , 1, 2 , 1, 3 , 1,4 , 2,1 , 2,2 , 2,3 , 2,4 , 3,4R∞ =
R R∞⊆ → transitive
Representasi graph untuk relasi R di atas adalah :
0 1 0 0
1 0 1 0
0 0 0 1
0 0 0 0
RM
⎡ ⎤⎢ ⎥⎢ ⎥= →⎢ ⎥⎢ ⎥⎣ ⎦
tidak transitive. Agar bersifat transitive, lakukan perkalian
hingga level tertentu dan joint-kan dengan matriks pada level yang lebih rendah :
2
0 1 0 0 0 1 0 0 1 0 1 0
1 0 1 0 1 0 1 0 0 1 0 1
0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
R RRM M x
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
2
2
1 0 1 0 0 1 0 0 1 1 1 0
0 1 0 1 1 0 1 0 1 1 1 1
0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0
RRR R M M
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥∪ = ∨ = ∨ =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
3 2
1 0 1 0 0 1 0 0 0 1 0 1
0 1 0 1 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
R R RM M x
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
Arwin@23206008
22
4 3 4 2
0 1 0 1 0 1 0 0 1 0 1 0
1 0 1 0 1 0 1 0 0 1 0 1
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
R R R R RM M x M M
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = = → =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
5 4 5 3
1 0 1 0 0 1 0 0 0 1 0 1
0 1 0 1 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
R R R R RM M x M M
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = = → =⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
dst.
2 .................RR RM M M∞ = ∨ ∨ akan diperoleh :
0 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1
1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1....
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥∨ ∨ ∨ = →⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦
transitive
4. Algoritma Warshall
a. Langkah 1 – kW diperoleh dari 1kW − dengan mentransfer semua “1”.
b. Langkah 2 – Daftar posisi-posisi dalam kolom k dari 1kW − dimana entry-nya adalah
“1”, demikian pula dengan posisi-posisi baris k dari 1kW − dimana entry-nya adalah “1”.
c. Langkah 3 – Letakkan “1” pada posisi ( ),j i yang diperoleh pada langkah 2
Contoh : Matriks pada contoh sebelumnya.
0
0 1 0 0
1 0 1 0
0 0 0 1
0 0 0 0
RW M
↓
←⎡ ⎤⎢ ⎥⎢ ⎥= =⎢ ⎥⎢ ⎥⎣ ⎦
terdapat “1” pada baris 1 (2) dan kolom 1 (2).
1
0 1 0 0
1 1 1 0
0 0 0 1
0 0 0 0
W
↓
⎡ ⎤⎢ ⎥←⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦
terdapat “1” pada baris 2 (1, 2, 3) dan kolom 2 (1, 2).
Arwin@23206008
23
2
1 1 1 0
1 1 1 0
0 0 0 1
0 0 0 0
W
↓
⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥←⎢ ⎥⎣ ⎦
terdapat “1” pada baris 3 (4) dan kolom 3 (1, 2).
3
1 1 1 1
1 1 1 1
0 0 0 1
0 0 0 0
W
↓
⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥←⎣ ⎦
terdapat “1” pada kolom 4 (1, 2, 3).
4 3W W= → tidak ada perubahan lagi.
5. Fungsi. :f A B→ . Contoh : fungsi Nilai sebagai berikut :
- f tidak onto - surjection - f -nya surjective
- onto = surjective
- one-to-one dan onto - one-to-one correspondence - bijective
- A B=
Arwin@23206008
24
Tanggal 5 Oktober 2006
1. Prinsip Sangkar Merpati
Contoh : Ambil 1n+ bilangan bulat sebarang maka sekurang-kurangnya ada 2 yang selisihnya
dapat dibagi n .
Misal : 10n =
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
1n+ bilangan; maka bilangan tersebut akan masuk pada salah satu dari n kelas kongruen.
moda b → sisa bila a dibagi b
mod mod moda b n a m b n≡ → = atau a b− dapat dibagi n
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.
Jawab :
Set latihan : 1 2 21, , ........................,a a a dimana 1 3; 1 21ia i≤ ≤ ≤ ≤ maka :
Hari ke
Jumlah Set
Total set∑ 1st 2nd
1 ||| 3 3 2 | 1 4 1 3 || 2 6 3 4 ||| 3 9 6 3 5 | 1 10 7 4 1 6 | 1 11 8 5 2 3 7 ||| 3 14 11 8 5 4 8 || 2 16 13 10 7 6 9 | 1 17 14 11 8 7 10 || 2 19 16 13 10 9
Arwin@23206008
25
11 | 1 20 17 14 11 10 12 | 1 21 0 18 15 12 11 13 || 2 23 2 20 17 14 13 14 || 1 24 3 21 18 15 14 15 | 3 27 6 21 18 17 16 ||| 2 29 8 20 19 17 || 1 30 9 21 20 18 | 1 31 10 21 19 || 2 33 12 20 | 1 34 13 21 || 2 36 15
Kesimpulan :
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. Fungsi bijection : one-to-one dan onto, A B= .
:f A B→
:f A A→ . Permutasi dapat direpresentasikan dengan fungsi bijection.
( ) ( ) ( ) ( ) ( ){ }, , , , , , , , ,a a b b c c d d e e
( ) ( ) ( ) ( ) ( ){ }, , , , , , , , ,a c b a c b d d e e
{ } ( ) ( ) ( ) ( ) ( ), , , ,a b c d e
A a b c d ep a p b p c p d p e
⎛ ⎞= → ⎜ ⎟
⎝ ⎠
Maka
1 2;a b c d e a b c d e
P Pa b c d e c a b d e
⎛ ⎞ ⎛ ⎞= =⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
Contoh : { }1, 2, 3A = maka ( )
33
3! 1.2.36
3 3 ! 0!P = = =
− dan diperoleh :
Arwin@23206008
26
2 4
1 3 5
1 2 3 1 2 3 1 2 31
1 2 3 2 1 3 3 1 2
1 2 3 1 2 3 1 2 3
1 3 2 2 3 1 3 2 1
A P P
P P P
⎛ ⎞ ⎛ ⎞ ⎛ ⎞= = =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎛ ⎞ ⎛ ⎞ ⎛ ⎞
= = =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
( ) ( ) ( ){ } ( ) ( ) ( ){ } ( ) ( ) ( ){ }14 4
14 3
1, 3 , 2,1 , 3,2 3,1 , 1, 2 , 2, 3 1, 2 , 2, 3 , 3,1
1 2 3
2 3 1
P P
P P
−
−
= → = =
⎛ ⎞= =⎜ ⎟⎝ ⎠
Permutation product-nya adalah :
2 3 1
1 2 3 1 2 3 1 2 3
2 1 3 2 3 1 1 3 2P P P
⎛ ⎞ ⎛ ⎞ ⎛ ⎞= = =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
o o
(lakukan dari belakang ke depan atau 3 2P P→ )
3. { }1 2, , .................., nA a a a= . r elemen dari A yang berbeda 1 2, , ..................., rb b b
Permutasi :P A A→ adalah ( ) ( ) ( ) ( )1 2 2 3 1 1, , ............., ,r rp b b p b b p b b p b b−= = = =
( )p x x= untuk x A∈ dan { }1 2, , ..........., rx b b b∉ disebut dengan cyclic permutation atau
cycle dan dinyatakan dengan ( )1 2, , ........, rb b b
Contoh : { }1, 2,3,4,5A =
( )1 2 3 4 51,3,5
3 2 5 4 1P
⎛ ⎞= = →⎜ ⎟⎝ ⎠
cycle
Penulisan cycle tidak secara eksplisit menyatakan set-nya, kecuali bila :
( ) { }1, 3,5 1,2, 3,4,5,6,7,8,9A→ =
( )1 2 3 4 5 6 7 8 91,3,5
3 2 5 4 1 6 7 8 9
⎛ ⎞=⎜ ⎟
⎝ ⎠ set-nya perlu dinyatakan.
Contoh : { }1,2, 3,4,5,6A =
( ) 1 2 3 4 5 64,1, 3,5
3 2 5 1 4 6
⎛ ⎞= →⎜ ⎟⎝ ⎠
cycle dengan panjang 4
( ) 1 2 3 4 5 65,6, 3
1 2 5 4 6 3
⎛ ⎞= →⎜ ⎟⎝ ⎠
cycle dengan panjang 3
Arwin@23206008
27
( ) ( )
( ) ( )
1 2 3 4 5 64,1, 3,5 5,6,3
3 2 4 1 6 5
1 2 3 4 5 65,6,3 4,1, 3,5
5 2 6 1 4 3
⎛ ⎞= ⎜ ⎟⎝ ⎠⎛ ⎞
= ⎜ ⎟⎝ ⎠
o
o
tidak sama.
Pada umumnya 1 2 2 1c c c c≠o o .
4. 2 cycle dari set A disebut disjoint jika tidak ada elemen A yang muncul bersama pada kedua
cycle.
Contoh : { }1,2, 3,4,5,6A =
( ) ( )1 2 3 4 5 6 1 2 3 4 5 64,1, 2 ; 5,6, 3
2 4 3 1 5 6 1 2 5 4 6 3
⎛ ⎞ ⎛ ⎞= =⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
( ) ( )
( ) ( )1 2 2 1
1 2 3 4 5 64,1, 2 5,6,3
2 4 5 1 6 3
1 2 3 4 5 65,6,3 4,1,2
2 4 5 1 6 3
c c c c
⎛ ⎞= ⎜ ⎟⎝ ⎠ =⎛ ⎞
= ⎜ ⎟⎝ ⎠
o
o o
o
bila 1c dan 2c disjoint.
5. Cycle dengan panjang 2 disebut dengan transposisi. Contoh : { }1, 2,3,4,5,6A =
( ) ( )1 2 3 4 5 6 1 2 3 4 5 61, 2 ; 2,6
2 1 3 4 5 6 1 6 3 4 5 2
⎛ ⎞ ⎛ ⎞= =⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
Permutasi dapat ditentukan dari product of transposition sebagai berikut :
( )
( ) ( )
1 2 3 4 5 63,5,6
1 2 5 4 6 3
1 2 3 4 5 6 1 2 3 4 5 63,6 3,5
1 2 6 4 5 3 1 2 5 4 3 6
1 2 3 4 5 6
1 2 5 4 6 3
⎛ ⎞= ⎜ ⎟⎝ ⎠
⎛ ⎞ ⎛ ⎞= ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠⎛ ⎞
= ⎜ ⎟⎝ ⎠
o o sama.
( ) ( ) ( ) ( )1, 3,5,4 1,3 1,5 1,4= o o
6. Partially Ordered Set (Poset)
Sebuah set A dan relasi R pada A yang mempunyai sifat reflexive, antisymmetric dan
transitive disebut dengan Poset.
Arwin@23206008
28
Contoh : { }1, 3,4,6,12A = dan :R relasi dapat membagi, maka :
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )1,1 , 1, 3 , 1,4 , 1,6 , 1,12 , 3,3 , 3,6 , 3,12 ,
4,4 , 4,12 , 6,6 , 6,12 , 12,12R
⎧ ⎫⎪ ⎪= ⎨ ⎬⎪ ⎪⎩ ⎭
1 3 4 6 12
1 1 1 1 1 1
0 1 0 1 1 3
0 0 1 0 1 4
0 0 0 1 1 6
0 0 0 0 1 12
RM
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥= →⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
perhatikan segitiga atas. Elemen-elemennya reflexive,
antisymmetric dan transitive.
7. Relasi
{ } ( ) ( ) ( ) ( ) ( ) ( ){ }1, 2, 3 ; 1,1 , 1, 2 , 1, 3 , 2, 2 , 2,3 , 3,3A R= = ≤ =
( ) ( ) ( ) ( ) ( ) ( ){ }1,1 , 2,1 , 2,2 , 3,1 , 3, 2 , 3, 3R = ≥ =
1 1 1 1 0 0
0 1 1 ; 1 1 0
0 0 1 1 1 1R RM M≤ ≥
⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥= =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦
Contoh :
{ } ( )1, 2, 3,4,12,|
AP A
R dapat membagi
==
= maka :
( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )1,1 , 1,2 , 1, 3 , 1,4 , 1,12 , 2, 2 , 2,4 ,
2,12 , 3, 3 , 3,12 , 4,4 , 4,12 , 12,12R
⎧ ⎫⎪ ⎪= ⎨ ⎬⎪ ⎪⎩ ⎭
Digraph
→
Hilangkan loop path
Arwin@23206008
29
12
4
2
3
1
Hilangkan transitive path
Elemen 2 dan 3 tidak comparable
→
Hilangkan tanda panah dan jadilah
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 : { }1,2, 3,4,12A =
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 : { }2,3,4,6,12,18,24,36 ;A R dapat dibagi= =
Poset tanpa greatest dan least elements.
Arwin@23206008
30
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
least element jika a x x A⊆ ∀ ∈ . Jadi sebuah Poset mempunyai sebanyak-banyaknya 1 greates
element dan 1 least element. Contoh : { }2,4,6,8,12,18,24, 36,72 ;A R dapat membagi= =
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 : { }24,12B =
Least upper bound (lub) adalah 24 dan greates lower bound (glb) adalah 12.
Arwin@23206008
31
Tanggal 6 Oktober 2006
1. Perhatikan gambar berikut ini :
{ } { }1 2, ; , ,
B A
B a b B c d e
⊆
= =
glb 1B tidak ada, lub 1B c=
glb 2B c= , lub 2B h= (?)
1B tidak mempunyai lower bound dan
mempunyai upper bound , , , , ,c d e f g h
2B mempunyai lower bound , ,a b c dan
mempunyai upper bound , ,f g h
{ }6,7,10
B A
B
⊆
=
upper bound { }10,11 maka lub 10
lower bound { }4,1 maka glb 4
2. 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 { },GLB a b dengan
a b∧ (meet). Contoh : { }1, 2,4,5,10, 20 ;A R dapat membagi= = maka :
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )1,1 , 1,2 , 1,4 , 1,5 , 1,10 , 1,20 , 2, 2 , 2,4 , 2,10 , 2,20 ,
4,4 , 4,20 , 5,5 , 5,10 , 5,20 , 10,10 , 10, 20 , 20, 20R
⎧ ⎫⎪ ⎪= ⎨ ⎬⎪ ⎪⎩ ⎭
Arwin@23206008
32
Tanggal 12 Oktober 2006
1. Distributive Lattice, contoh :
Ambil elemen , ,a b c
( ) ( ) ( )a b c a b a c
a I a O
a a
∧ ∨ = ∧ ∨ ∧
∧ = ∨=
Sifat : distributif
Ambil elemen , ,a b c
( ) ( ) ( )a b c a b a c
a I b O
a b
∧ ∨ = ∧ ∨ ∧
∧ = ∨≠
Sifat : tidak distributif
Ambil elemen , ,a b c
( ) ( ) ( )a b c a b a c
a I O O
a O
∧ ∨ = ∧ ∨ ∧
∧ = ∨≠
Sifat : tidak distributif
2. Teorema : Sebuah lattice, L , non distributive jika dan hanya jika mengandung sublattice yang
isomorphic dengan salah satu dari lattice di atas, yakni :
I
a cb
O
Arwin@23206008
33
3. 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 :
' 'a c b c
a c O b c O
a c I b c I
= =∧ = ∧ =∨ = ∨ =
∅
{ }
( ){ } { } { } { }
{ } { } { }{ } { }{ } { } { }{ } { }
, ,
, , , , , ,
, , , , , ,
' ,
, , ,
,
S a b c
a b c a bP S
a c b c a b c
a b c A
a b c a b c
a b c
=
⎧ ⎫∅⎪ ⎪= ⎨ ⎬⎪ ⎪⎩ ⎭
= =
∨ =
∧ =∅
{ }( )20 1, 2,4,5,10, 20 ,|
2 5 1
2 5 10
4 5 4' 5
4 5 5' 4
D
tidak komplemen
O
I
=
∧ =∨ =
∧ = =∨ = =
10
30
2
3
5
15
6
1
{ }( )30 1, 2,3,5,6,10,15,30 ,|
1' 30
2' 15
3' 10
5' 6
D =
====
Bila lattice-nya distributif, maka setiap elemen mempunyai sebuah komplemen yang unik.
Arwin@23206008
34
4. Finite Boolen Algebra. Contoh : { } ( )( ), , ; ,S a b c P S= ⊆ dan { } ( )( )2, 3,5 ; ,T P T= ⊆
maka :
{2,3,5}
{2}
{3}
{5}{2,5}
{3,5}
{2,3}
∅
⇔
isomorphic
{a,b,c}
{a}
{b}
{c}{a,c}
{b,c}
{a,b}
∅
:f S T→ didefinisikan sebagai berikut :
{ }( ) { }{ }( ) { }{ }( ) { }
{ }( ) { }{ }( ) { }{ }( ) { }
{ }( ) { }{ }( ) { }
2 , 2,3
3 , 2,5, , 2,3,5
5 , 3,5
f a f a bf
f b f a cf a b c
f c f b c
= =∅ = ∅
= ==
= =
1;
0;A
if a Sf
if a S
∈⎧= ⎨ ∉⎩
{ }{ }{ }
{ }{ }{ }{ }
, 110000
100 , 101
010 , 011
001 , , 111
a b
a a c
b b c
c a b c
=∅ =
= =
= =
= =
∅
5. Lattice nB . Jika 1 2, , ............, nx a a a= dan 1 2, , ............., ny b b b= elemen dari nB , maka :
a. a b≤ jika dan hanya jika k ka b≤ (sehingga bilangan 0 dan 1) untuk
1,2, .............,k n=
b. 1 2 ....... nx y c c c∧ = dengan { }min ,k k kc a b= . Contoh : 010 101 000∧ =
c. 1 2 ....... nx y c c c∨ = dengan { }max ,k k kc a b= . Contoh : 010 101 111∨ =
d. x mempunyai sebuah komplemen 1 2' ....... nx y y y= dengan 0ky = bila 1kx = dan
1 1ky + = bila 0kx = . Contoh : 010' 101=
Arwin@23206008
35
0 1 2 3n =
( )( ), nP S B⊆ ≅ dengan S n=
Contoh : { }( )6 1,2,3,6 ,|D =
6D
≅
isomorphic
2B
6 2:f D B→
( )( )
( )( )
1 00 3 10
2 01 6 11
f f
f f
= =
= =
{ }( )20 1, 2,4,5,10, 20 ,|D = diperoleh bahwa 20 2nD ≠ maka 20D bukan aljabar Boolean.
{ }( )30 1, 2,3,5,6,10,15,30 ,|D = diperoleh bahwa 30 2nD = maka 30D aljabar Boolean, 3B
dimana 3n = .
Bagaimana dengan { }1, 2,3,6,12, 24, 36,72A = dimana ( ),|P A ?
Setiap mD mempunyai kemungkinan menjadi aljabar Boolean. Untuk melihat suatu set adalah
aljabar Boolean, gunakan aturan di atas.
Arwin@23206008
36
6. Teorema : Ambil 1 2 ........ nn p p p= , dengan ip bilangan-bilangan prima yang berbeda, maka
nD adalah sebuah aljabar Boolean. Contoh :
210
2 | 210 6 | 210 30 | 210
3 | 210 10 | 210 70 | 210210 2.3.5.7
5 | 210 21 | 210 105 | 210
7 | 210 35 | 210 210 | 210
D= → dstnya
{ }66 2.3.11 1, 2, 3,11,22, 33,66= →
66D
≅
isomorphic
3B
7. 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
jika ∧ disubstitusikan untuk ∩ dan ∨ untuk ∪ .
Contoh : L aljabar Boolean sebarang dan ,X Y dalam L maka :
( )( )( )
' '
' '
' '
X X
X Y X Y
X Y X Y
=
∧ = ∨
∨ = ∧
( ) ( ) (010 011 010 ' 01
101 100
101
∧ = ∨
= ∨=
8. ( ) ( )( ), ,L P S⊆ ⇔ ⊆ adalah aljabar Boolean bila memiliki sifat-sifat 1 – 14 (hal. 219-220).
Arwin@23206008
37
Contoh :
' ,
c a O
c a Ic a b
c b O
c b I
∧ =∨ =
= →∧ =∨ =
Karena 'c tidak unik yakni ,a b maka
lattice ini bukan aljabar Boolean.
9. Contoh : Tunjukkan jika a bilangan bulat positif dan 2 |p n dengan p bilangan prima adalah
aljabar Boolean.
{ }{ }{ }{ }
{ }{ }{ }{ }{ }
{ }{ }{ }{ }{ }
{ }
6 2,3 35 5,71
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
= ==∅
= = =
= → = = = =
= = =
= = =
{ } ( )2,3,5,7S P S= =
10. Jika 2| n n p Q→ = bilangan bulat positif. p juga membagi n . nb bukan aljabar Boolean
maka D elemen nD . Contoh :
40
340
40 ?
2 .5
n D
D
= → =
=
2 | 40
2 | 20
2 |10
5
Karena ada pangkat, maka bukan aljabar Boolean.
11. Teorema : Untuk 1, ................nn B B B B≥ = × × × sebanyak n kali merupakan product Poset.
Arwin@23206008
38
1B
2B B B= ×
4B B B B B= × × ×
12. Pelajari aljabar Boolean hal. 223-237.
13. Group → Himpunan dan Operasi (harus punya sifat Tertutup)
Contoh : * = + , { }bilangan positif|Z x x+ =
3* 5 3 5 8 8 Z += + = → ∈
{ }0,1A
meet
=
∧ =
0 1
0 0 0
1 0 1
∧
0 1
0 0 1
1 1 1
∨
{ }, , ,A a b c d=
* a b c d
a a c b d
b b c b a
c c d b c
d a a b b
Bukan komutatif karena
*
*
a b c
b a b
==
* a b c d
a a c b d
b c d b a
c b b a c
d d a c d
Komutatif karena symmetric
pada diagonalnya
Arwin@23206008
39
Tanggal 16 Nopember 2006
1. Group dan Semigroup. Misalkan suatu mesin penjual dengan pilihan koin 200 dan 500.
Permen karet - 400
Permen biasa - 700
Permen coklat - 1000
(200, 200) → permen karet
(200, 500) → permen biasa
(500, 200) → permen biasa
(500, 500) → permen coklat
{ }{ }200,500
, ,
A
B karet biasa coklat
=
=
:f A A B× →
Onto bila setiap elemen dalam Range ter-
cover oleh elemen dari Domain
Definisi : Operasi biner → fungsi
Tabel multiplikasi menyatakan sebuah operasi biner
Koin yang dimasukkan Barang yang dikeluarkan
f 200 500
(200, 200)
(200, 500)
(500, 200)
(500, 500)
Karet
Biasa
Biasa
Coklat
200
500
Karet
Karet
Biasa
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
Warna rambut : orang asing (sifat → tertutup, :f A A A× → )
Warna Gelap Terang Gelap
Terang
Gelap
Gelap
Gelap
Terang
Arwin@23206008
40
Himpunan penjumlahan pada bilangan bulat positif
{ }0,1,2, ............................
*
Z
A A A
+ =
→ contoh : 1 2 3 3 A+ = → ∈
( ) ( ) asosiatif1 2 3 1 2 3+ + = + + − (tidak peduli urutan pengerjaannya)
Maka : ( ),*Z + adalah semigroup.
2. e A∈ sehingga * *e x x e= dimana x x A∀ ∈ , maka e disebut elemen identitas (satuan).
0 Z +∈ elemen identitas untuk operasi +
Contoh :
0 5 5 0
5 6 6 5 komutatif
+ = ++ = + −
3. y A∈ dimana * *y x x y e= = maka y adalah invers x , dituliskan dengan 1x−
4. Flow chart group dan semigroup.
5. Himpunan bilangan bulat Z dan operasi +. Buktikan bahwa ( ),Z + adalah abelian group !
( )( )( )( )
( ) ( )
2 2
0
2 5 10 7
2 5 10 7
5 7 7 5
invers
elemen identitas
asosiatif
komutatif
→− −→
+ − + = −
+ − + =
− + = + − −
maka ( ),Z + adalah abelian group.
Arwin@23206008
41
Sedangkan ( ),Z • bukan abelian group.
* a b
( ) ( )
1
1
* *
* * * *
* ; *
* ; *
*
*
a b b a komutatif
a a b a a b asosiatif
a a a b a bidentitas
a b b a a a
a a ainvers
b b a
−
−
= −
= −
= =−
= =
=−
=
Elemen invers adalah dirinya sendiri
*
*
a a a
b b a
==
a
a
b
b
b
a
6. { }1 2, , ....................., nA a a a= . *A adalah himpunan dari string yang dibangun dari elemen-
elemen A sehingga { }1 2 1 2 2 2* , , ,A a a a a a a= . Operasi • (penggandengan) “concatenation” pada
elemen-elemen *A menghasilkan :
3 2 2 3 2 2
1 2 2 2
1 2 3 3 1
1 2 3
1 2 2 2 1 2 3 3 1
a a a a a a
a a a a
a a a a a
a a a
a a a a a a a a a
αβγα β
• =
=
=
=
=g
( )*,A g adalah semigroup → free semigroup generated by A
λ β ββ λ β
==
g
g dimana λ adalah string kosong
Maka { }1 2 1 1 2 2* , , , ........., , , ............A a a a a a aλ= 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 : { }1,2,3, ...........A = dan { }1,4B =
dimana * adalah perkalian biasa, bila ( ),*A semigroup maka ( ),*B adalah subsemigroup dan monoid
dimana 1e = .
Arwin@23206008
42
8. Lihat dan pelajari contoh 18 hal. 312 dan contoh 6 hal. 331.
2
3
1
1 2 3
2 3 1
1 2 3
3 1 2
1 2 3
1 2 3
f
f
f
⎛ ⎞= ⎜ ⎟⎝ ⎠⎛ ⎞
= ⎜ ⎟⎝ ⎠⎛ ⎞
= ⎜ ⎟⎝ ⎠
2
1 2 3
1 3 2f
⎛ ⎞= ⎜ ⎟⎝ ⎠
1 2
1 2 3
2 3 1f f
⎛ ⎞= ⎜ ⎟⎝ ⎠
o
Group permutasinya adalah
{ }1 2 3 1 2 3, , , , ,A f f f g g g=
( ),A o permutation group bersifat
- tertutup
- asosiatif
- elemen satuan
- invers