Browse
- No file added yet -

# Functional-completeness criteria for finite domains.

thesis
posted on 2015-11-19, 08:55 authored by P. (Peter) Schofield
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.

1966-01-01

Mathematics

## Awarding institution

University of Leicester

• Doctoral

• PhD

en

## Categories

No categories selected

## Exports

RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC
figshare. credit for all your research.