Penyederhanaan fungsi Boolean. Gembong Edhi

Penyederhanaan fungsi Boolean

Gembong Edhi Setyawan [email protected] @gembong

TujuanPerkuliahan • Menggambar peta karnaugh berdasarkan fungsi boolean atau tabel kebenaran yang diketahui • Menyederhanakan fungsi boolean dengan menggunakan peta karnaugh • Menyederhanakan fungsi boolean dengan menggunakan metoda tabulasi.

Karnaugh maps  • Aljabar boolean membantu kita untuk menyederhanakan persamaan dan circuit • Karnaugh Map : teknis grafis yang digunakan untuk menyederhanakan ekspresi boolean kedalam form : – minimal sum of products (MSP) – minimal product of sums(MPS)

• Tujuan dari penyederhanaan

– Menghasilkan jumlah minimal dari terms product/sum – Masing-masing term akan memiliki jumlah literal minimal

Pengaturan ulang tabel kebenaran • 2 variabel fungsi memiliki 4 kemungkinan minterms. Kita dapat melakukan perubahan minterm sini kepeta karnaughY x y minterm 0

0

x’y’

0

1

x’y

1

0

xy’

1

1

xy

X

0 1

0 x’y’ xy’

1 x’y xy

• Sekarang kita dapat dengan mudah melihat minterms yang memiliki literal umum – Minterms pada bagian kiri dan kanan mengandung y’ and y Y – Minterms pada bagian atas dan bawah 0 1x’ and x Y’ Y mengandung X

0 1

x’y’ xy’

x’y xy

X’ X

x’y’ xy’

x’y xy

4

PenyederhanaanKarnaughMap • Bayangkan 2 variable sum pada minterms x’y’ + x’y • Setiap minterms yang terlihat pada baris atas Y dari K-map mengandung literal x’ x’y’ x’y X

xy’

xy

• Apa yang terjadi bila kita melakukan penyederhanaan expresi tersebut dengan x’y’ + x’y ?= x’(y’ + y) [ Distributive ] aljabar boolean = x’  1 = x’

[ y + y’ = 1 ] [ x 1 = x ]

5

Contoh 2 variabel • Contoh 2 : untuk expression x’y+ xy – Setiap minterms yang tampak bada sisi kanan dimana y tidak dikomplemenkan – Kita dapat menyederhanakan x’y+ xy to just y Y x’y xy

x’y’ xy’

X

• Bagaimana jika x’y’ + x’y + xy? – Kita memiliki x’y’ + x’y pada baris atas, yang dapat disederhanakan menjadi x’ – Ada juga x’y + xy bagian kanan yang dapat kita sederhanakan menjad iy Y – Persamaan ini dapat kita menjadi x’ + y x’y’ sederhanakan x’y X

xy’

xy

6

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

Minterm Maxterm Suku Lambang Suku Lambang x’y’z’ m0 x+y+z M0 x’y’z m1 x + y + z’ M1 x‘y z’ m2 x + y’+z M2 x’y z m3 x + y’+z’ M3 x y’z’ m4 x’+ y + z M4 x y’z m5 x’+ y + z’ M5 x y z’ m6 x’+ y’+ z M6 xyz m7 x’+ y’+ z’ M7

7

Karnaugh Map 3 variabel • untuk 3 variabel dengan input x,y,z , susunannyaYZadalah sebagai berikut YZ : X

0 1

00 x’y’z’ xy’z’

01 x’y’z xy’z

11 x’yz xyz

10 x’yz’ xyz’

X

0 1

00 m0 m4

01 m1 m5

• Cara lain untuk menyusun Kmap 3 Y variabel ( pilih yang anda sukai ) x’y’z’ x’y’z x’yz x’yz’ X

xy’z’

xy’z

xyz Z

xyz’

X

m0 m4

m1 m5

Z

11 m3 m7

10 m2 m6

Y m3 m7

m2 m6

8

Why the funny ordering? Y X

x’y’z’ xy’z’

x’y’z xy’z

x’yz xyz

x’yz’ xyz’

Z

Y X


x’y’z xy’z

x’yz xyz Z

x’yz’ xyz’

x’y’z + x’yz = x’z(y’ + y) = x’z 1 = x’z

= = = =

x’y’z’ + xy’z’ + x’yz’ + xyz’ z’(x’y’ + xy’ + x’y + xy) z’(y’(x’ + x) + y(x’ + x)) z’(y’+y) z’

• .

9

K-mapsdari sebuah tabel kebenaran • Kita dapat mengisi K-map langsung dari sebuah tabel kebenaran

– Output dari barisipada tabel dimasukkan pada kotak mi pada K-map – Ingat bahwa bagian kanan kolom darik-map x “ditukar” y z f(x,y,z) 0 0 0 0

0 0 1 1

0 1 0 1

0 1 0 0

X

1 1 1 1

0 0 1 1

0 1 0 1

0 1 1 1

Y

Y 0 0

1 1

0 1 Z

0 1

X

m0 m4

m1 m5

Z

m3 m7

m2 m6

10

Membaca MSP dariK-map

• Kita dapat menemukan expression SoP minimal – Setiap kotak sesuai dengan 1 term of product – Produk ditentukan dengan mencari literal umum Y padakotak X

0 0

1 1

0 1

0 1

Z

Y X


x’y’z xy’z

x’yz xyz

x’yz’ xyz’

Z

y’z

xy

F(x,y,z)= y’z + xy 11

Mengelompokkanminterms • Pengelompokanpadak-map – Buat persegi panjangan yang mengelilingi group dari 1,2,4, atau 8 dari nilai 1 – Semua nilai 1 pada map harus dimasukkan paling tidak pada 1 persegipanjang. – Jangan memasukkan nilai 0 Y – Setiap kelompok terdiri dari satu term of product X

0 0

1 1

0 1

0 1

Z

12

PIs AND EPIs (1/3) • Untuk menemukan expresi SOP yang paling sederhana kita harus mendapatkan : – jumlah minimum literals per product term – Jumlah

minimum product terms

• Bisa kita dapatkan melalui K-Map menggunakan – Group terbesar dari sebuah minterms ( prime implicants ) bila mungkin – Tidakada redundant grouping ( essential prime implicants )

• Implicant : product term yang dapat digunakan untuk mengkover minterms dari sebuah fungsi CS2100

Karnaugh Maps

13

PIs AND EPIs (2/3) • Prime implicant (PI): product term yang didapatkan dari menggabungkan jumlah minterms yang memungkinkan dari kotak yang terdapat pada map. ( kemungkinan pengelompokan terbesar ) • Selalu cari prime implicants pada sebuah K-map

CS2100

1

1

1

1

1

1

1

1

1

1

1

1

O

Karnaugh Maps

P

14

PIs AND EPIs (3/3) • Tidak ada redundant groups: 1

1

1

1

1

1

1

1

1

1

1

1

O

1

1

1

1

P

Essential prime implicants 

Essential prime implicant (EPI): prime implicant yang terdiri setidaknya satu minterm yang tidak dikover prime implicant yang lain.

CS2100

Karnaugh Maps

15

K-map Simplificationof SoP Expressions • Mari kita sederhanakan persamaan berikut f(x,y,z) = xy + y’z + xz • Kita harus mengkonversi persamaan tersebut ke minterms form

– Hal yang paling mudah adalah dengan membuat tabel kebenaran dari fungsi dan kemudian kita temukan mintermsnya – Anda dapat menuliskan literals nya atau dengan minterm x

y

z

f ( x ,y ,z )

0 0 0 0

0 0 1 1

0 1 0 1

0 1 0 0

1 1 1 1

0 0 1 1

0 1 0 1

0 1 1 1

• Berikut adalah tabel kebenaran dan mintermdari fungsi diatas : f(x,y,z) = x’y’z + xy’z + xyz’ + xyz

= m1 + m5 + m6 + m7

16

UnsimplifyingExpressions

• Kita juga dapat mengkonversi fungsi diatas dengan menggunakan aljabar boolean

– Terapkan hukum distribusi untuk menambahkan variabel yang hilang

xy + y’z + xz = (xy 1) + (y’z 1) + (xz 1) = (xy (z’ + z)) + (y’z (x’ + x)) + (xz (y’ + y)) = (xyz’ + xyz) + (x’y’z + xy’z) + (xy’z + xyz) = xyz’ + xyz + x’y’z + xy’z = m1+m5+m6+m7

• Dalam contoh diatas, kita sama sekali tidak “menyederhanakan”

– Hasil dari expres idiatas lebih luas dari pada fungsi aslinya – Tetapi dengan menemukan minterms akan memudahkan kita untuk menggabungkan terms tersebut pada sebuah k-map

17

ExampleK-map • Pada contoh kita , kita bisa menuliskan f(x,y,z) dengan cara sbb: f(x,y,z) = x’y’z + xy’z + xyz’ + xyz

f(x,y,z) = m1 + m5 + m6 + m7

Y x’y’z’ xy’z’

X

x’y’z xy’z

x’yz xyz

x’yz’ xyz’

Z

Y X

m0 m4

m1 m5

Z

m3 m7

m2 m6

• Hasil dari tabel kebenaran ditunjukkan Y pada0k-map dibawah ini 1 0 0 X

0

1

1

1

Z 18

FIGURE 4-11Karnaugh maps and truth tables for (a) two, (b) three, and (c) four variables.

Ronald Tocci/Neal Widmer/Gregory Moss Digital Systems: Principles and Applications, 9e

Copyright ©2004 by Pearson Education, Inc. Upper Saddle River, New Jersey 07458 All rights reserved.

FIGURE 4-12 Examples of looping pairs of adjacent 1s.



FIGURE 4-14 Examples of looping groups of eight 1s (octets).



Latihansoal • Simplify the sum of minterms m1+ m3 + m5 + m6 Y X Z

Y X

m0 m4

m1 m5

m3 m7

m2 m6

Z

22

Solusi

– Hijau dan merah muda overlap – Minterm m6 ditulis lengkap Y X

0 0

1 1

1 0

0 1

Z

• Hasil minimal sum of product adalahsbb : x’z+ y’z+xyz’ 23

K-maps can be tricky! Y 0 0

X

1 1

0 1

1 1

Z Y

Y X

0 0

1 1

0 1

1 1

X

0 0

1 1

0 1

Z

Z

y’z + yz’ + xy

y’z + yz’ + xz

1 1

24

4 variable K-maps – f(W,X,Y,Z) – Minterms pada kolom ketiga dan keempat, dan juga baris ke 3 dan bariske 4 dibalik

• Pengelompokan mirip dengan 3 variable, tetapi : – Kita bisa mengelompokkan persegipanjang 1,2 ,4 ,8,16 minterms 25

4 variable K-maps

Y

Y

W

w’x’y’z’ w’xy’z’ wxy’z’ wx’y’z’

w’x’y’z w’xy’z wxy’z wx’y’z

w’x’yz w’xyz wxyz wx’yz Z

w’x’yz’ w’xyz’ X wxyz’ wx’yz’

W

m0 m4 m12 m8

m1 m5 m13 m9

Z

m3 m7 m15 m11

m2 m6 X m14 m10

26

Contoh : Simplify m0+m2+m5+m8+m10+m13 • The expression is already a sum of minterms, so here’s the K-map: Y Y W

1 0 0 1

0 1 1 0

0 0 0 0

1 0 0 1

X W

Z

m0 m4 m12 m8

m1 m5 m13 m9

Z

Y

W

1 0 0 1

0 1 1 0

0 0 0 0

1 0 X 0 1

m3 m7 m15 m11

m2 m6 m14 m10

X

Y

W

w ’x ’y ’z ’ w ’x y ’z ’ w x y ’z ’ w x ’y ’z ’

• MSPZ = MSP x’z’ + xy’z

w ’x ’y ’z w ’x y ’z w x y ’z w x ’y ’z

w ’x ’y z w ’x y z w xyz w x ’y z

w ’x ’y z ’ w ’x y z ’ w xyz’ w x ’y z ’

X

Z

27

Contoh : Simplify m0+m2+m5+m8+m10+m13 • The expression is already a sum of minterms, so here’s the K-map: Y Y W

1 0 0 1

0 1 1 0

0 0 0 0

1 0 0 1

X W

Z

m0 m4 m12 m8

m1 m5 m13 m9

Z

Y

W

1 0 0 1

0 1 1 0

0 0 0 0

1 0 X 0 1

m3 m7 m15 m11

m2 m6 m14 m10

X

Y

W

w ’x ’y ’z ’ w ’x y ’z ’ w x y ’z ’ w x ’y ’z ’

• MSPZ = MSP x’z’ + xy’z

w ’x ’y ’z w ’x y ’z w x y ’z w x ’y ’z

w ’x ’y z w ’x y z w xyz w x ’y z

w ’x ’y z ’ w ’x y z ’ w xyz’ w x ’y z ’

X

Z

28

FIGURE 4-18 “Don’t-care” conditions should be changed to 0 or 1 to produce K-map looping that yields the simplest expression.



ContohKasus

Mari kita merancang sirkuit logika yang mengendalikan pintu lift di sebuah bangunan tiga lantai. sirkuit ini memiliki empat masukan. M adalah sebuah sinyal logika yang menunjukkan saat lift bergerak (M = 1) atau berhenti (M = 0). F1, F2, dan F3 adalah indikator sinyal lantai yangnormally LOW , danF1,F2,F3menjadi HIGHhanya ketika lift diposisikan pada tingkat dari lantai tertentu. Sebagai contoh, ketika elevator sedangberadadilantai dua, F2 = 1 dan F1 = = F3 0. Output sirkuit merupakan sinyalOpen, yangnormally LOWdan akanmenjadi High ketika pintu lift akan dibuka.





Penyederhanaan fungsi Boolean. Gembong Edhi

Recommend Documents