Unit-2 Boolean Algebra and Logic Gates

Introduction
- In 1854 George Boole introduced a systematic treatment of logic and developed for this
purpose an algebraic system known as symbolic logic, or Boolean algebra.
- Boolean algebra is a branch of mathematics and it can be used to describe the
manipulation and processing of binary information. The two-valued Boolean algebra has
important application in the design of modern computing systems.

Boolean Algebra
- Boolean algebra is algebra for the manipulation of objects that can take on only two
values, typically true and false.
- It is common to interpret the digital value 0 as false and the digital value 1 as true.
- A two-valued Boolean algebra is defined on a set of 2 elements B = {0, 1} with 3 binary
operators OR (+), AND ( • ), and NOT ( ' ).

Basic Theorem and Properties of Boolean Algebra

Duality Principle
It states that “Every algebraic expression deducible from the postulates of Boolean algebra
remains valid if the operators and identity elements are interchanged”. In a two-valued
Boolean algebra, the identity elements and the elements of the set B are the same: 1 and 0. If
the dual of an algebraic expression is desired, we simply interchange OR and AND operators
and replace 1's by 0's and 0's by 1's.
E.g. 𝑋 ∙ 𝑌 + 𝑍′ = (𝑋′ + 𝑌′) ∙ 𝑍
De-Morgan's Theorem
De Morgan’s theorem is used to convert OR type of expression into AND type and vice-versa.
It is further divided into two different types;
1st law:
It state that the total complement of sum is equal to the product of individual complement.
i.e. (A+B)’=A’ ٠B’

Proof:
Input Output
A B (A+B)’ A’ ٠B’
0 0 1 1
0 1 0 0
1 0 0 0
1 1 0 0

2nd law:
It state that the total complement of the product is equal to the sum of individual complement.
i.e. (A٠B)’ =A’+B’

Proof:
Input Output
A B (A٠B)’ A’+B’
0 0 1 1
0 1 1 1
1 0 1 1
1 1 0 0

Boolean Function
A binary variable can take a value of 0 or, 1. A Boolean function is an expression formed
with binary variables, the two binary operators OR and AND, unary operator NOT,
parenthesis and an equal sign. For a given value of variables, the function either can 0 or 1.
E.g.
𝐹1 = 𝑥𝑦𝑧′
𝐹 2 = 𝑥 + 𝑦 ′𝑧
𝐹3 = 𝑥′𝑦′𝑧 + 𝑥′𝑦𝑧 + 𝑥𝑦′
𝐹4 = 𝑥𝑦′ + 𝑥′𝑧

Truth Table of Boolean functions:

A truth table shows the relationship, in tabular form, between the input values and
the result of a specific Boolean operator or function on the input variables.
Here, F3 and F4 are same. Two functions of 𝑛 binary variables are said to be equal if they
have same values for all possible 2n combinations of the 𝑛 variables.

Algebraic Manipulation
When a Boolean function is implemented with logic gates, each literal in the function
designates an input to a gate and each term is implemented with a gate. The minimization of
the number of literals and the number of terms results is a circuit with less equipment.

Q. Simplify the following Boolean functions to a minimum number of literals.

1. 𝑥(𝑥′ + 𝑦)
= 𝑥𝑥′ + 𝑥𝑦
= 0 + 𝑥𝑦
= 𝑥𝑦

2. 𝑥 + 𝑥′𝑦
= (𝑥 + 𝑥′)(𝑥 + 𝑦)
= 1(𝑥 + 𝑦)
=𝑥+𝑦

3. (𝑥 + 𝑦)(𝑥 + 𝑦′)
= 𝑥 + 𝑥𝑦 + 𝑥𝑦′ + 𝑦𝑦′
= 𝑥(1 + 𝑦 + 𝑦′)
=𝑥

4. 𝑥𝑦 + 𝑥′𝑧 + 𝑦𝑧
= 𝑥𝑦 + 𝑥′𝑧 + 𝑦𝑧(𝑥 + 𝑥′)
= 𝑥𝑦 + 𝑥′𝑧 + 𝑥𝑦𝑧 + 𝑥′𝑦𝑧
= 𝑥𝑦(1 + 𝑧) + 𝑥′𝑧(1 + 𝑦)
= 𝑥𝑦 + 𝑥′𝑧
Q. Prove that: (𝒙 + 𝒚)(̅𝒙 + 𝒚) = 𝒚
Soln:

Note: To prove the equality of two Boolean expressions, you can also create the truth tables
for each and compare. If the truth tables are identical, the expressions are equal.

Q. Prove the Boolean expression: 𝑨𝑩 + 𝑨𝑩′𝑪 + 𝑨′𝑩𝑪 = 𝑨𝑩 + 𝑨𝑪 + 𝑩𝑪

Soln:
𝐴𝐵 + 𝐴𝐵′𝐶 + 𝐴′𝐵𝐶
= 𝐴(𝐵 + 𝐵′𝐶) + 𝐴′𝐵𝐶
= 𝐴(𝐵 + 𝐶) + 𝐴′𝐵𝐶 [∴ 𝐴 + 𝐴′𝐵 = 𝐴 + 𝐵]
= 𝐴𝐵 + 𝐴𝐶 + 𝐴′𝐵𝐶
= 𝐴𝐵 + (𝐴 + 𝐴′𝐵)𝐶
= 𝐴𝐵 + (𝐴 + 𝐵)𝐶
= 𝐴𝐵 + 𝐴𝐶 + 𝐵𝐶

̅ + 𝑩𝑪 using theorem and properties of Boolean

Q. Minimize the expression: 𝑨𝑩 + 𝑨𝑪
Algebra.

Soln:

̅
Complement of a function
The complement of a function 𝐹 is 𝐹′ and is obtained from an interchange of 0’s for 1’s and
1’s for 0’s in the value of 𝐹. The complement of a function may be derived algebraically
through De Morgan’s theorem.

Generalized theorems for finding complement:

Q. Find the Complement of the functions 𝑭𝟏 = 𝒙′𝒚𝒛′ + 𝒙′𝒚′𝒛 and 𝑭𝟐 = 𝒙(𝒚′𝒛′ + 𝒚𝒛).
Soln:
By applying DeMorgan’s theorem as many times as necessary, the complements are obtained
as follows:
Logic Gates
- A logic gate is an electronic device that produces a result based on one or more input
values.
- In reality, gates consist of one to six transistors, but digital designers think of them as a
single unit.
- Integrated circuits contain collections of gates suited to a particular purpose.
Logic gate can be categories as follows:
1. Basic Gate
a. NOT gate
A NOT gate accepts one input value and produces one output value.

Fig: Various representations of a NOT gate

By definition, if the input value for a NOT gate is 0, the output value is 1, and if the
input value is 1, the output is 0.
b. AND gate
An AND gate accepts two input signals. If the two input values for an AND gate are
both 1, the output is 1; otherwise, the output is 0.

Fig: Various representations of a AND gate

c. OR gate
If the two input values are both 0, the output value is 0; otherwise, the output is 1.

Fig: Various representations of a OR gate

2. Universal Gate

a. NAND gate
NAND gate is the combination of NOT gate and AND gate. If the two input values
for an NAND gate are both 1, the output is 0; otherwise, the output is 1.

Fig: Various representations of a NAND gate

b. NOR gate
NOR gate is the combination of NOT gate and OR gate. If the two input values for
NOR gate are both 0, the output value is 1; otherwise, the output is 0.

Fig: Various representations of a NOR gate

3. Derived/Extended Gate

a. Exclusive-OR gate (XOR)

An XOR gate produces 0 if its two inputs are the same, and a 1 otherwise.

= 𝐴𝐵′ + 𝐴′𝐵

Fig: Various representations of a XOR gate

b. Exclusive-NOR gate (X-NOR)

X-NOR is the complement of X-OR. An X-NOR gate produces 1 if its two inputs are
the same, and a 0 otherwise.
 = 𝐴⨀𝐵

Fig: Various representations of a X-NOR gate

Buffer Gate
The buffer gate returns the same output as same as that of input.

Universal Gate Realization

A universal gate is a gate which can implement any Boolean function without need to use any
other gate type. The NAND and NOR gates are universal gates.

1. NAND gate as a Universal Gate

To prove that any Boolean function can be implemented using only NAND gates, we
will show that the AND, OR, and NOT operations can be performed using only these
gates.

Fig: Three Circuits Constructed Using Only NAND Gates

Thus, the NAND gate is a universal gate since it can implement the AND, OR and NOT
functions.
 2. NOR gate as a Universal Gate
To prove that any Boolean function can be implemented using only NOR gates, we
will show that the AND, OR, and NOT operations can be performed using only these
gates.

Fig: Three Circuits Constructed Using Only NOR Gates

Thus, the NOR gate is a universal gate since it can implement the AND, OR and NOT
functions.

Gates with More Inputs

- Gates can be designed to accept three or more input values
- A three-input AND gate, for example, produces an output of 1 only if all input values are 1.

Fig: Various representations of a three input AND gate

Implementation of Boolean function using gates
𝐹1 = 𝑥𝑦𝑧′
𝐹 2 = 𝑥 + 𝑦 ′𝑧
𝐹3 = 𝑥′𝑦′𝑧 + 𝑥′𝑦𝑧 + 𝑥𝑦′

Q. Draw a logic gates that implements the following:

a. F = AB + C D' + B' C
b. F = (A + B) (B' + C) (C' + D + E)
n
Sol :
a.
b.

Integrated Circuits (ICs)

An Integrated circuit is an association (or connection) of various electronic devices such as
resistors, capacitors and transistors etched (or fabricated) to a semiconductor material such as
silicon or germanium. It is also called as a chip or microchip. An IC can function as an
amplifier, rectifier, oscillator, counter, timer and memory. Sometime ICs are connected to
various other systems to perform complex functions.
ICs can be categorized into two types
- Analog or Linear ICs
- Digital or logic ICs
Further there are certain ICs which can perform as a combination of both analog and digital
functions.
Analog or Linear ICs : They produce continuous output depending on the input signal.
From the name of the IC we can deduce that the output is a linear function of the input signal.
Op-amp (operational amplifier) is one of the types of linear ICs which are used in amplifiers,
timers and counters, oscillators etc.
Digital or Logic ICs : Unlike Analog ICs, Digital ICs never give a continuous output signal.
Instead it operates only during defined states. Digital ICs are used mostly in microprocessor
and various memory applications. Logic gates are the building blocks of Digital ICs which
operate either at 0 or 1.

Levels of Integration:
Small Scale Integration (SSI) devices contain several independent gates in a single package.
The inputs and outputs of the gates are connected directly to the pins in the package. The
number of gates is usually fewer than 10 and is limited by number of pins available in the IC.

Medium-scale integration (MSI) devices have a complexity of approximately 10 to 100

gates in a single package. They usually perform specific elementary digital operations such as
decoders, adders or multiplexers.
Large-scale integration (LSI) devices contain between 100 and a few thousand gates in a
single package. They include digital systems such as processor, memory chips and
programmable logic devices.

Very large-scale integration (VLSI) devices contain thousands of gates within a single
package. Examples are large memory arrays and complex microcomputer chips. Because of
their small size and low cost, VLSI devices have revolutionized the computer system design
technology, giving the designer the capabilities to create structures that previously were
uneconomical.

IC digital Logic Families

Many different logic families of digital IC’s have been introduced commercially.
TTL Transistor-transistor logic.
ECL Emitter-coupled logic.
MOS Metal-oxide semiconductor
CMOS Complementary metal-oxide semiconductor.
I2C Integrated-injection logic
 TTL has extensive list of digital functions and currently the most popular logic
family.
 ECL is used in systems requiring high-speed operations.
 MOS and I2C are used in circuits requiring high component density and
 CMOS is used in systems requiring low power consumption.

Positive and Negative Logic

The binary signal at the inputs and outputs of any gate has one of two values, except during
transition. One signal value represents logic-1 and the other logic-0. So there is a possibility
of two different assignments of signal level to logic value, as shown in Fig.

Positive logic: H = 1; L = 0
Negative Logic: H = 0; L = 1
 Fig: Demonstration of positive and negative logic
Special Characteristics
The characteristics that describe the performance of IC digital logic families are: Fan-out,
power dissipation, propagation delay and noise margin.
- Fan-out specifies the number of standard loads that the output of a gate can drive without
impairing its normal operation. A standard load is usually defined as the amount of
current needed by an input of another logic gate in the same IC family. Sometimes the
term loading is used instead of fan-out. This term is derived from the fact that the output
pin of a gate can supply limited current, above which it ceases to operate properly and is
said to be overloaded.

- Power dissipation is the supplied power required to operate the gate. This parameter is
expressed in milliwatts (mW) and represents the actual power dissipated in the gate.

- Propagation delay is the average transition delay time for a signal to propagate from
input to output when the binary signals change in value. Propagation delay is expressed in
nanoseconds (ns).

- Noise margin is the maximum noise voltage added to the input signal of a digital circuit
that does not cause an undesirable change in the circuit output. There are two types of
noise to be considered. DC noise is caused by a drift in the voltage level of a signal. AC
noise is a random pulse that may be created by other switching signals. Noise margin is
expressed in volts (V) and represent the maximum noise signal that can be tolerated by
the gate.
Typical characteristics of IC logic family