Pengantar Sistem Digital
RANGKAIAN LOGIKA KOMBINASI BAGIAN 1 : RANGKAIAN GERBANG DAN PERSAMAAN BOOLEAN Odd semester 2012/2013
Outline 2
Bagian 1: Logika Biner Gerbang Logika Dasar Aljabar Boolean, Manipulasi Aljabar
Bagian 2: Penyederhanaan Fungsi Karnough Map
Bagian 3: Gerbang NAND-NOR Gerbang X-OR Don’t Care Condition
3
Logika Biner
Logika Biner 4
Variabel Biner : salah satu dari 2 nilai diskrit Operator Logika : Beroperasi pada nilai biner dan variabel biner.
Dasar operator logika adalah merupakan fungsi logika AND, OR and NOT. Gerbang Logika mengimplementasikan fungsi logika Aljabar Boolean : Suatu sistem matematika yang sangat berguna untuk menspesifikasikan dan mentransformasikan fungsi Aljabar Boolean dipakai sebagai dasar untuk mendesain dan menganalisa sistem digital.
Variabel Biner. 5
Dua nilai biner disebut dengan beberapa nama berbeda: True/False On/Off Yes/No 1/0
Digunakan 1 dan 0 untuk menyatakan 2 nilai.
ContohVariable identifier : A,
B, y, z, or X1 RESET, START_IT, atau ADD1 (y.a.d)
Operasi Logikal 6
Tiga dasar operasi logikal adalah: AND OR
NOT
AND dinyatakan dengan titik (·).
OR dinyatakan dengan tambah (+).
NOT dinyatakan dengan overbar ( ¯ ), single quote mark (') sesudah, atau (~) sebelum variabel.
Contoh: 7
Contoh: Y = A B dibaca “Y adalah : A AND B.” z = x + y dibaca “z adalah : x OR y.” X = A dibaca “X adalah : NOT A.”
Catatan: Pernyataan: 1 + 1 = 2 (dibaca “one plus one equals two”)
tidak sama dengan : 1 + 1 = 1 (dibaca “1 or 1 equals 1”).
Definisi Operator 8
Operasi penerapan untuk nilai "0" and "1" untuk masing2 operator :
AND
0·0=0 0·1=0 1·0=0 1·1=1
OR
NOT
0+0=0 0+1=1 1+0=1 1+1=1
0=1 1=0
Truth Tables/Tabel Kebenaran 9
Truth table - Suatu daftar tabular dari nilai suatu fungsi untuk semua kemungkinan kombinasi. Contoh: Truth tables untuk operasi dasar : NOT OR AND X X Y Z = X·Y X Y Z = X+Y Z=X 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1
Implementasi Fungsi Logika. 10
MenggunakanSwitch Untuk
Switches in parallel => OR
inputs:
logic
1 is switch closed logic 0 is switch open Untuk
outputs:
logic
1 is light on logic 0 is light off.
Switches in series => AND
NOT
menggunakan switch seperti: Normally-closed switch => NOT logic
1 is switch open logic 0 is switch closed
C
Implementasi Fungsi Logika. (Continued) 11
Contoh: Logic Using Switches B
C
A
D
Lampu nyala (L = 1) untuk: L(A, B, C, D) = Dan bila tidak, mati (L = 0).
Model yang berguna untuk rangk relay dan untuk rangk gerbang CMOS , merupakan dasar dari teknologi logika digital saat ini.
12
Gerbang Logika (logic gates)
Gerbang Logika(Logic Gates) 13
Pada awal komputer, switches terbuka dan tertutup menggunakan medan magnit yang dihasilkan oleh energi dari koil pada relays. Switches secara bergantian membuka dan menutup jalan arus. Kemudian, vacuum tubes membuka dan menutup jalan arus secara elektronik, menggantikan relays. Saat ini, transistors dipakai sebagai electronic switches yang membuka dan menutup jalannya arus. Optional: Chapter 6 – Part 1: The Design Space
Simbol Gerbang Logika dan perilakunya. 14
Gerbang Logika mempunyai simbol khusus,
X
Z 5 X ·Y
Y
X
Z5 X1 Y
Y OR gate
AND gate
X
(a) Graphic symbols And waveform behavior in time as follows: X
0
0
1
1
Y
0
1
0
1
X ·Y
0
0
0
1
(OR)
X1 Y
0
1
1
1
(NOT)
X
1
1
0
0
(AND)
(b) Timing diagram
Z5 X NOT gate or inverter
Diagram Logika dan Ekspresi-nya. 15
Persamaan Boolean, tabel kebenaran dan Diagram Logika mentayakan Fungsi yang sama! Tabel Kebenaran adalah unik; ekspresi dan diagram logika tidak. Ini memberikan fleksibilitas dalam implementasi fungsi. Persamaan: Tabel Kebenaran XYZ 000 001 010 011 100 101 110 111
F = X + Y Z 0 1 0 0 X 1 1 Y 1 Z 1
F = X +Y Z Diagram Logika
F
16
Aljabar Boolean
Aljabar Boolean 17
Struktur Aljabar didefinisikan pada satu set atau minimum 2 elemen, A, B, dengan tiga operator biner (denoted +, · and yang dirumuskan secara mendasar sbb: 1. 3. 5. 7. 9.
X +0= X X+1 =1 X+X =X X+X = 1
X=X
10. X + Y = Y + X 12. (X + Y) + Z = X + (Y + Z) 14. X(Y + Z) = XY + XZ
16. X + Y = X . Y
2. 4. 6. 8.
X .1 =X .
X 0 =0 X .X = X
)
1-4 :Existence of 0 and 1 5-6 :Idempotence
X . X = 0 7-8 :Existence of complement
9 :Involution 11. XY = YX Commutative Associative 13. (XY) Z = X(YZ) 15. X + YZ = (X + Y) (X + Z) Distributive De Morgan’s 17. X . Y = X + Y
Beberapa properti dari identitas dan Aljabar. 18
“Dual” dari ekspresi suatu ekspresi aljabar didapat dengan menggantikan + and · dan menggantikan 0’s dan 1’s. Unless it happens to be self-dual, the dual of an expression does not equal the expression itself. Example: F = (A + C) · B + 0 dual F = (A · C + B) · 1 = A · C + B Example: G = X · Y + (W + Z) dual G = Example: H = A · B + A · C + B · C dual H = Are any of these functions self-dual?
Beberapa properti dari identitas dan Aljabar. (Continued) 19
Kemungkinan dapat lebih dari 2 elemen in B, yaitu elemen selain1 and 0. Umumnya disebut apa Aljabar Boolean dengan lebih dari 2 elemen?
Algebra of Sets Algebra of n-bit binary vectors
Bila B terdiri hanya 1 dan 0, maka B disebut switching algebra yang merupakan aljabar yang sering digunakan.
Operator Boolean 20
Urutan Evaluasi pada Ekspresi Boolean adalah : 1. Parentheses/kurung 2. NOT 3. AND 4. OR Akibatnya: Kurung muncul sekitar ekspresi OR Contoh : F = A(B + C)(C + D)
Contoh 1: Pembuktian Aljabar Boolean 21
A + A·B = A (Absorption Theorem)
Proof Steps
Justification (identity or theorem)
A + A·B = A·1+A·B
= A · ( 1 + B)
X=X·1
X · Y + X · Z = X ·(Y + Z)(Distributive Law)
= A·1
1+X=1
= A
X·1=X
Alasan melakukan pembuktian untuk mempelajari:
Ber-hati2 dan secara efisien menggunakan rumus dan teorema Aljabar Boolean. Bagaimana memilih identitas dan teorema yang cocok untuk diterapkan, untuk melanjutkan penyelesaian berikutnya.
Contoh 2: Pembuktian Aljabar Boolean 22
AB + AC + BC = AB + AC (Consensus Theorem)
Proof Steps
Justification (identity or theorem)
AB + AC + BC = AB + AC + 1 · BC
?
= AB + AC + (A + A) · BC
?
= (lanjutkan!)
Contoh 3: Pembuktian Aljabar Boolean 23
( X + Y ) Z + X Y = Y( X + Z ) Proof Steps Justification (identity or theorem) ( X + Y )Z + X Y = (lanjutkan!)
Teorema yang berguna 24
xy + xy = y
x + xy = x
(x + y )(x + y )= y x (x + y ) = x
x + x y = x + y x (x + y = ) x y xy + xz + yz = xy + xz
Minimization
Absorption Simplification
(x + y ) (x + z ) (y + z ) = (x + y ) (x + z ) x + y = xy
xy = x + y
Consensus
DeMorgan' s Laws
Pembuktian dengan penyederhanaan 25
xy +xy = y Buktikan!
(x + y )(x + y ) = y
Proof of DeMorgan’s Laws 26
x + y = xy Buktikan x + y + x’. y’ = 1
Buktikan (x + y) . x’. y’ = 0
xy = x + y
Evaluasi Fungsi Boolean 27
F1 = xy z F2 = x + yz F3 = x y z + x y z + x y F4 = x y + x z
x 0 0 0 0 1 1 1 1
y 0 0 1 1 0 0 1 1
z F1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0
F2 0 1 0 0 1 1 1 1
F3
F4
Penyederhanan Ekspresi 28
Suatu Penerapan Aljabar Boolean Sederhanakan agar didapat jumlah literal terkecil. (variabel complemen dan tidak complemen):
A B + ACD + A BD + AC D + A BCD = AB + ABCD + A C D + A C D + A B D = AB + AB(CD) + A C (D + D) + A B D = AB (1+ CD) + AC (1) + ABD = AB (1) + A C + A B D = B(A + AD) +AC
= B (A + D) + A C 5 literals
Fungsi Complemen 29
Gunakan Teorema DeMorgan's untuk mengkomplemen-kan fungsi: 1.
2.
Saling ditukar operators AND dan OR Komplemen-kan masing2 nilai konstan dan literal.
Contoh:Komplemenkan F
= xy z + x y z
F = (x + y + z)(x + y + z)
Contoh:Komplemen-kan
G=
G = (a + bc)d + e
30
Tugas 2 Soal dikerjakan berkelompok (4 orang)
•
Diketik dan disimpan sebagai file .doc atau .pdf
•
Dikumpulkan melalui SCELE (upload) link ditutup ketika mulai kuliah pekan depan. Tidak ada alasan masalah koneksi atau server down! Don’t do last minute! •
Upload di folder kelasnya masing-masing!!
•
Pengumpulan hardcopy (print) tidak akan diterima •
Soal dari Buku Edisi ke 4 31
2-2
2-3
2-4
2-6
2-7
2-8
2-9
SCELE: Cara login 32
Buka http://scele.ui.ac.id
Login dengan user dan password UI
Buka link Fakultas Teknik
Pilih Faculty Courses: S1 Reguler > Teknik Elektro > Pengantar Sistem Dijital
Atau.. 33
Search course: Pengantar Sistem Dijital
Link langsung setelah berhasil login: http://scele.ui.ac.id/course/view.php?id=2211
Enrolment key (catat!) 34
dijital2012
