Partial universal decision elements.
J.C. Muzio · Notre Dame Journal of Formal Logic · 1974
Ί Introduction.Given any functor of 2-valued logic there is a corresponding unit of computing machinery which is capable of completely representing the behaviour of that functor.These units are called decision elements.The introduction of this term is due to Goodell [3].Sobociήski [12] has shown that there exists a functor of four arguments which may define any of the functors of one or two arguments by the substitution of variables P, Q, etc., or constants 0, 1 in its arguments, this functor only being used once in any definition.The latter clause is important since it is well known that any Sheffer function can be used to define any functor, but there is no restriction on the number of occurrences of the function.Such a functor as that defined by Sobociήski is said to "generate" all the functors of two arguments.Defining such a functor corresponds to constructing a decision element which, by suitable setting of the inputs, can represent any of the 2-place functors.Decision elements of this type are called universal decision elements.Following Sobociήski's work, Rose [9] gives several functors of four arguments which correspond to universal decision elements and suggests a method to determine all such functors.Pugmire and Rose [8] suggest a very different approach to the same problem and Foxley [2] combined the advantages of both methods to actually determine the set of all fourvariable formulae which correspond to universal decision elements.More recently Rose [11] has investigated three-valued universal decision elements.In the present paper we are concerned with generating functors which will generate some particular subset of the set of functors of two arguments, but not the whole set.For this purpose we shall be considering three-place functors Φ(X, Y, Z).Such a functor cannot correspond to a universal decision element since it can easily be shown that it cannot generate a sufficient number of binary functors (see Sobociήski [12]).The particular subsets which will be considered are defined in section 3 but basically it is shown that: