GATE CS 2014 Set 3 Q55 — Boolean Algebra

We can simplify the given Boolean expression by using the fundamental properties of the exclusive OR (XOR) operation:

• Associativity & Commutativity: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ and $A \oplus B = B \oplus A$
• Self-inverse: $A \oplus A = 0$
• Identity: $A \oplus 0 = A$
• Complement: $A \oplus 1 = \overline{A}$

The given expression is:

$$F(P,Q) = \underbrace{\left( (1 \oplus P) \oplus (P \oplus Q) \right)}_{\text{Part 1}} \oplus \underbrace{\left( (P \oplus Q) \oplus (Q \oplus 0) \right)}_{\text{Part 2}}$$

Step 1: Simplify Part 1

$$\text{Part 1} = (1 \oplus P) \oplus (P \oplus Q)$$

Using associativity and commutativity, we can group the $P$ terms together:

$$\text{Part 1} = 1 \oplus (P \oplus P) \oplus Q$$

Since $P \oplus P = 0$:

$$\text{Part 1} = 1 \oplus 0 \oplus Q = 1 \oplus Q = \overline{Q}$$

Step 2: Simplify Part 2

$$\text{Part 2} = (P \oplus Q) \oplus (Q \oplus 0)$$

Since $Q \oplus 0 = Q$:

$$\text{Part 2} = (P \oplus Q) \oplus Q$$

Grouping the $Q$ terms together:

$$\text{Part 2} = P \oplus (Q \oplus Q)$$

Since $Q \oplus Q = 0$:

$$\text{Part 2} = P \oplus 0 = P$$

Step 3: Combine Part 1 and Part 2

Now, substitute the simplified parts back into the expression for $F(P,Q)$:

$$F(P,Q) = \text{Part 1} \oplus \text{Part 2} = \overline{Q} \oplus P$$

Using the property that complementing one input of an XOR gate complements the entire output:

$$\overline{Q} \oplus P = \overline{P \oplus Q}$$

Thus, the equivalent expression is $\overline{P \oplus Q}$, which corresponds to option D.