Select Medium / माध्यम चुनें:

Eng (English) Beng (বাংলা) Hindi (हिन्दी)

WBB • Class XII • Computer Science • Ch 5

Estimated Time: 120 mins

Study Progress: In Progress

Boolean Algebra and Logic Gates

Boolean Algebra is the mathematical foundation of digital computer logic and electronic circuit design, formulated by George Boole in 1854 and applied to switching circuits by Claude Shannon in 1938. It operates on binary variables that assume one of two discrete truth values: 0 (False/Low) and 1 (True/High). This chapter covers the foundational postulates, algebraic identities, De Morgan's dual theorems, and the principle of duality. It examines basic logic gates (AND, OR, NOT), universal gates (NAND and NOR) and their complete functional realizations, and special arithmetic gates (XOR, XNOR). Students explore canonical Minterm (SOP) and Maxterm (POS) standard expressions, systematic algebraic and Karnaugh Map (K-Map) multi-variable minimization techniques involving Gray code grouping and Don't Care conditions, and the design of combinational computational building blocks including Half and Full Adders, Half and Full Subtractors, Multiplexers (MUX), Demultiplexers (DEMUX), Encoders, and Decoders.

Take Chapter CBT Test View All Chapters

Overview Core Concepts Syntax & Core Commands Solved Examples Common Traps Summary Self Check Take MCQ Test

Why This Chapter Matters

Every modern microprocessor, graphics processor, and digital microcontroller consists of billions of interconnected transistors functioning as logic gates. Mastery of Boolean algebra and circuit minimization directly enables computer scientists and hardware engineers to reduce silicon die area, minimize propagation delay, eliminate static and dynamic hazards, and optimize power consumption in VLSI design. Understanding combinatorial circuits forms the crucial bridge connecting abstract mathematical algorithms with physical computer architecture and arithmetic logic units (ALUs).

Chapter Roadmap & Progression

1 Module 1: Boolean Constants, Variab...

2 Module 2: Fundamental Boolean Laws,...

3 Module 3: Logic Gates — Basic, Univ...

4 Module 4: Canonical SOP & POS Forms...

5 Module 5: Karnaugh Map (K-Map) Opti...

6 Module 6: Combinational Logic Circu...

Complete Concept Guide (100% Curriculum Coverage)

Module 1: Boolean Constants, Variables, Truth Tables & Fundamental Postulates

1.1 Binary Logic Foundations & Huntington's Postulates

Boolean Algebra is an algebraic structure defined over a two-element set $B = \{0, 1\}$ equipped with two binary operations: Logical Addition (OR, denoted by $+$) and Logical Multiplication (AND, denoted by $\cdot$), and one unary operation: Logical Inversion (NOT, denoted by $''$ or $\overline{A}$).

Operation	Symbol & Expression	Mathematical Definition	Electronic Switching Analogy
Logical NOT (Inversion)	$Y = A'$ or $\overline{A}$	$0' = 1$, $1' = 0$	Normally-closed switch in parallel with the load.
Logical AND (Conjunction)	$Y = A \cdot B$	Output is 1 if and only if ALL inputs are 1; otherwise 0.	Switches connected in series (both must close).
Logical OR (Disjunction)	$Y = A + B$	Output is 1 if AT LEAST ONE input is 1; 0 only when all are 0.	Switches connected in parallel (either path conducts).

1.2 Truth Tables for Primary Operations

A Truth Table lists all possible combinations of binary inputs and their corresponding logical output. For $n$ binary variables, the truth table contains exactly $2^n$ distinct rows:

Input A	Input B	NOT A ($A'$)	AND ($A \cdot B$)	OR ($A + B$)
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

Core Axioms of 0 and 1:

Identity Elements: $A + 0 = A$ (0 is the additive identity), and $A \cdot 1 = A$ (1 is the multiplicative identity).
Null Elements (Dominance): $A + 1 = 1$ (1 dominates OR), and $A \cdot 0 = 0$ (0 dominates AND).

Module 2: Fundamental Boolean Laws, Distributive Theorems, Duality & De Morgan's Laws

2.1 Master Summary of Boolean Algebraic Laws

Every Boolean law exists as a dual pair under the Principle of Duality:

Law Name	OR Form (Dual Form 1)	AND Form (Dual Form 2)	Description
Idempotent Law	$A + A = A$	$A \cdot A = A$	Repeating an input does not alter the output.
Involution Law	$(A')' = A$ (Double Inversion)		Inverting a variable twice yields original value.
Complementarity Law	$A + A' = 1$	$A \cdot A' = 0$	Variable paired with its complement.
Commutative Law	$A + B = B + A$	$A \cdot B = B \cdot A$	Order of binary operands is irrelevant.
Associative Law	$A + (B + C) = (A + B) + C$	$A(BC) = (AB)C$	Grouping of identical operations can be varied.
Distributive Law	$A \cdot (B + C) = AB + AC$	$A + (BC) = (A + B)(A + C)$	Crucial: Second distributive law does NOT hold in ordinary algebra!
Absorption Law	$A + AB = A$	$A(A + B) = A$	Redundant terms absorbed: $A + A'B = A + B$.
Consensus Theorem	$AB + A'C + BC = AB + A'C$	$(A+B)(A'+C)(B+C) = (A+B)(A'+C)$	Third term $BC$ is redundant consensus.

2.2 De Morgan's Laws & Principle of Duality

De Morgan's theorems describe the fundamental mathematical relationship between conjunction, disjunction, and complementation:

First Law: The complement of a logical sum equals the logical product of the complements: $(A + B)' = A' \cdot B'$. General form: $(A_1 + A_2 + \dots + A_n)' = A_1' \cdot A_2' \cdot \dots \cdot A_n'$.
Second Law: The complement of a logical product equals the logical sum of the complements: $(A \cdot B)' = A' + B'$. General form: $(A_1 \cdot A_2 \cdot \dots \cdot A_n)' = A_1' + A_2' + \dots + A_n'$.
Principle of Duality: Any valid Boolean identity remains valid if all $+$ operators are replaced by $\cdot$, all $\cdot$ operators by $+$, and all 0s and 1s are interchanged, keeping literal variables unchanged.

Rigorous Proof of Distributive Law $A + BC = (A + B)(A + C)$:

$\text{RHS} = (A + B)(A + C) = A \cdot A + A \cdot C + B \cdot A + B \cdot C$

$= A + AC + AB + BC \quad [\because A \cdot A = A]$

$= A(1 + C + B) + BC = A(1) + BC = A + BC = \text{LHS} \quad \text{[Q.E.D.]}$

Module 3: Logic Gates — Basic, Universal Realization & Derived Gates

3.1 Universal Logic Gates: NAND and NOR Realization

A gate is called a Universal Gate if ANY arbitrary Boolean function can be implemented solely using instances of that single gate type without requiring any other gate. Both NAND and NOR are universal gates.

Target Operation	Realization using ONLY NAND Gates	Min NAND Count	Realization using ONLY NOR Gates	Min NOR Count
NOT ($A'$)	Tie both inputs together: $(A \cdot A)' = A'$	1	Tie both inputs together: $(A + A)' = A'$	1
AND ($AB$)	NAND followed by a NAND inverter: $((AB)')' = AB$	2	Invert inputs first, then NOR: $(A' + B')' = (A')'(B')' = AB$	3
OR ($A+B$)	Invert inputs first, then NAND: $(A' \cdot B')' = A + B$	3	NOR followed by a NOR inverter: $((A + B)')' = A + B$	2
XOR ($A \oplus B$)	Standard 4-gate cross-coupled architecture	4	5-gate NOR configuration	5
XNOR ($A \odot B$)	5-gate NAND configuration	5	4-gate NOR configuration	4

3.2 Derived Arithmetic Gates: XOR and XNOR

XOR Gate (Exclusive-OR): Expression $Y = A \oplus B = A'B + AB'$. The output is 1 when an odd number of inputs are 1 (inequality detector). Used directly in binary adders and parity generators.
XNOR Gate (Equivalence Gate): Expression $Y = A \odot B = AB + A'B' = (A \oplus B)'$. The output is 1 when both inputs are identical (equality detector / coincidence circuit).

Module 4: Canonical SOP & POS Forms and Standard Boolean Expressions

4.1 Minterms (SOP) vs. Maxterms (POS)

Any Boolean function can be expressed uniquely in canonical standard forms where every product or sum term contains all independent variables:

Feature	Minterm / Canonical SOP (Sum of Products)	Maxterm / Canonical POS (Product of Sums)
Term Structure	Product of all variables (e.g., $A'BC$).	Sum of all variables (e.g., $A + B' + C$).
Variable Designation	Uncomplemented literal = 1, Complemented literal = 0.	Uncomplemented literal = 0, Complemented literal = 1.
Truth Table Mapping	Designated by rows where function output $F = 1$.	Designated by rows where function output $F = 0$.
Standard Shorthand Notation	$F(A, B, C) = \sum m(1, 3, 5, 7)$	$F(A, B, C) = \prod M(0, 2, 4, 6)$

Complementary Duality Rule: If an $n$-variable function has SOP form $F = \sum m(k_1, k_2, \dots)$, its canonical POS form is given by the exact index complement: $F = \prod M(\text{indices not in SOP})$. Furthermore, $F' = \sum m(\text{missing indices}) = \prod M(k_1, k_2, \dots)$.

Module 5: Karnaugh Map (K-Map) Optimization & Minimization

5.1 Gray Code Structure & Cell Adjacency

A Karnaugh Map (K-Map) is a graphical representation of a Boolean truth table arranged as a grid where adjacent cells differ by exactly ONE bit. This single-bit adjacency is achieved through Gray Code indexing ($00, 01, 11, 10$), allowing algebraic terms to combine via $X + X' = 1$.

Variables ($n$)	Cell Count ($2^n$)	Row & Column Indexing	Wrap-around Adjacencies
2 Variables ($A, B$)	4 cells	$A \in \{0, 1\}$, $B \in \{0, 1\}$	Simple edge adjacency
3 Variables ($A, B, C$)	8 cells (2 rows × 4 cols)	Row $A \in \{0, 1\}$, Col $BC \in \{00, 01, 11, 10\}$	Leftmost column (00) is adjacent to rightmost column (10).
4 Variables ($A, B, C, D$)	16 cells (4 rows × 4 cols)	Row $AB \in \{00, 01, 11, 10\}$, Col $CD \in \{00, 01, 11, 10\}$	Both outer columns and top/bottom rows wrap around; 4 outer corners form a valid Quad.

5.2 Systematic Grouping Rules & Don't Care Conditions

Powers of Two: Groups must contain $1, 2, 4, 8,$ or $16$ contiguous 1s (never 3, 5, or 6).
Variable Elimination:
- Pair (group of 2): Eliminates 1 variable.
- Quad (group of 4): Eliminates 2 variables.
- Octet (group of 8): Eliminates 3 variables.
Don't Care Conditions ($d$ or $X$): Input combinations that can never occur or whose output does not matter (e.g., BCD invalid states 10 to 15). Don't Cares may be treated as 1 if they help form a larger power-of-two group, or ignored as 0 otherwise.

Module 6: Combinational Logic Circuits — Adders, Subtractors, MUX, DEMUX & Decoders

6.1 Binary Arithmetic Circuits: Adders and Subtractors

Combinational circuits produce outputs that depend strictly on the instantaneous values of the inputs, without memory or feedback loops:

Circuit	Inputs	Output Equations	Gate Implementation
Half Adder	$A, B$ (2 bits)	$\text{Sum } S = A \oplus B$ $\text{Carry } C = A \cdot B$	1 XOR gate + 1 AND gate
Full Adder	$A, B, C_{in}$ (3 bits)	$\text{Sum } S = A \oplus B \oplus C_{in}$ $C_{out} = AB + C_{in}(A \oplus B)$	2 Half Adders + 1 OR gate
Half Subtractor	$A, B$ (2 bits)	$\text{Difference } D = A \oplus B$ $\text{Borrow } B_{out} = A' \cdot B$	1 XOR gate + 1 NOT gate + 1 AND gate
Full Subtractor	$A, B, B_{in}$ (3 bits)	$\text{Difference } D = A \oplus B \oplus B_{in}$ $B_{out} = A'B + (A \oplus B)'B_{in}$	2 Half Subtractors + 1 OR gate

6.2 Data Routing: Multiplexers, Demultiplexers, Decoders & Encoders

Multiplexer (MUX - Data Selector): Routes one of $2^n$ input data lines to a single output line based on $n$ binary selection lines. Example: 4-to-1 MUX requires 2 select lines ($S_1, S_0$), where $Y = S_1'S_0'I_0 + S_1'S_0I_1 + S_1S_0'I_2 + S_1S_0I_3$.
Demultiplexer (DEMUX - Data Distributor): Takes 1 input line and directs it to one of $2^n$ possible output channels based on $n$ select lines.
Decoder: Converts an $n$-bit coded input into a maximum of $2^n$ distinct active outputs. A 3-to-8 line decoder (e.g., 74LS138) with active-low outputs is standard for memory address decoding.
Encoder: Performs the reverse operation of a decoder, converting one of $2^n$ input lines into an $n$-bit binary code (e.g., 8-to-3 Priority Encoder).

Key Programming Syntax, Statements & Translator Rules

De Morgan's Dual Laws (Algebraic Expressions)

$$\overline{A + B} = \overline{A} \cdot \overline{B} \quad \text{and} \quad \overline{A \cdot B} = \overline{A} + \overline{B}$$

Boolean Distributive Laws (Dual Pair)

$$A \cdot (B + C) = AB + AC \quad \text{and} \quad A + (BC) = (A + B)(A + C)$$

Karnaugh Map Variable Elimination Rule

$$\text{Eliminated Variables} = k \quad \text{for a group of } 2^k \text{ adjacent cells in an } n\text{-variable map}$$

Full Adder Output Equations

$$S = A \oplus B \oplus C_{\text{in}}, \quad C_{\text{out}} = AB + BC_{\text{in}} + AC_{\text{in}} = AB + C_{\text{in}}(A \oplus B)$$

Multiplexer Input-Select Line Relation

$$2^n = I \implies n = \log_2(I)$$

Shannon's Expansion Theorem

$$f(x_1, x_2, \dots, x_n) = x_1 \cdot f(1, x_2, \dots, x_n) + x_1' \cdot f(0, x_2, \dots, x_n)$$

Conceptual Solved Examples & Case Studies

Example 1

Prove algebraically using Boolean postulates that $A + A'B = A + B$. State the name of the theorem used.

Step-by-Step Solution:

Solution:

Using the Second Distributive Law, which states that $X + YZ = (X + Y)(X + Z)$:

$\text{LHS} = A + A'B = (A + A')(A + B)$

By the Complementarity Law, $A + A' = 1$:

$= 1 \cdot (A + B)$

By the Identity Law of multiplication, $1 \cdot X = X$:

$= A + B = \text{RHS} \quad \text{[Proved]}$

Theorem Name: This identity is known as the Redundant Literal Rule (or simplified Absorption Theorem).

Example 2

Find the dual of the Boolean expression: $(A + B')(B + C') = AC' + B'$. Is this expression self-dual? Explain with reasons.

Step-by-Step Solution:

Solution:

Step 1: Finding the Dual Expression

According to the Principle of Duality, we obtain the dual by:

Replacing all OR operators ($+$) with AND operators ($\cdot$).
Replacing all AND operators ($\cdot$) with OR operators ($+$).
Leaving literals/complements completely unchanged.

Given expression: $(A + B') \cdot (B + C') = (A \cdot C') + B'$

Dual expression:

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

Step 2: Self-Dual Check

A Boolean function is self-dual if and only if its dual expression is logically identical to the original function. Here, the dual $(AB' + BC')$ is not algebraically equivalent to $(A + B')(B + C')$. Hence, the given expression is NOT self-dual.

Example 3

State De Morgan's First and Second Laws. Prove De Morgan's First Law for two variables using a complete Truth Table.

Step-by-Step Solution:

Solution:

Statements:

First Law: $(A + B)' = A' \cdot B'$ (The complement of a sum equals the product of the individual complements).
Second Law: $(A \cdot B)' = A' + B'$ (The complement of a product equals the sum of the individual complements).

Truth Table Proof of First Law:

A	B	A + B	(A + B)' [Col 4]	A'	B'	A' · B' [Col 7]
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Since the entries in Column 4 $(A + B)'$ and Column 7 $A' \cdot B'$ are identical for all possible input combinations $(1, 0, 0, 0)$, the theorem is rigorously proved.

Example 4

(a) Why are NAND and NOR gates called Universal Gates? (b) Show how to realize an AND gate and an OR gate using ONLY 2-input NAND gates with neat circuit expressions.

Step-by-Step Solution:

Solution:

(a) Definition of Universal Gate:

NAND and NOR gates are called Universal Gates because any basic logic function (NOT, AND, OR) or any arbitrary complex digital circuit can be completely synthesized and fabricated using only that single type of gate, without requiring any other discrete gates.

(b) Realization of AND Gate using NAND Gates:

To obtain $AB$, we first pass inputs $A$ and $B$ through a NAND gate to get $(AB)'$. Then we feed this output into a second NAND gate configured as an inverter (both inputs tied together):

$\text{Output } Y = ((AB)')' = AB$

Requirement: Exactly 2 NAND gates.

Realization of OR Gate using NAND Gates:

By De Morgan's Second Law: $A + B = (A' \cdot B')'$. Therefore:

Invert $A$ using a NAND gate: $A' = (A \cdot A)'$.
Invert $B$ using a NAND gate: $B' = (B \cdot B)'$.
Feed $A'$ and $B'$ into a third NAND gate: $Y = (A' \cdot B')' = (A')' + (B')' = A + B$.

Requirement: Exactly 3 NAND gates.

Example 5

Simplify the 4-variable Boolean function using a Karnaugh Map (K-Map): $F(A, B, C, D) = \sum m(0, 2, 5, 7, 8, 10, 13, 15)$. Write the minimal SOP expression and state each grouping clearly.

Step-by-Step Solution:

Solution:

Step 1: Cell Mapping in 4-Variable K-Map (16 Cells)

Row indices $AB \in \{00, 01, 11, 10\}$; Column indices $CD \in \{00, 01, 11, 10\}$:

Row 00: $m_0$ (cell 0), $m_2$ (cell 2) have 1s.
Row 01: $m_5$ (cell 5), $m_7$ (cell 7) have 1s.
Row 11: $m_{13}$ (cell 13), $m_{15}$ (cell 15) have 1s.
Row 10: $m_8$ (cell 8), $m_{10}$ (cell 10) have 1s.

Step 2: Grouping Identification

Quad 1 (Four Corners - Corner Adjacency): Cells $\{m_0, m_2, m_8, m_{10}\}$.
Rows 00 and 10 share $B = 0$ ($B'$).
Columns 00 and 10 share $D = 0$ ($D'$).
Term produced: $B'D'$.
Quad 2 (Middle Block): Cells $\{m_5, m_7, m_{13}, m_{15}\}$.
Rows 01 and 11 share $B = 1$ ($B$).
Columns 01 and 11 share $D = 1$ ($D$).
Term produced: $BD$.

Step 3: Minimal SOP Boolean Expression

$F(A, B, C, D) = B'D' + BD = B \odot D = (B \oplus D)'$

All 8 minterms are covered by exactly two Quads. The function reduces to an equivalence (XNOR) relationship between variables $B$ and $D$.

Example 6

(a) Design a Full Adder circuit using TWO Half Adders and ONE OR gate. (b) Write the truth table for the Full Adder. (c) Derive the algebraic expressions for Sum ($S$) and Carry Out ($C_{out}$). (d) Why is a Half Adder insufficient for adding multi-bit binary numbers?

Step-by-Step Solution:

Solution:

(a) Truth Table for Full Adder:

A	B	Cin	Sum (S)	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

(b) Algebraic Equations & Two Half Adders Architecture:

Half Adder 1 (HA-1): Inputs $A, B$.
Intermediate Sum $S_1 = A \oplus B$
Intermediate Carry $C_1 = A \cdot B$
Half Adder 2 (HA-2): Inputs $S_1, C_{in}$.
Final Sum: $\mathbf{S = S_1 \oplus C_{in} = A \oplus B \oplus C_{in}}$
Intermediate Carry $C_2 = S_1 \cdot C_{in} = (A \oplus B) \cdot C_{in}$
OR Gate: Combines the two carries:
$\mathbf{C_{out} = C_1 + C_2 = AB + C_{in}(A \oplus B)}$

(c) Why a Half Adder is Insufficient for Multi-bit Addition:

A Half Adder has only two input terminals ($A$ and $B$). It has no provision to accept an incoming carry bit ($C_{in}$) generated by the preceding less significant bit position. Hence, in multi-bit parallel ripple adders, a Half Adder can only be used at the least significant bit (LSB) position, while all subsequent higher bit columns strictly require Full Adders.

Common Misconceptions & Examiner Traps

Common Misconception

Applying ordinary algebra assumptions to Boolean addition, such as writing A + A = 2A or 1 + 1 = 2.

Scientific Reality & Correction

In Boolean algebra, addition represents logical OR, where A + A = A (Idempotent Law) and 1 + 1 = 1 (Bounded Dominance).

Common Misconception

Forming K-Map groups with 3, 5, or 6 cells.

Scientific Reality & Correction

Groups in a Karnaugh Map MUST contain powers of two cells (1, 2, 4, 8, 16) to ensure proper literal cancellation via Gray code.

Common Misconception

Confusing Minterm (SOP) and Maxterm (POS) binary representations.

Scientific Reality & Correction

In Minterms (SOP), an uncomplemented variable represents binary 1 and complemented represents 0. In Maxterms (POS), an uncomplemented variable represents binary 0 and complemented represents 1.

Common Misconception

Complementing literal variables when taking the Dual of a Boolean expression.

Scientific Reality & Correction

The Principle of Duality only interchanges operators (+ ↔ ·) and constants (0 ↔ 1). Literals (A, B', C) must remain completely untouched.

Common Misconception

Believing a Half Adder can be cascaded directly to construct a multi-bit binary ripple adder.

Scientific Reality & Correction

A Half Adder lacks a third carry-in (Cin) input. Cascaded multi-bit addition requires Full Adders for all bit positions except possibly the LSB.

Visual Learning & Conceptual Map

Chapter Summary & 10 Key Takeaways

Takeaway 1

Boolean algebra operates on binary variables restricted to two states (0 and 1) under AND, OR, and NOT operations.

Takeaway 2

Huntington's postulates and fundamental laws form the axiomatic foundation for algebraic logic circuit minimization.

Takeaway 3

De Morgan's Laws convert sum complements into product complements and vice versa, enabling seamless NOR/NAND conversion.

Takeaway 4

The Principle of Duality guarantees that interchanging AND/OR and 0/1 preserves the truth validity of any Boolean theorem.

Takeaway 5

NAND and NOR gates are universal because any logical function can be constructed exclusively using either gate type.

Takeaway 6

XOR (exclusive inequality) and XNOR (coincidence equality) gates serve as essential building blocks for binary arithmetic and parity checkers.

Takeaway 7

Canonical SOP is a sum of minterms (output 1s), while canonical POS is a product of maxterms (output 0s).

Takeaway 8

Karnaugh Maps utilize Gray code indexing to place single-bit changes adjacent, enabling systematic visual grouping in powers of two.

Takeaway 9

Don't Care conditions (X) represent impossible or irrelevant input states that can be treated as 1 to expand groups or 0 to ignore them.

Takeaway 10

Combinational circuits (Adders, Subtractors, MUX, DEMUX, Encoders, Decoders) have memoryless outputs determined strictly by instantaneous inputs.

Check Your Understanding (Diagnostic Practice Questions)

Diagnostic questions testing core conceptual clarity. Answers are hidden initially — solve each problem first, then click to reveal the step-by-step verified solution.

What is the minimum number of 2-input NAND gates required to implement a 2-input XOR gate?

Reveal Answer & Explanation

Answer: Exactly 4 NAND gates are required to implement a 2-input XOR gate.
Recall the standard cross-coupled 4-gate NAND architecture for A'B + AB'.

If a Boolean function in 3 variables has the canonical POS form F(A, B, C) = ∏M(0, 2, 4, 6), what is its canonical SOP expression?

Reveal Answer & Explanation

Answer: F(A, B, C) = ∑m(1, 3, 5, 7) = C.
SOP consists of the complement set of minterm indices from the total range 0 to 7.

In a 4-variable K-Map, if an Octet (group of 8 cells) is formed, how many variables are eliminated from the resulting product term?

Reveal Answer & Explanation

Answer: An Octet eliminates 3 variables, leaving a single literal in the resulting term.
Each doubling of group size (2^k) eliminates k variables. For an Octet, 2^3 = 8.

How many selection lines are required for an 8-to-1 Multiplexer (8:1 MUX)?

Reveal Answer & Explanation

Answer: Since 2^3 = 8, exactly 3 selection lines (S2, S1, S0) are required.
Use the formula 2^n = I, where I is the number of data input lines.

What is the output of an XNOR gate when its two binary inputs are A = 1 and B = 1?

Reveal Answer & Explanation

Answer: The output is 1, because both inputs are identical (1 ⊙ 1 = 1).
XNOR is an equivalence gate that outputs 1 when both inputs match.

Finished Studying This Chapter?

READY TO PRACTICE?

Timed CBT Practice Tests (Exam Simulator)

Put your concepts to the test with official curriculum-aligned Foundation and Advanced practice tests. Get instant accuracy scores, time metrics, and step-by-step verified explanations.

Foundation Test

15 MCQs • Core Concepts

Advanced Test

15 MCQs • HOTS & Traps

All Class 12 Computer Science Chapters

Ch 1: Programming in Python Ch 2: Data Structures Ch 3: Database Management System (DBMS) Ch 4: Computer Networks Ch 5: Boolean Algebra and Logic Gates Ch 6: Computer Security and Ethics

AI Study Friend

Instant Concept Tutor

Have a doubt in Boolean Algebra and Logic Gates? Ask our AI study tutor for rapid explanations or customized quizzes.

💬 "Explain core concepts of Boolean Algebra and Logic Ga..." 💬 "What are the common exam traps?" 💬 "How should I prepare for tests?"

Input A	Input B	NOT A (\(A'\))	AND (\(A \cdot B\))	OR (\(A + B\))
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

Target Operation	Realization using ONLY NAND Gates	Min NAND Count	Realization using ONLY NOR Gates	Min NOR Count
NOT (\(A'\))	Tie both inputs together: \((A \cdot A)' = A'\)	1	Tie both inputs together: \((A + A)' = A'\)	1
AND (\(AB\))	NAND followed by a NAND inverter: \(((AB)')' = AB\)	2	Invert inputs first, then NOR: \((A' + B')' = (A')'(B')' = AB\)	3
OR (\(A+B\))	Invert inputs first, then NAND: \((A' \cdot B')' = A + B\)	3	NOR followed by a NOR inverter: \(((A + B)')' = A + B\)	2
XOR (\(A \oplus B\))	Standard 4-gate cross-coupled architecture	4	5-gate NOR configuration	5
XNOR (\(A \odot B\))	5-gate NAND configuration	5	4-gate NOR configuration	4

Operation	Symbol & Expression	Mathematical Definition	Electronic Switching Analogy
Logical NOT (Inversion)	\(Y = A'\) or \(\overline{A}\)	\(0' = 1\), \(1' = 0\)	Normally-closed switch in parallel with the load.
Logical AND (Conjunction)	\(Y = A \cdot B\)	Output is 1 if and only if ALL inputs are 1; otherwise 0.	Switches connected in series (both must close).
Logical OR (Disjunction)	\(Y = A + B\)	Output is 1 if AT LEAST ONE input is 1; 0 only when all are 0.	Switches connected in parallel (either path conducts).

Law Name	OR Form (Dual Form 1)	AND Form (Dual Form 2)	Description
Idempotent Law	\(A + A = A\)	\(A \cdot A = A\)	Repeating an input does not alter the output.
Involution Law	\((A')' = A\) (Double Inversion)		Inverting a variable twice yields original value.
Complementarity Law	\(A + A' = 1\)	\(A \cdot A' = 0\)	Variable paired with its complement.
Commutative Law	\(A + B = B + A\)	\(A \cdot B = B \cdot A\)	Order of binary operands is irrelevant.
Associative Law	\(A + (B + C) = (A + B) + C\)	\(A(BC) = (AB)C\)	Grouping of identical operations can be varied.
Distributive Law	\(A \cdot (B + C) = AB + AC\)	\(A + (BC) = (A + B)(A + C)\)	Crucial: Second distributive law does NOT hold in ordinary algebra!
Absorption Law	\(A + AB = A\)	\(A(A + B) = A\)	Redundant terms absorbed: \(A + A'B = A + B\).
Consensus Theorem	\(AB + A'C + BC = AB + A'C\)	\((A+B)(A'+C)(B+C) = (A+B)(A'+C)\)	Third term \(BC\) is redundant consensus.

Feature	Minterm / Canonical SOP (Sum of Products)	Maxterm / Canonical POS (Product of Sums)
Term Structure	Product of all variables (e.g., \(A'BC\)).	Sum of all variables (e.g., \(A + B' + C\)).
Variable Designation	Uncomplemented literal = 1, Complemented literal = 0.	Uncomplemented literal = 0, Complemented literal = 1.
Truth Table Mapping	Designated by rows where function output \(F = 1\).	Designated by rows where function output \(F = 0\).
Standard Shorthand Notation	\(F(A, B, C) = \sum m(1, 3, 5, 7)\)	\(F(A, B, C) = \prod M(0, 2, 4, 6)\)

Variables (\(n\))	Cell Count (\(2^n\))	Row & Column Indexing	Wrap-around Adjacencies
2 Variables (\(A, B\))	4 cells	\(A \in \{0, 1\}\), \(B \in \{0, 1\}\)	Simple edge adjacency
3 Variables (\(A, B, C\))	8 cells (2 rows × 4 cols)	Row \(A \in \{0, 1\}\), Col \(BC \in \{00, 01, 11, 10\}\)	Leftmost column (00) is adjacent to rightmost column (10).
4 Variables (\(A, B, C, D\))	16 cells (4 rows × 4 cols)	Row \(AB \in \{00, 01, 11, 10\}\), Col \(CD \in \{00, 01, 11, 10\}\)	Both outer columns and top/bottom rows wrap around; 4 outer corners form a valid Quad.

Circuit	Inputs	Output Equations	Gate Implementation
Half Adder	\(A, B\) (2 bits)	\(\text{Sum } S = A \oplus B\) \(\text{Carry } C = A \cdot B\)	1 XOR gate + 1 AND gate
Full Adder	\(A, B, C_{in}\) (3 bits)	\(\text{Sum } S = A \oplus B \oplus C_{in}\) \(C_{out} = AB + C_{in}(A \oplus B)\)	2 Half Adders + 1 OR gate
Half Subtractor	\(A, B\) (2 bits)	\(\text{Difference } D = A \oplus B\) \(\text{Borrow } B_{out} = A' \cdot B\)	1 XOR gate + 1 NOT gate + 1 AND gate
Full Subtractor	\(A, B, B_{in}\) (3 bits)	\(\text{Difference } D = A \oplus B \oplus B_{in}\) \(B_{out} = A'B + (A \oplus B)'B_{in}\)	2 Half Subtractors + 1 OR gate

Boolean Algebra and Logic Gates

Why This Chapter Matters

Chapter Roadmap & Progression

Complete Concept Guide (100% Curriculum Coverage)

Module 1: Boolean Constants, Variables, Truth Tables & Fundamental Postulates

Module 2: Fundamental Boolean Laws, Distributive Theorems, Duality & De Morgan's Laws

Module 3: Logic Gates — Basic, Universal Realization & Derived Gates

Module 4: Canonical SOP & POS Forms and Standard Boolean Expressions

Module 5: Karnaugh Map (K-Map) Optimization & Minimization

Module 6: Combinational Logic Circuits — Adders, Subtractors, MUX, DEMUX & Decoders

Key Programming Syntax, Statements & Translator Rules

Conceptual Solved Examples & Case Studies

Common Misconceptions & Examiner Traps

Common Misconception

Scientific Reality & Correction

Common Misconception

Scientific Reality & Correction

Common Misconception

Scientific Reality & Correction

Common Misconception

Scientific Reality & Correction

Common Misconception

Scientific Reality & Correction

Visual Learning & Conceptual Map

Chapter Summary & 10 Key Takeaways

Check Your Understanding (Diagnostic Practice Questions)

Timed CBT Practice Tests (Exam Simulator)

All Class 12 Computer Science Chapters

AI Study Friend

Get the Latest Updates