ALJABAR BOOLEAN

Aljabar Boolean (B,+,.,’) adalah aljabar yang terdiri atas himpunan B dengan dua operator biner (+ dan .) dan sebuah operator uner (‘) yang memenuhi prostulat Huntington

PROSTULAT HUNTINGTON

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

Ekspresi Boolean

jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 . e2, e1’ adalah ekspresi Boolean

Prinsip Dualitas

S* disebut sebagai dual dari S.

S* diperoleh dengan cara mengganti

. dengan +

+ dengan .

0 dengan 1

1 dengan 0

HUKUM-HUKUM ALJABAR BOOLEAN

1. Hukum identitas:

(i) a + 0 = a

(ii) a × 1 = a

3. Hukum komplemen:

(i) a + a’ = 1

(ii) aa’ = 0

5. Hukum involusi:

(i) (a’)’ = a

7. Hukum komutatif:

(i) a + b = b + a

(ii) ab = ba

9. Hukum distributif:

(i) a + (b c) = (a + b) (a + c)

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

11. Hukum 0/1

(i) 0’ = 1

(ii) 1’ = 0

FUNGSI BOOLEAN

Fungsi Boolean/Fungsi biner adalah pemetaan dari Bⁿ ke B melalui ekspresi Boolean yang dituliskan sebagai

f : Bⁿ  -->  B

Setiap ekspresi Boolean tidak lain merupakan fungsi Boolean.

Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal.

Komplemen Fungsi

1. Cara pertama: menggunakan hukum De Morgan. Hukum De Morgan untuk dua buah peubah, x1 dan x2, adalah

Contoh. Misalkan f(x, y, z) = x(y’z’ + yz), maka

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

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

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

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

2. Cara kedua: menggunakan prinsip dualitas.

Tentukan dual dari ekspresi Boolean yang merepresentasikan lalu komplemenkan setiap literal di dalam dual tersebut.

Contoh. Misalkan f(x, y, z) = x(y’z’ + yz), maka

dual dari f: x + (y’ + z’) (y + z)

komplemenkan tiap literalnya: x’ + (y + z) (y’ + z’) = f

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

Bentuk Kanonik

Ada dua macam bentuk kanonik:

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

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

·  Setiap minterm/maxterm mengandung literal lengkap

Miniterm digunakan intuk SOP Maxterm digunakan untuk POS

Konversi Antar Bentuk Kanonik

Intinya m_x’=M_x

Bentuk Baku

Tidak harus mengandung literal yang lengkap.