Aljabar Boolean dan Gate

Gerbang

• Digital adalah rangkaian yang bernilai 1 atau 0, true atau false, on atau off
• 0 sampai 1 🡺 biner 0
• 2 sampai 5 🡺 biner 1
• Diluar hal tersebut tidak di ijinkan
• Gerbang adalah peralatan elektronik kecil yang dapat mengkalkulasi berbagai fungsi dari sinyal dengan dua nilai

​

Transistor dan Gerbang

+ V_cc

V_out

Kolektor

Basis

Emiter

V_in

+ V_cc

V_out

V₁

V₂

+ V_cc

V_out

V₁

V₂

Inverter/

_NOT

Nand

Nor

5 Gerbang Utama

A

X

NOT

NAND

NOR

AND

OR

Inverter

AND Adalah NAND yang di invert

OR Adalah NOR yang di invert

NAND dan NOR butuh 2 T

AND dan OR butuh 3 T

Aljabar Boolean

• Logic (logika) berasal dari kata logos (Bhs. Yunani) yang artinya kata (word) atau apa yang diucapkan, kemudian berubah menjadi studi sistem preskriptif dari argumen (argument) dan penalaran (reasoning), yaitu sistem yang menjadi acuan bagaimana manusia harus berfikir.
• Logika dapat dikatakan sebagai bentuk penarikan kesimpulan, apakah sesuatu atau argumen itu absah (valid) atau sebagai pendapat yang keliru (fallacious).
• Logika mendefinisikan struktur statement dan formula argument dan devises di mana semuanya dibuat kodenya.
• Dua kategori logika:
• Deductive reasoning : secara logika apa yang harus dilakukan dari suatu pendapat (premise).
• Inductive reasoning : bagaimana cara menyatakan sejumlah kejadian hasil pengamatan menjadi sebuah bentuk umum yang dapat dipercaya.

​

Aljabar Boolean

• Jenis logika:
• Aristotelian : 2 prinsip penting dalam logika yaitu tidak ada rumusan (preposition) benar atau salah dan adanya sebuah rumusan mungkin benar atau salah.
• Formal : hubungan antara konsep dan adanya sebuah cara untuk membuat komposisi bukti-bukti pernyataan
• Mathematical : logika berbasis formal untuk studi pemikiran matematikal.
• Philosophical : kaitan antara bahasa alami dan logika.
• Predicate : sentential logic level yang menjelaskan sifat kerja kata-kata seperti and, but, or, not, if-then, if and only if, dan neither-nor.
• Multi-valued : logika yang menambahkan possible sebagai harga ketiga selain false dan true.

​

Aljabar Boolean

• Komputasi çè logika formal:
• Logika Boolean (aljabar Boolean)
• Fuzzy logic.
• Aljabar Boolean:
• Dibuat George Boole (1850) dikembangkan John Venn (1881, Symbolic Logic) dan diperhalus Charles Dodgson menjadi Diagram Venn.
• S {K buah elemen dan 2 operator (product, sum)}
• Prinsip duality, cara mempertukarkan operasioperasi product dengan sum atau sebaliknya.

​

Aljabar Boolean

• Definisi, boolean algebra
• An algebraic structures which capture the essence of the logical operations [AND, OR, NOT] as well as the set theoretic operations [union, intersection, complement]
• An abstract mathematical system primarily used in computer science and in expressing the relationships between groups of objects or concepts (sets).
• Penggunaan teknik aljabar untuk ekspresi proportional calculus.
• Sifat-sifat fungsi-fungsi Boolean
• Logical sum, that is Boolean OR, of several argument values is true if one or more of the argument values is true and is false only if all the argument values are false.
• Logical product, that is Boolean AND, of several argument values is false if any of the argument values is false and is true only if all the argument values are true.
• NOT function ensures that NOT false = true and NOT true = false.

​

Definisi Formal

• Definisi Formal (lanjutan)
• Mutually distributive:
• a ^(b v c) = (a ^ b)v(a ^ c) dan
• a v(b ^ c) = (a v b) ^ (a v c)
• Universal bounds:
• 0 ^ a = 0, 0 v a = a, I ^ a = a, I v a = I
• Unary operations (inverse):
• a ^ a’ (¬a) = 0
• a v a’ = I
• De Morgan:
• ¬(ab) = ¬a v ¬b
• ¬(a + b) = ¬a ^ ¬b

​

Simplifikasi

• Simplifikasi: C + ¬(BC)

​

Simplifikasi

• Simplifikasi: ¬(AB)(¬A + B)(¬B + B)

Simplifikasi

• Simplifikasi: (A + C)(AD + A(¬D)) + AC + C

​

Ekspresi Boolean

• Bentuk
• Triplets: A OR B, X AND y
• Diadics: NOT Z
• Hirarki evaluasi
• Urutan top-bottom
• Ekspresi tanda kurung
• NOT
• AND
• OR
• Contoh: A AND B OR NOT C AND D identik dengan ((A AND B) OR ((NOT C) AND D))

​

Notasi Boolan

• Umum

​

AND OR NOT

Pemrograman && || ~

Operasi Boolean-1 · + -

Operasi Boolean-2 + ¬

Operasi Boolean-3 ^ v /

​

• Variabel
• True=T=On=1
• Fasle=F=Off=0
• Polish
• A • B => A B •
• A + B =>AB +
• ~B =>B ~
• Contoh: (A B) + ~(C + D) è ((A B )((C D + )~) +) è A B C D + ~ +

​

Aljabar Boolean

• Variabel dan fungsi yang memiliki nilai 0 dan 1

​

A

M

B

C

-A

-B

-C

A

B

C

-A

-B

-C

1

2

3

4

5

6

7

-ABC

A-BC

AB-C

ABC

TK F.Mayoritas

Rangkaian TK F.Mayoritas

M=f(ABC)

Tabel Kebenaran

Aljabar Boolean

• Simplifikasi aljabar Boolean memungkinkan desainer komputer membuat sirkit elektrikal.
• Dari fungsi F (N argumen) dapat didefinisikan sebuah tabel kebenaran dengan 2N masukan dapat digunakan untuk mencari ekspresi minterm dan maxterm. Misal untuk var. A, B, dan C:

​

Aljabar Boolean

• A term is a variable or a product (logical AND) of several different literals. For example, if you have two variables, A and B, there are 8 possible terms: A, B, ¬A, ¬B, ¬A¬B, ¬AB, A¬B, and AB.
• A minterm is a product containing exactly N literals.
• In general, there are 2N minterms for N variables.
• The set of possible minterms is very easy to generate since they correspond to the sequence of binary numbers.

​

Aljabar Boolean

• Representasi singkat
• Sum of minterms (SOM) ~ keluaran dari baris tabel kebenaran harganya 1, menggunakan notasi sigma (S).
• Product of maxterms (POM) ~ keluaran dari baris tabel kebenaran harganya 0, menggunakan notasi phi (? ).
• Contoh, dari tabel kebenaran hal. 14:
• F(A, B, C) = ¬A.¬B.¬C + ¬A.B.C + A.B.¬C

= m0 + m3 + m6 = S m (0, 3, 6)

• F(A,B,C) =

(A+B+¬C).(A+¬B+C).(¬A+B+C).(¬A+B+¬C).(¬A+¬B+¬C)

= M1M2M4M5M7 = ? M(1, 2, 4, 5, 7)

​

Aljabar Boolean

• Minterms dan SOM untuk 4-variabel:
• Y = ~A~BCD + ~ABCD + A~B~CD [blok]

​

Membaca Tabel Kebenaran (TK)

• Karena n var, kemungkinannya 2ⁿ
• Untuk 2 var = 00 01 10 11
• Dibaca berdasarkan kolom hasil
• NOT = 01 (2 bit=4 kemungkinan)
• NAND =1110 (4 bit=16 kemungkinan)
• NOR =1000 (4 bit=16 kemungkinan)
• AND =0001 (4 bit=16 kemungkinan)
• OR =0111 (4 bit=16 kemungkinan)
• Operator AND = . atau DOT
• Operator OR = + atau plus

Elektronika Dasar

Integrated Circuit (IC)

• IC (rangkaian terpadu) sering disebut chip

Kemasan dengan 2 deret pin diluar dan IC di dalamnya secara teknis disebut sebagai Dual Inline Packages (DIP)

– Klasifikasi chip:

• SSI (small scale integrated) = 1 -10 gates
• MSI (medium scale integrated) = 10 – 100 gates
• LSI (large scale integrated) = 100 – 100000 gates
• VLSI (very large scale integrated) = > 100000 Gates
• Contoh chips Intel: 4004, 8008, 8080, 8085, 8086, 80x86, Pentium, Itanium.
• Kemasan paling umum memiliki 14, 16, 18, 20, 22, 24, 28, 40, 64 atau 68 pin.

​

• Logika & teknologi gate
• IC = S (diode, resistor, transistor) secara terpadu; bipolar atau MOS.
• Bipolar menghasilkan SSI dan MSI yang cepat, tetapi perlu daya dan volume IC besar.
• DTL (diode-transistor logic)
• TTL (transistor-transistor logic)
• ECL (emitter-coupled logic)
• MOS menghasilkan LSI, VLSI, ULSI yang kompak, daya kecil, tetapi lebih lambat dibanding bipolar
• PMOS (p-Channel MOSFET)
• NMOS (n-channel MOSFET)
• CMOS (complimentary MOSFET)

​

• Implementasi TTL, seri
• 74xx, bekerja pada 0 - 70 C dan 4.75 - 5.25 V; 2 jenis: high-speed TTL dan low-power TTL.
• 52xx, bekerja pada -55 - >125 C dan 4.75 - 5.25 V; khusus untuk keperluan militer
• Karakteristik TTL
• Floating TTL input akan bekerja sebagai high input
• Worst-case input voltage, masukan antara 2 to 5 V akan menjadi high input untuk TTL
• Worst-case output voltage, output antara 0.4 - 2.4 V
• Compatible, output satu TTL bisa jadi input TTL lain.

​

• Karakteristik TTL
• Noise margin, selisih tegangan TTL driver – TTL load = 0.4 V, merepresentasikan proteksi terhadap noise.
• Sourcing & sinking, jika TTL output rendah akan muncul arus emitter yang bergerak dari emitter ke collector [= sink] dan sebaliknya sebaliknya bila TTL output tinggi [= source].
• Standard loading, sink = 16mA dan source = - 400 mA
• Loading rules: pick driver - pick load è fanout = max number of TTL emitters that can be reliably driven under worst-case conditions pada irisan keduanya.

​

Contoh dari F.Mayoritas

• A=1,B=0,C=1 maka A.-B.C=1
• -A.B+B.-C=1, untuk A=1 dan B=0 atau B=1 dan C=0
• -A.B.C=1 (Z1)
• A.-B.C=1 (Z2)
• A.B.-C=1 (Z3)
• A.B.C=1 (Z4)
• Jadi M=1(benar) jika salah satu dari Z1..Z4 adalah 1 (benar)
• M=-A.B.C+A.-B.C+A.B.-C+A.B.C

Implementasi Fungsi Boolean

1. Tulis Tabel Kebenaran dari Fungsi tsb
2. Sediakan Inverter (Gerbang NOT) untuk menghasilkan komplemen tiap input
3. Gambar Gerbang AND dengan sebuah Bit 1 pada kolom hasil
4. Hubungkan Gerbang AND ke input yang sesuai
5. Masukkan output gerbang AND ke Gerbang OR

Step 1, Tabel Kebenaran�M=Fungsi(ABC)

• 3 var, jadi 2³=16, buat tabel dengan 3 var dan 16 kemungkinan

Step 2, Inverter dan komplemennya�M=F(ABC)

A

B

C

-A

-B

-C

A

B

C

-A

-B

-C

1

2

3

Komplemen Inverter A,B dan C

Step 3, Gambar gerbang AND�M=F(ABC)

A

B

C

-A

-B

-C

A

B

C

-A

-B

-C

1

2

3

4

5

6

7

Step 4, Hubungkan input yang sesuai dengan gerbang AND�M=F(ABC)

A

B

C

-A

-B

-C

A

B

C

-A

-B

-C

1

2

3

4

5

6

7

-ABC

A-BC

AB-C

ABC

Kemungkinan kombinasi dari

Hasil Inverter adalah –ABC,A-BC,

AB-C dan ABC

Step 5, Masukan Output gerbang AND ke Sebuah Gerbang OR�M=F(ABC)

A

M

B

C

-A

-B

-C

A

B

C

-A

-B

-C

1

2

3

4

5

6

7

-ABC

A-BC

AB-C

ABC

Rangkaian TK F.Mayoritas

M=f(ABC)

IMPLEMENTASI Fungsi Boolean (lanj.)

• Menggunakan gerbang NAND dan NOR, sesuai prosedur tadi, sehingga membentuk gerbang NOT,OR dan AND
• Ganti gerbang multi input dengan rangkaian ekuivalen yang memiliki 2 input.
• Misal A+B+C+D, menjadi (A+B)+(C+D) dengan 3 OR 2 input
• Terakhir gerbang NOT,OR dan AND di ganti dengan rangkaian sbb :

IMPLEMENTASI Fungsi Boolean (lanj.)

A

B

A

A

-A

-A

AB

A

B

AB

A

B

AB

A+B

A

B

Gerbang NAND

Gerbang NOR

1 var di NAN dan di NOR

= NOT

2 var di NAND= AND

2 var di NOR= OR

Ekuivalensi Rangkaian

• Ide Jumlah gerbang semakin sedikit cost semakin murah

Rangkaiannya

A

B

C

AB

AC

AB+AC

A

B

C

B+C

A(B+C)

Hukum Aljabar Boolean

Alternatif gerbang NAND, NOR dan OR

-(AB)

=

(-A)+(-B)

-(A+B)

=

(-A)(-B)

(AB)

=

-((-A)+(-B))

(A+B)

=

-((-A)(-B))

3 Rangkaian menghitung XOR dengan NAND dan NOR

-A

B

A

-B

-A

B

A

-B

-A

B

A

-B

Tabel XOR

K-Map

• Metoda yang diperkenalkan oleh Maurice Karnaugh (1953).
• Penyederhanaan suatu ekspresi menjadi sebuah minimal sum of products (MSP).
• N buah variabel akan mempunyai 2N buah square, yang merepresentasikan kombinasi minterm atau invers-nya.
• Cara lain simplifikasi ekspresi boolean berdasar truth table dan buat matriks minterms.

​

K Map

• Minimization Technique
• Based on the Unifying Theorem: X + X' = 1
• The expression to be minimized should generally be in sum-of-product form.
• The function is mapped onto the K-map by marking a 1 in those squares corresponding to the terms in the expression.
• The other squares may be filled with 0's.
• Pairs of 1's on the map which are adjacent are combined using the theorem Y(X+X') = Y where Y is any Boolean expression.

​

Contoh

Contoh

• Penyederhanaan, misal untuk 3 var:

¬A¬BC + ¬ABC = ¬AC·(¬B + B) = ¬AC · 1 = ¬AC

• Perluasan/pengembangan, misal untuk 3 var:

AB + ¬BC + AC = (AB · 1) + (¬B C · 1) + (AC · 1)

= (AB · (¬C + C)) + (¬BC · (¬A + A)) + (AC ·

(¬B + B)) = (AB¬C + ABC) + (¬A¬BC + A¬BC)

+ (A¬BC + ABC) = AB¬C + ABC + ¬A¬BC

+ A¬BC = ¬A¬BC + A¬BC + AB¬C + ABC

​

• Pengelompokan:
• Pair, grup 2 buah bit 1 yang berdekatan.
• Quad, grup 4 buah bit 1 yang berdekatan.
• Octet, grup 8 buah bit 1 yang berdekatan.
• Overlapping, memanipulasi pengelompokan bit 1 lebih dari satu kali.
• Rolling, misalkan 2 pair di dua sisi digabung penjadi quad.
• Don’t care, sebuah truth table mungkin menghasilkan output tak jelas.

​

• Pemahaman
• pair ~ grup 2 buah bit 1yang berdekatan, secara horisontal atau vertikal
• quad ~ grup 4 buah bit 1 yang berdekatan dalam pola segi-4 atau deret [horisontal/ vertikal]
• octet ~ grup 8 buah bit 1 yang berdekatan
• • Contoh

​

Contoh