The Central Idea
A logic gate receives one or more Boolean inputs and produces a Boolean output.
Common input values are written
\[ 0\qquad\text{and}\qquad1, \]corresponding to low/high, false/true, off/on, or another two-state interpretation.
A circuit is built by connecting the output of one gate to the input of another.
Three Equivalent Descriptions
A Boolean system can often be described in three equivalent forms:
- a Boolean expression;
- a truth table;
- a logic circuit.
For example,
\[ y=p\land q \]describes an AND operation.
The corresponding gate produces \(1\) only when both inputs are \(1\).
The NOT Gate
A NOT gate has one input and one output.
It reverses the input:
\[ y=\neg p. \]| \(p\) | \(y\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
A NOT gate is also called an inverter.
The AND Gate
An AND gate produces \(1\) only when every required input is \(1\).
\[ y=p\land q. \]| \(p\) | \(q\) | \(y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The OR Gate
An OR gate produces \(1\) whenever at least one input is \(1\).
\[ y=p\lor q. \]| \(p\) | \(q\) | \(y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The XOR Gate
An XOR gate produces \(1\) when exactly one of its two inputs is \(1\).
\[ y=p\oplus q. \]| \(p\) | \(q\) | \(y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR is useful for difference detection and binary addition.
The NAND Gate
NAND means NOT-AND:
\[ y=\neg(p\land q). \]| \(p\) | \(q\) | \(y\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The NOR Gate
NOR means NOT-OR:
\[ y=\neg(p\lor q). \]| \(p\) | \(q\) | \(y\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
The XNOR Gate
XNOR is the complement of XOR.
\[ y=\neg(p\oplus q). \]It produces \(1\) when the two inputs agree.
| \(p\) | \(q\) | \(y\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Inputs, Outputs, and Wires
A circuit diagram represents Boolean information flowing through connected components.
An input wire carries a Boolean value into a gate.
An output wire carries the result to another gate or to the final output.
Intermediate wires represent intermediate Boolean expressions.
Reading a Circuit from Left to Right
A combinational logic circuit is usually evaluated from inputs toward the output.
Suppose the first stage computes
\[ a=p\land q \]and a second stage computes
\[ y=a\lor r. \]Then the complete circuit represents
\[ \boxed{y=(p\land q)\lor r}. \]Intermediate Signals
Naming intermediate signals makes circuits easier to analyze.
For
\[ y=(p\land q)\lor\neg r, \]define
\[ a=p\land q \]and
\[ b=\neg r. \]Then
\[ y=a\lor b. \]This mirrors the step-by-step evaluation of Boolean expressions.
Building a Circuit from an Expression
Consider
\[ y=(p\land q)\lor\neg r. \]A direct construction requires:
- an AND gate for \(p\land q\);
- a NOT gate for \(\neg r\);
- an OR gate combining those two outputs.
Expression Trees and Circuit Structure
The nested structure of a Boolean expression tells us how gates must be connected.
In
\[ \neg[(p\lor q)\land r], \]the inner OR is computed first:
\[ a=p\lor q. \]Then
\[ b=a\land r. \]Finally,
\[ y=\neg b. \]Building an Expression from a Circuit
To read a circuit symbolically:
- identify the output of each first-stage gate;
- name those intermediate results;
- substitute them into later gates;
- continue until the final output expression is obtained.
This process reverses circuit construction.
Example: Read a Two-Stage Circuit
Suppose one gate computes
\[ a=p\lor q \]while another computes
\[ b=\neg r. \]If the final gate computes
\[ y=a\land b, \]then
\[ \boxed{y=(p\lor q)\land\neg r}. \]Constructing a Truth Table for a Circuit
A circuit truth table can be built exactly like the truth table for its Boolean expression.
For
\[ y=(p\land q)\lor r, \]create an intermediate column for
\[ p\land q, \]then compute the final OR with \(r\).
Example: Circuit Truth Table
| \(p\) | \(q\) | \(r\) | \(p\land q\) | \((p\land q)\lor r\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Combinational Circuits
A combinational circuit has outputs determined only by its current inputs.
If the same inputs are supplied again, the same outputs result.
AND, OR, NOT networks built without stored state are combinational.
Combinational Circuits Do Not Remember
A purely combinational circuit has no internal memory of previous input values.
Its behavior is fully described by a Boolean function
\[ y=f(x_1,x_2,\ldots,x_n). \]Circuits that remember previous states require additional structures and will connect to finite-state machines later in this unit.
Equivalent Expressions Produce Equivalent Circuits
If two Boolean expressions are logically equivalent, then circuits implementing them have the same input-output behavior.
For example,
\[ p\land(q\lor r) \]and
\[ (p\land q)\lor(p\land r) \]produce the same output for every input assignment.
Circuit Simplification
Boolean algebra can reduce the number of gates needed by a circuit.
Consider
\[ (p\land q)\lor(p\land\neg q). \]Factor \(p\):
\[ p\land(q\lor\neg q). \]Since
\[ q\lor\neg q=T, \]we obtain
\[ \boxed{p}. \]The entire multi-gate network can therefore be replaced by a direct wire carrying \(p\).
Why Fewer Gates Can Matter
A simpler circuit can offer practical advantages such as:
- fewer components;
- lower cost;
- lower power use;
- less propagation delay;
- easier verification;
- simpler physical layout.
Propagation through Multiple Gates
In a physical circuit, signals require a small amount of time to pass through each gate.
A signal traveling through several gate levels may therefore arrive later than one traveling through fewer levels.
This time is called propagation delay.
At an introductory level, circuit depth provides a useful way to think about this delay.
Circuit Depth
The depth of a combinational circuit is the maximum number of gate stages along a path from an input to the output.
For
\[ y=(p\land q)\lor r, \]the path from \(p\) or \(q\) passes through an AND gate and then an OR gate.
That path has depth \(2\).
Fan-In
The fan-in of a gate is the number of input signals it accepts.
A standard two-input AND gate has fan-in \(2\).
A three-input AND gate has fan-in \(3\).
Larger Boolean conjunctions can be implemented with one multi-input gate or several smaller gates.
Fan-Out
The fan-out of a signal describes how many downstream gate inputs receive that signal.
A single Boolean result may feed several later gates.
In abstract logic diagrams, this is represented by branching a wire.
NAND Is Functionally Complete
Every Boolean function can be implemented using only NAND gates.
NOT can be built from NAND:
\[ \neg p \equiv p\uparrow p. \]Once NOT is available, AND and OR can also be built from NAND.
Building AND from NAND
First compute
\[ a=p\uparrow q=\neg(p\land q). \]Then invert \(a\) using another NAND:
\[ a\uparrow a=\neg a. \]Therefore,
\[ \boxed{ (p\uparrow q)\uparrow(p\uparrow q) \equiv p\land q }. \]Building OR from NAND
De Morgan gives
\[ p\lor q \equiv \neg(\neg p\land\neg q). \]NAND can construct both negations and the final negated conjunction:
\[ \boxed{ (p\uparrow p)\uparrow(q\uparrow q) \equiv p\lor q }. \]NOR Is Also Functionally Complete
NOR can similarly construct NOT, OR, and AND.
For example,
\[ p\downarrow p = \neg(p\lor p) \equiv \neg p. \]Therefore, NOR alone can implement every Boolean function.
Universal Gates
Because NAND and NOR can each generate all Boolean functions, they are often called universal gates.
This is valuable because a circuit family can be standardized around a single gate type.
Two-Level Circuits
Normal forms naturally produce two-level circuit structures.
A DNF expression is an OR of AND-terms.
This suggests:
- a first level of AND gates;
- a second level OR gate.
Negations may appear on the inputs as needed.
CNF Circuits
A CNF expression is an AND of OR-clauses.
This suggests:
- a first level of OR gates;
- a second level AND gate.
Thus normal forms translate naturally into regular circuit layouts.
Example: DNF to Circuit
Consider
\[ y=(p\land q)\lor(\neg p\land r). \]A direct circuit uses:
- a NOT gate to form \(\neg p\);
- an AND gate for \(p\land q\);
- an AND gate for \(\neg p\land r\);
- an OR gate combining the two terms.
Example: CNF to Circuit
Consider
\[ y=(p\lor q)\land(\neg p\lor r). \]A direct circuit uses:
- a NOT gate to form \(\neg p\);
- an OR gate for \(p\lor q\);
- an OR gate for \(\neg p\lor r\);
- an AND gate combining both clauses.
Designing from a Truth Table
A truth table can be converted into a Boolean expression and then into a circuit.
One systematic route is:
- identify the rows where the output is \(1\);
- write a minterm for each such row;
- OR the minterms together;
- translate the resulting DNF into gates.
Example: Build a Circuit from True Rows
Suppose a two-input output \(y\) is \(1\) only when the inputs differ.
The true rows are
\[ (p,q)=(1,0) \]and
\[ (p,q)=(0,1). \]The canonical DNF is
\[ (p\land\neg q)\lor(\neg p\land q). \]This is precisely XOR:
\[ \boxed{y=p\oplus q}. \]Binary Addition
Logic gates can perform arithmetic on binary digits.
Adding two one-bit inputs produces:
- a sum bit;
- a carry bit.
This leads to the half-adder.
The Half-Adder
Let the input bits be
\[ p,\qquad q. \]The sum bit is
\[ \boxed{S=p\oplus q}. \]The carry bit is
\[ \boxed{C=p\land q}. \]Half-Adder Truth Table
| \(p\) | \(q\) | \(S\) | \(C\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
When \(1+1\) is added in binary, the sum bit is \(0\) and the carry bit is \(1\).
Why the Half-Adder Uses XOR and AND
The sum bit is \(1\) exactly when the inputs differ.
That is XOR behavior.
A carry is needed only when both inputs are \(1\).
That is AND behavior.
The Full-Adder
A full-adder adds three one-bit inputs:
\[ p,\qquad q,\qquad c_{\text{in}}, \]where \(c_{\text{in}}\) is a carry from a previous position.
It produces:
\[ S \]and
\[ c_{\text{out}}. \]Full-Adder Sum
The sum bit is
\[ \boxed{ S=p\oplus q\oplus c_{\text{in}} }. \]The sum bit is \(1\) when an odd number of the three inputs are \(1\).
Full-Adder Carry
The carry output is \(1\) when at least two of the three inputs are \(1\).
One Boolean expression is
\[ \boxed{ c_{\text{out}} = (p\land q) \lor (p\land c_{\text{in}}) \lor (q\land c_{\text{in}}) }. \]From Adders to Larger Arithmetic Circuits
Full-adders can be connected so that the carry output from one position feeds the carry input of the next position.
This allows multi-bit binary numbers to be added.
More advanced digital arithmetic circuits extend the same Boolean principles.
Multiplexing as a Boolean Selection Problem
A selector signal can choose between two data inputs.
Let:
\[ a,\qquad b \]be data inputs and let \(s\) be a selector.
A two-way selection expression is
\[ \boxed{ y=(\neg s\land a)\lor(s\land b) }. \]When \(s=0\), \(y=a\). When \(s=1\), \(y=b\).
Comparators
Boolean circuits can compare bits.
For two inputs,
\[ p\leftrightarrow q \]or XNOR produces \(1\) when the bits are equal.
XOR produces \(1\) when they differ.
Control Logic
Many digital systems use Boolean circuits to decide whether an action should occur.
For example,
\[ \text{run} = \text{enabled} \land \neg\text{fault}. \]The system runs only when it is enabled and no fault is present.
Safety Interlocks
Boolean logic can model multiple safety requirements.
Suppose a machine may operate only if:
- the guard is closed;
- the emergency stop is not active;
- power is available.
A Boolean model is
\[ \boxed{ \text{operate} = \text{guard} \land \neg\text{emergency} \land \text{power} }. \]Circuits and Physical Meaning
The Boolean value \(1\) does not always mean the same physical thing.
Depending on the system, it may represent:
- a high voltage;
- a closed switch;
- permission granted;
- a detected signal;
- an active feature.
The Boolean structure remains the same even when the interpretation changes.
Positive and Negative Logic Conventions
In many systems, the higher electrical state is interpreted as \(1\) and the lower as \(0\).
Other conventions are possible.
Logic analysis should therefore distinguish the abstract Boolean value from the physical representation carrying that value.
Common Error: Confusing OR with XOR
OR gives
\[ 1\lor1=1, \]while XOR gives
\[ 1\oplus1=0. \]Their gate symbols and truth tables represent different functions.
Common Error: Forgetting the Inversion in NAND
NAND is not AND.
First compute
\[ p\land q, \]then invert:
\[ \boxed{\neg(p\land q)}. \]Common Error: Forgetting the Inversion in NOR
NOR is
\[ \boxed{\neg(p\lor q)}. \]It is \(1\) only when both inputs are \(0\).
Common Error: Reading a Circuit in the Wrong Order
A downstream gate depends on the outputs of upstream gates.
Evaluate the circuit from inputs toward the final output, respecting every intermediate signal.
Common Error: Ignoring a Branch
A signal may feed more than one gate.
Every branch carries the same Boolean value from that point unless another gate changes it.
Common Error: Treating a Combinational Circuit as Memory
A combinational circuit depends only on current inputs.
If a system must remember what happened earlier, a state-holding structure is required.
That distinction becomes central in finite-state machines.
Common Error: Assuming More Gates Means More Logical Power
A large circuit may implement exactly the same Boolean function as a much smaller circuit.
Boolean simplification can reveal unnecessary gates.
A Reliable Procedure for Evaluating a Circuit
- Write the input values.
- Identify the first-stage gates.
- Compute each first-stage output.
- Label intermediate signals when useful.
- Continue through later gates in dependency order.
- Record the final output.
- Check the result against the corresponding Boolean expression or truth table.
A Reliable Procedure for Building a Circuit from an Expression
- Identify the innermost Boolean operations.
- Create one gate for each operation.
- Connect the appropriate input variables to those gates.
- Use each gate output as the input to the next required operation.
- Continue until the final output is produced.
- Verify the circuit with selected input assignments or a full truth table.
A Reliable Procedure for Designing from a Truth Table
- Identify the input variables and output column.
- Find the rows where the output equals \(1\).
- Write a minterm for each true row.
- OR the minterms to form canonical DNF.
- Simplify the Boolean expression if possible.
- Translate the simplified expression into gates.
- Verify the circuit against the original truth table.
Example: Full Circuit Analysis Workflow
Suppose a circuit represents
\[ y=\neg(p\land q)\lor r. \]Let
\[ p=1,\qquad q=1,\qquad r=0. \]First,
\[ p\land q=1. \]Then,
\[ \neg(p\land q)=0. \]Finally,
\[ 0\lor0=0. \]Therefore,
\[ \boxed{y=0}. \]Example: Full Design Workflow
Design a circuit whose output is \(1\) exactly when \(p=1\) and \(q=0\).
The required minterm is
\[ p\land\neg q. \]Therefore, the circuit requires:
- a NOT gate on \(q\);
- an AND gate combining \(p\) and \(\neg q\).
The Boolean function is
\[ \boxed{y=p\land\neg q}. \]Practice 1: NOT Gate
If the input to a NOT gate is \(1\), what is the output?
Practice 2: AND Gate
Evaluate
\[ 1\land0. \]Practice 3: OR Gate
Evaluate
\[ 0\lor1. \]Practice 4: XOR Gate
Evaluate
\[ 1\oplus1. \]Practice 5: NAND Gate
Evaluate
\[ \neg(1\land1). \]Practice 6: Read a Circuit Expression
A first gate computes
\[ a=p\lor q. \]A NOT gate computes
\[ b=\neg r. \]A final AND gate combines \(a\) and \(b\).
Write the complete Boolean expression.
Practice 7: Half-Adder
For
\[ p=1,\qquad q=1, \]find the half-adder sum bit \(S\) and carry bit \(C\).
Practice 8: Simplify a Circuit Function
Simplify
\[ (p\land q)\lor(p\land\neg q). \]Practice 9: Two-Level DNF Circuit
How many first-level AND terms appear in
\[ (p\land q)\lor(\neg p\land r)\lor(q\land r)? \]Practice 10: Multiplexer
For
\[ y=(\neg s\land a)\lor(s\land b), \]what does \(y\) equal when \(s=0\)?
Practice Answers
Practice 1
\[ \boxed{0}. \]Practice 2
\[ \boxed{1\land0=0}. \]Practice 3
\[ \boxed{0\lor1=1}. \]Practice 4
\[ \boxed{1\oplus1=0}. \]Practice 5
\[ 1\land1=1, \]so
\[ \boxed{\neg(1\land1)=0}. \]Practice 6
\[ \boxed{(p\lor q)\land\neg r}. \]Practice 7
The sum bit is
\[ S=1\oplus1=0. \]The carry bit is
\[ C=1\land1=1. \]Therefore,
\[ \boxed{S=0,\qquad C=1}. \]Practice 8
Factor \(p\):
\[ p\land(q\lor\neg q). \]Since
\[ q\lor\neg q=T, \]we get
\[ \boxed{p}. \]Practice 9
There are three conjunction terms:
\[ p\land q, \] \[ \neg p\land r, \]and
\[ q\land r. \]Therefore,
\[ \boxed{3}. \]Practice 10
If \(s=0\), then
\[ \neg s=1. \]Therefore,
\[ y=(1\land a)\lor(0\land b) = a\lor0 = a. \]Thus,
\[ \boxed{y=a}. \]What to Remember
- Logic gates implement Boolean operations.
- NOT, AND, OR, XOR, NAND, NOR, and XNOR each have distinct truth behavior.
- Boolean expressions, truth tables, and circuits can describe the same system.
- Circuits should be evaluated from inputs through intermediate gates to outputs.
- Combinational circuits depend only on current inputs.
- Equivalent Boolean expressions produce equivalent circuit behavior.
- Boolean simplification can reduce gate count and circuit depth.
- NAND and NOR are universal gates.
- DNF naturally maps to AND-then-OR circuits, while CNF maps to OR-then-AND circuits.
- Half-adders and full-adders show how logic gates perform binary arithmetic.
The central habit is to move fluently among Boolean expressions, truth tables, and gate networks while preserving the same input-output behavior.
Where We Go Next
Logic gates and combinational circuits react only to current inputs. Many systems, however, must remember a current state and change that state in response to inputs.
The next lesson, Finite-State Machines, introduces systems whose behavior depends on both present input and stored state.