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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Математическое моделирование. Оптимальное управление Вестник Нижегородского университета им. Н. И. Лобачевского, 2012, № 4 (1), с. 225−231
УДК 519. 714
О СЛОЖНОСТИ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ ИЗ ИНВАРИАНТНЫХ КЛАССОВ КЛЕТОЧНЫМИ СХЕМАМИ ОГРАНИЧЕННОЙ ВЫСОТЫ С КРАТНЫМИ ВХОДАМИ
© 2012 г. А.Ю. Яблонская
Московский госуниверситет им. М.В. Ломоносова
уаЫошкауа. alexandra@gmail. сот
Поступила в редакцию 17. 04. 2012
Рассматривается модель клеточных схем ограниченной высоты с кратными входами и устанавливается асимптотическое поведение функции Шеннона для площади клеточных схем, реализующих функции из ненулевых инвариантных классов.
Ключеввк слова: клеточные схемы, ограниченная высота, кратные входы, инвариантный класс, асимптотика, функция Шеннона.
Введение
В данной статье исследуется одна из математических моделей интегральных схем — модель клеточных схем (КС), построенных из коммутационных и функциональных элементов. Считаем, что элементы КС расположены на плоскости, входами схемы помечены входы элементов на границе схемы, и, как правило, каждый вход встречается в схеме не более одного раза. Критерием сложности схемы является занимаемая ею площадь. Эта модель дает хорошее приближение к реальным интегральным схемам с точки зрения их геометрии, способов трассировки (соединения функциональных элементов схемы между собой) и т. д.
Впервые модель КС была предложена Кравцовым С. С. в [1]. В его работе был установлен порядок функции Шеннона, характеризующей сложность (площадь) реализации самой сложной функции алгебры логики (ФАЛ) от п булевых переменных (БП) в модели КС при п, стремящемся к бесконечности. Позже, в работе [2], было доказано существование асимптотики вида 02п для данной функции Шеннона, а в [3] приведен пример одного базиса КС, в котором удалось указать асимптотику функции Шеннона в явном виде. Для произвольного же базиса КС явный вид асимптотики до сих пор не найден. В данной работе для функции Шеннона, характеризующей площадь КС ограниченной высоты в стандартном базисе с кратными входами, расположенными только на одной из сторон схемы, которые реализуют функции из ненулевого инвариантного класса, установлена асимптоти-2п
ка вида С ----, где константа С зависит от ин-
^ п
вариантного класса (см. также [4]).
Описание модели и определения 1
Схема из клеточных элементов (см. [1, 2]) представляет собой плоскую прямоугольную решетку, в каждой клетке которой расположен один из элементов схемы. Размеры всех элементов одинаковы и принимаются за 1. Элементы могут быть как функциональными, то есть реализующими некоторую ФАЛ от своих входов, так и коммутационными, служащими для передачи сигнала к соседнему элементу с возможным изменением направления.
В данной работе рассматриваются плоские прямоугольные схемы над базисом Б0, состоящим из трех коммутационных элементов — разветвление, пересечение, изолятор — и из трех функциональных элементов, реализующих ФАЛ конъюнкция, дизъюнкция, отрицание. Базис Б0 является полным в классе КС в том смысле, что произвольную ФАЛ можно реализовать КС высоты 2 над этим базисом (см. [6]). Каждый из элементов базиса может быть повернут в плоскости на угол, кратный 90 градусам. В качестве входов и выходов схемы берутся входы и выходы элементов, расположенных на ее границе. Функциональные элементы соединяются между собой с помощью коммутационных элементов так, чтобы полученная схема представляла собой схему из функциональных элементов (СФЭ). Считаем, что КС реализует те же функции алгебры логики, что и соответствующая ей СФЭ.
Назовем К С односторонней схемой, если ее входные переменные могут подаваться только на одну границу схемы. Назовем К С схемой с кратными входами, если каждая ее входная переменная может подаваться в схему многократно. Исследуем односторонние КС с кратными
XV у у
Рис. 1. Базис Б0, над которым строится КС
входами (ОКСКВ) фиксированной высоты. Дадим практическое обоснование этой модели. Пусть имеется n параллельных проводников, по которым передаются значения БП xi,…, xn. Ниже, под этими проводниками, располагается КС, на верхнюю границу которой могут подаваться БП, идущие выше. Выход К С находится в правом нижнем углу схемы. Интерес к такого рода схемам обусловлен, прежде всего, тем фактом, что в реальных схемах функциональная часть, как правило, разбивается на блоки, соединенные между собой несколькими линиями передачи данных, и коммутация функциональных блоков может занимать достаточно большую часть схемы. Рассматриваемые схемы дают возможность проводить попутные, вспомогательные вычисления по ходу передачи сигналов, занимая лишь небольшую дополнительную часть площади всей схемы. В реальных схемах ОКСКВ могут встретиться в случае, когда по некоторой шине передается несколько сигналов, и в процессе передачи требуется проверить целостность передаваемых сигналов. Вполне очевидным требованием является наложение ограничения на высоту ОКСКВ.
Определим функцию Шеннона для площади ОКСКВ. Обозначим высоту схемы 2 через h (2), ее длину — я. (4 а площадь A (z) = h (l)^(l) и будем считать, что h (E)& lt- Х (Е). Пусть Р2 -множество всех ФАЛ от БП из счетного алфавита X = {x1,x2.}. Для некоторого класса функций Q, Q с Р2, обозначим за Q (n) множество функций из Q, зависящих от n переменных x1,., xn. Напомним, что для любой ФАЛ f е Р2 существует схема 2f высоты h (2 f)= 2, реализующая эту функцию f [6], а значит, для любого h & gt- 2 определена функция Ah (f), равная наименьшей из площадей A (2) где минимум берется по всем КС 2 высоты h, реализующим f Функция Шеннона Ah (Q (n)) для площади ОКСКВ высоты h в классе ФАЛ Q равна максимальной из площадей Ah (f), где максимум берется по всем ФАЛ f из Q (n):
Ah (Q (n))= mx Ah f (1)
f eQ (n)
Тиунчик А. А. в работе [6] доказал, что в таком же базисе коммутационных элементов и
произвольном полном базисе функциональных элементов соответствующая функция Шеннона для реализации ФАЛ от п БП имеет порядок
роста
2 2п
log n'-
Напомним (см. [7]), что класс Q, Q с Р2, называется инвариантным классом тогда и только тогда, когда Q замкнут относительно операций добавления и изъятия фиктивных переменных, переименования (без отождествления) переменных и подстановки констант вместо переменных. Определим для Q, Q с Р2, мощностную последовательность
log I Q (n)|
Or, п
(n) = -
2n
Если существует предел lim оQ (n) = оQ, то
Q Q
величина Oq называется мощностной характеристикой класса Q. Известно (см. [7]), что если Q — инвариантный класс, то 3
оQ (n) М оQ, где оQ е [0,1], и
оQ (n)= оQ (l + e (n)), где e (n) М 0 при n ^ да. Инвариантный класс, характеристика которого больше нуля, называется ненулевым инвариантным классом.
Зафиксируем некоторое h & gt- 3 и базис Б0 клеточных элементов. В данной работе для функции Шеннона Ah (Q (n)), определенной равенством (1), в любом ненулевом инвариантном
h2n
классе Q получена асимптотика вида оQ --------.
Q log n
Нижняя оценка
Лемма 1 (Нижняя оценка). При h & gt- 2 для ненулевого инвариантного класса Q справедлива
4
следующая асимптотическая нижняя оценка для функции Шеннона Ah (Q (n)):
h2n
Q 1---• (2)
log n
Доказательство. Подсчитаем число схем высоты h и длины X от n БП, которые можно построить в рассматриваемой модели, учитывая тот факт, что переменные подаются только на верхнюю границу схемы. Выберем те позиции на границе схемы, где будут располагаться вхо-
ды схемы, и те переменные, которые на них подаются. Заметим, что к каждому элементу схемы, расположенному на ее верхней границе, можно подвести одну из п переменных. Далее произвольно заполним всю схему клеточными элементами. Таким образом, с учетом возможных поворотов базисных элементов, имеем 21 вариант заполнения каждой клетки схемы и (п + + 1) х21йх вариантов построения всей схемы. Так как число различных схем должно быть меньше числа различных ФАЛ, которые они реализуют, то из определения функции Шеннона и полученной верхней оценки числа схем указанного типа вытекает следующее неравенство:
(п +1)^21^ = ((и +1)21*)Х & gt- 2Пе2″.
Решая это неравенство относительно X, получим
Тогда выполнено следующее равенство:
Х& gt--
аq2& quot-
ihi
а е 2 И
log (21h (n +1)) h log21 + log (n +1)
аq2n Г1 _ О^,
log n [ log n /
откуда следует, что
h2 ^ _ О (І)
AhQ (n))& gt- hi & gt-
Q
log n I log n
= 0.
Доказательство. Положим I (Т) = ^ е (/)2^Т ,
t=l
выберем параметр q = [Т/2] и разобьем сумму
д-1 Т
для 1(Т) на две части: 1(Т) = Х^('-)2'--Т + 5"^.
t=1 t=q
Функция е (?) монотонно не возрастает, а следовательно, е (?) & lt- е (1) при 1 & lt- I & lt- д — 1 и е (?) & lt- е (д) при t & gt- д. Тогда
I (Т)& lt- 2^Т.
t=1 t=q
Подсчитаем сумму геометрических прогрессий в последнем неравенстве:
тд о тТ+1 тд тд
1(Т)& lt- 6(1) 22−2 + ф) I--2- & lt- в (1) 2, + 2″) =
n2Lr/2J Г
= є(і) ~2т~ + 2є
, 2 + 2Є Г _ 1
Тем самым лемма 1 доказана.
Верхняя оценка
Получим асимптотическую верхнюю оценку вида (2) для функции Шеннона Ан^(п)). Для этого возьмем произвольную ФАЛ f из ненулевого инвариантного класса Q и построим для нее ОКСКВ, площадь которой асимптотически не больше, чем правая часть (2). Положим в основу доказательства разложение из работы [8].
Напомним некоторые определения из [8]. Множество наборов (а1,а2,^, ай), (а1,а2,^, ай), …, (а1,а2,^, ай) называется сферой с центром (а1,а2,^, а^). Как обычно, характеристической функцией множества наборов называется функция, равная единице только на наборах, принадлежащих этому множеству. Заметим, что характеристическая функция (х17г2,--Л) сферы с центром (а1,а2,., а^) может быть задана формулой
(Xl,…, хЛ)=ух… х"-, 1 х ух «++1… ха/. (3)
]=1
Докажем для начала три вспомогательные леммы.
Лемма 2. Пусть Q — инвариантный класс, ^(и) — мощностная последовательность класса Q, а OQ — его мощностная характеристика, причем ^(и) = OQ (1 + е (п)), где е (п) 1 0 при п ^ да.
Правая часть неравенства стремится к нулю при T ^ да, а значит, lim l (t) = 0. Лемма 2 дока-
T
зана.
Лемма 3. Пусть fxb…, xc) — произвольная функция из инвариантного класса Q и пусть 5 & lt- 2е. Тогда существует разбиение множества наборов единичного куба Bc на подмножества Ab…, AN,
Г 2е 1
где N = -, AI = AN-1| = 5, AN = 5 & lt- 5, такое,
5
что столбец функции f на подмножестве Ai, 1 & lt- i & lt- & lt- N — 1, может принимать не более чем
/^Oq5(1+?(5)) v.» / Г
2 Q значении, где е (5) ^ 0 при 5 ^ да.
Доказательство. Построим разбиение куба Bc, удовлетворяющее условию леммы. Пусть (t1,…, tk) — разложение числа 5 по степеням двоики, то есть
5 = 2tl +… + 2tk, где t1 & gt-… & gt- tk. Выделим из упорядоченного в лексическом порядке множества наборов куба Bc последовательные отрезки Aj длины (мощности) 2tj, где
для каждого i = 1,…, k j пробегает значения 1,. ,(N-1), а оставшиеся 5'- наборов объединим в отрезок An.
На каждом отрезке A/ длины 2tj значения первых n — tj переменных зафиксированы. Таким образом, на отрезке A/ столбец значении функции f (x1,., xc) совпадает со столбцом значении некоторои функции из инвариантного класса Q (tj), и поэтому число таких столбцов не
больше, чем 2"е (tj)2.
Определим подмножества А1,…, AN-1 множества наборов куба Bc, сгруппировав некоторые
отрезки А/, следующим образом:
k ~
At _ U, А, 1 & lt- i & lt- N -1.
j=i
Подмножества А1,…, AN образуют, очевидно, разбиение множества наборов куба Bc.
Из сказанного выше следует, что число различных столбцов значений функции J{x1,., xc) на подмножестве Ai не превышает величины
L (s) (t1)2 12 (tk)2 k
Воспользовавшись равенством из условия леммы, определяющим характеристику oq инвариантного класса Q, получим
log L (s) _ CTq (l + s (ii))2'-1 + CTq (l + s (i 2))2'-2 +… +
+ Qq (l + s (ik))2k _ CTq (s + s (ii)21 + s (i2)2 2 +… +
где
+ E (tt)2tk) = °q4 + ~(s))
~(s) s (ti)2t1, s (t2)2t2 +… + s (tk)2tk
B (t)2t
2t1 + 2t2… + 2tk
te (t1,-, tk}
te (ti,…, tk}
2tl + 2t2… + 2tk
& lt- ?в (г)2& lt-?е (?)2'-Л
/?{/,… ,} г=1
Так как г1 ^ да при 5 ^ да, то, согласно лемме 2, правая часть последнего неравенства и, следовательно, є (5), стремятся к нулю при 5 ^ да. Таким образом, для величины ?(5) получим
т (^ Ъ °о5(1+в (5))
следующую оценку: ?(5)& lt- 2 2, где
є(5) ^ 0 при 5 ^ да. Лемма 3 доказана.
Замечание. Число различных столбцов значений функции У (х1,_, хс) на подмножестве Ам
25'-
.
Лемма 4. Дизъюнкцию Fv вида Ц1 v^. vua^k можно реализовать ОКСКВ высоты один и длины не больше, чем (к+1).
Доказательство. Упорядочим переменные в дизъюнкции Fv таким образом, чтобы первыми подавались переменные с отрицанием, если они есть:
К = V" v ••• v v Уи+1 v … v Ук =
= V, & amp-. & amp- V V V, V … V V,.
1 т т+1 k
Схема, реализующая дизъюнкцию FV указанной формулой, изображена на рисунке 2. Лемма 4 доказана.
Рис. 2. Реализация дизъюнкции схемой высоты 1
Следствие. Конъюнкцию F& amp- вида
Uj"1 & amp-… & amp-ul" можно реализовать ОКСКВ высоты один и длины не больше, чем («+1).
Лемма 5 (Верхняя оценка). При h & gt- 3 в базисе Б0 для ненулевого инвариантного класса Q справедлива следующая верхняя оценка функции Шеннона Ah (Q (n)):
Ah (Q (4 & lt- Oq
h2n log n
Доказательство. Пусть / (х1,., хп) е Q. Построим для f ОКСКВ Е. высоты к & gt- 3, длина
которой асимптотически не больше ------------. Для
log n
этого модифицируем разложение ФАЛ f построенное в работе [8], и построим его вложение в ОКСКВ высоты h & gt- 3.
Разобьем набор переменных (xb…, xn) на четыре набора (xb…, xa), (xa+b…, xa+fe),
(xa+b+b* •-r^a+b+cX (xa+b+c+1,., xa+b+c+d) и обозначим их через р, р, р, и соответственно, где a +
+ b + c + d = n и d = 2d — степень двойки. Все
r d
наборы длины d разобьем на -- попарно не
d
пересекающихся сфер ([8], лемма 3) с характе-
2 d
ристическими функциями ф, (р), 1 & lt- i & lt- -.
i d
Пусть (р& gt- ~) _ Фі (р)f (р Р, р & gt- р). Тогда
f (р, ~, р, ~) _ V к ~ (р)к ~ (р)f (р, ~),
/, о, р
где, как и в дальнейшем, дизъюнкция берется по всем 1 & lt- i & lt- d, 0 Є Ba, р Є Bb. Функция f. gp (р, и) принимает значения, отличные от нуля, лишь на
наборах вида (q a+b+1, • • •, Qa+b+c, а (,), -, j ,
aj+1,…, а^), где (а (,),…, а^) — центр i-й сферы,
1 & lt- j & lt- d, и поэтому может быть задана матрицей M с 2c строками и d столбцами. Строки M соответствуют наборам значений (oa+b+1,., oa+b+c), а столбцы — наборам i-й сферы. Столбец матрицы M с номером j представляет собой столбец значений функции
W «(0 TiW «М «М
о, р, ха+,+1… X+b+c, a1 _, a'-, aj, aj+1
из инвариантного класса Q©.
,., a d))
2
Возьмем некоторый параметр 5 & lt- 2е и разобьем множество строк матрицы М, то есть куб Вс, согласно лемме 3, на подмножества А1,… АЛ, где = ••• = Ал-1 = 5, |Ал| = 5'- & lt- 5, такие, что число различных столбцов ~, которые могут встретиться в матрице М на подмножестве строк Ак (здесь, как и в дальнейшем, k пробегает
значения «,… ,(N-1)), не больше 2'
(З 5(1+є (5))
где
е (5)^ 0 при 5 ^ да, а на подмножестве строк
Ал — не больше 2 5.
Пусть функция /?ърк (~, и) принимает значения, отличные от нуля, только на подмножестве Ак и совпадает на Ак с (~, и), а функция /?5рк~ (~, и) принимает значения, отличные от нуля, только на группе В15~к~ столбцов, равных 5 (на подмножестве Ак), и совпадает на
В,
о, р, к, т
Ла, Р, к (р & gt-р) функция, р (р, р)
может быть представлена в виде
,~(р& gt-р)=ф, (р)/і(рг), р,і,~(р)А*, р, к,~(р).
где /?ъркр (р) — функция, в матрице которой все столбцы равны р на подмножестве Ак и состоят из нулей вне Ак, а /!~ркр (р) представляет собой дизъюнкцию |в, Эркр| переменных
из группы и или их отрицаний, которая равна единице только на наборах і-й сферы, соответствующих столбцам из В, 5 р к р.
Таким образом, функцию / можно представить формулой
/ (р, у, р, р) =
= V Кр (р)кр (р)Ф,(р)у (, р (р Щ*, р (р) =
ї, о, р, к, х
= V ф,(р)Кэ (р)у (, 2р)(р) VKр (р)Л (р)р, к, р (р)
і, р, к, х у р
Обозначив через Dрt (р) отрицание конъюнкции Кр (р), то есть дизъюнкцию вида Vе1 v_v, и заметив, что для произвольного р0
V К р (р0)fi'-Lk, р (р)=& amp-(^р (р0)v /!^), р, к, р (р)), р р
получим окончательную формулу для функции /.
у (р, р, р, р) =
= V ф, (р)Кр (рШ (р)& amp- (^р,(р) v Дкк, р (р)).
і, р, к, х р
Покажем, как можно вложить построенное разложение функции / (р, р, р, и) в КС? у высоты 3 над рассматриваемым базисом (см. рис. 1). Занумеруем ряды схемы сверху вниз и построим схему? у следующим образом. В первом и
втором рядах схемы расположим подсхемы Е, 5кТ, где параметры пробегают все стандартные значения, а в третьем ряду соберем дизъюнкцию этих подсхем.
Подсхема Е15к~ при фиксированных значениях, 5, к, ~ реализует формулу
Ф,(5)К5 (5Ш (5)& amp- (^' (~) V. /^ГР, к5 (5))
Р
и разбивается на четыре последовательно соединенные части, реализующие соответствующие сомножители указанной формулы. Функция ф,(5) реализуется по формуле (3) так, что в первом ряду генерируются конъюнкции от переменных ха+ъ+с+1,…, ха+ъ+с+а, преобразованные согласно следствию из леммы 4, а во втором ряду они собираются в общую дизъюнкцию. Конъюнкция К5 (р) реализуется так, что в первом ряду получаются необходимые отрицания входных переменных х1,., ха, а во втором ряду они собираются в общую конъюнкцию. Функция /к ~(р) реализуется по своей совершенной
конъюнктивной нормальной форме, где в первом ряду генерируются дизъюнкции от переменных ха+ъ+1,…, ха+ъ+с, преобразованные согласно лемме 4, а во втором ряду они собираются в общую конъюнкцию. И, наконец, функция & amp- ^ (р) V /'-?(д, р, к, р (Р)), преобразованная 5
согласно лемме 4, реализуется так, что в первом ряду получаются дизъюнкции для каждого значения р, а во втором ряду они собираются в общую конъюнкцию.
Схема Еу построена, а ее длина удовлетворяет следующим соотношениям (рис. 3):
, 5, к, р)& lt-
& lt- а (а +1) + 2е (с +1) + 2Ь (Ь +1)+2 В, & gt-. (Е ,) =
і, р, р, к, х
+ а,
рєВЬ
ІШ^лірЬ -?2аІ 2І^(^і, р, к, р)
і=1 аєВа к=1 х
а (N
а
V к=1 х [ N (
= - 2а а
і, а, р, к, х
221Я в.
у к=1 реВъ V ~
+ 22(а (а +1) + 2е (с +1) + 2ъ (ъ +1) + а).
к=1 5 у
Поскольку 2 |в, 5 р к 5 | = а при фиксирован-
5
ных ?, 5,5, к, то последнее равенство можно продолжить:
а
2
а
/{1(2]
___ІЛ. ________^ ________-V________

V V … & amp- & amp- & amp- & amp- & amp- & amp-

+ Ж *-» V-
Рис. 3. Построение схемы 2 f
i 2й
A,(s f)= - 2 a (N 2bd + 22 (d (d +1)
d t=i & gt-
+ 2c (c +1) + 2b (b +1) + a).
Так как число столбцов & gt- на подмножестве
Ak, 1 & lt- k & lt- N-1, не больше, чем 2nQs (1+s (s^,
где
е (^)1 0 при 5 ^ да, и не больше, чем 2s, на подмножестве строк AN, то
ф f) & lt- 2а (N 2b d + ((N -1)2
П"і(і+б (і))
+ 25 x
x (d (d +1) + 2c (c +1) + 2b (b +1) + а)) & lt-
(о c (
r d
& lt- -2а d
2c
-2bd + 5
2
-2 «e'- 5
П"і(і+б (і))
+ 25 Jx
ЛЛ
d (d +1) + 2c (c +1) + 2 (b +1) + а
/J
Положив
d = 2 Llog nJ-1, c = |_2log log n J b = [2 log-
= -1- [logn — 2log log)
Gn
получим оценку
ф f) & lt- -2а -2bd:
d s s Q log n
Лемма 5 доказана.
Теорема. При h & gt- 3 для ненулевого инвариантного класса Q справедлива оценка для функции Шеннона A (Q (n)):
A (Q (n)) ~aq.
log n
Утверждение теоремы непосредственно вытекает из леммы 1 и леммы 5.
Работа выполнена при поддержке ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009−2013 гг.
Примечания
1. Те понятия, которые не определены в данной работе, см., например, в [5].
2. Здесь и далее логарифм берется по основанию 2.
3. Запись a (n) ^ a обозначает тот факт, что последовательность a (n), монотонно не возрастая, стремится к пределу, а при n ^ да.
4. Неравенство a (n)& gt- b (n) означает, что существует последовательность s (n) ^ 0 при n ^ да, такая, что выполнено равенство a (n) = b (n)(1 + s (n)). Асимптотическое равенство a (n) ~ b (n) верно, если a (n) & gt- b (n) и b (n) & gt- a (n).
Список литературы
1. Кравцов С. С. О реализации функций алгебры логики в одном из классов схем из функциональных и коммутационных элементов // Проблемы кибернетики. М.: Наука, 1967. Вып. 19. С. 285−292.
2. Альбрехт А. О схемах из клеточных элементов // Проблемы кибернетики. М.: Наука, 1975. Вып. 33. С. 209−214.
3. Грибок С. В. Об одном базисе для схем из клеточных элементов // Вестник Московского Университета, сер. 15. Вычислительная математика и кибернетика. 1999. № 4. С. 36−39.
4. Улесова А. Ю. О сложности односторонних клеточных схем фиксированной высоты с кратными входами // Материалы XVI Международной конференции «Проблемы теоретической кибернетики». Н. Новгород: Издательство Нижегородского госуни-верситета, 2011.
5. Лупанов О. Б. Асимптотические оценки сложности управляющих систем // М.: Издательство МГУ, 1984.
6. Тиунчик А. А. О реализации функций алгебры логики клеточными схемами ограниченной ширины // Методы дискретного анализа в решении экстремальных задач. Новосибирск: Институт математики СО АН СССР, 1990. Вып. 50. С. 73−83.
7. Яблонский С. В. О невозможности элиминации перебора всех функций из Р2 при решении некоторых задач теории схем // ДАН СССР. 1959. Т. 124. № 1. С. 54−62.
8. Лупанов О. Б. О реализации функций алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе & amp-, v, — // Проблемы кибернетики. М.: Физматгиз, 1961. Вып. 6. С. 5−14.
х
ON IMPLEMENTATION COMPLEXITY OF THE BOOLEAN FUNCTIONS FROM INVARIANT CLASSES BY CELL CIRCUITS WITH LIMITED HEIGHT AND MULTIPLE INPUTS
A. Yu. Yablonskaya
A model of cell circuits with a limited height and multiple inputs is considered. An asymptotic behavior of the Shannon function is established for the area of cell circuits implementing functions from the nonzero invariant classes.
Keywords: cell circuits, limited height, multiple inputs, invariant class, asymptotics, Shannon function.

ПоказатьСвернуть
Заполнить форму текущей работой