ECE 3103
Digital Electronics
Boolean Algebra
Course Teacher
Dr Rafia Nishat Toma
Associate Professor
ECE Discipline,
Khulna University
Syllabus (Section A)
• Information & Digital Systems
✓ Introduction to digital systems, number systems, weighted and non-weighted
codes, code conversion, binary addition and subtraction, 2‟s complement method.
• Boolean Algebra
✓ Digital logic, Boolean algebra, Boolean function, canonical forms, Karnaugh
maps, minimization of Boolean functions, logic gates and their truth tables, design
methodologies,
• Combinational Logic Circuits
✓ combinational logic circuit design, arithmetic and data handling logic circuits,
decoder, encoder, multiplexer, demultiplexer.
• Sequential Logic Circuits
✓ SR, JK, T, and D flip-flops, master-slave JK flip-flop, timing diagrams of
different flip-flops, edge-triggered and leveltriggered timing diagrams, counters, registers,
memory, finite state machine, asynchronous & synchronous sequential systems, reliable
design and fault diagnosis.
2
Boolean Algebra & Combinational Logic Circuits
• Boolean Algebra
• Logic Gates and Operation:
Outline • AND, OR, NOT, NOR, NAND, XOR, XNOR
• Describing Logic Circuits Algebraically
• Determining Output Level from a Diagram
Implementing Circuits from Boolean Expressions
3
Boolean Algebra & Combinational Logic Circuits
❑ Boolean Algebra:
• Digital circuits operate in the binary mode where each input and output voltage
is either a 0 or a 1; 0 and 1 designates represent predefined voltage ranges.
• Boolean algebra is a means for expressing the relationship between a logic
circuit's inputs and outputs.
❑ Boolean Constants and Variables:
• Boolean algebra differs in a major way from ordinary algebra in that Boolean
constants and variables are allowed to have only two possible values 0 or 1.
• Boolean 0 and 1 do not present actual numbers but instead represent the
state of a voltage variable, or what is called its logic level.
• In fact, in Boolean algebra there are only three basic operations: OR, AND,
and NOT. These basic operations are called logic operations.
• Digital circuits called logic gates can be constructed from diodes, transistors,
and resistors connected in such a way that the circuit output is the result of a
basic logic operation (OR, AND, NOT) performed on the inputs.
4
Boolean Algebra & Combinational Logic Circuits
❑ Truth Tables:
• A Truth Table is a means for describing how a logic circuit's output
depends on the logic levels present at the circuit inputs.
Figure 1. Example of Truth Table for two-input and three-input.
• The table lists all possible combinations of logic levels present at inputs A and B along
with the corresponding output level x. 5
Boolean Algebra & Combinational Logic Circuits
❑ OR Operation:
• The Truth Table in Figure 2(a) shows what happens when two logic inputs, A
and B, are combined using the OR Operation to produce the output x.
• The table shows that x is a logic 1 for every combination of input levels where one or
more inputs are 1. The only case where x is a logic 0 is when both inputs are 0.
Figure 2. (a) Truth table defining the OR operation; (b) circuit symbol for a two-input OR gate.
• The Boolean expression for the OR Operation is ~
(1)
• In the operation, the "+" sign does not stand for ordinary addition; it stands for the
operation.
6
Boolean Algebra & Combinational Logic Circuits
❑ OR Gate:
• In digital circuitry an OR Gate is a circuit that has two or more inputs and
whose output is equal to the OR combination of the inputs.
• The inputs A and B are logic voltage levels, and the output x is a logic voltage
level whose value is the result of OR operation on A and B; that is x = A + B.
• Figure 3 shows a three-input OR gate and its Truth Table. The Boolean
expression for the three-input OR operation is ~
(2)
Figure (3). Symbol and Truth Table for a three-input OR gate.
7
Boolean Algebra & Combinational Logic Circuits
❑ OR Gate:
• The examination of the Truth Table shows again that the output will be 1 for
every case where one or more inputs are 1. This general principle is the same for all
OR gates with any number of inputs.
• Figure 4 shows the standard TTL SSI two input OR gate.
Figure (4). Quadruple two-input OR-gates.
8
Boolean Algebra & Combinational Logic Circuits
❑ OR Gate:
Example (1): Determine the OR gate output in Figure 5. The OR gate inputs A and B are
varying according to the timing diagrams shown. For example, A starts out LOW at time
t0, goes HIGH at t1, back LOW at t3, and so on.
Figure 5
9
Boolean Algebra & Combinational Logic Circuits
❑ AND Operation:
• The Truth Table in Figure 6(a) shows what happens when two logic inputs, A
and B, are combined using the AND Operation to produce output x. The Table
shows that x is a logic 1 only when both inputs (A and B) are at the logic 1
level. For any case where one of the inputs is 0, the output is 0.
Figure 6. (a) Truth Table for AND Operation; (b) AND gate symbol.
• The Boolean expression for the AND Operation is ~
(3)
• In this expression, the “.” sign stands for the Boolean AND operation and not the
multiplication operation.
10
Boolean Algebra & Combinational Logic Circuits
❑ AND Gate:
• The logic symbol for a two-input AND gate is shown in Figure 6(b). The
AND gate output is equal to the AND product of the logic inputs; that is x =
AB. In other words, the AND gats is a circuit that operates in such a way that its
output is HIGH only when all its inputs are HIGH. For all other cases, the
AND gate output is LOW.
• This same operation is characteristics of AND gates with more than two
inputs. For example, a three-input AND gate and its accompanying Truth Table are
shown in Figure 7.
Figure 7. Truth Table and symbol for a three-input AND gate. 11
Boolean Algebra & Combinational Logic Circuits
❑ AND Gate:
Example (2): Determine the output x from the AND gate in Figure 8 for the given input
waveforms.
Solution: Figure 8
For the given input waveforms, the output becomes HIGH only during the intervals t2 – t3
and t6 – t7. At all other times, one or more of the inputs are 0, thereby producing a
LOW output. 12
Boolean Algebra & Combinational Logic Circuits
❑ AND Gate:
• Figure 9 shows standard TTL Small Scale Integration (SSI)
circuit for a two-input AND gates..
Figure 9. Quadraple two-input AND gates.
13
Boolean Algebra & Combinational Logic Circuits
❑ NOT Operation:
• NOT Operation performs on a single input variable. For example, if the variable A is
subjected to the NOT Operation, the result x can be expressed as
(4)
• Where the over bar represents the NOT Operation. Expression of Equation (4) is read as
‘x equals NOT A’.
Figure 10. (a) Truth Table for NOT Operation; (b) Symbol of NOT gate; (c) sample waveforms.
❑ NOT Circuit (INVERTER):
• Figure 10(b) shows the symbol for a NOT circuit, which is most commonly called an
INVERTER. This circuit always has only a single input, and its output logic level is always
opposite to the logic level of this input.
• Figure 10(c) shows how the INVERTER affects an input signal. It inverts the input signal at all
points of the waveform.
14
Boolean Algebra & Combinational Logic Circuits
❑ NOT Operation:
• The NOT Operation is also referred to as inversion or
complementation.
• That is .
Figure 11 shows standard TTL (SSI) circuit for hex INVERTERs/NOT gates..
Figure 11. Hex
INVERTERs/NOT gates.
15
Boolean Algebra & Combinational Logic Circuits
❑ NOR Gate:
• The NOR gate operates like an OR gate
followed by an INVERTER.
• The Boolean Expression for two input (A
and B) NOR gate is:
(5)
• The symbol for a two-input NOR gate is
shown in Figure 12(a) and the
corresponding truth table is shown in
Figure 12(b).
• The equivalent circuit of NOR gate is
shown in Figure 12(c).
The truth table of Figure 12(b) shows that
the NOR gate output is the exact inverse
of the OR gate output for all possible input
conditions.
• The same operation can be extended to
NOR gates with more than two inputs. Figure 12. (a) NOR Symbol;
16
(b) equivalent circuit; (c) truth table.
Boolean Algebra & Combinational Logic Circuits
❑ NOR Gate:
Example (3): Determine the waveform at the output of a NOR gate for the input
waveforms shown in Figure 13.
Solution: Figure 13
One way to determine the NOR output waveform is to find first the OR output
waveform ad then invert it. Another way utilizes the fact that a NOR gate output will be
HIGH only when all inputs are LOW. Thus, we can examine the input waveforms, find
those time intervals where they are all LOW, and make the NOR output HIGH for those
intervals. The NOR output will be LOW for all other time intervals. The resultant
waveform is shown in the figure. .
17
Boolean Algebra & Combinational Logic Circuits
❑ NAND Gate:
• The symbol of a two-input NAND gate is
shown in Figure 14(a).
• The NAND operates like an AND gate
followed by an INVERTER which is
shown in Figure 14(b).
• The truth table for two-input NAND gate
is shown in Figure 14(c).
• The output expression for the NAND
gate is ~ (6)
• The truth table in Figure 14(c) shows
that the NAND gate output is the exact
inverse of the AND gate for all possible
input conditions.
• This same characteristics is true for
NAND gates having more than two
inputs. Figure 14. (a) NAND Symbol;
18
(b) equivalent circuit; (c) truth table.
Boolean Algebra & Combinational Logic Circuits
❑ NAND Gate:
Example (4): Determine the output waveform of a NAND gate having the inputs
shown in Figure 15.
Solution: Figure 15
One way is to draw first the output waveform for an AND gate and then invert it..
Another way utilizes the fact that a NAND output will be LOW only when all
inputs are HIGH. Thus, you can find those time intervals during which the inputs
are all HIGH, and make the NAND output LOW for those intervals. The output
will be HIGH at all other times.
19
Boolean Algebra & Combinational Logic Circuits
❑ NOR and NAND Gates:
• Figure 16 shows standard TTL (SSI) circuit for quadraple two- input NOR
and NAND gates..
(a) (b)
Figure 16. (a) Quadraple two-input NOR gates; (b) quadraple two- input NAND
gates.
20
Boolean Algebra & Combinational Logic Circuits
❑ Exclusive-OR (XOR) Gate:
• Boolean expression for two-input
XOR operation is ~
(7)
x = A B = AB + AB
• The standard logic symbol and
truth table for XOR gate are shown in
Figures 17(a) and 17(b).
• From the truth table of Figure
17(b) we find that, the output of
the XOR gate is HIGH or 1 if and only
if its inputs are not simultaneously HIGH
or LOW.
• When all the inputs are HIGH or Figure 17. (a) XOR Symbol;
LOW, the output is LOW or 0. (b) truth table.
21
Boolean Algebra & Combinational Logic Circuits
❑ XOR Gate:
• Figure 18 shows standard TTL (SSI) circuit for quadraple two- input XOR
gate..
Figure 18. Quadraple two-input XOR gate.
22
Boolean Algebra & Combinational Logic Circuits
❑ Exclusive-NOR (XNOR) Gate:
• XNOR is the complement of XOR.
The Boolean expression for two-
input XNOR operation is ~
x = A B = A B = AB + AB (8)
• The standard logic symbol and truth
table for XNOR gate are shown in
Figures 19(a) and 19(b).
• From the truth table of Figure 19(b) we
find that, the output of the XNOR gate is
HIGH or 1 if and only if its inputs are
simultaneously HIGH or LOW.
Figure 19. (a) XNOR Symbol;
• When all the inputs are not (b) truth table.
simultaneously HIGH or LOW, the
output is LOW or 0.
23
Boolean Algebra & Combinational Logic Circuits
❑ XNOR Gate:
• Figure 20 shows standard TTL (SSI) circuit for quadraple two- input
XNOR gate..
Figure 20. Quadraple two-input XNOR gate.
24
Boolean Algebra & Combinational Logic Circuits
❑ Describing Logic Circuits Algebraically:
• Any logic circuit, no matter how complex, can be completely described
using the three basic Boolean operations (AND, OR, and NOT).
• For the circuit of Figure 21, the Boolean expression becomes ~
Figure 21. Logic circuit with its Boolean expression.
25
Boolean Algebra & Combinational Logic Circuits
❑ Describing Logic Circuits Algebraically:
Evaluating logic-circuit outputs
For the case where A = 0,
B = 1, C = 1, and D = 1.
Try Figure 3-15 (b)
26
Boolean Algebra & Combinational Logic Circuits
❑ Describing Logic Circuits Algebraically:
Example (5) (Tocci-Exercise-B: 3-12(b)): Write the Boolean expression for output x in
Figure 23. Determine the value of x for all possible input conditions, and list the values in
a truth table.
B ABC
C
ABC x = ABC + ABC + ABD
ABD
Figure 23
27
Boolean Algebra & Combinational Logic Circuits
❑ Describing Logic Circuits Algebraically:
Example (5) (Tocci-Exercise-B: 3-12(b)):
Solution (Continued):
Figure 24. The truth table for the circuit of Figure 22.
28
Boolean Algebra & Combinational Logic Circuits
❑ Determining Output Level from a Diagram:
• The output logic level for given input levels can also be determined
directly from the circuit diagram without using the Boolean expression.
• Suppose the inputs to Figure 25 are, A = 0, B = 1, C = 1, and D = 1.
• The procedure is to start from the inputs and to proceed through each
INVERTER and gate, writing down each of their outputs in the process
until the final output is reached.
Figure 25. Logic circuit with its Boolean expression.
29
Boolean Algebra & Combinational Logic Circuits
❑ Implementing Circuits from Boolean Expressions:
• When the operation of a circuit is defined by a Boolean
expression, we can draw a logic-circuit diagram directly.
• Suppose that we want to construct a circuit whose output is ~
y = AC + BC + ABC
• The circuit diagram is shown in Figure 25.
Figure 26. Logic circuit with its Boolean expression. 30
References
1 “Digital Systems: Principles and Applications,” Neal S. Widmer,
Gregory L. Moss, and Ronald J. Tocci, 12th Ed., Pearson (2018).
2 Online Sources.
31
