Digital Logic Circuits

Boolean Algebra & Logic
Circuits
Boolean Algebra
Boolean Algebra is the mathematics we use to analyse digital gates and circuits.
Boolean Algebra is a system of mathematics based on logic that has its own set of rules or laws
which are used to define and reduce Boolean expressions.
Introduction
In the late 1930s, a young M.I.T. graduate student named Claude Shannon noticed an
analogy between the operations of switching devices, such as telephone switching
circuits, and the operations of logical connectives.
Claude Shannon
(1916–2001)
Introduction
Now consider the more complicated circuits
In the circuit of Figure (a) current flows and the light bulb turns on if, and only if, both switches P
and Q are closed. The switches in this circuit are said to be in series.
In the circuit of Figure (b) current flows and the light bulb turns on if, and only if, at least one of
the switches P or Q is closed. The switches in this circuit are said to be in parallel.
Introduction
All possible behaviors of these circuits are described by Table.
Observe that if the words closed and on are replaced by T and open and off are replaced by F, Table(a)
becomes the truth table for and and Table(b) becomes the truth table for or.
Consequently, the switching circuit of Figure(a) is said to correspond to the logical expression
and that of Figure(b) is said to correspond to
Input Output Table
Lists all its possible input signals together with their corresponding output signals.
The third row, for instance, indicates that for inputs P = 1, Q = 0, and R = 1, the output S is 0.
The first row, indicates that for inputs P = 1, Q = 1, and R = 1, the output S is 1.
Logical Circuits
1. A NOT-gate (or inverter)
A circuit with one input signal and one output signal.
If the input signal is 1, the output signal is 0.
Conversely, if the input signal is 0, then the output
signal is 1.
2. An AND-gate
A circuit with two input signals and one output
signal. If both input signals are 1, then the
output signal is 1. Otherwise, the output signal
is 0.
3. An OR-gate
Also has two input signals and one output signal. If
both input signals are 0, then the output signal is 0.
Otherwise, the output signal is 1.
The Input/Output Table for a Circuit
If you are given a set of input signals for a circuit, you can find its output by tracing through the
circuit gate by gate.
Example-1: Determining Output for a Given
Input
Indicate the output of the circuits shown below for the given input signals.
Solution: Example-1
a. Move from left to right through the diagram, tracing the action of each gate on the input
signals. The NOT-gate changes P = 0 to a 1, so both inputs to the AND-gate are 1; hence the
output R is 1. This is illustrated by annotating the diagram as shown below.
b. The output of the OR-gate is 1 since one of the input signals, P, is 1. The NOT-gate changes
this 1 into a 0, so the two inputs to the AND-gate are 0 and R = 1. Hence the output S is 0.
The trace is shown below.
Example-2: Constructing the Input/Output Table for a Circuit
Construct the input/output table for the following circuit.
Solution
List the four possible combinations of input signals, and find the output for each by tracing
through the circuit
The Boolean Expression Corresponding to a Circuit
In logic, variables such as p, q and r represent statements,
and a statement can have one of only two truth values: T
(true) or F (false).
A statement form is an expression, such as , composed of
statement variables and logical connectives.
In honor of one of the founders of symbolic logic, the
English mathematician George Boole, any variable, such
as a statement variable or an input signal, that can take
one of only two values is called a Boolean variable. George Boole
(1815–1864)
An expression composed of Boolean variables and the
connectives and is called a Boolean expression.
Example: Finding a Boolean Expression for a
Circuit
Find the Boolean expressions that correspond to the circuits shown below.
Solution: Example
a. Trace through the circuit from left to right, indicating the output of each gate symbolically, as
shown below
b. The Boolean expression corresponding to the circuit is , as shown below.

Solution: Example
Observe that the output of the circuit shown in Example (b) is 1 for exactly one combination of
inputs (P = 1, Q = 1, and R = 0) and is 0 for all other combinations of inputs.
For this reason, the circuit can be said to “recognize” one particular combination of inputs. The
output column of the input/output table has a 1 in exactly one row and 0’s in all other rows.
A recognizer is a circuit that

outputs a 1 for exactly one
particular combination of
input signals and outputs 0’s
for all other combinations.
The Circuit Corresponding to a Boolean Expression
The preceding examples showed how to find a Boolean expression corresponding to a circuit.
The following example shows how to construct a circuit corresponding to a Boolean expression.
Example: Constructing Circuits for Boolean Expressions

Construct circuits for the following Boolean expressions.
Solution: Example
a. Write the input variables in a column on the left side of the diagram. Then go from the right
side of the diagram to the left, working from the outermost part of the expression to the
innermost part. Since the last operation executed when evaluating ( is ∨, put an OR-gate at
the extreme right of the diagram. One input to this gate is , so draw an AND-gate to the left
of the OR-gate and show its output coming into the OR-gate. Since one input to the AND-
gate is , draw a line from to a NOT-gate and from there to the AND-gate. Since the other
input to the AND-gate is , draw a line from directly to the AND-gate. The other input to the
OR-gate is , so draw a line from Q to a NOT-gate and from the NOT-gate to the OR-gate.
The circuit you obtain is shown below.
Solution: Example
b. To start constructing this circuit, put one AND-gate at the extreme right for the between and . To the left of
that put the AND-gate corresponding to the between and . To the left of that put the AND-gates corresponding
to the ’s between P and Q and between R and S. The circuit is shown below
It follows from Logical Equivalence Laws that all the ways of adding parentheses to are logically equivalent.
Thus, for example,
It also follows that the circuit corresponds to , has the same input/output table as the circuit corresponds to .
Finding a Circuit That Corresponds to a Given Input/Output
Table
We will see how to design a circuit (or find a Boolean expression) corresponding to a given
input/output table.
The way to do this is to put several recognizers together in parallel.
Example: Designing a Circuit for a Given Input/Output Table

Design a circuit for the following input/output table:
Solution: Example
First construct a Boolean expression with this table as its truth table.
To do this, identify each row for which the output is 1—in this case, the first, third, and fourth rows.
For each such row, construct an and expression that produces a 1 (or true) for the exact combination of
input values for that row and a 0 (or false) for all other combinations of input values.
For example, the expression for the first row is because is 1 if and and , and it is 0 for all other values of ,
, and .
The expression for the third row is because is 1 if and and , and it is 0 for all other values of , , and .
Similarly, the expression for the fourth row is .
Now any Boolean expression with the given table as its truth table has the value 1 in case , or in case ,
or in case , and in no other cases.
It follows that a Boolean expression with the given truth table is
Solution: Example
The circuit corresponding to this expression
has the diagram shown in Figure.
Observe that expression (final one) is a
disjunction of terms that are themselves
conjunctions in which one of or , one of
or , and one of or all appear.
Such expressions are said to be in
disjunctive normal form or sum-of-
products form.
Example: Simplifying Combinational
Circuits
Consider the two combinational circuits shown in Figure.
If you trace through circuit (a), you will find that its input/output table is which is the same
as the input/output table for circuit (b).
Thus these two circuits do the same job in the sense that they transform the same
combinations of input signals into the same output signals.
Yet circuit (b) is simpler than circuit (a) in that it contains many fewer logic gates. Thus, as
part of an integrated circuit, it would take less space and require less power.
Equivalent Circuits
Two digital logic circuits are equivalent if, and only if, their input/output tables are identical.
Since logically equivalent statement forms have identical truth tables, you can determine that two
circuits are equivalent by finding the Boolean expressions corresponding to the circuits and
showing that these expressions, regarded as statement forms, are logically equivalent.
Example: Showing That Two Circuits Are Equivalent
Find the Boolean expressions for each circuit in Figure. Use Logical Equivalence Laws to show
that these expressions are logically equivalent when regarded as statement forms.
Solution: Example
The Boolean expressions that correspond to circuits (a) and (b) are ((P∧ ∼Q) ∨ (P ∧ Q)) ∧ Q
and P ∧ Q, respectively. By Logical Equivalence Laws
It follows that the truth tables for and are the same.
Hence the input/output tables for the circuits corresponding to these expressions are also the
same, and so the circuits are equivalent.
Logical Equivalence Laws

Digital Logic Circuits

Uploaded by

Copyright:

Available Formats

Digital Logic Circuits

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Digital Logic Circuits

Uploaded by

Copyright:

Available Formats

Boolean Algebra & Logic

b. The Boolean expression corresponding to the circuit is , as shown below.

A recognizer is a circuit that

Example: Constructing Circuits for Boolean Expressions

Example: Designing a Circuit for a Given Input/Output Table

You might also like