GATE CS 2015 Set 3 Q.12 (CS Q.2): Boolean Algebra and Logic Minimization

Let $\#$ be a binary operator defined as

X \# Y = X' + Y'

where $X$ and $Y$ are Boolean variables.

Consider the following two statements.
(S1) $(P \# Q) \# R = P \# (Q \# R)$
(S2) $Q \# R = R \# Q$

Which of the following is/are true for the Boolean variables $P$ , $Q$ and $R$ ?

Only S1 is true

Only S2 is true

Both S1 and S2 are true

Neither S1 nor S2 are true

Official answer and solution

Official answer: B
From: Official GATE 2015 answer key

Solution

Express the binary operator # in terms of standard Boolean logic operations and check commutativity and associativity.

The binary operator is defined as $X \# Y = X' + Y'$ .
By De Morgan's laws, $X' + Y' = (XY)'$ , which is the Boolean NAND operation.

Evaluate Statement (S2): $Q \# R = R \# Q$
$Q \# R = (QR)' = (RQ)' = R \# Q$ .
Since Boolean conjunction is commutative, the NAND operator is commutative. Thus, statement (S2) is true.

Evaluate Statement (S1): $(P \# Q) \# R = P \# (Q \# R)$
Test with truth values $P = 0, Q = 0, R = 1$ :

Left-hand side: $(0 \# 0) \# 1 = (0' + 0') \# 1 = 1 \# 1 = 1' + 1' = 0$ .
Right-hand side: $0 \# (0 \# 1) = 0 \# (0' + 1') = 0 \# 1 = 0' + 1' = 1$ .
Since $0 \ne 1$ , $(P \# Q) \# R \ne P \# (Q \# R)$ . Thus, statement (S1) is false.

Hence, only statement S2 is true (Option B).

Final answer

Common trap

Assuming that symmetrical operator definitions guarantee associativity, whereas NAND is strictly non-associative.

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

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 12 of 65, printed as CS Q.2
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