TEOREMA ALJABAR BOOLE
Aljabar Boole sangat penting peranannya di dalam proses perancangan maupun analisis rangkaian logika. Terdapat dua jenis teorema dalam aljabar boole, yakni teorema variabel tunggal dan teorema variabel jamak. Setiap teorema baik yang bersifat tunggal maupun jamak selalu memiliki teorema rangkapnya.
A. Teorema Variabel Tunggal Kelompok pertama teorema diberikan pada Gambar 2.1. Pada tiap teorema, X adalah sebuah variabel logika yang dapat bernilai 0 atau 1. Masing-masing teorema digambarkan pula diagram logika ekuivalennya, yang mana akan membantu untuk mengecek kebenarannya. Teorema-teorema pada Gambar 2.1 adalah teorema variabel tunggal (single variable thoerems) dengan hanya variabel X, jadi kita harus mengecek untuk kondisi-kondisi X = 0 dan X = 1.
Gambar 2.1
Teorema-teorema variabel tunggal (single variable)
Teorema (1) menyatakan bahwa jika suatu variabel apa saja di-AND-kan dengan 0, hasilnya pasti 0. Ini mudah untuk diingat sebab operasi AND adalah seperti perkalian biasa, dimana kita tahu bahwa apa saja yang dikalikan dengan 0 adalah 0. Kita juga tahu bahwa output dari gerbang AND akan menjadi 0 jika ada input yang bernilai 0. Tanpa memperdulikan level pada input yang lain.
Teorema (2) juga sama seperti pada perkalian biasa.
Teorema (3) dapat dibuktikan dengan mencoba masing-masing kondisi Jika X = 0, maka 0 . 0 = 0 Jika X =1, maka 1 . 1 = 1 Jika X . X = X
Teorema (4) dapat dibuktikan dengan cara yang sama. Bagaimanapun juga, teorema (4) juga dapat berasalan bahwa pada suatu saat apakah X atau kebalikannya X pasti menjadi level 0, jadi hasil perkalian AND-nya pasti selalu 0.
Teorema (5) adalah biasa, karena 0 jika ditambahkan dengan apa saja tidak mempengaruhi nilainya, apakah itu pada penambahan biasa atau pada penambahan OR.
Teorema (6) menyatakan bahwa jika suatu variabel apa saja di OR-kan dengan 1, hasilnya akan selalu 1. Mengecek teorema (6) untuk kedua nilai X : 0 + 1 = 1 dan 1 + 1 = 1 Dengan demikian kita dapat mengingat bahwa output dari OR gate akan menjadi 1 jika ada input yang bernilai 1, tanpa menghiraukan nilai input yang lain.
Teorema (7) dapat dibuktikan dengan pengecekan untuk kedua harga X : 0 + 0 = 0 dan 1 + 1=1
Teorema (8) dapat dibuktikan dengan cara yang sama atau kita dapat hanya beralasan pada suatu saat apakah X atau X pasti menjadi level 1 jadi kita selalu meng-OR-kan 0 dan 1 yang selalu menghasilkan 1.
Sebelum mengenalkan teorema-teorema selanjutnya, harus ditekankan bahwa dalam menerapkan teorema-teorema (1) - (8) variabel X bisa mewakili suatu ekspresi yang berisi lebih dari satu variabel. Sebagai contoh, jika kita mempunyai A B ( A B ), kita dapat memakai teorema (4) dengan memisalkan X = A B . Jadi kita dapat menyatakan bahwa A B ( A B ) = 0. Ide yang sama dapat diterapkan untuk menggunakan teorema-teorema tersebut di atas.
B. TEOREMA VARIABEL JAMAK (GANDA / MULTIVARIABLE) Teorema-teorema yang ditampilkan berikut ini melibatkan lebih dari satu variabel :
(9)
X+Y = Y+X
(10)
X.Y = Y.X
(11)
X + (Y + Z) = (X + Y) + Z = X + Y + Z
(12)
X(YZ) = (XY) Z = XYZ
(13)
X(Y + Z) = XY + XZ
(14)
(X + Y)(X + Z) = X + (Y . Z)
(15)
X + XY = X
(16)
X+ X Y = X+Y
(17)
X . ( X + Y) = X . Y
Hukum KOMUTATIF
Hukum ASOSIATIF
Hukum DISTRIBUTIF
Hukum ABSORTIF
Contoh 1: Sederhanakan ekspresi : Y = A B D + A B D
Penyelesaian : Y = ABD + AB D ingat teorema (13) X(Y + Z) = XY + XZ, maka menjadi Y = A B (D + D ) ingat teorema (8) 𝑋 + 𝑋 = 1, maka menjadi Y = AB . 1 ingat teorema (2) X . 1 = X, maka menjadi Y = AB
Contoh 2 : Sederhanakan Z = ( A + B)(A + B)
Penyelesaian : Z = ( A + B)(A + B) Ekspresi ini dapat diperluas sebagai berikut [teorema (13)] Z = A .A + A .B + B.A + B.B Memanggil teorema (4) : A . A = 0, juga B . B = B [teorema (3)] Z = 0 + A. B + B . A + B Z = AB + A B + B Dengan mengeluarkan B [teorema (13)] : Z = B ( A + A + 1) Akhirnya dengan menggunakan teorema (6), Z=B
Contoh 3 : Sederhanakan X = A C D + A B C D
Penyelesaian : X = A C D + A B C D ingat teorema (13) sehingga menjadi X = CD ( A + A B ) ingat teorema (16) sehingga menjadi X = C D (A + B) ingat teorema (13) sehingga menjadi X =ACD+BCD
TEOREMA De Morgan Dua teorema yang paling penting dari Aljabar Boolean disumbangkan oleh ahli matematika bernama DeMorgan. Teorema DeMorgan ini termasuk kedalm kelompok teorema variabel jamak dan sangat berguna dalam penyederhanaan suatu ekspresi. Kedua teorema tersebut adalah :
X Y = X . Y X .Y = X + Y
(18) (19)
Teorema DeMorgan itu dapat dinyatakan dengan kata-kata sebagai berikut : Setiap pernyataan dalam logika adalah ekuivalen dengan pertentangannya (inversion) dengan cara :
Penjumlahan logika (fungsi OR) ditukar menjadi perkalian logika (fungsi AND) dan sebaliknya
Serta mengganti tiap-tiap variabel dengan pertentangannya (fungsi NOT)
Contoh 4 :
Sederhanakan A B C dengan teorema DeMorgan Penyelesaian :
AB C
= A B . C = AB . C
Catatan : B adalah sama dengan B, jadi ( A + B) . C = A . C + B C Hasil terakhir ini hanya berisi tanda-tanda inverter (pembalik) yang membalik variabel tunggal.
Contoh 5 : Sederhanakan ekspresi Z = ( A C ).( B D ) Penyelesaian : Z = ( A C ) ( B D) = ( A..C ) ( B.D) Z = AC + B D
C. UNIVERSALITAS GERBANG NOR DAN NAND Gerbang NOR dan NAND memiliki sifat Universal, artinya semua gerbang logika atau rangkaian logika dapat disusun dengan menggunakan gerbang NOR saja atau NAND saja. Berikut ini akan ditunjukkan bahwa semua gerbang logika dapat disusun hanya dengan gerbang NOR saja atau dengan NAND saja.
Universalitas Gerbang NOR
Universalitas Gerbang NAND