Classes of universal decision elements using negative substitutions.
J.C. Muzio · Notre Dame Journal of Formal Logic · 1979
Introduction In 1953 Sobociήski [6] showed that there exists a function of four arguments in two-valued logic which may define any binary function by substitution of the variables p,q or constants 0, 1 into its arguments, this function only being used once in any definition.Such a function is said to generate all the binary functions and is termed a universal decision element.Sobociήski also proved that no three-place function can correspond to such a universal decision element.In [3] and [4] the present author considered three-place functions and gave a complete classification of them according to which subsets of the binary functions they generate.In the present paper* we are also concerned with three place functions, but in addition to allowing the substitution of the variables and the constants we also admit the substitution of the negated variables.Under these conditions it is possible for a three-place function to generate all the binary functions, and for the remainder of this paper we term such a function a universal decision element.For our purpose it is sufficient to divide the three-place functions into 14 distinct classes, the behaviour of the elements of a class being essentially similar.These classes have been discussed in more general terms by several authors (see Harrison [2], p. 148 et.seq.and Ninomaya [5]).We investigate which of the classes consist of functions which are universal decision elements in both the general case and in a restricted case.In section 4 we make the restriction that each variable may be substituted only once (either in true or negated form).It transpires that this implies that exactly one class of functions consists of universal decision elements.The general case, of not restricting the substitutions, is considered in section 5 and two more classes of functions correspond to universal decision elements.In both cases we describe exactly which binary