Symetrická booleovská funkce

V matematice je symetrická booleovská funkce taková booleovská funkce , jejíž hodnota nezávisí na permutaci jejích vstupních bitů, ale závisí pouze na počtu jednotek na vstupu [1] .

Z definice vyplývá, že místo pravdivostní tabulky , tradičně používané pro reprezentaci booleovských funkcí, můžete použít kompaktnější reprezentaci pro symetrické booleovské funkce n proměnných: ve formě ( n  + 1)-rozměrného vektoru, v i -tá pozice, z níž ( i  = 0 , …,  n ) je hodnota funkce zapsána pro všechny vstupní vektory obsahující i jedničky.

Zvláštní příležitosti

Speciální případy symetrických booleovských funkcí jsou [1] :

• Prahové funkce : nabývají hodnoty 1 na všech vstupních vektorech, které mají k nebo více jedniček pro dané k ;
• Funkce přesné hodnoty : vezměte hodnotu 1 na všech vstupních vektorech, které mají přesně k 1s pro dané k ;
• Funkce čítače : na všech vstupních vektorech nabere hodnotu 1, počet jednotek je srovnatelný s k modulo m pro dané k a m ​​;
• Paritní funkce : mít hodnotu 1 na všech vstupních vektorech se sudým počtem 1s.

Poznámky

1. ↑ 1 2 Ingo Wegener , "The Complexity of Symmetric Boolean Functions", in: Computation Theory and Logic , Lecture Notes in Computer Science , sv. 270, 1987, str. 433-442