close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
О ФУНКЦИОНАЛЬНОЙ РАЗДЕЛИМОСТИ БУЛЕВЫХ ФУНКЦИЙ,
ЗАДАВАЕМЫХ КВАДРАТИЧНЫМИ НЕРАВЕНСТВАМИ
Шурупов А. Н.
3. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
И АВТОМАТИЗИРОВАННЫЕ СИСТЕМЫ
3.1. О ФУНКЦИОНАЛЬНОЙ РАЗДЕЛИМОСТИ БУЛЕВЫХ ФУНКЦИЙ,
ЗАДАВАЕМЫХ КВАДРАТИЧНЫМИ НЕРАВЕНСТВАМИ
Шурупов Андрей Николаевич, к.т.н., доцент, доцент, МИРЭА (ТУ), ashurupov@mail.ru
Аннотация: Эта работа продолжает исследование функциональной структуры булевых функций, задаваемых
действительными линейными неравенствами. Однако, в отличие от [2], где объектом исследования являются
булевые пороговые функции, в настоящей работе рассматриваются булевые функции, определяемые одним
нелинейным неравенством второй степени. Многочлены второй степени среди всех нелинейных многочленов
обладают наименьшим размером задания, т.е. свойством, существенным в ряде прикладных задач.
Доказаны три критерия функциональной разделимости для булевых квадратичных пороговых функций.
Второй критерий не требует анализа табличного задания функции и формулируется в терминах пороговой
структуры.
Интерес к пороговым функциям в настоящее время обуславливается их применениями для решения задач распознавания образов, в искусственных нейронных сетях и других областях [3].
Ключевые слова: булевые функции, пороговые функции, декомпозиция, квадратичные неравенства
3.1. ON A DECOMPOSITION OF BOOLEAN FUNCTIONS REPRESENTED BY
QUADRATIC INEQUALITIES
Shurupov Andrey N., Ph.D., Associate Professor, Moscow State Institute of Radio-Engineering
Electronics and Automation (MSIRTEA) (TU), ashurupov@mail.ru
Abstract: This paper advances results on Boolean threshold function decomposition [2] to Boolean functions
represented by one quadratic inequalities. Quadratic polynoms are the most compact non-linear polynoms and this
property sometimes is quite important. We proved three criterions for non-trivial decomposition of quadratic Boolean threshold function. The second one can be applied without analysis of truth table and only needs some
evolvement of threshold structure.
Threshold functions provide a simple but fundamental model for many questions investigated in image recognition, artificial neural networks and many other areas [3].
Index terms: Boolean functions, threshold functions, decomposition, quadratic inequalities
Практическое быстродействие вычислительных алгоритмов тесно связано, с одной стороны, с эффективностью самого алгоритма, а, с другой стороны, с
реализацией этого алгоритма в вычислительной среде. Тематика псевдобулевых неравенств затрагивает
оба этих направления. Например, система нелинейных булевых уравнений может быть эффективно решена в случае существования компактного представления в виде системы линейных неравенств (см. [9,
10]). Перспективные вычислительные среды на элементной базе искусственных нейронных сетей также
требуют представления алгоритмов в виде систем
линейных неравенств [3]. В частности, для решения
последней задачи необходимо уметь реализовывать
булевые и, в общем случае, многозначные функции в
виде формул над классом линейных пороговых функций (т.е. булевых или многозначных функций, однозначно задаваемых одним линейным неравенством).
Смежные с указанной выше проблемой вопросы
функциональной разделимости для булевых пороговых функций рассмотрены в [2]. Прекрасный обзор и
ряд глубоких результатов по декомпозиции многозначных функций содержится в [1]. В этой работе исследуются функциональная разделимость булевых
функций из одного специфического класса − булевых
пороговых функций, задаваемых квадратичными неравенствами. Нахождение таких декомпозиций позволит уменьшить трудоемкость реализации булевых
функций указанного вида в любой вычислительной
среде, особенно, в нейрокомпьютерах.
Необходимо отметить, что общая задача проверки
функциональной разделимости произвольной булевой функции относится к классу NP. Результаты настоящей работы представляют интерес и для задачи эффективной проверки существования простых декомпозиций квадратичных пороговых булевых функций.
53
Computational nanotechnology
2-2014
Основные понятия
В дальнейшем нам потребуются следующие понятия и утверждения, часть которых хорошо известна и
может быть найдена в [1], [4], [5], [6]. Пусть
{
}
n
F2 ( n) = f : {0,1} → {0,1}
– множество всех булевых функций от
n переменных.
Определение 1. Пусть K – некоторый непустой класс
булевых функций. Если для функции f ∈ F2 ( n) существует представление
( (
)
f ( x1,K, xn ) = ϕ ψ xi1 ,K, xim , xim+1 ,K, xin
)
(1)
для некоторых m, перестановки индексов переменных ( i1 ,K, in ) и функций ϕ ,ψ ∈ K , то говорят, что f
допускает простую бесповторную декомпозицию в
классе K. При этом переменные xi ,K, xi называют1
m
ся связанными, а xi ,K, xi – свободными. Везде
m +1
n
далее в силу рассмотрения только бесповторных декомпозиций будем опускать термин “бесповторная”.
Простая декомпозиция называется нетривиальной,
если 1 < m < n . Функции, допускающие нетривиальные простые декомпозиции называются функционально разделимыми над соответствующим классом
1
функций■ .
Заметим, что данное выше определение является
более общим по отношению к определению 2.15 работы [6], так как рассматривает декомпозицию в произвольном классе булевых функций. Кроме того, в
смысле определения 2.15 указанной работы функционально неразделимой будет булевая функция
f ( x1 , x2 , x3 , x4 ) = ( x1 x2 ⊕ x1 x2 ⊕ x2 x3 ) x4 , в то время
как она является очевидно разложимой (и разделимой в смысле определения 1).
Далее без особых оговорок будем в случаях, ясных
по контексту изложения, использовать для неотрицательных целых чисел и векторов − их двоичных представлений − одни и те же обозначения.
Таблица разбиения T (m )
булевой функции
ISSN 2313-223X
а) в T (m ) существует не более двух типов различных строк;
б) в T (m ) найдется такой столбец, что все
остальные столбцы либо совпадают с ним, либо
получаются из него инвертированием всех его элементов, либо состоят из одних нулей, либо – из
единиц. ■
Введем определение булевых функций, задаваемых
квадратичными неравенствами, функциональные
свойства которых будут изучаться в этой работе. Более общее определение полиномиально-задаваемой
(или полиномиальной, как в [8]) пороговой функции
можно найти вместе с богатой библиографией и обзором результатов по пороговым функциям в [7].
Также эти понятия приводятся в [8], как и следующее
определение.
Определение 2. Булева функция f ∈ F2 (n) называется квадратичной пороговой (к.п.б.ф), если существует многочлен q ( x1 ,..., xn ) с действительными
коэффициентами такой, что:
deg q ( x1 ,..., xn ) = 2 ;
f ( x1 ,..., xn ) = 0 ⇔ q( x1 ,..., xn ) ≤ 0 . ■
Традиционные пороговые функции в смысле определения 2 могут быть названы линейными пороговыми функциями. Отметим, что хотя в [8] булева функция в смысле определения 2 называется знаковой
функцией многочлена q, а сам многочлен q – пороговым элементом, мы будем использовать также терминологию определения 2 для сохранения преемственности с теорией булевых линейных пороговых
функций.
Многочлен q из определения 2 может быть представлен в виде
q ( x1 ,..., xn ) = l ( x1 ,..., xn ) + q2 ( x1 ,..., xn )
где l – линейная часть многочлена, а q2 – квадратичная часть. Так как для булевых переменных справедливо
равенство
то
многочлен
x = x2 ,
l = a1 x1 + ... + an xn + a0 совпадает с
f ( x1 ,…, xn ) с параметром m определяется как мат-
q1 = a1 x12 + ... + an xn2 + a0 на булевых значениях пе-
рица, состоящая из 2m строк и 2n−m столбцов с элементами tu ,v = f (u , v) = f (u1 ,…, um , v1 ,…, vn −m ) .
ременных. Поэтому в качестве порогового элемента
можно взять многочлен q = q1 + q2 , и без ограниче-
Теорема 1 ([2]). Булева функция
f
допускает про-
стую декомпозицию вида
f (x1 , x2 ,..., xn ) = ϕ (ψ (x1 , x2 ,..., xm ), xm+1 ,..., xn )
(2)
в том и только том случае, когда выполняется
любое из следующих условий:
1
Этим символом будем обозначать границу формулировки определения, теоремы, самого доказательства теоремы
(если оно приводится вместе с теоремой) и других подобных фрагментов текста.
ния общности, далее будем рассматривать только
такие многочлены для задания квадратичных пороговых функций. Очевидно, что многочлен q − a0 является квадратичной формой. Заметим, что линейные
пороговые булевые функции являются квадратичными пороговыми в силу вышеизложенного.
Изменим в целях удобства оперирования квадратичными формами определение пороговой функции
f ( x1 ,..., xn ) = 0 ⇔ q( x1,..., xn ) ≤ 0 на равносильное
путем переноса свободного члена порогового элемента q в правую часть:
54
О ФУНКЦИОНАЛЬНОЙ РАЗДЕЛИМОСТИ БУЛЕВЫХ ФУНКЦИЙ,
ЗАДАВАЕМЫХ КВАДРАТИЧНЫМИ НЕРАВЕНСТВАМИ
f ( x1 ,..., xn ) = 0 ⇔ g ( x1 ,..., xn ) ≤ t ,
Шурупов А. Н.
ся неравенством возможно более чем второй степени
в отличие от исходной к.п.б.ф.
Пусть
где g = q − a0 , t = − a0 .
Укажем способы задания квадратичных пороговых
функций. Пусть g = g
– вектор коэффициентов
ij
u = ∑ uij xi x j
квадратичной формы g при фиксированном способе
их упорядочивания. Пара ( g , t ) − называется струк-
– квадратичная форма от m первых переменных, а
m
( )
i , j =1
n
турой квадратичной пороговой функции f (и обозначается f ~ ( g , t ) ), элементы вектора g = g i j –
( )
весами, а t – порогом. Известно, что структура является неоднозначным способом задания к.п.б.ф.
Вместо вектора коэффициентов многочлена в структуре можно указывать матрицу квадратичной формы.
Пусть
g ( x1 ,..., xn ) =
∑
n
g i j xi x j + ∑ gi xi2
1≤i < j ≤ n
i =1
– каноническая форма многочлена квадратичной
формы, тогда элементы матрицы W = w
q
ij
( )
квадратичной формы g ( x ,..., x ) = xW x
1
n
g
T
i , j =1,n
над полем
действительных чисел от переменных x = ( x1 ,K, xn )
определяются как
wi j =
gi j
, i < j,
2
wi j = w j i , i > j,
∑
v=
vi j xi x j
i , j = m +1
− квадратичная форма от (n-m) остальных переменных. Тогда через w = u + v обозначим естественным
образом составленную из этих форм квадратичную
форму от n переменных, для которой также будем
использовать обозначение через набор весов
w = (u | v) . Квадратичная форма вида w = (u | v )
называется распавшейся.
Лемма 1. Квадратичная форма w является распавшейся тогда и только тогда, когда существует
каноническая форма K w , такая что матрица перехода С – распавшаяся, т.е. C = diag ( Cu , Cv ) .
Доказательство. Необходимость следует из того, что
матрица W квадратичной формы – распавшаяся, и
поэтому каждую клетку можно независимо от другой
привести к диагональной с помощью своей матрицы
перехода. Достаточность следует из равенства
 C −1K C
 .■
0
W = u u u

−1
Cv K vCv 
0

wi i = g i .
Пусть A =
w
Очевидно, что g i j = wij + w ji , i ≠ j .
Квадратичная форма называется канонической (или
имеет канонический вид), если ее матрица диагональная. Известно, что любая ненулевая квадратичная форма над полем действительных чисел эквивалентна некоторой канонической, т.е. существует такая
ортогональная действительная матрица С, что замена
переменных x = yC переводит матрицу W квадратичной формы в каноническую KW = diag ( λ1 ,..., λn ) ,
где λi – собственные значения матрицы W . Отметим,
−1
что при такой замене переменные y = xC уже не
являются вообще говоря булевыми при булевых
наборах x , и поэтому эквивалентные квадратичные
формы задают в общем случае разные к.п.б.ф. Исключением здесь является случай, в котором булевы
наборы переменных x и y связаны невырожденной
действительной матрицей перехода, тогда эта матрица должна быть подстановочной, и соответствующие
булевы функции отличаются перестановкой переменных. Для неподстановочных матриц перехода исходная и новая к.п.б.ф. могут быть не связаны друг с другом линейным преобразованием координат. Аналогично, рассматривая линейное преобразование координат над GF(2), получаем, что новая функция задает-
{{w( x ) | x ∈{0,1} }} − мультимножество
n
значений квадратичной формы w ( x ) , вычисленных
для всех булевых векторов. Под набором
w* = ( w0* , w1* ,K, w2*n −1 )
понимается
упорядоченные
по неубыванию элементы множества Aw . Введем
обозначение
{ Aw}
для множества значений квадра-
тичной формы w.
Определим, как в работе [2], понятия нижнего  a  и
w
верхнего  a  приближений действительного числа a в
w
множестве значений w ( x ) следующим образом:
 a  w = max { z ∈ { Aw } z ≤ a} ,
 a  w = min { z ∈ { Aw } z > a} .
Заметим, что нижнее и верхнее приближения a существуют если и только если, когда
*
2n −1
a<w
a ≥ w0*
и
соответственно, где n − ранг w. В дальней-
шем для удобства максимальный элемент последовательности
w*
*
обозначим через wmax
. Кроме того,
положим  a  = −∞ , если
w
55
a < w0* , и  a  w = +∞ ,
Computational nanotechnology
2-2014
*
если a ≥ wmax
, и в этом случае будем говорить о бесконечных приближениях.
Очевидны следующие свойства конечных приближений:
 w  = w
j : w*j = w
1.
2.
*
i w
*
;
i
*
,
i
а также  w  = w
 
*
i w
*
,
j
(3)
где g,h1,h2 – к.п.б.ф.
Доказательство. Необходимость. Пусть f – к.п.б.ф. со
структурой ( u v , t ) . По теореме 1 в S (m ) существует не
более двух типов различных строк. В случае, если все
строки совпадают, то функция f зависит несущественно от первых m переменных и, полагая
h1 ( xm+1,K, xn ) = h2 ( xm+1,K, xn ) = f ( 0,K,0, xm+1,K, xn ) ,
w ( x ) ≤ a ⇒ w ( x ) ≤  a  w ;
4.  w*  = w* , если
i +1
 i w
том и только том случае, когда справедливо представление
f ( x1 ,K, xn ) =g ( x1 ,K, xm ) h1 ( xm+1 ,K, xn ) ∨ h2 ( xm+1,K, xn ) ,
для всех
 a  w ≤ a ;
3. если
ISSN 2313-223X
wi* ≠ wi*+1 ;
g ( x1 ,K, xm ) ≡ 0 ,
5.  a  > a .
w
получаем
искомое
представле-
(m )
i ∈ 0,2m − 1 , j ∈ 0,2n−m − 1 для к.п.б.ф. f со структурой
( u | v, t ) , rang u = m :
ние (2). Рассмотрим случай, когда в S
существуют
ровно два типа различных строк. Тогда по свойству
монотонности индексы строк одного типа в S (m ) образуют последовательность подряд идущих чисел.
Пусть строки с индексами 0,1,K, r − 1 совпадают и
si j = 0 ⇔ ui* + v*j ≤ t ,
более таких строк в S (m ) нет. Определим таблицы M1
si j = 1 ⇔ ui* + v*j > t.
и M 2 размера 2 m × 2 n − m следующим образом. M 1
имеет нулевыми r первых строк, а остальные совпа-
Введем
в
рассмотрение
таблицу
S
(m )
= si j ,
r
sr , а M 2 состоит из одинаковых строк, совпаr
дающих с s0 – первой строкой таблицы S (m) . Тогда по
Для таблицы S (m ) справедливо свойство монотонности: если p ≥ i, q ≥ j , то s pq ≥ sij .
дают с
Легко установить связь таблиц S (m ) и T (m ) . Пусть
g1, g 2 – подстановки степеней 2m и 2 n− m такие, что
свойству монотонности имеем
ui* = u ( g1 ( i ) ) , v*j = v ( g 2 ( j ) ) ,
где i ∈ 0,2m − 1, j ∈ 0, 2n −m − 1 – индексы строк и
столбцов. Тогда
t g1 ( i ), g 2 ( j ) = si , j .
Неочевидной является связь между функциональной разделимостью с параметром m и диагональным
видом матрицы весов к.п.б.ф. Действительно, для
m = 1 любая, в том числе к.п.б.ф., допускает тривиальную декомпозицию, однако при этом матрица
квадратичной формы не обязательно является распавшейся с блоком размера 1. Поэтому в дальнейшем
при исследования функциональной разделимости
к.п.б.ф. с параметром m будем рассматривать упрощающее предположение, заключающееся в том, что
квадратичная форма – распавшаяся.
Критерии функциональной разделимости
Следующая теорема является прямым обобщение
теоремы 2 работы [2] и утверждает, что для к.п.б.ф. с
распавшейся квадратичной формой при решении вопроса о функциональной разделимости достаточно
ограничиться только классом квадратичных пороговых булевых функций. Для простоты далее везде будем считать, что перестановка переменных в (1) тождественная.
Теорема 2. К.п.б.ф. f со структурой ( u v , t ) допускает простую декомпозицию вида (2) над F2 (n) в
S (m) = M1 ∨ M 2 , где
дизъюнкция (а также ниже используемая операция
булева умножения) применяется к таблицам поэлементно. Для M 1 справедливо представление
1
2
M 1 = M 1( ) ⋅ M 1( ) , где M1(1) – таблица размера
2 m × 2n−m , состоящая из первых r нулевых и (2m − r )
2
1-константных остальных строк; M 1( ) – таблица раз-
мера 2 m × 2 n − m , состоящая из одинаковых строк, совпадающих с
r
sr . Итак, имеем
S(
m)
= M 1( ) ⋅ M 1( ) ∨ M 2 .
1
2
Напомним, что булевы умножение и дизъюнкция являются линейно-пороговыми функциями, а значит −
к.п.б. функциями. Поэтому для завершения доказательства достаточно показать, что M 1(1) , M 1( 2) , M 2
определяют табличное задание искомых к.п.б.ф.
g,h1,h2 в (2).
Пусть w = u | v и подстановки g1 и g2 задают связь
таблиц
S (m ) и T (m ) : t g (i ), g ( j ) = si , j Приведем по1
2
дробное изложение доказательства для таблицы M 2 .
Для M 1(1) , M 1( 2 ) рассуждения практически полностью
( ) со-
аналогичны. По построению таблица M = m( 2 )
2
ij
стоит из одинаковых строк, совпадающих с
довательно
r
s0 , сле-
( 2)
( 2)
2
T2 = tij( ) , t g1 ( i ), g2 ( j ) = mij , является
( )
таблицей булевой функции, зависящей от перемен-
56
О ФУНКЦИОНАЛЬНОЙ РАЗДЕЛИМОСТИ БУЛЕВЫХ ФУНКЦИЙ,
ЗАДАВАЕМЫХ КВАДРАТИЧНЫМИ НЕРАВЕНСТВАМИ
xm+1 ,K, xn . Обозначим эту булеву функцию че-
ных
рез h2. Покажем, что h2 − к.п.б.ф. Действительно,
справедлива следующая цепочка равносильных
утверждений:
h2 ( y ) = h2 ( y1 ,K , yn−m ) = 0 ⇔
⇔ для любых p ∈ 0, 2 m − 1 t (p , )y = m g( −)1( p ), g −1( y ) = 0 ⇔
2
2
1
⇔ s0,q = 0, q = g
−1
2
2
(
)
Таким образом, h2 − к.п.б.ф. со структурой v, t − u0* .
(
Рассмотрим случай c2 ≥ t − u0* . Пусть α – такой индекс столбца, что выполняется vα* ≤ c2 < vα* +1 (чуть
ниже рассмотрим остальные варианты для α ). Тогда
*
*
из (4) имеем umax
+  c2  = umax
+ vα* ≤ t , и по свойству монотонности S (m ) элементы si , j = 0 для всех i
⇔ u0* + vq* ≤ t ⇔ u0* + v ( g 2 ( q ) ) ≤ t ⇔ v( y ) ≤ t − u0* .
Аналогично, таблицы M 1
рую функцию p ( x1 ,K, xn ) = g ⋅ h1 ∨ h2 . Докажем, что
f ( x1 ,K, xn ) ≡ p ( x1 ,K, xn ) .
v
( y) ⇔
(1) ,
( 2)
M1
) (
задают к.п.б.ф. g, h1
со структурами u , u * и v, t − u
r −1
*
r
).
Достаточность очевидна. Действительно, искомая
декомпозиция имеет вид:
ϕ ( x1,..., xm ) = g ,
Следующие результаты обобщают теорему 3 работы
[2] и сводят исследование функциональной разделимости к.п.б.ф. к анализу ее структуры.
Теорема 3. К.п.б.ф. f со структурой
( u | v, t )
до-
пускает простую декомпозицию вида (2) в том и
только том случае, когда найдутся такие числа
с1,с2, что выполняются неравенства
*
max c1  u + t − u0*  , umax
+ c2  v ≤ t < c1  u + c2  v . (4)
v
)
Доказательство. Необходимость. По теореме 2
справедливо представление (3). Тогда система (4)
выполняется для соответствующих приближений порогов c1 = ur*−1 , c2 = t − ur* , c3 = t − u0* функций g,h1,h2,
что означает si , j = 1 для всех
*
umax
+  c2  v ≤ t < c1  u + c2  v равносильно сов-
падению остальных строк S (m ) .
Достаточность. В случае, если все строки таблицы
Пусть для заданного m-разбиения
t система (4) имеет решение
Пусть c2 < t − u0* = с3 .
Функция p ( x1 ,K, xn ) = 0 в том и только том случае,
если для некоторых y ∈ {0,1}m , z ∈ {0,1}n−m , x = ( y, z )
выполняется
 g ( y ) = 0
 g ( y ) h1 ( z ) = 0 или h ( z ) = 0
 2


h2 ( z ) = 0
 h1 ( z ) = 0

 h2 ( z ) = 0
Тогда, продолжая равносильные преобразования,
получим
 u ( y ) ≤  c1  u

  v( z ) ≤  с3  v
v z ≤ c
,
 ( )  2  v
что означает с учетом (4) выполнение в первом случае неравенства
w( y, z ) = u ( y )+v( z ) ≤ c1  +  c3  ≤ t ,
u
с1 , с2 .
*
*
w( y, z ) = u ( y ) + v ( z ) ≤ umax
+ v ( z ) ≤ umax
+ c2  v ≤ t .
Итак, доказано включение
{
}
{
}
Ap0 = x ∈{0,1}n p ( x ) = 0 ⊆ A0f = x ∈{0,1}n f ( x ) = 0 . (5)
В случае, если p ( y , z ) = 1, имеем
 g ( y ) = 1
 g ( y ) h1 ( z ) = 1 ⇔ 
⇔

 h1 ( z ) = 1
h
z
=
1
(
)
2


Покажем, что
где c3 = t − u0* . Правая часть (3) определяет некото-
v
а во втором –
( u | v, t ) и числа
функция f имеет вид (3), причем g,h1,h2 – к.п.б.ф. со
структурами ( u , c1 ) , ( v, c2 ) , ( v, c3 ) , соответственно,
и j > α . Таким обра-
противоречие. К аналогичному результату, а именно
*
.
f ≡ 0 , приводит предположение vα* = vmax
S (m ) функции f одинаковы, имеем тривиальную декомпозицию для функции f, т.е. то, что требовалось
доказать. Поэтому будем считать, что имеем не менее двух типов различных строк в таблице S (m ) .
i
зом, в таблице S (m ) все строки одинаковые, что противоречит нашим предположениям. Если же
α + 1 = 0 , то s0,0 = 1 и f ≡ 1, что также образует
участвующих в представлении (3). Действительно,
неравенство  c1  + c3  ≤ t является следствием
u
v
совпадения строк таблицы S (m ) с номерами из множества {0,1,K, r − 1} , а выполнение неравенства
t ≤ u0* + c2 < u0* + vα* +1 ,
и j ≤ α . С другой стороны,
ψ (ϕ , xk +1,..., xn ) = ϕ h1 ( xm+1,..., xn ) ∨ h2 ( xm+1,..., xn ) .■
(
Шурупов А. Н.
 u ( y ) ≥ c1  u

 v ( z ) ≥  c2  v
v ( z ) > c .
3

 h2 ( z ) = 1
Проанализируем последнюю систему. Если выполняется g ( y ) h1 ( z ) = 1 , то по условию получаем
w ( y, z ) = u ( y ) + v ( z ) ≥ c1  u +  c2  v > t .
57
Computational nanotechnology
2-2014
В случае v ( z ) > c3 имеем следующую цепочку неравенств
w ( y, z ) = u ( y ) + v ( z ) > u ( y ) + c3 = u ( y ) − u0* + t ≥ t .
Итак, из p ( y, z ) = 1 получаем w(y , z ) > t , что доказывает включение
A1p ⊆ A1f
(6)
Объединяя
(5)
и
(6),
учитывая,
что
0
1
0
1
0
1
0
1
n,
∅
поAp I Ap = Aw I Aw =
| Ap U Ap |=| Af U Af |= 2
лучим Ap0 = A0f и A1p = A1f , то есть f – имеет вид (3),
что и требовалось доказать. Теорема доказана. ■
Замечание 1. Легко видеть, что теоремы 2 и 3 по
существу используют только факт декомпозиции полинома w ( x ) = w ( y, z ) = u ( y ) + v ( z ) . По этой причине эти результаты можно обобщить на произвольный функциональный класс, содержащий дизъюнкцию и конъюнкцию.
Теорема 4. К.п.б.ф. f ( x1 ,K, xn ) со структурой
( u | v , t ) , допускает представление вида (2) тогда и
только тогда, когда
{t − b 
u
}
*
b ∈ { Av } , u0* ≤ t − b < umax
≤ 1.
(7)
Доказательство. Воспользуемся табличным представлением функции f в виде S ( m) . В силу условия монотонности индексы одинаковых строк таблицы S ( ) образуют последовательность подряд идущих целых чисел. По
теореме 1 достаточно доказать, что выполнение неравенства (7) означает существование в S ( m ) не более двух
различных типов строк и наоборот. Строки с индексами i
и i +1 различны в том и только том случае, если найдется
такой j ∈ 0,2n−m − 1 , что si j < si +1, j . Это означает
m
ui* + v*j ≤ t < ui*+1 + v*j , что равносильно существованию b ∈ { Av } такому, что ui* ≤ t − b < ui*+1 . При этом
ui* = t − b  u . Таким образом, знакоперемена ( 0,1) в
b -ом столбце однозначно определяется величиной
*
t − b  u < umax . Следовательно, различные конечные
*
нижние приближения t − b  < umax
соответствуют
u
различным строкам (при этом первая строка не входит в
подсчет, так как не образует знакоперемены). Таким
образом, число таких конечных нижних приближений
равно числу блоков одинаковых строк таблицы S ( m) минус единица. ■
Список литературы:
1. Черемушкин А.В. Бесповторная декомпозиция сильно зависимых функций // Дискретная математика. 2004. Т.16. Вып.3.
С.3–42.
2. Шурупов А. Н. О функциональной разделимости булевых
пороговых функций // Дискретная математика. 1997. Т.9.
Вып. 2. С. 59−73.
ISSN 2313-223X
3. Ежов А. А., Шумский С. А. Нейрокомпьютинг и его применения в экономике и бизнесе. М., 1998. 222 с.
4. Ashenhurst R.L. The decomposition of switching functions //
Ann. Comput. Laborat. Harv. Univ. 1959. V.29. PP.74-116.
5. Дертоузос М. Пороговая логика / Перевод с англ.
Б. Л. Овсиевича, Л. Я. Розенблюма, под ред. В. И. Варшавского.
М.: Мир, 1967. 343 с. Перевод изд.: Threshold Logic: A Synthesis
Approach / Michael L. Dertouzos. The M.I.T. Press, Cambridge,
Massachusetts, 1965.
6. Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии / М.: МЦНМО, 2004.
470 с.
7. Crama Y., Hammer P. L. Boolean Functions. Theory, Algorithms
and Applications. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2011. 687 p.
8. Подольский В. В. Оценки весов персептронов (полиномиальных пороговых булевых функций). Автореферат дисс. на
соискание уч.степени к.ф.м.н. по спец.01.01.06. М., МГУ им
М.В. Ломоносова, 2009.
9. Балакин Г. В., Никонов В. Г. Методы сведения булевых
уравнений к системам пороговых соотношений // Обозрение
прикладной и промышленной математики. Т.1, Вып.3, 1994.
С.389-401.
10. Анашкина Н. В., Шурупов А. Н. Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств // Прикладная дискретная
математика. Приложение. №7, сентябрь 2014. Томск, Издательство ТГУ, 2014. С.151-153
List of reference:
1. Cheremushkin A.V. Iteration-free decomposition of strongly
dependent functions // Discrete Mathematics. 2004. V.16, Issue 3,
Pages 3-42.
2. Shurupov A. N. On decomposition of threshold Boolean functions // Discrete Mathematics and Applications dma. V.9, Issue 2,
Pages 59-73.
3. A.A. Ezhov and S.A. Shumsky. Neurocomputing and its applications in economics and business. Moscow.: MEPHI, 1998. 222 p.
4. Ashenhurst R.L. The decomposition of switching functions //
Ann. Comput. Laborat. Harv. Univ. 1959. V.29. PP.74-116.
5. Michael L. Dertouzos. Threshold Logic: A Synthesis Approach /
The M.I.T. Press, Cambridge, Massachusetts, 1965.
6. Logachëv, O.A.; Sal’nikov, A.A.; Yashchenko, V.V. Boolean functions in coding theory and cryptology. Moscow: Moskovskiĭ Tsentr
Nepreryvnogo Matematicheskogo Obrazovaniya (ISBN 5-94057117-4). 470 p. (2004).
7. Crama Y., Hammer P. L. Boolean Functions. Theory, Algorithms
and Applications. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2011. 687 p.
8. Podolskii V. V. Bounds of Perceptrons Weights (polynomial
threshold Boolean functions). PhD thesis. Moscow: MSU, 2009.
9. Balakin, G.V.; Nikonov, V.G. Methods for reduction of Boolean
equations to systems of threshold relations. (Russian) Zbl
0836.94026 Obozr. Prikl. Prom. Mat. 1, No.3, 389-401 (1994).
10. Anashkina N. V., Shurupov A. N. Application of Simulated Annealing and Balas Algorithms for Solving Pseudo-Boolean Linear
Inequalities Systems // App. Discrete Mathematics, №7. Tomsk,
2014. Pages 151-153.
58
О ФУНКЦИОНАЛЬНОЙ РАЗДЕЛИМОСТИ БУЛЕВЫХ ФУНКЦИЙ,
ЗАДАВАЕМЫХ КВАДРАТИЧНЫМИ НЕРАВЕНСТВАМИ
ОТЗЫВ
научного консультанта на статью Шурупова А.Н. «О функциональной разделимости булевых функций, задаваемых квадратичными неравенствами»
В соответствии с заявленной концепцией в журнале «Вычислительные нанотехнологии» рассматривается проблема сочетания фундаментального и прикладного аспектов в различных
прикладных задачах, в том числе математической природы. В
представленной статье в качестве базовой прикладной задачи
рассматривается проблема декомпозиции булевой функции
при условии задания ее квадратичным неравенством. Нахождение такого представления позволит сократить емкостную и
временную сложности реализации функций из указанного
класса, представляющего большой интерес в различных приложениях, от технических до моделирования нейрофизиологических процессов.
Автор статьи – Шурупов А.Н. – известен как признанный специалист в данной предметной области. Представленная статья
стала закономерным итогом проводимых им системных исследований проблем декомпозиции булевых функций, является новой и актуальной.
По тексту статьи научным консультантом был сделан ряд замечаний, которые в окончательной редакции были учтены.
Наиболее существенное уточнение связано с расширением
сферы практических ее приложений за счет сводимости рассматриваемой задачи к классу NP.
Рекомендую статью А.Н. Шурупова «О функциональной разделимости булевых функций, задаваемых квадратичными
неравенствами» к опубликованию в журнале «Вычислительные нанотехнологии».
Доктор технических наук,
член президиума РАЕН
В.Г. Никонов
59
Шурупов А. Н.
Документ
Категория
Без категории
Просмотров
6
Размер файла
241 Кб
Теги
задаваемые, функциональная, разделимости, булевых, функции, квадратичными, неравенства
1/--страниц
Пожаловаться на содержимое документа