О сложности реализации функций многозначной логики формулами специального вида тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

005054223

На правах рукописи УДК 519.95

Трущин Дмитрий Владимирович

О СЛОЖНОСТИ РЕАЛИЗАЦИИ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ ФОРМУЛАМИ СПЕЦИАЛЬНОГО ВИДА

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2012

- 1 НОЯ 2012

005054223

Работа выполнена на кафедре дискретной математики Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор Угольников Александр Борисович

Официальные оппоненты: Глухов Михаил Михайлович

Ведущая организация: ФГАОУ ВПО «Казанский (Приволжский)

федеральный университет»

Защита диссертации состоится 30 ноября 2012 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж). Автореферат разослан 30 октября 2012 года.

Ученый секретарь диссертационного совета

доктор физико-математических наук, профессор (Академия криптографии РФ, академик-секретарь отделения)

Стеценко Владимир Алексеевич кандидат физико-математических наук, доцент (ФГБОУ ВПО«Московский педагогический государственный университет»)

14-08.

Д.501.001.84 при МГУ

доктор физико-математических наук,

профессор

Иванов Александр Олегович

Общая характеристика работы

Актуальность темы

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

Одной из основных задач математической кибернетики является построение и изучение модельных классов управляющих систем с точки зрения их сложности. В общем случае эта задача может быть сформулирована следующим образом. Рассматривается набор базисных элементов, из которых но некоторым правилам строятся более сложные объекты — управляющие системы (например, схемы из функциональных элементов, контактные схемы, формулы). Заданы правила, позволяющие каждой системе сопоставить реализуемую ей функцию. Кроме того, каждой системе сопоставлено положительное число (сложность), которое характеризует ее стоимость. Рассматриваемая задача состоит в построении по заданной функции такой управляющей системы, которая реализует эту функцию и является оптимальной относительно выбранной меры сложности; при этом сложность построенной системы называется сложностью этой функции. Для заданного множества функций исследуется также поведение функции Шеннона, которая характеризует сложность реализации в рассматриваемом классе управляющих систем самой сложной функции, принадлежащей этому множеству и зависящей от фиксированного числа перменных.

Пусть к > 2. Положим Ек = {0,1....,к - 1}. Обозначим через Рк множество всех функций /г-значной логики. Формулы над конечными базисами, реализующие функции из Рк, — один го основных модельных классов управляющих систем. Основными мерами сложности формул являются

число символов неременных, входящих в формулу, и глубина; число символов переменных характеризует "стоимость", а глубина — время вычисления реализуемой функции. Для каждой конечной системы 21 С Рк через [2t] обозначим множество функций, реализуемых нетривиальными формулами над системой 21. Пусть Fe [21]. Функцию Шеннона по сложности (числу символов переменных) для множества F обозначим через L^(F(n)), а функцию Шеннона по глубине — через D<n(F(n)). Если F = [21], то функции Шеннона L<n(F(n)) и Dz(F(n)) обозначается также через Ь&(п) и Да(п) соответственно.

Асимптотически оптимальные методы синтеза для основных модельных классов управляющих систем были разработаны О. Б. Лунановым1. В частности, он показал, что для любого полного в Р2 конечного базиса 21 имеет место асимптотическое равенство

2"

Z,a(n) ~ Рт——, log2n

где р — константа, зависящая от системы 21 (минимальный приведенный вес элементов базиса).

Наряду с задачей о поведении функции Шеннона для класса Р2, рассматривается также задача о поведении функции Шеннона для различных подмножеств этого множества. Одной из наиболее известных и хорошо изученных с функциональной точки зрения классификаций булевых функций является описание семейства всех замкнутых относительно операции суперпозиции классов функций, полученное Э. Постом2. Он показал, что это семейство является счетным, и что для каждого замкнутого класса существует конечная порождающая система.

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

1Лупанов ОБ. Об одном методе синтеза схем ,// Известия вузов, Радиофизика Т. 1958. С. 120-140. Лупанов О.Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960. 61-80.

Лугтнов О.Б. Об одном классе схем из функционльных элементов // Проблемы кибернетики. 1961. Вып. 7. С. 60-114.

2Post E.L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43, 3. 163-185. Post E.L. Two valued iterative systems of mathematical logic 11 Annals of Math. Studies. Princeton-London; Princeton Univ. Press. 1941. 5. 122.

задачи — синтез в полных базисах и синтез в неполных базисах. Для каждого нолного конечного базиса и каждого замкнутого класса булевых функций, не содержащегося полностью ни в одном из классов3 S,L,K,D, асимптотически точные формулы для соответствующих функций Шеннона были получены А. Е. Андреевым4. Для некоторых замкнутых классов и любых конечных систем, порождающих эти классы, асимптотически точные формулы для соответствующих функций Шеннона получены А. Б. Угольниковым5. Он показал также6, что для произвольной конечной системы булевых функций функции Шеннона по глубине и сложности имеют соответственно линейный и экспоненциальный порядок роста относительно числа переменных.

Таким образом, в задаче о сложности реализации булевых функций получен ряд существенных результатов. Получение аналогичных результатов для функций А;-значной логики (к > 3) сопряжено со значительными трудностями, которые связаны с континуальностью семейства замкнутых классов7 и отсутствием описания семейства всех конечнопорожденых замкнутых классов. Вместе с тем, для некоторых полных в Рк базисов асимптотически точные формулы для соответствующих функций Шеннона были получены в работах Ю.В. Захаровой8, С. Б. Гашкова9, С. А. Ложкина10. Задачу о реализации формулами функций из класса11 Р3,2 исследовал Д. А. Дагаев12.

3Здесь S — класс всех самодвойственых функций, L — класс всех линейных функций, К — класс всех конъюнкций, D — класс всех дизъюнкций.

Андреев А.Е. О сложности монотонных функций // Вестник Московского университета. Сер. 1, Математика. Механика. М.: Изд-во МГУ, 1985. Вып. 4. С. 83-87.

Андреев А.Е. О синтезе функциональных сстей // Докт. диссертация. М.: МГУ им. М.В.Ломносова, 1985.

Угольников А.Б. Синтез схем и формул в неполных базисах // Докл. АН СССР. 1979. 249, 1. 60-62. Угольников А.Б. Синтез схем и формул в неполных базисах // Препринт ИПМ АН СССР. 1980. Вып. 112.

Угольников A.B. О глубине формул в неполных базисах // Математические вопросы кибернетики. 1988, выи. 1. 242-245.

7Янов Ю.И., Мучник A.A. О существовании fc-значных замкнутых классов, не имеющих конечного базиса //Докл. АН СССР. 1959. 127, 1. С. 44-46.

Захарова Ю.В. Реализация функций из Рк формулами // Матем. заметки. 1972. Т. 11 , вып. 1. С. 99-108.

Гашков С.Б. О параллельном вычислении некоторых классов многочленов с растущим числом переменных ,// Вестник Московского университета. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 1990. Вып. 2. С. 88-92.

ыЛожкин С.А. О сложности реализации функций к-значной логики формулами и квазиформулами /,/ Проблемы теоретической кибернетики' Мат-лы XI Междупар. коиф. Ульяновск. М.: РГГУ, 1908. С. 125-127.

Здесь — класс всех функций fc-значной логики, принимающих значения 0 и 1, к > 3.

Дагаев Д.А. О сложности функций многозначной логики, принимающих два значения // Канд.

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

Одно из важных направлений исследований в задачах синтеза формул над конечными базисами состоит в исследовании реализации функций формулами специального вида. Подобный подход можно найти в ряде работ14. В работах О. Б. Лупанова15 изучаются формулы ограниченной глубины в базисе {V, -л}, включающие дизъюнктивные и конъюнктивные нормальные формы. В этих работах показано, что при построении асимптотически наилучших формул для почти всех функций алгебры логики достаточно ограничиваться формулами глубины не более 3. К этому направлению исследований относится также задача о реализации функций многозначной логики а-формулами, т.е. такими формулами, в которых каждая подформула содержит не более одной нетривиальной главной подформулы. Впервые эту задачу рассмотрел М. М. Глухов16. Он показал существование в Pk при к > 7 конечных

диссертация. М.: МГУ им. М.ВЛомносова, 2011.

13Угольников A.B. О сложности реализации формулами одной последовательности функций многозначной логики // Математические вопросы кибернетики. 1989, вып. 2. 174-176.

Угольников A.B. О сложности реализации формулами одной последовательности функций 4-значной логики // Вестпик Московского университета. Сер. 1. Математика. Механика. 2004. Вып. 3. С. 52-55. Андреев A.A. Об одной последовательности функций многозначной логики // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 2011. Выи. 6. С. 52-57.

l4Abhyankar S. Minimal «sum of products sum» expressions of Boolean functions. IRE Trans., EC-7, 4, 1958. 268-276.

Лупанов O.B. Об асимптотических оценках сложности формул, реализующих функции алгебры логики // Докл. АН СССР. 1959. Т. 128, 3. С. 464-467.

Васильев Ю.Л., Глаголев В.В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974. 99-147.

15 Лупанов О.Б. О реализации функций алгебры логики формулами ограниченной глубины в базисе // Докл. АН СССР. 1961. Т. 136, 5. С. 1041-1042. Лупанов О.В. О реализации функций алгебры логики формулами ограниченной глубины в базисе {V, // Проблемы кибернетики. Вып. 6. М.; Физматгиз, 1961. С. 5-13.

13 Глухое М.М. Об а-замкнутых классах и а-полных системах функций к-значной логики // Дискретная

а-полных систем17. А. Л. Чернышев18 нашел условия а-полноты систем функций многозначной логики, при каждом к > 5 построил а-полные системы из двух бинарных операций с правым сокращением, а также показал отсутствие конечных а-полных систем в Р2. А. Л. Шабунин19 привел примеры конечных а-полных систем в Р3 и Р4.

Цель работы

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

Основные методы исследования

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

Научная новизна

Все результаты диссертации являются новыми. В диссертации получены следующие основные результаты.

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

2. Выделено семейство двоично представимых функций трехзначной логики, для которого значения функции Шеннона над некоторой а-полной

математика. 1989. Т. 1, вып. 1. С. 16-21.

"Система функций называется а-полной, если каждую функцию ¿-звачной логики можно реализовать а-формулой над этой системой.

18 Чернышев А.Л. Условия а-полноты систем функций многозначной логики // Дискретная математика. 1992. Т. 4, вып. 4. С. 117-130.

19Шабунин А.Л. Примеры а-полных систем і-значной логики при к = 3,4 // Дискретная математика. 2006. Т. 18, вып. 4. С. 45-35.

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

3. Для каждой конечной системы функций Акзначной логики (к > 3), принимающих только значения 0 и 1, получены полиномиальные верхние оценки для соответствующих функций Шеннона.

4. Для каждого простого к, к > 3, получены верхние оценки вида скп, где с < 1, для глубины произвольной функции А;-значной логики над некоторой а-полной системой.

Теоретическая и практическая ценность

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

Апробация результатов

Результаты диссертации неоднократно докладывались на семинаре "Функции многозначной логики и смежные вопросы" под руководством проф. А. Б. Угольникова, проф. Р. М. Колпакова и проф. С. Б. Гашкова (2008-2012 гг.), на семинаре "Синтез и сложность управляющих систем" под руководством проф. О.М. Касим-Заде (2009 г.), на X Международном семинаре "Дискретная математика и ее приложения" (Москва, 2010 г.), на XVI Международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород, 2011 г.), на VIII молодежной научной школе по дискретной математике и ее приложениям (Москва, 2011 г.), на XI Международном семинаре "Дискретная математика и се приложения" (Москва, 2012 г.), на Научной конференции "Ломоносовские чтения" в МГУ имени М. В. Ломоносова (2008-2012 гг.).

Публикации

Основные результаты диссертации опубликованы в б работах, список которых приведен в конце автореферата [1-6].

Структура и объем диссертации

Диссертация состоит из введения, четырех глав и списка литературы. Полный объем диссертации — 78 страниц. Список литературы содержит 55 наименований.

Содержание работы

В диссертации рассматривается задача о сложности реализации а-формулами функций ¿-значной логики (А; > 2). В качестве меры сложности формул выступает глубина. Для каждой конечной системы функций 21 через [21]ц обозначается ее а-пополнение. т.е. множество всех функций, реализуемых нетривиальными а-формулами над системой 01. Для каждой функции / £ [21]а глубина этой функции обозначается через £>§[(/). Исследуется поведение функции Шеннона .0§(п).

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

В главе 1 приводятся основные определения и обозначения, а также вспомогательные утверждения.

В главе 2 рассматриваются функции двузначной логики. Сначала приводится описание эквивалентных преобразований формул над конечными системами булевых функций. Затем с использованием этих преобразований для рассматриваемых систем функций получены полиномиальные верхние и нижние оценки для функций Шеннона.

Основным результатом главы 2 является

Теорема 1. Пусть тг > 1, 21 — произвольная конечная система булевых функций, /(х1,..., хп) £ [21]а. Пусть т(21) — максимальное число переменных у функций из 21, а р(21) — максимальное число переменных у немонотонных функций из 21. Тогда

Щ(Л < спГ,

где с — некоторая константа, зависящая от 21, г — т(21) +р(21) — 2.

Также в этой главе получен критерий существования в заданном замкнутом классе булевых функций конечной (^-порождающей системы.

Теорема 2. Пусть F — замкнутый класс булевых функций. Конечная система 21 булевых функций, такая, что Р С [21]а, существует тогда и только тогда, когда F полностью содержится в одном из классов К, Ь.

Кроме того, в главе 2 для некоторых конечных систем функций получены точные по порядку нижние оценки для функций Шеннона.

В главе 3 рассматривается задача о реализации двоично представимых функций трехзначной логики «-формулами над системой из всех бинарных операций с правым сокращением. Сформулируем необходимые определения. Пусть к > 2. Двухместная функция д(х, г) е Рк называется бинарной операцией с правым сокращением, если для любых элементов Ь, с € Ек существует, и притом ровно один элемент а е Ек, такой, что д(а,Ь) = с. Множество всех бинарных операций с правым сокращением обозначается через 23к- Функция и>(х\,... ,хп) € Рк называется двоично представимой, если существуют функция /1(2:1,... ,х„) е Рк и функции щ(хх),..., ип(х„) £ Рк,2, такие, что ги(х1, ...,хп)= Ци^хх),..., ип(хп)).

В этой главе построен пример последовательности двоично представимых функций трехзначной логики, имеющей экспоненциальную относительно числа переменных сложность над системой ш3.

Теорема 3. Для любого п>1 и любого набора а — (01, аг,..., а,п, с) из Е%+1, такого, что с ф 0, имеет место неравенство

где

I С, если Ж; = <2г, I = 1, . . . П, фа(х 1,...,Хп) = <

I 0, иначе.

Обозначим через IV множество всех двоично представимых функций трехзначной логики. В работе значения функции Шеннона 0%з(\У(п)) найдены с точностью до аддитивной константы.

Теорема 4. Для любого п > 1 имеют место неравенства

2" - 2 < 0% (\¥{п)) < 2" - 1.

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

В главе 4 рассматривается реализация произвольных функций А>значной логики (к > 3). В первом разделе результаты главы 1 обобщены для функций многозначной логики, принимающих только значения 0 и 1. Получены полиномиальные верхние оценки для функций Шеннона.

Теорема 5. Пусть 21 — произвольная конечная система функций из Р^, , хп) € [21]о. Пусть тп(21) — максимальное число переменных у функций из 21. Тогда

Д£(/М) < спг,

где с — некоторая константа, зависящая от 21, г = 2(т(21) — 1).

Пусть п > 1, /(хь..., хп) 6 Рассмотрим булеву функцию д{х\,..хп), такую, что для любого набора а € имеет место равенство д(а) — /(а). Булева функция д называется проекцией функции / и обозначается через рг(/). Для любого множества функций Р С Р^2 через рг(Р) обозначим множество всех функций, являющихся проекциями функций из множества F. Легко видеть, что если Р — замкнутый класс функций /г-значной логики, то рг(Р) — замкнутый класс булевых функций. Следствием теоремы 5 является следующее утверждение.

Теорема 6. Пусть к > 3, Р — замкнутный класс функций к-значной логики, F С Рк,2- И пусть класс рг(Р) не содержится полностью ни в одном из классов Ь, К, Б. Тогда не существует конечной системы 21 функций к-значной логики, такой, что Р С [21]а.

Во втором разделе главы 4 для каждого простого к, к > 3, получены верхние оценки сложности произвольной функции &-значной логики над системой 93^, состоящей из всех бинарных операций с правым сокращением.

Теорема 7. Пусть к — простое число, к > 3, п > 1. Тогда система 03 * является а-полной и имеет место неравенство

Доказано, что справедливы следующие асимптотические верхние и нижние оценки соответствующей функции Шеннона.

Теорема 8. Пусть к — простое число, к > 3, п > 1. Тогда справедливы неравенства

< па („\ < ~ 1 /-"

Автор выражает глубокую искреннюю благодарность своему научному руководителю доктору физико-математических наук, профессору А. Б. Угольникову за постановку задачи и постоянное внимание к работе.

Публикации автора по теме диссертации

1. Трущин Д.В. О глубине a-пополнений систем булевых функций // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2009. Вып. 2. С. 72-75.

2. Трущин Д.В. О сложности реализации функций из одного класса трехзначной логики формулами специального вида // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2012. Вып. 4. Стр. 20-26.

3. Трущин Д.В. О нижних оценках глубины формул специального вида // Мат-лы X Междунар. сем. "Дискретная математика и ее приложения" (Москва, 1-6 февраля 2010 г.) — М.: Изд-во механико-математического факультета МГУ, 2010. С. 139-141.

4. Трущин Д.В. Об оценках глубины a-пополнений систем функций трехзначной логики // Проблемы теоретической кибернетики: Мат-лы XVI Междунар. конф. Н.Новгород: Изд-во ННГУ, 2011. С. 484-487.

5. Трущин Д.В. О сложности реализации функций трехзначной логики формулами специального вида // Мат-лы VIII молодежной научной школы по дискретной математике и ее приложениям (Москва 24-29 октября 2011 г.). Часть II. С. 44-48.

6. Трущин Д.В. О сложности реализации функций многозначной логики формулами специального вида // Мат-лы XI Междунар. сем. "Дискретная математика и ее приложения" (Москва, 18-23 июня 2012 г.) М.: Изд-ва механико-математического факультета МГУ, 2012. С. 174-176.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ ТиражС экз. Заказ №

Введение

1 Определения и вспомогательные утверждения

1.1 Основные определения и обозначения.

1.2 Некоторые замкнутые классы.

1.3 Бинарные операции с правым сокращением.

2 Булевы функции

2.1 Эквивалентные преобразования а-формул

2.2 Верхние оценки функций Шеннона.

2.3 Реализация монотонных функций.

2.4 Реализация немонотонных функций.

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

3.1 Критерий двоичной представимости функции

3.2 Частичная эквивалентность многочленов.

3.3 Сопоставление многочленов формулам

3.4 Верхние оценки функции Шеннона для класса двоично представимых функций.

3.5 Нижние оценки функции Шеннона для класса двоично представимых функций.

3.6 Верхние оценки глубины для произвольной функции.

4 Функции многозначной логики

4.1 Функции из Р/г)

4.2 Верхние оценки глубины для произвольной функции Список литературы

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

Одной из основных задач математической кибернетики является построение и изучение модельных классов управляющих систем с точки зрения их сложности. В общем случае эта задача, может быть сформулирована следующим образом. Рассматривается набор базисных элементов, из которых по некоторым правилам строятся более сложные объекты — управляющие системы (например, схемы из функциональных элементов, контактные схемы, формулы). Заданы правила, позволяющие каждой системе сопоставить реализуемую ей функцию. Кроме того, каждой системе сопоставлено положительное число (сложность), которое характеризует ее стоимость. Рассматриваемая задача состоит в построении по заданной функции такой управляющей системы, которая реализует эту функцию и является оптимальной относительно выбранной меры сложности; при этом сложность построенной системы называется сложностью этой функции. Для заданного множества функций исследуется также поведение функции Шеннона, которая характеризует сложность реализации в рассматриваемом классе управляющих систем самой сложной функции, принадлежащей этому множеству и зависящей от фиксированного числа перменных.

Пусть к > 2. Положим = {0,1,.,/: — 1}. Обозначим через Рк множество всех функций &-значной логики. Формулы над конечными базисами, реализующие функции из Р;с, — один из основных модельных классов управляющих систем. Основными мерами сложности формул являются число символов переменных, входящих в формулу, и глубина; число символов переменных характеризует "стоимость", а глубина — время вычисления реализуемой функции. Для каждой конечной системы 21 С Рк через [21] обозначим множество функций, реализуемых нетривиальными формулами над системой 21. Пусть Р € [21]. Функцию Шеннона по сложности (числу символов переменных) для множества Р обозначим через Ь%(Р(п)), а функцию Шеннона по глубине — через Дя^п)). Если Р = [21], то функции Шеннона Ь^(Р(п)) и Да{Р(п}) будем обозначать также через Ь%(п) и соответственно.

Асимптотически оптимальные методы синтеза для основных модельных классов управляющих систем были разработаны О. Б. Лупановым [14, 15, 20, 21, 22, 23, 24, 25]. В частности, он показал [16, 17], что для любого полного в Рч конечного базиса 21 имеет место асимптотическое равенство

2 п

Ь%(п) ~ р--,

1оё2 п где р — константа, зависящая от системы 21 (минимальный приведенный вес элементов базиса).

Наряду с задачей о поведении функции Шеннона для класса Р2, рассматривается также задача о поведении функции Шеннона для различных подмножеств этого множества. Одной из наиболее известных и хорошо изученных с функциональной точки зрения классификаций булевых функций является описание семейства всех замкнутых относительно операции суперпозиции классов функций, полученное Э. Постом [46, 47]. Он показал, что это семейство является счетным, и что для каждого замкнутого класса существует конечная порождающая система. Изложение этих результатов содержится также в [40, 32, 26, 44, 27, 45, 35].

При исследовании задачи синтеза формул в конечных базисах, реализующих функции из замкнутых классов Поста, рассматриваются две отдельные задачи — синтез в полных базисах и синтез в неполных базисах. Для каждого полного конечного базиса и каждого замкнутого класса булевых функций, не содержащегося полностью ни в одном из классов1 3,Ь,К,И, асимптотически точные формулы для соответствующих функций Шеннона были получены А. Е. Андреевым [3, 4]. Для некоторых замкнутых классов и любых конечных систем, порождающих эти классы, асимптотически точные формулы для соответствующих функций Шеннона получены А. Б. Угольниковым [28, 29]. Он показал также [30, 31], что для произвольной конечной системы булевых функций функции Шеннона по глубине и сложности имеют соответственно линейный и экспоненциальный порядок роста относительно числа переменных.

Таким образом, в задаче о сложности реализации булевых функций получен ряд существенных результатов. Получение аналогичных результатов для функций Ахзначной логики (к > 3) сопряжено со значительными трудностями, которые связаны с континуальностью семейства замкнутых классов [42] (см. также [41]) и отсутствием описания семейства всех конечнопорожденых замкнутых классов2. Вместе с тем, для некоторых полных в базисов асимптотически точные формулы для соответствующих функций Шеннона были получены в работах Ю. В. Захаровой [11], С. Б. Гашкова [6], С.А. Ложкина [13]. Задачу о реализации формулами функций из класса3 Рз,2 исследовал Д.А. Дагаев [8, 9, 10]. Он получил оценки и асимптотически точные формулы для функций Шеннона, соответствующих некоторым замкнутым классам. В то же время при исследовании задачи синтеза формул в неполных базисах приведены примеры последовательностей функций многозначной логики, сложность которых имеет сверхэкспоненциальный порядок роста относительно числа переменных [31, 33, 34, 1, 2]. Эти результаты говорят о принципиальных отличиях многозначных логик от двузначной логики с точки зрения теории сложности.

Одно из важных направлений исследований в задачах синтеза формул над конечными базисами состоит в исследовании реализации функций формулами

1 Здесь Б — класс всех самодвойственых функций, Ь — класс всех линейных функций, К — класс всех конъюнкций, О — класс всех дизъюнкций.

2К настоящему времени получено описание лишь отдельных семейств замкнутых классов функций многозначной логики (см., например, работы [38, 39, 48, 49]).

З3десь РК2 — класс всех функций к-значной логики, принимающих значения 0 и 1, к > 3. специального вида. Подобный подход можно найти в ряде работ [43, 16, 5]. В работах О. Б. Лупанова [18, 19] изучаются формулы ограниченной глубины в базисе {У,&,-п}, включающие дизъюнктивные и конъюнктивные нормальные формы. В этих работах показано, что при построении асимптотически наилучших формул для почти всех функций алгебры логики достаточно ограничиваться формулами глубины не более 3. К этому направлению исследований относится также задача о реализации функций многозначной логики си-формулами, т.е. такимим формулами, в которых каждая подформула содержит не более одной нетривиальной главной подформулы. Впервые эту задачу рассмотрел М. М. Глухов [7]. Он показал существование в Рь при к > 7 конечных а-полных систем4. А. Л. Чернышов [36] нашел условия а-полноты систем функций многозначной логики, при каждом к > 5 построил а-полные системы из двух бинарных операций с правым сокращением, а также показал отсутствие конечных о;-полных систем в Р2. А. Л. Шабунин [37] привел примеры конечных а-полных систем в Рз и Р4.

В данной работе рассматривается задача о сложности реализации а-формулами функций Акзначной логики (к > 2). В качестве меры сложности формул выступает глубина. Для каждой конечной системы функций 21 через [21]а обозначается ее а-пополнение, т.е. множество всех функций, реализуемых нетривиальными си-формулами над системой 21. Для каждой функции / € [21] а глубина этой функции обозначается через !)$(/). Исследуется поведение функции Шеннона

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

1. Андреев A.A. Об одной последовательности функций многозначной логики // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 2011. Вып. 6. С. 52-57.

2. Андреев A.A. Об одной последовательности функций многозначной логики / / Мат-лы XI Междунар. сем. "Дисретная математика и ее приложения" (Москва, 18-23 июня 2012 г.) М.:Изд-во механико-математического факультета МГУ, 2012. С. 88-90.

3. Андреев А.Е. О сложности монотонных функций // Вестник Московского университета. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 1985. Вып. 4. С. 83-87.

4. Андреев А.Е. О синтезе функциональных сетей // Докт. диссертация. М.: МГУ им. М.В.Ломносова, 1985.

5. Васильев Ю.Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974. С. 99-147.

6. Гашков С. В. О параллельном вычислении некоторых классов многочленов с растущим числом переменных // Вестник Московского университета. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 1990. Вып. 2. С. 88-92.

7. Глухое М.М. Об а-замкнутых классах и а-пол пых системах функций fc-значной логики // Дискретная математика. 1989. Т. 1, вып. 1. С. 16-21.

8. Дагаев Д.А. О сложности псевдолинейных функций // Вестник Московского университета. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 2010. Вып. 2. С. 53-56.

9. Дагаев Д.А. О сложности функций из некоторых классов трехзначной логики // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 2011. Вып. 3. С. 60-63.

10. Дагаев Д.А. О сложности функций многозначной логики, принимающих два значения // Канд. диссертация. М.: МГУ им. М.В.Ломносова, 2011.

11. Захарова Ю.В. Реализация функций из Рк формулами // Матем. заметки. 1972. Т. 11, вып. 1. С. 99-108.

12. Курош А.Г. Курс высшей алгебры. М.: Наука, 1975.

13. Ложкин С.А. О сложности реализации функций /¿-значной логики формулами и квазиформулами // Проблемы теоретической кибернетики: Мат-лы XI Междунар. конф. Ульяновск. М.: РГГУ, 1996. С. 125-127.

14. Лупанов O.E. О синтезе контактных схем // ДАН СССР. 1958. Т. 119. 1. С. 23-26.

15. Лупанов О.В. Об одном методе синтеза схем // Известия вузов, Радиофизика I. 1958. С. 120-140.

16. Лупанов О.Б. Об асимптотических оценках сложности формул, реализующих функции алгебры логики // ДАН СССР. 1959. Т. 128, вып. 3. С. 464-467.

17. Лупанов О.Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып.З. М.: Физматгиз, 1960. С. 61-80.

18. Лупанов О. Б. О реализации функций алгебры логики формулами ограниченной глубины в базисе {V,&,-.} // Докл. АН СССР. 1961. Т. 136, 5. С. 1041-1042.

19. Лупанов О. Б. О реализации функций алгебры логики формулами ограниченной глубины в базисе -1} // Проблемы кибернетики. Вып. 6. М.: Физматгиз, 1961. С. 5-13.

20. Лупанов О.Б. Об одном классе схем из функциональных элементов // Проблемы кибернетики. Вып. 7. М.: Физматгмз, 1961. С. 60-114.

21. Лупанов О.Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. 1963. Вып. 10. С. 63-97.

22. Лупанов О.Б. О сложности реализации функций алгебры логики релейно-контактными схемами // Проблемы кибернетики. 1964. Вып. 11. С. 25-48.

23. Лупанов О. Б, Об одном подходе к синтезу управляющих систем — методе локального кодирования // Проблемы кибернетики. 1965. Вып. 14. С. 31-110.

24. Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики. 1973. Вып. 26. С. 109-140.

25. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: МГУ, 1984.

26. Марчепков С. С., Угольников А.Б. Замкнутые классы булевых функций. М.: ИПМ АН СССР, 1990.

27. Марченков С. С. Замкнутые классы булевых функций. М.: Физматлит, 2000.

28. Угольников А.Б. Синтез схем и формул в неполных базисах // Докл. АН СССР. 1979. 249, 1. С. 60-62.

29. Угольников А.Б. Синтез схем и формул в неполных базисах // Препринт ИПМ АН СССР. 1980. Вып. 112.

30. Угольников А.Б. О глубине формул в неполных базисах // Математические вопросы кибернетики. 1988, вып. 1. С. 242-245.

31. Угольников А.Б. О глубине и сложности формул, реализующих функции из замкнутых классов // Докл. АН СССР. 1988. 298, вып.6. С. 1341-1344.

32. Угольников А.Б. О замкнутых классах Поста // Известия ВУЗов. Математика. 1988. 7 (314). С. 79-88.

33. Угольников А.Б. О сложности реализации формулами одной последовательности функций многозначной логики // Математические вопросы кибернетики. 1989, вып. 2. С. 174-176.

34. Угольников А.Б. О сложности реализации формулами одной последовательности функций 4-значной логики // Вестник Московского университета. Сер. 1. Математика. Механика. 2004. Вып. 3. С. 52-55.

35. Угольников A.B. Классы Поста. М.: Изд-во ЦПИ при мех.-мат. ф-те МГУ им. М.В.Ломоносова, 2008.

36. Чернышов А.Л. Условия а-полноты систем функций многозначной логики // Дискретная математика. 1992. Т. 4, вып. 4. С. 117-130.

37. Шабунин А.Л. Примеры а-полных систем /г-значной логики при к = 3,4 // Дискретная математика. 2006. Т. 18, вып. 4. С. 45-55.

38. Яблонский C.B. О функциональной полноте в трехзначном исчислении // Докл. АН СССР. 1954. 95, вып. 6. С.1152-1156.

39. Яблонский C.B. Функциональные построения в /г-значной логике // Труды матем. ин-та АН СССР им. Стеклова. 1958. Т. 51. С. 5-142.

40. Яблонский C.B., Гаврилов Г.П., Кудрявцев В.В. Функции алгебры логикии и классы Поста. М.: Наука, 1966.

41. Яблонский C.B. Введение в дискретную математику. М.-Высшая школа, 2008.

42. Янов Ю.И., Мучник A.A. О существовании fc-значных замкнутых классов, не имеющих конечного базиса //Докл. АН СССР. 1959. 127, 1. С. 44-46.

43. Abhyankar S. Minimal «sum of products sum» expressions of Boolean functions. IRE Trans., EC-7, 4, 1958. P. 268-276.

44. Lau D. On closed subsets of Boolean functions (A new proof of Post's theorem) // J. Process. Cybern. EIK. 1991. V. 27, 3. P. 167-178.

45. Lau. D. Function Algebras on Finite Sets. Springer-Verlag, Berlin, 2006.

46. Post E.L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43, 3. P. 163-185.

47. Post E.L. Two valued iterative systems of mathematical logic // Annals of Math. Studies. Princeton-London: Princeton Univ. Press. 1941. 5. 122.

48. Rosenberg I. G. La structure des functions de plusieurs variables sur un ensemble finil // Comptes Rendus, de l'Academ. Paris, Ser. A.B. 260. 1965. P. 3817-3819.

49. Rosenberg I.G. Uber die funktionale Vollständigkeit in den mehrvertigen Logiken // Rozpravy Öeskoslovenske Academie ved. Rada matematickych a priridnich ved. Praha, 1970. Rocnik 80, Sesit 4. S. 3-93.

50. Трущин Д. В. О глубине а-пополнений систем булевых функций // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2009. Вып. 2. С. 72-75.

51. Трущин Д.В. О нижних оценках глубины формул специального вида // Мат-лы X Междунар. сем. "Дисретная математика и ее приложения" (Москва, 1-6 февраля 2010 г.) — М.: Изд-во механико-математического факультета МГУ, 2010. С. 139-141.

52. Трущин Д.В. Об оценках глубины Cü-пополнений систем функций трехзначной логики // Проблемы теоретической кибернетики: Мат-лы XVI Междунар. конф. Н.Новгород: Изд-во ННГУ, 2011. С. 484-487.

53. Трущин Д.В. О сложности реализации функций трехзначной логики формулами специального вида // Мат-лы VIII молодежной научной школы по дискретной математике и ее приложениям (Москва 24-29 октября 2011 г.). Часть II. С. 44-48.

54. Трущин Д.В. О сложности реализации функций из одного класса трехзначной логики формулами специального вида // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2012. Вып. 4. Стр. 20-26.