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.


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.


1 Answer 1


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.

  • \$\begingroup\$ Does it return 3D array truth table and can't output with echo? \$\endgroup\$
    – l4m2
    Nov 6, 2018 at 15:13
  • \$\begingroup\$ @l4m2 I don't understand your question. J can print array of any dimensions. \$\endgroup\$
    Nov 6, 2018 at 17:13
  • \$\begingroup\$ 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},... \$\endgroup\$
    – l4m2
    Nov 6, 2018 at 18:48

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.