Skip to content

extension of quine-mccluskey minimization of logical expressions from boolean to multivalued

License

Notifications You must be signed in to change notification settings

PalinkasAljoscha/Logic_Minimization

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Background

Boolean functions can written as an boolean expression like e.g. A and B or B and C and not A. Here the variables are boolean. Methods to minimize these expressions are Quine-McCluskey and Petrick's Method As expression become large the complexity of these algorithms growth rapidly, in fact one step of the method is equivalent to NP-hard set covering problem.

Also "A<3 and B>=1 or A=1 and C>=2" is a logical expression, but the variables are now multivalued and we need to define their range.

This algorithm

extends the Quine-McCluskey method to also minimize expression of multivalued logic as A<3 and B>=1 or A=1 and C>=2. To this end the multivalued variables are represented by several boolean variables and their interdependecies. When the minimization on these boolean cases are carried out, the interdependencies need to be handled. This happens in the creation of prime implicants. The reduction of prime implicants to minimal cover stays the same. A devide and conquer approach is used to improve runtime for reducing prime cover.

Apart from Quine-McClusky extension and implementation, Logicfun class has helper methods to read, write, random generate multivalued expressions.

About

extension of quine-mccluskey minimization of logical expressions from boolean to multivalued

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages