Slide Tugas Pertemuan 6 Matematika Diskrit: Aljabar Boolean

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

Slide Tugas Pertemuan 3 Matematika Diskrit: Kuantor dan Induksi Matematika

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.

Slide Tugas Pertemuan 4 Matematika Diskrit: Kombinatorial

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

By: Farhan & Hafiz