Pengantar Sistem Digital
Outline 2
Bagian 1: Logika Biner Gerbang Logika Dasar Aljabar Boolean, Manipulasi Aljabar
Bagian 2:
RANGKAIAN LOGIKA KOMBINASI
Penyederhanaan Fungsi Karnough Map
Bagian 3: Gerbang NAND-NOR Gerbang X-OR Don’t Care Condition
BAGIAN 1 : RANGKAIAN GERBANG DAN PERSAMAAN BOOLEAN
Odd semester 2012/2013
Logika Biner 4
Logika Biner
3
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.
Operasi Logikal
Variabel Biner. 5
Variabel Biner : salah satu dari 2 nilai diskrit
6
Dua nilai biner disebut dengan beberapa nama berbeda: True/False On/Off Yes/No 1/0
AND OR NOT
Digunakan 1 dan 0 untuk menyatakan 2 nilai. ContohVariable identifier : A, B, y, z, or X1 RESET, START_IT, atau ADD1 (y.a.d)
Tiga dasar operasi logikal adalah:
AND dinyatakan dengan titik (·).
OR dinyatakan dengan tambah (+).
NOT dinyatakan dengan overbar ( ¯ ), single quote mark (') sesudah, atau (~) sebelum variabel.
1
Contoh:
Definisi Operator
7
8
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.”
Operasi penerapan untuk nilai "0" and "1" untuk masing2 operator : AND
NOT
0+0=0 0+1=1 1+0=1 1+1=1
0=1 1=0
0·0=0 0·1=0 1·0=0 1·1=1
Catatan: Pernyataan: 1 + 1 = 2 (dibaca “one plus one equals two”)
tidak sama dengan : 1 + 1 = 1 (dibaca “1 or 1 equals 1”).
Implementasi Fungsi Logika.
Truth Tables/Tabel Kebenaran 9
OR
10
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
MenggunakanSwitch
logic logic
1 is switch closed 0 is switch open
Untuk outputs: logic logic
Switches in parallel => OR
Untuk inputs:
1 is light on 0 is light off.
Switches in series => AND
NOT menggunakan switch seperti: Normally-closed switch => NOT logic logic
1 is switch open 0 is switch closed
C
Implementasi Fungsi Logika. (Continued) 11
Contoh: Logic Using Switches B
C
A
12
Gerbang Logika (logic gates)
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.
2
Gerbang Logika(Logic Gates)
Simbol Gerbang Logika dan perilakunya.
13
14
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.
Gerbang Logika mempunyai simbol khusus,
X
Z 5 X ·Y
Y
X
Z5 X1 Y
Y
X
OR gate
AND gate
(a) Graphic symbols And waveform behavior in time as follows:
Kemudian, vacuum tubes membuka dan menutup jalan arus secara elektronik, menggantikan relays.
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
Saat ini, transistors dipakai sebagai electronic switches yang membuka dan menutup jalannya arus. (AND)
Optional: Chapter 6 – Part 1: The Design Space
Z5 X NOT gate or inverter
(b) Timing diagram
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
16
Aljabar Boolean
F = X +Y Z Diagram Logika F
Aljabar Boolean
Beberapa properti dari identitas dan Aljabar.
17
18
Struktur Aljabar didefinisikan pada satu set atau minimum 2 elemen, A, B, dengan tiga operator biner (denoted +, · and ) yang dirumuskan secara mendasar sbb:
1.
X +0 = X
2.
X .1 = X
3.
X+1 =1
4.
X .0 =0 .X
=X
1-4 :Existence of 0 and 1 5-6 :Idempotence
5.
X+X = X
6.
X
7.
X+X = 1
8.
9.
X=X
X . X = 0 7-8 :Existence of complement 9 :Involution
10. X + Y = Y + X 12. (X + Y) + Z = X + (Y + Z) 14. X(Y + Z) = XY + XZ
11.
Commutative Associative
15.
16. X + Y = X . Y
17.
X + YZ = (X + Y) (X + Z) Distributive De Morgan’s X.Y =X+Y
XY = YX 13. (XY) Z = X(Y Z)
“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?
3
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?
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)
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.
Contoh 2: Pembuktian Aljabar Boolean
Contoh 1: Pembuktian Aljabar Boolean 21
22
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
Proof Steps
1+X=1
= A
X·1=X
Justification (identity or theorem)
AB + AC + BC
X · Y + X · Z = X ·(Y + Z)(Distributive Law)
= A·1
AB + AC + BC = AB + AC (Consensus Theorem)
= AB + AC + 1 · BC
?
= AB + AC + (A + A) · BC
?
= (lanjutkan!)
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.
Teorema yang berguna
Contoh 3: Pembuktian Aljabar Boolean 23
24
( X + Y ) Z + X Y = Y( X + Z ) Proof Steps Justification (identity or theorem) (X + Y )Z + X Y = (lanjutkan!)
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
4
Proof of DeMorgan’s Laws
Pembuktian dengan penyederhanaan
(x + y )(x + y ) = y
25
xy + xy = y
26
x + y = xy
xy = x + y
Buktikan x + y + x’. y’ = 1
Buktikan!
Buktikan (x + y) . x’. y’ = 0
Evaluasi Fungsi Boolean 27
F1 = xy z F2 = x + yz F3 = x y z + x y z + x y F4 = x y + x z
Penyederhanan Ekspresi 28
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
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 •
5
Soal dari Buku Edisi ke 4 31
SCELE: Cara login 32
2-2
Buka http://scele.ui.ac.id
2-3
Login dengan user dan password UI
2-4
Buka link Fakultas Teknik
2-6
Pilih Faculty Courses:
2-7
S1 Reguler >
2-8
Teknik Elektro >
2-9
Pengantar Sistem Dijital
Atau.. 33
Enrolment key (catat!) 34
Search course: Pengantar Sistem Dijital dijital2012
Link langsung setelah berhasil login: http://scele.ui.ac.id/course/view.php?id=2211
6
