Home › Physics › Modern Physics › Boolean Algebra and Digital Logic

Modern Physics

Boolean Algebra and Digital Logic

Boolean algebra is a branch of mathematics dealing with binary variables and logic operations used to analyze and simplify digital circuits. It forms the foundation of modern digital electronics, underpinning microprocessors, computer architecture, and gate-level logic design.

UP TGT ScienceUP PGT PhysicsStudy Notes + Practice

Scope and prerequisites

TGT core

Basic logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR), truth tables, symbols, and fundamental Boolean postulates and laws.

PGT extension

De Morgan's theorems, Karnaugh maps (K-maps) for simplification, Boolean expression minimization, realization of universal gates, and arithmetic circuits.

Prerequisites

Binary number system and number base conversions
Basic concepts of voltage levels in digital electronics (TTL and CMOS)
Set theory intersections and unions

Fundamental Postulates of Boolean Algebra

Boolean variables take only two discrete values: logic 0 (false/LOW) and logic 1 (true/HIGH).
The basic operations are logical addition (OR, denoted by +), logical multiplication (AND, denoted by · or juxtaposition), and complementation (NOT, denoted by an overbar).
The commutative laws state that A + $B = B + A$ and A · $B = B \cdot A$.

Basic Logic Gates and Truth Tables

The NOT gate (inverter) outputs the logical complement of its single input: Y = Ā.
The AND gate outputs HIGH (1) only when all its inputs are HIGH: $Y = A \cdot B$.
The OR gate outputs HIGH (1) if at least one of its inputs is HIGH: $Y = A + B$.

Universal Gates: NAND and NOR

A NAND gate is a combination of an AND gate followed by a NOT gate, with output $Y = (A \cdot B)̄$.
A NOR gate is a combination of an OR gate followed by a NOT gate, with output $Y = (A + B)̄$.
NAND and NOR gates are termed universal gates because any boolean function can be implemented using only NAND gates or only NOR gates.

De Morgan's Theorems

First Theorem: The complement of a sum is equal to the product of the complements, i.e., (A + B)̄ = Ā · B̄.
Second Theorem: The complement of a product is equal to the sum of the complements, i.e., (A · B)̄ = Ā + B̄.
These theorems are essential for converting sum-of-products (SOP) to product-of-sums (POS) forms and vice versa.

Derivations

Simplification of Boolean Expression using Boolean Postulates

Conditions: Simplify $Y = AB + A(B + C) + B(B + C)$

Distribute terms: $Y = AB + AB + AC + BB + BC$
Apply idempotent law (BB = B and AB + A$B = AB): Y = AB + AC + B + BC$
Apply absorption law on B + BC (since B + B$C = B): Y = AB + AC + B$
Apply absorption law on AB + B (since AB + $B = B): Y = B + AC$
Apply distributive law or consensus if applicable; final reduced form is $Y = B + AC$

Result: $Y = B + AC$

Realization of OR Gate using only NAND Gates

Conditions: Expression to implement: $Y = A + B using NAND logic$

Apply double complement to OR function: $Y = (A + B)̄̄$
Apply De Morgan's first theorem inside the inner complement: (A + B)̄ = Ā · B̄
Substitute back: $Y = (Ā \cdot B̄)̄$
Recognize that Ā is obtained by connecting input A to both terminals of a NAND gate, and similarly B̄.
The final output Y is obtained by feeding Ā and B̄ into a third NAND gate.

Result: Y = ((A \cdot A)' \cdot (B \cdot B)')'

Formula sheet

Formula / law	Equation	Variables and units	Conditions
AND Operation Law	$$A \cdot 0 = 0, \quad A \cdot 1 = A, \quad A \cdot A = A, \quad A \cdot A' = 0$$	A = Binary variable Dimensionless (Logic states)	Boolean algebra domain {0, 1}
OR Operation Law	$$A + 0 = A, \quad A + 1 = 1, \quad A + A = A, \quad A + A' = 1$$	A = Binary variable Dimensionless (Logic states)	Boolean algebra domain {0, 1}
Involution Law	$$(A')' = A$$	A = Binary variable Dimensionless	None
Commutative Laws	$$A + B = B + A, \quad A \cdot B = B \cdot A$$	A, B = Binary variables Dimensionless	None
Associative Laws	$$A + (B + C) = (A + B) + C, \quad A \cdot (B \cdot C) = (A \cdot B) \cdot C$$	A, B, C = Binary variables Dimensionless	None
Distributive Laws	$$A \cdot (B + C) = A \cdot B + A \cdot C, \quad A + (B \cdot C) = (A + B) \cdot (A + C)$$	A, B, C = Binary variables Dimensionless	None
De Morgan's First Theorem	$$(A + B)' = A' \cdot B'$$	A, B = Binary variables Dimensionless	None
De Morgan's Second Theorem	$$(A \cdot B)' = A' + B'$$	A, B = Binary variables Dimensionless	None

Graphs and experiments

Timing Diagram for Logic Gates

Draw: Square wave voltage pulses representing inputs A(t) and B(t) against time, with the corresponding output voltage pulse wave Y(t) for an AND or OR gate.

Interpret: Visualizes the propagation delay and real-time response of digital gates to changing input levels.

Exam use: Used in PGT questions to determine output waveforms given specific input pulse trains.

Transistor-Transistor Logic (TTL) NOT Gate Circuit

Draw: Circuit diagram featuring a multi-emitter npn transistor at the input stage followed by phase-splitter and totem-pole output driver transistors.

Interpret: Demonstrates how physical semiconductor devices implement digital inversion and voltage switching thresholds.

Exam use: Conceptual understanding of hardware implementation of Boolean NOT operations.

Karnaugh Map (K-map) Grid Structure

Draw: A 2-variable or 4-variable grid arranged in Gray code sequence (00, 01, 11, 10) to map minterms for Boolean minimization.

Interpret: Provides a pictorial method of grouping adjacent cells containing 1s to eliminate redundant literals.

Exam use: Tested in PGT numericals for minimizing complex SOP expressions.

Solved numericals

TGT core

Simplify the Boolean expression: $Y = AB'C + ABC' + ABC + A'BC$.

Group terms with common factors: $Y = AC(B' + B) + BC(A + A')$
Use the complement law (B' + B = 1 and A + A' = 1): $Y = AC(1) + BC(1)$
Simplify: $Y = AC + BC$
Factor out C: $Y = (A + B)C$

Answer: $Y = (A + B)C$

PGT extension

Find the dual of the Boolean expression: $X = AB + A'(B + C')$.

Recall that to find the dual of a Boolean expression, replace AND (.) with OR (+), OR (+) with AND (.), 0 with 1, and 1 with 0, leaving variables unchanged.
Original expression: $X = AB + A'(B + C')$
Replace '+' with '.' and '.' with '+': $X_dual = (A + B) \cdot (A' + (B \cdot C''))$
Note: Constants remain unchanged if present, variables retain their uncomplemented/complemented status.

Answer: $X_dual = (A + B)(A' + BC')$

PGT extension

Using De Morgan's theorems, simplify the expression $Y = ((A + B')' + C)'$.

Apply De Morgan's second theorem to the outer complement: $Y = (A + B')'' \cdot C'$
Apply involution law ((A + B')'' = A + B'): $Y = (A + B') \cdot C'$
Expand the expression: $Y = AC' + B'C'$

Answer: $Y = AC' + B'C'$

Assumptions and limitations

Assumption: Binary voltage levels are strictly categorized into two distinct states (Logic 0 and Logic 1) with instantaneous transitions. Limitation: Real physical circuits experience rise times, fall times, and propagation delays, and ambiguous voltage zones can cause erratic noise susceptibility.

Common misconceptions

Common error: Boolean addition (A + B) is equivalent to arithmetic addition (1 + 1 = 2).

Correct: Boolean addition represents logical OR, where 1 + 1 = 1.

Boolean algebra operates on a two-valued domain {0, 1} where maximum logical truth is 1.

Common error: The dual of an expression is the same as its complement.

Correct: The dual interchanges AND and OR operators, whereas the complement interchanges operators AND/OR and also inverts all variables (A to A').

Duality is based on operator interchange, while complementation applies De Morgan's laws fully.

Quick revision

Boolean algebra uses variables restricted to two states: 0 and 1, governed by OR (+), AND (.), and NOT (') operations.
AND Operation Law: A \cdot 0 = 0, \quad A \cdot 1 = A, \quad A \cdot A = A, \quad A \cdot A' = 0
OR Operation Law: A + 0 = A, \quad A + 1 = 1, \quad A + A = A, \quad A + A' = 1

Must remember

Boolean variables take only two discrete values: logic 0 ($0$) and logic 1 ($1$).
NAND and NOR gates are known as universal gates because any boolean function can be implemented using only NAND or only NOR gates.
De Morgan's First Theorem states that the complement of a sum is equal to the product of the complements: $(A + B)' = A' \cdot B'$.
De Morgan's Second Theorem states that the complement of a product is equal to the sum of the complements: $(A \cdot B)' = A' + B'$.
In Boolean algebra, logical addition satisfies $1 + 1 = 1$, unlike standard arithmetic addition.

Glossary

Logic GateAn idealized or physical electronic circuit implementing a certain boolean function.

Universal GateA gate like NAND or NOR that can be used to construct any arbitrary logic function.

Involution LawThe boolean law stating that the double complement of a variable returns the original variable, $(A')' = A$.

Sum-of-Products (SOP)An expression formed by ORing (summing) multiple ANDed terms (products).

AND Gate vs OR Gate

Feature	AND Gate	OR Gate
Boolean Operation	Logical Multiplication ($A \cdot B$)	Logical Addition ($A + B$)
Condition for HIGH Output	All inputs must be HIGH ($1$)	At least one input must be HIGH ($1$)
Output for inputs (0, 1)	0	1

Practice Quiz

Choose an option to reveal the explanation.

1. What is the output of the boolean expression $A + A \cdot B$?

Explanation: Using absorption law: $A + A \cdot B = A(1 + B) = A(1) = A$.

2. Which of the following gates are known as universal gates?

Explanation: NAND and NOR gates are termed universal gates because any boolean function can be implemented using only NAND gates or only NOR gates.

3. According to De Morgan's First Theorem, $(A + B)'$ is equal to:

Explanation: De Morgan's First Theorem states that the complement of a sum is equal to the product of the complements: $(A + B)' = A' \cdot B'$.

4. What does the Boolean operation $1 + 1$ evaluate to?

Explanation: Boolean addition represents logical OR, where $1 + 1 = 1$ because logic variables only take values in the domain $\{0, 1\}$.

5. Which logic gate outputs HIGH only when all its inputs are HIGH?

Explanation: The AND gate outputs HIGH ($1$) only when all its inputs are HIGH ($1$).

6. What is the result of the Involution Law in Boolean algebra, given by $(A')'$?

Explanation: The Involution Law states that double complementation yields the original variable, i.e., $(A')' = A$.

7. What is the output of an OR gate when inputs are $A = 0$ and $B = 1$?

Explanation: An OR gate outputs HIGH if at least one input is HIGH. Thus, $0 + 1 = 1$.

8. Which law states that $A + B = B + A$?

Explanation: The commutative law for logical addition states that $A + B = B + A$.

9. What is the Boolean expression for a NAND gate with inputs $A$ and $B$?

Explanation: A NAND gate combines an AND gate followed by a NOT gate, resulting in $Y = (A \cdot B)'$.

10. What does $A \cdot A'$ evaluate to in Boolean algebra?

Explanation: By the AND operation law, a variable multiplied by its complement is always $0$ ($A \cdot A' = 0$).

11. What is the dual expression of $A + 0 = A$?

Explanation: The dual is obtained by interchanging $+$ with $\cdot$ and $0$ with $1$. Thus, $A + 0 = A$ becomes $A \cdot 1 = A$.

12. Which theorem states that $(A \cdot B)' = A' + B'$?

Explanation: De Morgan's Second Theorem states that the complement of a product is equal to the sum of the complements: $(A \cdot B)' = A' + B'$.

13. What is the output of a NOT gate if the input is $0$?

Explanation: A NOT gate inverts its single input. If input is $0$, output $Y = 0' = 1$.

14. Which of the following represents the distributive law $A \cdot (B + C)$?

Explanation: The distributive law states that $A \cdot (B + C) = A \cdot B + A \cdot C$.

15. What is the value of $A + 1$ in Boolean algebra?

Explanation: By the OR operation law, anything ORed with $1$ yields $1$ ($A + 1 = 1$).

PYQ Patterns

These are pattern-based practice questions. Authentic year labels are only used when verified from a source.

1. The boolean expression $(A + B)(A + C)$ is equivalent to:

Explanation: Expanding the expression: $(A + B)(A + C) = A \cdot A + A \cdot C + B \cdot A + B \cdot C = A + A(C + B) + B \cdot C = A(1 + B + C) + B \cdot C = A + B \cdot C$.

2. Simplify the boolean expression $Y = A \cdot B + A \cdot B' + A' \cdot B$.

Explanation: Combine terms: $A \cdot B + A \cdot B' = A(B + B') = A(1) = A$. Then $A + A' \cdot B = (A + A')(A + B) = 1 \cdot (A + B) = A + B$.

3. What single logic gate is represented by the combination of an OR gate followed by a NOT gate?

Explanation: An OR gate followed by a NOT gate forms a NOR gate, with output $Y = (A + B)'$.

4. Find the complement of the function $F = A \cdot B' + A' \cdot B$.

Explanation: Using De Morgan's laws: $F' = (A \cdot B' + A' \cdot B)' = (A \cdot B')' \cdot (A' \cdot B)' = (A' + B)(A + B') = A \cdot A' + A \cdot B + A' \cdot B' + B \cdot B' = 0 + A \cdot B + A' \cdot B' + 0 = A \cdot B + A' \cdot B'$-wait, note that $(A' + B)(A + B') = A \cdot B + A' \cdot B'$ by expansion.

5. Which boolean expression is equivalent to the logic circuit output $Y = \overline{\overline{A} \cdot \overline{B}}$?

Explanation: Applying De Morgan's theorem to $Y = (A' \cdot B')' = (A')' + (B')' = A + B$. This is a realization of an OR gate using NAND logic (or De Morgan's form).

6. How many universal gates are minimally required to realize a NOT gate?

Explanation: A NOT gate can be implemented using a single NAND gate by tying its two inputs together: $(A \cdot A)' = A'$; similarly for a NOR gate: $(A + A)' = A'$.

Timed Topic Test

Attempt these questions under a ten-minute limit using a separate timer.

1. What is the canonical Sum-of-Products (SOP) form equivalent to the boolean expression $A + B'$?

Explanation: Expand missing variables: $A = A(B + B') = A \cdot B + A \cdot B'$. $B' = B'(A + A') = A \cdot B' + A' \cdot B'$. Combining them with logical OR and removing duplicates gives $A \cdot B + A \cdot B' + A' \cdot B'$.

2. The expression $AB + \overline{A}C + BC$ simplifies to:

Explanation: By the consensus theorem, the term $BC$ is redundant because it is formed by combining the variables $B$ and $C$ from $AB$ and $\overline{A}C$. Thus, $AB + \overline{A}C + BC = AB + \overline{A}C$.

3. What is the dual of the Boolean expression $A \cdot (B + C) = A \cdot B + A \cdot C$?

Explanation: To find the dual, interchange $\cdot$ with $+$ and $1$ with $0$ (or keep variables as is). Thus, $A \cdot (B + C) = A \cdot B + A \cdot C$ becomes $A + (B \cdot C) = (A + B) \cdot (A + C)$.

4. Which of the following expressions represents an Exclusive-OR (XOR) operation?

Explanation: An XOR gate outputs HIGH when inputs are different, represented by $Y = A \cdot B' + A' \cdot B$.

5. If a circuit has output $Y = (A' + B') \cdot (A + B)$, what is its simplified form?

Explanation: Note that $(A' + B') = (A \cdot B)'$ by De Morgan's law, and $(A + B) = (A' \cdot B')'$. Therefore, $Y = (A \cdot B)' \cdot (A' \cdot B')'$, which is the expression for an XOR gate ($A \cdot B' + A' \cdot B$).

6. In Boolean algebra, what is the simplification of $X + X'Y$?

Explanation: Using distributive and absorption laws: $X + X'Y = (X + X')(X + Y) = 1 \cdot (X + Y) = X + Y$.

7. Which gate combination is equivalent to an AND gate when only NOR gates are permitted?

Explanation: To get an AND gate using NOR gates: $A$ and $B$ are first inverted using NOR gates as NOT gates ($A' = (A+A)'$, $B' = (B+B)'$), and then fed into another NOR gate whose output is inverted or combined to yield $AB$. Specifically, $(A' + B')' = ((A+A)' + (B+B)')' = A \cdot B$.

8. What is the Boolean function represented by a 3-input NAND gate with inputs $A, B, C$?

Explanation: A 3-input NAND gate performs the AND operation on all inputs and then complements the result: $Y = (A \cdot B \cdot C)'$.

9. Which of the following is NOT a valid Boolean algebraic identity?

Explanation: The identity $A + A = 1$ is false; the correct idempotent law for addition is $A + A = A$. $A + A' = 1$ is the complement law.

10. Simplify the expression $Y = AB + A(B + C) + B(B + C)$.

Explanation: Expand terms: $AB + AB + AC + B + BC = AB + AC + B + BC$. Since $B + BC = B$ and $AB + B = B$, the expression reduces to $B + AC$.