PERTEMUAN 12

SIMPUL ASAL    SIMPUL TUJUAN        LINTASAN TERPENDEK                  JARAK
            1                              3                         1,3                                                          10
            1                              4                         1,3,4                                                       25
            1                              2                         1,3,4,2                                                    45
            1                              5                         1,5                                                          45
            1                              6                          -                                                              -

Lintasan Terpendek adalah dari simpul asal 1 ke simpul 3

PERTEMUAN 9

Nyatakan fungsi Boolean berikut ke dalam bentuk rangkaian pensaklaran dan rangkain digital.
1) f(x,y,z) = x'y + (x'+ xy)z + x(y+y'z+z)
2) f(x,y) = xy' + x'y
3) f(x,y,z) = xy + xy'z + y(x'+z) + y'z'

1)

 2) 

3)

Hasil Penyederhanaan: f(x,y,z) = yz +xz'
Latihan:
a. Sederhanakan dengan cara Aljabar
1. f(x,y,z) = x'y'z + x'yz + xy'
    --->      = x'z(y '+ y) + xy'
    --->      = x'z.1 + xy'
    --->      = x'z + xy'
2. f(x,y,z) = xy + x'z + yz
    --->      = xy + x'z + yz(x+x')
    --->      = xy + x'z + xyz + x'yz
    --->      = xy + xyz + x'z + x'zy
    --->      = xy(1 + z) + x'z(1 + y)
    --->      = xy + x'z
3. f(x,y,z) = (x + y)(x' + z)(y + z)
    --->      = (x + y)(x' + z)(y + z)
    --->      = xy. x'z. yz
    --->      = x'yz . yz
    --->      = x' + yz

b. Sederhanakan dengan metode Peta Karnaugh dan gambarkan rangkaian logika sebelum dan setelah
    disederhanakan
    f(x,y,z) = x'yz + x'yz' + xy'z' + xy'z  

Rangkaian Logika

Tabel Peta Karnaugh

PERTEMUAN 6

Buktikan bahwa untuk sembarang elemen a dan b dari aljabar Boolean :
(i). a+a'b=a+b
(ii).a(a'+b)=ab
(iii).a+1=1
(iv).(ab)'=a'+b'
Jawab:
(i). a+a'b=(a+ab)+a'b    penyerapan
              =a+(ab+a'b)    Asosiatif
              =a(a+a')b        Distributif
              =a+1.b            Komplemen
              =a+b               Identitas

(ii). a(a'+b)=aa'+ab      distributif
                  =0+ab        Komplemen
                  =ab            Identitas

(iii). a+1=a+(a+a')    Komplemen
              =(a+a)+a'    Asosiatif
              =a+a'           Idempoten
              =1               Komplemen

(iv). (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+(yz'+y'z)'
                = x+(yz')'(y'z)'
                = x+(y'+z(y+z')

2. f'(x)=x'

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

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

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

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

PERTEMUAN 4

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 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

PERTEMUAN 3

1. Tentukan Validitas pernyataan dibawah ini bila domain pembicaraannya himpunan bilangan real
a) ∀x, ∀y, P(x² < y + 1)                         b) ∀x, ∀y, P[(x < y) → (x² < y²)]
    ∀x, ∃y, P(x² < y + 1)                              ∀x, ∃y, P[(x < y) → (x² < y²)]
    ∃x, ∀y, P(x² < y + 1)                              ∃x, ∀y, P[(x < y) → (x² < y²)]
    ∃x, ∃y, P(x² < y + 1)                               ∃x, ∃y, P[(x < y) → (x² < y²)]
    Jawaban: a) Semua bilangan real dalam himpunan x dan himpunan y yang merupakan
                        bilangan real. Bilangan x real dapat dibagi habis dengan bilangan y real.
                        Setiap ada bilangan real dari himpunan y dan semua dari himpunan x. Bilangan-
                        bilangan x dapat dibagi habis oleh beberapa bilangan y.
                        Beberapa ada bilangan real dari himpunan x dan semua dari himpunan y.
                        Bilangan x tidak dapat dibagi habis oleh semua bilangan y dinyatakan salah.
                        Beberapa bilangan x dan juga beberapa bilangan y. Harusnya kalau dihitung bilangan
                        tersebut dengan operator < bahwa tidak benar.
                    b) Semua bilangan real dalam himpunan x dan himpunan y merupakan bilangan real. Jika himpunan x kurang dari himpunan y maka himpunan x² kurang dari himpunan y².
Semua bilangan  x adalah bilangan real dan beberapa himpunan y adalh bilangan real. Jika anggota himpunan x kurang dari anggota himpunan y maka anggota himpunan x² kurang dari anggota himpunan y². Beberapa amggota himpunan x adalah bilangan real dan semua anggota himpunan y adalah bilangan real. Jika anggota himpunan x kurang dari anggota himpunan y maka anggota himpunan x² kurang dari anggota himpunan y². Beberapa anggota himpunan x adalah bilangan real dan beberapa anggota himpunan y adalah bilangan real. Jika anggota himpunan x kurang dari anggota himpunan y maka anggota himpunan x² kurang dari anggota himpunan y².
                       
2. Negasikan setiap pernyataan dibawah ini:
    a) ∀x, P(x) ∧ ∃y, Q(y)
    b) ∃x, P(x) ∨ ∀y, Q(y)
    c) ∀x, ∃y, [P(x) ∨ Q(y)] 
    Jawaban: a) ~ [∀x, P(x) ∧ ∃y, Q(y)]
                       = ∃x, ~P(x) ∨ ∀x, ∼Q(y)
                    b) ~ [∃x, P(x) ∧ ∀y, Q(y)]
                       = ∀x, ~P(x) ∨ ∃y, ~Q(y)
                    c) ~ [∀x, ∃y, [P(x) ∨ Q(y)]
                       = ∃x, ∀y, [~P(x) ∧ ~Q(y)]

Induksi Matematika
Buktikan dengan induksi matematik
1. Jumlah n buah bilangan ganjil positif pertama adalah n²
    Jawaban: Basis induksi: p(1) benar, karena jumlah satu buah bilangan ganjil positif pertama adalah
                   1²=1
                    Langkah induksi: misalkan p(n) benar, yaitu asumsikan bahwa
                    1 + 3 + 5 + .... + (2n-1) = n²
                    adalah benar (hipotesis induksi) [catatlah bahwa bilangan ganjil positif ke-n adalah
                    (2n-1)]
                    Kita harus memperlihatkan bahwa p(n + 1) juga benar, yaitu
                    1 + 3 + 5 +....+ (2n-1) + (2n + 1) = (n + 1)²
                    Hal ini dapat kita tunjukkan sebagai berikut:
                    1 + 3 + 5 + .... + (2n - 1) + (2n + 1) = [1 + 3 +5 + .... + (2n-1) + (2n + 1)
                                                                             = n² + (2n + 1)
                                                                             = n² + 2n + 1
                                                                             = (n + 1)²
2. Untuk semua n ≥ 1, buktikan dengan induksi matematik bahwa n³ + 2n adalah kelipatan 3.
    Jawaban: Basis Induksi: p(1) benar, karena untuk n = 1, 1³ + 2(1) = 3 adalah kelipatan 3.
                    Langkah induksi: misalkan p(n) benar, yaitu proposisi
                                  n³ + 2n adalah kelipatan 3
                   diasumsikan benar (hipotesis induksi). Kita harus memperlihatkan bahwa p(n + 1) juga
                   benar, yaitu
                   (n + 1)³ + 2(n+1) adalah kelipatan 3
                  Hal ini dapat kita tunjukkan sebagai berikut:
                  (n + 1)³ + 2(n + 1) = (n³ + 3n³ + 3n + 1) + (2n + 2)
                                                = (n³ + 2n) + 3n² + 3n + 3
                                                = (n³ + 2n) + 3(n² + n + 1)

3. 1.2 + 2.3 + 3.4 + .... + n(n + 1) = n(n + 1)(n + 2)/3
    Untuk n = 1
    1.2 + 2.3 + .... + n(n + 1) = (n(n + 1)(n + 2 ))/3
    1(1 + 1) = (1(1 + 1)(1 + 2))/3
    1(2) = (1(2)(3))/3
    2 = 2
    terbukti benar,
    untuk n = k
    1.2 + 2.3 + .... + k(k + 1) = (k(k + 1)(k + 2))/3

    Uji untuk n = k + 1
    1.2 + 2.3 + .... + n(n + 1) = (n(n + 1)(n + 2))/3
    1.2 + 2.3 + .... + k(k + 1) + (k + 1)(k + 2) = ((k + 1)(k + 1 + 1)(k + 1 + 2))/3
    1.2 + 2.3 + .... + k(k + 1) + (k + 1)(k + 2) = ((k + 1)(k + 2)(k + 3))/3
    (k(k + 1)(k + 2))/3 + (k + 1)(k + 2) = ((k + 1)(k + 2)(k + 3))/3
    k(k + 1)(k + 2) + 3(k + 1)(k + 2) = (k + 1)(k + 2)(k + 3)
    (k + 3)(k + 1)(k + 2) = (k + 1)(k + 2)(k + 3)
    terbukti benar.

PERTEMUAN 2

Latihan
Selidiki jenis Fungsi atau bukan, fungsi satu-ke-satu atau bukan, fungsi pada atau bukan.

1. A={1,2,3,4} dan B={u,v,w} diberikan f={(1,u),(2,v),(3,w)}
    Jawab: Fungsi satu-ke-satu 

2. A={1,2,3} dan B={u,v,w} diberikan f={(1,u),(1,v),(2,v),(3,w)}
    Jawab: Fungsi pada, bukan fungsi satu-ke-satu.

3. A={1,2,3} dan B={u,v,w,x} diberikan f={(1,w),(2,u),(3,v)}
    Jawab: Fungsi satu-ke-satu, bukan fungsi pada.

4. A={1,2,3} dan B={u,v,w} diberikan f= {(1,u),(2,u),(3,v)}
    Jawab: Fungsi pada.

5. A={1,2,3} dan B={u,v,w} diberikan f = {(1,u),(2,w),(3,v)}
    Jawab: Fungsi Satu-ke-satu,

PERTEMUAN 1

1. Kumpulan benda atau objek nyata maupun abstrak yang mempunyai sifat-sifat tertentu yang sama disebut.........

    a. Himpunan                    d.Kuasa

    b. Komutatif                    e. Assosiatif

    c. Gabungan

(Jawaban : a.Himpunan)

2. Notasi untuk menyatakan A anggota himpunan adalah.............

    A.          B.        C.     D.       E.

(Jawaban : B.)

3.A={Matematika diskrit, Automata, Rangkaian Digital}
   B={Automata, TRL}
   Maka operasi AB adalah...........
   a.{Matematika Diskrit}        d.{TRL}
   b.{Automata}                       e.{}
   c.{Rangkaian Digital}

(Jawaban : b.{Automata})

4.Dibawah ini yang termasuk hukum komutatif adalah.............
   a.AB=A                       b.(AB)C=A(BC)
   c.AU=U                      d.AU=A
   e.AB=BA

(Jawaban : e.AB=BA)

5.Jika A={Mouse, CPU} maka kuasa himpunannya ada..............
   a.1            b.2                c.3             d.4            e.0

(Jawaban : b.2)

--------------------------------------------------------------------------------------------------------------------------

1. Tuliskan dalam bentuk deskripsi himpunan berikut ini:
    A = { Adobe Photoshop, Macromedia Fireworks, PrintShopPro, GIMP, ....}
    B = { PHP, ASP, Cold Fusion, ....}
    C = { Windows, Linux, Unix, MacOS, OS/2, ....}
    D = { Disket, CD-R, Hardisk, ....}
    Jawaban : A = Himpunan dari Aplikasi manipulasi Foto dan Penggunaan Multimedia.
                     B = Himpunan dari Bahasa Pemrograman dan Framework pemgembang  perangkat lunak.
                     C = Himpunan dari Nama-nama Sistem operasi.
                     D = Himpunan dari Nama-nama media penyimpan data.

2. Misalkan semesta pembicaraan adalah Sistem Produksi Microsoft dan Himpunan-himpunan lainnya dinyatakan oleh:
    A = { win3.1, win3.11, win95, win97 }
    B = { win97, win98, win98SE, winME}
    C = { winME, win2000, winXP,....}
    Carilah: a) (A U B)-B          b) (A Ո B) U C'          c) (A ⊕ C) - C
                 d) (B-C) ⊕ A          e) (A Ո B) U (A Ո C)'

                 f) (A-B) Ո C'          g)2^A      h) 2^B

                   I) N_{A Ո B}        j)N_{A U B        
     Jawaban:  a) (}A U B)-B = (A-B) U (B-B) = A - B = {win3.1, win3.11, win95}
                      b) (A Ո B) U C' = (A U C') Ո (B U C')
                                               = (A U C') Ո (C' U B)
                                               = A U (C' Ո C') U B
                                               = A U B = {win3.1, win3.11, win95, win97, win98, win98SE, winME}

                     c)  (A ⊕ B) - C = ((A - B) U (B - A)) - C

                                             = ((A Ո  B') U (B Ո  A')) Ո C'
                                             =  {win3.11, win95, win98, win98SE}
                     d) (B-C) ⊕ A = {win3.1, win3.11, win95, win98, win98SE, win2000, winXP}
                     e) (A Ո B) U (A Ո C)' = (A Ո B) U (A' U C')
                                                       = {win97, win98, win98SE, winME}
                     f) (A - B) Ո C' = {win3.1,win3.11,win95}
                     g)2^A =  {∅, {win3.1},{win3.11},{win95},{win97},{win3.1,win3.11}, {win3.1,win95},{win3.1,win97}, {win3.11,win95}, {win3.11,win97}, {win95,win97}, {win3.1,win3.11,win95}, {win3.1,win3.11,win97}, {win3.11,win95,win97},{win3.1,win3.11,win95,win97}, 
                     h) 2^B = {win97,},{win98},{win98SE},{winME},{win97,win98},{win97,win98SE},{win98,win98SE},{win98SE,winME},{win98,winMe},{win97,winME},{win97,win98,win98SE},{win97,win98,winME},{win98,win98SE,winME},{win97,win98SE,winME},
                     i) N_{A Ո B   = 1}
                     j) NA U B= {win3.1,win3.11,win95,win97,win98,win98SE,winME}=7

3.  Dari 35 orang programmer yang mengikuti wawancra untuk sebuah pekerjaan diketahui
      25 menguasai Pascal
      28 menguasai C++
      2 tidak menguasai keduanya
    Berapakah yang mengusai keduanya?

    Programmer = U = 35.                          Pascal = N(P) = 25
    C++ = N(C) = 28                                   Tidak keduanya = N(AՈB)' = 2

    N(AՈB) = N(P)+N(C) - U
                  = (25+28) - 35
                  = 53 - 35 = 18 orang
     18 orang yang menguasai keduanya.