Reduting the rank of the conjunction, representing the root of the logical equation

In this paper the modification of Zakrevskij algorithm of finding a root of logical equation has been suggested. A root of logic equation D = 0 is representing by product r _i. The purpose of this modification is to find a product that has possibly smaller rank. As a rule finding the root of logic equation is reduced to tree traversal. Here, we deal with D = 0, where D is SoP (Sum of Products), that is represented as a set of ternary vectors. The ternary vector is a partially specified bit vector, i.e. elements (variables xi) of it can contain values {1,0, x}. The values ' 1' and '0' are determined values. The value x is don't care symbol. Note this set as M. The root of the equation is formed with the decomposition tree, by variables x _i. In general, from the vertex of the tree marked by variable x, run three branches labeled with the values {0,1,x}. Each branch is associated with a corresponding subset of ternary vectors obtained by dividing a set M with respect to variable x _i into three subsets M (x _l = 1), M (x _l =0), M (x _l = x). The variable x _i from the set with maximum power is included into to product ri with the opposite sign of inversion. The decomposition tree is changed so that from the vertex labeled xi, run two branches, one of which is labeled with a determined value, but another is labeled with value x. If the next step of decomposition fails that is the product ri cannot be derived as the root of the equation, then we return to the closest vertex of decomposition tree for which both sets M (x _l =1), M°(x _l =0) is not empty. The root of the equation is found when the set corresponding to branch labeled x is empty. In this paper variable selection heuristics have been proposed. The experimental results confirm advantages of this approach. The sufficient conditions for the existence of the root of logic equation D = 0 have been formulated.

Keywords

Authors

References