edited by
1,031 views
2 votes
2 votes

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?

  1. $128$
  2. $132$
  3. $254$
  4. $256$
edited by

2 Answers

Best answer
6 votes
6 votes
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$.$
selected by

Related questions

1 votes
1 votes
1 answer
4