We study a class of functions $ F $ satisfying a condition denoted by $ 0_x $, meaning $ F(x) = 0 $ whenever $ x $ meets a specific threshold. We show that $ F $ is generated by a finite set of functions, none of which are majority or choice functions. Key theoretical results are presented, including proofs of the closure of $ F $ under superposition and the inclusion $ F \subseteq T_0 $, where $ T_0 $ denotes the set of all functions that evaluate to zero whenever at least one variable is zero. Our main theorems confirm that majority functions and choice functions are not elements of $ F $. We further prove that $ F $ is finitely generated, that is, definable by a finite set of functions. These findings offer a novel framework for constructing finitely generated classes in multi-valued logic while excluding the commonly used but computationally intricate majority and choice functions, with practical implications in computational optimization. In conclusion, we discuss potential directions for further research, including the exploration of other classes of functions and the investigation of their properties and applications.
Citation: Anton A. Esin. Finitely generated classes of multi-argument logic functions excluding majority and choice functions[J]. AIMS Mathematics, 2025, 10(4): 10002-10027. doi: 10.3934/math.2025457
We study a class of functions $ F $ satisfying a condition denoted by $ 0_x $, meaning $ F(x) = 0 $ whenever $ x $ meets a specific threshold. We show that $ F $ is generated by a finite set of functions, none of which are majority or choice functions. Key theoretical results are presented, including proofs of the closure of $ F $ under superposition and the inclusion $ F \subseteq T_0 $, where $ T_0 $ denotes the set of all functions that evaluate to zero whenever at least one variable is zero. Our main theorems confirm that majority functions and choice functions are not elements of $ F $. We further prove that $ F $ is finitely generated, that is, definable by a finite set of functions. These findings offer a novel framework for constructing finitely generated classes in multi-valued logic while excluding the commonly used but computationally intricate majority and choice functions, with practical implications in computational optimization. In conclusion, we discuss potential directions for further research, including the exploration of other classes of functions and the investigation of their properties and applications.
| [1] | M. D. Miller, M. A. Thornton, Multiple Valued Logic: Concepts and Representations, Cham: Springer, 2008, https://doi.org/10.1007/978-3-031-79779-8 |
| [2] | M. D. Miller, M. A. Thornton, MVL Concepts and Algebra, Cham: Springer, 2008, 21–42. https://doi.org/10.1007/978-3-031-79779-8_2 |
| [3] |
D. G. Meshchaninov, A family of closed classes in k-valued logic, Moscow Univ. Comput. Math. Cybern., 43 (2019), 25–31. https://doi.org/10.3103/S0278641919010059 doi: 10.3103/S0278641919010059
|
| [4] | L. T. Polkowski, Many-Valued Logics, In: Logics for Computer and Data Sciences, and Artificial Intelligence, Cham: Springer, 2022,171–205. https://doi.org/10.1007/978-3-030-91680-0_6 |
| [5] | Y. I. Manin, B. Zilber, A course in mathematical logic for mathematicians, New York: Springer, 2010. |
| [6] | M. Malkov, Classification of closed sets of functions in multi-valued logic, SOP Trans. Appl. Math, 1 (2014), 96–105. |
| [7] | V. B. Larionov, V. S. Fedorova, On the complexity of the superstructure of classes of monotonic k-valued functions of a special form, News Irkutsk State Univ. Ser. Math., 5 (2012), 70–79. |
| [8] | V. B. Larionov, V. S. Fedorova, On the superstructure of some classes of monotonic functions of multivalued logic, News Irkutsk State Univ. Ser. Math., 6 (2013), 38–47. |
| [9] |
R. A. Salim, Applications of multivalued logic to set theory and calculus, J. Hunan Univ. Nat. Sci., 50 (2023), 39–51. https://doi.org/10.55463/issn.1674-2974.50.12.5 doi: 10.55463/issn.1674-2974.50.12.5
|
| [10] | G. Bruns, P. Godefroid, Model checking with multi-valued logics, In: International Colloquium on Automata, Languages, and Programming, Berlin, Heidelberg: Springer, 2004,281–293. |
| [11] | C.-Y. Lin, C.-J. Liau, Many-valued coalgebraic modal logic: One-step completeness and finite model property, Fuzzy Sets Syst., 467 (2023), 108564. |
| [12] | A. Deptuła, M. Stosiak, R. Cieślicki, M. Karpenko, K. Urbanowicz, P. Skačkauskas, et al., Application of the methodology of multi-valued logic trees with weighting factors in the optimization of a proportional valve, Axioms, 12 (2023), 8. |
| [13] | S. Al-Askaar, M. Perkowski, A new approach to machine learning based on functional decomposition of multi-valued functions, 2021 IEEE 51st International Symposium on Multiple-Valued Logic (ISMVL), 2021,128–135. |
| [14] | A. Y. Bykovsky, N. A. Vasiliev, Parametrical t-gate for joint processing of quantum and classic optoelectronic signals, J, 6 (2023), 384–410. |
| [15] |
X. Kong, Q. Sun, H. Li, Survey on mathematical models and methods of complex logical dynamical systems, Mathematics, 10 (2022), 3722. https://doi.org/10.3390/math10203722 doi: 10.3390/math10203722
|
| [16] | A. A. Esin, Analyzis and design principles of modern control systems based on multi-valued logic models, Upravlenie Bol'shimi Sistemami, 88 (2020), 69–98. |
| [17] | E. Y. Kalimulina, Application of multi-valued logic models in traffic aggregation problems in mobile networks, 2021 IEEE 15th International Conference on Application of Information and Communication Technologies (AICT), 2021, 1–6. |
| [18] | E. Y. Kalimulina, Mathematical model for reliability optimization of distributed telecommunications networks, Proceedings of 2011 International Conference on Computer Science and Network Technology, 2011, 2847–2853. |
| [19] |
E. Y. Kalimulina, A new approach for dependability planning of network systems, Int. J. Syst. Assur. Eng. Manag., 4 (2013), 215–222. https://doi.org/10.1007/s13198-013-0185-2 doi: 10.1007/s13198-013-0185-2
|
| [20] | R. F. H. Fischer, S. Müelich, Coded modulation and shaping for multivalued physical unclonable functions, IEEE Access, 10 (2022), 99178–99194. |
| [21] | E. Y. Kalimulina, Lattice structure of some closed classes for non-binary logic and its applications, In: Mathematical Methods for Engineering Applications, Cham: Springer, 2022, 25–34. |
| [22] | I. Aizenberg, Multiple-Valued Logic and Complex-Valued Neural Networks, Claudio Moraga: A Passion for Multi-Valued Logic and Soft Computing, Cham: Springer, 2017,153–171. https://doi.org/10.1007/978-3-319-48317-7_10 |
| [23] | Y. Zhang, H. Bölcskei, Cellular automata, many-valued logic, and deep neural networks, 2024. Available from: https://arXiv.org/abs/2404.05259. |
| [24] |
E. Y. Kalimulina, Lattice structure of some closed classes for three-valued logic and its applications, Mathematics, 10 (2022), 94. https://doi.org/10.3390/math10010094 doi: 10.3390/math10010094
|
| [25] | A. Esin, Structural analyzis of precomplete classes and closure diagrams in multi-valued logic, Iran. J. Fuzzy Syst., 21 (2024), 127–145. |
| [26] | D. N. Zhuk, From two-valued logic to k -valued logic, Intell. Syst. Theory Appl., 22 (2018), 131–149. |
| [27] |
V. B. Alekseev, On closed classes in partial $k$-valued logic containing a class of monotonic functions, Discrete Math., 30 (2018), 3–13. http://doi.org/10.4213/dm1518 doi: 10.4213/dm1518
|
| [28] | E. Y. Kalimulina, Mutual generation of the choice and majority functions, In: Mathematical Methods for Engineering Applications, Cham: Springer, 2023, 49–57. |
| [29] |
S. S. Marchenkov, A-closed classes of many-valued logic containing constants, Discrete Math. Appl., 8 (1998), 357–374. https://doi.org/10.1515/dma.1998.8.4.357 doi: 10.1515/dma.1998.8.4.357
|
| [30] |
E. Y. Kalimulina, Finiteness of one-valued function classes in many-valued logic, Fractal Fract., 8 (2024), 29. https://doi.org/10.3390/fractalfract8010029 doi: 10.3390/fractalfract8010029
|
| [31] | W. Liu, T. Zhang, E. McLarnon, M. O'Neill, P. Montuschi, F. Lombardi, Design and analyzis of majority logic-based approximate adders and multipliers, IEEE Trans. Emerging Top. Comput., 9 (2021), 1609–1624. |
| [32] | S. Hoory, A. Magen, T. Pitassi, Monotone circuits for the majority function, In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Berlin, Heidelberg: Springer, 2006,410–425. |
| [33] | J. Han, J. Gao, P. Jonker, Y. Qi, J. Fortes, Toward hardware-redundant, fault-tolerant logic for nanoelectronics, IEEE Design Test Comput., 22 (2005), 328–339. |
| [34] | U. Felgner, Choice functions on sets and classes, In: Sets and Classes on The Work by Paul Bernays, Elsevier, 1976,217–255. https://doi.org/10.1016/S0049-237X(08)70887-5 |
| [35] | Y. Yamamoto, An extension of ternary majority function and its application to evolvable system, 33rd International Symposium on Multiple-Valued Logic, 2003. Proceedings., 2003, 17–23. |
| [36] | V. Lecomte, P. Ramakrishnan, L.-Y. Tan, The composition complexity of majority, 2022. Available from: https://arXiv.org/abs/2205.02374 |
| [37] | I. S. Sergeev, Upper bounds for the formula size of the majority function, 2012. Available from: https://arXiv.org/abs/1208.3874 |
| [38] | C. Garban, J. E. Steif, Noise Sensitivity of Boolean Functions and Percolation, Cambridge University Press, 2014. https://doi.org/10.1017/CBO9781139924160 |
| [39] | A. Darabi, M. R. Salehi, E. Abiri, One-sided 10t static-random access memory cell for energy-efficient and noise-immune internet of things applications, Int. J. Circuit Theory Appl., 51 (2023), 379–397. |
| [40] | A. El Gamal, Coding for noisy networks, IEEE Inform. Theory Soc. Newsl., 60 (2010), 8–17. |
| [41] | S. H. Lim, Y.-H. Kim, A. El Gamal, S.-Y. Chung, Noisy network coding, IEEE Trans. Inf. Theory, 57 (2011), 3132–3152. |
| [42] | A. A. Esin, Characteristics of structurally finite classes of order-preserving three-valued logic maps, Logic J. IGPL, jzae128, https://doi.org/10.1093/jigpal/jzae128 |
| [43] | C. Baaij, Digital circuit in C$\lambda$aSH: functional specifications and type-directed synthesis, PhD thesis, University of Twente, 2015. |
| [44] |
S. S. Marchenkov, On the action of the implicative closure operator on the set of partial functions of the multivalued logic, Discrete Math. Appl., 31 (2021), 155–164. https://doi.org/10.1515/dma-2021-0014 doi: 10.1515/dma-2021-0014
|
| [45] |
L. Renren, L. Czukai, The maximal closed classes of unary functions in p-valued logic, Math. Logic Q., 42 (1996), 234–240. https://doi.org/10.1002/malq.199604201200 doi: 10.1002/malq.199604201200
|
| [46] | L. Haddad, D. Lau, Some criteria for partial sheffer functions in k-valued logic., J. Multiple-Valued Logic Soft Comput., 13 (2007), 415. |
| [47] | V. B. Alekseev, On closed classes in partial k-valued logic that contain all polynomials, Discrete Math. Appl., 31 (2021), 231–240. |
| [48] |
I. Makarov, Existence of finite total equivalence systems for certain closed classes of 3-valued logic functions, Log. Univ., 9 (2015), 1–26. https://doi.org/10.1007/s11787-015-0117-9 doi: 10.1007/s11787-015-0117-9
|
| [49] | K. A. Baker, A. F. Pixley, Polynomial interpolation and the chinese remainder theorem for algebraic systems, Math. Z., 143 (1975), 165–174. |
| [50] | A. B. Ugolnikov, About closed Post classes, Izv. Vyssh. Uchebn. Zaved. Mat, 1988, 79–88. Translation in Soviet Math. (Iz. VUZ), 32 (1988), 131–142. |
| [51] | A. B. Ugolnkov, Some problems in the field of mutivalued logics, Proc. X Int. Workshop "Discrete Mathematics and its Applications, 2010, 1–6. |
| [52] | A. B. Ugolnkov. S. S. Marchenkov, Closed classes of Boolean functions, Institute of Appl. Mathematics named after M. V. Keldysh of the USSR Academy of Sciences, Moscow: IPM, 1990. Available from: https://books.google.ru/books?id = LHNHtQEACAAJ. |
Figures(1) / Tables(2)
Anton A. Esin. Finitely generated classes of multi-argument logic functions excluding majority and choice functions[J]. AIMS Mathematics, 2025, 10(4): 10002-10027. doi: 10.3934/math.2025457
DownLoad: