Тугылбаева Б.Г.

Восточно-Казахстанский государственный университет им.С. Аманжолова, Казахстан

Некоторые свойства конгруэнций на подклонах клона Бурле ранга три

Предитеративной алгеброй Поста[1] называется алгебра Р_А^*=‹О_А,ζ,τ,Δ,›, носителем которой является О_А множество всех функций отображающих множество А в себя, а операции ζ, τ, Δ, задаются при n>1 с помощью равенств: (ζf)(x₁,x₂,….,x_n)= f(x₂,x₃….,x_n,x₁), (τf)(x₁,x₂,….,x_n)= f(x₂,x₁,x₃….,x_n ), (Δf)(x₁,x₂,….,x_n-1)=f(x₁,x₁,x₂….,x_n-1),(fg)(x₁,…x_n+m-1)=f(g(x₁,….,x_m),x_m+1,…,x_n+m-1).

Если f – унарная функция, то ζf =τf= Δf=f.

Подалгебры алгебры , содержащие проекции, т.е. функции (х₁,…,х_n)=х_i, называются клонами. Мощность множества A называется рангом клона. Клон конечного ранга k будет обозначаться через .

Клоны играют важную роль в теории универсальных алгебр, они находят применение в вычислительной технике, распознавании образов и т.д.

Клон, все функции которого удовлетворяют термальному условию [3], называется TC- клоном. На трехэлементном множестве A ={0,1,2} имеется всего два максимальных TC-клона L и В. Клон L состоит из линейных операций. Клон B состоит из одноместных операций и из операций представимых в виде f₀(f₁(x₁)+…f_n(x_n)), где сложение ведется по mod2, а операции f_i одноместные. Такие функции называются квазилинейными, а образованный ими клон B - клоном Бурле.

В [3] построена решетка всех подклонов клона Z, образованного проекциями и операциями, принадлежащими клону Бурле, принимающими значения 0 и 1. Одноместные функции, принадлежащие клону Z, перечислены в таблице 1. Любую отличную от проекции функцию из Z, можно представить в виде:

f(x₁,….,x_n)=C_f (*)

(сложение по mod2), C₀ выделяют фиктивные переменные, C_f{0,1},

{i₁,….,i_n}={1,…n}, Г_f={i₁,….,i_p}, Φ_f={i_p+1,….,i_p+q}, Ψ_f={i_p+q+1,….,i_p+q+r}.

Переменные из множества K_f= Φ_f UΨ_f назовем основными.

x	φ	ψ	γ	δ			C0	C1
0 1 2	0 1 0	0 1 1	0 0 1	1 1 0	1 0 1	1 0 0	0 0 0	1 1 1

Таблица 1

Клоном со свойством , называется клон, содержащий функции или . Клон K называется клоном со свойством , если в K есть функция, имеющая, по крайней мере, две основные переменные.

Использование операции дает следующие результаты: f^m =, при i>1 , f^m=f^m+n-1, φf^m=ψf^m=f^m, γf^m=, i=0,1. (**)

Применение операции Δ к бинарным функциям дает следующие результаты:

Δ (φ(x₁)ψ(x₂) )= γ( x₁), Δ (γ (x₁) φ(x₂) )= ψ ( x₁), (***) Δ (γ (x₁) ψ (x₂) )= φ ( x₁) Δ (u(x₁)u(x₂) )= C₀( x₁), u { φ ,ψ, γ, C }

Будем писать æ₁ æ₂, если æ₁ æ₂ и между конгруэнциями æ₁и æ₂ нет промежуточной конгруэнции æ₃: æ₁ æ₃æ₂ æ₁= æ₃ æ₂= æ₃.

Горловым в [2] доказано, что на клонах не существует внеарностных конгруэнций, отличных от единичной æ₁. Там же доказано Свойство 1: пусть ææ_a, подарностная конгруэнция на клоне K. Она совпадает с æ_a тогда и только тогда, когда по ней сравнимы две различные проекции.

В [4] доказано, что на подклонах клона Z имеется конгруэнция æ_е, которая на множестве E совпадает с нулевой конгруэнцией, а на множестве Z\E с арностной. Е-множество всех проекций. Там же описаны все конгруэнции, имеющиеся на подклонах клона Z в которых все отличные от проекций функции не являются креативными и доказано, что между конгруэнциями æ_е и æ_а нет промежуточной: æ_еæ_а.

В данной работе описываются конгруэнции, имеющиеся на подклонах клона Z, не содержащиеся в æ_е.

Докажем два свойства конгруэнций имеющиеся на подклонах клона Z.

Свойство 2. Если по некоторой конгруэнции æ сравнимы функции f, g такие что K_f K_g, то æ_е æ.

Доказательство. Синхронно применяя операций ζ, τ к данному сравнению получим функции f₁, g₁ такие, что последняя переменная у функции f₁ основная, а у g₁ нет. Применив n-2 раза операцию Δ, получим сравнение

u(x₁,x₂)≡v(x₁,x₂)(æ), K_u K _v. (S)

1)Если K_u={i}, K_v=Ø или K_u={i}, K_v={1,2}, то применяя операцию Δ к сравнению (S) получим сравнение s(x)≡t(x)(æ), K_s={1}, K_t= Ø. Подставив это сравнение в себя, получим одно из следующих φ≡C(æ), ψ≡C(æ) , где C - константа. Подставим в них сравнение h≡h, где h(x₁,....., x_m)K любая функция. Отсюда каждая содержащаяся в K m–арная функция сравнима с константой C, значит æ_е æ.

2) Если K_u=Ø, K_v={1,2}, то верно сравнение s≡t, K_s =Ø K_t={i}, s(x₁,x₂)=Δ(uu),

t(x₁,x₂)=Δ(vv)(æ). Значит, этот случай сводится к первому.

3)Если K_u={1}, K_v={2}, то для любой функцию h(x₁,....., x_m)K, функции s(x₁,.....,x_m)=Δ(uh){h, h1}, t(x₁,.....,x_m)=Δ(vh) сравнимы. Функция t не зависит от h. Если s=h1, то вместо h подставим функцию h1. Таким образом каждая содержащаяся в K m–арная функция сравнима с t, значит æ_е æ.

Свойство 3. Пусть по конгруэнции æ сравнимы проекция и функция f, такая что K_f {i}.Тогда æ совпадает с арностной конгруэнцией æ_а.

Доказательство: Пусть f(x₁,.....,x_n) ≡(æ), K_f{i}. Аналогично доказательству свойства 2 доказывается включение æ_еæ.

Тогда для любой функции f из клона K, f≡ ζ (f)(æ). Из сравнений ζ (f)≡ζ()(æ), f≡(æ), следует ≡ζ ()(æ), где ζ () - проекция, не совпадающая с . Тогда из свойства 1 следует æ=æ_а.

Введем следующие обозначения для эквивалентностей:

f≡g(π)(f=g)(K_f=K_g)&(C_f=C_g)(f=&K_g={i}&C_g=0) f≡g(π₀₁)(f=g)(K_f=K_g ) ( f=& K_g ={i})

Лемма 1. На клонах, со свойством , эквивалентность π₀₁ является конгруэнцией и π₀₁ æ_а.

Доказательство: Стабильность относительно операций ζ, τ следует из того, что любую функцию можно представить в виде суммы (*) операция сложения

коммутативна. Стабильность относительно операций и Δ следует из их свойств (**) и (***).

Покажем, что если π₀₁ææ_а и π₀₁æ, то æ=æ_а. Так как π₀₁æ, найдутся две функции f и g, сравнимые по æ, но не сравнимые по π₀₁.

Возможны следующие три случая:

1. Обе функции являются проекциями, и сравнение имеет вид ≡(æ), где ij. Из свойства 1 следует æ= æ_а.

2. Только одна из функций, например g, является проекцией , тогда

K_f{i}. Согласно свойству 3, æ= æ_а.

3.Обе функции не являются проекциями, тогда K_fK_g. Из свойства 2 получим æ_еæ. Тогда по æ сравнимы функции s, u такие, что K_s={i}, K_u={j}. По условию π₀₁æ. Поэтому ≡s(æ), ≡u(æ). Отсюда ≡(æ), ij. По свойству 1, æ= æ_а.

Лемма 2. На клонах, содержащих функции φ или ψ эквивалентность π является конгруэнцией. Пусть K клон со свойством . Если в клоне K нет функций или , то πæ_а, если есть, то ππ₀₁.

Доказательство. Стабильность относительно основных операций и первое включение доказываются, так же как и в Лемме 2. Докажем второе. Пусть πæπ₀₁ и клон K содержит функцию . Клон K клон со свойством , поэтому в нем есть функция φφ. Допустим функции f и g сравнимы по конгруэнции æ, но несравнимы по π₀₁.

1.Если только одна из функций, например g, является проекцией g =, тогда

K_f = {i}, C_f=1. Отождествляя все переменные, получим (e,) æ .

2. Если обе функции не являются проекциями, тогда C_fC_g. Отождествляя все переменные получим одну из пар (φ,), (С₀,С₁), (γ,δ). Подставляя второе и третье сравнения в тривиальное сравнение (φφ, φφ) получим первое. Так как πæ, то в конгруэнции æ есть пара (e,φ)(e,)æ. Из пары (e,) с помощью основных операций можно получить любую пару из π₀₁. Таким образом, π₀₁æ.

Если некоторая подарностная конгруэнция, заданная на подклонах клона Z не содержится в æ_е, то по ней сравнимы две разные функции, из которых хотя бы одна является проекцией. Поэтому из перечисленных утверждений следует следующая теорема.

Теорема 1)На подклонах клона Z со свойствами и , в частности на самом клоне Z, всего две конгруэнции π, π₀₁ не содержатся в æ_е, ππ₀₁æ_а.

2)Если K клон со свойством не обладает свойством , то на нем только одна конгруэнция π не содержится в æ_е, π æ_а.

Литература:

1. Мальцев А.И. Итеративные алгебры Поста. Новосибирск: НГУ,1976

2. Горлов В.В. О конгруэнциях на замкнутых классах Поста// Мат. заметки 1973 т.13.№5 стр. 725-734

3. Деметрович Я., Мальцев И.А. О строении клона Бурле на трехэлементном множестве// Acta cybernetica. 1989. V. 9, \No 1.P. 1-25.

4.Мальцев И.А., Тугылбаева Б.Г. Конгруэнции на подклонах клона Бурле ранга три, не содержащих креативных функций//Сиб.мат.журнал. 2008,том 49,№5 стр.1087-1104