Please use this identifier to cite or link to this item:
http://hdl.handle.net/2381/34569
Title: | Functional-completeness criteria for finite domains. |
Authors: | Schofield, P. (Peter) |
Award date: | 1966 |
Presented at: | University of Leicester |
Abstract: | Necessary and sufficient conditions for the functional completeness of a set F of functions with variables and values ranging over N = {lcub}0,1,...,n{rcub}, where n ? 1, are investigated and in particular, completeness criteria for a single function are determined. Complete solutions are known in the special cases n = 1,2, and results about these special cases which are of use in formulating general theorems are discussed. Proceeding to the general case some preliminary criteria (which presuppose that certain 2-place functions are generated by F) for the functional completeness of F are derived. These results show that the set consisting of all 2-place functions is complete. In the special case n + 1 = p (a prime number) the functions of F are shown to have a special form, and this is used in some illustrations of complete subsets. The value sequence of a function satisfying the Stupecki conditions (that is, depending on at least 2 of its argument places, and taking all n + 1 values of N) is now examined, and some properties of such a function are found. These results are then used in demonstrating the completeness of a set F which generates all 1-place functions, together with a function satisfying the Stupecki conditions. Our main results give improved sufficient conditions for the completeness of F. In particular a set F is complete if it generates a triply transitive group of permutations of N and contains either (i) only a single function or (ii) at least one function satisfying the Stupecki conditions, the latter apart from certain exceptional cases. A detailed investigation shows that these occur only when n = 2 or when n + 1 is a power of 2 and all functions of F are linear in each variable, relative to some mapping of N as a vector space over Z2. Finally a different mapping of N into Z42 is considered, and it is shown that the functions of F can be given a unique representation relative to this mapping. This representation is then used to find some examples of complete subsets. |
Links: | http://hdl.handle.net/2381/34569 |
Level: | Doctoral |
Qualification: | Ph.D. |
Rights: | Copyright © the author. All rights reserved. |
Appears in Collections: | Theses, Dept. of Mathematics Leicester Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
U296355.pdf | 25.35 MB | Adobe PDF | View/Open |
Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.