DUNIA ISLAM
NFORMASI AGAMA DI INDONESIA
| Agama di Indonesia memegang
peranan penting dalam kehidupan masyarakat. Hal ini dinyatakan di dalam
ideologi bangsa Indonesia, Pancasila: “Ketuhanan Yang Maha Esa”.
Sejumlah agama di Indonesia berpengaruh secara kolektif terhadap
politik, ekonomi dan budaya. Di tahun 1998, kira-kira 88% dari 222 juta
penduduk Indonesia adalah pemeluk Islam, 5% Protestan, 3% Katholik, 2%
Hindu, 1% Buddha, dan 1% kepercayaan lainnya. Dalam UUD 1945 dinyatakan bahwa "tiap-tiap penduduk diberikan kebebasan untuk memilih dan mempraktikkan kepercayaannya dan menjamin semuanya akan kebebasan untuk menyembah, menurut agama atau kepercayaannya". Pemerintah, bagaimanapun, secara resmi hanya mengakui enam agama, yakni Islam, Katolik, Protestan, Hindu, Buddha dan Konghucu. |
|
1. ISLAM |
|
Sejarah Islam di Indonesia sangatlah kompleks dan mencerminkan keanekaragaman dan kesempurnaan tersebut kedalam kultur. Pada abad ke-12, sebagian besar pedagang orang Islam dari India tiba di pulau Sumatera, Jawa dan Kalimantan. Hindu yang dominan beserta kerajaan Buddha, seperti Majapahit dan Sriwijaya, mengalami kemunduran, dimana banyak pengikutnya berpindah agama ke Islam. Dalam jumlah yang lebih kecil, banyak penganut Hindu yang berpindah ke Bali, sebagian Jawa dan Sumatera. [16] Dalam beberapa kasus, ajaran Islam di Indonesia dipraktikkan dalam bentuk yang berbeda jika dibandingkan dengan Islam daerah Timur Tengah. |
|
2. KRISTEN KATOLIK |
|
Agama Katolik untuk pertama kalinya masuk ke Indonesia pada bagian pertama abad ketujuh di Sumatera Utara. Fakta ini ditegaskan kembali oleh (Alm) Prof. Dr. Sucipto Wirjosuprapto. Untuk mengerti fakta ini, perlulah penelitian dan rentetan berita dan kesaksian yang tersebar dalam jangka waktu dan tempat yang lebih luas. Berita tersebut dapat dibaca dalam sejarah kuno karangan seorang ahli sejarah Shaykh Abu Salih al-Armini yang menulis buku "Daftar berita-berita tentang Gereja-gereja dan pertapaan dari provinsi Mesir dan tanah-tanah di luarnya". yang memuat berita tentang 707 gereja dan 181 pertapaan Serani yang tersebar di Mesir, Nubia, Abbessinia, Afrika Barat, Spanyol, Arabia, India dan Indonesia. Dengan terus dilakukan penyelidikan berita dari Abu Salih al-Armini kita dapat mengambil kesimpulan kota Barus yang dahulu disebut Pancur dan saat ini terletak di dalam Keuskupan Sibolga di Sumatera Utara adalah tempat kediaman umat Katolik tertua di Indonesia. Di Barus juga telah berdiri sebuah Gereja dengan nama Gereja Bunda Perawan Murni Maria (Gereja Katolik Indonesia seri 1, diterbitkan oleh KWI) Awal mula: abad ke-14 sampai abad ke-18 Dan selanjutnya abad ke-14 dan ke-15 entah sebagai kelanjutan umat di Barus atau bukan ternyata ada kesaksian bahwa abad ke-14 dan ke-15 telah ada umat Katolik di Sumatera Selatan. Kristen Katolik tiba di Indonesia saat kedatangan bangsa Portugis yang berdagang rempah-rempah. Banyak orang Portugis yang memiliki tujuan untuk menyebarkan agama Katolik Roma di Indonesia, dimulai dari kepulauan Maluku pada tahun 1534. Antara tahun 1546 dan 1547, pelopor misionaris Kristen, Fransiskus Xaverius, mengunjungi pulau itu dan membaptiskan beberapa ribu penduduk setempat. Selama masa VOC, banyak praktisi paham Katolik Roma yang jatuh, dalam hal kaitan kebijakan VOC yang mengutuk agama itu. Yang paling tampak adalah di Flores dan Timor Timur, dimana VOC berpusat. Lebih dari itu, para imam Katolik Roma telah dikirim ke penjara atau dihukum dan digantikan oleh para imam Protestan dari Belanda. Seorang imam Katolik Roma telah dieksekusi karena merayakan misa kudus di suatu penjara semasa Jan Pieterszoon Coen menjabat sebagai gubernur Hindia Belanda. Pada tahun 2006, 3% dari penduduk Indonesia adalah Katolik, lebih kecil dibandingkan para penganut Protestan. Mereka kebanyakan tinggal di Papua dan Flores. |
|
3. KRISTEN PROTESTAN |
|
Protestan membentuk suatu perkumpulan minoritas penting di beberapa wilayah. Sebagai contoh, di pulau Sulawesi, 17% penduduknya adalah Protestan, terutama di Tana Toraja dan Sulawesi Tengah. Sekitar 65% penduduk di Tana Toraja adalah Protestan. dibeberapa wilayah, keseluruhan desa atau kampung memiliki sebutan berbeda terhadap aliran Protestan ini, seperti Adventist atau Bala Keselamatan, tergantung pada keberhasilan aktivitas para misionaris. Di Indonesia, terdapat dua provinsi yang mayoritas penduduknya adalah Protestan, yaitu Papua dan Sulawesi Utara, dengan 60% dan 64% dari jumlah penduduk. Di Papua, ajaran Protestan telah dipraktikkan secara baik oleh penduduk asli. Di Sulawesi Utara, kaum Minahasa yang berpusat di sekeliling Manado, berpindah agama ke Protestan pada sekitar abad ke-19. Saat ini, kebanyakan dari penduduk asli Sulawesi Utara menjalankan beberapa aliran Protestan. Selain itu, para transmigran dari pulau Jawa dan Madura yang beragama Islam juga mulai berdatangan. Pada tahun 2006, lima persen dari jumlah penduduk Indonesia adalah penganut Kristen Protestan. |
|
4. HINDU |
|
Hindu di Indonesia berbeda dengan Hindu lainnya di dunia. Sebagai contoh, Hindu di Indonesia, secara formal ditunjuk sebagai agama Hindu Dharma, tidak pernah menerapkan sistem kasta. Contoh lain adalah, bahwa Epos keagamaan Hindu Mahabharata (Pertempuran Besar Keturunan Bharata) dan Ramayana (Perjalanan Rama), menjadi tradisi penting para pengikut Hindu di Indonesia, yang dinyatakan dalam bentuk wayang dan pertunjukan tari. Aliran Hindu juga telah terbentuk dengan cara yang berbeda di daerah pulau Jawa, yang jadilah lebih dipengaruhi oleh versi Islam mereka sendiri, yang dikenal sebagai Islam Abangan atau Islam Kejawen. Semua praktisi agama Hindu Dharma berbagi kepercayaan dengan banyak orang umum, kebanyakan adalah Lima Filosofi: Panca Srada. Ini meliputi kepercayaan satu Yang Maha Kuasa Tuhan, kepercayaan didalam jiwa dan semangat, serta karma atau kepercayaan akan hukuman tindakan timbal balik. Dibanding kepercayaan atas siklus kelahiran kembali dan reinkarnasi, Hindu di Indonesia lebih terkait dengan banyak sekali yang berasal dari nenek moyang roh. Sebagai tambahan, agama Hindu disini lebih memusatkan pada seni dan upacara agama dibanding kitab, hukum dan kepercayaan. Menurut catatan, jumlah penganut Hindu di Indonesia pada tahun 2006 adalah 6,5 juta orang, sekitar 1,8% dari jumlah penduduk Indonesia, merupakan nomor empat terbesar. Namun jumlah ini diperdebatkan oleh perwakilan Hindu Indonesia, Parisada Hindu Dharma Indonesia (PHDI). PHDI memberi suatu perkiraan bahwa ada 18 juta orang penganut Hindu di Indonesia. Sekitar 93 % penganut Hindu berada di Bali. Selain Bali juga terdapat di Sumatera, Jawa, Lombok, dan pulau Kalimantan yang juga memiliki populasi Hindu cukup besar, yaitu di Kalimantan Tengah, sekitar 15,8 % (sebagian besarnya adalah Hindu Kaharingan, agama lokal Kalimantan yang digabungkan ke dalam agama Hindu). |
|
5. BHUDAH |
|
Mengikuti kejatuhan Soekarno pada pertengahan tahun 1960-an, dalam Pancasila ditekankan lagi pengakuan akan satu Tuhan (monoteisme). Sebagai hasilnya, pendiri Perbuddhi (Persatuan Buddha Indonesia), Bhikku Ashin Jinarakkhita, mengusulkan bahwa ada satu dewata tertinggi, Sang Hyang Adi Buddha. Hal ini didukung dengan sejarah di belakang versi Buddha Indonesia di masa lampau menurut teks Jawa kuno dan bentuk candi Borobudur. Menurut sensus nasional tahun 1990, lebih dari 1% dari total penduduk Indonesia beragama Buddha, sekitar 1,8 juta orang. Kebanyakan penganut agama Buddha berada di Jakarta, walaupun ada juga di lain provinsi seperti Riau, Sumatra Utara dan Kalimantan Barat. Namun, jumlah ini mungkin terlalu tinggi, mengingat agama Konghucu dan Taoisme tidak dianggap sebagai agama resmi di Indonesia, sehingga dalam sensus diri mereka dianggap sebagai penganut agama Buddha. |
|
6. KONGHUCU |
|
Setelah kemerdekaan Indonesia di tahun 1945, Konghucu di Indonesia terikut oleh beberapa huru-hara politis dan telah digunakan untuk beberapa kepentingan politis. Pada 1965, Soekarno mengeluarkan sebuah keputusan presiden No. 1/Pn.Ps/1965 1/Pn.Ps/1965, dimana agama resmi di Indonesia menjadi enam, termasuklah Konghucu. Pada awal tahun 1961, Asosiasi Khung Chiao Hui Indonesia (PKCHI), suatu organisasi Konghucu, mengumumkan bahwa aliran Konghucu merupakan suatu agama dan Confucius adalah nabi mereka. Tahun 1967, Soekarno digantikan oleh Soeharto, menandai era Orde Baru. Di bawah pemerintahan Soeharto, perundang-undangan anti Tiongkok telah diberlakukan demi keuntungan dukungan politik dari orang-orang, terutama setelah kejatuhan PKI, yang diklaim telah didukung oleh Tiongkok. Soeharto mengeluarkan instruksi presiden No. 14/1967, mengenai kultur Tionghoa, peribadatan, perayaan Tionghoa, serta menghimbau orang Tionghoa untuk mengubah nama asli mereka. Bagaimanapun, Soeharto mengetahui bagaimana cara mengendalikan Tionghoa Indonesia, masyarakat yang hanya 3% dari populasi penduduk Indonesia, tetapi memiliki pengaruh dominan di sektor perekonomian Indonesia. Di tahun yang sama, Soeharto menyatakan bahwa “Konghucu berhak mendapatkan suatu tempat pantas di dalam negeri” di depan konferensi PKCHI. Pada tahun 1969, UU No. 5/1969 dikeluarkan, menggantikan keputusan presiden tahun 1967 mengenai enam agama resmi. Namun, hal ini berbeda dalam praktiknya. Pada 1978, Menteri Dalam Negeri mengeluarkan keputusan bahwa hanya ada lima agama resmi, tidak termasuk Konghucu. Pada tanggal 27 Januari 1979, dalam suatu pertemuan kabinet, dengan kuat memutuskan bahwa Konghucu bukanlah suatu agama. Keputusan Menteri Dalam Negeri telah dikeluarkan pada tahun 1990 yang menegaskan bahwa hanya ada lima agama resmi di Indonesia. Karenanya, status Konghucu di Indonesia pada era Orde Baru tidak pernah jelas. De jure, berlawanan hukum, di lain pihak hukum yang lebih tinggi mengizinkan Konghucu, tetapi hukum yang lebih rendah tidak mengakuinya. De facto, Konghucu tidak diakui oleh pemerintah dan pengikutnya wajib menjadi agama lain (biasanya Kristen atau Buddha) untuk menjaga kewarganegaraan mereka. Praktik ini telah diterapkan di banyak sektor, termasuk dalam kartu tanda penduduk, pendaftaran perkawinan, dan bahkan dalam pendidikan kewarga negaraan di Indonesia yang hanya mengenalkan lima agama resmi. Setelah reformasi Indonesia tahun 1998, ketika kejatuhan Soeharto, Abdurrahman Wahid dipilih menjadi presiden yang keempat. Wahid mencabut instruksi presiden No. 14/1967 dan keputusan Menteri Dalam Negeri tahun 1978. Konghucu kini secara resmi dianggap sebagai agama di Indonesia. Kultur Tionghoa dan semua yang terkait dengan aktifitas Tionghoa kini diizinkan untuk dipraktekkan. Warga Tionghoa Indonesia dan pemeluk Konghucu kini dibebaskan untuk melaksanakan ajaran dan tradisi mereka. |
|
| ||||||||||||||||||||
matika distrit
LECTURE
NOTES
MATEMATIKA DISKRIT
Disusun
Oleh :
Dra. D. L. CRISPINA PARDEDE, DEA.
JURUSAN
TEKNIK INFORMATIKA
UNIVERSITAS
GUNADARMA
PONDOK CINA, MARET 2004
DAFTAR ISI
Pertemuan
Ke-1
BAB I STRUKTUR ALJABAR
Sebuah sistem dimana terdapat sebuah
himpunan dan satu atau lebih dari satu operasi n-ary, yang didefinisikan pada
himpunan tersebut, dinamakan sistem aljabar. Selanjutnya, sebuah sistem aljabar
akan dinyatakan dengan (S,f1 ,f2 ,f3 ,...,fn)
dimana S sebuah himpunan tidak kosong dan f1 , f2 , ....,
fn operasi-operasi yang
didefinisikan pada S. Sebagai contoh, (Z,+) adalah sebuah sistem aljabar yang
dibentuk oleh himpunan bilangan bulat Z dan operasi penjumlahan biasa ; (Z,+,x)
adalah sebuah sistem aljabar yang dibentuk oleh himpunan bilangan bulat dan dua
buah operasi biner.
Sistem aljabar yang termasuk dalam pokok
bahasan Matematika Diskrit yang akan diberikan adalah sistem aljabar satu
operasi biner dan sistem aljabar dua operasi biner. Sebelum melihat jenis-jenis
sistem aljabar dan konsep-konsep yang berkaitan dengannya, kita akan tinjau
lebih dahulu operasi biner dan sifat-sifat operasi biner.
1.1. OPERASI BINER
Operasi biner pada himpunan tidak kosong
S adalah pemetaan dari S x S kepada S. Notasi yang digunakan untuk menyatakan
operasi biner adalah +, x, *,
· , Å , Ä , dan sebagainya. Hasil dari sebuah
operasi, misalnya Ä
, pada elemen a dan b akan ditulis sebagai a Ä b.
Contoh
1.1.
Operasi
berikut adalah beberapa contoh operasi biner :
-. Operasi pembagian pada bilangan riil.
-.
Warna rambut anak yang ditentukan oleh warna rambut orang tuanya.
-. Operasi biner Å yang didefinisikan sebagai a Å b = a +
b – 2ab. ð
1.2. SIFAT OPERASI BINER
Sifat-sifat
yang dimiliki oleh sebuah sistem aljabar nantinya ditentukan oleh sifat-sifat
yang dimiliki oleh setiap operasi di dalam sistem aljabar tersebut. Berikut
akan diuraikan sifat-sifat yang dapat dimiliki oleh sebuah operasi biner.
Misalkan
* dan Å
adalah operasi biner. Operasi * dikatakan :
-. KOMUTATIF , jika a * b = b * a, untuk setiap a, b.
-. ASOSIATIF, jika (a * b) * c
= a * (b * c), untuk setiap a, b, c.
-. Mempunyai :
IDENTITAS,
jika terdapat e sedemikian hingga a * e = e * a = a, untuk setiap a.
IDENTITAS
KIRI, jika terdapat e1 sedemikian hingga e1 * a = a, untuk setiap a.
IDENTITAS
KANAN, jika terdapat e2 sedemikian hingga a * e2 = a, untuk setiap
-.
Mempunyai sifat INVERS, jika untuk setiap
a terdapat a-1 sedemikian hingga a * a-1 = a-1 * a
= e, dimana e adalah elemen identitas
untuk operasi *. a-1 disebut invers
dari elemen a.
-.
DISTRIBUTIF terhadap operasi Å , jika untuk setiap a, b, c berlaku
a *
(b Å c ) = ( a * b) Å (a * c)
dan (b Å c ) * a = ( b * a) Å (c * a).
Contoh 1.2.
Operasi biner
penjumlahan biasa adalah sebuah operasi yang bersifat komutatif, karena untuk
sembarang bilangan x dan y
berlaku x+y = y+x. Operasi penjumlahan
bersifat asosiatif, karena untuk sembarang x, y, z berlaku (x+y)+z = x+(y+z).
Identitas untuk operasi penjumlahan adalah 0 (nol). Invers penjumlahan untuk
sembarang bilangan p adalah –p, karena
p+(-p)=0.
ð
Contoh 1.3.
-. Operasi perkalian bersifat distributif terhadap operasi
penjumlahan, karena untuk setiap bilangan
a, b dan c berlaku a x (b+c) = (a x b) + (a x c) dan (b + c) x a = (b x a) + (c x a).
-. Operasi penjumlahan tidak bersifat distributif
terhadap operasi perkalian, karena terdapat
p, q dan r
dimana p + (q x r) ¹ (p + q) x (p + r). Sebagai contoh 2 + (3 x 4)
¹ (2 +
3) x (2 + 4). ð
Himpunan S
dikatakan tertutup terhadap terhadap operasi biner *
, jika untuk setiap a, b Î S berlaku a *
b Î S
Contoh 1.4.
-. Himpunan bilangan
bulat Z
tertutup terhadap operasi penjumlahan biasa, karena untuk setiap x, y Î Z berlaku x + y Î Z.
-. Himpunan bilangan bulat Z
tidak tertutup terhadap operasi pembagian biasa, karena terdapat 2, 3 Î Z dimana 2 : 3 Ï Z. ð
Soal
Latihan 1.1.
1. Tunjukkan bahwa himpunan bilangan genap tertutup terhadap
operasi penjumlahan.
2. Tunjukkan bahwa operasi penjumlahan bersifat asosiatif pada
himpunan bilangan kelipatan 2.
3. Misalkan A adalah himpunan bilangan asli. Operasi
biner * didefinisikan pada himpunan tersebut. Selidiki sifat asosiatif operasi
biner yang didefinisikan sebagai berikut : [LIU]
a. a * b = a + b + 3.
b. a * b = a + b – 2ab.
c. a * b = a + 2b.
d. a * b =
max (a,b).
4. Misalkan (A,*)
sebuah sistem aljabar dengan *
operasi biner dimana untuk setiap a,b Î A berlaku a * b =
a. Tunjukkan bahwa *
bersifat asosiatif. [LIU]
|
a. Tentukan b Å d, c Å d dan (a Å d) Å c.
b.
Apakah operasi Å bersifat komutatif ?.
c. Tentukan (bila ada) elemen identitas untuk
operasi Å.
Pertemuan
Ke-2
1.3. SISTEM ALJABAR SATU OPERASI
Sistem
aljabar satu operasi (S,*)
dibentuk oleh sebuah himpunan dan sebuah operasi yang didefinisikan
terhadapnya. Berdasarkan sifat-sifat yang dimiliki, sistem aljabar satu operasi
dapat dibedakan menjadi beberapa jenis seperti yang akan diuraikan berikut ini.
1.3.1. SEMIGROUP
Sistem
aljabar (S, *) merupakan semigroup, jika
1. Himpunan S tertutup
di bawah operasi *.
2. Operasi * bersifat asosiatif.
Contoh 1.5.
(Z,+)
merupakan sebuah semigroup ð
Jika operasi biner pada semigroup (S,*)
tersebut bersifat komutatif, maka semigroup (S,*) disebut juga semigroup abel.
Contoh 1.6.
(Z,+)
merupakan sebuah semigroup abel ð
1.3.2. MONOID
Sistem
aljabar (S, *) merupakan monoid, jika
1. Himpunan S tertutup
di bawah operasi * .
2. Operasi * bersifat asosiatif.
3. Pada S terdapat
elemen identitas untuk operasi * .
Contoh 1.7.
(Z,+)
merupakan sebuah monoid dengan elemen identitas penjumlahan . ð
Jika operasi biner pada monoid
(S,*)
tersebut bersifat komutatif, maka monoid (S,*) disebut juga monoid abel.
Contoh 1.8.
Sistem
aljabar (Z,+) merupakan sebuah monoid abel ð
1.3.3. GROUP
Sistem
aljabar (S, *) merupakan monoid, jika
1. Himpunan S tertutup
di bawah operasi * .
2. Operasi * bersifat asosiatif.
3. Pada S terdapat
elemen identitas untuk operasi * .
4. Setiap anggota S
memiliki invers untuk operasi * dan invers tersebut merupakan anggota
S juga.
Contoh 1.9.
(Z,+)
merupakan sebuah group ð
Jika operasi biner pada group (S,*) tersebut bersifat komutatif,
maka group (S,*)
disebut juga group abel.
Contoh 1.10.
Sistem aljabar
(Z,+) merupakan sebuah group abel ð
Soal Latihan 1.2.
1.
Tunjukkan bahwa himpunan bilangan kelipatan dua membentuk
group di bawah operasi penjumlahan.
2.
Misalkan (A,*) sebuah semigroup dan a sebuah anggota A. Pada himpunan A
tersebut didefinisikan operasi biner dimana
x y = x * a * y. Tunjukkan bahwa operasi tersebut bersifat asosiatif. [LIU]
3.
Misalkan (A,*) sebuah semigroup komutatif. Tunjukkan
bahwa jika a * a = a dan b * b = b, maka (a * b) * (a * b) = a * b. [LIU]
Pertemuan
Ke-3
1.3.4. SUBGROUP
Misalkan (G,*) sebuah group dan H Í G.
Jika (H,*) membentuk group, maka (H,*)
merupakan subgroup dari group (G,*).
Contoh 1.11.
(Z,+)
merupakan sebuah group. Misalkan A2
={ x | x = 3n, n Î Z }. Jelas bahwa A2 Í Z. Karena (A2,+) membentuk group, maka
(A2,+) merupakan subgroup dari group (Z,+). ð
Contoh 1.12.
Diketahui Z4 = {0, 1, 2, 3} dan operasi
biner Å
didefinisikan sebagai
.
(Z4 , Å)
adalah sebuah group.
Misalkan B = {0, 2}. Jelas bahwa B Í Z4 . (B , Å)
merupakan subgroup dari group (Z4 , Å).
Sedangkan C = {0, 1, 2}, yang
juga merupakan himpunan bagian dari Z4 , bukan merupakan subgroup dari group Z4
. ð
1.3.5. SUBGROUP SIKLIK
Misalkan
(G,*)
sebuah group dengan elemen identitas e Î G. Jika a Î
G, maka subgroup siklik yang dibangun oleh
a adalah himpunan
gp(a)
= { ... , a-2 , a-1
, a0 , a1 , a2 , ... }
=
{ an |
n Î Z }.
Dimana a0 = e. Dalam hal ini
berlaku pula hukum eksponen, am * an = am+n untuk m,nÎZ. Sebagai contoh, a4 * a2 = a6 , a1 * a1 = a2 .
Untuk n Ï Z+ , an dapat dicari dengan
mengingat bahwa a0 = e dan hukum eksponen a0 = a1 * a-1. Berdasarkan kedua hal tersebut, maka a-1 adalah invers dari
a untuk operasi * dan
a-2 , a-3 dan seterusnya dapat dicari.
Order dari subgroup siklik
gp(a) = { an |
n Î Z } adalah integer positif m
terkecil sedemikian hingga am
= e.
Contoh 1.13.
Perhatikan
group (Z4, Å)
dari contoh 1.12. di atas. Elemen identitas pada group tersebut adalah 0.
Subgroup siklik yang dibangun oleh 2 Î Z4 adalah gp(2) = { 2n
| n Î Z } = {0, 2}. Order
dari gp(2) tersebut adalah 2. ð
Jika
terdapat x Î G sedemikian hingga gp(x) = G, maka group G disebut group siklik
dan elemen x
tersebut dinamakan generator dari G.
Contoh 1.14.
Perhatikan
group (Z4,Å)
dari contoh 1.12. Subgroup siklik yang dibangun oleh 1 Î Z4 adalah gp(1) = { 1n | n Î Z } = {0, 1, 2, 3}. Oleh karena gp(1) = Z4,
maka (Z4,Å)
merupakan group siklik dan 1 merupakan generator. ð
1.3.6. SUBGROUP NORMAL
Misalkan
(G,*) sebuah
group dan (H,*) merupakan
subgroup dari group (G,*).
Koset kiri dari H adalah himpunan a*H = { a * h | " h Î H } dan koset kanan dari H adalah H*a = { h * a | " h Î H }, untuk setiap a Î G.
Contoh
1.15.
(Z4
, Å) adalah group dan B = {0 , 2} adalah subgroup
dari (Z4 , Å).
Koset kiri dari B adalah
a Å B untuk
setiap a Î Z4 : 0 Å B = {0 , 2} , 1 Å B = {1 , 3} , 2 Å B = {0 , 2} , dan 3 Å B = {1 , 3}. Jadi, koset kiri dari B
adalah {0,2} dan {1,3}. Koset kanan dari
B adalah B Å a untuk setiap a Î Z4 : B Å 0 = {0 , 2}, B Å 1 = {1 , 3} , B Å 2 = {0 , 2} , dan B Å 3 = {1 , 3}. Jadi, koset kanan dari B
adalah {0,2} dan {1,3} ð
Suatu subgroup (H,*) dari group (G,*) merupakan subgroup normal jika untuk
setiap a Î G berlaku a*H = H*a
(koset kiri H = koset kanan H, untuk setiap anggota G).
Contoh 1.16.
B = {0
, 2} yang merupakan subgroup dari (Z4 , Å) adalah subgroup normal dari (Z4
, Å), karena
untuk setiap a Î Z4 , a Å B = B Å a.
ð
Himpunan koset dari subgroup
normal H pada group (G, *)
membentuk group kuosien di bawah operasi perkalian koset.
Contoh 1.17.
Koset dari B = {0 , 2} yang
merupakan subgroup dari (Z4,Å) adalah {0 , 2} dan {1 , 3}. Himpunan
{{0 , 2}, {1 , 3}} membentuk group kuosien di bawah operasi perkalian
koset.
Ä
|
{0 , 2}
|
{1 , 3}
|
{0 , 2}
|
{0 , 2}
|
{1 , 3}
|
{1 , 3}
|
{1 , 3}
|
{0 , 2}
|
ð
Soal Latihan 1.3.
1.
Tentukan subgroup siklik yang dibangun oleh 3 dari group (Z,+).
2.
Operasi biner Ä dari group
(V, Ä)
didefinisikan dalam bentuk tabel berikut.
Ä
|
e
|
a
|
b
|
c
|
e
|
e
|
a
|
b
|
c
|
a
|
a
|
b
|
c
|
e
|
b
|
b
|
c
|
e
|
a
|
c
|
c
|
e
|
a
|
b
|
a.
Tentukan subgroup siklik yang dibangun oleh setiap
anggota V dan tentukan ordernya.
b.
Apakah V merupakan group siklik ? Jelaskan !
3. Himpunan bilangan kelipatan 3 merupakan himpunan bagian dari
himpunan bilangan bulat Z. Diketahui bahwa (Z,+) adalah sebuah group abel.
Selidiki apakah himpunan bilangan kelipatan 3 merupakan subgroup normal dari
group (Z,+). Jika ya, tentukan koset
kiri dari himpunan tersebut.
Pertemuan
Ke-4
1.4. SISTEM ALJABAR DUA OPERASI
Sebuah
sistem aljabar dengan dua operasi (S, +, *) dibentuk oleh sebuah himpunan, sebuah operasi aditif
‘+’ dan sebuah operasi multiplikatif ‘*’. Sistem aljabar dengan dua operasi yang akan dibahas
di sini adalah ring dan field.
1.4.1. RING
Sebuah sistem aljabar (S,+,*)
adalah sebuah ring jika sifat-sifat berikut dipenuhi :
1. (S, +) merupakan group abel.
2. Himpunan S tertutup terhadap operasi *.
3. Operasi *
bersifat asosiatif, untuk setiap x, y, z
Î
S berlaku (x * y ) *
z = x * ( y * z).
4. Untuk setiap x, y, z Î
S berlaku hukum distributif kiri x *(
y + z) = (x * y) +
(x * z)
dan hukum distributif kanan (y + z) *
x = (y * x) +
(z * x).
Contoh 1.18.
Sistem
aljabar (Z,+,x) merupakan sebuah ring. ð
Jika kedua
operasi biner pada ring (S,+,*)
bersifat komutatif, maka ring tersebut merupakan ring komutatif.
Contoh 1.19.
Operasi x
pada ring (Z,+,x) bersifat komutatif. Dengan demikian (Z,+,x) merupakan sebuah
ring komutatif. ð
Jika pada ring (S,+,*) terdapat e Î
S dimana a * e = e * a = a, untuk setiap aÎS, maka ring tersebut merupakan ring berunitas. Elemen e
tersebut merupakan identitas untuk operasi multiplikatif * dan
dinamakan unitas. Elemen identitas untuk operasi aditif pada ring (S,+,*) disebut elemen nol (zero element).
Contoh 1.20.
Ring (Z,+,x)
merupakan ring berunitas dengan 1ÎZ sebagai unitas dan 0ÎZ sebagai elemen nol.
ð
Jika
operasi * pada ring
(S,+,*) bersifat komutatif dan terdapat e Î
S dimana a * e = e * a = a, untuk setiap aÎS, maka (S,+,*) merupakan ring komutatif berunitas.
Contoh 1.21.
Ring (Z,+,x)
merupakan ring komutatif berunitas. ð
Jika pada
ring berunitas (S,+,*), untuk setiap a Î S, a bukan elemen nol, terdapat a-1 Î S sedemikian hingga
a * a-1
= a-1 * a =
e, maka ring tersebut merupakan division ring.
Contoh 1.22.
Ring (Z,+,x) bukan merupakan division ring, karena untuk 2 Î
S invers perkaliannya adalah ½ Ï
Z. ð
1.4.2. FIELD
Sebuah sistem aljabar (S,+,*)
adalah sebuah field jika sifat-sifat berikut dipenuhi :
1. (S, +,*)
merupakan division ring.
2. (S - {0}, *)
merupakan group abel, dimana 0 merupakan elemen nol.
Contoh 1.23.
Sistem
aljabar (R,+,x) merupakan field (R =
himpunan bilangan riil). ð
1.4.3. SUBRING
Misalkan (S,+,*) sebuah ring dan A sebuah himpunan bagian yang tidak
kosong dari S. Himpunan A merupakan subring dari ring S, jika (A,+,*)
merupakan ring.
Contoh 1.24.
Himpunan
bilangan bulat Z merupakan himpunan bagian dari himpunan bilangan riil R.
Sistem aljabar (R,+,x) merupakan sebuah ring. Oleh karena (Z,+,x) merupakan
ring, maka (Z,+,x) merupakan subring
dari ring (R,+,x) . ð
Soal Latihan 1.4.
1.
Nyatakan Benar atau Salah.
______ Setiap
field merupakan sebuah ring.
______ Setiap
ring memiliki identitas multiplikatif.
______ Perkalian
pada sebuah field bersifat komutatif.
______ Penjumlahan
pada setiap ring bersifat komutatif.
2.
Selidiki apakah sistem aljabar berikut merupakan
ring.
a.
(Z+, +, x).
b.
(Zn , + , x) ; Zn = { p x n | p Î Z }.
3.
Diketahui (Z,
+, x) merupakan sebuah ring. Selidiki apakah himpunan bilangan kelipatan 2
merupakan subring dari ring (Z, +, x).
4. Diketahui
M2 = { B ½ B matriks riil
ordo 2x2}. Pada M2 didefinisikan operasi penjumlahan matriks +2
dan operasi perkalian matriks x2. Selidiki sistem aljabar (M2
, +2 , x2 ).
Pertemuan
Ke-5
BAB II KOMBINATORIK
2.1. PERMUTASI DAN KOMBINASI
Sebuah permutasi dari sebuah himpunan
obyek-obyek berbeda adalah penyusunan berurutan dari obyek-obyek tersebut.
Contoh 2.1.
Misalkan
S = {1, 2, 3}. Susunan 3 1 2 adalah
sebuah permutasi dari S. Susunan 3
2 adalah sebuah permutasi-2
(2-permutation) dari S ð
Banyak
permutasi-r dari himpunan dengan
n obyek berbeda dinyatakan sebagai P(n,r) dimana
P(n,r) = n . (n - 1) . (n - 2) . (n - 3)
. ... . (n – r + 1).
Jika
r = n , maka
P(n,n) = n . (n - 1) . (n - 2) . (n - 3)
. ... . (n – n + 1).
=
n . (n - 1) . (n - 2) . (n - 3) . ... . 1
=
n !
atau ditulis Pn
= n !
Contoh 2.2.
P(8,3) =
8. 7. 6 = 336
= 
=
ð
=
ð
Rumus umum : n
. (n-1) . (n-2) = 
P(n,r) = 
Sebuah kombinasi-r
elemen-elemen dari sebuah himpunan adalah pemilihan tak berurutan (tanpa
memperhatikan urutan) r elemen dari himpunan tersebut.
Contoh 2.3.
Jika S
= {1, 2, 3, 4}, susunan { 1, 3, 4 } adalah sebuah kombinasi-3 dari S. ð
Banyaknya
kombinasi-r (r-combinations) dari sebuah himpunan dengan n obyek berbeda
dinyatakan sebagai C(n,r) atau 
atau 
.
atau .
Rumus umum : 
Jika r = n,
maka 
Contoh 2.4.
Misalkan S = {1, 2, 3, 4}.
Kombinasi-4 dari S adalah {
1, 2, 3, 4 } ; 
.
.
Kombinasi-3 dari S adalah {
1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}
; 
.
.
Tentukan 
ð
ð
Soal Latihan 2.1.
1. Tunjukkan bahwa P(n,n-1) = P(n,n).
2.
Nomor telephon internal dalam sebuah
kampus terdiri dari lima angka dimana angka pertama tidak sama dengan nol.
Banyaknya nomor telephon berbeda yang dapat disusun di kampus tersebut adalah
......... .
3.
Pada sebuah lingkungan RT, penduduknya
berencana menyelenggarakan acara peringatan kemerdekaan Indonesia. Demi
lancarnya kelangsungan acara tersebut, mereka bersepakat untuk menyusun sebuah
kepanitiaan yang beranggotakan 12 orang. Jika dalam lingkungan tersebut
terdapat 16 pasangan suami istri, berapa pilihan yang mereka miliki untuk
membentuk kepanitiaan yang beranggotakan 4 wanita dan 8 pria ?
Soal Latihan 2.2.
1. Sebuah
himpunan yang tidak kosong dan mengandung
26 anggota memiliki himpunan
bagian yang mengandung 6 anggota sebanyak
............ .
2.
Tunjukkan bahwa C(n,n-r)
= C(n,r) .
Soal Latihan 2.3.
1. Seorang mahasiswa
harus menjawab 8 dari 10 soal ujian Matematika
Diskrit.
a.
Berapa banyak pilihan yang ia miliki ?
b.
Berapa banyak pilihan yang ia miliki jika ia harus
menjawab 3 soal pertama.
2. Jika P (n,k) menyatakan permutasi k dari n
obyek dan C (n,k)
menyatakan kombinasi k
dari n obyek , maka pernyataan
yang benar adalah :
a. C (n ,k ) – P (n ,k ) =
½ C (n ,k ).
b. C (n ,k ) = P (n ,k ) . P (k ,k ).
c. P (n ,k ) = C (n ,k ) . P (k ,k ).
d. P (n , n – k ) = C (n ,n – k
) P (k ,k ).
2.2. KOMBINASI PADA HIMPUNAN DENGAN PENGULANGAN
Sebuah
himpunan disebut himpunan ganda (himpunan dengan pengulangan) jika setiap
anggotanya berulang.
Contoh 2.5.
1). A = {
3.a, 2.b, 5.c } adalah sebuah himpunan dari 3 elemen
berbeda dengan pengulangan hingga.
2). B = {
~.3, ~.5, ~.7, ~.9 } adalah sebuah himpunan dari empat
elemen berbeda dengan pengulangan tak hingga.
3). C = { ~.p,
10.q, 3.r, ~.s } adalah sebuah
himpunan dari empat elemen berbeda dengan pengulangan.
ð
Misalkan
A sebuah himpunan ganda berpengulang tak hingga dengan k anggota berbeda. Banyaknya kombinasi-r pada
A dinyatakan sebagai :
Contoh 2.6.
Diketahui S = { ~.a } . Banyaknya kombinasi-5 pada S
adalah :
ð
Soal Latihan 2.4.
1.
Tentukan kombinasi-5 dari B
= { ~.a, ~.b} .
2. Banyaknya kombinasi-8 dari C
= { ~.a, ~.b, ~.c } .
3. Banyaknya kombinasi-8 dari himpunan { ~.p,
~.q, ~.r } yang mengandung paling
sedikit 4 buah q adalah
........... .
4. Hitung banyaknya kombinasi 10 dari himpunan
{ ~.1, ~.2, ~.3, ~.4 } yang
a. mengandung paling sedikit 4 buah 3.
b.
mengandung paling sedikit 5 buah 2.
c. mengandung paling sedikit 4 buah 3 dan 5
buah 2.
d. tidak mengandung 2
dan 3.
Pertemuan
Ke-6
BAB III PRINSIP INKLUSI DAN EKSKLUSI
Misalkan A dan B sembarang himpunan.
Penjumlahan ½A½+½B½ menghitung banyaknya elemen A yang tidak terdapat dalam B dan banyaknya
elemen B yang tidak terdapat dalam A tepat satu kali, dan banyaknya elemen yang
terdapat dalam A Ç B sebanyak dua kali. Oleh karena itu,
pengurangan banyaknya elemen yang terdapat dalam A Ç B
dari ½A½+½B½ membuat banyaknya anggota A Ç B dihitung tepat satu kali. Dengan demikian,
½A È B½= ½A½+½B½ - ½A Ç B½.
Generalisasi dari hal
tersebut bagi gabungan dari sejumlah himpunan dinamakan prinsip
inklusi-eksklusi.
Contoh 3.1.
Dalam
sebuah kelas terdapat 25 mahasiswa yang menyukai matematika diskrit, 13
mahasiswa menyukai aljabar linier dan 8 orang diantaranya menyukai matematika
diskrit dan aljabar linier. Berapa mahasiswa terdapat dalam kelas tersebut ?
Jawab :
Misalkan A himpunan mahasiswa yang menyukai
matematika diskrit dan B himpunan mahasiswa yang menyukai aljabar linier.
Himpunan mahasiswa yang menyukai kedua mata kuliah tersebut dapat dinyatakan
sebagai himpunan A Ç B. Banyaknya mahasiswa yang menyukai salah satu dari kedua mata kuliah
tersebut atau keduanya dinyatakan dengan ½A È B½.
Dengan demikian ½A È B½ =
½A½+½B½ - ½A Ç B½
= 25 + 13 – 8
= 30.
Jadi, terdapat 30 orang mahasiswa dalam kelas
tersebut. ð
Contoh 3.2.
Berapa
banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh
7 atau 11 ?
Jawab :
Misalkan P himpunan bilangan bulat positif
tidak melampaui 1000 yang habis dibagi 7 dan Q himpunan bilangan bulat positif
tidak melampaui 1000 yang habis dibagi 11. Dengan demikian P È Q adalah himpunan bilangan bulat positif
tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11, dan P Ç Q himpunan
bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan habis
dibagi 11.
½P½ = 
½Q½ =
½P Ç Q½ = 
½P È Q½ = ½P½ + ½Q½ -½P Ç Q½ = 142 + 90 – 12 = 220.
Jadi,
terdapat 220 bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7
atau habis dibagi 11. Ilustrasi dari penghitungan tesebut dapat dilihat pada diagram
di bawah ini.
 |
ð
Soal Latihan 3.1.
1.
Berapa banyak elemen yang terdapat dalam
himpunan A1 A2
jika terdapat 12 elemen dalam A1 dan
18 elemen dalam A2 ,
dan
a.
A1
Ç A2
= Æ
b.
½A1 Ç A2½ = 6
c.
½A1 Ç A2½ = 1
d.
A1
Í A2
2.
Pada sebuah sekolah tinggi terdapat 345 siswa yang mengambil mata kuliah
kalkulus, 212 siswa mengambil kuliah matematika diskrit dan 188 siswa mengambil
kedua mata kuliah tersebut. Berapa siswa yang mengambil kalkulus saja atau
matematika diskrit saja ?
Jika A, B dan C adalah sembarang himpunan,
maka
½A È B È C½ = ½A½ + ½B½ + ½C½ - ½A ÇB½ - ½A ÇC½-½B ÇC½ + ½A ÇB Ç C½
Contoh 3.3.
Berapa
banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh
5, 7 atau 11 ?
Jawab :
Misalkan P himpunan bilangan bulat positif tidak
melampaui 1000 yang habis dibagi 5, Q
himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7, dan R
himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 11.
Dengan demikian P È Q È
R adalah himpunan bilangan bulat positif
tidak melampaui 1000 yang habis dibagi 5 atau 7 atau 11, dan himpunan P Ç Q Ç R adalah
himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, 7 dan
11. Himpunan P Ç Q adalah himpunan bilangan bulat positif
tidak melampaui 1000 yang habis dibagi 5 dan 7,
P Ç R
adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5
dan 11, dan Q Ç R
adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7
dan 11.
½P½ = 
; ½Q½ = ; ½R½ =
; ½Q½ = ; ½R½ =
½P Ç Q½ = 
; ½P Ç R½ = 
; ½P Ç R½ =
½Q Ç R½ = 
½P Ç Q Ç R½ = 
½P È Q È R½
= 200 + 142 + 90 – 28 – 18 – 12 + 2 = 376.
Jadi,
terdapat 376 bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, 7
atau habis dibagi 11. Ilustrasi dari penghitungan tesebut dapat dilihat pada
diagram di bawah ini.
 |
ð
Soal Latihan 3.2.
1. Berapa banyak elemen yang terdapat dalam
himpunan A1 È A2 È A3 jika terdapat 100 elemen dalam A1 , 1000 elemen dalam A2 dan
10000 elemen dalam A3 ,
dan jika
a. A1
Í A2
dan A2 Í A3
b.
Terdapat dua elemen bersama pada setiap pasang himpunan dan satu elemen
bersama dari setiap pasangan tiga himpunan.
2.
Tentukan banyaknya bilangan bulat positif tidak
lebih dari 500 yang habis dibagi oleh 2, 5 dan 7.
3.
Seorang mahasiswa harus menjawab 8 dari 10 soal
ujian Matematika Diskrit. Berapa banyak pilihan yang ia miliki jika paling
sedikit ia harus menjawab 4 dari 5 soal pertama ?
Formulasi
prinsip inklusi eksklusi untuk himpunan hingga
A1 , A2 , A3 , ... , An ,
adalah sebagai berikut :
½A1 È A2 È ... È An ½ = 
½Ai½ - 
½Ai Ç Aj½ +
½Ai½ - ½Ai Ç Aj½ +
+ 
½Ai Ç Aj Ç Ak½
- ..... +
½Ai Ç Aj Ç Ak½
- ..... +
+ ( -1 )n+1 ½Ai Ç Aj Ç ... Ç An½ .
Contoh 3.4.
Berdasarkan prinsip inklusi eksklusi, formula
untuk menghitung banyaknya anggota himpunan hasil gabungan empat himpunan
hingga.
½A1 È A2 È A3 È A4½ = ½A1½+½A2½+½A3½+½A4½ - ½A1 Ç A2½ - ½A1
Ç A3½ +
-½A1 Ç A4½- ½A2 Ç A3½- ½A2
Ç A3½- ½A3 Ç A4½ +
+ ½A1 Ç A2 Ç A3½ + ½A1 Ç A2 Ç A4½ +
+ ½A1 Ç A3 Ç A4½ + ½A2 Ç A3 Ç A4½ +
- ½A1 Ç A2 Ç A3 Ç A4½ .
Soal Latihan 3.3.
1. Berapa banyak elemen yang terdapat dalam
gabungan dari lima himpunan jika setiap
himpunan memiliki 10000 anggota, setiap pasang elemen memiliki 1000 elemen
bersama, setiap pasangan tiga himpunan memiliki 100 elemen bersama, setiap
empat himpunan memiliki 10 elemen bersama dan terdapat satu elemen bersama dari
ke lima himpunan ?
2. Tuliskan formula inklusi eksklusi untuk
menghitung banyaknya anggota gabungan enam himpunan dimana tidak ada tiga
himpunan memiliki elemen bersama.
3. Tentukan banyaknya kombinasi 10 dari
himpunan { 3.a, 5.b, 7.c }.
Pertemuan
Ke-7
BAB IV FUNGSI DISKRIT NUMERIK
4.1. FUNGSI NUMERIK
Sebuah fungsi adalah sebuah relasi biner yang secara unik
menugaskan kepada setiap anggota domain, satu dan hanya satu elemen kodomain.
Fungsi diskrit numerik, atau singkatnya disebut fungsi numerik, adalah sebuah
fungsi dengan himpunan bilangan cacah sebagai domain dan himpunan bilangan riil
sebagai kodomainnya. Fungsi numerik ini menjadi pokok bahasan yang menarik
karena sering digunakan dalam komputasi digital.
Penyajian
fungsi numerik pada prinsipnya bisa dilakukan dengan menuliskan daftar panjang
harga-harganya, namun pada prakteknya dibutuhkan penyajian dalam bentuk yang
tidak terlalu panjang. Contoh berikut menampilkan beberapa bentuk penyajian
dari fungsi numerik.
Contoh 4.1.
an = 7n3
+ 1 , n ³
0.
bn
= 
; cn
= 
; cn
=
ð
Contoh 4.2.
Seseorang menyimpan uang
sejumlah Rp. 10.000.000,- pada bank
dengan tingkat bunga 10% per tahun. Pada
akhir dari tahun pertama, jumlah uang orang tersebut bertambah menjadi Rp.
11.000.000,-. Pada akhir tahun ke-dua, jumlah uangnya menjadi 12.100.000,-
demikian seterusnya. Jika ar menyatakan jumlah uang pada akhir tahun
ke-r, maka fungsi a tersebut adalah ar
= 10.000.000 (1,1)r , r ³ 0.
Berapa
jumlah uang orang tersebut setelah 30 tahun ? ð
4.2. MANIPULASI FUNGSI NUMERIK
Jumlah
dari dua fungsi numerik adalah sebuah fungsi numerik yang harganya pada n
tertentu sama dengan jumlah harga-harga dari kedua fungsi numerik pada n.
Contoh 4.3.
Jika diketahui an = 2n , n ³ 0,
bn = 5 , n ³
0 dan cn = an + bn ,
maka cn = 2n + 5 , n ³ 0. ð
Hasil kali
(produk) dari dua fungsi numerik adalah sebuah fungsi numerik yang harganya
pada n
tertentu sama dengan hasil kali harga-harga dari kedua fungsi numerik
pada n.
Contoh 4.4.
Jika diketahui an = 2n , n ³ 0,
bn = 5 , n ³
0 dan dn = an . bn ,
maka dn = 5(2n) , n ³ 0. ð
Contoh 4.5.
Misalkan pn = , qn = 
.
, qn = .
Tentukan tn = pn + qn ,
dan vn = pn
. qn .
Jawab :
tn = 
vn = 
ð
ð
Misalkan an adalah sebuah fungsi numerik
dan i adalah sebuah integer positif.
Kita gunakan Sia untuk menyatakan fungsi numerik yang nilainya 0
pada n = 0,1,…, (i-1) dan
nilainya sama dengan a n-i pada
n ³ i.
Sia = 
Contoh 4.6.
Misalkan bn
= 2n , n ³ 0 dan cn = S4b , maka
cn = 
ð
ð
Misalkan an adalah sebuah fungsi numerik
dan i adalah sebuah integer positif.
Kita gunakan S-ia untuk menyatakan fungsi numerik yang nilainya sama
dengan a n+i pada
n ³ 0.
S-ia = a n+i , n ³ 0
Contoh 4.7.
Misalkan bn = 2n , n ³ 0 dan
dn = S-5 b ,
maka dn = 2n+5 , n ³ 0 ð
Beda maju (forward difference) dari sebuah fungsi
numerik an adalah sebuah fungsi numerik yang dinyatakan
dengan Da , dimana harga Da
pada n sama dengan harga an+1
- an .
Da = an+1 - an , n ³ 0.
Beda ke belakang (backward difference) dari sebuah fungsi numerik an
adalah sebuah fungsi numerik dinyatakan dengan Ña , dimana harga Ña pada n = 0 sama dengan harga a0 dan
harga Ña
pada n ³
1 sama dengan an - an-1
.
Ña
= 
.
. Contoh 4.8.
Misalkan bn = 2n , n ³ 0 dan
en = Db, maka en = 2n , n ³ 0 ð
Contoh 4.9.
Misalkan bn = 2n , n ³ 0 dan
fn = Ñb, maka fn = 
ð
ð
Soal Latihan 4.
1.
Diketahui f1
= -2 , f2 = 4 , f3
= -8 , f4 = 10 dst.
Tentukan fn .
2.
Sebuah bola dijatuhkan dari ketinggian 15 meter.
Bola tersebut selalu memantul dan mencapai ketinggian sepertiga dari ketinggian
sebelumnya. Jika ht
menyatakan ketinggian yang dicapai bola setelah pantulan ke-t, tentukan fungsi
ht tersebut.
3.
Diketahui fungsi numerik pn = 
,
,
Tentukan :
a. S2 a dan S-2
a.
b. Ña dan Da .
Pertemuan
Ke-8
BAB V RELASI REKURENSI LINIER BERKOEFISIEN KONSTAN
Sebuah
relasi rekurensi linier berkoefisien konstan dari sebuah fungsi numerik a, secara umum ditulis sebagai berikut
C0 an + C1
an-1 + C2 an-2 + … + Ck an-k
= f(n)
dimana
Ci , untuk i = 0,1,2,…,k
adalah konstan dan f(n) adalah
sebuah fungsi numerik dengan variabel n.
Relasi
rekurensi tersebut dikatakan relasi rekurensi linier berderajat k , jika C0 dan Ck keduanya tidak bernilai 0 (nol).
Contoh
5.1.
2 an
+ 2 an-1 = 3n adalah sebuah relasi rekurensi linier
berderajat 1
tn
= 7 tn-1 adalah
sebuah relasi rekurensi linier berderajat
1
an
– an-1 – an-2 = 0 adalah
sebuah relasi rekurensi linier berderajat
2
bn-3 – 3bn = n+3 adalah sebuah relasi rekurensi linier
berderajat 3 ð
Untuk
sebuah relasi rekurensi dengan koefisien konstan derajat k, jika diberikan k buah
harga aj yang berurutan am-k , am-k+1 , … , am-1 untuk suatu nilai m
tertentu, maka setiap nilai am yang lain dapat dicari dengan rumus
am
= 
( C1 am-1
+ C2 am-2 + … + Ck am-k - f(m) )
( C1 am-1
+ C2 am-2 + … + Ck am-k - f(m) )
dan selanjutnya, harga am+1 juga dapat dicari dengan cara
am+1
= ( C1 am
+ C2 am-1 + … + Ck am-k+1 - f(m+1) )
( C1 am
+ C2 am-1 + … + Ck am-k+1 - f(m+1) )
demikian pula untuk nilai am+2 , am+3 dan seterusnya. Di lain pihak, harga am-k-1 dapat pula dihitung dengan
am-k-1
= 
( C1 am-1
+ C2 am-2 + … + Ck-1 am-k - f(m-1) )
( C1 am-1
+ C2 am-2 + … + Ck-1 am-k - f(m-1) )
dan
am-k-2 dapat dicari
dengan
am-k-2
= 
( C1 am-2
+ C2 am-3 + … + Ck-1 am-k-1 - f(m-2) ).
( C1 am-2
+ C2 am-3 + … + Ck-1 am-k-1 - f(m-2) ).
Harga am-k-3 dan seterusnya
dapat dicari dengan cara yang sama. Jadi, untuk sebuah relasi rekurensi linier
berkoefisien konstan derajat k
, bila harga k buah aj
yang berurutan diketahui, maka harga aj
yang lainnya dapat ditentukan secara unik. Dengan kata lain, k buah
harga aj yang diberikan merupakan himpunan syarat batas
(kondisi batas) yang harus dipenuhi oleh relasi rekurensi tersebut untuk dpat
memperoleh harga yang unik.
5.1. SOLUSI DARI RELASI REKURENSI
Seperti
telah disebutkan pada bagian sebelumnya, sebuah relasi rekurensi linier
berkoefisien konstan dapat dinyatakan dalam bentuk C0 an + C1 an-1
+ … + Ck an-k = f(n). Bila nilai f(n) = 0, maka diperoleh relasi rekurensi
yang memenuhi
C0 an + C1
an-1 + C2 an-2 + … + Ck an-k
= 0.
Relasi rekurensi demikian disebut dengan
relasi rekurensi homogen dan solusi dari relasi rekurensi homogen ini dinamakan
solusi homogen atau jawab homogen.
Dalam
usaha mencari solusi dari sebuah relasi rekurensi perlu dicari dua macam
solusi, yaitu :
1.
Solusi homogen (jawab homogen) yang diperoleh dari relasi
rekurensi linier dengan mengambil harga f(n) = 0.
2.
Solusi khusus/partikuler (jawab khusus) yang memenuhi
relasi rekurensi sebenarnya.
Solusi total atau jawab keseluruhan dari
sebuah relasi rekurensi adalah jumlah dari solusi homogen dan solusi
partikuler. Misalkan an(h) = (a0(h),
a1(h), … ) adalah
solusi homogen yang diperoleh dan
misalkan an(p)
= (a0(p), a1(p), … ) adalah solusi
partikuler yang diperoleh, maka solusi total dari relasi rekurensi yang
dimaksud adalah
an = a(h) + a(p)
Soal Latihan 5.1.
1. Tentukan
lima nilai pertama dari an
= an-1 + 3 an-2 jika diketahui a0 = 1 dan a1
= 2.
2. Misalkan {an} sebuah barisan
bilangan yang memenuhi relasi rekurensi
an
= an-1 – an-2
untuk n = 2, 3, 4,... dimana a0
= 3 dan a1 = 5. Tentukan a2
dan a3 .
3.
Diketahui
gn = gn-1 + 2 gn-2 dimana
g6 = 11 dan g4 = 3. Tentukan g7 dan g9 .
4.
Tentukan relasi rekurensi untuk menghitung jumlah langkah yang diperlukan untuk
memindahkan n cakram pada permainan menara Hanoi.
5. Sebuah bola dijatuhkan dari ketinggian 15
meter. Bola tersebut selalu memantul dan mencapai ketinggian sepertiga dari
ketinggian sebelumnya. Nyatakan relasi rekurensi untuk menghitung tinggi bola
pada pantulan ke t.
Pertemuan
Ke-9
5.2. SOLUSI HOMOGEN DARI RELASI REKURENSI
Solusi homogen dari sebuah relasi
rekurensi linier dapat dicari dengan mengambil harga f(n)=0. Solusi homogen dari sebuah persamaan
diferensial linier dengan koefisien konstan dinyatakan dalam bentuk Aan , dimana a adalah akar karakteristik dan
A adalah konstanta yang harganya
akan ditentukan kemudian untuk memenuhi syarat batas yang diberikan. Dengan
substitusi bentuk Aan kepada
an pada persamaan
homogen C0 an +
C1 an-1 + C2 an-2 + … + Ck
an-k = 0 , maka diperoleh
C0 Aan + C1 Aan-1 + C2 Aan-2 + … + Ck Aan-k = 0.
Dengan penyederhanaan pada persamaan
tersebut, maka diperoleh
C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = 0
Persamaan
ini merupakan persamaan karakteristik dari persamaan diferensial yang
diberikan. Jika, bila
adalah akar karakteristik dari persamaan karakteristik ini, maka Aan akan memenuhi persamaan
homogen. Jadi, solusi homogen yang dicari akan berbentuk Aan.
Bila
persamaan karakteristik memiliki sebanyak
k akar karakteristik
berbeda (a1 ¹ a2 ¹
… ¹ ak) , maka solusi homogen dari relasi rekurensi yang dimaksud
dinyatakan dalam bentuk
an(h) = A1
a1n + A2 a2n + … + Ak akn
dimana
ai
adalah akar karakteristik dari persamaan karakeristik yang diperoleh,
sedangkan Ai adalah konstanta yang akan dicari untuk
memenuhi kondisi batas yang ditentukan.
Tentukan solusi homogen dari
relasi rekurensi bn + bn-1
– 6 bn-2 = 0 dengan kondisi
batas b0 = 0 , b1 = 1 .
Penyelesaian :
Relasi rekurensi tersebut
adalah relasi rekurensi homogen, karena f(n)=0.
Persamaan karakteristik dari
relasi rekurensi bn + bn-1
– 6 bn-2 = 0
adalah a2
+ a
- 6 = 0 atau (a + 3) ( a - 2) = 0
hingga diperoleh akar-akar
karakteristik a1 = -3 dan a2 = 2.
Oleh karena akar-akar
karakteristiknya berbeda, maka solusi homogennya berbentuk bn(h) = A1 a1n + A2 a2n Þ bn(h)
= A1 (-3)n + A2
. 2n.
Dengan kondisi batas b0 = 0 dan
b1 = 1 , maka
b0(h) = A1 (-3)0 + A2
. 20 Þ 0
= A1 + A2 .
b1(h) = A1 (-3)1 + A2
. 21 Þ 1
=
-3 A1 + 2 A2 .
bila diselesaikan maka akan
diperoleh harga A1 =
(-1/5) dan A2 = 1/5 , sehingga jawab homogen
dari relasi rekurensi bn +
bn-1 – 6 bn-2 = 0
adalah
bn(h)
= 
(-3)n
+ 
. 2n ð
(-3)n
+ . 2n ð
Jika akar karakteristik a1 dari persamaan
karakteristik merupakan akar ganda yang berulang sebanyak m
kali, maka bentuk solusi homogen yang sesuai untuk akar ganda tersebut
adalah
(A1 . nm-1 + A2
. nm-2 + … + Am-2 n2 + Am-1 . m + Am
) a1n
dimana
Ai adalah konstanta
yang nantinya akan ditentukan untuk memenuhi kondisi batas yang ditentukan.
Tentukan solusi dari relasi
rekurensi an + 4 an-1
+ 4 an-2 = 2n .
Penyelesaian :
Relasi rekurensi homogen : an + 4 an-1
+ 4 an-2 =0.
Persamaan karakteristiknya
adalah a2
+ 4 a
+ 4 = 0
(a + 2) ( a + 2) = 0
hingga diperoleh akar-akar
karakteristik a1 = a2 = -2 , m = 2,
Oleh karena akar-akar
karakteristiknya ganda,
maka solusi homogennya
berbentuk an(h) = (A1 nm-1 + A2 nm-2)
a1n ,
an(h)
= (A1 n + A2 )
(-2)n ð
Contoh 5.4.
Tentukan solusi homogen dari
relasi rekurensi
4 an
- 20 an-1 + 17 an-2 – 4 an-3 = 0.
Penyelesaian :
Persamaan karakteristiknya :
4 a3
- 20 a2 + 17 a - 4 = 0
akar-akar karakteristiknya ½ , ½ dan 4
solusi
homogennya berbentuk an(h)
= (A1 n + A2 )
(½)n + A3 . 4n ð
Soal Latihan
5.2.
1.
Tentukan akar karakteristik dari relasi rekurensi an = 6 an-1 .
2.
Tentukan akar karakteristik dari relasi rekurensi an = an-1 + 3 an-2
.
3.
Tentukan solusi homogen dari relasi rekurensi berikut :
a.
an – 7 an-1 + 10 an-2 =
0 dengan syarat batas a0 = 0 dan a1
= 3.
b.
an – 4 an-1 + 4 an-2 =
0 dengan syarat batas a0 = 1 dan a1
= 6.
c.
an + 6 an-1 + 9 an-2 =
3 dengan syarat batas a0 = 1 dan a1
= 1.
d.
an - 2 an-1 + 2 an-2 – an-3
= 0 dengan a0 = 1, a1 = 1 dan a2 = 1 .
4.
Diketahui a0
= 0 , a1 = 1 , a2 = 4 , a3 = 12 memenuhi relasi rekurensi
ar
+ C1 ar-1 + C2 ar-2 = 0. Tentukan fungsi ar .
Pertemuan
Ke-10
5.3. SOLUSI KHUSUS DARI RELASI REKURENSI
Pada
dasarnya tidak ada satu metode yang dapat menentukan solusi khusus dari sebuah
relasi rekurensi linier yang tidak homogen. Untuk menentukan solusi khusus dari
sebuah relasi rekurensi linier dengan
f(n) ¹ 0, akan
diberikan beberapa model solusi yang disesuaikan dengan bentuk f(n). Model yang sering digunakan adalah
model polinomial atau model eksponensial.
1.
Secara umum, jika
f(n) berbentuk polinomial
derajat t dalam
n :
F1 nt
+ F2 nt-1 + …
+ Ft n + Ft+1 ,
maka bentuk dari solusi
khusus yang sesuai adalah :
P1 nt + P2 nt-1
+ … + Pt n + Pt+1
2.
Jika f(n) berbentuk
bn
dan b
bukan akar karakteristik dari persamaan homogen, maka jawab khusus
berbentuk
P bn
3.
Jika f(n) berbentuk (F1.nt + F2.nt-1
+…+ Ft.n + Ft+1 ).bn dan b bukan akar karakteristik dari
persamaan homogen, maka bentuk dari solusi khusus yang sesuai adalah :
(P1 nt + P2 nt-1
+ … + Pt n + Pt+1 ) bn
4.
Jika f(n) berbentuk
(F1.nt + F2.nt-1 +…+ Ft.n
+ Ft+1 ).bn dan b
akar karakteristik yang berulang sebanyak (m-1)
kali, maka bentuk dari solusi khusus yang sesuai adalah :
nm-1.
(P1 nt + P2 nt-1 + … + Pt
n + Pt+1 ) bn
Contoh 5.5.
Diketahui ar – 7 ar-1 + 10 ar-2
= 3r . Tentukan solusi khusus dari ar.
Penyelesaian :
Diketahui
f(r) = 3r .
Oleh karena bentuk dari f(r) tersebut adalah br dan b = 3
bukan akar karakteristik, maka solusi khusus dari relasi rekurensi tersebut
berbentuk P3r.
ar = P 3r.
Soal Latihan 5.3.
1. Tentukan solusi khusus dari relasi
rekurensi berikut :
a. ar
+ 5 ar-1 + 6 ar-2 = 3 r2 – 2r + 1.
b. ar
– 5 ar-1 + 6 ar-2 = 1.
c. ar
– 4 ar-1 + 4 ar-2 = (r + 1) 2r .
2. Tentukan solusi total dari relasi
rekurensi :
a. ar
– 7 ar-1 + 10 ar-2 = 3r dengan
a0 = 0 dan a1
= 1 .
b. ar
+ 6 ar-1 + 9 ar-2 = 3
dengan a0 = 0 dan a1 = 1 .
3. Tentukan solusi total dari relasi
rekurensi :
a. ar
– 7 ar-1 + 10 ar-2 = 3r dengan
a0 = 0 dan a1
= 1 .
b. ar
+ 6 ar-1 + 9 ar-2 = 3
dengan a0 = 0 dan a1 = 1 .
Pertemuan
Ke-11
BAB VI FUNGSI PEMBANGKIT
Fungsi pembangkit (generating function) dari sebuah fungsi
numerik
an=(a0,
a1, a2,… , ar, … )
adalah sebuah deret tak
hingga
A(z) = a0 + a1 z + a2 z2 + a3
z3 + … + an zn + … .
Pada deret tersebut,
pangkat dari variabel z merupakan indikator sedemikian hingga
koefisien dari zn adalah harga fungsi numerik pada n. Untuk sebuah fungsi numerik an
digunakan nama A(z)
untuk menyatakan fungsi pembangkitnya.
Contoh 6.1.
Diketahui
fungsi numerik gn = 3n , n ³ 0. Fungsi numerik tersebut dapat pula
ditulis sebagai gn = (1, 3,
32, 33, … ).
Fungsi pembangkit dari
fungsi numerik gn tersebut adalah
G(z) = 1 + 3 z +
32 z2 + 33 z3 + … 3n zn
+ …
yang
dalam bentuk tertutup dapat ditulis sebagai
G(z) = 
ð
ð
Jika fungsi
numerik c merupakan jumlah dari fungsi numerik a dan b,
maka fungsi pembangkit dari fungsi numerik c tersebut adalah C(z) = A(z) + B(z), dimana A(z) merupakan fungsi pembangkit dari fungsi numerik a dan
B(z) adalah fungsi pembangkit dari fungsi numerik b.
Contoh 6.2.
Diketahui
fungsi numerik gn = 3n
, n ³ 0
dan fungsi numerik hn
= 2n, n ³
0.
Jika jn = gn + hn , maka
J(z) = + 
yang dapat pula
ditulis sebagai J(z) = 
ð
+ yang dapat pula
ditulis sebagai J(z) = ðContoh 6.3.
Diketahui
fungsi pembangkit dari fungsi numerik
a adalah A(z) = 
. Fungsi pembangkit tersebut dapat ditulis
sebagai A(z) = 
+ . Dengan demikian
diperoleh fungsi numerik an :
. Fungsi pembangkit tersebut dapat ditulis
sebagai A(z) = + . Dengan demikian
diperoleh fungsi numerik an :
an =
2n + (-2)n , n ³ 0
atau dapat ditulis sebagai
an
= 
ð
ð
Jika A(z) merupakan fungsi pembangkit dari fungsi numerik an,
maka ziA(z) adalah fungsi pembangkit
dari Sia , untuk i bilangan bulat positif.
Contoh 6.4.
Diketahui
fungsi numerik gn = 3n , n ³ 0.
Fungsi pembangkit dari bn = S6g adalah
B(z) = z6 ()
)
yang
dapat pula ditulis sebagai B(z) = 
ð
ð
Jika A(z) merupakan fungsi pembangkit dari fungsi numerik an, maka z-i (A(z) – a0 –
a1 z – a2 z2 - … - ai - 1 zi -1 ) adalah fungsi pembangkit dari S-i a , untuk i bilangan bulat
positif.
Contoh 6.5.
Diketahui
fungsi numerik gn = 3n , n ³ 0.
Fungsi pembangkit dari cn = S-4g adalah
C(z) = z-4 (G(z) – g0 – g1 z – g2 z2 – g3
z3 )
C(z) =
z-4 ( - 1 – 3 z – 32
z2 – 33 z3 ) ð
- 1 – 3 z – 32
z2 – 33 z3 ) ð
Jika A(z) merupakan fungsi pembangkit dari fungsi numerik an dan fungsi numerik bn = Da, maka
B(z) = 
(A(z) – a0) – A(z).
(A(z) – a0) – A(z).Contoh 6.6.
Diketahui
fungsi numerik gn = 3n , n ³ 0.
Fungsi pembangkit dari dn = Dg
adalah
D(z) = (G(z) – g0) – G(z).
(G(z) – g0) – G(z).
D(z) =
( - 1) – ð
( - 1) – ð
Jika A(z) merupakan fungsi pembangkit dari fungsi numerik an dan fungsi numerik cn = Ña, maka
C(z) = A(z) – z. A(z).
Contoh 6.7.
Diketahui
fungsi numerik gn = 3n , n ³ 0.
Fungsi pembangkit dari en = Ñg
adalah
E(z) = G(z) – z. G(z) = – 
–
E(z) = 
ð
ð
Soal Latihan 6.
1. Tentukan fungsi pembangkit dari ar = 2 + 3 r+1
.
2. Tentukan fungsi pembangkit dari fungsi ar = 
3.
Tentukan fungsi numerik dari fungsi pembangkit
a.
A(z) = 
b.
B(z) = 
c.
C(z) = 
DAFTAR PUSTAKA
[1] Liu, C.
L., "Elements of Discrete
Mathematics", New York : McGraw Hill, 1986.
[2] Rossen, Kenneth H., "Discrete Mathematics and It's Applications", Edisi Ke-3,
New York : McGraw Hill, 1995.
[3] Suryadi H. S., "Pengantar Struktur Diskrit", Jakarta : Universitas
Gunadarma, 1994.