Szimmetrikus logikai függvény
A matematikában szimmetrikus Boole - függvény egy olyan Boole-függvény , amelynek értéke nem a bemeneti bitjeinek permutációjától, hanem csak a bemeneti egységek számától függ [1] .
A definícióból az következik, hogy a hagyományosan Boole-függvények ábrázolására használt igazságtábla helyett n változó szimmetrikus Boole-függvényeihez használhatunk kompaktabb ábrázolást is : ( n + 1)-dimenziós vektor formájában, az i -ben. -edik pozíciója, amelynek ( i = 0, …, n ) a függvény értéke minden i -es vektorra fel van írva .
Különleges alkalmak
A szimmetrikus logikai függvények speciális esetei [1] :
- Küszöbfüggvények : vegyük fel az 1 értéket minden olyan bemeneti vektoron, amelyekben egy adott k -hoz k vagy több van ;
- Pontos értékű függvények : vegyük az 1-es értéket minden olyan bemeneti vektoron, amelyekben pontosan k 1s van egy adott k -re ;
- Számlálófüggvények : vegyük fel az 1 értéket minden olyan bemeneti vektoron, amelyekben az egységek száma összevethető k modulo m értékkel adott k és m esetén ;
- Paritásfüggvények : vegye fel az 1 értéket minden páros számú 1-es bemeneti vektoron.
Jegyzetek
- ↑ 1 2 Ingo Wegener , "The Complexity of Symmetric Boolean Functions", in: Computation Theory and Logic , Lecture Notes in Computer Science , vol. 270, 1987, pp. 433-442