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 esta razón, también se las conoce como funciones booleanas de conteo . ^{[ 2 ]}

Hay 2 ^{n +1} funciones booleanas simétricas n -arias. En lugar de la tabla de verdad , utilizada tradicionalmente 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 mapean n+1 elementos a dos elementos, $f:\{0,1,...,n\}\rightarrow \{0,1\}$ .

Las funciones booleanas simétricas se utilizan para clasificar los problemas de satisfacibilidad booleana .

Casos especiales

Se reconocen varios casos especiales: ^{[ 1 ]}

Función de mayoría : su valor es 1 en vectores de entrada con más de n/2 unos.
Funciones umbral : su valor es 1 en vectores de entrada con k o más unos para un k fijo.
Función de igualdad total y desigualdad total : sus valores son 1 cuando las entradas no tienen todas el mismo valor.
Funciones de conteo exacto : su valor es 1 en vectores de entrada con k unos para un k fijo.
- Función one-hot o 1 en n : su valor es 1 en vectores de entrada con exactamente un elemento.
- Función de un solo cero : su valor es 1 en vectores de entrada con exactamente un cero.
Funciones de congruencia : su valor es 1 en vectores de entrada con el número de unos congruentes a k mod m para k y m fijos.
Función de paridad : su valor es 1 si el vector de entrada tiene un número impar de unos.

Las versiones n-arias de AND , OR , XOR , NAND , NOR y XNOR también son funciones booleanas simétricas.

Propiedades

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

Peso

El peso de la función se puede calcular a partir de su vector de valores:

$|f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{k}$

Forma normal algebraica

La forma normal algebraica contiene todos los monomios de cierto orden. $m$ o ninguna de ellas; es decir, la transformación de Möbius ${\hat {f}}$ La función también es una función simétrica. Por lo tanto, también puede describirse mediante un vector de bits simple ( n +1), el vector ANF. ${\hat {f}}_{m}$ Los vectores ANF y de valores están relacionados por una relación de Möbius: ${\hat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}$ dónde $k_{2}\subsetequ m_{2}$ denota todos los pesos k cuya representación en base 2 está cubierta por la representación en base 2 de m (una consecuencia del teorema de Lucas ). ^{[ 3 ]} Efectivamente, una función booleana simétrica de n variables corresponde a una función booleana ordinaria de log(n) variables que actúa sobre la representación en base 2 del peso de entrada.

Por ejemplo, para funciones de tres variables:

${\begin{array}{lcl}{\hat {f}}_{0}&=&f_{0}\\{\hat {f}}_{1}&=&f_{0}\oplus f_{1}\\{\hat {f}}_{2}&=&f_{0}\oplus f_{2}\\{\hat {f}}_{3}&=&f_{0}\oplus f_{1}\oplus f_{2}\oplus f_{3}\end{array}}$

Entonces, la función de mayoría de tres variables con vector de valores (0, 0, 1, 1) tiene vector ANF (0, 0, 1, 0), es decir: ${\text{Maj}}(x,y,z)=xy\oplus xz\oplus yz$

polinomio hipercubo unitario

Los coeficientes del polinomio real que coinciden con la función en $\{0,1\}^{n}$ son dados por: $f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k}}f_{k}$ Por ejemplo, el polinomio de la función de mayoría de tres variables tiene coeficientes (0, 0, 1, -2): ${\text{Maj}}(x,y,z)=(xy+xz+yz)-2(xyz)$

Ejemplos

Véase también

Función simétrica

Referencias

1 2 Ingo Wegener , "La complejidad de las funciones booleanas simétricas", en: Teoría de la computación y lógica , Lecture Notes in Computer Science , vol. 270, 1987, pp. 433–442
↑ "BooleanCountingFunction—Documentación del lenguaje Wolfram" . reference.wolfram.com . Consultado el 25 de mayo de 2021 .
↑ Canteaut, A.; Videau, M. (2005). "Funciones booleanas simétricas" . IEEE Transactions on Information Theory . 51 (8): 2791– 2811. doi : 10.1109/TIT.2005.851743 . ISSN 1557-9654 .

[weg-1] 1 2 Ingo Wegener , "La complejidad de las funciones booleanas simétricas", en: Teoría de la computación y lógica , Lecture Notes in Computer Science , vol. 270, 1987, pp. 433–442

[2] "BooleanCountingFunction—Documentación del lenguaje Wolfram" . reference.wolfram.com . Consultado el 25 de mayo de 2021 .

[3] Canteaut, A.; Videau, M. (2005). "Funciones booleanas simétricas" . IEEE Transactions on Information Theory . 51 (8): 2791– 2811. doi : 10.1109/TIT.2005.851743 . ISSN 1557-9654 .

[ 1 ]

[ 2 ]

[ 3 ]