ДОКЛАДЫ АКАДЕМИИ НАУК, 2012, том 442, № 5, с. 598-599
МАТЕМАТИКА
УДК 519.716
ОПЕРАТОР ПОЗИТИВНОГО ЗАМЫКАНИЯ © 2012 г. С. С. Марченков
Представлено академиком Ю.И. Журавлевым 14.09.2011 г. Поступило 16.09.2011 г.
Один из распространенных способов классификации функций многозначной логики состоит в задании на множестве Pk функций k-значной логики некоторого оператора замыкания О. Подмножества множества Pk, замкнутые относительно оператора О, образуют О-классификацию множества Pk. Самый известный оператор замыкания — оператор суперпозиции — при любом k > 3 дает континуальную классификацию множества Pk [5]. Однако существует ряд "сильных" операторов замыкания, которые порождают конечные либо счетные классификации. К таким операторам относится оператор позитивного замыкания [2], представляющий собой дальнейшее расширение оператора параметрического замыкания А.В. Кузнецова [1] и дающий при любом k > 2 конечную классификацию множества Pk.
В данном сообщении предложено алгебраическое описание позитивно замкнутых классов, полностью решен вопрос о позитивно предпол-ных классах и указаны все атомы решетки позитивно замкнутых классов трехзначной логики.
Пусть k> 2, Ek = {0, 1, ..., k — 1}, Pk — множество всех функций на Ek (множество функций k-знач-ной логики). Если Q с Pk и n > 1, то через Q(n) обозначаем множество всех n-местных функций из Q. Введем основные понятия, связанные с оператором позитивного замыкания. Вначале определим язык Pos. Исходными символами языка Pos являются символы предметных переменных х1, x2, ...
(с областью значений Ek), символы f"п для обозначения функций из p\-), знаки равенства —, конъюнкции &, дизъюнкции V, квантора существования 3, левой и правой скобок и запятой.
Терм языка Pos определим по индукции. Символ предметной переменной есть терм; если xji,
Xj2, ..., xJn — символы предметных переменных (не обязательно различные), а /"п — символ
Московский государственный университет им. М.В. Ломоносова
функции из Pkn), то f¡n) (xJí, Xj2, ..., xJn) есть терм; если t1, t2, ..., tm — термы, а fm) — символ функции из p\ ), то
г (tj, t2, ..., tm) есть терм. Всякий терм языка Pos очевидным образом определяет некоторую функцию из Pk.
Если t1, t2 — термы языка Pos, то выражение (ti = t2) называем элементарной формулой языка Pos. Из элементарных формул по обычным правилам с помощью связок &, v и квантора 3 определяем остальные формулы языка Pos.
Всякая формула языка Pos с m свободными переменными задает некоторое m-местное отношение на Ek. Пусть Qс Pk, Ф(х1, x2,..., xm) — формула языка Pos со свободными переменными x1, x2, ..., xm, все функциональные символы которой суть обозначения функций из Q, и формула Ф^, x2, ..., xm) определяет отношение r(x1, ..., xm) на Ek. В этом случае говорим, что формула Ф позитивно выражает отношение r через функции множества Q. Понятие позитивной выразимости переносим с отношений на функции. Именно, если g(x1, x2, ..., xm) — функция из Pk, а формула Ф(x1, x2, ..., xm, y) языка Pos позитивно выражает отношение y = g(x1, x2, ..., xm) (график функции g) через функции множества Q, то говорим, что формула Ф позитивно выражает функцию g через функции множества Q. Совокупность всех функций, позитивно выразимых через функции множества Q, называем позитивным замыканием множества Q и обозначаем Pos[Q]. Множества вида Pos[Q] называем позитивно замкнутыми классами. Если Q с R, R — позитивно замкнутый класс и Pos[Q] = R, то говорим, что множество Q позитивно порождает класс R.
Совокупность всех позитивно замкнутых классов в Pk образует решетку с операцией пересечения и операцией объединения вида Pos[Q u R] (здесь Q, R — позитивно замкнутые классы). Эту решетку обозначим через Решетка имеет единицу — класс Pk, а также нуль — класс всех селекторных функций (проекций).
Если Q с Pk, ф е Р[Г) и для всякой функцииf из Q выполняется тождество
Лф(Х1), ф(х2), ..., ф( Xn)) = ф(/(хь X2, ..., Xn)) ,
ОПЕРАТОР ПОЗИТИВНОГО ЗАМЫКАНИЯ
599
то говорят, что ф есть эндоморфизм алгебры (Ек; 0. Множество Епё(Ек; Q) всех эндоморфизмов алгебры (Ек; 0 образует моноид — полугруппу с операцией композиции и единицей (тождественным отображением). Далее множество всех эндоморфизмов алгебры (Ек; 0 обозначаем через Епё(0, а в случае Q = {/} — через Епё( /).
Теорема 1 доказана в сотрудничестве с С.А. Ла-тушкиным.
Теорема 1. Пусть к > 2, Q с Рк и / е Рк.
Тогда/е Pos[Q] в том и только том случае, когда ЕпОД) с Епё(/).
Следствие. При любом к > 2 различные позитивно замкнутые классы в Рк имеют различные полугруппы эндоморфизмов.
Позитивно замкнутый класс Q называется позитивно предполным в Рк, если Q Ф Рк и не существует такого позитивно замкнутого класса Я, что Q с Я с Рк (включения строгие). Позитивно пред-полные классы задают коатомы решетки
Пусть Q с Р[Г). Обозначим через ф^) множество всех функций из Рк, полугруппа эндоморфизмов которых содержит множество Q. Известно [4], что множество ф^) является позитивно замкнутым классом. Одноместная функция g называется идемпотентной, если g(g) = g.
Те о р е м а 2. При любом к > 2 позитивно пред-полные в Рк классы и только они представимы в виде ф^), где g — либо идемпотентная функция, отличная от тождественной функции, либо перестановка на множестве Ек, цикловое разложение которой состоит из циклов одной и той же простой длины и, возможно, циклов длины 1, число которых в этом случае должно быть не менее двух.
Отметим, что позитивная предполнота ряда классов доказана в [3, 4]. Все позитивно предпол-ные в Р2 и Р3 классы найдены в [2, 3].
(3)
Пусть т0, т1 — функции из Р3 , которые удовлетворяют тождеству
т(х, х, у) = Ш1 (х, у, х) = т,(у, х, х) = х, и, кроме того, функция т0 равна нулю на всех наборах с тремя различными компонентами, а для функции т1 справедливы равенства
Ш!(0, 1, 2) = Ш!(1, 2, 0) = т1(2, 0, 1) = 0,
Ш!(0, 2, 1) = Ш1 (1, 0, 2) = Ш1(2, 1, 0) = 1.
Теорема 3. Решетка имеет 10 атомов. Они позитивно порождаются функциями 0, 1, 2, 2х + 2у (шоё3), т0, т1 и четырьмя фунциями, двойственными функция т0, т1.
Отметим, что полугруппа эндоморфизмов класса Pos[0] состоит из всех функций множества Р(3Г), сохраняющих константу нуль; полугруппа эндоморфизмов класса Pos[2x + 2у] — из всех перестановок на множестве Е3 и функций 0, 1, 2; полугруппа эндоморфизмов класса Pos[m0] — из функций 0, (001), (002), (010), (012), (020), (021), (101), (110), 1, (112), (121), (202), (212), (220), (221), 2; полугруппа эндоморфизмов класса Pos[m1] — из функций 0, (001), (002), (012), (102), (110), 1, (112), (220), (221), 2
(функцию/из множества Р\Г) мы изображаем вектором (/(0)/(1)/(2))).
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 09-01-00701).
СПИСОК ЛИТЕРАТУРЫ
1. Кузнецов А.В. Логический вывод. М.: Наука, 1979. С. 5-33.
2. Марченков С.С. // Дискрет. математика. 1999. Т. 11. № 4. С. 110-126.
3. Марченков С.С. // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13. № 3. С. 27-39.
4. Марченков С.С. // Дискрет. анализ и исслед. операций. 2009. Т. 16. № 6. С. 52-67.
5. Янов Ю.И, Мучник А.А. // ДАН. 1959. Т. 127. № 1. С. 44-46.
ДОКЛАДЫ АКАДЕМИИ НАУК том 442 № 5 2012
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.