Matematika Diskrit Pertemuan 13

1.Graf tak berarah terhubung yang tidak mengandung sirkuit disebut…….

a.Pohon                                                       b.Binary             

c.Akar                                                          d.Level

e.Anak                                                         (Jawaban yang benar : a.Pohon)

2.Sisi pada pohon rentang disebut dengan……

a.Tali hubung                                              b.Cabang

c.akar                                                           d.Rank

e.Upapohon                                                 (Jawaban yang benar : b. Cabang)

3.Metode yang digunakan untuk menyelesaikan pohon rentang minimum adalah…….

a.Algoritma Prim                                          b.Algoritma Kruskal

c.Traveling Salesman                                   d.a dan c benar

e.a dan b benar                                             (Jawaban yang benar : a.Algoritma Prim)

4.Di bawah ini yang bukan terminologi pohon adalah……

a.Anak                                                         b.Lintasan

c.Sirkuit                                                       d.Derajat

e.Daun                                                         (Jawaban yang benar : c.Sirkuit)

5.Pohon biner dengan daun berupa operand dan simpul dalam

berupa operator disebut dengan pohon………

a.Keputusan                                                 b.Huffman

c.Prefiks                                                       d.Ekspresi

e.Pencarian biner                                        (Jawaban yang benar : d. Ekspresi)

Matematika Diskrit Pertemuan 14

1.Suatu bahasa yang harus mengikuti aturan bahasa pemrograman dan bahasa matematis seperti aljabar dan logika proposisi disebut bahasa……

a.Formal                                                   b.Natural            

c.Verbal                                                    d.Frasa

e Automata                                              (Jawaban yang benar : a.Formal)

2.Jenis tata bahasa dalam bahasa formal terdiri dari…..

a.1                                                              b.2

c.3                                                              d.4

e.5                                                             (Jawaban yang benar : c.3)

3.Level terendah dari hirarki mesin dan bahasa disebut......

a.Formal                                                      b.Natural            

c.Verbal                                                       d.Frasa

e.Automata terhingga                                (Jawaban yang benar: e. Automata terhingga)

4.Dalam diagram transisi untuk menyatakan string yang valid telah dikenali ditandai dengan……

a.Busur                                                      b.Lingkaran ganda          

c.Simbol                                                    d.Kategori

e. inisiasi                                                   (Jawaban yang benar :  b.Lingkaran ganda)

5.Tokoh penemu mesin Turing adalah…..

a.Alan                                                       b.Automata       

c.Alan Turing                                           d.James Turing

e.David Turing                                         (Jawaban yang benar : c.Alan Turing)

Matematika Diskrit Pertemuan 12

Matematika Diskrit

Pertemuan 12

1. Untuk merepresentasikan graf ada ……..cara

a. 1

b. 2

c. 3

d. 4

e. 5

Jawaban : c. 3

2. Dua buah graf  disebut graf…….

a. Isomorfik

b. Dual

c. Euler

d. Hamilton

e. Planar

Jawaban : a. Isomorfik

3. Untuk menyatakan jumlah wilayah dalam graf dinotasikan dengan…….

a. n

b. f

c. e

d. s

e. r

Jawaban : b. f

4. Lintasan atau sirkuit yang melalui sisi-sisi graf tepat satu kali disebut…..

a. Isomorfik

b. Dual

c. Planar

d. Euler

e. Hamilton

Jawaban : d. Euler

5. Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut graf……..

a. Isomorfik

b. Dual

c. Planar

d. Euler

e. Hamilton

Jawaban : c. Planar

Matematika Diskrit Pertemuan 11

1. Himpunan simpul-simpul yang dihubungkan oleh sisi-sisi disebut…….

a. Graf

b. Pohon

c. vertex

d. edges

e. node

Jawaban : a. Graf

2. Graf yang tidak mengandung gelang maupun sisi ganda disebut graf…….

a. Berhingga       

b. Sederhana      

c. Berarah

d. Tak sederhana

e. Tak berhingga

Jawaban : b. Sederhana      

3. Dalam pengujian program kita menerapkan jenis graf…..

a. Sederhana

b. Tak berarah

c. Berarah

d. Tak sederhana

e. Tak berhingga

Jawaban : c. Berarah

4. Lintasan elementer dengan simpul awal sama dengan simpul akhir disebut…….

a. Derajat

b. Terhubung

c. Simpul terpencil

d. Siklus

e. Pohon

Jawaban : d. Siklus

5. Jumlah sisi pada graf lengkap dirumuskan dengan…….

a. n-1

b. (n-1)/2

c. nr/2

d. 2n

e. n(n-1)/2

Jawaban : e. n(n-1)/2

Matematika Diskrit Pertemuan 10

1. Langkah-langkah logis untuk menyelesaikan masalah disebut dengan….....

a. Algoritma        

b. Notasi O-besar

c. Rekurensi

d. Fungsi 

c. Rekurensi     

e. Relasi

Jawaban : a. Algoritma        

                  

2. Permasalahan pencarian biner akan optimal jika menggunakan algoritma waktu….

a. O(1)                 

b. O(n!)               

c. O(log n)          

d. O(n log n)

e. O(n)     

Jawaban : c. O(log n)          

3. Jenis cara pencarian data ada…..

a. 1                                               

b. 2

c. 4                    

d. 5  

e. 6                  

Jawaban : a. 1                     

4. Data 27 80 02 46 16 12 50

jika diurutkan  dengan metode seleksi maka pada langkah ke-3 diperoleh urutan……

a. 02 80 27 46 16 12 50

b. 02 12 27 46 16 80 50

c. 02 12 16 46 27 80 50      

d. 02 12 16 27 46 80 50

e. 02 12 16 27 46 80 50

Jawaban : c. 02 12 16 46 27 80 50      

5. Kemampuan memanggil dirinya sendiri dengan parameter berbeda sampai pengulangan berenti disebut…

a. Algoritma           

b. Notasi O-besar

c. Relasi               

d. Fungsi             

e. Rekurensi

Jawaban : e. Rekurensi

Essay

Data 27 80 02 46 16 12 50

Cari urutan ke-3 pada metode

1.bubble sort

2.insertion sort

3.merge sort

Jawaban :

1.Bubble  sort

27 80 02 46 16 12 50

02 27 80 46 16 12 50  ------> iterasi 1

02 12 27 80 46 16 50  ------> iterasi 2

02 12 16 27 80 46 50 ------> iterasi 3

2.Insertion sort

27 80 02 46 16 12 50

27 02  46 16 12 50 80 -----> iterasi 1

27 02 16 12 46 50 80 -----> iterasi 2

02 16 12 27 46 50 80 -----> iterasi 3

3.Merge sort

27 80 02 46 16 12 50

(27-80) (02-46) (12-16) (50-x) -----> iterasi 1

(02-27-46-80) (12-16-50-x)     -----> iterasi 2

(02-12-16-27-46-50-80-x)       -----> iterasi 3

Matematika Diskrit Pertemuan 9

1. Fungsi Boolean yang dinyatakan sebagai jumlah dari hasil kali,hasil kali dari jumlah dengan setiap suku mengandung literal yang lengkap disebut dengan……...

a. Literal                                               

b. Suku/term

c. Kanonik

d. Komplemen

e. Baku

Jawaban : c. Kanonik

2. Di bawah ini yang merupakan jenis-jenis bentuk kanonik adalah……..

a. Minterm       

b. Maxterm      

c. SOP

d. POS

e. Benar semua

Jawaban : e. Benar semua

3. Dalam aplikasi fungsi boolean dalam jaringan pensaklaran operasi perkalian merupakan bentuk hubungan……

a. Seri                    

b. Paralel           

c. Seri-paralel

d. Tertutup

e. Terbuka

Jawaban : a. Seri

4. Dalam aplikasi fungsi boolean daalam rangkaian digital elektronik negasi dari perkalian disebut……

a. AND                

b. NAND                            

c. OR

d. NOR

e. XOR

Jawaban : b. NAND

5. f(w,x,y,z) = wxy’z’ + wxy’z + wx’y’z’ + wx’y’z jika disederhanakan menjadi…….

a. f(w,x,y,z) = wx                           

b. f(w,x,y,z) = xy’                           

c. f(w,x,y,z) = wy

d. f(w,x,y,z) = wy’

e. f(w,x,y,z) = yz

Jawaban : d. f(w,x,y,z) = wy’

Matematika Diskrit Pertemuan 6

1.Aljabar yang terdiri atas suatu himpunan dengan operasi jumlah/disjungsi, kali/konjungsi dan komplemen/negasi serta elemen 0 dan 1 disebut …

A. Pernyataan     D. Geometri

B. Aritmatika     E. Aljabar Boolean

C. Aljabar Real

Jawaban : E. Aljabar Boolean

2.Dibawah ini yang merupakan hukum dominasi adalah …

A. a + 0 = a      D. a + 1 = 1

B. a.a = a        E. a.b = b.a

C. a + a’ = 1

Jawaban : D. a + 1 = 1

3.Peubah dalam Boolean disebut dengan …

A. Relasi         D. Komplemen

B. Literal        E. Variabel

C. Fungsi

Jawaban : E. Variabel

4.f(x,y) = x’y + xy’ + y’ jika dicari komplemennya menjadi …

A. f’(x,y) = (x+y’)(x’+y)y(x+y’)y’  D. f’(x,y) = (x’ + y)

B. f’(x,y) = xy’ + x’y + y          E. Salah semua

C. f’(x,y) = x’y + xy’ + y’

Jawaban : B. f’(x,y) = xy’ + x’y + y

5.f(x,y) = x’y +xy’ + y’ jika dicari bentuk dualnya menjadi …

A. f’(x,y) = (x+y’)(x’+y)y(x+y’)y’  D. f’(x,y) = (x’ + y)

B. f’(x,y) = xy’ + x’y + y          E. Salah semua

C. f’(x,y) = x’y + xy’ + y’

Jawaban : B. f’(x,y) = xy’ + x’y + y

ESSAY

Buktikan bahwa untuk sembarang elemen a dan b dari aljabar Boolean :

1.a(a'+b)=ab

2.a+1=1

3.(ab)'=a'+b'

Jawab:

1. a(a'+b)= aa'+ab          Distributif

          = 0+ab            Komplemen

          = ab              Identitas

2. a+1 = a+(a+a')           Komplemen

       =(a+a)+a'            Asosiatif

       = a+a'               Idempoten

       = 1                  Komplemen

3. (ab)'= ab.a'+abb'        Dsitributif

        = 0.b+a.0           Komplemen

        = 0+0               Dominansi

        = 0                 Identitas

Cari Komplemen Dari:

1. f(x,y,z)=x'(yz'+y'z)

2. f(x)=x

3. f(x,y)=x'y+xy'+y'

4. f(x,y)=x'y'

5. f(x,y)=(x+y)'

6. f(x.y,z)=xyz'

jawab:

1. f(x,y,z) = x’(yz’ + y’z)

            = x(y’z + yz’)

2. f(x) = x

        = x’

3. f(x,y) = x’y + xy’ + y’

          = xy’ + x’y + y

4. f(x,y) = x’ y’

          = xy

5. f(x,y) = (x+y)’

          = (x’+y’)

          = (x+y)

6. f(x,y,z) = xyz’
            = x’y’z

Matematika Diskrit Pertemuan 5

1. Suatu kalimat yang bernilai benar atau salah saja disebut…..

a. Deklarasi         

b. proposisi       

c. Pernyataan

d. disjungsi

e. Implikasi

Jawaban : c. Pernyataan

2. p = hari ini saya kuliah matematika diskrit, jika dicari negasinya maka hasilnya……

a. Hari ini saya tidak kuliah matematika diskrit

b. Besok saya kuliah matematika diskrit

c. Saya kuliah matematika diskrit

d. Hari ini saya kuliah automata

e. semua salah

Jawaban :  a. Hari ini saya tidak kuliah matematika diskrit

3. Jika p benar, q salah dan r benar, maka proposisi di bawah ini yang mempunyai nilai kebanaran ‘salah’ adalah……..

a. (pÚq)→r

b. (pÙq)→r

c. (pÙ~q)Úr

d. (pÚq)→~r

e. (pÚq)Úr

Jawaban :  d. (pÚq)→~r

4. Kumpulan pernyataan – pernyataan atau premis-premis atau dasar pendapat serta kesimpulan(konklusi) disebut dengan…..

a. Premis

b. Argumen

c. Pernyataan

d. Proposisi

e. Validitas

Jawaban : b. Argumen

5. 1. Jika saya rajin belajar maka nilai saya bagus

   2. Saya rajin belajar Dari dua argumen di atas maka kesimpulan yang diperoleh yaitu……..

a. Nilai saya tidak bagus

b. Saya tidak rajin belajar

c. Nilai saya bagus

d. Saya rajin belajar

e. Semua benar

Jawaban :  c. Nilai saya bagus

ESSAY I
Selidiki apakah kedua proposisi dibawah ini setara:

1. P(1) = Tidak benar bahwa system bilangan biner dipergunakan dalan system digital atau system digital hanya dapat mengasumsikan nilai yang berlainan.

2. p(2) = Sistem bilangan biner tidak dipergunakan dalam system digital dan tidak benar bahwa system digital hanya dapat mengasumsikan nilai yang berlainan.

(hint: buktikan : ~( p Ú q ) º ~ p Ù ~ q )

Jawaban :

Kedua Proposisi di atas dapat di tulisakan dengan notasi sebagai berikut:

1.~(p v q)

2.~p^~q

Sehingga tabel kebenaran nya sebagai berikut :

Jadi,kedua proposisi tersebut setara atau ~(p v q) º~p ^ ~q

3. Tentukan konvers, invers, dan kontrapositif dari proposisi berikut:

Jika Ms Word aplikatifnya maka windows sistem operasinya

Jawaban :

Konvers = “jika windows sistem operasinya , maka Ms Word aplikatifnya”

Invers  =”jika Bukan Ms Word aplikasinya, Maka Bukan Windows sistem operasinya”.

Kontraposisi=”jika bukan Windows sistem operasinya, maka Bukan Ms Word Aplikatifnya”.

Tabel Kebenaran

Jadi dapat disimpulkan bahwa proposisi yang saling kontra-positip mempunyai nilai kebenaran yang sama (ekuivalen).

Berdasarkan sifat tersebut maka kita dapat membuktikan suatu dalil dalam bentuk implikasi melalui nilai kebenaran kontra-positipnya.

ESSAY II

Beri Argumen dan Tulis Simbolnya

1. Jika harga gula naik, maka pabrik gula akan senang.

Jika pabrik gula senang, maka petani tebu akan senang.

Jadi, jika harga gula naik,maka petani tebu akan senang

Jawaban:

Hypothetical syllogism

p → q

q → r

p → r

2. Jika lampu lalu lintas menyala merah, maka semua kendaraan akan berhenti.

Lampu lalu lintas menyala merah.

Jadi,dengan demikian semua kendaraan akan berhenti

Jawaban:

Modus Ponens

p → q

p

؞q

3. Program computer ini memiliki bug, atau menginputnya salah.

Inputnya tidak salah.

Jadi,dengan demikian, program komputer ini memiliki bug

Jawaban:

Disjunctive syllogism

p v q

~ p

؞q

4. Jika saya makan, maka saya akan kenyang.

Saya tidak kenyang.

Jadi, Dengan demikian, saya tidak kenyang

Jawaban:

Modus Tollens

p → q

~ q

؞~ p

Matematika Diskrit Pertemuan 4

1. Kaidah dasar perhitungan yaitu penjumlahan dan perkalian digunakan dalam

a. Kombinatorial

b. Permutasi

c. Kombinasi

d. Relasi

e. Induksi matematika

Jawaban =  a. Kombinatorial

2. Suatu pengurutan data dimana urutan tidak diperhatikan adalah definisi .....

a. Permutasi

b. Kombinasi

c. Himpunan

d. Relasi

e. Fungsi

Jawaban = b. Kombinasi

3. Penyusunan obyek dimana sebagian obyek sama disebut dengan .....

a. Permutasi bentuk umum

b. Kombinasi bentuk umum

c. Kombinasi perulangan

d. Permutasi perulangan

e. a dan b benar

Jawaban = e. a dan b benar

4. Hasil perhitungan dari P(8,3) adalah ....

a. 6720

b. 240

c. 336

d. 520     

e. 56

Jawaban = c. 336

5. Hasil perhitungan dari C((6,3)C(4,2) adalah ....

a. 2   

b. 6    

c. 1440

d. 120    

e. 144

Jawaban = c. 1440

ESSAY

1.Empat buah ujian dilakukan dalam periode enam hari. Berapa banyak pengaturan jadwal yang dapat dilakukan sehingga tidak ada dua ujian atau lebih yang dilakukan pada hari yang sama?
6!/(4-2)! = 6! / 2! = 6 x 5 x 4 x 3 x 2 x 1 / 2 x 1 = 360

2.anggap metode kode berupa susunan huruf dulu baru susunan angka

banyak caranya

= banyak cara menyusun huruf × banyak cara menyusun angka

= 26P4 × 10P3

= 26×25×24×23×10×9×8 = 258.336.000

3.Berapakah jumlah kemungkinan membentuk 3 angka

dari 5 angka berikut: 1, 2, 3, 4 , 5, jika:

(a) tidak boleh ada pengulangan angka, dan

(b) boleh ada pengulangan angka.

Penyelesaian:

(a) Dengan kaidah perkalian: (5)(4)(3) = 60 buah

Dengan rumus permutasi P(5, 3) = 5!/(5 – 3)!=5!/2!= 60

(b) Tidak dapat diselesaikan dengan rumus permutasi.

Dengan kiadah perkalian: (5)(5)(5) = 5pangkat3= 125.

4. String biner yang panjangnya 32 bit disusun oleh digit 1 atau 0. Berapa banyak string biner yang tepat berisi 7 buah bit 1
jawaban: C(32,7) = 3.365.856

5. Sebuah karakter dalam sistem ASCII berukuran 1 byte atau 8 bit (1 atau 0).

a. Berapa banyak pola bit yang terbentuk? (atau berapa banyak karakter yang dapat  dipresentasikan?)

b. Berapa banyak pola bit yang mempunyai 3 bit 1?

c. Berapa banyak pola bit yang mempunyai bit 1 sejumlah genap?

Jawaban: 

a. Karakter ASCII dalam urutan 0,1,2,3,4,5,6,7

   Posisi 0 dapat diisi dengan 2 cara (1 atau 0)

   Posisi 1 dapat diisi dengan 2 cara (1 atau 0)

   Posisi 2 dapat diisi dengan 2 cara (1 atau 0)

   Posisi 3 dapat diisi dengan 2 cara (1 atau 0)

   Posisi 4 dapat diisi dengan 2 cara (1 atau 0)

   Posisi 5 dapat diisi dengan 2 cara (1 atau 0)

   Posisi 6 dapat diisi dengan 2 cara (1 atau 0)

   Posisi 7 dapat diisi dengan 2 cara (1 atau 0)

   Semua posisi harus diisi, jadi jumlah pola bit yang terbentuk

   = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 2^8

b. Kombinasi dari delapan dengan tiga atau C(n,r) = n!

   dengan r!(n-r)!

   C (8,3) = 8!/3!(8-3)! =  56

c. Banyaknya pola bit yang mempunyai 0 buah bit 1 = C(8,0)

   Banyaknya pola bit yang mempunyai 2 buah bit 1 = C(8,2)

   Banyaknya pola bit yang mempunyai 4 buah bit 1 = C(8,4)

   Banyaknya pola bit yang mempunyai 6 buah bit 1 = C(8,6)

   Maka banyak pola bit yang mempunyai bit 1 sejumlah genap 

   = C(8,0) + C(8,2) + C(8,4) + C(8,6) 

   = 40320 + 28 + 70 + 20160 = 60578

6.Suatu Panitia akan dibentuk dengan jumlah 5 orang. Berapa carakah pembentukan panitia tersebut  dapat dilakukan jika calon anggota terdiri dari 4 orang pria dan 3 orang wanita dan panitia harus

a. terbentuk tanpa persyaratan lain

b. terdiri 3 pria dan 2 wanita

c. terdiri 2 pria dan 3 wanita

Jawaban: 

a. Karena tidak ada persyaratan yang lain jika semua pria dan wantita ditentukan menjadi panitia.

C(4,4) + C(3,1) = 4!/0!.4! + 3!/2!.1!

= 1 + 3 = 4 cara

                    

b. C(4,3) + C(3,2) = 4!/3!.1! + 3!/1!.2! = 4 + 3 = 7 cara

                    

c.  C(4,2) + C(3,3) = 4!/2!.2! + 3!/0!.3! = 6 + 1 = 7 cara