Тугылбаева Б.Г.
Восточно-Казахстанский государственный университет им.С. Аманжолова, Казахстан
Некоторые свойства конгруэнций на
подклонах клона Бурле ранга три
Предитеративной
алгеброй Поста[1] называется алгебра РА*=‹ОА,ζ,τ,Δ,›, носителем которой
является ОА множество всех функций
отображающих множество А в себя, а операции ζ, τ, Δ,
задаются при n>1 с помощью равенств: (ζf)(x1,x2,….,xn)= f(x2,x3….,xn,x1), (τf)(x1,x2,….,xn)= f(x2,x1,x3….,xn ), (Δf)(x1,x2,….,xn-1)=f(x1,x1,x2….,xn-1),(f
g)(x1,…xn+m-1)=f(g(x1,….,xm),xm+1,…,xn+m-1).
Если
f – унарная функция, то ζf =τf= Δf=f.
Подалгебры
алгебры , содержащие проекции, т.е. функции
(х1,…,хn)=хi, называются
клонами. Мощность множества A
называется рангом клона. Клон
конечного ранга
k будет обозначаться через
.
Клоны играют важную роль в теории
универсальных алгебр, они находят применение в вычислительной технике,
распознавании образов и т.д.
Клон, все функции которого удовлетворяют
термальному условию [3], называется TC- клоном.
На трехэлементном множестве A ={0,1,2}
имеется всего два максимальных TC-клона L и В. Клон L состоит
из линейных операций. Клон B состоит из одноместных операций и из операций
представимых в виде f0(f1(x1)+…fn(xn)), где сложение ведется по mod2, а операции fi одноместные. Такие функции называются квазилинейными,
а образованный ими клон B - клоном Бурле.
В [3] построена решетка всех
подклонов клона Z,
образованного проекциями и операциями, принадлежащими клону Бурле, принимающими
значения 0 и 1. Одноместные функции, принадлежащие клону Z, перечислены в таблице 1. Любую отличную от проекции
функцию из Z, можно представить в виде:
f(x1,….,xn)=Cf (*)
(сложение по mod2), C0 выделяют
фиктивные переменные, Cf
{0,1},
{i1,….,in}={1,…n}, Гf={i1,….,ip}, Φf={ip+1,….,ip+q},
Ψf={ip+q+1,….,ip+q+r}.
Переменные из множества Kf= Φ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 есть функция, имеющая, по крайней мере, две
основные переменные.
Использование операции дает следующие
результаты:
fm =
, при i>1 ,
fm=fm+n-1, φ
fm=ψ
fm=fm, γ
fm=
,
i=0,1. (**)
Применение операции Δ к бинарным функциям дает следующие результаты:
Δ (φ(x1)ψ(x2) )= γ( x1), Δ (γ (x1)
φ(x2) )=
ψ ( x1), (***) Δ (γ (x1)
ψ (x2) )=
φ ( x1) Δ (u(x1)
u(x2) )= C0( x1), u
{ φ ,ψ,
γ, C }
Будем писать æ1 æ2, если æ1
æ2 и между конгруэнциями æ1и
æ2 нет промежуточной конгруэнции æ3: æ1
æ3
æ2
æ1= æ3
æ2= æ3.
Горловым в [2]
доказано, что на клонах не существует внеарностных конгруэнций, отличных от единичной æ1. Там же
доказано Свойство 1: пусть ææa,
подарностная конгруэнция на клоне K. Она совпадает с æa тогда
и только тогда, когда по ней сравнимы
две различные проекции.
В [4] доказано, что на
подклонах клона Z имеется конгруэнция æе,
которая на множестве E совпадает с
нулевой конгруэнцией, а на множестве Z\E с арностной. Е-множество
всех проекций. Там же описаны все
конгруэнции, имеющиеся на подклонах клона Z в которых все отличные от проекций функции не
являются креативными и доказано, что между
конгруэнциями æе и æа нет промежуточной:
æеæа.
В данной работе
описываются конгруэнции, имеющиеся на подклонах клона Z, не содержащиеся в æе.
Докажем два свойства конгруэнций имеющиеся
на подклонах клона Z.
Свойство 2. Если
по некоторой конгруэнции æ сравнимы функции f, g такие что Kf Kg, то æе
æ.
Доказательство. Синхронно применяя операций ζ, τ
к данному сравнению получим функции f1,
g1 такие, что последняя переменная у функции f1 основная,
а у g1 нет. Применив n-2 раза операцию Δ, получим сравнение
u(x1,x2)≡v(x1,x2)(æ),
Ku K v. (S)
1)Если Ku={i}, Kv=Ø
или Ku={i}, Kv={1,2}, то применяя операцию Δ к сравнению (S) получим сравнение s(x)≡t(x)(æ), Ks={1}, Kt=
Ø. Подставив это сравнение в себя, получим одно из следующих φ≡C(æ), ψ≡C(æ) , где C - константа. Подставим в них сравнение h≡h, где h(x1,....., xm)K любая функция. Отсюда каждая содержащаяся в K m–арная функция сравнима с константой C, значит æе
æ.
2) Если Ku=Ø,
Kv={1,2}, то верно сравнение s≡t, Ks
=Ø Kt={i}, s(x1,x2)=Δ(uu),
t(x1,x2)=Δ(vv)(æ). Значит, этот случай сводится к первому.
3)Если Ku={1},
Kv={2}, то для любой функцию h(x1,....., xm)K, функции s(x1,.....,xm)=Δ(u
h)
{h, h
1}, t(x1,.....,xm)=Δ(v
h) сравнимы. Функция t не
зависит от h. Если s=h
1, то вместо h подставим функцию h
1. Таким образом каждая
содержащаяся в K m–арная функция сравнима с t, значит æе
æ.
Свойство 3.
Пусть по конгруэнции æ сравнимы
проекция и функция f, такая что Kf
{i}.Тогда æ совпадает с
арностной конгруэнцией æа.
Доказательство:
Пусть f(x1,.....,xn) ≡(æ), Kf
{i}. Аналогично доказательству
свойства 2 доказывается включение æе
æ.
Тогда для любой функции f из клона K, f≡ ζ (f)(æ). Из
сравнений ζ (f)≡ζ()(æ), f≡
(æ), следует
≡ζ (
)(æ), где ζ (
) - проекция, не совпадающая с
. Тогда из свойства 1 следует æ=æа.
Введем следующие обозначения для эквивалентностей:
f≡g(π)(f=g)
(Kf=Kg)&(Cf=Cg)
(f=
&Kg={i}&Cg=0)
f≡g(π01)
(f=g)
(Kf=Kg )
( f=
& Kg ={i})
Лемма 1. На
клонах, со свойством , эквивалентность π01 является конгруэнцией
и π01
æа.
Доказательство: Стабильность относительно операций ζ, τ следует
из того, что любую функцию можно представить в виде суммы (*) операция сложения
коммутативна. Стабильность относительно операций и Δ следует из их свойств (**) и (***).
Покажем, что если π01æ
æа и π01
æ, то æ=æа. Так как π01
æ, найдутся две функции f и g, сравнимые по æ, но не сравнимые по π01.
Возможны следующие три случая:
1. Обе функции являются проекциями, и сравнение имеет
вид ≡
(æ), где i
j. Из свойства 1 следует æ=
æа.
2. Только одна из функций, например g, является
проекцией , тогда
Kf{i}. Согласно свойству 3, æ= æа.
3.Обе функции не являются проекциями, тогда KfKg. Из свойства 2
получим æе
æ. Тогда по æ сравнимы функции s, u такие, что Ks={i}, Ku={j}. По условию π01
æ. Поэтому
≡s(æ),
≡u(æ). Отсюда
≡
(æ), i
j. По свойству 1, æ= æа.
Лемма 2. На
клонах, содержащих функции φ или ψ эквивалентность π является
конгруэнцией. Пусть K клон со свойством . Если в клоне K нет функций
или
, то π
æа, если есть, то π
π01.
Доказательство. Стабильность относительно основных операций и первое включение доказываются, так
же как и в Лемме 2. Докажем второе. Пусть πæ
π01 и клон K содержит функцию
. Клон K клон со свойством
, поэтому в нем есть функция φ
φ. Допустим
функции f и g сравнимы по конгруэнции æ, но несравнимы по π01.
1.Если только одна из функций, например g, является
проекцией g =, тогда
Kf = {i}, Cf=1.
Отождествляя все переменные, получим (e,)
æ .
2. Если обе функции не являются проекциями, тогда CfCg. Отождествляя все переменные получим одну из пар (φ,
), (С0,С1), (γ,δ). Подставляя
второе и третье сравнения в тривиальное сравнение (φ
φ, φ
φ) получим первое. Так как π
æ, то в конгруэнции
æ есть пара (e,φ)
(e,
)
æ. Из пары (e,
) с помощью основных операций можно получить любую пару из
π01. Таким образом, π01
æ.
Если
некоторая подарностная конгруэнция,
заданная на подклонах клона Z не содержится в æе, то по ней
сравнимы две разные функции, из которых хотя бы одна является проекцией.
Поэтому из перечисленных утверждений следует следующая теорема.
Теорема 1)На подклонах клона Z со свойствами и
, в частности на самом клоне Z, всего две конгруэнции π, π01 не содержатся в
æе, π
π01
æа.
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