Open Access
Research Article
Novel Boolean logic manipulation : A symbolic computation and camouflaged graph construction
*Gete UmbreyCorresponding authorgete.umbrey@rgu.ac.inDepartment of Mathematics Jawaharlal Nehru College PasighatEast Siang, Arunachal Pradesh, 791102, IndiaView full profile → , Bhaba Kumar Sarmabks@iitg.ac.inDepartment of Mathematics Indian Institute of Technology GuwahatiGuwahati, Assam, 781039, IndiaView full profile → , Bhuban Chandra Deuribhuban.math@gmail.comDepartment of Mathematics Jawaharlal Nehru College, Pasighat PasighatEast Siang, Arunachal Pradesh, 791102, IndiaView full profile → , Alfonso Bustamanteathal.zigma@gmail.comDepartment of Mathematics University of Chile SantiagoSantiago, 8320000, ChileView full profile → , Botem Moyongbotemmoyong.bm@gmail.comDepartment of Mathematics Dara Natung Government CollegeItanagar, Arunachal Pradesh, 791111, IndiaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Oct 2025
- Published Online:
- 01 Apr 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-2220
- Pages:
- 1567–1589
Abstract
This article introduces a systematic, symbolic, and pure algebraic technique called the “Extraction and Combination Method” for minimizing Boolean expressions. This method simplifies Boolean expressions through a sequence of algebraic manipulations that methodically extract factors and combine terms to reduce the complexity of redundant literal terms and operations. The algorithmic process involves the breakdown of the complex Boolean expression into distinct components, applying the natural and fundamental laws of Boolean algebra. Systematic ordering and generalization of Boolean operations/subexpressions ensure that we can invariably reach termination and achieve a unique minimized form for any given Boolean expression. The set of processes of decomposition of the expression into subexpressions, parallel minimization, and recombination is repeated iteratively until we get an optimized form. The minimization process avoids exhaustive truth table generation. We proposed to seamlessly transform the algebraic form used in our framework into a Boolean graph-a simple undirected graph in the graph-theoretic sense that allows Boolean expressions to be studied and manipulated through graph operations such as union and intersection, and establishes a natural bridge between algebraic logic and classical graph theory. The method enables tautology detection, construction of Boolean graph and camouflaged graph, identification and removal of auxiliary vertices and auxiliary subgraphs, and derivation of simplified Boolean graphs representing minimal expressions.
Keywords
Subject Classifications
05C2506E3094C1068Q25
References
[1] V. D. Agrawal, ELEC 2200-002 Digital Logic Circuits – Logic Minimization (Chapter 3), Lecture Slides, Auburn University (2014). [2] S. B. Akers, “Binary decision diagrams,” IEEE Transactions on Computers, vol. C-27, no. 6, pp. 509–516 (1978). [3] E. Alharbi, “Truth graph: A novel method for minimizing Boolean algebra expressions by using graphs,” in Diagrammatic Representation and Inference, Lecture Notes in Computer Science, vol. 12169, A. V. Pietarinen et al., Eds. Springer, pp. 8–36 (2020). [4] A. Blake, Canonical Expressions in Boolean Algebra. Chicago, USA: University of Chicago Press (1937). [5] R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni-Vincentelli, “Logic minimization algorithms for VLSI synthesis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 3, no. 1, pp. 2–13 (1984). [6] R. E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Transactions on Computers, vol. C-35, no. 8, pp. 677–691 (1986). [7] A. Bustamante, G. Umbrey, B. Moyong, and B. K. Sarma, “A Zykov algebra approach to clique propagation: Classifying clique complexes in graphs,” Discrete Mathematics, Algorithms and Applications, vol. 17, no. 6, pp. 1–32 (2025). [8] S. H. N. Cheng and R. de Wolf, “The subsumption theorem in inductive logic programming: Facts and fallacies,” in Proc. Int. Conf. on Inductive Logic Programming (ILP), Leuven, pp. 147–160 (1995). [9] A. B. Chowdhury, T. Benjamin, M. Romanelli, R. Karri, and S. Garg, “Retrieval-guided reinforcement learning for Boolean circuit minimization,” in Proc. Int. Conf. on Learning Representations (ICLR) (2024). [10] A. Church and J. B. Rosser, “Some properties of conversion,” Transactions of the American Mathematical Society, vol. 39, no. 3, pp. 472–482 (1936). [11] D. Das and S. Mandal, “An efficient algorithm for the minimization of large binary decision diagrams,” Computers & Mathematics with Applications, vol. 66, no. 5, pp. 779–789 (2013). [12] C. Eduardo and J. Levy, “General Boolean formula minimization with QBF solvers,” in Artificial Intelligence Research and Development. IOS Press, pp. 347–358 (2023). [13] W. I. Fletcher, An Engineering Approach to Digital Design. Englewood Cliffs, NJ, USA: Prentice Hall (1980). [14] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, USA: Freeman (1979). [15] A. Ghosh, “Multi-objective genetic algorithm for efficient FPGA implementation of reversible circuits,” Integration, the VLSI Journal, vol. 75, pp. 61–70 (2020). [16] M. Haghparast and S. Mohammadi, “An efficient quantum-inspired genetic algorithm for Boolean function minimization,” Computers & Electrical Engineering, vol. 59, pp. 1–14 (2017). [17] S. L. Harris and D. Harris, “Combinational logic design,” in Digital Design and Computer Architecture. Morgan Kaufmann, pp. 52–104 (2022). [18] J. P. Hayes, Introduction to Digital Logic Design. Boca Raton, FL, USA: CRC Press (2020). [19] M. Karnaugh, “The map method for synthesis of combinational logic circuits,” Transactions of the American Institute of Electrical Engineers, Part I, vol. 72, no. 5, pp. 593–599 (1953). [20] P. Kadam, “Financial fraud detection using jump-attentive graph neural networks,” in Proc. Int. Conf. on Machine Learning and Applications (ICMLA), IEEE, pp. 628–635 (2024). [21] A. A. Kadhim, “A Boolean approach to the study of system reliability,” AIP Conference Proceedings, vol. 2457, no. 1, Art. no. 020002 (2023). [22] C. Y. Lee, “Representation of switching circuits by binary-decision programs,” Bell System Technical Journal, vol. 38, pp. 985–999 (1959). [23] L. Ma, “Truth graph method: A handy method different from that of Lesniewski’s,” Studies in Logic, Grammar and Rhetoric, vol. 42, no. 55, pp. 101–115 (2015). [24] M. Manna and S. Roy, “A novel heuristic algorithm for efficient minimization of large Boolean functions,” Applied Intelligence, vol. 49, no. 7, pp. 2355–2373 (2019). [25] W. V. O. Quine, “Simplification of Boolean functions,” in Digital Computers: Advanced Coding Techniques (1952). [26] S. Rudeanu, Boolean Functions and Equations. Amsterdam, Netherlands: North-Holland (1974). [27] S. Rudeanu, “Algebraic methods versus map methods of solving Boolean equations,” International Journal of Computer Mathematics, vol. 80, no. 7, pp. 815–817 (2003). [28] A. M. Rushdi, “A comparison of algebraic and map methods for solving general Boolean equations,” Journal of Qassim University: Engineering and Computer Sciences, vol. 5, no. 2, pp. 147–173 (2012). [29] A. M. Rushdi, “Improved variable-entered Karnaugh-map procedures,” Computers & Electrical Engineering, vol. 13, no. 1, pp. 41–52 (1987). [30] B. K. Sarma, G. Umbrey, and M. K. Enduri, “The algebra of simple graphs and maximal cliques,” Mathematical Forum, vol. 33 (2025). [31] P. Sengupta, A. Tyagi, J. Hu, V. K. Rajan, H. Mostafa, and S. Majumdar, “MinBLoG: Minimization of Boolean logic functions using graph attention network,” in Proc. ACM/IEEE Int. Symp. on Machine Learning for CAD (MLCAD) (2024). [32] C. Senthilpari, K. Diwakar, K. Munusamy, and J. S. Francisca, “Layout parameter analysis in Shannon expansion theorem based on 32-bit adder circuit,” Engineering Science and Technology, an International Journal, vol. 20, no. 1, pp. 35–40 (2017). [33] A. S. Singh, “Minimization of Boolean function using K-map,” Electrically4U (2021). [34] G. Umbrey, B. K. Sarma, S. Rahman and A. Bustamante, “Boolean algebra and lattice of graphs with their applications in cryptography,” Discrete Mathematics, Algorithms and Applications, (in press) (2026). [35] V. M. E. Van Valkenburg, Logic and Computer Design Fundamentals. Pearson (2014). [36] Wolfram Research, “BooleanGraph,” Wolfram Language Documentation (2010).
Views: 198Downloads: 8Citations: 0
