CMI2011-A-05

Question

A $\text{3-ary}$  boolean function is a function that takes three boolean arguments and produces a boolean output. Let $f$ and $g$ be  $\text{3-ary}$ boolean functions. We say that $f$ and $g$ are neighbours if $f$ and $g$ agree on at least one input and disagree on at least one input: that is, there exist $x,\: y,\: z$ such that $f(x, y, z) = g(x, y, z)$ and $x',y',z'$ such that $f(x',y',z') \neq g(x',y',z')$.
Suppose we fix a $\text{3-ary}$ boolean function $h$. How many neighbours does $h$ have?

• A. $128$
• B. $132$
• C. $254$
• D. $256$

Answer 1

For $\text{3-ary}$ boolean functions there can be $8$ possible inputs.

We fixed a $\text{3-ary}$ boolean function $h$.

Total number of possible functions $=2^8=256.$

Functions not allowed to be neighbors of $h$ are the ones agreeing on all inputs (exactly one possible) and one which is disagreeing on all inputs (again exactly one where the Boolean output is the complement of $h)$.

Hence, $h$ has $256-2=254$ neighbors$.$

Comments

@ MK Utkarsh ,

a function can not be neighbour of it self so we can exclude one from that “one agreeing on all input ” indirectly wants to say that .

am i correct ?

Answer 2

$C)$ $\text{Agree on 1 , disagree on 7 $+$ Agree on 2, disagree on 6 $+\ldots+$ Agree on 7, disagree on 1}$

$=\binom{8}{1}+\binom{8}{2}+\ldots+\binom{8}{7}$

$=254$