Boolean Matematika Distrik

Definisi Boolean

Misalkan B adalah himpunan yang didefinisikan pada dua operasi biner, Ʌ dan V , dan sebuah operasi binary, dinotasikan ‘; misalkan 0 dan 1 menyatakan dua elemen yang berbeda dari B. maka sextuplet

   
      (B,  Ʌ  , V  , ‘, 0, 1)

disebut aljabar Boolean jika aksioma-aksioma berikut berlaku untuk setiap elemen x, y, z dari himpunan B:
1. Untuk setiap x dan y dalam B, ( hukum kumutatif)
     x v y = y v x
     x ᴧ y = y ᴧ  x

2. Untuk setiap x, y, dan z dalam B, ( hukum distributif)
    x ᴧ ( y v z) = ( x ᴧ y) (x ᴧ z)
    x v ( y ᴧ z) = ( x v y) ᴧ  (x v z)

3. Untuk setiap x dalam B,( hukum identitas)
    x v 0 = x
    x ᴧ 1 = x

4. Untuk setiap x dalam B, ( hukum negasi)
    x v x’ = 1
    x ᴧ x’ = 0

5. Untuk setiap x, y, dan z dalam B, ( hukumAsosiatif)
    (x v y) v z = y v (x v z)
    (x  ᴧ y) ᴧ  z = y ᴧ  (x ᴧ z)

Ekspresi Boolean
Misalkan (B, +, ∙ , ’) adalah sebuah aljabar Boolean.
Suatu ekspresi Boolean dalam (B, +, ∙ , ’) adalah:
(i)   Elemen di dalam B, ex : 0 dan 1
(ii)  Peubah / literal /  variabel, ex : a , b, c
(iii) jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 ∙ e2, e1’ adalah ekspresi  Boolean.

Contoh:
        0
        1
        a
        b
        a + b
        a ∙ b
        a’∙ (b + c)
        a ∙ b’ + a ∙ b ∙ c’ + b’, dan sebagainya

Mengevaluasi Ekspresi Boolean
Contoh :  a’ ∙ (b + c)
              Jika a = 0, b = 1 dan c = 0, maka hasil evaluasi ekspresi
              0’ ∙ (1 + 0) = 1 ∙ 1 = 1

Dua ekspresi Boolean dikatakan ekivalen (di lambangkan dengan ‘=’) jika keduanya bernilai sama untuk setiap nilai-nilai pada n peubah.

Contoh :  a ∙ (b + c) = (a ∙ b) + (a ∙ c)
# Catatan : tanda titik (∙) dapat hilang dari penulisan ekpresi Boolean, kecuali :
(i)    a(b + c) = ab + ac
(ii)    a + bc = (a + b) (a + c)
(iii)    a ∙ 0 , bukan a0


Prinsip Dualitas
Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan operator
 +, ∙ , dan komplemen, maka jika pernyataan S* diperoleh dengan cara mengganti
                       ∙  dengan  +
                      +  dengan  ∙
                      0  dengan  1
                      1  dengan  0
dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S* disebut sebagai dual dari S.
Contoh:
(i)   (a ∙ 1)(0 + a’) = 0  dualnya (a + 0) + (1 ∙ a’) = 1
(ii)  a(a‘ + b) = ab       dualnya a + a‘b = a + b

Hukum-hukum Aljabar Boolean

Contoh:
Buktikan (i) a + a’b = a + b   dan   (ii) a(a’ + b) = ab
Penyelesaian:
    (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) adalah dual dari (i)



Fungsi Boolean
Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bn ke B melalui ekspresi Boolean, kita menuliskannya sebagai
        f : Bn → B
yang dalam hal ini Bn adalah himpunan yang beranggotakan pasangan terurut ganda-n (ordered n-tuple) di dalam daerah asal B. 

Misalkan sebuah fungsi Boolean adalah
f(x, y, z) = xyz + x’y + y’z

Fungsi f memetakan nilai-nilai pasangan terurut ganda-3
(x, y, z) ke himpunan {0, 1}.
Contohnya, (1, 0, 1) yang berarti x = 1, y = 0, dan z = 1
sehingga f(1, 0, 1) = 1 ∙ 0 ∙ 1 + 1’ ∙ 0 + 0’∙ 1 = 0 + 0 + 1 = 1


Bentuk Kanonik
Ada 2 macam bentuk Kanonik:
1. Penjumlahan dari hasil kali (Sum Of Product / SOP)
Contoh :   f(x,y,z) = x’y’z + xy’z’ + xyz
           Setiap suku (term) disebut minterm

2. Perkalian dari hasil jumlah (Produck Of Sum / POS)
Contoh :  g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)
                   (x’ + y + z’)(x’ + y’ + z) 
           Setiap suku (term) disebut maxterm

Konversi Antar Bentuk Kanonik
Misalkan
f(x, y, z)    = ∑ (1, 4, 5, 6, 7)

dan f ’adalah fungsi komplemen dari f,

f ’(x, y, z) = ∑ (0, 2, 3)  = m0+ m2 + m3

Dengan menggunakan hukum De Morgan, kita dapat memperoleh fungsi f dalam bentuk POS:

    f ’(x, y, z)  = (f ’(x, y, z))’ = (m0 + m2 + m3)’
               = m0’ . m2’ . m3’
                     = (x’y’z’)’ (x’y z’)’ (x’y z)’
            = (x + y + z) (x + y’ + z) (x + y’ + z’)
            = M0 M2 M3
            = ∏ (0,2,3)

Jadi,  f(x, y, z) = ∏ (1, 4, 5, 6, 7) = ∏ (0,2,3).

Kesimpulan: mj’ = Mj

Aplikasi Aljabar Boolean

1. Jaringan Pensaklaran (Switching Network)

Saklar adalah objek yang mempunyai dua buah keadaan: buka dan tutup. 

Tiga bentuk gerbang paling sederhana:

Rangkaian Digital Elektronik

Penyederhanaan Fungsi Boolean

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

disederhanakan menjadi

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

Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara:
1. Secara Aljabar
Contoh :
f(x,y,z) = xy + x’z + yz
       = xy + x’z + yz(x + x’)
       = xy + x’z + xyz + x’yz
       = xy (1 + z) + x’z(1 + y)
       = xy + x’z

2. Menggunakan Peta Karnaugh
    Peta Karnaugh dengan 2 Peubah

    Peta Karnaugh dengan 3 Peubah

  Peta Karnaugh dengan 4 Peubah

3. Menggunakan Metode Quine Mc Cluskey (Metode Tabulasi)
    a. Pasangan : dua buah 1 yang bertetangga

Fungsi Matematika Distrik

Definisi Fungsi

Diberikan dua himpunan A dan B Relasi biner f dari A ke B merupakan suatu fungsi jika setiap elemen di dalam A dihubungkan dengan tepat satu elemen di dalam B.
Jika f adalah fungsi dari A ke B  kita menuliskan
 f : A → B
yang artinya f memetakan A ke B.
A disebut daerah asal (domain) dari f dan B disebut daerah hasil (codomain) dari f.
Nama lain untuk fungsi adalah pemetaan atau transformasi.
Kita menuliskan f(a) = b jika elemen a di dalam A dihubungkan dengan elemen b di dalam B.
Jika f(a) = b, maka b dinamakan bayangan (image) dari a dan a dinamakan pra-bayangan (pre-image) dari b.
Himpunan yang berisi semua nilai pemetaan f disebut jelajah (range) dari f. Perhatikan bahwa jelajah dari f adalah himpunan bagian (mungkin proper subset) dari B.

Jenis Fungsi

Fungsi injektif (injective)
Fungsi f dikatakan one-to-one atau injektif (injective) apabila a dan b anggota himpunan A maka f(a) ≠ f(b) bilamana a ≠ b untuk f(a) dan f(b) anggota himpunan B.

 
 






Fungsi injektif (injective)
Fungsi f dikatakan one-to-one atau injektif (injective) apabila a dan b anggota himpunan A maka f(a) ≠ f(b) bilamana a ≠ b untuk f(a) dan f(b) anggota himpunan B

 








Fungsi bijeksi(bijection)
Fungsi f dikatakan berkorespodensi satu-satu atau bijeksi(bijection) apabila ia fungsi one-to-one dan surjective.
Contoh:
Fungsi f = {(1,a),(2,b),(3,c)}
dari X = {1,2,3} ke Y = {a,b,c}
→bijeksi 

 






Fungsi Invers
Apabila f merupakan fungsi berkorespondensi satu-satu dari himpunan A ke himpunan B maka fungsi tersebut mempunyai invers yaitu f ' y) = x , untuk x ∈ A dan y ∈ B, f ' merupakan invers dari fungsi f.


Komposisi Fungsi
Komposisi dari dua fungsi f dan g dinyatakan f°g, f merupakan fungsi yang memetakan anggota himpunan A ke himpunan B dan fungsi g memetakan anggota himpunan B ke himpunan C. Fungsi dari himpunan A ke himpunan C didefinisikan f° g(x) = f( g(x)), x ∈ A 

Beberapa Fungsi Khusus

Fungsi Floor (batas bawah)
Batas bawah dari x adalah bilangan bulat terbesar yang kecil dari atau sama dengan x. Dengan notasi └ ┘ Contoh: 
└8.3┘ = 8 
└-8.7┘ = -9

Fungsi Ceiling (batas atas)
Batas atas dari x adalah bilangan bulat terkecil yang lebih besar atau sama dengan x. Dengan notasi ┌  ┐         
Contoh: 
┌ 6 ┐   = 6             Г-11.3˥ = -11
 Г 9 ˥    = 10          Г-8˥      = -8

Fungsi Modulu
Jika x adalah bilangan bulat tak negatif dan y adalah bilangan bulat positif, didefinisikan x mod y sebagai sisa jika x dibagi y.
Contoh:
6 mod 2 = 0
5 mod 1 = 0
8 mod 12 = 8
199673 mod 2 = 1

Fungsi Faktorial
Untuk sembarang bilangan bulat non negatif n, faktorial dari n dilambangkan dengan n ! yang didefinisikan






0! didefinisikan 1
Contoh:
1! = 1
2! = 2.(2-1) = 2
3! = 3. (3-1) (3-2) = 6
dst
n! = n. (n-1) !
 
Fungsi EksponsialFungsi eksponensial berbentuk :





 


Untuk kasus perpangkatan negatif :

Contoh :
43 = 4 x 4 x 4 = 64
4-3 = 1/64

Fungsi Logaritmik
Fungsi logaritmik berbentuk:

Contoh :
4log 64 = 3 karena 64 = 43
ë 2log 1000û = 9 karena 29 = 512 tetapi 210 = 1024

Fungsi Rekursif
Fungsi f dikatakan fungsi rekursif jika definisi fungsinya mengacu pada dirinya sendiri.
Fungsi rekursif disusun oleh 2 bagian :
Basis
Bagian yang berisi nilai awal yang tidak mengacu pada dirinya sendiri.
Bagian ini menghentikan definisi rekursif (dan memberikan sebuah nilai yang terdefinisi pada fungsi rekursif)
Rekurens
Bagian yang mendefinisikan argumen fungsi dalam terminologi dirinya sendiri
Setiap kali fungsi mengacu pada dirinya sendiri, argumen dari fungsi harus lebih dekat ke nilai awal (basis)
Misalkan f(n) = n! maka fungsi faktorial dapat dituliskan sebagai :

Contoh I: 
Perhitungan n! secara rekursif :
Basis
n! = 1            jika n = 0
Rekurens
n! = n x (n-1)!        Jika n > 0
Contoh :
5! = 5 x 4!      (rekurens)
             4! = 4 x 3!
                          3! = 3 x 2!
                 2! = 2 x 1!
                             1! = 1 x 0!
                              0! = 1
Sehingga :
    0! = 1
    1! = 1 x 0! = 1 x 1 = 1
    2! = 2 x 1! = 2 x 1 = 2
    3! = 3 x 2! = 3 x 2 = 6
    4! = 4 x 3! = 4 x 6 = 24
    5! = 5 x 4! = 5 x 24 = 120
Jadi 5! = 120

Contoh II:
Misalkan n menyatakan bilangan bulat positif dan fungsi f didefinisikan secara rekursif :

Tentukan :
f(25)            
f(10)
Penyelesaian :
f(25) = f(ë25/2û)+1 = f(12) + 1
               = [f(ë12/2û)+1] + 1 = f(6) + 1 + 1 = f(6) + 2
               = [f(ë6/2û)+1 ] + 2 = f(3) + 1 + 2 = f(3) + 3
               = [f(ë3/2û)+1 ] + 3 = f(1) + 1 + 3 = f(1) + 4
               = 0 + 4 = 4
f(10) = f(ë10/2û)+1 = f(5) + 1
               = [f(ë5/2û)+1] + 1 = f(2) + 1 + 1 = f(2) + 2
               = [f(ë2/2û)+1 ] + 2 = f(1) + 1 + 2 = f(1) + 3
               = 0 + 3 = 3

 







 

LOGIKA

Logika

cara berpikir dengan mengembangkan sesuatu berdasarkan akal budi dan bukan dengan perasaan atau pengalaman. Pelajaran logika difokuskan pada hubungan antara pernyataanpernyataan (statements).

LOGIKA PROPOSISI

Di dalam matematika, tidak semua kalimat berhubungan dengan logika. Hanya kalimat yang bernilai benar atau salah saja yang digunakan dalam penalaran. Kalimat tersebut dinamakan proposisi (preposition).

Secara didenifisikan proposisi adalah Pernyataan atau kalimat deklaratif yang bernilai benar (true) atau salah (false), tetapi tidak keduanya.

Contoh :

Proposisi :

1. 6 adalah bilangan genap
2. Ibu kota provinsi jawa barat adalah Semarang
3. Kemarin hari hujan
4. 2 + 2 = 4

Bukan Proposisi :

1. Jam berapa Kereta tiba ?
2. Tolong ambilkan buku tulis itu !
3. X + 3 = 8
4. X ≥ 3

 

 Mengkombinasikan Proposisi

Operator Logika untuk menkombinasikan proposisi yaitu dan, atau dan tidak. Dua operator pertama dinamakan operator biner karena operator tersebut mengoperasikan dua buah proposisi, sedangkan operator ketiga dinamakan operator uner karena ia hanya membutuhkan satu buah proposisi.

Proposisi yang terbentuk dari pengkombinasian beberapa proposisi atomik disebut proposisi majemuk.

Dalam logika matematika dikenal sebanyak 5 penghubung, yaitu: 

Konjungsi    (conjunction) : p dan q dengan  Notasi p Λ q  

Dengan tabel kebenaran sebegai berikut 

Contoh :
p : Hari ini hujan F q : Hari ini dingin T

• p Λ q : Hari ini hujan dan hari ini dingin / hari ini hujan dan dingin

 

Disjungsi (disjunction) : p atau q dengan Notasi  p V q

Dengan tabel kebenaran sebagai berikut

Contoh :

p : ibu pergi ke pasar T

q : ibu belanja sayuran F

p v q : ibu pergi ke pasar atau belanja sayuran

 

a.      C. Ingkaran (negation) : dari p: tidak p dengan Notasi: ~p

Dengan tabel sebagai berikut

Contoh :

p : pemuda itu tinggi

~p : tidak benar pemuda itu tinggi / pemuda     

       itu tidak tinggi.

a.      EXCLUSIVE OR (XOR) (⊕)

Jika dimiliki proposisi p dan q maka EXCLUSIVE OR (XOR) dari proposisi p dan q adalah proposisi dengan tabel kebenaran sebagai berikut

Perlu diberi catatan untuk mudah membedakan OR dan XOR adalah pada XOR

hanya kan bernilai TRUE jika dau proposisi bernilai berbeda: T dan F atau F dan T.

a.      IMPLIKASI (→ )

Jika dimiliki proposisi p dan q maka IMPLIKASI p→q (dibaca : JIKA p MAKA q) dari proposisi p dan q adalah proposisi dengan tabel kebenaran sebagai berikut

Catatan :

Dalam IMPLIKASI : p → q maka baik p maupun q keduanya adalah proposisi yang dapat bernilai benar atau salah.

 Tabel kebenaran (Truth table)

Untuk mengevaluasi apakah sebuah proposisi majemuk benar atau salah kita perlu tabel kebenaran dari hasil yang ada dalam proposisi tersebut. Untuk sembarang proposisi p dan q, rangkuman tabel kebenaran yaitu:

 

  Hukum-hukum Logika Proposisi

1. Hukum Identas      (i)  p  v   F  ↔ p      (ii) p  Λ   T  ↔ p	2. Hukum null/Dominasi      (i) p  Λ   F  ↔  F      (ii) p  v  T  ↔  T
3. Hukum Negasi     (i)  p  v  ~p  ↔ T     (ii) p  Λ   ~p  ↔ F	4. Hukum idempoten     (i)  p  v  p  ↔ p     (ii) p  Λ   p   ↔ p
5. Hukum Involusi(negasi ganda)     (i)  ~ (~p)  ↔ p	6. Hukum Penyerapan (absorpsi)     (i)  p  v  (p Λ q) ↔ p     (ii) p  Λ  (p v q) ↔ p
7. Hukum komutatif     (i)  p  v  q  ↔ q  v  p     (ii) p  Λ  q   ↔ q Λ  p	8. Hukum assosiatif     (i)  p v (q v r) ↔ (p v q) v r     (ii) p Λ (q Λ r ) ↔ (p Λ q)  Λ  r
9. Hukum Distributif     (i)  p v (q Λ r) ↔ (p v q) Λ (p v r)     (ii) p Λ (q v r ) ↔ (p Λ q)  v  (p Λ r)	10. Hukum De Morgan      (i)  ~(p Λ q) ↔ ~p v ~q      (ii) ~(p v q) ↔ ~p Λ ~q

 

Hukum-hukum logika di atas bermanfaat untuk membuktikan keekivalenan duabuah proposisi.khususnya pada proposisi majemuk yang mempunyai banyak proposisi atomik. Bila suatu proposisi majemuk mempunyai n buah porposisi atomik, maka tabel kebenarannya terdiri dari 2n baris. Untuk n yang besar jelas tidak praktis menggunakan tabel kebenaran, misalnya untuk n = 10 terdapat 210 baris di dalam tabel kebenarannya.

Contoh

Tunjukkan bahwa p v ~(p v q) dan p v ~q keduanya ekivalen secara logika

Penyelesaian:

p v ~(p v q )  ⇔p v (~p ^ ~q)                         (Hukum De Mogran)

            ⇔ (p v ~p) ^ (p v ~q)                 (Hukum distributif)

               ⇔T ^ (p v ~q)                             (Hukum negasi)

                           ⇔p v ~q                          (Hukum identitas)

 PROPOSISI BERSYARAT

Misalkan p dan q adalah proposisi. Proposisi majemuk “jika p maka q” disebut proposisi bersyarat(implikasi) dan dilambangkan p → q Proposisi p disebut hipotesis (atau anteseden atau premis atau kondisi) dan proposisi q disebut konklusi (atau konsekuen)

 

Tabel kebenaran

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

 

r  Bi-implikasi

Misalkan p dan q adalah proposisi. Proposisi majemuk “p jikan dan hanya jika q” disebut bi kondisional (bi-implikasi) dan dilambangkan p ↔ q.

Tabel kebenaran

p	q	p ↔q
T	T	T
T	F	F
F	T	F
F	F	T

INFERENSI (KESIMPULAN)

Inferse adalah proses penarikan kesimpulan dari beberapa proposisi.

1. Modus Ponen atau Law Of  Detachment

p → q

p

jadi : q

2. Modus Tollen

p → q

~ q

jadi : ~ p

3. Silogisme Hipotesis

p→q

q →r

jadi :p→r

4. Silogisme Disjungtif

p v q

~ p

jadi: q

5. Simplifikasi

p ^q

jadi: p

6. Penjumlahan

p

jadi :p v q

7. Konjungsi

p

q         

jadi : p ^ q