• Zaid Al-Wardi Electrical Engineering Department, College of Engineering, Mustansiriyah University, Baghdad, Iraq
  • Osama Al-Wardi Brandenburg University of Technology, Cottbus-Senftenberg, Germany



Boolean Algebra, Sum of products, Two-level Boolean representation, Logic Circuit Synthesis


The problem of computing the set of prime implicants to represent a Boolean function is a classical problem that is still considered a running problem for research because all known approaches have limitations. The article reviews existing methods for computing prime implicants and highlights their limitations, particularly for multi-output functions and limited scalability due to the growth in memory required to complete the computation. Then it proposes a recursive ternary-based minimization algorithm to compute the prime implicants of multi-output Boolean functions. The algorithm is based on the concept of Programmable Logic Array (PLA) tables, which provide a structured and efficient representation of Boolean functions. The algorithm takes advantage of the ternary logic system to efficiently compute the prime implicants while maintaining scalability for large and complex functions, which has significant implications for digital circuit design and optimization.


Prasad, V. C. (2018). Novel method to simplify Boolean functions. Automatyka/Automatics, 22(2), 29.

Rai, S., Neto, W. L., Miyasaka, Y., Zhang, X., Yu, M., Yi, Q., Fujita, M., Manske, G. B., Pontes, M. F., da Rosa, L. S., de Aguiar, M. S., Butzen, P. F., Chien, P.-C., Huang, Y.-S., Wang, H.-R., Jiang, J.-H. R., Gu, J., Zhao, Z., Jiang, Z., … Chatterjee, S. (2021). Logic Synthesis Meets Machine Learning: Trading Exactness for Generalization. 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE).

Fujita, M. (2019). Basic and Advanced Researches in Logic Synthesis and their Industrial Contributions. Proceedings of the 2019 International Symposium on Physical Design.

Salhi, Y. (2018). Approaches for Enumerating All the Essential Prime Implicants. Lecture Notes in Computer Science, 228–239.

Mados, B., Bilanova, Z., Chovancova, E., and Adam, N. (2019). Field Programmable Gate Array Hardware Accelerator of Prime Implicants Generation for Single-Output Boolean Functions Minimization. 2019 17th International Conference on Emerging ELearning Technologies and Applications (ICETA).

Kubica, M., Opara, A., and Kania, D. (2020). Methods for Representing Boolean Functions—Basic Definitions. Technology Mapping for LUT-Based FPGA, 15–24.

Quine, W. V. (1952). The Problem of Simplifying Truth Functions. The American Mathematical Monthly, 59(8), 521–531.

McCluskey, E. J. (1956). Minimization of Boolean Functions*. Bell System Technical Journal, 35(6), 1417–1444.

Petrick, S. R., and Sethares, G. C. (1968). On the Determination of Complete Sets of Logical Functions. IEEE Transactions on Computers, C-17(3), 273–273.

Seda, P., Seda, M., Hosek, J., Dvorak, J., and Sedova, J. (2019). The Improvement of Quine-McCluskey Method Using Set Covering Problem for Safety Systems. 2019 4th International Conference on Intelligent Green Building and Smart Grid (IGBSG).

Joshi, M., Sunori, S. K., Tewari, N., Maurya, S., Joshi, M., and Juneja, P. K. (2021). Formulation of C++ program for Quine–McCluskey Method of Boolean Function Minimization. Machine Learning, Advances in Computing, Renewable Energy and Communication, 341–346.

Vu, H.-G., Bui, N.-D., Nguyen, A.-T., and ThanhBangLe. (2021). Performance Evaluation of Quine-McCluskey Method on Multi-core CPU. 2021 8th NAFOSTED Conference on Information and Computer Science (NICS).

Balasubramanian, P., Bernasconi, A., Ciriani, V., and Villa, T. (2021). A Boolean Heuristic for Disjoint SOP Synthesis. 2021 24th Euromicro Conference on Digital System Design (DSD).

Su, S., Zou, C., Kong, W., Han, J., and Qian, W. (2020). A Novel Heuristic Search Method for Two-Level Approximate Logic Synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39(3), 654–669.

Miao, J., Gerstlauer, A., & Orshansky, M. (2013). Approximate logic synthesis under general error magnitude and frequency constraints. 2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD).

Ammes, G., Neto, W. L., Butzen, P., Gaillardon, P.-E., & Ribas, R. P. (2022). A Two-Level Approximate Logic Synthesis Combining Cube Insertion and Removal. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(11), 5126–5130.

Ammes, G., Butzen, P. F., Reis, A. I., & Ribas, R. (2022). Two-Level and Multilevel Approximate Logic Synthesis. Journal of Integrated Circuits and Systems, 17(3), 1–14.

Kanakia, H., Nazemi, M., Fayyazi, A., & Pedram, M. (2021). ESPRESSO-GPU: Blazingly Fast Two-Level Logic Minimization. 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE).

Potvin, N., Bersini, H., and Milojevic, D. (2022). Espresso to the rescue of genetic programming facing exponential complexity. Proceedings of the Genetic and Evolutionary Computation Conference Companion.

Duşa, A. (2008). A mathematical approach to the boolean minimization problem. Quality & Quantity, 44(1), 99–113.

Rudell, R. L., and Sangiovanni-Vincentelli, A. (1987). Multiple-Valued Minimization for PLA Optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(5), 727–750.

Fiser, P., Rucky, P., and Vanova, I. (2008). Fast Boolean Minimizer for Completely Specified Functions. 2008 11th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems.

Lee, S.-Y., Kim, S., and Kang, S. (2019). Ternary Logic Synthesis with Modified Quine-McCluskey Algorithm. 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL).

Stanković, R. S., Astola, J. T., and Moraga, C. (2012). Representation of Multiple-Valued Logic Functions. Synthesis Lectures on Digital Circuits & Systems, Morgan & Claypool Publishers. ISBN: 978-3-031-79852-8

Al-Wardi, Z. (2021). Radix-p Multiple Valued Logic Function Simplification using Higher Radix Representation. Journal of Physics: Conference Series, 1804(1), 012016.




Submission Dates

Received 16/3/2023

Accepted 24/4/2023

Published 1/5/2023

How to Cite

Al-Wardi, Z., & Al-Wardi, O. (2023). RECURSIVE TERNARY-BASED ALGORITHM FOR COMPUTING PRIME IMPLICANTS OF MULTI-OUTPUT BOOLEAN FUNCTIONS. Journal of Engineering and Sustainable Development, 27(3), 308–316.