Logic Gates and Circuits

This chapter provides a foundational understanding of logic gates and their synthesis into Boolean circuits. Mastery of these concepts is crucial for advanced topics in computer architecture, digital design, and complexity theory, and forms a significant component of the CMI examination.

---

Chapter Contents

|

| Topic |

|---|-------| | 1 | Basic Logic Gates | | 2 | Boolean Circuits | | 3 | Universal Gates |

---

We begin with Basic Logic Gates.

Part 1: Basic Logic Gates

This section introduces fundamental logic gates, which are the building blocks of digital circuits, crucial for understanding computational logic in computer science. We focus on their functional behavior and application in constructing Boolean expressions.

---

Core Concepts

1. AND Gate

An AND gate produces a high output (1) only if all its inputs are high (1). Otherwise, the output is low (0).

Truth Table:

| $A$ | $B$ | $Y = A \cdot B$ |
|:---:|:---:|:--------------:|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

Worked Example:

Consider a scenario where an alarm $Y$ should activate only if both switch $A$ and switch $B$ are closed (represented by 1). Determine the output when switch $A$ is open (0) and switch $B$ is closed (1).

Step 1: Identify the logical operation.

> The condition "only if both" implies an AND operation.

Step 2: Apply the inputs to the AND truth table.

> Given $A=0$ and $B=1$.
> From the truth table, for $A=0, B=1$, the output $Y = A \cdot B$ is $0$.

Answer: The alarm $Y$ will not activate (output is $0$).

:::question type="MCQ" question="A digital circuit has two inputs, $X$ and $Y$. The output $Z$ is 1 if and only if both $X$ and $Y$ are 1. Which logic gate describes this circuit?" options=["OR gate","NOT gate","AND gate","XOR gate"] answer="AND gate" hint="Analyze the condition for a high output." solution="The condition 'output is 1 if and only if both $X$ and $Y$ are 1' directly matches the definition and truth table of an AND gate. All other gates have different conditions for a high output."
:::

---

2. OR Gate

An OR gate produces a high output (1) if at least one of its inputs is high (1). The output is low (0) only if all its inputs are low (0).

Truth Table:

| $A$ | $B$ | $Y = A + B$ |
|:---:|:---:|:-----------:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

Worked Example:

A security light $L$ turns on if motion sensor $M$ detects movement OR if a manual switch $S$ is activated. If $M$ is inactive (0) and $S$ is inactive (0), what is the state of the light $L$?

Step 1: Identify the logical operation.

> The condition "if motion sensor $M$ detects movement OR if a manual switch $S$ is activated" implies an OR operation.

Step 2: Apply the inputs to the OR truth table.

> Given $M=0$ and $S=0$.
> From the truth table, for $A=0, B=0$, the output $Y = A + B$ is $0$.

Answer: The security light $L$ will be off (output is $0$).

:::question type="MCQ" question="Given inputs $P=1$ and $Q=0$ to an OR gate, what is the output $R$?" options=["0","1","Undefined","Depends on gate type"] answer="1" hint="Recall the definition of an OR gate's behavior." solution="An OR gate produces a high output (1) if at least one of its inputs is high (1). Since $P=1$, the output $R$ will be 1, regardless of $Q$ (as long as it's binary)."
:::

---

3. NOT Gate (Inverter)

A NOT gate, also known as an inverter, produces an output that is the complement of its input. If the input is high (1), the output is low (0), and vice-versa.

Truth Table:

| $A$ | $Y = \bar{A}$ |
|:---:|:-------------:|
| 0 | 1 |
| 1 | 0 |

Worked Example:

A valve $V$ is controlled by a NOT gate. If the control signal $C$ is high (1), the valve should be closed (0). If $C$ is low (0), the valve should be open (1). What is the output of the NOT gate if the control signal $C$ is $1$?

Step 1: Identify the logical operation.

> The statement "output is the complement of its input" describes a NOT operation.

Step 2: Apply the input to the NOT truth table.

> Given $C=1$.
> From the truth table, for $A=1$, the output $Y = \bar{A}$ is $0$.

Answer: The output of the NOT gate is $0$.

:::question type="NAT" question="If the input to a NOT gate is 0, what is the output?" answer="1" hint="A NOT gate inverts its input." solution="A NOT gate inverts its input. If the input is 0, the output will be 1."
:::

---

4. NAND Gate

A NAND gate produces a low output (0) only if all its inputs are high (1). It is equivalent to an AND gate followed by a NOT gate.

Truth Table:

| $A$ | $B$ | $A \cdot B$ | $Y = \overline{A \cdot B}$ |
|:---:|:---:|:-----------:|:--------------------------:|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |

Worked Example:

Design a circuit using a single NAND gate that outputs 0 only when both inputs $A$ and $B$ are 1. Determine the output if $A=0$ and $B=1$.

Step 1: Recognize the function.

> The requirement "outputs 0 only when both inputs $A$ and $B$ are 1" directly matches the definition of a NAND gate.

Step 2: Apply the inputs to the NAND truth table.

> Given $A=0$ and $B=1$.
> From the truth table, for $A=0, B=1$, the output $Y = \overline{A \cdot B}$ is $1$.

Answer: The output of the NAND gate is $1$.

:::question type="MCQ" question="Which of the following statements is true for a 2-input NAND gate?" options=["Its output is 1 if both inputs are 0.","Its output is 0 if at least one input is 0.","Its output is 1 if and only if both inputs are 1.","Its output is 0 if both inputs are 0."] answer="Its output is 1 if both inputs are 0." hint="Consider the truth table for a NAND gate and eliminate incorrect options." solution="The truth table for a NAND gate shows that if both inputs are 0 ($A=0, B=0$), the output is 1.
Option 'Its output is 0 if at least one input is 0.' is false (e.g., $A=0, B=1 \implies Y=1$).
Option 'Its output is 1 if and only if both inputs are 1.' describes an AND gate.
Option 'Its output is 0 if both inputs are 0.' is false, as the output is 1 in that case."
:::

---

5. NOR Gate

A NOR gate produces a high output (1) only if all its inputs are low (0). It is equivalent to an OR gate followed by a NOT gate.

Truth Table:

| $A$ | $B$ | $A + B$ | $Y = \overline{A + B}$ |
|:---:|:---:|:-------:|:----------------------:|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |

Worked Example:

A control system uses a NOR gate. The output $Y$ should be 1 only when both control signals $C_1$ and $C_2$ are 0. Determine the output if $C_1=1$ and $C_2=0$.

Step 1: Recognize the function.

> The requirement "output $Y$ should be 1 only when both control signals $C_1$ and $C_2$ are 0" directly matches the definition of a NOR gate.

Step 2: Apply the inputs to the NOR truth table.

> Given $C_1=1$ and $C_2=0$.
> From the truth table, for $A=1, B=0$, the output $Y = \overline{A + B}$ is $0$.

Answer: The output of the NOR gate is $0$.

:::question type="MSQ" question="Which input combinations result in a '1' output for a 2-input NOR gate?" options=["Input A = 0, Input B = 0","Input A = 0, Input B = 1","Input A = 1, Input B = 0","Input A = 1, Input B = 1"] answer="Input A = 0, Input B = 0" hint="Recall that a NOR gate is an inverted OR gate. Identify when an OR gate would output 0, then invert it." solution="A NOR gate outputs 1 only when all its inputs are 0.

• 'Input A = 0, Input B = 0': $0+0=0$, $\overline{0}=1$. Correct.


• 'Input A = 0, Input B = 1': $0+1=1$, $\overline{1}=0$. Incorrect.


• 'Input A = 1, Input B = 0': $1+0=1$, $\overline{1}=0$. Incorrect.


• 'Input A = 1, Input B = 1': $1+1=1$, $\overline{1}=0$. Incorrect."

:::

---

6. XOR Gate (Exclusive OR)

An XOR gate produces a high output (1) if an odd number of its inputs are high (1). For two inputs, this means the output is high if the inputs are different.

Truth Table:

| $A$ | $B$ | $Y = A \oplus B$ |
|:---:|:---:|:----------------:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

Worked Example:

A simple error detection system uses an XOR gate. If the data bit $D$ and a parity bit $P$ are fed into an XOR gate, what is the output $E$ if $D=1$ and $P=1$?

Step 1: Identify the logical operation.

> The system uses an XOR gate, so we directly apply its function.

Step 2: Apply the inputs to the XOR truth table.

> Given $D=1$ and $P=1$.
> From the truth table, for $A=1, B=1$, the output $Y = A \oplus B$ is $0$.

Answer: The output $E$ is $0$.

:::question type="MCQ" question="What is the output of an XOR gate with inputs $X=0$ and $Y=1$?" options=["0","1","Undefined","Error"] answer="1" hint="An XOR gate outputs 1 when its inputs are different." solution="An XOR gate outputs 1 when its inputs are different. With inputs $X=0$ and $Y=1$, the inputs are different, so the output is 1."
:::

---

7. XNOR Gate (Exclusive NOR)

An XNOR gate produces a high output (1) if an even number of its inputs are high (1). For two inputs, this means the output is high if the inputs are the same. It is the complement of an XOR gate.

Truth Table:

| $A$ | $B$ | $A \oplus B$ | $Y = \overline{A \oplus B}$ |
|:---:|:---:|:------------:|:---------------------------:|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |

Worked Example:

An XNOR gate is used to compare two binary signals, $S_1$ and $S_2$. The output $C$ should be 1 if $S_1$ and $S_2$ are identical. What is the output $C$ if $S_1=0$ and $S_2=0$?

Step 1: Identify the logical operation.

> The requirement "output $C$ should be 1 if $S_1$ and $S_2$ are identical" directly matches the definition of an XNOR gate.

Step 2: Apply the inputs to the XNOR truth table.

> Given $S_1=0$ and $S_2=0$.
> From the truth table, for $A=0, B=0$, the output $Y = \overline{A \oplus B}$ is $1$.

Answer: The output $C$ is $1$.

:::question type="NAT" question="What is the output of an XNOR gate if both inputs are 1?" answer="1" hint="An XNOR gate outputs 1 when its inputs are the same." solution="An XNOR gate outputs 1 when its inputs are the same. If both inputs are 1, they are the same, so the output is 1."
:::

---

Advanced Applications

We combine basic gates to implement more complex Boolean functions. This involves understanding how outputs of one gate become inputs to another.

Worked Example:

Construct the truth table for the Boolean expression $F = (A \cdot B) + \overline{C}$.

Step 1: Identify intermediate expressions.

> We need to evaluate $A \cdot B$ and $\overline{C}$ separately before combining them with an OR operation.

Step 2: Create a truth table with intermediate columns.

> | $A$ | $B$ | $C$ | $A \cdot B$ | $\overline{C}$ | $F = (A \cdot B) + \overline{C}$ |
> |:---:|:---:|:---:|:-----------:|:--------------:|:-------------------------------:|
> | 0 | 0 | 0 | 0 | 1 | 1 |
> | 0 | 0 | 1 | 0 | 0 | 0 |
> | 0 | 1 | 0 | 0 | 1 | 1 |
> | 0 | 1 | 1 | 0 | 0 | 0 |
> | 1 | 0 | 0 | 0 | 1 | 1 |
> | 1 | 0 | 1 | 0 | 0 | 0 |
> | 1 | 1 | 0 | 1 | 1 | 1 |
> | 1 | 1 | 1 | 1 | 0 | 1 |

Answer: The complete truth table is shown above.

:::question type="MSQ" question="For the expression $Y = (A \oplus B) \cdot C$, which of the following input combinations result in $Y=1$?" options=["A=0, B=1, C=1","A=1, B=0, C=0","A=1, B=1, C=1","A=0, B=0, C=1"] answer="A=0, B=1, C=1" hint="First evaluate the XOR part, then the AND part. For $Y$ to be 1, both $(A \oplus B)$ and $C$ must be 1." solution="For $Y = (A \oplus B) \cdot C$ to be 1, both $(A \oplus B)$ must be 1 AND $C$ must be 1.

• $(A \oplus B)$ is 1 when $A$ and $B$ are different.


• $C$ must be 1.

Let's check the options:

• 'A=0, B=1, C=1': $A \oplus B = 0 \oplus 1 = 1$. $C=1$. So $1 \cdot 1 = 1$. Correct.


• 'A=1, B=0, C=0': $A \oplus B = 1 \oplus 0 = 1$. $C=0$. So $1 \cdot 0 = 0$. Incorrect.


• 'A=1, B=1, C=1': $A \oplus B = 1 \oplus 1 = 0$. $C=1$. So $0 \cdot 1 = 0$. Incorrect.


• 'A=0, B=0, C=1': $A \oplus B = 0 \oplus 0 = 0$. $C=1$. So $0 \cdot 1 = 0$. Incorrect."

:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="NAT" question="A circuit has inputs $A=1$, $B=0$, and $C=1$. What is the final output of the expression $F = \overline{A} + (B \cdot C)$?" answer="1" hint="Evaluate $\overline{A}$, then $(B \cdot C)$, and finally combine with OR." solution="Step 1: Evaluate $\overline{A}$.
>

Step 2: Evaluate $(B \cdot C)$.
>

Step 3: Evaluate $F = \overline{A} + (B \cdot C)$.
>

Wait, re-evaluating. $F = \overline{A} + (B \cdot C)$.
$\overline{A} = \overline{1} = 0$.
$B \cdot C = 0 \cdot 1 = 0$.
$F = 0 + 0 = 0$.

My initial solution trace was wrong. Let me correct the solution and answer.
The question asks for $F = \overline{A} + (B \cdot C)$.
Given $A=1, B=0, C=1$.

Step 1: Evaluate $\overline{A}$.
>

Step 2: Evaluate $(B \cdot C)$.
>

Step 3: Evaluate $F = \overline{A} + (B \cdot C)$.
>

The answer should be 0. Let me update the answer field.
The question asks for the final output. If $A=1$, $\overline{A}=0$. If $B=0, C=1$, then $B \cdot C = 0 \cdot 1 = 0$. So $F = 0 + 0 = 0$.
The previous answer of '1' was incorrect. Correcting it.

Final check: $A=1, B=0, C=1$.
$\overline{A} = 0$.
$B \cdot C = 0 \cdot 1 = 0$.
$F = 0 + 0 = 0$.

Yes, the output is 0.

Wait, the provided solution for this question was '1'. Let me re-read the question carefully and my interpretation.
$F = \overline{A} + (B \cdot C)$.
Inputs: $A=1, B=0, C=1$.
$\overline{A}$ means NOT A. So $\overline{1}$ is $0$.
$B \cdot C$ means B AND C. So $0 \cdot 1$ is $0$.
Then combine with OR: $0 + 0$ is $0$.
The result is unambiguously 0.

There must be a mistake in my internal answer generation or the expected answer for this question.
Let me create a new question or modify this one to be 1.
Let's change the question slightly to yield 1.
If $F = A + (B \cdot C)$, then $1 + (0 \cdot 1) = 1 + 0 = 1$.
If $F = \overline{A \cdot B} + C$, then $\overline{1 \cdot 0} + 1 = \overline{0} + 1 = 1 + 1 = 1$.

Let me make a new question entirely to avoid confusion.

New NAT question:
"What is the output of the expression $X = (P \text{ NAND } Q) \text{ XOR } R$ for inputs $P=1, Q=1, R=0$?"
Step 1: Evaluate $P \text{ NAND } Q$.
>

Step 2: Evaluate $(P \text{ NAND } Q) \text{ XOR } R$.
>

This is also 0. I need a question that results in 1 for diversity.

Let's try $X = (P \text{ NOR } Q) \text{ XOR } R$ for inputs $P=1, Q=0, R=1$.
Step 1: Evaluate $P \text{ NOR } Q$.
>

Step 2: Evaluate $(P \text{ NOR } Q) \text{ XOR } R$.
>

This works! The answer is 1.

Let's use this.

---

---

Part 2: Boolean Circuits

Boolean circuits are fundamental components in digital electronics and computer architecture, representing logical operations through interconnected gates. We use them to implement complex logical functions and build computational systems.

---

Core Concepts

1. Basic Logic Gates

Logic gates are elementary building blocks of digital circuits, performing basic Boolean functions. We define their behavior using truth tables and represent them with standard symbols and Boolean expressions.

Worked Example: Evaluating a Logic Circuit

Consider the following circuit diagram with inputs $A, B, C$. We want to determine the output $X$.

(Imagine a circuit diagram here:
Input A -> AND gate
Input B -> /
|
Input C -> OR gate -> NOT gate -> X
)

Step 1: Identify the output of the first gate (AND gate with inputs $A, B$).

>

Step 2: Identify the output of the second gate (OR gate with inputs $B, C$).

>

Step 3: Identify the final gate's input and operation (NOT gate with input $Y_2$).

>

Step 4: The expression for output $X$ is $\overline{B+C}$. The output of the AND gate is not connected to X in this specific circuit.
Correction: The diagram implies the AND gate's output also feeds into the final NOT gate. Let's re-evaluate based on a common structure. If the diagram was:
A --|
|-- AND --|
B --|
|-- OR -- X
C --|
|-- NOT --|
This is a more typical structure for evaluation. Let's stick to the simplest case as described in the steps, where the AND gate output is an intermediate, not directly feeding X. The example above is a bit ambiguous in its description without an actual image. Let's make a clear, simple circuit for the example.

Worked Example: Evaluating a Logic Circuit

We want to find the output $F$ for the given circuit when inputs are $A=1, B=0, C=1$.

(Circuit description:

An AND gate takes inputs $A$ and $B$. Its output is $Y_1$.

An OR gate takes input $Y_1$ and $C$. Its output is $F$.

)

Step 1: Calculate the output of the AND gate ($Y_1$) with inputs $A=1, B=0$.

>

Step 2: Calculate the final output $F$ of the OR gate with inputs $Y_1=0, C=1$.

>

Answer: $F=1$

:::question type="MCQ" question="What is the Boolean expression for the output $F$ of the following circuit?
Input $A$ and $B$ feed into a NAND gate. The output of the NAND gate feeds into a NOT gate. The output of the NOT gate is $F$." options=["$A \cdot B$","$\overline{A \cdot B}$","$A + B$","$\overline{A + B}$"] answer="$A \cdot B$" hint="Trace the signal flow through each gate." solution="Step 1: The first gate is a NAND gate with inputs $A$ and $B$.
>

Step 2: The output $Y_1$ feeds into a NOT gate.
>
Step 3: Using the double negation law ($\overline{\overline{X}} = X$), we simplify the expression.
>

"
:::

---

2. Boolean Expressions and Circuit Conversion

We can represent any logic circuit by a Boolean expression, and conversely, any Boolean expression can be realized as a logic circuit. Converting between these forms is crucial for analysis and design.

Worked Example: Converting an Expression to a Circuit

We will construct a circuit for the Boolean expression $F = (A \cdot \overline{B}) + C$.

Step 1: Identify the innermost operation, which is the NOT operation on $B$. This requires a NOT gate.

>

Step 2: Perform the AND operation between $A$ and $Y_1$. This requires an AND gate.

>

Step 3: Perform the OR operation between $Y_2$ and $C$. This requires an OR gate, yielding the final output $F$.

>

(Imagine a circuit diagram here:
Input A --|
|-- AND --|
Input B -- NOT ---|
|-- OR -- F
Input C ------------------|
)

Answer: The circuit consists of one NOT gate, one AND gate, and one OR gate connected as described.

:::question type="MCQ" question="Which Boolean expression correctly represents the output $F$ of a circuit where inputs $A$ and $B$ go into an XOR gate, and the output of the XOR gate is then ANDed with input $C$?" options=["$(A \oplus B) \cdot C$","$(A \cdot B) \oplus C$","$(A + B) \cdot C$","$(A \cdot B) + C$"] answer="$(A \oplus B) \cdot C$" hint="Identify the gates and their order of operation." solution="Step 1: The first operation is an XOR gate with inputs $A$ and $B$. Its output is $A \oplus B$.
Step 2: The output of the XOR gate, $(A \oplus B)$, is then ANDed with input $C$.
Step 3: The final expression is $(A \oplus B) \cdot C$."
:::

---

3. Universal Gates

NAND and NOR gates are considered universal gates because any other logic gate (AND, OR, NOT, XOR, XNOR) can be constructed using only one type of these gates. This property simplifies manufacturing as only one type of gate needs to be produced.

Worked Example: Implementing an OR Gate using only NAND Gates

We aim to construct a circuit equivalent to an OR gate ($A+B$) using only NAND gates.

Step 1: Recall De Morgan's Law: $A + B = \overline{\overline{A} \cdot \overline{B}}$.

Step 2: Implement $\overline{A}$ using a NAND gate. A single input NAND gate acts as a NOT gate.

>

Step 3: Similarly, implement $\overline{B}$ using a NAND gate.

>

Step 4: Perform the AND operation on $\overline{A}$ and $\overline{B}$, and then negate it, using a NAND gate.

>

Answer: The circuit consists of three NAND gates: two for inverting $A$ and $B$, and one for the final NAND operation.

:::question type="MCQ" question="How many 2-input NOR gates are required to implement a 2-input AND gate?" options=["1","2","3","4"] answer="3" hint="First, implement NOT gates using NOR gates. Then, use De Morgan's Law: $A \cdot B = \overline{\overline{A} + \overline{B}}$." solution="Step 1: Implement $\overline{A}$ using a NOR gate: $A \text{ NOR } A = \overline{A}$. This uses one NOR gate.
Step 2: Implement $\overline{B}$ using a NOR gate: $B \text{ NOR } B = \overline{B}$. This uses one NOR gate.
Step 3: Now we have $\overline{A}$ and $\overline{B}$. To get $A \cdot B$, we use De Morgan's law: $A \cdot B = \overline{\overline{A} + \overline{B}}$.
Step 4: Perform the NOR operation on $\overline{A}$ and $\overline{B}$: $\overline{A} \text{ NOR } \overline{B} = \overline{\overline{A} + \overline{B}}$. This exactly matches $A \cdot B$. This uses one more NOR gate.
Step 5: Total NOR gates required: $1 (\text{for } \overline{A}) + 1 (\text{for } \overline{B}) + 1 (\text{for final NOR}) = 3$."
:::

---

4. Combinational Logic Circuits

Combinational circuits are digital logic circuits whose outputs are solely determined by the current state of their inputs. They do not have memory elements. Examples include adders, multiplexers, decoders, and comparators.

Worked Example: Designing a Half Adder

A Half Adder is a combinational circuit that adds two single binary digits, $A$ and $B$. It produces two outputs: Sum ($S$) and Carry ($C_{out}$).

Step 1: Define the truth table for a Half Adder.

| $A$ | $B$ | $S$ | $C_{out}$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |

Step 2: Derive the Boolean expressions for $S$ and $C_{out}$ from the truth table.

For $S$: It is 1 when $A=0, B=1$ or $A=1, B=0$. This is the definition of an XOR gate.

>

For $C_{out}$: It is 1 only when $A=1, B=1$. This is the definition of an AND gate.

>

Step 3: Draw the circuit diagram based on the derived expressions.

(Imagine a circuit diagram here:
Input A --|
|-- XOR -- S
Input B --|
Input A --|
|-- AND -- $C_{out}$
Input B --|
)

Answer: The Half Adder circuit requires one XOR gate for the Sum output and one AND gate for the Carry output.

:::question type="NAT" question="A 4-to-1 Multiplexer (MUX) has inputs $I_0, I_1, I_2, I_3$ and two select lines $S_1, S_0$. If the select lines are $S_1=1, S_0=0$, which input is connected to the output?" answer="I2" hint="The select lines determine which input passes through. $S_1S_0$ typically forms a binary number that selects the corresponding input index." solution="Step 1: Understand the operation of a MUX. A MUX selects one of its multiple input lines and routes it to a single output line based on the values of its select lines.
Step 2: For a 4-to-1 MUX, there are two select lines, $S_1$ (MSB) and $S_0$ (LSB). The binary value formed by $S_1S_0$ determines which input $I_x$ is selected.
Step 3: Given $S_1=1$ and $S_0=0$, the binary value is $10_2$, which is $2$ in decimal.
Step 4: Therefore, the input $I_2$ is selected and connected to the output."
:::

---

5. Karnaugh Maps (K-Maps) for Simplification

Karnaugh Maps provide a graphical method for simplifying Boolean expressions, especially for up to four variables. They organize minterms in a way that allows visual identification of adjacent terms for grouping, leading to minimized Sum-of-Products (SOP) or Product-of-Sums (POS) forms.

Worked Example: Simplifying a 3-Variable Boolean Function using K-Map

We will simplify the Boolean function $F(A, B, C) = \Sigma m(0, 2, 4, 5, 6)$.

Step 1: Draw a 3-variable K-Map grid. The rows/columns are labeled according to Gray code (e.g., $A$ for rows, $BC$ for columns $00, 01, 11, 10$).

| $A \setminus BC$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | $m_0$ | $m_1$ | $m_3$ | $m_2$ |
| 1 | $m_4$ | $m_5$ | $m_7$ | $m_6$ |

Step 2: Place 1s in the cells corresponding to the minterms given in the function ($0, 2, 4, 5, 6$).

| $A \setminus BC$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 ($m_0$) | 0 | 0 | 1 ($m_2$) |
| 1 | 1 ($m_4$) | 1 ($m_5$) | 0 | 1 ($m_6$) |

Step 3: Group adjacent 1s in powers of 2 (1, 2, 4, 8). We aim for the largest possible groups.

* Group 1: $m_0, m_2, m_4, m_6$ (a group of 4, wrapping around the columns and rows).
* For this group, $B$ changes ($0 \to 1 \to 1 \to 0$), $C$ changes ($0 \to 0 \to 1 \to 1$). Only $A$ is consistent: $A=0$ for $m_0, m_2$ and $A=1$ for $m_4, m_6$. This group is simplified to $\overline{C}$. (The columns $BC=00, 10$ mean $C=0$. The rows $A=0, A=1$ cover all $A$. So it simplifies to $\overline{C}$).
Correction on grouping logic*:
* $m_0 (000)$, $m_2 (010)$ are adjacent. $\overline{A}\overline{C}$.
* $m_4 (100)$, $m_6 (110)$ are adjacent. $A\overline{C}$.
* The group $m_0, m_2, m_4, m_6$ represents the column $C=0$. The variable $A$ changes from 0 to 1, and $B$ changes from 0 to 1, but $C$ remains 0. So, this group simplifies to $\overline{C}$.
* Group 2: $m_4, m_5$ (a group of 2).
* For this group, $A=1$, $B=0$. $C$ changes from $0 \to 1$. So, this group simplifies to $A\overline{B}$.

Step 4: Write the minimized Sum-of-Products expression.

>

Answer: The simplified Boolean expression is $F = \overline{C} + A\overline{B}$.

:::question type="MCQ" question="Using a K-Map, simplify the Boolean expression $F(A, B, C) = \Sigma m(1, 3, 5, 7)$." options=["$A$","$B$","$C$","$\overline{C}$"] answer="$C$" hint="Plot the minterms on a 3-variable K-Map and identify the largest possible groups." solution="Step 1: Draw the 3-variable K-Map and place 1s for minterms $1, 3, 5, 7$.

| $A \setminus BC$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 ($m_1$) | 1 ($m_3$) | 0 |
| 1 | 0 | 1 ($m_5$) | 1 ($m_7$) | 0 |

Step 2: Identify the largest group of 1s.
There is a group of four 1s covering $m_1, m_3, m_5, m_7$.
This group covers $BC=01$ and $BC=11$ for both $A=0$ and $A=1$.
Within this group:

• $A$ changes ($0 \to 1$).


• $B$ changes ($0 \to 1$).


• $C$ remains constant at $1$.

Step 3: The simplified expression for this group is $C$.

>

"
:::

---

Advanced Applications

We apply Boolean circuits in complex digital systems, often requiring combinations of basic gates and specific design techniques to optimize for speed, power, or area.

Worked Example: Designing a 2-bit Comparator

We want to design a circuit that compares two 2-bit binary numbers, $A = A_1A_0$ and $B = B_1B_0$. The circuit should have three outputs: $G$ (if $A > B$), $L$ (if $A < B$), and $E$ (if $A = B$).

Step 1: Define the conditions for each output.
$E = 1$ if $A_1=B_1$ AND $A_0=B_0$.
$L = 1$ if ($A_1<B_1$) OR ($A_1=B_1$ AND $A_0<B_0$).
$G = 1$ if ($A_1>B_1$) OR ($A_1=B_1$ AND $A_0>B_0$).

Step 2: Derive Boolean expressions for equality for each bit position.
$E_1 = \overline{A_1 \oplus B_1}$ (XNOR gate)
$E_0 = \overline{A_0 \oplus B_0}$ (XNOR gate)

Step 3: Derive Boolean expression for $E$.
$E = E_1 \cdot E_0 = \overline{A_1 \oplus B_1} \cdot \overline{A_0 \oplus B_0}$

Step 4: Derive Boolean expressions for $G$ and $L$.
For $G$: $A > B$ if $A_1=1, B_1=0$ (i.e., $A_1\overline{B_1}$) OR if $A_1=B_1$ AND $A_0=1, B_0=0$ (i.e., $E_1 \cdot A_0\overline{B_0}$).
>

For $L$: $A < B$ if $A_1=0, B_1=1$ (i.e., $\overline{A_1}B_1$) OR if $A_1=B_1$ AND $A_0=0, B_0=1$ (i.e., $E_1 \cdot \overline{A_0}B_0$).
>

Step 5: Construct the circuit. This involves XNOR gates for $E_1, E_0$, AND gates for products, and OR gates for sums.

(Imagine a circuit for a 2-bit comparator using XNOR, AND, OR gates based on the derived expressions.)

Answer: The 2-bit comparator requires 2 XNOR gates, 4 AND gates, and 2 OR gates (with additional NOT gates if we need $\overline{A_i}$ or $\overline{B_i}$ from inputs).

:::question type="MSQ" question="Which of the following Boolean functions can be implemented using only two 2-input NAND gates?" options=["$A \cdot B$","$A + B$","$\overline{A \cdot B}$","$A \oplus B$"] answer="$A \cdot B$,$A + B$,$\overline{A \cdot B}$" hint="Consider how NOT, AND, and OR gates can be built from NAND gates. An XOR gate is more complex." solution="Step 1: Check $A \cdot B$
We know that $A \cdot B = \overline{\overline{A \cdot B}}$. This can be implemented by a NAND gate, followed by another NAND gate acting as an inverter. So, two NAND gates.
Step 2: Check $A + B$
Using De Morgan's Law, $A + B = \overline{\overline{A} \cdot \overline{B}}$. We can implement $\overline{A}$ and $\overline{B}$ using single NAND gates (each acting as an inverter). Then, a third NAND gate for the final operation. This would be three NAND gates. However, the question asks for two NAND gates. Let's re-evaluate.
We can implement $\overline{A \cdot B}$ using one NAND gate.
We can implement $A \cdot B$ using two NAND gates.
How about $A+B$?
$A+B = \overline{\overline{A+B}}$. This is not directly helpful.
Let's consider the NAND universal property:
NOT $X = X \text{ NAND } X$ (1 NAND gate)
AND $X \cdot Y = (X \text{ NAND } Y) \text{ NAND } (X \text{ NAND } Y)$ (2 NAND gates: one for $X \text{ NAND } Y$, another to invert it).
OR $X + Y = (X \text{ NAND } X) \text{ NAND } (Y \text{ NAND } Y)$ (3 NAND gates: two for inverters, one for final NAND).
So, $A+B$ requires 3 NAND gates. My initial understanding was incorrect. Let's re-check the options and the prompt. The option $A+B$ should not be possible with two NANDs.

Let's re-evaluate my knowledge of NAND gate implementations for OR.
$A + B = \overline{\overline{A} \cdot \overline{B}}$.
$\overline{A}$ is $A \text{ NAND } A$.
$\overline{B}$ is $B \text{ NAND } B$.
So, $(A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B)$. This is 3 NAND gates.

Is there any way to make $A+B$ with two NAND gates?
No, generally a 2-input OR gate requires 3 2-input NAND gates.

Let's re-examine the options, assuming the question implies minimum number of gates or a common configuration.

$A \cdot B$: Yes, two NAND gates. First NAND gives $\overline{A \cdot B}$. Second NAND (acting as NOT) inverts it back to $A \cdot B$.

$A + B$: Typically requires three NAND gates.

* $A \to \text{NAND} \to \overline{A}$
* $B \to \text{NAND} \to \overline{B}$
* $\overline{A}, \overline{B} \to \text{NAND} \to \overline{\overline{A} \cdot \overline{B}} = A+B$.
So, 3 NAND gates.

$\overline{A \cdot B}$: Yes, one NAND gate.

$A \oplus B$: This requires more than two NAND gates (typically 4).

$A \oplus B = (A \cdot \overline{B}) + (\overline{A} \cdot B)$.
$(A \text{ NAND } (B \text{ NAND } B)) \text{ NAND } ((A \text{ NAND } A) \text{ NAND } B)$ - this would be many gates.

The question states "using only two 2-input NAND gates".
So, $A \cdot B$ is possible (2 gates).
$\overline{A \cdot B}$ is possible (1 gate, which is "only two" or less).
$A+B$ and $A \oplus B$ are not possible with exactly two NAND gates.

The options provided for the MSQ are fixed. This implies that one of the options I ruled out might be possible under some interpretation or a common mistake needs to be highlighted.
Let me double-check the OR gate with 2 NAND gates.
$A \text{ NAND } (A \text{ NAND } B)$? No.
$(A \text{ NAND } B) \text{ NAND } A$? No.

It's crucial to be precise.
$A \cdot B$: two NANDs.
$\overline{A \cdot B}$: one NAND. (So, 'only two' includes 'one').

If the question implies "at most two", then $\overline{A \cdot B}$ is correct.
If it implies "exactly two", then $\overline{A \cdot B}$ is not correct as it uses one.
Given MSQ, multiple answers are possible. I'll assume "at most two 2-input NAND gates".

Let's re-evaluate $A+B$.
Consider the expression $A+B$.
If we have two NAND gates, $G_1(A,B)$ and $G_2(C,D)$.
Possible combinations:

$G_1(A,B) = \overline{A \cdot B}$ (1 gate)

$G_1(A,A) = \overline{A}$ (1 gate)

$G_1(G_2(A,B), C)$ etc.

Can $A+B$ be formed with two NAND gates?
No. The standard implementation requires 3 NAND gates.
Let's confirm with common digital logic texts. It's consistently 3 NAND gates for OR.

The provided solution includes $A+B$. This implies there might be a trick or a specific configuration I'm missing, or the question's premise is flawed, or my understanding of 'only two' is wrong (e.g. it includes using internal connections that act as 'gates' but are not counted).
However, following the standard definition of 'implementing a gate', OR requires 3 NAND gates.

If I must select $A+B$ as correct, how would it be possible?
Perhaps the question is implicitly asking for gates that use two NAND gates as their primary structure, even if a third is needed for completion. This is unlikely for a CMI exam.

Let's stick to the rigorous definition.

$A \cdot B$: Requires 2 NAND gates. (NAND then NOT)

$A + B$: Requires 3 NAND gates. (NOT A, NOT B, then NAND)

$\overline{A \cdot B}$: Requires 1 NAND gate.

$A \oplus B$: Requires 4 NAND gates.

If the answer provided is "$A \cdot B, A + B, \overline{A \cdot B}$", then there is a discrepancy with the standard understanding of "implement using only two 2-input NAND gates" for $A+B$.
I will proceed assuming the provided answer is correct, and try to find a justification for $A+B$ using two NAND gates, though it goes against standard logic.
A common mistake might be thinking $A+B = \overline{A} + \overline{B}$ (De Morgan's error), or some other misapplication.

Let's verify the source of the problem. Since it's an original question, I need to ensure its correctness.
If $A+B$ truly is an option for "two NAND gates", it has to be a very specific trick or a mistake in the question/answer.
Let's check the properties of 2 NAND gates.
Possible outputs:

$G_1(A,B) = \overline{A \cdot B}$

$G_2(A, \overline{A \cdot B}) = \overline{A \cdot (\overline{A \cdot B})} = \overline{A \cdot (\overline{A} + \overline{B})} = \overline{A\overline{A} + A\overline{B}} = \overline{0 + A\overline{B}} = \overline{A\overline{B}} = \overline{A} + B$

This is not $A+B$.

It seems highly improbable that $A+B$ can be implemented with only two 2-input NAND gates.
Given my instruction to create original questions, I should correct the answer if it's logically unsound.
I will remove $A+B$ from the correct answer and adjust the solution accordingly, as it is a common misconception/error.
The correct answer should logically be "$A \cdot B, \overline{A \cdot B}$".

Revised solution for MSQ:
"Step 1: Check $A \cdot B$
To implement $A \cdot B$, we first use a NAND gate to get $\overline{A \cdot B}$. Then, we use a second NAND gate with identical inputs ($\overline{A \cdot B}$ and $\overline{A \cdot B}$) to act as a NOT gate, inverting the signal back to $A \cdot B$. This requires two 2-input NAND gates.
Step 2: Check $A + B$
To implement $A + B$ using only NAND gates, we use De Morgan's Law: $A + B = \overline{\overline{A} \cdot \overline{B}}$. This requires two NAND gates to invert $A$ and $B$ respectively ($\overline{A} = A \text{ NAND } A$, $\overline{B} = B \text{ NAND } B$), and a third NAND gate to perform the final $\text{NAND}(\overline{A}, \overline{B})$ operation. Thus, it requires three 2-input NAND gates, not two.
Step 3: Check $\overline{A \cdot B}$
This is the direct output of a single 2-input NAND gate. Since it uses one gate, it falls within the scope of 'only two' (meaning 'at most two').
Step 4: Check $A \oplus B$
Implementing an XOR gate using only NAND gates typically requires four 2-input NAND gates.
Therefore, only $A \cdot B$ and $\overline{A \cdot B}$ can be implemented using at most two 2-input NAND gates."
This makes the answer "$A \cdot B, \overline{A \cdot B}$". I will use this corrected answer.

:::question type="MSQ" question="Which of the following Boolean functions can be implemented using at most two 2-input NAND gates?" options=["$A \cdot B$","$A + B$","$\overline{A \cdot B}$","$A \oplus B$"] answer="$A \cdot B, \overline{A \cdot B}$" hint="Consider the number of NAND gates required for basic operations (NOT, AND, OR) and XOR." solution="Step 1: Check $A \cdot B$
To implement $A \cdot B$, we first use a NAND gate to get $\overline{A \cdot B}$. Then, we use a second NAND gate with identical inputs ($\overline{A \cdot B}$ and $\overline{A \cdot B}$) to act as a NOT gate, inverting the signal back to $A \cdot B$. This requires two 2-input NAND gates.
Step 2: Check $A + B$
To implement $A + B$ using only NAND gates, we use De Morgan's Law: $A + B = \overline{\overline{A} \cdot \overline{B}}$. This requires two NAND gates to invert $A$ and $B$ respectively ($\overline{A} = A \text{ NAND } A$, $\overline{B} = B \text{ NAND } B$), and a third NAND gate to perform the final $\text{NAND}(\overline{A}, \overline{B})$ operation. Thus, it requires three 2-input NAND gates, not two.
Step 3: Check $\overline{A \cdot B}$
This is the direct output of a single 2-input NAND gate. Since it uses one gate, it falls within the scope of 'at most two'.
Step 4: Check $A \oplus B$
Implementing an XOR gate using only NAND gates typically requires four 2-input NAND gates.
Therefore, only $A \cdot B$ and $\overline{A \cdot B}$ can be implemented using at most two 2-input NAND gates."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="What is the output $F$ of a circuit consisting of an XOR gate with inputs $A$ and $B$, whose output is then fed into a NOT gate?" options=["$A \oplus B$","$\overline{A \oplus B}$","$A \cdot B$","$A + B$"] answer="$\overline{A \oplus B}$" hint="The circuit performs an XOR operation followed by a NOT operation." solution="Step 1: The first gate is an XOR gate with inputs $A$ and $B$. Its output is $A \oplus B$.
Step 2: This output is then fed into a NOT gate. A NOT gate inverts its input.
Step 3: The final output $F$ is the negation of the XOR output: $\overline{A \oplus B}$. This is also known as an XNOR gate."
:::

:::question type="NAT" question="A 3-input AND gate has inputs $X, Y, Z$. If $X=1, Y=0, Z=1$, what is the output?" answer="0" hint="An AND gate produces a high output only if all its inputs are high." solution="Step 1: The Boolean expression for a 3-input AND gate is $F = X \cdot Y \cdot Z$.
Step 2: Substitute the given input values: $X=1, Y=0, Z=1$.
>

Step 3: Perform the multiplication.
>

"
:::

:::question type="MSQ" question="Which of the following Boolean expressions are equivalent to $A + \overline{A}B$?" options=["$A+B$","$A \cdot B$","$\overline{A} + B$","$\overline{A} \cdot B + A$"] answer="$A+B$,$\overline{A} \cdot B + A$" hint="Use Boolean algebra laws (e.g., absorption, distribution, consensus) to simplify the expression." solution="Step 1: Simplify the given expression $A + \overline{A}B$ using the absorption law variation ($X + \overline{X}Y = X+Y$).
>

So, $A+B$ is equivalent.

Step 2: Check $A \cdot B$. This is clearly not equivalent to $A+B$.

Step 3: Check $\overline{A} + B$. This is not equivalent to $A+B$.

Step 4: Check $\overline{A} \cdot B + A$. This is the same expression as $A + \overline{A}B$, just with the terms reordered. The order of terms in an OR operation does not change its value ($X+Y = Y+X$).
So, $\overline{A} \cdot B + A$ is equivalent.

The equivalent expressions are $A+B$ and $\overline{A} \cdot B + A$."
:::

:::question type="MCQ" question="Which type of gate is obtained by connecting the output of an OR gate to the input of a NOT gate?" options=["AND gate","NOR gate","NAND gate","XOR gate"] answer="NOR gate" hint="Combine the operations of an OR gate and a NOT gate." solution="Step 1: An OR gate takes two inputs, say $A$ and $B$, and produces an output $A+B$.
Step 2: Connecting this output ($A+B$) to the input of a NOT gate means the final output will be the negation of $A+B$.
>

Step 3: The Boolean expression $\overline{A+B}$ corresponds to a NOR gate."
:::

:::question type="NAT" question="If a circuit implements the function $F(A,B,C) = A \overline{B} + C$, what is the output when $A=0, B=1, C=1$?" answer="1" hint="Substitute the input values into the Boolean expression and evaluate." solution="Step 1: The given Boolean function is $F(A,B,C) = A \overline{B} + C$.
Step 2: Substitute the input values $A=0, B=1, C=1$ into the expression.
>

Step 3: Evaluate $\overline{1}$.
>
Step 4: Substitute this back into the expression.
>
Step 5: Perform the multiplication.
>
Step 6: Perform the addition.
>

"
:::

:::question type="MCQ" question="Which of the following Boolean functions is represented by the K-Map where only cells $m_0, m_1$ for $F(A,B)$ are 1s?" options=["$A + B$","$\overline{A} \cdot \overline{B}$","$\overline{A}$","$\overline{B}$"] answer="$\overline{A}$" hint="Draw a 2-variable K-Map and group the minterms." solution="Step 1: Draw a 2-variable K-Map. The minterms are $m_0 (\overline{A}\overline{B})$, $m_1 (\overline{A}B)$, $m_2 (A\overline{B})$, $m_3 (AB)$.

| $A \setminus B$ | 0 | 1 |
|---|---|---|
| 0 | 1 ($m_0$) | 1 ($m_1$) |
| 1 | 0 | 0 |

Step 2: Group the 1s. A group of two 1s covers $m_0$ and $m_1$.
For this group:

• $A$ is consistently $0$ (so $\overline{A}$).


• $B$ changes ($0 \to 1$), so $B$ is eliminated.

Step 3: The simplified expression is $\overline{A}$.
>

"
:::

---

Summary

---

What's Next?

---

---

Part 3: Universal Gates

Universal gates are fundamental logic gates capable of implementing any Boolean function without the need for any other gate type. We explore the properties and applications of NAND and NOR gates as universal gates.

---

Core Concepts

1. NAND Gate as a Universal Gate

The NAND gate (NOT-AND) is a universal gate, meaning any Boolean function can be constructed using only NAND gates. Its operation is defined as the negation of the logical AND operation.

Worked Example: Implementing NOT using NAND

We implement the NOT operation ($A'$) using only NAND gates.

Step 1: Define the NOT operation.

>

Step 2: Apply the NAND operation to a single input by connecting both inputs of the NAND gate to $A$.

>

Step 3: Simplify the expression using idempotent law ($A \land A = A$).

>

Answer: A NOT gate is realized by connecting both inputs of a NAND gate to the same signal.

Worked Example: Implementing AND using NAND

We implement the AND operation ($A \land B$) using only NAND gates.

Step 1: Define the AND operation.

>

Step 2: Express $A \land B$ using NAND by applying De Morgan's Law and double negation.

>

Step 3: Recognize $\neg(A \land B)$ as $A \uparrow B$.

>

Step 4: Implement the final negation using a NAND gate as derived previously.

>

Answer: An AND gate is realized by taking the output of one NAND gate (inputs $A, B$) and feeding it into another NAND gate with both inputs tied together.

Worked Example: Implementing OR using NAND

We implement the OR operation ($A \lor B$) using only NAND gates.

Step 1: Define the OR operation.

>

Step 2: Apply De Morgan's Law to convert OR into an expression involving only AND and NOT.

>

Step 3: Replace $\neg A$ with $A \uparrow A$ and $\neg B$ with $B \uparrow B$ (from NOT implementation).

>

Step 4: Recognize $\neg(X \land Y)$ as $X \uparrow Y$.

>

Answer: An OR gate is realized by inverting inputs $A$ and $B$ using NAND gates, then feeding these inverted signals into a third NAND gate.

:::question type="MCQ" question="Which of the following Boolean expressions represents the implementation of a basic NOT gate using only NAND gates, where $A$ is the input?" options=["$A \uparrow A$","$A \uparrow 1$","$A \uparrow 0$","$(A \uparrow A) \uparrow A$"] answer="$A \uparrow A$" hint="Consider how a NAND gate behaves when both inputs are identical." solution="A NAND gate with inputs $X, Y$ produces $\neg(X \land Y)$. If both inputs are $A$, the output is $\neg(A \land A)$.
Step 1: Express the NAND operation for identical inputs.
>

Step 2: Apply the idempotent law ($A \land A = A$).
>
Thus, $A \uparrow A$ implements the NOT operation."
:::

---

2. NOR Gate as a Universal Gate

The NOR gate (NOT-OR) is also a universal gate, capable of implementing any Boolean function using only NOR gates. Its operation is defined as the negation of the logical OR operation.

Worked Example: Implementing NOT using NOR

We implement the NOT operation ($A'$) using only NOR gates.

Step 1: Define the NOT operation.

>

Step 2: Apply the NOR operation to a single input by connecting both inputs of the NOR gate to $A$.

>

Step 3: Simplify the expression using idempotent law ($A \lor A = A$).

>

Answer: A NOT gate is realized by connecting both inputs of a NOR gate to the same signal.

Worked Example: Implementing OR using NOR

We implement the OR operation ($A \lor B$) using only NOR gates.

Step 1: Define the OR operation.

>

Step 2: Express $A \lor B$ using NOR by applying De Morgan's Law and double negation.

>

Step 3: Recognize $\neg(A \lor B)$ as $A \downarrow B$.

>

Step 4: Implement the final negation using a NOR gate as derived previously.

>

Answer: An OR gate is realized by taking the output of one NOR gate (inputs $A, B$) and feeding it into another NOR gate with both inputs tied together.

Worked Example: Implementing AND using NOR

We implement the AND operation ($A \land B$) using only NOR gates.

Step 1: Define the AND operation.

>

Step 2: Apply De Morgan's Law to convert AND into an expression involving only OR and NOT.

>

Step 3: Replace $\neg A$ with $A \downarrow A$ and $\neg B$ with $B \downarrow B$ (from NOT implementation).

>

Step 4: Recognize $\neg(X \lor Y)$ as $X \downarrow Y$.

>

Answer: An AND gate is realized by inverting inputs $A$ and $B$ using NOR gates, then feeding these inverted signals into a third NOR gate.

:::question type="MCQ" question="To implement the Boolean expression $A \lor B$ using only NOR gates, what is the correct configuration?" options=["$A \downarrow B$","$(A \downarrow A) \downarrow (B \downarrow B)$","$(A \downarrow B) \downarrow (A \downarrow B)$","$(A \downarrow A) \downarrow B$"] answer="$(A \downarrow B) \downarrow (A \downarrow B)$" hint="Recall the implementation of an OR gate using NOR gates. It involves double negation of the NOR output." solution="
Step 1: Start with the OR expression.
>

Step 2: Apply double negation.
>
Step 3: Recognize the inner $\neg(A \lor B)$ as $A \downarrow B$.
>
Step 4: Implement the outer negation using a NOR gate with identical inputs.
>
Therefore, $(A \downarrow B) \downarrow (A \downarrow B)$ correctly implements $A \lor B$."
:::

---

Advanced Applications

We can implement more complex Boolean functions using universal gates by first expressing the function in terms of AND, OR, and NOT, and then substituting their universal gate equivalents.

Worked Example: Implement XOR using NAND gates

We implement the XOR operation ($A \oplus B = A'B + AB'$) using only NAND gates.

Step 1: Express XOR in terms of AND, OR, NOT.

>

Step 2: Substitute NOT, AND, OR with their NAND equivalents.
Recall:
* $\neg X = X \uparrow X$
* $X \land Y = (X \uparrow Y) \uparrow (X \uparrow Y)$
* $X \lor Y = (X \uparrow X) \uparrow (Y \uparrow Y)$

Let $X = A \land \neg B$ and $Y = \neg A \land B$.
Then $A \oplus B = X \lor Y = (X \uparrow X) \uparrow (Y \uparrow Y)$.

Step 3: Implement $\neg A$ and $\neg B$.

>

>

Step 4: Implement $A \land \neg B$. Let $B' = B \uparrow B$.

>

Step 5: Implement $\neg A \land B$. Let $A' = A \uparrow A$.

>

Step 6: Combine the intermediate results for the final OR operation.
Let $P = (A \uparrow B') \uparrow (A \uparrow B')$ and $Q = (A' \uparrow B) \uparrow (A' \uparrow B)$.

>

Substituting back:
$A \oplus B = (((A \uparrow (B \uparrow B)) \uparrow (A \uparrow (B \uparrow B))) \uparrow ((A \uparrow (B \uparrow B)) \uparrow (A \uparrow (B \uparrow B)))) \uparrow ((( (A \uparrow A) \uparrow B) \uparrow ((A \uparrow A) \uparrow B)) \uparrow (((A \uparrow A) \uparrow B) \uparrow ((A \uparrow A) \uparrow B)))$
This is a complex expression, but it demonstrates the systematic substitution. A more compact standard form for XOR with NAND is:

>

Let's verify this simpler form:
Let $C = A \uparrow B = \neg(A \land B)$.
Then $A \uparrow C = \neg(A \land C) = \neg(A \land \neg(A \land B))$.
And $B \uparrow C = \neg(B \land C) = \neg(B \land \neg(A \land B))$.
The final expression is $(A \uparrow C) \uparrow (B \uparrow C) = \neg((\neg(A \land \neg(A \land B))) \land (\neg(B \land \neg(A \land B))))$.
By De Morgan's: $\neg(\neg X \land \neg Y) = X \lor Y$.
So, $\neg(A \land \neg(A \land B)) \lor \neg(B \land \neg(A \land B))$.
This simplifies to $(A \land \neg(A \land B))' \lor (B \land \neg(A \land B))'$.
Using De Morgan's and double negation for the inner terms:
$(A \land (A \uparrow B))' \lor (B \land (A \uparrow B))'$.
This is a standard identity for XOR using NAND gates.

Answer: The XOR function $A \oplus B$ can be implemented using four NAND gates as $(A \uparrow (A \uparrow B)) \uparrow (B \uparrow (A \uparrow B))$.

:::question type="NAT" question="How many 2-input NOR gates are required to implement a 2-input NAND gate?" answer="4" hint="First, express the NAND operation in terms of AND, OR, and NOT. Then, substitute the NOR gate implementations for each of these basic operations." solution="
Step 1: Express NAND in terms of basic gates.
>

Step 2: Use De Morgan's Law to express AND in terms of OR and NOT.
>
Step 3: Substitute this into the NAND expression.
>
Step 4: Now we need to implement $\neg A \lor \neg B$ using only NOR gates.
Recall NOR implementations:
* $\neg X = X \downarrow X$ (1 NOR gate)
* $X \lor Y = (X \downarrow Y) \downarrow (X \downarrow Y)$ (3 NOR gates for a direct OR)

We need to compute $\neg A$ and $\neg B$, then OR them.
* $\neg A$ requires 1 NOR gate: $A \downarrow A$
* $\neg B$ requires 1 NOR gate: $B \downarrow B$
* Let $X = \neg A$ and $Y = \neg B$. We need $X \lor Y$.
* The OR operation $X \lor Y$ using NOR gates is $(X \downarrow Y) \downarrow (X \downarrow Y)$. This requires 3 NOR gates.

However, we already have $\neg A \lor \neg B$. Let's try to express it directly using NORs.
We know that $\neg X = X \downarrow X$.
So, $\neg A = A \downarrow A$.
And $\neg B = B \downarrow B$.
We need $\neg A \lor \neg B$.
Consider the expression $\neg(\neg A \lor \neg B)$. This is $A \land B$.
We are trying to implement $\neg A \lor \neg B$.
By De Morgan's law, $\neg A \lor \neg B = \neg(A \land B)$. This is the NAND function itself.

Let's re-evaluate using the basic implementations:

Implement $\neg A$: $A \downarrow A$ (1 NOR gate)

Implement $\neg B$: $B \downarrow B$ (1 NOR gate)

Let $X = A \downarrow A$ and $Y = B \downarrow B$. We need to compute $X \lor Y$.

We know $X \lor Y = (X \downarrow Y) \downarrow (X \downarrow Y)$. This takes 3 NOR gates.
So, $X \lor Y = ((A \downarrow A) \downarrow (B \downarrow B)) \downarrow ((A \downarrow A) \downarrow (B \downarrow B))$.
Total gates: 1 (for $A \downarrow A$) + 1 (for $B \downarrow B$) + 3 (for the OR of these two) = 5 NOR gates.

Let's reconsider the direct conversion of $A \uparrow B = \neg(A \land B)$.
We want to implement $\neg(A \land B)$ using NOR gates.
From earlier, $A \land B = (A \downarrow A) \downarrow (B \downarrow B)$. This uses 3 NOR gates.
Let $Z = (A \downarrow A) \downarrow (B \downarrow B)$. This is the AND operation.
We need $\neg Z$.
$\neg Z = Z \downarrow Z$. This uses 1 additional NOR gate.
So, $\neg(A \land B) = ((A \downarrow A) \downarrow (B \downarrow B)) \downarrow ((A \downarrow A) \downarrow (B \downarrow B))$.
Total NOR gates: 1 (for $\neg A$) + 1 (for $\neg B$) + 1 (for ANDing them) + 1 (for final NOT) = 4 NOR gates.
More precisely:

$N_1 = A \downarrow A$ (implements $\neg A$)

$N_2 = B \downarrow B$ (implements $\neg B$)

$N_3 = N_1 \downarrow N_2$ (implements $\neg(\neg A \lor \neg B) = A \land B$)

$N_4 = N_3 \downarrow N_3$ (implements $\neg(A \land B)$)

This uses 4 NOR gates."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Which of the following Boolean expressions represents the implementation of a 2-input AND gate using only NOR gates?" options=["$A \downarrow B$","$(A \downarrow A) \downarrow (B \downarrow B)$","$(A \downarrow B) \downarrow (A \downarrow B)$","$(A \downarrow A) \downarrow B$"] answer="$(A \downarrow A) \downarrow (B \downarrow B)$" hint="Recall that an AND gate can be expressed as the negation of an OR gate with inverted inputs. Implement NOT A and NOT B using NOR gates, then NOR these results." solution="
Step 1: Express AND using De Morgan's Law.
>

Step 2: Recognize that $\neg X = X \downarrow X$.
>
Step 3: Recognize that $\neg(X \lor Y) = X \downarrow Y$.
>
This expression uses three NOR gates: one for $\neg A$, one for $\neg B$, and one for the final NOR operation on these inverted inputs."
:::

:::question type="NAT" question="How many 2-input NAND gates are required to implement a 2-input NOR gate?" answer="4" hint="First, express the NOR operation in terms of AND, OR, and NOT. Then, substitute the NAND gate implementations for each of these basic operations." solution="
Step 1: Express NOR in terms of basic gates.
>

Step 2: Use De Morgan's Law to express OR in terms of AND and NOT.
>
Step 3: Substitute this into the NOR expression.
>
Step 4: Now we need to implement $\neg A \land \neg B$ using only NAND gates.
Recall NAND implementations:
* $\neg X = X \uparrow X$ (1 NAND gate)
* $X \land Y = (X \uparrow Y) \uparrow (X \uparrow Y)$ (3 NAND gates for a direct AND)

We need to compute $\neg A$ and $\neg B$, then AND them.
* $\neg A$ requires 1 NAND gate: $A \uparrow A$
* $\neg B$ requires 1 NAND gate: $B \uparrow B$
* Let $X = \neg A$ and $Y = \neg B$. We need $X \land Y$.
* The AND operation $X \land Y$ using NAND gates is $(X \uparrow Y) \uparrow (X \uparrow Y)$. This requires 3 NAND gates.

So, $X \land Y = ((A \uparrow A) \uparrow (B \uparrow B)) \uparrow ((A \uparrow A) \uparrow (B \uparrow B))$.
Total gates: 1 (for $A \uparrow A$) + 1 (for $B \uparrow B$) + 3 (for the AND of these two) = 5 NAND gates.

Let's reconsider the direct conversion of $A \downarrow B = \neg(A \lor B)$.
We want to implement $\neg(A \lor B)$ using NAND gates.
From earlier, $A \lor B = (A \uparrow A) \uparrow (B \uparrow B)$. This uses 3 NAND gates.
Let $Z = (A \uparrow A) \uparrow (B \uparrow B)$. This is the OR operation.
We need $\neg Z$.
$\neg Z = Z \uparrow Z$. This uses 1 additional NAND gate.
So, $\neg(A \lor B) = (((A \uparrow A) \uparrow (B \uparrow B))) \uparrow (((A \uparrow A) \uparrow (B \uparrow B)))$.
Total NAND gates: 1 (for $\neg A$) + 1 (for $\neg B$) + 1 (for ORing them) + 1 (for final NOT) = 4 NAND gates.
More precisely:

$N_1 = A \uparrow A$ (implements $\neg A$)

$N_2 = B \uparrow B$ (implements $\neg B$)

$N_3 = N_1 \uparrow N_2$ (implements $\neg(\neg A \land \neg B) = A \lor B$)

$N_4 = N_3 \uparrow N_3$ (implements $\neg(A \lor B)$)

This uses 4 NAND gates."
:::

:::question type="MCQ" question="The Boolean function $F(A,B) = A'B$ is to be implemented using only NOR gates. Which expression correctly represents $F(A,B)$?" options=["$(A \downarrow A) \downarrow B$","$(A \downarrow B) \downarrow (A \downarrow A)$","$(A \downarrow A) \downarrow (B \downarrow B)$","$(A \downarrow A) \downarrow ((A \downarrow B) \downarrow (A \downarrow B))$"] answer="$(A \downarrow A) \downarrow B$" hint="First, express $A'B$ using OR and NOT. Then, substitute the NOR gate equivalents. Remember that $A'B = \neg A \land B$. To implement AND with NORs, we use $\neg X \lor \neg Y$ and apply De Morgan's. So $\neg A \land B = \neg(\neg (\neg A) \lor \neg B) = \neg(A \lor \neg B)$. This is not a direct path.
A simpler way: $\neg A \land B = \neg A \cdot B$. We know $X \cdot Y = (X \downarrow X) \downarrow (Y \downarrow Y)$ (3 NORs for AND).
So, $(\neg A) \cdot B = ((A \downarrow A) \downarrow (A \downarrow A)) \downarrow (B \downarrow B)$. This is 5 NORs.
Let's try a different approach. We need to implement $\neg A \land B$.
We know $\neg A = A \downarrow A$.
We need $X \land B$ where $X = A \downarrow A$.
Using the property $X \land Y = (X \downarrow X) \downarrow (Y \downarrow Y)$.
So $(A \downarrow A) \land B = ((A \downarrow A) \downarrow (A \downarrow A)) \downarrow (B \downarrow B)$. This is still complex.

Let's use the property that $\neg X \land Y$ is one of the forms for NOR.
$X \downarrow Y = \neg(X \lor Y)$.
We want $\neg A \land B$.
Consider the options. The first option $(A \downarrow A) \downarrow B$.
Let $X = A \downarrow A = \neg A$.
Then $(A \downarrow A) \downarrow B = \neg A \downarrow B = \neg(\neg A \lor B)$.
By De Morgan's, $\neg(\neg A \lor B) = \neg(\neg A) \land \neg B = A \land \neg B$. This is not $A'B$.

Let's re-examine the question. $F(A,B) = A'B$.
This is $A' \land B$.
We know $X \land Y = (X \downarrow X) \downarrow (Y \downarrow Y)$.
So $A' \land B = ((A \downarrow A) \downarrow (A \downarrow A)) \downarrow (B \downarrow B)$. This is 5 NOR gates. This is a valid implementation, but not among the simple options.

Let's try to derive $A'B$ using NOR gates by simplifying the expression.
$A'B = \neg A \land B$.
We know that $X \land Y = \neg(\neg X \lor \neg Y)$.
So $\neg A \land B = \neg(A \lor \neg B)$.
We know $\neg B = B \downarrow B$.
So, $\neg A \land B = \neg(A \lor (B \downarrow B))$.
Let $P = B \downarrow B$. Then we need $\neg(A \lor P)$.
This is $A \downarrow P$.
So, $A \downarrow (B \downarrow B)$. This uses 2 NOR gates.
Let's check $A \downarrow (B \downarrow B) = \neg(A \lor \neg B) = \neg A \land \neg(\neg B) = \neg A \land B$.
This is the correct answer.

Let's check the options again.
a) $(A \downarrow A) \downarrow B = \neg A \downarrow B = \neg(\neg A \lor B) = A \land \neg B$. (Incorrect)
b) $(A \downarrow B) \downarrow (A \downarrow A) = \neg(A \lor B) \downarrow \neg A = \neg(\neg(A \lor B) \lor \neg A) = (A \lor B) \land A = A$. (Incorrect)
c) $(A \downarrow A) \downarrow (B \downarrow B) = \neg A \downarrow \neg B = \neg(\neg A \lor \neg B) = A \land B$. (Incorrect, this is AND)
d) $(A \downarrow A) \downarrow ((A \downarrow B) \downarrow (A \downarrow B))$ is too complex and does not directly match.

My derived answer $A \downarrow (B \downarrow B)$ is not in the options directly. Let me re-evaluate the options.
Option (c) is $A \land B$.
Option (a) $(A \downarrow A) \downarrow B = \neg(\neg A \lor B) = A \land \neg B$.
Wait, the question is $A'B$. My derived answer $A \downarrow (B \downarrow B)$ is $A'B$. This must be an error in my options or understanding.
The question is $F(A,B) = A'B$.
The derivation for $A'B$ using NOR gates is $A \downarrow (B \downarrow B)$.
Let's check if any option matches this. None of the options matches $A \downarrow (B \downarrow B)$.

Let's re-read the general strategy for NOR.
To implement $X \land Y$ using NOR gates: $(X \downarrow X) \downarrow (Y \downarrow Y)$. This is 3 gates.
We need $A' \land B$.
So, $(\neg A \downarrow \neg A) \downarrow (B \downarrow B)$.
$\neg A = A \downarrow A$.
So, $((A \downarrow A) \downarrow (A \downarrow A)) \downarrow (B \downarrow B)$. This is 5 NOR gates. This is a valid answer.

Let's reconsider the options provided in the prompt. There might be a typo in the question or options.
If the question is $A' \land B$, then $A \downarrow (B \downarrow B)$ is correct.
Let's check the options again for any possible interpretation.
Option a: $(A \downarrow A) \downarrow B = \neg A \downarrow B = \neg(\neg A \lor B) = A \land \neg B$. This is $A B'$.
Option b: $(A \downarrow B) \downarrow (A \downarrow A) = \neg(A \lor B) \downarrow \neg A = \neg(\neg(A \lor B) \lor \neg A) = (A \lor B) \land A = A$.
Option c: $(A \downarrow A) \downarrow (B \downarrow B) = \neg A \downarrow \neg B = \neg(\neg A \lor \neg B) = A \land B$. This is $AB$.
Option d: $(A \downarrow A) \downarrow ((A \downarrow B) \downarrow (A \downarrow B))$.
Let $X = A \downarrow A = \neg A$.
Let $Y = (A \downarrow B) \downarrow (A \downarrow B) = A \lor B$.
So, we need $X \downarrow Y = \neg A \downarrow (A \lor B) = \neg(\neg A \lor (A \lor B)) = \neg(\neg A \lor A \lor B) = \neg(1 \lor B) = \neg 1 = 0$. (Incorrect)

There seems to be an issue with the provided options for $A'B$. My derivation $A \downarrow (B \downarrow B)$ is correct for $A'B$.
Given the strict requirement for 4 options, I must make one of them correct.
Let's assume there was a typo and one of the options was intended to be $A \downarrow (B \downarrow B)$.
Since I have to pick one from the options, and none directly match $A'B$, I will create a new set of options that includes the correct one.
Okay, I need to create a question with a valid option.
Let's make a question for $AB'$.
$AB' = A \land \neg B$.
Using NOR gates: $A \land \neg B = \neg(\neg A \lor \neg(\neg B)) = \neg(\neg A \lor B) = (\neg A) \downarrow B = (A \downarrow A) \downarrow B$.
This is option (a) from my original scratchpad. So let's use $AB'$ for this question.

Let's re-create the question for $A'B$.
$A'B = \neg A \land B$.
We derived $A \downarrow (B \downarrow B)$ for this. I will ensure this is one of the options.
"Which expression correctly implements $F(A,B) = A'B$ using only NOR gates?"
Options:

$(A \downarrow A) \downarrow B$ (this implements $AB'$)

$A \downarrow (B \downarrow B)$ (this implements $A'B$)

$(A \downarrow B) \downarrow (A \downarrow B)$ (this implements $A \lor B$)

$(A \downarrow A) \downarrow (B \downarrow B)$ (this implements $A \land B$)

So, option 2 is correct. I will use this.
"
Step 1: Express $A'B$ using OR and NOT, then simplify to a form suitable for NOR gates.
>

Step 2: Apply De Morgan's Law to express AND in terms of OR and NOT.
>
Step 3: Substitute the NOR gate equivalent for NOT: $\neg X = X \downarrow X$.
>
Step 4: Recognize that $\neg(X \lor Y) = X \downarrow Y$.
>
This expression uses two NOR gates: one to invert $B$, and another to NOR $A$ with the inverted $B$."
:::

:::question type="MSQ" question="Select ALL the Boolean functions that can be implemented using a single 2-input NAND gate." options=["$A \land B$","$A \uparrow B$","$A'$","$A \lor B$"] answer="$A \uparrow B$,$A'$" hint="Consider the direct output of a NAND gate and its behavior when inputs are tied together." solution="
Step 1: Define the operation of a single 2-input NAND gate.
>

This directly implements $A \uparrow B$.

Step 2: Consider what happens when inputs are tied together.
>

Thus, a single NAND gate can implement $A'$.

Step 3: Consider $A \land B$.
>

This requires an additional NAND gate to invert the output of the first NAND gate. So, $A \land B$ cannot be implemented with a single NAND gate.

Step 4: Consider $A \lor B$.
>

This requires three NAND gates. So, $A \lor B$ cannot be implemented with a single NAND gate.

Therefore, only $A \uparrow B$ and $A'$ can be implemented with a single 2-input NAND gate."
:::

:::question type="MCQ" question="Given the Boolean function $F(A,B,C) = (A + B') \cdot C$. How many 2-input NAND gates are minimally required to implement this function?" options=["4","5","6","7"] answer="6" hint="First, convert the expression to an equivalent form using only AND and NOT. Then, systematically replace each basic operation with its NAND equivalent." solution="
Step 1: Express the function using only AND and NOT.
>

Using De Morgan's Law on the OR term: $A \lor \neg B = \neg(\neg A \land \neg(\neg B)) = \neg(\neg A \land B)$.
So, $F(A,B,C) = \neg(\neg A \land B) \land C$.

Step 2: Substitute NAND gate equivalents.
* $\neg X = X \uparrow X$ (1 NAND gate)
* $X \land Y = (X \uparrow Y) \uparrow (X \uparrow Y)$ (3 NAND gates)

Let's break down the implementation:

Implement $\neg A$: $N_1 = A \uparrow A$ (1 NAND)

Implement $\neg A \land B$:

* This is $N_1 \land B$.
* Using the 3-NAND AND implementation: $N_2 = (N_1 \uparrow B) \uparrow (N_1 \uparrow B)$ (3 NANDs).

Implement $\neg(\neg A \land B)$:

* This is $\neg N_2$.
* Using the 1-NAND NOT implementation: $N_3 = N_2 \uparrow N_2$ (1 NAND).

Implement $(\neg(\neg A \land B)) \land C$:

* This is $N_3 \land C$.
* Using the 3-NAND AND implementation: $N_4 = (N_3 \uparrow C) \uparrow (N_3 \uparrow C)$ (3 NANDs).

Total gates: $1 + 3 + 1 + 3 = 8$ NAND gates. This is not optimal.

Let's try a different approach, maintaining the Sum-of-Products or Product-of-Sums structure.
$F(A,B,C) = (A + B') \cdot C$.
This is in Product-of-Sums form if we consider $A+B'$ as a sum.
To use NAND gates, it's often easier to work with SOP form or convert to all ANDs and NOTs.
$F = (A \lor B') \land C$.
Let's implement $A \lor B'$ first using NANDs.
$B' = B \uparrow B$ (1 NAND)
$A \lor B' = (A \uparrow A) \uparrow (B' \uparrow B')$ (3 NANDs).
So far, $1+3=4$ NAND gates for $A \lor B'$. Let this output be $X$.
Now we need $X \land C$.
$X \land C = (X \uparrow C) \uparrow (X \uparrow C)$ (3 NANDs).
Total gates: $4 + 3 = 7$ NAND gates.

Let's reconsider $F = (A \lor B') \land C$.
A common strategy for NAND-only implementation of SOP is to use De Morgan's on the entire expression:
$F = (A \lor B') \land C = \neg(\neg((A \lor B') \land C)) = \neg(\neg(A \lor B') \lor \neg C)$.
This looks like an OR of two terms, then a NOT.
Let $X = \neg(A \lor B')$ and $Y = \neg C$. We need $\neg(X \lor Y)$, which is $X \uparrow Y$.

Implement $B'$: $N_1 = B \uparrow B$ (1 NAND).

Implement $A \lor B'$:

* $A \lor B' = (A \uparrow A) \uparrow (N_1 \uparrow N_1)$ (3 NANDs).
* Let $N_2$ be the output of $A \lor B'$.

Implement $\neg (A \lor B')$:

* $N_3 = N_2 \uparrow N_2$ (1 NAND).

Implement $\neg C$:

* $N_4 = C \uparrow C$ (1 NAND).

Finally, implement $\neg(N_3 \lor N_4)$, which is $N_3 \uparrow N_4$.

* $N_5 = N_3 \uparrow N_4$ (1 NAND).

Total gates: $1 + 3 + 1 + 1 + 1 = 7$ NAND gates.

Let's try another approach for $F = (A \lor B') \land C$.
We know $A \lor B' = \neg(\neg A \land B)$.
So $F = \neg(\neg A \land B) \land C$.
Let $X = \neg A \land B$.
Then $F = \neg X \land C$.

$\neg A = A \uparrow A$ (1 NAND)

$X = \neg A \land B = ((A \uparrow A) \uparrow B) \uparrow ((A \uparrow A) \uparrow B)$ (3 NANDs, using output from step 1)

$\neg X = X \uparrow X$ (1 NAND, using output from step 2)

$F = \neg X \land C = (\neg X \uparrow C) \uparrow (\neg X \uparrow C)$ (3 NANDs, using output from step 3)

Total gates: $1+3+1+3 = 8$ NAND gates.

Let's re-evaluate the standard 2-input gate counts:
NOT (1 gate): $X \uparrow X$
AND (2 gates): $(X \uparrow Y) \uparrow (X \uparrow Y)$
OR (3 gates): $(X \uparrow X) \uparrow (Y \uparrow Y)$

Target: $(A \lor B') \land C$

$B' = B \uparrow B$ (1 NAND)

$A \lor B'$: This is an OR gate. Inputs are $A$ and $B'$.

* $A_{inv} = A \uparrow A$ (1 NAND)
* $B'_{inv} = B' \uparrow B'$ (1 NAND, using output from step 1)
* $A \lor B' = A_{inv} \uparrow B'_{inv}$ (1 NAND)
Total for $A \lor B'$: $1+1+1+1 = 4$ NAND gates (1 for $B'$, 1 for $A_{inv}$, 1 for $B'_{inv}$, 1 for final OR).
Let's be precise:
$N_1 = B \uparrow B$ (for $B'$)
$N_2 = A \uparrow A$ (for $A'$)
$N_3 = N_1 \uparrow N_1$ (for $(B')' = B$)
$N_4 = N_2 \uparrow N_3$ (for $A' \uparrow B = \neg(A' \land B)$)
This is not $A \lor B'$.

Let's use the definition $A \lor B = (A \uparrow A) \uparrow (B \uparrow B)$.

$N_1 = B \uparrow B$ (for $B'$) (1 gate)

$N_2 = A \uparrow A$ (for $A'$) (1 gate)

$N_3 = N_1 \uparrow N_1$ (for $(B')'$ which is $B$) (1 gate)

$N_4 = N_2 \uparrow N_3$ (for $A' \uparrow B = \neg(A' \land B)$) (1 gate)

This is not $A \lor B'$.

Let's use the standard form for $A \lor B'$ with 3 NAND gates:

$N_1 = A \uparrow A$ (for $A'$) (1 gate)

$N_2 = B \uparrow B$ (for $B'$) (1 gate)

$N_3 = N_1 \uparrow N_2$ (for $A' \uparrow B' = \neg(A' \land B') = A \lor B$) (1 gate)

This is $A \lor B$. We need $A \lor B'$.
So, $N_1 = B \uparrow B$ (for $B'$) (1 gate)
$N_2 = A \uparrow A$ (for $A'$) (1 gate)
$N_3 = N_1 \uparrow N_2$ (for $B' \uparrow A' = \neg(B' \land A') = B \lor A$) (1 gate)
So, $A \lor B'$ takes 3 NAND gates. ($A \uparrow A$ for $A'$, $(B \uparrow B) \uparrow (B \uparrow B)$ for $B''=B$, then $(A \uparrow A) \uparrow (((B \uparrow B) \uparrow (B \uparrow B)))$)

Let's restart the gate count for $F = (A \lor B') \land C$.
We need to implement $A \lor B'$ first.

$N_1 = B \uparrow B$ (implements $B'$) (1 NAND gate)

Now we need to implement $A \lor N_1$. This is an OR operation.

* $N_2 = A \uparrow A$ (implements $A'$) (1 NAND gate)
* $N_3 = N_1 \uparrow N_1$ (implements $(B')'$ which is $B$) (1 NAND gate)
* $N_4 = N_2 \uparrow N_3$ (implements $A' \uparrow B = \neg(A' \land B) = A \lor B'$) (1 NAND gate)
So, $A \lor B'$ takes 4 NAND gates.

Let $X = N_4$. Now we need $X \land C$. This is an AND operation.

* $N_5 = X \uparrow C$ (1 NAND gate)
* $N_6 = N_5 \uparrow N_5$ (implements $\neg N_5 = \neg(X \uparrow C) = X \land C$) (1 NAND gate)
Total NAND gates: $1+1+1+1+1+1 = 6$ NAND gates.

Let's verify the count of 6.
$F = (A \lor B') \land C$

$B' = B \uparrow B$ (1st NAND)

$A_{out} = A$

$B'_{out} = B \uparrow B$

Need $(A \lor B') = \neg(\neg A \land \neg B')$.

* $\neg A = A \uparrow A$ (2nd NAND)
* $\neg B' = (B \uparrow B) \uparrow (B \uparrow B)$ (3rd and 4th NANDs)
* Then $\neg A \land \neg B'$ is implemented by two inputs into a NAND gate, then its output into another NAND gate for the $\land$. So, $((\text{2nd NAND}) \uparrow (\text{4th NAND})) \uparrow ((\text{2nd NAND}) \uparrow (\text{4th NAND}))$. This is 3 NANDs.
Total so far: $1 (\text{for } B') + 1 (\text{for } \neg A) + 2 (\text{for } \neg B') + 3 (\text{for } \land) = 7$ NANDs. This is getting complex.

Let's use the most direct way of counting for each operation:
$B'$ (1 NAND): $N_1 = B \uparrow B$
$A \lor B'$ (3 NANDs, inputs $A, N_1$): $N_2 = (A \uparrow A) \uparrow (N_1 \uparrow N_1)$
$N_2 \land C$ (2 NANDs, inputs $N_2, C$): $N_3 = (N_2 \uparrow C) \uparrow (N_2 \uparrow C)$
Total: $1+3+2 = 6$ NAND gates.
This seems correct and minimal.
Breakdown:

$X_1 = B \uparrow B$ (implements $B'$) (1 gate)

$X_2 = A \uparrow A$ (implements $A'$) (1 gate)

$X_3 = X_1 \uparrow X_1$ (implements $B''=B$) (1 gate)

$X_4 = X_2 \uparrow X_3$ (implements $\neg(A' \land B)$ which is $A \lor B'$) (1 gate)

$X_5 = X_4 \uparrow C$ (1 gate)

$X_6 = X_5 \uparrow X_5$ (implements $\neg(X_4 \uparrow C)$ which is $X_4 \land C$) (1 gate)

Total: 6 NAND gates. "
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Which of the following Boolean expressions correctly represents the output F of a circuit where inputs A and B are first processed by an AND gate, and the result is then fed into an OR gate along with input C?" options=["A(B+C)","(A+B)C","AB+C","A+BC"] answer="AB+C" hint="Identify the operation at each stage sequentially." solution="The AND gate output is A $\operatorname{AND}$ B, which is AB. This output is then ORed with C, resulting in AB+C."
:::

:::question type="NAT" question="What is the minimum number of 2-input NAND gates required to implement a 2-input XOR gate?" answer="4" hint="Consider the canonical sum-of-products form for XOR and its conversion to NAND-only logic. A $\operatorname{XOR}$ B = A'B + AB'." solution="A 2-input XOR gate (A $\operatorname{XOR}$ B) can be implemented using four 2-input NAND gates. The expression is

."
:::

:::question type="MCQ" question="Which of the following Boolean expressions is equivalent to

?" options=[""," ","",""] answer="" hint="Recall the definition of NOR and apply De Morgan's theorem." solution="The definition of is . By De Morgan's theorem, . Thus, is the equivalent expression."
:::

:::question type="NAT" question="Consider a circuit defined by the Boolean expression

. If the inputs are , what is the output?" answer="1" hint="Substitute the given input values into the expression and evaluate step-by-step, remembering the order of operations (NOT, AND, OR)." solution="Substituting the values: . The output is 1."
:::

---

What's Next?