Boolean Algebra and Digital Logic

Introduction

Boolean algebra is the mathematics of reasoning with two-valued variables. Its values are usually written as 0 and 1, representing alternatives such as false/true, off/on, low/high, or reject/accept. Although Boolean algebra was developed by George Boole as a theory of logic, it is now fundamental to digital electronics, computer architecture, programming-language conditions, database queries, search systems, and rule-based artificial intelligence.

A digital circuit processes binary inputs and produces binary outputs. The same computation can be described in several equivalent ways: a verbal rule, a truth table, a Boolean expression, a logic-gate network, or a program condition. The ability to move between these representations is an important skill in computer applications. Boolean simplification reduces the number of gates or software tests required, while canonical forms and Karnaugh maps provide systematic design methods.

This chapter develops Boolean laws, truth tables, canonical representations, logic minimization, combinational circuits, and an introduction to sequential logic. It also explains practical limitations: real circuits have propagation delays, physical costs, hazards, and power requirements, even when their Boolean expressions appear equivalent.

Learning Objectives

After completing this chapter, a student should be able to:

1. Explain Boolean variables, constants, operators, logic gates, and truth tables.
2. Apply Boolean identities and De Morgan’s laws to simplify expressions.
3. Convert between truth tables, Boolean expressions, and logic circuits.
4. Construct minterm and maxterm canonical forms.
5. Minimize suitable expressions using Karnaugh maps.
6. Analyze common combinational circuits such as adders, multiplexers, and decoders.
7. Distinguish combinational logic from sequential logic and explain the role of memory.
8. Relate digital logic to software conditions, databases, and rule-based systems.
9. Evaluate design trade-offs involving cost, delay, hazards, testing, and reliability.

1. Boolean Variables and Operators

A Boolean variable takes one of two values: 0 or 1. A Boolean function maps one or more Boolean inputs to a Boolean output. For n independent inputs, there are 2ⁿ possible input combinations.

The three basic operations are:

• NOT, written A′ or ¬A, reverses the value of A.
• AND, written A·B or AB, is 1 only when both inputs are 1.
• OR, written A + B, is 1 when at least one input is 1.

The symbols + and · are logical operators in this context, not ordinary arithmetic addition and multiplication. For example, 1 + 1 = 1 in Boolean algebra because OR of two true values remains true.

The precedence convention is NOT first, AND second, and OR third. Thus A + BC′ means A + (B·(C′)). Parentheses should be used when there is any possibility of confusion.

A truth table lists every possible input combination and the corresponding output. It is a complete specification of a Boolean function, although it may become large: a function of 10 variables requires 2¹⁰ = 1,024 rows.

2. Fundamental Boolean Laws

Boolean identities permit expressions to be transformed without changing their output. The most important laws are shown below.

The second distributive law is particularly different from ordinary algebra. In Boolean algebra, A + BC = (A+B)(A+C). It can be verified by a truth table or by applying the first distributive law and complement identities.

De Morgan’s Laws

De Morgan’s laws connect complementation with AND and OR:

For several variables, complementation changes every AND to OR and every OR to AND, while complementing each variable. For example:

These laws are useful when implementing a circuit using only NAND gates or only NOR gates. A NAND gate is the complement of AND, while a NOR gate is the complement of OR.

Worked Example 1: Algebraic Simplification

Simplify F = A + A′B.

Using the distributive identity in the form X + YZ = (X+Y)(X+Z):

F = (A + A′)(A + B)

By the complement law, A + A′ = 1:

F = 1(A+B) = A+B.

Therefore, the simplified expression is F = A + B. The original expression requires an inverter, an AND operation, and an OR operation; the simplified expression requires only an OR operation.

Worked Example 2: Absorption

Simplify F = AB + AB′.

Factor A:

F = A(B+B′) = A·1 = A.

This result illustrates why algebraic simplification can reduce both hardware and computational work.

3. Logic Gates and Equivalent Representations

A gate is a physical or simulated device implementing a Boolean operation. The principal gates are NOT, AND, OR, NAND, NOR, XOR, and XNOR.

XOR, or exclusive OR, is 1 when its inputs differ:

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

NAND and NOR are universal gates: any Boolean function can be constructed using only NAND gates or only NOR gates. This property is important in integrated-circuit design because using one standard gate type may simplify manufacturing and layout.

A Boolean expression, truth table, and gate circuit are three representations of the same logical function. A designer commonly moves from a problem statement to a truth table, from the truth table to an expression, and from the expression to a minimized circuit.

4. Standard and Canonical Forms

A product term is an AND of literals, where a literal is a variable or its complement. For example, AB′C is a product term. A sum term is an OR of literals, such as A+B′+C.

A sum-of-products (SOP) expression is an OR of product terms:

A product-of-sums (POS) expression is an AND of sum terms:

A canonical SOP contains a minterm for every truth-table row in which F = 1. A minterm contains every variable exactly once. For variables A, B, and C, the row A=0, B=1, C=0 corresponds to A′BC′. It is often denoted m₂ because the binary pattern 010 equals decimal 2.

A canonical POS contains a maxterm for every row in which F = 0. A maxterm also contains every variable exactly once, but a variable appears uncomplemented when its row value is 0 and complemented when its row value is 1. The row 010 therefore corresponds to the maxterm (A + B′ + C).

For a function of three variables:

means that F is 1 at minterm indices 1, 3, 5, and 7. Equivalently, the function is 0 at indices 0, 2, 4, and 6, so it can be written:

The notation assumes a stated variable order, here A as the most significant variable and C as the least significant variable.

Obtaining Canonical SOP from a Truth Table

1. Identify each row for which F = 1.
2. Write a minterm for that row.
3. OR all minterms together.

Obtaining Canonical POS from a Truth Table

1. Identify each row for which F = 0.
2. Write a maxterm for that row.
3. AND all maxterms together.

Canonical forms are systematic but often inefficient. A three-variable function may require several three-literal terms even when a much shorter expression exists. Minimization addresses this problem.

5. Karnaugh Maps

A Karnaugh map, or K-map, is a visual method for minimizing Boolean expressions. Its cells represent minterms arranged in Gray-code order, so adjacent cells differ in exactly one variable. Adjacency also wraps around edges: the left and right boundaries are adjacent, as are the top and bottom boundaries.

For a two-variable function, the map has four cells. A three-variable map has eight cells, commonly arranged with one variable on the rows and two variables on the columns. A four-variable map has 16 cells.

K-map Grouping Rules

• Place 1s in cells corresponding to the function’s minterms for SOP minimization.
• Group adjacent 1s in rectangles containing 1, 2, 4, 8, or 16 cells.
• Groups must contain a power of two cells.
• Groups may overlap when this produces a simpler result.
• Every 1 must be covered at least once.
• Make groups as large as possible, because each doubling removes one literal.
• Groups may wrap around map edges.
• A variable that changes within a group is eliminated; a variable that remains constant is retained.

For POS minimization, group 0s instead. The resulting terms are sum terms rather than product terms.

Worked Example 3: Three-Variable K-map

Consider:

The binary indices are 001, 011, 101, and 111. In every selected row, C = 1, while A and B vary. These four adjacent cells form one group. Since only C remains constant:

This is much simpler than the canonical expression A′B′C + A′BC + AB′C + ABC.

Don’t-Care Conditions

Some input combinations may never occur or may have no required output. These are marked X and called don’t-care conditions. During minimization, an X may be treated as either 0 or 1 if doing so creates a larger useful group. It need not be included if it does not help.

Don’t-care conditions must be justified by the application. Treating an actually possible and safety-critical state as a don’t-care can produce an unsafe circuit.

6. Combinational Logic Design

A combinational circuit’s output depends only on its current inputs. It has no internal memory. Examples include arithmetic units, decoders, encoders, multiplexers, comparators, and code converters.

Half Adder

A half adder adds two one-bit inputs A and B. Its outputs are sum S and carry C:

The XOR is 1 when exactly one input is 1; the AND produces a carry when both inputs are 1.

Full Adder

A full adder adds A, B, and an incoming carry Cᵢₙ. It produces a sum S and outgoing carry Cₒᵤₜ:

An equivalent expression is Cₒᵤₜ = AB + ACᵢₙ + BCᵢₙ. A chain of full adders can add multi-bit binary numbers, although the carry must propagate from one position to the next.

Multiplexer

A multiplexer selects one of several data inputs and forwards it to a single output. A 2-to-1 multiplexer with data inputs D₀ and D₁ and select input S has:

When S=0, Y=D₀; when S=1, Y=D₁. Multiplexers are used in processors, communication systems, and software-controlled data paths.

Decoder

A decoder converts n input bits into up to 2ⁿ mutually exclusive output lines. A 2-to-4 decoder activates one output for each input combination. Decoders are used in memory addressing, instruction interpretation, and display control.

7. Sequential Logic and Memory

A sequential circuit’s output depends on current inputs and stored state. The general conceptual model is:

The state is commonly stored in latches or flip-flops. A clock coordinates state changes in synchronous systems.

A latch is level-sensitive: it may respond throughout an active level of an enable signal. A flip-flop is commonly edge-triggered: it samples input at a specified clock edge. A D flip-flop stores one data bit. Ideally, at the active edge:

The equation describes logical behavior, not unlimited physical speed. Setup time is the minimum interval that D must be stable before the clock edge; hold time is the minimum interval it must remain stable after the edge. Violating these requirements can cause metastability, in which the output takes an unpredictable time to settle.

A finite-state machine (FSM) models sequential behavior using a finite set of states, input-dependent transitions, and outputs. Moore-machine outputs depend only on state; Mealy-machine outputs depend on state and current input. FSMs are widely used in vending machines, communication protocols, user-interface controllers, and workflow software.

8. Hazards, Delay, and Practical Design

Boolean equivalence does not guarantee identical physical behavior. Gates have propagation delay: the output changes after a finite time following an input change. If different paths have different delays, a circuit can produce a brief unwanted pulse called a glitch or hazard.

A static-1 hazard occurs when an output that should remain 1 temporarily falls to 0. A common remedy in two-level SOP logic is to add a redundant consensus term, provided it does not alter the steady-state function. For example, carefully analyzing adjacent implicants may show that an additional covering term prevents a gap during a transition.

Other practical concerns include:

• fan-in: the number of inputs a gate can accept;
• fan-out: the number of gate inputs driven by an output;
• propagation delay and maximum operating frequency;
• power consumption and heat;
• noise margins and signal integrity;
• testability and fault coverage;
• physical area and manufacturing cost.

A minimized expression is not always the best implementation. A slightly larger circuit may be faster, safer, easier to test, or less vulnerable to hazards. In software, excessive Boolean compression can likewise reduce readability and increase maintenance risk.

9. Boolean Logic in Software and Information Systems

Programming conditions use the same logical concepts. For example, a policy may state:

“Approve a transaction if the account is active AND the amount is below a limit AND either multi-factor authentication succeeds OR the transaction is from a trusted device.”

This can be represented as:

In many programming languages, AND is written &&, OR as ||, and NOT as !. The logical meaning is similar, but programming languages may use short-circuit evaluation. In an expression P && Q, Q may not be evaluated if P is false. This is operationally different from a physical gate network, where signals propagate through all connected gates.

Boolean algebra also appears in SQL WHERE clauses, access-control rules, spreadsheet formulas, search filters, and expert systems. De Morgan’s laws help convert exclusions into positive conditions. For instance, “not (employee is inactive or account is suspended)” becomes “employee is active and account is not suspended.”

Security decisions require particular care. A minimized or rewritten condition must preserve policy meaning, including treatment of missing, unknown, or null values. Classical Boolean algebra assumes only 0 and 1, whereas SQL commonly uses three-valued logic: TRUE, FALSE, and UNKNOWN. Therefore, algebraic transformations that are valid in two-valued logic should be tested before being applied to database predicates.

10. Applied Case: Access-Control Controller

Background

The following is an illustrative case. A university laboratory wants an electronic door controller for authorized users. The door may unlock when the system is powered, the user’s credential is valid, and either the laboratory is in normal operating hours or an approved supervisor override is active. A fire alarm must prevent unlocking.

Let P represent power available, V represent valid credential, H represent permitted hours, O represent supervisor override, and F represent fire alarm active. The unlock function is:

Problem Analysis

The expression captures the policy directly. Every required safety condition is an AND factor. The alternatives H and O are grouped by OR. The fire alarm is complemented because unlocking is allowed only when F=0.

A truth table could be constructed with 2⁵ = 32 rows, but the factored expression is more readable than a fully expanded canonical form. If the controller is implemented using gates, the expression can be realized with an OR gate for H+O, an inverter for F, and AND gates for the remaining conditions.

Verification and Testing

Test cases should include:

• P=1, V=1, H=1, O=0, F=0: unlock is 1.
• P=1, V=1, H=0, O=1, F=0: unlock is 1.
• P=1, V=1, H=1, O=1, F=1: unlock is 0 because the alarm dominates.
• P=1, V=0, H=1, O=1, F=0: unlock is 0.
• P=0, V=1, H=1, O=1, F=0: unlock is 0.

Outcome and Learning Points

The Boolean model gives a compact, auditable specification. However, a real safety system should not rely solely on algebra. It should use fail-safe electrical design, independent alarm wiring, authenticated override procedures, logging, access reviews, and formal testing. A supervisor override may require dual authorization rather than a single Boolean input. The case demonstrates that Boolean simplification supports implementation, but governance and safety requirements determine whether the implementation is acceptable.

11. Best Practices and Limitations

1. Define variable meanings and polarity explicitly. Confusing “alarm active” with “alarm safe” is a common source of errors.
2. State the variable order when using minterm or maxterm indices.
3. Verify a simplification with a truth table, symbolic tool, or exhaustive software test.
4. Use K-maps for small functions; use algorithmic methods such as Quine–McCluskey or electronic-design automation tools for larger systems.
5. Preserve meaningful structure in software conditions rather than minimizing purely for character count.
6. Consider unknown, missing, and invalid inputs rather than assuming every input is cleanly binary.
7. Analyze timing, hazards, reset behavior, and metastability in sequential circuits.
8. Document safety assumptions and test boundary cases.

Karnaugh maps become difficult beyond four or five variables. Algebraic minimization may produce different but equivalent results, and the globally minimum gate count depends on the available gate library, fan-in restrictions, delay targets, and technology. Consequently, “simplest Boolean expression” and “best engineering implementation” are related but not identical goals.

Chapter Summary

Boolean algebra provides a formal language for two-valued reasoning. NOT, AND, and OR form the basic operations, while NAND and NOR are universal gates and XOR is central to arithmetic circuits. Boolean laws—including identity, complement, absorption, distributive, and De Morgan’s laws—permit correct simplification.

Truth tables completely specify Boolean functions. Canonical SOP uses minterms associated with output 1, while canonical POS uses maxterms associated with output 0. Karnaugh maps minimize small functions by grouping adjacent cells in powers of two; don’t-care conditions may be used when justified. Combinational circuits depend only on current inputs, whereas sequential circuits include state and timing.

Boolean reasoning is applied in adders, multiplexers, decoders, processors, databases, software conditions, access-control systems, and rule-based applications. Practical design must also address delay, hazards, fan-out, power, metastability, testing, security, and the interpretation of unknown values. A mathematically equivalent expression is not automatically the safest or most maintainable implementation.

Key Terms

Boolean variable: A variable whose value is either 0 or 1.

Boolean function: A mapping from Boolean inputs to a Boolean output.

Literal: A variable or its complement.

Complement: The NOT of a Boolean variable or expression.

Truth table: A complete listing of input combinations and outputs.

Logic gate: A device or model implementing a Boolean operation.

NAND: NOT-AND operation; a universal logic gate.

NOR: NOT-OR operation; a universal logic gate.

XOR: Exclusive OR; true when inputs differ.

SOP: Sum-of-products expression.

POS: Product-of-sums expression.

Minterm: A product term containing every variable once.

Maxterm: A sum term containing every variable once.

Canonical form: A standard expression containing all relevant minterms or maxterms.

Karnaugh map: A Gray-code-arranged map used for Boolean minimization.

Don’t-care condition: An input state whose output is unrestricted for the application.

Combinational circuit: A circuit whose output depends only on current inputs.

Sequential circuit: A circuit whose behavior depends on inputs and stored state.

Flip-flop: An edge-triggered storage element, commonly storing one bit.

Hazard: An unwanted transient caused by unequal propagation delays.

Review Questions

Short Answer Questions

1. What is the difference between a Boolean variable and an ordinary numerical variable?
2. State both of De Morgan’s laws.
3. What is the purpose of a canonical SOP form?
4. Why must Karnaugh-map groups contain powers of two cells?
5. Distinguish a combinational circuit from a sequential circuit.

Long Answer Questions

1. Explain the principal Boolean laws and demonstrate how they simplify a Boolean expression.
2. Describe how a truth table is converted into canonical SOP and canonical POS forms.
3. Explain Karnaugh-map adjacency, grouping, wraparound, and don’t-care conditions.
4. Derive and explain the equations for a half adder and a full adder.
5. Discuss why physical circuit design involves considerations beyond Boolean minimization.

Analytical / Application Questions

1. A system grants access when the device is registered, the user is authenticated, and either the request is internal or an administrator has approved it. Express the policy in Boolean form and identify tests that should be performed.
2. Minimize F(A,B,C) = Σm(0,2,4,6) using a three-variable Karnaugh map. Explain which variable remains constant.
3. A software filter is changed from “not (expired OR suspended)” to “not expired AND not suspended.” Determine whether the transformation is logically valid under two-valued Boolean logic and identify a database situation in which additional care is required.

Multiple Choice Questions with Answers

Question 1

Which expression is equivalent to A + A′B?

A. A

B. A + B

C. AB

D. A′ + B

Correct Answer: B. A + B

Question 2

For three variables A, B, and C, how many rows are required in a complete truth table?

A. 3

B. 6

C. 8

D. 9

Correct Answer: C. 8

Question 3

Which Boolean operation is 1 when two inputs are different?

A. AND

B. OR

C. XNOR

D. XOR

Correct Answer: D. XOR

Question 4

The canonical SOP form includes a minterm for each row where the function output is:

A. 0

B. 1

C. Unknown only

D. Equal to the number of variables

Correct Answer: B. 1

Question 5

In a Karnaugh map, a valid group may contain:

A. 3 cells only

B. 5 cells only

C. Any number of cells

D. 1, 2, 4, or 8 cells

Correct Answer: D. 1, 2, 4, or 8 cells

Question 6

If F(A,B,C) = Σm(1,3,5,7), the simplified expression is:

A. A

B. B

C. C

D. A+B

Correct Answer: C. C

Question 7

What is the sum output of a half adder?

A. AB

B. A+B

C. A ⊕ B

D. A′B′

Correct Answer: C. A ⊕ B

Question 8

For a 2-to-1 multiplexer, which expression selects D₀ when S=0 and D₁ when S=1?

A. Y = SD₀ + S′D₁

B. Y = S′D₀ + SD₁

C. Y = D₀D₁

D. Y = S + D₀ + D₁

Correct Answer: B. Y = S′D₀ + SD₁

Question 9

Which circuit type includes stored state?

A. Combinational circuit

B. Sequential circuit

C. Decoder only

D. Pure OR network

Correct Answer: B. Sequential circuit

Question 10

Which issue can result from unequal propagation delays in different circuit paths?

A. Minterm

B. Canonical form

C. Hazard or glitch

D. Gray-code encoding

Correct Answer: C. Hazard or glitch