997:
756:
992:{\displaystyle {\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}}}
1252:
686:
1073:
501:
1353:
147:
382:
726:
607:
1119:
564:
319:
1124:
532:
405:
612:
1008:
420:
1261:
1935:
32:
of its input bits, i.e., it depends only on the number of ones (or zeros) in the input. For this reason they are also known as
153:
78:
324:
2018:
1949:
691:
2023:
511:
71:
ones. Mathematically, the symmetric
Boolean functions correspond one-to-one with the functions that map
47:, traditionally used to represent Boolean functions, one may use a more compact representation for an
1734:
535:
576:
744:). Effectively, an n-variable symmetric Boolean function corresponds to a log(n)-variable ordinary
1904:
1085:
741:
540:
1994:
1255:
1002:
169:
1986:
745:
25:
297:
1574:
254:
566:
of the function is also a symmetric function. It can thus also be described by a simple (
517:
390:
385:
2012:
761:
1926:
1794:
44:
29:
17:
1974:
1998:
1990:
1855:
1730:
283:
275:
1247:{\displaystyle f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k}}f_{k}}
1668:
1570:
1450:
279:
271:
263:
235:: their value is 1 on input vectors with the number of ones congruent to
1635:
267:
213:
1082:
The coefficients of the real polynomial agreeing with the function on
733:
681:{\displaystyle {\hat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}}
415:
The weight of the function can be calculated from its value vector:
196:: their values is 1 when the inputs do (not) all have the same value
1005:
with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:
609:. The ANF and value vectors are related by a Möbius relation:
258:: their value is 1 if the input vector has odd number of ones
173:: their value is 1 on input vectors with more than n/2 ones
736:
representation is covered by the base-2 representation of
748:
acting on the base-2 representation of the input weight.
227:: their value is 1 on input vectors with exactly one zero
1950:"BooleanCountingFunction—Wolfram Language Documentation"
1068:{\displaystyle {\text{Maj}}(x,y,z)=xy\oplus xz\oplus yz}
221:: their value is 1 on input vectors with exactly one one
1929:, "The Complexity of Symmetric Boolean Functions", in:
496:{\displaystyle |f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{k}}
67:) is the value of the function on an input vector with
1363:
The 16 symmetric
Boolean functions of three variables
1348:{\displaystyle {\text{Maj}}(x,y,z)=(xy+xz+yz)-2(xyz)}
1264:
1127:
1088:
1011:
759:
694:
615:
579:
543:
520:
423:
393:
327:
300:
81:
1347:
1246:
1113:
1067:
991:
720:
680:
601:
558:
526:
495:
399:
376:
313:
142:{\displaystyle f:\{0,1,...,n\}\rightarrow \{0,1\}}
141:
1228:
1215:
477:
464:
152:Symmetric Boolean functions are used to classify
377:{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}
514:either contains all monomials of certain order
8:
1102:
1089:
371:
359:
347:
334:
136:
124:
118:
88:
751:For example, for three-variable functions:
51:-variable symmetric Boolean function: the (
1258:polynomial has coefficients (0, 0, 1, -2):
164:A number of special cases are recognized:
1265:
1263:
1238:
1227:
1214:
1212:
1205:
1197:
1189:
1181:
1180:
1161:
1150:
1137:
1132:
1126:
1105:
1087:
1012:
1010:
979:
966:
953:
940:
923:
912:
911:
900:
887:
870:
859:
858:
847:
834:
817:
806:
805:
794:
777:
766:
765:
760:
758:
712:
699:
693:
672:
660:
647:
642:
629:
618:
617:
614:
593:
582:
581:
578:
545:
544:
542:
519:
487:
476:
463:
461:
455:
444:
432:
424:
422:
392:
350:
326:
305:
299:
202:: their value is 1 on input vectors with
179:: their value is 1 on input vectors with
80:
1361:
1979:IEEE Transactions on Information Theory
1916:
43:-ary Boolean functions. Instead of the
286:are also symmetric Boolean functions.
1922:
1920:
7:
721:{\displaystyle k_{2}\subseteq m_{2}}
384:when applied to an input vector of
28:whose value does not depend on the
1219:
468:
321:denotes the value of the function
14:
1973:Canteaut, A.; Videau, M. (2005).
1936:Lecture Notes in Computer Science
1254:For example, the three variable
154:Boolean satisfiability problems
63: = 0, ...,
1342:
1330:
1321:
1294:
1288:
1270:
1206:
1198:
1190:
1182:
1177:
1167:
1035:
1017:
917:
864:
811:
771:
623:
602:{\displaystyle {\hat {f}}_{m}}
587:
550:
433:
425:
356:
121:
55: + 1)-vector, whose
1:
1975:"Symmetric Boolean functions"
1939:, vol. 270, 1987, pp. 433–442
1931:Computation Theory and Logic
534:, or none of them; i.e. the
1114:{\displaystyle \{0,1\}^{n}}
2040:
559:{\displaystyle {\hat {f}}}
75:elements to two elements,
34:Boolean counting functions
22:symmetric Boolean function
1453:, Threshold(3), Count(3)
1382:
1379:
1376:
1373:
1370:
1367:
1078:Unit hypercube polynomial
183:or more ones for a fixed
728:denotes all the weights
1991:10.1109/TIT.2005.851743
1514:"most", "at least two"
1511:Majority, Threshold(2)
1380:Colloquial description
1641:"any", "at least one"
1349:
1248:
1166:
1115:
1069:
1001:So the three variable
993:
722:
682:
603:
560:
528:
497:
460:
401:
378:
315:
262:The n-ary versions of
194:not-all-equal function
143:
39:There are 2 symmetric
1954:reference.wolfram.com
1350:
1249:
1146:
1116:
1070:
994:
723:
683:
604:
561:
529:
512:algebraic normal form
506:Algebraic normal form
498:
440:
402:
379:
316:
314:{\displaystyle f_{k}}
200:Exact-count functions
144:
1262:
1125:
1086:
1009:
757:
692:
613:
577:
570:+1) bit vector, the
541:
518:
421:
391:
325:
298:
233:Congruence functions
79:
1482:Count(2), One-cold
1364:
1142:
177:Threshold functions
1905:Symmetric function
1828:"not exactly two"
1767:"not exactly one"
1540:Count(1), One-hot
1362:
1345:
1244:
1128:
1111:
1065:
989:
987:
740:(a consequence of
718:
678:
667:
599:
556:
524:
493:
397:
374:
311:
294:In the following,
139:
1896:
1895:
1268:
1256:majority function
1226:
1015:
1003:majority function
920:
867:
814:
774:
638:
626:
590:
553:
527:{\displaystyle m}
475:
400:{\displaystyle k}
225:One-cold function
206:ones for a fixed
170:Majority function
2031:
2003:
2002:
1985:(8): 2791–2811.
1970:
1964:
1963:
1961:
1960:
1946:
1940:
1924:
1365:
1354:
1352:
1351:
1346:
1269:
1266:
1253:
1251:
1250:
1245:
1243:
1242:
1233:
1232:
1231:
1218:
1211:
1210:
1209:
1201:
1193:
1185:
1165:
1160:
1141:
1136:
1120:
1118:
1117:
1112:
1110:
1109:
1074:
1072:
1071:
1066:
1016:
1013:
998:
996:
995:
990:
988:
984:
983:
971:
970:
958:
957:
945:
944:
928:
927:
922:
921:
913:
905:
904:
892:
891:
875:
874:
869:
868:
860:
852:
851:
839:
838:
822:
821:
816:
815:
807:
799:
798:
782:
781:
776:
775:
767:
746:Boolean function
727:
725:
724:
719:
717:
716:
704:
703:
687:
685:
684:
679:
677:
676:
666:
665:
664:
652:
651:
634:
633:
628:
627:
619:
608:
606:
605:
600:
598:
597:
592:
591:
583:
565:
563:
562:
557:
555:
554:
546:
536:Möbius transform
533:
531:
530:
525:
502:
500:
499:
494:
492:
491:
482:
481:
480:
467:
459:
454:
436:
428:
406:
404:
403:
398:
383:
381:
380:
375:
355:
354:
320:
318:
317:
312:
310:
309:
148:
146:
145:
140:
26:Boolean function
2039:
2038:
2034:
2033:
2032:
2030:
2029:
2028:
2019:Boolean algebra
2009:
2008:
2007:
2006:
1972:
1971:
1967:
1958:
1956:
1948:
1947:
1943:
1925:
1918:
1913:
1901:
1638:, Threshold(1)
1579:"one or three"
1420:Constant false
1368:Function value
1360:
1260:
1259:
1234:
1213:
1176:
1123:
1122:
1101:
1084:
1083:
1080:
1007:
1006:
986:
985:
975:
962:
949:
936:
934:
929:
910:
907:
906:
896:
883:
881:
876:
857:
854:
853:
843:
830:
828:
823:
804:
801:
800:
790:
788:
783:
764:
755:
754:
708:
695:
690:
689:
668:
656:
643:
616:
611:
610:
580:
575:
574:
539:
538:
516:
515:
508:
483:
462:
419:
418:
413:
389:
388:
346:
323:
322:
301:
296:
295:
292:
255:Parity function
239: mod
219:1-in-n function
162:
77:
76:
12:
11:
5:
2037:
2035:
2027:
2026:
2021:
2011:
2010:
2005:
2004:
1965:
1941:
1915:
1914:
1912:
1909:
1908:
1907:
1900:
1897:
1894:
1893:
1890:
1887:
1886:Constant true
1884:
1881:
1878:
1875:
1872:
1869:
1865:
1864:
1861:
1860:"at most two"
1858:
1852:
1849:
1846:
1843:
1840:
1837:
1833:
1832:
1829:
1826:
1824:
1821:
1818:
1815:
1812:
1809:
1805:
1804:
1801:
1800:"at most one"
1798:
1791:
1788:
1785:
1782:
1779:
1776:
1772:
1771:
1768:
1765:
1763:
1760:
1757:
1754:
1751:
1748:
1744:
1743:
1740:
1739:"none or two"
1737:
1727:
1724:
1721:
1718:
1715:
1712:
1708:
1707:
1704:
1703:"all or none"
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1679:
1678:
1675:
1672:
1665:
1662:
1659:
1656:
1653:
1650:
1646:
1645:
1642:
1639:
1632:
1629:
1626:
1623:
1620:
1617:
1613:
1612:
1609:
1606:
1605:Not-all-equal
1603:
1600:
1597:
1594:
1591:
1588:
1584:
1583:
1580:
1577:
1567:
1564:
1561:
1558:
1555:
1552:
1548:
1547:
1544:
1543:"exactly one"
1541:
1538:
1535:
1532:
1529:
1526:
1523:
1519:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1497:
1494:
1490:
1489:
1486:
1485:"exactly two"
1483:
1480:
1477:
1474:
1471:
1468:
1465:
1461:
1460:
1457:
1454:
1447:
1444:
1441:
1438:
1435:
1432:
1428:
1427:
1424:
1421:
1418:
1415:
1412:
1409:
1406:
1403:
1399:
1398:
1395:
1392:
1389:
1385:
1384:
1381:
1378:
1375:
1372:
1369:
1359:
1356:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1241:
1237:
1230:
1225:
1222:
1217:
1208:
1204:
1200:
1196:
1192:
1188:
1184:
1179:
1175:
1172:
1169:
1164:
1159:
1156:
1153:
1149:
1145:
1140:
1135:
1131:
1108:
1104:
1100:
1097:
1094:
1091:
1079:
1076:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
982:
978:
974:
969:
965:
961:
956:
952:
948:
943:
939:
935:
933:
930:
926:
919:
916:
909:
908:
903:
899:
895:
890:
886:
882:
880:
877:
873:
866:
863:
856:
855:
850:
846:
842:
837:
833:
829:
827:
824:
820:
813:
810:
803:
802:
797:
793:
789:
787:
784:
780:
773:
770:
763:
762:
742:Lucas’ theorem
715:
711:
707:
702:
698:
675:
671:
663:
659:
655:
650:
646:
641:
637:
632:
625:
622:
596:
589:
586:
552:
549:
523:
507:
504:
490:
486:
479:
474:
471:
466:
458:
453:
450:
447:
443:
439:
435:
431:
427:
412:
409:
396:
373:
370:
367:
364:
361:
358:
353:
349:
345:
342:
339:
336:
333:
330:
308:
304:
291:
288:
260:
259:
251:
230:
229:
228:
222:
197:
187:
174:
161:
158:
138:
135:
132:
129:
126:
123:
120:
117:
114:
111:
108:
105:
102:
99:
96:
93:
90:
87:
84:
13:
10:
9:
6:
4:
3:
2:
2036:
2025:
2022:
2020:
2017:
2016:
2014:
2000:
1996:
1992:
1988:
1984:
1980:
1976:
1969:
1966:
1955:
1951:
1945:
1942:
1938:
1937:
1932:
1928:
1923:
1921:
1917:
1910:
1906:
1903:
1902:
1898:
1892:(1, 0, 0, 0)
1891:
1888:
1885:
1882:
1880:(1, 1, 1, 1)
1879:
1876:
1873:
1870:
1867:
1866:
1863:(1, 0, 0, 1)
1862:
1859:
1857:
1853:
1850:
1848:(1, 1, 1, 0)
1847:
1844:
1841:
1838:
1835:
1834:
1831:(1, 0, 1, 1)
1830:
1827:
1825:
1822:
1820:(1, 1, 0, 1)
1819:
1816:
1813:
1810:
1807:
1806:
1803:(1, 0, 1, 0)
1802:
1799:
1796:
1792:
1789:
1787:(1, 1, 0, 0)
1786:
1783:
1780:
1777:
1774:
1773:
1770:(1, 1, 0, 1)
1769:
1766:
1764:
1761:
1759:(1, 0, 1, 1)
1758:
1755:
1752:
1749:
1746:
1745:
1742:(1, 1, 0, 0)
1741:
1738:
1736:
1732:
1728:
1725:
1723:(1, 0, 1, 0)
1722:
1719:
1716:
1713:
1710:
1709:
1706:(1, 1, 1, 0)
1705:
1702:
1699:
1696:
1694:(1, 0, 0, 1)
1693:
1690:
1687:
1684:
1681:
1680:
1677:(1, 1, 1, 1)
1676:
1673:
1670:
1666:
1663:
1661:(1, 0, 0, 0)
1660:
1657:
1654:
1651:
1648:
1647:
1644:(0, 1, 1, 1)
1643:
1640:
1637:
1633:
1630:
1628:(0, 1, 1, 1)
1627:
1624:
1621:
1618:
1615:
1614:
1611:(0, 1, 1, 0)
1610:
1608:"one or two"
1607:
1604:
1601:
1599:(0, 1, 1, 0)
1598:
1595:
1592:
1589:
1586:
1585:
1582:(0, 1, 0, 0)
1581:
1578:
1576:
1572:
1568:
1565:
1563:(0, 1, 0, 1)
1562:
1559:
1556:
1553:
1550:
1549:
1546:(0, 1, 0, 1)
1545:
1542:
1539:
1536:
1534:(0, 1, 0, 0)
1533:
1530:
1527:
1524:
1521:
1520:
1517:(0, 0, 1, 0)
1516:
1513:
1510:
1507:
1505:(0, 0, 1, 1)
1504:
1501:
1498:
1495:
1492:
1491:
1488:(0, 0, 1, 1)
1487:
1484:
1481:
1478:
1476:(0, 0, 1, 0)
1475:
1472:
1469:
1466:
1463:
1462:
1459:(0, 0, 0, 1)
1458:
1455:
1452:
1448:
1445:
1443:(0, 0, 0, 1)
1442:
1439:
1436:
1433:
1430:
1429:
1426:(0, 0, 0, 0)
1425:
1422:
1419:
1416:
1414:(0, 0, 0, 0)
1413:
1410:
1407:
1404:
1401:
1400:
1396:
1393:
1390:
1387:
1386:
1371:Value vector
1366:
1357:
1355:
1339:
1336:
1333:
1327:
1324:
1318:
1315:
1312:
1309:
1306:
1303:
1300:
1297:
1291:
1285:
1282:
1279:
1276:
1273:
1257:
1239:
1235:
1223:
1220:
1202:
1194:
1186:
1173:
1170:
1162:
1157:
1154:
1151:
1147:
1143:
1138:
1133:
1129:
1121:are given by:
1106:
1098:
1095:
1092:
1077:
1075:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1032:
1029:
1026:
1023:
1020:
1004:
999:
980:
976:
972:
967:
963:
959:
954:
950:
946:
941:
937:
931:
924:
914:
901:
897:
893:
888:
884:
878:
871:
861:
848:
844:
840:
835:
831:
825:
818:
808:
795:
791:
785:
778:
768:
752:
749:
747:
743:
739:
735:
731:
713:
709:
705:
700:
696:
673:
669:
661:
657:
653:
648:
644:
639:
635:
630:
620:
594:
584:
573:
569:
547:
537:
521:
513:
505:
503:
488:
484:
472:
469:
456:
451:
448:
445:
441:
437:
429:
416:
410:
408:
394:
387:
368:
365:
362:
351:
343:
340:
337:
331:
328:
306:
302:
289:
287:
285:
281:
277:
273:
269:
265:
257:
256:
252:
250:
246:
242:
238:
234:
231:
226:
223:
220:
216:
215:
211:
210:
209:
205:
201:
198:
195:
191:
188:
186:
182:
178:
175:
172:
171:
167:
166:
165:
160:Special cases
159:
157:
155:
150:
133:
130:
127:
115:
112:
109:
106:
103:
100:
97:
94:
91:
85:
82:
74:
70:
66:
62:
58:
54:
50:
46:
42:
37:
35:
31:
27:
23:
19:
2024:Cryptography
1982:
1978:
1968:
1957:. Retrieved
1953:
1944:
1934:
1930:
1927:Ingo Wegener
1456:"all three"
1081:
1000:
753:
750:
737:
729:
571:
567:
509:
417:
414:
293:
261:
253:
248:
244:
240:
236:
232:
224:
218:
212:
207:
203:
199:
193:
189:
184:
180:
176:
168:
163:
151:
72:
68:
64:
60:
56:
52:
48:
40:
38:
33:
21:
15:
1795:Horn clause
1735:even parity
1671:, Count(0)
1383:ANF vector
59:-th entry (
45:truth table
18:mathematics
2013:Categories
1959:2021-05-25
1911:References
1854:Three-way
1729:Three-way
1700:All-equal
1667:Three-way
1634:Three-way
1569:Three-way
1449:Three-way
572:ANF vector
290:Properties
243:for fixed
1999:1557-9654
1889:"always"
1325:−
1171:−
1148:∑
1139:∗
1057:⊕
1048:⊕
973:⊕
960:⊕
947:⊕
918:^
894:⊕
865:^
841:⊕
812:^
772:^
706:⊆
654:⊆
640:⨁
624:^
588:^
551:^
442:∑
357:→
190:All-equal
122:→
1899:See also
1573:, (odd)
1423:"never"
1358:Examples
1674:"none"
1374:Weight
247:,
214:One-hot
1997:
1575:parity
734:base-2
732:whose
688:where
411:Weight
386:weight
1377:Name
30:order
24:is a
1995:ISSN
1856:NAND
1731:XNOR
510:The
284:XNOR
282:and
276:NAND
192:and
20:, a
1987:doi
1669:NOR
1571:XOR
1451:AND
1267:Maj
1014:Maj
280:NOR
272:XOR
264:AND
217:or
73:n+1
16:In
2015::
1993:.
1983:51
1981:.
1977:.
1952:.
1933:,
1919:^
1883:8
1877:T
1874:T
1871:T
1868:T
1851:7
1845:F
1842:T
1839:T
1836:T
1823:5
1817:T
1814:F
1811:T
1808:T
1797:)
1790:4
1784:F
1781:F
1778:T
1775:T
1762:5
1756:T
1753:T
1750:F
1747:T
1733:,
1726:4
1720:F
1717:T
1714:F
1711:T
1697:2
1691:T
1688:F
1685:F
1682:T
1664:1
1658:F
1655:F
1652:F
1649:T
1636:OR
1631:7
1625:T
1622:T
1619:T
1616:F
1602:6
1596:F
1593:T
1590:T
1587:F
1566:4
1560:T
1557:F
1554:T
1551:F
1537:3
1531:F
1528:F
1525:T
1522:F
1508:4
1502:T
1499:T
1496:F
1493:F
1479:3
1473:F
1470:T
1467:F
1464:F
1446:1
1440:T
1437:F
1434:F
1431:F
1417:0
1411:F
1408:F
1405:F
1402:F
1397:3
1394:2
1391:1
1388:0
407:.
278:,
274:,
270:,
268:OR
266:,
156:.
149:.
36:.
2001:.
1989::
1962:.
1793:(
1343:)
1340:z
1337:y
1334:x
1331:(
1328:2
1322:)
1319:z
1316:y
1313:+
1310:z
1307:x
1304:+
1301:y
1298:x
1295:(
1292:=
1289:)
1286:z
1283:,
1280:y
1277:,
1274:x
1271:(
1240:k
1236:f
1229:)
1224:k
1221:m
1216:(
1207:|
1203:m
1199:|
1195:+
1191:|
1187:k
1183:|
1178:)
1174:1
1168:(
1163:m
1158:0
1155:=
1152:k
1144:=
1134:m
1130:f
1107:n
1103:}
1099:1
1096:,
1093:0
1090:{
1063:z
1060:y
1054:z
1051:x
1045:y
1042:x
1039:=
1036:)
1033:z
1030:,
1027:y
1024:,
1021:x
1018:(
981:3
977:f
968:2
964:f
955:1
951:f
942:0
938:f
932:=
925:3
915:f
902:2
898:f
889:0
885:f
879:=
872:2
862:f
849:1
845:f
836:0
832:f
826:=
819:1
809:f
796:0
792:f
786:=
779:0
769:f
738:m
730:k
714:2
710:m
701:2
697:k
674:k
670:f
662:2
658:m
649:2
645:k
636:=
631:m
621:f
595:m
585:f
568:n
548:f
522:m
489:k
485:f
478:)
473:k
470:n
465:(
457:n
452:0
449:=
446:k
438:=
434:|
430:f
426:|
395:k
372:}
369:1
366:,
363:0
360:{
352:n
348:}
344:1
341:,
338:0
335:{
332::
329:f
307:k
303:f
249:m
245:k
241:m
237:k
208:k
204:k
185:k
181:k
137:}
134:1
131:,
128:0
125:{
119:}
116:n
113:,
110:.
107:.
104:.
101:,
98:1
95:,
92:0
89:{
86::
83:f
69:i
65:n
61:i
57:i
53:n
49:n
41:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.