Министерство образования и науки Российской Федерации
УДК
ГРНТИ
Инв. №
УТВЕРЖДЕНО:
Исполнитель:
Факультет вычислительной математики и
кибернетики Московского государственного
университета имени М.В. Ломоносова
От имени Руководителя организации
/ Моисеев Е.И. /
М.П.
НАУЧНО-ТЕХНИЧЕСКИЙ
ОТЧЕТ о выполнении 4 этапа Государственного контракта № 16.740.11.0570 от 30 мая 2011 г.
Исполнитель: Факультет вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова Программа (мероприятие): Федеральная целевая программа «Научные и научнопедагогические кадры инновационной России» на 2009-2013 гг., в рамках реализации мероприятия № 1.3.1 Проведение научных исследований молодыми учеными кандидатами наук.
Проект: Свойства дискретных функций и операций над ними Руководитель проекта:
/Федорова Валентина Сергеевна (подпись) Москва 2012 г.
СПИСОК ОСНОВНЫХ ИСПОЛНИТЕЛЕЙ
по Государственному контракту 16.740.11.0570 от 30 мая 2011 на выполнение поисковых научно-исследовательских работ для государственных нужд Организация-Исполнитель: Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова Руководитель темы:кандидат физико- Федорова В. С.
математических наук, без подпись, дата ученого звания Исполнители темы:
кандидат физико- Ларионов В. Б.
математических наук, без подпись, дата ученого звания Реферат Отчет 32 с., 1 ч., 1 рис., 0 табл., 10 источн., 2 прил.
Многозначная логика, дискретная функция, замкнутый класс, монотонность, частично упорядоченное множество, надструктура, предикат В отчете представлены результаты исследований, выполненных по 4 этапу Государственного контракта № 16.740.11.0570 "Свойства дискретных функций и операций над ними" (шифр "2011-1.3.1-111-001") от 30 мая по направлению "Проведение научных исследований молодыми кандидатами наук в следующих областях:- математика; - механика" в рамках мероприятия 1.3.1 "Проведение научных исследований молодыми учеными - кандидатами наук.", мероприятия 1.3 "Проведение научных исследований молодыми учеными - кандидатами наук и целевыми аспирантами в научно-образовательных центрах", направления 1 "Стимулирование закрепления молодежи в сфере науки, образования и высоких технологий."
федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009-2013 годы.
Цель работы - Получение результатов для полного описания надструктуры класса однородных функций многозначной логики, а также доказательство критерия наличия бесконечной надструктуры для специальных классов монотонных функций многозначной логики.
Методы теории множеств, теории графов, теории функций многозначной логики, соответствие Галуа между решетками функций и предикатов.
Персональный компьютер; операционная система Microsoft Windows; пакет офисных программ Microsoft Office; текстовый редактор TeXnicCenter и пакет программ MikTeX.
1. Полное описание надструктуры класса однородных функций многозначной логики.
2. Статья, содержащая результаты решения исследуемых задач, в высокорейтинговом российском или зарубежном журнале.
3. Доказательство критерия наличия бесконечной надструктуры для классов монотонных функций, сохраняющих частично упорядоченное множество специального вида.
4. Публикация в трудах научной конференции.
5. Научно-технический отчёт по четвертому этапу.
Содержание Содержание
1. Введение
2. Однородные функции и монотонные, сохраняющие частично упорядоченное множество специального вида
2.1. Надструктура класса однородных функций многозначной логики
2.2. Надструктура класса монотонных функций, сохраняющих частично упорядоченное множество специального вида
2.3. Публикации результатов НИР
3. Заключение
4. Список использованных источников
Приложение А
Приложение Б
Теория дискретных управляющих систем занимает одно из важнейших мест в области знаний, исследования по которой в отечественной традиции относят к математической кибернетике, а в зарубежной – к theoretical computer science. Различные задачи, связанные с дискретными управляющими системами, играют важную роль как в теоретических исследованиях, так и при решении прикладных задач из разных областей знаний.
Исследования, проводимые в рамках работ по Государственному контракту, связаны с изучением неотъемлемой части теории дискретных управляющих систем – теории дискретных функций. В частности, проведенные в рамках четвертого этапа работ по Государственному контракту исследования касались теории функциональных систем, а точнее, проблем выразимости, классификации элементов и описания замкнутых классов функций.
На четвертом этапе Государственного контракта были выполнены работы по следующим направлениям, касающимся изучения строения фрагментов решетки замкнутых классов функций многозначной логики:
1. Исследовалась надструктура замкнутого класса однородных функций многозначной логики. Была доказана ее конечность и получено полное описание всех классов (и их взаимных включений), содержащих класс однородных функций. Также были изучены основные свойства надструктуры класса однородных функций многозначной логики.
2. Исследовалась надструктура классов монотонных функций многозначной максимальными элементами и одним минимальным элементом. Доказан критерий наличия бесконечной надструктуры для таких классов монотонных Кроме того, выполненные на четвертом этапе работы включали также следующие действия:
3. Подготовка научных статей к публикации: по результатам проведенных исследований опубликованы статьи в высокорейтинговом российском журнале 4. Подготовка настоящего научно-технического отчета.
Все перечисленные работы проводились в соответствии с составленным ранее планом проведения исследований, вошедшим в научно-технический отчет по итогам первого этапа. Подробное изложение результатов проведенных исследований содержится в основной части настоящего отчета.
2. Однородные функции и монотонные, сохраняющие частично упорядоченное множество специального вида 2.1. Надструктура класса однородных функций многозначной логики Одной из основных задач в теории функций многозначной логики является проблема выразимости функций: заданную k-значную функцию или класс функций требуется выразить, используя суперпозицию функций некоторого имеющегося множества. Указанную задачу, несколько уменьшив общность постановки, можно переформулировать в задачу описания всех замкнутых относительно операции суперпозиции классов функций k-значной логики, то есть таких классов, которые содержат любую функцию, представимую суперпозицией произвольных функций этого класса.
Яновым и Мучником в [1] было показано, что решетка замкнутых относительно операции суперпозиции классов функций k-значной логики для любого k 3 содержит континуальное число классов. В силу невозможности ее исчерпывающего описания представляется интересным изучение различных подмножеств этой решетки. В рамках третьего этапа данного Государственного контракта была описана структура всех классов, содержащих произвольный класс самодвойственных функций [2]. В рамках четвертого этапа с использованием схожей техники изучается надструктура класса однородных функций.
В качестве основного инструмента исследований по данной тематике был выбран предикатный подход, но также широко применялись теория Галуа, аппарат теории графов и элементы теории частичного порядка.
Введем необходимые определения и обозначения. Обозначим через Ek множество Функция f ( x1,, xn ) называется функцией k-значной логики ( k 2 ), если она определена на Ek и все ее значения принадлежат Ek.
Будем использовать следующие стандартные обозначения. Множество всех функций k-значной логики обозначим Pk. Для любого подмножества A из Pk через [A] будем обозначать замыкание относительно операции суперпозиции (для функций везде далее будет идти речь именно об этом типе замыкания). Множество всех замкнутых классов в k, упорядоченных по отношению включения, будем называть решеткой замкнутых классов k-значной логики.
Для данного класса A надструктурой будем называть множество классов, строго содержащих класс A.
Пусть на множестве Ek задана некоторая подстановка. Функция k-значной логики f ( x1,, xn ) называется самодвойственной относительно подстановки, если выполнено следующее тождество:
где через Известно [3], что множество всех функций из Pk, самодвойственных относительно, является замкнутым классом. Обозначим этот класс через S.
Замкнутый класс функций, равный пересечению всех классов самодвойственных функций, называется классом однородных функций. Будем обозначать указанный класс через S k.
Пусть p ( x1,, xm ) – некоторый предикат, определенный на Ek, f ( y1,, y n ) – функция из множества Pk. Будем говорить, что функция f ( y1,, y n ) сохраняет предикат p ( x1,, xm ), если для любых n наборов ai = (ai1,, aim ), i {1,, n }, удовлетворяющих предикату p, набор ( f (a11,, a n1 ),, f (a1m,, a nm ) ) также удовлетворяет предикату p. По определению будем считать, что тождественно ложный предикат сохраняет любая функция.
Обозначим через Pol ( p ) множество функций, сохраняющих предикат p. Для произвольного множества функций A через Inv A обозначим множество предикатов, каждый из которых сохраняет любая функция из A.
отождествление переменных, добавление квантора существования по какой-либо переменной (проекция). Для произвольного множества предикатов P через [P] будем обозначать замыкание относительно указанных операций. Подробное определение этих операций можно найти в [4] и [5].
Лемма 2 [6]. Пусть p = p1 & & pm, где предикаты p1,, pm не имеют общих переменных. Тогда Пусть A и B – произвольные непустые подмножества Ek одинаковой мощности.
Обозначим через FAB множество всех различных взаимно однозначных отображений множества A во множество B, а через Fk – объединение множеств FAB для всевозможных пар подмножеств A и B указанного вида. Для f FAB обозначим D f = A, T f = A B.
Для произвольного отображения f Fk обозначим через R f ( x1, x2 ) предикат, истинный на всех парах (a, f (a )), где a D( f ), и только на них.
Замкнутые классы функций S f = Pol ( R f ), где f Fk, будем называть классами квазисамодвойственных функций, а сами функции, входящие в указанные классы, – квазисамодвойственными функциями. Отметим, что согласно данному определению все классы самодвойственных функций [3] (в случае D f Ek, f – не тождественная подстановка), а также класс Pk (в случае D f Ek, f – тождественная подстановка на Ek ) являются классами квазисамодвойственных функций. Если f – тождественная подстановка на D f, где D f Ek, то S f – предполный центральный класс [6].
Зафиксируем некоторое число k 3. Пусть = { 1,, k !} – множество всех подстановок на Ek. Отметим, что Обозначим множество {R 1,, R k } через RS. Окончательно получаем S k = Pol RS.
Лемма 3. Для любого предиката p [ RS ] справедливо S k Pol p.
Доказательство. Пусть R = R 1 & R 2 & & R k !, где конъюнкция строится без отождествления переменных, 1,, – все подстановки на Ek. По лемме 2 справедливо Pol R = = S k. Заметим, что из предиката R подходящей проекцией переменных можно получить любой предикат R i, откуда RS [R ].
Получаем, что для любого предиката p [ RS ] справедливо p [R ], откуда из леммы 1 следует S k Pol p.
Лемма 4. Пусть замкнутый класс A содержит класс S k. Тогда для любого предиката p Inv A справедливо p [ RS ].
Доказательство. Снова рассмотрим предикат R из доказательства леммы 3.
Справедливо S k = Pol R A, откуда Inv A Inv Pol R (см. [4]). Обозначим через d ( x1, x2 ) предикат, являющийся двухместной диагональю (d ( a, b) = TRUE тогда и только тогда, когда a = b ). Отметим, что d [ R] ( d ( x1, x2 ) = Re ( x1, x2 ), где e – тождественная на Ek подстановка). С учетом сказанного из [4] следует Inv Pol R = [R ], откуда Inv A [R]. По построению предиката R справедливо R [ RS ].
Получаем, что для любого p Inv A справедливо p [ RS ].
f FAB, A k 1, содержит класс однородных функций.
Доказательство. Пусть класс квазисамодвойственных функций S f удовлетворяет условию леммы. Если S f является классом самодвойственных функций, утверждение леммы следует из определения класса однородных функций. Поэтому далее будем считать, что A < k 1.
Обозначим множество C = Ek \ A. Тогда | C | > 1. Пусть g – некоторая подстановка подстановку на множестве Ek, такую, что 1 (a ) = a, если a A, и 1 ( a) = g (a), если a C. Пусть – некоторая подстановка на множестве Ek, являющаяся доопределением отображения f.
Для завершения доказательства остается воспользоваться леммой 1.
Пусть предикат p реализуется над RS формулой F. Везде далее будем считать, что ориентированный граф G(F) по следующему правилу: между множеством вершин G(F) и множеством переменных F (учитываем и свободные, и связанные) существует взаимно однозначное соответствие. Вершину, соответствующую переменной x, пометим символом «x», если переменная x свободная, и « x », если связанная. Данную вершину для краткости изложения будем обозначать v x. В графе G(F) есть ориентированное ребро (v x, v y ) с пометкой « i », тогда и только тогда, когда в формуле F содержится запись Отметим, что по графу формулы G(F) формула F с вынесенными вперед кванторами существования восстанавливается однозначно.
Путем из вершины v1 в вершину v2 в ориентированном графе G будем называть любую последовательность ребер вида вершины и ребра в которой могут повторяться. Ориентация ребер указанной последовательности может быть любой. Замкнутым путем называется путь, в котором первая и последняя вершины совпадают.
Для произвольного пути S в графе определим величину L(S), являющуюся подстановкой на Ek и характеризующую указанный путь. Для пути, состоящего из одного ребра (v1, v2 ) с пометкой i, положим Для пути S = {( w1, w2 ), ( w2, w3 ),, ( wm 1, wm )} положим Непосредственно из определений графа формулы и величины L следует утверждение.
Лемма 6. Пусть предикат p реализуется над RS формулой F с графом G(F). Тогда для любого набора a, такого, что p (a ) = TRUE, и для двух произвольных вершин графа v y1, v y2, соединенных путем S, и таких, что переменные y1, y 2 приняли на наборе a значения b и c соответственно, справедливо c = (L(S))(b).
множество элементов a Ek, таких, что справедливо a = ( L( S ))(a ) для любого замкнутого пути S, проходящего через вершину v y.
Лемма 7. Пусть предикат p реализуется над RS формулой F с множеством свободных переменных {x1,, xn } и со связным графом G(F). Пусть между любыми двумя вершинами v xi, v x j в GF существует путь S ij, такой, что L( S ij ) = ij, i, j {1,, n }. Тогда справедливо:
Доказательство. Пусть набор некоторого i справедливо ai Txi. Это означает, что существует замкнутый путь S, проходящий через вершину v xi, такой, что L(S ) = и (ai ) ai. Получаем противоречие с леммой 6. Справедливость соотношения a j = ij (ai ) вытекает непосредственно из леммы 6.
Пусть теперь набор a таков, что перечисленные в лемме два условия выполнены.
Покажем, что p (a ) = TRUE.
Рассмотрим произвольную вершину v y графа G(F). Поскольку указанный граф связный, то существует путь S1 от вершины v xi до v y. Пусть L( S1 ) = 1. Присвоим переменной y значение b = 1 (ai ). Пусть S 2 – некоторый путь из v xi в v y, отличный от S1, и L( S 2 ) = 2.
Покажем, что b = 2 ( ai ), то есть найденное значение b не зависит от выбора пути.
Соединением путей S1 и S 2 можно получить замкнутый путь S 3, проходящий через 1 ( a) = 2 (a). В силу доказанного и второго условия леммы все переменные x j, j {1,, n } при данном присвоении примут значения a j.
Покажем, что на присвоенных значениях каждый сомножитель формулы F будет истинен, то есть p (a ) = TRUE. Предположим, что при проведенном выше присвоении переменные yl, y j приняли соответственно значения bl и b j. Это означает, что из вершины v xi существуют пути S, S до вершин v yl, v y j соответственно, при этом формулы F соответствует ребру (v yl, v y j ) графа G(F), L({(v yl, v y j )}) =. Соединением указанного ребра с путями S, S получим замкнутый путь S, проходящий через вершину или (bl ) = b j. Получаем, что R (bl, b j ) = TRUE.
Теорема. Надструктура класса однородных функций состоит только из классов квазисамодвойственных функций S f, где f FAB, A k 1, и их пересечений.
Доказательство. То, что указанные в формулировке теоремы классы входят в надструктуру класса однородных функций S, было доказано в лемме 5. Покажем далее, что никакие другие классы не содержатся в указанной надструктуре.
Рассмотрим некоторый класс A, содержащий S. Возьмем произвольный предикат p из множества Inv A. По лемме 4 выполняется p [ RS ]. Обозначим через F формулу, реализующую p над множеством RS, G ( F ) – ее граф. Рассмотрим вначале случай, когда G(F) связен.
Пусть x1,, xn – все свободные переменные формулы F. Поскольку граф G(F) связен, то существуют пути S 2,, S n от вершины v x2 до вершин v xn, соответственно.
Обозначим = L( S j ), A = Tx1. Отметим, что множество A не может быть мощности k – (поскольку никакая подстановка не может иметь в точности k – 1 неподвижный элемент).
Если местность n предиката p равна единице, то по лемме 7 получаем p (a ) = TRUE тогда и только тогда, когда a A. В этом случае Pol ( p ) либо совпадает с Pk (если A Ek ), либо является предполным центральным классом. При этом Pol ( p ) = Pol R f, где f – тождественное отображение множества A в себя, является классом квазисамодвойственных функций.
Пусть теперь n = 2. По лемме 7 получаем p( a, b) = TRUE тогда и только тогда, когда a A и b = 2 (a ). Получаем, что p = R f, где f – взаимно однозначное отображение, определенное на множестве A и совпадающее на нем с подстановкой 2, то есть Pol ( p ) – класс квазисамодвойственных функций.
Остается случай n > 2. Обозначим предикаты где i { 2,, n }. Получаем, что pi [ p ], откуда pi [ RS ]. Предикаты pi попадают в уже рассмотренный случай (граф формулы, реализующей pi, можно получить из графа GF перепомечиванием вершин, поэтому указанный граф будет связным), то есть классы Pol pi являются классами квазисамодвойственных функций. Рассмотрим предикат Пусть набор a таков, что p (a ) = TRUE. Получаем, что все pi (a1, ai ) = TRUE, откуда Отсюда имеем, что a1 A, ai = i (a1 ) для всех i { 2,, n }. По лемме 7 получаем, что p (a ) = TRUE. Окончательно имеем p = p.
Итак, мы получили представление отождествления переменных. Из последнего соотношения следует, что получается из t отождествлением переменных).
С другой стороны, из pi [ p ] следует, что t [ p ]. По лемме 1 получаем, что Pol p = Pol t. По лемме 2 класс Pol t, а значит, и Pol p, является пересечением классов Pol pi, то есть классов квазисамодвойственных функций.
Пусть теперь GF – несвязный граф. Каждая компонента связности GF очевидным образом задает свой предикат, для которого справедливы приведенные выше рассуждения. Предикат p является конъюнкцией (без отождествления переменных) указанных предикатов. Опять получаем [6], что Pol p – некоторое пересечение классов самодвойственных и квазисамодвойственных функций.
2.2. Надструктура класса монотонных функций, сохраняющих частично упорядоченное множество специального вида многозначной логики, сохраняющих частично упорядоченное множество с тремя максимальными элементами и одним минимальным элементом.
некоторое отношение частичного порядка r. Возьмем два произвольных набора a = (a1,, a n ) и b = (b1,, bn ) из n. Будем говорить, что a не превосходит b относительно частичного порядка r и записывать a r b, если для любого 1 i n справедливо неравенство ai r bi.
Функция f ( x1,, x n ) называется монотонной относительно частичного порядка Множество всех функций из k, монотонных относительно r, называется классом монотонных функций r.
Будем задавать частичный порядок r частично упорядоченным множеством (ЧУМ) Обозначим через Pol ( p ) множество функций, сохраняющих предикат p. Класс R ( x, y ) = TRUE x y [5]. Везде далее, когда будем писать, что монотонный класс задается предикатом R, подразумевается именно предикат R ( x, y ).
Одним из семейств предполных классов функций k-значной логики при k (везде далее рассматриваются только такие k) является некоторое подмножество всех классов монотонных функций [7]. Класс является предполным тогда и только тогда, когда ЧУМ H обладает в точности одним максимальным и одним минимальным элементом [8].
Одним из участников Государственного контракта ранее было доказано [9]–[10], что в случае, когда класс монотонных функций не является предполным, его надструктура (то есть множество содержащих его классов) может быть бесконечной. В рамках четвертого этапа Государственного контракта устанавливается критерий наличия бесконечной надструктуры для случая, когда ЧУМ H имеет в точности три максимальных элемента и один минимальный.
Обозначим через 1 и множества, изображенные на рисунке 1.
надструктуры.
Определим L как множество, состоящее из всех ЧУМ H, которые содержат подмножество 1, изображенное слева на рисунке 1. Причем в H не появляются пути из в 3 по вершинам, являющимся максимумами 1 и 2. Уточним это понятие: не существует последовательности элементов v1,, v m в L такой, что v1 = 0, v m = 3, vi сравнимо с vi + 1 ( i {1,, m 1} ) (то есть либо vi vi+ 1, либо vi + 1 vi ), все vi – максимумы 1 и 2.
«