METHODS FOR SOLVING SYSTEMS OF BOOLEAN EQUATIONS

Öz

To minimize logical formulas when solving systems of Boolean equations, a method is proposed for transforming formulas from the Zhegalkin polynomial into a disjunctive normal form. An algorithm for simplifying logical functions in the class of disjunctive normal forms is given. A method for multiplying logical expressions in the class of disjunctive normal forms is proposed. As a result, the logical formulas are reduced to the product of the formulations of the Boolean equations of the system, from which the solutions of the system of Boolean equations are obtained

Anahtar Kelimeler

• Zhegalkin polynomial
• linear Boolean functions
• polynomial length
• disjunctive normal forms
• first-order neighborhood
• metric characteristic.

Kaynakça

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. Glavnayaredaksiyafiziko-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 Nisan, N. and Szegedy, M. (1991). On the Degree of Boolean Functions as Real Polynomials, in preparation.
12. 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
13. Gu J., Purdom P., Franco J., Wah B.W. Algorithms for the satisfiability (SAT) problem:A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997.Vol. 35. P. 19–152.
14. Goldberg E., Novikov Y. BerkMin: A Fast and Robust SAT Solver // Automation andTest in Europe (DATE). 2002. P. 142–149.