EST2501 Digital Fundamentals (2): Logical Fundamentals

Posted on 2026-05-23 Edited on 2026-09-29 In Exploration Word count in article: 5.6k Reading time ≈ 20 mins.

This chapter covers basic concepts of logic gates and the art of logic circuit design and simplication. In my own opinion, this part should be learned together with Discrete Mathematics.

Collections of EST2501 Digital Electronics notes:

Digital Fundamentals;

Logical Fundamentals (this article);

Combinational Logic Circuit;

Sequential Logic Circuit.

You can find a general introduction to this course in the first article of this series.

Gate

Gate is a simple electronic circuit that realized a logical operation.

Basic Logic Gates

Name	Logical Expression
Inverter (NOT) gate
AND gate
OR gate
NAND gate
NOR gate
Exclusive-OR (XOR) gate
XNOR gate

The negation indicator is a “bubble” () that indicates inversion or complementation when it appears on the input or output of any logic element.

Negative-OR is a logic gate that performs the OR operation followed by a NOT operation. It can be represented by the logical expression , which is equivalent to the NAND gate.

Negative-AND is a logic gate that performs the AND operation followed by a NOT operation. It can be represented by the logical expression , which is equivalent to the NOR gate.

Truth table is trivial and can be easily derived from the logical expression, so it is not listed here.

Gate Implementations

This section presents a very simple structural model of gates based on an idealized device called a logic switch.

A logic switch is a three-terminal device that is used to control the connection of two points in a circuit. The three terminals are called the control terminal, the input terminal, and the output terminal.

A logic switch can be in one of two states: open or closed. The open state means that the input terminal is not connected to the output terminal, while the closed state means that the switch conducts between its data terminals.

By the status when the control terminal is not activated, or normal state, the logic switch can be divided into two types: normally open (NO, or active-high) and normally closed (NC, or active-low) logic switches.

Ideal logic switch is a logic switch that has zero resistance when it is closed and infinite resistance when it is open. However, in practice, there is always some resistance when the switch is closed and some leakage current when the switch is open. Also, time required to change states is greater than zero.

Passive pullup and active pullup are techniques used to ensure that the input terminal of a logic switch is held at a known voltage level when the control terminal is not activated.

Integrated Circuit Technology

Supply Voltage and Power Dissipation

For TTL (Transistor-Transistor Logic) technology, the supply voltage is typically 5V, and the power dissipation is around 10mW per gate. For CMOS (Complementary Metal-Oxide-Semiconductor) technology, the supply voltage can range from 3.3V to 5V, and the power dissipation is much lower than TTL, typically in the range of microwatts to milliwatts per gate.

Below are the input and output logic levels for TTL. The input logic level is the voltage level that is recognized as a HIGH or LOW signal by the gate, while the output logic level is the voltage level that the gate produces when it outputs a HIGH or LOW signal.

Below are the input and output logic levels for different voltage levels in CMOS technology.

Noise margin is the difference between the input logic level and the output logic level of a gate. It is a measure of how much noise can be tolerated by the gate without causing an error in the output.

CMOS Technology

Complementary Metal-Oxide-Semiconductor (CMOS) technology is based on the use of both p-type and n-type MOSFETs (Metal-Oxide-Semiconductor Field-Effect Transistors) to implement logic gates.

Take -channel MOSFET as an example. When the control terminal is at a HIGH voltage level, the n-channel conducts between the input and output terminals, i.e., when where is the threshold voltage.

Similarly, for -channel MOSFET, it conducts when the control terminal is at a LOW voltage level, i.e., when .

TTL Technology

Transistor-Transistor Logic (TTL) technology is based on the use of bipolar junction transistors (BJTs) to implement logic gates. If is greater than the threshold voltage (usually around 0.7V), the transistor is in the active region and conducts between the collector and emitter terminals, i.e., when .

Although ideally an inverter should only have one transistor, in practice, it is implemented with multiple transistors to achieve better performance and noise margin.

TTL vs CMOS

Power. Even the most power-efficient Bipolar family listed (ALS at 1.4 mW, or 1400 µW) consumes over 500 times more quiescent power than the highest-consuming CMOS family listed (HC/AHC at 2.75 µW). CMOS is heavily favored for low-power or battery-operated designs.

Speed. Historically, Bipolar TTL was much faster than early CMOS, but the table shows advanced CMOS has closed the gap.

Output drive. BiCMOS effectively combines the high output current driving capabilities of Bipolar transistors with the lower power characteristics of CMOS, making it ideal for bus interfacing or driving heavy loads.

The propagation delay time is the time it takes for a change in the input of a gate to produce a change in the output. TTL gates typically have a propagation delay of around 10 nanoseconds, while CMOS gates can have a propagation delay as low as 1 nanosecond.

	TTL	CMOS
DC Supply Voltage (Vcc)	5V	5V,3.3V
Switching Speed	FAST	slow
Propagation Delay	FAST	slow
Power Dissipation	HIGH	low
Noise Immunity	low	HIGH
Integrated Complexity	HIGH	low
Unused pin	Open	Connect to +V

Boolean Algebra and Logic Simplification

Sum term. A sum term is the sum of literals, such as , , etc. A sum term is false if all literals are false, and true otherwise.

Product term. A product term is the product of literals, such as , , etc. A product term is true if all literals are true, and false otherwise.

Operation Laws

De Morgan’s Theorems

Here is another important theorem, which will be refered again in the simplicaton of product-of-sum expression: .

Standard Forms

Sum of Products (SOP). A Boolean expression is in SOP form if it is a sum of product terms. For example, is in SOP form.
Product of Sums (POS). A Boolean expression is in POS form if it is a product of sum terms. For example, is in POS form.
Standard sum of products (SSP). A Boolean expression is in SSP form if it is a sum of product terms, and each product term contains all variables in either true or complemented form. For example, is in SSP form.
Standard product of sums (SPS). A Boolean expression is in SPS form if it is a product of sum terms, and each sum term contains all variables in either true or complemented form. For example, is in SPS form.

2 rules are often used in the conversioin: and .

Truth table is an important tool for converting between different forms of Boolean expressions. For SOP form, we can identify the minterms (product terms) that correspond to the rows of the truth table where the output is 1. For POS form, we can identify the maxterms (sum terms) that correspond to the rows of the truth table where the output is 0.

The index of a minterm or maxterm is the decimal equivalent of the binary representation of the input variables in the truth table. For example, for 3 variables , , and , the minterm corresponds to the binary input 101, which has an index of 5 (). The maxterm corresponds to the binary input 010, which has an index of 2 ().

Karnaugh Map

A Karnaugh Map (K-map), invented by Maurice Karnaugh in 1953, is a graphical method for simplifying Boolean expressions. It rearranges the truth table into a two-dimensional grid where adjacent cells differ by exactly one variable (Gray code ordering), allowing visual identification of terms that can be combined and eliminated.

Structure of K-Map

Each cell in a K-map corresponds to a minterm. The rows and columns are labeled using Gray code so that moving between any two adjacent cells (horizontally or vertically) changes exactly one variable. The top/bottom edges and left/right edges are also considered adjacent (the map wraps around like a torus).

2-Variable K-Map:

4-Variable K-Map:

Minimization of SOP Using K-Map

The goal of SOP minimization is to find a minimal sum-of-products expression. The procedure:

Plot the function: Place 1s in all cells corresponding to minterms where the function evaluates to 1.
Form prime implicants: Group adjacent 1s into the largest possible rectangular groups of size (). Each group must contain only 1s and must be a power of 2 in size (1, 2, 4, 8, …). Groups may wrap around edges.
Cover all 1s: Select a minimum set of prime implicants that covers every 1 in the map (essential prime implicants must be included).
Write the expression: Each selected group corresponds to a product term — variables that remain constant (same value) across the group are kept; variables that change (both 0 and 1 appear) are eliminated.

Rules for grouping: - Groups must be rectangular and contain cells. - Groups must be as large as possible (to eliminate more variables). - Overlapping groups are allowed and often necessary. - A cell may be covered by multiple groups (by the idempotent law: ). - Always include essential prime implicants (those covering a 1 not covered by any other prime implicant).

Minimization of POS Using K-Map

For POS minimization, the procedure is dual to SOP:

Plot the function: Place 0s in cells corresponding to maxterms where the function evaluates to 0.
Group adjacent 0s into the largest possible rectangular groups of size , same rules as SOP.
Write the expression: Each group corresponds to a sum term. For each group, identify variables that are constant — if a variable is 0 across the group, it appears uncomplemented in the sum term; if it is 1, it appears complemented. Variables that change are eliminated.
The final POS expression is the product of all sum terms.

Alternative method: Minimize the complement function in SOP form using 0s on the K-map, then take the complement using De Morgan’s theorem to obtain in POS form.

Relationship between SOP and POS on K-Map: The SOP form covers the 1s; the POS form covers the 0s. The choice depends on which yields a simpler expression — if the function has fewer 0s than 1s, POS minimization on 0s is more efficient.

Minimization with Don’t-Care Terms

A don’t-care term is an input combination that either never occurs in practice or for which the output value does not matter. Don’t-cares are denoted by or on the K-map.

The key insight: each don’t-care can be treated as either 0 or 1, whichever helps form larger groups. Different don’t-cares in the same map may be assigned different values.

Procedure for SOP with don’t-cares: 1. Plot 1s for minterms where , and s for don’t-care terms. 2. When grouping 1s, treat an as 1 only if it allows forming a larger group (one that would otherwise be impossible or smaller). Do not form groups consisting entirely of don’t-cares. 3. Any not used in a group is treated as 0.

Dimension-Reduced K-Map (Variable-Entered Map)

A Dimension-Reduced K-Map (also called a Variable-Entered Map, VEM) extends the standard K-map by allowing variables (or expressions) to be placed inside cells instead of just constants 0, 1, or X. This effectively compresses a higher-dimensional map into a lower-dimensional one, reducing the number of variables displayed in the grid structure.

Motivation: A 5- or 6-variable K-map becomes unwieldy. By “entering” one or more variables into the map cells, we can represent functions of more variables using a smaller grid.

Map entries and their meaning:

Entry	Meaning
0	Function is 0 regardless of entered variable(s)
1	Function is 1 regardless of entered variable(s)
	Function equals (1 when , 0 when )
	Function equals (1 when , 0 when )

Example: using a 2-variable map with entered

Decompose with respect to : - : evaluate for → → entries for - : evaluate for → → entries for

Construct the 2-variable VEM:



	1

Reading cell : gives minterm , so entry is .
Reading cell : both and give 1 (minterms ), so entry is .

Minimization using VEM:

The grouping rules extend naturally:

Cells with entry 1 can be grouped with other 1s just as in a standard K-map.
Cells with entry can be grouped with cells containing or 1 — the resulting term includes .
Cells with entry can be grouped with cells containing or 1 — the resulting term includes .
A cell with cannot be directly grouped with a cell containing (unless both are subsumed by a larger group covering both polarities).