Minimal Sets of Distinct Literals for a Logically Passive Function
R.C. De Vries · Journal of the ACM · 1971
A method is presented for determining minimal sets of distinct literals for a logically passive function, i.e. one which can be implemented, using only AND and OR gates.The first step in the procedure is the determination of vacuous variables by an examination of the truth table.The resulting table is then expanded to include one column for each variable and the complement of each variable.Columns are examined to determine which ones can be deleted and yet leave the function logically passive.The procedure for deleting columns is considered in detail, together with the effects of deleting the columns.Certain columns can be deleted on the basis of information within the column, others on the basis of a comparison of columns.These criteria are then examined in the light of (1) the effect of column removal on the ability to remove other columns, and (2) the effect of column removal on the ability to obtain at least one minimal solution.The criteria are compared with the dominance relations which are used in solving for minimal solutions from prime implicant tables.Finally, a means of detecting certain absolutely minimal forms is presented.