3
$\begingroup$

How many symmetric boolean functions exist that are linear?
Let $f$ be a $n$-variable boolean function. $f$ is said to be symmetric if it is unchanged by any permutation of its variables, i.e. for 2-variable boolean functions $f$ is symmetric if $f(a,b) = f(b,a)$. In addition $f$ is called a linear function if it does not include second- or higher degree product terms in the ring sum normal form (RSNF). For example, a 2-variable function $g(x_1, x_2)$ is linear if the RSNF is of the form $$f(x_1, x_2) = c_0 \oplus c_1 x_1 \oplus c_2 x_2$$
I found the number of symmetric functions as $2^{n+1}$ and the number of linear functions as $2^n$ but I'm not sure if the number of linear functions is correct.
How do I get the number of symmetric functions that are also linear?

$\endgroup$
2
  • 1
    $\begingroup$ @D.W. I am currently preparing for entrance examinations and encountered this question in a past exam. $\endgroup$
    – M3n4p
    Commented Jan 8 at 6:35
  • 1
    $\begingroup$ Thank you for the improved post! $\endgroup$
    – D.W.
    Commented Jan 8 at 6:46

1 Answer 1

1
$\begingroup$

There are only 4 symmetric linear functions. You can easily show that you must have $c_1=c_2$ (otherwise $f(1,0,0,\dots,0)$ will be different from $f(0,1,0,\dots,0)$), and similarly, you must have $c_1=c_2=\cdots=c_n$. $c_0$ can be anything. Therefore, once you choose $c_0$ and $c_1$, the function is wholly determined.

There are $2^{n+1}$ linear functions, when your definition of linear functions allows a constant term $c_0$.

$\endgroup$
6
  • 1
    $\begingroup$ What is the number of symmetric functions? I argued that because $f$ is symmetric it is only dependent on the number of its input variables. Because they can only take $n+1$ different values the number of symmetric boolean functions is therefore $2^{n+1}$. $\endgroup$
    – M3n4p
    Commented Jan 8 at 7:05
  • $\begingroup$ @M3n4p, that is best asked separately, using the 'Ask Question' button. I suggest counting the number of such functions with $n=4$ by hand, and comparing to your formula, to gain some partial insight. Hint: if you have such an $f$, and I tell you that I have an input in mind with two 1's and two 0's, but I don't tell you the particular input I have in mind, is the output fully determined? $\endgroup$
    – D.W.
    Commented Jan 8 at 7:16
  • 1
    $\begingroup$ I counted all the $n = 4$ functions and it fulfills $2^{n+1}$. I don't know how you would get more? $\endgroup$
    – M3n4p
    Commented Jan 8 at 14:17
  • $\begingroup$ @M3n4p, the comments here aren't intended for interactive discussion or for follow-up questions. I would suggesting using the 'Ask Question' button to ask how many symmetric functions there are. When you do that, show your work for how you got $2^{n+1}$ as the general formula, and how you got that number for $n=4$. $\endgroup$
    – D.W.
    Commented Jan 8 at 17:19
  • $\begingroup$ There are $2^{n+1}$ symmetric $n$-ary Boolean functions, this is stated in the Wikipedia entry "symmetric boolean function". $\endgroup$ Commented May 24 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.