Funcție booleană simetrică

În matematică , o funcție booleană simetrică este o astfel de funcție booleană , a cărei valoare nu depinde de permutarea biților săi de intrare, ci depinde doar de numărul de unități de la intrare [1] .

Din definiție rezultă că în locul tabelului de adevăr , folosit în mod tradițional pentru a reprezenta funcțiile booleene, puteți utiliza o reprezentare mai compactă pentru funcțiile booleene simetrice ale n variabile: sub forma vectorului ( n  + 1)-dimensional, în i -a poziție din care ( i  = 0 , …,  n ) valoarea funcției este scrisă pentru toți vectorii de intrare care îi conțin i .

Ocazii speciale

Cazurile speciale de funcții booleene simetrice sunt [1] :

• Funcții de prag : iau valoarea 1 pe toți vectorii de intrare care au k sau mai mulți pentru un k dat ;
• Funcții de valoare exactă : luați valoarea 1 pe toți vectorii de intrare care au exact k 1s pentru un k dat ;
• Funcții de contor : luați valoarea 1 pe toți vectorii de intrare, numărul de unități în care este comparabil cu k modulo m pentru k și m date ;
• Funcții de paritate : luați valoarea 1 pe toți vectorii de intrare cu un număr par de 1s.

Note

1. ↑ 1 2 Ingo Wegener , „The Complexity of Symmetric Boolean Functions”, în: Computation Theory and Logic , Lecture Notes in Computer Science , vol. 270, 1987, pp. 433-442