The efficiency of real systems of logical programming is to a great extent limited by the necessity to solve hard combinatorial problems typical for logical inference and design. Obviously, it is practically impossible to overcome the difficulties of their solving only by increasing the speed of computers and by paralleling computations. Far more perspective is the progress in theory, which takes into account the detailed specific of the regarded problems and enables sometimes to change the space of combinatorial search for a smaller one. This is illustrated by the following example. It is known, that AND/EXOR-circuits have some advantages over traditional AND/OR-circuits: they are more testable and more compact in case of symmetrical Boolean functions used for circuit implementation of arithmetic operations. Their optimal synthesis can be reduced to economical representation of Boolean functions by polynomials of some type (Zhegalkin, Reed-Muller with fixed polarity, or general type) having minimum number of conjunctive terms.
The problem is to minimize the number of terms in polynomials (of the chosen type) implementing Boolean functions under consideration. This problem is more difficult in case of incompletely specified Boolean functions, and becomes far more hard when not one but a system of such functions has to be realized. Practically efficient methods to solve this problem were proposed by the author before for one Boolean function and for a system of m Boolean functions of n variables which are specified on s input combinations.
In the first case only those s inputs were considered where the function is defined and the problem was reduced to looking for an optimal solution of the corresponding system of s linear logical equations [1]. The other method, intended for the latter case, is based on the theory of linear vector spaces and is especially efficient in application to weakly specified Boolean functions, with small s [2].
It was found out later that with increasing m and n there arises the possibility of existing of "superoptimal" solutions, as were called polynomial representations where the number of conjunctive terms coincides with the rank of the considered system of Boolean functions. An algorithm for finding "superoptimal" solutions is proposed in this paper. It works very fast when such a solution does exist. Let B and U be some sets of Boolean vector-columns of values of arguments and functions, accordingly, representing some regarded system F on the definition area, r(U) - the rank of U, i.e. the maximal number of linearly independent elements in U, and Sp(U) - the vector space over U. And let cl(B) be the conjunctive closure of B, comprised of all different results of multiplace componentwise conjunctions of vectors from B. It is clear that any solution of the considered problem should be presented by some irredundant polynomials implementing F, and it was shown in [1] that in case of Zhegalkin polynomials they consist only of elements from cl(B), and that any implementing irredundant polynomial of general type consists of elements from cl(B+), where B+ is the union of B and the set of componentwise negations of all vectors from B.
Consider below the set R of Boolean vector-columns which equals either cl(B) or cl(B+), depending on the type of polynomials chosen for the implementation. Let C be an arbitrary subset of R. C is a solution if every vector from U equals the mod-2-sum of some vectors from C. It is known that for any system F of Boolean functions the number |C| of conjunctive terms in C can not be less than r(U), but is greater as a rule. That is why C is called superoptimal (SSO) if |C|=r(U).
The suggested algorithm is based on the following reasoning: Sp(C)=Sp(U) in case when C is a SSO, hence each element of C equals the mod-2-sum of several elements of an arbitrary basis of U, hence when a SSO exists, all r(U) its elements can be found by testing elements from R one by one, solving each time a corresponding system of linear logic equations (by the Gaussian method of variables exclusion).
The algorithm is superfast indeed, that is testified by the following results of experiments conducted on PC AT 386 (programming language LYaPAS) and covering the region of parameters n and m up to several hundreds of variables and functions. A succession of vector sets B and U was randomly generated and subjected to the algorithm which found superoptimal solutions in Zhegalkin representation. The following parameters of the solutions were measured: k is the number of terms in a solution, w - the sum of their weights, and t - the time of calculation in seconds.
n=m=s 50 100 150 200 250 300 350 400 k 50 100 149 199 249 299 350 399 w 50 99 257 298 357 442 349 613 t 1.25 11 24 59 107 180 135 423