A tutorial exposition of semi-tensor products of matrices with a stress on their representation of boolean functions

Abstract EN

This paper is a detailed tutorial exposition of a novel and highly-useful product of matrices called the semi-tensor product (STP).

This new product allows the multiplication of two matrices and that do not satisfy the conformity condition required in a conventional matrix product (CMP), namely, that the column dimension n of the first matrix be equal to the row dimension p of the second matrix B.

The STP inherits almost all of the properties of the CMP, and reduces to it when n = p.

The basic concepts, properties, manipulations of the STP are presented, and demonstrated via tutorial illustrative examples.

Applications of the STP include multi-linear and non-linear control problems, theoretical analysis of mathematical problems, and derivation of mathematical proofs.

We emphasize the STP use in the matrix expression of Boolean (Switching or logical) functions.

We achieve a better understanding of this use by translating the STP terminology to conventional or more familiar representations of Boolean functions, and by explicitly identifying the bases on which the matrix expressions of the Boolean function are constructed.

We compare the STP representation of Boolean functions with other well known representations such as the Variable-Entered Karnaugh Maps (VEKMs) and the Reduced Ordered Binary Decision Diagrams (ROBDDs).

We show that while these latter representations are complete multi-level ones, the STP representation is a single leaf-level representation.

In essence, the STP representation is a truth-table expression of both the function and its complement, and hence it involves unnecessary duplication.

The readability of the STP representation of a Boolean function is hindered by its implicit reverse ordering starting at 1 rather than at 0.

The STP representation is suitable for the larger class of pseudo-Boolean functions, and hence it is somewhat loose for the restricted class of Boolean functions.

For example, it uses the very general and costly operation of real addition to implement the OR operation of Boolean algebra.

Such an inefficient implementation cannot be tolerated when the intended applications are among the most intractable problems.

Despite the aforementioned negative aspects, the utility of the STP in a variety of applications and even in handling Boolean functions is undeniable.

In fact, the STP is computationally successful in handling medium-sized problems in areas ranging from Boolean synchronous networks to logic deduction.

The STP is an effective tool for mathematical proofs and derivations over the Boolean domain.

We demonstrate this point by using mathematical induction in a novel STP derivation of the Preparata Transformation which relates the truth-table representation of a two-valued Boolean function to its linear (Reed-Müller) one.