Об одном семействе е-замкнутых классов гиперфункций ранга

В теории дискретных функций, наряду со всюду определенными функциями k-значной логики, изучаются и функции, определенные не на всех наборах. К не всюду заданным функциям на конечном множестве относятся в том числе гиперфункции, у которых неопределенность понимается как некоторое неодноэлементное непустое подмножество конечного множества, на котором эти функции заданы. Для уточнения операции суперпозиции гиперфункций требуется определить их значения на наборах, составленных из подмножеств. В тоже время в качестве оператора замыкания на множестве гиперфункций можно рассматривать операторы, которые существенно сильнее суперпозиции и могут порождать конечную классификацию функций. К таким операторам относится, в частности, оператор замыкания с разветвлением по предикату равенства [1].

Исследование его свойств на множестве булевых функций, частичных булевых функций и на множестве функций многозначной логики можно посмотреть в работах [2, 3], в работе [5] для множества частичных булевых функций найдены все замкнутые классы. В [6] для гиперфункций на двухэлементном множестве был сформулирован критерий функциональной полноты. Для гиперфункций на трехэлементном множестве в [7] были описаны классы гиперфункций, сохраняющих некоторое множество.

В настоящей работе рассматриваются действия оператора замыкания с разветвлением по предикату равенства на множестве гиперфункций ранга k .

1.    Основные определения

Пусть E k = {0,1, к , к - 1} и 2 E k — множество всех подмножеств E k . Определим множество Н_к — множество всех гиперфункций ранга к :

H r = { f\f : E k ^ 2 E \{ 0 }}, H k = U H k .

n

Говоря о гиперфункциях, удобно не различать одноэлементное множество и элемент этого множества, поэтому в дальнейшем одноэлементное множество { b} будем обозначать символом b .

Если Р_к — множество функций к -значной логики, то справедливо включение Р_к с Н_к .

Пусть f (xlvK xn ), f.(x1,K, xm ), •••, fn (x ^к, xm ) — гиперфункции. Суперпозиция f ( f( x 1,K, xmX-K fn ( xi,K, xm ))

определяет гиперфункцию g ( x ₁, к , x m ) следующим образом, если набор ( a 1 , к a m ) е E m , то по определению

g ⁽ a 1 , к , a m ) =     U ^{f ( b} 1 , K , ^b n ).

^b i ^e fj ⁽ a 1 , K , a m )

Будем говорить, что гиперфункция g ( x 1 , к , x m ) получается из гиперфункций f , ( x 1 , к , x m ), f , ( x 1 , к , x m ) с помощью операции разветвления по предикату равенства, если для некоторых i , j е {1, к , m } выполняется f X x 1 , к , x m ), если x j = x j ;

g ^{( x} 1 , к , x m ) =

f X x 1 , - ■, x m ), в противном случае.

Для множества Q с Н_к определим E-замыкание как множество всех гиперфункций из Н_к , которые можно получить из множества Q с помощью операций введения фиктивных переменных, отождествления переменных, суперпозиции и разветвления по предикату равенства. Множество гиперфункций, совпадающее со своим E-замыканием, называется E-замкнутым классом.

2.    E-полные множества гиперфункций

В [3] показано, что система констант {0,1, к , к - 1} E-полна в классе Р_к . Для гиперфункций справедливо следующее утверждение.

Теорема 1. При любом к >  2 система гиперфункций {0,1, к , к - 1,{0,1, к , к - 1}} E-полна в классе Н_к .

Доказательство. Пусть f ( x 1 , к , x n ) — произвольная гиперфункция из Н_к . Определим в классе Р_к функции h 1 ( x₁, к , x n ),..., h_k - 1( x 1, к , x n ) и g ( x 1 , к , x_k ) по следующему принципу.

Если f ( a 1 , к , a n ) = c , где c — элемент множества Е_к , то h 1 ( a 1 , к , a n ) = c , ., h k _ч( а „к , a n ) = c и          g ( c , к , c ,0) = c ,...,

g ( c , к , c , к - 1) = c .

Если f (а 1,к,an) = {t 1, к, tm}, где 1 < m < к -1, ti е Ек , то h1(a 1,к, an ) = t1, h 2( a1,к, an ) = t 2>. hm (a 1,к, an ) = tm , hm+1(a 1,к, an ) = tm ,•••, hk-1( a 1,к, an ) = tm . Функция g формируется следующим образом:    g(t1,t2,к,tm,tm,...tm,i) = ti    для 1 < i < m и g(t1, t 2,к, tm , tm ,к tm , j) = tm при j = 0, m < j < к - 1.

Если f ( a 1 , к , a n ) = {0,1, к , к - 1}, то положим h 1 ( a 1 , к , a n ) = к - 1, ., h_{k 4}( a „к , a n ) = 1, а также g ( к - 1, к - 2, к ,2,1, i ) = i , где 0 <  i <  к - 1.

Тогда гиперфункцию f ( x ₁, к , x n ) можно представить следующей суперпозицией функций из класса Р_к и гиперфункции {0,1, к к - 1}.

^{f ( X} 1 ^, к ^, x n ) = g ^{( h} 1 ⁽ x 1 , к , x n ), к , ^h h - 1 ^{( X} 1 ^, к ^, x n ^),{0,1, к , ^{к - 1})}.

Теорема доказана.

Следствие. При любом к >  2 система гиперфункций {0,1, к , к - 1, A }, где A — тождественная отличная от константы гиперфункция, E-полна в классе Н_к .

Доказательство. Укажем механизм построения гиперфункции {0,1, к , к - 1} c использованием констант 0,1, к , к - 1 и гиперфункции f - A .

Пусть с — некоторая константа, такая, что c ^ A. Построим гиперфункцию fc, если x 1 = x 2; g(x 1, x 2) = 1 , {A, в противном случае.

Выберем константу b такую, что b е A . Суперпозиция g ( f ( x ), b ) определяет гиперфункцию, которая на всех наборах принимает значение равное A о c .

Применяя указанный способ построения гиперфункций нужное количество итераций, можно получить гиперфункцию вида {0,1, к , к - 1}. Следствие доказано.

3.    Классы гиперфункций, сохраняющих перестановки

Пусть п — некоторая перестановка на множестве E_k = {0,1, к , к - 1}. Определим класс гиперфункций S^. следующим образом:

S - = ^{ f ^е H k I ^{п (} f ( « ^к, a n )) и f (^ « Дк, ^п« )) ^{ф0, a} i е E k ^}, где для любого множества В , являющегося подмножеством E_k , множество пВ понимается как {пЬ | b е В }.

Теорема 2. Класс S _n замкнут относительно операции суперпозиции.

Доказательство. Пусть гиперфункции f (x 1, к, xm), f,(x 1, к, xn), ..., fm (x 1, к, xn) принадлежат классу Sn и пусть

h ⁽ x ^к, x n ) = f ⁽ f X x ^к, x n Х-^{к f} m ⁽ x ^к, x n ⁾⁾-

Покажем, что гиперфункция h(x 1,к, xn) принадлежит классу Sn , а именно, для любого набора («1, к, an) е Ekn выполняется п (h(«1, к, «n)) n h(п(«1), к, п«)) Ф 0.

По определению

п ( h ( « ,

« n )) = ^п

U f ( Г 1ж Y m ) У Y i ^e fl (^.-- А ,)            У

U ^{n (} f ⁽ Y 1

Y i ^е f i ( « ^к А )

Y m )) = A ,

h ( п ( « 1 ), к , п« )) =       U f (5 1 , к , 5 m ) = В .

6 i e f ( п ( « 1 ), к , п ( « n ))

Для набора ( « 1 , к , «_n ) и для любого i выполняется ^{п ( f}i ⁽ « 1 , к , «n )) ^{П f}i ^(п(« 1 ), к , ^{п (} « П )) *^0, т.е. существует такой набор ( 5 1 , к , 5 m ), что 5_iе п ( f ( « 1 , к , «_n )) и

• ⁵ i ^е fi^(п(« 1 ), к , ^{п (} « п )). Пусть ⁵ i = ^{п (} ^ -), где ^ i ^e fi⁽« 1 ^, к , « n ).

Рассмотрим значение f (51,к,5m). С одной стороны, в силу того, что 5i е fi(п(«1), к,п(«п)), все элементы этого множества содержатся в В. С другой стороны, f (51,к, 5m ) = f (п(a1),к, п(^т )) и ^ е fi- («„к, «n ). Для набора (о\, к, am) выполняется п (f (а1,к, am )) n f (Хо-Дк, п(ат )) *0, ai е fi- («„к, «n ).

Рассмотрим некоторый элемент p е E_k такой, что

Р ^{е f (п(о} 1 ), к , ^{п ( о} т )) = ^{f ( 5} 1 , к , ⁵ т ), ⁵ i ^{е f}_t^(п(« 1 ), к , ^{п (} « п ^)).

Это означает, что p е В . В тоже время

Р е п(f (о1,к,°т)), о е fi-(«„к,«n). Следовательно, p е A. В итоге, п (h(«1, к, «n)) n h(п(«1), к, п(«п )) Ф 0.

Теорема доказана.

Теорема 3. Класс S _n замкнут относительно операции разветвления по предикату равенства.

Доказательство. Пусть гиперфункции f, (x 1, к, xn), f2(x 1, к, xn) принадлежат классу S^ и пусть h (x i, к, xn) =

• f , ( x 1 , к.,x n ), если x, = x j ;

f ₂( x 1 , ..., x n ), в противном случае.

Применим к гиперфункции h перестановку п . Тогда

^{п (} h ^(a 1 ^, к ^, a n )) =

п( f , ( « 1 , к , « п )), если a , = a j ;

п( f ₂( a 1 , к , a n )), в противном случае, если n ( a i ) = n ( a j ); в противном случае.

f (п(« ), к, п(о,)), 11    n h (п(a), к, п(о,)) = ]

¹     ’ n      I f 2 ( п ( « 1 ), к , п(« п )),

Но п(ai) = п(«j) о ai = aj, поэтому f f (п(« ),к, п(о,)), 11    n h (п(a), к, п(о,)) = ]

¹     ’ n      I f 2 ( п ( « 1 ), к , п(« п )),

если a i = a j ;

в противном случае.

Пусть a i = a j . Тогда h («₁, к , a n ) = f ₁( « ₁, к , a n ). С другой стороны, ^{п ( h} ( « „к, ^a n )) = ^{п ( f} X ^a i^,. K ^a n ))

и

• ^{h (n(a} i ), к , ^{n ( a} n )) = ^f 1 ( fr^ ), к , ^{n ( a} n )) .

По условиюп(f1(«1,к,an)) n fX^a,),...,n(an)) *0. Тогда п (h(«„к,«п)) nh(п« ),к,п(«п)) * 0.

Если a i * a j , то h ( « ₁, к , a n ) = f ₂( « ₁, к , a n ) и рассуждения проводятся аналогичным образом. Теорема доказана.

Замкнутость относительно отождествления переменных и введения фиктивных переменных показывается несложным образом.

Таким образом, классы 8 ^ являются E-замкнутыми на множестве гиперфункций ранга k . Рассмотрим вопрос полноты таких классов.

Теорема 4. Если перестановка п разлагается в произведение циклов одной и той же простой длины p , то класс S ,- является Е-предполным в классе H _k .

Доказательство. Пусть п — перестановка из условия теоремы и функция f ( x ₁, к , x_n ) не принадлежит классу 8 ^ . Это означает, что есть такой набор (a₁, к ,a_n ) для которого выполняется

^{п ( f (a} 1 ^, к ^,a n )) ^{П f (п(a} 1 ^), к ^,П(a n )) = ⁰.

Повторяя рассуждения из [4, п. 1.8], несложно показать, что гиперфункцию f ( x ₁, к , x_n ) можно считать одноместной.

Пусть для f ( x ) и a е E k выполняется п ( f ( a )) n f (n(a )) = 0 . Положим f (a ) = С , f (n(a )) = B. Рассмотрим наборы ( с₁,a ) и ( с₂,a ), где с 1 , с ₂ е С . Покажем, что такие наборы не лежат на одной орбите. Если они лежат на одной орбите, то для некоторого s выполняется П ( c 1 ,a ) = ( c ₂, a ). Тогда n^s ( c 1 ) = c ₂ и n^s ( a ) = a . Поэтому s = tp . Получили, что с ₂ = n tp ( c 1 ) = c .

Аналогично, если наборы ( b 1 ,n(a )) и ( b ₂, n ( a )), где b 1 , b ₂ е B лежат на одной орбите, то b 1 = b ₂.

Рассмотрим наборы вида ( с , a ) и ( b,n(a )), где с е С , b е B . Покажем, что они тоже не могут лежать на одной орбите. Если они лежат на одной орбите, то для некоторого s выполняется n^s ( c,a ) = ( b , n ( a )). Отсюда n^{s - 1}( a ) = a . Значит s - 1 = pt и n pt ^{+ 1}( c ) = b , значит п ( c ) = b . Что противоречит условию пС n B = 0 .

Таким образом, все наборы вида ( с ₁, a ), ( с ₂, a ), ( b 1 , n ( a )) и ( b ₂, n ( a )), где с 1 * с ₂, b 1 * b ₂, с 1 , с ₂ е С , b 1 , b ₂ е B лежат на разных орбитах. Поэтому в классе S , найдется гиперфункция g ( x , y ), зависящая от 2-х аргументов, такая, что на указанных выше наборах она принимает некоторое одно и тоже значение в . Рассмотрим гиперфункцию h ( x ) = g ( f ( x ), x ). По определению h (a ) = U Yе f ( a ) = C g (Y, a ) = в и h(n(a )) = U ₇е f( , ( a )) = B g(Y,n(a )) = в . Функция u ( x ) = { a , n ( a )} очевидно также принадлежит классу S , . Суперпозиция h ( u ( x )) = h ({ a , n ( a )}) тождественно равна константе в .

С учетом того, что гиперфункция, тождественно равная множеству E _k , лежит в любом классе S , , получаем справедливость утверждения. Теорема доказана.

Заключение

В работе рассмотрено семейство классов гиперфункций, сохраняющих перестановки на множестве E_k и замкнутых относительно оператора суперпозиции и оператора разветвления по предикату равенства. Показано, что, если перестановка разлагается в произведение циклов одной и той же простой длины, то такие классы являются предполными в классе гиперфункций ранга к . В [7] описаны E-предполные классы гиперфункций ранга 3, сохраняющие некоторое подмножество E ₃. Эти результаты могут быть обобщены для гиперфункций, заданных на произвольном множестве.