Definability of Boolean function classes by linear equations over \(\mathbf{GF}(2)\). (English) Zbl 1051.06009
Summary: Necessary and sufficient conditions are provided for a class of Boolean functions to be definable by a set of linear functional equations over the two-element field. The conditions are given both in terms of closure with respect to certain functional compositions and in terms of definability by relational constraints.
MSC:
| 06E30 | Boolean functions |
| 39B52 | Functional equations for functions with more general domains and/or ranges |
Keywords:
Boolean function classes; Clones; Equational classes; Linear functions; Relational constraintsReferences:
| [1] | Davio, M.; Deschamps, J.-P; Thayse, A., Discrete and Switching Functions, McGraw Hill (1978), Georgi Publishing: Georgi Publishing New York · Zbl 0385.94020 |
| [2] | Ekin, O.; Foldes, S.; Hammer, P. L.; Hellerstein, L., Equational characterizations of Boolean function classes, Discrete Math., 211, 27-51 (2000) · Zbl 0947.06008 |
| [3] | Foldes, S., Equational classes of Boolean functions via the HSP theorem, Algebra Universalis, 44, 309-324 (2000) · Zbl 1013.06016 |
| [4] | S. Foldes, G. Pogosyan, Post classes characterized by functional terms, Rutcor Research Report 32, 2000, Rutgers University, Discrete Appl. Math., X-ref: 10.1016/j.dam.2003.01.002; S. Foldes, G. Pogosyan, Post classes characterized by functional terms, Rutcor Research Report 32, 2000, Rutgers University, Discrete Appl. Math., X-ref: 10.1016/j.dam.2003.01.002 · Zbl 1051.06011 |
| [5] | Geiger, D., Closed systems of functions and predicates, Pacific, J. Math., 27, 95-100 (1968) · Zbl 0186.02502 |
| [6] | Hellerstein, L., On generalized constraints and certificates, Discrete Math., 226, 211-232 (2001) · Zbl 0965.06016 |
| [7] | Mal’cev, A. I., The Metamathematics of Algebraic Systems (1971), North-Holland: North-Holland Amsterdam · Zbl 0231.02002 |
| [8] | Pippenger, N., Theories of Computability (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0879.03013 |
| [9] | Pippenger, N., Galois theory for minors of finite functions, Discrete Math., 254, 405-419 (2002) · Zbl 1010.06012 |
| [10] | Pogosyan, G., Classes of Boolean functions defined by functional terms, Multiple Valued Logic, 7, 417-448 (2002) · Zbl 1016.06011 |
| [11] | E. Post, The Two-valued iterative systems of mathematical logic, Annals of Mathematics Studies, Vol. 5, Princeton University Press, Princeton, NJ, 1941.; E. Post, The Two-valued iterative systems of mathematical logic, Annals of Mathematics Studies, Vol. 5, Princeton University Press, Princeton, NJ, 1941. · Zbl 0063.06326 |
| [12] | Pöschel, R.; Kaluzhnin, L. A., Funktionen- und Relationenalgebren (1979), Birkhäusser: Birkhäusser Basel · Zbl 0418.03044 |
| [13] | Stone, M. H., Subsumption of the theory of Boolean algebras under the theory of rings, Proc. Natl. Acad. Sci. USA, 31, 103-105 (1935) · Zbl 0011.05104 |
| [14] | Wang, C., Boolean minors, Discrete Math., 141, 237-258 (1995) · Zbl 0837.68081 |
| [15] | Wang, C.; Williams, A. C., The threshold order of a Boolean function, Discrete Appl. Math., 31, 51-69 (1991) · Zbl 0728.94015 |
| [16] | I.E. Zverovich, Characterization of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes, Rutcor Research Report 17, 2000, Rutgers University; http://rutcor.rutgers.edu; I.E. Zverovich, Characterization of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes, Rutcor Research Report 17, 2000, Rutgers University; http://rutcor.rutgers.edu |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
