Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T00:59:02.821Z Has data issue: false hasContentIssue false
  • English
  • Français

Complete subsets of mappings over a finite domain

Published online by Cambridge University Press:  24 October 2008

P. Schofield
P. Schofield
Affiliation:
University of Glasgow
Get access Rights & Permissions [Opens in a new window]

Extract

Improved sufficient conditions are developed for the functional completeness of a set F of functions with variables and values ranging over N = {1, 2, …, n}, where n ≥ 3. In particular, 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 Slupecki conditions, the latter apart from certain exceptional cases. These are shown by a detailed investigation to occur only when n = 3 or when n is a power of 2 and all functions of F are linear in each variable, relative to some representation of N as a vector space over Z2.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 62 , Issue 4 , October 1966 , pp. 597 - 611
Copyright
Copyright © Cambridge Philosophical Society 1966

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Burnside, W.The theory of groups (Cambridge University Press, 1911).Google Scholar
(2)Davies, Roy O.Two theorems on essential variables. J. London Math. Soc. 41 (1966).Google Scholar
(3)Hall, M.The theory of groups (Macmillan, 1959).Google Scholar
(4)Jordan, C.Recherehes sur les substitutions. J. Math. Pures Appl. 17 (1872), 351–367.Google Scholar
(5)Post, E.The two-valued iterative systems of mathematical logic (Princeton University Press, 1941).Google Scholar
(6)Salomaa, A.On the composition of functions of several variables ranging over a finite set. Ann. Univ. Turkuensis, Ser. A. I. 41 (1960).Google Scholar
(7)Salomaa, A.Some completeness criteria for sets of functions over a finite domain. I. Ann. Univ. Turkuensis Ser. A.I. 53 (1962).Google Scholar
(8)Salomaa, A.Some completeness criteria for sets of functions over a finite domain. II. Ann. Univ. Turkuensis, Ser. A. I. 63 (1963).Google Scholar
(9)Salomaa, A.On essential variables of functions, especially in the algebra of logic. Ann. Acad. Sci. Fenn. Ser. A.I. Math. 339 (1963), 3–11.Google Scholar
(10)Schofield, P.On a correspondence between many-valued and two-valued logics. Zeit. f. math. logik 10 (1964), 265–274.CrossRefGoogle Scholar
(11)Wheeler, R. F.Complete connectives for the 3-valued propositional calculus. Proc. London Math. Soc. forthcoming.Google Scholar
(12)Yablonskii, S. V.Functional constructions in k-valued logic. Trudy Mat. Inst. Steklov 51 (1958), 5–142 (in Russian).Google Scholar