Matematika Diskrit

Himpunan 

Himpunan : Sembarang kumpulan objek
Dengan kata lain : Kumpulan dari objek-objek tertentu yang merupakan suatu kesatuan
Elemen dari himpunan : Objek-objek itu sendiri

Notasi
Dengan menulis semua elemen-elemennya diantara tanda akolade à {     }
Dengan menyebutkan suatu sifat karakteristik dengan mana dapat ditentukan, apakah satu objek anggota dari himpunan tersebut atau bukan
à { (simbol sembarang elemen | sifat karakteristik elemen tersebut }
{x1, …, xn} : himpunan yang terdiri dari unsur x1, …, xn
{x|p(x)} : himpunan semua x dengan x adalah unsur sifat p(x)
x Î X : x adalah unsur dari X
x Ï X : x bukan unsur dari X
X = Y : kesamaan himpunan (X dan Y mempunyai unsur-unsur yang sama)
|X| : jumlah unsur di X
f : himpunan kosong
X Í Y : X adalah subhimpunan dari Y
Ã(x) : pangkat himpunan (himpunan kuasa) dari X
`X atau X’ : komplemen dari X

Operasi-operasi Dasar

Gabungan (Union)
Misal : A gabungan B (semua unsur di A dan B)
Notasi : A U B
Contoh :  A = { 1,2,3,4} dan B = {2,4,6,8}
               A U B = {1,2,3,4,6,8}

Irisan (intersection)
Notasi : A Ç B
Contoh :  A = { 1,2,3,4} dan B = {2,4,6,8}
               A Ç B = {2, 4}

Penjumlahan
Notasi : A + B
Contoh :  A = { 1,2,3,4} dan B = {2,4,6,8}
               A + B = {1,3,6,8}

Selisih
Notasi : A – B atau B - A
Contoh : A = { 1,2,3,4} dan B = {2,4,6,8}
              A - B = {1,3}

Selisih Simetrik
A D B = (A È B) – (A Ç B)

Contoh 
Diketahui :
S = {1,2,3,…, 10}
A = {1,2,3,5,7}
B = {2,3,4,8,10}
A È B = {1,2,3,4,5,7,8,10}
A Ç B = {2,3}
A + B = {1,4,5,7,8,10}
A – B = {1,5,7}
B – A = {4,8,10}
`A = {4,6,8,9,10}
`B = {1,5,6,7,9}
(A È B)’ = {4,6,8,9,10}
A D B = (A È B) – (A Ç B)
           = {1,2,3,4,5,7,8,10} - {2,3}
           = {1,4,5,7,8,10}

Sifat-sifat
  1. Hukum assosiatif
          (A È B) È C = A È (B È C)                   (A Ç B) Ç C = A Ç (B Ç C)

  1. Hukum komutatif
          A È B = B È A                                    A Ç B = B Ç A 
  1. Hukum distributif
          A Ç (B È C ) = (A Ç B) È (A Ç C)      A È (B Ç C ) = (A È B) Ç (A È C) 
  1. Hukum identitas
          A È f = A                                             A È S = A
  1. Hukum komplemen
          A È `A = S                                           A Ç `A = f
  1. Hukum idempoten
          A È A = A                                            A Ç A = A 
  1. Hukum ikatan
          A È S = S                                             A Ç f = f
 
  1. Hukum penyerapan
          A È (A Ç B) = A                                  A Ç (A È B) = A 
  1. Hukum involusi
  1. Hukum de Morgan untuk himpunan 

Permutasi
 

Definisi PERMUTASI : Jumlah urutan berbeda dari pengurutan objek-objek.
PERMUTASI : Permutasi dari n unsur yang berbeda x1,…, xn adalah   sebuah pengurutan dari n unsur x1,…, xn  

Banyaknya permutasi-r dari sebuah himpunan objek-objek yang berbeda :


Contoh PERMUTASI #1 :
Q:Tentukan banyaknya cara agar sekelompok tujuh orang dapat mengatur diri mereka dalam suatu barisan yang terdiri dari tujuh kursi.
A:Tujuh orang dapat menyusun diri mereka dalam suatu barisan 7*6*5*4*3*2*1 = 7!
Q:Jika mereka duduk mengelilingi sebuah meja melingkar.
A:Satu orang dapat duduk di suatu tempat pada meja melingkar. Enam lainnya kemudian dapat mengatur mereka dalam 6*5*4*3*2*1 = 6! Cara mengelilingi meja.

Contoh PERMUTASI #2 :
Q: Sebuah kotak memuat 10 buah bola lampu. Tentukan banyaknyan sample dari: (a) ukuran 3 dengan pengembalian dan (b) ukuran 3 tanpa pengembalian.
A: (a) n = 103 = 10*10*10= 1000 dan                                       
    (b) n=P(10,3)=10*9*8= 720
Q: Tentukan banyaknya n susunan kartu dalam permainan 5 kartu tersusun jika kartu tertutupnya adalah sebuah As.
A: Ada 4 pilihan untuk kartu tertutup, kemudian 51, 50, 49, 48 pilihan untuk 4 kartu lainnya. Sehingga n = 4*51*50*49*48 = 311875200

Contoh PERMUTASI #3 :
Q: Sebuah team debat terdiri dari 3 laki-laki dan 2 perempuan Tentukan banyaknya n cara agar mereka bisa duduk dalam  satu baris.
A: Karena ada 5 orang, maka n = 5*4*3*2*1 = 360
Q: Sebuah team debat terdiri dari 3 laki-laki dan 2 perempuan Tentukan banyaknya n cara agar mereka bisa duduk dalam  satu baris, jika : (a) laki-laki dan perempuan masing-masing duduk bersama dan (b) hanya perempuan duduk bersama.
A: (a) LLLPP atau PPLLL, sehingga n = 2*3!*2!=2*6*2=24
     (b) PPLLL, LPPLL, LLPPL, LLLPP, shg n = 4*3!*2!=48

Contoh PERMUTASI #4 :
Q: Tentukan n banyaknya kata-kata berhuruf empat yg dapat dibentuk dari kata NUMERICAL
A: Karena ada 9 huruf, maka n = (9,4) = 9*8*7*6 = 3024
Q: Tentukan n banyaknya kata-kata berhuruf empat yg dapat dibentuk dari kata NUMERICAL, jika kata-katanya berawalan dan berakhiran sebuah huruf konsonan.
A: Ada 5 huruf konsonan. Sehingga ada 5 pilihan utk huruf pertama, 4 pilihan utk huruf terakhir kemudian 7 dan 6 pilihan utk huruf kedua dan ketiga. Sehingga n=5*7*6*4=840

Contoh PERMUTASI #5 :
Q: Tentukan n banyaknya kata-kata berhuruf empat yg dapat dibentuk  dari kata NUMERICAL, jika kata-katanya harus memuat huruf R.
A: Ada 4 tempat utk meletakkan huruf R dalam kata. Tiga tempat yg lain dapat dipilih dalam 8,7,6 cara. Sehingga n = 4*8*7*6=1344
Q: Tentukan n banyaknya kata-kata berhuruf empat yg dapat dibentuk dari kata NUMERICAL, jika kata-katanya harus memuat huruf M dan berakhir dengan sebuah huruf vokal
A: Ada 5 huruf vokal. Sehingga ada 4 pilihan utk huruf terakhir. Ada 3 tempat utk meletakkan huruf M dalam kata. Dua tempat lainnya dapat dipilih dalam 7 dan 6 cara. Sehingga n=4*3*7*6=504

Contoh PERMUTASI #6 :
Q: Tentukan n jika P(n,2)=72
A: P(n,2)= n(n – 1) =n2 – n =72 atau n2-n-72=0, (n-9)(n+8)=0, sehingga n = 9
Q: Tentukan n jika 2P(n,2) + 50 = P(2n,2)
A: P(n,2) = n(n-1) = n2 – n dan P(2n,2) = 2n(2n-1) = 4n2 – 2n. Jadi   2(n2-n) +50 = 4n2 – 2n atau 2n2 – 2n +50 = 4n2 – 2n atau 50 = 2n2 atau n2 = 25, karena n harus positip maka jawaban yang mungkin adalah n=5

Definisi PERMUTASI dgn PENGULANGAN :
Banyaknya permutasi dari n objek dari n1 yang sama, n2 yang sama, …, nr yang sama adalah :
                              n!
                      n1! n2! ….nr!

Contoh PERMUTASI dgn Pengulangan #1 :
Q: Tentukan banyaknya m kata-kata tujuh huruf yang dapat dibentuk    dari huruf-huruf dalam kata “BENZENE”.
A: Kita mencari banyaknya permutasi dari tujuh objek yag 3 huruf adalah sama (E-nya) dan 2 huruf adalah sama (N-nya), maka m = 7!/ 3!2! = 7*6*5*4*3*2*1/3*2*1*2*1 = 420
Q: Tentukan banyaknya Permutasi berbeda yang dapat dibentuk dari semua huruf dlm masing-masing kata (a)THEM dan (b) THAT
A: (a) 4! = 24, karena ada 4 huruf dan tanpa pengulangan.
     (b) 4!/ 2! = 12. karena ada 4 huruf yang dua hurufnya adalah T

Contoh PERMUTASI dgn Pengulangan #2 :
Q: Tentukan banyaknya permutasi yang berbeda yg dapat dibentuk dari semua huruf dalam masing-masing kata: (a) RADAR dan (b) UNUSUAL.
A: (a) 5!/ 2!2! = 30, karena ada 5 huruf yg dua R-nya dan dua A-nya yang sama.
     (b) 7!/ 3! = 840, karena ada 7 huruf yang tiga U-nya sama.
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semua huruf dalam kata MISSISSIPPI.
A: Terdapat 11 huruf yang empat I-nya sama, empat S-nya sama dan dua P-nya sama. Jadi m = 11!/ 4!4!2! = 34650

Contoh PERMUTASI dgn Pengulangan #3 :
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semua    huruf dalam kata MISSISSIPPI, jika kata-katanya berawal dengan sebuah huruf I.
A: Sekarang ada 10 sisa tempat untuk mengisi dimana 3 adalah I, 4 S, dan 2 P. Sehingga m = 10!/ 3!4!2! = 12600
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semua    huruf dalam kata MISSISSIPPI, jika kata-katanya berawal dan berakhir dengan sebuah huruf S
A: Sekarang ada 9 sisa tempat untuk mengisi dimana 4 adalah I, 2 S, dan 2 P. Sehingga m = 9!/ 4!2!2! = 7560

Contoh PERMUTASI dgn Pengulangan #4 :
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semua    huruf dalam kata MISSISSIPPI, jika dua huruf P-nya berdampingan satu sama lain.
A: Ada 10 cara utk menempatkan dua P-nya, huruf pertama dan huruf kedua, atau huruf kedua dan ketiga, …, atau huruf kesepuluh dan huruf kesebelas. Dalam setiap kasus, ada 9 sisa tempat untuk mengisi dimana 4 adalah I dan 4 adalah S, sehingga m = 10*(9!/ 4!4!) = 6300
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semua huruf dalam kata MISSISSIPPI, jika 4 huruf S-nya berdampingan satu sama yg lain.
A: Anggap 4 huruf S-nya sebagai satu huruf (1S), maka sekarang terdapat 8 huruf yg 4 adalah I dan 2 adalah P, shg m = 8!/ 4!2! = 840.

Contoh PERMUTASI dgn Pengulangan #5 :
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semuahuruf dalam kata ELEVEN.
A: Ada 6 huruf yang 3 huruf adalah E, sehingga m = 6!/ 3! = 120
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semua huruf dalam kata ELEVEN, jika kata-katanya berawal dengan huruf L.
A: Sekarang ada 5 sisa tempat untuk mengisi dimana 3 huruf adalah E, sehingga m = 5!/ 3! = 20.

Contoh PERMUTASI dgn Pengulangan #6 :
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semua huruf dalam kata ELEVEN, jika kata-katanya berawal dan berakhir oleh huruf E.
A: Sekarang hanya ada 4 sisa tempat utk mengisi 4 huruf yang berbeda m = 4! = 24
Q: Tentukan banyaknya m Permutasi yang dapat dibentuk dari semua    huruf dalam kata ELEVEN, jika kata-katanya berawal dengan huruf E dan berakhir oleh huruf N.
A: Sekarang ada 4 sisa tempat untuk mengisi dimana 2 huruf adalah E, sehingga m = 4!/ 2! = 12.

Kombinasi

Definisi KOMBINASI : Diberikan sebuah himpunan n objek, sebuah kombinasi dari n
objek diambil r secara berturut-turut adalah suatu pemilihan r
objek dimana urutannya tidak berpengaruh.

KOMBINASI : Diberikan sebuah himpunan X = {x1,…, xn} yang mengandung n unsur  (berbeda)
a)      Sebuah r-kombinasi dari X adalah seleksi tak terurut dari r-unsur X  (yakni subhimpunan r-unsur dari X)
b)      Banyaknya r-kombinasi dari sebuah himpunan dengan n-unsur yang  berbeda dinotasikan dengan :


Contoh Kombinasi #1 :
Q: S= {a,b,c,d} yang diambil 3 secara serentak, maka banyaknya kombinasi yg terjadi ?
A: C(4, 3) = 4!/ 3!(4-3)! = 4!/ 3! = 4


Contoh Kombinasi #2 : 
Berapa banyak cara menyeleksi panitia yang terdiri dari 2 wanita    dan 3 pria dari sekelompok 5 wanita yang berbeda dan 6 pria yang berbeda
                                    nw = 5 ; rw = 2 ; np = 6 ; rp = 3

    Contoh KOMBINASI #3 :
    : Seorang petani membeli 3 ekor sapi, 2 ekor babi, dan 4 ekor ayam   betina dari seseorang yang mempunyai enam ekor sapi, lima ekor babi, dan delapan ekor ayam betina. Berapa banyak pilihan yang dipunyai petani ?
    A:  6*5*4*5*4*8*7*6*5/ 1*2*3*1*2*1*2*3*4 = 20 * 10 * 70 = 14000 cara

    Contoh KOMBINASI #4 :
    Q: Suatu kelas terdiri dari tujuh orang laki-laki dan lima orang perempuan. Tentukan banyaknya m panitia yang terdiri dari lima orang dpt dipilih.
    A: Setiap panitia adalah sebuah kombinasi dari 12 orang diambil 5 sekaligus, shg m = c(12,5) = 5544 cara
    Q: Suatu kelas terdiri dari tujuh orang laki-laki dan lima orang perempuan. Tentukan banyaknya m panitia yang terdiri dari 3 pria dan 2 wanita.
    A: m = 7*6*5*5*4/ 1*2*3*1*2 = 350

    Contoh KOMBINASI #5 :
    Q: Sebuah kantong memuat lima kelereng merah  dan enam kelereng   putih. Tentukan banyaknya m cara agar 4 kelereng dapat diambil dari dalam kantong.
    A: Empat kelereng (dari sembarang warna) dapat diambil dari sebelas kelereng dalam m = c(11,4) = 11*10*9*8/ 1*2*3*4 = 330 cara
    Q: Sebuah kantong memuat lima kelereng merah  dan enam kelereng   putih. Tentukan banyaknya m cara jika dua kelereng harus merah dan dua kelereng harus putih.
    A: m = 5*4*6*5/ 2*1*2*1 = 150
    Langganan: Postingan (Atom)