ALJABAR BOLEAN
Komputer memanipulasi elemen-elemen diskrit dari informasi yang diawali oleh kualitas fisik ynag disebut dengan sinyal. Sinyal-sinyal tersebut biasanya terbatas pada dua kemungkinan nilai yang disebut sebagai biner. Dua level sudah cukup karena setiap pesan yang diinginkan, serumit apapun, dapat dikodekan dalam sistem biner dengan menggunakan string dari simbol 0 dan 1. Karena itu, alat-alat dengan dua macam status seperti saklar, dioda, magnetik core dan transistor dapat digunakan untuk mengolah informasi karena kedua kodisi tersebut (on lawan off, conducting lawan non-conducting, bermagnet positif lawan bermagnet negatif, potensial tinggi lawan potensial rendah) dapat mewakili kedua simbol biner, 0 dan 1.
Pada tahun 1938, Claude Shannon menunjukkan cara untuk menganalisis dan merancang sirkuit logika digital dengan menggunakan persamaan aljabar yang melibatkan variabel-variabel yang hanya dapat berisi dua macam nilai. Ia mendasarkan pendekatannya pada konsep Aljabar Boolean, yang pada awalnya ditemukan oleh George Bool, seorang ahli matematika abad sembilan belas. Bool tertarik untuk menemukan aturan-aturan yang sama mengendalikan kerja pikiran manusia. Dan Shannon mengamati bahwa aturan-aturan yang sama mengendalikan tingkah laku sirkuit digital. Prinsip-prinsio yang menuntun pendekatan Shannon ini adalah: Kurangi masalah perancangan dan analisis sirkuit digital untuk studi ekspresi dalam sebuah aljabar Boolean.
Aljabar Boolean adalah struktur aljabar yang terdiri dari suatu kumpulan elemen-elemen B bersama dua operasi biner {+} dan {-} dan sebuah operasi unary { } sedemikian sehingga aksioma-aksioma berikut berisi:
1.Kumpulan B berisi paling sedikit dua elemen a, b sedemikian sehingga a != b.
2.Closure properties pada operasi biner: Untuk semua a, b B, (a) a + b B (b) a . b B
3.Hukum Komutatif: Untuk semua a, b B, (a) a + b = b + a (b) a . b = b . a
4.Adanya identitas: (a) Ada sebuah elemen identitas dalam operasi {+}, ditunjukan oleh 0, sedemikian sehingga a+0=a, untuk semua a B
5.(b) Ada sebuah elemen identitas dalam operasi (.), ditunjukan oleh 1, sedemikian sehingga a.1=a, umtuk semua a B.
6.Hukum Distributif: Untuk setiap a B, harus ada sebuah elemen a B (komplemen a) sedemikian sehingga: (a) a + a = 1 (b) a. a = 0
7.Hukum Asosiatif: Untuk semua a, b, c B, (a) a + (b + c) = (a + b) + c (b) a . (b . c) = (a . b) . c
Perhatikan bahwa hukum asosiatif dapat diturunkan dari aksioma-aksioma yang lain.
Proaritas operator dalam aljabar boolean adlah sedemikian rupa sehingga sebuah ekspresi yang berada di dalam tanda kurung harus sievaluasi sebelum semua operasi lainnya. Jenis operasi lain yang harus didahulukan adalah komplemen {-}, kemudian {.} dan terakhir {+}. Jika tanda kurung tidak digunakan, operasi {.} dikerjakan sebelum operasi {+}. Juga, simbol {.} dapat dihilangkan, dalam kasus dimana ab dianggap mempunyai arti a.b Perhatikan bahwa aksioma-aksioma tersebut diatur secara berpasangan. Setiap pernyataan dapat diperoleh dari pernyataan lainnya dengan saling mempertukarkan operasi {+} dan {.} serta elemen identitas 0 dan 1. Hal ini disebut sebagai prinsip rangkap dua (principle of duality) dan diilustrasikan sebagai berikut: a + (b . c) = (a + b) . (a + c) a . (b +. c) = (a . b) + (a . c) Karena itu, setiap ekspresi (teorema) aljabar yang ditarik kesimpulannya dari aksioma-aksioma tersebut memiliki kembaran yang juga benar.
TABEL 3.1 BEBERAPA IDENTITAS PENTING DALAM ALJABAR BOOLEAN (1a) x + 0 = x
(1b) x . 1 =x Aksioma 4
(2a) x ( y + z ) = xy + xz
(2b) x + xy = (x + y)(x + z) Pendistribusian
(3a) x + x = 1
(3b) xx = 0 Aksioma 6
(4a) x + x = x
(4b) xx = x Idempotens
i (5a) x + I = 1
(5b) x . 0 = 0
(6a) x + xy = x
(6b) x (x + y) = x absorpsi
(7a) (x + y)y = xy
(7b) xy + y = x + y
(8a) (x + y)(x + y) = x
(8b) xy + xy = x Kedekatan logika
(9a) (x + y)(x + z)(y + z) = (x + y)(x + z)
(9b) xy + xz + yz = xy + xz Konsensus
(10a) (x1 + x2 + … + xn) = (x1x2…xn) Hukum DeMorgan
(10b) (x1x2…x)n = (x1 + x2 + … + xn)
(11a) f(x1,x2, … , xn) = xif(x1,x2,…,xi-1, 1, xi+1, …,xn) + xif(x1,x2,…,xi-1, 0, xi+1, …,xn) Teorema ekspansi Shannon
(11b) f(x1,x2, … , xn) = [xi + f(x1,x2,...,xi-1, 0, xi+1, …,xn)] . [Xi + f(x1,x2,...,xi-1, 0, xi+1, …,xn)]
Tabel diatas berisi daftar berbagai identitas penting dalam aljabar boolean. Mereka diletakkan dalam daftar secara berpasangan, ditunjukkan oleh (a) dan (b). Kita dapat menggunakan identitas tersebut untuk membuktikan identitas lainnya atau untuk memanipulasi ekspresi aljabar Boolean kedalam bentuk lain. Contoh paling mudah dari aljabar boolean hanya terdiri dari dua elemen, 0 dan 1, dinyatakan untuk memenuhi 1 + 1 = 1 . 1 = 1 + 0 = 0 + 1 = 1 0 + 0 = 0 . 0 = 1 . 0 = 0 . 1 = 0 1 = 0 0 = 1 Dengan mudah dapat ditunjukkan bahwa semua aksioma terpenuhi untuk kasis ini. Aljabar seperti ini sering disebut sebagai aljabar boolean dua-nilai (two-valued) atau switching algebra.
