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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ @D.W. I am currently preparing for entrance examinations and encountered this question in a past exam. $\endgroup$M3n4p– M3n4p2024-01-08 06:35:09 +00:00Commented Jan 8, 2024 at 6:35
-
1$\begingroup$ Thank you for the improved post! $\endgroup$D.W.– D.W. ♦2024-01-08 06:46:43 +00:00Commented Jan 8, 2024 at 6:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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$.
-
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– M3n4p2024-01-08 07:05:49 +00:00Commented Jan 8, 2024 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$2024-01-08 07:16:55 +00:00Commented Jan 8, 2024 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– M3n4p2024-01-08 14:17:18 +00:00Commented Jan 8, 2024 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$2024-01-08 17:19:28 +00:00Commented Jan 8, 2024 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$Yan King Yin– Yan King Yin2024-05-24 12:49:17 +00:00Commented May 24, 2024 at 12:49