ALJABAR BOOLEAN

DEFINISI ALJABAR BOOLEAN

Misalkan terdapat

- Dua operator biner: + dan ⋅

 - Sebuah operator uner: ’.

 - B : himpunan yang didefinisikan pada operator +, ⋅, dan ’

 - 0 dan 1 adalah dua elemen yang berbeda dari B.

 Tupel (B, +, ⋅, ’)

disebut aljabar Boolean jika untuk setiap a, b, c ∈ B berlaku aksioma-aksioma atau postulat Huntington berikut:

1.      Closure: (i) a + b ∈ B

(ii) a ⋅ b ∈ B

2.      Identitas: (i) a + 0 = a

 (ii) a ⋅ 1 = a

3.      Komutatif: (i) a + b = b + a

 (ii) a ⋅ b = b . a

4.      Distributif:(i) a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)

(ii) a + (b ⋅ c) = (a + b) ⋅ (a + c)

5.      Komplemen1: (i) a + a’ = 1

 (ii) a ⋅ a’ = 0

 ALJABAR BOOLEAN DUA-NILAI

Aljabar Boolean dua-nilai:

- B = {0, 1}

 - operator biner, + dan ⋅

 - operator uner, ’

 - Kaidah untuk operator biner dan operator uner:

 

Cek apakah memenuhi postulat Huntington:

1. Closure : jelas berlaku

2. Identitas: jelas berlaku karena dari tabel dapat kita lihat bahwa:

(i) 0 + 1 = 1 + 0 = 1

(ii) 1 ⋅ 0 = 0 ⋅ 1 = 0

3. Komutatif: jelas berlaku dengan melihat simetri tabel operatorbiner

4. Distributif:

(i) a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c) dapat ditunjukkan benar dari tabel operator biner di atas dengan membentuk tabel kebenaran:

(ii) Hukum distributif a + (b ⋅ c) = (a + b) ⋅ (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengancara yang sama seperti (i).

5. Komplemen:

 (i) a + a‘ = 1, karena 0 + 0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1

(ii) a ⋅ a = 0, karena 0 ⋅ 0’= 0 ⋅ 1 = 0 dan 1 ⋅ 1’ = 1 ⋅ 0 = 0

Karena kelima postulat Huntington dipenuhi, maka terbukti bahwaB = {0, 1} bersama-sama dengan operator biner + dan ⋅operator komplemen ‘ merupakan aljabar Boolean

EKSPRESI BOOLEAN

o   Misalkan (B, +, ⋅, ’) adalah sebuah aljabar Boolean. Suatuekspresi Boolean dalam (B, +, ⋅, ’) adalah: (i) setiap elemen di dalam B, (ii) setiap peubah, (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

o   Dua ekspresi Boolean dikatakan ekivalen(dilambangkan dengan ‘=’) jika keduanya mempunyai nilai yang sama untuksetiap pemberian nilai-nilai kepada n peubah. Contoh:

 a ⋅ (b + c) = (a . b) + (a ⋅ c)

HUKUM-HUKUM ALJABAR BOOLEAN

FUNGSI BOOLEAN

Fungsi Boolean(disebut juga fungsi biner) adalah pemetaandari Bn ke Bmelalui ekspresi Boolean, kita menuliskannyasebagai f : Bn → B yang dalam hal ini Bnadalah himpunan yang beranggotakanpasangan terurut ganda-n (ordered n-tuple) di dalam daerah asal B.

Setiap ekspresi Boolean tidak lain merupakan fungsiBoolean.

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 dua macam bentuk kanonik:

1. Penjumlahan dari hasil kali (sum-of-product atau SOP)

2. Perkalian dari hasil jumlah (product-of-sum atau POS)

 Contoh:

1. f(x, y, z) = x’y’z + xy’z’ + xyz → SOP Setiap suku (term) disebut minterm

2. g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’) (x’ + y + z’)(x’ + y’ + z) → POS Setiap suku (term) disebut maxterm

 Setiap minterm/maxterm mengandung literal lengkap

Contoh :

Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.

Penyelesaian:

(a)    SOP

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsisama dengan 1 adalah 001, 100, dan 111, maka fungsiBooleannya dalam bentuk kanonik SOP adalah

f(x, y, z) = x’y’z + xy’z’ + xyz

atau

(dengan menggunakan lambang minterm), f(x, y, z) = m1 + m4 + m7 = Σ (1, 4, 7)

(b)   POS

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsisama dengan 0 adalah 000, 010, 011, 101, dan 110, makafungsi Booleannya dalam bentuk kanonik POS adalah

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

atau dalam bentuk lain,

 f(x, y, z) = M0 M2 M3 M5 M6 = Π(0, 2, 3, 5, 6)

 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

2. Menggunakan Peta Karnaugh

3. Menggunakan metode Quine Mc Cluskey (metode Tabulasi)

1. PenyederhanaanSecaraAljabar

Contoh:

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

= (x + x’)(x + y)

 = 1 ⋅ (x + y )

= x + y

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

 = x’z(y’ + y) + xy’

 = x’z + xz’

3.      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.PetaKarnaugh

a. Peta Karnaugh dengan dua peubah 

b. Peta dengan tiga peubah

c. Peta dengan empat peubah