Aljabar yang berhubungan dengan variable-variable biner dan operasi-operasi lojik. Fungsi boolean terdiri dari variable-variable biner yang menunjukan fungsi ( 0 dan 1). Exp.
F = x+y’z
X dan y’z disebut suku-suku atau term dari fungsi F
X, y’ dan z disebut literal.
Tabel kebenaran untuk fungsi f=x+y’z
F = x+y’z
X dan y’z disebut suku-suku atau term dari fungsi F
X, y’ dan z disebut literal.
Tabel kebenaran untuk fungsi f=x+y’z
X
|
Y
|
Z
|
F=x+y’z
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
Ada 8 kombinasi biner yang mungkin dengan meng-asign ke masing-masing tiga variable x, y dan z
Hukum-hukum Aljabar Boolean
1. Hukum identitas:
(i) a
+ 0 = a
(ii) a
 1 = a |
2. Hukum idempoten:
(i) a +
a = a
(ii) a
a = a |
3. Hukum komplemen:
(i) a
+ a’ = 1
(ii) aa’
= 0
|
4.
Hukum dominansi:
(i) a
0 = 0 (ii) a +
1 = 1 |
5. Hukum involusi:
(i) (a’)’ = a
|
6. Hukum penyerapan:
(i) a +
ab = a
(ii) a(a +
b) = a
|
7.
Hukum komutatif:
(i) a
+ b = b + a
(ii) ab = ba
|
8.
Hukum asosiatif:
(i) a
+ (b + c)
= (a + b) + c
(ii) a (b
c) = (a b)
c
|
9.
Hukum distributif:
(i) a + (b c) = (a + b)
(a + c)
(ii) a (b + c) =
a b + a c
|
10.
Hukum De Morgan:
(i) (a +
b)’ = a’b’
(ii) (ab)’
= a’ + b’
|
11. Hukum 0/1
(i)
0’ = 1
(ii) 1’ = 0
|
Manipulasi aljabar
Dengan aljabar boolean maka rangkaian digital bisa disederhanakan. Exp.
F = x’yz + x’yz’ + xz
= x’y(z+z’) + xz
= x’y.1 + xz
= x’y + xz
Teble kebenaran untuk dua fungsi ekuivalen di atas:
X
|
Y
|
Z
|
x’
|
Z’
|
Xz
|
X’y
|
X’yz
|
X’yz’
|
X’yz +
x’yz’ + xz
|
X’y + xz
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
Fungsi Boolean
Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bn ke B melalui ekspresi Boolean, kita menuliskannya sebagai
f : Bn B
yang dalam hal ini Bn adalah himpunan yang beranggotakan pasangan terurut ganda-n
(ordered n-tuple) di dalam daerah asal B.
Setiap ekspresi Boolean tidak lain merupakan fungsi Boolean. Misalkan sebuah fungsi Boolean adalah
f(x, y, z) = xyz + x’y + y’z
Fungsi f memetakan nilai-nilai pasangan terurut ganda-3 (x, y, z) ke himpunan {0, 1}.
Contoh. Diketahui fungsi Booelan f(x, y, z) = xy z’, nyatakan h dalam tabel kebenaran. Penyelesaian:
x
|
y
|
z
|
f(x, y, z) =
xy z’
|
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
0
0
0
0
0
0
1
0
|
Komplemen Fungsi
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’)
Bentuk Kanonik
Jadi, ada dua macam bentuk kanonik:
1. Penjumlahan dari hasil kali (sum-of-product atau SOP)
2. Perkalian dari hasil jumlah (product-of-sum atau POS) Contoh: 1. f(x, y, z) = x’y’z + xy’z’ + xyz SOP
Setiap suku (term) disebut minterm
2. g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)
(x’ + y + z’)(x’ + y’ + z) POS Setiap suku (term) disebut maxterm
Setiap minterm/maxterm mengandung literal lengkap
Minterm
|
Maxterm
|
||||
x
y
|
Suku
|
Lambang
|
Suku
|
Lambang
|
|
0
0
1
1
|
0
1
0
1
|
x’y’ x’y xy’
x y
|
m0 m1 m2 m3
|
x
+ y
x + y’ x’
+ y x’ + y’
|
M0
M1
M2
M3
|
Minterm
|
Maxterm
|
|||||
x
y
z
|
Suku
|
Lambang
|
Suku
|
Lambang
|
||
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
x’y’z’ x’y’z x‘y
z’ x’y z
x y’z’
x
y’z x y
z’ x y z
|
m0 m1 m2 m3 m4 m5 m6 m7
|
x + y +
z
x + y +
z’
x
+ y’+z x + y’+z’ x’+
y + z x’+ y +
z’ x’+ y’+
z x’+ y’+ z’
|
M0
M1
M2
M3
M4
M5
M6
M7
|
Contoh 7.10. Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.
Tabel 7.10
x
|
y
|
z
|
f(x, y, z)
|
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
0
1
0
0
1
0
0
1
|
Penyelesaian: (a) SOP
Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 adalah 001,
100, dan 111, maka fungsi Booleannya dalam bentuk kanonik SOP adalah
f(x, y, z) = x’y’z + xy’z’ + xyz
atau (dengan menggunakan lambang minterm),
f(x, y, z) = m1 + m4 + m7 = (1, 4, 7)
(b) POS
Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 adalah 000,
010, 011, 101, dan 110, maka fungsi Booleannya dalam bentuk kanonik POS adalah
f(x, y, z) = (x + y + z)(x + y’+ z)(x + y’+ z’)
(x’+ y + z’)(x’+ y’+ z)
atau dalam bentuk lain,
f(x, y, z) = M0 M2 M3 M5 M6 = (0, 2, 3, 5, 6)