Symmetrinen Boolen funktio

Matematiikassa symmetrinen Boolen funktio on sellainen Boolen funktio , jonka arvo ei riipu sen tulobittien permutaatiosta, vaan riippuu vain tulon yksiköiden määrästä [1] .

Määritelmästä seuraa, että totuustaulukon sijaan, jota perinteisesti käytetään edustamaan Boolen funktioita, voit käyttää kompaktimpaa esitystä n muuttujan symmetrisille Boolen funktioille: ( n  + 1)-ulotteisen vektorin muodossa, i :ssä -:s paikka, josta ( i  = 0 , …,  n ) funktion arvo kirjoitetaan kaikille i yksikköä sisältäville syötevektoreille.

Erikoistilaisuudet

Symmetristen Boolen funktioiden erikoistapaukset ovat [1] :

• Kynnysfunktiot : ota arvo 1 kaikille syötevektoreille, joissa on k tai useampia tietylle k :lle ;
• Tarkan arvon funktiot : ota arvo 1 kaikille tulovektoreille, joilla on täsmälleen k 1s tietylle k :lle ;
• Laskurifunktiot : ota arvo 1 kaikille tulovektoreille, joiden yksiköiden lukumäärä on verrattavissa k modulo m :ään tietylle k :lle ja m :lle ;
• Pariteettifunktiot : ota arvo 1 kaikille tulovektoreille, joiden parillinen määrä on 1.

Muistiinpanot

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