MGU Mathematics Series — Discrete Mathematics
Part V: Discrete Models, Computation, and Capstone Structures
Boolean Algebra · Logic Gates · Circuits · Binary Numbers
Chapter 13 of 14
MGU Mathematics Series  ·  Discrete Mathematics  ·  Library Textbook Edition

Chapter 13:
Boolean Algebra,
Circuits, and Digital Logic

Boolean values and operations, truth tables, logic gates, circuit diagrams, De Morgan's Laws, simplification, and binary numbers — the mathematics that turns logic into hardware

■ Discrete Mathematics ■

■ 14 Sections  •  Part V of 5 ■

Builds on Chapter 2: Logic and Truth  ·  Prepares students for Chapter 14 and Computer Architecture, Cybersecurity, and Cryptography

Chapter 13 — Front Matter

Purpose and Overview

This chapter completes the bridge between mathematical logic and the physical world of computing. In Chapter 2, you learned that logical statements can be true or false and that connectives like AND, OR, and NOT combine statements according to precise rules. In this chapter, you will see that those same logical ideas can be expressed algebraically, drawn as circuits, and built into physical hardware.

Boolean algebra is the mathematical system that uses exactly two values — typically written 0 and 1, or False and True — and three fundamental operations. It was developed by the mathematician George Boole in the nineteenth century, long before computers existed. When engineers in the twentieth century needed a mathematical language to describe electronic switching circuits, Boolean algebra turned out to be exactly the right tool. Every smartphone, laptop, server, and microcontroller operating today is built from logical operations implemented as circuits in silicon.

By the end of this chapter, you will understand how logical ideas become algebraic expressions, how those expressions map to circuit diagrams, how circuits can be simplified, and how digital computers represent and process information using binary numbers. This chapter does not require calculus. It builds on logic from Chapter 2, algebraic reasoning from your Algebra II background, and truth tables you have already practiced.

Opening Question

A combination lock on a secure door is supposed to open when all three of the following conditions are met: the correct PIN has been entered, the door sensor confirms it is fully closed, and the security system is not in lockdown mode. How would you represent this rule precisely so that a computer circuit could evaluate it automatically? And if a second rule says the door should also open for a master key regardless of the other conditions, how do you combine both rules into a single logical expression that a physical circuit can carry out? By the end of this chapter, you will be able to write, simplify, and diagram expressions exactly like these — and understand how they translate into hardware.

Why This Chapter Matters

Every digital device you use processes information using circuits built from logical gates. The mathematical language those gates implement is Boolean algebra. When programmers write conditional statements — if (x AND y) OR (NOT z) — they are writing Boolean expressions. When hardware engineers design processors, memory controllers, and communication systems, they design networks of logical gates described by Boolean algebra.

Understanding Boolean algebra means understanding the mathematical foundation of computing itself. It explains why computers use binary (0s and 1s), how decisions are made at the hardware level, how circuits can be analyzed and simplified, and how logical structure becomes physical structure.

This chapter also connects directly to cybersecurity. Encryption algorithms depend on logical operations applied to binary data. Understanding Boolean logic is a prerequisite for understanding how bitwise operations work, how data is masked, shifted, and transformed in low-level computing, and how circuits can be analyzed for vulnerabilities.

14Sections
10Objectives
22Key Terms
10+Worked Examples

Learning Objectives

  1. 1Explain what Boolean algebra is and why it uses exactly two values.
  2. 2Identify and evaluate the three fundamental Boolean operations: AND, OR, and NOT.
  3. 3Construct truth tables for Boolean expressions.
  4. 4Identify and describe the standard logic gates: AND, OR, NOT, NAND, NOR, XOR, and XNOR.
  5. 5Translate between Boolean expressions and circuit diagrams.
  6. 6State and apply De Morgan's Laws.
  7. 7Simplify Boolean expressions using algebraic laws.
  8. 8Explain why NAND and NOR gates are functionally complete.
  9. 9Convert small positive integers between binary and decimal representations.
  10. 10Describe how digital logic underlies computation and digital systems.

Key Terms

Boolean algebra, Boolean variable, Boolean value, complement, AND operation, OR operation, NOT operation, truth table, logic gate, AND gate, OR gate, NOT gate (inverter), NAND gate, NOR gate, XOR gate, XNOR gate, Boolean expression, functional completeness, De Morgan's Laws, circuit diagram, simplification, binary number, bit, binary digit, digital logic, combinational circuit.

Chapter 13 — Contents

Sections at a Glance

Sections 13.1 – 13.4
Foundations of Boolean Algebra
Why It Matters · Boolean Values · Boolean Operations · Truth Tables
Section 13.1

Why Boolean Algebra Matters

Mathematics does not always deal with continuous quantities like lengths, areas, weights, or temperatures. Sometimes what matters is not how much but which state: a switch is open or closed, a signal is high or low, a condition is satisfied or not satisfied, a bit is 0 or 1.

Boolean algebra is the branch of mathematics that studies these two-valued systems. It was introduced by George Boole in his 1854 work An Investigation of the Laws of Thought, where he showed that logical reasoning could be expressed using algebraic operations on variables that take only the values 0 and 1.

For most of the nineteenth and early twentieth centuries, Boolean algebra was studied as a branch of pure logic and abstract algebra. Then, in 1937, the mathematician and engineer Claude Shannon wrote a landmark master's thesis at MIT demonstrating that Boolean algebra could be used to analyze and design electrical switching circuits. This insight is one of the most consequential connections between abstract mathematics and engineering in history. It showed that a switching circuit — where current either flows or does not — implements Boolean logic exactly.

Modern computers are built from billions of transistors, each of which acts as a switch. Groups of transistors are combined into logic gates. Logic gates are connected into circuits. Circuits process data, perform arithmetic, store memory, and communicate. The entire hierarchy from transistor to supercomputer rests on Boolean algebra.

Understanding Boolean algebra gives you access to the mathematical language of computing at its most fundamental level.

Practice 13.1Concept Check
  1. In your own words, explain what makes a system "two-valued." Give an example of a two-valued system that is not a computer.
  2. Why was Shannon's connection between Boolean algebra and switching circuits so significant for the history of computing?
  3. Describe the hierarchy from transistor to logic gate to circuit to computer in your own words.
Section 13.2

Boolean Values

In Boolean algebra, variables can take exactly one of two values. These values are written in different ways depending on context.

ContextTrue ValueFalse Value
LogicTrue (T)False (F)
Boolean algebra10
ElectronicsHighLow
Computing10

Throughout this chapter, we will primarily use 1 for true and 0 for false, which is the standard convention in Boolean algebra and digital logic. The two values are called Boolean values, and a variable that can hold either value is called a Boolean variable.

When you write a Boolean expression, every variable in it represents a condition that is either satisfied (1) or not satisfied (0). The expression itself evaluates to either 1 or 0 based on the values of its variables.

Example 13.2.1
Interpreting Boolean variables
  • ProblemLet \( x \) represent "the user is logged in" and \( y \) represent "the user has administrator rights." Suppose \( x = 1 \) and \( y = 0 \). What does this tell us about the user?
  • ThinkEach variable represents a condition. The value 1 means the condition is satisfied; the value 0 means it is not.
  • Solvex = 1: the user is logged in. y = 0: the user does not have administrator rights.
  • CheckBoth values are either 0 or 1, consistent with Boolean variables. The interpretation matches the meaning assigned to each variable.
Answer: The user is logged in but does not have administrator rights.
Student Note

In ordinary algebra, a variable like \( x \) can take infinitely many real values. In Boolean algebra, a variable takes only the value 0 or the value 1. This restriction is not a limitation — it is the entire point. Boolean algebra is the algebra of two-state systems.

Practice 13.2Concept and Notation
  1. Let \( p \) represent "the printer has paper" and \( q \) represent "the printer is connected to the network." If \( p = 0 \) and \( q = 1 \), describe the state of the printer in words.
  2. For each situation, assign a Boolean variable name and state whether the value should be 0 or 1: (a) a smoke detector battery is dead; (b) a car's seatbelt is fastened; (c) a webpage finished loading.
  3. Explain why the restriction to exactly two values makes Boolean algebra useful for describing switches and circuits.
Section 13.3

Boolean Operations

Boolean algebra has three fundamental operations. Every other Boolean operation can be built from these three.

The NOT Operation (Complement)

The NOT operation takes one Boolean value and produces its opposite. If the input is 1, the output is 0. If the input is 0, the output is 1.

The NOT of a variable \( x \) is written as \( \overline{x} \), read "not \( x \)" or "the complement of \( x \)." In some texts it is written \( \neg x \) or \( x' \).

\( x \)\( \overline{x} \)
01
10

The NOT operation reverses the state. A locked door becomes unlocked. A false condition becomes true. A 0 bit becomes a 1 bit.

The AND Operation

The AND operation takes two Boolean values and produces 1 only when both inputs are 1. In all other cases, it produces 0.

The AND of variables \( x \) and \( y \) is written as \( x \cdot y \), or simply \( xy \), or sometimes \( x \land y \). The notation \( x \cdot y \) reflects the analogy with multiplication: in ordinary arithmetic, \( 1 \cdot 1 = 1 \), \( 1 \cdot 0 = 0 \), \( 0 \cdot 1 = 0 \), and \( 0 \cdot 0 = 0 \).

\( x \)\( y \)\( x \cdot y \)
000
010
100
111

The AND operation models "both conditions must hold." The light turns on only if the switch is up AND the bulb is working. The file opens only if you have read permission AND the file exists.

The OR Operation

The OR operation takes two Boolean values and produces 1 when at least one input is 1. It produces 0 only when both inputs are 0.

The OR of variables \( x \) and \( y \) is written as \( x + y \), or sometimes \( x \lor y \). The notation \( x + y \) reflects the analogy with addition, though note that in Boolean algebra, \( 1 + 1 = 1 \), not 2. The rule is: if either or both inputs are 1, the output is 1.

\( x \)\( y \)\( x + y \)
000
011
101
111

The OR operation models "at least one condition holds." The alarm sounds if the front door opens OR the back door opens. The payment is accepted if credit card OR bank transfer is provided.

Important Warning

In Boolean algebra, the symbol \( + \) does not mean addition in the ordinary sense. It means the logical OR operation. Similarly, \( \cdot \) means the logical AND, not ordinary multiplication. The rules look similar to arithmetic in some cases, but they differ in critical ways. Most importantly, \( 1 + 1 = 1 \) in Boolean algebra, not 2.

Operation Priority

Boolean algebra follows an order of operations:

1. NOT is applied first (highest priority).
2. AND is applied next.
3. OR is applied last (lowest priority).

Parentheses override this order, just as in ordinary algebra.

Example 13.3.1
Applying operation priority
  • ProblemExplain how operation priority groups the expression \( x + y \cdot \overline{z} \).
  • ThinkNOT binds most tightly, then AND, then OR. I will work from the highest-priority operation inward.
  • SolveStep 1 (NOT): apply NOT to z, giving z̄ Step 2 (AND): apply AND between y and z̄, giving y · z̄ Step 3 (OR): apply OR between x and y · z̄
  • CheckInserting parentheses for every grouping gives \( x + (y \cdot (\overline{z})) \), which matches the original expression exactly with no ambiguity.
Answer: \( x + y \cdot \overline{z} \) means \( x + (y \cdot \overline{z}) \).
Practice 13.3Evaluating Boolean Operations
  1. Find \( \overline{1} \) and \( \overline{0} \).
  2. Evaluate \( 1 \cdot 0 \) and \( 0 \cdot 0 \).
  3. Evaluate \( 1 + 0 \) and \( 1 + 1 \).
  4. Evaluate \( \overline{0} \cdot 1 \).
  5. Evaluate \( 1 + 0 \cdot 0 \) using operation priority.
  6. Evaluate \( (1 + 0) \cdot \overline{1} \).
  7. Evaluate \( \overline{1 \cdot 0} \).
  8. Evaluate \( 0 + \overline{0} \cdot 1 \).
Section 13.4

Truth Tables Revisited

A truth table is a systematic way to evaluate a Boolean expression for every possible combination of its input values. You first encountered truth tables in Chapter 2 in the context of logic. In Boolean algebra, the structure is identical: list all possible input combinations, then compute the output of the expression for each one.

For a Boolean expression with \( n \) variables, the truth table has \( 2^n \) rows, one for each combination of input values.

How to Construct a Truth Table

1. List all variables as column headers.

2. Fill in all \( 2^n \) combinations of 0s and 1s, using a systematic pattern.

3. Add columns for any intermediate subexpressions.

4. Add a final column for the full expression.

5. Evaluate the expression for each row.

Tip — A Pattern for Filling in Inputs

In the rightmost variable column, alternate 0, 1, 0, 1, .... In the next column to the left, alternate in groups of two: 0, 0, 1, 1, 0, 0, 1, 1, .... Continue doubling the group size for each additional variable to the left.

Example 13.4.1
Constructing a truth table
  • ProblemConstruct a truth table for the expression \( \overline{x} + y \cdot z \).
  • ThinkThis expression has three variables: \( x \), \( y \), and \( z \). The table will have \( 2^3 = 8 \) rows. Following operation priority, NOT is applied to \( x \) first, then AND combines \( y \) and \( z \), then OR combines \( \overline{x} \) with \( y \cdot z \). I will add intermediate columns for \( \overline{x} \) and \( y \cdot z \).
  • Solve
    \( x \)\( y \)\( z \)\( \overline{x} \)\( y \cdot z \)\( \overline{x} + y \cdot z \)
    000101
    001101
    010101
    011111
    100000
    101000
    110000
    111011
  • CheckWhen \( x = 0 \), \( \overline{x} = 1 \), so the OR output is always 1 regardless of \( y \) and \( z \). That accounts for rows 1–4 all giving output 1. When \( x = 1 \), \( \overline{x} = 0 \), so the output equals \( y \cdot z \), which is 1 only when both \( y = 1 \) and \( z = 1 \). That gives 1 only in row 8.
Answer: The expression \( \overline{x} + y \cdot z \) evaluates to 1 in five of the eight input combinations, and evaluates to 0 in three of them (rows 5, 6, and 7).

Two Boolean expressions are logically equivalent if they produce the same truth table output for every possible input combination. Logical equivalence in Boolean algebra corresponds exactly to logical equivalence in propositional logic from Chapter 2. We write \( E_1 = E_2 \) to indicate that expressions \( E_1 \) and \( E_2 \) are equivalent.

Practice 13.4Truth Table Construction
  1. Construct a truth table for \( x \cdot \overline{y} \).
  2. Construct a truth table for \( \overline{x} + \overline{y} \).
  3. Construct a truth table for \( x \cdot y + \overline{x} \cdot \overline{y} \). How many rows give output 1?
  4. Construct a truth table for \( (x + y) \cdot z \). Use intermediate columns.
  5. Use truth tables to determine whether \( \overline{x} \cdot \overline{y} \) and \( \overline{x + y} \) are logically equivalent.
Sections 13.5 – 13.8
Logic Gates, Circuits, and De Morgan's Laws
Logic Gates · AND/OR/NOT Circuits · Universal Gates · De Morgan's Laws
Section 13.5

Logic Gates

A logic gate is a physical or symbolic device that implements a Boolean operation. Each gate accepts one or more binary inputs and produces a single binary output according to a fixed rule. Logic gates are the building blocks of all digital circuits.

In circuit diagrams, each type of gate is drawn with a standard symbol. Since this textbook is presented in HTML, the gate symbols below are described in words and can be looked up in any standard digital logic reference or illustrated in an accompanying diagram.

NOT Gate (Inverter)

Diagram Instruction

Draw a triangle pointing right with a small circle (bubble) at the output tip. The bubble indicates inversion. One input enters on the flat left side; the inverted output exits through the bubble.

Inputs: one. Output: the complement of the input. Rule: Output = \( \overline{A} \).

Input \( A \)Output \( \overline{A} \)
01
10

AND Gate

Diagram Instruction

Draw a D-shaped symbol with a flat left side, where two or more inputs enter, and a curved right side, where the output exits.

Inputs: two or more. Output: 1 if and only if all inputs are 1; 0 otherwise. Rule: Output = \( A \cdot B \).

\( A \)\( B \)Output
000
010
100
111

OR Gate

Diagram Instruction

Draw a curved shape with a concave left side, where inputs enter, and a pointed right side, where the output exits.

Inputs: two or more. Output: 1 if at least one input is 1; 0 only if all inputs are 0. Rule: Output = \( A + B \).

\( A \)\( B \)Output
000
011
101
111

XOR Gate (Exclusive OR)

The XOR gate (exclusive OR) produces 1 when the inputs differ — that is, when exactly one input is 1 but not both.

Diagram Instruction

Draw a shape like the OR gate, but add an extra curved line just before the concave left side, slightly separated from the main body of the gate.

Inputs: two. Output: 1 if inputs differ; 0 if inputs are the same. Rule: Output = \( A \oplus B \).

\( A \)\( B \)\( A \oplus B \)
000
011
101
110

The XOR operation is particularly important in computing for detecting differences, computing parity, and performing binary addition. Notice that XOR gives 0 when both inputs are 1, unlike OR, which gives 1.

XNOR Gate (Exclusive NOR)

The XNOR gate produces 1 when the inputs are the same, and 0 when they differ. It is the complement of XOR. Rule: Output = \( \overline{A \oplus B} \).

\( A \)\( B \)Output
001
010
100
111

XNOR is used in equality testing: the output is 1 precisely when the two inputs match.

Student Note

You now have five gate types: NOT, AND, OR, XOR, and XNOR. The two most important for understanding the mathematical foundations are AND, OR, and NOT, because any Boolean expression can be built from these three alone. XOR and XNOR are derived from them but are common enough in practice to have their own standard symbols.

Practice 13.5Gates and Truth Tables
  1. For each gate (AND, OR, NOT, XOR, XNOR), write the Boolean expression it computes and describe its symbol in one sentence.
  2. Two signals \( A \) and \( B \) enter an XOR gate. \( A = 1 \) and \( B = 1 \). What is the output? Explain why this differs from the output of an OR gate with the same inputs.
  3. A sensor outputs 1 if a door is open and 0 if it is closed. A second sensor outputs 1 if an alarm is armed. Which gate would you use to test "the door is open AND the alarm is armed"? Which gate would test "exactly one of these is true"?
Section 13.6

AND, OR, and NOT Circuits

A circuit is a network of connected logic gates. Inputs enter the circuit from the left, pass through gates, and produce one or more outputs on the right. The output of one gate can become the input of another, allowing complex Boolean expressions to be computed step by step.

From Expression to Circuit

1. Identify the structure of the expression using operation priority and parentheses.

2. Work from the innermost operations outward.

3. Draw each operation as the appropriate gate.

4. Connect outputs of earlier gates to inputs of later gates.

Example 13.6.1
Drawing a circuit from a Boolean expression
  • ProblemDraw a circuit for the expression \( (A + B) \cdot \overline{C} \).
  • ThinkThe expression has two main parts connected by AND: the subexpression \( A + B \) and the subexpression \( \overline{C} \). I will need an OR gate for \( A + B \), a NOT gate for \( \overline{C} \), and then an AND gate combining the two results.
  • Solve
    Circuit Description
    • Input \( A \) and input \( B \) both enter an OR gate. The OR gate outputs \( A + B \).
    • Input \( C \) enters a NOT gate. The NOT gate outputs \( \overline{C} \).
    • The output of the OR gate (\( A + B \)) and the output of the NOT gate (\( \overline{C} \)) both enter an AND gate.
    • The AND gate outputs \( (A + B) \cdot \overline{C} \).
    Diagram Instruction

    Draw three input lines labeled \( A \), \( B \), and \( C \) on the left. Connect \( A \) and \( B \) into an OR gate. Connect \( C \) into a NOT gate (inverter). Connect the output of the OR gate and the output of the NOT gate into an AND gate. Label the final output on the right.

  • CheckWhen \( A = 1 \), \( B = 0 \), \( C = 0 \): \( A + B = 1 \), \( \overline{C} = 1 \), so \( (A + B) \cdot \overline{C} = 1 \cdot 1 = 1 \). When \( A = 0 \), \( B = 0 \), \( C = 1 \): \( A + B = 0 \), \( \overline{C} = 0 \), so the output is \( 0 \cdot 0 = 0 \). Both match what the expression should give.
Answer: The circuit requires one OR gate, one NOT gate, and one AND gate, connected in the order described above.

The reverse process is equally important. Given a circuit diagram, you can recover the Boolean expression by tracing from inputs to output, writing the operation each gate performs.

Example 13.6.2
Reading a circuit diagram
  • ProblemA circuit is described as follows: Inputs \( X \) and \( Y \) enter a NAND gate (described in Section 13.7). The output of the NAND gate and input \( Z \) enter an OR gate. What Boolean expression does this circuit implement?
  • ThinkI need to write the output of each gate in order, starting from the inputs and ending at the final gate.
  • SolveThe NAND gate on \( X \) and \( Y \) produces \( \overline{X \cdot Y} \). Then the OR gate combines that with \( Z \): Output = X̄Y + Z, written as Output = (X · Y)̄ + Z
  • CheckThe order of gates traced matches the order described: NAND first, OR second, with \( Z \) joining only at the final gate. This matches the description.
Answer: The circuit implements \( \overline{X \cdot Y} + Z \).
Practice 13.6Circuits and Expressions
  1. Draw (describe in words) a circuit for \( A \cdot B + C \).
  2. Draw (describe in words) a circuit for \( \overline{A} \cdot (B + C) \).
  3. A circuit is described as: input \( A \) enters a NOT gate. The output of the NOT gate and input \( B \) enter an OR gate. Write the Boolean expression this circuit implements.
  4. A circuit is described as: inputs \( A \) and \( B \) enter an AND gate. The output of that AND gate and input \( C \) enter a second AND gate. Write the Boolean expression. What can you conclude about ANDing more than two inputs together?
Section 13.7

NAND and NOR Gates as Universal Gates

The NAND Gate

The NAND gate (NOT-AND) computes AND and then inverts the result. Rule: Output = \( \overline{A \cdot B} \).

\( A \)\( B \)\( A \cdot B \)\( \overline{A \cdot B} \)
0001
0101
1001
1110
Diagram Instruction

Draw an AND gate symbol with a small circle (bubble) added at the output to indicate inversion.

The NAND gate outputs 0 only when both inputs are 1. In every other case, it outputs 1.

The NOR Gate

The NOR gate (NOT-OR) computes OR and then inverts the result. Rule: Output = \( \overline{A + B} \).

\( A \)\( B \)\( A + B \)\( \overline{A + B} \)
0001
0110
1010
1110
Diagram Instruction

Draw an OR gate symbol with a small circle (bubble) added at the output to indicate inversion.

The NOR gate outputs 1 only when both inputs are 0.

Functional Completeness

A set of gates is called functionally complete (or universal) if every Boolean function can be built using only gates from that set.

Claim: The set \(\{\text{NAND}\}\) is functionally complete. So is \(\{\text{NOR}\}\).

This is a remarkable fact. It means that if you have only NAND gates, you can build any logical circuit — including AND gates, OR gates, NOT gates, and everything else. The same is true for NOR gates alone.

Example 13.7.1
Building NOT from NAND
  • ProblemShow how a NOT gate can be built using only a NAND gate.
  • ThinkThe NAND gate computes \( \overline{A \cdot B} \). I need an expression that reduces to \( \overline{A} \) using only one input signal.
  • SolveConnect both inputs of a NAND gate to the same signal \( A \). Then the output is: A · A = A (Idempotent Law) NAND(A, A) = (A · A)̄ = Ā
    Diagram Instruction

    Draw a NAND gate. Connect input \( A \) to both input terminals. The output is \( \overline{A} \).

  • CheckIf \( A = 1 \): \( A \cdot A = 1 \cdot 1 = 1 \), so output is \( \overline{1} = 0 = \overline{A} \). ✓ If \( A = 0 \): \( A \cdot A = 0 \), so output is \( \overline{0} = 1 = \overline{A} \). ✓
Answer: \( \overline{A} = \overline{A \cdot A} \), so a single NAND gate with both inputs tied to \( A \) computes NOT \( A \).

How to build AND from NAND: An AND gate is a NAND gate followed by a NOT gate. Since a NOT gate can be built from NAND (as shown above), two NAND gates suffice to build an AND gate.

How to build OR from NAND: By De Morgan's Laws (Section 13.8), \( A + B = \overline{\overline{A} \cdot \overline{B}} \). So: apply NOT (via NAND) to each input, then apply NAND to the results. This requires three NAND gates.

Why This Matters in Practice

Early integrated circuits were manufactured with large numbers of identical gates. If only one gate type needed to be produced in quantity, manufacturing became simpler and cheaper. Both NAND and NOR gates are relatively easy to implement in transistor-based electronics. This is why functional completeness is not just a mathematical curiosity — it has direct engineering implications.

Practice 13.7NAND, NOR, and Functional Completeness
  1. Construct the truth table for a NOR gate directly, without referring to OR. Verify it matches \( \overline{A + B} \).
  2. Show how to build a NOT gate using only a NOR gate. (Hint: follow the same idea as Example 13.7.1, but use the idempotent law for OR.)
  3. Explain in your own words why functional completeness is useful for hardware manufacturers.
  4. Using the result \( A + B = \overline{\overline{A} \cdot \overline{B}} \), describe step by step how to build an OR gate from three NAND gates.
Section 13.8

De Morgan's Laws

De Morgan's Laws are two of the most important identities in Boolean algebra. They describe how NOT distributes over AND and OR. You first encountered these as logical equivalences in Chapter 2. Here they appear in algebraic form.

De Morgan's First Law

$$\overline{A \cdot B} = \overline{A} + \overline{B}$$

In words: The complement of a product equals the sum of the complements.

De Morgan's Second Law

$$\overline{A + B} = \overline{A} \cdot \overline{B}$$

In words: The complement of a sum equals the product of the complements.

These laws allow you to push a NOT inward through an AND or an OR, provided you change AND to OR (or OR to AND) at the same time.

Verification by Truth Table

Let us verify the first law.

\( A \)\( B \)\( A \cdot B \)\( \overline{A \cdot B} \)\( \overline{A} \)\( \overline{B} \)\( \overline{A} + \overline{B} \)
0001111
0101101
1001011
1110000

The columns for \( \overline{A \cdot B} \) and \( \overline{A} + \overline{B} \) are identical. The law is verified.

Example 13.8.1
Applying De Morgan's Laws
  • ProblemSimplify \( \overline{A + \overline{B}} \) using De Morgan's Laws.
  • ThinkThe NOT applies to the entire expression \( A + \overline{B} \). By De Morgan's Second Law, the complement of a sum equals the product of the complements.
  • SolveA + B̄ ̄ = Ā · B̄ ̄ = Ā · B $$\overline{A + \overline{B}} = \overline{A} \cdot \overline{\overline{B}} = \overline{A} \cdot B$$ The double complement \( \overline{\overline{B}} \) simplifies to \( B \), since NOT NOT equals the original value.
  • CheckVerify with inputs \( A = 0 \), \( B = 1 \): Original: \( \overline{0 + \overline{1}} = \overline{0 + 0} = \overline{0} = 1 \). Simplified: \( \overline{0} \cdot 1 = 1 \cdot 1 = 1 \). ✓
Answer: \( \overline{A + \overline{B}} = \overline{A} \cdot B \)
Generalized De Morgan's Laws

De Morgan's Laws extend to expressions with more than two variables:

$$\overline{A \cdot B \cdot C} = \overline{A} + \overline{B} + \overline{C}$$

$$\overline{A + B + C} = \overline{A} \cdot \overline{B} \cdot \overline{C}$$

The pattern is: push the NOT inward, complement every variable, and flip every AND to OR (or every OR to AND).

Practice 13.8De Morgan's Laws
  1. Apply De Morgan's Law to \( \overline{A \cdot B} \).
  2. Apply De Morgan's Law to \( \overline{A + B} \).
  3. Simplify \( \overline{\overline{A} \cdot B} \).
  4. Simplify \( \overline{A \cdot \overline{B}} \).
  5. Apply the generalized law to \( \overline{A + B + C} \).
  6. Apply the generalized law to \( \overline{A \cdot B \cdot C} \).
  7. Verify by truth table that \( \overline{A + B} = \overline{A} \cdot \overline{B} \).
  8. Simplify \( \overline{\overline{A} + \overline{B}} \) and explain each step.
Sections 13.9 – 13.11
Simplification, Circuit Diagrams, and Binary Numbers
Boolean Laws · Simplification Strategy · Circuit Diagrams · Binary Conversion · Half Adder
Section 13.9

Simplifying Boolean Expressions

One of the central goals of Boolean algebra is simplification. A simpler expression requires fewer gates to implement in hardware, which reduces cost, power consumption, and space. Just as you simplify algebraic expressions by applying algebraic laws, you simplify Boolean expressions by applying Boolean laws.

Laws of Boolean Algebra

The following laws hold for all Boolean variables \( A \), \( B \), and \( C \). Each law can be verified by truth table.

Identity and Null (Domination) Laws

$$A + 0 = A \qquad A \cdot 1 = A$$

$$A + 1 = 1 \qquad A \cdot 0 = 0$$

Idempotent and Complement Laws

$$A + A = A \qquad A \cdot A = A$$

$$A + \overline{A} = 1 \qquad A \cdot \overline{A} = 0$$

Double Complement Law: $$\overline{\overline{A}} = A$$

Commutative and Associative Laws

$$A + B = B + A \qquad A \cdot B = B \cdot A$$

$$(A + B) + C = A + (B + C) \qquad (A \cdot B) \cdot C = A \cdot (B \cdot C)$$

Distributive Laws

$$A \cdot (B + C) = A \cdot B + A \cdot C$$

$$A + (B \cdot C) = (A + B) \cdot (A + C)$$

Absorption Laws and De Morgan's Laws

$$A + A \cdot B = A \qquad A \cdot (A + B) = A$$

$$\overline{A \cdot B} = \overline{A} + \overline{B} \qquad \overline{A + B} = \overline{A} \cdot \overline{B}$$

Student Note

The second distributive law — \( A + (B \cdot C) = (A + B) \cdot (A + C) \) — has no direct analog in ordinary algebra. In ordinary algebra, \( a + bc \neq (a + b)(a + c) \). This is one of the places where Boolean algebra and ordinary algebra differ. Verify it by truth table before relying on it.

Example 13.9.1
Simplifying a Boolean expression
  • ProblemSimplify \( A \cdot B + A \cdot \overline{B} \).
  • ThinkBoth terms contain \( A \) as a factor. I can factor out \( A \) using the distributive law in reverse, then apply the complement law.
  • SolveA·B + A·B̄ = A · (B + B̄) (Distributive Law) = A · 1 (Complement Law) = A (Identity Law) $$A \cdot B + A \cdot \overline{B} = A \cdot (B + \overline{B}) = A \cdot 1 = A$$
  • CheckLet \( A = 1 \), \( B = 0 \): \( 1 \cdot 0 + 1 \cdot 1 = 0 + 1 = 1 = A \). ✓ Let \( A = 0 \), \( B = 1 \): \( 0 \cdot 1 + 0 \cdot 0 = 0 + 0 = 0 = A \). ✓
Answer: \( A \cdot B + A \cdot \overline{B} = A \)

This simplification means that a circuit which computes \( A \cdot B + A \cdot \overline{B} \) can be replaced by a single wire carrying \( A \). The complex circuit and the simple wire always produce the same output.

Example 13.9.2
Simplifying with De Morgan's Laws and absorption
  • ProblemSimplify \( \overline{(\overline{A} \cdot B)} + A \).
  • ThinkBegin with De Morgan's Law on \( \overline{(\overline{A} \cdot B)} \), then see if absorption or the idempotent law applies.
  • Solve(Ā · B)̄ + A = (Ā̄ + B̄) + A (De Morgan's First Law) = (A + B̄) + A (Double Complement) = A + B̄ + A (Associative Law) = A + B̄ (Idempotent Law) $$\overline{(\overline{A} \cdot B)} + A = A + \overline{B}$$
  • CheckLet \( A = 0 \), \( B = 0 \): Original: \( \overline{(1 \cdot 0)} + 0 = \overline{0} + 0 = 1 + 0 = 1 \). Simplified: \( 0 + 1 = 1 \). ✓ Let \( A = 1 \), \( B = 1 \): Original: \( \overline{(0 \cdot 1)} + 1 = \overline{0} + 1 = 1 + 1 = 1 \). Simplified: \( 1 + 0 = 1 \). ✓
Answer: \( \overline{(\overline{A} \cdot B)} + A = A + \overline{B} \)
A Strategy for Simplification

1. Apply De Morgan's Laws to remove NOT from over a compound expression.

2. Apply the double complement law to remove double negations.

3. Look for complement pairs (\( A \) and \( \overline{A} \)) that produce 0 (by AND) or 1 (by OR).

4. Factor using the distributive law to group terms.

5. Apply absorption to eliminate redundant terms.

6. Always verify by comparing truth tables of the original and simplified expressions.

Practice 13.9Simplification Practice
  1. \( A \cdot A + B \)
  2. \( (A + B) \cdot \overline{A + B} \)
  3. \( A + \overline{A} \cdot B \)
  4. \( \overline{\overline{A} + \overline{B}} \)
  5. \( A \cdot B + A \cdot \overline{B} + \overline{A} \cdot B \)
  6. \( (A + B)(A + \overline{B}) \)
  7. \( A \cdot (B + \overline{B} \cdot C) \)
  8. \( \overline{A} \cdot \overline{B} + \overline{A} \cdot B \)

For each expression, show every step and name the law applied at each stage.

Section 13.10

Circuit Diagrams

A circuit diagram (also called a logic diagram or gate diagram) is a drawing that shows how logic gates are connected to implement a Boolean expression. Inputs appear on the left, outputs appear on the right, and gates are connected by wires.

Reading and drawing circuit diagrams is a practical skill. In this section, we practice converting between expressions and diagrams in both directions.

From Expression to Circuit

1. Identify the top-level operation (the last operation applied in evaluation order).

2. Identify the inputs to that operation.

3. Recursively expand each input until you reach the original variables.

4. Draw gates from left to right, with inputs on the left and the final output on the right.

Example 13.10.1
Circuit for a three-variable expression
  • ProblemDraw a circuit for \( F = A \cdot \overline{B} + \overline{A} \cdot C \).
  • ThinkThe top-level operation is OR. The two inputs to OR are \( A \cdot \overline{B} \) and \( \overline{A} \cdot C \). Each of those inputs is an AND of two signals. \( \overline{B} \) requires a NOT gate on \( B \). \( \overline{A} \) requires a NOT gate on \( A \).
  • Solve
    Circuit Description
    • Input \( B \) enters a NOT gate, producing \( \overline{B} \).
    • Input \( A \) enters a NOT gate, producing \( \overline{A} \).
    • Inputs \( A \) and \( \overline{B} \) enter the first AND gate, producing \( A \cdot \overline{B} \).
    • Inputs \( \overline{A} \) and \( C \) enter the second AND gate, producing \( \overline{A} \cdot C \).
    • The outputs of both AND gates enter an OR gate, producing \( F = A \cdot \overline{B} + \overline{A} \cdot C \).
    Diagram Instruction

    Draw inputs \( A \), \( B \), and \( C \) on the left. Run \( B \) through a NOT gate. Run \( A \) through a separate NOT gate. Connect original \( A \) and the output of the NOT-\( B \) gate into AND Gate 1. Connect the output of the NOT-\( A \) gate and \( C \) into AND Gate 2. Connect the outputs of both AND gates into an OR gate. Label the output \( F \).

  • CheckWhen \( A = 1 \), \( B = 0 \), \( C = 0 \): \( \overline{B} = 1 \), so \( A \cdot \overline{B} = 1 \cdot 1 = 1 \). \( \overline{A} = 0 \), so \( \overline{A} \cdot C = 0 \cdot 0 = 0 \). \( F = 1 + 0 = 1 \). ✓
Answer: The circuit uses two NOT gates, two AND gates, and one OR gate, connected in the structure described above.
From Circuit to Expression

1. Begin at the output gate.

2. Identify its inputs.

3. Trace each input back to its source gate or input variable.

4. Write the subexpression for each gate.

5. Combine subexpressions at each gate until the full expression is written.

This process is the reverse of the previous one. With practice, it becomes fluent.

Practice 13.10Circuit Diagrams
  1. Draw (describe in words) a circuit for \( F = (A + B) \cdot C \).
  2. Draw (describe in words) a circuit for \( F = \overline{A \cdot B \cdot C} \).
  3. A circuit is described as: input \( A \) enters a NOT gate, producing \( \overline{A} \). Inputs \( \overline{A} \) and \( B \) enter an OR gate. The output of that OR gate and input \( C \) enter an AND gate. Write the Boolean expression this circuit implements.
  4. Draw a circuit for \( F = A \cdot B + A \cdot C + B \cdot C \). How many gates of each type are needed before any simplification?
Section 13.11

Binary Numbers as an Introduction

Digital computers represent all data — numbers, text, images, sounds, programs — using sequences of binary digits called bits. A bit is a single binary digit, either 0 or 1. Understanding binary numbers is essential for understanding how computers store and process information using Boolean circuits.

Counting in Binary

The binary number system uses base 2, just as the decimal system uses base 10. In decimal, each digit position represents a power of 10:

$$\underbrace{4}_{10^3}\,\underbrace{7}_{10^2}\,\underbrace{3}_{10^1}\,\underbrace{2}_{10^0} = 4 \times 1000 + 7 \times 100 + 3 \times 10 + 2 \times 1 = 4732$$

In binary, each digit position represents a power of 2:

$$\underbrace{1}_{2^3}\,\underbrace{0}_{2^2}\,\underbrace{1}_{2^1}\,\underbrace{1}_{2^0}$$

The binary number \( 1011_2 \) is read by computing:

$$1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 0 + 2 + 1 = 11_{10}$$

So the binary number \( 1011 \) equals the decimal number \( 11 \).

Converting from Binary to Decimal

Procedure

1. Write the binary number with its digits indexed from right (position 0) to left.

2. Multiply each digit by \( 2^{\text{position}} \).

3. Add the results.

Example 13.11.1
Binary to decimal conversion
  • ProblemConvert \( 110101_2 \) to decimal.
  • ThinkThis is a six-bit binary number. I will assign position values from right (position 0) to left (position 5) and compute the sum.
  • Solve
    Bit110101
    Position543210
    Value\(2^5{=}32\)\(2^4{=}16\)\(2^3{=}8\)\(2^2{=}4\)\(2^1{=}2\)\(2^0{=}1\)
    $$1 \times 32 + 1 \times 16 + 0 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 32 + 16 + 0 + 4 + 0 + 1 = 53$$
  • Check\( 32 + 16 = 48 \), \( 48 + 4 = 52 \), \( 52 + 1 = 53 \). ✓
Answer: \( 110101_2 = 53_{10} \)

Converting from Decimal to Binary

To convert a positive decimal integer to binary, repeatedly divide by 2 and record the remainders. The binary representation is the sequence of remainders read from bottom to top.

Example 13.11.2
Decimal to binary conversion
  • ProblemConvert \( 45_{10} \) to binary.
  • ThinkDivide repeatedly by 2 until the quotient is 0. Record remainders.
  • Solve
    DivisionQuotientRemainder
    \(45 \div 2\)221
    \(22 \div 2\)110
    \(11 \div 2\)51
    \(5 \div 2\)21
    \(2 \div 2\)10
    \(1 \div 2\)01
    Reading remainders from bottom to top: \( 101101 \)
  • CheckConvert back: \( 1 \times 32 + 0 \times 16 + 1 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 32 + 8 + 4 + 1 = 45 \). ✓
Answer: \( 45_{10} = 101101_2 \)

Why Binary and Boolean Logic Connect

Boolean logic and binary numbers are two sides of the same idea. A bit is a Boolean value stored as a signal. A Boolean expression applied to bits computes a new bit. A circuit of gates applied to a binary number (understood as a sequence of bits) transforms that number.

For example, the XOR operation on two bits computes the last digit of their binary sum (without carrying). The AND operation computes whether there is a carry. Building addition from XOR and AND gates is one of the foundational circuit designs in computing, called a half adder.

Half Adder

For two one-bit inputs \( A \) and \( B \):

Sum bit \( S = A \oplus B \) (XOR gate)

Carry bit \( C = A \cdot B \) (AND gate)

\( A \)\( B \)\( S = A \oplus B \)\( C = A \cdot B \)
0000
0110
1010
1101

When \( A = 1 \) and \( B = 1 \), the binary sum is \( 10_2 \), meaning sum digit 0 and carry digit 1. The circuit captures this exactly.

Practice 13.11Binary Number Practice
  1. Convert \( 1101_2 \) to decimal.
  2. Convert \( 100110_2 \) to decimal.
  3. Convert \( 27_{10} \) to binary.
  4. Convert \( 50_{10} \) to binary.
  5. Use the half adder to find the sum and carry bits for \( A = 0 \), \( B = 1 \).
  6. Use the half adder to find the sum and carry bits for \( A = 1 \), \( B = 1 \). What decimal number does the pair (carry, sum) represent?
Sections 13.12 – 13.14
Digital Logic in Practice, Common Mistakes, and the Road Ahead
Digital Logic in Computers · Common Mistakes · Preparing for Computer Architecture and Cybersecurity
Section 13.12

Digital Logic in Computers

Modern computers perform all of their operations using logic circuits. The operations you have studied in this chapter are not abstract curiosities — they are the actual operations executed in hardware billions of times per second.

The Processor

The central processing unit (CPU) of a computer is a large, complex circuit built from logic gates. The gates are implemented using transistors in silicon. A modern CPU contains billions of transistors, but each transistor is still fundamentally a switch — a device that is either on (conducting current, representing 1) or off (not conducting, representing 0).

The CPU performs arithmetic using circuits called arithmetic logic units (ALUs). An ALU is built from half adders, full adders, and other gate combinations. It can add, subtract (using complement representations), compare, and apply bitwise Boolean operations to binary numbers.

Memory

Computer memory stores Boolean values. A single memory cell stores one bit. Groups of eight bits form a byte. The memory you use when you open a program or load a file is an array of cells, each holding a 0 or a 1, read and written by circuits controlled by Boolean logic.

Conditional Logic in Hardware

When a program executes an if-then-else decision, a circuit evaluates a Boolean condition and routes data accordingly. The condition is a Boolean expression. The routing is controlled by a multiplexer — a circuit that selects one of its inputs based on a control signal.

Bitwise Operations in Computing

Programming languages expose Boolean operations directly as bitwise operators that apply Boolean logic to each pair of corresponding bits in two integers. For example, in many languages:

OperatorMeaning
A & BComputes the AND of each bit of \( A \) and each bit of \( B \).
A | BComputes the OR of each bit.
~AComputes the NOT (complement) of each bit.
A ^ BComputes the XOR of each bit.

These operations are used constantly in systems programming, cryptography, graphics, networking, and data processing.

MGU Library Connection
  • For students entering programming courses, the transition from Boolean algebra to bitwise operators in C, Java, Python, and other languages is direct. The mathematical operations in this chapter map immediately to programming operations. See the MGU Computer Science Library pages for examples.

Cryptography and Boolean Logic

Many encryption algorithms operate on bits using Boolean operations. The XOR operation is particularly important: XOR-ing a plaintext bit with a key bit produces a ciphertext bit, and XOR-ing the ciphertext bit with the same key bit recovers the plaintext. This is the basis of one-time pad encryption and stream cipher design.

Boolean permutations, substitutions, and combinations of XOR, AND, and OR operations underlie the structure of block ciphers including AES (Advanced Encryption Standard), which protects most secure internet communication today.

MGU Library Connection
  • Students entering cybersecurity or cryptography courses will study how Boolean operations on bit sequences form the core of symmetric encryption. The Boolean algebra in this chapter is the mathematical prerequisite for that work. See the MGU Cybersecurity and Cryptography Library pages.
Practice 13.12Applications in Computing
  1. Explain in your own words what an ALU does and how it relates to Boolean algebra.
  2. A byte is eight bits. How many distinct values can a single byte represent? Explain your reasoning using ideas from Chapter 7 or 8.
  3. Suppose a one-bit plaintext message is \( M = 1 \) and the one-bit key is \( K = 1 \). The ciphertext is \( C = M \oplus K \). Compute \( C \). Now XOR the ciphertext with the key: \( M' = C \oplus K \). What is \( M' \)? What does this demonstrate about XOR in encryption?
Section 13.13

Common Boolean Algebra and Circuit Mistakes

Understanding where errors typically occur helps you avoid them and catch them when checking your work.

Mistake 1 — Treating + and · as Ordinary Arithmetic
A + A = 2A Correct: A + A = A (Idempotent Law). In Boolean algebra, 1 + 1 = 1, not 2. The symbols + and · represent OR and AND, not addition and multiplication.
Mistake 2 — Forgetting Operation Priority
Treating A + B · C as (A + B) · C Correct: A + B · C means A + (B · C), because NOT binds most tightly, then AND, then OR. When in doubt, use parentheses to make the intended grouping explicit.
Mistake 3 — Distributing NOT Incorrectly
A + B ̄ = Ā + B̄ Correct: A + B ̄ = Ā · B̄ (De Morgan's Second Law). The most common De Morgan's Law mistake is forgetting to flip AND to OR (or OR to AND) when pushing NOT inward.
Mistake 4 — Applying Ordinary Algebra's Distributive Law in Reverse
(A + B)(A + C) = A² + AC + AB + BC Correct: (A + B)(A + C) = A + BC in Boolean algebra. These are different from ordinary algebra. When applying the second distributive law, verify by truth table.
Mistake 5 — Stopping Simplification Too Early
Leaving A + A · B unsimplified Correct: A + A · B simplifies by absorption to just A. Always check whether absorption, complement, or idempotent laws apply after each step.
Mistake 6 — Confusing XOR with OR

XOR outputs 0 when both inputs are 1. OR outputs 1 when both inputs are 1. These gates behave the same for all other inputs, which can lead students to use them interchangeably when they should not.

InputsORXOR
0, 000
0, 111
1, 011
1, 110
Mistake 7 — Confusion About Gate Symbols in Diagrams

NAND and NOR symbols look like AND and OR symbols with a bubble added at the output. Omitting or misplacing the bubble changes the meaning entirely. Always label gates clearly.

Mistake 8 — Incorrect Binary-Decimal Conversion
1010₂ → 1·2⁰ + 0·2¹ + 1·2² + 0·2³ = 1 + 0 + 4 + 0 = 5 Correct: the rightmost digit is always position 0 (the ones place, 2⁰). For 1010₂: 1·2³ + 0·2² + 1·2¹ + 0·2⁰ = 8 + 0 + 2 + 0 = 10. Students sometimes start multiplying from the left using position 0, rather than from the right.
Practice 13.13Error Analysis
  1. A student writes: \( \overline{A + B} = \overline{A} + \overline{B} \). What law did the student misapply? Write the correct identity.
  2. A student evaluates \( A + B \cdot C \) with \( A = 0, B = 1, C = 1 \) as follows: first compute \( A + B = 0 + 1 = 1 \), then compute \( 1 \cdot C = 1 \cdot 1 = 1 \). The student concludes the answer is 1. Is this correct? If not, what went wrong?
  3. A student simplifies \( A + A \cdot B \) as follows: "Factor out \( A \): \( A(1 + B) = A \cdot 1 = A \)." Another student simplifies by absorption directly. Do both methods give the correct answer? If so, which law does each use?
  4. A student converts the binary number \( 1010_2 \) to decimal by computing \( 1 \times 2^0 + 0 \times 2^1 + 1 \times 2^2 + 0 \times 2^3 = 1 + 0 + 4 + 0 = 5 \). Is this correct? If not, what is the correct decimal value?
  5. A student writes: "Since \( 1 + 1 = 2 > 1 \) in arithmetic, and \( 2 \neq 1 \), the expression \( A + A \) when \( A = 1 \) should equal 2 in Boolean algebra." Identify and correct the error.
Section 13.14

Preparing for Computer Architecture and Cybersecurity

Chapter 13 is the final chapter before the capstone. You now have a working knowledge of Boolean algebra, logic gates, circuits, simplification, De Morgan's Laws, binary numbers, and digital logic.

The ideas in this chapter open into several areas of further study:

Computer Architecture

Courses in computer organization and architecture examine how processors are built from ALUs, registers, memory units, control circuits, and buses — all of which are implemented using the Boolean logic gates you have studied. Concepts like carry-ripple addition, multiplexers, decoders, encoders, and flip-flops (memory elements) build directly on this chapter.

Combinational versus Sequential Circuits

The circuits studied here are combinational — their output depends only on their current inputs. Sequential circuits include memory (feedback): their output can depend on their history. Flip-flops and latches are the building blocks of sequential circuits. This leads to state machines and registers.

Digital Systems Design

Engineers use hardware description languages (HDLs) such as VHDL and Verilog to describe Boolean circuits as programs, which are then synthesized into physical circuits on programmable chips. Boolean algebra is the mathematical foundation of HDL design.

Cybersecurity and Cryptography

As noted in Section 13.12, Boolean operations are central to symmetric encryption. Bitwise XOR, AND, OR, and NOT are used in stream ciphers, hash functions, block cipher rounds, and key scheduling. Understanding the mathematical behavior of these operations is a prerequisite for studying cryptographic algorithms.

Artificial Intelligence Hardware

Neural network inference is accelerating on specialized hardware (GPUs, TPUs, and custom AI chips). The arithmetic operations these chips perform — including multiply-accumulate operations at reduced precision — are implemented using Boolean circuits. Understanding the link between logic and arithmetic deepens understanding of how AI systems run efficiently.

MGU Library Connection
  • Students preparing for computer architecture, digital design, cybersecurity, or cryptography courses should review this chapter thoroughly. See the MGU Computer Architecture Library page and the MGU Cybersecurity Foundations Library page for further reading.
Chapter 13 — Back Matter

Chapter Summary

Key Terms Review

Boolean algebra
The algebraic system with two values (0 and 1) and three fundamental operations: NOT, AND, OR.
Boolean variable
A variable that can hold either of the two Boolean values.
Boolean value
One of the two values in Boolean algebra: 0 (false) or 1 (true).
complement
The NOT of a Boolean value; written \( \overline{A} \).
AND operation
The Boolean operation that outputs 1 only when both inputs are 1; written \( A \cdot B \) or \( AB \).
OR operation
The Boolean operation that outputs 1 when at least one input is 1; written \( A + B \).
NOT operation
The Boolean operation that inverts a value; written \( \overline{A} \).
truth table
A systematic table evaluating a Boolean expression for all input combinations.
logic gate
A physical or symbolic device implementing a Boolean operation.
AND gate
A logic gate whose output is 1 if and only if all inputs are 1.
OR gate
A logic gate whose output is 1 if at least one input is 1.
NOT gate (inverter)
A logic gate computing the complement \( \overline{A} \) of its single input.
NAND gate
A logic gate computing \( \overline{A \cdot B} \); AND followed by NOT.
NOR gate
A logic gate computing \( \overline{A + B} \); OR followed by NOT.
XOR gate
A logic gate whose output is 1 when the inputs differ; written \( A \oplus B \).
XNOR gate
A logic gate whose output is 1 when the inputs are the same; the complement of XOR.
Boolean expression
A formula built from Boolean variables and operations.
functional completeness
The property of a set of gates that allows every Boolean function to be expressed using only gates from that set. NAND alone and NOR alone are each functionally complete.
De Morgan's Laws
The identities \( \overline{A \cdot B} = \overline{A} + \overline{B} \) and \( \overline{A + B} = \overline{A} \cdot \overline{B} \).
circuit diagram
A drawing showing logic gates connected by wires to implement a Boolean expression.
binary number
A number represented in base 2 using only the digits 0 and 1.
bit (binary digit)
A single digit in the binary number system; either 0 or 1.
digital logic
The use of Boolean operations and binary signals to implement computation in hardware.
combinational circuit
A circuit whose output depends only on its current inputs, with no memory or feedback.

Concept Review Questions

These questions test understanding of definitions and ideas. Write answers in complete sentences.

  1. What are the two Boolean values, and what do they represent?
  2. Why is Boolean algebra called "two-valued"? What does this mean?
  3. Describe in words the difference between AND, OR, and NOT.
  4. What is a logic gate? How does a gate relate to a Boolean operation?
  5. What does it mean for a set of gates to be functionally complete?
  6. State De Morgan's First Law and explain in words what it says.
  7. State De Morgan's Second Law and explain in words what it says.
  8. What is an idempotent law? Give an example using Boolean algebra.
  9. Why is simplification of Boolean expressions practically important?
  10. What is a bit? What is the connection between bits and Boolean values?
  11. In a binary number, which position corresponds to \( 2^0 \)?
  12. Explain how XOR and AND combine to implement binary addition in a half adder.
  13. Give one example of how Boolean algebra is used in cryptography.
  14. Why is a NAND gate sometimes preferred over a separate AND gate followed by a NOT gate in circuit design?
  15. What is the difference between XOR and OR? When do they give different outputs?

Skill Practice

Part ABoolean Expression Evaluation
  1. Evaluate \( A \cdot \overline{B} + C \) when \( A = 1, B = 1, C = 0 \).
  2. Evaluate \( \overline{A + B} \cdot C \) when \( A = 0, B = 0, C = 1 \).
  3. Evaluate \( \overline{(A \cdot B) + C} \) when \( A = 1, B = 0, C = 1 \).
  4. Evaluate \( A \oplus B \) when (a) \( A = 0, B = 0 \) and (b) \( A = 1, B = 1 \).
  5. Evaluate \( \overline{A} \cdot \overline{B} + A \cdot B \) when \( A = 1, B = 0 \).
Part BTruth Table Practice
  1. Construct a complete truth table for \( A \cdot B + \overline{A} \).
  2. Construct a complete truth table for \( (A + B) \cdot (A + C) \).
  3. Construct a complete truth table for \( \overline{A + B \cdot C} \).
  4. Construct a complete truth table for \( A \oplus B \oplus C \).
  5. Construct a complete truth table for \( \overline{A} \cdot B + A \cdot \overline{B} \).
  6. Is \( \overline{A \cdot B} \) equal to \( \overline{A} \cdot \overline{B} \)? Use truth tables to decide.
  7. Is \( A \cdot (B + C) \) equal to \( A \cdot B + A \cdot C \)? Use truth tables to decide.
Part CCircuit Practice
  1. Draw a circuit diagram for \( F = A + \overline{B} \). Describe the gates needed.
  2. Draw a circuit diagram for \( F = (A \cdot B) + (A \cdot C) \). What simplification of this expression does the circuit suggest?
  3. Draw a circuit diagram for \( F = \overline{A \cdot B} + C \) (a NAND gate feeding into an OR gate with \( C \)).
  4. A circuit has two inputs \( X \) and \( Y \). They each pass through NOT gates. The outputs of the NOT gates enter an AND gate. Write the Boolean expression this circuit implements. Then apply De Morgan's Law to name an equivalent gate.
  5. A circuit is described as: Inputs \( A \), \( B \), and \( C \). \( A \) and \( B \) enter an XOR gate. The output of the XOR gate and \( C \) enter an AND gate. Write the Boolean expression for this circuit.
  6. Show using gates that NOT can be built from a NAND gate with both inputs tied together.
  7. Draw a half adder circuit and label the sum and carry outputs.
Part DSimplification Practice (Applied)

For each, simplify the Boolean expression as much as possible, then describe a situation in which the simplified circuit might represent a real-world condition.

  1. \( (A + \overline{A}) \cdot B \) — What does this always simplify to, and what does it mean about the condition \( B \)?
  2. \( A \cdot 0 + B \)
  3. \( \overline{A} \cdot \overline{B} + \overline{A} \cdot B \)
  4. A security system activates when: (the alarm is triggered AND the door is open) OR (the alarm is triggered AND the motion sensor detects movement). Write this as a Boolean expression using variables \( T \), \( D \), and \( M \), then simplify.
  5. An access control system grants access when: (the card is valid AND the PIN is correct) OR (the override key is active). A second version of the system uses NAND gates only. Using De Morgan's Laws, rewrite the access condition in a form that uses only NAND operations.

Applications

Application 1 — Password Validation

A system grants login access when the following condition is true: the username exists in the database (variable \( U \)) AND (the password is correct (variable \( P \)) OR the biometric scan succeeds (variable \( B \))). Write this condition as a Boolean expression. Construct its truth table. Identify which input combinations grant access.

Application 2 — Traffic Signal Logic

A simple intersection controller should turn on the green light (\( G = 1 \)) when: a car is present in the lane (variable \( C \)), AND the crossing pedestrian signal is off (variable \( \overline{W} \)), AND no emergency vehicle override is active (variable \( \overline{E} \)). Write the Boolean expression for \( G \) and draw a circuit implementing it.

Application 3 — Binary Arithmetic

Use the half adder circuit to compute the binary sum of \( 1 \) and \( 1 \). What are the sum bit and carry bit? What decimal result does this represent?

Application 4 — XOR and Encryption

Suppose a one-bit plaintext message is \( M = 1 \) and the one-bit key is \( K = 1 \). The ciphertext is \( C = M \oplus K \). Compute \( C \). Now XOR the ciphertext with the key: \( M' = C \oplus K \). What is \( M' \)? What does this demonstrate about XOR in encryption?

Application 5 — Simplifying a Control Circuit

A heating system turns on its heating element (\( H = 1 \)) when: (the temperature is below the setpoint (variable \( L \)) AND the thermostat is enabled (variable \( T \))) OR (the manual override is activated (variable \( O \))). The engineer realizes the circuit can be simplified if the thermostat is always enabled (\( T = 1 \)). Simplify the expression under this assumption. What does this mean for the circuit?

Error Analysis

Each of the following contains a mistake. Identify the error and write the correct result.

Problem 1
A student writes: A + B ̄ = Ā + B̄

What law did the student misapply? Write the correct identity.

Problem 2
For A = 0, B = 1, C = 1: A + B = 0 + 1 = 1, then 1 · C = 1, so A + B · C = 1

Is this correct? If not, what went wrong?

Problem 3
A + A·B simplified two different ways

A student simplifies A + A · B as follows: "Factor out A: A(1 + B) = A · 1 = A." Another student simplifies by absorption directly. Do both methods give the correct answer? If so, which law does each use?

Problem 4
1010₂ = 1·2⁰ + 0·2¹ + 1·2² + 0·2³ = 1 + 0 + 4 + 0 = 5

Is this correct? If not, what is the correct decimal value?

Problem 5
"Since 1 + 1 = 2 > 1 in arithmetic, A + A when A = 1 should equal 2 in Boolean algebra."

Identify and correct the error.

Chapter 13 Checkpoint

Chapter 13 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 13
Part A — Boolean Values and Operations
  1. State the value of each expression: (a) \( 1 \cdot 0 \) (b) \( 0 + 1 \) (c) \( \overline{1} \) (d) \( 1 + 1 \) (e) \( 0 \cdot 0 \)
  2. Evaluate \( (A + B) \cdot \overline{C} \) for \( A = 1, B = 0, C = 1 \). Show each step.
  3. Construct the complete truth table for \( F = A \cdot B + \overline{A} \cdot C \).
Part B — Logic Gates
  1. Name the gate whose output is 0 only when all inputs are 1. Write its Boolean expression for two inputs \( A \) and \( B \).
  2. Name the gate whose output is 1 only when the inputs differ. Write its Boolean expression.
  3. Describe in words how to build a NOT gate using only NAND gates.
Part C — De Morgan's Laws and Simplification
  1. Apply De Morgan's Laws to simplify \( \overline{\overline{A} + B} \).
  2. Simplify \( A \cdot B + A \cdot \overline{B} + \overline{A} \cdot B + \overline{A} \cdot \overline{B} \). What does the result tell you?
  3. Use the absorption law to simplify \( A \cdot B + A \).
  4. A student claims that \( \overline{A \cdot B} = \overline{A} \cdot \overline{B} \). Is the student correct? State the correct form and name the law.
Part D — Circuits
  1. Write the Boolean expression for the following circuit description: Inputs \( X \) and \( Y \) enter a NAND gate. The output of the NAND gate and input \( Z \) enter an OR gate. What is the final Boolean expression?
  2. Draw a circuit (describe in words) for the expression \( F = \overline{A} \cdot B + A \cdot \overline{B} \). Name each gate used.
  3. What does it mean for a gate type to be "functionally complete"? Give one example.
Part E — Binary Numbers
  1. Convert \( 10110_2 \) to decimal.
  2. Convert \( 37_{10} \) to binary. Show your work using the repeated division method.
  3. In a half adder, what is the sum bit and carry bit when \( A = 1 \) and \( B = 0 \)?
Part F — Applications and Reasoning
  1. A door unlock system uses three inputs: a PIN entry (\( P \)), a card swipe (\( C \)), and an emergency override (\( E \)). The door unlocks when: (PIN is entered AND card is swiped) OR the emergency override is active. Write this as a Boolean expression.
  2. Simplify the expression from Problem 17 if the emergency override is never used (\( E = 0 \)).
  3. A student simplifies \( \overline{A + B \cdot C} \) by writing \( \overline{A} + \overline{B} \cdot \overline{C} \). Find the error, identify which law was misapplied, and write the correct simplification.
  4. Explain in three to five sentences why Boolean algebra is the mathematical foundation of digital computers. Your explanation should mention binary values, logic gates, circuits, and computation.
Looking Ahead
Chapter 14: Discrete Mathematics Capstone and Applications

Chapter 13 sits at the intersection of mathematics, logic, and engineering. The Boolean algebra you have studied here is not an isolated topic. It is the language in which digital systems are designed, analyzed, and verified. The operations in this chapter are implemented physically in transistors and combined into functional units — adders, multiplexers, comparators, decoders, registers, and memory cells — that make up a processor. Every CPU instruction ultimately reduces to sequences of Boolean operations on binary data.

Engineers use Boolean algebra to minimize gate counts, reduce power consumption, and verify circuit correctness. Karnaugh maps and the Quine-McCluskey algorithm — systematic methods for minimizing Boolean expressions — are within reach of students who master this chapter. Boolean operations, especially XOR, are also central to encryption, hashing, and error correction, foundational for studying block ciphers, stream ciphers, and hash functions. Every programming language provides bitwise Boolean operators that implement these ideas directly.

Boolean algebra is an example of a mathematical structure called a complemented distributive lattice, or equivalently, a Boolean ring. Students continuing into abstract algebra will encounter Boolean algebras as a family of algebraic structures satisfying the same axioms used in this chapter. Chapter 14, the capstone, will bring this chapter's logic and circuits together with sets, proof, counting, graph theory, algorithms, modular arithmetic, recursion, and relations — the full toolkit of discrete mathematics — to model real systems involving choices, connections, rules, steps, and finite structures.

MGU Library Connection
  • Boolean Algebra and Logic Gate Reference — Appendix O of this textbook
  • Logic Laws Reference — Appendix C of this textbook
  • Discrete Mathematics, Chapter 2: Logic and Truth
  • MGU Computer Architecture Library — processors, ALUs, and sequential circuits
  • MGU Cybersecurity and Cryptography Library — bitwise operations and symmetric encryption
  • MGU Dictionary entries: Boolean algebra, logic gate, De Morgan's Laws, binary number, functional completeness