Logika Informatika : Sifat Kalimat, Pohon Semantik, dan Pengujian 2 Kalimat, beserta Contoh Soal

Matematika Diskrit : Prinsip Inklusi-Ekslusi, Permutasi, Kombinasi, dan Contoh Soal

Prinsip Inklusi - Eksklusi

Misalkan A dan B adalah himpunan berhingga yang saling lepas (disjoint), maka

Misalkan A dan B adalah himpunan berhingga, maka

berhingga dan

Misalkan A, B, dan C adalah himpunan berhingga, maka

berhingga dan

Contoh :

Informasi terkecil di memori komputer disimpan dalam byte. 1 byte = 8-bit (0 atau 1). Berapa banyaknya byte yang diawali dengan ‘11’ atau diakhiri dengan ‘11’?

A = himpunan byte yang diawali dengan ‘11’

B = himpunan byte yang diakhiri dengan ‘11’

= himpunan byte yang diawali dan diakhiri dengan ‘11’



Akan ditentukan 

Akan ditentukan |A|

Akan ditentukan |B|

Akan ditentukan

  

Maka 

Latihan 1

Berapa banyak nomor polisi mobil yang mungkin, yang diawali dengan 2 huruf dan diikuti dengan 4 angka, dengan huruf pertama B atau angka terakhir 3? Asumsikan semua huruf dapat digunakan pada nomor polisi.

Latihan 2

Permutasi

Permutasi adalah banyaknya urutan berbeda dari pengaturan objek-objek. Misalkan ada n objek, maka banyaknya urutan yang mungkin yang dapat dibentuk, atau permutasi n dari n objek adalah :

Contoh : 

Berapa banyak “kata” yang dapat dibentuk dari kata “BOSAN”? 

Maka banyak “kata” yang dapat dibentuk : 

P(5,5)= 5.4.3.2.1 = 5! = 120 kata 

Latihan 3

Tiga buah bola dengan warna merah, kuning, dan hijau akan dimasukkan ke dalam 3 buah kotak. Berapa banyak urutan berbeda yang dapat dibuat dari penempatan bola ke dalam kotak? Apa saja urutan tersebut ?

Permutasi r dari n objek berbeda P(n,r) adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek,

Contoh : 

Enam buah bola berwarna merah, kuning, hijau, biru, ungu, dan hitam akan dimasukkan ke dalam 3 buah kotak. Berapa banyak urutan yang mungkin dari penempatan bola ke dalam kotak? 

Latihan 4

Berapa banyak bilangan terdiri atas 4 angka yang dapat dibentuk dari 1,2,3,4,5,6,7,8?

Permutasi Melingkar

Permutasi melingkar dari n objek adalah penyusunan objek-objek yang mengelilingi sebuah lingkaran. Banyaknya susunan objek yang mengelilingi lingkaran adalah (n-1)!

Contoh :

Ada 5 mahasiswa yang duduk di sebuah meja bundar. Berapa banyaknya susunan duduk mahasiswa tersebut?

(n-1)! = (5-1)! = 4! = 4.3.2.1 = 24 susunan 

Permutasi Bentuk Umum

Jika ada n bola yang tidak semuanya berbeda warna. 

Misalnya : 

n1 bola berwarna merah 

n2 bola berwarna hijau 

… 

nk bola berwarna kuning 

maka permutasi n bola ini dirumuskan sebagai berikut : 

Contoh : 

Berapa banyak “kata” atau string yang dapat dibentuk dari huruf-huruf pada kata MISSISSIPPI? 

S = {M, I, S, S, I, S, S, I, P, P, I} 

• Huruf M = 1 buah (n1) 
• Huruf I = 4 buah (n2) 
• Huruf S = 4 buah (n3) 
• Huruf P = 2 buah (n4) 

n = 1 + 4 + 4 + 2 = 11 buah 

Maka :

Latihan 5

Sepuluh lembar kertas akan diwarnai dengan sebagai berikut :

3 lembar dengan warna merah, 
4 lembar dengan warna hijau, dan 
3 lembar dengan warna kuning. 

Berapa banyaknya cara pewarnaan ?

Kombinasi

Kombinasi r elemen dari n elemen adalah banyaknya pemilihan yang tidak terurut r elemen yang diambil dari n elemen.

Notasi

Dengan

Contoh 1 : 

Berapa banyaknya himpunan bagian dari A = {1,2,3,4,5} yang terdiri atas 3 elemen?

Jadi banyaknya himpunan bagian dari A yang beranggotakan 3 elemen adalah 10 buah, yaitu: 

{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5} 

Contoh 2 : 

Di antara 10 mahasiswa Teknik Informatika angkatan 2010, berapa banyaknya cara membentuk perwakilan yang beranggotakan 5 orang ? 

Jadi ada 252 cara untuk membentuk perwakilan beranggotakan 5 orang yang diambil dari 10 orang. 

Contoh 3: 

Salah satu mahasiswa dari 10 mahasiswa tersebut adalah Adi. Berapa banyaknya cara membentuk perwakilan yang terdiri atas 5 orang sedemikian sehingga Adi selalu menjadi bagian dari perwakilan? 

Karena Adi diasumsikan selalu terpilih, maka tinggal 4 orang anggota yang harus dipilih dari 9 orang. 

Contoh 4 : 

Terdapat 5 mahasiswi dan 3 mahasiswa. Berapa banyak cara membentuk kelompok yang terdiri atas 2 mahasiswi dan 2 mahasiswa? 

Banyaknya cara memilih 2 mahasiswi dari 5 mahasiswi adalah C(5,2) = 10 cara. 

Banyaknya cara memilih 2 mahasiswa dari 3 mahasiswa adalah C(3,2) = 3 cara 

Maka banyaknya cara memilih 2 mahasiswi dan 2 mahasiswa adalah C(5,2).C(3,2)=10.3=30 cara.

Latihan 6

Ada 7 orang mahasiswa dari Jurusan Matematika dan 8 orang mahasiswa jurusan Informatika. Akan dibentuk kelompok beranggotakan 4 orang. Bagaimana cara membentuk kelompok jika banyaknya mahasiswa jurusan Matematika yang terpilih harus sama dengan banyaknya mahasiswa jurusan Informatika ?

Kombinasi Bentuk Umum

Jika ada n bola yang tidak semuanya berbeda warna.

Misalnya :

n1 bola berwarna merah

n2 bola berwarna hijau

…

nk bola berwarna kuning

maka kombinasi n bola ini dirumuskan sebagai berikut :

Contoh : 

Terdapat 8 buah buku. Bagaimana cara membagi buku sehingga A akan mendapat 4 buku, B mendapat 2 buku, dan C mendapat 2 buku? 

Kombinasi dengan Pengulangan

Banyaknya kombinasi dari r buah objek yang diambil dari n buah objek dimana pengulangan diperbolehkan adalah C(n+r-1,r). 

Contoh 1 :

Akan dibagikan 10 jeruk kepada 3 orang anak sedemikian sehingga setiap anak boleh mendapat lebih dari 1 jeruk. Berapa banyaknya cara pembagian ini? 

n = 3, r = 10

Banyaknya cara pembagian adalah C(3+10-1,10) = C(12,10)

Contoh 2 : 

Terdapat kumpulan bola berwarna merah, hijau, kuning. Banyaknya masing-masing bola setidaknya 8 buah. Berapa banyak cara memilih 8 buah bola jika paling sedikit 1 bola dari masing-masing warna terpilih ? 

Diketahui n = 3 dan r = 8. 

Karena setidaknya 1 bola dari masing-masing warna harus terpilih, maka tinggal 5 bola yang harus dipilih.

Maka cara memilih 5 bola ini adalah C(3+5-1,5)=C(7,5) 

Latihan 7

Dari sejumlah besar CD berisi program aplikasi A, B, C, D, dan E, berapa banyak cara 10 CD dapat diambil ?