Función booleana simétrica

---

En matemáticas , una función booleana simétrica es una función booleana cuyo valor no depende del orden de sus bits de entrada, es decir, depende únicamente del número de unos (o ceros) en la entrada. ^[1] Por este motivo también se conocen como funciones booleanas de conteo . ^[2]

Hay 2 ^{n +1} funciones booleanas simétricas n -arias. En lugar de la tabla de verdad , tradicionalmente utilizada para representar funciones booleanas, se puede utilizar una representación más compacta para una función booleana simétrica de n variables: el vector ( n +  1), cuya i -ésima entrada ( i  = 0, .. .,  n ) es el valor de la función en un vector de entrada con i unos. Matemáticamente, las funciones booleanas simétricas se corresponden uno a uno con las funciones que asignan n+1 elementos a dos elementos, .${\displaystyle f:\{0,1,...,n\}\rightarrow \{0,1\}}$

A continuación, denota el valor de la función cuando se aplica a un vector de entrada de peso .${\displaystyle f_{k}}$${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$ ${\ estilo de visualización k}$

La forma normal algebraica contiene todos los monomios de cierto orden , o ninguno de ellos; es decir, la transformada de Möbius de la función también es una función simétrica. Por lo tanto, también se puede describir mediante un vector de bits simple ( n +1), el vector ANF . Los vectores ANF y de valor están relacionados por una relación de Möbius:${\ estilo de visualización m}$ ${\ estilo de visualización {\ sombrero {f}}}$ ${\displaystyle {\sombrero {f}}_{m}}$

Entonces, la función mayoritaria de tres variables con vector de valor (0, 0, 1, 1) tiene un vector ANF (0, 0, 1, 0), es decir:

Los coeficientes del polinomio real que concuerdan con la función en están dados por:${\ estilo de visualización \ {0,1 \}^ {n}}$

---