USING COMPLEX CONJUNCTIONS IN SOLVING NONLINEAR BOOLEAN EQUATIONS

In order to simplify logical statements and reduce the time for solving systems of non-linear Boolean equations, a criterion for the absorption of complex conjunctions by a first-order neighborhood of conjunctions of statements of a separate class of systems of non-linear Boolean equations above the second degree, given by Zhegalkin polynomials, is proposed. In the class of systems of nonlinear Boolean equations under study, the logical formulas of Zhegalkin polynomials are completely or partially divided into some linear factors. As a result, logical formulas are reduced to the disjunction of complex elementary conjunctions, consisting of the product of individual arguments, linear polynomials or their negations, on the basis of which a system of nonlinear Boolean equations is obtained. Some problems of minimizing special disjunctive normal forms obtained from the Zhegalkin polynomial above the second degree of special classes are considered.

Anahtar Kelimeler:

Zhegalkin polynomial, linear Boolean functions, homogeneous-unit matrices, polynomial length, disjunctive normal forms

PDF

___

[1] Kabulov, A., Baizhumanov, A., Saymanov, I., Berdimurodov, M. "E_ective methods for solving systems of nonlinear equations of the algebra of logic based on disjunctions of complex conjunctions". 2022 International Conference of Science and Information Technology in Smart Administration, ICSINTESA 2022, 2022, pp. 95_99
[2] Kabulov, A., Baizhumanov, A., Saymanov, I., Berdimurodov, M. "Algorithms for Minimizing Disjunctions of Complex Conjunctions Based on First-Order Neighborhood Information for Solving Systems of Boolean Equations". 2022 International Conference of Science and Information Technology in Smart Administration, ICSINTESA 2022, 2022, pp. 100_104
[3] E. Navruzov and A. Kabulov, "Detection and analysis types of DDoS attack,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-7, doi: 10.1109/IEMTRONICS55184.2022.9795729.
[4] A. Kabulov, I. Saymanov, I. Yarashov and F. Muxammadiev, "Algorithmic method of security of the Internet of Things based on steganographic coding,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-5, doi: 10.1109/IEMTRONICS52119.2021.9422588.
[5] A. Kabulov, I. Normatov, E. Urunbaev and F. Muhammadiev, "Invariant Continuation of Discrete Multi-Valued Functions and Their Implementation,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-6, doi: 10.1109/IEMTRONICS52119.2021.9422486.
[6] A. Kabulov, I. Normatov, A.Seytov and A.Kudaybergenov, "Optimal Management of Water Resources in Large Main Canals with Cascade Pumping Stations,"2020 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Vancouver, BC, Canada, 2020, pp. 1-4, doi: 10.1109/IEMTRONICS51293.2020.9216402.
[7] Kabulov, A.V., Normatov, I.H. (2019). About problems of decoding and searching for the maximum upper zero of discrete monotone functions. Journal of Physics: Conference Series, 1260(10), 102006. doi:10.1088/1742-6596/1260/10/102006
[8] Kabulov, A.V., Normatov, I.H. Ashurov A.O. (2019). Computational methods of minimization of multiple functions. Journal of Physics: Conference Series, 1260(10), 10200. doi:10.1088/1742-6596/1260/10/102007
[9] Yablonskii S.V. Vvedenie v diskretnuyumatematiku: Ucheb. posobiedlyavuzov. -2e izd., pererab. idop. -M.:Nauka, Glavnayaredaksiya_ziko-matematicheskoy literature, -384 s.
[10] Djukova, E.V., Zhuravlev, Y.I. Monotone Dualization Problem and Its Generalizations: Asymptotic Estimates of the Number of Solutions. Comput. Math. and Math. Phys. 58, 2064_2077 (2018). https://doi.org/10.1134/S0965542518120102
[11] Leont'ev, V.K. Symmetric boolean polynomials. Comput. Math. and Math. Phys. 50, 1447_1458 (2010). https://doi.org/10.1134/S0965542510080142
[12] Nisan, N. and Szegedy, M. (1991). On the Degree of Boolean Functions as Real Polynomials, in preparation.
[13] RamamohanPaturi. 1992. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing (STOC '92). Association for Computing Machinery, New York, NY, USA, 468_474. https://doi.org/10.1145/129712.129758.
[14] Gu J., Purdom P., Franco J., Wah B.W. Algorithms for the satis_ability (SAT) problem:A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997.Vol. 35. P. 19_152.
[15] Goldberg E., Novikov Y. BerkMin: A Fast and Robust SAT Solver // Automation andTest in Europe (DATE). 2002. P.142_149.