Number Systems & Boolean Algebra
Complete Guide for GATE CS — Binary, Octal, Hex Conversions, 2’s Complement, Boolean Laws, De Morgan’s Theorems, SOP & POS
Last Updated: April 2026
📌 Key Takeaways
- Number bases: Binary (base-2), Octal (base-8), Decimal (base-10), Hexadecimal (base-16). Hex digits A–F = 10–15. 1 hex digit = 4 binary bits.
- 2’s complement: Invert all bits + add 1. Used for signed integer representation. Range for n bits: −2n−1 to +2n−1−1. Subtraction A−B = A + 2’s complement(B), ignore final carry.
- Boolean algebra: Variables take values 0 or 1. Operations: AND (·), OR (+), NOT (‘). Follows commutative, associative, distributive, absorption, and identity laws.
- De Morgan’s Theorems: (A+B)’ = A’·B’ | (A·B)’ = A’+B’. Fundamental for converting between NAND/NOR implementations.
- SOP: Sum of minterms (rows where f=1). Minterm mᵢ = product of all literals that evaluates to 1 for row i.
- POS: Product of maxterms (rows where f=0). Maxterm Mᵢ = sum of all literals that evaluates to 0 for row i.
- GATE tests: base conversion, 2’s complement overflow detection, Boolean simplification using laws, and SOP/POS canonical forms.
1. Number Systems — Bases & Conversions
| Base | Name | Digits | Prefix |
|---|---|---|---|
| 2 | Binary | 0, 1 | 0b or subscript ₂ |
| 8 | Octal | 0–7 | 0o or subscript ₈ |
| 10 | Decimal | 0–9 | (default) |
| 16 | Hexadecimal | 0–9, A–F (A=10…F=15) | 0x or subscript ₁₆ |
Conversion Rules
Any base → Decimal: Multiply each digit by its positional weight (baseⁿ) and sum.
1011₂ = 1×2³+0×2²+1×2¹+1×2⁰ = 8+0+2+1 = 11₁₀
Decimal → Binary: Repeated division by 2; read remainders bottom-to-top.
Binary ↔ Octal: Group binary digits in 3s from right; each group = one octal digit.
110 101 011₂ = 6 5 3₈ = 653₈
Binary ↔ Hex: Group binary digits in 4s from right; each group = one hex digit.
1010 1111₂ = A F₁₆ = AF₁₆
Octal/Hex → Decimal: Expand by positional weights in base 8 or 16.
1.1 Hex Digit Reference
| Hex | Decimal | Binary (4-bit) |
|---|---|---|
| 0–9 | 0–9 | 0000–1001 |
| A | 10 | 1010 |
| B | 11 | 1011 |
| C | 12 | 1100 |
| D | 13 | 1101 |
| E | 14 | 1110 |
| F | 15 | 1111 |
2. Binary Arithmetic
Binary Addition Rules
0+0=0 | 0+1=1 | 1+0=1 | 1+1=10 (sum=0, carry=1) | 1+1+1=11 (sum=1, carry=1)
Example: 1011 + 0110:
1011
+ 0110
─────
10001 (carries: 1100)
Overflow Detection
Unsigned overflow: Final carry out of MSB = 1
Signed overflow: Carry into MSB ≠ Carry out of MSB
Two positive numbers sum to a negative, or two negative numbers sum to a positive → overflow.
3. 1’s and 2’s Complement — Signed Numbers
Complement Operations
1’s complement: Invert all bits. (0→1, 1→0)
1’s complement of 01011010 = 10100101
2’s complement: Invert all bits, then add 1. (= 1’s complement + 1)
2’s complement of 01011010: invert → 10100101, add 1 → 10100110
Shortcut: Copy bits from right up to and including the first 1; invert all remaining bits.
| Representation | Positive Range | Negative Range | Zero | Used in? |
|---|---|---|---|---|
| Sign-Magnitude | 0 to 2n−1−1 | −(2n−1−1) to −0 | Two zeros (+0,−0) | Old systems |
| 1’s Complement | 0 to 2n−1−1 | −(2n−1−1) to −0 | Two zeros | Rarely used |
| 2’s Complement | 0 to 2n−1−1 | −2n−1 to −1 | Unique zero | All modern CPUs |
2’s Complement Range & Subtraction
n-bit 2’s complement range: −2n−1 to +2n−1−1
4-bit: −8 to +7 8-bit: −128 to +127 16-bit: −32768 to +32767
Subtraction A − B: Compute 2’s complement of B, then add A + (2’s complement of B). Discard any final carry beyond n bits.
4. Boolean Algebra Laws & Theorems
| Law | AND form | OR form |
|---|---|---|
| Identity | A·1 = A | A+0 = A |
| Null/Dominance | A·0 = 0 | A+1 = 1 |
| Idempotent | A·A = A | A+A = A |
| Complement | A·A’ = 0 | A+A’ = 1 |
| Double Complement | (A’)’ = A | (A’)’ = A |
| Commutative | A·B = B·A | A+B = B+A |
| Associative | (A·B)·C = A·(B·C) | (A+B)+C = A+(B+C) |
| Distributive | A·(B+C) = A·B + A·C | A+(B·C) = (A+B)·(A+C) |
| Absorption | A·(A+B) = A | A+(A·B) = A |
| De Morgan | (A·B)’ = A’+B’ | (A+B)’ = A’·B’ |
| Consensus | A·B + A’·C + B·C = A·B + A’·C | (A+B)·(A’+C)·(B+C) = (A+B)·(A’+C) |
XOR Properties (important for GATE)
A ⊕ 0 = A | A ⊕ 1 = A’ | A ⊕ A = 0 | A ⊕ A’ = 1
A ⊕ B = A’B + AB’ (XOR = difference)
XNOR = (A⊕B)’ = AB + A’B’ (XNOR = equality)
XOR is commutative and associative: A⊕B⊕C = (A⊕B)⊕C = A⊕(B⊕C)
5. SOP, POS, Minterms & Maxterms
Minterms and Maxterms
For a 3-variable function f(A,B,C), each input combination i (0–7) has:
Minterm mᵢ: Product (AND) of all literals that evaluates to 1 only for row i.
m₅ (row 5 = 101 → A=1,B=0,C=1): mᵢ = A·B’·C
Maxterm Mᵢ: Sum (OR) of all literals that evaluates to 0 only for row i.
M₅ (row 5 = 101 → A=1,B=0,C=1): Mᵢ = A’+B+C’
Key relationship: mᵢ’ = Mᵢ (complement of minterm = maxterm, same index)
Canonical SOP: f = Σm(i) for all i where f=1
Canonical POS: f = ΠM(i) for all i where f=0
Complement: f’ = Σm(j) for all j where f=0 = ΠM(k) for all k where f=1
6. Canonical & Standard Forms
| Form | Structure | When to Use |
|---|---|---|
| Canonical SOP (minterm expansion) | OR of all minterms where f=1 | Starting point for K-map minimization |
| Canonical POS (maxterm expansion) | AND of all maxterms where f=0 | When number of 0s in truth table is small |
| Standard SOP | OR of product terms (not necessarily canonical) | Simplified circuit implementation |
| Standard POS | AND of sum terms (not necessarily canonical) | Simplified circuit implementation |
7. Worked Examples (GATE CS Level)
Example 1 — Number Conversions & 2’s Complement
Problem: (a) Convert 173₁₀ to binary, octal, and hex. (b) Represent −45 in 8-bit 2’s complement. (c) Compute 7 − 12 using 5-bit 2’s complement. Identify if overflow occurs.
(a) 173₁₀ conversions:
Binary: 173÷2=86R1 → 86÷2=43R0 → 43÷2=21R1 → 21÷2=10R1 → 10÷2=5R0 → 5÷2=2R1 → 2÷2=1R0 → 1÷2=0R1
173₁₀ = 10101101₂
Group in 3s: 010 101 101 → 255₈
Group in 4s: 1010 1101 → AD₁₆
(b) −45 in 8-bit 2’s complement:
45₁₀ = 00101101₂. Invert: 11010010. Add 1: 11010011.
−45 in 8-bit 2’s complement = 11010011₂
Verify: 11010011 in unsigned = 211. 256−211=45. ✓
(c) 7 − 12 in 5-bit 2’s complement:
7 = 00111₂. 12 = 01100₂. 2’s complement of 12: invert=10011, +1=10100.
00111 + 10100 = 11011₂
No carry out of MSB (5th bit). MSB of result = 1 → negative number.
11011₂ in 2’s complement = −(00101₂) = −5₁₀. 7−12=−5 ✓
Overflow check: carry into MSB=1, carry out of MSB=0 → 1≠0 → No overflow? Wait: 7−12=−5, result is −5 which is within 5-bit range [−16, +15] → no overflow.
Example 2 — Boolean Simplification
Problem: Simplify: (a) F = AB + AB’ + A’B, (b) F = (A+B)(A+B’)(A’+B), (c) F = A’B’C + A’BC + AB’C + ABC.
(a) F = AB + AB’ + A’B:
= A(B+B’) + A’B = A·1 + A’B = A + A’B = (A+A’)(A+B) = 1·(A+B) = A + B
(b) F = (A+B)(A+B’)(A’+B):
(A+B)(A+B’) = A + BB’ = A + 0 = A (using distributive law: A+(B·B’)=A+0=A)
A·(A’+B) = AA’ + AB = 0 + AB = AB
(c) F = A’B’C + A’BC + AB’C + ABC:
= A’C(B’+B) + AC(B’+B) = A’C·1 + AC·1 = A’C + AC = C(A’+A) = C·1 = C
Simplified answers: (a) A+B | (b) AB | (c) C
Example 3 — SOP/POS from Truth Table
Problem: A 3-variable function f(A,B,C) has the truth table below. Write (a) canonical SOP, (b) canonical POS, (c) simplified SOP using Boolean algebra.
| Row | A | B | C | f |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 1 |
f=1 at rows 1,3,5,7. f=0 at rows 0,2,4,6.
(a) Canonical SOP: f = Σm(1,3,5,7)
= A’B’C + A’BC + AB’C + ABC
(b) Canonical POS: f = ΠM(0,2,4,6)
= (A+B+C)(A+B’+C)(A’+B+C)(A’+B’+C)
(c) Simplified SOP:
f = A’B’C + A’BC + AB’C + ABC = C(A’B’+A’B+AB’+AB) = C[(A'(B’+B)) + A(B’+B)] = C[A’+A] = C
8. 5 Common Mistakes in Number Systems & Boolean Algebra
Mistake 1 — Reading Remainders in Wrong Order for Base Conversion
What happens: Converting 13₁₀ to binary by repeated division and reading remainders top-to-bottom: getting 1011 instead of 1101.
Root cause: The first remainder (from dividing 13) is the Least Significant Bit (LSB), not the Most Significant Bit.
Correct approach: Read remainders from BOTTOM to TOP (last remainder first = MSB).
Mistake 2 — Forgetting to Add 1 in 2’s Complement Conversion
What happens: Students compute 1’s complement (just invert) and call it 2’s complement.
Root cause: Confusing the two operations — 1’s complement = invert only; 2’s complement = invert + add 1.
Correct approach: 2’s complement = 1’s complement + 1. Or use shortcut: copy bits from right up to and including first 1, invert the rest.
Mistake 3 — Wrong Application of De Morgan’s Theorem
What happens: Students write (AB)’ = A’B’ instead of A’+B’, or (A+B)’ = A’+B’ instead of A’B’.
Root cause: Confusing the two forms. The operation changes: NOT(AND) = OR of complements; NOT(OR) = AND of complements.
Correct approach: “Break the line, change the sign.” Draw a bar over the whole expression, then change AND↔OR: (A·B)’ = A’+B’; (A+B)’ = A’·B’.
Mistake 4 — Constructing Wrong Maxterm for POS
What happens: For f=0 at row 5 (A=1,B=0,C=1), students write maxterm as A·B’·C instead of A’+B+C’.
Root cause: Confusing minterm and maxterm construction rules. Minterm: variables without complement where input=1, with complement where input=0. Maxterm: opposite — complement where input=1, no complement where input=0.
Correct approach: Maxterm Mᵢ: for each variable, complement it if that variable’s bit is 1 in row i. Join with OR. For row 5 (101): A’+B+C’.
Mistake 5 — Signed Overflow vs Unsigned Overflow
What happens: Students detect overflow by looking only at the final carry, which is the unsigned overflow rule — they miss signed overflow.
Root cause: Two different overflow conditions exist. Unsigned overflow: final carry out = 1. Signed (2’s complement) overflow: carry into MSB ≠ carry out of MSB.
Correct approach: For signed arithmetic, track both the carry INTO the MSB position and the carry OUT of it. If they differ, signed overflow has occurred.
9. Frequently Asked Questions
Q1. How do you convert a decimal number to binary?
Repeatedly divide by 2, collecting remainders. The binary number is formed by reading remainders from bottom (last) to top (first). Example: 45: 45÷2=22R1, 22÷2=11R0, 11÷2=5R1, 5÷2=2R1, 2÷2=1R0, 1÷2=0R1. Read upward: 101101₂. Verify: 32+8+4+1=45 ✓. For fractions: multiply by 2 repeatedly and collect the integer parts (read top to bottom for the fractional binary).
Q2. What is 2’s complement and how is it used for subtraction?
2’s complement is the standard representation for signed integers in modern computers. To find 2’s complement: invert all bits, then add 1. For subtraction A−B: compute 2’s complement of B, then add A to it. Discard any carry beyond the word size. The beauty: subtraction becomes addition, so the same adder hardware handles both. Range for n bits: −2n−1 to +2n−1−1. Special case: the most negative number (1000…0) has no positive counterpart — its 2’s complement is itself.
Q3. State De Morgan’s theorems for Boolean algebra.
De Morgan’s First: (A·B)’ = A’ + B’ — NOT(A AND B) = (NOT A) OR (NOT B). De Morgan’s Second: (A+B)’ = A’·B’ — NOT(A OR B) = (NOT A) AND (NOT B). Memory trick: “Break the bar, change the operation.” These theorems are critical for: (1) converting AND-OR networks to NAND-NAND (more practical — NAND is the universal gate); (2) converting OR-AND networks to NOR-NOR; (3) complement derivation in SOP/POS. Extended De Morgan: (A·B·C)’ = A’+B’+C’ and (A+B+C)’ = A’·B’·C’.
Q4. What is the difference between SOP and POS forms?
SOP (Sum of Products) = OR of AND terms. Each AND term is called a product term or implicant. The canonical SOP sums ALL minterms where f=1. Suitable when the function has few 1s in the truth table. POS (Product of Sums) = AND of OR terms. Each OR term is a sum term or clause. The canonical POS multiplies ALL maxterms where f=0. Suitable when the function has few 0s. The two forms are duals of each other: every SOP theorem has a POS dual (swap AND↔OR, 0↔1). Both canonical forms represent the same function uniquely.