Symmetrisk boolesk funktion

I matematik är en symmetrisk boolesk funktion en sådan boolesk funktion , vars värde inte beror på permutationen av dess inmatningsbitar, utan bara beror på antalet enheter vid ingången [1] .

Det följer av definitionen att istället för sanningstabellen , som traditionellt används för att representera booleska funktioner, kan du använda en mer kompakt representation för symmetriska booleska funktioner av n variabler: i form av ( n  + 1)-dimensionell vektor, i i -th position av vilken ( i  = 0 , …,  n ) värdet på funktionen skrivs för alla indatavektorer som innehåller i enor.

Särskilda tillfällen

Specialfall av symmetriska booleska funktioner är [1] :

• Tröskelfunktioner : ta värdet 1 på alla indatavektorer som har k eller fler ettor för en given k ;
• Exakta värdefunktioner : ta värdet 1 på alla indatavektorer som har exakt k 1s för en given k ;
• Räknarfunktioner : ta värdet 1 på alla ingångsvektorer, antalet enheter i vilka är jämförbart med k modulo m för givna k och m ;
• Paritetsfunktioner : ta värdet 1 på alla ingångsvektorer med ett jämnt antal 1:or.

Anteckningar

1. ↑ 1 2 Ingo Wegener , "komplexiteten av symmetriska booleska funktioner", i: Beräkningsteori och logik , föreläsningsanteckningar i datavetenskap , vol. 270, 1987, sid. 433-442