Boolean Algebra and Logic Gates

Introduction

Digital systems process information using discrete signal levels, commonly represented as 0 and 1. These values may correspond to LOW and HIGH voltages, false and true conditions, or inactive and active states. The mathematical system used to describe and manipulate such binary conditions is Boolean algebra. Logic gates are the electronic circuits that implement Boolean operations.

Boolean algebra provides a precise method for simplifying logic expressions, designing digital circuits, constructing truth tables, and verifying circuit behaviour. It is therefore fundamental to computer architecture, networking hardware, embedded systems, memory devices, processors, and control systems.

Learning Objectives

After studying this chapter, you should be able to:

• explain Boolean variables, constants, operators, and expressions;
• apply Boolean laws and identities to simplify expressions;
• use the principle of duality and De Morgan’s theorems;
• construct and interpret truth tables;
• describe AND, OR, NOT, NAND, NOR, XOR, and XNOR gates;
• implement basic functions using universal NAND and NOR gates;
• analyse a logic circuit and derive its Boolean expression;
• select suitable gates for practical digital-system requirements.

1. Boolean Variables and Notation

A Boolean variable can have only one of two values: 0 or 1. A variable is usually represented by a letter such as A, B, or X. The complement or inverse of A is written as A' or overline{A}. It has the opposite value of A.

Three basic operations are used:

• AND, written A·B or simply AB;
• OR, written A+B;
• NOT, written A' or ¬A.

The symbols + and · do not represent ordinary arithmetic addition and multiplication. In Boolean algebra, A+B is 1 if at least one input is 1, while A·B is 1 only when all inputs are 1.

A Boolean expression combines variables and operators. For example,

The expression means that the output F is 1 when A and B are both 1, or when C is 0.

Operator precedence

Unless parentheses are used, operations are normally evaluated in this order:

1. NOT;
2. AND;
3. OR.

Thus, A+B·C' means A+(B·C'). Parentheses should be used whenever they improve clarity.

2. Fundamental Boolean Laws

Boolean laws allow expressions to be transformed without changing their logical function. The variables may represent any Boolean values.

Identity laws

A signal ORed with 0 or ANDed with 1 remains unchanged.

Null or domination laws

OR with 1 always produces 1; AND with 0 always produces 0.

Idempotent laws

Repeating the same condition does not alter its value.

Complement laws

A condition and its complement cannot both be true, and one of them must be true.

Involution law

Complementing a variable twice restores the original value.

Commutative laws

The order of operands does not matter for AND or OR.

Associative laws

Grouping does not matter when only one type of operation is involved.

Distributive laws

Boolean algebra has two distributive laws:

The second law differs from ordinary arithmetic and is particularly useful in logic simplification.

Absorption laws

For example, if A is already true, the additional condition A·B cannot change the result of A + A·B.

Combining or consensus-related identities

Useful derived identities include:

These can be verified by distributive, complement, and identity laws.

3. Principle of Duality

The principle of duality states that a valid Boolean identity remains valid when AND and OR are interchanged and 0 and 1 are interchanged. Variables and complements remain unchanged.

For example, the identity

has the dual form

Similarly, the dual of

is

Duality is not a separate simplification law; it is a method for generating or checking related identities.

4. De Morgan’s Theorems

De Morgan’s theorems describe how complementation affects grouped expressions:

and

In words:

• the complement of an AND is the OR of the complements;
• the complement of an OR is the AND of the complements.

For three variables, the laws become:

These theorems are central to NAND and NOR implementation. They also help engineers convert active-high logic into active-low logic and simplify circuits containing inverted outputs.

Worked example 1: Applying De Morgan’s theorem

Simplify F=(A+B)'. Applying the second theorem gives:

Thus, F is 1 only when both A and B are 0.

Worked example 2: Algebraic simplification

Simplify:

Factor A:

Using the complement law:

The original circuit can therefore be replaced by a direct connection from A, provided loading and electrical design constraints permit it.

5. Truth Tables

A truth table lists every possible input combination and the corresponding output. For n independent binary inputs, the number of rows is:

Here, n is the number of input variables. The formula assumes that each input can independently take either 0 or 1.

For two inputs, there are 2²=4 combinations. For three inputs, there are 2³=8.

Truth tables are used to define gates, verify algebraic expressions, test designs, and compare circuits for functional equivalence.

6. Basic Logic Gates

NOT gate

A NOT gate has one input and produces its complement.

AND gate

The output of an AND gate is 1 only when every input is 1.

AND logic models conditions that must all be satisfied, such as “card valid AND password correct.”

OR gate

The output of an OR gate is 1 when at least one input is 1.

OR logic models alternatives, such as “sensor 1 active OR sensor 2 active.”

NAND gate

A NAND gate is an AND gate followed by NOT:

NOR gate

A NOR gate is an OR gate followed by NOT:

XOR gate

The exclusive-OR gate produces 1 when the inputs are different:

XOR is used in binary addition, parity generation, error detection, and comparison of changing states.

XNOR gate

XNOR is the complement of XOR and produces 1 when the inputs are equal:

XNOR is useful for equality comparison and agreement detection.

7. Universal Gates

A universal gate can be used alone to implement any Boolean function. NAND and NOR are universal gates.

Implementing NOT with NAND

Connect both inputs of a NAND gate to A:

Implementing AND with NAND

First produce (A·B)', then invert it using a second NAND gate:

Implementing OR with NAND

By De Morgan’s theorem:

Therefore, invert A and B with NAND gates and feed the results into a third NAND gate.

Implementing NOT with NOR

Connect both inputs of a NOR gate to A:

Implementing OR with NOR

Invert the NOR output:

Implementing AND with NOR

Using De Morgan’s theorem:

Thus, invert both inputs with NOR gates and apply them to a third NOR gate.

Universal-gate design may reduce the number of different integrated-circuit types required, simplifying procurement and maintenance. However, gate count, propagation delay, power consumption, and wiring complexity must also be considered.

8. Deriving and Simplifying Logic Functions

A circuit can be analysed from its input toward its output. The output of each intermediate gate is assigned a temporary variable, and the final expression is formed from these variables.

Worked example 3: Circuit expression

Suppose two inputs A and B enter an AND gate, while C enters a NOT gate. The two resulting signals enter an OR gate. The output is:

The output is 1 if A and B are both 1, or if C is 0.

Worked example 4: Functional verification

Consider:

By absorption:

A truth-table check confirms this result:

The two output columns are identical for every input combination, proving functional equivalence.

9. Applied Case: Access-Control Interlock

Background

Consider an equipment room whose door should unlock only when an authorised card is detected and a supervisor enables access. For safety, an emergency-lock signal must prevent unlocking under all conditions.

Problem

Let A represent an authorised card, S represent supervisor approval, and E represent emergency lock active. The unlock output U must be 1 only when A and S are 1 and E is 0.

Analysis and solution

The Boolean function is:

The design requires an AND gate for A and S, a NOT gate for E, and a three-input AND gate. An equivalent NAND-only implementation can be created by replacing the inversion and AND operations with NAND configurations.

Outcome

The circuit prevents access if the card is invalid, approval is absent, or emergency lock is active. The design should be tested for all eight input combinations because there are 2³=8 possible states.

Learning points

This example demonstrates that Boolean expressions can translate operational requirements into hardware. It also shows why signal definitions must be explicit: confusing “emergency active” with “safe condition” would invert the intended behaviour.

10. Practical Design Considerations

Boolean correctness is necessary but not sufficient for a reliable physical circuit.

• Propagation delay: a gate requires finite time to respond to an input change. Cascaded gates increase total delay.
• Fan-in: a gate may support only a limited number of inputs.
• Fan-out: one output may drive only a specified number of subsequent inputs.
• Logic-level compatibility: voltage thresholds must be compatible between devices.
• Power consumption: unnecessary gates increase static or dynamic power.
• Hazards and glitches: unequal path delays can produce temporary incorrect pulses.
• Active-low signals: a bar, overline, or bubble often indicates that 0 represents the asserted condition.
• Testing: truth tables, simulation, and hardware measurements should be used together.

In safety-related systems, a Boolean expression should be reviewed independently, tested against abnormal conditions, and documented with unambiguous signal names. Logic simplification must never remove a condition that is required for safety, security, or regulatory compliance.

Chapter Summary

Boolean algebra is the mathematical foundation for representing and simplifying digital logic. Boolean variables take the values 0 and 1, while NOT, AND, and OR form the basic operations. Identity, complement, distributive, associative, commutative, absorption, and related laws permit equivalent expressions to be derived. The principle of duality exchanges AND with OR and 0 with 1. De Morgan’s theorems explain how complements distribute across AND and OR and are essential for NAND and NOR designs.

Truth tables enumerate all possible input combinations and provide a direct method for defining and verifying logic functions. AND, OR, NOT, NAND, NOR, XOR, and XNOR gates implement common Boolean operations. NAND and NOR are universal gates because either type alone can implement NOT, AND, OR, and therefore any Boolean function. Practical design additionally requires attention to delay, fan-out, voltage levels, power, hazards, testing, and safety.

Key Terms

Boolean algebra: Algebra for variables restricted to 0 and 1.

Boolean variable: A variable that can have the value 0 or 1.

Complement: The inverse of a Boolean value or expression.

AND: Operation producing 1 only when all inputs are 1.

OR: Operation producing 1 when at least one input is 1.

NOT: Unary operation that complements an input.

Truth table: Table listing input combinations and corresponding outputs.

Logic gate: Electronic circuit implementing a Boolean operation.

NAND: Complement of the AND operation.

NOR: Complement of the OR operation.

XOR: Operation producing 1 when inputs differ.

XNOR: Operation producing 1 when inputs are equal.

Duality: Principle interchanging AND with OR and 0 with 1.

De Morgan’s theorems: Rules for complementing grouped AND and OR expressions.

Universal gate: Gate type capable of implementing any Boolean function by itself.

Absorption: Simplification law such as A+A·B=A.

Fan-in: Number of inputs accepted by a gate.

Fan-out: Number of gate inputs driven by one output.

Propagation delay: Time between an input change and the corresponding output change.

Logic hazard: Temporary unwanted output caused by unequal circuit delays.

Review Questions

Short Answer Questions

1. What is a Boolean variable?
2. State the two De Morgan’s theorems.
3. What is the difference between XOR and OR?
4. Why are NAND and NOR called universal gates?
5. How many rows are required for a truth table with four independent inputs?

Long Answer Questions

1. Explain the fundamental Boolean laws with suitable examples.
2. Describe the operation and applications of AND, OR, NOT, NAND, NOR, XOR, and XNOR gates.
3. Explain the principle of duality and show how it generates related Boolean identities.
4. Describe how NAND gates can be used to implement NOT, AND, and OR functions.
5. Explain the practical limitations that must be considered when implementing a Boolean expression in hardware.

Analytical / Application Questions

1. Simplify F=A·B+A·B'+A·C. Show each Boolean step and explain the resulting circuit.
2. Design a logic function for an alarm that activates when a door is open and either motion is detected or the system is armed. Define variables and write the Boolean expression.
3. A control output is defined as Y=(A+B)·C'. Construct its truth table and identify all input combinations for which Y is 1.

Multiple Choice Questions with Answers

Question 1

Which Boolean identity is represented by A+A·B=A?

A. Identity law

B. Absorption law

C. Complement law

D. Associative law

Correct Answer: B. Absorption law

Question 2

How many rows are required for a truth table with three independent inputs?

A. 3

B. 6

C. 8

D. 9

Correct Answer: C. 8

Question 3

What is the output of an AND gate when its inputs are 1 and 0?

A. 0

B. 1

C. Undefined

D. Depends on gate order

Correct Answer: A. 0

Question 4

Which expression is equivalent to (A+B)'?

A. A'+B'

B. A'·B'

C. A·B

D. A+B

Correct Answer: B. A'·B'

Question 5

An XOR gate produces 1 when its two inputs are:

A. Both 0

B. Both 1

C. Different

D. Always identical

Correct Answer: C. Different

Question 6

Which gates are universal gates?

A. AND and OR

B. XOR and XNOR

C. NOT and AND

D. NAND and NOR

Correct Answer: D. NAND and NOR

Question 7

Simplify A·(B+B').

A. 0

B. 1

C. A

D. B

Correct Answer: C. A

Question 8

What is the output of a NOR gate for inputs A = 0 and B = 0?

A. 0

B. 1

C. A

D. B'

Correct Answer: B. 1

Question 9

Which gate is commonly used to detect equality between two binary inputs?

A. XNOR

B. NAND

C. OR

D. NOT

Correct Answer: A. XNOR

Question 10

If F=A·B+C', under which condition is F certainly 1?

A. A = 0, B = 0, C = 1

B. A = 1, B = 0, C = 1

C. A = 1, B = 1, C = 0

D. A = 0, B = 1, C = 1

Correct Answer: C. A = 1, B = 1, C = 0