GATE CS 2014 Set 3 Q.65 (CS Q.55): Boolean Algebra and Logic Minimization

Let $\oplus$ denote the Exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean expression for $F$ over two variables $P$ and $Q$ :

F(P, Q) = ((1 \oplus P) \oplus (P \oplus Q)) \oplus ((P \oplus Q) \oplus (Q \oplus 0))

The equivalent expression for $F$ is

$P + Q$

$\overline{P + Q}$

$P \oplus Q$

$\overline{P \oplus Q}$

Official answer and solution

Official answer: D
From: Official GATE 2014 answer key

Solution

Apply the associative, commutative, and self-inverse algebraic properties of the XOR operation to simplify the Boolean expression.

Given expression:

F(P, Q) = ((1 \oplus P) \oplus (P \oplus Q)) \oplus ((P \oplus Q) \oplus (Q \oplus 0))

Properties of XOR ( $\oplus$ ):
- Commutative: $A \oplus B = B \oplus A$
- Associative: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
- Identity element: $A \oplus 0 = A$
- Inversion: $A \oplus 1 = \overline{A}$
- Self-inverse: $A \oplus A = 0$
Expand the Expression:
Because $\oplus$ is associative and commutative, parentheses can be removed entirely:
$F(P, Q) = 1 \oplus P \oplus P \oplus Q \oplus P \oplus Q \oplus Q \oplus 0.$
Count and Cancel Duplicate Terms:
- Constant $0$ : vanishes ( $X \oplus 0 = X$ ).
- Variable $P$ : occurs 3 times: $P \oplus P \oplus P = (P \oplus P) \oplus P = 0 \oplus P = P.$
- Variable $Q$ : occurs 3 times: $Q \oplus Q \oplus Q = (Q \oplus Q) \oplus Q = 0 \oplus Q = Q.$
- Constant $1$ : occurs 1 time.
Combine Simplified Terms:
$F(P, Q) = 1 \oplus P \oplus Q = 1 \oplus (P \oplus Q) = \overline{P \oplus Q}.$

This is the XNOR operation, corresponding to option D.

Final answer

Common trap

Simplifying 1 + P + Q as normal arithmetic or OR operation instead of modulo-2 XOR addition.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 3
Question: 65 of 65, printed as CS Q.55
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source