Ulang Kaji Konsep Matematika Teori Bahasa dan Automata
Viska Mutiawani - Informatika FMIPA Unsyiah
1
Ulang Kaji Konsep Matematika • • • • •
Set / himpunan Fungsi Relasi Graf Teknik pembuktian
Viska Mutiawani - Informatika FMIPA Unsyiah
2
SET • Set : kumpulan unsur-unsur
A {1, 2, 3} B {motor , bus, sepeda, mobil}
• Keanggotaan set :
1 A kapal B Viska Mutiawani - Informatika FMIPA Unsyiah
3
Representasi Set • C = { a, b, c, d, e, f, g, h, i, j, k } • C = { a, b, …, k } • S = { 2, 4, 6, … }
finite set
infinite set
• S = { j : j > 0, and j = 2k for some k>0 } • S = { j : j is nonnegative and even } Viska Mutiawani - Informatika FMIPA Unsyiah
4
A = { 1, 2, 3, 4, 5 }
U A
6
2
1
7
4
8
3 5 9
10 Set Universal: semua kemungkinan unsur yang mungkin U = { 1 , … , 10 } 5
Operasi Set A = { 1, 2, 3 }
B = { 2, 3, 4, 5}
• Union
B
A
A U B = { 1, 2, 3, 4, 5 }
2
1
4
3
5
• Intersection
U
A
B = { 2, 3 }
2 3
• Difference • A-B={1} • B - A = { 4, 5 } Viska Mutiawani - Informatika FMIPA Unsyiah
1
Diagram Venn 6
Operasi Set (2) • Complement Universal set = {1, …, 7} A = { 1, 2, 3 }
A
4
A = { 4, 5, 6, 7}
A 1
2 3
5
6 7
A=A Viska Mutiawani - Informatika FMIPA Unsyiah
7
{ bil bulat genap } = { bil bulat ganjil} Bilangan bulat ganjil
1
2 3
genap
5
6
4 7 8
Hukum DeMorgan
U
A
U
AUB=A
B
B =A U B
Coba buktikan!
Viska Mutiawani - Informatika FMIPA Unsyiah
9
Set/Himpunan kosong: ={} SU
=S
U
=
S
S-
= Universal Set
=S
-S=
10
Subset A = { 1, 2, 3} A
U
B
A
U
Proper Subset:
B = { 1, 2, 3, 4, 5 }
B B A
11
Set Disjoint A = { 1, 2, 3 }
A
U
A
B = { 5, 6} B=
B
12
Kardinalitas Set •Hanya untuk set yang finite/terhingga A = { 2, 5, 7 }
|A| = 3 (ukuran set)
13
Powerset Powerset merupakan set/himpunan yang terdiri Dari semua subset dari set tersebut S = { a, b, c } Powerset dari S = set yang terdiri dari semua subset S 2S = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } Perhatikan: | 2S | = 2|S|
( 8 = 23 ) 14
Cross Cartesian A = { 2, 4 }
B = { 2, 3, 5 }
A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 5) }
|A X B| = |A| |B|
Berlaku juga pada set lebih dari dua AXBX…XZ 15
FUNGSI domain 4
range B
A 1 2
5
f(1) = a
a b
3
c
f : A -> B Jika A = domain maka f disebut sebagai fungsi total sebaliknya f merupakan fungsi partial 16
RELASI R = {(x1, y1), (x2, y2), (x3, y3), …} xi R yi Contoh jika R = ‘>’: 2 > 1, 3 > 2, 3 > 1
17
Relasi Ekuivalensi • Refleksif:
xRx
• Simetrik: x R y • Transitif:
yRx
x R y dan y R z
xRz
Contoh jika: R = ‘=‘ •x=x •x=y
y=x
• x = y dan y = z
x=z 18
Kelas Ekuivalensi Untuk relasi ekuivalensi R kelas ekuivalensi dari x = {y : x R y}
Contoh: R = { (1, 1), (2, 2), (1, 2), (2, 1), (3, 3), (4, 4), (3, 4), (4, 3) } Kelas ekuivalensi dari 1 = {1, 2} Kelas ekuivalensi dari 3 = {3, 4} 19
GRAF Graf berarah e node
b d
a c • Node (Vertices) V = { a, b, c, d, e } • Sisi
E = { (a,b), (b,c), (b,e),(c,a), (c,e), (d,c), (e,b), (e,d) } 20
Graf Berlabel 2 6
2
b
1 a
e
3 6
5
d
c
21
Walk/jalan e b d
a c
Walk merupakan urutan dari sisi yang berdekatan (e, d), (d, c), (c, a) 22
Path/laluan e b d
a c
Path merupakan walk yang sisinya tidak berulang Path sederhana: path dimana tidak ada node yang berulang 23
Cycle/siklus e
asal b
3 a
1
d
2 c
Cycle: walk dari node asal ke node itu lagi Cycle sederhana: cycle yang node asalnya saja berulang
24
Euler Tour 8
asal e
7 4 a
1
b 3
6
5
2
d
c Cycle yang melewati semua sisi satu kali saja
25
Hamiltonian Cycle 5
1
b
4 a
base e 2
3
d
c
Siklus sederhana yang mengandung semua node
26
Temukan semua path sederhana pada graf berikut
e b d
a c
asal
27
Langkah 1 e b d
a c
asal
(c, a) (c, e)
28
Langkah 2 e b d
a (c, a) (c, a), (a, b)
c
asal
(c, e) (c, e), (e, b) (c, e), (e, d) 29
Langkah 3 e b d
a (c, a) (c, a), (a, b)
c
asal
(c, a), (a, b), (b, e) (c, e) (c, e), (e, b) (c, e), (e, d)
30
Langkah 4 e b (c, a)
d
a
(c, a), (a, b) (c, a), (a, b), (b, e)
c
asal
(c, a), (a, b), (b, e), (e,d) (c, e) (c, e), (e, b) (c, e), (e, d)
31
root
Tree/pohon
parent leaf child Tree juga graf, hanya tidak memiliki siklus 32
root
Level 0
Level 1 Tinggi 3
leaf Level 2
Level 3 33
Binary Tree
34
TEKNIK PEMBUKTIAN • Pembuktian secara induksi
• Pembuktian secara kontradiksi
35
Induksi Jika ada pernyataan P1, P2, P3, … Jika diketahui: • untuk beberapa b, P1, P2, …, Pb adalah benar • untuk nilai k >= b maka P1, P2, …, Pk juga menyatakan Pk+1 Maka Setiap Pi adalah benar 36
Pembuktian secara Induksi • Dasar induksi Temukan P1, P2, …, Pb yang bernilai benar • Hipotesis induksi Asumsinya P1, P2, …, Pk adalah benar, untuk setiap k >= b
• Langkah induksi Tunjukkan bahwa Pk+1 bernilai benar
37
Contoh Teorema: Binary tree dengan tinggi n memiliki paling banyak 2n daun. Pembuktian secara induksi: Jika L(i) merupakan jumlah maksimum daun pada setiap subtree di ketinggian/level i
38
Kita ingin buktikan: L(i) <= 2i
• Dasar induksi L(0) = 1
(root node)
•Hipotesis induksi Anggap L(i) <= 2i untuk semua i = 0, 1, …, k
• Langkah induksi kita perlu tunjukkan bahwa L(k + 1) <= 2k+1
39
Langkah Induksi
tinggi k k+1
Dari hipotesis induksi: L(k) <= 2k 40
Langkah Induksi
height k
L(k) <= 2k
k+1 L(k+1) <= 2 * L(k) <= 2 * 2k = 2k+1 (binary tree ada dua daun jadi untuk setiap node akan memiliki maksimal dua daun
41
Pembuktian secara Kontradiksi Kita ingin buktikan bahwa pernyataan P adalah benar, dengan cara:
• asumsikan P bernilai salah • kemudian buktikan hingga tercapai kesimpulan P bernilai salah adalah tidak benar • maka, pernyataan P pastilah benar 42
Contoh 1 Teorema: Jika n2 genap maka n genap Bukti: Dengan kontradiksi kita asumsikan jika n2 genap maka n ganjil
Kita buktikan hal tersebut tidak mungkin
43
Bukti: Diketahui n2 genap (kita asumsikan benar) maka n ganjil (negasinya) Karena n ganjil maka n bisa ditulis dengan bentuk n = 2m + 1 dengan m bilangan bulat Diperoleh n2 = (2m + 1)2 n2 = 4m2 + 4m +1 n2 = 2(2m2 + 2m) + 1 Itu berarti n2 = 2(2m2 + 2m) + 1 ganjil. Kontradiksi dengan asumsi “n2 genap” karena terjadi kontradiksi maka dapat disimpulkan jika n2 genap maka n genap 44
Contoh 2 Teorema:
2
merupakan nilai irrasional
Bukti: Anggap secara kontradiksi bahwa ianya rasional
2 = n/m n dan m adalah nilai yang jika dibagi ada hasil
Kita buktikan hal tersebut tidak mungkin 45
2
= n/m
2 m2 = n 2
2 kali nilai berapapun adalah
n genap maka
Genap, maka n2 adalah genap
n=2k m adalah
2 m2 = 4k2
m2 = 2k2
genap maka, m=2p
Oleh karena itu m dan n memiliki hasil pembagi: 2
Kontradiksi!
46
Latihan 2 {1,2,3} ? 2 {1,2,3} ? {1,2} {1,2,3} ? {1,2} {1,2,3} ? { A, B, C} ? { A, B, C} ? 47
Latihan • Buatlah notasi bagi set Z yang mempunyai anggota {0,1,2,3,4}
Z {x | x N | x 5} – N mewakili bilangan natural (bilangan asli)
• Buatlah notasi bagi set Y yang merupakan bilangan ganjil • Buatlah notasi bagi set yang terdiri dari 2 pasang (2-tuples) bilangan natural dengan syarat nilai elemen pertama lebih kecil dari elemen kedua pada tuples 48
