A system of linear logical equations is considered represented by
the expression Rx=u, where matrix R and vector u are given and vector
x is to be found (all Boolean). Sometimes it can have many roots, and
the regarded problem is to find a shortest one, with minimum number
of 1s. The problem has useful applications in the design of AND/EXOR
logic circuits implementing weakly specified Boolean functions -
defined on a relatively small number of input combinations. A
recursive stair-case algorithm is suggested for solving it, using a
modified tree searching technique and enabling to obtain
both exact and approximating solutions. When Zhegalkin polynomials
are used by that, matrix R is the conjunctive closure of the Boolean
matrix B consisting of vector-columns which represent argument values
on the definition area, and vector u represents the corresponding
values of the function; in case of more general Reed-Muller
polynomials componentwise inversions of some columns
of B can be added to R. The problem is generalized on multi-output
circuits: the matrix equation RX=U is regarded in this case, where
the sought- for matrix X should contain the minimum number of non-
zero rows. Practically efficient methods proposed for the latter
problem are based on the theory of linear vector spaces.
Inhalt:/ Content: Institut für Informatik
TU Bergakademie Freiberg
Gestaltung/ Layout: Webmaster
19. Februar 1997
