A novel method to simplify Boolean functions

Authors

  • VIshnuvajjula Charan Prasad Dayalbagh Educational Institute

DOI:

https://doi.org/10.7494/automat.2018.22.2.29

Keywords:

Boolean functions, minimization, prime implicants, prime implicates

Abstract

Most methods for the determination of prime implicants of a Boolean function  depend on minterms of the function. Deviating from this philosophy, this paper presents a method which depends on maxterms ( minterms of the complement of the function) for this purpose. Normally maxterms are used to get prime implicates and not prime implicants.  It is shown that all prime implicants of a Boolean function can be obtained by expanding and simplifying any product of sums form of the function appropriately. No special form of product of sums is required. More generally prime implicants can be generated from any form of the function  by converting it into a POS using well known techniques.  The prime implicants of a product of Boolean functions can be obtained from the prime implicants of individual Boolean functions. This allows us to handle big functions by breaking them into product of smaller functions. A simple method is presented to obtain one minimal set of prime implicants from all prime implicants without using minterms.  Similar statements hold for prime implicates also . In particular all prime implicates can be obtained from any sum of products form.   Twelve variable examples are solved to illustrate the methods.

Author Biography

VIshnuvajjula Charan Prasad, Dayalbagh Educational Institute

Department of Electrical Engineering , Honorary Professor  ( Retired Professor of Electrical Engineering , Indian Institute of Technology , Delhi )

References

Marcus M.P, Swithching Circuits for Engineers , Prentice –Hall , Englewood Cliffs , New Jersey , 1969

Givone D.D, Digital Principles and Design ,International Edition , Mc Graw-Hill, New York , 2003

Z. Kohavi and N.K. Jha , Switching and Finite Automata Theory, Cambridge University Press, New York , 2010 , www.cambridge.org / 9780521857482

A . B. Marcovitz, Introduction to logic design, International Edition, Mc Graw –Hill, New York, 2002.

N.N.Biswas , “ Minimization of Boolean functions”, IEEE Trans. On Computers , Vol.C-20 / 8 , pp.925 – 929 , Aug.1971

Suresh Chander , “ Minimization of switching functions – A fast technique”, IEEE Trans. On Computers, Vol.C – 24 , pp.735 – 756 , 1975

Rhyne, Noe, McKinney, Pooch , “ A new technique for the fast minimization of switching functions”, IEEE Trans. On Computers, Vol. C – 26, pp. 757 – 764 , 1977

B.Gurunath, N.N.Biswas, “ An algorithm for multiple output minimization” , IEEE Trans. On CAD of Integrated circuits, Vol.8 , pp.1007 – 1013 , 1989.

S. Minato , Fast generation of prime irredundant covers from Binary decision Diagrams , IEICE Trans. Fundamentals , Vol. E 76 – A , No.6, pp.967-973 , June 1993.

S.P.Tomaszewski, I.U. Celix, G.E.Antoniou , “ WWW – Based Boolean function minimization” , Intl. J. Appl. Math. Comput. Sci. , Vol.13 / 1 , pp. 577 – 583 , 2003.

V. C. Prasad , Efficient minimization of Boolean functions , International Journal Of Electrical Engineering Education , Vol. 45 / 4 , pp.321-327, Oct. 2008

V.C.Prasad , “ Quality of minimal sets of prime implicants of Boolean functions” , Intl. Journal of Electronics and Telecommunications (Poland) , Vol. 63 / 2 , pp. 165 – 169 , 2017.

V.C.Prasad ,“ Generalized Karnaugh Map method for Boolean functions of many variables”, IETE Journal of Education (India) , Vol. 58 / 1 , pp.11 – 19 , 2017

Downloads

Published

2019-04-21

How to Cite

Prasad, V. C. (2019). A novel method to simplify Boolean functions. Automatyka/Automatics, 22(2), 29. https://doi.org/10.7494/automat.2018.22.2.29

Issue

Section

Articles