1
$\begingroup$

i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them all. But if you know the name of what i am searching for or have some strategy how i could approach this or tips for literature where i can read about it, that would also help.

My question is the following:

How many different boolean functions exist up to permutation of its $n$ variables. That is two functions $f$ and $g$ are considered the same if $$ g(x_1,x_2,\dots,x_n) = f(x_{\sigma^{-1}(1)},x_{\sigma^{-1}(2)},\dots,x_{\sigma^{-1}(n)}) \quad \text{for some} \quad \sigma \in S_n $$ For example, i want to treat $A \wedge \neg B$ as if it was equal to $\neg A \wedge B$, and therefore count it only once.

Edit: I also want to treat $A \wedge \neg B$ as if it was equal to $\neg B \wedge A$. That means, i want to treat functions as equal if they are

  1. semantically equal
  2. semantically different but there exists a permutation of variables that makes them semantically equal
Improve this question
$\endgroup$
5
  • $\begingroup$ Do you want to treat $A\wedge \neg B$ as equal to $\neg A \wedge B$ or as equal to $B\wedge \neg A$? The distinction is important, because the first equality is semantic (unless you consider $\wedge$ as an unordered operator), but the second is "only" syntaxic. $\endgroup$
    – Nathaniel
    May 19, 2022 at 16:04
  • $\begingroup$ To give another example: do you consider $\neg(A\wedge B)$ as equal to $(\neg A)\vee(\neg B)$ or not. $\endgroup$
    – Nathaniel
    May 19, 2022 at 16:07
  • $\begingroup$ I want to treat $A \wedge \neg B$ as equal to $\neg A \wedge B$ and as equal to $B \wedge \neg A$. I want count syntacticly different formulas only once but also, more importantly, i want to count those semanticly different formulas only once that become semantically equal if the variables are permuted in some way. $\endgroup$
    – vreithinger
    May 19, 2022 at 16:09
  • $\begingroup$ To answer your second question: yes i consider them equal. But i want to stress that this is not all i am asking. I want to also consider semantically different functions equal if they become semantically equal if the variables are permuted in some way. So, for example: Traditionally $\neg (A \wedge \neg B) = \neg A \vee B$ but i also want $\neg (A \wedge \neg B) = \neg (B \wedge \neg A)$ which would normally not be equal $\endgroup$
    – vreithinger
    May 19, 2022 at 16:10
  • $\begingroup$ Thank you for the precisions. I suggest you add them to your question. $\endgroup$
    – Nathaniel
    May 19, 2022 at 16:18

1 Answer 1

Reset to default
2
$\begingroup$

You are looking for A003180.

The related sequence A003181 counts functions depending on all variables.

Often one allows further operations: negation of inputs, and negation of the output. The corresponding sequence is then A000370.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you a lot. I will read up on that $\endgroup$
    – vreithinger
    May 19, 2022 at 16:32
  • $\begingroup$ Do you also know of an algorithm to list all the functions? $\endgroup$
    – vreithinger
    Dec 22, 2022 at 10:07
  • $\begingroup$ The same approaches used for listing graphs up to isomorphism could also be used here. $\endgroup$
    – Yuval Filmus
    Dec 23, 2022 at 0:25

Your Answer

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

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