Symmetrisk boolesk funktion

I matematik er en symmetrisk boolsk funktion sådan en boolsk funktion , hvis værdi ikke afhænger af permutationen af ​​dens inputbit, men kun afhænger af antallet af enheder ved indgangen [1] .

Det følger af definitionen, at du i stedet for sandhedstabellen , traditionelt brugt til at repræsentere boolske funktioner, kan bruge en mere kompakt repræsentation for symmetriske boolske funktioner af n variable: i form af ( n  + 1)-dimensional vektor, i i -th position, hvoraf ( i  = 0, …,  n ) værdien af ​​funktionen er skrevet for alle inputvektorer, der indeholder i ener.

Særlige lejligheder

Særlige tilfælde af symmetriske booleske funktioner er [1] :

• Tærskelfunktioner : Tag værdien 1 på alle inputvektorer med k eller flere ener for en given k ;
• Præcise værdifunktioner : Tag værdien 1 på alle inputvektorer, der har nøjagtigt k 1s for en given k ;
• Tællerfunktioner : tag værdien 1 på alle inputvektorer, hvor antallet af enheder er sammenligneligt med k modulo m for givet k og m ;
• Paritetsfunktioner : Tag værdien 1 på alle inputvektorer med et lige antal 1s.

Noter

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