Aljabar Boolean
Sistem aljabar dengan dua operasi penjumlahan (+) dan perkalian (.) yang didefinisikan sehingga memenuhi ketentuan berikut ini:
Aturan A1 sampai dengan A5, M1 sampai M3, M5, D1, dan D2.
Setiap elemen a, b,c dari S mempunyai sifat-sifat atau aksioma-aksioma berikut ini:
Representasi Fungsi Boolean:
A1 | a+b ∈ S | <closure>
M2 | a.b ∈ S | <closure>
A2 | a+(b+c) = (a+b) + c | <asosiatif>
M2 | a.(b.c)=(a.b).c | <asosiatif>
A3 | Jika 0 ∈ S maka untuk setiap a ∈ S, adalah a + 0 = 0 + a = a | <identitas>
M3 | Jika 1 ∈ S maka untuk setiap a ∈ S, adalah a . 1 = 1 . a = a | <identitas>
A5 | a + b = b + a | <komunikatif>
M5 | a.b = b.a | <komunikatif>
D1 | a.(b+c) = a.b + a.c | <distributif>
D2 | (a+b) .c = a.c + b.c | <distributif>
D3 | a + (b.c) = ( a + b ) . ( a+ c ) | <distributif>
D4 | (a.b) + c = ( a + c ) . ( b + c ) | <distributif>
C1 | Untuk setiap a ∈ S, dan a' ∈ S, maka a + a' = 1 dan a . a' = 0 | <komplemen>
Prinsip Dualitas
Teorema 1 (Idempoten)Untuk setiap elemen a, berlaku: a + a = a dan a . a = a
Teorema 2
Untuk setiap elemen a, berlaku: a + 1 = 1 dan a. 0 = 0
Teorema 3 (Hukum Penyerapan)
Untuk setiap elemen a dan b, berlaku: a + a . b = a dan a . ( a + b ) = a
Teorema 4 (Hukum de Morgan)
Untuk setiap elemen a dan b, berlaku: (a + b)' = a' + b' dan (a + b)' = a'.b'
Teorema 5 : 0' = 1 dan 1'=0
Teorema 6
Jika suatu Aljabar Boolean berisi paling sedikit dua elemen yang berbeda,
maka 0 ≠ 1
Fungsi Boolean
Misalkan x1, x2, x3, ... , Xn merupakan variabel-variabel ajlabar Boolean.Fungsi Boolean dengan n variabel adalah fungsi yang dapat dibentuk dari aturan-aturan sebagai berikut:
Fungsi Konstan
f(x1, x2, x3, ... , xn)=a
Fungsi Proyeksi
f(x1, x2, x3, ... , xn) = xi i = 1,2,3, ... , n
Fungsi Komplemen
g(x1, x2, x3, ... , xn) = (f(x1, x2, x3, ... , xn))'
Fungsi Gabungan
h(x1, x2, x3, ... , xn) = f(x1, x2, x3, ... , xn) + g(x1, x2, x3, ... , xn)
h(x1, x2, x3, ... , xn) = f(x1, x2, x3, ... , xn) . g(x1, x2, x3, ... , xn)
Bentuk Fungsi Boolean
Suatu fungsi Boolean dapat dinyatakan dalam bentuk yang berbeda tetapi memiliki arti yang sama.
Contoh:
f1(x,y) = x' . y'
f2(x,y) = ( x + y )'
f1 dan f2 merupakan bentuk fungsi Boolean yang sama, yaitu dengan menggunakan Hukum De Morgan.
Contoh: Fungsi Boolean
f(x,y) = x'y + xy' + y'
f1(x,y) = x' . y'
f2(x,y) = ( x + y )'
f1 dan f2 merupakan bentuk fungsi Boolean yang sama, yaitu dengan menggunakan Hukum De Morgan.
Nilai Fungsi
Fungsi Boolean dinyatakan nilainya pada setiap variabel yaitu pada setiap kombinasi NOL dan SATU (0,1).Contoh: Fungsi Boolean
f(x,y) = x'y + xy' + y'
| x | y | x'y | xy' | y' | f(x,y) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
Cara Representasi
Dengan Aljabar
Contoh: f(x,y,z) = xyz'
Dengan menggunakan tabel kebenaran
| x | y | z | xyz' |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Jumlah elemen dalam tabel kebenaran adalah jumlah kombinasi dari nilai variabel-variabelnya, yaitu sejumlah 2 n, dimana n adalah banyaknya variabel biner.
Minterm dan Maxterm
Terdapat 2 bentuk fungsi Boolean:- SOP (Sum of Product) → penjumlahan dari perkalian → disebut juga sebagai bentuk Minterm → ∑mi
- POS (Product of Sum) → perkalian dari penjumlahan → disebut juga sebagai bentuk Maxterm → ∏mi
Minterm dan Maxterm 2 variabel:
| Minterm | Maxterm | ||||
|---|---|---|---|---|---|
| x | y | Term | Nilai | Term | Nilai |
| 0 | 0 | x'y' | m0 | x+y | M0 |
| 0 | 1 | x'y | m1 | x+y' | M1 |
| 1 | 0 | xy' | m2 | x'+y | M2 |
| 1 | 1 | xy | m3 | x'+y' | M3 |
Minterm dan Maxterm 3 variabel:
| Minterm | Maxterm | |||||
|---|---|---|---|---|---|---|
| x | y | z | Term | Nilai | Term | Nilai |
| 0 | 0 | 0 | x'y'z' | m0 | x+y+z | M0 |
| 0 | 0 | 1 | x'y'z | m1 | x+y+z' | M1 |
| 0 | 1 | 0 | x'yz' | m2 | x+y'+z | M2 |
| 0 | 1 | 1 | x'yz | m3 | x+y'+z' | M3 |
| 1 | 0 | 0 | xy'z' | m4 | x'+y+z | M4 |
| 1 | 0 | 1 | xy'z | m5 | x'+y+z' | M5 |
| 1 | 1 | 0 | xyz' | m6 | x'+y'+z | M6 |
| 1 | 1 | 1 | xyz | m7 | x'+y'+z' | M7 |
Penyederhanaan Fungsi Boolean
Asumsi yang dipakai dalam penyederhanaan:
Bentuk fungsi boolean paling sederhana adalah SOP
Operasi yang digunakan adalah operasi penjumlahan (+), perkalian (.) dan komplemen (')
Terdapat tiga cara dalam penyederhanaan fungsi Boolean:
Cara Aljabar
Bersifat trial and error
Penyederhanaan menggunakan aksioma-akx+sioma dan teorema-teorema ang ada pada aljabar Boolean
Peta Karnaugh
Mengacu pada diagram Venn
Menggunakan bentuk-bentuk peta Karnaugh
Metoda Quine-McCluskey
Penyederhanaan didasarkan pada hukum distribusi
Eliminasi Prime Implicant Redundant.
Latihan:
Sederhanakan fungsi Boolean f(x,y)= x'y + xy' + xy
Jawab:
f(x,y) = x'y +xy' +xy
=x'y + x. (y'+y) | distributif
=x'y + x .1 | Komplemen
=x'y + x | Identitas
=(x'+x)(x+y) | Distributif
= 1. (x+y) | Komplen
= x + y | Identitas