Unit 2: Boolean Algebra and Logic gates - Subjective Questions

A logic gate is an elementary electronic circuit that performs a logical operation on one or more binary inputs to produce a single binary output. Gates are the fundamental building blocks of all digital circuits.

1. AND Gate

• Output is HIGH (1) only when all inputs are HIGH.
• Boolean expression:

2. OR Gate

• Output is HIGH (1) when at least one input is HIGH.
• Boolean expression:

3. NOT Gate (Inverter)

• Output is the complement of the input.
• Boolean expression:

These three gates together form a functionally complete set, meaning any Boolean function can be realized using combinations of them.

Universal Gates: NAND and NOR gates are called universal gates because any logic function or any other gate (AND, OR, NOT) can be implemented using only NAND gates or only NOR gates. This is economically important since a circuit can be built using a single type of gate.

Implementation using NAND gates:

1. NOT using NAND — tie both inputs together:

2. AND using NAND — a NAND followed by a NAND-inverter:

3. OR using NAND — invert each input, then NAND them (De Morgan's theorem):

• The first stage inverts A and B using two NAND-inverters.
• The second stage NANDs and , giving .

Since all three basic gates are realizable, NAND is functionally complete — hence universal. The same reasoning applies to NOR gates.

XOR (Exclusive-OR) Gate

• Output is HIGH when the number of HIGH inputs is odd (for 2 inputs, when inputs differ).
• Expression:

XNOR (Exclusive-NOR) Gate

• Output is HIGH when inputs are equal. It is the complement of XOR.
• Expression:

Applications of XOR:

• Half/Full adders (sum generation).
• Parity generators and checkers.

Applications of XNOR:

• Equality/comparator circuits.
• Parity checking (even parity).

De Morgan's Theorems relate the complement of a sum/product to the product/sum of complements.

Theorem 1:

Theorem 2:

Verification of Theorem 1:

Columns and are identical → proved.

Verification of Theorem 2:

Columns match → proved. De Morgan's theorems are essential for converting between AND/OR forms and for implementing circuits with universal gates.

Boolean algebra is a mathematical system dealing with binary variables and logic operations. Its key laws are:

1. Identity Laws

2. Null (Dominance) Laws

3. Idempotent Laws

4. Complement Laws

5. Involution Law

6. Commutative Laws

7. Associative Laws

8. Distributive Laws

9. Absorption Laws

These laws are used to simplify Boolean expressions, reducing gate count and circuit cost.

Given:

Step 1 — Distributive law: expand the bracketed terms.

Step 2 — Idempotent law ():

Step 3 — Idempotent law ():

Step 4 — Absorption law ():

Step 5 — Absorption law ():

Final simplified expression:

The original expression needing several gates reduces to just one AND and one OR gate.

Canonical Form: Each term contains all the variables of the function (either complemented or uncomplemented). There are two types:

• Canonical SOP (Sum of Minterms): OR of minterms.
• Canonical POS (Product of Maxterms): AND of maxterms.

Standard Form: Terms may contain fewer than all variables. Two types:

• Standard SOP: sum of product terms, e.g. .
• Standard POS: product of sum terms, e.g. .

Minterm: A product (AND) term in which every variable appears once (true or complemented). For an -variable function there are minterms. It equals 1 for exactly one input combination.

• Example (2 variables): , , , .

Maxterm: A sum (OR) term in which every variable appears once. It equals 0 for exactly one input combination.

• Example (2 variables): , , , .

Key difference: Canonical form is unique and complete (all variables per term); standard form is a simplified representation. Also, .

Truth Table for :

Canonical SOP (OR of minterms where F = 1):

Canonical POS (AND of maxterms where F = 0, i.e. positions 0,2,4,6):

Observation: All the minterms have , so the function simplifies to .

A Karnaugh Map (K-map) is a graphical tool for simplifying Boolean expressions. It is a grid where each cell represents one minterm, arranged so that adjacent cells differ in only one variable (Gray code ordering). This adjacency lets us visually combine terms that can be simplified.

Sizes:

• 2 variables → 4 cells
• 3 variables → 8 cells
• 4 variables → 16 cells

Rules for grouping:

• Groups must contain cells (1, 2, 4, 8, 16...).
• Groups must be rectangular (horizontal or vertical), not diagonal.
• Make groups as large as possible to eliminate more variables.
• Groups may overlap and wrap around edges (map is toroidal).
• Use the minimum number of groups that covers all 1s.
• Every 1 must be covered by at least one group.

Reading the result: For each group, keep variables that stay constant; drop variables that change.

Advantages over algebraic method:

• Systematic and visual — less prone to error.
• Guarantees a minimal (or near-minimal) SOP/POS.
• No need to remember many algebraic identities.
• Handles don't-care conditions easily.

Limitation: Becomes cumbersome beyond 5–6 variables.

Given:

Minterms 0–7 correspond to all combinations where .

K-map (rows AB, columns CD in Gray order):

Grouping: All eight 1s form one group of 8 cells occupying the region where . In this group, B, C, and D all change, but A remains 0 throughout.

Simplified expression:

Implementation: A single NOT gate (inverter) on input A produces the output — the simplest possible realization.

Given:

K-map:

Groupings:

• Group 1 (quad): m0, m1, m8, m9 → → term
• Group 2 (quad): m0, m2, m8, m10 → → term
• Group 3 (pair): m1, m5 → → term

Minimized SOP:

Grouping in powers of two and choosing the largest possible groups yields this minimal expression.

Don't-care conditions are input combinations for which the output of a function is unspecified — either the combination never occurs, or its output value does not matter. They are denoted by X (or d) in the truth table/K-map.

Significance:

• During K-map grouping, each X can be treated as 1 or 0, whichever helps form larger groups and yields simpler expressions.
• They provide flexibility and often lead to a much simpler circuit.
• We are not forced to cover a don't-care; use it only if it helps.

Example: BCD codes use only 0–9; combinations 10–15 never occur, so they are don't-cares.

Consider

When simplifying, we may treat as 1 to enlarge a group. For instance, grouping m1, m3 with d0, d2 forms a quad giving (assuming appropriate positions), simpler than covering only the required 1s.

Key point: Don't-cares are optional 1s — used opportunistically to minimize the final expression, but never required to be covered.

Given: Required minterms , don't-cares .

K-map (X = don't-care):

Groupings:

• Group 1 (quad): m3, m7, m11, m15 → column → term .
• Group 2 (quad): m1, m3 with X0, X2 (top row) → → term .

Using the don't-cares 0 and 2 as 1s lets Group 2 become a full quad, giving a simpler term.

Minimized SOP:

Without the don't-cares, the second term would have been the larger ; the don't-cares yield a simpler result.

Sum of Products (SOP):

• Logical OR of AND terms (product terms).
• Formed from the input rows where output = 1 (minterms).
• Example:
• Implemented as AND-OR (or NAND-NAND) logic.

Product of Sums (POS):

• Logical AND of OR terms (sum terms).
• Formed from the input rows where output = 0 (maxterms).
• Example:
• Implemented as OR-AND (or NOR-NOR) logic.

Comparison:

Obtaining POS from a truth table:

1. Identify each row where the output F = 0.
2. For each such row, write a sum (OR) term (maxterm): a variable appears complemented if its value is 1, and uncomplemented if its value is 0 (opposite of minterm rule).
3. AND all these maxterms together.

Example: If F = 0 at → maxterm .

A Half Adder adds two single-bit binary numbers A and B, producing a Sum (S) and a Carry (C).

Truth Table:

Deriving Expressions (SOP from output = 1 rows):

Sum:

Carry:

Implementation:

• Sum is generated by a single XOR gate with inputs A and B.
• Carry is generated by a single AND gate with inputs A and B.

Limitation: A half adder cannot accept a carry input from a previous stage, which is why a full adder is needed for multi-bit addition.

A Full Adder adds three bits: A, B, and carry-in , producing Sum (S) and Carry-out ().

Truth Table:

Sum . The minterms cannot be combined on a K-map (checkerboard pattern), giving:

Carry-out . K-map grouping gives:

Implementation:

• Sum: two XOR gates in cascade — .
• Carry: three AND gates feeding one OR gate, or the compact form .
• A full adder can be built from two half adders + one OR gate.

Given:

Identify minterms:

So .

Truth Table:

K-map:

Groupings:

• Pair (m1, m5):
• Pair (m4, m5):
• Pair (m5, m7):

Minimized SOP:

Procedure for NOR-only implementation:

1. Start with the function in POS (Product of Sums) form, since NOR is naturally suited to OR-AND structures.
2. A two-level OR-AND circuit converts directly to a NOR-NOR structure.
3. Replace each gate with NOR equivalents, using double inversion where necessary. A NOR gate acts as an OR followed by an inverter; bubbles are matched using De Morgan's theorem.

Given:

Step 1 — Insert double negation over the whole function:

Step 2 — Apply De Morgan to the inner complement:

Step 3 — Identify NOR operations:

• → NOR gate 1.
• → NOR gate 2.
• The outer expression where are the two NOR outputs → NOR gate 3.

Implementation: Three NOR gates:

• Gate 1: inputs A, B →
• Gate 2: inputs C, D →
• Gate 3: inputs = outputs of gates 1 and 2 →

This realizes the function using only NOR gates.

Consensus Theorem: The term (the consensus term) is redundant and can be eliminated.

Algebraic Proof:

Start with the LHS and expand the consensus term by multiplying with :

Group terms:

Apply absorption ( and ):

K-map Verification (variables A, B, C):

• minterms 6, 7
• minterms 1, 3
• minterms 3, 7

The two natural groups are:

• : cells m6, m7
• : cells m1, m3

Every 1 (including m3 and m7 that would cover) is already covered by these two groups. Hence is redundant, confirming the theorem.

Five-variable K-map construction: A 5-variable map has cells. It is drawn as two 4-variable maps side by side — one for and one for . Cells in the same position on both maps are considered adjacent (mirror adjacency), allowing groups to span across the two maps.

Given:

Map A = 0 (minterms 0–15), variables BCDE:

• 1s at m0, m2, m4, m6 (all with ... actually ), m9, m13.

Map A = 1 (minterms 16–31):

• 1s at m21, m23, m25, m29, m31.

Groupings:

• Group 1: m0, m2, m4, m6 (A=0) → ... these share region → term .
• Group 2: m9, m13, m25, m29 span both maps → → term combine to style; here term -type. These give $BD... $
• Group 3: m21, m23, m29, m31 (A=1) → region combined → term -type.

Representative minimized SOP:

Note: The essential technique is treating the two 4-variable halves as vertically stacked, checking both in-map adjacency and across-map (mirror) adjacency to form the largest valid groups. Exact terms depend on careful cell placement; the method shown is the systematic approach for five-variable minimization.