Boolean Algebra and Logic Identities
De Morgan's First Theorem
\overline{A \cdot B} = \bar{A} + \bar{B}
| Symbol | Description | Unit |
|---|---|---|
| A, B | Boolean variables | dimensionless |
Worked example
Verify De Morgan's theorem for A = 1, B = 0.
Given: A = 1, B = 0
- LHS: A·B = 1·0 = 0, so NOT(A·B) = 1
- RHS: NOT A = 0, NOT B = 1, so NOT A + NOT B = 0 + 1 = 1
- LHS = RHS = 1 ✓
Answer: Theorem verified: NOT(A·B) = NOT A + NOT B = 1
De Morgan's Second Theorem
\overline{A + B} = \bar{A} \cdot \bar{B}
Worked example
Verify for A = 0, B = 0.
Given: A = 0, B = 0
- LHS: A+B = 0+0 = 0, NOT(0) = 1
- RHS: NOT A = 1, NOT B = 1, 1·1 = 1
- LHS = RHS = 1 ✓
Answer: Theorem verified: NOT(A+B) = NOT A · NOT B = 1
Consensus Theorem
AB + \bar{A}C + BC = AB + \bar{A}C
Worked example
Simplify F = AB + NOT_A·C + BC.
Given: Expression: AB + NOT_A·C + BC
- The consensus term BC = B(A + NOT_A) = AB + NOT_A·B
- F = AB + NOT_A·C + BC is redundant since BC is covered
- F = AB + NOT_A·C (drop BC)
Answer: F = AB + NOT_A·C
SOP from Truth Table (Minterm Sum)
F = \sum m(i) \quad \text{where minterm } m_i = \text{product of literals}
| Symbol | Description | Unit |
|---|---|---|
| m_i | Minterm where output = 1 | dimensionless |
Worked example
Write SOP for F(A,B,C) with minterms at 1,3,5,7.
Given: Minterms: 1 (001), 3 (011), 5 (101), 7 (111)
- m1 = NOT_A · NOT_B · C
- m3 = NOT_A · B · C
- m5 = A · NOT_B · C
- m7 = A · B · C
- F = NOT_A·NOT_B·C + NOT_A·B·C + A·NOT_B·C + A·B·C
- Factor: C(NOT_A·NOT_B + NOT_A·B + A·NOT_B + A·B) = C·1 = C
Answer: F = C
Number Systems and Code Conversion
Binary to Decimal
N_{10} = \sum_{i} b_i \cdot 2^i
| Symbol | Description | Unit |
|---|---|---|
| b_i | Binary digit at position i | 0 or 1 |
| i | Bit position (0 = LSB) | dimensionless |
Worked example
Convert binary 10110101 to decimal.
Given: Binary: 1 0 1 1 0 1 0 1
- 1×2⁷ + 0×2⁶ + 1×2⁵ + 1×2⁴ + 0×2³ + 1×2² + 0×2¹ + 1×2⁰
- = 128 + 0 + 32 + 16 + 0 + 4 + 0 + 1
- = 181
Answer: 10110101₂ = 181₁₀
Gray Code to Binary
B_n = G_n, \quad B_{n-1} = B_n \oplus G_{n-1}, \ldots
| Symbol | Description | Unit |
|---|---|---|
| B_n | Binary MSB | bit |
| G_n | Gray code MSB | bit |
| \oplus | XOR operation | dimensionless |
Worked example
Convert Gray code 1101 to binary.
Given: Gray: G3=1, G2=1, G1=0, G0=1
- B3 = G3 = 1
- B2 = B3 XOR G2 = 1 XOR 1 = 0
- B1 = B2 XOR G1 = 0 XOR 0 = 0
- B0 = B1 XOR G0 = 0 XOR 1 = 1
Answer: Gray 1101 → Binary 1001
2's Complement (Negation)
\text{2's complement} = \text{1's complement} + 1
Worked example
Find 2's complement of 8-bit number 00110100 (= +52).
Given: Binary: 00110100
- 1's complement: flip all bits → 11001011
- Add 1: 11001011 + 00000001 = 11001100
- 11001100 = -(52) in 2's complement
Answer: 2's complement = 11001100 (= -52)
Combinational Circuits
Full Adder Sum and Carry
S = A \oplus B \oplus C_{in}, \quad C_{out} = AB + C_{in}(A \oplus B)
| Symbol | Description | Unit |
|---|---|---|
| S | Sum output | bit |
| C_{in} | Carry input | bit |
| C_{out} | Carry output | bit |
Worked example
Find S and C_out for A=1, B=1, C_in=1.
Given: A = 1, B = 1, C_in = 1
- S = 1 XOR 1 XOR 1 = 0 XOR 1 = 1
- A XOR B = 0
- C_out = 1·1 + 1·0 = 1 + 0 = 1
Answer: S = 1, C_out = 1
Multiplexer Output (2:1 MUX)
Y = S \cdot I_1 + \bar{S} \cdot I_0
| Symbol | Description | Unit |
|---|---|---|
| S | Select line | bit |
| I_0, I_1 | Data inputs | bit |
Worked example
2:1 MUX with I0 = 1, I1 = 0, S = 1. Find Y.
Given: I0 = 1, I1 = 0, S = 1
- Y = S·I1 + NOT_S·I0
- Y = 1·0 + 0·1
- Y = 0 + 0 = 0
Answer: Y = 0 (I1 is selected when S=1)
Priority Encoder Output
\text{Output} = \text{highest active input index in binary}
Worked example
8:3 priority encoder: inputs I7=0, I6=0, I5=1, I4=1, others = 0. Find output.
Given: Active inputs: I5=1, I4=1 (I5 has higher priority)
- Highest active input is I5
- Binary code for 5 = 101
Answer: Output = 101 (priority goes to I5)
Comparator Output Condition
A > B \Rightarrow A_{gt} = 1; \quad A = B \Rightarrow A_{eq} = 1
Worked example
4-bit comparator: A = 1010 (10), B = 0111 (7). Determine outputs.
Given: A = 10, B = 7
- 10 > 7, so A_gt = 1
- A_lt = 0, A_eq = 0
Answer: A_gt = 1, A_lt = 0, A_eq = 0
Flip-Flops and Latches
D Flip-Flop Next State
Q^{n+1} = D
| Symbol | Description | Unit |
|---|---|---|
| Q^{n+1} | Next state output | bit |
| D | Data input | bit |
Worked example
D FF: Q=0, D=1, clock rising edge arrives. Find Q_next.
Given: Q_current = 0, D = 1
- On rising clock edge, Q_next = D
- Q_next = 1
Answer: Q_next = 1
JK Flip-Flop Next State
Q^{n+1} = J\bar{Q}^n + \bar{K}Q^n
| Symbol | Description | Unit |
|---|---|---|
| J, K | Set and reset inputs | bit |
Worked example
JK FF: Q=1, J=1, K=1 (toggle). Find Q_next.
Given: Q = 1, J = 1, K = 1
- Q_next = J·NOT_Q + NOT_K·Q
- = 1·0 + 0·1
- = 0 + 0 = 0 (toggles from 1 to 0)
Answer: Q_next = 0 (toggle occurred)
T Flip-Flop Next State
Q^{n+1} = T \oplus Q^n
| Symbol | Description | Unit |
|---|---|---|
| T | Toggle input | bit |
Worked example
T FF with Q=0, T=1. Find Q_next.
Given: Q = 0, T = 1
- Q_next = T XOR Q = 1 XOR 0 = 1
Answer: Q_next = 1
Setup and Hold Time Constraint
t_{clk} \geq t_{p,FF} + t_{comb} + t_{setup}
| Symbol | Description | Unit |
|---|---|---|
| t_{clk} | Clock period | ns |
| t_{p,FF} | Flip-flop propagation delay | ns |
| t_{comb} | Combinational logic delay | ns |
| t_{setup} | Setup time requirement | ns |
Worked example
Find minimum clock period: FF propagation = 3 ns, combinational = 5 ns, setup = 2 ns.
Given: t_p = 3 ns, t_comb = 5 ns, t_setup = 2 ns
- t_clk(min) = t_p + t_comb + t_setup
- = 3 + 5 + 2
- = 10 ns
Answer: Minimum clock period = 10 ns → max frequency = 100 MHz
Counters
Modulus of a Counter
M = 2^n \quad \text{(for n-bit natural binary counter)}
| Symbol | Description | Unit |
|---|---|---|
| M | Modulus (number of states) | dimensionless |
| n | Number of flip-flops | dimensionless |
Worked example
How many flip-flops are needed for a MOD-12 counter?
Given: M = 12
- 2^n ≥ M → 2^n ≥ 12
- 2³ = 8 < 12, 2⁴ = 16 ≥ 12
- n = 4 flip-flops required
Answer: n = 4 FFs (with reset at count 12)
Counter Output Frequency
f_{out} = \frac{f_{clk}}{M}
| Symbol | Description | Unit |
|---|---|---|
| f_{out} | Output frequency | Hz |
| f_{clk} | Input clock frequency | Hz |
Worked example
A MOD-8 counter has a 1 MHz clock. Find Q2 (MSB) output frequency.
Given: f_clk = 1 MHz, M = 8
- f_out = f_clk / M
- f_out = 1×10⁶ / 8
- f_out = 125000 Hz
Answer: f_out = 125 kHz
Propagation Delay in Ripple Counter
t_{total} = n \cdot t_{p,FF}
| Symbol | Description | Unit |
|---|---|---|
| t_{total} | Total propagation delay | ns |
| n | Number of flip-flop stages | dimensionless |
| t_{p,FF} | Individual FF propagation delay | ns |
Worked example
4-bit ripple counter with each FF delay = 15 ns. Find total delay.
Given: n = 4, t_p = 15 ns
- t_total = 4 × 15 = 60 ns
- Max clock frequency = 1 / 60e-9 = 16.67 MHz
Answer: Total delay = 60 ns, max f_clk = 16.67 MHz
ADC and DAC Conversion
DAC Output Voltage (Binary Weighted)
V_{out} = -R_f \sum_{i=0}^{n-1} \frac{b_i V_{ref}}{2^{n-1-i} R}
| Symbol | Description | Unit |
|---|---|---|
| V_{out} | Analog output | V |
| b_i | Bit value (0 or 1) | dimensionless |
| V_{ref} | Reference voltage | V |
Worked example
4-bit DAC with V_ref = 5 V, R = 10 kΩ, Rf = 10 kΩ, input = 1010. Find V_out.
Given: b3=1, b2=0, b1=1, b0=0, V_ref = 5 V
- V_out = -(Rf/R)·V_ref·(b3/1 + b2/2 + b1/4 + b0/8)
- = -(1)·5·(1/1 + 0/2 + 1/4 + 0/8)
- = -5·(1 + 0 + 0.25 + 0)
- = -5 × 1.25 = -6.25 V
Answer: V_out = -6.25 V
ADC Resolution (Step Size)
\Delta V = \frac{V_{FS}}{2^n - 1} \approx \frac{V_{FS}}{2^n}
| Symbol | Description | Unit |
|---|---|---|
| \Delta V | Resolution (LSB voltage) | V |
| V_{FS} | Full-scale voltage | V |
| n | Number of bits | dimensionless |
Worked example
Find resolution of a 10-bit ADC with V_FS = 5 V.
Given: n = 10, V_FS = 5 V
- ΔV = V_FS / (2^n - 1)
- = 5 / (1024 - 1)
- = 5 / 1023
- = 0.004887 V
Answer: Resolution ≈ 4.89 mV per LSB
ADC Quantization Error
e_q = \pm \frac{\Delta V}{2} = \pm \frac{V_{FS}}{2^{n+1}}
| Symbol | Description | Unit |
|---|---|---|
| e_q | Quantization error | V |
Worked example
Find max quantization error for the 10-bit ADC above.
Given: ΔV = 4.89 mV
- e_q = ±ΔV/2
- e_q = ±4.89/2
- e_q = ±2.44 mV
Answer: Maximum quantization error = ±2.44 mV
Quick reference
| Formula | Expression |
|---|---|
| De Morgan 1 | NOT(A·B) = NOT_A + NOT_B |
| De Morgan 2 | NOT(A+B) = NOT_A · NOT_B |
| D FF Next State | Q_next = D |
| JK FF Next State | Q_next = J·NOT_Q + NOT_K·Q |
| T FF Next State | Q_next = T XOR Q |
| Full Adder Sum | S = A XOR B XOR C_in |
| Full Adder Carry | C_out = AB + C_in(A XOR B) |
| MUX Output (2:1) | Y = S·I1 + NOT_S·I0 |
| Counter Modulus | M = 2^n |
| Counter Output Freq | f_out = f_clk / M |
| ADC Resolution | ΔV = V_FS / (2^n - 1) |
| Quantization Error | e_q = ±ΔV/2 |
| Ripple Counter Delay | t_total = n × t_p |
| Setup Time Constraint | t_clk ≥ t_p + t_comb + t_setup |
| Gray to Binary | B_n = G_n; B_{n-1} = B_n XOR G_{n-1} |
Exam tips
- GATE questions on Karnaugh maps often include don't-care conditions — always check whether using them reduces the SOP to fewer literals before finalizing.
- For JK flip-flop state table questions, remember J=1,K=0 sets; J=0,K=1 resets; J=K=1 toggles; J=K=0 holds — these four cases appear directly in exam problems.
- Synchronous counter maximum frequency is limited by (t_p + t_comb + t_setup) while asynchronous (ripple) counter is limited by n × t_p — examiners test this distinction.
- ADC resolution questions require verifying whether the formula uses (2^n - 1) or 2^n — the exact expression depends on whether zero is included in the count.
- For logic family compatibility questions, check V_OH(driver) ≥ V_IH(load) and V_OL(driver) ≤ V_IL(load) — both conditions must hold simultaneously.
- Hazard detection in combinational circuits: a static-1 hazard occurs when two adjacent minterms share no common group in the K-map — always cover shared groups with additional prime implicants.