Module-4
Logic Gates and Boolean algebra: Introduction to Boolean Algebra and Boolean operators,
Symbolic representation, Boolean algebraic function and Truth table of different Digital logic
Gates (AND, OR, NOT, NAND, NOR, EX-OR, EX-NOR); Realization of Basic logic gates using
universal gates, Adder, Subtractor, adder/subtractor.
Ref. Digital logic and Computer Design by M. Morris Mano
Boolean algebra
• Boolean algebra, like any other deductive mathematical system, may be defined with a set of elements, a set
of operators, and a number of unproved axioms or postulates
• A set of elements is any collection of objects having a common property
• If S is a set, and x and y are certain objects, then 𝑥 ∈ 𝑆 denotes that x is an element of the set S, and y ∉ 𝑆
denotes that y is not an element of S.
• A binary operator defined on a set S of elements is a rule that assigns to each pair of elements from S a
unique element from S.
➢ As an example. consider the relation a * b= c. We say that * is a binary operator if it specifies a rule for finding
c from the pair (a, b) and also if a, b, c ∈ S. However, * is not a binary if a, b ∈ S, whereas the rule finds c ∉ 𝑆
• The postulates of a mathematical system form the basic assumptions from which it is possible to deduce
the rules, theorems, and properties of the system. The most common postulates used to formulate
various algebraic structures are
• An example of an algebraic structure is a field. A field is a set of elements, together with two binary operators,
each having properties 1 to 5 and both operators combined to give property 6.
The operators and postulates have the following meanings:
AXIOMATIC DEFINITION OF BOOLEAN ALGEBRA
• Boolean algebra is an algebraic structure defined on a set of elements B together with two binary operators + and .
provided the following (Huntington) postulates are satisfied:
Two-Valued Boolean Algebra
• A two-valued Boolean algebra is defined on a set of two elements, B= {0, 1}, with rules for the two binary
operators + and . as shown in the following operator tables (the rule for the complement operator is for
verification of postulate 5):
These rules are the AND, OR, and NOT operations, respectively,
• We must now show that the Huntington postulates are valid for the set B = {0, 1} and the two binary
operators defined before
BASIC THEOREMS AND PROPERTIES OF BOOLEAN ALGEBRA
Duality
It states that every algebraic expression deducible from the postulates of Boolean algebra
remains valid if the operators and identity elements are inter- changed. In a two-valued
Boolean algebra, the identity elements and the elements of the set B are the same: 1 and 0. The
duality principle has many applications. If the dual of an algebraic expression is desired, we
simply interchange OR and AND operators and replace l's by 0's and 0's by 1's.
Basic Theorems
• The theorems of Boolean algebra can be shown to hold true by means of truth tables. In truth
tables, both sides of the relation are checked to yield identical results for all possible combinations of
variables involved. The following truth table verifies the first absorption theorem
Proof of Theorem 6(a)
The algebraic proofs of the associative law and DeMorgan's theorem using truth Table
BOOLEAN FUNCTIONS
• A binary variable can take the value of 0 or 1. A Boolean function is an expression
formed with binary variables, the two binary operators OR and AND, and unary
operator NOT, parentheses, and an equal sign. For a given value of the variables, the
function can be either 0 or 1. Consider, for example, the Boolean function
The above is an example of a Boolean function represented as an algebraic expression
• A Boolean function may also be represented in a truth table.
➢ To represent a function in a truth table, we need a list of the 2n combinations of 1's and 0's
of the n binary variables, and a column showing the combinations for which the function is
equal to 1 or 0. See the table below
➢ Any Boolean function can be represented in a
truth table. The number of rows in the table is 2n.
where n is the number of binary variables in the
function. The l's and O’s combinations for each
row is easily obtained from the binary numbers by
counting from 0 to 2n -1.
• The question now arises, is it possible to find two algebraic expressions that specify the
same function?
• The answer to this question is yes. As a matter of fact, the manipulation of Boolean algebra is
applied mostly to the problem of finding simpler expressions for the same function. Consider, for
example, the function:
➢ From the Table, we find that F4 is the same as F3,
since both have identical l's and 0’s for each
combination of values of the three binary variables.
➢ In general, two functions of n binary variables are said to
be equal if they have the same value for all possible 2n
combinations of the n variables.
Example:
From Distributive Law
Example
CANONICAL AND STANDARD FORM
Minterms and Maxterms
• A binary variable may appear either in its normal form (x) or in its complement form (x’).
• Now consider two binary variables x and y combined with an AND operation. Since each variable may
appear in either form, there are four possible combinations x’y’, x’y, xy', and xy. Each of these four AND
terms is called a minterm, or a standard product.
• In a similar manner, n variables can be combined to form 2n minterms. The 2n different minterms may be
determined by a method similar to the one shown in Table for three variables.
• The binary numbers from 0 to 2n - I are listed under the n variables.
• Each minterm is obtained from an AND term of the a variables, with each variable being primed if the
corresponding bit of the binary number is a 0 and unprimed if a 1.
• A symbol for each minterm is also shown in the table and is of the form mj. where j denotes the decimal
equivalent of the binary number of the minterm designated.
• ln a similar fashion, n variables forming an OR term, with each variable being primed or unprimed, provide 2n
possible combinations, called maxterms, or standard sums.
• The eight maxterms for three variables, together with their symbolic designation are listed in Table.
• Any 2n maxterms for n variables may be determined similarly.
• Each maxterm is obtained from an OR term of the n variables, with each variable being unprimed if the
corresponding bit is a 0 and primed if a 1.
• Note that each maxterm is the complement of its corresponding minterm, and vice versa
• A Boolean function may be expressed algebraically from a given truth table by forming a minterm for each
combination of the variables that produces a 1 in the function, and then taking the OR of all those terms.
• For example, the function f1 in the below Table is determined by expressing the combinations 001, 100, and 1 11
as x'y'z, xy’z', and xyz. respectively. Since each one of these minterms results in fi = 1, we should have
Sum of Minterms
• It is sometimes convenient to express the Boolean function in its sum of minterms form.
• If not in this form, it can be made so by first expanding the expression into a sum of AND terms.
Each term is then inspected to see if it contains all the variables. If it misses one or more variables,
it is ANDed with an expression such as x + x', where x is one of the missing variables. The following
example clarifies this procedure.
Prob.
The function has three variables, A, B, and C. The first term A is missing two variables; therefore:
This is still missing one variable:
Product of Maxterms
• Each of the 2n functions of n binary variables can be also expressed as a product of maxterms.
• To express the Boolean function as a product of maxterms, it must first be brought into a form of OR terms.
• This may be done by using the distributive law, x+ yz = (x + y)( x + z). Then any missing variable x in each OR term
is ORed with Xx. This pracedure is clarified by the following example.
Example
• The complement missing of a function expressed as the sum of minterms equals the sum of minterms missing
from the original function. This is because the original function is expressed by those minterms that make the
function equal to 1, whereas its complement is a 1 for those minterms that the function is a 0. AS an example,
consider the function
➢ The last conversion follows from the definition of minterms and maxterms. it is clear that the following
relation holds true:
Digital Logic Gates
Logic Gates Implementation Using Universal Gates (NAND/NOR)
Implementation using NAND gates
Implementation using NOR gates
Combinational Logic
• Logic circuits for digital systems may be combinational or sequential.
• A combinational circuit consists of logic gates whose outputs at any time are determined directly from the
present combination of inputs without regard to previous inputs. A combinational circuit performs a specific
information-processing operation fully specified logically by a set of Boolean functions.
• Sequential circuits employ memory elements (binary cells) in addition to logic gates. Their outputs are a
function of the inputs and the state of the memory elements. The state of memory elements, in turn, is a
function of previous inputs. As a consequence, the outputs of a sequential circuit depend not only on present
inputs, but also on past inputs, and the circuit behavior must be specified by a time sequence of inputs and
internal states.
Fig. Block diagram of a combinational circuit
For n input variables there are 2n possible combinations of binary input values, For each possible input combination,
there is one and only one possible output combination. A combinational circuit can be described by m Boolean
functions, one for each output variable. Each output function is expressed in terms of the n input variables.
DESIGN PROCEDURE
1. The problem is stated.
2. The number of available input variables and required output variables is determined.
3. The input and output variables are assigned letter symbols
4. The truth table that defines the required relationships between inputs and outputs is
derived.
5. The simplified Boolean function for each output is obtained.
6. The logic diagram is drawn
ADDERS
• Digital computers perform a variety of information-processing tasks. Among basic functions encountered
are the various arithmetic operations. The most basic arithmetic operation, no doubt, is the addition of two
binary digits.
• This simple addition consists of four possible elementary operations, namely,
0+0 = 0, 0+1 = 1, 1+0 = 1, and 1+1= 10.
The first three operations produces sum whose length is one digit, but when both augend and addend bits
are equal to 1, the binary sum consists of two digits. The higher significant bit of this result is called carry.
• A combinational circuit that performs the addition of two bits is called a half-adder.
• One that performs the addition of three bits (two significant bits and previous carry) is a full-adder.
Half-Adder
• From the verbal explanation of a half-adder, we find that this circuit needs two binary inputs and two
binary outputs. The input variables and designate the augend addend bits; the output variables produce the
sum and carry. It is necessary to specify two output variables because the result may consist of two binary'
digits. We arbitrarily assign symbols x and y to the two inputs and S (for sum) and C (for carry) to the
outputs.
• The simplified Boolean functions for the two output can be obtained directly from truth table. The
simplified sum of products expressions are
Fig. Various implementations of a half-adder
Full-Adder
• A full-adder is a combinational circuit that forms the arithmetic sum of three input bits. It consists of
three inputs and two outputs. Two of the input variables, denoted by x and y, represent the two significant
bits to be added. The third input, z, represents the carry from the previous lower significant position.
The truth table of the full-adder is as follows
Fig, Implementation of full-adder in sum of products
• A full-adder can be implemented with two half-adders and one OR gate, as shown in Fig.
and the carry output is:
Fig. Implementation of a full-adder with two hall-adders and an OR gate
SUBTRACTORS
• The subtraction of two binary numbers may be accomplished by taking the complement of the subtrahend and
adding it to the minuend. By this method, the subtraction operation becomes an addition operation requiring full
adders for its machine implementation.
• It is possible to implement subtraction with logic circuits in a direct manner, as done with paper and pencil. By
this method. each subtrahend bit of the number is subtracted from its corresponding significant minuend bit to
form a difference bit. If the minuend bit is smaller than the subtrahend bit, a l is borrowed from the next
significant position. The fact that a 1 has been borrowed must be conveyed to the next higher pair of bits by
means of a binary signal coming out (output) of a given stage and going into (input) the next higher stage.
• Just as there are half- and full-adders, there are half-and full-subractors,
Half-Subtractor
• A half-subtractor is a combinational circuit that subtracts two bits and produces their difference. It also has an
output to specify if a 1 has been borrowed.
• Designate the minuend bit by x and the subtrahend bit by y
• To perform x – y, we have to check the relative magnitudes of x and y. If x > y, we have three possibilities:
0 - 0 = 0, 1 - 0 = 1, and 1 - 1 = 0. The result is called the difference bit. If x < y, we have 0 - 1, and it is
necessary to borrow a 1 from the next higher stage. The 1 borrowed from the next higher stage adds 2 to
the minuend bit just as in the decimal system a borrow adds 10 to a minuend digit. With the minuend equal
to 2, the difference becomes 2 -1 = 1.
• The truth table for the input-output relationships of a half-subtractor can now be derived as follows
• It is interesting to note that the logic for D is exactly the same as the logic
for output S in the half-adder.
Full-Subtractor
• A full-subtractor is a combinational circuit that performs a subtraction between two bits, taking into account
that a l may have been borrowed by a lower significant stage. This circuit has three inputs and two outputs The
three inputs, x, y, and z, denote the minuend, subtrahend, and previous borrow, respectively. The two
outputs, D and B, represent the difference and output borrow, respectively. The truth table for the circuit is as
follows:
Binary Parallel Adder
Binary Parallel Adder Subtractor
