Symmetrisk boolesk funktion

I matematik är en symmetrisk boolesk funktion en boolesk funktion vars värde inte beror på ordningen på dess inmatade bitar, dvs det beror bara på antalet ettor (eller nollor) i inmatningen. Av denna anledning är de också kända som booleska räknefunktioner .

Det finns 2 ^{n +1} symmetriska n -ära booleska funktioner. Istället för sanningstabellen , som traditionellt används för att representera booleska funktioner, kan man använda en mer kompakt representation för en n -variabel symmetrisk boolesk funktion: ( n + 1)-vektorn, vars i -te ingång ( i = 0, .. ., n ) är värdet av funktionen på en indatavektor med i -ettor. Matematiskt motsvarar de symmetriska booleska funktionerna en-till-en de funktioner som mappar n+1 element till två element, $f:\{0,1,...,n\}\högerpil \{0,1\}$ .

Symmetriska booleska funktioner används för att klassificera booleska tillfredsställelseproblem .

Speciella fall

Ett antal specialfall erkänns:

• Majoritetsfunktion : deras värde är 1 på ingångsvektorer med fler än n/2 ettor
• Tröskelfunktioner : deras värde är 1 på ingångsvektorer med k eller fler ettor för en fast k
• Alla-lika och inte-alla-lika funktion : deras värden är 1 när ingångarna har (inte) alla samma värde
• Exakt räknefunktioner : deras värde är 1 på ingångsvektorer med k ettor för en fast k
  • En-het eller 1-i-n-funktion : deras värde är 1 på indatavektorer med exakt en
  • En-kall funktion : deras värde är 1 på ingångsvektorer med exakt en nolla
• Kongruensfunktioner : deras värde är 1 på indatavektorer med antalet ettor kongruent med k mod m för fast k , m
• Paritetsfunktion : deras värde är 1 om ingångsvektorn har udda antal ettor

De nära versionerna av AND , OR , XOR , NAND , NOR och XNOR är också symmetriska booleska funktioner.

Egenskaper

I det följande betecknar $f_{k}$ värdet av funktionen $f:\{0,1\}^{n}\rightarrow \{0,1\}$ när den tillämpas på en indatavektor med vikten $k$ .

Vikt

Funktionens vikt kan beräknas från dess värdevektor:

$$|f|=\summa _{k=0}^{n}{\binom {n}{k}}f_{k}$$

Algebraisk normalform

Den algebraiska normalformen innehåller antingen alla monomer av viss ordning $m$ , eller ingen av dem; dvs Möbiustransformen ${\hat {f}}$ för funktionen är också en symmetrisk funktion. Den kan alltså också beskrivas med en enkel ( n +1) bitvektor, ANF-vektorn ${\hat {f}}_{m}$ . ANF- och värdevektorerna är relaterade av en Möbius-relation:

$${\hat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}$$

där $k_{2}\subseteq m_{2}$ betecknar alla vikterna k vars bas-2- representation täcks av bas-2-representationen av m (en konsekvens av Lucas sats ). Effektivt motsvarar en n-variabel symmetrisk boolesk funktion en log(n)-variabel vanlig boolesk funktion som verkar på bas-2-representationen av den ingående vikten.

Till exempel, för funktioner med tre variabler:

$${\begin{array}{lcl}{\hat { f}}_{0}&=&f_{0}\\{\hat {f}}_{1}&=&f_{0}\oplus f_{1}\\{\hat {f}}_{2 }&=&f_{0}\oplus f_{2}\\{\hat {f}}_{3}&=&f_{0}\oplus f_{1}\oplus f_{2}\oplus f_{3} \end{array}}$$

Så de tre variabla majoritetsfunktionerna med värdevektor (0, 0, 1, 1) har ANF-vektor (0, 0, 1, 0), dvs.

$${\text{Maj}}(x,y,z)=xy\oplus xz\oplus yz$$

Enhetshyperkubpolynom

Koefficienterna för det reella polynomet som överensstämmer med funktionen på $\{0,1\}^{n}$ ges av:

$$f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m} {k}}f_{k}$$

Till exempel har polynomet med tre variabla majoritetsfunktioner koefficienter (0, 0, 1, -2):

$${\text{Maj}}(x,y,z)=(xy+xz+yz )-2(xyz)$$

Exempel

De 16 symmetriska booleska funktionerna av tre variabler

Funktionsvärde				Värde vektor	Vikt	namn	Samtalsbeskrivning	ANF-vektor
0	1	2	3
F	F	F	F	(0, 0, 0, 0)	0	Ständigt falskt	"aldrig"	(0, 0, 0, 0)
F	F	F	T	(0, 0, 0, 1)	1	Trevägs AND , Tröskel(3), Räkna(3)	"alla tre"	(0, 0, 0, 1)
F	F	T	F	(0, 0, 1, 0)	3	Räkna(2), En-kall	"exakt två"	(0, 0, 1, 1)
F	F	T	T	(0, 0, 1, 1)	4	Majoritet, tröskel(2)	"mest", "minst två"	(0, 0, 1, 0)
F	T	F	F	(0, 1, 0, 0)	3	Räkna(1), One-hot	"exakt en"	(0, 1, 0, 1)
F	T	F	T	(0, 1, 0, 1)	4	Trevägs XOR , (udda) paritet	"en eller tre"	(0, 1, 0, 0)
F	T	T	F	(0, 1, 1, 0)	6	Inte-alla-lika	"en eller två"	(0, 1, 1, 0)
F	T	T	T	(0, 1, 1, 1)	7	Trevägs ELLER , tröskel(1)	"alla", "minst en"	(0, 1, 1, 1)
T	F	F	F	(1, 0, 0, 0)	1	Trevägs NOR , Count(0)	"ingen"	(1, 1, 1, 1)
T	F	F	T	(1, 0, 0, 1)	2	Alla lika	"alla eller inga"	(1, 1, 1, 0)
T	F	T	F	(1, 0, 1, 0)	4	Trevägs XNOR , jämn paritet	"ingen eller två"	(1, 1, 0, 0)
T	F	T	T	(1, 0, 1, 1)	5		"inte precis en"	(1, 1, 0, 1)
T	T	F	F	(1, 1, 0, 0)	4	( Hornklausul )	"högst en"	(1, 0, 1, 0)
T	T	F	T	(1, 1, 0, 1)	5		"inte direkt två"	(1, 0, 1, 1)
T	T	T	F	(1, 1, 1, 0)	7	Trevägs NAND	"högst två"	(1, 0, 0, 1)
T	T	T	T	(1, 1, 1, 1)	8	Ständigt sant	"alltid"	(1, 0, 0, 0)

Se även

• Symmetrisk funktion