Алгебраически вырожденные приближения булевых функций
Исследуются свойства k-мерных приближений булевых функций. Одним из основных результатов является теорема о строении k-мерных функций степени d, находящихся на расстоянии не более 2^(n-d)(1- ε), ε∊(0,1), от заданной булевой функции n переменных, 1≤d≤k≤n, ε∊(0,1). Эта теорема существенно усиливает ра...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/124734 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Алгебраически вырожденные приближения булевых функций / А.Н. Алексейчук, С.Н. Конюшок // Кибернетика и системный анализ. — 2014. — Т. 50, № 6. — С. 3-14. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124734 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1247342025-02-09T09:33:21Z Алгебраически вырожденные приближения булевых функций Алгебраїчно вироджені наближення булевих функцій Algebraic degenerate approximations of Boolean functions Алексейчук, А.Н. Конюшок, С.Н. Кибернетика Исследуются свойства k-мерных приближений булевых функций. Одним из основных результатов является теорема о строении k-мерных функций степени d, находящихся на расстоянии не более 2^(n-d)(1- ε), ε∊(0,1), от заданной булевой функции n переменных, 1≤d≤k≤n, ε∊(0,1). Эта теорема существенно усиливает ранее известный результат П. Гопалана и позволяет заметно повысить эффективность предложенного им алгоритма построения всех указанных k-мерных булевых функций. Досліджуються властивості k-вимірних наближень булевих функцій. Одним з основних результат ів є теорема про будову k-вимірних функцій степеня d, що знаходяться на відстані не більше 2^(n-d)(1- ε), ε∊(0,1), від заданої булевої функції n змінних, 1≤d≤k≤n, ε∊(0,1). Ця теорема суттєво підсилює раніше відомий результат П. Гопалана та дозволяє значно підвищити ефективність запропонованого ним алгоритму побудови усіх зазначених k-вимірних булевих функцій. The properties of k-dimensional approximations of Boolean functions are analyzed. One of the main results is a theorem that specifies the structure of k-dimensional functions of degree d within the distance of 2^(n-d)(1- ε), ε∊(0,1), from a specified n-variable function, 1≤d≤k≤n, ε∊(0,1). This theorem significantly improves Gopalan’s result and notably increases the efficiency of his algorithm for finding all of the mentioned k-dimensional Boolean functions. 2014 Article Алгебраически вырожденные приближения булевых функций / А.Н. Алексейчук, С.Н. Конюшок // Кибернетика и системный анализ. — 2014. — Т. 50, № 6. — С. 3-14. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124734 519.7 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Алексейчук, А.Н. Конюшок, С.Н. Алгебраически вырожденные приближения булевых функций Кибернетика и системный анализ |
| description |
Исследуются свойства k-мерных приближений булевых функций. Одним из основных результатов является теорема о строении k-мерных функций степени d, находящихся на расстоянии не более 2^(n-d)(1- ε), ε∊(0,1), от заданной булевой функции n переменных, 1≤d≤k≤n, ε∊(0,1). Эта теорема существенно усиливает ранее известный результат П. Гопалана и позволяет заметно повысить эффективность предложенного им алгоритма построения всех указанных k-мерных булевых функций. |
| format |
Article |
| author |
Алексейчук, А.Н. Конюшок, С.Н. |
| author_facet |
Алексейчук, А.Н. Конюшок, С.Н. |
| author_sort |
Алексейчук, А.Н. |
| title |
Алгебраически вырожденные приближения булевых функций |
| title_short |
Алгебраически вырожденные приближения булевых функций |
| title_full |
Алгебраически вырожденные приближения булевых функций |
| title_fullStr |
Алгебраически вырожденные приближения булевых функций |
| title_full_unstemmed |
Алгебраически вырожденные приближения булевых функций |
| title_sort |
алгебраически вырожденные приближения булевых функций |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Кибернетика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124734 |
| citation_txt |
Алгебраически вырожденные приближения булевых функций / А.Н. Алексейчук, С.Н. Конюшок // Кибернетика и системный анализ. — 2014. — Т. 50, № 6. — С. 3-14. — Бібліогр.: 12 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT aleksejčukan algebraičeskivyroždennyepribliženiâbulevyhfunkcij AT konûšoksn algebraičeskivyroždennyepribliženiâbulevyhfunkcij AT aleksejčukan algebraíčnovirodženínabližennâbulevihfunkcíj AT konûšoksn algebraíčnovirodženínabližennâbulevihfunkcíj AT aleksejčukan algebraicdegenerateapproximationsofbooleanfunctions AT konûšoksn algebraicdegenerateapproximationsofbooleanfunctions |
| first_indexed |
2025-11-25T06:49:19Z |
| last_indexed |
2025-11-25T06:49:19Z |
| _version_ |
1849744031365464064 |
| fulltext |
À.Í. ÀËÅÊÑÅÉ×ÓÊ, Ñ.Í. ÊÎÍÞØÎÊ
ÓÄÊ 519.7 ÀËÃÅÁÐÀÈ×ÅÑÊÈ ÂÛÐÎÆÄÅÍÍÛÅ
ÏÐÈÁËÈÆÅÍÈß ÁÓËÅÂÛÕ ÔÓÍÊÖÈÉ
Àííîòàöèÿ. Èññëåäóþòñÿ ñâîéñòâà k-ìåðíûõ ïðèáëèæåíèé áóëåâûõ ôóíêöèé. Îäíèì èç
îñíîâíûõ ðåçóëüòàòîâ ÿâëÿåòñÿ òåîðåìà î ñòðîåíèè k-ìåðíûõ ôóíêöèé ñòåïåíè d, íàõîäÿ-
ùèõñÿ íà ðàññòîÿíèè íå áîëåå 2 1n d� �( )� , �� ( , )0 1 , îò çàäàííîé áóëåâîé ôóíêöèè n ïåðå-
ìåííûõ, 1 � � �d k n , �� ( , )0 1 . Ýòà òåîðåìà ñóùåñòâåííî óñèëèâàåò ðàíåå èçâåñòíûé ðå-
çóëüòàò Ï. Ãîïàëàíà è ïîçâîëÿåò çàìåòíî ïîâûñèòü ýôôåêòèâíîñòü ïðåäëîæåííîãî èì àë-
ãîðèòìà ïîñòðîåíèÿ âñåõ óêàçàííûõ k-ìåðíûõ áóëåâûõ ôóíêöèé.
Êëþ÷åâûå ñëîâà: êîððåëÿöèîííûé êðèïòîàíàëèç, âûðîæäåííàÿ áóëåâà ôóíêöèÿ, k-ìåðíàÿ ôóíê-
öèÿ, ïðåîáðàçîâàíèå Óîëøà–Àäàìàðà, íàõîæäåíèå k-ìåðíûõ ïðèáëèæåíèé áóëåâûõ ôóíêöèé.
ÂÂÅÄÅÍÈÅ
Áóëåâà ôóíêöèÿ g n:{ , } { , }0 1 0 1� ( )0 � �k n íàçûâàåòñÿ k-ìåðíîé [1, 2], åñëè ñó-
ùåñòâóþò ôóíêöèÿ �:{ , } { , }0 1 0 1k � è n k� -ìàòðèöà A íàä ïîëåì èç äâóõ ýëåìåí-
òîâ òàêèå, ÷òî äëÿ ëþáîãî x n�{ , }0 1 âûïîëíÿåòñÿ ðàâåíñòâî g x xA( ) ( )� � . Ôóíê-
öèÿ g íàçûâàåòñÿ àëãåáðàè÷åñêè âûðîæäåííîé, åñëè îíà ÿâëÿåòñÿ k-ìåðíîé äëÿ
íåêîòîðîãî k n� , è íåâûðîæäåííîé — â ïðîòèâíîì ñëó÷àå [3–5].
Ïåðâûå ðåçóëüòàòû î êîððåëÿöèîííûõ ñâîéñòâàõ àëãåáðàè÷åñêè âûðîæäåííûõ
áóëåâûõ ôóíêöèé îòíîñÿòñÿ ê 70-ì ãîäàì ïðîøëîãî âåêà [3]. Â íàñòîÿùåå âðåìÿ
èíòåðåñ ê èññëåäîâàíèþ ýòèõ ôóíêöèé îáóñëîâëåí çàäà÷àìè êðèïòîàíàëèçà è òåî-
ðèè êîäèðîâàíèÿ. Îòìåòèì ðàáîòû [6–8], â êîòîðûõ îïèñàí ðÿä àòàê íà ãåíåðàòîðû
ãàììû ïîòî÷íûõ øèôðîâ, ôóíêöèè óñëîæíåíèÿ êîòîðûõ ÿâëÿþòñÿ àëãåáðàè÷åñêè
âûðîæäåííûìè èëè áëèçêè ê òàêîâûì.
Îáîçíà÷èì Bn k, ìíîæåñòâî âñåõ k-ìåðíûõ áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ.
 [5] èññëåäîâàíû ïðèáëèæåíèÿ áóëåâûõ ôóíêöèé ôóíêöèÿìè èç ìíîæåñòâà Bn n, �1 ;
â ÷àñòíîñòè, íàéäåíî ðàññòîÿíèå ìåæäó ïðîèçâîëüíîé ôóíêöèåé f n:{ , } { , }0 1 0 1�
è ìíîæåñòâîì àëãåáðàè÷åñêè âûðîæäåííûõ ôóíêöèé îò n ïåðåìåííûõ, óêàçàí ñïîñîá
íàõîæäåíèÿ ôóíêöèé, áëèæàéøèõ ê f âî ìíîæåñòâå Bn n, �1, è ïîëó÷åíû îöåíêè èõ ïî-
ðÿäêîâ (â [4, 5] ïîðÿäêîì âûðîæäåííîñòè ôóíêöèè g Bn n� �, 1 íàçûâàåòñÿ íàèáîëüøåå
÷èñëî n k� , äëÿ êîòîðîãî g ÿâëÿåòñÿ k-ìåðíîé ôóíêöèåé).
Èçó÷åíèþ k-ìåðíûõ ïðèáëèæåíèé áóëåâûõ ôóíêöèé ïðè âñåõ âîçìîæíûõ çíà-
÷åíèÿõ k ïîñâÿùåíû ðàáîòû [1, 2, 9–11], ïðè÷åì â [2] ðàññìàòðèâàþòñÿ ôóíêöèè
íàä ïðîèçâîëüíûì êîíå÷íûì ïîëåì.
 [1] ïðåäëîæåí âåðîÿòíîñòíûé àëãîðèòì ðàñïîçíàâàíèÿ ñâîéñòâà k-ìåðíîñòè.
Äëÿ ëþáîé ôóíêöèè f n:{ , } { , }0 1 0 1� , çàäàííîé ñ ïîìîùüþ îðàêóëà, è ÷èñåë
k n� �{ , , ... , }0 1 1 , �� ( , )0 1 ýòîò àëãîðèòì ïîçâîëÿåò ïðîâåðèòü ãèïîòåçó H0 : f Bn k� ,
îòíîñèòåëüíî àëüòåðíàòèâû H1, ñîñòîÿùåé â òîì, ÷òî f íàõîäèòñÿ íà ðàññòîÿíèè íå ìå-
íåå 2n � îò ìíîæåñòâà k-ìåðíûõ ôóíêöèé, çà O n kk( )22 1�� äâîè÷íûõ îïåðàöèé. Áîëåå
ýôôåêòèâíûé òåñò k-ìåðíîñòè, òðóäîåìêîñòü êîòîðîãî ñîñòàâëÿåò O n kk( )2 2 1�� äâî-
è÷íûõ îïåðàöèé, ïðåäëîæåí â [10].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 3
© À.Í. Àëåêñåé÷óê, Ñ.Í. Êîíþøîê, 2014
Äëÿ ïîñòðîåíèÿ ýôôåêòèâíûõ àòàê íà ñèììåòðè÷íûå êðèïòîñèñòåìû íåîáõî-
äèìî íàõîäèòü k-ìåðíûå ôóíêöèè, äîñòàòî÷íî áëèçêèå ê çàäàííîé ôóíêöèè
f n:{ , } { , }0 1 0 1� . Ïðè ýòîì íàèáîëüøèé èíòåðåñ ïðåäñòàâëÿåò ñëó÷àé, êîãäà f çàäà-
åòñÿ ñ ïîìîùüþ îðàêóëà, n âåëèêî (íàïðèìåð, n 64), à k — ìàë� (ôèêñèðîâàíî èëè
ìåäëåííî óâåëè÷èâàåòñÿ ñ ðîñòîì n). Ýôôåêòèâíîñòü ðåøåíèÿ ýòîé çàäà÷è ñóùå-
ñòâåííî çàâèñèò îò ðàññòîÿíèÿ ìåæäó ôóíêöèåé f è åå èñêîìûìè ïðèáëèæåíèÿìè.
Ïóñòü g — k-ìåðíàÿ ôóíêöèÿ îò n ïåðåìåííûõ, íàõîäÿùàÿñÿ îò ôóíêöèè f íà ðàñ-
ñòîÿíèè íå áîëåå 2 11n k�
�( ) ( )� , �� ( , )0 1 (îòìåòèì, ÷òî ôóíêöèÿ g îïðåäåëÿåòñÿ ýòèì
óñëîâèåì îäíîçíà÷íî).  [1] ïðåäëîæåí âåðîÿòíîñòíûé àëãîðèòì, ïîçâîëÿþùèé íàõî-
äèòü g ïî çàäàííûì f , k è � ñ âåðîÿòíîñòüþ íå ìåíåå 1��, �� ( , )0 1 , çà
O n nk k( log( ))2 24 2 2 2 1� �� � äâîè÷íûõ îïåðàöèé.  [11] ïðåäñòàâëåí äðóãîé àëãîðèòì,
äâîè÷íàÿ ñëîæíîñòü êîòîðîãî ðàâíà O k n k nk k( log( ))2 22 2 3 2 1 2 1 1 1� � � � � �� � � � .
Çàäà÷à îïðåäåëåíèÿ âñåõ ôóíêöèé g Bn k� , , íàõîäÿùèõñÿ îò çàäàííîé ôóíê-
öèè f n:{ , } { , }0 1 0 1� íà ðàññòîÿíèè, íå ïðåâûøàþùåì 2 1n k� �( )� , �� ( , )0 1 , ÿâëÿåò-
ñÿ áîëåå òðóäíîé. Ñóùåñòâåííûé âêëàä â åå ðåøåíèå ñäåëàí â ðàáîòå [2], ïîñâÿ-
ùåííîé èçó÷åíèþ k-ìåðíûõ ïðèáëèæåíèé ôóíêöèé îò n ïåðåìåííûõ íàä ïðîèç-
âîëüíûì êîíå÷íûì ïîëåì. Îäíèì èç îñíîâíûõ ðåçóëüòàòîâ ýòîé ðàáîòû ÿâëÿåòñÿ
òåîðåìà, îïèñûâàþùàÿ ñòðîåíèå k-ìåðíûõ ôóíêöèé ñòåïåíè íå âûøå d íàä ïîëåì
GF( )q , íàõîäÿùèõñÿ îò çàäàííîé ôóíêöèè f q qn: ( ) ( )GF GF� íà ðàññòîÿíèè íå áî-
ëåå � �q d( )( )1� , ãäå �q d( ) — ìèíèìàëüíîå ðàññòîÿíèå êîäà Ðèäà–Ìàëëåðà
RMq n d( , ) , 1� �d k, �� ( , )0 1 (ñì. [2, ï. 4]).  íàñòîÿùåé ñòàòüå äîêàçàíà òåîðåìà,
ñóùåñòâåííî óñèëèâàþùàÿ ýòîò ðåçóëüòàò äëÿ ñëó÷àÿ áóëåâûõ ôóíêöèé. Ïîëó÷åí òàê-
æå ðÿä óòâåðæäåíèé î ñâîéñòâàõ k-ìåðíûõ ïðèáëèæåíèé áóëåâûõ ôóíêöèé, äîïîëíÿ-
þùèõ è óòî÷íÿþùèõ îòäåëüíûå ðåçóëüòàòû ðàáîò [5, 9].
ÎÏÐÅÄÅËÅÍÈÅ ÎÑÍÎÂÍÛÕ ÏÎÍßÒÈÉ
È ÍÅÊÎÒÎÐÛÅ ÂÑÏÎÌÎÃÀÒÅËÜÍÛÅ ÐÅÇÓËÜÒÀÒÛ
Îáîçíà÷èì Vn ìíîæåñòâî äâîè÷íûõ âåêòîðîâ äëèíû n . Ýòî ìíîæåñòâî ÿâëÿåòñÿ
âåêòîðíûì ïðîñòðàíñòâîì ðàçìåðíîñòè n íàä ïîëåì F �GF( )2 (ïðè n � 0 ïîëàãà-
åì V0 0�{ }). Ñóììà âåêòîðîâ � � �� � �( )1 � n , x x x Vn n� �( ,... , )1 îïðåäåëÿåòñÿ ïî
ôîðìóëå � � �� � � �x x xn n( , , )1 1 � , à áóëåâî ñêàëÿðíîå ïðîèçâåäåíèå — ïî
ôîðìóëå � � �x x xn n� �
�1 1 (çäåñü è íèæå ñèìâîë � îáîçíà÷àåò îïåðàöèþ
ñëîæåíèÿ êàê ýëåìåíòîâ ïîëÿ F, òàê è âåêòîðîâ íàä ýòèì ïîëåì).
 äàëüíåéøåì èñïîëüçóþòñÿ ñëåäóþùèå îáîçíà÷åíèÿ: # M — ìîùíîñòü ìíî-
æåñòâà M; � �M — ïîäïðîñòðàíñòâî, ïîðîæäåííîå ìíîæåñòâîì M Vn� ; Fn k� —
ìíîæåñòâî ìàòðèö ðàçìåðà n k� íàä ïîëåì F; C A( ) — ïîäïðîñòðàíñòâî âåêòîðíîãî
ïðîñòðàíñòâà Vn , ïîðîæäåííîå ñòîëáöàìè ìàòðèöû A Fn k� � .
Äëÿ ëþáîãî ìíîæåñòâà M Vn� îáîçíà÷èì M� ïîäïðîñòðàíñòâî, äóàëüíîå ê M :
M V x M xn
� � � � � �{ | : }� � 0 ; äëÿ ëþáûõ a b, �Z ïîëîæèì a b i a i b, { : }� � � �Z .
Îáîçíà÷èì Bn ìíîæåñòâî áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ. Îòíîñèòåëüíîå ðàñ-
ñòîÿíèå ìåæäó ôóíêöèÿìè f g Bn, � îïðåäåëÿåòñÿ ïî ôîðìóëå d f g x Vn
n( , ) #{ :� ��2
f x g x( ) ( )}� , à îòíîñèòåëüíîå ðàññòîÿíèå îò ôóíêöèè f Bn� äî ìíîæåñòâà U Bn� —
ïî ôîðìóëå d f U d f g
g U
( , ) min ( , )�
�
. ×èñëî wt f x V f xn
n( ) #{ : ( ) }� � ��2 1 íàçûâàåòñÿ îò-
íîñèòåëüíûì âåñîì ôóíêöèè f Bn� . Áóëåâà ôóíêöèÿ íàçûâàåòñÿ óðàâíîâåøåííîé,
åñëè åå îòíîñèòåëüíûé âåñ ðàâåí 1 2/ .
Îáîçíà÷èì deg f ñòåïåíü ïîëèíîìà Æåãàëêèíà ôóíêöèè f Bn� . Äîêàçà-
òåëüñòâî ñëåäóþùåé ëåììû ìîæíî íàéòè â [12, òåîðåìà 5.5].
Ëåììà 1. Ïóñòü f Bn� \ { }0 . Òîãäà wt f f( ) �2 deg .
Äëÿ ëþáîé ôóíêöèè f Bn� ïîëîæèì
� ( ) ( ) ( )f n f x x
x Vn
� �� �� �
�
�2 1 , ��Vn , (1)
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6
D f x f x f x� �( ) ( ) ( )� � � , x Vn� , (2)
I V D ff n� � �{ : }� � 0 .
×èñëà â (1) íàçûâàþòñÿ íîðìèðîâàííûìè êîýôôèöèåíòàìè Óîëøà–Àäàìàðà
ôóíêöèè f , à ôóíêöèÿ (2) — åå ïðîèçâîäíîé ïî íàïðàâëåíèþ ��Vn [12].
Äëÿ ëþáîãî k n�0, îáîçíà÷èì �n k, ìíîæåñòâî âñåõ k-ìåðíûõ ïîäïðîñòðàíñòâ
âåêòîðíîãî ïðîñòðàíñòâà Vn . Ïîëîæèì
� f
x H
H f x( ) � ( )�
�
� 2 , H n k�� , . (3)
Äëÿ ëþáîãî L n n k� �� , îáîçíà÷èì L Ls s� � � , s Vk� , âñå ïîïàðíî ðàçëè÷íûå
ñìåæíûå êëàññû ïðîñòðàíñòâà Vn ïî ïîäïðîñòðàíñòâó L . Ñïðàâåäëèâû ñëåäóþ-
ùèå ñîîòíîøåíèÿ [12, òåîðåìà 2.89, ëåììà 2.4]:
� �
�
f
n k n D f x
x VH
H
n
( ) ( )( ) ( )� �� � �
��
��
�
2 2 1 , H n k�� , , (4)
2 1 1� �
� �
� � �� �
�
( ) ( )( ) � ( )( )n k f x
x L
x
x Ls
sf x
�
, L n n k� �� , , s Vk� . (5)
Ïðè k n� èç ôîðìóëû (4) âûòåêàåò ðàâåíñòâî Ïàðñåâàëÿ:
� f n
x V
V f x
n
( ) � ( )� �
�
� 2 1.
Îïðåäåëåíèå 1 [1, 2]. Ôóíêöèÿ g Bn� íàçûâàåòñÿ k-ìåðíîé, k n�0, , åñëè îíà
äîïóñêàåò ïðåäñòàâëåíèå â âèäå
g x xA( ) ( )� � , x Vn� , (6)
ãäå ��Bk , A Fn k� � .
Îáîçíà÷èì Bn k, ìíîæåñòâî âñåõ k-ìåðíûõ ôóíêöèé îò n ïåðåìåííûõ, ïîëî-
æèì Bn,� ��1 . Ñïðàâåäëèâû ñîîòíîøåíèÿ
B B B Bn n n n n n, , , ,0 1 1� � � ��� ;
ïðè ýòîì ìíîæåñòâî Bn,0 ñîñòîèò èç äâóõ ôóíêöèé-êîíñòàíò, ìíîæåñòâî Bn,1
ñîâïàäàåò ñ êëàññîì àôôèííûõ ôóíêöèé, à ìíîæåñòâî Bn n, — ñ ñîâîêóïíîñòüþ
âñåõ áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ. Ôóíêöèè èç ìíîæåñòâà Bn n, �1 íàçûâà-
þòñÿ àëãåáðàè÷åñêè âûðîæäåííûìè, à ôóíêöèè èç ìíîæåñòâà B Bn n n\ , �1 — íå-
âûðîæäåííûìè [3–5].
Îïðåäåëåíèå 2. Íàçîâåì ôóíêöèþ g Bn� ñòðîãî k-ìåðíîé, åñëè
g B Bn k n k� �, ,\ 1, ò.å. k ÿâëÿåòñÿ íàèìåíüøèì íåîòðèöàòåëüíûì öåëûì ÷èñëîì, äëÿ
êîòîðîãî ñóùåñòâóåò ïðåäñòàâëåíèå ôóíêöèè g â âèäå (6). Êàæäîå òàêîå ïðåäñòàâ-
ëåíèå (ñîîòâåòñòâóþùåå íàèìåíüøåìó âîçìîæíîìó çíà÷åíèþ k) íàçîâåì íåïðèâî-
äèìûì ïðåäñòàâëåíèåì ôóíêöèè g.
Ñëåäóþùàÿ ëåììà ïî ñóùåñòâó ñîâïàäàåò ñ óòâåðæäåíèåì 2 â ñòàòüå [5].
Ëåììà 2 [5]. Ôóíêöèÿ g Bn� ÿâëÿåòñÿ ñòðîãî k-ìåðíîé òîãäà è òîëüêî òîãäà,
êîãäà dim I n kg � � , k n�0, .
Ñëåäñòâèå 1. Ïðåäñòàâëåíèå (6) ÿâëÿåòñÿ íåïðèâîäèìûì òîãäà è òîëüêî òîãäà,
êîãäà rank A k� è I � �{ }0 . Ïðè ýòîì I x V xA C Ag n� � � � �{ : } ( )0 .
Îòìåòèì, ÷òî êàæäàÿ k-ìåðíàÿ ôóíêöèÿ g äîïóñêàåò òàêîå ïðåäñòàâëåíèå
â âèäå (6), äëÿ êîòîðîãî rank A k� : äîñòàòî÷íî ðàññìîòðåòü íåïðèâîäèìîå ïðåä-
ñòàâëåíèå g x xB( ) ( )� � , x Vn� , ãäå ��Br , B Fn r� � , r B k� �rank , äîïîëíèòü ìàòðè-
öó B äî n k� -ìàòðèöû ðàíãà k è çàìåíèòü ôóíêöèþ � ôóíêöèåé, ïîëó÷åííîé ïóòåì
ââåäåíèÿ k r� ôèêòèâíûõ ïåðåìåííûõ.
 äàëüíåéøåì äëÿ ôóíêöèè g Bn k� , , çàäàííîé ïî ôîðìóëå (6), áóäåì èñïîëü-
çîâàòü îáîçíà÷åíèå g A�, , ïðåäïîëàãàÿ, ÷òî ��Bk , A Fn k� � è rank A k� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 5
ÄÎÏÓÑÒÈÌÛÅ ÏÎÄÏÐÎÑÒÐÀÍÑÒÂÀ. ÎÖÅÍÊÈ ÎÒÍÎÑÈÒÅËÜÍÎÃÎ ÐÀÑÑÒÎßÍÈß
ÌÅÆÄÓ ÁÓËÅÂÎÉ ÔÓÍÊÖÈÅÉ È ÌÍÎÆÅÑÒÂÎÌ k-ÌÅÐÍÛÕ ÔÓÍÊÖÈÉ
Ïóñòü f Bn� , k n� �0 1, , �� ( , )0 1 .
Îïðåäåëåíèå 3. Íàçîâåì ïðîñòðàíñòâî H n k�� , �-äîïóñòèìûì äëÿ ôóíêöèè
f , åñëè ñóùåñòâóåò ïàðà ( , )� A B Fk n k� � � òàêàÿ, ÷òî rank A k� , H C A� ( ) è
d f g A( , ) / ( ),� ��
�1 2 1 .
Äëÿ ëþáîãî H n k�� , îáîçíà÷èì B Hn k, ( ) ìíîæåñòâî âñåõ ôóíêöèé g Bn k� , ,
äîïóñêàþùèõ ïðåäñòàâëåíèå â âèäå (6) òàêîå, ÷òî rank A k� è H C A� ( ) . Î÷åâèäíî,
÷òî
B B Hn k n k
H n k
, , ( )
,
�
��
� . (7)
Ïðè ýòîì �-äîïóñòèìûìè äëÿ ôóíêöèè f ÿâëÿþòñÿ òå è òîëüêî òå ïîäïðîñòðàí-
ñòâà H n k�� , , äëÿ êîòîðûõ d f B Hn k( , ( )) / ( ), �
�1 2 1 �
Äëÿ ëþáîãî H n k�� , ïîëîæèì
l H f xf
n
s V
f x
x L
k
k s
s( ) ( ) � ( )( )( )� �
�
�
��
�
�
��� ��
� �
�� �2 1 2 1
� x
x Hs Vk ��
��
�
�
�
�
�
�, (8)
ãäå { : } /L L s V V Ls s k n� � � �� , L H� � (îòìåòèì, ÷òî â ñèëó ðàâåíñòâà (5) ïàðà-
ìåòð l Hf ( ) îïðåäåëåí êîððåêòíî).
Äîêàæåì ðÿä óòâåðæäåíèé, óòî÷íÿþùèõ òåîðåìû 4 è 5, ïðèâåäåííûå â [9] áåç
äîêàçàòåëüñòâà.
Ëåììà 3. Äëÿ ëþáûõ f Bn� , k n� �0 1, , H n k�� , ñïðàâåäëèâî ðàâåíñòâî
d f B H l Hn k f( , ( )) / ( ( )), �
�1 2 1 . (9)
Ïðè ýòîì ôóíêöèÿ g B HA n k�, , ( )� ÿâëÿåòñÿ áëèæàéøåé ê f âî ìíîæåñòâå
B Hn k, ( ) òîãäà è òîëüêî òîãäà, êîãäà âûïîëíÿþòñÿ ñëåäóþùèå ñîîòíîøåíèÿ:
� ( )( ) ( ) � ( )( )( )f Ay f Aysy
y V
s sy
y Vk k
� � � �
�
�
��
�
�
�
� �
� �1 1 1�
�, s Vk� . (10)
Äîêàçàòåëüñòâî. Ïóñòü g g B HA n k� ��, , ( ) , ãäå C A H( ) � . Çàìåòèì, ÷òî âñå
ðàçëè÷íûå ñìåæíûå êëàññû ïðîñòðàíñòâà Vn ïî ïîäïðîñòðàíñòâó L H� � èìåþò
ñëåäóþùèé âèä: L x V xA ss n� � �{ : }, s Vk� . Îòñþäà íà îñíîâàíèè ôîðìóë (5) è (8)
âûòåêàþò ðàâåíñòâà
2 1 1� �
� �
� � �� �( ) ( )( ) � ( )( )n k f x
x L
sy
y Vs k
f Ay , s Vk� , (11)
l H f Ayf
k sy
y Vs V kk
( ) � ( )( )� �
�
�
��
�
�
��
�
��
��2 1 , (12)
èñïîëüçóÿ êîòîðûå ïîëó÷èì
1 2 2 1� � � �� �
�
�d f g n f x g x
x Vn
( , ) ( ) ( ) ( )
� � � � �� �
��
� � ���2 1 2 1 2 1n f x g x
x Ls V
k s n k
sk
( ) ( ) ( )( ) ( ) ( ) ( )� f x
x Ls V sk
( )
��
��
�
�
�
�
�
�
�
�
�
� � �
�
�
�
�
�
�
�
�
��
��
���2 1 1 2k s sy
y Vs V
kf Ay f A
kk
( ) � ( )( ) � (( )� y l Hsy
y Vs V
f
kk
)( ) ( )�
�
�
��
�
�
���
��
�� 1 .
Ïðè ýòîì ïîñëåäíåå íåðàâåíñòâî îáðàùàåòñÿ â ðàâåíñòâî òîãäà è òîëüêî òîãäà,
êîãäà âûïîëíÿþòñÿ ñîîòíîøåíèÿ (10).
Ëåììà äîêàçàíà.
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6
Ñëåäñòâèå 2. Ïîäïðîñòðàíñòâî H n k�� , ÿâëÿåòñÿ �-äîïóñòèìûì äëÿ ôóíêöèè f
òîãäà è òîëüêî òîãäà, êîãäà l Hf ( ) � .
Ëåììà 4. Äëÿ ëþáûõ f Bn� , k n� �0 1, , H n k�� , ñïðàâåäëèâû íåðàâåíñòâà
� �f f fH l H H( ) ( ) ( ( )) /� � 1 2 , (13)
ãäå � f H( ) îïðåäåëÿåòñÿ ïî ôîðìóëå (3).
Äîêàçàòåëüñòâî. Îáîçíà÷èì A ïðîèçâîëüíóþ n k� -ìàòðèöó, ñòîëáöû êîòîðîé
îáðàçóþò áàçèñ âåêòîðíîãî ïðîñòðàíñòâà H; ïîëîæèì L H� � ,
u f Ays
sy
y Vk
� �
�
�
��
�
�
��
�
� � ( )( )1 , s Vk� .
Íà îñíîâàíèè ôîðìóë (5) è (8) ñïðàâåäëèâû ðàâåíñòâà (11), (12), èç êîòîðûõ
ñëåäóåò, ÷òî 0 1� �us , s Vk� è
l H uf
k
s
s Vk
( ) � �
�
�2 .
Ñëåäîâàòåëüíî,
2 22 2
1 2
�
�
�
�
� �� �
�
�
�
�
�
�
�
�
k
s
s V
f
k
s
s V
u l H u
k k
( )
/
. (14)
Êðîìå òîãî, ñïðàâåäëèâû ñëåäóþùèå ñîîòíîøåíèÿ:
2 2 12
1 2
1 2
1
�
�
�
�
�� �� �k
s
s V
k
s V
s y y
y
u f Ay f Ay
k k
� ( ) � ( )( )
( )
( , y Vk2
2)�
� �
� �
�
�
�
�
�
�
�
�
� �
�
�� ( ) � ( ) ( )
( )
( , )
f Ay f Ay k s y y
s Vy y k
1 2 2 1 1 2
1 2 � �
� �� �
V y V
k k
f Ay H
2
2� ( ) ( )� . (15)
Èç ôîðìóë (14), (15) ïîëó÷àåì íåðàâåíñòâà (13).
Ëåììà äîêàçàíà.
Íåïîñðåäñòâåííî èç ñîîòíîøåíèé (7), (9), (13) âûòåêàþò ñëåäóþùàÿ òåîðåìà,
óñòàíàâëèâàþùàÿ ÿâíîå âûðàæåíèå, à òàêæå îöåíêè îòíîñèòåëüíîãî ðàññòîÿíèÿ
ìåæäó áóëåâîé ôóíêöèåé è ìíîæåñòâîì k-ìåðíûõ ôóíêöèé.
Òåîðåìà 1. Äëÿ ëþáûõ f Bn� , k n� �0 1, ñïðàâåäëèâû ñîîòíîøåíèÿ
d f B l Hn k
H L
f
n k
( , ) / max ( ),
,
�
�
�
�
�
�
�
�
�
��
1 2 1 ,
(16)
1 2 1 1 2 11 2/ max ( ( )) ( , ) /
,
/
,
�
�
�
�
�
�
�
�
� � �
�
�H L
f n k
n k
H d f B� max ( )
,H L
f
n k
H
�
�
�
�
�
�
�
�
�� , (17)
ãäå l Hf ( ) îïðåäåëÿåòñÿ ïî ôîðìóëå (8), à � f H( ) — ïî ôîðìóëå (3).
Îòìåòèì, ÷òî ïðè k �1 ðàâåíñòâî (16) ïî ñóùåñòâó ñîâïàäàåò ñ èçâåñòíîé ôîðìó-
ëîé äëÿ îòíîñèòåëüíîãî ðàññòîÿíèÿ ìåæäó áóëåâîé ôóíêöèåé è ìíîæåñòâîì àôôèííûõ
ôóíêöèé îò n ïåðåìåííûõ. Äåéñòâèòåëüíî, åñëè H n� �{ , } ,0 1� � , ãäå � � 0, òî íà
îñíîâàíèè âòîðîãî ðàâåíñòâà (8)
l H f f f f ff ( ) / (| � ( ) � ( )| | � ( ) � ( )| ) max{| � ( )�
� �1 2 0 0 0� � | , | � ( )|}f � ,
îòêóäà ñëåäóåò
d f B l Hn
H
f
n
( , ) / max ( ) / max,
,
1 1 2 1 1 2 1
1
�
�
�
�
��
�
�
�� �
�
� �� � Vn
f| � ( )|�
�
�
��
�
�
�� .
Îòìåòèì òàêæå, ÷òî ïðè k �1íèæíÿÿ ãðàíèöà (17) äîñòèãàåòñÿ äëÿ ëþáîé óðàâ-
íîâåøåííîé ôóíêöèè f Bn� . Êðîìå òîãî, îáà íåðàâåíñòâà (17) îáðàùàþòñÿ â ðà-
âåíñòâà, åñëè f — k-ìåðíàÿ ôóíêöèÿ, k n� �0 1, .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 7
Ïðè k n� �1 ôîðìóëà (16) ïðèâîäèò ê ñîîòíîøåíèþ äëÿ îòíîñèòåëüíîãî ðàñ-
ñòîÿíèÿ ìåæäó ôóíêöèåé f è ìíîæåñòâîì àëãåáðàè÷åñêè âûðîæäåííûõ ôóíêöèé,
ïîëó÷åííîìó ðàíåå â [5].
Ñëåäñòâèå 3 [5]. Äëÿ ëþáîé ôóíêöèè f Bn� âûïîëíÿåòñÿ ðàâåíñòâî
d f B wt D fn n
u V
u
n
( , ) / min ( ),
\{ }
�
�
�
1
0
1 2 ,
ãäå D fu — ïðîèçâîäíàÿ ôóíêöèè f ïî íàïðàâëåíèþ u .
Äîêàçàòåëüñòâî. Ïóñòü L u n� �{ , } ,0 1� , ãäå u � 0, è V L L Ln s s/ {� � � � : s Vn� �1}.
Ñîãëàñíî ïåðâîìó ðàâåíñòâó (8)
l Lf
n
s V
f x
x L
n f
n s
s( ) ( ) ( )( ) (� � �
�
�
��
�
�
��� ��
� �
�
�
� �2 1 2 1
1
�� �) ( )
( )
� ��
� �
� 1
1
f u
s V
s
n
�
� � � � � � � ��
�
�2 2 01
1
n
n s s
n
n us V f f u x V D f x#{ : ( ) ( )} #{ : ( ) }� � 1�wt D fu( ) .
Ñëåäîâàòåëüíî, íà îñíîâàíèè ôîðìóëû (16)
d f B l Ln n
L
f
n
( , ) / max ( ),
,
�
�
��
�
�
�
��
�
�
�� �1 1 2 1
1�
1 2 1 1
0
/ max ( ( ))
\ { }
� �
�
�
��
�
�
���u V
u
n
wt D f =
1 2
0
/ min ( )
\ { }
�u V
u
n
wt D f ,
÷òî è òðåáîâàëîñü äîêàçàòü.
ÑÂßÇÜ ÌÅÆÄÓ ÄÎÏÓÑÒÈÌÛÌÈ ÏÎÄÏÐÎÑÒÐÀÍÑÒÂÀÌÈ È ÌÅÒÐÈ×ÅÑÊÈÌÈ
ÕÀÐÀÊÒÅÐÈÑÒÈÊÀÌÈ ÏÐÎÈÇÂÎÄÍÛÕ ÏÎ ÍÀÏÐÀÂËÅÍÈßÌ ÁÓËÅÂÛÕ ÔÓÍÊÖÈÉ
Ñîãëàñíî îïðåäåëåíèþ 3 è ëåììå 3 íàõîæäåíèå k-ìåðíûõ ôóíêöèé, ðàñïîëîæåí-
íûõ îò çàäàííîé ôóíêöèè f Bn� íà ðàññòîÿíèè íå áîëåå 1 2 1/ ( )
�� , �� ( , )0 1 ,
ñâîäèòñÿ ê ïîñòðîåíèþ k-ìåðíûõ ïîäïðîñòðàíñòâ âåêòîðíîãî ïðîñòðàíñòâà Vn ,
�-äîïóñòèìûõ äëÿ ôóíêöèè f . Äåéñòâèòåëüíî, êàæäîé ôóíêöèè g g A� �, , óäîâ-
ëåòâîðÿþùåé óñëîâèþ d f g( , ) / ( )�
�1 2 1 � , ñîîòâåòñòâóåò (ïî êðàéíåé ìåðå
îäíî) �-äîïóñòèìîå ïîäïðîñòðàíñòâî H C A� ( ) . Ïðè ýòîì äëÿ êàæäîãî òàêîãî
ïîäïðîñòðàíñòâà H ëåììà 3 ïîçâîëÿåò ïîñòðîèòü âñå áëèæàéøèå ê f k-ìåðíûå
ôóíêöèè g g A� �, òàêèå, ÷òî H C A� ( ) è (êàê ñëåäñòâèå) d f g( , ) / ( )�
�1 2 1 � .
Íèæå äîêàçàíà òåîðåìà, óñòàíàâëèâàþùàÿ ñïîñîá íàõîæäåíèÿ âñåõ �-äîïó-
ñòèìûõ ïîäïðîñòðàíñòâ äëÿ çàäàííîé áóëåâîé ôóíêöèè.
Äëÿ ëþáûõ f Bn� , �� ( , )0 1 îáîçíà÷èì
�( f V wt D fn, ) { : ( ) }� � ��� � � . (18)
Òåîðåìà 2. Åñëè ïîäïðîñòðàíñòâî H n k�� , ÿâëÿåòñÿ �-äîïóñòèìûì äëÿ ôóíêöèè
f Bn� , òî H f� � ��( , )1 � . Ïðè ýòîì åñëè L n n k� �� , è L f�
�� ( , / ( ))1 2 1 � , òî
L� — �-äîïóñòèìîå ïîäïðîñòðàíñòâî äëÿ ôóíêöèè f .
Äîêàçàòåëüñòâî. Ïóñòü ñóùåñòâóåò ïàðà ( , )� A B Fk n k� � � òàêàÿ, ÷òî
rank A k� , H C A� ( ) è d f g A( , ) / ( ),� ��
�1 2 1 . Îáîçíà÷èì
g g A� �, , g x g x( ) ( ) ( )� �� � , f x f x( ) ( ) ( )� �� � , x Vn, �� .
Ïîñêîëüêó H C A x V xAn
� �� � � �( ) { : }0 , òî íà îñíîâàíèè ôîðìóëû (6) äëÿ ëþ-
áîãî �� �H âûïîëíÿåòñÿ ðàâåíñòâî g g( )� � . Ñëåäîâàòåëüíî, äëÿ êàæäîãî óêà-
çàííîãî �
wt D f wt f f wt f g g f( ) ( ) ( )( ) ( ) ( )
�
� � �� � � � � � �
� �
� � � �wt f g wt g f d f g( ) ( ) ( , )( ) ( )� � �2 1 ,
îòêóäà ñëåäóåò, ÷òî H f� � ��( , )1 � .
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6
Ïóñòü äàëåå L n n k� �� , è äëÿ ëþáîãî ��L âûïîëíÿåòñÿ íåðàâåíñòâî
wt D f( ) / ( )� ��
�1 2 1 . Ïîëàãàÿ H L� � , íà îñíîâàíèè íèæíåé ãðàíèöû (13) è ôîð-
ìóëû (4) ïîëó÷èì
l H Hf f
n k n D f x
x VL n
( ) ( ) ( )( ) ( ) � � �� � �
��
��� �
�
2 2 1 2 1 2� �
�
� �( ) ( ( ))n k
L
wt D f�
�
�.
Îòñþäà â ñèëó ñëåäñòâèÿ 2 âûòåêàåò, ÷òî ïîäïðîñòðàíñòâî H ÿâëÿåòñÿ �-äîïó-
ñòèìûì äëÿ ôóíêöèè f .
Òåîðåìà äîêàçàíà.
Ñëåäñòâèå 4. Åñëè ìíîæåñòâî �( f , )1�� íå ñîäåðæèò ïîäïðîñòðàíñòâ ðàçìåðíîñòè
n k� , òî d f Bn k( , ) / ( ), �
�1 2 1 � . Åñëè ñóùåñòâóåò ( )n k� -ìåðíîå ïîäïðîñòðàíñòâî, ñî-
äåðæàùååñÿ âî ìíîæåñòâå �( f , / ( ))1 2 1
�� , òî d f Bn k( , ) / ( ), �
�1 2 1 � .
Ïîëó÷åííàÿ òåîðåìà ïîçâîëÿåò ïðåäëîæèòü ñëåäóþùèé àëãîðèòì.
Àëãîðèòì íàõîæäåíèÿ âñåõ k-ìåðíûõ ïîäïðîñòðàíñòâ, �-äîïóñòèìûõ äëÿ
ôóíêöèè f Bn� , çàäàííîé òàáëèöåé èñòèííîñòè.
1. Âû÷èñëèâ çíà÷åíèÿ àâòîêîððåëÿöèîííîé ôóíêöèè
� f
D f x
x Vn
( ) ( )
( )� �� �
�
� 1 , ��Vn ,
ñ ïîìîùüþ àëãîðèòìà áûñòðîãî ïðåîáðàçîâàíèÿ Àäàìàðà (ñì. íàïðèìåð,
[12, c. 217]), ïîñòðîèòü ìíîæåñòâî � ( f , )1�� .
2. Åñëè ýòî ìíîæåñòâî íå ñîäåðæèò ïîäïðîñòðàíñòâ ðàçìåðíîñòè n k� , òî äëÿ
ôóíêöèè f íå ñóùåñòâóåò �-äîïóñòèìûõ k-ìåðíûõ ïîäïðîñòðàíñòâ. Â ïðîòèâíîì ñëó-
÷àå ïîñòðîèòü ìíîæåñòâî, ñîñòîÿùåå èç âñåõ ïîäïðîñòðàíñòâ L� òàêèõ, ÷òî L n n k� �� ,
è ëèáî L f�
��( , / ( ))1 2 1 � , ëèáî L f f� �
�� �( (, ) \ , / ( ))1 1 2 1� � è l Lf ( )� �.
Âñå óêàçàííûå ïîäïðîñòðàíñòâà è òîëüêî îíè ÿâëÿþòñÿ èñêîìûìè.
Îòìåòèì, ÷òî âîçìîæíîñòü ïðèìåíåíèÿ ýòîãî àëãîðèòìà íà ïðàêòèêå îïðåäå-
ëÿåòñÿ ñòðîåíèåì ìíîæåñòâ (18). Íèæå èçëîæåíû ðåçóëüòàòû, ïîçâîëÿþùèå ïðåä-
ëîæèòü áîëåå ýôôåêòèâíûé àëãîðèòì íàõîæäåíèÿ ðÿäà âûñîêîâåðîÿòíûõ k-ìåðíûõ
ïðèáëèæåíèé áóëåâûõ ôóíêöèé.
ÓÑÈËÅÍÈÅ ÒÅÎÐÅÌÛ ÃÎÏÀËÀÍÀ ÄËß ÁÓËÅÂÛÕ ÔÓÍÊÖÈÉ
 ðàáîòå [2, ï. 4] äîêàçàíà òåîðåìà, îïèñûâàþùàÿ ñòðîåíèå îïðåäåëåííûõ
k-ìåðíûõ ïðèáëèæåíèé ôóíêöèé îò n ïåðåìåííûõ íàä ïðîèçâîëüíûì êîíå÷íûì
ïîëåì. Ïðèìåíèòåëüíî ê áóëåâûì ôóíêöèÿì ýòà òåîðåìà èìååò ñëåäóþùèé âèä.
Òåîðåìà 3 [2]. Ïóñòü f Bn� , g Bn k� , , deg g � d è d f g d( , ) ( )� ��2 1 � , ãäå
1� �d k, �� ( , )0 1 . Òîãäà
I I fg g
k d� � � �� � �
!
"
#
$
� � �: | � ( )| /1
8 2
2 2 2 .
Èç òåîðåìû 3 ñëåäóåò, ÷òî êàæäàÿ ôóíêöèÿ g , óäîâëåòâîðÿþùàÿ åå óñëîâèþ,
äîïóñêàåò òàêîå ïðåäñòàâëåíèå (6), â êîòîðîì ñòîëáöû ìàòðèöû A ïðèíàäëåæàò
ìíîæåñòâó
S V ff n( ) { : | � ( )| } � � � � (19)
ïðè �� � � �
1
2 21
8 2
2 k d/ . Ïîñêîëüêó | ( )|S f � �2 äëÿ ëþáûõ f Bn� ,
� ( , )0 1 , òî ÷èñëî óêàçàííûõ ôóíêöèé g îãðàíè÷åíî ñâåðõó âåëè÷èíîé
�
1
2 2 7 42
2�
��k k k d kN k d N k d( , ) ( , )( ) , (20)
ãäå N k d
k
i
i
d
( , ) �
��
�
� �
�
�
�2 0 — ÷èñëî áóëåâûõ ôóíêöèé ñòåïåíè íå âûøå d îò k ïåðåìåí-
íûõ. Òàêèì îáðàçîì, äëÿ íàõîæäåíèÿ âñåõ óêàçàííûõ ôóíêöèé äîñòàòî÷íî ïåðå-
áðàòü âñåâîçìîæíûå íàáîðû ( , , , )� � �1 � k , ãäå � � 1 1, , ( )� k fS� , ��Bk ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 9
deg � � d , çàäàòü ôóíêöèþ g ïî ôîðìóëå g x x xk( ) ( , , )� � � �1 � , x Vn� , è ïðîâå-
ðèòü óñëîâèå d f g d( , ) ( )� ��2 1 � . Åñëè êàæäóþ òàêóþ ïðîâåðêó ïðèíÿòü çà îäíó
îïåðàöèþ, òî òðóäîåìêîñòü îïèñàííîãî àëãîðèòìà ïîñòðîåíèÿ âñåõ ôóíêöèé g ïî
çàäàííîìó ìíîæåñòâó S f ( ) (ñì. [2, ï. 4]) îöåíèâàåòñÿ ñâåðõó ïî ôîðìóëå (20).
Îñíîâíûì ðåçóëüòàòîì íàñòîÿùåãî ðàçäåëà ÿâëÿåòñÿ òåîðåìà, óñèëèâàþùàÿ
òåîðåìó 3 è (êàê ñëåäñòâèå) âåðõíþþ îöåíêó (20). Ïðåæäå ÷åì ñôîðìóëèðîâàòü ýòó
òåîðåìó, äàäèì îäíî îïðåäåëåíèå è óñòàíîâèì ðÿä âñïîìîãàòåëüíûõ ðåçóëüòàòîâ.
Äëÿ ëþáîé ôóíêöèè g Bn� ïîëîæèì �( ) / min ( )g wt D g
I g
�
%
1 2
�
� .
Îòìåòèì, ÷òî åñëè g — ñòðîãî k-ìåðíàÿ ôóíêöèÿ è (6) — åå íåïðèâîäèìîå
ïðåäñòàâëåíèå, òî wt D g wt D A( ) ( )� � �� äëÿ ëþáîãî ��Vn , îòêóäà â ñèëó ñëåä-
ñòâèé 1 è 3 âûòåêàåò, ÷òî
�( ) / min ( ) ( , )
\{ }
,g wt D d B
a V
a k k
k
�
�
�
�1 2
0
1� � .
Îïðåäåëåíèå 4. Íàçîâåì ôóíêöèþ g Bn k� , ñïåöèàëüíûì ( , )k � -ïðèáëèæåíèåì
ôóíêöèè f Bn� , åñëè g — ñòðîãî k-ìåðíàÿ ôóíêöèÿ è
d f g g( , ) ( )( )� �� 1 � , �� ( , )0 1 .
Êàê ïîêàçûâàåò ñëåäóþùàÿ ëåììà, êëàññ ñïåöèàëüíûõ ïðèáëèæåíèé âêëþ÷àåò
ôóíêöèè, óäîâëåòâîðÿþùèå óñëîâèþ òåîðåìû 3.
Ëåììà 5. Ïóñòü f Bn� , g Bn k� , — ñòðîãî k-ìåðíàÿ ôóíêöèÿ, deg g d� è
d f g d( , ) ( )� ��2 1 � , ãäå 1� �d k , �� ( , )0 1 . Òîãäà g ÿâëÿåòñÿ ñïåöèàëüíûì
( , )k � -ïðèáëèæåíèåì ôóíêöèè f .
Äîêàçàòåëüñòâî. Åñëè �% I g , òî D g� � 0. Ïîñêîëüêó ïðè ýòîì deg( )D g d� � �1,
òî íà îñíîâàíèè ëåììû 1 ñïðàâåäëèâî ñîîòíîøåíèå �( ) / min ( )g wt D g
I
d
g
�
%
�1 2 2
�
� ,
÷òî è òðåáîâàëîñü äîêàçàòü.
Ñëåäóþùàÿ ëåììà èãðàåò êëþ÷åâóþ ðîëü â äîêàçàòåëüñòâå îñíîâíîé òåîðåìû
íàñòîÿùåãî ðàçäåëà.
Ëåììà 6. Ïóñòü f Bn� , g — ñïåöèàëüíîå ( , )k � -ïðèáëèæåíèå ôóíêöèè f
è g x xA( ) ( )� � , x Vn� , — íåïðèâîäèìîå ïðåäñòàâëåíèå ôóíêöèè g . Ïóñòü äàëåå
g x xA0 ( ) ( )� � , x Vn� , — k-ìåðíàÿ ôóíêöèÿ, áëèæàéøàÿ ê f íà ìíîæåñòâå
B C An k, ( ( )) . Äëÿ ëþáûõ a Vk� \ { }0 , t �N îáîçíà÷èì
M a u ut
k
s
s
s V
s a
s a t
k
( ) ( ( ) ( ) )( ) ( )� � � ��
�
�
��2 1 1 2� � ,
ãäå
u f Ays
sy
y Vk
� �
�
�
��
�
�
��
�
� � ( )( )1 , s Vk� .
Òîãäà äëÿ ëþáîãî �� ( , )0 1 âûïîëíÿþòñÿ ñëåäóþùèå íåðàâåíñòâà:
( ) ( )
( , )
( ) max( )2
2
1
22 2 1 1� �
�
t
a t
t kwt D
d f g
M a�
�
�
�
�
�
�
� � � �
y V
ay
t
k
f Ay
�
�
�
�
�
�
�
�
�
�
�
�:
| � ( )|
1
2
. (21)
Äîêàçàòåëüñòâî. Óáåäèìñÿ â ñïðàâåäëèâîñòè íèæíåé ãðàíèöû (21). Îáîçíà÷èì
� � � �
s
s s
s
s a s a
s au u� �
�� � � �
�( ) ( )( ) ( ) ( ) ( )1 1 , s Vk� ,
V s V D sk a s( ) { : ( ) , }� �
�� � � 1 2 .
Âíà÷àëå äîêàæåì ñîîòíîøåíèÿ
d f g k
s
s Vk
( , ) / ( / )�
�
�
�
�2 1 2 1 1 2
, (22)
2
2
1
� �
�
k
aV wt D
d f g
# ( ) ( )
( , )
� �
�
.
(23)
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6
Ïîëîæèì H C A� ( ) , L x V xA ss n� � �{ : }, s Vk� . Ïîñêîëüêó ôóíêöèÿ g 0 ÿâëÿåò-
ñÿ áëèæàéøåé ê ôóíêöèè f íà ìíîæåñòâå B Hn k, ( ) , òî íà îñíîâàíèè ëåììû 3 âû-
ïîëíÿþòñÿ ðàâåíñòâà
� ( )( ) ( ) ( )f Ay usy
y V
s
s
k
� � �
�
� 1 1 � , s Vk� . (24)
Èñïîëüçóÿ ôîðìóëû (11) è (24), ïîëó÷àåì
1 2 2 1� � � �� �
�
�d f g n f x g x
x Vn
( , ) ( ) ( ) ( )
� � � � �� �
��
� � ���2 1 2 1 2 1n f x g x
x Ls V
k s n k
sk
( ) ( ) ( )( ) ( ) ( ) ( )� f x
x Ls V sk
( )
��
��
�
�
�
�
�
�
�
�
�
� � �
�
�
�
�
�
�
�
�
� ��
��
���2 1 1 2 1k s sy
y Vs V
kf Ay
kk
( ) � ( )( ) ( )( )� � �
( ) ( ) /s s
s V
s
k
s V
s
k k
u�
�
�
�
� ��
2 1 2 .
Èòàê, ñïðàâåäëèâî ðàâåíñòâî (22).
Äëÿ äîêàçàòåëüñòâà ñîîòíîøåíèÿ (23) çàìåòèì, ÷òî
2 2 1 2 1� � �� � � � � �k k
k a
k
k a sV s V D s s V D s# ( ) #{ : ( ) } #{ : ( ) ,� � �
� 2�}
� � � ��wt D s Va
k
k s( ) #{ : }�
�2 2
� � �
�
�
��wt D s Va
k
k s( ) #{ : / ( / ) / ( )}�
�2 1 2 1 1 2 1 2 1 ,
ïðè÷åì 1 2 1 1 2 0/ ( / )
�
s äëÿ ëþáîãî s Vk� . Ñëåäîâàòåëüíî,
2 1 2 1 1 2 1 2 1
2
1
2 1 2 1� ��
�
�
� �
�
�k
k s
ks V#{ : / ( / ) / ( )} / (
�
�
1 2/ )
�
�
�
�
�
�
�
�
�
�
s
s Vk
,
ñïðàâåäëèâîñòü ñîîòíîøåíèÿ (23) âûòåêàåò èç ðàâåíñòâà (22).
Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà íèæíåé ãðàíèöû (21) âîñïîëüçóåìñÿ íåðàâåí-
ñòâîì
M a u ut
k
s
s V
s a
D s ta( ) ( ( ) )
( )
( ) � ��
�
��2 1 2
�
�
(25)
è çàìåòèì, ÷òî
| ( ) |
( )
u us s a
D sa� � � 1 2
� � , s V� ( )� . (26)
Äåéñòâèòåëüíî, åñëè s V� ( )� è D sa �( ) �1, òî
| ( ) |
( )
u u u us s a
D s
s s a s
a� � �
� �1 2
�
� .
Åñëè s V� ( )� è D sa �( ) � 0 , òî | ( ) | | |
( )
u u u us s a
D s
s s a
a� � � �� �1
�
. Ïðè ýòîì
D sa �( ) �1,
�s 2 è, ñëåäîâàòåëüíî, ( ) ( )( ) ( ) ( ) ( )� � � �� � � �1 1� � � �s s s a s a ,
�� �
s
s s
s s au u� � � �
�( ) ( )( ) ( )1 2 . Íî òîãäà | | | |
�s s s au u� � � 2 , ÷òî è òðåáîâà-
ëîñü äîêàçàòü. Òàêèì îáðàçîì, â ñèëó ñîîòíîøåíèé (23), (25), (26) ñïðàâåäëèâà
íèæíÿÿ ãðàíèöà (21).
Äëÿ äîêàçàòåëüñòâà âåðõíåé ãðàíèöû (21) âîñïîëüçóåìñÿ ðàâåíñòâàìè (24).
 ðåçóëüòàòå ïîëó÷èì, ÷òî
M a f Ay f Ayt
k sy
y V
s a y
y Vk k
( ) � ( )( ) � ( )( )( )� � � �
�
�
�
�
�
�
� �2 1 1�
�
�
�
�
�
�
�
�
s V
t
k
2
� � � �
�
�
�
�
�
�
�
�
�
��
��2 1 1 1
2
k sy
y V
ay
s V
t
f Ay
kk
� ( )( ) ( ( ) ) � �
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
��2 12
1
2
t k sy
y V
ay
s V
t
f Ay
kk
� ( )( )
:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 11
�
��
�
�
�
�
�2 12
1 2
1 2
1
t k
s V
t
s y y
yk
tf Ay f Ay� ( ) � ( )( )
( )
( �
�
� �
� � �
� �
y V
ay ay
t k
t
t
2
2
1 2 1
) :
�
�
�� �
� �
22
1 2 1 1 2 1
1 2
t
t t
y y
f Ay f Ay f Ay Ay� ( ) � ( ) � ( )
( � t k
t
t
V
ay ay
�
�
�
�
� � �
� �
1
2 1
1 2 1 1
) :
�
�
�
�
�
�
�
�
�
�
�
��
�� � ��
22
11 2 1
2
t
y V
ayy y V
k
t k
f Aymax | � ( )|
:
( )�
t
t
k
ay ay
t
t k t
y V
ay
�
�� � �
� �
�
�
� �
1
1 2 1 1
2
2 1 2 1
1
2
:
( )( )
:
max |
�
� ( )|f Ay
t
�
�
�
�
�
�
�
�
�
�
2
.
Ëåììà ïîëíîñòüþ äîêàçàíà.
Ñëåäóþùàÿ òåîðåìà îáîáùàåò è îäíîâðåìåííî óñèëèâàåò òåîðåìó 3.
Òåîðåìà 4. Ïóñòü g — ñïåöèàëüíîå ( , )k � -ïðèáëèæåíèå ôóíêöèè f Bn� . Òîãäà
I x I f xg g
� �� & � '{ : | � ( )| } 0 , (27)
ãäå
� �0
1 2 3 2 1 22
4
3 3
2� �
!
"
#
$
� �max , ( )/ / /k k g� . (28)
Äîêàçàòåëüñòâî. Ïóñòü g x xA( ) ( )� � , x Vn� — íåïðèâîäèìîå ïðåäñòàâëåíèå
ôóíêöèè g. Ñîãëàñíî ñëåäñòâèþ 1 âûïîëíÿåòñÿ ðàâåíñòâî I C Ag
� � ( ) . Îáîçíà÷èì
W x C A f x� & � '{ ( ): | � ( )| } 0 è çàìåòèì, ÷òî ñóùåñòâóåò �( � 0 òàêîå, ÷òî
W x C A f x� & � � � ( '{ ( ): | � ( )| } �0 .
Ïðåäïîëîæèì, ÷òî ðàâåíñòâî (27) íå âûïîëíÿåòñÿ, ò.å. W C A)
�
( ) . Òîãäà
W C A x V xAn
�
�
�* � � �( ) { : }0 è ñóùåñòâóåò âåêòîð �� �W òàêîé, ÷òî a A� �� 0 .
Îòñþäà ñëåäóåò, ÷òî äëÿ ëþáîãî y Vk� , óäîâëåòâîðÿþùåãî óñëîâèþ ay �1, ñïðàâåä-
ëèâî íåðàâåíñòâî | � ( )|f Ay � � ( �0 . Äåéñòâèòåëüíî, ïîñêîëüêó 1 0� � �ay Ay�( ) è
�� �W , òî Ay W% , à çíà÷èò | � ( )|f Ay � � ( �0 .
Èòàê, èìååò ìåñòî íåðàâåíñòâî
max | � ( )|
:y V
ay
k
f Ay
�
�
� � (
1
0 � .
Îòñþäà íà îñíîâàíèè îöåíîê (21) ñëåäóåò, ÷òî äëÿ ëþáûõ �� ( , )0 1 , t �N ñïðà-
âåäëèâî íåðàâåíñòâî
( ) ( )
( , )
( )( )2
2
1
22 2 1 1
0
2� �
�
�t
a
t k twt D
d f g
�
�
�
�
�
�
�
� � � (�
,
êîòîðîå çàïèøåì â âèäå
2
2
1
2
1
2
2 1
2
1
2
0� �
�
�wt D
d f g
a
t
k
t
t t( )
( , )
( )�
�
�
�
�
�
�
� � � (
�
.
Äàëåå, ïî óñëîâèþ òåîðåìû èìååì d f g g( , ) ( )( )� �� 1 � ; êðîìå òîãî, èç ðàâåíñòâà
I C Ag
� � ( ) , óñëîâèÿ a A� �� 0 è îïðåäåëåíèÿ ïàðàìåòðà �( )g âûòåêàåò, ÷òî
wt D wt D g ga( ) ( ) ( )� �� 2� . Ñëåäîâàòåëüíî, äëÿ ëþáîãî � �� ( , )0
wt D
d f g
g
g
a( )
( , )
( )
( )( )
�
�
�
�
�
�
�
�
�
�
2
1
2
2 1
1
�
�
2 1
1
1
2 0� �( ) ( )( )g g�
�
�
�
�
�
�
�
� � �
�
�
� � .
Èòàê, äëÿ ëþáûõ � �� ( , )0 , t �N ñïðàâåäëèâî íåðàâåíñòâî
2 2 2
1
2
2 1
2
1
2
0� � � �( ( )( )) ( )� g t
k
t
t t� � � (
�
. (29)
Ïåðåõîäÿ ê ïðåäåëó ïðè t �+ â îáåèõ ÷àñòÿõ íåðàâåíñòâà (29), ïîëó÷aeì, ÷òî
2 2 0� �� � (k ( ) äëÿ ëþáîãî � �� ( , )0 è, ñëåäîâàòåëüíî, 21
0
� � � (k � � .
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6
Íàêîíåö, ïîëàãàÿ â (29) t �1, � � �
� 2 , ïîëó÷aeì
4
3 3
2 2 1 2
0
� � � (k g/ /( )� �
� �� .
Òàêèì îáðàçîì, ñïðàâåäëèâî íåðàâåíñòâî
max{ , ( ) }/ /2
4
3 3
21 2 1 2
0
� � � � (k k g� � �
� �� ,
êîòîðîå, îäíàêî, ïðîòèâîðå÷èò ôîðìóëå (28). Òàêèì îáðàçîì, ïðåäïîëîæåíèå î òîì,
÷òî W C A� ( ) , ÿâëÿåòñÿ ëîæíûì; ñëåäîâàòåëüíî, âûïîëíÿåòñÿ ðàâåíñòâî (27).
Òåîðåìà äîêàçàíà.
Íåïîñðåäñòâåííî èç òåîðåìû 4 è ëåììû 5 ïîëó÷àåì ñëåäóþùèå óòâåðæäåíèÿ.
Ñëåäñòâèå 5. Ïóñòü f Bn� , g Bn k� , — ñòðîãî k-ìåðíàÿ ôóíêöèÿ, deg g d� è
d f g d( , ) ( )� ��2 1 � , ãäå 1� �d k , �� ( , )0 1 . Òîãäà ôóíêöèÿ g äîïóñêàåò òàêîå ïðåä-
ñòàâëåíèå (6), â êîòîðîì ñòîëáöû ìàòðèöû A ÿâëÿþòñÿ ëèíåéíî íåçàâèñèìûìè âåêòîðàìè,
ïðèíàäëåæàùèìè ìíîæåñòâó S f ( ) 0 âèäà (19), ãäå 0 îïðåäåëÿåòñÿ ïî ôîðìóëå (28).
Ñëåäñòâèå 6. Ïóñòü f Bn� , g Bn k� , , deg g d� è d f g d( , ) ( )� ��2 1 � , ãäå
1� �d k, �� ( , )0 1 . Òîãäà ôóíêöèÿ g äîïóñêàåò ïðåäñòàâëåíèå (6), â êîòîðîì ñòîëá-
öû ìàòðèöû A ïðèíàäëåæàò ìíîæåñòâó S f ( ) ïðè
� �� � �
!
"
#
$
� � �
0
1 2 22
4
3 3
2 3 2max , / / /k k d .
 ÷àñòíîñòè, ÷èñëî óêàçàííûõ ôóíêöèé g îãðàíè÷åíî ñâåðõó âåëè÷èíîé
� �
0
2 2 2 2 1 32 2
2 2� � �
��k k k k k k d kN k d N k d( , ) min { , } ( , )( ) , (30)
ãäå N k d
k
i
i
d
( , ) �
��
�
� �
�
�
�2 0 — ÷èñëî áóëåâûõ ôóíêöèé ñòåïåíè íå âûøå d îò k ïåðåìåííûõ.
Êàê âèäíî èç ôîðìóë (20) è (30), ïîëó÷åííàÿ îöåíêà êîëè÷åñòâà k-ìåðíûõ
ôóíêöèé, óäîâëåòâîðÿþùèõ óñëîâèþ òåîðåìû 3, çàìåòíî ëó÷øå îöåíêè èç [2]. Áî-
ëåå òîãî, ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Ñëåäñòâèå 7. Ïóñòü f Bn� , k n� �1 1, . Òîãäà êàæäàÿ ôóíêöèÿ g B Bn k n k� �, ,\ 1 ,
óäîâëåòâîðÿþùàÿ óñëîâèþ d f g k( , ) ( )� ��2 1 � , �� ( , )0 1 , äîïóñêàåò òàêîå ïðåäñòàâëå-
íèå (6), â êîòîðîì ñòîëáöû ìàòðèöû A ïðèíàäëåæàò ìíîæåñòâó S f
k( )21� � . Ïðè ýòîì
÷èñëî óêàçàííûõ ôóíêöèé íå ïðåâîñõîäèò 2 2 12 2 22k k k k� �
� ( ) .
Äîêàçàòåëüñòâî. Ïóñòü g g A� �, — ñòðîãî k-ìåðíàÿ ôóíêöèÿ òàêàÿ, ÷òî
d f g k( , ) ( )� ��2 1 � . Åñëè g g A( � ( (� , è d f g k( , ) ( )( � ��2 1 � , òî
2 2 2 2 1 2k k kd d g g d g f d f g( , ) ( , ) ( ( , ) ( , )) ( )� � �( � ( �
( � � � ,
îòêóäà ñëåäóåò, ÷òî 2 1k d ( , )� �( � . Òàêèì îáðàçîì, äëÿ ëþáîé n k� -ìàòðèöû A
ðàíãà k ñóùåñòâóåò íå áîëåå 2 1k
ôóíêöèé ��Bk , óäîâëåòâîðÿþùèõ óñëîâèþ
d f g A
k( , ) ( ),� �� ��2 1 . Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà îñòàåòñÿ ïðèìåíèòü òåî-
ðåìó 4. Îòìåòèì, ÷òî èìïëèêàöèÿ
( ( , ) ( ), ( ) ( , , ), ) ( , ,d f g g x x x x Vk
k n k� � � � , ��2 1 1 1� � � � � �� � S f
k( )21� � ),
ñïðàâåäëèâàÿ ïðè âûïîëíåíèè óñëîâèÿ ñëåäñòâèÿ 7, ïðåîáðàçóåòñÿ â ðàâíîñèëü-
íîå óòâåðæäåíèå ïðè k �1: àôôèííàÿ ôóíêöèÿ ñ âåêòîðîì êîýôôèöèåíòîâ
��Vn \ { }0 òîãäà è òîëüêî òîãäà íàõîäèòñÿ îò ôóíêöèè f Bn� íà îòíîñèòåëüíîì
ðàññòîÿíèè íå áîëåå 1 2 1/ ( )
�� , �� ( , )0 1 , êîãäà | � ( )|f � � . Ïðè ýòîì îöåíêà èç
òåîðåìû 3 ïîçâîëÿåò ëèøü óòâåðæäàòü, ÷òî | � ( )| /f � �
1 16 2 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6 13
ÇÀÊËÞ×ÅÍÈÅ
Îñíîâíûìè ðåçóëüòàòàìè ñòàòüè ÿâëÿþòñÿ òåîðåìû 1, 2 è 4. Ïåðâàÿ èç íèõ ñî-
äåðæèò ÿâíîå âûðàæåíèå, à òàêæå îöåíêè îòíîñèòåëüíîãî ðàññòîÿíèÿ ìåæäó áó-
ëåâîé ôóíêöåé è ìíîæåñòâîì k-ìåðíûõ ôóíêöèé îò n ïåðåìåííûõ. Âòîðàÿ òåî-
ðåìà óñòàíàâëèâàåò ñâÿçü ìåæäó k-ìåðíûìè ïðèáëèæåíèÿìè ïðîèçâîëüíîé
ôóíêöèè f Bn� è ìåòðè÷åñêèìè ñâîéñòâàìè åå ïðîèçâîäíûõ ïî íàïðàâëåíèÿì.
Òåîðåìà 4 îïèñûâàåò ñòðîåíèå ñïåöèàëüíûõ k-ìåðíûõ ïðèáëèæåíèé ôóíêöèè
f Bn� , çàìåòíî óñèëèâàÿ ðàíåå èçâåñòíûé ðåçóëüòàò Ï. Ãîïàëàíà [2].
Ïîñòðîåíèå k-ìåðíûõ ôóíêöèé, íàõîäÿùèõñÿ îò çàäàííîé ôóíêöèè f Bn� íà
ðàññòîÿíèè íå áîëåå 1 2 1/ ( )
�� , �� ( , )0 1 , ñâîäèòñÿ ê ïîñòðîåíèþ �-äîïóñòèìûõ äëÿ
f k-ìåðíûõ ïîäïðîñòðàíñòâ âåêòîðíîãî ïðîñòðàíñòâà Vn . Äëÿ íàõîæäåíèÿ âñåõ òà-
êèõ ïîäïðîñòðàíñòâ ìîæíî ïðèìåíÿòü îïèñàííûé â ñòàòüå àëãîðèòì, ñëîæíîñòü
êîòîðîãî çàâèñèò îò ñòðîåíèÿ ìíîæåñòâ âèäà (18).
Òåîðåìà 4 è ñëåäñòâèÿ èç íåå ñîäåðæàò âàæíóþ èíôîðìàöèþ î ñòðîåíèè
k-ìåðíûõ ôóíêöèé ñòåïåíè d, íàõîäÿùèõñÿ íà ðàññòîÿíèè íå áîëåå 2 1n d� �( )� îò
çàäàííîé áóëåâîé ôóíêöèè n ïåðåìåííûõ, 1� � �d k n, �� ( , )0 1 . Ýòà èíôîðìàöèÿ
ïîçâîëÿåò óñòàíîâèòü íåòðèâèàëüíûå âåðõíèå îöåíêè êîëè÷åñòâà óêàçàííûõ k-ìåð-
íûõ ôóíêöèé è ñóùåñòâåííî ïîâûñèòü ýôôåêòèâíîñòü àëãîðèòìà èõ ïîñòðîåíèÿ,
ïðåëîæåííîãî â [2].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. T e s t i n g Fourier dimensionality and sparsity / P. Gopalan, R. O’Donnel, A. Servedio, A. Shpilka,
K. Wimmer // SIAM J. on Comput. — 2011. — 40(4). — P. 1075–1100.
2. G o p a l a n P . A Fourier-analytic approach to Reed-Muller decoding // Annual IEEE Symp. on Foundation
in Computer Science. — FOCS 2010, Proceedings. — Berlin: Springer–Verlag, 2010. — P. 685–694.
3. L e c h n e r R . L . Harmonic analysis of switching functions // Recent Developments in Switching Theory.
— New–York: Academic Press, 1971. — P. 122–228.
4. D a w s o n E . , W u C . K . Construction of correlation immune Boolean functions // Inform. and
Communicat. Security, Proceedings. — Berlin: Springer–Verlag, 1997. — P. 170–180.
5. À ë å ê ñ å å â Å . Ê . Î íåêîòîðûõ ìåðàõ íåëèíåéíîñòè áóëåâûõ ôóíêöèé // Ïðèêëàä. äèñêðåòíàÿ ìàòå-
ìàòèêà. — 2011. — ¹ 2(12). — Ñ. 5–16.
6. D a e m e n J . , G o v a e r t s R . , V a n d e w a l l e J . Resynchronization weaknesses in synchronous stream
ciphers // Advances in Cryptology — EUROCRYPT’93, Proceedings. — Berlin: Springer–Verlag, 1993.
— P. 159–167.
7. G o l i ñ' J . , M o r g a r i G . On the resynchronization attack // Fast Software Encryption. — FSE’03,
Proceedings. — Berlin: Springer–Verlag, 2003. — P. 100–110.
8. À ë å ê ñ å å â Å . Ê . Îá àòàêå íà ôèëüòðóþùèé ãåíåðàòîð ñ ôóíêöèåé óñëîæíåíèÿ, áëèçêîé ê àëãåáðà-
è÷åñêè âûðîæäåííîé // Ñá. ñòàòåé ìîëîäûõ ó÷åíûõ ôàêóëüòåòà ÌÂÊ ÌÃÓ. — 2011. — Âûï. 8. —
Ñ. 114–123.
9. C a n t e a u t A . On the correlations between a combining function and function of fewer variables // The
2002 IEEE Inform. Theory Workshop, Proceedings. — Berlin: Springer–Verlag, 2002. — P. 78–81.
10. À ë å ê ñ å é ÷ ó ê À . Í . , Ê î í þ ø î ê Ñ . Í . Óñîâåðøåíñòâîâàííûé òåñò k-ìåðíîñòè äëÿ áóëåâûõ
ôóíêöèé // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2013. — 49, ¹ 2. — Ñ. 27–35.
11. A l e k s e y c h u k A . N . , K o n y u s h o k S . N . Fast algorithm for reconstruction of high-probable
low-dimensional approximations for Boolean functions // Modern Stochastics: Theory and Applications III,
Proceedings. — Kyiv. Taras Shevchenko National University, 2012. — P. 32.
12. Ë î ã à ÷ å â Î . À . , Ñ à ë ü í è ê î â À . À . , ß ù å í ê î Â . Â . Áóëåâû ôóíêöèè â òåîðèè êîäèðîâàíèÿ è
êðèïòîëîãèè. — Ì.: ÌÖÍÌÎ, 2004. — 470 ñ.
Ïîñòóïèëà 05.11.2013
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 6
|