Министерство образования и науки Российской Федерации

УДК

ГРНТИ

Инв. №

УТВЕРЖДЕНО:

Исполнитель:

Государственное учебно-научное учреждение

Факультет вычислительной математики и

кибернетики Московского государственного

университета имени М.В.Ломоносова

От имени Руководителя организации

/ Моисеев Е. И. /

М.П.

НАУЧНО-ТЕХНИЧЕСКИЙ

ОТЧЕТ о выполнении 2 этапа Государственного контракта № 16.740.11.0570 от 30 мая 2011 г.

Исполнитель: Государственное учебно-научное учреждение Факультет вычислительной математики и кибернетики Московского государственного университета имени М.В.Ломоносова Программа (мероприятие): Федеральная целевая программа «Научные и научнопедагогические кадры инновационной России» на 2009-2013 гг., в рамках реализации мероприятия № 1.3.1 Проведение научных исследований молодыми учеными кандидатами наук.

Проект: Свойства дискретных функций и операций над ними Руководитель проекта:

/Федорова Валентина Сергеевна (подпись) Москва 2011 г.

СПИСОК ОСНОВНЫХ ИСПОЛНИТЕЛЕЙ

по Государственному контракту 16.740.11.0570 от 30 мая 2011 на выполнение поисковых научно-исследовательских работ для государственных нужд Организация-Исполнитель: Государственное учебно-научное учреждение Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова Руководитель темы:

кандидат физико- Федорова В. С.

математических наук, без подпись, дата ученого звания Исполнители темы:

кандидат физико- Ларионов В. Б.

математических наук, без подпись, дата ученого звания Реферат Отчет 38 с., 1 ч., 2 рис., 0 табл., 10 источн., 2 прил.

Многозначная логика, дискретная функция, замкнутый класс, бесповторная функция, самодвойственность, надструктура, критерий В отчете представлены результаты исследований, выполненных по 2 этапу Государственного контракта № 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-значной логики, то есть таких классов, которые содержат любую функцию, представимую суперпозицией произвольных функций этого класса.

Введем необходимые определения и обозначения. Обозначим через множество {0, 1,, k 1}. Функция f ( x1,, x n ) называется функцией k-значной логики ( k 2 ), если она определена на Следуя традиции, будем обозначать через k множество всех k-значных функций k-значной логики. Для любого подмножества A из k через [A] будем обозначать замыкание относительно операции суперпозиции (для функций далее везде будет идти речь именно об этом типе замыкания). Множество всех замкнутых классов в k, упорядоченных по отношению включения, будем называть решеткой замкнутых классов k-значной логики.

Яновым и Мучником в [1] было показано, что при k 3 множество всех замкнутых классов функций из k имеет мощность континуум. В связи с этим особенный интерес представляет изучение именно фрагментов решетки замкнутых классов функций из k.

Для данного класса A надструктурой будем называть множество классов, строго содержащих класс A.

Как было доказано И. Розенбергом в работе [2], в k при k 3 существует ровно шесть семейств предполных классов. Одно из них – это семейство S, являющееся подмножеством множества всех самодвойственных классов функций k-значной логики. В работе [3] С. В. Яблонским было доказано, что класс функций, самодвойственных относительно некоторой подстановки, принадлежит семейству S тогда и только тогда, когда указанная подстановка разлагается в произведение циклов одинаковой длины, являющейся простым числом.

Ранее одним из исполнителей данного Государственного контракта была описана надструктура замкнутых классов самодвойственных функций [4], которые по своим свойствам близки к предполным классам семейства S. Было показано, что произвольный замкнутый класс самодвойственных функций всегда обладает конечным множеством содержащих его замкнутых классов. В рамках второго этапа работ по Государственному контракту было рассмотрено новое семейство квазисамодвойственных функций и изучена надструктура классов из указанного семейства.

В качестве основного инструмента исследований по данной тематике был выбран предикатный подход, но также широко применялись теория Галуа, аппарат теории графов, элементы теории частичного порядка, алгебраические свойства групп подстановок.

Пусть p ( x1,, x m ) – некоторый предикат, определенный на k, f ( y1,, y n ) – предикат удовлетворяет предикату p. По определению будем считать, что тождественно ложный предикат сохраняет любая функция.

Обозначим через Pol ( p ) множество функций, сохраняющих предикат p.

Пусть A и B – произвольные непустые подмножества k, имеющие равную мощность. Обозначим через FAB множество всех различных взаимно однозначных отображений множества A во множество B, а через Fk – объединение множеств FAB для всевозможных пар подмножеств A и B указанного вида. Область определения отображения f обозначим через D( f ) (справедливо D( f ) = A для всех f FAB).

Для произвольного отображения f Fk обозначим через R f ( x1, x 2 ) предикат, истинный на всех парах ( a, f (a ) ), где a D ( f ), и только на них.

Замкнутые классы функций S f = Pol ( R f ), где f Fk, D( f ) Ek, и существует элемент a D( f ) такой, что f (a) a ( f не является тождественным отображением), будем называть классами квазисамодвойственных функций, а сами функции, входящие в указанные классы, – квазисамодвойственными функциями.

Отметим, что, если в последнем определении положить D( f ) = k, мы получим определение самодвойственных функций [3].

Рассмотрим строение отображений FAB. Сопоставим каждому такому отображению ориентированный граф G f по следующему правилу. Множество вершин графа – {v 0,, v k 1 }. Будем говорить, что вершина vi соответствует элементу i k. В графе G f есть ориентированное ребро (vi, v j ) тогда и только тогда, когда справедливо представляющих собой ориентированные циклы (в том числе циклы длины один – петли) или ориентированные пути (в том числе пути длины ноль – изолированные вершины, у которых отсутствуют инцидентные им ребра). Обозначим множество элементов k, соответствующих вершинам, входящим в компоненты связности первого типа (циклы), через L1 ( f ), множество оставшихся элементов – через L2 ( f ).

Если множество L2 ( f ) =, мы получаем обычные классы самодвойственных функций. При этом циклы графа G f соответствуют циклам подстановки f.

ориентированные пути имеют длину ноль. При этом мы получаем, что A = B, и f представляет собой подстановку на множестве A, строго содержащемся во множестве k.

В работе одного из исполнителей данного Государственного контракта [4] было показано, самодвойственных функций S, где – подстановка на всем множестве k, получающаяся доопределением отображения f 0. Поэтому полное описание надрешетки классов S f 0 известно.

произвольных ориентированных цепей из элементов множества L2 ( f 0 ). Оказывается, что все такие классы S f будут находиться в решетке замкнутых классов под классом S f 0.

Таким образом, любой класс квазисамодвойственных функций S f будет содержаться в некотором классе S f 0, где f 0 получается разрушением всех цепей в графе G f.

Отсюда получаем следующую теорему, являющуюся основным результатом исследований по теории функциональных систем в рамках второго этапа работ по данному Государственному контракту.

Теорема. Любой класс квазисамодвойственных функций имеет конечную надструктуру.

2.2. Решение некоторых задач о бесповторных дискретных функциях Одним из интенсивно развивающихся направлений в современной дискретной математике является теория алгоритмического обучения, среди важнейших задач которой можно назвать задачу расшифровки функций. Суть ее заключается в следующем. Пусть фиксирован некоторый класс функций, для определенности булевых, и имеется черный ящик, в котором «содержится» некоторая неизвестная функция из этого класса. Требуется, задавая вопросы типа «Какое значение принимает неизвестная функция на данном входном наборе?», определить, какая именно функция находится в черном ящике.

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

Популярными объектами задач расшифровки являются бесповторные функции, то есть функции, которые можно выразить формулами без повторений переменных. В данном определении неявным образом фигурирует базис – множество «исходных» функций, на основе которых строятся формулы. Традиционно в качестве базиса рассматривается так называемый элементарный базис, состоящий из конъюнкции (логическое И), дизъюнкции (логическое ИЛИ) и отрицания, а также базис из конъюнкции и дизъюнкции.

Представляется интересным получить обоснование повторности функции, исходя из информации о ее значениях лишь на нескольких наборах, поэтому в рамках работ по второму этапу данного Государственного контракта была рассмотрена новая эквивалентная формулировка свойства повторности в элементарном базисе, и с ее помощью построено короткое обходное доказательство критерия Стеценко [5] для минимальных (по отношению «быть подфункцией») повторных функций.

Введем необходимые определения. Булева функция f ( x1,, x n ), представимая (не представимая) бесповторной формулой в элементарном базисе {&,, ¬ } называется бесповторной (соответственно, повторной).

(антимонотонной) по переменной xi, если для любого набора значений оставшихся Функция, монотонная или антимонотонная по всем переменным, называется поляризуемой.

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

Предложение 1. Любая бесповторная функция представима в виде дерева, во внутренних вершинах которого реализуются чередующиеся конъюнкции и дизъюнкции произвольной арности, а в листьях – тождественные функции и отрицания попарно различных переменных.

Отметим, что по соглашению константы 0 и 1 считаются бесповторными функциями, поэтому справедлив следующий факт.

Предложение 2. Множество бесповторных функций замкнуто относительно подстановки констант.

Из Предложения 1 вытекает следующее утверждение.

Предложение 3. Неполяризуемая функция повторна.

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

При помощи Предложения 1 и правил де Моргана легко доказываются следующий факт.

Предложение 4. Обобщенно однотипные функции бесповторны одновременно.

Существенная переменная xi функции g ( x1,, x m ) называется отмеченной, если обе функции не равны тождественно константам и существенно зависят от всех существенных переменных g, кроме xi.

Будем говорить, что функция имеет запретную четверку, если на области ее определения существуют две пары соседних по одной и той же переменной наборов, на которых функция совпадает с этой переменной и ее отрицанием соответственно. Заметим, что функция, не содержащая запретных четверок, является поляризуемой. Будем говорить, что функция f ( x1,, x n ) имеет запретную шестерку, если на области ее определения или области определения какой-либо обобщенно однотипной с ней функции существуют две тройки наборов (0, 0, 3,, n ), (0, 1, 3,, n ), (1, 0, 3,, n ) и (0, 1, 3,, n ), (1, 0, 3,, n ), (1, 1, 3,, n ), на которых рассматриваемая функция совпадает с дизъюнкцией x1 x 2 и конъюнкцией x1 & x 2 соответственно.

Функциями Стеценко называются функции следующих пяти семейств:

Рассмотрим следующие свойства.

Свойство 1. Функция f ( x1,, x n ) повторна.

Свойство 2. Из функции f ( x1,, x n ) подстановкой констант можно получить функцию, обладающую отмеченной переменной.

Свойство 3. Из функции f ( x1,, x n ) подстановкой констант можно получить функцию, обобщенно однотипную с некоторой функцией Cтеценко.

Свойство 4. У функции f ( x1,, x n ) имеется запретная четверка или запретная шестерка.

Здесь и далее считается, что функция f также может быть получена из себя самой подстановкой констант.

Теорема Субботовской [7]. Свойства 1 и 2 эквивалентны.

Теорема Стеценко [5]. Свойства 2 и 3 эквивалентны.

Отметим, что следующие четыре утверждения доказываются тривиально.

Утверждение 1. Всякая функция Стеценко имеет отмеченную переменную:

(3) (2).

Утверждение 2. Всякая функция, обладающая отмеченной переменной, повторна:

(2) (1).

Утверждение 3. Всякая функция Стеценко имеет запретную четверку либо запретную шестерку: (3) (4).

Утверждение 4. Всякая функция, имеющая запретную четверку либо запретную шестерку, повторна: (4) (1).

Из теоремы Субботовской, теоремы Стеценко и утверждений 3 и 4 вытекает эквивалентность свойств 1, 2, 3 и 4.

Однако мы покажем обходной вариант доказательства теоремы Стеценко, установив справедливость импликаций (1), (2) (4) и (4) (3). Справедливость теоремы Субботовской при этом предполагается известной.

Схема упоминавшихся импликаций проиллюстрирована на рис. 1. Тривиальные следования обозначены простыми стрелками, теоремы Субботовской и Стеценко – двойными, доказанные ниже результаты – волнистыми стрелками.

подстановками констант на места каких-либо переменных, будем называть подфункциями остальных – собственных подфункций.

Однозначность представления бесповторных функций деревьями, упомянутого в предложении 1, была доказана В. А. Гурвичем [8]: для любой пары существенных переменных xi, x j из бесповторной функции f подстановкой констант на места остальных переменных можно получить либо конъюнкцию xi & x j, либо дизъюнкцию xi x j, но не обе эти функции, при этом сама функция f однозначно определяется множеством ее существенных переменных и информацией о наличии всевозможных подфункций вида xi & x j и xi x j.

обсуждалась в работе [9], а однозначное представление бесповторных функций в более широких базисах получено в [10].

Лемма 1. Для поляризуемой повторной функции можно найти шесть наборов, доказывающих ее повторность.

монотонную повторную функцию f ( x1,, x n ) и воспользуемся результатом теоремы Субботовской. Пусть подстановкой констант из f можно получить функцию g ( x1,, x m ), переменная x m которой является отмеченной. Не ограничивая общности рассуждений, будем считать, что g минимальна, то есть никакой подстановкой констант из нее нельзя получить функцию, имеющую отмеченную переменную и не равную g. Это, в частности, означает, что g зависит существенно от всех своих переменных. Согласно определению отмеченной переменной, функции g ( x1,, x m 1, 0) и g ( x1,, x m 1, 1) также существенно зависят от всех своих переменных. Так как g минимальна, то эти функции являются бесповторными по теореме Субботовской. Кроме того, они не равны между собой в силу существенной зависимости g от x m. Согласно вышеупомянутым результатам Гурвича [8], для пары различных бесповторных функций, существенно зависящих от переменных x1,, x m 1 и только от них, найдется такая пара переменных xi, x j с 1 i < j m 1, что подстановкой некоторых констант из одной функции можно получить конъюнкцию xi & x j, а из другой – дизъюнкцию xi x j (отметим, что наборы подставляемых констант могут различаться). Таким образом, функция g, а следовательно, и f обладает запретной шестеркой. Значения f на наборах этой шестерки доказывают ее повторность. Лемма доказана.

Теорема 1. Всякая повторная функция имеет запретную четверку или запретную шестерку: (1), (2) (4).

Доказательство. Пусть функция f повторна. Если каждая из переменных f является монотонной либо антимонотонной, то f по определению поляризуема и, следовательно, обладает запретной шестеркой по лемме 1. Если же некоторая переменная xi функции f не является ни монотонной, ни антимонотонной, то существуют две пары соседних по этой переменной наборов, на которых f совпадает с xi и xi соответственно.

Это и означает, что f имеет запретную четверку. Теорема доказана.

Подчеркнем, что теорема Стеценко в данном доказательстве не используется.

Перейдем к доказательству импликации (4) (3).

Рассмотрим вначале функции f, обладающие запретной четверкой.

Лемма 2. Пусть функция f имеет запретную четверку по переменной x и все ее собственные подфункции бесповторны. Пусть каждая из остальных переменных либо монотонна, либо антимонотонна. Тогда f обобщенно однотипна с функцией f d из первого семейства Стеценко.

Доказательство. Пусть ~ = ( y,, y ) монотонны, ~ = ( z,, z ) – антимонотонны, f = f ( x, ~, ~ ). Здесь и далее будем обозначать символами 0 и ~ векторы подходящей размерности, состоящие из нулей и единиц соответственно.

Рассмотрим подфункцию f 1x. Из монотонности переменных ~ получаем, что f (1, ~, 0 ) = 1 для любых y и f (1, ~, 1 ) = 0 для любых y. Заметим, что подфункции f 1x и f 0x функции f различаются только на наборах ( 0, 0 ) и ( 1, 1 ) (в противном случае у f есть неполяризуемая и, следовательно, повторная подфункция, что противоречит условию леммы). Поэтому для f 0 справедливы соотношения: f (0, ~, 0 ) = 1 для любых ~, кроме 0 ; f (0, ~, 1 ) = 0 для любых y, кроме 1. Иными словами, f (0, y, 0 ) = y1 y k и Так как все собственные подфункции функции f бесповторны, то, в частности, функция f (0, ~, ~ ) не имеет запретных шестерок, так что необходимо k 1. Точно так же m 1, откуда n 3. Случай n 1 невозможен; при n = 2 единственной подходящей функцией является сумма по модулю два двух переменных, не имеющая ни монотонных, ни антимонотонных переменных. Следовательно, n = 3 и k = m = 1. Нетрудно убедиться, что единственная функция, удовлетворяющая поставленным условиям, имеет вид x & y x & z и обобщенно однотипна с функцией f d(3) из первого семейства Стеценко.

Лемма доказана.

Лемма 3. Пусть функция f имеет запретную четверку по переменной x и все ее собственные подфункции бесповторны. Пусть переменная z функции f не является ни монотонной, ни антимонотонной. Тогда f обобщенно однотипна с одной из функций f d(s ) или f t (s ) из первого или второго семейства Стеценко соответственно.

где символы и означают соответственно отрицание и набор, противоположный Так как все подфункции функции f бесповторны, то следует, что запретная четверка для переменной z единственна, поэтому любая замена значения переменной x приводит к нарушению соответствующего равенства. Однако из бесповторности всех f ( x, ~, z ) f ( x, ~, z ) выполняется только при ( ~, z ) Следовательно, = 0 либо = 1.

Заметим, что оба случая c = 1 невозможны. Действительно, если = 0, то условия f (,, z ) = f (1, 0, z ) = z и f ( x, 0, 0) = x противоречивы. Если же = 1, то противоречивы условия f (,, z ) = f (1, 1, z ) = z и f ( x, 1, 1) = x. Следовательно, = 0.

Покажем, что если = 0, то функция f представима в виде где g ( y1,, y k ) – некоторая булева функция, удовлетворяющая условию g ( 0 ) = g ( 1 ) = 1.

В случае же = 1 функция f представима в виде где g ( 0 ) = g ( 1 ) = 0. Приведем доказательство только для случая = 1, так как рассуждения для = 0 практически идентичны.

В самом деле, при (, ) = (0, 1 ) имеющиеся равенства позволяют заключить, что Обозначим f (0, ~, 0) = g ( ~ ). Из бесповторности всех собственных подфункций функции f следует, что функции f (, ~, ) могут отличаться только при ~ = 0 и при ~ = ~, что и дает искомое представление для f.

Заметим, что в обоих случаях у f (либо у обобщенно однотипной с ней функции) имеется такая тройка бесповторных подфункций h, h', h' ', что h( 0 ) = h( 1 ) = 0, а h' и h' ' получаются из h заменой одного из этих значений на 1, причем область определения любой из подфункций h' и h' ' образует в объединении с областью определения h булев куб размерности k + 1. Иными словами, пары (h, h' ) и (h, h' ' ) задают бесповторные подфункции функции f, зависящие от k + 1 переменной.

Дальнейшие рассуждения также приведем, не ограничивая общности, для случая = 1. Заметим, что задаваемые парами (h, h' ) и (h, h' ' ) бесповторные функции получаются переименованием и возможным инвертированием переменной t из функций соответственно. Из отсутствия у этих функций запретных шестерок нетрудно вывести, как в доказательстве предыдущей леммы, что функция h имеет не более одной монотонной, а также не более одной антимонотонной существенной переменной. Так как h( 0 ) = h( 1 ) =, то либо h = 0, либо h получается переименованием переменных из функции y1 & y 2.

Непосредственная проверка показывает, что в случае h = 0 функция f обобщенно однотипна с функцией f t из второго семейства функций Стеценко, а в случае h = y1 & y 2 – с функцией f d( k + 2 ) из первого семейства функций Стеценко. Лемма доказана.

Теорема 2. Всякая функция, имеющая запретную четверку, обладает подфункцией, обобщенно однотипной с некоторой функцией первого или второго семейства Стеценко, то есть с f d или f t.

Доказательство теоремы 2 вытекает из леммы 2 и леммы 3.

обладающую единственной запретной шестеркой вида (воспользовавшись преобразованиями обобщенной однотипности, этого всегда можно добиться).

Введем дискретную функцию монотонное отображение переменных z1,, z, где 1, в частичный шестиэлементный порядок монотонных функций двух переменных 0 < x & y < x, y < x y < 1 по правилу, изображенному на рис. 2:

Рис. 2. Частичный шестиэлементный порядок монотонных функций собственные подфункции бесповторны. Пусть F (0,,0) = x & y и F (1,,1) = x y. Тогда f обобщенно однотипна с некоторой функцией третьего либо четвертого семейства Стеценко, то есть с f m при s 3 либо с f 4.

xy xz1 yz1 = f m3), принадлежащую второму семейству функций Стеценко. Пусть = 2, F (0, 1) = x и F (1, 0) = y. Тогда f ( x, y, z1, z 2 ) = xy xz 2 yz1 = f 4 – функция четвертого функция третьего семейства функций Стеценко. Лемма доказана.

собственные подфункции бесповторны. Пусть промежуточных наборах F принимает значения x & y и x y и, возможно, 0, 1, x и y.

Тогда f обобщенно однотипна с некоторой функцией третьего либо пятого семейства Стеценко, то есть с f m при s 3 либо с f 5.

Доказательство. Так как все собственные подфункции f бесповторны, то F принимает каждое из значений x & y и x y ровно на одном наборе, причем эти два набора противоположны. Рассмотрим интервалы булева куба между этими наборами и наборами 0, ~.

Функция F обладает на этих интервалах следующими свойствами:

на нижнем левом подкубе (от 0 до x & y ) функция F равна нулю всюду, кроме верхней точки, в которой она принимает значение x & y ;

на верхнем правом подкубе (от x y до 1) функция F равна единице всюду, кроме нижней точки, в которой она принимает значение x y ;

на верхнем левом подкубе (от x & y до 1) в нижней точке, и только в ней, функция F равна x & y, а в промежуточных точках F принимает значения из множества {x, y, 1}. Из строения рассматриваемого частично упорядоченного множества следует, что на данном подкубе есть антицепи верхних x и верхних y (в объединении также образующие антицепь), везде под ними реализуются только x и y соответственно. Во всех остальных точках функция F равна 1;

на нижнем правом подкубе (от 0 до x y ) в верхней точке, и только в ней, функция F равна x y, в промежуточных точках – {x, y, 0}. Аналогично предыдущему пункту, на этом подкубе есть антицепи нижних x, нижних y, везде над ними реализуются только x и y соответственно. Во всех остальных Уточним строение верхнего левого и нижнего правого подкубов. Пусть z ij, i, j = 1, 2, 3, – дизъюнкции различных групп переменных ~ij, содержащих по k ij 0, i, j = 1, 2, 3, переменных соответственно; z ij, i, j = 1, 2, 3, – конъюнкции тех же групп переменных z ij. На исследуемых подкубах реализуются функции соответственно Выясним конкретный вид этих функций, подставляя константы вместо переменных Подставим вначале x = 0. Предположим, что k11 = k12 = k13 = 0. Тогда функции на рассматриваемых подкубах равны соответственно Таким образом, подфункция функции f, получаемая подстановкой x = 0, обладает подфункциями z 32 z 33 и z 32 & z 33. С другой стороны, эта подфункция бесповторна и, следовательно, не имеет запретных шестерок. Следовательно, общее число переменных в множествах ~32 и ~33 не превосходит 1: k 32 + k 33 1. В случае же k11 + k12 + k13 > 0 с помощью аналогичных рассуждений получаем k 33 = k 32 = k 23 = k 22 = 0 и k12 + k13 1.

Три остальные подстановки приводят к следующим результатам:

Лишь четыре группы переменных могут быть одновременно отличными от нуля:

порождаемые ими функции.

Пусть вначале k 33 = 1. Тогда на верхнем левом и нижнем правом подкубах реализуются функции соответственно x & y z, ( x y ) & z, где z – произвольная переменная из ~33. Значит, функция f ( x, y, u1,, u, u + 1 ), где u + 1 = z, имеет вид и обобщенно однотипна с функцией f m из третьего семейства функций Стеценко.

Пусть теперь k12 1, k 21 1 и k12 + k 21 > 0. Возможны три варианта:

если k12 = 1 и k 21 = 1 то на верхнем левом и нижнем правом подкубах получается функция обобщенно однотипная с функцией f 4 четвертого семейства Стеценко. Эта функция повторна, поэтому = 1. В этом случае функция обобщенно однотипна с функцией f 5 из пятого семейства Стеценко.

по условию в верхней точке верхнего левого подкуба функция F должна принимать значение 1, а рассматриваемая подфункция ( x z12 ) & y при z12 = равна y. Таким образом, этот вариант невозможен.

также постороннее решение.

Теперь рассмотрим случай k11, k13 1, k 31 1. Возможны четыре варианта:

являются посторонними решениями.

( x & z11 y ) & z13 – также являются посторонними решениями.

x & z11 & z 31 y – также являются посторонними решениями.

подфункцию – дизъюнкцию, а на другом – в конъюнкцию, то они не могут одновременно входить в промежуточный подкуб, так как все собственные подфункции f по условию бесповторны. Следовательно, одновременно могут появиться переменные y и z13 либо y и z 31 – это равносильно тому, что размерности нижнего левого и верхнего правого подкубов равны единице.

Значит, искомая функция f ( x, y, u1, ~11, z13, z 31 ) имеет вид однотипная с функцией f 4 из четвертого семейства функций Стеценко, которая повторна.

Следовательно, этот вариант также невозможен.

Наконец, в случае k 22, k 23 1 и k 32 1 получаемые функции обобщенно однотипны с функциями, возникающими в предыдущем случае. Лемма доказана.

Теорема 3. Всякая поляризуемая функция, имеющая запретную шестерку, обладает подфункцией, обобщенно однотипной с некоторой функцией третьего, четвертого или пятого семейства Стеценко, то есть с f m, f 4 или f 5.

Доказательство теоремы 3 вытекает из леммы 4 и леммы 5.

Теорема 4. Всякая функция, имеющая запретную четверку или запретную шестерку, обладает подфункцией, обобщенно однотипной с некоторой функцией Стеценко: (4) (3).

Доказательство теоремы 4 следует из теоремы 2 и теоремы 3.

2.3. Публикации результатов НИР По результатам проведенных исследований сделана публикация в трудах научной конференции и опубликована статья в высокорейтинговом российском журнале:

• В. Б. Ларионов О надструктуре некоторых классов функций k-значной логики // XVI международная конференция "Проблемы теоретической кибернетики" (Нижний Новгород, 20–25 июня 2011 г.). Нижний Новгород: изд-во Нижегородского государственного университета. 2011. С. 263-266.

• А. А. Вороненко, В. С. Федорова, Д. В. Чистиков Повторность булевых функций в элементарном базисе // Известия вузов. Серия Математика. 2011, № 11, c. 72– Копии статей включены в Приложение А к настоящему отчету, заключения экспертной комиссии по их открытому опубликованию – в Приложение Б.

3. Заключение В рамках второго этапа работ по Государственному контракту проведены следующие исследования в соответствии с планом:

1. Доказана конечность надструктуры классов функций многозначной логики специального вида, являющихся некоторым обобщением классов самодвойственных функций, – классов квазисамодвойственных функций.

2. Доказана повторность дискретных функций специального вида по информации об их значениях на некоторых наборах.

3. По результатам исследований сделана публикация в трудах научной конференции и опубликована статья в высокорейтинговом российском журнале.

4. Подготовлен научно-технический отчет по итогам второго этапа.

План проведения исследований второго этапа выполнен полностью. Копии статей приводятся в Приложении А. Все полученные научные результаты являются новыми;

перед их публикацией получено заключение экспертной комиссии по открытому опубликованию (Приложение Б). Материалы, описывающие проведение исследований, включают все необходимые сведения для обеспечения возможности воспроизведения результатов.

4. Список использованных источников 1. Янов Ю. И., Мучник А. А. О существовании k-значных замкнутых классов, не имеющих конечного базиса // Доклады АН СССР. 1959. Т. 127, № 1. С. 44–46.

2. Rosenberg I. G. La structure des fonctions de plusiers variables sur un ensemble fini // Comptes Rendus Acad. Sci. Paris. 1965. Volume 260. P. 3817–3819.

3. Яблонский С. В. Функциональные построения в k-значной логике // Труды математического института имени В. А. Стеклова Академии наук СССР. 1958.

Т. 51. С. 5–142.

4. Ларионов В. Б. О положении самодвойственных k-значных функций в решетке замкнутых классов // Сборник статей молодых ученых факультета ВМК МГУ.

2009. Вып. 6. С. 90–105.

5. Стеценко В. А. О предплохих базисах в Р2 // Математические вопросы кибернетики. Вып. 4. М.: Физматлит, 1992. С. 139-177.

6. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

7. Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // ДАН СССР. 1963. Т. 149. № 4. С. 784–787.

8. Гурвич В. А. О бесповторных булевых функциях // Успехи матем. наук. 1977. Т.

32. № 3. С. 183–184.

9. Вороненко А. А. О длине проверяющего теста для бесповторных функций в базисе {0, 1, &,, ¬ } // Дискретная математика. Т. 17. № 2. 2005. C. 139–143.

10. Вороненко А. А. О проверяющих тестах для бесповторных функций // Математические вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 163–