Generating Threshold Functions of up to Eight Variables Using Computer

Kasiyah Machmudin
University of Indonesia



Threshold functions are restricted class of Boolean functions that model neurons. In an artificial neural network a neuron represents a processing unit. Threshold functions also attracted some attention because they realize threshold gates, which have higher processing power compared to the conventional gates. It has been proven that a necessary and sufficient condition for a Boolean function of less than eight variables be a threshold function is being completely monotonic. This property and other theorems shown in this paper are used to develop an algorithm and a computer program that generates threshold functions of up to eight variables. In order to express threshold functions and their useful properties in a programming language, such as Pascal, a new way of representing threshold functions based on the minterm expansion form via vertex maps is introduced. This representation, which is strongly related to the geometric aspects of threshold functions, seems very fruitful. Some suggestions for future research topics that is related to enhancement of the new generating algorithms and potential uses of vertex maps are presented in this paper. There are three students doing their research in this field. Although the algorithm developed works for threshold functions with eight variables the program can generate only those of up to five variables because of some limitations. The enumeration of those functions and their non-isomorphic vertex maps are given in this paper. Key words threshold function, completely monotonic, minterm expansion form, vertex map.

© ATCM, Inc. 2001.