Functional Completeness of Multi-valued Logical
Functions under Uniform Compositions
AkihiroNOZAKI
（Received August 31，1978） Abstract Here considered is the problem of functional completeness of multi−valued logical functions under a certain restricted composition． We define the notion of＊・completeness of a set of functions， which represents the universality of a set of gate−type elements of digital circuits each of which has a common delay． We have established a decidable criterion for a set of multi−valued logical functions to be＊−complete． We gave a representation theorem of maximal＊’incomplete sets， and listed up all maxima1＊・incomplete sets of logical functions and those of ternary logical functions． As S． V． Yablonski has conjectured， the number of maxima1＊・incomplete sets is shown to be finite． 1． Introduction Aset of logical functions is often said to be complete iff it can generate the whole set of logical functions． For instance， the following sets are known to be complete： Ho＝｛OR， NOT｝， H，＝｛NAND｝where
OR （x，の＝Max｛x， y｝， NOT（x）＝1−xand
NAND（x，の＝1−xy． The notion of completeness is considered also for aset of functions defined over a finite set X， and has been studied extensively by many researchers （see the survey of I． Rosenberg ［6］）． In many papers， by the way， the following operations are allowed to generate new functions from given ones． （1） Replacement of variables：for instance， the function． NOT can be generated immediately from NAND in the following manner． NOT（x）＝NAND（x， x）． （2） Composition of functions：for instance， the function NAND can be obtained from OR and NOT in the following manner． NAND＠，の＝OR（NOT（の， NOT（の）． In genera1， a function h can be composed from a functionゾwith p variables and functions gi with s（りvariables，1≦i≦P， in the following manner． h（X，，＿，XN）＝∫（91＠、，＿， X、ω），92＠、（1）．1，＿， x、（、）．、｛，））・…・9，（・…XN））・ where」V denotes the sum of all s（り’s． It should be noted that every argument of function f is substituted by a function。 To phasize this point， we shall call hereafter operation uniform composition． （3） Mixed operation：for instance， let us sider a logical function f defined as follows． f（x，の＝Max栖1−y｝．This functionゾcan be constructed from
and NOT in the following way． f（x，の＝NAND（NOT＠），の． In this case， the first argument of NAND is stituted by a function， while the second to be a variable． In some apPlications， however， rations may not be allowed． When athe
em− this con・NAND
sub−remalns
all of these ope・ や ひ composltlon of functions represents an、interconnection of switch・ ing elements， each of which evaluates a logical function in a common and definite delay， a mixed■
December 1978
Report of the Faculty of Engineering， Yamanashi UniversityNo．29
operation may violate the synchronization of sig・ nals． In 1956， J． von Neumann has already dis・ cussed the effect of delays． One of his results can be stated in our terminology as follows． The function NANI）can not generate the whole set of logical functions， if we are allowed to use only replacements of variables and uniform com・ ■posltlons． Therefore it will be of interest to consider the completeness without mixed operations． Let us denote by、Ωthe set of all functions de． fined over an arbitrary finite base set X． A subset Fof、2 is said to be＊・complete iff it can generate all functions in J2 by replacements of variables and uniform compositions． In this paper， we sha11 give conditions for a set」F of functions to be ＊・ complete， together with some results on maximal ＊・incomplete sets． In particular， we shall resolve positively the following conjecture suggested by S．V． Yablonski［11］：for any finite set X， there exist only a finite number of maxima1＊−incomplete sets of functions defined over X． 2． Basic Concepts Let X be a finite set containing exactly k ele・ ments We shall assume for simplicity that X＝｛0，1，＿，k−1｝
and
， le≧2． We denote by 9（k）（or simply 9）the set of all functions with arbitrary numbers of variables de・ fined over X． De血nition 2．1 Let F and G be subsets of 9． We denote by F（（×））Gthe set of all functions h， each of which can be defined by a function fin F and functions gl，＿， gp in G in such a way as follow・ ing： h（Xl，＿， X。）＝＝ f（9、＠、（1，1｝，＿， Xt（1，、（、｝）），．．．， …・9。（x、｛。，1）・…・Xe・。，、・。）））・ where n is an arbitrary positive integer， p is the number of variables of f and s（i）denotes that of gi， and t（i，ノ）’s are arbitrary integers between l and n． In other words， a function h is in F⑧G iff it can be obtained by composing皿iformly a function∫in．F and functions 9τ’s in G， and then replacing variables arbitrarily， 1・emma 2．1 F⑧（G⑧11）＝（F⑧G）⑧H The proof is immediate by definition． De血nition 2．2 Let F be a subset of 2． We denote： F（1）＝F⑧｛1｝， F（n）＝F（・−1）⑧．F（1）， where the symbol∬stands for the identity map・ ping：1（x）＝x． F＊＝UF（・）， n＝1 F＝（Fu｛1｝）＊． Asubset F of J2（〃）is said to be＊−complete iff F＊＝9（le）． It is said to be complete iff F＝9（le）． By definition， a set F of functions is complete if it is＊−complete． The converse is not always true：the set｛NAND｝is complete in、Ω（2）， al− though it is not＊−complete．Lemma 2．2 （1）F⊆．F＊⊆F
（2） If a set F contains the identity I， then F＊＝F． The proof is immediate by de丘nition． 3． ＊−Completeness Criterions Let 9，（ゐ）be the whole set of one−variable map・ pings de丘ned in the base set X． We denote byg。ゾthe left composite of mappingsゾand g in
9，（le）：g。ア⑰）＝g（ア＠））． The set 9，（〃）forms a semigroup with respect to this product． 1）e血nition 3．1 Let S be a subset of 2，（〃）． We denote： F（S）＝｛∫∈・91（｛ゾ｝⑧S）∩9，（le）⊆S｝． In other words， a functionプwithヵvariables is in F（s）iff for any mapPings g1・…・gP in 8， thecomposed mapPing
h（x）＝ア（91ω・…・9。（x）） is always in S． The set F（S）contains always the identity． A set F of functions is contained in F（S） iff （F⑧S）∩Ω1⊆S． Lemma 3．1 （1）F（S）＝F（S） （2） If a proper subset S of 、Ω1 con− tains the identity， then F（S）is not complete． Proof（1） （F（S）（n）⑧S）∩9，＝（F（s）⑧（＿⑧（F（s）⑧（F（s）⑧s）∩9正） ∩9，）＿∩9，）∩9，⊆S．
Hence
F（s）（n）⊆F（s）． Since the set F（S） contains the identity， （F（s）＝F（s）＊＝UF（s）（n〕⊆F（5）⊆F（s）． （2）Let g be a one・variable mapPing which does not belong to S． Then g is not in F（S）， since gGSand
9＝9・1∈（｛9｝⑧s）∩91． Definition 3．2 Let a and b be distinct elements of the base set X． We denote： K（a，b）＝｛∫∈9（〃）lf（α，．．．，の＝f（b，＿，b）｝． Lemma 3．2 1（（α， b）＊＝K（a， b）． Proof It will be easily seen that for any subsetFof9，
F⑧1（（a，b）⊆K（α，b）． Theorem l Asubset F of 9（〃）is＊−complete iff the following conditions are satisfied． （1） For any positive integer〃， the set F（n） is complete． （2）For any distinct elementsαand b of X， F is not contained in the set 1（（a， b）． Proof（Only−if part） Let us consider a four−varia− ble function H defined as follows．H（一・の一
o竺．≡1：：：i三：
where e denotes the addition in modulo le． Suppose that F is＊−complete， and H∈F｛P），Co∈F（φand C1∈F（γ｝ for some positive integers♪， g and γ， where Cα denotes the constant mapPing：Cα＠）＝α． Since the identity∫can be obtained from H by replacing all arguments of、仔by x， 1∈Fω． Consequently， for any positive integer n， H，∫，Co and C1∈F（pq’n）and
Wand I∈F（2pqrn），where
W（x，の＝H（1ぴ），1（の，Co＠）， C1（の） ＝Max｛x， y｝（iD 1． According to Webb［9コ， this function W can gene− rate all functions in、2（k）． Therefore， ゆ F（”）⊇uF（2P・’n）m⊇｛w，1｝＊＝｛w｝＝ρ（le）． m−1 Hence the condition （1）is necessary for the set F to be＊−complete． The necessity of the condition（2）is obvious by Lemma 3．2． （If part）A． Let us consider the subset Sn of 9，（le）defined as follows： Sn＝F（n）∩9、． Since the set、9， is finite， there exist distinct in・ tegers p and （7，ヵ＜q， such that Sρ and Sq are identica1． We denote this subset by S（S＝Sp＝Sq）． Obvious・ 1y， s⊆Fゆ）． Besides， F（q−P）⊆F（s）， since （F（q’P）⑧s）∩ρ1＝（F（q−P）⑧（F（P）∩9，））9， ＝F（q）∩9，＝s． By the condition（1）， F（s）＝F（8）⊇F（・−P）＝2， that is， F（s）＝9． B． Letαand b be arbitrary distinct elements ofX．We say that a mapping h with one variable
separates αand b， iff the values h（α） and h（b） are distinct． By condition（2）， F contains a mapPing∫which is not in K（α， b）． Therefore F〔1〕contains the following mapping which separates a and b： 9（∋ニゾ（x，＿，りc）． Since the elements g（a）and g（b）can again be separated by a certain mapping g’in F（1）， the elementsαand b are separated also by the com・ posite g’。g in F（2）・ By continuing similar steps， we shall have a mapping h in F（P）which separatesaandb．
C． Now let Q be the whole set of pairs of dis− tinct elements of X：Q＝｛（al， bi），．．．，（aκ， bκ）｝． Let hi be a mapping in F（P）which separates aiand bi・We de丘ne a function／with K variables
as follows． ・⑰・，…・XK）一o1二：1隠ll㌘（のf°「a1’”
If a and α’are distinct， then hi（α）キh、（a’）December 1978
Report of the Faculty of Engineering， Yamanashi University No．29 for some i． Therefore the mapping／is well de・ −fined． As we have proved in the paragraph A， the set F（S） is equal to・9 and hence contains this func− tionノ． Therefore ’ 1（x）＝ノ（h、（x），＿，娠（x）） ∈（｛1｝⑧（F（P）∩9，））∩9， ⊆（｛J｝⑧S）∩9，⊆S⊆F（P）． Thus the identity l is contained in、F（P）． The＊− completeness of the set F is now immediate： F＊⊇uF（pn）⊇（F（・））＊＝F（P｝・・9． 万＝1 This completes the proof of the theorem． The condition（1）of this theorem involves in・ 丘nitely many values of n and therefore is not easy to verify． So we shall give another criterion bywhich we can determine effectively whether a
finite subset F of 9（le）is＊−complete or not． De血nition 3．3 （1）Afunction fin J2（k）is said to be simple iff its value depends on at most one argument． In other words， a functionfis simple iff it is the case that i f（x、，＿，Xn）＝9（Xi） for a certain mapping g with one variable and a fixed su缶x i． We denote by S（le）the set of all simple func・ ．tions and a11 non−surjective functions in 32（k）． （2）Afunction fin・S2（le）is said to be linear iff it can be written in modulo le arithmetics as follows． ゾ＠、，＿，X。）＝α。㊥α、π、㊥＿㊥a。Xn． We denote by L（le）the whole set of linear func・ tions in J2（le）． We denote： N（le）一o隠llll蕊
Theorem 2 （J． Butler）Asubset F of 9（le）is
complete iff the following conditions are satisfied． （1）For any proper subsemigroup S of・91（k） containing the identity， F，5EF（S）． （2） F≠ハ1（」K）． For the proof， the reader is referred to Butler［1］． 1・emma 3．3 （1）N（ゐ）＝N（k） （2）F⊆N（le）iff F（n）⊆N（k） Proof（1） Straightforward（see［1］）． （2） If the set F is contained in IV（〃）， then for any n， F（n）⊆F⊆N（le）＝N（k）． Now suppose that F is not contained in 」V（le）． Then obviously F（1）is not contained in IV（fe）． We shall show by mathematical induction on n that the set F（n｝is not contained in N（le）， Let fbe a function withクvariables in F（n−1） and g a function with q variables ill F（1）， neither of which belongs to／V（〃）． We shall show that the following function h in F（n）does not belong to 2V（k）： h（X，・…，X。q）＝ゾ（9ぴ1・…・Xq），9（X，．1，＿，X，，），＿， 9（…・％，））・ Case 1． k＝2． We assume for contradiction that h is linear： h（X・・…・㌔）＝α。㊥α、X、㊥…①a。，X。，． Since the functions∫and g are non・1inear， neither of them is constant， and nor is their composite h． Therefore we can assume without loss of genera− 1ity that al＝1． Now any mapping with a single variable y in 9（2）can be written in the form：cy①d， where c and d are some binary constant． In particular， ア（y，9（0，＿，0），＿，9（0，＿，0））＝cy㊥d for some o and d． Hence a。㊥alXl①…㊤a，Xq −h（x1，…， Xq，0，…，0） ＝プ（9◎1，…，Xq），9（0，．一，0），＿，9（0，＿，0）） ＝c・9（x、，…，Xq）①d． Sinceα1 is not zero， c must be equal to one， and therefore 9＠1・…・Xq）＝（d㊥α。）⑪鋼㊥…Φaqx。． But this contradicts the assumption that g is non’ 1inear． Case 2．〃≧3． Since the functions f and g are not in／V（le）， they are surjective， and so is h． Let us assume for contradiction that the value of h depends on a single variable， say xl． Since g is surjective， there is a q−tuple （ait，．．．，輪）for eachたX such that
9（α乞1，…，a、q）＝i． Then for any arguments y（1），…，y（ヵ）of f， ！（y（1），＿，y（P））＝ア（9（％ω、，＿，a，・｛1），）・…・9（a，（。）1・…・ay（。），）） ＝h（ay（1）1・…・ay（P），）・ Thus the value of fis determined by ay〔1）1， that is， by y（1）． This contradicts the assumption that ∫is not in 」∼「（le）． 1）efinition 3．4 Let S and S’be subsets of ・9．，． We denote： F（5，s’）＝｛ゾ∈91（｛∫｝⑭S）9，⊆S’｝． In other words， a function∫is in F（S， S’）iff for any mapPings g1・…・gP in S the composed mapPing h（x）＝ア（9、（x），…，9P（x）） is always in S’． By definition， F（s，s）＝F（s）
and
F⊆F（S，S’）iff（F⑧5）∩9，⊆S’． 1、emma 3．4 Let F be a subset of 9，5a subset of 9，， and〃is a positive integer． Then the fol・ 10wing conditions are equivalent． （1）F（n）⊆F（S） （2） There exists a sequence So，＿， Sn of subsets of ・2， such that So＝・Sn＝Sand
F⊆∩F（Si．1， Sτ） tニユ Pmof Suppose that the condition（1）is satisfied． We define 80＝Sn＝Sand
s乞＝（F（i）⑧5）∩9、 for 1≦i〈n． Then， （F⑧S。）∩91＝（F⑧S）∩9、＝51，and
（FOPSt．、）∩9，＝F⑧（（F（i−1）⑧S）∩9，）∩9、 ＝F（i）⑧s）∩Ω1＝Si for 1≦i＜n． Besides， by the condition（1）， （F⑧s。．1）∩9，＝（F（n）⑧S）∩9，⊆S・ Sπ・ Thus the condition F⊆F（Sz−1， Si） holds fo al1 1≦i≦n． ・ Now suppose that the condition（2）is satisfied．Then by taking
S＝So， we have the following inclusions： （F（n｝⑧S。）∩ρ、＝（Fa）⑧．．．⑧F（1）⑧S。）∩9、 ⊆（F（1）⑧＿⑧Si）∩9， ● ． ． ■ ● ■ ● ● ● ⊆（．Fa）ops。．1）∩91 ⊆Sn＝s． Hence it is the case that F（n）⊆F（s）． De血nition 3．5 A sequence So，＿， Snt of subsets of 9， is called normal chain iff the following condi’ tions are satisfied． （1） The set so is a proper subsemigroup of・91 containing the identity． （2） So＝Sn （3） S誘差Sゴfor any 1≦i〈∫≦n・ By the condition（3）， the sets S1，＿， Sm are distinct to each another． Since、2，（ん） is finite， there are only a finite number of normal chains in 9，（k）． Theorem 3 A subset・F of・2（ゐ）is＊−complete iff it satisfies the following conditions． （3．1） For any normal chain So，＿，Snt， F≠∩F（Si．1，5D i＝1 （3．2） 17≠」V（le） （3．3） For any distinct elementsαand b of X， F．；2K（a，b）． Proof By Theorem 2， the condition（1）of Theorem lcan be replaced by the following conditions． （1a） For any positive integer n and any proper subsernigroup S of 9，（h）containing the identity， F（n）≠F（s）． （1b） For any positive integer n， F（n）5と1V（le）． By Lemma 3．3， the condition （1b）is equivalent to （3．2）． We shall show that the condition（1a）is equivalent to （3．1）． Let us consider the following inclusions． （C） F（n）⊆F（S） （d） F⊆∩F（Si．．1， St） 〆＝1 1f the condition（d）holds for some normal chain（S＞，then by Lemma 3．4the condition（c）holds
for％＝〃2 aDd S＝So． Conversely， suppose that the condition（c）holds for some positive integer n anda proper subsemigroup S of 9， containing the
identity． Then again by Lemma 3．4， there is a sequence So，＿， Sn of subsets of、Ω1 which satisfies the condition （d） and the equality：December 1978
Report of the Faculty of Engineering， Yamanashi University No．29 （e） So＝S（a proper subsemigroup of 9， con・ taining I）． If Sz is contained in 5ゴfor someゴand∫such that 1≦i＜ノ≦n，then we can shorten the sequence in the following way without violating the conditions （d） and （e）： 5。・…・5、．1・Sj・…・Sn・ By applying the same procedure repeatedly， we can remove all subsets which violate the condition （3）of normal chain． So we can eventually anormal chain satisfying the condition（d）． completes the proof of the theorem． Corollary For any finite subset F of・2（k）， is a finite procedure to determine whethes ＊・complete or not． Proof All of the following conditions are ble． （1）F⊆F（S，S’）， or equivalently， （、F⑧s）∩9，⊆S’． （2）F⊆N（le） （3）F⊆K（a，b）．4． Maximal＊−incomplete Sets
have
This
thereFis
decida・Amaximal incomplete set F is an incomplete
subset of、2 such that any set 1汀’ containing the set F properly is complete． Similarly， a subset Fof g is called maximal＊−incomplete set（or＊− maximal set in short）iff it is not＊・cOmplete and any set F’containing F properly is＊・complete．Lemma 4．1 Every maximal incomplete set is a
maxima1＊−incomplete set． Proof As it is easily seen， every maximal incom・ plete set F contains the identity and is＊・incom− plete． If a set F’contains F properly， then F’ contains also the identity． Hence F’＊＝F’＝、Ω． Let us denote by￠（〃）the whole class of the following subsets of 52（〃）． （1） ∩F（S日，Si）， where｛Si｝is a normal chain． （2）κ（α，b）， whereαand b are distinct elements ofX． （3） 」∼「（ゐ）． Lemma 4．2 （1） All＊−maximal sets are in φ（le）． （2）If a setルfinφ（〃）is maxima1 inψ（〃）with respect to the set theoretical in・ clusion， then it is＊・maxima1．Proof （1）Any＊・maximal setルI is＊・incomplete
and therefore is contained in some setルf’in￠（ゐ）． By the maximality ofル1， we haveル1＝M’． （2） Obvioue． The following theorems are now immediate． Theorem 4 The number of＊・maximal sets in J2（le） is finite． Theorem 5 A set F of functions is＊−complete iff it iS nOt COntaining in any＊・maXimal Set． Theorem 6 （Representation theorem） （1） The set IV（ん）is＊．maximal． ， （2）The set K（a，6）is＊・maximal for any dis− tinct elementsαand 60f X． （3） A＊−maximal set M other than 2V（〃）and 1（（α，b）’s can be represented in the following form： M＝∩F（Si．1， S＞， i＝1 where（Sτ）is a certain normal chain． Proof （1）This follows to Lemma 4．1， since 2V（〃） is known to be a maximal incomplete set（［1］）． （2） Let∫be a function which is not inK（α，b）． We shall show that the set 1（（α， b）∪｛∫｝is always ＊−complete． Let h be an arbitrary function withヵvariables． ハ We consider functions f， g and H defined as fol・ lOWS． ハ ∫（x）＝f（x，＿，x）， 9（x）＝xifx￥b， 9（b）＝α， H（x，，…，Xp， Yl，…，Yp）＝where
αi＝ h（a，．．．，a）．．． lf Xi＝b for some i， h（α1，…・αρ）…other・ wise， Obviously， b）． Besides， h（x、・…，y。）＝＝H（9（x、）・…，9（Xp）・プ（Xl）・…・ノ（x。））・Therefore
h∈K（α，b）⑧（K（a，b）∪｛ゾ｝）ω へ a．．．if Ii＝a and yi＝ノてa） ハ b．．．if Xi＝a and yz＝ノてb） Xi．．．otherwise． ハゾisin ｛f｝（1）andgandHareinK（a，
｛f∈0（2）1ア⑰，＿，∋ ＝1−x｝． Remark 1． The first five sets are maximal in’ complete sets obtained by且Post［4］． Remark 2． In this case， F（｛1，Co， C1｝，｛NOT， Co， C1｝）＝F（｛NOT， Co， C1｝，｛1， Co， C1｝）
