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

• Кочергин, Алексей Вадимович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Кочергин, Алексей Вадимович

Оглавление

Введение

1. Случай конечных базисов

§ 1.1. Основные понятия. Постановка задачи

§ 1.2. Нижняя оценка функции Шеннона глубины

§ 1.3. Верхняя оценка функции Шеннона глубины

§ 1.4. Примеры конечных базисов

§ 1.5. Нахождение асимптотики функции Шеннона глубины

2. Случай бесконечных базисов

§ 2.1. Базисы бесконечной характеристики

§ 2.2. Базисы конечной характеристики. Нижняя оценка функции

Шеннона глубины

§ 2.3. Базисы конечной характеристики. Верхняя оценка функции

Шеннона глубины

§ 2.4. Примеры базисов конечной характеристики

Список литературы

Введение диссертации (часть автореферата) на тему «О глубине функций многозначной логики»

Введение

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

Возникает вопрос о том, каким образом измерять качество схемы. Этот вопрос, как правило, решается введением специальной численной характеристики схемы: меры сложности схем. В качестве меры сложности схем берется, например, число проводящих контактов, число элементов, вес (стоимость), глубина, задержка, площадь (объем), мощность, активность и др. (см., например, [58, 21, 29, 33, 13, 15, 2, 9]). Таким образом, ка-

ж дои схеме сопоставляется некоторое неотрицательное число, называемое сложностью этой схемы относительно заданной меры сложности. Считается, что чем меньше значение сложности, тем лучше схема (опять-таки относительно заданной меры). Следовательно, задачу можно переформулировать так: для каждой функции / из заданного множества требуется найти реализующую ее схему с минимально возможным значением сложности. Это минимальное значение называется сложностью функции.

В случае, когда множество базисных элементов конечно и всякая схема состоит из конечного числа элементов, у описанной задачи теоретически имеется тривиальное решение методом перебора всех схем определенной сложности. Однако практически им можно воспользоваться даже с применением современных вычислительных возможностей, как правило, только для малых значений сложности, так как с ростом числа элементов количество различных схем растет очень быстро. Подробнее см. [49].

Уточним постановку задачи. Пусть каждой схеме S над заданным базисом поставлено в соответствие неотрицательное число L(S) — сложность этой схеме. Для каждой функции / определяется ее сложность L(f) следующим образом L(f) = min L(S), где минимум берется по всем схемам S, реализующим функцию /. Задача состоит в построении для каждой рассматриваемой функции / схемы S, удовлетворяющей равенству L(/) = L(S). Однако такая задача, как правило, оказывается очень трудной. В связи с этим часто рассматривают задачу построения схем, в том или ином смысле близких к оптимальным (например, асиптотически оптимальных схем). Вводится функция L(F) = maxL(/), где максимум берется по всем функциям / из некоторого класса F (класс F предполается конечным и состоящим из функций, допускающих реалицию в заданном классе схем). Требуется найти метод синтеза схем, позволяющий для произвольной функции / из класса F, построить схему 5, которая реализует функцию / и для которой значение L(S) близко к величине L(F). Например, если Fn — класс всех функций fc-значной логики от п переменных,

L(S) — схемная сложность (число элементов) схем из функциональных элементов над фиксированным конечным функционально полным базисом (см. ниже), то для каждой функции / из класса Fn требуется построить схему 5, реализующую функцию /, для которой величина L(S) асимптотически не превосходит величины L(n) = L{Fn). Функцию L(n) часто называют функцией Шеннона в честь К. Э. Шеннона, который в 1949 г. предложил [58] такой подход при изучении задачи синтеза контактных схем.

Начиная со второй половины 1950-х годов О.Б. Лупановым были разработаны асимптотически оптимальные методы синтеза и получены асимптотически точные оценки сложности для многих важнейших классов управляющих систем: вентильных схем глубины 2 и контактно-вентильных схем [21], контактных схем [23], схем из функциональных элементов над произвольным конечным базисом булевых функций [22], формул над произвольным конечным базисом булевых функций [24] и др. [26, 27, 28, 29, 32].

Впоследствии для различных классов функций, различных видов управляющих систем и различных мер сложности многими авторами были установлены асимптотически точные (или точные по порядку роста) оценки функций Шеннона (см., например, [48, 36, 47, 55, 16, 14, 6, 8, 45]).

В данной работе рассматривается реализация функций в одном из наиболее важных модельных классов управляющих систем — классе схем из функциональных элементов (см, например, [27]).

Будем рассматривать реализацию функции fc-значной логики (к > 2) схемами из функциональных элементов над произвольным базисом. Здесь и далее под базисом понимается произвольное функционально полное множество функций £;-значной логики, т. е. такое, что суперпозициями функций этого множества можно реализовать любую функцию fc-значной логики. Базис называется бесконечным, если для любого натурального числа га существует функция из этого базиса, существенно зависящая более чем

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

Изучаемая в работе мера сложности — глубина схемы. Под глубиной схемы понимается максимальное число элементов в ориентированных цепях, ведущих от какого-либо из входов схемы к ее выходу. Глубиной функции /г-значной логики / над базисом В называется минимальная глубина схем, реализующих функцию / над базисом В. В работе для произвольного базиса В исследуется поведение функции Шеннона глубины DB(n), характеризующей максимальную глубину функций от п переменных и определяемой равенством Db(ti) = тахДв(/), где максимум берется по всем функциям fc-значной логики /, зависящим от п переменных.

С содержательной точки зрения рассматриваемое в данной работе понятие глубины связано с представлениями о задержке (или времени работы) схемы. Подробнее об этих понятиях и их взаимосвязях см., например, [29, 44]. Время работы является одной из наиболее существенных характеристик современных вычислительных устройств.

Отметим, что в ряде работ [25, 30, 53, 20] под «глубиной» (или «глубиной альтернирования») схемы понимается максимальное число перемен типов элементов в цепях, ведущих от входов схемы к ее выходу. Это понятие существенно отличается от изучаемого в данной работе, и в данной работе не рассматривается.

Отметим также, что в данной работе исследуется глубина функций к-значной логики только над функционально полными системами. Однако глубина функций изучалась и над функционально неполными системами функций двузначной и fc-значной (к > 3) логики (см., например, работы А. Б. Угольникова [41, 42], А. А. Андреева [1]). В ряде работ также

получены соотношения, связывающие глубину и формульную сложность функций (см., например, работы Ф. М. Спиры [61], В. М. Храпченко [43], И. Вегенера [62], А. Б. Угольникова [40], М. Е. Рагаца [57], Р. Ф. Сафи-на [38]). В данной работе в качестве меры сложности рассматривается только глубина схем, а ее взаимосвязи с другими мерами сложности, как и сами другие меры сложности, не рассматриваются.

В 1970 г. О. Б. Лупановым [29] было установлено, что в случае двузначной логики (к = 2) для любого конечного базиса В выполняется соотношение

Е>в(п) ~ Сп,

где С = (к^2га)-1, а га — максимальное число существенных переменных у функций из базиса В. (Символ «~» обозначает асимптотическое равенство; определения асимптотического равенства и других асимптотических соотношений приведены в §1.1.) В случае классического базиса В0 двузначной логики, состоящего из конъюнкции двух переменных, дизъюнкции двух переменных и отрицания, эта оценка для функции Шеннона глубины 1>в0(п) уточнялась в работах Ф. М. Спиры [60], У. Ф. Мак-Колла и М. С. Патерсона [54], С. Б. Гашкова [5], С. А. Ложкина [18]. Наиболее точная верхняя оценка была получена С. А. Ложкиным в работе [18], в которой была установлена справедливость следующего неравенства:

Dвo{n) < \п - 1о§2 п + Ь(п)~1, где Ъ{п) = о(1) при п —> оо. Нижняя оценка вида

О во (га) > ~ 1°§2 п + а(п)1 >

где а(п) = о(1) при п —> оо, вытекает из стандартных мощностных соображений (см., например, [5]).

В 1996 г. С. А. Ложкиным [19] было показано, что для произвольного конечного базиса В функций двузначной логики справедливо равенство

Ов{п) = С{п - 1о§2 п) + с(п),

где c(n) = 0(1).

Результатов о поведении функции Шеннона глубины в случае бесконечных базисов функций двузначной логики до появления работ [10, 11, 12] было известно немного. Асимптотики роста (или хотя бы порядки роста) были найдены только для небольшого числа базисов. При этом во всех известных примерах функция Шеннона либо была ограничена сверху константой (в частности, для базиса, состоящего из всех функций двузначной логики, или для базиса функций двузначной логики, состоящего из всех пороговых функций [31]), либо росла по порядку как log2n (например, для базиса функций двузначной логики, состоящего из конъюнкции двух переменных и всех линейных функций — фактически это следует из результатов работы [17]).

В 2007 г. О. М. Касим-Заде [10] было установлено, что для любого бесконечного базиса В функций двузначной логики порядок роста функции Шеннона глубины DB(n) при п —У оо равен либо 1, либо log2n. В работах [11, 12] О. М. Касим-Заде этот результат усилил: было показано, что для любого бесконечного базиса В функций двузначной логики либо существует константа а, 1 < а < б, такая, что DB(n) = а при всех достаточно больших п, либо существуют целочисленная константа Ъ > 2, такая, что |"logbn] < -Dß(n) < flogen] + 5 при всех п.

При к > 3 задача о поведении функции Шеннона глубины функций fc-значной логики при реализации схемами из функциональных элементов до последнего времени оставалась практически неисследованной. Можно указать, по-видимому, только на некоторые тривиальные результаты, являющиеся очевидными обобщениями на А:-значные логики случая двузначной логики. Например, для конечного базиса В*, состоящего из всех функций fc-значной логики от двух переменных, легко показать, что порядок роста функции Шеннона глубины DB* (п) при п —у оо равен п. Отсюда очевидным образом следует, что и для любого конечного базиса В функций /с-значной логики функция Шеннона глубины DB{n) при п —> оо по

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

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

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

В первой главе диссертации изучается поведение функции Шеннона глубины схем над произвольным конечным базисом функций /с-значной логики. В начале первой главы (§1.1) вводятся основные понятия и определения, формулируются основные результаты этой главы, заключающиеся в трех следующих теоремах.

Теорема 1 (1.1). При любом натуральном к, к > 2, для произвольного конечного базиса В функций к-значной логики существует такая положительная константа ав, что при п —У оо выполняется соотношение

Ов(п) ~ авп.

Теорема 2 (1.2). При любом натуральном к, к > 2, для произвольного

конечного базиса В константа ав из соотношения Дв(?г) ~ авп имеет

Теорема 3 (1.3). При любом натуральном к, к > 2, существует алгоритм нахождения по произвольному конечному базису В функций к-значной логики многочлена с целыми коэффициентами, максимальным действительным корнем которого является число Тв-

Говоря содержательно, теорема 1 для произвольного конечного базиса В функций &-значной логики устанавливает существование асимптотики функции Шеннона глубины вида Ов(п) ~ а^п, линейной по числу п переменных реализуемых функций, а теоремы 2 и 3 дают «эффективное» в некотором естественном смысле решение проблемы нахождения константы ав в указанной асимптотике: по теореме 2 эта константа выражается в «замкнутой форме» через логарифм от алгебраического числа тв, которое по теореме 3 задается как корень некоторого вычисляемого по базису В многочлена с целыми коэффициентами.

В §§1.2-1.3 приводится доказательство теоремы 1. Наметим основные шаги этого доказательства. Для любого конечного базиса В функций к-значной логики и произвольного натурального числа с? вводится величина А^в(^) как наибольшее число существенных переменных у функций, допускающих над базисом В реализацию схемой глубины не более (1. Устанавливается, что для любого конечного базиса В функций /с-значной логики существует положительный предел

В §1.2 на основе мощностных соображений доказывается, что для любого е, е > 0, при всех достаточно больших п выполняется неравенство Вв(п) > авп( 1 — е), причем доля функций /(#1,..., жп), для которых

вид ав = (к^тв) 1, где тв является алгебраическим числом.

¿—юо д,

Далее вводится константа а в, определеляемая равенством

Ищ

Ав(/) < &вп( 1 — е), стремится к 0 с ростом п. (Отметим, что с учетом этого теореме 1 можно придать даже более сильную форму — имеет место так называемый «эффект Шеннона»: почти все функции имеют почти одинаковую глубину, асимптотически равную значению функции Шеннона.) В §1.3 доказывается верхняя оценка функции Шеннона глубины

£>я(п) < авп + о(п),

где п —У оо. При доказательстве этой оценки используется некоторый аналог леммы О. Б. Лупанова об обобщенном разложении из [33].

Теорема 1 устанавливает лишь факт существования асимптотики указанного вида для функции Шеннона глубины над любым конечным базисом функций А;-значной логики. Возникает проблема нахождения по конечному базису В соответствующей константы а в из этой асимптотики. В §1.4 рассматривается ряд хорошо известных конечных базисов функций &-значной логики, дающих конкретные примеры возможных асимптотик функций Шеннона глубины. Во всех указанных примерах константа ав в соответсвующей асимптотике имеет вид а в = (logk тв)~г, где тв является рациональным (и даже натуральным) числом. Далее, здесь же приводится пример конечного базиса В, для которого константа тв в представлении ав = (logьТв)~1 является числом иррациональным. Последний пример указывает на принципиальное отличие /с-значных (к > 3) логик от двузначной: при к — 2 для любого конечного базиса В константа тв — натуральное число [29]. Теорема 2 показывает, что в общем случае для конечных базисов функций /г-значной логики число тв является алгебраическим.

Далее в §1.5 проводится доказательство теорем 2-3. Определяется объект, называемый А-грамматикой, который по существу отличается от контекстно-свободной грамматики лишь отсутствием терминальных символов. Описывается алгоритм построения по произвольному конечному базису В функций /с-значной логики некоторой А-грамматики Зв-, имеющей в некотором подходящем смысле хорошие свойства. Далее описыва-

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

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

Теорема 4 (2.1). При любом фиксированном к, к > 2, для любого бесконечного базиса В функций к-значной логики либо существует константа 7в > 1, такая, что Дв(п) = 7в при всех достаточно больших п, либо существует константа /3в > 0; такая, что при п —> оо имеет место соотношение Вв(п) ~ Двк^2п.

Сначала в §2.1 вводится понятие обобщенной ^степени базиса В. Для произвольного бесконечного базиса В и любого простого числа р определяется величина gdegpB, называемая обобщенной р-степенью базиса В и принимающая значения из расширенного множества натуральных чисел N и {оо} (подробное определение этого понятия и объяснение соответствующих обозначений см. в тексте диссертации). Устанавливается, что для любого бесконечного базиса В функций &-значной логики имеет место одна из двух взаимоисключающих возможностей: либо gdegqB = оо при любом простом д, либо существует единственное простое р, такое, что gdegpB < оо. В первом случае базис В называется базисом бесконечной характеристики, во втором — базисом конечной характеристики. (В случае к — 2 введенное в диссертации понятие обобщенной р-степени базиса совпадает с известным понятием р-степени базиса функций двузначной логики [10].)

Далее в §2.1 устанавливается, что для произвольного бесконечного ба-

зиса В бесконечной характеристики при всех достаточно больших п выполняется равенство

где 7в — некоторая константа, зависящая от базиса В. В конце параграфа рассматриваются некоторые примеры базисов бесконечной характеристики. (Тривиальным примером такого базиса является бесконечный базис, состоящий из всех функций £;-значной логики.)

В §§2.2-2.3 исследуются бесконечные базисы конечной характеристики. Для произвольного бесконечного базиса В конечной характеристки вводится положительная константа кв как предел некоторой последовательности положительных чисел, зависящей от базиса В (подробнее см. в § 2.2). Сначала в §2.2 устанавливается нижняя оценка: доказывается, что для произвольного бесконечного базиса В конечной характеристики и любого е > 0, при всех достаточно больших п справедливо неравенство

В отличие от случая конечных базисов в случае бесконечных базисов конечной характеристики нижняя оценка устанавливается конструктивно: явно предъявляется последовательность функций &-значной логики {/п} (где /п зависит от п переменных), удовлетворяющих при произвольном е > 0, и всех достаточно больших п неравенству

Далее в §2.3 доказывается верхняя оценка: устанавливается, что при п — оо для произвольного бесконечного базиса В конечной характеристики выполняется соотношение

Таким образом, устанавливается, что для любого бесконечного базиса В конечной характеристики выполняется соотношение

£>в(п) = 7в

ВвЦп) > (кв1 ~ е) 1о

£>в(п) < К В1 1о§2 п + п).

£>в(п) ~ /Зв1оё2п,

где (Зв = квг.

В §2.4 рассматриваются примеры бесконечных базисов конечной характеристики. В случае функций двузначной логики для любого бесконечного базиса В конечной характеристики асимптотика функции Шеннона глубины может быть записана [11] в виде Дв(п) ~ 1о&3п, где з (в > 2) — некоторое натуральное число, зависящее от базиса В. В §2.4 сначала для всякого к > 3 устанавливается существование бесконечных базисов функций к-значной логики с аналогичной асимптотикой функции Шеннона глубины при всех достаточно больших е. Далее приводится пример бесконечного базиса конечной характеристики, для которого функция Шеннона глубины не представима в таком виде (в этом случае асимптотика функции Шеннона имеет вид -Ов(п) ~ где £ — число иррациональное). Этот пример указывает на еще одно принципиальное отличие /г-значных (при к > 3) логик от двузначной.

Отметим, что справедливость утверждений теорем 1-4 в случае двузначной логики вытекает из перечисленных ранее результатов других авторов. Случай к = 2 включен в формулировки теорем лишь для полноты изложения. Результаты теорем 1 и 4 дают полную качественную картину асимптотического поведения функции Шеннона глубины над произвольным базисом функций /г-значной логики при всех к > 2.

Основные результаты диссертации опубликованы автором в работах [63, 64, 65].

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

Глава 1.

Случай конечных базисов

§1.1. Основные понятия. Постановка задачи

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

множестве Е% и принимающую значения из множетсва Ек, назовем булевой квазифункцией. Отметим, что булева функция является частным случаем булевой квазифункции. Скажем, что функция &-значной логики f(xl,..., Хп) порождает булеву квазифункцию Н(х\,..., хп), если для любого набора (о^,..., о;п) из нулей и единиц выполняется равенство /(аь ... ,ап) = Ь,{аъ ...,«„).

Говорят, что функция /г-значной логики ж2,. • •, хп) зависит существенно от переменной Х{, 1 < г < га, если существуют элементы

«2, • • ■ , СУг-Ъ С^г+1; • • • 5 А ИЗ МНОЖеСТВа Ек, для которых выполняется неравенство

/(<*!, а2> . • . , »¿-1, С**, «¿+1, • • • > Ып) ф /(«1, СХ.2, • • • , «¿-1, А) <*»+1> • • • , «п)-В этом случае переменная х^ называется существенной перемен-

ной. Если переменная Х{ не является существенной, то она называется несущественной. В этом случае говорят, что функция f(x 1,Ж2,...,#П) от переменной Х{ зависит несущественно. Пусть / = /(хь ... ,Xí-i,Xí,Xí+i, ... ,хп) и д = g(xi,...,xi-i,xi+i,...,xn) — произвольные функции fc-значной логики, удовлетворяющие условию: для любого набора (cyi, ..., i, j,..., an) из E£ выполняется равенство

/(ai,..., «í-I, CKj, ai+i, ...,a„)= . .., Qfi+i, • • •, o;n).

В этом случае говорят, что функция д получена из функции / путем изъятия (удаления) несущественной переменной а также, что функция / получена из функции g путем введения (добавления) несущественной переменной Х{.

Пусть X = £2, • • •, xti...} — счетное множество переменных, а А = {fi(xi,..., хП1),..., fs(xi,..., хПз),...} — конечное или счетное множество функций А;-значной логики. Введем индуктивно понятие формулы над множеством А.

1. Любой символ переменной из множества X является формулой над множеством А.

2. Выражения /¿(жь ..., хПг) являются формулами над множеством А.

3. Пусть Фь Ф2,..., ФПг — некоторые формулы над множеством А. Тогда выражение /¿(Ф1, Ф2,..., ФПг) — формула над множеством А.

Формула над множеством А называется бесповторной, если каждая переменная входит в нее не более одного раза. Пусть Ф — произвольная формула над множеством А. Индуктивно определим понятие подформулы формулы Ф. Единственной подформулой символа переменной Х{ является символ переменной Xi- Пусть формула Ф имеет вид /¿(Ф1, Ф2,..., ФПг), где fi — символ некоторой функции из множества А, а Ф1, Ф2,..., ФПг — некоторые формулы над множеством А. Тогда подформулами формулы Ф являются все подформулы формул Ф1, Ф2,..., ФПг, а также сама формула Ф.

Каждой формуле поставим в соответствие некоторую функцию к-значной логики. Пусть а = (а1? а2,..., ап) £ — некоторый набор значений переменных Х\, ж2, ■. ■, хп, а Ф — произвольная формула над множеством функций А = {Л(ж1,..., хП1),..., /Джь ..., хПа),...}, содержащая переменные х\, сс2, ■ ■ ■, хп и не содержащая других переменных. Определим индуктивно понятие значения формулы Ф на наборе 5, обозначаемое через

1. Значение переменной Х{ на наборе й равно с^.

2. Пусть уже определены значения ФхФ2|аг, • • • > Фщ\а- Тогда для формулы Ф = /¿(Фь Ф2, • • •, Фщ) имеем:

Ф|а — /¿(Ф^аЬ | й ? • ■ • ■> Фтг^|а)-

Таким образом, значение формулы Ф определено на произвольном наборе а = («1, «2 ,-••■> из Тем самым формуле Ф сопоставлена некоторая функция &-значной логики д = д(хх, £2, • • •, хп). Будем говорить, что формула Ф реализует функцию д над множеством А.

Пусть Ф — произвольная формула над множеством А функций к-значной логики. Под сложностью формулы Ф над множеством А будем понимать число вхождений символов функций из множества А в эту формулу. Глубину Ф) формулы Ф над множеством А определим следующим образом: РДФ) = 0, если формула Ф является переменной; ВА(Ф) = 1+тахх<;<п 5А{Фг), если формула Ф имеет вид /¿(Фь Ф2, • • •, Фп<), где ^ — символ некоторой функции из множества А, а Фх, Ф2,..., ФПг — некоторые формулы над множеством А. Наименьшая глубина формул над множеством А, реализующих функцию А;-значной логики /, называется глубиной функции / над множеством А и обозначается через

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

Список литературы диссертационного исследования кандидат наук Кочергин, Алексей Вадимович, 2013 год

Литература

[1] Андреев А. А. Об одной последовательности функций многозначной логики // Вестник Московского университета. Сер. 1. Математика. Механика. — 2011. — № 6. — С. 3-7.

[2] Вайнцвайг М. Н. О мощности схем из функциональных элементов // Доклады АН СССР. — 1961. — Т. 139, № 2. — С. 320-323.

[3] Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.

[4] Гантмахер Ф. Р. Теория матриц. Часть вторая. Издание второе. — М.: Наука, 1966.

[5] Гашков С. Б. О глубине булевых функций // Проблемы кибернетики, вып. 34. — М.: Наука, 1978. — С. 265-268.

[6] Гашков С. В., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней // Методы дискретного анализа в теории графов и сложности. — Новосибирск, 1992. — Вып. 52. — С. 22-40.

[7] Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973.

[8] Глухов М. М., Зубов А. Ю. О длинах симметрических и знакопеременных групп подстановок в различных системах образующих // Математические вопросы кибернетики, вып. 8. — М.: Наука, 1999. — С. 5-32.

[9] Касим-Заде О. М. Об одной мере сложности схем из функциональных элементов // Проблемы кибернетики, вып. 38. — М.: Наука, 1981. — С. 117-179.

[10] Касим-Заде О. М. О глубине булевых функций при реализации схемами над произвольным базисом // Вестник Московского университета. Сер. 1. Математика. Механика. — 2007. — К9 1. — С. 18-21.

[11] Касим-Заде О. М. О глубине булевых функций над произвольным бесконечным базисом // Дискретный анализ и исследование операций. Сер. 1. — 2007. — Т. 14, 1. — С. 45-69.

[12] Касим-Заде О. М. О глубине булевых функций при реализации схемами над произвольным бесконечным базисом // Вестник Московского университета. Сер. 1. Математика. Механика. — 2012. — № 6. — С. 55-57.

[13] Коршунов А. Д. Об оценках сложности схем из объемных функциональных элементов // Проблемы кибернетики, вып. 19. — М.: Наука, 1967. — С. 275-284.

[14] Кочергин В. В. О сложности вычислений в конечных абелевых группах // Доклады АН СССР. — 1991. — Т. 317, № 2. — С. 291-294.

[15] Кравцов С. С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики, вып. 19. — М.: Наука, 1967. — С. 285-292.

[16] Кузьмин В. А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Методы дискретного анализа в теории кодов и схем. Сб. научн. тр., вып. 29. — Новосибирск: Ин-т математики СО АН СССР, 1976. — С. 11-39.

[17] Ложкин С. А. Асимптотическое поведение функций Шеннона для задержек схем из функциональных элементов // Математические заметки. — 1976. — Т. 19, № 6. — С. 939-951.

[18] Ложкин С. А. О глубине функций алгебры логики в некоторых базисах // Annales Univ. Sei. Budapest. Sec. Comput. — 1983. — V. 4. — P. 113-125.

[19] Ложкин С. А. О глубине функций алгебры логики в произвольном полном базисе // Вестник Московского университета. Сер. 1. Математика. Механика. — 1996. — № 2. — С. 80-82.

[20] Ложкин С. А., Коноводов В. А. О синтезе и сложности формул с ограниченной глубиной альтернирования // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. — 2012. — m 2. — С. 28-36.

[21] Лупанов О. Б. О вентильных и контактно-вентильных схемах // Доклады АН СССР. — 1956. — Т. 111, № 6. — С. 1171-1174.

[22] Лупанов О. Б. Об одном методе синтеза схем // Известия высших учебных заведений. Радиофизика. — 1958. — Т. 1, № 1. — С. 120-140.

[23] Лупанов О. Б. О синтезе контактных схем // Доклады АН СССР. — 1958. — Т. 119, № 1. — С. 23-26.

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

[25] Лупанов О. Б. О реализации функций алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе &,V,-i. // Проблемы кибернетики, вып. 6. — М.: Физматгиз, 1961. — С. 5-14.

[26] Лупанов О. Б. Об обном классе схем из функциональных элементов (формулы с частичной памятью) // Проблемы кибернетики, вып. 7. — М.: Физматгиз, 1962. — С. 61-114.

[27] Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, вып. 10. — М.: Физматгиз, 1963. — С 63-97.

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

[29] Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики, вып. 23. — М.: Наука, 1970. — С. 4381.

[30] Лупанов О. Б. О влиянии глубины формул на их сложность // Кибернетика. — 1970. — № 2. — С. 46-49.

[31] Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 26. — М.: Наука, 1973. — С. 109-140.

[32] Лупанов О. Б. О сложности универсальной параллельно-последовательной сети глубины 3 // Труды МИ АН СССР. — 1973. — Т. 133. — С. 120-140.

[33] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во Московского университета, 1984.

[34] Лупанов О. Б. Конспект лекций по курсу «Введение в математическую логику» / Под редакцией А. Б. Уголъникова. — М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2007. — 192 с.

[35] Люстерник Л. А., Соболев В. И. Элементы функционального анализа. Издание второе. — М.: Наука, 1965.

[36] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики, вып. 21. — М.: Наука, 1969. — С. 5102.

[37] Полиа Г., Сеге Г. Задачи и теоремы из анализа. Часть первая. Издание третье. — М.: Наука, 1978.

[38] Сафин Р. Ф. О равномерности систем монотонных функций // Вестник Московского университета. Сер. 1. Математика. Механика. — 2003. — № 2. — С. 15-20.

[39] Сэвидж Д. Е. Сложность вычислений. — М.: Изд.-во «Факториал». — 1998.

[40] Угольников А. Б. О глубине и полиномиальной эквивалентности формул для замкнутых классов двузначной логики // Математические заметки. — 1987. — Т. 42, № 4. — С. 603-612.

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

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

[43] Храпченко В. М. О соотношении между сложностью и глубиной формул в базисе, содержащем медиану // Методы дискретного анализа в теории кодов и схем. Сб. научн. тр., вып. 37. — Новосибирск: Инт математики СО АН СССР, 1981. — С. 77-84.

[44] Храпченко В. М. Новые соотношения между глубиной и задержкой // Дискретная математика. — 1995. — Т. 7, вып. 4. — С. 77-85.

[45] Чашкин А. В. О средней монотонной сложности булевых функций Дискретный анализ и исследование операций. Сер. 1. — 2004. — Т. 11, 4. — С. 68-80.

[46] Черухин Д. Ю. Об инвариантных классах функций, бесповторно выразимых формулами // Дискретный анализ и исследование операций. Сер. 1. — 2002. — Т. 9, 4. — С. 57-74.

[47] Шоломов JI. А. О реализации недоопределенных булевых функций схемами из функциональных элементов // Проблемы кибернетики, вып. 21. — М.: Наука, 1969. — С. 215-226.

[48] Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию // УМН. — 1957. — Т. 12, 6. — С. 189-196.

[49] Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики, вып. 2. — М.: Физматгиз, 1959. -— С. 7-38.

[50] Яблонский С. В. Дискретная математика и математические вопросы кибернетики. Т. I / (Под ред. С. В. Яблонского и О. Б. Лупанова). — М.: Наука, 1974. — С. 9-66.

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

[52] Bellman R. Е. On a quasi-linear equation // Can. Jour. Math. — 1956. — V. 8. — P. 198-202.

[53] Boppana R. В., Sipser M. The complexity of finite functions // Handbook of Theoretical Computer Science. — V. A. Algoritms and complexity — Amsterdam: Elsiver, 1990. — P. 757-804.

[54] McColl W. F., Paterson M. S. The depth of all Boolean functions // SIAM J. Comput. — 1977. — V. 6, № 2. — P. 373-380.

[55] Pippenger N. The mimimum number of edges in graphs with prescribed paths // Math. Systems Theory. — 1979. — V. 12, № 4. — P. 325-346.

[56] Post E. Introduction to a general theory of elementary propositions // Amer. J. Math. — 1921. — Vol. 43. — P. 163-185.

[57] Ragaz M. E. Parallelizable algebras // Archiv fur Mathematische Logik und Grundlagenforschung. — 1986/87. — Bd. 26/1, № 2. — P. 77-99.

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

[59] Smolensky R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity // Proc. 19th Annual ACM Symposium on Theory of Computing (1987). — N. Y.: ACM, 1987. — P. 77-82.

[60] Spira P. M. On the time necessary to compute switching functions // IEEE Transactions on Computers. — 1971. — V. 20 (1). — P. 104-105.

[61] Spira P. M. On time-hardware complexity tradeoffs for Boolean functions // Proc. 4th Hawai Symposium on System Sciences. — 1971. — P. 525-527.

[62] Wegener I. Relating monotone formula size and monotone formula depth of Boolean functions // Information Processing Letters. — 1983. — V. 16. — P. 41-42.

Работы автора по теме диссертации

[63] Кочергин А. В. О глубине функций fc-значной логики в бесконечных базисах // Вестник Московского университета. Сер. 1. Математика. Механика. — 2011. — № 1. — С. 22-26.

Кочергин А. В. О глубине функций многозначной логики // Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О. Б. Лупанова (Москва, 18-23 июня 2012 г.). — М.: Изд-во механико-математического факультета МГУ, 2012. — С. 133-135.

Кочергин А. В. О глубине функций А;-значной логики в конечных базисах // Вестник Московского университета. Сер. 1. Математика. Механика. — 2013. — № 1. — С. 56-59.