О глубине функций многозначной логики

• Автор: Кочергин, Алексей Вадимович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 86 с.

Оглавление
Введение

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].
Уточним постановку задачи. Пусть каждой схеме 5 над заданным базисом поставлено в соответствие неотрицательное число Ь(Б) — сложность этой схеме. Для каждой функции / определяется ее сложность £(/) следующим образом Т(/) = ттФ(5), где минимум берется по всем схемам 5, реализующим функцию /. Задача состоит в построении для каждой рассматриваемой функции / схемы 5, удовлетворяющей равенству !/(/) = Д(5). Однако такая задача, как правило, оказывается очень трудной. В связи с этим часто рассматривают задачу построения схем, в том или ином смысле близких к оптимальным (например, асиптотически оптимальных схем). Вводится функция Ь(Р) = тахТ(/), где максимум берется по всем функциям / из некоторого класса У (класс У предполается конечным и состоящим из функций, допускающих реалицию в заданном классе схем). Требуется найти метод синтеза схем, позволяющий для произвольной функции / из класса У, построить схему 5, которая реализует функцию / и для которой значение Т(5) близко к величине Т(Т). Например, если — класс всех функций /с-значной логики от п переменных,

< cLt + (l°gfc 2)схв fтт./2"| + c( |"n/2] ) + d% + (A; + 3)e?i + 0(3 + -D^ ( [n/2] ).
В силу произвольности булевой квазифункции g получаем неравенство
D'B(n) < (logfe 2)ав [n/2] + с([п/2]) + D'B(n/2]) + d5,
где d5 = di+d,2+(kJro)dl+d:i. Используя последнее неравенство, индукцией по п несложно показать, что имеет место соотнощение
D'B(n) < (ogk2)aB(n/2] + [[n/2]/2] + ... + 1) +
+(с(Гп/21) + c([[n/2]/2]) + ... + с(1)) + [log2nd5 + D'B( 1).
Поскольку для любого положительного числа х имеет место соотношение [[х]/2] = [х/2], то последнее неравенство можно переписать в виде
D'B{n) < (logfc 2)aB([n/2] + [n/4] + [n/8] + ... + 1) +
+ (c([n/2]) + c([n/4]) + c([n/8]) + ... + c(l)) + [log2n]d5 + D'B( 1).
В силу (1.4) выполняется соотношение
[n/2] + [n/4] + [n/8] + ... + 1 < n + [log2 n].
Таким образом, справедливо неравенство
D'B{n) < (logfc2)aBn + (c([n/2]) + c([n/4]) + c([n/8]) + ... + c(l)) +
+ [log2 n](d5 + (logfc 2)aB) + D'B{).
Отсюда и в силу леммы 1.12 получаем доказываемое утверждение. Лемма 1.14 доказана.
Перейдем к доказательству верхней оценки. Сначала покажем, что имеет иместо следующее простое утверждение.
Лемма 1.15. Существует такая положительная константа Ci, что при любом натуральном п справедливо неравенство
DB(n) < Сп.