Содержание к диссертации
Введение
Глава 1. Представление функций на основе специальных универсальных множеств. Некоторые вопросы суперпозиции схем 21
1.1. Селекторные разбиения множества переменных булевых функций 21
1.2. Универсальные множества функций и способы их построения 29
1.3. Некоторые вопросы суперпозиции и синтеза ориентированных контактных схем 36
Глава 2. Синтез оптимальных по весу ориентированных контактных схем с ограниченной полустепенью исхода 40
2.1. Построение универсальных множеств для некоторых функций 40
2.2. Синтез ориентированных контактных схем на основе регулярных разбиений единичного куба и универсальных множеств функций 54
2.3. Оценки числа схем из некоторых классов ориентированных контактных схем 66
Глава 3. Синтез оптимальных по сложности ориентированных контактных схем с ограниченной полустепенью исхода 74
3.1. Некоторые сведения из теории полислов 74
3.2. Верхние оценки сложности ориентированных контактных схем с ограниченной полустепенью исхода 77
Глава 4. Синтез оптимальных по сложности ориентированных и итеративных контактных схем с ограниченной степенью 102
4.1. Верхние оценки сложности схем с ограниченной степенью 102
4.1.1. Синтез итеративных контактных схем 102
4.1.2. Синтез ориентированных контактных схем 117
4.2. Нижние мощностные оценки функций Шеннона 118
Литература 120
- Универсальные множества функций и способы их построения
- Синтез ориентированных контактных схем на основе регулярных разбиений единичного куба и универсальных множеств функций
- Верхние оценки сложности ориентированных контактных схем с ограниченной полустепенью исхода
- Синтез итеративных контактных схем
Введение к работе
Общая характеристика работы
Теория дискретных управляющих систем является важным разделом дискретной математики и математической кибернетики [16,24,33]. Она занимается изучением математических моделей дискретных преобразователей информации, то есть устройств, осуществляющих требуемое преобразование наборов входных значений в выходные. К числу примеров подобных устройств относятся различные виды интегральных схем.
Каждая математическая модель дискретного преобразователя информации, рассматриваемая в теории управляющих систем, характеризуется заданием набора базисных элементов, правил построения схем и законов их функционирования. Отметим, что схема традиционно задается графом определенного вида, а ее функционирование описывается системой функций алгебры логики (булевых функций). При этом говорится, что система функций реализуется схемой.
Одна из основных задач теории управляющих систем - задача синтеза, -состоит в построении для заданной системы функций F реализующей её схемы Е из заданного класса, на которой достигается оптимальное значение заданного «"показателя» эффективности. В качестве показателя эффективности традиционно используется функционал L, который ставит в соответствие каждой схеме Е из заданного класса некоторое неотрицательное действительное число .ЦЕ), называемое её сложностью. Решение задачи синтеза для системы функций F состоит в нахождении схемы Е, обладающей минимальной сложностью среди всех схем из заданного класса, реализующих F.
Понятие полноты заданного класса управляющих систем означает, что схемами из этого класса можно реализовать любую булеву функцию. В этом случае можно определить сложность произвольной булевой функции, как минимальную сложность схемы, которая ее реализует. В теории дискретных управляющих систем рассматривается асимптотическая постановка задачи
синтеза, которая была впервые предложена К. Шенноном [3]. В этой постановке вводится функция Ь{п) от натурального аргумента п, названная впоследствии функцией Шеннона, которая равна максимальной сложности булевой функции от п переменных при ее реализации схемами из заданного класса. Таким образом, Ь{п) характеризует сложность реализации самой «трудной» функции от п переменных в заданном классе схем. Далее изучается поведение функции L(n) при растущих значениях п.
В работе [3] был установлен порядок 2п/п функции Шеннона LKC(n), связанной со сложностью контактных схем, где под сложностью понималось общее число контактов схемы. Асимптотическое значение 2п/п этой функции Шеннона было позже получено О. Б. Лупановым [19]. Изучение основных классов схем продолжилось в работах О. Б. Лупанова [20,21,23], где им была установлена асимптотика функций Шеннона, связанных с классом релейно-контактных схем, классом схем из функциональных элементов и формул над произвольным полным конечным базисом.
Среди различных моделей дискретных управляющих систем можно выделить классы систем «преобразующего» («функционального») и «проводящего» («контактного») типов. В системах «преобразующего» или «функционального» типа схемы обычно строятся по определенным правилам из элементов априорно заданного базиса. Каждый элемент базиса реализует некоторую булеву функцию (базисную функцию) и обладает определенной сложностью. Граф схемы задает последовательность операций суперпозиции базисных функций. Примерами управляющих систем «преобразующего» типа являются класс схем из функциональных элементов и класс формул, построенных из элементов конечного полного базиса (см., например, [33]) и др. При реализации булевых функций схемами из перечисленных моделей учитываются такие меры сложности, как общее число элементов в схеме, сумма сложностей элементов, из которых состоит схема, задержка или время срабатывания схемы, площадь (объем) геометрической реализации схемы на плоскости (в пространстве) и т.д.
В управляющих системах «проводящего» или «контактного» типа реализация булевых функций осуществляется с помощью передачи сигналов по ребрам (дугам) графа схемы, называемых контактами. При этом проводимостью контактов «управляют» внешние или специальные внутренние булевы
переменные. К системам «контактного» типа относятся класс контактных схем [20], класс релейно-контактных схем [23] и др.
При моделировании дискретных преобразователей информации обычно стремятся учесть их физические особенности, например, площадь, емкость или задержку функционального элемента интегральной схемы, возможность реализации схемы на плоскости и т.д. С этой целью ставится задача синтеза для классов схем с некоторыми ограничениями на структуру, а также применяются различные подходы к определению сложности схем.
Настоящая работа посвящена решению задачи синтеза в асимптотической постановке для некоторых классов схем «контактного» типа при наличии различных ограничений на смежные контакты схем. Перечислим основные результаты асимптотической теории синтеза, связанные с изучением схем «контактного» типа, а также укажем известные подходы к введению структурных ограничений и определению сложности схем.
Напомним, что функция Шеннона для сложности схем из функциональных элементов над произвольным полным конечным базисом Б асимптотически равна рБ2п/п, где рБ - некоторая константа, зависящая от базиса Б [20]. Класс формул [21] над базисом Б является частным случаем класса схем из функциональных элементов, в которых выход любого элемента может быть соединен только с одним входом другого элемента. В работе [21] О. Б. Лу-паповым была установлена асимптотика1 рв2п/ log п функции Шеннона для сложности формул над базисом Б. Таким образом, введение «жёстких» ограничений на,структуру схемы повлияло на порядок функции Шеннона. В работе [22] О. Б. Лупапов изучал класс схем из функциональных элементов над базисом Б, являющийся промежуточным между классом схем без ограничений [20] и классом формул [21]. В нем выход любого элемента мог соединятся не более, чем с d входами других элементов, где d - константа. Было установлено, что при определенных соотношениях на величину d, а также сложность и число входов элементов базиса Б, асимптотика соответствующей функции Шеннона по-прежнему составляет рБ2п/п.
Класс параллельно-последовательных схем (7г-схем) (см., например, [24]) -частный случай класса контактных схем, допускающих, в частности, геомет-
ХВ данной работе основание 2 у логарифмов опускается.
рическую реализацию на плоскости. Воспользовавшись соответствием между 7Г-схемами и формулами над базисом {&, V, -}, в которых знаки отрицания встречаются лишь над символами переменных, а также методом синтеза [21], можно получить асимптотическое значение 2n/logn функции Шеннона Ь*(п), связанной со сложностью булевых функций в классе 7г-схем (см. также [24]).
В работе [7] А. Д. Коршуновым было изучено асимптотическое поведение функций Шеннона ЬдС(п) и Ьд(п), связанных со сложностью реализации булевых функций контактными схемами и 7г-схемами соответственно с ограничением Л на степени вершин схем. При А ^ 3 была установлена асимптотика функции Шеннона ЬдС(п) вида j^2n/n, а для функции Шеннона Щ(п) было доказано, что при любом А ^ 3 она асимптотически равна 2п/ log п.
Представление булевых функций с помощью двоичных решающих диаграмм (Binary Decision Diagrams, BDD) было впервые предложено в [1]. Отметим, что BDD можно рассматривать, как ориентированную контактную схему с одним истоком, являющимся входом, и двумя стоками, являющимися выходами, в графе которой отсутствуют ориентированные циклы и из каждой вершины, отличной от выходов, исходят две дуги с противоположными пометками вида Х{,щ. Под размером BDD понимается количество вершин BDD, отличных от выходов. В другой интерпретации [8], BDD можно рассматривать как программу, состоящую из операторов условного перехода, не содержащую циклов и имеющую две точки останова 0 и 1. В каждом операторе условного перехода вычисляется значение одной из входных булевых переменных и в зависимости от вычисленного значения осуществляется переход либо в другой оператор программы, либо в одну из точек останова. Результат работы программы на заданном наборе переменных определяется той точкой останова, в которую приведет последовательность операторов перехода (путь вычисления). Под размером программы понимается количество содержащихся в ней операторов. В работе [1] была получена нижняя асимптотическая оценка 2п~1/п и верхняя асимптотическая оценка 2п+2/п для функции Шеннона 5BDD(n), связанной с реализацией булевых функций в классе BDD. Позднее в [8] для этой функции была установлена асимптотика 2п/п.
Отметим, что для получения верхней оценки функции Шеннона, связан-
ной со сложностью реализации булевых функций в заданном классе схем, обычно предлагается специальный метод синтеза, а соответствующая нижняя оценка устанавливается из т.н. мощностного неравенства, предложенного К. Шенноном [3]. Точность получаемых оценок можно характеризовать их относительной погрешностью, равной отношению разности между верхней и нижней оценками функции Шеннона к ней самой [13]. Будем также рассматривать г(п)-нормированную относительную погрешность (г(п)-НОП) оценок некоторой функции Шеннона Ь(п), равную величине относительной погрешности оценок, умноженной на г (га), где г (га) - растущая функция от натурального аргумента га.
Для указанных выше оценок [19], [7] и [8] функций Шеннона LKC(ra), 1/д(га) и 5'BDD(ra) соответственно величина га-НОП составляла 0(л/п). Оценки [21] и [7] функций Шеннона 1Л(га) и Щ(п) соответственно для классов 7г-схем, а также оценки функции Шеннона, связанной со сложностью формул над произвольным полным конечным базисом, были получены с log га-НОП вида O(loglogra).
Работа С. А. Ложкина [9] положила начало исследованиям, связанным с уточнением известных оценок функций Шеннона для основных классов схем. В частности, в [9] изучался класс ориентированных контактных схем, т.е. контактных схем из ориентированных контактов, и для соответствующей функции Шеннона LOKC(ra) были получены асимптотические оценки, имеющие га-НОП вида 0(1). В работе [11] С. А. Ложкиным был предложен термин асимптотические оценки высокой степени точности (АОВСТ), для обозначения оценок некоторой функции Шеннона L{n) с г(га)-НОП вида 0(1), где г (га) асимптотически равно отношению 2п/Ь(п).
В работах [10-14] был изложен общий подход к получению верхних асимптотических оценок функций Шеннона, который в т.ч. позволяет получать АОВСТ для функций Шеннона, связанных с реализацией булевых функций в основных классах управляющих систем. В частности, в этих работах были получены АОВСТ для сложности формул над произвольном полным конечным базисом, для сложности схем из функциональных элементов с ограничениями на ветвления выходов элементов определенного типа, а также для сложности т.н. функционально-проводящих схем, класс которых обобщает некоторые распространенные классы схем.
Отметим, методы синтеза [11] позволяют установить асимптотическое значение 2п~1/п функции Шеннона /,икс(п), связанной с реализацией булевых функций в классе итеративных контактных схем, который является модификацией класса релейно-контактных схем [23]. При этом полученные оценки будут иметь тг-НОП вида 0(1), т.е. будут являться оценками высокой степени точности.
В работе [25] рассматривались схемы из функциональных элементов над произвольным полным базисом Б и элементом задержки, в которых допускались ветвления выходов только элементов задержки, а параметр t задавал максимальное допустимое количество ветвящихся элементов задержки в схеме. При некоторых ограничениях на величину t = t(n) были получены АОВСТ для соответствующей функции Шеннона.
В последнее время активно изучаются различные подклассы BDD, в которых вводятся определенные ограничения на структуру BDD (см, например, [2,4,5,15]). Так, например, рассматриваются упорядоченные (строго) ^-считывающие BDD, в которых каждый путь вычисления разбивается на к непересекающихся сегментов, таких, что на каждом сегменте каждая переменная встречается не более одного раза (соответственно в точности один раз) и переменные встречаются в определенном порядке, одинаковом для всех сегментов и путей вычисления. Упорядоченные 1-считывающие BDD являются «удобной» структурой данных для внутреннего представления некоторых булевых функций в системах автоматизированного проектирования интегральных схем (см., например, [2]). Исследуются вопросы о возможности реализации булевых функций упорядоченными (строго) ^-считывающими BDD полиномиальной сложности, а также вопросы существования нижних экспоненциальных оценок для сложности булевых функций в этих классах BDD (см. [5]). Отметим, что при к ^ 2 асимптотическое значение 2п/п для сложности упорядоченных ^-считывающих и строго ^-считывающих BDD приводится в работе [15]. При этом полученные оценки имеют n-НОП вида o(logn). Там же получены асимптотические оценки для сложности BDD общего вида с n-НОП вида o(log7i).
В работе [26] описан класс схем контактного типа, представляющий собой математическую модель интегральных схем на дополняющих МОП-транзисторах (КМОП схем). В этой модели замыкающий (соответственно размыкаю-
щий) контакт переменной Х{ соответствует n-МОП или р-МОП транзистору, на затвор которого подаётся значение Хі (соответственно жг-), а контактная схема описывает соединения между истоками и стоками транзисторов. Отметим, что одно из естественных ограничений, которое можно вводить в подобных моделях, является ограничение степеней вершин контактной схемы. В работе [26] установлена асимптотика 2n+l/n функции Шеннона, связанной со сложностью КМОП схем, для случая, когда контакты разрешается помечать только символами «внешних» булевых переменных. В другой модели КМОП схем [6] допускается использование в качестве пометок контактов специальных «внутренних» булевых переменных, реализуемых в вершинах схемы. Для соответствующей функции Шеннона в работе [6] получена асимптотика вида 2п/п.
Перейдем к описанию классов схем, рассматриваемых в диссертации. Начнем с описания классов ориентированных контактных схем, в которых ограничена одна из полустепеней вершин.
В данной работе вводится класс ориентированных контактных схем U^'v^' с ограничением Л на полустепень исхода вершин схемы и ограничением v на количество различных булевых переменных, которые используются среди пометок исходящих дуг. При таком определении произвольная BDD принадлежит указанному классу схем при Л.= 2, v = 1. Под сложностью ориентированной- контактной схемы понимается, как обычно, число контактов в ней. В работе разработаны новые методы синтеза, позволяющие установить асимптотические оценки сложности схем из класса Z^A,^"OKC, при v = Л, а также при Л = 2 и v — 1, имеющие n-НОП вида log log п + O(l). Предложенные методы синтеза позволяют также получить асимптотические оценки сложности BDD и сложности упорядоченных ^-считывающих BDD при к ^ 4 с n-НОП вида log log п + O(l). Таким образом, получены более точные, по сравнению с работой [15], асимптотические оценки соответствующих функций Шеннона для классов BDD.
С целью получения асимптотически оптимальных ориентированных контактных схем класса U^,l/^'0KC, обладающих некоторыми дополнительными свойствами, в работе предлагаются альтернативные подходы к определению сложности булевых функций.
В первом подходе для произвольных действительных положительных чи-
сел w' и w", где w" > w', вес вершины v ориентированной контактной схемы
полагается равным и/, если в v заходит не более одной дуги и w" иначе. Вес
схемы равен сумме весов её вершин. Для функций Шеннона, связанных с ве
сом схем класса весом BDD, а также весом упорядоченных (строго)
^-считывающих BDD при fc^2B работе получены асимптотические оценки,
являющиеся оценками высокой степени точности.
Следующая постановка задачи синтеза, предлагаемая в работе, состоит в
том, что сложность булевой функции / определяется как минимальная слож
ность схемы из класса^/(Л.гУ)-кс) реализующей / и имеющей не более t вершин,
в которые заходит более одной дуги. При некоторых ограничениях на t = t(n)
в работе получены оценки высокой степени точности для соответствующих
функций Шеннона, связанных с классом и классами BDD.
Теперь опишем рассматриваемые в диссертации классы схем контактного типа, в которых накладывается ограничение на степени вершин. Отметим, что используя методы синтеза [7] можно получить асимптотическое значение j~^2n/n (верхнюю оценку -^2п/п) для функции Шеннона LKC(n) (соответственно L^KC(n)), связанной со сложностью ориентированных контактных схем (соответственно итеративных контактных схем), в которых степени вершин ограничены константой Л. При этом оценки для функции Шеннона LKC(n) можно получить с п-НОП вида 0(л/п).
Метод синтеза, предложенный в настоящей работе позволяет установить асимптотические оценки функции Шеннона LKC(n), для которых п-НОП составляет ^ logn + log log п + 0(1). Также в работе описан новый асимптотически оптимальный метод синтеза, из которого вытекает асимптотика д^-2п_1/п функции Шеннона L"KC(n). При этом оценки, полученные для функции Шеннона L"KC(n) имеют п-НОП вида 0(^Jn\ogn).
Основные результаты работы представлены в [17,18,28-32].
Основные определения и формулировка полученных результатов
В данном параграфе будут введены изучаемые в диссертации классы схем и связанные с ними функции Шеннона, а также будут приведены полученные для этих функций Шеннона асимптотические нижние и верхние оценки.
Напомним основные понятия теории графов.
Набор вида (G, V, V"), где G = (V, Е) - граф с множеством вершин V и множеством ребер Е, а У и V" - упорядоченные выборки из V длины р и q соответственно называется (р, д) -сетью. При этом г-я вершина выборки V' (соответственно выборки V") называется г-м входным полюсом или входом (соответственно г-м выходным полюсом или выходом) сети . Будем называть сеть = (G, V, V") ориентированной (соответственно неориентированной) если граф G является ориентированным (соответственно неориентированным).
Число ребер, инцидентных вершине v графа G, т.е. степень вершины v, будем, как обычно, обозначать через degQ(v). Пусть v - вершина ориентированного графа G, тогда обозначим через degj(v) (соответственно deg^(v)) полустепень захода вершины v, т.е. число дуг, заходящих в v (соответственно полустепень исхода вершины и, т.е. число дуг, исходящих из v). Напомним, что вершина v ориентированного графа G называется стоком (соответственно истоком), если deg^(v) = 0 (соответственно degj(v) = 0).
Буквами булевой переменной Х{ будем называть Х{ и х\.
Неориентированная сеть Е с входами а\,..., ар, выходами &i,..., bq, в которой все ребра помечены буквами переменных xi,...,xn, называется (р, q)-KOHmaKmnou схемой ((р, q)-KC) от переменных хі,...,хпк обозначается Е(#і,..., хп) или Е(аі,..., ар; &i,..., bq\ х\,..., хп). Ребра КС называются контактами. При этом контакт, помеченный буквой Х{ (буквой xi) называется замыкающим (соответственно размыкающим). Обозначим множество всех контактных схем через Ыко.
Напомним, что в графе G = (V:E) последовательность, состоящая из ребер ei,... ,еп, где ег- = (vi,Vi+i) Є Е, называется {v\ — vn+\) путём графа G. Если все ребра пути различны, то он называется цепью, а если, кроме того, различны все его вершины, то - простой цепью. Цепь, начальная и конечная вершина которой совпадают, называется циклом.
Пусть - КС от переменных х\,..., хп и пусть vi, г?2 - вершины Е. Определим функцию проводимости gVuV2(x\,... ,хп) между вершинами v\ и V2, как булеву функцию, которая равна 1 на наборе а — (а\,..., ап) {0,1}п тогда и только тогда, когда в схеме Е существует (v\ — г^) цепь, состоящая из контактов, помеченных буквами ж"1,..., х*п При этом будем говорить, что
функция gVl,v2 реализуется между вершинами v\,V2- Отметим, что функции проводимости gVl,v2 и gV2,Vl совпадают.
Положим по определению, что если v — вершина (1, m)-KC Е, то в v реализуется функция проводимости между входом и вершиной v, и что Е реализует набор функций (/і,..., /то), где fi - функция проводимости между входом и г-м выходом схемы Е, г = 1,... , т. Также будем говорить, что (р, q)-KC Е(жі,..., хп) реализует матрицу из р строк и q столбцов, состоящую из булевых функций от переменных xi,...,xn так, что на пересечении г'-й строки и j-ro столбца стоит функция проводимости между г-м входом и j-u выходом схемы Е, г = 1,... ,р, j = 1,..., q. Схемы Е' и Е", реализующие матрицы F' и F" соответственно, называются эквивалентными, если2 F' = F".
Аналогично определяется структура и функционирование ориентированной контактной схемы (ОКС) с тем исключением, что граф ОКС является ориентированной сетью. При этом отметим, что если v\ и г>2 - различные вершины ОКС Е, то в общем случае функции проводимости gVl,V2 и S^i могут не совпадать. Обозначим через Ыокс множество всех ОКС.
Пусть р ^ 1. Назовем р-входовой двоичной решающей диаграммой {p-BDD) любую (р, 2)-0КС Е(яі,..., хп), граф которой не содержит ориентированных циклов, входы Е и только они являются истоками, выходы являются стоками и из каждой вершины Е, отличной от выходов, исходит-пара противоположных контактов, помеченных буквами Х{ и Хі, где г Є [1,п]. При этом выходы p-BDD Е помечены 0 и 1, и считается, что Е реализует столбец функций проводимости между входами и выходом, помеченным 1.
Обозначим через UBDD класс всех ОКС, являющихся p-BDD для некоторого р ^ 1. Для удобства в обозначении произвольной схемы Е из класса UBDT) будем иногда опускать указание числа входов схемы и называть схему Е двоичной решающей диаграммой (BDD). Отметим, что определение 1-входовой BDD совпадает с традиционным определением двоичной решающей диаграммы или ветвящейся программы (см., например, [4,5]).
Будем также рассматривать BDD с некоторыми структурными ограничениями. Зафиксируем порядок булевых переменных xi,... ,хп. Назовем BDD Е от переменных Xi,...,xn упорядоченной (строго) k-считывающей с по-
2Равенство булевых функций, как обычно, будем рассматривать с точностью до добавления или изъятия несущественных переменных.
рядком переменных х\,... ,хп, если произвольная простая цепь из входа в выход Е разбивается на к сегментов, таких, что:
на каждом сегменте переменные встречаются в порядке х\,..., хп;
на каждом сегменте каждая переменная встречается не более одного раза (соответственно в точности один раз).
Множество всех упорядоченных ^-считывающих (соответственно строго fc-считывающих) с порядком хь ..., хп BDD обозначим через Uk'OBDD(x\,..., хп) (соответственно через Uk-SOBDD(xi,..., хп)). Введем также класс Uk-BDD (Uk-S0BDD), содержащий все упорядоченные fc-считывающие (соответственно строго к-считывающие) BDD.
Пусть в (1, ?п)-КС Е(а; &i,..., Ът; х\,..., хп) переменная Хі входит без отрицаний, а функция /j, реализуемая в выходе bj, не зависит от переменной Х{. В этом случае определим операцию присоединения переменной хі к выходу bj, в результате которой вершине, помеченной bj, сопоставляется внутренняя переменная и, выходная пометка bj снимается, а все пометки Х{ заменяются на пометку и. Полученная таким образом схема Е' зависит от переменных х\,..., Хі-і,Хі+і, . , хп, имеет входной полюс а и выходные полюса b\,..., &j_i,*6j_|_i, ..., Ът. Пусть v - вершина схемы Е, и пусть gajV - функция, которая в ней реализуется, тогда по определению положим, что в схеме Е' в вершине v реализуется функция ga,v(xi,..., xi-\, fj, Жі+ь > хп)- Функционирование схемы Е' представляет собой набор функций, реализуемых в ее выходах. Теперь пусть 1 < j\ < ... < % ^ т и 1 ^ ii < ... < %k ^ п -наборы индексов и пусть переменные х^,..., Xik входят в схему Е без отрицаний, а каждая из функций /^,..., fjk не зависит существенно от переменных 3,..., Xik. В этом случае определим операцию одновременного присоединения переменных Xii:... ,Х{к к выходам bjx,..., bjk соответственно, состоящую в последовательном выполнении операций присоединения переменной Х{г к выходу bjx, ..., переменной Xik к выходу bjk. При этом выходу bjt сопоставляется внутренняя переменная Ujt, t = 1,..., к. Нетрудно убедиться в том, что при выполнении указанных условий на функции /^,..., fjk введённая операция определена корректно и её результат не зависит от порядка, в котором применяются однократные операции присоединения переменной к выходу. Схема, полученная в результате присоединения переменных к выходам,
называется итеративной контактной схемой {ИКС) на базе КС Е. Множество всех ИКС обозначим через иИкс.
Для КС (ОКС) Е и натурального Л обозначим через М>А() множество вершин v схемы Е, таких, что degs(v) > Л. Для ОКС Е положим М>Л() (соответственно М~Л(Е)) - множество вершин v схемы S, таких, что deg(i;) > Л (соответственно elegit)) > Л). Если ' - ИКС на базе КС Е, то положим М>Л(Е') = М>Л(Е).
Для вершины v ОКС Е обозначим через u^(v) число различных булевых переменных, которые встречаются среди пометок дуг, исходящих из г;. Пусть г/(Е) = maxvz(v), где максимум берется по всем вершинам Е.
Обозначим через множество всех ОКС Е, таких, что множе-
ство М~Л(Е) является пустым и ^(Е) ^ и. Таким образом, класс содержит схемы, в которых из каждой вершины исходит не более Л дуг, а среди пометок этих дуг используются буквы не более, чем і/ различных булевых переменных. Отметим, что из введённых определений следует, что
uBvn с и^1)~окс.
Пусть Е - схема, принадлежащая одному из введенных выше классов ЫА, тогда сложностью ДЕ) схемы Е называется число контактов в Е. Отметим, что если Е является BDD, то 1/(Е) - четное и число вершин Е равно величине (L(S)/2 + 2). В предположении, что класс является полным, т.е. что любую булеву функцию можно реализовать некоторой схемой из класса ЫА, для булевой функции / определим величину LA(f), называемую сложностью f относительно функционала LA, как минимальное значение величины L(E) на множестве тех схем Е из ЫА, которые реализуют /. Для натурального п определим, как обычно, функцию Шеннона LA(n)
LA(n)= max LA(f).
f(xit...,xn)
Пусть дополнительно известно, что для натурального Л множество схем Е класса ЫА, таких, что степени вершин Е не превосходят Л, является полным. Тогда для булевой функции / определим LA(/), как минимальное значение величины Ь(Е) на множестве схем Е из UA, реализующих /, таких,
что М>Л(Е) = 0. Введём соответствующую функцию Шеннона LA (п)
LA(n) = max Lft/).
Пусть г; - вершина ОКС Е. Для положительных действительных величин
w' и го", где го" > w', введем понятие веса Wwi)W>t(v) вершины v следующим
образом:
Г«/, degj^Xl,
Ww'tW»{v) = < +
[ w", deg(v) > 1.
Вес WW'iW"(H) схемы E есть сумма весов вершин Е.
Пусть ЫА - один из введенных выше классов ОКС с ограничением на полу степени исхода вершин. В предположении, что класс ЫА является полным, для булевой функции / определим величину WA,w„(f), называемую весом f относительно функционала WA, w„, как минимальное значение величины WW')Wit(Y?) на множестве тех схем Е из ЫА, которые реализуют /. Пусть для натурального параметра t подмножество схем S класса UA, таких, что IM+^E)! < t, является полным. Тогда определим LA(f,t), как минимальное значение величины L(E) на множестве схем Е из UA, реализующих /, таких, что IM+^E)! ^ t. Введём функции Шеннона WA,w„(n) и LA(n,t)
ww',w"(n) = t ,max WtW„(f),
f{xi,...,xn)
LA(n,t)= max LA{f,t).
f(xi,...,xn)
Точность оценок некоторой функции Шеннона L{n) будем характеризовать их относительной погрешностью (ОП), т.е. отношением разности между верхней и нижней оценками функции Шеннона к ней самой [13]. Также введём п-нормированную относительную погрешность (п-НОП) оценок функции Шеннона L(n), равную величине относительной погрешности, умноженной на п. Асимптотическими оценками функции Шеннона Ь(п) высокой степени точности будем называть оценки с п-НОП вида 0(1).
Перечислим основные результаты для введенных функций Шеннона. Первая серия результатов относится к поведению функций Шеннона для веса ориентированных контактных схем и BDD.
Теорема 1. Для любых натуральных X и v, где X^2ul^i/^X, а также положительных вещественных величин w' и из", где ги" > ги'', при п = 1,2,... справедливо3
w^w-^.;(1+^*"±0w). (1)
Теорема 2. Для любого натурального k ^ 2, а также положительных вещественных величин w' и w", где w" > w'; при п = 1,2,... справедливо
ft \ ГЬ J
п \ п
И4«»(„) . ^ Л + 21g"±0W) . (4)
' п \ п J
Отметим, что полученные асимптотические оценки (1)-(4) являются оценками высокой степени точности.
В диссертации также установлено, что если в определении веса WwijW»(T,) ОКС Е учитывать с весом w" вершины, в которые заходит более d дуг, где d - натуральная константа, а все остальные вершины учитывать с весом ги', то асимптотика соответствующих функций Шеннона по-прежнему составляет -^ 2п/п для класса U^x,v^'OKC и w' 2п/п для классов BDD.
Перечислим результаты для функций Шеннона, связанных со сложностью ориентированных контактных схем и BDD при наличии растущего ограничения t = t(n) на число вершин с полустепенью захода больше 1.
Теорема 3. Для любых натуральных X и и, где A^2ul^i/^A, при п = 1,2,... и t = t(n), гдеА \ogt(n) = fl(n) и t(n) не превосходит 2п/п2, справедливо
L<^>-OKCM) = * . Т Л ± о (-) V
K,J Л-1 logi + ^lognV \nJJ
3Равенство r(n) — pin) ±0(q(n)) означает, что \г(п) — р(п)\ = 0(q(n)). 4Равенство р(п) = Cl(q(n)) означает, что р(п) = 0(q(n)) и q(n) = 0(р(п)).
Теорема 4. Для любого натурального к ^ 2 при п = 1,2,... u = ^(^); где і(п) —» оо при п —> со u і(п) не превосходит 2п/п2, справедливо
Lk-SOBm(n,t) = ^-(l±Or 1 ^
logt \
и если, кроме того, log t(n) = ft(n), то
lbd>-^(i±o6))' ifcoBD>-*)=iS(i±o)-
Отметим, что асимптотические оценки, приведенные в теореме 3 и в теореме 4 для класса BDD и класса упорядоченных ^-считывающих BDD при k ^ 2, являются оценками высокой степени точности.
Укажем результаты для функций Шеннона, связанных со сложностью ориентированных контактных схем с ограниченной полустепенью исхода.
Теорема 5. Для любых натуральных X и и, где A^2«1^j/^A, при п = 1,2,... справедлива нижняя оценка
Ь<«.окс(п) > А . 21 /х + W'^-ОД)
Л — 1 n \ n /
а также в случае v = 1, Х — 2 и в случае v — А при п = 1, 2,... справедлива верхняя оценка
ь<А,,)-окс(п) ^ _j*_ . 22 Л + ^^Г^п +log log n + Q(l)\
^ Л — 1 п \ п J
Теорема 6. Для любого натурального к ^ 4 при п = 1,2,... справедливы оценки
2^ / + loglogn + OWy
п \ п J
пп+1 / / 1 \ \ ОП+1
±_(1_0(-П
Легко видеть, что асимптотические оценки, приведенные в теоремах 5, 6 имеют те-НОП вида log log п + 0(1).
Наконец, приведем результаты для функций Шеннона, связанных со сложностью итеративных и ориентированных контактных схем, в которых степени вершин ограничены константой Л.
Теорема 7. Для любого натурального А ^ 3 при п — 1,2,... справедливы оценки
п А 2П Л -^logn + loglogn-hO(l)
okc,_w А 2" Л >hlBn + 0(l)
Г» <
А — 2 те \ п
Таким образом, оценки для функции Шеннона LKC(n) имеет n-НОП вида д^2 log n -f log log те + O(l).
Теорема 8.. Ддл любого натурального А ^ 3 npw n = 1,2,... справедливы оценки
А 22 / logn - Q(m < * / AgnNN
2А-2 п \ те /AW2A-2nV \ V J J
В диссертации также установлено, что нижние оценки, перечисленные в теоремах 1-8, справедливы для сложности и веса - относительно соответствующих функционалов, - почти всех булевых функций от те переменных.
Отметим, что методы синтеза, используемые в диссертации при доказательстве верхних оценок теорем 1, 3 и 5 для класса ОКС с ограниченной полустепенью исхода, могут быть применены для получения аналогичных результатов в модели ОКС с ограниченной полустепенью захода.
Дальнейшее изложение будет построено следующим образом. Глава 1 содержит вспомогательные определения и утверждения, необходимые для получения верхних оценок функций Шеннона. В ней вводятся такие понятия, как селекторное разбиение переменных булевой функции, каноническая матрица булевой функции, универсальное множество функций и др. Там же приводятся простейшие методы синтеза схем. В главе 2 описывается метод синтеза схем из класса /(Л>")-кс На основе регулярных разбиений единичного
куба и универсальных множеств функций, позволяющий установить верхние оценки в теоремах 1-4. Также в главе 2 доказываются верхние оценки числа схем определённого вида из класса ц{х^)-кс и классов BDD, которые затем используются при получении мощностных неравенств, позволяющих установить нижние оценки в теоремах 1-6. В третьей главе описан новый метод синтеза для получения верхних оценок теорем 5 и 6. Доказательство верхних и нижних оценок теорем 7 и 8 ведётся в главе 4 диссертации. При этом доказательство верхней оценки теоремы 7 основано на использовании метода синтеза главы 3, в то время как верхние оценки теоремы 8 получены с использованием нового метода синтеза.
Универсальные множества функций и способы их построения
На наборах единичного куба Вп будем рассматривать лексикографический порядок, который задается нумерацией N : Вп — [0,2П), такой, что для набора ос = (скі,..., ап) Є Вп его номер М{а) равен Для натурального s обозначим через fis матрицу из Bs 2\ такую, что все столбцы ц3- различны и для j — 1,..., 2s столбец fj,sijl есть транспонированный набор а из Bs, имеющий номер N(a) = (j — 1). Таким образом, матрица /is имеет вид Пусть функция (р(уі,... ,yt) существенно зависит от своих переменных, D = (Yi,..., Yd) - селекторное разбиение множества переменных ip, N - селективная матрица разбиения D и s = (si,..., Sd) - набор неотрицательных целых чисел. Для і = 1,..., t положим ki - номер компоненты разбиения D, которой принадлежит переменная у І. Обозначим и определим матрицу М Є Вн,г следующим образом: Матрица М имеет вид где для і — 1,..., t матрица Мг- - (s&., /)-матрица над В. Пусть г Є [1, ] и s&. 0, тогда матрица Мг- имеет вид где для j = I,..., t матрица My - (sjtt, 2Ski )-матрица, причём если ki ф kj, то матрица My состоит из элементов iVp, j J, а если к( = kj, то матрица My равна матрице jiSk,. Матрицу М, построенную указанным образом, будем называть канонической для функции (р, разбиения D, селективной матрицы N и спектра s [13]. Отметим, что для j — 1,..., t длина матрицы My равна 2Shi для любого і Є [1, t]. Положим и будем считать, что матрица М соответствует переменной yj. Также бу дем считать, что конкатенация вида М ... М т соответствует набору переменных (yj17... ;yjm). Легко видеть, что если спектр ё состоит из чётных чисел, то для любого j, j Є [1, t], 5-подматрица матрицы состоящая из строк с чётными номерами совпадает с точностью до перестановки столбцов с б -подматрицей матрицы М \ состоящей из строк с нечётными номерами, и содержит 2Skj различных столбцов. Отметим, что если у и yj2 попадают в одну компоненту разбиения D, то матрицы М и М 2 совпадают. Отсюда вытекает неравенство
Из определений вытекает, что если D - тривиальное разбиение переменных функции р, в котором г -я компонента содержит переменную у і, і — 1, . . . , t, то матрица М имеет структуру, приведённую на рис. 1.1. Рис. 1.1: Каноническая матрица для тривиального разбиения Из определения канонической матрицы вытекает следующее утверждение. Лемма 1.3. Пусть функция p(yi,... ,yt) существенно зависит от своих переменных, D - селекторное разбиение множества переменных функции (р, матрица М является канонической для функции р и разбиения D, а матрица М - произвольная S-подматрица матрицы М, тогда для любого а, а Є Bh(M} 1, найдутся единственные натуральные числа ji,... ,jt, такие, что где М ) - С-подматрица матрицы М, соответствующая переменной yj, j = l,..., . Доказательство. Рассмотрим случай М = М. Пусть разбиение D имеет длину d, a ki - номер компоненты разбиения D, которой принадлежит переменная УІ, і = 1,..., t. Будем считать, что матрица М является канонической для селективной матрицы N Є Bb,t и спектра s = (s\,... , Sd). Представим матрицу М \ j Є [l,t], и столбец а в виде где h(Mij) = h{ai) = ski, і = 1,...,t. Пусть і є [l,t]. Если Sk, = 0, тогда положим ji = 1. Пусть Sk, 0 и при подстановке в функцию элементов набора N(i) на места всех переменных, за исключением переменных компоненты DlkiJ функция р совпадает с у І Si, где Si Є В, тогда найдется единственный номер ji столбца матрицы М , совпадающего с оц @ 5І. Положим и докажем, что J3 = а. Действительно, пусть (3 — Д о.. .оД, где /i($) = h(ai). Для каждого г, г Є [l,t], такого, что s 0, в равенстве (1.2) в функции р на места всех переменных, за исключением переменных компоненты DpEiJ, подставляются элементы набора N(i), поэтому выполнено равенство завершающее доказательство леммы при М = М. Приведенные рассуждения легко переносятся на случай, когда из матрицы М вычеркнуты некоторые строки. Пусть (p{yi,-..,yt) - булева функция, существенно зависящая от всех своих переменных и пусть D = (У[,..., Yd) - некоторое разбиение множества переменных р. Набор множеств функций G = {G\,..., () от переменных х\,..., хт называется универсальным порядка т для tp и D или, иначе, (ср, D)-универсальным порядка т, если для любой функции д{х\,... ,хт) в множестве G\U...UGd найдутся функции gi,... ,gt, такие, что д может быть представлена в виде и при этом функции из множества Gi подставляются только на места переменных множества Yi,i = 1:... ,d. Множество функций, являющееся объединением компонент ((р, 1))-универсального набора, будем называть -универсальным мноэюеством.
Таким образом, введённое определение совпадает с понятием ( -универсального множества функций из работы [16]. Лемма 1.4. Пусть D = (УЇ,... ,Ya) - селекторное разбиение множества переменных булевой функции р(уі,... ,yt). Для любого натурального т и набора неотрицательных четных чисел s = (si,..., Sd), удовлетворяющих d условию J2 \Yk\sk 2т, существует набор множеств функций G = (Gi,..., Gd), являющийся ( /?, D)-универсальным порядка т, такой, что для к = 1,..., d Доказательство. Пусть М - каноническая для функции р, разбиения D и спектра s матрица. Из условий леммы вытекает, что h(M) 2т. Положим М =_М([1,2т]) и пусть yj1} . ,yjd - некоторые элементы множеств Yi,... ,Yd соответственно. Положим Gk набор различных булевых функций от переменных жі,..., хт, столбцы значений которых лежат в множестве С(М к ), где Af(Jfc) - С-подматрица матрицы М, соответствующая переменной /jfc, к = 1,..., d. Из леммы 1.3 и из свойств канонической матрицы М вытекает, что набор G — (G\,..., Gd) является искомым. D Следствие. Пусть в условиях леммы D - тривиальное разбиение, а N -селективная матрица разбиения D. Положим и пусть ht-i 2m. Тогда ((p, D)-универсальный набор G дополнительно обладает следующими свойствами: 3. Для любой функции д{х\,..., хт) для к = 1,..., t в множестве Gk найдётся единственная функция, которая будет подставляться на место переменной у к в равенстве (1.3). 4- ДЛЯ к = l,...,t функции из мнооїсества Gk принимают для і = 1,..., (к — 1), (к + 1),..., (t — 1) значение ІУ[г, Щ на наборах куба Вт с номерами из отрезка [/іг-_і,тіп(/іг-, 2т)). Доказательство. Для доказательства достаточно повторить построения лем мы 1.4 для матрицы М, являющейся канонической для функции р, разбиения D, спектра s и селективной матрицы N. Пусть D = (Yi,...,Yd) - разбиение множества Y, a Z - подмножество Y и пусть i\,...,ik - номера компонент разбиения D, имеющих непустое пересечение с Z. Тогда будем говорить, что разбиение & = (ZnYil,...,ZnYik) порождается разбиением D на множестве Z. Сформулируем утверждение о существовании универсального набора множеств функций, аналогичное утверждению из [11, 4]. Лемма 1.5. Пусть D - селекторное разбиение множества переменных Y функции р, a D = (У1;... ,1 -) - некоторое разбиение множества Y на к компонент и пусть разбиение D\ порождается разбиением D на множестве Yf, і = 1,... ,к. Тогда для любых натуральных S\,...,Sk и т, таких, что si log Щ\, і — 1,..., к, и k 2m YJ\Yi\{si-H{Di)), (1.4) г=1 существует ((р, D )-универсальный порядка т набор множеств G — (G\,..., Gk), такой, что для каждого і = 1,..., к выполнено: 1. \d\ 2S +2; 2. число различных функций вида д,(х\,..., хт-\, а), где д Є G{ и а Є В, не больше, чем dj2s,/2+1; где d{ = l(Di).
Синтез ориентированных контактных схем на основе регулярных разбиений единичного куба и универсальных множеств функций
Для і = 1,..., 29-711 положим О.І - набор куба Bq с номером (г — 1) и пусть Si = S ф &І. Легко видеть, что для г = 1,..., 2q m множество Si является га-регулярным. Докажем, что набор множеств A = (Si,... , S2?-) образу ет разбиение куба Bq. Пусть 7 Є Bq и пусть (3 - единственный набор из множества S такой, что /5[1,га] = 7[[l m]l- Положим a = J3 Ф 7 и пусть г = М{а) + 1. Отметим, что М{а) 2q m и J3 Ф а = 7 откуда вытекает, что набор 7 принадлежит множеству Sj. Из того, что произвольный набор куба Bq содержится только в одном из множеств набора Л, следует, что А является разбиением куба Bq. D Разбиение куба Bq, построенное по лемме 2.7, будем называть регулярным разбиением. Пусть д, п - натуральные, q п.
Обозначим X — \Х\, . . . , Хп), X = \Х\, . . . , Xq), X = {Xq+l, . . . , Хц) и введем для булевой функции f(x) и параметра q следующее основное представление. /()= \/ "( ")-/( V)- (2.8) Следующая лемма описывает метод синтеза, основанный на регулярных разбиениях единичного куба и универсальных множествах функций, причём часть функций универсального множества «моделируются» переменными на компонентах подходящего регулярного разбиения. Лемма 2.8. Пусть т,п,Х uv - натуральные, где т п,Х 2и1 р \, а (р(щ,..., uPl, 2/1,..., уР2) - булева функция, в которой переменные множества U = {щ,...,иРх} (соответственно Y = {уі,..., уР2}) - прямые (соответственно итеративные) переменные. Пусть, далее, Т - разделительная по выходам (1,р2)-0КС из класса и(х )-кс от переменных щ,... ,иР1, такая, что ip(uii...,uPl,yi,...,yP2) = \J fi(ui,...,uPl)yi, г=1 где fi - функция проводимости от входа Т к выходу с номером і, і — 1,..., Р2 Пусть G = ((?!, () - набор множеств функций, являющийся универсаль ным порядка т для р и разбиения (U, Y), такой, что q = m+Cri п, а схе ма EG2 из класса реализует столбец, состоящий из всех функций системы G i. Тогда для любой булевой функции f(xi,... ,хп) существует схема Е/, реализующая f и принадлежащая классу и(х и)-кс) такая, что L(Zf) 2n mL(T) + L(EG2) + 0(2q + 2п-т), А&(Е,) 2«-т + М+(Г)2""т + M+(EG2) + G2, WwW,{Zf) 2n-mN + WW { G2) + w"\G2\ + Q(2q + 2"-ro), где N - суммарный вес вершин схемы Т, отличных от выходов. Доказательство.
Будем считать, что функции из множеств G\ и G2 зависят от переменных х\,..., хт. Пусть G\ - набор, состоящий из всех функций G\\ G\ = ((ft,. -. ,9q-m). Применим лемму 2.7 к набору G\ и получим разбиение A = (Si,..., S24-) наборов куба Bq(xm+\,..., xq, хт,..., х\). Перейдём от разложения вида (2.8) для функции f{x\,..., хп) и параметра q п к следующему представлению: № = V XiW V К »@ ) &Фъ ---. ), (2-9) г=1 а"еВп-ч где Xi{% ) характеристическая функция множества Si, а функция f(x ,д") совпадает с fa",i(xi, .., хт) на наборах Si, г = 1,..., 2q m. Возьмём схему EQq(a; bo,..., Ь2ч-\; xm+i,..., xq, хт,..., xi) (см. рис. 1.2) и для каждого г, і = 1,..., 2q m, отождествим те ее выходные вершины, номера которых совпадают с номерами наборов из Si. Полученную (1,2?_т)-ОКС обозначим EQ. Заметим, что ОКС Е 0 реализует набор характеристических функций (xi,... ,X29-m) разбиения А . Пусть Е0 - объединение 2q m непересекающихся (l,2"_9)-OKC EQ (xq+i,... ,хп). Обозначим результат стыковки Ео(Е0) через Ео. Пометим выходы ОКС EQ так, чтобы в выходе 6 , а" — (o-q+i,..., crn) Є Bn q, осуществлялась реализация функции Xi\x ) Xq+1 Хп Отметим, что схема Ео содержит 2q m вершин с полустепенью захода больше 1. Легко видеть, что выполнены неравенства: W№ »(E0) w 2q + w 2n-m + w"2q-m, L(E0) = O(29 + 2n-m). Так как набор [G\, G2) является универсальным для функции ip и разби
Верхние оценки сложности ориентированных контактных схем с ограниченной полустепенью исхода
Пусть ірі, г = 0,1,2 - булевы функции. Сформулируем лемму, которая обобщает соответствующее утверждение [13, гл. 2, 6] на случай реализации функции (рі в виде ( -надстройки над некоторым подмножеством входов ФУНКЦИИ /?2 Лемма 3.4. Пусть булевы функции tpo(xi,..., xq Q, у\,..., yq ) и {щ, , Щ 2, z\,..., zq») существенно зависят от своих переменных, a D 2 и D 2 - разбиения множеств U = {щ,... ,uq } и Z = {z\,..., z } соответственно, такие, что разбиение Di — D2 D2 является селекторным разбиением пере менных функции (f2- Пусть, далее, функция tpi реализуется сро-надстройкой над множеством входов Z функции ц 2- Для любых натуральных s , s", т\ и четных 5, t\, t2, таких, что % и матрицы N Є Btl,mi существуют матрицы W\, W", W2, W", W2, P, такие, что h(P) = t2, Щ Є Bu q , і = 1,2, где W[ Є Bfl 2; W( j Є В1иШ при і = 1,2 и j = 1,... ,mi, а также выполнены следующие свойства: 1. Справедливо равенство -p\(W\) = N, матрица W[ не зависит от матрицы N и имеет d = 1{D 2) различных столбцов. 2. Положим J\ (J2) - множество всех чисел из отрезка [1, qoq2], сравнимых с 1,..., q Q (соответственно с (q Q + 1),. - , qo) по модулю до- Для і = 1,2, j = 1,..., mi имеет место равенство W/jJi]] = W", причем матрица W" не зависит от матрицы N и имеет q 0d", где d" = 1{D2), различных столбцов. 3. Число различных столбцов в матрице, являющейся конкатенацией для j = 1,... ,гп\ матриц И Д ] о И Д/гЦ; не превосходит 2s +4. 4- Матрица Р не зависит от матрицы N и является S-подматрицей некоторой канонической для функции р2 и разбиения Z матрицы. Длина С -подматрицы матрицы Р, соответствующей переменным множества U не превосходит 2s +2, а матрица tpo(W2) содержит все столбцы С-подматрицы матрицы Р, соответствующей переменным множества Z. 5. Для сг = 0,1; і — 1,2 выполнено неравенство Прежде чем переходить к доказательству леммы 3.4 прокомментируем её формулировку.
В лемме 3.4, по сути, утверждается, что если М\ и MI - некоторые -подматрицы матриц, являющихся каноническими для функций ц \ и 2 соответственно, то существует матрица М = W" о Wl[ такая, что матрица W{ в совокупности с некоторыми дополнительными столбцами образуют матрицу Mi (см. свойство 1 леммы 3.4), а матрица (poiW ) в совокупности с некоторыми дополнительными столбцами образуют матрицу Мч (см. свойство 4 леммы 3.4) и при этом выполняется «естественное» ограничение на число различных столбцов матрицы М (см. свойство 3 леммы 3.4). С содержательной точки зрения это означает следующее: если на входы функции /?i подавать столбцы матрицы М, а матрицу N «реализовывать» с помощью функции (рі на первой половине строк матрицы М, соответствующих подматрице W", то столбцы матрицы М2 могут быть при этом «считаны» на второй ПОЛОВИНе СТрОК, СООТВеТСТВуЮЩИХ ПОДМатрИЦе ]%, С ВЫХОДОВ фуНКЦИЙ ifo, входящих в формулу для функции (р\. Также отметим, что необходимость построения дополнительных матриц в формулировке леммы 3.4 обусловлена, фактически, наличием у функций (pi, і — 0,1,2, как итеративных, так и прямых переменных (последние будут использоваться для «моделирования» части столбцов матриц М\ и М2 на компонентах подходящего разбиения единичного куба). Доказательство леммы 3.4- Доказательство леммы проведём следующим образом. Сначала определим структуру некоторых канонических для функций рі и /?2 матриц. Затем введём наборы полислов, связанных с построенными матрицами, и опишем выборки из наборов полислов. Наконец, установим справедливость пунктов 1-5 утверждения леммы на основании свойств построенных выборок. Для удобства введём дополнительные обозначения. Положим qj = q j + q", где j = 0, 2, и gi = q 2 + 7о(?2 Из условий леммы следует, что функция щ зависит от qi переменных, г — 0,1, 2.
Пусть Щ - разбиение отрезка [1, 1 длины d", такое, что -Ё р]] состоит из номеров переменных множества Z, попавших в компоненту .D I&J, где к = 1,... ,d". Не ограничивая общности рассуждений будем считать, что разбиение D% является гиперотрезком. Обозначим пк = .Оад, к = 1,...,d". Пусть {ffcifc Є [1, d"],j Є [1,пк]} -система взаимнооднозначных отображений переменных функции (ро в различные непересекающиеся между собой и с U U Z множества переменных. Будем считать, что функция ір\ является результатом суперпозиции функций ф2 и ср0, при которой функции tpo(k,i{x, у)),..., ipo(k,nk(x, у)), где х = (хг,...,хд 0), у = (уі,...,% ). подставляется на места переменных компоненты Х И, к = 1,... ,d". Для к = 1,..., d" положим
Синтез итеративных контактных схем
Доказательство. Присоединим к входу и выходу схемы Е контакт х+1 и обозначим результат через Ео- Пусть v Є М А(Е0) и пусть {ei,..., е } - множество всех контактов, инцидентных v. Положим h = \d/{\ — 2)], объединим 103 схему Ео и схему С/і-і,о-(а; Ьь ..., bh-i\ Хп+і, , Хп+і), после чего отождествим полюс а и вершину v и для і = 1,... ,(h—1) перенесем контакты ej, где (t-l)(A-2) j t(A-2), с вершины v на вершину 6 . Проделаем указанную операцию для каждой вершины v из множества М Л(Ео), используя при этом каждый раз новую схему вида Ct-i,a, где t = \degs (v)/(X — 2)]. Обозначим результат через . Легко видеть, что схема реализует функцию / . При этом L(S KL(0)+ Е ( veM x{Z0) degs» А-2 - 1 U L(E) A-2 E degs( )+4 "ЄМ А(Е) Лемма доказана. П Отметим, что техника построения схем, не содержащих вершины степени больше заданной константы А, описанная в лемме 4.2, фактически, приводится в работе [7] при построении асимптотически оптимальной контактной схемы, степени вершин которой ограничены А. Для доказательства верхней оценки функции Шеннона L KC(n) введём специальные булевы функции, а также построим для них универсальные наборы функций, обладающие необходимыми свойствами. «2(А-2) и\-1 U\- ад-2 W\ a\-i Ор -А+З Рис. 4.3: Схема SPt\-2 Пусть р - натуральное, р = р(Х — 2). Рассмотрим (1,р )-КС SP)\-2 (см. рис. 4.3) от переменных и = (щ,..., Up ), w = (u i,..., wp-i), с входными по люсами ai,..., dpi и выходным полюсом ао. Обозначим через /і,.. , /р функции проводимости от входов ai,..., ар/ соответственно к выходу ао-
Положим у — (уі, .. ,Ур ) - набор булевых переменных. Определим функцию -pVj\-2 следующим образом: Р ipP,\-2(y,u,w) = \J fi(u,w)yi. г=1 Будем говорить, что набор натуральных чисел / = (i\, . . . ,гр) удовлетворяет условию ( ), если для к — 1,... ,р выполнено (fc-l)(A-2) гк fc(A —2). Далее для набора булевых переменных z = (z\,..., zp) и набора / = («і,..., ip), удовлетворяющего условию ( ), обозначим через LpPjx-2,i{y,u,w, z) функцию, которая получается из функции (pPj\-2(y,u,w) в результате замены переменной yh на yikzk, к = 1,... ,р. Пусть I— (ii,..., ip) - набор, удовлетворяющий условию ( ) и пусть Введем следующие множества переменных функции (pP;x-2,i(y,u,w,z): У = {Уі,---,Уї}, U = {щ,...,ир }, W = {wi,...,wp-i}, Z = {zi,...,Zp}. Рассмотрим матрицу MPJ\ 2,I, которая имеет структуру, приведенную на рис. 4.4. Строки и столбцы матрицы МР;л-2,/ соответствуют переменным наборов у, й, w, z так, как это показано на рис. 4.4. При этом используются следующие обозначения: Матрица Aft - это (s, )-матрица, все элементы которой равны а, где а Є В. Матрица Еп это (?г, п)-матрица, на главной диагонали которой стоят 1, а вне главной диагонали - 0. w. У\ У? щ Up! W\ p-1 z\ Уі,. ..,Ур Ui,...,Up Wi,...,Wp-i Zi,...,Zp -Ёу ми А{1) ЛХ) л(0) Р У ми Лі) р ,р д(1) p-l.p М М " 4(1) д(1)лр,р мІгР М { Ло) р,р Рис. 4.4: К определению матрицы Мр -2,і Матрица M l - это (p к, p — 1)-матрица, в которой и для г = 1,..., (р— 1) матрица М 1(((і — 1)к, і к]) содержит 0 в столбцах с номерами из отрезка [г, р— 1] и содержит 1 во всех остальных столбцах. Матрица М" = М{ ([1,р - 1]).. Пусть R — (гь ... ,rt) - набор натуральных чисел, не превосходящих п. Матрица Мд)П - это (t, п)-матрица, в которой в k-Vs. строке стоит 1 в столбце с номером 7 и стоят нули во всех остальных столбцах, где к = 1,...,1 Матрица М = М//)Р», где набор / имеет вид I — (к\,..., кр-\) и состоит из чисел ki = i(X -2) + 1, і = 1,..., (p-1). Лемма 4.3.
Матрица MPi\-2,i является селективной матрицей тривиального разбиения ПеремеННЫХ функции /?p,A-2,J Доказательство. Для доказательства леммы введём дополнительные обозначения. Пусть X - некоторое множество переменных функции f(x\,..., хп). Будем обозначать через Х\а, а Є В, подстановку константы т в функцию / вместо всех переменных множества X. Для набора различных булевых переменных х = (xi,...:xt) и набора констант а = {о \,...,at) Є В1 будем обозначать через х\& подстановку в функцию / констант набора а по правилу х1 = ri,...,xt = at Рассмотрим каждое из подмножеств переменных Y, U: W, Z функции pp,\-2,i 1. Пусть і є [1,р 1- Выполним подстановку (Y\{yi})\o} Z\\. В этом случае функция pPi\-2,i совпадет с Уіщиіі - Wk, где к = [ъ/(Х — 2)J. Легко видеть, что при подстановке U\E , , й)\м"_ (І) функция р,\-2,1 совпадет с УІ 2. Пусть г Є [1,р \- Выполним подстановку Уі, Z\i и ([/\{иг-})0. В этом случае функция р.А-г,/ совпадет с U{Wi---Wk, где к = [г/(Х — 2)J, поэтому после подстановки W\M"_ (І) функция /?Р)л-2,/ совпадет с щ. 3. Пусть і Є [1,р— 1]. Выполним подстановку Y\\, Z\\. Заметим, в случае подстановки й\м (і) функция (pPj\-2,i совпадет с иі\ Wi, откуда вытекает, что набор М(2р +ъ) является селективным набором переменной wi. 4. Пусть і Є [1,р]. Выполним подстановку Уі, (Z\{zi})\o. Легко видеть, что при подстановке U\MJ ,{І) функция pPt\-2,i совпадет с Z{W\.. .Wi-i, поэтому набор М(2р +р — 1 + г) является селективным набором переменной Zi. Из пунктов 1-4 вытекает утверждение леммы. Замечание. В матрице МРі\-2,і от набора I зависит только матрица М[ = MPt\_2,il(p , р + "]]] Для произвольного I матрицу Mi можно составить из столбцов матриц М \ MW, где MW([1,2р +р- 1]) = М()([1,2р + р- 1]) = Ер/ о А% о М , МЮ([2р + р-1,2р + 2р-1]) = Ар% а і -я строка матрицы М {[2р -\-р—1,2р +2р—1]) содерэюит 1 в столбцах с номерами из отрезка ((і — 1)(Л — 2),г(А — 2)] и содержит 0 в остальных столбцах, і — 1,... ,р. Лемма 4.4. Для любых натуральных р, т, s, s , s", таких, что s, s , s" -четные, а для p = p{\ — 2), p" = (p + p — 1), выполнены неравенства ps +p s +p"s" 2m, p s 2m, существует набор (/-її / il silf fill /4 / i \ p,X-2 — i i, , bp , Lr , Lr , Lri, ..., Lrp) множеств функций от m переменных со следующими свойствами: 1. Выполнены соотношения: \С{\ = 2s , і — 1,... ,р , \G" U G"\ p"2s"+l, \6г\=28,і = 1,...,р. 2. Пусть I - произвольный набор длины р, удовлетворяющий условию ( ). Для любой булевой функции f(x\,..., хт) найдутся функции g[,..., g ,, где g\ є G\ при і = 1,..., р , функции g {,..., g из G", функции g {,..., g из G", функции gi,..., gp, где c/j Є Gi при j — 1,... ,p, такие, что f = pp,\-2,i{g[,..., g p , g",..., #,g i,...,$[_i, gi, , gP), (4.2) причем функции g[,..., g pl не зависят от функции (pp,\ 2,i и определяются однозначно по функции f, а д"х д"2 = 0 при 1 j i 32 р Доказательство. Пусть I = (ii, . . . ,ър) - произвольный набор, удовлетворяющий условию ( ), D - тривиальное разбиение переменных функции /?PIA-2,J и пусть MPi\-2,i - селективная матрица разбиения D, построенная по лемме 4.3. Применим следствие леммы 1.4 к функции pPtx-2,i, разбиению D, селективной матрице MPIA_2,J и числам Si = = Sp = S , Sp -fl = = Sp +pi = S , Sp +p»+i = = Spij-p"+p = S, и обозначим полученный по этой лемме ( р,л-2,.г, ))-универсальный набор через
