Symetrická booleovská funkce - Symmetric Boolean function
v matematika, a symetrická booleovská funkce je Booleovská funkce jehož hodnota nezávisí na permutace jeho vstupních bitů, tj. záleží pouze na počtu jedniček na vstupu.[1]
Z definice vyplývá, že existují 2n+1 symetrický n-ary logické funkce. Znamená to, že namísto pravdivostní tabulka, který se tradičně používá k reprezentaci booleovských funkcí, lze použít kompaktnější vyjádření pro nproměnná symetrická booleovská funkce: (n + 1) -vector, jehož i-tý záznam (i = 0, ..., n) je hodnota funkce na vstupním vektoru s i ty.
Speciální případy
Rozpoznává se řada zvláštních případů.[1]
- Prahové funkce: jejich hodnota je 1 na vstupních vektorech s k nebo více pro pevné k
- Funkce s přesnou hodnotou: jejich hodnota je 1 na vstupních vektorech s k ty pro pevné k
- Funkce počítání : jejich hodnota je 1 na vstupních vektorech s počtem shodných k modm pro pevné k, m
- Paritní funkce: jejich hodnota je 1, pokud má vstupní vektor lichý počet.
Reference
- ^ A b Ingo Wegener „Složitost symetrických booleovských funkcí“, in: Teorie a logika výpočtu, Přednášky z informatiky, sv. 270, 1987, str. 433–442