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.


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 '18 at 15:13
  • \$\begingroup\$ @l4m2 I don't understand your question. J can print array of any dimensions. \$\endgroup\$ – user202729 Nov 6 '18 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 '18 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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