Me gustaría saber el número de funciones booleanas en $N$ variables. Sin embargo, hay un truco: cuando una función puede obtenerse a partir de otra permutando las variables, éstas sólo deben contar una vez. Por ejemplo, $a\wedge b$ y $a\wedge c$ son iguales (porque acabamos de intercambiar $b$ y $c$ asumiendo $N\ge 3$ ), pero son distintas de $\neg a\wedge b$ o $\neg(a\wedge b)$ .
Para $N=0,1,2$ hay $2,4,12$ dichas funciones. Especulé con la fórmula $$\prod_{k=0}^N\left[{N\choose k}+1\right]$$ que predice $64$ y $700$ para $N=3,4$ pero mi simulación por ordenador no lo confirma (cuenta $92$ y $8500$ respectivamente). Sin embargo, soy escéptico sobre mi simulación, porque esa secuencia no existe en OEIS.
¿Cuántas funciones hay? ¿Es correcta mi fórmula?
EDITAR:
Para $N=2$ con variables $a$ y $b$ tenemos las siguientes funciones: $true$ , $false$ , $a$ , $\neg a$ , $a\wedge b$ , $\neg(a\wedge b)$ , $a\vee b$ , $\neg(a\vee b)$ , $\neg a\wedge b$ , $\neg a\vee b$ , $a\otimes b$ , $a\leftrightarrow b$ . Los siguientes son duplicados: $b$ , $\neg b$ , $\neg b\wedge a$ , $\neg b\vee a$ . Contando estos también se obtendría el $2^{2^N}=16$ .
