GATE Overflow Test Series | Digital Logic | Test 1 | Question: 2

Question

Which of the following functions is not associative?

• A. AND
• B. OR
• C. EXOR
• D. NAND

Answer 1

1.  AND is associative and commutative.

• $A\cdot B = B\cdot A\;\text{(commutative)}$
• $(A\cdot B) \cdot C = A\cdot (B \cdot C)\;\text{(Associative)}$

 

2. OR is associative and commutative.

• $A + B = B + A\;\text{(commutative)}$
• $(A + B) + C = A + (B + C)\;\text{(Associative)}$

3.  EXOR is associative and commutative.

 

1. $A \oplus B = B  \oplus A\;\text{(commutative)}$

• Proof $:A \oplus B = A\overline{B} + \overline{A}B $
• $B \oplus A = B\overline{A} + \overline{B}A =  A\overline{B} + \overline{A}B = A \oplus B$

2. $(A \oplus B) \oplus C = A \oplus(B \oplus C)\;\text{(Associative)}$

• Proof $:(A \oplus B) \oplus C = (A\overline{B} + \overline{A}B ) \oplus C = (A\overline{B} + \overline{A}B)\; \overline{C} + \overline{(A\overline{B} + \overline{A}B)}\;\;C = A\overline{B}\; \overline{C} + \overline{A}\;B\; \overline{C} + (A B+ \overline{A}\;\;\overline{B})C \quad \left[\because\overline{(X \oplus Y)} =  X \odot Y = XY  + \overline{X}\;\overline{Y}\right]$
• $=A\overline{B}\; \overline{C} + \overline{A}\;B\; \overline{C} + A B C+ \overline{A}\;\;\overline{B}\;C$ 
• And, $A \oplus(B \oplus C) = A \oplus (B\overline{C} + \overline{B}C ) = A\;\;\overline{(B\overline{C} + \overline{B}C)} + \overline{A}\;\;(B\overline{C} + \overline{B}C) = A(BC + \overline{B}\;\;\overline{C}) +  \overline{A}\;B\;\overline{C} +\overline{A}\; \overline{B}\;C)  \quad \left[\because\overline{(X \oplus Y)} =  X \odot Y = XY  + \overline{X}\;\overline{Y}\right]$
• $=A B C +  A\overline{B}\; \overline{C} + \overline{A}\;B\; \overline{C} + + \overline{A}\;\;\overline{B}\;C$ 
• Hence, $(A \oplus B) \oplus C = A \oplus(B \oplus C)\;\text{Proved.}$

4.  NAND is commutative but not associative.

 

1. $A\uparrow B =B\uparrow A = \overline{A\cdot B} = \overline{B\cdot A}\;\text{(commutative)}$
2. $(A \uparrow B) \uparrow C \neq A \uparrow (B \uparrow C)\;\text{(not associative)}$

• Proof $:(A \uparrow B) \uparrow C = \overline{(A\cdot B)} \uparrow C = \overline{\overline{A\cdot B}\cdot C} = \overline{\overline{A\cdot B}} + \overline{C} = AB + \overline{C}$
• $A \uparrow (B \uparrow C) = A \uparrow \overline{(B\cdot C)} = \overline{A \cdot \overline{B\cdot C}} = \overline{A} \cdot \overline{\overline{B\cdot C}} = \overline{A} + BC$
• Clearly,  both are not equal.

$\textbf{Note:}$ Similarly EXNOR is commutative and associative, and NOR is commutative but not associative.

Answer 2

NAND function is not associative.

Answer 3

Every gate is associative except 

NAND , NOR