Jon T. Butler

Department of Electrical and Computer Engineering

Naval Postgraduate School

Monterey, CA 93943-5121

Room will be announced. Thursday, 18 November 1999, 11:00 - 12:00

An irredundant sum-of-products (ISOP) expression has the property that if any product (AND) term is deleted, the function is changed. Among all ISOP's are minimal sum-of-products (MSOP) expressions. Much research has been devoted to efficiently determining the MSOP. Also, among ISOP's are worst sum-of-products (WSOP) expressions. Little research has been done on this topic until recently, when certain algorithms have been shown to produce such expressions. For example, the Minato-Morreale algorithm produces the WSOP for whole classes of functions. This surprising result has shown the need for understanding how many more products are in WSOP's than in MSOP's. We show a class of functions for which the ratio of number of products in WSOP's to the number of products in MSOP's increases arbitrarily as n, the number of variables increases. These functions also have the characteristic that the Minato-Morreale algorithm produces WSOP's. We also explore the distribution of ISOP's to the number of product terms giving insight into the difficulty of minimizing functions.


Jon T. Butler is a Professor of Electrical and Computer Engineering at the Naval Postgraduate School, Monterey, CA. He received the B.E.E. and M.Engr. degrees from Rensselaer Polytechnic Institute in 1966 and 1967, respectively., and the Ph.D. degree from Ohio State University in 1973. He was an editor of the IEEE Transactions on Computers, and Editor-in-Chief of Computer and Editor-in-Chief of Computer Society Press. He was the first chairman of the Computer Society's Technical Committee on Multiple-Valued Logic and is a Fellow of the IEEE. His research interests are multiple-valued logic and general logic design.