GATE CS 2007 Q33 — Boolean Algebra

The given connective $*$ is defined as:

This is the standard XNOR (equivalence) operator, denoted as $\odot$. Let us analyze the properties of the $\odot$ operator:

• Commutativity: $A \odot B = B \odot A$
• Associativity: $(A \odot B) \odot C = A \odot (B \odot C)$
• Identity: $1 \odot A = A$
• Self-equivalence: $A \odot A = 1$

We are given $Z = X * Y = X \odot Y$. Let us evaluate each expression:

1. Evaluating $P : X = Y * Z$

$$\begin{aligned} Y * Z &= Y \odot (X \odot Y) \\ &= (Y \odot Y) \odot X & \quad \text{(by associativity and commutativity)} \\ &= 1 \odot X & \quad \text{(since } Y \odot Y = 1\text{)} \\ &= X \end{aligned}$$ Thus, $P$ is valid.

2. Evaluating $Q : Y = X * Z$

$$\begin{aligned} X * Z &= X \odot (X \odot Y) \\ &= (X \odot X) \odot Y \\ &= 1 \odot Y \\ &= Y \end{aligned}$$ Thus, $Q$ is valid.

3. Evaluating $R : X * Y * Z = 1$

$$\begin{aligned} X * Y * Z &= (X \odot Y) \odot Z \\ &= Z \odot Z & \quad \text{(since } X \odot Y = Z\text{)} \\ &= 1 \end{aligned}$$ Thus, $R$ is valid.

Since $P$, $Q$, and $R$ are all valid, the correct option is D.