Aljabar Boolean dan Prinsip Dualitas
Aljabar Boolean
menggunakan aturan-aturan yang diturunkan dari
asumsi dasar
(aksioma/dalil/postulat)
1a. 0 · 0
= 0
2a. 1 · 1
= 1
3a. 0 · 1
= 1 · 0 = 0
4a. Jika x = 0, maka x = 1
1b. 1 + 1 = 1
2b. 0 + 0 = 0
3b. 1 + 0 = 0 + 1 = 1
4b. Jika x = 1, maka x = 0
• Dalil dituliskan berpasangan !untuk menunjukkan prinsip dualitas
_ Jika diberikan sebarang ekspresi logika, dual dari ekspresi
tersebut dapat dibentuk
dengan mengganti semua + dengan ·
atau sebaliknya serta
mengganti 0 dengan 1 atau sebaliknya
• dalil(b)
merupakan dual dari dalil(a) dan sebaliknya
_ Dual dari pernyataan benar adalah juga benar
Teorema
1 Variabel
• Aturan ini diturunkan dari
aksioma. x adalah variabel tunggal
5a. x · 0
= 0
6a. x · 1
= x
7a. x · x = x
8a. x · x = 0
5b. x + 1 = 1
6b. x + 0 = x
7b. x + x = x
8b. x + x = 1
9. x = x
Hukum-hukum
Aljabar
10a. x · y = y · x 10b. x + y = y + x !Komutatif
11a. x · (y · z) = (x · y) · z 11b. x + (y + z) = (x + y) + z !Asosiatif
12a. x · (y + z) = x · y + x · z 12b. x + y · z = (x + y) · (x + z) !Distributif
13a. x + x · y = x 13b. x · (x + y) = x !Absorsi
14a. x · y + x · y = x 14b. (x + y) · (x + y) = x !Penggabungan
15a. x · y = x + y 15b. x + y = x · y !DeMorgan
16a. x + x · y = x + y 16b. x · (x + y) = x · y
17a.
x·y+y ·z+x·z = x·y+x·z
17b. (x + y) · (y + z) · (x + z) =
(x + y) · (x + z)
Sintesis
Ekspresi Logika
Proses
Sintesis
• Diinginkan suatu fungsi,
bagaimana mengimplementasikannya
dalam bentuk ekspresi
atau rangkaian logika?
_ Proses ini disebut sintesis: membangkitkan ekspresi dan/atau
rangkaian dari deskripsi
perilaku fungsionalnya
• Misalnya
_ Desain rangkaian logika dengan dua masukan x1dan x2
_ Rangkaian memonitor switch, menghasilkan keluaran logika 1 jika
switch (x1,x2) mempunyai keadaan (0,0), (0,1) atau (1,1) dan
keluaran 0 jika switch
(1,0)
_ Pernyataan lain: jika switch x1tersambung dan x2terputus maka
keluaran harus 0,
keadaan switch lainnya keluaran harus 1
Proses
Sintesis
• Diinginkan suatu fungsi,
bagaimana mengimplementasikannya
dalam bentuk ekspresi
atau rangkaian logika?
_ Proses ini disebut sintesis: membangkitkan ekspresi dan/atau
rangkaian dari deskripsi
perilaku fungsionalnya
• Misalnya
_ Desain rangkaian logika dengan dua masukan x1dan x2
_ Rangkaian memonitor switch, menghasilkan keluaran logika 1 jika
switch (x1,x2) mempunyai keadaan (0,0), (0,1) atau (1,1) dan
keluaran 0 jika switch
(1,0)
_ Pernyataan lain: jika switch x1tersambung dan x2terputus maka
keluaran harus 0,
keadaan switch lainnya keluaran harus 1
• Langkah desain: membuat tabel
kebenaran untuk menuliskan term
perkalian yang
menghasilkan keluaran 1
Tabel
Kebenaran dan Hasil Ekspresi (SOP)
• Tabel kebenaran untuk fungsi
yang harus disintesis
• Realisasi f adalah f = x1x2 + x1x2 + x1x2
Minterm
dan Bentuk Kanonik SOP
• Untuk sebuah fungsi dengan n
buah variabel f (x1, x2 . . . xn)
_ Sebuah minterm dari f adalah satu term perkalian dari n
variabel yang
ditampilkan sekali, baik dalam bentuk tidak
diinverskan maupun
diinverskan
_ Jika diberikan satu baris dalam tabel kebenaran, minterm
dibentuk dengan
memasukkan variabel xi jika xi = 1 atau xi
jika xi = 0
_ Notasi mj merupakan
minterm dari baris nomor j di tabel
kebenaran. Contoh:
• Baris 1
(j = 0), x1 = 0, x2 = 0, x3 = 0
minterm: m0 = x1x2x3
• Baris 2
(j = 1), x1 = 0, x2 = 0, x3 = 1
minterm: m1 = x1x2x3
Minterm
dan Bentuk Kanonik SOP
• Tiap baris dari tabel
kebenaran membentuk satu
buah minterm
• Fungsi f dapat dinyatakan
dengan ekspresi
penjumlahan
dari semua
minterm di mana tiap minterm
di-AND-kan dengan nilai f
yang bersesuaian
Baris i x1 x2 x3 mintermmi f
0 0 0 0 x1x2x3 0
1 0 0 1 x1x2x3 1
2 0 1 0 x1x2x3 0
3 0 1 1 x1x2x3 0
4 1 0 0 x1x2x3 1
5 1 0 1 x1x2x3 1
6 1 1 0 x1x2x3 1
7 1 1 1 x1x2x3 0
• Contoh: diberikan nilai f
seperti tabel di atas, bentuk kanonik SOP:
f = m0 · 0 + m1 · 1 + m2 · 0 + m3 · 0 + m4 · 1 + m5 · 1 + m6 · 1 + m7 · 0
=
m1 + m4 + m5 + m6
=
x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3
Notasi
SOP
• Persamaan SOP dapat dinyatakan
dalam notasi m
f
= m1 +m4 + m5 + m6
=
x1x2x3
| {z }
1
+
x1x2x3
| {z }
4
+
x1x2x3
| {z }
5
+
x1x2x3
| {z }
6
• Notasi Persamaan SOP: f = Pm(1, 4, 5, 6)
• Implementasi:
_ Ekspresi fungsi f tersebut secara fungsional benar dan unik
_ Namun, mungkin tidak menghasilkan implementasi yang
paling sederhana
Prinsip
Duality
• Jika suatu fungsi f dinyatakan
dalam suatu tabel kebenaran, maka
ekspresi untuk f dapat
diperoleh (disintesis) dengan cara:
1. Melihat semua baris
dalam tabel dimana f=1, atau
2. Melihat semua baris
dalam tabel dimana f=0
• Pendekatan (1) menggunakan
minterm
• Pendekatan (2) menggunakan
komplemen dari minterm, disebut
maxterm
Penjelasan
Dualitas SOP-POS
• Jika fungsi f dinyatakan dalam tabel kebenaran, maka fungsi
inversnya f , dapat dinyatakan dengan penjumlahan minterm
dengan f = 1, yaitu di baris di mana
f = 0
f = m0 + m2 + m3 + m7
= x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3
• Fungsi f dapat dinyatakan
f = m0 + m2 + m3 + m7
=
x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3
=
_x1x2x3_ · _x1x2x3_ · _x1x2x3_ · (x1x2x3)
=
(x1 + x2 + x3) (x1 + x2 + x3) (x1 + x2 + x3) (x1 + x2 + x3)
• Meletakkan dasar untuk
menyatakan fungsi sebagai bentuk
perkalian semua term
perjumlahan, maxterm
Maxterm
dan Bentuk Kanonik POS
• Untuk sebuah fungsi dengan n
buah variabel f (x1, x2 . . . xn)
• Sebuah maxterm dari f adalah
satu term penjumlahan dari n
variabel yang
ditampilkan sekali baik dalam bentuk tidak diinverskan
maupun diinverskan
_ Jika diberikan satu baris dalam tabel kebenaran, maxterm
dibentuk dengan
memasukkan variabel xi jika xi = 0 atau xi
jika xi = 1
_ Notasi Mj (dengan
huruf M besar) merupakan maxterm dari
baris nomor j di tabel kebenaran. Contoh:
• Baris 1
(j = 0), x1 = 0, x2 = 0, x3 = 0
maxterm: M0 = x1 + x2 + x3
• Baris 2
(j = 1), x1 = 0, x2 = 0, x3 = 1
maxterm: M1 = x1 + x2 + x3
Maxterm
dan Bentuk Kanonik POS
• Tiap baris dari tabel
kebenaran membentuk satu
buah maxterm
• Fungsi f dapat dinyatakan
dengan ekspresi perkalian
dari semua maxterm di
mana
tiap maxterm di-OR-kan
dengan nilai f yang
bersesuaian
Baris i x1 x2 x3 maxtermMi f
0 0 0 0 x1 +x2 +x3 0
1 0 0 1 x1 +x2 +x3 1
2 0 1 0 x1 +x2 +x3 0
3 0 1 1 x1 +x2 +x3 0
4 1 0 0 x1 +x2 +x3 1
5 1 0 1 x1 +x2 +x3 1
6 1 1 0 x1 +x2 +x3 1
7 1 1 1 x1 +x2 +x3 0
• Contoh: diberikan nilai f
seperti tabel di atas, bentuk kanonik POS:
f = (M0 + 0) (M1
+ 1) (M2 + 0) (M3 + 0) (M4 + 1) (M5 + 1) (M6 + 1) (M7 + 0)
=
M0 ·M2 ·M3 ·M7
=
(x1 + x2 + x3) (x1 + x2 + x3) (x1 + x2 + x3) (x1 + x2 + x3)
Notasi
POS
• Persamaan POS dapat dinyatakan
dalam notasi M
f = M0 ·M2 ·M3 ·M7
=
(x1 + x2 + x3)
| {0z }
· (x1 + x2 + x3)
| {2z }
· (x1 + x2 + x3)
| {3z }
· (x1 + x2 + x3)
| {7z }
• Notasi Persamaan SOP: f = QM(0, 2, 3, 7)
• Persamaan berikut benar untuk
fungsi f (x1, x2, x3)di
atas:
Xm(1, 4, 5, 6) = YM(0, 2, 3, 7)
x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 = (x1 + x2 + x3) (x1 + x2 + x3)
(x1 + x2 + x3) (x1 + x2 + x3)
Konversi
Bentuk POS-SOP
• Jika suatu fungsi f diberikan dalam bentukPm atau QM, maka
dengan mudah dapat
dicari fungsi f atau f dalam bentukPm atau
QM
Bentuk Fungsi dan Bentuk
yang Diinginkan
Asal f = Pm f = QM f = Pm f = QM
f = Pm
(1,4,5,6)
- Nomor yg tdk
ada dlm
daftar
(0,2,3,7)
Nomor yang
tdk ada dlm
daftar
(0,2,3,7)
Nomor yang
ada dlm
daftar
(1,4,5,6)
f = QM
(0,2,3,7)
Nomor yg tdk
ada dlm
daftar
(1,4,5,6)
- Nomor yang
ada dlm
daftar
(0,2,3,7)
Nomor yg tdk
ada dlm
daftar
(1,4,5,6)
•
Penyederhanaan
Rangkaian dengan Aljabar
• Suatu fungsi logika dapat
dinyatakan dalam beberapa bentuk ekspresi yang ekivalen
_ Misalnya: f1 = x1x2 + x1x2 + x1x2 dan f2 = x1 + x2 adalah ekivalen
secara fungsional
_ Proses optimasi memilih salah satu dari beberapa rangkaian
ekivalen untuk
memenuhi constraint
nonfungsional (area, cost)
_ Catatan: rangkaian dengan jumlah gerbang minimal bisa jadi bukan
merupakan solusi
terbaik, tergantung constraintnya. Misalnya constraint delay
Fungsi: f = x1x2 + x1x2 + x1x2
• Replikasi term 2: f = x1x2 +x1x2 +x1x2 +x1x2
• Distributif (12b): f = x1 (x2 + x2) + (x1 + x1) x2
• Teorema (8b): f = x1 · 1 + 1 · x2
• Teorema (6a): f = x1 + x2
Rangkaian
Logika dengan NAND dan NOR
• Fungsi
NAND adalah inversi fungsi
AND
f(x1, x2) = f1(x1, x2) = x1 · x2
• Gerbang NAND merupakan gerbang
AND yang diikuti gerbang
NOT
• Fungsi NOR adalah inversi
fungsi OR
f(x1, x2) = f1(x1, x2) = x1 + x2
• Gerbang NOR merupakan gerbang
OR yang diikuti gerbang
NOT
• Rangkaian AND-OR (bentuk SOP)
dapat dikonversi menjadi
rangkaian NAND-NAND
• Bentuk ekspresinya: inverskan
minterm, ganti (+) dengan (.), inverskan ekspresi
_ Contoh: f = Pm(1, 4, 5, 6)
f = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3
=
x1x2x3 · x1x2x3 · x1x2x3 · x1x2x3
Rangkaian
OR-AND dan NOR-NOR
• Rangkaian OR-AND (bentuk POS)
dapat dikonversi menjadi
rangkaian NOR-NOR
• Bentuk ekspresinya: inverskan
maxterm, ganti (.) dengan (+), inverskan ekspresi
• Contoh: f = QM(0, 2, 3, 7)
f = (x1 + x2 + x3) (x1 + x2 + x3) (x1 + x2 + x3) (x1 + x2 + x3)
=
x1 + x2 + x3_ + x1 + x2 + x3_ + x1 + x2 + x3_ + x1 + x2 + x3_
Tidak ada komentar:
Posting Komentar