10 11.teknik digital aljabar-boolean_02

04/13/2023Zulfadli Sulthan - PTIK - UNM

Pertemuan 10 & 11

1

Teknik Digital


Aljabar Boolean Ch.2

2


Contoh Teorema DeMorgan: NAND

3


Contoh Teorema DeMorgan: NOR

(X + Y)’ = (X’ · Y’)

(X + Y)’ dirujuk sebagai gerbang NOR pada ekspresi gerbang logika

4


Gerbang-gerbang NAND & NOR

Menggunakan jumlah rangkaian yang lebih sedikit ketimbang gerbang-gerbang AND & OR

Fan-in & Fan-out

5


Generalisasi Teorema DeMorgan

(T14) [F(X1, X2, . . ., Xn, +, ·)]’ = F(X1’, X2’, . . ., Xn’, · , +)

Diberikan suatu ekspresi logika n-variabel, komplemennya dapat ditemukan melalui “swapping + dan · dan penkomplemenan seluruh variabel

Contoh:

F(W,X,Y,Z) = (W’ · X) + (X · Y) + (W · (X’ + Z’))

= ((W)’ · X) + (X · Y) + (W · ((X)’ + (Z)’))

[F(W,X,Y,Z)]’ = ((W’)’ + X’) · (X’ + Y’) · (W’ + ((X’)’ · (Z’)’)) Gunakan (T4) (X’)’ = X, pers. Diatas dpt disederhanakan menjadi:

[F(W,X,Y,Z)]’ = (W + X’) · (X’ + Y’) · (W’ + (X · Z))

6


REVISI DualitasSetiap teorema pada aljabar switching tetap benar jika 0 & 1

di-swapped dan · & + di-swapped.

Benar karena seluruh duals dari seluruh aksioma adalah benar, sehingga duals dari seluruh teorema aljabar switching dapat dibuktikan dengan menggunakan duals aksioma-aksioma..

Kita dapat menuliskan kembali teorema DeMorgan sebagai

berikut [F(X1, X2, …., Xn)]’ = FD(X1’, X2’, …., Xn’) Catatan …

A · B + C A + B · C (A + B) · CDuality bukan berarti ekuivalensi !!

7


Manipulasi ekspresi BooleanBagaimana menyatakan (A · B + C)?Gunakan teorema DeMorgan …

A · B + C = ( ( A · B + C )’ )’ = ( ( A · B )’ · C’ )’ = ( ( A’ + B’ ) · C’ )’( A · B + C )’ = ( A’ + B’ ) · C’

8


Aksioma-aksioma dan Teorema-teorema Aljabar Switching

(A1) X = 0 if X ¹ 1 (A1’) X = 1 if X ¹ 0 (A2) If X = 0, then X’ = 1 (A2’) if X = 1, then, X’ = 0 (A3) 0 . 0 = 0 (A3’) 1 + 1 = 1 (A4) 1 . 1 = 1 (A4’) 0 + 0 = 0 (A5) 0 . 1 = 1 . 0 = 0 (A5’) 1 + 0 = 0 + 1 = 1 (T1) X + 0 = X (T1’) X . 1 = X (Identities) (T2) X + 1 = 1 (T2’) X . 0 = 0 (Null elements) (T3) X + X = X (T3’) X . X = X (Idempotency) (T4) (X’)’ = X (Involution) (T5) X + X’ = 1 (T5’) X . X’ = 0 (Complements) (T6) X + Y = Y + X (T6’) X . Y = Y . X (Commutativity) (T7) (X + Y) + Z = X + (Y + Z) (T7’) (X . Y) . Z = X . (Y . Z) (Associativity) (T8) X . Y + X . Z = X . (Y + Z) (T8’) (X + Y) . (X + Z) = X + Y . Z (Distributivity) (T9) X + X . Y = X (T9’) X . (X + Y) = X (Covering) (T10) X . Y + X . Y’ = X (T10’) (X + Y) . (X + Y’) = X (Combining) (T11) X . Y + X’. Z + Y . Z = X . Y + X’ . Z (T11’) (X + Y) . ( X’ + Z) . (Y + Z) = (X + Y) . (X’ + Z) (Consensus) (T12) X + X + . . . + X = X (T12’) X . X . . . . . X = X (Generalized idempotency) (T13) (X1 . X2 . . . . . Xn)’ = X1’ + X2’ + . . . + Xn’ (T13’) (X1 + X2 + . . . + Xn)’ = X1’ . X2’ . . . . . Xn’ (DeMorgan’s theorems) (T14) [F(X1, X2, . . ., Xn, +, .)]’ = F(X1’, X2’, . . ., Xn’, . , +) (Generalized DeMorgran’s theorem)

9


Definisi lanjut – Ekspresi Boolean Term perkalian:

Z’, (W · X · Y), (X · Y’ · Z), (W’ · Y’ · Z)

Term penjumlahan: Z’, (W + X + Y), (X + Y’ + Z), (W’ + Y’ + Z)

Ekspresi sum-of-products (SOP):

Z’ + (W · X · Y) + (X · Y’ · Z) + (W’ · Y’ · Z)

Ekspresi product-of-sums (POS) : Z’ · (W + X + Y) · (X + Y’ + Z) · (W’ + Y’ + Z)

Term normal: term perkalian atau penjumlahan di dalamnya tidak ada variabel yang muncul lebih dari sekali.

Contoh-contoh term-term non-normal: W·X·X·Y’ W+W+X’+Y X·X’·Y Contoh-cobtoh term-term normal: W·X·Y’ W+X’+Y 0

10


Minterm dan Maxterm

Minterm: Sebuah minterm n-variabel merupakan sebuah term perkalian normal

dengan n literals. Terdapat 2n term perkalian yang demikian. Contoh-contoh minterm 4-variabel:

W · X’ · Y’ · Z’ W · X · Y’ · Z W’ · X’ · Y · Z’ Dapat didefinisikan sebagai sebuah term perkalian yang = 1 pada benar-

benar satu baris dari tabel kebenaran

11


Cont’

Maxterm: Sebuah maxterm n-variabel merupakan sebuah term penjumlahan normal

dengan n literals. Terdapat 2n term penjumlahan yang demikian. Contoh-contoh maksterm 4-variabel:

W’ + X’ + Y + Z’ W + X’ + Y’ + Z W’ + X’ + Y + Z Dapat didefiniskan sebagai sebuah term penjumlahan yang = 0 pada

benar-benar satu baris dari tabel kebenaran

12


Minterms/Maxterms untuk sebuah fungsi 3-variabel

13


Representasi Penjumlahan Kanonis

Minterm i : Baris i dari tabel kebenaran yang memiliki keluaran 1 1

Penjumlahan Kanonis (Canonical sum):

Jumlah dari seluruh minterms untuk suatu fungsi yang diberikan (tabel kebenaran)

Notasi Σ:

Contoh: Σ X,Y,Z (0, 3, 4, 6, 7)

= X’·Y’·Z’ + X’·Y·Z + X·Y’·Z’ + X·Y·Z’ + X·Y·Z

Representasi ini biasa direalisasi dengan menggunakan rangkaian logika AND-OR 2 level dengan inverter-iverter pada masukan-masukan gerbang AND, seperti yang diperlukan

14


Example Fungsi direpresentasikan dengan tabel kebenaran:

mempunyai representasi penjumlahan kanonis sebagai berikut:

15


Representasi perkalian kanonis

Maxterm i: baris i dari tabel kebenara yang mempunyai keluaran 0

Pekalian kanonis:

Perkalian dari maxterms untuk suatu fungsi yang diberikan (tabel kebenaran)

Notasi :

Contoh: X,Y,Z (1,2,5)

= (X + Y + Z’) . (X + Y’ + Z) . (X’ + Y + Z’)

Representasi direalisasi dengan menggunakan rangkaian logika OR-AND 2 levels dengan inverter-inverter pada masukan-masukan gerbang OR, seperti dibutuhkan

16


Example

17


Konversi antara daftar Minterm/Maxterm

Dapatkan komplemen dari set …

Contoh: Σ X,Y,Z(0,1,2,3) = X,Y,Z(4,5,6,7) Σ X,Y(1) = X,Y(0,2,3) Σ W,X,Y,Z(0,1,2,3,5,7,11,13) = W,X,Y,Z(4,6,8,9,12,14,15)

18


Thank you !!!

19

10 11.teknik digital aljabar-boolean_02

Technology