Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ http://journals.uran...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
http://journals.uran.ua/tarp/a...
Article
License: CC BY
Data sources: UnpayWall
https://doi.org/10.15587/2312-...
Article . 2017 . Peer-reviewed
Data sources: Crossref
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method

Authors: Riznyk, Volodymyr; Solomko, Mykhailo;

Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method

Abstract

The simplification of the problem of Boolean function minimization by a combinatorial method is a new procedure for the algebra of logic – super-sticking of variables. This procedure is performed if there is a complete binary combinatorial system with repetition or an incomplete binary combinatorial system with repetition in the truth table structure. The procedure for reducing the total perfect disjunctive normal form (PDNF) of the logical function gives unity. And since the complete PDNF uniquely determines the complete binary combinatorial system with repetition and vice versa, this gives grounds to delete all the blocks of the complete binary combinatorial system from the truth table, whose structure allows to carry out the rules of super-sticking of variables. The efficiency of the algebraic operation of supers-sticking of variables greatly simplifies the algorithm for Boolean function minimization and allows manual minimization of functions with a number of variables up to 10. The complexity of the algorithm for finding the minimal function by a combinatorial method is O(n) and is linear for n<7. With an increase in the number of variables from n=6 to 8, the growth dynamics of the number of transformations is characterized by the law O(n 2 ), followed by the growth of O(f(n)) with the increase in the Boolean function capacity according to the polynomial law. The introduction of an algebraic operation of super-sticking of variables to the problem of Boolean function minimization is more advantageous in comparison with analogs in the following factors: – lower cost of development and implementation, since a significant proportion of functions are minimized by functions with a number of variables of no more than 16, and therefore, in general, the need for automation of the process of minimizing the function decreases; – increase in manual minimization of 4–10 bit functions, facilitates control and study of the algorithm for minimizing the logic function. The combinatorial method of Boolean functions minimization can find practical application in the design of electronic computer systems, because: – minimization of the DNF function is one of the multiextremal logic-combinatorial problems, the solution of which is, in particular, the combinatorial device of the block-diagram with repetition; – extends the capabilities of the algorithm for Boolean functions minimization for their application in information technology; – improves the algebraic method of Boolean function minimization due to the tabular organization of the method, the introduction of the shaped transformation apparatus and the rules of super-sticking of variables.

Keywords

булева функція; метод мінімізації; мінімізація логічної функції; блок-схема з повторенням; мінтерми; супер-склеювання змінних, булева функция; метод минимизации; минимизация логической функции; блок-схема с повторением; минтермы; супер-склеивание переменных, Boolean function; minimization method; minimization of a logical function; block-diagram with repetition; minterm; super-sticking of variables, UDC 519.718

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    3
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
3
Average
Average
Average
gold