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

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

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

Михайлец Екатерина Викторовна пл

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 5 \М,? Ш

Москва - 2012

005014081

005014081

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

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Касим-Заде Октай Мурадович, доктор физико-математических наук, профессор.

Глухов Михаил Михайлович, доктор физико-математических наук, профессор, ак.-секретарь отделения Академии криптографии РФ; Сапоженко Александр Антонович, доктор физико-математических наук, профессор кафедры математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Институт математики имени С. Л. Соболева СО РАН.

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

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

Автореферат разослан 22 февраля 2012 г.

Ученый секретарь

диссертационного совета

Д.501.001.84 при МГУ

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

профессор

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

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

Вопрос о сложности реализации функций fc-зпачпой логики посредством различных видов схем является одним из центральных вопросов в теории управляющих систем. Одни из первых значительных результатов в этой области принадлежат К. Э. Шеннону1. Им был предложен новый подход к изучению проблем сложности, основанный на рассмотрении функционалов, характеризующих наибольшую сложность функций из класса К при реализации схемами из класса U управляющих систем. К.Э. Шеннон ввел величину Ьц(К), характеризующую сложность реализации любой функции из класса К в классе управляющих систем U, названную функцией Шеннона.

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

1 Shannon С.Е. The synthesis of two-terminal switching circuits // Bell Syst. Techn. Joum., 1949. V. 28. № 1. P. 59-98 (русский перевод: Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963.).

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

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

3Андреев А.Е. О синтезе схем из функциональных элементов в полных монотонных базисах // Математические вопросы кибернетики, 1988. №1. С. 114-139.

Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука, 1996. С. 190-214.

Нечипорук Э. И. О синтезе логических сетей в неполных и вырожденных базисах // Проблемы киберенетики. Вып. 14. М.: Наука, 1965. С. 111-160.

Угольников А. Б. О реализации функций из замкнутых классов схемами из функциональных элементов в полном базисе // Доклады АН СССР. 1983. Т. 271. №1. С. 49 51.

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

Savage J. Е. The complexity of computing. New York: Robert E. Kreiger Publishing Company, 1987 (русский перевод: Джон Э.Сэвидж. Сложность вычислений. М.: Факториал, 1998).

4 Орлов В. А. Реализация функций из 1% схемами в произвольном базисе из функциональных элементов // Докл. РАН. 1998. Т. 359, №3. С. 308-309.

к-значной логики при реализации формулами и схемами из функциональных элементов.

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

По-видимому, впервые понятие неявной выразимости было введено А. В. Кузнецовым5, наряду с понятием параметрической выразимости, как одно из обобщений понятия выразимости функций формулами (суперпозициями).

Неявным представлением функции /(х\,. ■. ,хп) над заданной системой функций А, А С Рь называется всякая система уравнений вида

{<р1(х1,...,хп,у) = 'ф1(хи..., хп, у), <рт(х 1, ...,хту) = "фт(хи ...,хп,у),

удовлетворяющая условиям6: • • ■ 1 <рт> Фь ■ ■ ■ > Фт € [Л и {х}] и имеющая единственное решение у = /(хь ..., хп).

Множество всех функций, допускающих неявное представление над системой функций А, называется неявным расширением системы А и обозначается через 1{А). В силу соотношения /(Л) = /([Л]), справедливого для любой системы Л, Л С Р^, при исследовании неявной выразимости можно без ограничения общности рассматривать только замкнутые по суперпозиции классы функций ¿-значной логики.

Тот факт, что понятие неявной выразимости является обобщением понятия выразимости функций суперпозициями, следует из легко проверяемого соотношения [Л] С /(Л). В свою очередь, параметрическая выразимость7 представляет собой обобщение понятия неявной выразимости.

Ткачев Г. А. О сложности реализации одной последовательности функций Аг-значной логики // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. 1977. №1. С. 45-57.

Захарова Е. Ю. Реализация функций из Рк формулами // Матем. заметки. 1972. Т. 11, Л'® 1. С. 99108.

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

5Кузнецов А. В. О средствах для обнаружения невыводимости или невыразимости // Логический вывод. М.: Наука, 1979. С. 5-33.

еЧерез [Л} обозначается замыкание по суперпозиции системы функций А.

гО параметрической выразимости функций см.: Кузнецов А. В. О средствах для обнаружения невынодимости или невыразимости // Логический вывод. М.: Наука, 1979. С. 5-33.

Система функций называется неявно полной в Ресли ее неявное расширение совпадает с Р¡..

Проблема неявной полноты в Рь полностью решена при к — 2 и к = 3. Проблему неявной выразимости для случая двузначной логики решил О. М. Касим-Заде. Из его работы8, в частности, следует, что в Р> существует ровно один минимальный по включению неявно полный замкнутый по суперпозиции класс — класс всех монотонных булевых функций. Соответственно, критерий неявной полноты в Р¡> можно сформулировать следующим образом: система булевых функций неявно полна тогда и только тогда, когда ее замыкание по суперпозиции содержит класс всех монотонных функций.

В трехзначной логике проблема неявной полноты в терминах минимальных неявно полных классов была решена Е. А. Ореховой. В ее работе9 была найдена система всех минимальных по включению неявно полных замкнутых по суперпозиции классов в Рз, состоящая из 27 различных классов функций.

Позднее О. М. Касим-Заде установил10 критерий неявной полноты в Рк и доказал конечность системы всех минимальных неявно полных замкнутых по суперпозиции классов в Рк для любых значений к, к > 2.

После решения проблемы неявной выразимости в Рг естественным образом возник вопрос о сложности неявных представлений. Одной из наиболее естественных и интересных с различных точек зрения мер сложности для неявных представлений является число входящих в них уравнений, именуемое рангом представления. Понятие ранга впервые было введено О. М. Касим-Заде в применении к булевым функциям.

Пусть / — произвольная функция из неявного расширения заданной системы функций А в Рк, / € 1(А). Рангом тти(/) функции / над системой А называется наименьшее число уравнений, достаточное для построения неявного представления функции / над системой А. Далее традиционным образом вводится функция Шеннона, характеризующая сложность реализации самых сложных функций от п переменных из множества /(А). Ранговой функцией тпа(п) системы А называется наибольшее значение ранга функций /, принадлежащих неявному расшире-

8Касим-Заде О.М. О неявной выразимости булевых функций // Вестник Моск. ун-та. Серия 1. Математика. Механика. 1995. .V* 2. С. 44-49.

9 Орехова Е. Л. Об одном критерии неявной полноты в трехзначной логике // Математические вопросы кибернетики. Вып. 12. М.: Физматлит, 2003. С. 27-74.

™Касим-Заде О.М. О неявной полноте в Ахшачной логике // Вестник Моск. ун-та. Серия 1. Математика. Механика. 2007. №3. С. 9-13.

нию системы А и существенно зависящих не более, чем от п переменных

XI; . . . , ХП.

Отметим, что для любой системы А, А С Рк1 выполняется равенство тд(п) = ггг[у!](п). Следовательно, при поиске ранговых функций без ограничения общности можно предполагать, что рассматриваемые системы функций /с-значной логики замкнуты по суперпозиции.

О. М. Касим-Заде11 исследовал поведение ранговых функций для всех замкнутых по суперпозиции классов функций двузначной логики. Для ряда классов булевых функций он получил точные выражения ранговых функций, для остальных классов — с точностью до порядка роста относительно п, где п — число переменных, фигурирующее в определении ранговой функции. При этом во всех случаях порядок роста ранговой функции для систем функций в Р2 оказался либо линейным по п, либо близким к линейному. Для классов12 Ог и где г — 2,3,6,7 и > 2, ранговая функция равна по порядку величине ггк^п, для остальных классов ранговая функция либо линейна, либо равна 1.

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

Цель работы

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

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

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

11 Касим-Заде О. М. Об одной метрической характеристике неявных и параметрических представлений булевых функций // Математические вопросы кибернетики. Вып. 6. М.: Наука. Физматлит, 1996. С. 133-188.

12Обозначения классов даны по книге: Яблонский С. В., Гаврилов Г. П., Кудрявцев В. В. Функции алгебры логики и классы Поста. М.: Наука, 1966.

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

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

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

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

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

4. Доказана неявная полнота всякого класса функций Амзначной логики, монотонных относительно заданной согласованной пары невырожденных частичных порядков на множестве Е^. Для каждого такого класса найдено точное выражение ранговой функции, линейно зависящее от числа переменных.

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

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

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

Результаты диссертации докладывались на семинаре «Синтез и сложность управляющих систем» под руководством профессора О. М. Касим-Заде (2011 г.), на семинаре «Математические вопросы кибернетики» под

руководством профессора О. М. Касим-Заде (2006-2011 г.), на XVI Международной школе-семинаре «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня 2006г.), на VI молодежной научной школе по дискретной математике и ее приложениям (Москва, 2007г.), на IX Международном семинаре «Дискретная математика и ее приложения» (Москва, 18-23 июня 2007 г.), на VII молодежной научной школе по дискретной математике и ее приложениям (Москва, 18-22 мая 2009 г.), на X Международном семинаре «Дискретная математика и ее приложения» (Москва, 1-6февраля 2010 г.), на Международной научной конференции «Ломоносов-2010» (Москва, 12-15 апреля 2010 г.), на VIII молодежной научной школе по дискретной математике и ее приложениям (Москва, 24-28 октября 2011г.).

Публикации

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

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

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

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

Зададим на множестве Еь = {0,1,..., к— 1} отношение 9Л частичного порядка, к > 2. Максимальную длину цепи в частично упорядоченном множестве (£^;9Л), будем обозначать через Л).

Пусть помимо частичного порядка 9Л на множестве Ек задан еще один частичный порядок ЯЛ'. Будем говорить, что порядок ЯЛ' подчинен порядку ЯЛ (обозначение ЯЛ' С ЯЛ), если для любых элементов а, Ъ из Ек, связанных соотношением а <зл' Ь, выполняется соотношение а <ая Ь. При этом пару порядков (ЯЛ, ЯЛ') будем называть согласованной в Ек-Всюду в дальнейшем, говоря о паре порядков (ЯЛ, ЯЛ'), будем подразумевать, что она является согласованной, т. е. ЯЛ' С ШТ.

Для любого п, п > 1, распространим отношение порядка ЯЛ на куб13

п Кубом будем называть совокупность всех наборов длины п с компонентами из Ек.

ЕЦ следующим образом: будем говорить, что выполняется неравенство (ai,..., ап) (ßi,..., ßn), если при всех г, г = !,■•■,п, выполняются соотношения а; <зл ßi.

Пусть Un — произвольное подмножество куба ЕПусть в кубе задан частичный порядок 93t. Тогда можно говорить о частично упорядоченном множестве ([/"; 931) и о соответствующей этому множеству максимальной длине цепи, которую будем обозначать через s([/",93t).

Рассмотрим произвольную функцию f(xi,...,xn) из Pk. Пусть на области определения функции / задан частичный порядок 9Л, а на области значения Ек функции / — частичный порядок 971', подчиненный порядку 9Л, 9Л' С Ш. Функцию f(x) будем называть монотонной от носительно пары порядков (93Т, 93Т'), если для любых двух наборов ä и ß из куба связанных соотношением а <<т ß, выполняется неравенство

№ <ш т.

Будем говорить, что функция f(xi,...,x„), / G Рк, монотонна на множестве Un, Un С относительно пары порядков (93t, 93t'), если для любых двух наборов ä и ß из Un, таких что <5 ß, выполняется соотношение f(ä) <щр f{ß)-

Рассмотрим для некоторого натурального п непустое семейство Мп функций п переменных из Рк- Пусть функция ß(xi, ...,х„) принадлежит Мп. Будем говорить, что семейство функций Мп обладает свойством14 Д[(УП; 93?, 93t'], если Мп есть совокупность всех функций от п переменных, монотонных на множестве наборов Un относительно пары порядков (£Ш, 9Я') и совпадающих с функцией ju на множестве \ [/".

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

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

В главе 2 для всякого невырожденного класса функций в Рк, монотонных относительно заданной согласованной пары порядков (931, 931')

"Зависимость свойства Д[17";Ш1,Я31'] от функции /1, не отражена в обозначении, так как она не существенна для целей настоящей работы.

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

Помимо этого, во второй главе приведены следствия из данного результата, устанавливающие точные выражения ранговых функций для отдельных частных случаев отношений порядков 9Л и ЮТ'. Также на основе этого результата доказана теорема о верхней оценке ранговой функции классов, содержащих для всякого натурального п и каждого множества наборов Щ из заданного разбиения15 {С/"}-!"' куба Ек, систему функций М", обладающую свойством Д^?1; £Ш,ШГ'], где 1 < г < г(п).

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

Теорема 1. Пусть на мноокестве Ек, к > 2, заданы частичные порядки Ш и ЮТ', такие, что ЮГ С 9Л и з(Ек,Ш') > 1. Пусть А - класс всех функций в Рк, монотонных относительно пары порядков (9Я, ЮТ'). Тогда система А неявно полна в Рк и при всех натуральных п ранговая функция системы А удовлетворяет равенству:

(п + 1)з(Ек,т) + Г 2 з(Ек,Ш)

тА(п) =

В разделе 2.2 приведены некоторые следствия из теоремы 1, а также утверждения, являющиеся в некотором смысле обобщениями этой теоремы.

В случае совпадения частичных порядков ЮТ и ЮТ' ранговая функция класса А функций, монотонных относительно пары порядков (Ш1, ОЛ'), зависит только от числа п и устанавливается следующей теоремой.

Теорема 2. Пусть на множестве Ек, к >2, задай частичный порядок ЮТ, удовлетворяющий условию > 1. Пусть А — класс всех

функций в Рк, монотонных относительно пары порядков (ЮТ, ЮТ). Тогда

15Совокупность {¡Л};',,! попарно непересекающихся подмножеств множества II называется разбиением множества V, если их объединение и'=1 К совпадает с V.

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

п + 2' 2

тл(п)

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

Теорема 3. Пусть на множестве Е^, к > 1, задан частичный порядок Ш', подчиненный отношению линейного порядка!-6 в Ек и удовлетворяющий условию з(Ек,Ш') > 1. Пусть А — класс всех функций в Рк, монотонных относительно порядка 9Л', за исключением, возможно, некоторых констант, отвечающих изолированныл/7 точкам порядка Ш'. Тогда система А неявно полна в Рк и при всех натуральных п для ранговой функции системы А выполняется равенство:

тпА(п) =

(п+!)(*- 1) + 1'

2а{Ек,Щ

Теоремы 2 и 3 являются прямыми следствиями из теоремы 1.

В разделе 2.2 также вводятся обобщения понятий ранга и ранговой функции, характеризующие число уравнений, достаточное для задания значений18 функций п переменных на некотором подмножестве куба Е%+1.

Пусть /(хь ...,хп) — функция п переменных из неявного расширения произвольной системы функций А в Рк, / £ 1(А). РангомгпА^/, 11п+1) функции / над системой А относительно подмножества [7"+1 в кубе Е£+1 будем называть наименьшее число уравнений, достаточное для задания значений функции / на множестве 1Гп+1. Ранговой функцией тпа(п, ип+1) системы А относительно множестваИп+1 будем называть

16 Линейным на множестве Ек является порядок 0< 1 < ■ ■ • < /г — 1.

|73начение i, i е Ек, будем называть изолированной точкой частичного порядка ОЯ на множестве Ек, если элемент г несравним ни с одним другим элементом в частично упорядоченном множестве (Ек-т).

18Подсистема системы неявных уравнений, реализующей функцию /(х'1,... ,хп), задает знйненил функции / на подмножестве (7"+1 куба если для каждого набора (а, /)) из ип+х, такого, что 0 ^ /(а), данная подсистема содержит уравнение, обращающееся в неравенство па этом наборе.

максимум рангов относительно множества (7"+1 всех функций ¿-значной логики, принадлежащих неявному расширению системы А и существенно зависящих не более, чем от п переменных.

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

Теорема 4. Пусть для произвольного натурального числап в кубе Е£+1 задано подмножество Пусть на множестве Е¡¡, к > 2, заданы

частичные порядки Ш и Ш', такие, что Ш' С Ш1 и з(Еь,Ш') > 1. Пусть А — замкнутый по суперпозиции неявно полный класс функций в Рь, содержащий некоторое семейство Мп+1 функций от п + 1 пе-рел1енной, обладающее свойством А[1/п+1-, 9Я, ЯЯ']. Тогда выполняется неравенство:

Гв((7п+1,ЯК) + 1~

тА{тг,ип+1) <

2 з{Ек,Ш)

Теорема 5. Пусть для произвольного натурального числап задано разбиение куба Е£+х. Пусть на множестве Е/. задан частичный порядок 9Л и частичные порядки г = 1,... ,г(п), такие, что Ш, С Ш, 9Я,:) > 1 при любом г, 1 < г < г(п). Пусть А — замкнутый по суперпозиции неявно полный класс функций в Р^, содержащий для каждого г, I < г < г(п), некоторое семейство функций обладающее свойством Д[(/"+1;9Я, ШЦ. Тогда выполняется неравенство:

т(п)

тА{п) < ^ ¿=1

ал) + 1

25 (ЕЬЩ)

В главе 3 рассматриваются шесть минимальных неявно полных замкнутых классов функций трехзначной логики И^, И^з> и для каждого из них исследуется поведение ранговой функции. Для классов И^, И^, Ил4 устанавливаются точные значения соответствующих им ранговых функций, для остальных классов находятся верхние и нижние оценки, которые дают представление о порядке роста ранговой функции относительно числа переменных. Ранговые функции классов И^ и И-'б имеют экспоненциальный порядок роста, ранговые функции классов И^, И'з, V/\ — линейный порядок роста.

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

описание классов г = 1,..., 6, и их свойств, приводятся вспомогательные определения и обозначения, используемые в дальнейших доказательствах.

В разделе 3.2 устанавливаются оценки для ранговых функций классов И'!, И'г, И'з, И^, имеющих линейный порядок роста ранговой функции.

Теорема 6. При всех натуральных значениях п для ранговых функций классов и И^ выполняются равенства:

При доказательстве теоремы 6 показывается, что классы Ц\ и 1У2 есть классы всех монотонных функций в Рз, выпускающих значения 2 и 1 соответственно, откуда следует, что классы и И^ удовлетворяют условиям теоремы 3.

Теорема 7. При всех натуральных п для ранговой фупции класса №3 выполняются неравенства:

При доказательстве верхней оценки ранговой функции класса \¥з используется теорема 5.

Нижняя оценка вытекает из теоремы 2, так как класс И'з содержит только монотонные относительно линейного порядка функции трехзначной логики.

Теорема 8. При всех натуральных п для ранговой фунции класса И'\ выполняется равенство:

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

тц-1_(п) = тпцг2(п) = п + 2.

+ 2.

тп'Л{п) = п + 2.

Для получения нижней оценки рассматривается функция/(хх,... ,х„) специального вида, удовлетворяющая определенным условиям, и показывается, что любое неявное представление 5(/) функции / над классом Ш4 состоит из не менее, чем п + 2 уравнений.

В разделе 3.3 доказываются теоремы о ранговых функциях классов И^ и И^, имеющих экспоненциальный порядок роста ранговой функции.

Теорема 9. При всех натуральных п для ранговой функции класса И^ выполняются неравенства:

2(»+1)/2 _ 1/2 <

тж^п) < {п + 2)2".

Нижняя оценка ранговой функции класса И^ устанавливается следующим образом. Сначала доказывается, что все функции из классаИ^ обладают определенными свойствами. Затем строится функция/(ж1,.. .,хп) специального вида и задается некоторое подмножество наборов ф" в кубе Далее показывается, что для любого неявного представления 5(/) функции / над И75, в силу доказанных ранее свойств класса IV^, число наборов в Оп не превосходит числа определенных комбинаций уравнений в системе 5(/). Из полученного неравенства извлекается нижняя оценка для числа уравнений в системе 5'(/), а следовательно, и для ранговой функции класса И^.

Обоснование верхней оценки опирается на теорему 5.

Теорема 10. При любом натуральном п для ранговой функции класса М^б выполняются неравенства:

2п < ггцу6(п) < (п + 2)2".

Для получения нижней оценки ранговой функции класса 1¥(п как и в предыдущей теореме, строится функция /(хь. >. ,хп) специального вида и задается некоторое подмножество наборов <2П в кубе Щ. Затем на основе определенных свойств функций из класса И^ показывается, что в любом неявном представлении функции / над И^ число уравнений не меньше, чем число наборов в <2"•

При доказательстве верхней оценки используется теорема 5.

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

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

1. Михайлец Е. В. О ранге неявных представлений функций fc-значной логики над классом монотонных функций // Материалы XVI Международной школы-семинара «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня 2006). М.: Изд-во мех.-мат. ф-та МГУ, 2006. С. 78-83.

2. Михайлец Е. В. О ранге неявных представлений над классами монотонных функций /с-значной логики // Материалы VI Молодежной научной школы по дискретной математике и ее приложениям (Москва, ИПМ, 2007). М.: Изд-во ИПМ, 2007. С.2С-29.

3. Михайлец Е. В. О ранге неявных представлений над одним классом функций трехзначной логики // Вестник Моск. ун-та. Серия 1. Математика. Механика. М.: Изд-во МГУ, 2008. № 2. С. 65-70.

4. Михайлец Е. В. О ранге неявных представлений над одним классом функций трехзначной логики // Материалы VII Молодежной научной школы по дискретной математике и ее приложениям (Москва, ИПМ, 2009). М.: Изд-во мех.-мат. ф-та МГУ, 2009. Часть 2. С. 17-20.

5. Михайлец Е. В. О ранге неявных представлений над некоторыми классами функций трехзначной логики // Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 2010). М.: Изд-во мех.-мат. ф-та МГУ, 2010. С. 127-129.

6. Михайлец Е. В. Об одном классе функций трехзначной логики с экспоненциальным ростом ранговой функции // Материалы VIII Молодежной научной школы по дискретной математике и ее приложениям (Москва, ИПМ, 2011). М.: Изд-во мех.-мат. ф-та МГУ, 2011. С. 12-15.

Подписано в печать:

20.02.2012

Заказ № 6700 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru