# All different functions

For functions $$\f, g: \{0,1\}^n \rightarrow \{0,1\} \$$, we say $$\f \sim g\$$ if there's a permutation of $$\1,2,3,...,n\$$ called $$\i_1,i_2,i_3,...,i_n\$$ so that $$\f(x_1,x_2,x_3,...,x_n) = g(x_{i_1},x_{i_2},x_{i_3},...,x_{i_n})\$$. Therefore, all such functions are divided in several sets such that, for any two functions $$\f, g\$$ in a same set, $$\f \sim g\$$; for any two functions $$\f, g\$$ in different sets, $$\f \not\sim g\$$. (Equivalence relation) Given $$\n\$$, output these sets or one of each set.

Samples:

0 -> {0}, {1}
1 -> {0}, {1}, {a}, {!a}
2 -> {0}, {1}, {a, b}, {!a, !b}, {a & b}, {a | b}, {a & !b, b & !a}, {a | !b, b | !a}, {a ^ b}, {a ^ !b}, {!a & !b}, {!a | !b}


You can output the function as a possible expression(like what's done in the example, but should theoretically support $$\n>26\$$), a table marking outputs for all possible inputs (truth table), or a set containing inputs that make output $$\1\$$.

Shortest code win.

• @JoKing Anything, so there are $2^{2^n}$ functions for given $n$.
– l4m2
Nov 6, 2018 at 4:42
• @JoKing Also, all boolean functions can be represented in term of AND and OR. Nov 6, 2018 at 14:33
• @user202729 AND, OR, and NOT at the very least (not that this is a problem since you have used all three). Just AND and OR won't work. Nov 6, 2018 at 14:48
• Nov 6, 2018 at 14:52

# J, 62 bytes

f=:3 :'~.(2#~2^y)([:<@~.@/:~((i.@!A.i.)y)|:(y#2)\$])@#:i.2^2^y'


Try it online!

-3 bytes for anonymous function (removing f=:)

For each boolean function (truth table), generate its equivalence class, then remove duplicates.

• Does it return 3D array truth table and can't output with echo?
– l4m2
Nov 6, 2018 at 15:13
• @l4m2 I don't understand your question. J can print array of any dimensions. Nov 6, 2018 at 17:13
• or maybe I can't read it? I think f(3) outputs {0,0},{0,a&b},{0,a&!b,0,b&!a,a&b,0},...
– l4m2
Nov 6, 2018 at 18:48