Menyederhanakan Fungsi Boolean

Sebelum memasuki tahap penyederhanaan sebaiknya kamu memperlajari dahulu hukum-hukum dasar operasi aljabar boolean, Teorema Aljabar Boolean.
Penyederhanaan Fungsi Boolean Dengan Aljabar

Penyederhanaan suatu fungsi Boolean dapat dilakukan dengan bebarapa cara di antaranya dengan metode penyederhanaan Aljabar yaitu berdasarkan hukum atau Teorema Aljabar Boolean.

Istilah-istilah yang perlu diketahui sebelum melakukan penyederhanaan fungsi Boolean:
Proposisi (dalil), yaitu pernyataan yang mungkin bisa Benar atau Salah (True atau False). Contoh: "Anda Belajar Aljabar Boolean" --> True, 5 kurang dari 3 --> False. Pertanyaan dan eklamasi tidak termasuk proposisi. Contoh: "Dimana Anda Kuliah?" --> bukan proposisi karena mempunyai banyak jawaban dan tidak menghasilkan True dan False.
Negasi (sangkalan). Contoh: Jika X' adalah negasi dari X maka jika X="Saya sedang menulis" maka X'="Saya sedang tidak menulis" demikian juga sebaliknya. Negasi dari X ditulis X' atau dengan tanda garis di atas huruf X.
Predikat, hampir sama dengan proposisi tetapi belum bisa menghasilkan True dan False karena nilai variabel belum dispesifikasikan. Contoh: X>8, pernyataan tersebut dapat menghasilkan True jika X bernilai lebih dari 8 (8, 9, 10, 11,...) dan dan akan bernilai False jika X bernilai kurang dari atau sama dengan 8 (8, 7, 6, 5, ...).
Operasi Boolean, yaitu operasi yang telah ditetapkan terhadap data misalnya penjumlahan 6+7 adalah operasi matematika.
Operand, yaitu data-data yang dikenakan suatu operasi. Pada penjumlahan 6+7, angka 6 dan angka 7 adalah operand. Proposisi dan predikat akan menjadi operand dalam operasi logika. Contoh:
p(x) adalah predikat yang mewakili x>8, q(y) adalah predikat yang mewakili y=7, p(x) OR q(y) adalah operasi logika dimana p(x) dan q(y) adalah operand dan "OR" adalah operator logika.
Operator, yaitu tanda atau simbol dari suatu operasi. Pada penjumlahan 6+7, tanda plus (+) adalah operator.
Penyederhanaan Boolean akan selalu berhubungan dengan:
Operator AND untuk menyatakan perkalian yang ditulis dengan titik (.), contoh A.B, X.Y, P.Q
Operator OR untuk menyatakan penjumlahan yang ditulis dengan tanda plus (+), contoh A+B, X+Y, P+Q
NOT (Negasi) yang ditulis dengan tanda kutip tunggal (') atau tanda garis di atas, contoh A', B', C'.
Semua operator tersebut nantinya akan dipakai untuk menyederhanakan bilangan biner yang diwakili  oleh variabel tertentu. Tanda titik yang mewakili perkalian dapat dihilangkan kecuali ada penekanan, contoh A.B sama dengan AB, X.Y sama dengan XY, tetapi A.0 akan tetap ditulis A.0.

Contoh-contoh penyederhanaan fungsi Boolean.
F = A + A'B
   = (A+A') (A+B)         {Hukum Distributif T3}
   = 1 (A+B)                 {Hukum T7}
   = A+B

   atau langsung dengan hukum T9

F = A'B'C + A'BC + AB'
   = A'C (B'+B) + AB'    {Hukum Distributif T3 dan T8}
   = A'C (1) + AB'         {Hukum T7}
   = A'C + AB'
 
F = ABCD + ABCD'
   = ABC (D+D')          {Hukum Distributif T3 dan T8}
   = ABC (1)                {Hukum T7}
   = ABC

F = ABC'D' + ABC'D + ABCD + ABCD'
   = ABC' (D'+D) + ABC (D+D')    {Hukum Distributif T3 dan T8}
   = ABC' (1) + ABC (1)                {Hukum T7}
   = ABC' + ABC
   = AB (C'+C)                              {Hukum Distributif T3 dan T8}
   = AB (1)                                    {Hukum T7}
   = AB

F = X (XY+Z)  
   = X.XY + XZ      {Hukum T3}
   = XY + XZ         {Hukum T4}
   = X (Y+Z)          {Hukum T3}
 
F = X + XY '+ X'Y
   = X (1+Y') + X'Y    {Hukum T3}
   = X (1) + X'Y         {Hukum T7}
   = X + X'Y              {Hukum T9}
   = X + Y

F = X'Y' + XY' + XY
   = X'Y' + X (Y'+Y)            {Hukum T3}
   = X'Y + X (1)                  {Hukum T7}
   = X'Y + X atau X + X'Y   {Hukum T9}
   = X + Y

referensi : Mano, Morris.2001.Digital Design and Verilog HDL

Read more...

Teorema Aljabar Boolean

Dalam matematika dan ilmu komputer, Aljabar Boolean adalah struktur aljabar yang "mencakup intisari" operasi logika (AND, OR dan NOT) dan teori himpunan untuk operasi union, intersection, dan complement. Penamaan Aljabar Boolean berasal dari nama seorang matematikawan asal Inggris, bernama George Boole. Dialah yang pertama kali mendefinisikan istilah itu sebagai bagian dari sistem logika pada pertengahan abad ke-19.

Boolean adalah suatu tipe data yang hanya mempunyai dua nilai yaitu true dan false (benar dan salah). Pada beberapa bahasa pemrograman nilaitrue dan  false dapat digantikan dengan logic 1 dan logic 0. Aljabar Boolean merupakan alat matematis yang dapat digunakan untuk menganalisa suatu rangkaian logika melalui metode-metode penyederhanaan yang dilakukan.

Untuk lebih memahami operasi-operasi logika Boolean sebaiknya terlebih dahulu dipahami karakteristik yang berlaku pada gerbang-gerbang digital dasar seperti gerbang AND, gerbang OR, gerbang NOT, gerbang XOR, gerbang NAND, gerbang, NOR, dan gerbang XNOR. Karakteristik dari setiap gerbang digital dasar tersebut dapat dilihat melalui tabel kebenaran gerbang logika dasar.

DASAR-DASAR ALJABAR BOOLEAN
Pengembangan Aljabar Boolean dimulai dari asumsi-asumsi Postulat Boolean dan Teorema Aljabar Boolean.

A. Postulat Boolean
Diturunkan dari fungsi AND Gate, OR Gate, dan NOT Gate.

1. Turunan dari fungsi AND Gate (Gerbang AND): Jika salah satu input ber-logic 0 maka output akan 0.
2. Turunan dari fungsi OR Gate (Gerbang OR) : Jika salah satu input ber-logic 1 maka output akan 1.
3. Turunan dari fungsi NOT Gate (Gerbang NOT) : Output akan merupakan kebalikan dari input.

B. Teorema Aljabar Boolean

1. Hukum Commutative (T1)
   a. A + B = B + A
   b. A . B = B . A
2. Hukum Assosiative (T2)
   a. (A + B) + C = A + (B + C)
   b. (A . B) . C = A . (B . C)
3. Hukum Distributive (T3)
   a. A . (B + C) = A.B + A.C
   b. A + (B . C) = (A + B) . (A + C)
4. Hukum Identity (T4)
   a. A + A = A
   b A . A = A
5. Hukum Negation (T5)
   a. (A') = A'
   b. (A'') = A
6. Hukum Redudance (T6)
   a. A + A.B = A
   
   Pembuktian:
   

   A   B	A . B	A + A.B
   0    0	0	0
   0    1	0	0
   1    0	1	1
   1    1	1	1

   
   b. A. (A + B) = A
7. Hukum Identity T7
   a. 0 + A = A
   b. 1 + A = 1
   c. 0 . A = 0
   d. 1 . A = A
8. Hukum Invers T8
   a. A + A' = 1
   b. A . A' = 0
9. Hukum Collaps T9
   a. A + A' . B = A + B
   
   Pembuktian:
   

   A   B	A' . B	A + A'.B	A + B
   0    0	0	0	0
   0    1	1	1	1
   1    0	0	1	1
   1    1	0	1	1

   
   b. A. (A' + B) = A . B
10. Teorema Van De Morgan
    a. (A + B)' = A' . B'
    b. (A . B)' = A' + B'

Bentuk penulisan lain dari NOT:

Referesi : http://lecturer.eepis-its.edu

Read more...