PEN YEDERHANAA N
DENGAN ALJABAR
TUJUAN I.
Gunakanlah teorema konsensus untuk menghapuskan term pada kalimat switching dan menambahkan term ke kalimat tersebut.
2.
Sederhanakanlahkalimat switchingdengan menggunakan hukum dan teorema aljabar Boolean.
3.
Dengan sebuah persamaan, buktikan secara aljabar bahwa persamaan tersebut valid dan tunjukkan bahwa persamaan tersebut tidak valid.
PETUNJUKBELAJAR "I. Pelajarilah Bagian 4.1, Teorema Konsensus. Teorema konsensusomerupakan metode penting untuk menyederhanakan fungsi switching. (a) Dalam masing-masing kalimat berikut ini, carilah term konsensus dan hilangkan term tersebut : abc'd + a'be + be'de (a'+b + c)(a + d)(b + c + d) ab'c + a'bd + bcd' + a'bc
(b) Hilangkan dua term dari kalimat berikut ini dengan mengplikasikan teorema konsensus:
A'B'C + BC'D' + A'CD + AB'D' + BCD + AC'D'
(Petunjuk : Pertama kali, bandingkanterm pertama dengan masing-msaing term yang ada untuk melihatjika ada konsensus, maka bandingkan term kedua dengan masing-masing term yang lainnya, dst.)
96
(c) Pelajarilah contoh yang diberikan dalam Persamaan (4-3) dan (4-4) dengan hati-hati. Sekarang marilah kita mulai dengan bentuk kalimat empat-tenn (Persamaan 4-3):
A'C'D + A'BD + ABC + ACD' Dapatkah kalimat tersebut dikurangi menjadi tiga term dengan mengaplikasikan teorema konsensus tersebut ? Sebelum kita dapat mengurangi kalimat di atas, kita harus menambahkan tenn yang lain. Tenn manakah yang dapat ditambahkandengan mengaplikasikanteorema konsensus ? Tambahkan tenn ini dan kemudian kurangilah kalimat tersebut menjadi tiga tenn. Setelahpenguranganinidapatkahtenn yang ditambahkantersebut dihilangkan ? Bila tidak, mengapa ? (d) Hilangkanlah dua tenn dari kalimat berikut ini dengan mengaplikasikan teorema konsensus dual : (a' + c' + d)(a' + b + c)(a + b + d)(a' + b + d)(b + c' + d) Gunakanlah tanda kurung untuk menunjukkan bagaimana anda membuat tenn konsensus. (Petunjuk : Pertama kali, carilah konsensus dari dua tenn pertama dan hilangkanlah.)
(e) Derivasikan Teorema (3-12) dengan menggunakan teorema konsensus. (f)
2.
Kerjakan Latihan Program 4.1. Kemudian kerjakanlah Soal 4.4. dan 4.11.
Pelajarilah Bagian 4.2 Penyederhanaan secara Aljabar dari Kalimat Switchmg. (a) Teorema manakah yang digunakan untuk : Mengkombinasikan tenn ? Menghapus tenn ? 97
Menghapus literal ? Menambahkan term yang berlebihan ? Memfaktorkan atau mengkalikan ? (b) Perhatikan bahwa dalam contoh Persamaan (4-8), term yang berlebihan WZ' ditambahkan dan kemudian dihapuskan setelah digunakan untuk menghapuskanterm lain.Mengapabisa menghapuskanWZ' dalam contoh ini ? Jika sebuah term telah ditambahkan dengan teOl-emakonsensus, ia mungkin tidak selalu memungkinkan untuk menghapus term selanjutnya dengan teorema konsensus. Mengapa ?
(c) Anda memerlukan latihan yang memadai untuk mengembangkan ketrampilandalam menyederhanakankalimat switching.Kerjakan sampai Latihan Terprogram 4.2 dan 4.3. (d) Kerjakanlah Soal 4.7, 4.12, dan 4.14. p73 (e) Ketika menyederhanakan suatu kalimat dengan menggunakan aljabar Boolean, dua pertanyaan yang seringkali diajukan adalah : (I)
Oi mana saya harus memulai ?
(2) Bagaimana saya tahu bahwa saya telah selesai ? Oalam menjawabpertanyaanno (I), biasanyayang terbaik adalah mencoba teknik sederhana seperti mengkombinasikanterm atau menghapus term dan literal sebelum mencoba hal yang lebih rumit seperti menggunakan teorema konsensus atau menambahkan term yang berlebih. Pertanyaan no. (2) biasanya sulit untuk dijawab karena memungkinkan untuk menyederhanakanbeberapa kalimat tanpa terlebih dahulu menambahkan term berlebih. Biasanya kita akan menyebutkan berapa term untuk mendapatkanpemecahan minimum yang telah diminimalkan.Oalam Unit 6 dan 7, anda akan mempelajariteknikyang sistematikyang akan menjamin pencarian solusi minimum.
98
3.
Pelajarilah Bagian 4.3, Pembuktian Validitas suatu Persamaan (a) Ketika berusaha membuktikanbahwa suatu persamaan itu valid, bolehkah untuk menambahkan beberapa kalimat pada kedua sisi ? (b) Kerjakan Soal 4.18. (c) Tunjukkan bahwa (4-14) dan (4-15) mempertimbangkan x= 0 dan x=1.
adalah
benar
dengan
(d) Dengan a'(b + d') = a'(b + e'), "bukti" berikut ini menunjukkan bahwa d = e; a'(b + d') a + b'd
b'd
= a'(b
+ e')
= a + b'e = b'e
d=e Sebutkan dua hal yang salah dengan "pembuktian" tersebut. Berilah serangkaian nilai-nilai untuk a, b, c, dan e dan tunjukkan bahwa hasilnya tidak benar. 4.
Bacalah kembali tujuan dari Unit ini. Ketika anda rilerasa puas bahwa anda telah memenuhi tujuan tersebut, tempuhlah uji persiapan.
PENYEDERHANAAN SECARAALJABAR 4.1 TEOREMAKONSENSU$ Teorema konsensus sangat bermanfaat dalam menyederhanakan kalimat Boolean. Dengan kalimat berbentuk XY + X'Z + YZ bentuk YZ adalah redundan dan dapat dihilangkan untuk membentuk kalimat yang ekuivalen XY + X'Z. Term yang dihilangkan ditunjuk sebagai "term konsensus." Dengan sepasang teorema di mana sebuah variabel muncul dalam satu term dan komplemen variabel tersebut muncul dalam term lain, maka term konsensus dibentuk dengan mengkalikan dua term asli bersama, meninggalkan variabel yang dipilih dan komplemennya. Misalnya, konsensus ab dan a'c adalah be; konsensus abd dan b'de adalah (ad)(de')= ade'. Konsensus term ab'd dan a'bd' adalah O. 99
Teorema konsensus dapat dinyatakan sebagai berikut : XY + X'Z + YZ = XY + X'Z
(4-1)
Bukti : XY + X'Z + YZ
= XY + X'Z + (X + X')YZ = (XY + XYZ) + ( X'Z + X'YZ) = XY(l + Z) + x'Z(l + Y) = XY + X'Z
Teorema konsensus dapat digunakan untuk menghilangkan term redundan dari kalimat Boolean. Misalnya, dalam kalimat berikut ini, b'c adalah konsensus dari a'b' dan ab, sedangkan ab adalah konsensus ac dan be', sehingga kedua term konsensus dapat dihilangkan :
~
J,
a'b + ac + oc' + b'c + ab = a'b' + ac + be' ~ l' Tanda kurung di atas menunjukkan bagaimana term konsensus dibentuk. Bentuk dual dari teorema konsensus adalah (X + Y)(X' + Z)(Y + Z)= (X + Y)(X' + Z)
(4-2)
Perhatikan lagi bahwa kunci untuk mengenali term konsensus pertama kali harus mencari sepasang term, salah satunya berisi satu variabel dan yang lainnya berisi komplemen. Dalam kasus ini, konsensus dibentuk dengan menambahkan pasangan term ini bersama meninggalkan variabel terpilih dan komplemennya. Dalam kalimat berikut, (a + b + d') merupakan bentuk konsensus dan dapat dihilangkan dengan menggunakan teorema konsensus dua :
I~
I
(a + b + c')(a + b + d')(b + c + d')=(a + b + c')(b + c + d')
Hasil akhir yang diperoleh dengan aplit<.asiteorema konsensus mungkin tergantung padw susunan di mana term tersebut dihapuskan.
100
- ..- --- .-------
CONTOH :
A'C'D + A'BD + BCD + ABC + ACD'
(4-3)
Pertama kali lita menghapuskan BCD seperti terlihat di atas. (Mengapa BCD tersebut dapat dihapus ?) Sekarang BCD telah dihapus, sehingga tidak ada lagi, dan BCD tersebut tidak dapat digunakan untuk menghapus term lain. Periksalah semua pasangan term yang menunjukkan bahwa tidak ada term tambahan yang dapat dihapus dengan teorema konsensus. Sekarang kita mulai lagi : A'C'D + A'BD + BCD + ABC + ACD'
(4-4)
Sekarang kita tidak menghilangkan BCD, namun kita menghilangkan dua term lain dengan teorem akonsensus. Setelah melakukan hal ini, observasilah bahwa BCD tidak dapat dihilangkanlagi. Perhatikanbahwa kalimat yang dikurangi menjadi empat termjika BCD dihilangkan pertama kali, namun ia dapat dikurangi menjadi tiga term jika BCD tidak dihilangkan. Kadang-kadang tidak memungkinkan secara langsung mengurangi suatu kalimat menjadi jumlah term minimum dengan secara sederhana menghapuskan term begitu saja. Mungkin pertama kali perlu menambahkan sebuah term dengan menggunakan teorema konsensus dan kemudian menggunakan term tambahan untuk menghapus term l;ain. Misalnya, perhatikan kalimat berikut : F
= ABCD + B'CDE
+ A'B' + BCE'
Jika kita membandingkan setiap pasang term untuk melihat apakah sebuah term konsensus dapat dibuat, kita mencari term konsensus ACDE saja (dari ABCD dan B'CDE) dan A'CE'(dari A'B' dan BCE'). Karena tidak ada term konsensus semacam ini yang muncul dalam kalimat asli, kita tidak dapat secara langsung term dengan menggunakan teorema konsensus. Namun demikian, jika pertama kali kita menambahkan term konsensus ACDE ke F , maka kita dapatkan:
F
~
I
= ABCD+ B'CDE + A'B' T
I
I
I
I
+ BCE' + ACDE
101
Kemudian kita dapat menghapuskan ABCD dan B'CDE dengan menggunakan teorema konsensus, dan F berkurang menjadi : F
= A'B'
+ BCE' + ACDE
Term ACDE tidak menjadi redundan lagi dan tidak dapat dihapus dari kalimat terakhir. .
4.2 PENYEDERHANAAN SECARAALJABARDARIKALiMATSWITCHING Pada bagian ini kita akan menerapkan teorema aljabar Boolean untuk menyederhanakkan kalimat switching. Penyederhanaan ini penting karena penyederhanaan kalimat mengurangi biaya pernyataan kalimat dengan menggunakan gerbang. Selanjutnya kita akan mempelajari metode grafik untuk menyederhanakan fungsi s\'.itching, namun kita akan mempelajari metode aljabar terlebih dahulu. Lagi pula untuk mengkalikan dan memfaktorkan, tiga cara pokok menyederhanakan fungsi switching adalah mengkombinasikan term, dan menghapus literal. I.
Mengkombinasukan term. Gunakan teorema XY + XY'=X untuk mengkombinasikan dua term. CONTOH: abe'd' + abed'
= abd'
[X= abd', Y=e]
(4-5)
Ketika mengkombinasikan term dengan menggunakan teorem seperti di atas, dua term yang hams dikombinasikan hams berisi variabel yang tepat sarna, dan tepat salah satu variabel hams muncul dikomplementasikan dalam satu term dan bukan dalam term lain. Karena X + X
= X,
maka term yang ada
dapat diduplikasikan dan dikombinasikan dengan dua term yang lain atau lebih. CONTOH: ab'e + abe + a'be 102
= ab'e
+ abe + a'be = ae + be
Teorema tersebut masih dapat digunakan, tentu saja bila X dan Y diganti
dengan kalimatyang lebih rumit.
.
CONTOH: (a + bc)(d + e') + a'(b'+ c')(d + e') [X
2.
=d +
=d
+ e'
e', Y= a + bc, Y'= a'(b'+c')]
Menghapuskan term. Gunakan teorema X + XY = X untuk mengeliminasi term redundan bila memungkinkan; kemudian eobalah mengaplikasikan teorema konsensus (XY = X'Z + YZ = XY + X'Z) untuk menghapuskan setiap term konsensus. CONTOH : a'b + a'be a'be'+ bed + a'bd
3.
= a'b
[X
=.a'bc'+bcd
= a'b] [X=c, Y=bd, Z=a'b]
(4-6)
Menghapus literal. Gunakan teorema X + X'Y = X + Y untuk mengurangi literal redundan.Pemfaktoran sederhana mungkindiperlukan sebelum teorema tersebut diaplikasikan. CONTOH : A'B + A'B'C'D'+ ABCD'
= A'(B
+ B'C'D')+ ABCD'
= A'(B + C'D') + ABCD' = B(A'+ ACD') + A'C'D' = B(A'+ CD') + A'C'D'
= A'B + BCD' + A'e'D'
(4-7)
Kalimat yang diperoleh setelah mengaplikasikan 1,2, dan 3 di atas t!dak memerlukan jumlah term minimum atau jumlah literal minimum. Jika tidak, dan tidak ada penyederhanaan lebih lanjut yang dapat dibuat dengan menggunakan I ,2, dan 3, membebaskan pengantar term redundan mungkin diperlukan sebelum penyederhanaan lebih lanjut dapat dibuat. 103
4.
Menambahkan term redundan. Term redundan dapat diperkenalkan dengan berbagai cara seperti menambahkan xx', mengkalikan dengan (x + x'), menambahkan yz ke xy + x'z, atau menambahkan xy ke x. Bila memungkinkan, term yang ditambahkan tersebut. harus dipilih sehingga mereka akan mengkombinasikan atau menghapus term lain. CONTOH :
xw
+ XY + X'Z' + WY'Z' (tambahkan WZ' dengan teorema konsensus)
=WX + XY + X'Z' + WY'Z' + WZ' = WX + XY + X'Z' = WX + XY + X'Z'
(hilangkan WY'Z')
+ WZ' (hilangkan WZ') (4-8)
Contoh komprehensif berikut ini menggambarkan penggunaan keempat metode :
A'B'C'D'+ A'BC'D'+ A'BD + ABC'!} + ABCD + ACD'+ B'CD'
"
v
/
A'C'D'
= A'C'D'-+- BD(A'+
AC) + ACD'+ B'CD'
@
= A'C'D'+
A'BD + BCD + ACD' + B'CD'
~
+ ABC @)
konsensusACD'
~
= A'C'D'
+ -A'BD +"B€I)..+ ~
"
v
+ B'CD' + ABC /
konsensus BCD
= A'O'D' + A'BD + B'CD'+ ABC Teorema apa yang digunakan dalam langkah 1,2.3. dan 4 ? 104
(4-9)
Jika kalirnat yang disederhanakan harus ditinggalkan dalarn bentuk hasilpenjumlahan daripada dalam bentuk jumlah-hasil, maka dual dari teorema yang digunakan di atas harus diaplikasikan. CONTOH : (A' + B' + C')(A'+ ~"'V
B' + C)(B' + C) (A + C)(7\ -1>B I C) .
B')
= (A'+ B')~(A
@
+ C)=(A'+B')(A + C)
(4-10)
Teorema apa yang digunakan dalarn langkah 1,2, dan 3 ? Secara umurn, tidak ada cara yang mudah untuk menentukan kapan kalin:tat Boolean mempunyaijurnlah term minimum atau jumlah literal minimum. Metode yang sistematik untuk rnenemukan kalimat dengan jumlah-hasil minimum dan hasil-jumlah minimum akan dibahas dalarn Unit 6 dan 7.
4.3 MEMBUKTlKAN VALID/TAS SUATUPERSAMAAN Seringkali kita perlu rnenentukan apakah sebuah persamaan valid untuk semua kombinasi nilai variabel. Beberapa metode dapat digunakan untuk menentukan apakah sebuah persamaan itu valid : I.
Susunlah tabel kebenaran dan evaluasilah kedua sisi persamaan untuk semua kombinasi nilai variabel. (Metode ini agak membosankan jika jumlah variabelnya besar, dan tentunya tidak menyenangkan)
2.
Hitunglah satu sisi persamaan dengan mengaplikasikan berbagai teorema sampai identik dengan sisi yang lain.
3.
Kurangilah kedua sisi persamaan secara independen pada kalimat yang sarna.
4.
Dibolehkan untuk melakukan operasi yang sarna pada kedua sisi persamaan yang asalkan operasi tersebut dapat dibalik. Misalnya, bisa saja mengkomplementasikan kedua sisi persamaan, namun tidak boleh mengkalikan kedua sisi persamaan dengan kalimat yang sarna. (perkalian 105
tidak dapat dibalik karena bagian tidak ditentukan untuk aljabar Boolean.) Demikian pula, tidak diperbolehkan untuk menambahkan term yang sarna pada kedua sisi persamaan karena pengurangan tidak ditentukan pada aljabar Boolean.
Untuk membuktikanbahwa sebuah persamaantidak valid, sudah cukup dengan menunjukkan satu kombinasi nilai variabel di mana dua sisi persamaan mempunyai nilai yang berbeda. Ketika menggunakan metode 2 atau 3 di atas untuk membuktikan bahwa sebuah persamaan itu valis, strategi yang berguna adalah : I.
Pertama kurangilah kedua sisi dengan jumlah-hasil (atau hasil-jumlah).
2.
Bandingkan kedua sisi persamaan untuk melihat bagaimana perbedaan . mereka.
3.
Kemudian cobalah untuk menambahkan term pada satu sisi persamaan yang ada pada sisi lain.
4.
Akhimya, cobalah untuk mengurangi term dari satu sisi yang tidak ada pada sisi lain.
Metode apapun yang digunakan, seringkali membandingkan kedua sisi persamaan dan membiarkan perbedaan diantara keduanya akan memberikan petunjuk langkah apa yang hams ditempuh selanjutnya. CONTOH 1 Tunjukkan bahwa, A'BD'+ BCD + ABC'+ AB'D
= BC'D'+
AD + A'BC
Dimulai dengan sisi sebelah kiri, pertama kali. kita menambahkan term kon~ensus, kemudian mengkombinasikan term dan akhimya menghapus term dengan teorema konsensus. A'BD'+ BCD + ABC'+ AB'D
=
A'BD + BCD + ABC' + AB'D + BC'D'
+ A'BC + ABD
(tambahkankonsensusdari A'BD' dan ABC'~ (tambahkankonsensusdari A'BD' dan BCD) (tambahkan konsensus dari BCD dan A:BC'
106
J
= AD + A'BD'+
BCD + ABC'+ BC'D'+ A'BC = BC'D'+ AD + A'BC
Lb
(4-11)
~menghilangbn ~sensusdan dari DC'D' clanAD) menghilangkankonsensusAD A'Bq menghilangkankonsensusdari BC'D' dan A'BC)
CONTOH 2 Tunjukkan bahwa persamaan berikut ini valid : A'BC'D + (A'+ BC)(a + C'D') + BC'D + A'BC'
= ABCD + A'C'D'+
ABD + ABCD'+ BC'D
Pertama kali kita akan mengurangi sisi sebelah kiri : A'BC'D + (A'+ BC)(A + C'D')+BC'D+ A'BC' (menghilangkan A'BC'D dengan menggunakan (2-13»
=(A'+
BC)(a + C'D')( BC'D + A'BC'
(mengkalikan dengan menggunakan (3-12» = ABC + A'C'D'+ BC'D + A'BC' (menghilangkan A'BC' dengan konsensus)
= ABC + A'C'D'+
BC'D
Sekarang kita akan mengurangi sisi sebelah kanan :
= ABCD + A'C'D'+
ABD + ABCD'+ BC'D
(Kombinasikan ABCD dan ABCD') = ABC + A'C'D'+ ABD + BC'D (hilangkan ABD dengan konsensus)
= ABC + A'C'D'+
BC'D
Karena kedua sisi persam~ asal secara bebas dikurangi dengan kalimat yang sarna, rnaka persarnaan tersebut valid.
107
-
Seperti yang telah kita teliti sebelumnya, beberapa teorema aljabar Boolean tidak berlaku untuk aljabar biasa. Demikian pula beberapa teorema aljabar biasa tidak berlaku untuk aljabar Boolean. Misalnya, perhatikan hukum penghapusan
untuk aljabarbiasa :
.
Jika x + y
= x + z, maka y = Z
(4-12)
Hukum penghapusan tidak berlaku untuk aljabar Boolean. Kita akan menunjukkan hal ini dengan menyusun contoh pembanding di mana x+y
= x + z namun y y z. Buatlahx = I, Y = 0, z = 1. Kemudian I + 0 =I + I tapi 0 * I
Dalam aljabar biasa, hukum penghapusan untuk perkalian adalah jika xy
= xz,
Hukum ini valid asalkan x
.
makay=z
(4-13)
* o.
Dalam aljabar Boolean, hukum penghapusan untuk perkalian juga tidak valid ketika x = O. (Buatlah x = 0, y = 0, z = I; maka 0.0=0.1, tapi 0 * I). Karena x = 0 sampai pada setengah dalam switching aljabar, maka hukum penghapusan untuk perkalian tidak dapat digunakan. Meskipun Pernyataan (4-12) dan (4-13) biasanya salah untuk aljabar Boolean, kebalikannya Jika y
= z,
Jika y = z,
maka x + y = x + z
(4-14)
maka
(4-15)
xy = xz
adalah benar. Jadi, kita lihat bahwa meskipun penambahan term yang sarna pada kedua sisi persamaan Boolean membawa pada persamaan yang valid, operasi kebalikan penghapusan atau pengurangan term daTi kedua sisi biasanya tidak membawa pada persamaan yang valid. Demikian pula, perkalian kedua sisi persamaan Boolean dengan term yang sarna membawa pada persamaan yang valid, namun tidak secara berkebalikan. Ketika kita berusaha untuk membuktikan bahwa suat\l persamaan itu valid, maka tidak diperbolehkan untuk menambahkan kalimat yang sarna pada kedua sisi persamaan atau mengkalikan kedua sisi dengan kalimat yang sarna, karena operasi ini tidak dapat dibolak-balik. 108
LATiHANTERPROGRAM4.1 Tutuplah jawaban pada latihan ini dengan selembar kertas dan geserlah ke bawah ketika anda memeriksa jawaban anda. Kalimat berikut ini hams disederhanakan dengan menggunakan teorema konsensus : AC'+ AB'D + A'B'C + A'CD'+ B'C'D' Pertama kali, carilah semua term konsensus dengan memeriksa semua pasangan term.
Jawaban : term konsensus ditunjukkan sebagai berikut :
r--A'B'D'~ AC'+ AB'D + A'B'C + A'CD'+ B'C'D'
\~ ~I AB'C'
Dapatkah kalimat asli disederhanakan dengan aplikasi teorema konsensus langsung ?
Jawab: Tidak, karena tidak satupun term konsensus muncul dalam kalimat asli.
Sekarang tambahkan term konsensus B'CD ke kalimat asli. bantingkan term yang ditambahkan dengan masing-masing term asli untuk melihat apakah ada konsensus. Hilangkan sebanyak mungkin term asli.
109
Jawab : (AB'D) A. , AC'+ AB'D + A'B'C + A'CD'+ B'C'D'+ B'CD /
v
(A'B'C')
Sekarang kita telah menghapus dua term, dapatkah B'CD juga dihilangkan? Bagaimanakan kalimat akhir setelah dikurangi ?
Jawab: Tidak, karena term yang digunakan untuk membentuk B'CD telah hilang. Jawaban akhir adalah : AC' + A'CD'+ B'C'D'+ B'CD
LATiHANTERPROGRAM 4.2 . Tutuplah jawaban latihan ini dengan selembar kertas dan geserlah ke bawah ketika anda mengeeek jawaban anda.
Soal : Kalimat berikut ini harus disederhanakan ab'cd'e + acd + acfgh'+ abcd'e + acde' + e'h' Nyatakan sebuah teorema yang dapat digunakan untuk mengkombinasikan sepasang term dan aplikasikanlah u~tuk mengkombinasikan dua term dalam kalimat di atas. Jawab: Aplikasikan XY + XY' mengurangi kalimat menjadi
=X
pada term abcd'e dan abed'e, yang
acd'e + acd + acfgh'+ acde' + e'h' 110
Sekarang sebutkan sebuah teorema (selain teorema konsensus) yang dapat digunakan untuk menghilangkan term dan aplikasikanlah untuk menghilangkan sebuah term pada kaliamt di atas. Jawab : Aplikasikan X + Xy = X untuk menghapus acde'. (Term mana yang berkoresponden dengan X 1) Jawabannya adalah : aed'e + aed + aefgh'+ e'h' Sekarang sebutkan sebuah teorema yang dapat digunakan untuk menghapuskan literal, dan aplikasikanlah untuk menghapus sebuah literal dari salah satu term dalam kalimat di atas. (Petunjuk : Mungkin perlu memfaktorkan beberapa variabel biasa dari sepasang term sebelum teorema tersebut dapat diaplikasikan.) Jawab : Gunakan X + X'y
= X + Y untuk menghapus sebuah literal dari acd'e.
Untuk melakukanhal ini, pertamakali faktorkanlahac dari dua term pertama: acd'e + acd = ac(d + d'e). Setelah menghapus d', kalimat hasilnya adalah ace + aed + aefgh'+
e'h'
( I) Dapatkah setiap term dihapuskan dari kalimat ini dengan aplikasi teorema konsensus secara langsung 1 (2) Jika tidak, tambahkan term redundan dengan menggunakan teorema konsensus, dan gunakan redundan ini untuk menghapus salah satu dari term lain. (3) Akhirnya. kurangilah kaliamt anda menjadi tiga term.
Jawab : (a) Tidak (b) Tambahkan konsensus ace dan e'h' ace + aed + aef'gh'+ e'h'+ aeh'
111
---
Sekarang hilangkanlah acf gh' (dengan X + XY = X) ace + acd + e'h'+ ach' (c) Sekarang hilangkan ach' dengan teorema konsensus. Jawaban akhimya adalah : .
ace + acd + e'h'
LATiHANTERPROGRAM 4.3 Tetap tutuplah jawaban pada latihan ini dengan selembar kertas dan geserlah
ke bawah ketika anda mengecekjawaban anda. Z
= (A + C' + P' (A + C + E
.
+ G)(a + C' + P + G)(A + B + C' + D' +G)
= G)(A'+
B + G)(B + C'+ P + G)
Kalimat di atas hams disederhanakan menjadi bentuk : (X + X + X)(X + X + X)(X + X + X) di mana setiap X mewakili sebuah literal. Sebutkan sebuah teorema yang dapat digunakan untuk mengkombinasikan dua term Z pertama dan aplikasikanlah. (Petunjuk : Dua jumlah term hanya berbeda satu variabel.)
Jawab:
(X + Y)(X + Y')
=X
Z= (A+C' +GXA+B +C'+D'+GXA+C +E+GXA'+B +G) (B+C'+P+G) Sekarang sebutkan sebuah teorema (selain teorema konsensus) yang dapat digunakan untuk menghapuskan jumlah term dan aplikasikanlah ke kalimat di atas.
112
Jawab:
X(X + Y)
Z = (A + C'
=x
+ G)(A + C + E + G)(A' + B + G)(B + C'+ F + G)
Selanjutnya, hilangkan satu literal dari term kedua, biarkan kalimat tersebut tetap tidak berubah. (petunjuk : Hal ini tidak dapat dilakukan dengan aplikasi satu teorema secara langsung; secara per bagian perlu dikalikan dua jumlah term pertama sebelum menghapus literal tersebut.) Jawab : (A + C'+ G)(A + C+ E + G)
= A + G + C'(C + E)= A + G + C'E
Oleh karena itu, Z = (A + C'+ G)(A + E + G)(A'+ B + G)(B + C'+ F + G)
(a) Dapatkah setiap term dihapuskan dari kalimat ini dengan aplikasi teorema konsensus secara langsung ? . (b) Jika tidak, tambahkan jumlah term redundan dengan menggunakan teorema konsensus, dan gunakan term redundan ini untuk menghapus salah satu term lain. (c) Akhimya, kurangilah kalimat anda menjadihasil term jumlah tiga.
Jawab : (a) Tidak (b) Tambahkan B + C'+ G (konsensus dari A + C'+ G dan A' + B + G) Gunakan
X(X + Y)
B + C'+ F + G.
= X,
di mana X
= B + C' + G,
untuk menghilangkan
(c) Sekarang hilangkanlah B + C'+ G dengan konsensus. Jawaban akhimya adalah : Z
= (A + C'+
G)(A + E + G)(A' + B + G)
113
---
-
...~
- -----------.
SOAL 4.4
Sederhanakanlah masing-masing kalimat berikut ini dengan menggunakan teorema konsensus saja (atau dual-nya) : (a) BC'D'+ ABC' + AC'D + AB'D + A'BD' (kurangilah menjadi tiga term). (b) W'Y'+ WYZ + XY'Z + WX'Y (kumngilah menjadi tiga term) (c) (B + C + D)(A + B + C)(A' + C + D)(B' + C'+D')
4.5
Ulangilah Soal 4.4 untuk : (a) W'XY + WXY + WY'Z + WY'Z' (B) A'BC' + BC'D' + A'CD + B'CD = A'BD (c) (A + B + C)(B + C'+ D)(A + B + D)(A' + B' + D')
4.6
Sederhanakanlah kalimat berikut ini dengan menggunakan teorema konsensus saja atau dual-nya : (a) WX'Y'+ W'YZ'+ W'XZ'+ WY'Z' (b) A'B'C + ABD + A'CDE + BCDE + A'BDE (c) (A + B + C )(A + C'+ D')(B'+C'+ D')(C + D) (d) (W + X')(Y + Z')(W + Y)(X + Y)(W + Z)(X + Z)
4.7
Sederhanakanlah
masing-masing kalimat berikut ini :
(a)
xy + x'yz'+ yz
(b)
(xy'+z)(x + y')z
(c)
xy'+ z + (x'+y)z'
(d)
a'd(b'+ c) + a'd'(b + c') ... (b'+c)(b + c')
(e)
w'x'+ x'y'+ yz + w'z'
(t)
A'BCD + A'BC'D + B'EF + CDE'G + A'DEF + A'B'EF (kurangilah menjadi jumJah tiga term)
(g) .(a'+ d'+ b'c)(b + d + ac')]'+b'c'd~+ term) 114
a'c'd (kurangilah menjadi tiga
-- - - - - --. - -- - --
4.8
--
Sederhanakanlahmasing-masingkalimatberikutini: (a) a'(b'+ c) + a + be' (b) ab + a'be'+ be (c) z(x'+ y)(x'y + z) (d) w'x'(y'+ z) + wx'(y + z) + (y'+ z)(y + z') (e) ab + a'c'+ b'd'+ c'd'(kurangilah menjadi jumlah tiga term) (f)
w'x'y'+ w'xz'+ [(x+ y + w'z)(x'+z'+wy'»' (kurangilahmenjadijumlah tiga term)
(g) ABC' + ABC'D' + ABD'E + A'EFG + CD'EG + CD'EG' (kurangilah menjadi tiga term)
4.9
Sederhanakanlah masing-masing kalimat berikut ini : (a) F
= AB + AC + BC + B'C'
(b) AB + ABC + BCD' + AB'D + A'CD'+ A'BCD (kurangilah menjadi tiga term) (c) F= AB'+A'BC +AB'C' + A'BD'+ A'B'D'+BCD (kurangilahmenjadi tiga term)
4.10 Sederhanakanlah menjadi jumJah tiga term : (a) A'C'D'+ AC: + BCD + A'CD'+ A'BC + AB'C' (b) A'B'C'+ ABD + A'C + A'CD'+ AC'D + AB'C' 4.11 Faktorkanla)t untuk mendapatkan hasil dari empat term dan kemudian kurangilat1 menjadi tiga term dengan mengaplikasikan teorema konsensus : X'Y'Z' + XYZ 4.12 Faktorkanlah Z =ABC + DE + ACF + AD' + AB'E' dan sederhanakanlah menjadi bentuk (X + X)(X + X)(X + X + X + X)(di mana masing-masing X mewakili sebuah literal). Sekarang buatlah Z sebagai jumlah hasil minimum dalam bentuk :
xx+xx+xx+xx 115
4.13 Ulangilah Soal 4.12 untuk F
= A'B
+ AC + BC'D'+ BEF + BDF.
4.14 Kurangilah menjadi jumlah hasil minimum:
F
=WXY' + (W'Y' == X) + ( Y ~
4.15 Sederhanakanlah: F
= a'b
4.16 Sederhanakanlah : F
= ab ~
WZ).
~ be ~ ab ~ b'e'.
be ~ a'b' ~ be'.
4.17 Buktikan secara aljabar bahwa persamaan berikut ini valid : (a)
(A'+ B' + D')(A + B + D')(B + C + D)(A + C')(A + C'+ D) = A'C'D + ACD' + BC'D'
(b) (A'+ B)(A + C + D)(A' + B + C)(B' + C'+ D')(B' + C'+ D)
= ABC'+
A'C'D + A'B'C
4.18 Manakah dari persamaan berikut ini yang selalu valid (berilah bukti seeara aljabar) :
= ab'+ be' + ea' (a + b)(b + e)(e + a) = (a'+ b')(b'+
(a) a'b + b'e + e'a (b)
(e) abe+ ab'e' + b'ed + be'd + ad
e')(e'+ a')
=abe + ab'e'+ b'ed + be'd
4.19 Ulangilah soal 4.18 untuk : (a) xy'+ x'z + yz'= x'y + xz' + y'z
(b) (x + y)(y + z)(x + z) = (x'+ y')(y'+ z')(x'+ z') (e) abe'+ ab'e + b'e'd + bed = ab'e + abe'+ ad+ bed+ b'e'd
116
4.20 Buktikan secara alajab?r : (a)
(A E9 B)( + C) + (A
==
B)(B'+ C')= A'+ ( B E9 C).
(b) ABC + A'B'C'+ ABD + B'C'D XZ +-Y'Z'+ WYZ + WX'Y
= (X + W + Y')(X
=(B + C')(A + B')(A'+
C + D) (C)
+ Y + Z')(X'+ Z + Y')
4.21 Buktikan secara aljabar : (a) (X'+ Y')(X
==
Z) + (X + Y)(X E9Z) = (X E9Y) + Z'
(b) (X' + X + Y')(W + X'+ Y)(W + Y'+ Z)
= X'Y'+
WX + XYZ + W'YZ
(c) ABC + A'C'D'+ A'BD'+ ACD =(A'+C)(A + D')(B + C'+ D) 4.22 Manakah dari pemyataan berikut ini yang selalu benar ? Buktikan jawaban anda. (a) Jika x(y + a') (b) Jika a
= x(y + b'), kemudiana = b.
= b kemudian x(y + a') = x(y + b').
4.23 Manakah dari pemyataan berikut ini yang selalu benar ? Buktikan jawaban anda.
= C, maka AD' + BD' =CD. + AC = A'D, maka B + C = D. B = C, maka A + B + D = C + D.
(a) Jika A + B (b) Jika A'B (c)
Jika A +
(d) Jika A + B + C= C + D, maka A + B = D.
117
