ALJABAR BOOLEAN
TUJUAN Daftar mengenai 17 hukum dan teorema aljabar Boolean diberikan pada halaman 40 unit ini. Ketika anda menyelesaikan unit ini, anda akan mengenal dengan baik dan dapat menggunakan setiap hukum dan teorema sebelas hukum pertama aljabar Boolean ini. Secara khusus anda akan dapat :
1. Memahami operasi dan hukum dasar aljabar Boolean. 2.
Menghubungkan operasi dan hukum ini ke jaringan yang terdiri dari simbol AND , simbol OR, dan INVERTER. Juga dapat menghubungkan operasi dan hukum ini ke jaringan yang terdiri dari hubungan switching.
3.
Membuktikan setiap hukum ini dengan menggunakan tabel "benar".
4.
Menerapkan hukum ini ke penghitungan pemyataan aljabar yang meliputi : a.
Mengkalikan pemyataan untuk mendapatkanjumlah hasil.
b.
Memfaktorkan engkapan untuk mendapatkan hasil penjumlahan
c.
Menyederhanakan pemyataan dengan menerapkan salah satu hukum tersebut.
PEDOMANBELAJAR I.
Dalam unit ini anda akan mempelajari aljabar Boolean, matematika dasar yang diperlukan untuk disain logika sistem digital. Ketika anda pertama kali mempelajari aljabar biasa, anda akan memerlukan sejumlah latihan sebelum anda dapat menggunakan aljabar Boolean secara efektif. Namun demikian, pada akhir pelajaran ini. anda akan sangat "kerasan" dengan aljabar Boolean seperti halnya dengan aljabar biasa. Untungnya,banyak aturan aljabar Boolean sama dengan aljabar biasa, namun perhatikan benar-benar untuk beberapa hal yang mengejutkan.
2.
Pelajarilah Bagian 2.1 dan 2.2 unit ini, Pengantar dan Operasi Dasar. (a) Bagaimana arti simbolO'dan I yang digunakan dalam unit ini berbeda dengan makna yang digunakan dalam Unit 1 ?
26
dO__O
_ __ ___0
- -----
(b) Dua notasi yang biasa digunakan untuk inversi atau komplemen dari A adalah A- atau A'. Yang kedua menguntungkan. karena memudahkan bagi pengetik. printer dan komputer. (Pernahkah "anda mencoba mendapatkan komputer yang dapat mencetak garis di atas huruf ?) Kita akan menggunakan A' untuk komplemen A. Anda dapat menggunakan notasi lain dalam pekerjaan anda. namun janganlah mencampurkan notasi dalam persamaan yang sarna. Kebanyakan para insinyur menggunakan + untuk OR dan _ (atau tidak ada simbol) untuk AND. dan kita akan mengikuti praktek ini. Suatu notasi altematif. seringkali digunakan oleh matematikawan adalah v untuk OR dan untuk AND. (c) Banyak simbol yang berbeda digunakan untuk blok logika AND. OR. dan INTERVER. I Lihat Bagian 8.6 dan Lampiran B.l untuk pembahasan simbol gerbang altematif. Kita akan menggunakan :
~for
.lL:r-
AND
~for ~OR
~for
~
INVERTER
Bentuk simbol ini disesuaikan dengan yang biasanya digunakan dalam prakterk indus.tri. Kita telah menambahkan + dan
·
untuk kejelasan. Simbol
di atas menunjuk pada arah arus tanda. Simbol ini memudahkan untuk membacadiagramjaringan dibandingkandengan simbolsimbolkotak atau lingkaran yang digunakan dalam beberapa buku. (d) Tentukan output masing-masing simbol berikut ini :
l 1
1Y'
,.+ ......
(e) Tentukan input yang tidak tertentu untuk masing-masing simbol berikut ini jika'outputnya adalah sebagai berikut: 27
o~ ~I 3.
Pelajarilah Bagian 2.3, Ungkapan Boolean dan Tabel Benar-salah (a) Berapavariabel-kahyang dikandungdalam pemyataanberikut ini ? Berapa literal ? A'BC'D + AB + B'CD + D'
=B =0 dan C = D =I. tunjukkanoutput dari setiap simbol (0 atau I) pada diagram jaringan :
(b) Untuk jaringan berikut ini, jika A
C D
F
(c) Derivasikan
pernyataan Boolean untuk output jaringan. Kernudian = B = 0 dan C = D = E = I ke dalarn pemyataan anda dan periksalah bahwa nilai F yang diperoleh dengan cara ini sarna dengan substitusikan
A
yan g diperoleh pada diagram jaringan dalarn (b). (d) Tulislah pemyataan untuk output jaringan berikut ini dan lengkapilah tabel kebenaran : A B
A'
A'B
IA'B)'
A F
F=
(e) Ketika rnengisi kornbinasi nilai untuk variabel di sebelah kiri suatu tabel kebenaran, selalu rnendaftar kombinasi 0 dan I dalam susunan biner. Misalnya, untuk tabel kebenaran variabel-3, baris pertarna hams 000, baris berikutnya 001, kernudian 010, 011, 100, 101, 110 dan 111. Tulislah pernyataan untuk output jaringan berikut ini dan lengkapilah tabel kebenaran :
28
ABC
8'
A + 8'
A F
B
F=
(t) Gambarlah jaringan simbol yang mempuntai output : Z
= [BC'
+ F(E + AD')]'
(Petunjuk : Mulailah dengan tanda kurung yang paling dalam dan gambarlah jaringan untuk AD' lebih dulu.) 4.
Pelajarilah Bagian 2.4, Teorema Dasar (a) Buktikan setiap teorema92-4) sampai(2-8D) dengan menunjukkanbahwa teorema ini valid untuk X=Odan X=I . (b) Tentukan output untuk masing-masing simbol berikut ini :
A A
. I:}-
.
: =E>-
:'=8-
:=8- :=8-
:'=E>- :=E>- :=E>-
(c) Tentukan manakah teorema dasar yang digunakan dalam penyederhanaan masing-masing pernyataan berikut ini : (AB' + C) (BC'
·0 = 0 A
+ A) (BC'
+ A)
(B + C') + I = I
= BC'+
(X' + YZ) (X' + YZ)'= 0
A
X(Y' + Z) + [X(Y' + Z)]' = I D'(E'+ F) +D'(E'+F) = D'(E'+F) 29
5.
Pelajarilah Bagian 2.5, Hukum Komutatif, Asosiatif, dan Distributif. (a) Nyatakan hukum asosiatif untuk OR. (b) Nyatakan hukum komutatif untuk AND. (c) Sederhanakanjaringan berikut ini dengan menggunakan hukum asosiatif. Jawaban anda hams memerlukan dua simbol saja. A
B
rL--/
C
D
) +)-G
E F
(d)
Untuk setiap simbol tentukan nilai input yang tidak tertentunya :
(e) Dengan menggunakan tabel kebenaran, periksalah hukum distributif, Persamaan (2-11).
(f)
Gambarkanlah hukum distributif, Persamaan (2-11) dan (2-IID), menggunakan simbol AND dan OR.
dengan
(g) Periksalah persamaan (2-3) dengan menggunakan hukum distributif kedua.
(h) Tunjukkan bagaimana hukum distributif kedua dapat digunakan untuk faktor RS + T.
30
6.
Pelajari Bagian 2.6 Penyederhanaan Teorema: (a) Oengan menyelesaikantabel kebenaran,buktikan bahwa XV' + Y = X + Y.
x
Y
0 0 I I
0 I 0 1
"
XY'
XY' + Y
II
I
X+Y
I
(b) Manakah dari teorema (2-12) sampai (2-140) yang diterapkan untuk menyederhanakan masing-masing pemyataan berikut ini ? Tentukan X dan Y pada masing-masing kasus. (A + B)(OE)' + DE AB' + AB'C'O'
= A + B + DE
= AB'
(A' + B) (CD +E') + (A' + B)(CO + E')' (A + BC'.+ O'E) (A + O'E)
(c)
=A
= A'
+ B
+ O'E
Sederhanakan jaringan berikut ini menjadi satu simbol ; A B C D z=
31
(d)
7.
Kerjakan Permasalahan 2.1, 2.2(a) dan (c), 2.3, dan 2.14(a) dan (b).
Pelajarilah Bagian 2.7 Perkalian dan Pemfaktoran (a) Tunjukkan manakah dari pemyataan berikut ini yang merupakan bentuk hasil penjumlahan, bentuk penjumlahan hasil, atau bukan kedua-duanya : AB' + D'EF' + G (A + B'C') (A' +BC) AB' (C' + D + E') (F' + G) X'Y + WX (X' + Z) + A'B'C'
Jawaban anda atas pertanyaan ini akan meliputi hasil penjumlahan, satu penjumlahan hasil, dan dua "bukan keduanya", tidak harus dengan urutan tersebut. (b) Ketika mengalikan sebuah pemyataan, bila memungkinkan mengapa hukum distributif yang kedua hams diaplikasikan sebelum hukum distributif biasa ? (c) Faktorkan sebanyak mungkin dengan menggunakan hukum distributif biasa:
AD + B'CD + B'DE Sekarang, faktorkan hasil anda dengan menggunakan hukum distributif kedua untuk mendapatkan hasil penjumlahan. (d)
8.
32
Kerjakan Permasalahan 2.6(a) dan (b), 2.9, dan 2.12(a) dan (b).
Mungkin bagian unit ini yang paling sulit adalah menggunakan hukum distributif yang kedua untuk memfaktorkan atau mengalikan sebuah pernyataan. Jika anda mempunyai kesulitan dengan Permasalahan 2.6 atau 2.9, atau and a tidak dapat mengerjakannya dengan cepat, pelajarilah contoh dalam Bagian 2.7 kembali, clan kemudian kerjakanlah permasalahan berikut 1111.
___ __u___
___- __ ____n_____
Kalikanlah : (a)
(B' + D + E) (B' + D + A)(AE + C')
(b)
(A + C')(B' + D) (C' + D')(C + D)E
Seperti biasanya, ketika kita katakan kalikanlah, kita tidak bennaksud untuk mengalikan dengan kekuatan kasar, namun dengan menggunakan hukum distributif kedua apakah anda dapat memotongjumlah kerja yang diperlukan. Jawaban untuk (a) di atas harus dalam bentuk berikut ini : XX + XX + XX + dan (b) dalam bentuk : XXX + XXXXX, di mana setiap X mewakili variabel tunggal atau komplementnya. Sekarang, faktorkanlahjawaban anda ke (a) untuk melihat apakah anda dapat kembali ke pemyataan aslinya. 9.
Ulangilah ke-sebelas hukum dan teorema yang pertama pada halaman 40. Yakinlah bahwa anda dapat mengenali ketika menerapkannya bahkan ketika sebuah ungkapan telah diubah untuk suatu variabel.
10. Bacalah kembali tujuan unit ini. Jika anda puas bahwa anda dapat memenuhi tujuan ini, tempuhlah uji kesiapan. (Catalan : Anda akan diberi salinan lembaranteorema (halaman 40) ketika anda menempuh uji kesiapan saat ini. Namun, sampai akhir Unit 3, anda hams mengetahui semua teorema di luar kepala.)
ALJABARBOOLEAN 2.1 PENGANTAR Matematika dasar yang diperlukan untuk mempelajari disain logika sistem digital adalah aljabar Boolean.33 George Boole mengembangkan aljab~ tahun 1847 dan menggunakannya untuk memecahkan permasalahan dalam logika matematis. Claude Shannon pertama kali menerapkan aljabar Boolean untuk disain jaringan pertukaran pada tahun 1939. 33
.,
Aljabar Boolean mempunyai banyak aplikasi lain termasuk rangkaian teori dan logika matematika, namun kami akan membatasi penerapannya pada jaringan switching dalam buku ini. Karena semua alat switching yang akan kita gunakan pada dasamya alat dua-keadaan (seperti transistor de~gan output voltasi tinggi atau rendah), kita akan mempelajari kasus khusus aljabar Boolean di mana semua variabel mengasumsikan hanya salah satu dari dua nilai tersebut. Aljabar Boolean dua nitai ini sering ditunjuk sebagai aljabar switching. Kita akan menggunakan variabel Boolean, seperti X atau Y, untukmewakili input atau output jaringan switching. Kita akan mengasumsi~an bahwa setiap variabel ini hanya dapat mengambil pada dua nilai yang berbeda. Simbol "0" dan "I" digunakan untuk mewakili dua nilai yang berbeda ini. Jadi, jika X adalah variabel (switching) Boolean, maka X = 0 atau X = I. Meskipun simbol 0 dan I digunakan dalam bab ini seperti bilangan biner, namun mereka bukan bilangan biner. Mereka tidak mempunyai nilai numerik, namun hanya merupakan dua simbol yang mewakili dua nilai variabel yang bertukar. Simbol 0, misalnya, mungkin berkorespondensi pada voltase rendah dan I mungkin berkorespondensi dengan voltase tinggi. F dan T dapat digunakan juga seperti 0 dan I.
2.2 OPERASIDASAR Operasi dasar aljabar Boolean adalah AND, OR, dan komplemen ( atau inversi). Komplemen dari 0 adalah I, dan komplemen dari I adalah O. Secara
simbolik,kita tulis
:
O'=ldanl'=O di mana tanda (') menFlndakan komplementasi. Jika X adalah variabel bertukar, X'
= I jika X = 0,
dan X'
= 0 jika
X
= I.
.Nama lain untuk komplementasi adalah inversi, dan sirkuit elektronik yang membentuk inversi X ditunjuk sebagai inverter.Secara simbolik, kita menampilkan inverter dengan ,
34
di mana lingkaran pada output menunjukkan inversi. Jika logika 0 berkoresponden dengan voltase rendah dan logika I berkoresponden dengan voltase tinggi, maka voltase rendah pada input inverter menghasilkan voltase tinggi pada output dan demikian pula sebaliknya. Komplementasi kadangkala ditunjuk sebagai operasi NOT karena X = I jika X tidak sarna dengan O. Operasi AND dapat didefinisikan sebagai berikut :
o
0=00
1=0
I
0=01
I=I
di mana "." menandakan AND. (Meskipun tanda ini seperti perkalian biner, namun bukan merupakan perkaian biner karena 0 dan I di sini adalah konstan Boolean, bukan bilangan biner). Jika kita menulis pemyataan Boolean C = A_B, maka nilai A dan B yang dapat menentukan C dari tabel berikut ini : A
B
0 0
0 I
I
0
I
I
C=A.B I
I !
I I
I
0 0
0 I
Perhatikan bahwa C = I jika (jika dan hanya jika) A dan B keduanya adalah I, oleh karenanya namanya operasi AND. Simbollogika yang mewakili operasi AND ditampilkan sebagai berikut ,
Simbol "." seringkali dihilangkan dalam pemyataan Boolean, dan biasanya kita akan menulis AB daripada A_B. Operasi ANDjuga ditunjuk sebagai perkalian logika (atau Boolean) . 35
Operai ORR dapat didefinisikan sebagai berikut : 0+0=00+1=11+0=11+1=1 di mana "++ menandai OR. Jika kita menulis C = A+B, maka dari nilai A dan B yang ada kita dapat menentukan C dari tabel berikut ini :
A
B
C=A+B
0 0 I 1
0 I 0 I
0 1 I I
Perhatikan bahwa C = I jika A dan B ( atau keduanya) adalah I, oleh karenanya dinamakan operasi OR. Jenis operasi ini kadangkala ditunjuk sebagai "OR inklusif', Simbol logika yang menampilkan operasi OR diwakili oleh
Operasi OR juga ditunjuk sebagai penambahan logika (atau Boolean). Sirkuit elektronik yang mewujudkan inverter dan simbol AND dan OR digambarkan dalam Lampiran A. Selanjutnya, kita akan menerapkan aljabar switching untuk menggambarkan jaringan yang berisi hubungan switching. Kita akan memberi label pada masingmasing hubungan dengan sebuah variabel. Jika hubungan X dibuka, maka kita akan menentukan nilai X, menjadi 0; jika hubungan X ditutup, maka kita akan menentukan nilai X menjadi 1.
Keterangan:
36
I. hubungan terbuka 2. hubungan tertutup
Sekarang perhatikan jaringan yang terdiri dari dua hubungan serioKita akan menentukan transmisi di antara tenninal sebagai T = 0 jika terdapat sirkuit terbuka di antara terminal dan T = I jika sirkuit tertutup di antara tenninal tersebut.
Keterangan:
I. sirkuit terbuka di antara terminal I dan 2 2. sirkuit tertutup di antara tenninal I dan 2
Sekarang kita telah mempunyaisirkuit tertutup di antara tenninal I dan 2 (T = I) jika (jika dan hanya jika) hubungan A ditutup dan hubungan B ditutup. Nyatakan hal ini secara aljabar,
Berikutnya, perhatikan suatujaringan yang terdiri dari duahubungan paralel.
Dalam kasus ini, kita mempunyai sirkuit tertutup antara terminal I dan 2 jika hubungan A ditutup atau hubungan B ditutup. Dengan menggunakan konversi yang sarna untuk menentukan variabel seperti di atas, sebuah persamaan yang
menggambarkankeadaanjaringan ini adalah
:
T=A+B Jadi, hubungan seri menampilkan operasi AND dan hubungal) paralel menampilkan operasi OR.
37
2.3 PERNYATAAN BOOLEANDANTABEL"BENAR-SALAH" Pemyataan Boolean dibentuk dengan menerapkan operasi dasar pada satu pada satu variabel atau konstan. Pemyataan yang paling sederhana terdiri dari sebuah konstan atau variabel, seperti 0, X, atau Y'. Pemyataan yang lebih rumit dibentuk dengan mengkombinasikan dua ungkapan atau lebih dengan menggunakan AND atau OR atau dengan mengkomplementasikan pemyataan
yang lain. Contoh pemyataanini adalah,
.
AB' +C [A(C + D»)' + BE Tanda kurung ditambahkan ketika diperlukan untuk menentukan urutannya di mana operasi terse but diwakili. Ketika tanda kurung ini dihilangkan, komplementasi dilakukan pertama kali diikuti dengan AND dan kemudian diikuti dengan OR. Jadi dalam (2-1), B' dibentuk pertama kali, kemudian AB' dan akhimya AB' + C. Masing-masing pemyataan berkorespondensisecara langsung denganjaringan simbol logika. Gambar 2-1 memberikan jaringan untuk Pemyataan (2-1) dan (22) di atas. Suatu pemyataan dievaluasi dengan mensubstitusi nilai 0 atau I untuk setiap variabel. Jika A = B = C = 1 dan D = E = 0 , nilai Pemyataan (2-2) adalah
[A(C + D»)' +BE
= [1(1 + 0»)' +
I
·
0
= [1(1»)' + 0 = 0 + 0 = 0
Masing - masing ke~unculan variabel atau komplemennya dalam pemyataan tersebut akan ditunjuk sebagai literal. Jadi, pemyataan berikut ini, yang mempunyai 3 variabel, mempunyai 10 literal :
ab'c + a'b + a'bc + b'c'
38
(AB' + C)
B (a)
C [A (C + D»)'
D
[A (C+D))'+ BE B E (b)
Gambar 2-/ Jaringan untuk Pemyataan
A---I .
F=A'+B
(2-/) dan (2-2) AB
A'
00
1 1 0 0
o 1 (a)
1 0 1 .1
F-A'+B 1 1 0 1 (b)
Gambar 2-2 Jaringan 2 inpit dan Tabel "Benar-salah"
Ketika suatu pemyataan diungkapkan dengan menggunakan simbol logika. setiap r ..;raldalam pemyataan berkorespondensi dengan simbol input. Tabel "KeOOnaran"Uuga disebut taOOIkombinasi} menentukan nilai suatu pemyataan Boolean untuk setiap kombinasi nilai variaOOIyang memungkinkan dalam pemyataan. Nama taOOI"keOOnaran"tersebut OOrasaldari tabel yang.serupa yang digunakan dalam logika simbolik untuk mendaftar "benar" atau "salah" dalam sebuah pemyataan dengan OOrbagaikeadaan yang memungkinkan. Kita dapat menggunakan taOOIkebenaran ini untuk menentukan nilai output untuk jaringan simbol logika dalam OOntuknilai variabel input. Output jaringan dalam Gambar 2-2 (a) adalah F = A' + B. Gambar 2-2 (b) menunjukkan sebuah tabel kebenaran yang menentukan output jaringan untuk semua kombinasi nilai yang memungkinkan dari A dan B, dan kolom berikutnya memberikan nilai yang berkorespondensidari A' . Kolom terakhir yang memberikan nilai A' + B, dibentuk 39
_u
- -
-
___
___
- -
-- -----
-
oleh pernbuatan OR bersarna dengan nilai yang berkorespondensi dari A' dan B pada setiap baris. Berikutnya, kita rnenggunakan tabel kebenaran ini untuk rnenentukan nilai Pemyataan (2-1) untuk sernua kornbinasi nilai yang rnernungkinkan dari variabel A, B, C. Pada sisi sebelah kiri dari Tabel 2-1 kita rnernbuat daftar nilai variabel A, B, dan C. Karena rnasing-rnasingdari tiga variabel ini dapat rnengasurnsikan nilai 0 atau 1, rnaka terdapat kornbinasi nilai variabel 2 x 2 x 2 = 8. Kornbinasi ini dengan rnudah dapat diperoleh dengan:rnernbuat daftar bilangan biner 000, 00 I, ..., Ill. Pada tiga kolorn berikutnya dalarn tabel kebenaran ini, kita rnenghitung B', AB' dan AB' + C, secara berurutan. Oua pemyataan disebut sarna bila rnernpunyai nilai yang sarna untuk setiap kornbinasi variabel yang rnungkin. Pemyataan (A + C) (B' + C) dievaluasi dengan rnenggunakan tiga kolorn terakhir pada Tabel 2-1. Karena pemyataan ini rnernpunyai nilai yang sarna dengan AB' + C untuk ke-delapan kornbinasi nilai variabel A, B, dan C, kita sirnpulkan : AB' + C
= (A
+ C) (B' +C)
Jika suatu pemyataan rnernpunyai variabel n, dan rnasing-rnasing variabel bisa rnernpunyai nilai 0 atau I, bilangan kornbinasi nilai variabel yang berbeda adalah : 2 x 2 x 2 x ...
= 2"
n kali Oleh karenanya, tabel kebenaran untuk pernyataan variabel-n akan mernpunyai baris 2".
2.4 DALILDASAR Oalil dasar aljabar Boolean berikut ini hanya rneliputi variabel tunggal : Operasi dengan 0 dan 1
X+O=X X+I=X 40
(2-4) (2-5)
(2-40) (2-50)
Hukum Idempoten
X +X
=X
(2-60)
(2-6)
Hukum Involusi (X')'
=X
(2-7)
Hukum Komplementaritas X + X'
=1
X
(2-8)
· X'=0
(2-80)
Masing-masing dalil ini dengan mudah dibuktikan dengan menunjukkan bahwa dalil ini valid untuk nilai yang memungkinkan dari X. Misalnya, untuk membuktikan X + X' = I, kita mengobservasi bahwa jika, X
= 0, 0 + 0' = 0 + I = I,
dan jika X = I, I + 1'= 1 + 0 = 1
Setiap pemyataan dapat disubstitusikan untuk variabel Xuntuk variabel X dalam dalil ini. Jadi, dengan Oalil (2-5), (AB' + 0) E + 1 = 1. dan dengan Oalil (2-80), (AB' + O)(AB' + 0)'
=0
Kita akan mengilustrasikan beberapa dari dalil dasar dengan jaringan switching. Seperti sebelumnya, 0 akan mewakili sirkuit terbuka atau hubungan terbuka dan 1 akan mewakili sirkuit tertutup atau hubungan tertutup.Jika kedua hubungan ini diberi label dengan variabel A, maka ini berarti bahwa kedua hubungan terbuka ketika A = 0 dan keduanya tertutup ketika A = I. Jadi jaringannya
41
--
---
--
dapat diganti dengan hubungan tunggal :
Hal ini rnenggarnbarkan dalil A
·A =
A. Dernikian pula,
yang rnenggarnbarkan dalil A + A = A. Hubungan paralel dengan sirkuit terbuka sarna dengan hubungan sendiri
. (A+ 1
= 1)
sernentara hubungan paralel dengan sirkuit pendek sarna dengan sirkuit pendek.
(A + 0 = A)
42
Jika suatu hubungan diberi label A', kemudian hubungan ini terbuka ketika A tertutup, dan demikian pula sebaliknya. Oleh karenanya A paralel dengan A' dapat diganti dengan sirkuit tertutup karena satu atau yang -lain dari kedua hubungan ini selalu tertutup.
. ~A+
A'
= ))
Demikian pula, hubungan seri A dengan A' dapat diganti dengan sirkuit terbuka (mengapa ?)
. .
.
2.5 HUKUMKOMUTATlF, ASOSIATlF, DANDISTRIBUTIF Kebanyakan hukum aljabar biasa, seperti hukum komutatif dan asosiatif, juga menerapkan aljabar Boolean. Hukum komutatif untuk AND dan OR yang mengikuti secara langsung dari definisi operasi AND dan OR, adalah : XY=YX
(2-9)
X+Y=Y+X
(2-9D)
Ini berarti bahwa urutan di mana variabel tersebut ditulis tidak akan mempengaruhi hasH penerapan operasi AND dan OR.
Hukum asosiatif juga menerapkan AND dan OR : 43
-
--
-
-
-
-
= X(YZ) = XYZ + Z = X + (Y+Z) = X + Y
(2-10)
(XY)Z (X + Y)
(2-10D)
+ Z
Ketika membentuk AND (atau OR) dati tiga variabel, hasilnya tergantung pada pasangan variabel yang dita asosiasikan bersama, maka tanda kurung dapat dihilangkan 'seperti ditunjukkan dalam Persamaan (2-10) dan (2-IOD). Kita akan membuktikan hukum asosiatif untuk AND dengan menggunakan tabel "kebenaran" (Tabel 2-2). Pada sisi sebelah kiri dari tabel tersebut, kita membuat daftar semua nitai kombinasi variabel X, Y, Z. Pada dua kolom berikutnya dari tabel "kebenaran" ini, kita menghitung XY dan YZ untuk setiap nitai kombinasi X, Y, Z. Akhirnya, kita menghitung (XY)Z dan X(YZ). Karena (XY)Z dan X(YZ) sama untuk semua kombinasi nilai variabel yang mungkin, maka kita simpulkan bahwa Persamaan (2-10) valid. Gambar 2-3 menggambarkan hukum asosiatif dengan menggunakan simbol AND atau OR. Dalam gambar 2-3 (a) dua simbol AND 2 input diganti dengan satu simbol AND 3 input. Demikian pula dalam Gambar 2-3(b) dua simbol OR 2 input diganti dengan satu simbol OR 3 input. Ketika dua variabel atau lebih di-AND-kan bersama, maka nilai hasil tersebut akan menjadi I jika semua variabel mempunyai nilai 1. Jika setiap variabel mempunyai nilai 0, maka hasil operasi AND akan O. Misalnya,
XYZ
= 1 jika
X
=Y =Z = 1
Tabel 2-2 Pembuktian Hukum Asosiatif AND XYZ 000 001 010 o 11 100 101 110 1 11 44
II
XY
YZ
0 0 0 0 0 0 1 1
0 0 0 1 0 0 0 1
I
(XY)Z
X(YZ)
!
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
lAB)
C =ABC (a)
IA + B) + C
=A + B + C
(b)
Gambar 2-3 Hukum Asosiatif untuk AND dan OR
Ketika dua variabelatau lebihdi-OR-kan bersama, nilai hasilnya akan menjadi 1 jika setiap variabel mempunyai nilai I. Hasil operasi OR akan 0 jika semua variabel mempunyai nilai O. Misalnya, X +Y+Z
= 0 jika
X
=Y =Z =0
Oengan menggunakan tabel "kebenaran", memudahkan untuk menunjukkan bahwa hukum distributif valid : X(Y + Z)
= XY + XZ
(2-1.1)
Lagi pula untuk aljabar biasa , hukum distributif yang kedua itu valid untuk aljabar Boolean namun tidak valid untuk aljabar biasa:
X + YZ
= (X
+ Y)(X + Z)
(2-110)
Bukti dari hukum distributif kedua adalah sebagai berikut : (X + Y)(X +Z)
= X(X
+ Z) + Y(X + Z)
= XX + XZ + YX + YZ
= X + XZ + XY + YZ = X
·
(dengan (2-11»
1 + XZ + YZ
(dengan (2-60) dan (2-40»
= X( 1 + Z + Y) + YZ. = X_I
+YZ
= X + YZ
«dengan (2-11) dan (2-5» 45
Hukum distributif biasa menyatakan bahwa operadi AND mendistribusikan melampaui OR, sementara huku'm distributif kedua menyatakan bahwa OR mendistribusikan melebihi AND. Hukum kedua ini sangat berguna dalam menghitung pemyataan Boolean. Khususnya, pemyataan seperti A + BC, yang tidak dapat difaktorkan dalam aljabar biasa, secara mudah difaktorkan dengan menggunakanhukumdistributifkedua : A + BC = (A + B) (A + C)
2.6 TEOREMAPENYEDERHANAAN Teorema berikut ini bermanfaat dalam penyederhanaan kalimat Boolean : Xy + Xy' = X
(2-12)
(X + y)(X + Y')=X
(2-120)
X+Xy=X
(2-13)
X(X+y)
(2-130)
(X + Y')Y = Xy
(2-14)
Xy'
= X
+ Y = X + Y
(2-140)
Pada setiap kasus, satu kalimat dapat diganti dengan kalimat yang lebih sederhana. Karena masing-masing kalimat berkorespondensi dengan jaringangerbang logika, dengan menyederhanakan sebuah kalimat yang mengarah pada penyederhanaan jaringan logika berkorespondensi. Setiap teorema di atas dapat dibuktikan dengan menggunakan tabel kebenaran, atau mereka dapat dibuktikan secara aljabar dimulai dengan teorema dasar. X + Xy = X.l + XY = X(1+Y) = X.l = X
Pembuktian dari (2-13) :
Pembuktian dari (2-130) : X(X+Y) = XX + XY = X + XY = X (dengan (2-60) dan (2-13)) Pembuktian dari (2-140)
:
Y + XY' =(Y + X)(Y + Y') = ( Y + X) 1= Y + X (dengan (2-110) dan (2-8))
Pembuktian terhadap teorema yang lain dapat dilakukan seperti latihan di atas.
46
Kita akan menggambarkan Teorema (2-14D) dengan menggunakan katup. Perhatikan jaringan berikut ini :
Transmisinya adalah T =Y + XY' karena terdapat sirkuit tertutup di antara terminal jika katup Y ditutup atau katup X ditutup dan katup Y' ditutup. Jaringan berikut ini ekuivalen karenajika Y ditutup (Y= I) pada keduajaringan mempunyai transmisi I; jika Y dibuka (Y' = 1) pada kedua jaringan mempunyai transmisi
x.
Contoh berikut ini mengilustrasikan penyederhanaanjaringan gerbang logika dengan menggunakan salah satu teorema. Dalam gambar 2-4, output jaringan (a) adalah
F
= A(A'
+ B)
Dengan teorema (2-14), kalimat untuk F menyederhanakan AB. Oleh karena itu, jaringan (a) dapat diganti dengan jaringan ekuivalen (b). I" A
_
F (a)
A
. =G-
A-L-/ B. Gambar 2-4 Jaringan Gerbang Ekuivalen
F (b)
47
Setiap kalimat dapat disubstitusikan untuk X dan Y dalam teorema tersebut.
CONTOH 1
Sederhanakan Z
= A'BC
+ A'
Kalimat ini mempunyai bentuk yang sama dengan (2-13) jika kita membiarkan dan Y = Be. Oleh karena itu kalimat ini menyederhanakan ke Z = X + XY X = A'. X
= A'
=
CONTOH 2
Sederhanakan
Substitusi :
Z
= [A +
Z=[ X
--
-
B'C + D + EF][A + B"C + (D + EF)']
+
Y
][
+
X
Y'
Kemudian dengan (2-12D), kalimat tersebut berkurang menjadi Z + X A + B'C
CONTOH 2
-
= (AB - + C)(B'D + C'E') + (AB + C)' Substitusi Z= Y' X + Y Dengan (2-14D): Z = X + Y = B'D + C'E' + (AB + C)' Sederhanakan
Z
Perhatikan bahwa dalam contoh ini kita membiarkan Y = (AB + C)' daripada (AB + C) agar supaya cOl:okdengan bentuk (2-14D).
2.7 MENGALIKAN DANMEMFAKTORKAN Dua hukum distributif digunakan untuk mengkalikan suatu kalimat untuk mendapatkan bentuk jumlah yang dihasilkan. Suatu kalimat dikatakan bentuk jumlah hasil ketika semua hasil merupakan hasil dari satu variabel tunggal saja. 48
Bentuk ini merupakanakhir dari hasHketika sebuah kaIimat benar-benardikaIikan. Biasanya mudah untuk mengenali kalimat hasH penjumlahan karena ia terdiri dari bentuk jumlah hasH: AB' + CD'E + AC'E'
(2-15)
Namun demikian, dalam kasus penurunan, satu bentuk hasHatau lebih dapat terdiri dari variabel tunggal. Misalnya, (A~C' + DEFG + H
(2-16)
A + B" + C + D'E
(2-17)
dan
masih dianggap dalam bentuk jumlah- hasH. Kalimat (A + B) CD + EF bukan dalam bentuk jumlah hasH karena bentuk A + B memasuki ke dalam satu produk namun bukan merupakan variabel tunggaI. Ketika mengkalikan sebuah kalimat, hukum distribusi kedua harus diaplikasikan terlebih dahulu bila mungkin. Misalnya, untuk mengkalikan (A + BC)(A + D + E) jadikan X=A,
Y=BC,
Z=D+E
Kemudian, (X + Y)(X + Z)
= X + YZ = A + BC(D + E) = A + BCD + BCE
tentu saja, hasil yang sarna akan sulit diperoleh dengan mengkalikan kalimat asli secara lengkap dan kemudian menghilangkan bentuk sisanya : (A + BC)(A + D + E)
= A + AD + AE + ABC + BCD + BCE = A (1 + D + E + BC) + BCD + BCE
= A + BCD + BCE Anda akan menghemat banyak waktu jika anda belajar untuk .mengaplikasikan hukum distributif kedua seperti di atas, daripada sulit mengerjakan problem tersebut. 49
Kedua hukum distributif dapat digunakan untuk memfaktorkan kaliamt untuk mendapatkan bentuk jumlah - hasil. Suatu kalimat merupakanbentukjumlahhasil bila semua jumlah merupakan jumlah veriabel tungggal. Biasanya mudah untuk mengenali ka1imatjumlah hasil karena ia terdiri dari bentuk hasil dari penjumlahan :
(A + B)(C + 0' + E)(A + C' + E')
(2-18)
Namun demikian, dalam kasus penurunan, satu bentuk penjumlahan atau lebih dapat terdiri dari variabel tunggal. Misalnya, ( A + B')(C + 0 + E)F
(2-19)
dan AB'C(D'
+ E)
(2-20)
masih dianggap dalam bentuk hasil-penjumlahan, namun (A + B)(C + D) + .
EF bukan bentuk hasil-penjumlahan. Suatu kalimat dapat difaktorkan secara penuh
jika kalimat tersebut dalam bentuk hasil-penjumlahan. Setiap kalimat yang bukan dalam bentuk ini dapat difaktorkan lebih lanjut. Contoh berikut ini mengilustrasika.n bagaimana memfaktorkan dengan menggunakan hukum distributif kedua :
CONTOH X
1
Faktorkan A + B'CD. Kalimat ini merupakan bentuk dari X + YZ di mana Y = B' dan Z = CD, sehingga
= A,
A + B'CD = (X + Y)(X + Z) = (A + B')(A + CD)
A + CD dapat difaktorkan kembali dengan menggunakan hukum distributif kedua, sehingga : A + B'CD = (X + Y)(X + Z) = (A + B')(A + CD) 50
CONTOH 2 Faktorkan AB'+ CD.
AB' + CD
= (A
= (AB'
+ C)(B'
+ C')(AB' + D) .~
perhatikan bagaimana X + YZ =(X + Y)(X + Z) diaplikasikan di sini.
+ C')(A + D)(B' + D) ~
hukum distributif kedua diaplikasikan lagi pada masing-masing bentuk.
CONTOH 3 Faktorkan
C'D + C'E' + G'H
CD + C'E' + G'H
= C(D
+ E') + G'H f--
Pertamakali menerapkan hukum distribusi biasa, XY + XZ = X(Y + Z)
= ( C'
+ G'H)(D + E' + G'H)
= (C'+G')(C'+H)(D+E'+G')(D+E'+H)
kemudian menerapkan hukum distributif kedua ~
sekarang tentukan X, Y, dan Z pada masingmasing kalimat dan selesaikanlah pemfaktorannya
Seperti pada contoh 3 di atas, hukum distributif biasa harus diaplikasikan sebelum hukum kedua ketika memfaktorkan suatu kalimat. Suatu kalimat hasil-penjumlahan dapat selalu dinyatakan secara langsung dengan satu atau lebih AND dengan OR tunggal pada output jaringan. Gambar 2-5 menunjukkan jaringan untuk Persamaan (2-15) dan (2-17). Kebalikan diperlukan untuk menurunkan variabel komplementasi yang telah dihapus. Jaringan yang terlihat dalam Gambar 2-5 dan 2-6 seringkali ditunjuk sebagai jaringan dua-tingkat karena jaringan tersebut mempunyai mempunyai maksimum dua gerbang seri antara input dan jaringan output. 51
A B'
-
-
-
I
D EA
B' A e' E'
I
+
e
I
Gambar 2-5 Jaringan untuk Persamaan (2-15) dan (2-17)
A
--10-
B'-C/j
!
I C D' E
~~
D'
A B' C
.
E
E'~
Gambar 2-6 Jaringan untuk Persamaan (2-18) dan (2-20)
52
SOAL-SOAL 2.1
Buktikan teorema beikut ini secara 'aijabar : (a) X(X' + Y) = XY (b) (X + Y)(X + Z) = X + YZ (c) XY + XY' = X (d) (A + B)(A + B') = A
2.2
IIustrasikan teorema berikut ini dengan menggunakan jaringan. katup : (a) X + XY = X (b) XY + XY' = X (c)
(d)
X + YZ = (X + Y)(X + Z) (X + Y')Y= XY
Pada setiap kasus, jelaskan mengapa jaringan tersebut ekuivalen.
2.3
Sederhanakan masing-masing kalimat berikut ini dengan mengaplikasikan salah satu teorema. Sebutkanlall teorema yang digunakan (lihat hat. 40). (a) ABC' + (ABC')' (b) (AB + CD')(AB + D'E) (c) A + B'C + D'(A + B'C) (d) AB'(C + D) + (C + D)' (e) [(EF)' + AB + C'D'](EF) (t)
2.4
(AB + C) + D + EF)(AB + C)'
Ulangilah soal 2.3 untuk : (a) A'B'C + (A'B'C)' (b) A(B + C'D) + B + C'D (c) A + B + C'D(A + B)' (d) (A'B + CD')(A'B + CE) (e) [AB' + (CD)' + E'F]CD (t) (A' + BC)(D'E + F)' + (D'E + F)
53
2.5
Ulangilah Soal 2.3 untuk : (a)
(X + Y'Z)(X + Y'Z)'
(b) (W + X' + YZ)(W' + X' + YZ) (c) (V'W + X)'(X + Y + Z + V'W) (d) (V' + W'X)(V'
+ W'X + Y'Z)
(e) (W' + X)YZ' + (W' + X)'YZ' (t)
2.6
(V' + U + W)(WX + Y + UZ') + (WX + UZ' + Y)
Kalikanlah untuk mendapatkan penjumlahan hasil : (a) (A + B)(A + C')(A + D)(BC'D + E) (b) (A + B' + C)(B' + C + D)(A' + C) (c) (A + B'C + D)(B'C + D' + E)(A + E')(AD + E') (d) (A' + BE')(BE'
2.7
+ C + D)(E + C')
Kalikanlah untuk mendapatkan penjumlahan hasil : (a) (A' + B)(C' + B'D)(A + E ... B'D) (b) (A + B')(A + C + D')(A + B + D') (c) (A + B)(B + C)(B + D')(ACD'
+ E)
(d) (AB + C')(A + C')(A + B' + DE')(B'
2.8
+ C' + DE')
KaHkanlah untuk mendapatkan penjumlahan hasil : (a) (A + B')(A + C + D)(A + B' + D) (b) (A' + B)(A' + C)(C + D)(B + D)
2.9
Faktorkanlah masing-masing kalimat berikut ini untuk menda patkan hasil penjumlahan : (a) DE + F'G' (b) WX' + WY'Z' + WYZ
54
__.u.
_ h
(c) A'CD + E'F + BCD (d) ABE + D'E + ACE (e) ACD + C'D' + A'D' (t) H + U.' + K'L (jawaban harns mernpakan hasil empat bentuk, masing-masing sebagai jumlah dari tiga variabel).
2.10 Faktorkanlah masing-masing kalimat berikut ini untuk mendapatkan hasil penjumlahan : (a) H'I' + JK (b) ABC + A'B'C + CD' (c) AB' + ACD + ADE' (d) AB'C + BCD' + EF' (e) WX'Y + W'X' + W'Y' (t) AB' + (CD' + E) (jawaban harns mernpakan hasil dari 4 bentuk, masing-masing jumlah 3 variabel).
2.11 Faktorkanlah masing-masing kalimat berikut ini untuk mendapatkan hasil penjumlahan : (a) W + X'YZ (b) VW + XY' + Z (c) A'B'C + B'CD' + B'E' (d) ABC + ADE' + ABF'
2.12 Gambarkan suatu jaringan untuk menyatakan masing-masing fungsi 'berikut ini dengan hanya menggunakan satu gerbang AND dan satu gerbang OR: (a) (A + B + C + D)(A + B + C + E)(A + B + C + F) (b) WXYZ + VXYZ + UXYZ (c) ABCD + ABCE + ABCF (d) (W + X + Y + Z)(V + X + Y + Z)(U + X + Y + Z) 55
2.13 Garnbarlah jaringan untuk rnenyatakan fungsi berikut ini dengan rnenggunakan dua gerbang OR dan dua gerbang AND : F =(V + W + X)(V + X + Y)(V + Z)
2.14 Untuk rnasing-rnasing jaringan berikut ini, tentukan output dan buatlah disain jaringan yang lebih sederhana dengan output yang sarna. (Tentukan jaringan output dengan lebih dulu rnenernukan output pada rnasing-rnasing gerbang, dari kiri ke kanan, dan sederhanakanlah sekaligus).
A x
(al
B y A B (b)
z
(CI
56
2.15 Ulangilah soal 2.14 untuk : A
B
(a,
A
B (b)
A B'
A B (c)
2.16 Buktikan persamaan OOrikutini dengan menggunakan taOOIkeOOnaran: (a) W'XY + WZ = (W' + Z)(W + XV) (b) (~+ C)(AB + C')= AB + AC' 57
-
HUKUMDANTEOREMA ALJABARBOOLEAN Operasi dengan 0 dan I : 1. X+O=X 2. X + I = I
ID. X. I = X 2D. X. 0 = 0
Hukum Idempoten: 3. X + X = X
3D. X. X = X
Hukum Involusi: 4. (X')' = X Hukum komplementaritas : 5. X + X' = I
5D. X
Hukum Komutatif : 6. X + Y = Y + X
6D. XY
·
X'
=0
= YX
Hukum Asosiatif : 7.
(X + Y) + Z
= X + (Y + Z) =X+Y+Z
7D. (XY)Z= X(YZ) = XYZ
Hukum Distributif : 8.
X(Y + Z)
= XY + XZ
8D. X + YZ
= (X + Y)(X + Z)
Teorema penyederhanaan : 9.. XY + XY' = X 10. X + XY = X I
11. (X + Y')Y
58
= XY
9D. (X + Y)(X + Y') = X IOD. X(X + Y) = X lID. XY' + Y = X + Y
Hukum OeMorgan : 12. (X + Y + Z + ...)'
= X'Y'Z'...
120. (XYZ...)'= X'+Y'+Z'...
Oualitas : 14. (X + Y + Z + ...)D = XYZ...
140. (XYZ...)D=X + Y + Z + ...
Teorema untuk mengkalikan dan memfaktorkan : 16. (X + Y)(X' + Z)
= XZ + X'Y
160. XY + X'Z
= (X +-,Z)(X'+ Y)
Teorema Konsensus :
= Xy. + X'Z (X + Y)(Y + Z)(X' + Z) = (X + Y)(X'
17. XY + YZ + X'Z 170.
+ Z)
59
