Chapter 3 Logic Gates

Digital Logic

Logic Gates

Logic gate is an element to build a digital circuit logic block. It can make a logical decision for the digital circuit. The most common logic gates are AND, OR, XOR, NOT, NOR, NAND and XNOR. The logic gates NOR and NAND which are also called universal gates. Logic gates which can be one or more inputs and only produce single output.

AND Gate

A	B	F(A∩B)
0	0	0
0	1	0
1	0	0
1	1	1

AND gate is a basic digital logic gate that implement the logical conjunction. According to the truth table, with an operation of AND(F=AB or F=A.B). AND gate only produces an output of 1 when BOTH the inputs are 1, otherwise the output is 0.

OR Gate

A	B	F(A∪B)
0	0	0
0	1	1
1	0	1
1	1	1

OR gate is a basic digital logic gate that implement the logical disjunction. According to the truth table, with an operation of OR(F=A+B). OR gate produces an output of 1 when there is either or both inputs are 1.

XOR Gate

A	B	F
0	0	0
0	1	1
1	0	1
1	1	0

XOR gate(EOR gate or ExOR gate) is a basic logic gate that implement an exclusive or (exclusive disjunction). According to the truth table, with an operation of XOR(F=A.B'+A'.B). XOR gate will only produces output 1 when there is only one of the input is 1 and another is 0. That's mean is both of the inputs are 0 or 1, then the output will be 0.

NOT Gate

A	F
0	1
1	0

NOT gate is a basic logic gate that implement logical negation, it's also known as an inverter because it changes the input to its opposite(inverts it). According to the truth table, with an operation of NOT(F=A' or F=!A). NOT gate will only receive one input and produce an output by invert input. For example, when NOT gate received an input 1, then the output will be 0. Otherwise, if the input is 0, then the output will be 1.

NAND Gate

A	B	F
0	0	1
0	1	1
1	0	1
1	1	0

NAND gate(Negated AND or NOT AND) is called a universal gate because combinations of it can be used to accomplish all the basic functions. According to the truth table, with an operation of NAND[F=(A.B)']. NAND gate produces output 1 if it received either one or both 0. The output of NAND  gate is reverse from AND gate.

NOR Gate

A	B	F
0	0	1
0	1	0
1	0	0
1	1	0

NOR gate(Negated OR or NOT OR) is called a universal gate because combinations of it can be used to accomplish all the basic functions. According to the truth table, with an operation of NOR[F=(A+B)']. NOR gate produces output 1 only when it received BOTH input 0,other than that. The output of NOR gate is reverse from OR gate.

Chapter 3 Combinational Circuits

Boolean Algebra

• A branch of mathematics and it can be used to describe the manipulation and processing of binary information.
• Boolean algebra is algebra for the manipulation of ojects that can take only two values: True & False
• Normally we will interpret the digital value 0 as false and digital value 1 as true.
• A Boolean algebra have two binary operation which is commonly denoted by + and ·,besides that it is a unary operation, usually denoted by ¯ or ~ or '.
•  x + x' = 1 and x·x' = 0

Truth Table

• A truth table shows how a logic circuit's output responds to various combinations of the inputs, using logic 1 for true and logic 0 for false. 
• The output can be achieved by a combination of logic gates.

Basic Logic Gates

• Basic logic diagram is a graphical representation of a logic circuit that shows the wiring and connections of each individual logic gate, represented by a specific graphical symbol,that implements the logic circuit.
• There are many types of logic gates but we are here just show few logic gates.

Multi input Logic Gate

Combination of AND gates

Boolean Expression

	AND Form	OR Form
Identity Law	A.1=A	A+0=A
Zero and One Law	A.0=0	A+ 1=1
Inverse Law	A.A’=0	A+A’=1
Idempotent Law	A.A=A	A+A=A
Commutative Law	A.B=B.A	A+B=B+A
Associative Law	A.(B.C)=(A.B).C	A+(B+C)=(A+B)+C
Distributive Law	A+(B.C)=(A+B).(A+C)	A.(B+C)=(A.B)+(A.C)
Absorption Law	A(A+B)=A	A+A.B=A A+A’B=A+B
DeMorgan’s Law	(A.B)’=A’+B’	(A+B)’=A’.B’
Double Complement Law	(X’)’=X

For example:
Simplify the following Boolean expression

1. XY′Z′+XY′Z′W+XZ′

= XY'Z'(1+W)+XZ'
= XY'Z'+XZ'                        (because (1+W)=1)
= XZ'(Y'+1)                      
= XZ'                                  (because (Y'+1)=1)

2.(X+Y)(Y+Z)(X'+Z)
= (XY+XZ+YY+YZ)(X'+Z)
= XX'Y+XX'Z+X'YY+X'YZ+XYZ+XZZ+YYZ+YZZ
= X'Y+X'YZ+XYZ+XZ+YZ+YZ                 (because XX'=0,YY=Y,andZZ=Z)
= X'Y(1+Z)+XZ(Y+1)+YZ                        (because YZ+YZ=YZ)
= X'Y+XZ                                              (because 1+Z=1 and Y+1+1)

Boolean Equation Forms
All boolean equation can be divided into 2 forms which is:
a) Sum of product(SOP)
eg:
1. F = A+AB+ABC'
2. F = X+YZ+XZ
3. F = XY+YZ+X'Z

b) Product of sum(POS)
eg:
1. F = (A+B)(B+C)(C+D)
2. F = (X'+Y')(X+Z')(Y+Z)

De Morgan's Law

 A * B = A + B

Proof:

x ∈ (A ∩ B)' 
x ∉ A ∩ B
x ∉ A or x ∉ B
x ∈ A' or x ∈ B' 
x ∈ A' ∪ B' 
(A ∩ B)' = A' ∪ B'
Therefore, (A.B)'= A'+B' 


A + B = A * B

Proof:

x ∈ (A ∪ B)' 
x ∉ A ∪ B
x ∉ A and x ∉ B
x ∈ A'  and x ∈ B' 
x ∈ A' ∩ B' 
(A ∪ B)' = A' ∩ B' 
Therefore, (A + B)' = A' * B' 

Chapter 3 Combinational Circuits(Karnaugh Map)

Chapter 3 The Basic Of Logic Design

K-Map ( Karnaugh Map)

Peta Karnaugh adalah peta yang telah diilhamkan oleh seorang pakar matematik yang bernama maurice Karnaugh pada tahun 1953. Ia digunakan untuk mempermudahkan sesuatu ungkapan logik atau  untuk menukarkan jadual  kebenaran kepada litar logik sepadannya melalui proses yang mudah dan teratur. Ia disusun sebegitu rupa supaya setiap kotak yang diletakkan bersebelahan berbeza hanya 1 bit sahaja  diantara satu sama lain.

Bilangan kotak yang diperlukan untuk sesuatu bilangan pembolehuban berkait dengan 2^n. . Ini bermaksud sekiranya terdapat 2 pembolehubah maka 4 kotak diperlukan. Sekiranya terdapat 3 pembolehubah 8 kotak diperlukan dan begitu juga seterusnya. Untuk lebih memahami tentang bagaimana pembinaan  sesuatu peta Karnaugh, perhatikan contoh yang berikut"-

Membina peta Karnaugh 2 angkaubah:-
Contoh 1:
Diberi jadual kebenaran seperti yang ditunjukkan pada Jadual 1, buatkan pada Karnaugh  untuk jadual tersebut:-





Jadual 1: Jadual Kebenaran



Penyelesaian:

Oleh kerana untuk jadual kebenaran tersebut hanya terdapat 2 angkaubah, peta Karnaugh yang perlu dibina hanya mempunyai 4 kotak sahaja. Setiap kotak dalam peta Karnaugh adalah mewakili keluaran untuk sesuatu jadual keberanan. Untuk petak A' B' sebenarnya adalah sama dengan masukan  00 di dalam jadual kebenaran, oleh itu keluaran 0 untuk masukan tersebut perlulah dimasukan ke dalam petak. A'B' di dalam peta Karnaugh pada Jadual 2.

	A’	A
B’	0	1
B	1	0

 Jadual 2: Peta Karnaugh

Contoh 2:
Diberikan ungkapan logik Z=A'B' +A'B+AB'. Buatkan peta Karnaugh untuk ungkapan logik yang tersebut.

Penyelesaian:
Oleh kerana hanya ungkapan logik sahaja yang diberi, anda dikehendaki membuat andaian yang berikut:

Untuk ungkapan yang terdapat dalam soalan, katakan A'B'=1. Anda perlu mengisikan logic 1 dalam peta Karnaugh pada Jadual 3. Ungkapan yang tidak terdapat di dalam soalan, anda dikehendaki mengisikan logik 0 ke dalam petak tersebut.

Z=A'B'+A'B+AB'

	A’	A
B’	1	1
B	1	0

 Jadual 3: Peta Karnaugh bagi unkapan Z=A'B'+A'B+AB'

Membina peta Karnaugh 3 angkaubah

Contoh 1

 Binakan peta Karnaugh daripada jadual kebenaran seperti yang ditunjukkan pada Jadual 4 yang berikut:-

Jadual 4: Jadual Kebenaran 3 angkaubah

Penyelesaian:

Daripada jadual kebenaran yang diberi terdapat 3 masukan iaitu A, B dan C. Oleh itu, berdasarkan kepada formula yang telah diberi, anda perlu membina 8 kotak untuk 3 angkaubah tersebut. Kotak yang perlu dibina adalah seperti pada Jadual 5, di mana setiap petak adalah mewakili  keluaran untuk setiap masukan jadual kebenaran . Contohnya masukan 000 adalah sama dengan  petak A'B'C' , oleh itu pada petak tersebut mestilah dimasukkan 0. Begitu juga dengan petak yang lain.

	A’B’	A’B	AB	AB’
C’	0	0	0	0
C	1	1	1	1

 Jadual 5: Peta Karnaugh 3 angkaubah