close

Вход

Забыли?

вход по аккаунту

?

О максимальных клонах частичных ультрафункций на двухэлементном множестве.

код для вставкиСкачать
Серия «Математика»
2016. Т. 16. С. 3—18
Онлайн-доступ к журналу:
http://isu.ru/izvestia
ИЗВЕСТИЯ
Иркутского
государственного
университета
УДК 519.716
MSC 68R01
О максимальных клонах частичных
ультрафункций на двухэлементном множестве
С. А. Бадмаев, И. К. Шаранхаев
Бурятский государственный университет
Аннотация. Класс дискретных функций, определенных на конечном множестве
A и принимающих в качестве значений подмножества множества A, является естественным обобщением класса конечнозначных функций на A (функций k-значной
логики). Функции такого вида называют мультифункциями или мультиоперациями
на A, и они находят применение, например при решении функциональных уравнений, в логических и технических системах. Очевидно, что суперпозиция в обычном
смысле для работы с мультифункциями не подходит, поэтому для мультифункций
требуется несколько расширить стандартное понятие суперпозиции. Отметим, что
существуют различные способы определения операции суперпозиции мультифункций, один из таких способов рассматривается в этой работе. Мультифункции на A
с данной суперпозицией называют частичными ультрафункциями на A.
В данной статье в качестве исходного множества A рассматривается двухэлементное множество и исследуется классическая для теории дискретных функций
задача описания решетки так называемых клонов — множеств функций, замкнутых
относительно операции суперпозиции и содержащих все функции-проекции. С помощью предикатного подхода нам удалось дать описание двух максимальных клонов
частичных ультрафункций на двухэлементном множестве.
Ключевые слова: мультифункция, частичная ультрафункция, суперпозиция, максимальный клон, клон.
1. Основные понятия и определения
Пусть A = {0, 1} и F = {∅, {0}, {1}, {0, 1}}. Определим следующие
множества функций:
∗
∗ = {f |f : An → F }, P ∗ =
P2,n ,
P2,n
2
n
∗ и |f (α̃)| = 1 для всех α̃ ∈ An }, P =
P2,n .
P2,n = {f |f ∈ P2,n
2
n
4
С. А. БАДМАЕВ, И. К. ШАРАНХАЕВ
Функции из P2 называют булевыми функциями, из P2∗ – мультифункциями на A.
Для того чтобы суперпозиция f (f1 (x1 , . . . , xm ), . . . , fn (x1 , . . . , xm )),
где f, f1 , . . . , fn ∈ P2∗ , определяла мультифункцию g(x1 , . . . , xm ), следуя
[1; 5], определим значения мультифункции f на наборах из подмножеств
множества A следующим образом: если (α1 , . . . , αm ) ∈ Am , то
⎧
f (β1 , . . . , βn ), если пересечение не пусто;
⎪
⎨
βi ∈fi (α
1 ,...,αm )
g(α1 , . . . , αm ) =
f (β1 , . . . , βn ), в противном случае.
⎪
⎩
βi ∈fi (α1 ,...,αm )
На наборах, содержащих ∅, мультифункция принимает значение ∅.
Это определение позволяет вычислить значение f (x1 , . . . , xn ) на любом
наборе (σ1 , . . . , σn ) ∈ F n .
Если мультифункции на A рассматриваются с данной суперпозицией, то их называют частичными ультрафункциями на A.
В дальнейшем, если это не вызывает недоразумений, частичную ультрафункцию будем называть просто функцией. Наборы с элементами
из A будем называть двоичными.
Проекцией называется функция ein : (α1 , . . . , αi , . . . , αn ) → {αi }.
Отметим, что в настоящей работе мы будем придерживаться терминологии, принятой в [4], что позволит нам не вводить дополнительных
определений.
Клоном называется множество функций, замкнутое относительно
суперпозиции, добавления и удаления несущественных переменных, содержащее все проекции.
Клон K называется максимальным, если не существует клона K1
такого, что K ⊂ K1 ⊂ P2∗ . Заметим, что понятие максимального клона
соответствует понятию предполного класса.
Для упрощения записи используется следующая кодировка: ∅ ↔ ∗,
{0} ↔ 0, {1} ↔ 1, {0, 1} ↔ −, тогда F = {∗, 0, 1, −}.
Обозначим через P ol(R) класс функций, сохраняющих предикат R.
2. Вспомогательные утверждения
Приведем некоторые вспомогательные результаты.
Лемма 1. Пусть функции f, f1 , . . . , fs сохраняют предикат Rm , опре-
деленный на множестве F , функция g(x1 , . . . , xn ) есть суперпозиция
1
m
f (f1 , . . . , fs ) и двоичные наборы (α11 , . . . , αm
1 ), . . . , (αn , . . . , αn ) принадлежат Rm . Тогда набор
m
(g(α11 , . . . , α1n ), . . . , g(αm
1 , . . . , αn ))
принадлежит Rm .
Известия Иркутского государственного университета.
2016. Т. 16. Серия «Математика». С. 3–18
О МАКСИМАЛЬНЫХ КЛОНАХ ЧАСТИЧНЫХ УЛЬТРАФУНКЦИЙ
5
Доказательство. Следует из того, что для любого двоичного набора
(β1 , . . . , βn ) выполняется
g(β1 , . . . , βn ) = f (f1 (β1 , . . . , βn ), . . . , fs (β1 , . . . , βn )).
Введем в рассмотрение предикаты
⎛
0
⎝
0
R1 =
0
⎛
0
⎝
R2 = 0
0
⎞
0 1 1 1 1 1 − − 0 1 − ∗ ∗ ∗ ∗ ∗ ∗ ∗
1 0 1 1 1 − 1 − ∗ ∗ ∗ 0 1 − ∗ ∗ ∗ ∗⎠ ,
1 1 0 1 − 1 1 − ∗ ∗ ∗ ∗ ∗ ∗ 0 1 − ∗
⎞
0 0 1 1 0 0 − − 0 1 − ∗ ∗ ∗ ∗ ∗ ∗ ∗
0 1 0 1 0 − 0 − ∗ ∗ ∗ 0 1 − ∗ ∗ ∗ ∗⎠ .
1 0 0 1 − 0 0 − ∗ ∗ ∗ ∗ ∗ ∗ 0 1 − ∗
Доказательства приведенных ниже лемм 2 и 3 полностью совпадают
с доказательствами соответствующих утверждений из работы [4].
Лемма 2. Пусть f (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) сохраняет предикат
Rm и переменная xi несущественная. Тогда g(x1 , . . . , xi−1 , xi+1 , . . . , xn ),
полученная из f удалением несущественной переменной xi , сохраняет
предикат Rm .
Лемма 3. Пусть Rm – m-местный предикат и для любого набора
(β1 , . . . , βi1 , . . . , βi2 , . . . , βis , . . . , βm ) из Rm такого, что βi1 , βi2 , . . . , βis
и только они равны ∗, выполняется следующее условие: если набор
(γ1 , . . . , γi1 , . . . , γi2 , . . . , γis , . . . , γm ) принадлежит Rm , то набор
(δ1 , . . . , δi1 , . . . , δi2 , . . . , δis , . . . , δm ),
где δj = ∗ для j ∈ {i1 , i2 , . . . , is } и δj = γj для остальных j, также принадлежит Rm . Тогда, если g(x1 , . . . , xi−1 , xi+1 , . . . , xn ) сохраняет Rm , то f (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ), полученная из g добавлением
несущественной переменной xi , также сохраняет Rm .
Следствие 1. Класс P ol(R1 ) замкнут относительно добавления и
удаления несущественных переменных.
Пусть наборы α̃i = (αi1 , αi2 , . . . , αin ), где i ∈ {1, 2, 3} такие, что
(α1j , α2j , α3j )t ∈ R1 ,
где j ∈ {1, . . . , n}. Обозначим через α̃i,0 уточнение набора α̃i , в котором
все значения − заменили на 0, а через α̃i,1 — уточнение набора α̃i ,
в котором все значения − заменили на 1. Заметим, что для любого
i,1
i,1 t
t
уточнения τ̃ набора α̃i двоичные наборы (τj , αi,0
j , τj ) и (αj , τj , αj )
принадлежат предикату R1 .
6
С. А. БАДМАЕВ, И. К. ШАРАНХАЕВ
Лемма 4. Пусть h(x1 , . . . , xn ) = f (g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )),
где f, g1 , . . . , gm ∈ P ol(R1 ), наборы α̃i = (αi1 , αi2 , . . . , αin ), где i ∈ {1, 2, 3}
такие, что (α1j , α2j , α3j )t ∈ R1 , где j ∈ {1, . . . , n}. Если для некоторого k
имеем h(α̃k ) = 0, то выполняются следующие условия:
1) h(α̃k,0 ) = 0;
2) h(α̃k,1 ) ∈ {∗, 0}, причем если h(α̃k,1 ) = 0, то для любого уточнения τ̃ набора α̃k имеем h(τ̃ ) = 0.
Доказательство. Оба условия докажем от противного.
1) Так как случай h(α̃k,0 ) = 1 сразу невозможен, допустим, что
уточнение
δ̃ набора α̃k такое, что
h(α̃k,0 ) ∈ {∗, −}. Тогда
⎫
⎞ ⎧
⎛ существует
δ̃
⎨0 0⎬
⎝
h(δ̃) = 0. Отсюда h α̃k,0 ⎠ ∈ ∗ , − , противоречие лемме 1.
⎩
⎭
0 0
δ̃
2) Так как случай h(α̃k,1 ) = 1 также сразу невозможен, допустим,
k
что h(α̃k,1 ) = −. Тогда
⎞ ⎛ ⎞ уточнение δ̃ набора α̃ такое, что
⎛ k,1существует
α̃
−
⎝
h(δ̃) = 0. Отсюда h
δ̃ ⎠ = ⎝ 0 ⎠, противоречие лемме 1.
−
α̃k,1
k,1
k
Если h(α̃ ) = 0 и найдется⎛уточнение
⎫ α̃ такое, что выпол⎞ ⎧ τ̃ набора
k,1
α̃
⎨0 0⎬
няется h(τ̃ ) ∈ {∗, −}, тогда h ⎝ τ̃ ⎠ ∈ ∗ , − , противоречие.
⎩
⎭
0 0
α̃k,1
Лемма 5. Пусть h(x1 , . . . , xn ) = f (g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )),
где f, g1 , . . . , gm ∈ P ol(R1 ), наборы α̃i = (αi1 , αi2 , . . . , αin ), где i ∈ {1, 2, 3}
такие, что (α1j , α2j , α3j )t ∈ R1 , где j ∈ {1, . . . , n}. Если для некоторого k
имеем h(α̃k ) = 1, то выполняются следующие условия:
1) h(α̃k,0 ) ∈ {1, −}, причем если h(α̃k,0 ) = 1, то среди уточнений
набора α̃k нет таких, на которых значение функции h равно −;
2) h(α̃k,1 ) ∈ {∗, 1}, причем если h(α̃k,1 ) = 1, то среди уточнений
набора α̃k нет таких, на которых значение функции h равно ∗.
Доказательство. Оба утверждения докажем от противного.
1) Так как случай h(α̃k,0 ) = 0 сразу невозможен, допустим, что
уточнение δ̃ набора α̃k такое, что h(δ̃) = 1.
h(α̃k,0 ) = ∗.
⎞ существует
⎛ ⎞
⎛Тогда
δ̃
1
Отсюда h ⎝α̃k,0 ⎠ = ⎝∗⎠ , противоречие лемме 1.
1
δ̃
k,0
k
существует
Пусть h(α̃ ) =⎛1 и ⎞
⎛ ⎞ уточнение τ̃ набора α̃ такое, что
τ̃
−
⎝
h(τ̃ ) = −. Тогда h α̃k,0 ⎠ = ⎝ 1 ⎠ , противоречие лемме 1.
−
τ̃
Известия Иркутского государственного университета.
2016. Т. 16. Серия «Математика». С. 3–18
О МАКСИМАЛЬНЫХ КЛОНАХ ЧАСТИЧНЫХ УЛЬТРАФУНКЦИЙ
7
2) Так как случай h(α̃k,1 ) = 0 также сразу невозможен, допустим,
k
Тогда⎞существует
что h(α̃k,1 ) = −. ⎛
⎛ ⎞ уточнение δ̃ набора α̃ такое, что
k,1
α̃
−
h(δ̃) = 1. Тогда h ⎝ δ̃ ⎠ = ⎝ 1 ⎠ , противоречие лемме 1.
−
α̃k,1
k,1
уточнение τ̃ набора α̃k такое,
Теперь пусть h(α̃ ⎛) = 1⎞и найдется
⎛ ⎞
k,1
1
α̃
что h(τ̃ ) = ∗. Тогда h ⎝ τ̃ ⎠ = ⎝∗⎠ , противоречие лемме 1.
1
α̃k,1
Лемма 6. Пусть h(x1 , . . . , xn ) = f (g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )),
где f, g1 , . . . , gm ∈ P ol(R1 ), наборы α̃i = (αi1 , αi2 , . . . , αin ), где i ∈ {1, 2, 3}
такие, что (α1j , α2j , α3j )t ∈ R1 , где j ∈ {1, . . . , n}. Если для некоторого
k имеем h(α̃k ) = −, тогда совокупность значений h на всевозможных
уточнениях набора α̃k совпадает с одним из следующих вариантов:
1) {−};
2) {∗, −}, причем h(α̃k,0 ) = − и h(α̃k,1 ) = ∗;
3) {0, 1}, причем h(α̃k,0 ) = 0 и h(α̃k,1 ) = 1;
4) {∗, 1, −}, причем h(α̃k,0 ) = − и h(α̃k,1 ) = ∗;
5) {∗, 0, 1}, причем h(α̃k,0 ) = 0 и h(α̃k,1 ) = ∗.
Доказательство. Сначала докажем от противного, что совокупность
значений h на всевозможных уточнениях набора α̃k не совпадает ни с
одним из отставшихся вариантов: а) {∗, 0, −}, б) {0, 1, −}, в) {∗, 0, 1, −}.
а) Пусть совокупностью значений функции h на всевозможных уточ−}. ⎛ ⎞
нениях набора α̃k является⎛{∗, 0,⎞
τ̃
−
/ R1 , где τ̃ — уточнение
Если h(α̃k,0 ) = 0, то h ⎝α̃k,0 ⎠ = ⎝ 0 ⎠ ∈
−
τ̃
1.
набора α̃k такое, что h(τ̃ ) = −, противоречие
⎧лемме ⎫
⎞
⎛
τ̃
0
0
⎨
⎬
− , ∗
∈
/ R1 , где τ̃ —
Если h(α̃k,0 ) ∈ {−, ∗}, то h ⎝α̃k,0 ⎠ ∈
⎩
⎭
0 0
τ̃
уточнение набора α̃k такое, что h(τ̃ ) = 0, противоречие лемме 1.
б) Пусть совокупностью значений функции h на всевозможных уточ−}. ⎛ ⎞
нениях набора α̃k является⎛{0, 1,⎞
τ̃
−
k,0
k,0
⎠
⎝
⎝
0⎠ ∈
=
/ R1 , где τ̃ — уточнение
Если h(α̃ ) = 0, то f α̃
−
τ̃
1.
набора α̃k такое, что h(τ̃ ) = −, противоречие
⎧лемме ⎫
⎞
⎛
τ̃
⎨0 0⎬
1 , −
∈
/ R1 , где τ̃ —
Если h(α̃k,0 ) ∈ {1, −}, то h ⎝α̃k,0 ⎠ ∈
⎩
⎭
0 0
τ̃
уточнение набора α̃k такое, что h(τ̃ ) = 0, противоречие лемме 1.
8
С. А. БАДМАЕВ, И. К. ШАРАНХАЕВ
в) Пусть совокупностью значений функции h на всевозможных уточ1, −}.⎛ ⎞
нениях набора α̃k является⎛{∗, 0,⎞
τ̃
−
/ R1 , где τ̃ — уточнение
Если h(α̃k,0 ) = 0, то h ⎝α̃k,0 ⎠ = ⎝ 0 ⎠ ∈
−
τ̃
набора α̃k такое, что h(τ̃ ) = −, противоречие
⎞ ⎧ лемме 1. ⎫
⎛
τ̃
⎨0 0 0⎬
k,0
k,0
⎠
⎝
Если h(α̃ ) ∈ {1, −, ∗}, то h α̃
∈ 1 , − , ∗ ∈
/ R1 , где τ̃ —
⎩
⎭
0 0 0
τ̃
уточнение набора α̃k такое, что h(τ̃ ) = 0, противоречие лемме 1.
Далее от противного докажем справедливость вариантов 2)–5). В
каждом случае получим противоречие с леммой 1.
= ∗, то
уточнение τ̃ набора α̃k такое, что
2) Если h(α̃k,0 ) ⎛
⎞ существует
⎛ ⎞
τ̃
−
k,0
⎠
⎝
⎝
= ∗⎠ ∈
/ R1 , противоречие.
h(τ̃ ) = −. Тогда h α̃
−
τ̃
уточнение τ̃ набора α̃k такое, что
Если h(α̃k,1 ) =⎛−, то⎞существует
⎛ ⎞
k,1
−
α̃
/ R1 , противоречие.
h(τ̃ ) = ∗. Тогда h ⎝ τ̃ ⎠ = ⎝ ∗ ⎠ ∈
−
α̃k,1
= 1, то
уточнение τ̃ набора α̃k такое, что
3) Если h(α̃k,0 )⎛
⎞ существует
⎛ ⎞
τ̃
0
k,0
⎠
⎝
⎝
= 1⎠ ∈
/ R1 , противоречие.
h(τ̃ ) = 0. Тогда h α̃
0
τ̃
уточнение τ̃ набора α̃k такое, что
Если h(α̃k,1 ) =⎛0, то⎞существует
⎛
⎞
0
α̃k,1
⎝
τ̃ ⎠ = ⎝1⎠ ∈
/ R1 , противоречие.
h(τ̃ ) = 1. Тогда h
0
α̃k,1
уточнение τ̃ набора α̃k такое,
4) Если h(α̃k,0 ) ∈ {∗,⎛1}, то
⎧
⎫
⎞ существует
τ̃
⎨− − ⎬
/ R1 , противоречие.
что h(τ̃ ) = −. Тогда h ⎝α̃k,0 ⎠ ∈ ∗ , 1 ∈
⎩
⎭
− −
τ̃
−}, то⎞существует
уточнение τ̃ набора α̃k такое,
Если h(α̃k,1 ) ∈ {1, ⎛
⎧
⎫
α̃k,1
⎨1 −⎬
⎝
τ̃ ⎠ ∈ ∗ , ∗ ∈
/ R1 , противоречие.
что h(τ̃ ) = ∗. Тогда h
⎩
⎭
1 −
α̃k,1
k
5) Если h(α̃k,0 ) ∈ {∗,
⎧
⎫ уточнение τ̃ набора α̃ такое,
⎞ существует
⎛1}, то
τ̃
⎨0 0⎬
/ R1 , противоречие.
что h(τ̃ ) = 0. Тогда h ⎝α̃k,0 ⎠ ∈ ∗ , 1 ∈
⎩
⎭
0 0
τ̃
Известия Иркутского государственного университета.
2016. Т. 16. Серия «Математика». С. 3–18
О МАКСИМАЛЬНЫХ КЛОНАХ ЧАСТИЧНЫХ УЛЬТРАФУНКЦИЙ
9
k
1}, то⎞существует
Если h(α̃k,1 ) ∈ {0, ⎛
⎧
⎫уточнение τ̃ набора α̃ такое,
k,1
α̃
⎨0 1⎬
/ R1 , противоречие.
что h(τ̃ ) = ∗. Тогда h ⎝ τ̃ ⎠ ∈ ∗ , ∗ ∈
⎩
⎭
0 1
α̃k,1
Лемма 7. Пусть h(x1 , . . . , xn ) = f (g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )),
где f, g1 , . . . , gm ∈ P ol(R1 ), наборы α̃i = (αi1 , αi2 , . . . , αin ), где i ∈ {1, 2, 3}
такие, что (α1j , α2j , α3j )t ∈ R1 , где j ∈ {1, . . . , n}. Если для некоторого k
имеем h(α̃k ) = ∗, то на всех уточнениях набора α̃k значение функции
h равно ∗.
Доказательство. Следует из определения суперпозиции.
Лемма 8. Следующие множества совпадают с P2∗ :
1) [{(1∗), (1−)}]; 2) [{(∗0), (−0)}];
3) [{(0−), (−1), (0∗)}]; 4) [{(0−), (−1), (∗0)}].
Доказательство. Пункты 1) и 2) доказаны в [2].
3) Множество {(0−), (−1), (0∗)} сведем к {(1∗),
(1−)}.
− −
1
. С помощью
Из функции (−1) получим константу 1:
=
1
1 1
1 0
1 0 1
−
константы 1 получим функции (1∗) и (−−):
=
,
=
.
1
∗
∗
−
1
−
⎛
⎞ ⎛ ⎞ ⎛
⎞ ⎛ ⎞
0 − 0
− − − 0
1
⎟ ⎜ ∗ ⎟ ∗ ⎜− 0 ⎟ ⎜ 1 ⎟
0⎜
−
∗
⎟=⎜ ⎟; ⎜
⎟=⎜ ⎟.
И далее ⎜
1⎝ 1 0⎠ ⎝ 1 ⎠ 1 ⎝− −⎠ ⎝−⎠
1 1 ∗
∗
∗ − −
−
(−0)}.
4) Множество {(0−), (−1), (∗0)} сведем к {(∗0),
− −
1
Из функции (−1) получим константу 1:
=
. С помощью
1 1
1
0 1
−
константы 1 получим (−−):
=
.
−
1
−
⎞ ⎛ ⎞
⎛
⎞ ⎛ ⎞ ⎛
−
0 0 ∗
∗
∗ − −
⎟
⎜
⎜
⎟
⎜
⎟
⎜
0 − ∗⎟ ⎜ ∗ ⎟ ∗ ⎜− −⎟ ⎜−⎟
⎟.
=
И далее ⎜
=
;
1⎝ 0 0⎠ ⎝ 0 ⎠ 0 ⎝ 1 −⎠ ⎝ 0 ⎠
0
1 − 0
− − 1 −
Лемма 9. Верно, что [P ol(R1 ) {f }] = P2∗ , где f ∈ {(0−), (10), (1−),
(−0), (∗0), (∗1), (∗−), (000∗), (0001), (− − −1), (− − −∗)}.
Доказательство. Нетрудно убедиться, что функции (00), (01), (0∗),
(11), (1∗), (−1), (−−), (−∗),
сохраняют предикат R1 .
(∗∗),
(0111),
(−111)
− 1
1
− −
0
В силу того, что
=
и
=
справедливость утвер1 0
−
0 0
−
ждения при f ∈ {(0−), (10), (1−), (−0)} следует из леммы 8.
10
С. А. БАДМАЕВ, И. К. ШАРАНХАЕВ
Если f = (∗0), то следующая
последовательность
⎛
⎞ ⎛
⎞ ⎛
⎞ ⎛ ⎞суперпозиций
⎛
⎞ ⎛при⎞
∗ 0 0
∗ 0 0 ∗
∗ ∗ − 0
1
⎜ ⎟ ⎜
⎟ ⎜ ⎟ ⎜
⎟ ⎜ ⎟
∗⎜1 0⎟
⎟=⎜0⎟; 0⎜0 0⎟=⎜0⎟; 0⎜ 1 0⎟=⎜ 1 ⎟;
ведет к функции (0−): ⎜
0⎝1 0⎠ ⎝0⎠ 1⎝1 0⎠ ⎝1⎠ 1⎝− 1⎠ ⎝−⎠
0 1 0
0 1 1 0
1 1 1 1
1
⎞ ⎛ ⎞ ⎛
⎞ ⎛ ⎞ ⎛
⎞ ⎛ ⎞ ⎛
⎞ ⎛ ⎞
⎛
− 0 − 0
0 0 0 0
0 0 − 0
0
1 1 0
⎟ ⎜ ⎟ ⎜
⎟ ⎜ ⎟ ⎜
⎟ ⎜ ⎟ ⎜
⎟ ⎜ ⎟
1⎜
⎜ 1 0⎟=⎜−⎟; 0⎜− 0⎟=⎜0⎟; 0⎜0 0⎟=⎜0⎟; 0⎜− 0⎟=⎜ 0 ⎟.
⎠
⎝
⎠
⎝
⎠
⎝
⎠
⎝
⎠
⎝
⎠
⎝
⎝
1
∗ 1 0
∗ 1 1 ∗
∗ ∗ − 1⎠ ⎝−⎠
− − 0
−
− ∗ − 0
0 1 1 0
1 1 − 1
1 1 0
Если f ∈ {(∗1), (∗−)}, то применяя операцию суперпозиции к функциям (00) и f получим функцию (∗0).
функцию (−0): ⎛
⎞ ⎛ ⎞
⎛Если⎞f =
⎛ (000∗),
⎞ ⎛ то можно
⎞ ⎛ получить
⎞
0
0 0 0
0 0 − 0
−
0 0 −
⎟ ⎜0⎟ 0⎜− 0⎟ ⎜−⎟
⎜0 −⎟ ⎜ 0 ⎟
0⎜
0
0
0
⎟=⎜ ⎟.
⎜
⎟=⎜ ⎟; ⎜
⎟=⎜ ⎟. Если f = (0001), то ⎜
1⎝1 0⎠ ⎝1⎠ 1⎝− 1⎠ ⎝ 0 ⎠
0⎝1 −⎠ ⎝−⎠
−
1 1 ∗
∗ ∗ − 1
0
1 1 −
⎛
⎞ ⎛ ⎞
⎛
⎞ ⎛ ⎞
0 − 0
0
0 0 −
0
⎜
⎟
⎜
⎟
⎜
⎟
⎜
0 − 0⎟ ⎜0⎟ 0⎜0 −⎟ ⎜0⎟
Если f ∈ {(− − −1), (− − −∗)}, то ⎜
=
и
= ⎟.
∗⎝− 0⎠ ⎝0⎠ 0⎝0 −⎠ ⎝0⎠
∗ 1 0
∗
0 0 ∗
∗
3. Описание максимальных клонов
В [5] описаны два максимальных клона частичных ультрафункций
на конечном множестве. В этом разделе с помощью отношения сохранения предиката функцией получено описание двух новых максимальных
клонов частичных ультрафункций на двухэлементном множестве.
Теорема 1. Класс P ol(R1 ) является клоном.
Доказательство. По следствию 1 класс P ol(R1 ) замкнут относительно
добавления и удаления несущественных переменных, и очевидно, что
функция e21 = (01) сохраняет R1 . Таким образом, остается доказать,
что класс P ol(R1 ) замкнут относительно суперпозиции. От противного.
Пусть
h(x1 , . . . , xn ) = f (g1 (x1 , . . . , xn ), g2 (x1 , . . . , xn ) . . . , gm (x1 , . . . , xn )),
где f, g1 , . . . , gm — произвольные функции из класса P ol(R1 ).
i ), где i ∈ {1, 2, 3},
. . , α⎞
Допустим, существуют наборы α̃i = (αi1 , . ⎛
n
⎛ 1⎞
α̃1
α̃
/ R1 , т. е. h ⎝α̃2 ⎠
такие, что (α1j , α2j , α3j )t ∈ R1 для любого j, но h ⎝α̃2 ⎠ ∈
α̃3
α̃3
Известия Иркутского государственного университета.
2016. Т. 16. Серия «Математика». С. 3–18
11
⎛ ⎞ ⎛ ⎞ ⎛ ⎞
0
0
1
⎝
⎠
⎝
⎠
⎝
должен совпадать с одним из следующих столбцов: 0 , 1 , 0⎠,
1
0
0
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
0
0
−
0
0
1
1
−
−
0
⎝ 0 ⎠, ⎝−⎠, ⎝ 0 ⎠, ⎝ 1 ⎠, ⎝−⎠, ⎝ 0 ⎠, ⎝−⎠, ⎝ 0 ⎠, ⎝ 1 ⎠, ⎝−⎠,
−
0
0
−
1
−
0
1
0
−
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
−
−
1
−
−
μ
μ
∗
⎝ 0 ⎠, ⎝−⎠, ⎝−⎠, ⎝ 1 ⎠, ⎝−⎠, ⎝ η ⎠, ⎝ ∗ ⎠, ⎝μ⎠, где μ, η ∈ {0, 1, −}.
−
0
−
−
1
∗
η
η
i
i
i
Отметим, что ⎛
наборы
⎞ α̃ = (α1 , . . . , αn ), где i ∈ {1, 2, 3}, не содержат
α̃1
∗, иначе набор h ⎝α̃2 ⎠ ∈ R1 . Так как перестановка строк R1 не меняет
α̃3
⎛ 1⎞
α̃
его, достаточно рассмотреть случаи, когда h ⎝α̃2 ⎠ совпадает с одним
α̃3
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
0
0
0
0
−
μ
из столбцов: ⎝0⎠, ⎝ 0 ⎠, ⎝ 1 ⎠, ⎝−⎠, ⎝ 1 ⎠, ⎝ η ⎠, где μ, η ∈ {0, 1, −}.
1
−
−
−
−
∗
Рассмотрим
Всюду получаем противоречие
⎫
⎛ варианты.
⎞
⎛ 1,0 ⎞ ⎧лемме 1.
⎛ 1 ⎞ все
0
α̃
α̃
⎨0 0⎬
I. h ⎝α̃2 ⎠ = ⎝0⎠. В силу лемм 4, 5 имеем h ⎝α̃2,0 ⎠ ∈ 0 , 0 ,
⎩
⎭
α̃3
α̃3,0
1
1 −
противоречие.
⎛ ⎞
⎛ 1⎞
0
α̃
II. h ⎝α̃2 ⎠ = ⎝ 0 ⎠. 1. Допустим, на любом уточнении набора α̃3
−
α̃3
функция
h
принимает
значение ∗ или −. Тогда в силу лемм 4, 6 имеем
⎛ 1,0 ⎞ ⎛ ⎞
0
α̃
/ R1 , противоречие.
h ⎝α̃2,0 ⎠ = ⎝ 0 ⎠ ∈
α̃3,0
−
3
значение
2. Допустим, на любом уточнении
⎫
⎞ ⎧ h принимает
⎛ α̃1,0функция
α̃
⎨0 0⎬
0 или 1. В силу лемм 4, 6 имеем h ⎝α̃2,1 ⎠ ∈ 0 , ∗ , противоречие.
⎩
⎭
1 1
α̃3,1
3 функция h принимает значение
3. Допустим, на любом уточнении α̃⎛
⎞ ⎛ ⎞
0
α̃1,0
∗, 1 или −. В силу лемм 4, 6 имеем h ⎝α̃2,0 ⎠ = ⎝ 0 ⎠, противоречие.
α̃3,0
−
3
h принимает⎫значение
4. Допустим, на любом уточнении α̃⎛функция
⎞ ⎧
α̃1,0
⎨0 0 0⎬
∗, 0 или 1. Тогда по лемме 4 имеем h ⎝ δ̃ ⎠ ∈ 0 , ∗ , − , где τ̃ –
⎩
⎭
1 1 1
τ̃
О МАКСИМАЛЬНЫХ КЛОНАХ ЧАСТИЧНЫХ УЛЬТРАФУНКЦИЙ
12
С. А. БАДМАЕВ, И. К. ШАРАНХАЕВ
уточнение набора α̃3 такое, что h(τ̃ ) = 1, а δ̃ – уточнение набора α̃2 ,
t
при котором для всех i ∈ {1, . . . , n} двоичный набор (α1,0
i , δi , τi ) ∈ R1 .
Противоречие.
⎛ ⎞
⎛ 1⎞
0
α̃
2
⎠
⎝
⎝
= 1 ⎠. 1. Допустим, на любом уточнении набора α̃3
III. h α̃
3
α̃
−
функция
h
принимает
⎫ значение ∗ или −. В силу лемм 4, 5, 6 имеем
⎛ 1,0 ⎞ ⎧
α̃
⎨0 0⎬
h ⎝α̃2,0 ⎠ ∈ 1 , − . Противоречие.
⎩
⎭
− −
α̃3,0
значение
2. Допустим, на любом уточнении⎛α̃3 функция
⎫
⎞ ⎧ h принимает
α̃1,0
⎨0 0⎬
0 или 1. В силу лемм 4, 5, 6 имеем h ⎝α̃2,0 ⎠ ∈ 1 , − . Противоречие.
⎩
⎭
α̃3,0
0 0
h⎞
принимает
зна3. Допустим, на любом уточнении α̃3 функция
⎧
⎫
⎛ 1,0
0
0
α̃
⎨
⎬
1 , − .
чение ∗, 1 или −. В силу лемм 4, 5, 6 имеем h ⎝α̃2,0 ⎠ ∈
⎩
⎭
α̃3,0
− −
Противоречие.
4. Допустим, на любом уточнении набора α̃3 функция
⎧
⎫
⎛ 1,0 ⎞ h принимает
α̃
⎨0 0⎬
значение ∗, 0 или 1. В силу лемм 4, 5, 6 имеем h ⎝α̃2,0 ⎠ ∈ 1 , − .
⎩
⎭
α̃3,0
0 0
Противоречие.
⎛ ⎞
⎛ 1⎞
0
α̃
IV. h ⎝α̃2 ⎠ = ⎝−⎠. 1. Допустим, на любом уточнении набора α̃2
−
α̃3
функция
h
принимает
⎫ значение ∗ или −. Тогда в силу лемм 4, 6 имеем
⎛ 1,0 ⎞ ⎧
α̃
⎨0 0⎬
h ⎝α̃2,0 ⎠ ∈ − , − . Противоречие.
⎩
⎭
α̃3,0
0 −
2. Допустим, на любом уточнении набора α̃2 функция h принимает
3
значение 0 или 1. Если среди уточнений
⎞ ⎛ α̃ ⎞нет таких, на которых
⎛ 1,0набора
0
α̃
значение функции h равно 0, то h ⎝α̃2,0 ⎠ = ⎝ 0 ⎠, противоречие. Если
−
α̃3,0
3
же среди уточнений набора α̃ имеются такие, на которых значение
функции h равно 0, то возможны два случая:
⎫
⎛ 2,0 ⎞ ⎧
α̃
⎨0 0⎬
а) h(α̃3,1 ) = 1. В силу лемм 4, 6 имеем h ⎝α̃1,1 ⎠ ∈ ∗ , 0 , проти⎩
⎭
1 1
α̃3,1
воречие.
Известия Иркутского государственного университета.
2016. Т. 16. Серия «Математика». С. 3–18
13
⎞
⎛
⎞
α̃1,0
0
2,1
3,1
⎝
⎠
⎝
= 1⎠, противоречие.
б) h(α̃ ) = ∗. Аналогично, h α̃
3,1
α̃
∗
3. Допустим, на любом уточнении
набора
α̃2 функция
⎫ h принимает
⎛ 1,0 ⎞ ⎧
α̃
0
0
⎨
⎬
значение ∗, 1 или −. Аналогично, h ⎝α̃2,0 ⎠ ∈ − , − , противоречие.
⎩
⎭
0 −
α̃3,0
4. Допустим, на любом уточнении набора α̃2 функция h принимает
значение ∗, 0 или 1.
значеа) Если на любом уточнении набора α̃⎛3 функция
⎞ ⎛h принимает
⎞
0
α̃1,0
ние ∗ или −, то в силу лемм 4, 6 имеем h ⎝α̃2,0 ⎠ = ⎝ 0 ⎠, противоречие.
α̃3,0
−
3
функция
h
принимает значеб) Если на любом уточнении
набора
α̃
⎫
⎛ 2,0 ⎞ ⎧
0
0
α̃
⎨
⎬
ние 0 или 1, то аналогично, h ⎝α̃1,1 ⎠ ∈ ∗ , 0 , противоречие.
⎩
⎭
α̃3,1
1 1
в) Если на любом уточнении набора
α̃3 функция
⎛ ⎞ h принимает значе⎛ 1,0 ⎞
0
α̃
ние ∗, 1 или −, то аналогично, h ⎝α̃2,0 ⎠ = ⎝ 0 ⎠, противоречие.
−
α̃3,0
3
h принимает
знаг) Если на любом уточнении набора
⎧
⎫
⎛ α̃ ⎞функция
⎨∗ 0 − ⎬
δ̃
0 , 0 , 0 , где τ̃ –
чение ∗, 0 или 1, то аналогично, h ⎝α̃2,0 ⎠ ∈
⎩
⎭
1 1 1
τ̃
уточнение набора α̃3 такое, что h(τ̃ ) = 1, а δ̃ – уточнение набора α̃1 ,
t
при котором для всех i ∈ {1, . . . , n} двоичный набор (δi , α2,0
i , τi ) принадлежит
1 . Противоречие.
⎞
⎛ ⎞
⎛ R
−
α̃1
2
⎠
⎝
⎝
1 ⎠. 1. Допустим, на любом уточнении набора α̃1
=
V. h α̃
3
α̃
−
функция h принимает значение ∗ или −.
а) Если на любом уточнении набора α̃3 функция
⎧
⎫ зна⎛ 1,0 ⎞ h принимает
α̃
−⎬
⎨−
1 , 1 , где
чение ∗ или −, то в силу лемм 4, 6 имеем h ⎝ τ̃ ⎠ ∈
⎩
⎭
∗ −
δ̃
τ̃ – уточнение набора α̃2 такое, что h(τ̃ ) = 1, а δ̃ – уточнение набора
t
α̃3 , при котором для всех i ∈ {1, . . . , n} двоичный набор (α1,0
i , τi , δi )
принадлежит R1 . Противоречие.
3
б) Если на любом уточнении
⎫ h принимает значе⎞ α̃⎧ функция
⎛ набора
1,0
α̃
⎨− − ⎬
ние 0 или 1, то аналогично, h ⎝α̃2,0 ⎠ ∈ 1 , − . Противоречие.
⎩
⎭
α̃3,0
0 0
О МАКСИМАЛЬНЫХ КЛОНАХ ЧАСТИЧНЫХ УЛЬТРАФУНКЦИЙ
⎛
14
С. А. БАДМАЕВ, И. К. ШАРАНХАЕВ
в) Допустим, на любом уточнении набора α̃3 функция h принимает
значение ∗, 1 или −. Теперь
используем
⎛ 1,0
⎞ ⎛ ⎞лемму 5.
α̃
−
Если h(α˜2,0 ) = 1, то h ⎝α̃2,0 ⎠ = ⎝ 1 ⎠ по лемме 6. Противоречие.
α̃3,0
−
⎫
⎛ 2,0 ⎞ ⎧
α̃
⎨− − ⎬
Если же h(α˜2,0 ) = −, то h ⎝ δ̃ ⎠ ∈ ∗ , − , где τ̃ – уточнение
⎩
⎭
1 1
τ̃
набора α̃3 такое, что h(τ̃ ) = 1, а δ̃ – уточнение набора α̃1 , при котором
t
для всех i ∈ {1, . . . , n} двоичный набор (α2,0
i , δi , τi ) принадлежит R1 .
Противоречие.
г) Если на любом⎛уточнении
набора⎫
α̃3 функция h принимает значе⎧
⎞
α̃1,0
⎨− − ⎬
⎝
ние ∗, 0 или 1, то h α̃2,0 ⎠ ∈ 1 , − по лемме 6, противоречие.
⎩
⎭
α̃3,0
0 0
1
принимает значение
2. Допустим, на любом
⎞ ⎧ α̃ функция h⎫
⎛ уточнении
1,0
α̃
⎨0 0 0 0⎬
0 или 1. Аналогично, h ⎝α̃2,0 ⎠ ∈ 1 , 1 , − , − , противоречие.
⎩
⎭
α̃3,0
0 −
0 −
3. Допустим, на любом уточнении набора α̃1 функция h принимает
значение ∗, 1 или −.
а) Допустим, на любых уточнениях набора α̃3 функция h принимает
значение ∗ или −. Теперь⎛используем
5.
⎞ ⎛ лемму
⎞
α̃1,0
−
Если h(α˜2,0 ) = 1, то h ⎝α̃2,0 ⎠ = ⎝ 1 ⎠ по лемме 6, противоречие.
α̃3,0
−
⎫
⎞ ⎧
⎛
τ̃
⎨1 1⎬
Если же h(α˜2,0 ) = −, то h ⎝α̃2,0 ⎠ ∈ − , − , где τ̃ – уточнение
⎩
⎭
∗ −
δ̃
набора α̃1 такое, что h(τ̃ ) = 1, а δ̃ – уточнение набора α̃3 , при котором
t
для всех i ∈ {1, . . . , n} двоичный набор (τi , α2,0
i , δi ) принадлежит R1 .
Противоречие.
3
б) Если на любом
уточнении
⎫ α̃ функция h принимает значе⎞ ⎧ набора
⎛ 1,0
−⎬
α̃
⎨−
2,0
⎠
⎝
∈ 1 , − по лемме 6, противоречие.
ние 0 или 1, то h α̃
⎩
⎭
α̃3,0
0 0
в) Допустим, на любых уточнениях набора α̃3 функция h принимает
значение ∗, 1 или −.
в1) Если на
набора α̃2 функция h принимает зна⎞ уточнении
⎛ ⎞
⎛ любом
1,0
−
α̃
чение 1, то h ⎝α̃2,0 ⎠ = ⎝ 1 ⎠ по лемме 6, противоречие.
α̃3,0
−
Известия Иркутского государственного университета.
2016. Т. 16. Серия «Математика». С. 3–18
О МАКСИМАЛЬНЫХ КЛОНАХ ЧАСТИЧНЫХ УЛЬТРАФУНКЦИЙ
15
h принимает значев2) Если на любом уточнении
набора
α̃2 функция
⎛ 1,0
⎞ ⎛
⎞
α̃
−
ние ∗ или 1, то h(α˜2,0 ) = 1 и h ⎝α̃2,0 ⎠ = ⎝ 1 ⎠ по лемме 5, противоречие.
α̃3,0
−
2
h принимает значение 1
в3) Если на любом уточнении
⎛ 1,0 ⎞ α̃ ⎛функция
⎞
α̃
−
или −, то h(α˜2,1 ) = 1 и h ⎝α̃2,1 ⎠ = ⎝ 1 ⎠ по лемме 5, противоречие.
∗
α̃3,1
3
г) Если на любом⎛уточнении
набора
⎫α̃ функция h принимает значе⎞ ⎧
1,0
α̃
⎨− − ⎬
2,0
⎠
⎝
∈ 1 , − по леммам 5, 6. Противоречие.
ние ∗, 0 или 1, то h α̃
⎩
⎭
α̃3,0
0 0
h принима4. Допустим, на любых уточнениях набора
α̃1 функция
⎧
⎫
⎛ 1,0 ⎞
0
0
0 0⎬
α̃
⎨
1 , 1 , − , − ,
ет значение ∗, 0 или 1. Аналогично, h ⎝α̃2,0 ⎠ ∈
⎩
⎭
0 − 0 −
α̃3,0
противоречие.
⎛ 1⎞ ⎛ ⎞
μ
α̃
2
⎠
⎝
⎝
= η ⎠, где μ, η ∈ {0, 1, −}. Тогда в силу лемм 4, 5, 6, 7
VI. h α̃
3
α̃
∗
⎛ 1,0 ⎞ ⎛ ⎞
α̃
γ
имеем h ⎝α̃2,0 ⎠ = ⎝ δ ⎠, где γ, δ ∈ {0, 1, −}, противоречие.
∗
α̃3,0
Теорема 2. Клон P ol(R1 ) является максимальным.
Доказательство. Покажем, что множество [P ol(R1 ) {f }] совпадает с
P2∗ , где f не сохраняет предикат R1 . В силу того, что перестановка
строк в ⎛
предикате R1 не меняет⎞его, достаточно рассмотреть случаи,
0 0 1 1 1 1 1 − −
когда f ⎝0 1 0 1 1 1 − 1 −⎠ будет равен одному из следующих
0 1 1 0 1 − 1 1 −
⎛ ⎞
⎛ ⎞
⎛ ⎞
⎛ ⎞
⎛ ⎞
⎛ ⎞
0
0
0
0
−
μ
вариантов: I) ⎝0⎠, II) ⎝ 0 ⎠, III) ⎝ 1 ⎠, IV) ⎝−⎠, V) ⎝−⎠ и VI) ⎝ η ⎠,
1
−
−
−
1
∗
где μ, η⎛∈ {0, 1, −}.
⎞ ⎛ ⎞
0 0 1 1 1 1 1 − −
0
I. f ⎝0 1 0 1 1 1 − 1 −⎠=⎝0⎠. Тогда f (00000 − − − −) = 0
0 1 1 0 1 − 1 1 −
1
0 0 0 0 0 − − − −
и f (01111111−) ∈ {∗, 1}, иначе получим f
∈
0 0 1 1 1 1 1 − −
1
−
∗
0 1 1 0 1 − 1 1 −
1
1
;
;
и f
∈
;
, по
0
0
0
0 1 1 1 1 1 1 1 −
0
−
лемме 9 имеем [P ol(R1 ) {f }] = P2∗ .
16
С. А. БАДМАЕВ, И. К. ШАРАНХАЕВ
⎛
0 0 0 0 0 − −
⎜0 0 1 1 1 1 1
Но тогда f ⎜
⎝0 1 0 1 1 1 −
0 1 1 1 1 1 1
∗
9 имеем [P ol(R
⎛ 1 ) {f }] = P2 .
0 0 1 1 1 1 1 −
II–IV. f ⎝0 1 0 1 1 1 − 1
0 1 1 0 1 − 1 1
−
−
1
1
⎞
⎛ ⎞
⎛ ⎞
−
0
0
⎟
⎜
⎟
⎜
−⎟
0⎟
0⎟
⎟. По лемме
равен ⎜
или ⎜
⎠
⎝
⎠
⎝
−
0
0⎠
−
∗
1
⎫
⎞ ⎧
−
⎨0 0 0⎬
−⎠ ∈ 0 , 1 , − .
⎩
⎭
−
− − −
0 0 0 0 0 − − − −
Если f (00000 − − − −) ∈ {∗, 1, −}, то f
∈
0 0 1 1 1 1 1 − −
∗
1
−
;
;
, а в случае f (00000 − − − −) = 0 получим, что
0
0
0
0 0 0 0 0 − − − −
0
f
=
. По лемме 9 [P ol(R1 ) {f }] = P2∗ .
0 1 1 0 1 − 1 1 −
−
⎛
⎞ ⎛ ⎞
0 0 1 1 1 1 1 − −
−
⎝
⎠
⎝
V. f 0 1 0 1 1 1 − 1 − = −⎠. Тогда f (00000 − − − −) = −,
0 1 1 0 1 − 1 1 −
1
0 0 0 0 0 − − − −
∗
0 0 0 0 0 − − − −
иначе f
=
иf
∈
0 1 1 0 1 − 1 1 −
1
0 0 1 1 1 1 1 − −
0
1
;
, по лемме 9 имеем [P ol(R1 ) {f }] = P2∗ .
−
−
0 1 1 0 1 − 1 1 −
Если f (01111111−) ∈ {0, −}, то получаем f
∈
0 1 1 1 1 1 1 1 −
1
1
;
, по лемме 9 имеем [P ol(R1 ) {f }] = P2∗ .
0
−⎛
⎞
⎛ ⎞
⎛ ⎞
0 0 0 0 0 − − − −
−
−
⎜0 0 1 1 1 1 1 − −⎟
⎜−⎟
⎜−⎟
⎟
⎜ ⎟
⎜ ⎟
Тогда f ⎜
⎝0 1 0 1 1 1 − 1 −⎠ равен ⎝−⎠ или ⎝−⎠, по лемме
0 1 1 1 1 1 1 1 −
∗
1
∗
9 имеем ⎛
[P ol(R1 ) {f }] = P2 . ⎞ ⎛ ⎞
0 0 1 1 1 1 1 − −
μ
⎝
⎠
⎝
VI. f 0 1 0 1 1 1 − 1 − = η ⎠, где μ, η ∈ {0, 1, −}.
0 1 1 0 1 − 1 1 −
∗
Тогда f (00000−−−−) = α и f (01111111−)= ∗, где α ∈ {0, 1, −}. Дей
0 0 0 0 0 − − − −
ствительно, если f (00000 − − − −) = ∗, то f
∈
0 0 1 1 1 1 1 − −
∗
∗
∗
;
;
, по лемме 9 имеем [P ol(R1 ) {f }] = P2∗ .
0
1
−
0 1 1 0 1 − 1 1 −
В случае f (01111111−) ∈ {0, 1, −}, то имеем f
∈
0 1 1 1 1 1 1 1 −
∗
∗
∗
;
;
, по лемме 9 [P ol(R1 ) {f }] = P2∗ .
0
1
−
Известия Иркутского государственного университета.
2016. Т. 16. Серия «Математика». С. 3–18
17
⎛
⎞ ⎛ ⎞
0 0 0 0 0 − − − −
α
⎜0 0 1 1 1 1 1 − −⎟ ⎜μ⎟
⎟ ⎜ ⎟
Следовательно, f ⎜
⎝0 1 0 1 1 1 − 1 −⎠=⎝ η ⎠, где α, μ, η ∈ {0, 1, −}.
0 1 1 1 1 1 1 1 −
∗
⎛
⎞ ⎛ ⎞
− α 0
−
⎟ ⎜−⎟
−⎜
μ
0
⎟=⎜ ⎟, по лемме 9 [P ol(R1 ) {f }] = P ∗ .
Отсюда получаем ⎜
2
−⎝ η 0⎠ ⎝−⎠
− ∗ 0
∗
О МАКСИМАЛЬНЫХ КЛОНАХ ЧАСТИЧНЫХ УЛЬТРАФУНКЦИЙ
Следствие 2. Класс P ol(R2 ) является максимальным клоном.
Доказательство. В силу двойственности предикатов R1 и R2 .
Список литературы
1.
2.
3.
4.
5.
Бадмаев С. А. Минимальные частичные ультраклоны на двухэлементном
множестве / С. А. Бадмаев, И. К. Шаранхаев // Изв. Иркут. гос. ун-та. Сер.
Математика. – 2014. – Т. 9. – С. 3–9.
Бадмаев С. А. О полных множествах частичных ультрафункций на двухэлементном множестве / С. А. Бадмаев // Вестн. Бурят. гос. ун-та. Математика,
информатика. – 2015. – № 3. – С. 61–67.
Пантелеев В. И. Критерий полноты для доопределяемых булевых функций /
В. И. Пантелеев // Вестн. Самар. гос. ун-та. Естественнонауч. сер. – 2009. –
№ 2 (68). – С. 60–79.
Пантелеев В. И. Критерий полноты для недоопределенных частичных булевых функций / В. И. Пантелеев // Вестн. Новосиб. гос. ун-та. Сер.
Математика, механика, информатика. – 2009. – Т. 9, № 3. – С. 95–114.
Пантелеев В. И. О двух максимальных мультиклонах и частичных ультраклонах / В. И. Пантелеев // Изв. Иркут. гос. ун-та. Сер. Математика. – 2012.
– Т. 5, № 4. – C. 46–53.
Бадмаев Сергей Александрович, аспирант, Институт математики и информатики, Бурятский государственный университет, 670000,
Улан-Удэ, ул. Смолина, 24а тел.: (3012)219757
(e-mail: badmaevsa@mail.ru)
Шаранхаев Иван Константинович, кандидат физико-математических наук, доцент, Институт математики и информатики, Бурятский
государственный университет, 670000, Улан-Удэ, ул. Смолина, 24а тел.:
(3012) 219757 (e-mail: goran5@mail.ru)
S. A. Badmaev, I. K. Sharankhaev
On Maximal Clones of Partial Ultrafunctions
on a Two-Element Set
18
С. А. БАДМАЕВ, И. К. ШАРАНХАЕВ
Abstract. Class of discrete functions from a finite set A to set of all subsets of A
is a natural generalization of the class of many-valued functions on A (k-valued logic
functions). Functions of this type are called multifunctions or multioperations on A, and
are used, for example, in the solution of the functional equations, in logical and technical
systems. It is obvious that the superposition in the usual sense not appropriate for multifunctions, therefore, we need to expand the standard concept of superposition. We note
there are various ways to determine the operation of superposition of multifunctions, one
of such methods is considered in this paper. Multifunctions on A with this superposition
are called partial ultrafunctions on A. In this article starting set A is two-element set
and we consider classical problem of theory of discrete functions – description of clones –
sets of functions closed with respect to the operation of superposition and containing all
the projections. We got a description of the two maximal clones of partial ultrafunctions
of a two-element set by the predicate approach.
Keywords: multifunction, partial ultrafunction, superposition, clone, maximal clone.
References
1.
2.
3.
4.
5.
Badmaev S.A., Sharankhaev I.K. Minimal Partial Ultraclones on a Two-element
Set (in Russian). Izvestiya Irk. Gos. Univ. Ser. Matematika, 2014, vol. 9, pp. 3-9.
Badmaev S.A. On Complete Sets of Partial Ultrafunctions on a Two-element Set
(in Russian). Vestnik Buryat. Gos. Univ. Matem., Inform., 2015, no 3, pp. 61-67.
Panteleyev V.I. Completeness Criterion for Incompletely Defined Boolean
Functions (in Russian). Vestnik Samar. Gos. Univ. Est.-Naush. Ser., 2009, vol.
2, no 68, pp. 60-79.
Panteleyev V.I. Completeness Criterion for Sub-defined Partial Boolean Functions
(in Russian). Vestnik Novosibir. Gos. Univ. Ser.: Matem., Mechan., Inform., 2009,
vol. 9, no 3, pp. 95-114.
Panteleyev V.I. On Two Maximal Multiclones and Partial Ultraclones (in Russian).
Izvestiya Irk. Gos. Univ. Ser. Matematika, 2012, vol. 5, no 4, pp. 46-53.
Badmaev Sergey Alexandrovich, Postgraduate, Buryat State University, 24a, Smolin st., Ulan-Ude, 670000 tel.: (3012)219757
(e-mail: badmaevsa@mail.ru)
Sharankhaev Ivan Konstantinovich, Candidate of Sciences (Physics
and Mathematics), Buryat State University, 24a, Smolin st., Ulan-Ude,
670000 tel.: (3012)219757 (e-mail: goran5@mail.ru)
Известия Иркутского государственного университета.
2016. Т. 16. Серия «Математика». С. 3–18
Документ
Категория
Без категории
Просмотров
3
Размер файла
314 Кб
Теги
клона, частичных, множества, ультрафункций, двухэлементном, максимальной
1/--страниц
Пожаловаться на содержимое документа