Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения
Розглянуто теоретико-множинний підхід до нерозділювальної декомпозиції бульових функцій від n змінних різних форм задання, що ґрунтується на методі pq, -розбиття кон’юнктермів і понятті декомпозиційних клонів. Описано два шляхи пошуку нерозділювальної функційної декомпозиції. Сформульовано теореми п...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2009 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44365 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения / Б.Е. Рыцар // Кибернетика и системный анализ. — 2009. — № 3. — С. 15-41. — Бібліогр.: 20 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860079543931371520 |
|---|---|
| author | Рыцар, Б.Е. |
| author_facet | Рыцар, Б.Е. |
| citation_txt | Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения / Б.Е. Рыцар // Кибернетика и системный анализ. — 2009. — № 3. — С. 15-41. — Бібліогр.: 20 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто теоретико-множинний підхід до нерозділювальної декомпозиції бульових функцій від n змінних різних форм задання, що ґрунтується на методі pq, -розбиття кон’юнктермів і понятті декомпозиційних клонів. Описано два шляхи пошуку нерозділювальної функційної декомпозиції. Сформульовано теореми про нерозділювальну декомпозицію повних і частинних функцій, а також їх систем. Запропонований підхід проілюстровано на прикладах.
A set-theoretical approach to the non-disjoint decomposition of different forms of representation of Boolean functions of n variables is considered. This approach is based on the method of p,q-partition of conjuncterms and the concept of decomposition clones. Two ways of searching for some non-disjoint functional decomposition are described. Theorems on the non-disjoint decomposition of complete and partial functions and their systems are formulated. The proposed approach is illustrated by examples.
|
| first_indexed | 2025-12-07T17:15:43Z |
| format | Article |
| fulltext |
ÓÄÊ 62.519
Á.Å. ÐÛÖÀÐ
ÍÎÂÛÉ ÏÎÄÕÎÄ Ê ÄÅÊÎÌÏÎÇÈÖÈÈ ÁÓËÅÂÛÕ ÔÓÍÊÖÈÉ.
4. ÍÅÐÀÇÄÅËÈÒÅËÜÍÀß ÄÅÊÎÌÏÎÇÈÖÈß: ÌÅÒÎÄ p q, -ÐÀÇÁÈÅÍÈß1
Êëþ÷åâûå ñëîâà: íåðàçäåëèòåëüíàÿ ôóíêöèîíàëüíàÿ äåêîìïîçèöèÿ, p q, -ðàçáèå-
íèå êîíúþíêòåðìîâ áóëåâîé ôóíêöèè, òåîðåòèêî-ìíîæåñòâåííûé ïîäõîä, ðàñ-
øèðåííûå êëîíû, ñæàòûå êëîíû.
Ïðè íåðàçäåëèòåëüíîé ôóíêöèîíàëüíîé äåêîìïîçèöèè [1–3], â îòëè÷èå îò ðàçäå-
ëèòåëüíîé, íåêîòîðûå ïåðåìåííûå çàäàííîé áóëåâîé ôóíêöèè â ðåçóëüòàòå èõ
ðàçáèåíèÿ (â ïðîñòåéøåì ñëó÷àå íà äâà êëàññà) ÿâëÿþòñÿ îáùèìè äëÿ ïîä-
ôóíêöèé îò ïåðåìåííûõ ýòèõ êëàññîâ.
Çàäà÷à íåðàçäåëèòåëüíîé äåêîìïîçèöèè áóëåâûõ ôóíêöèé çàíèìàåò îñîáî
âàæíîå ìåñòî â ëîãè÷åñêîì ñèíòåçå êîìáèíàöèîííûõ ñåòåé. Ê íåé ïðèõîäèòñÿ ïðè-
áåãàòü â ñëó÷àå, êîãäà äëÿ çàäàííîãî ðàçáèåíèÿ ëèáî äëÿ âñåõ âîçìîæíûõ ðàçáèå-
íèé ïåðåìåííûõ çàäàííîé ôóíêöèè ðàçäåëèòåëüíîé äåêîìïîçèöèèÿ íå ñóùåñòâóåò.
Òàêàÿ ñèòóàöèÿ ÷àñòî âîçíèêàåò ïðè ìíîãîóðîâíåâîé äåêîìïîçèöèè, îáóñëîâëåí-
íîé îãðàíè÷åííûì ôîðìàòîì ðàçáèåíèÿ (íàïðèìåð, ïðè èñïîëüçîâàíèè â êà÷åñòâå
ëîãè÷åñêîãî áàçèñà ìàêðîÿ÷ååê ïðîãðàììèðóåìîé ìàòðèöû òèïà FPGA (Field
Programmable Gate Array) ñ ÷èñëîì âõîäîâ 3–5) [4–7].  ïðàêòèêå ëîãè÷åñêîãî
ñèíòåçà öèôðîâûõ óñòðîéñòâ íåðàçäåëèòåëüíàÿ äåêîìïîçèöèÿ áóëåâûõ ôóíêöèé
âñòðå÷àåòñÿ ÷àùå ðàçäåëèòåëüíîé [4, 5].
Èçâåñòíûå ìåòîäû íåðàçäåëèòåëüíîé ôóíêöèîíàëüíîé äåêîìïîçèöèè ïðåèìó-
ùåñòâåííî îñíîâàíû íà èäåå Êóðòèñà [1], ñóòü êîòîðîé ñîñòîèò â òîì, ÷òî îïðåäå-
ëåíèå óñëîâèÿ äåêîìïîçèðóåìîñòè/íåäåêîìïîçèðóåìîñòè çàäàííîé ôóíêöèè îöåíè-
âàåòñÿ ïî êàðòàì (ìàòðèöàì), à òàêæå íà èñïîëüçîâàíèè ðàçëîæåíèÿ Øåííîíà çà-
äàííîé ôóíêöèè îòíîñèòåëüíî îáùåé (äëÿ êëàññîâ ðàçáèåíèÿ) ïåðåìåííîé ëèáî
ïåðåìåííûõ [2–12]. Îäíàêî ïðè áîëüøîì ÷èñëå ïåðåìåííûõ, à òàêæå äëÿ ñèñòåìû
ôóíêöèé, çàäàííûõ â ÄÍÔ, ïîäîáíûå ìàòðè÷íî-àíàëèòè÷åñêèå ïîäõîäû ÿâëÿþòñÿ
äîâîëüíî ãðîìîçäêèìè è ñëîæíûìè äëÿ ðåàëèçèöèè. Ñëåäóåò çàìåòèòü, ÷òî ìíîãèå
èçâåñòíûå ìåòîäû ôóíêöèîíàëüíîé äåêîìïîçèöèè âîîáùå íåäåéñòâåííû â ñëó÷àå
íåðàçäåëèòåëüíîé äåêîìïîçèöèè [3, 12, 15].
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ íåðàçäåëèòåëüíàÿ äåêîìïîçèöèÿ áóëåâûõ
ôóíêöèé íà îñíîâå òåîðåòèêî-ìíîæåñòâåííîãî ìåòîäà, ÿâëÿþùàÿñÿ âàæíîé ñîñòàâ-
ëÿþùåé ðÿäà ðàáîò àâòîðà ïî ôóíêöèîíàëüíîé äåêîìïîçèöèè [16–18]. Ïðè ýòîì àâ-
òîð èñõîäèò èç òîãî, ÷òî ðàçäåëèòåëüíóþ äåêîìïîçèöèþ â íåêîòîðîì ñìûñëå ìîæ-
íà ñ÷èòàòü ÷àñòíûì ñëó÷àåì íåðàçäåëèòåëüíîé äåêîìïîçèöèè. Äðóãèìè ñëîâàìè,
ðàññìîòðåííûå â [16–18] îñíîâíûå îïåðàöèè è ïðîöåäóðû, ïðèìåíÿåìûå ïðè ðàç-
äåëèòåëüíîé äåêîìïîçèöèè, áóäóò ñîõðàíåíû è äëÿ ñëó÷àÿ íåðàçäåëèòåëüíîé äå-
êîìïîçèöèè. Âìåñòå ñ òåì ñëåäóåò ïîä÷åðêíóòü, ÷òî ïîñêîëüêó â ñëó÷àå íåðàçäåëè-
òåëüíîé äåêîìïîçèöèè ïåðåñå÷åíèå êëàññîâ ðàçáèåíèÿ íå ïóñòî (ñóììà èõ ìîùíî-
ñòåé òåïåðü áóäåò áîëüøå n), òî íåêîððåêòíî ïðèìåíÿòü êëþ÷åâîå ñëîâî
«q-ðàçáèåíèå» âìåñòå ñ ïðîèçâîäíûìè òåðìèíàìè, à èìåííî ( )n q� - è q-ðàçáèòûå
êîíúþíêòåðìû, êëîíû ( )n q� - è q-êëàññà è ò.ï. Ïîýòîìó â äàííîì ñëó÷àå âìåñòî
òåðìèíà «q-ðàçáèåíèå» áóäåò ïðèìåíåí òåðìèí « p q, -ðàçáèåíèå» (âìåñòå ñ ñîîòâåò-
ñòâóþùèìè ïðîèçâîäíûìè òåðìèíàìè), ïîä êîòîðûì ïîäðàçóìåâàåòñÿ áîëåå
øèðîêîå ïîíÿòèå ðàçáèåíèÿ íà äâà êëàññà — êîãäà ðàçáèâàåìûå êëàññû p è q ìîãóò
ïåðåñåêàòüñÿ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 15
1 Íà÷àëî ñì. â ¹ 5, 2001, ¹ 1, 2002, ¹ 2, 2007.
© Á.Å. Ðûöàð, 2009
1. ÎÑÍÎÂÍÛÅ ÏÎËÎÆÅÍÈß
Ïóñòü çàäàíà ïîëíàÿ áóëåâàÿ ôóíêöèÿ îò n ïåðåìåííûõ f X( ) , X x x xn�{ }1 2, ,... , ,
ò.å. f n: , ,{ } { }0 1 0 1� . Ïîä íåðàçäåëèòåëüíîé äåêîìïîçèöèåé ôóíêöèè f X( ) ìåòî-
äîì p q, -ðàçáèåíèÿ êîíúþíêòåðìîâ áóäåì ïîíèìàòü åå ðàçëîæåíèå íà ñóïåðïîçè-
öèþ ôóíêöèé îò ÷èñëà ïåðåìåííûõ, ìåíüøåãî n, íî áîëüøåãî åäèíèöû, ÷òî
ïðåäñòàâëÿþò ñîîòâåòñòâóþùèå âûðàæåíèÿ
f X X Xp q( ) ( ( ), )� � �1 , (1)
f X X Xp q( ) ( , ( ))� � �2 , (2)
f X X Xp q( ) ( ( ), ( ))� � � �1 2 . (3)
Çäåñü X p è X q — ïîäìíîæåñòâà ìíîæåñòâà X , ïðè÷åì X X Xp q� � , êîòîðûå
îáðàçóþò íåïóñòîå ïåðåñå÷åíèå X X Zp q� � , Z x x x
c
�{ }� � �1 2
, ,... , , ãäå
q n� �{ }2 3 2, ,... , , p n q c� � � , c n� �{ }12 3, ,... , , c q — ÷èñëî îáùèõ ïåðåìåííûõ,
ïðè÷åì | X pp |� , | X qq |� ; �1 ( )X p è �2 ( )X q — ñâÿçûâàþùèå ôóíêöèè, � —
îñòàòî÷íàÿ ôóíêöèÿ.
Ñîãëàñíî êëàññèôèêàöèè [19] íåðàçäåëèòåëüíûå äåêîìïîçèöèè ïîëíîé ôóíê-
öèè f , ïðåäñòàâëÿåìûå ñóïåðïîçèöèÿìè (1)–(3), ïî âèäó áëî÷íîé ñòðóêòóðû ïîäîá-
íû ðàçäåëèòåëüíûì äåêîìïîçèöèÿì [16]. Íà ðèñ. 1 ìíîæåñòâî îáùèõ ïåðåìåííûõ Z
óñëîâíî ïîêàçàíî ïóíêòèðíûìè ëèíèÿìè. Ñóïåðïîçèöèè (1) è (2) ïðåäñòàâëÿþò îä-
íîáëî÷íûå íåðàçäåëèòåëüíûå äåêîìïîçèöèè (ðèñ. 1, à, á), à (3) — äâóõáëî÷íóþ íå-
ðàçäåëèòåëüíóþ äåêîìïîçèöèþ (ðèñ. 1, â). Ïðè ñ � 0 , ò.å. êîãäà Z �
, ñóïåðïîçèöèè
(1), (2) è (3) ïðåäñòàâëÿþò ñîîòâåòñòâóþùèå âèäû ðàçäåëèòåëüíîé äåêîìïîçèöèè
ôóíêöèè f X( ) [16]. Èñõîäÿ èç ýòîãî ñóïåðïîçèöèè (1), (2) è (3) áóäåì íàçûâàòü
ïðîñòûìè íåðàçäåëèòåëüíûìè äåêîìïîçèöèÿìè ôóíêöèè f X( ) .
Çàìåòèì, ÷òî äâóõáëî÷íàÿ íåðàçäåëèòåëüíàÿ äåêîìïîçèöèÿ (3) âîçìîæíà äëÿ ôóíê-
öèé îò ÷èñëà ïåðåìåííûõ n � 3, à îäíîáëî÷íûå íåðàçäåëèòåëüíûå äåêîìïîçèöèè (1)
è (2) — äëÿ ôóíêöèé îò ÷èñëà ïåðåìåííûõ n � 4. Ïðè ýòîì ñ óâåëè÷åíèåì ÷èñëà ïåðå-
ìåííûõ n è ÷èñëà îáùèõ ïåðåìåííûõ c êîëè÷åñòâî âîçìîæíûõ âàðèàíòîâ íåðàçäåëè-
òåëüíûõ äåêîìïîçèöèé, â îòëè÷èå îò ðàçäåëèòåëüíûõ, êîìáèíàòîðíî óâåëè÷èâàåòñÿ.
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
f
�
�1pX
qX
)(Z
f
�
pX
qX �2 f
�
pX
qX �2
�1
)(Z )(Z
Ðèñ. 1
a á â
x3
x2
x1
�1
� f
�2
�1
� f
x4
x3
x2
x1
x4
x3
x2
x1
� f
�2
x4
x3
x2
x1
�1
� f
�2
x4
x3
x2
x1
�1
� f
�2
� f
x4
x3
x2
x1
�1
�2
Ðèñ. 2
� � �( ( , ), ( , ))1 1 2 2 2 3x x x x � �( ( , , ), , )1 1 2 3 3 4x x x x x � �( , , ( , , , ))x x x x x x1 2 2 1 2 3 4
� � �( ( , , ), ( , ))1 1 2 3 2 3 4x x x x x � � �( ( , ), ( , , ))1 1 2 2 2 3 4x x x x x � � �( ( , , ), ( , , ))1 1 2 3 2 2 3 4x x x x x x
a á â
ã ä å
Íà ðèñ. 2 ïðèâåäåíû ïðèìåðû âîçìîæíûõ ïðîñòåéøèõ ñëó÷àåâ íåðàçäåëèòåëü-
íûõ äåêîìïîçèöèé è ñîîòâåòñòâóþùèõ èì äåêîìïîçèöèîííûõ âûðàæåíèé.  ÷àñò-
íîñòè, äëÿ ôóíêöèè f x x x( , , )1 2 3 èìååì äâóõáëî÷íóþ äåêîìïîçèöèþ âèäà (3) ïðè
ñ �1(Z x�{ }2 ) (ðèñ. 2, à); äëÿ ôóíêöèè f x x x x( , , , )1 2 3 4 èìååì îäíîáëî÷íûå äåêîì-
ïîçèöèè âèäîâ (1) è (2) ïðè ñ �1(Z x�{ }3 è Z x�{ }2 ) (ðèñ. 2, á, â); äâóõáëî÷íûå äå-
êîìïîçèöèè (3) — ïðè ñ �1 (Z x�{ }3 è Z x�{ }2 ) (ðèñ. 2, ã, ä); äâóõáëî÷íóþ
äåêîìïîçèöèþ (3) — ïðè ñ � 2 (Z x x�{ }2 3, ) (ðèñ. 2, å).
Äåêîìïîçèðóåìóþ çàäàííóþ ôóíêöèþ f , êàê ïîëíóþ f n: , ,{ } { }0 1 0 1� , òàê è
÷àñòè÷íóþ f n: , , , ~{ } { }0 1 0 1� , áóäåì ïðåäñòàâëÿòü â òåîðåòèêî-ìíîæåñòâåííîé
ôîðìå (ÒÌÔ) [16] äâóìÿ ìíîæåñòâàìè ìèíòåðìîâ: ÒÌÔ Y m m mr
1
1 2
1�{ }, ,... ,
è ÒÌÔ Y m m mr r
0
1 2
0� � �{ }, ,... , � , ò.å. ñîâåðøåííîé ÒÌÔ Y
Y
Y
�
�
�
��
1
0
, ãäå � � �2n r
â ñëó÷àå ïîëíîé ôóíêöèè f , à â ñëó÷àå ÷àñòè÷íîé ôóíêöèè f èìååì � �2n r ;
r n | |E
2
.
2. ÄÂÀ ÑÏÎÑÎÁÀ ÏÎÈÑÊÀ ÍÅÐÀÇÄÅËÈÒÅËÜÍÎÉ ÄÅÊÎÌÏÎÇÈÖÈÈ
Ïî ìåòîäó p q, -ðàçáèåíèÿ âûäåëèì äâà ñïîñîáà ïîëó÷åíèÿ íåðàçäåëèòåëüíîé äå-
êîìïîçèöèè çàäàííîé ôóíêöèè f , îòëè÷àþùèåñÿ êàê âèäîì çàäàâàåìîé ìàñêè
p q, -ðàçáèåíèÿ, íàêëàäûâàåìîé íà äâîè÷íûå ìèíòåðìû ñîâåðøåííîé ÒÌÔ Y , òàê
è ïðîöåäóðàìè ïîëó÷åíèÿ ðàçáèòûõ ìèíòåðìîâ è äåêîìïîçèöèîííûõ êëîíîâ.
Ðàññìîòðèì ïðîñòåéøèé ñëó÷àé ïîèñêà íåðàçäåëèòåëüíîé äåêîìïîçèöèè ïîëíîé
áóëåâîé ôóíêöèè f , çàäàííîé ñîâåðøåííîé ÒÌÔ
Y
m m m
m m m
r
r r rn
�
�
�
�� � � �
{ , ,... , } ,
{ , ,... , } ,
1 2
1
1 2 2
0
êîãäà â îáîèõ êëàññàõ ðàçáèåíèÿ ïðèñóòñòâóåò îäíà îáùàÿ ïåðåìåííàÿ, ò.å. êîã-
äà ñ � 1. Î÷åâèäíî, ÷òî ðàññìàòðèâàåìûé ïîäõîä ìîæåò áûòü îáîáùåí è äëÿ
cëó÷àÿ ñ �1.
2.1. Ñïîñîá ðàñøèðåííîãî p q, -ðàçáèåíèÿ. Â îñíîâå ñïîñîáà ðàñøèðåííîãî
p q, -ðàçáèåíèÿ ëåæèò èäåÿ íàëîæåíèÿ íà äâîè÷íûå ìèíòåðìû ôóíêöèè f , çàäàííîé
ñîâåðøåííîé ÒÌÔ
Y
n n n r
n
�
� � � � � � � � �
� � �
{ }
{
( ) , ( ) ,... , ( )
(
� � � � � �
� �
1 1 1 2 1
1
1 ) , ( ) ,... , ( )r n r n rn� � �
� � � � � �
�
�
�� 1 1 2 1 2
0� � � � }
, � i �{ }0 1, ,
ìàñêè { }l l l l l lj jp q� � � �1 1
� � � � � � � � � � � �| ñ îáùèì ëèòåðàëîì l x x
j j j�{ }, ñîîòâåò-
ñòâåííî èñêîìîìó âèäó íåðàçäåëèòåëüíîé äåêîìïîçèöèè. Â ðåçóëüòàòå òàê íàçû-
âàåìîãî ðàñøèðåííîãî p q, -ðàçáèåíèÿ îáðàçóåòñÿ ñîâåðøåííàÿ ÒÌÄÔ Y çàäàííîé
ôóíêöèè f , ðàçáèòûå ìèíòåðìû êîòîðîé èìåþò â îáîèõ êëàññàõ ðàçáèåíèÿ îäè-
íàêîâûé ïî çíà÷åíèþ îáùèé ýëåìåíò � j �{ }0 1, :
� �� � � � � � � � � � � �
P
j j
q
p q
l l l l l l{ | }� � � �1 1
�
� � � � � � � � � � � � � � � �{( ) | ( ) , (� � � � � � � �� � � � �1 1 11 1j
p
j
q
jp q
� �
� � � � � � � � � � � �� �
�
� � � � � �
�
� � � �
p
p q
p
j r
p
j r
) |
{( ) | ( )
2
1 11 1
q
j r
p
p
, ( ) |� � �� �1 2
� � � � � �
�
�
�� �
(4)
( ) ( ) | (� � � � � � � �� � � � �1 1 12
� � � � � � � � � � � � � � � � � �j
q
j r
p
jq p
� � �
� � � � � � � � � � � � � ��
�
� � � � � �
�
� � � �
q
q p
r
q
j r
q
j
) } ,
( ) ( )
1
21 1
�
2 2
0
1n q nr
p
j
r
q
� �
� � � � � �| ( ) ,� � �� � }
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 17
ãäå ( ) | ( )� � � � � �� � � �1 1
� � � � � � � � � � � �j i
p
j i
q
p q
— i-é ðàçáèòûé ìèíòåðì, ñîñòîÿ-
ùèé èç ñóáìèíòåðìîâ p-êëàññà ( )� � �� �1
� �j i
p
p
è q-êëàññà
( )� � �� �1
� �j i
q
q
.
Äàëåå íàä ïîëó÷åííûìè ðàçáèòûìè ìèíòåðìàìè (4) êàæäîé ñîñòàâëÿþùåé
ÒÌÄÔ Y 1 è ÒÌÄÔ Y 0 âûïîëíÿåòñÿ ïðîöåäóðà ðàçäåëåíèÿ (îïåðàòîð �
� j
) íà 2c ïîä-
ìíîæåñòâà äëÿ ìàñîê, èìåþùèõ îïðåäåëåííûå çíà÷åíèÿ îáùåãî ëèòåðàëà l j �{ }0 1, .
 ñëó÷àå ñ �1îáðàçóþòñÿ äâà ïîäìíîæåñòâà äëÿ ìàñêè { }l l l l
p q� � � �1 1
0 0� � � �|
(îïåðàòîð �
0 j
) è äâà ïîäìíîæåñòâà äëÿ ìàñêè { }l l l l
p q� � � �1 1
1 1� � � �| (îïåðàòîð
�
1j
). Çàòåì íàä ýëåìåíòàìè êàæäîãî ïîäìíîæåñòâà âûïîëíÿåòñÿ îïåðàöèÿ «îáúåäè-
íåíèå ñïðàâà» (îïåðàòîð �
�|
) ëèáî «îáúåäèíåíèå ñëåâà» (îïåðàòîð �
� |
) â çàâèñèìîñòè
îò òîãî, êàêèå ïåðåìåííûå ôóíêöèè f ñîãëàñíî çàäàíèÿ íåîáõîäèìî ñâÿçûâàòü äëÿ
ôîðìèðîâàíèÿ îïðåäåëåííîãî âèäà äåêîìïîçèöèè, ÷òî, â ñâîþ î÷åðåäü, áóäåò
îïðåäåëÿòü êëàññ äåêîìïîçèöèîííûõ êëîíîâ [16]. Åñëè ñâÿçûâàþòñÿ ïåðåìåííûå
p-êëàññà, ò.å. èñêîìûìè ÿâëÿþòñÿ äåêîìïîçèöèîííûå êëîíû p-êëàññà (îïåðàòîð �
|clo
),
òî íàä ýëåìåíòàìè êàæäîãî ïîäìíîæåñòâà âûïîëíÿåòñÿ îïåðàöèÿ «îáúåäèíåíèå
ñïðàâà», à åñëè ñâÿçûâàþòñÿ ïåðåìåííûå q-êëàññà, ò.å. èñêîìûìè ÿâëÿþòñÿ äåêîì-
ïîçèöèîííûå êëîíû q-êëàññà (îïåðàòîð �
clo |
), òî âûïîëíÿåòñÿ îïåðàöèÿ «îáúåäèíå-
íèå ñëåâà». Çàòåì íàä ïîëó÷åííûìè ìíîæåñòâàìè âûïîëíÿåòñÿ ïðîöåäóðà êëîíèðî-
âàíèÿ, â ðåçóëüòàòå êîòîðîé äëÿ ìàñîê { }l l l l
p q� � � �
1 1
0 0� � � �| è
{ }l l l l
p q� � � �
1 1
1 1� � � �| îáðàçóþòñÿ òàê íàçûâàåìûå ðàñøèðåííûå p-êëîíû ëèáî
ðàñøèðåííûå q-êëîíû, êîòîðûå çàòåì ïîäâåðãàþòñÿ îïåðàöèè îáúåäèíåíèÿ. Ïðè
ýòîì çàìåòèì, ÷òî âñëåäñòâèå ïðîöåäóð ðàñøèðåíèÿ è ðàçäåëåíèÿ â ñôîðìèðîâàâ-
øèõñÿ êëîíàõ îáðàçóþòñÿ íåïîëíûå îáúåäèíåíèÿ íåôèêñèðîâàííûõ ñóáìèíòåðìîâ,
ò.å. íåïîëíûå ìíîæåñòâà ÷èñåë èç E
2
p (åñëè ýòî q-êëîíû) ëèáî ÷èñåë èç E
2
q (åñëè ýòî
p-êëîíû), à ìíîæåñòâà èõ ôèêñèðîâàííûõ ñóáìèíòåðìîâ îáðàçóþò ïóñòûå ïåðåñå÷åíèÿ.
Íà ïðèìåðå ñâÿçûâàíèÿ ïåðåìåííûõ p-êëàññà è, ñëåäîâàòåëüíî, ôîðìèðîâàíèÿ
p-êëîíîâ äëÿ ñ �1 ïîëó÷èì ìíîæåñòâà
� �
0
1 1
0 0{ }l l l l
p q� � � �� � � �|
�
�
�
�
�
�
�
�
�
�
��
�
�
��
�
�
{ } { }
{ } { }
� �
� �
1 1
0 0
|
|
|
{ ,... ,
clo
A
B
C
D
E
F
C C
k
�
�
��
�
�
�� �} { , ... },
1
0 0
0
(5)
� �� � � � � � � � � � � �
1
1 1
1 1{ }l l l l
p q� � � �|
�
�
�
�
�
�
�
�
�
�
��
�
�
��
�
�
{ } { }
{ } { }
{
� �
� �
1 1
0 0
|
|
|
, ... ,
clo
G
H
I
K
L
M
C C
k
�
�
��
�
�
�� �} ,... ,{ }
1
1 1
1
,
(6)
ãäå A D, ,� è G K, ,� — ìíîæåñòâà ôèêñèðîâàííûõ ñóáìèíòåðìîâ ðàñøèðåííûõ
p-êëîíîâ, îáðàçóþùèå ïóñòûå ïåðåñå÷åíèÿ A G� �
, A K� �
, D G� �
è
D K� �
; B C E F, , , ,� è H I L M, , , ,� — ìíîæåñòâà íåôèêñèðîâàííûõ ñóáìèí-
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
òåðìîâ ðàñøèðåííûõ p-êëîíîâ, ñîñòàâëÿþùèå íåïîëíûå ìíîæåñòâà B C q� � E
2
,
E F q� � E
2
, H I q� � E
2
, L M q� � E
2
; C C
k1
0 0
0
,... , è C C
k1
1 1
1
,... , — óñëîâíûå îáîçíà-
÷åíèÿ êëîíîâ, ïîëó÷åííûõ ïîñëå îïåðàöèè îáúåäèíåíèÿ, äëÿ ñîîòâåòñòâóþùèõ ìàñîê.
Îáðàçîâàíèå óïîìÿíóòûõ âûøå íåïîëíûõ ìíîæåñòâ íåôèêñèðîâàííûõ ñóá-
ìèíòåðìîâ â îáðàçîâàâøèõñÿ êëîíàõ çàäàííîé ôóíêöèè f ñîîòâåòñòâóåò èñêóñ-
ñòâåííîìó ðàñøèðåíèþ áóëåâîãî ïðîñòðàíñòâà çà ñ÷åò èñêóññòâåííîãî âíåñåíèÿ
íåêîòîðîãî ÷èñëà åå çíà÷åíèé, êîòîðûå óñëîâíî íàçîâåì íåñóùåñòâóþùèìè è îáî-
çíà÷èì ñèìâîëîì �.  îòëè÷èå îò íåñóùåñòâåííûõ (sic!) çíà÷åíèé ÷àñòè÷íîé ôóíê-
öèè f n: , , , ~{ } { }0 1 0 1� , ãäå òèëüäîé (~) îáû÷íî îáîçíà÷àþò åå íåñóùåñòâåííûå
çíà÷åíèÿ, íåñóùåñòâóþùèå çíà÷åíèÿ îáëàäàþò, êàê îêàçàëîñü, áîëåå ãèáêèìè ñâîé-
ñòâàìè äëÿ ôîðìèðîâàíèÿ îïðåäåëåííîãî âèäà íåðàçäåëèòåëüíîé äåêîìïîçèöèè.
Åñëè íåñóùåñòâåííûì çíà÷åíèÿì ÷àñòè÷íîé ôóíêöèè f â ðåçóëüòàòå ïðèíÿòîãî äî-
îïðåäåëåíèÿ ìîæíî ïðèïèñàòü òîëüêî îäíî çíà÷åíèå — ëèáî 0, ëèáî 1, òî íåñóùåñ-
òâóþùèì çíà÷åíèÿì, ïðè÷åì ïðîèçâîëüíîé (ïîëíîé èëè ÷àñòè÷íîé) ôóíêöèè f ,
ìîæíî ïðèïèñàòü çíà÷åíèÿ 0 è 1 îäíîâðåìåííî. Äðóãèìè ñëîâàìè, çàäàííóþ ôóíê-
öèþ f ïîñëå ïðîöåäóðû ðàñøèðåííîãî p q, -ðàçáèåíèÿ ìîæíî îïðåäåëèòü ñëåäóþ-
ùèì îáðàçîì: åñëè îíà ïîëíàÿ, òî f n: , , ,{ } { }0 1 0 1� � , à åñëè îíà ÷àñòè÷íàÿ, òî
f n: , , , ~,{ } { }0 1 0 1� � , ãäå ñèìâîë � îáîçíà÷àåò åå íåñóùåñòâóþùèå çíà÷åíèÿ.
Ïðèâåäåííûé íèæå ïðèìåð èëëþñòðèðóåò ðàññìîòðåííûé ñïîñîá.
Ïðèìåð 1 [1, ñ. 339]. Ñïîñîáîì ðàñøèðåííîãî p q, -ðàçáèåíèÿ íàéòè ìíîæåñòâà
ðàñøèðåííûõ p-êëîíîâ äëÿ ìàñîê { }l l l1 4 20 0| è { }l l l1 4 21 1| ïîëíîé áóëåâîé ôóíêöèè
f x x x x( , , , )1 2 3 4 , çàäàííîé ñîâåðøåííîé ÒÌÔ
Y �
{0000,0010,0100,0111,1011,1110}
{0001,0011,0101,
1
0110,1000,1001,1010,1100,1101,1111}0
�
�
��
.
Ðåøåíèå. Â ðåçóëüòàòå ïðîöåäóðû p q, -ðàçáèåíèÿ äëÿ çàäàííîé ìàñêè
{ }l l l l l1 3 4 2 3| ïîëó÷èì
{ }
{000|00,010|01,000|10,011|11,111|01,
l l l l l1 3 4 2 3| �
110|11}
{001|00,011|01,001|10,010|11,100|00,101|00
1
,
110|01,100|10,101|10,111|11}0
�
�
�
�
�
Íàä ðàçáèòûìè ìèíòåðìàìè ñîâåðøåííîé ÒÌÄÔ Y âûïîëíèì ïðîöåäóðó ðàç-
äåëåíèÿ (ñ �1) äëÿ ìàñîê { }l l l1 4 20 0| è { }l l l1 4 21 1| , à çàòåì (ïåðåéäÿ äëÿ ëó÷øåãî âîñ-
ïðèÿòèÿ ê äåñÿòè÷íîìó ïðåäñòàâëåíèþ) — îïåðàöèþ «îáúåäèíåíèå ñïðàâà»:
�
� �
�
�
�
0
1 4 2
3
0 0
00 2
{ }
{000|00, 0|10} {0|(0 }
{001
1 1
l l l|
, )
|
|00, 1|10, |00, |00, |10,
|10} {1|(0,20
00 100 101 100
101 �
�|
), | (0,2), | (0,2)}
{ }
{01
04 5
1 1
1
1 4 2
3
�
�
�
�
�
�
�
� �
�
|
|
clo
l l l
0|01, |11, |01, |11} {2|1, |3, |1, |3}
{0
1 1011 111 110 3 7 6�
�|
11|01, |11, |01, |11} {3|1, |3, |1, |3}0 010 110 111 2 6 7�
�
�|
�
�
�
�
�
�
�
�
�
�
�
�
�
�
|clo
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 19
Ïîñëå ïðîöåäóðû êëîíèðîâàíèÿ è îïåðàöèè îáúåäèíåíèÿ ïîëó÷èì èñêîìûå
ìíîæåñòâà ðàñøèðåííûõ p-êëîíîâ
�
�
�
�
��
�
�
��
��
�
��
�
�
��
��
�
��
�
�
��
�|
{
,
,
,
,
,
,
clo
0
0 2
1
0 2
4
0 2
5
0 2
0
0 2
14 5
0 2,
} {
,
, , ,
,
|
�
�
��
�
�
�� �
�
�
�
��
�
�
��
��
�
��
�
�
��
�
clo
{ , , , }2
1
3
3
3
1
6
3
1
7
1
3
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
�� �{ , , , }2 7
1
3
3 6
3
1
�
�
��
�
�
��
�
�
��
�
�
��
�
�
�
�
�
�
,
ãäå çíàê � ñèìâîëèçèðóåò ìíîæåñòâà íåñóùåñòâóþùèõ ÷èñëîâûõ ñóáìèíòåðìîâ
â ðàñøèðåííûõ p-êëîíàõ çàäàííîé ôóíêöèè f .
Ðàññìîòðèì òåïåðü èíîé ïóòü ïîëó÷åíèÿ àíàëîãè÷íîãî ðåçóëüòàòà.
2.2. Ñïîñîá ñæàòîãî p q, -ðàçáèåíèÿ. Ñóòü ýòîãî ñïîñîáà ñîñòîèò â òîì, ÷òî
íàä äâîè÷íûìè ìèíòåðìàìè ñîâåðøåííîé ÒÌÔ
Y
n n n r
n
�
� � � � � � � � �
� � �
{ }
{
( ) , ( ) ,... , ( )
(
� � � � � �
� �
1 1 1 2 1
1
1 ) , ( ) ,... , ( )r n r n rn� � �
� � � � � �
�
�
�� 1 1 2 1 2
0� � � � }
, � i �{ }01, ,
â ñëó÷àå ñ � 1 ñíà÷àëà âûïîëíÿåòñÿ ïðîöåäóðà p q, -ðàçáèåíèÿ äëÿ ìàñêè ëèòåðà-
ëîâ { }l l l l lj j j n| 1 1 1� �� � , ãäå l j �{ }0 1, — îáùèé äëÿ îáîèõ êëàññîâ ëèòåðàë ìàñ-
êè { }l l l l l lj jp q� � � �1 1
� � � �| , êîòîðàÿ çàäàåò èñêîìûé âèä íåðàçäåëèòåëüíîé
äåêîìïîçèöèè çàäàííîé ôóíêöèè f . Ïîñëå îïåðàöèè «îáúåäèíåíèå ñïðàâà» (îïå-
ðàòîð �
�|
) ïîëó÷åííûå ðàçáèòûå ìèíòåðìû ñîñòàâëÿþò ñîâåðøåííóþ ÒÌÄÔ Y
(îòäåëüíî äëÿ Y 1 è Y 0 )
� �� �
P
j j j n
q
l l l l l{ }| 1 1 1� �
�
� � � � � �
� � �
� �
�
�
{( ) | ( ) , ( ) |
(
� � � � � �
� �
j j j n
n
j
j
1
1
1 1 1 1
1
2
1
1 1 1 2
1
1 1 1� � � � � � �j n
n
j r
n q
j j n r�
� �
� �� � � � � � � � �) ,... , ( ) | ( )n
j r j j n r
n
j r
�
�
� � � �
�
�
� � � � � �
1 1
1
1
1 1 1 1
1
}
{
|
( ) | ( ) , ( )� � � � � � �
� � �
�
�
� � � � � � � �
2
1
1 1 1 2
1
2
1
1
|
( ) ,... , ( ) | (� � � � � �j j n r
n
j
rn
� � � � �
�
�
�
��
�
�
�
�
� � � �
�
�
� � �j j n
r
n
n1 1
2
1 0)
|
}
�
�
�
��
�
�
�
�
� �
�
� �
|
|
| , |
| , |
{ }
{ }
0 1
0 1
0
1
1
1 1
0
0
1
0 0
Y Y
Y Y
j j
j j
.
(7)
Çäåñü ìíîæåñòâî Y
j
j j n
n
j j� � �
�
� ��
0
1
1 1 1
1
1 1 1
1
{( ) , (� � � � � � �
�
� � � � �
�n
n) , ...
2
1�
... , ( )� � � �
�1 1 1
1 1
� �j j n
n
r
� �
�
�
} è ìíîæåñòâî Y
j
j j� � ��
1
1
1 1 1{(� � �� � � �
�n
n) , (
1
1
1
�
�
� � � �� � � � � � �
� �j j n
n
j j n
n
r
� �
�
� �
�
��
1 1
1
1 1 1
1 1
2
) ,... , ( ) } , r r r�� �� � , ïðåäñòàâëÿþò ñî-
âåðøåííûå ÒÌÔ ïîäôóíêöèè f f x x x xx j j nj
� � �( ,... , , , ,... , )
1 1 10 è ïîäôóíêöèè
f f x x x xx j j nj
� � �( ,... , , , , ,... , )1 1 11 ñîîòâåòñòâåííî, ïîëó÷àåìûå â ðåçóëüòàòå ðàçëî-
æåíèÿ Øåííîíà çàäàííîé ôóíêöèè f x x xn( , ,... , )1 2 ïî íåêîòîðîé ïåðåìåííîé x
j
,
ò.å. f x x x x f x fn i x i xi i
( , ,... , )1 2 � � , à ìíîæåñòâà Y
j� �
0
0
1{(� � � � �
�j j n
n
� �
�
1 1
1
1
� ) ,
( ) ,... , ( )� � � � � � � �
� �1 1 1
1
1 1 1
1
2
� � � �j j n
n
j j n
n
r
� �
�
� �
�
���
}0 è Y
j j j� � ��1
0
1 1 1{(� � �� �
� � � � �� � � � � � � � �� �n
n
j j n
n
j j) , ( ) , . . . , (
1 2
1
1 1 1
1
1 1 1
�
� �
�
� � n
n
r
) ,� ����
�1 0} r r rn� � �� ���� � �2 ,
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
åñòü ñîâåðøåííûå ÒÌÔ èíâåðñèé ýòèõ æå ïîäôóíêöèé, ò.å. f xj
�
� � �f x x x xj j n( ,... , , , ,... , )1 1 10 è f f x x x xx j j nj
� � �( ,... , , , ,... , )1 1 11 ñîîòâåòñòâåííî.
Íàä ýëåìåíòàìè ñîâåðøåííûõ ÒÌÔ ïîäôóíêöèé (7) Y
Y
Y
j
j
j
�
�
�
�
�
�
�
�
0
0
1
0
0
è
Y
Y
Y
j
j
j
�
�
�
�
�
�
�
�
1
1
1
1
0
âûïîëíÿåòñÿ ïðîöåäóðà ñæàòîãî p q, -ðàçáèåíèÿ äëÿ ìàñêè
{ }l l l l l l l lj j j jp q� � � �1 11 1 1 1� � � �� � � �| , â êîòîðîé îòñóòñòâóåò îáùèé ëèòåðàë l j .
Ïîñëå ýòîãî, êàê è â ï. 2.1, âûïîëíÿþòñÿ ïðîöåäóðà êëîíèðîâàíèÿ è îïåðàöèÿ îáúå-
äèíåíèÿ. Òàêèì îáðàçîì, èç ñîâåðøåííûõ ÒÌÔ ïîäôóíêöèé Y
j�0 è Y
j�1 (ñì. (7))
ñôîðìèðóþòñÿ ìíîæåñòâà òàê íàçûâàåìûõ â äàííîì ñëó÷àå ñæàòûõ p-êëîíîâ, â êî-
òîðûõ îòñóòñòâóåò çíà÷åíèå îáùåé ïåðåìåííîé x j �{ }0 1, :
Y
j
j j n j j
�
� � � �
�
� � � � � � � � � � � �
0
1 1 1 1 1 1 1{( ) ,... , (� � � � � � � � n r
j j n j j
)
( ) ,... , (
�
� � � �� � � � � � � � � � � �
}
{
1
1 1 1 1 1 1 1� � � � � � � � n r
P
q
) ���
�
�
��
�
}0
� �� � � � � � � � � � � �� � � �
P
j j j j
q
p q
l l l l l l l l{ }� � � �1 11 1 1 1| (8)
�
�
�
�
�
�
�
� �
�
�
�
�
��
�
�
��
�
�
{ } { }
{ } { }
{
� �
� �
1 1
0 0
|
|
|
, .
clo
A
B
C
.. , } ,... ,�
�
�
�
�
��
�
�
�� � � �
�
D
E
F
C C
k
{ }
1
0 0
0
,
Y
j
j j n j j
�
� � � �
�
� � � � � � � � � � � �
1
1 1 1 1 1 1 1{( ) ,... , (� � � � � � � � n r
j j n j j
)
( ) ,... , (
��
� � � �� � � � � � � � � � �
}
{
1
1 1 1 1 1 1 1� � � � � � � �
�
�
��
�
����� n r
P
q
) }0
� �� � � � � � � � � � � �� � � �
P
j j j j
q
p q
l l l l l l l l{ }� � � �1 11 1 1 1| (9)
�
�
�
�
�
�
�
� �
�
�
�
�
��
�
�
��
�
�
{ } { }
{ } { }
{
� �
� �
1 1
0 0
|
|
|
, .
clo
G
H
I
.. , } ,... ,�
�
�
�
�
��
�
�
�� � � �
�
K
L
M
C C
k
{ }
1
1 1
1
.
Çäåñü À B C M� � � � �, , , , — ìíîæåñòâà ñóáìèíòåðìîâ ñæàòûõ p-êëîíîâ;
C C
k
� �
�1
0 0
0
,... , è C C
k
� �
�1
1 1
1
,... , — óñëîâíûå îáîçíà÷åíèÿ ñôîðìèðîâàííûõ ïîñëå îáúå-
äèíåíèÿ ïîëó÷åííûõ êëîíîâ ñîîòâåòñòâóþùèõ ïîäôóíêöèé çàäàííîé ôóíêöèè f .
Íàä ñæàòûìè p-êëîíàìè ïîäôóíêöèé (8) è (9) ïðèìåíÿåòñÿ ïðîöåäóðà ðàñøè-
ðåíèÿ (îïåðàòîð �
� � j
), âíîñÿùàÿ â îáà êëàññà ðàçáèåíèÿ îäèíàêîâûå çíà÷åíèÿ îá-
ùåé ïåðåìåííîé x j �{ }0 1, ñîãëàñíî çàäàííîé ìàñêå { }l l l l l lj jp q� � � �1 1
� � � �| .
Ïðè÷åì ê ìíîæåñòâó (8) { }C C
k
� � �1
0 0
0
,... , ïðèìåíÿåòñÿ îïåðàòîð �
�0j
, ôîðìèðóþùèé
ðàñøèðåííûå p-êëîíû ïî ìàñêå { }l l l l
p q� � � �1 1
0 0� � � �| (îïåðàòîð �
�0j
), à ê
ìíîæåñòâó (9) { }C C
k
� �
�1
1 1
1
,... , — îïåðàòîð �
�1j
, ôîðìèðóþùèé ðàñøèðåííûå p-êëîíû
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 21
ïî ìàñêå { }l l l l
p q� � � �1 1
1 1� � � �| , à èìåííî
{ } { }C C C C
k k
j
� � ��
�
1
0 0
0
1
0 0
0 0
,... , ,... , , (10)
{ } { }C C C C
k k
j
� � �
�
�
1
1 1
1
1
1 1
1 1
,... , ,... , , (11)
ãäå C C
k1
0 0
0
,... , è C C
k1
1 1
1
,... , — ðàñøèðåííûå êëîíû ñîîòâåòñòâóþùèõ ïîäôóíê-
öèé, ÿâëÿþùèåñÿ òåìè æå ñòðóêòóðèðîâàííûìè îáðàçîâàíèÿìè, ïîëó÷åííûìè
â (5) è (6) ñîîòâåòñòâåííî.
Ðàññìîòðåííîå âûøå ïðîèëëþñòðèðóåì íà ïðèìåðå.
Ïðèìåð 2. Ñïîñîáîì ñæàòîãî p q, -ðàçáèåíèÿ íàéòè ìíîæåñòâà ðàñøèðåííûõ
p-êëîíîâ äëÿ ìàñîê { }l l l1 4 20 0| è { }l l l1 4 21 1| ôóíêöèè f èç ïðèìåðà 1.
Ðåøåíèå. Èç ñîâåðøåííîé ÒÌÔ Y çàäàííîé ôóíêöèè f x x x x( , , , )1 2 3 4 ñíà÷àëà
íàéäåì ñîâåðøåííûå ÒÌÔ åå ïîäôóíêöèé Y�03
è Y�13
, à çàòåì âûïîëíèì ïðîöåäó-
ðó ñæàòîãî p q, -ðàçáèåíèÿ:
Y �
{0000,0010,0100,0111,1011,1110}
{0001,0011,0101,
1
0110,1000,1001,1010,1100,1101,1111}0
�
�
��
�
P
q
� �
P
q
l l l l{ | }3 1 2 4
{0|000,1|000,0|010,1|011,1|101,1|110}
{0|001,1|001,0|011, |101,1|100,0|11
1
1010 0100 0| , | , 0,0|111,1|111}0
�
�
��
;
Y
P
q
� �
�
�
��
�03
100
{000,010}
{001,011, 101,110,111}
1
0,
{l l l1 4 2| }�
{00|0,00|1}
{01|0,01|1,10|0,11|0,10|1,11|
1
1}0
�
�
��
;
Y
P
q
� �
�
�
��
�13
010
{000,011,101,110}
{001, 100,111}
1
0,
{l l l1 4 2
1 1
| }�
{00|0,01|1, 1|0, 0|1}
{01|0,00|1,10|0,11|
1
1}0
�
�
��
.
Íàä ïîëó÷åííûìè ÒÌÄÔ Y�03
è Y�13
âûïîëíèì ïðîöåäóðó êëîíèðîâàíèÿ,
îïåðàöèþ îáúåäèíåíèÿ îáðàçîâàâøèõñÿ ñæàòûõ êëîíîâ, à çàòåì ïðîöåäóðû èõ ðàñ-
øèðåíèÿ �
�03
äëÿ Y�03
è �
�13
äëÿ Y�13
:
�
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
|
{
,
,
,
,
,
clo
00
01
01
01
10
01
,
,
} {
,
, , ,
,
11
01
00
01
01 10 11
01
�
�
��
�
�
�� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
}
03
� �
�
�
�
��
�
�
��
��03
{ | } {
,
, , ,
,
l l l1 4 20 0 000
0010
001 100 101
0010
�
�
��
�
�
��};
�
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�|
{ , , ,
clo
00
0
1
01
1
0
10
1
0
11
0
1�
��
�
�
�� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
} { , , , }0011
0
1
01 10
1
0
13
� �
�
�
��
�
�
��
�
�
�1
1 4 21 1 010 111
01
11
011 110
11
01
3
{ | } { , , ,l l l ��
�
�
��}.
 ðåçóëüòàòå ïîëó÷àåì òå æå ìíîæåñòâà p-êëîíîâ, êàê è ïðè èñïîëüçîâàíèè
ñïîñîáà ðàñøèðåííîãî p q, -ðàçáèåíèÿ (ñì. ï. 2.1)
{
,
, , ,
,
}
{ , , ,
0
0 2
1 4 5
0 2
2 7
1
3
3
�
�
�
��
�
�
��
��
�
��
�
�
��
�
�
��
�
�
�� 6
3
1
�
�
��
�
�
��
�
�
�
�
�
� }
.
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
Âèä íåðàçäåëèòåëüíîé äåêîìïîçèöèè, êàê è ÷èñëî âîçìîæíûõ åå ðåøåíèé,
îïðåäåëÿåòñÿ (êàê ïðè ðàçäåëèòåëüíîé äåêîìïîçèöèè) íà îñíîâàíèè òàê íàçûâàå-
ìûõ ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ çàäàííîé ôóíêöèè f . Ïîñëåäíèå îáðàçó-
þòñÿ èç ðàñøèðåííûõ êëîíîâ ïóòåì ïîýëåìåíòíîé âûáîðêè ïî îäíîìó ðàçíîìó
ýëåìåíòó èç êàæäîãî èõ ìíîæåñòâà, à çàòåì â îáðàçîâàâøåìñÿ ìíîæåñòâå êàæäîé
âûáîðêè îêîí÷àòåëüíî ôîðìèðóþòñÿ îïåðàöèåé îáúåäèíåíèÿ â ìíîæåñòâî ðàñøè-
ðåííûõ ìàêñèìàëüíûõ êëîíîâ çàäàííîé ôóíêöèè f . ×èñëî âîçìîæíûõ ïîýëåìåíò-
íûõ âûáîðîê (à çíà÷èò, è ÷èñëî îáðàçîâàâøèõñÿ ìíîæåñòâ) îïðåäåëÿåòñÿ êîìáèíà-
òîðíî, ñ îäíîé ñòîðîíû, ìàêñèìàëüíûì ÷èñëîì ìíîæåñòâ ðàñøèðåííûõ êëîíîâ, êî-
òîðîå çàâèñèò îò ñ è ðàâíî 2c , à ñ äðóãîé — ìîùíîñòüþ ki êàæäîãî òàêîãî
ìíîæåñòâà. Òàêèì îáðàçîì, ïîñëå êàæäîãî ïîëíîãî ïðîñëåæèâàíèÿ ïî âñåì ðàçíûì
ýëåìåíòàì ìíîæåñòâ ðàñøèðåííûõ êëîíîâ è ïîñëåäóþùåãî èõ îáúåäèíåíèÿ ñôîð-
ìèðóåòñÿ îäíî ìíîæåñòâî ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ, ïðåäñòàâëÿþùåå
îäíî èç ðåøåíèé, à ïîñëå èñ÷åðïàíèÿ âñåõ âîçìîæíûõ ñïîñîáîâ âûáîðêè — ïîëíîå
ìíîæåñòâî âîçìîæíûõ ðåøåíèé íåðàçäåëèòåëüíîé äåêîìïîçèöèè çàäàííîé ôóíê-
öèè f . Ïðè ýòîì çàìåòèì, ÷òî ÷åì áîëüøå çíà÷åíèÿ ñ è ki , òåì áîëüøå ÷èñëî âûáî-
ðîê, à ñëåäîâàòåëüíî áîëüøå âîçìîæíûõ ðåøåíèé äåêîìïîçèöèè.
Äëÿ ðàññìîòðåííîãî âûøå ïðèìåðà, èëëþñòðèðóþùåãî ñëó÷àé ñ �1, âñëåä-
ñòâèå ïîëíûõ ïîïàðíûõ âûáîðîê ðàñøèðåííûõ êëîíîâ èç äâóõ ìíîæåñòâ (5) è (6)
ëèáî (10) è (11) ïîñëå îïåðàöèè îáúåäèíåíèÿ îáðàçóþòñÿ äâà èñêîìûõ ìíîæåñòâà
ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ:
{ }
{ }
C C
C C
k
k
1
0 0
1
1 1
0
1
,... ,
,... ,
�
�
�
�
�
�
� � � � � � �{{ } { }} {{ } {C C C C C C C C
k k k k1
0
1
1 0 1
1
0
1
1 0 1
0 1 0 1
, ,� � }} { }
{{ } { }} {{
�
� � �
C C
C C C C
k k
k k
11
01 01
1
0 1 0
1
1
0 1
1 0
,... ,
, ,� C C C C C C
k k k k1
0 1 0
1
1
1
01
1
01
1 0 1 0
� � � � �
�
�
�
� } { }} { }� ,... ,
, (12)
ãäå C C
k k11
01 01
0 1
,... , è C C
k k1
01
1
01
1 0
,... , — óñëîâíûå îáîçíà÷åíèÿ ðàñøèðåííûõ ìàêñè-
ìàëüíûõ êëîíîâ ñîîòâåòñòâóþùèõ ðåøåíèé íåðàçäåëèòåëüíîé äåêîìïîçèöèè
ôóíêöèè f äëÿ ñëó÷àÿ ñ �1. Íåòðóäíî óáåäèòüñÿ, ÷òî ïðè k k0 1 2� � èç äâóõ âîç-
ìîæíûõ âûáîðîê ïî äâà êëîíà îáðàçóåòñÿ âñåãî äâà ìíîæåñòâà ðàñøèðåííûõ
ìàêñèìàëüíûõ êëîíîâ çàäàííîé ôóíêöèè f .
Äëÿ ðàññìîòðåííîé âûøå ôóíêöèè (ñì. ïðèìåðû 1 è 2) âñëåäñòâèå âçàèìíî ïî-
ïàðíûõ âûáîðîê è îáúåäèíåíèÿ ðàñøèðåííûõ êëîíîâ { , }
1
0
1
1
2
0
2
1C C C C� � è
{ , }
1
0
2
1
2
0
1
1C C C C� � ïîëó÷èì äâà ìíîæåñòâà ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ
{ , }
11
01
22
01C C è { , }
12
01
21
01C C , îïðåäåëÿþùèõ ðåøåíèÿ íåðàçäåëèòåëüíîé äåêîìïîçèöèè
ýòîé ôóíêöèè:
1. {
,
, , , ,
,
,0
0 2
2 7
1
3
14 5
0 2
3 6
�
�
�
��
�
�
���
�
�
��
�
�
��
��
�
��
�
�
���
3
1
0 2 7
012
3
13 4 5 6
3
012
�
�
��
�
�
�� �
�
�
��
�
�
��
�
�
} { , ,
, ,
, , , , ,
, ,
��
�
�
��};
2. {
,
, , , ,
,
,0
0 2
3 6
3
1
14 5
0 2
2 7
�
�
�
��
�
�
���
�
�
��
�
�
��
��
�
��
�
�
���
1
3
0 3 6
0 2 3
1
12 4 5 7
1
0 2 3
�
�
��
�
�
�� �
�
�
��
�
�
��
�
�
} { , ,
, ,
, , , , ,
, ,
��
�
�
��}.
Ðèñ. 3 èëëþñòðèðóåò îïèñàííûé âûøå ñïîñîá ðàñøèðåííîãî p q, -ðàçáèåíèÿ íà
äåêîìïîçèöèîííûõ êàðòàõ [16], ãäå ñèìâîë � óêàçûâàåò íà ïåðåõîä ê ñëåäóþùåìó
ýòàïó ïðåîáðàçîâàíèÿ.  ÷àñòíîñòè, íà ðèñ. 3, à ïîêàçàíû êàðòû äëÿ ìàñîê
{ }l l l1 4 20 0| è { }l l l1 4 21 1| , èëëþñòðèðóþùèå ïðîöåäóðó ðàçäåëåíèÿ; óïðîùåííûå êàð-
òû îòíîñèòåëüíî ðèñ. 3, à ïîëó÷åíû âñëåäñòâèå îïåðàöèè îáúåäèíåíèÿ (ðèñ. 3, á).
Êàðòà äëÿ çàäàííîé ìàñêè { }l l l l l1 3 4 2 3| , îáðàçîâàííàÿ èç êàðò íà ðèñ. 3, á, èëëþñòðè-
ðóåò ïðîöåäóðó êëîíèðîâàíèÿ, ãäå êàæäàÿ ñòðîêà ýòîé êàðòû îòîáðàæàåò îäèí èç
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 23
ðàñøèðåííûõ êëîíîâ C
1
0 , C
2
0 , C
1
1, C
2
1 , ò.å. ïîäôóíêöèè (ðèñ. 3, â). Êàðòû, ïîëó÷åí-
íûå èç ðèñ. 3, â âñëåäñòâèå îáúåäèíåíèé { , }
1
0
1
1
2
0
2
1C C C C� � è { , },
1
0
2
1
2
0
1
1C C C C� �
äàíû íà ðèñ. 3, ã. Êàðòû, îòîáðàæàþùèå ðàñøèðåííûå ìàêñèìàëüíûå êëîíû
{ , }
11
01
22
01C C è { , }
12
01
21
01C C è ïðåäñòàâëÿþùèå ðåøåíèÿ íåðàçäåëèòåëüíîé äåêîìïîçè-
öèè, ïîêàçàíû íà ðèñ. 4, ä. Çàøòðèõîâàííûå ó÷àñòêè êàðò âèçóàëèçèðóþò çíà÷èìûå
ýëåìåíòû êàðò ðèñ. 3, á â ðåçóëüòàòå âûïîëíåíèÿ ïðîöåäóðû (12).
Íà îñíîâàíèè âûøåèçëîæåííîãî ñôîðìóëèðóåì ñëåäóþùóþ òåîðåìó.
Òåîðåìà 1. Áóëåâà ôóíêöèÿ f x x xj n( ,... , ,... , )1 , çàäàííàÿ ñîâåðøåííîé ÒÌÔ
Y
Y
Y
�
�
�
��
1
0
, äîïóñêàåò ïðîñòóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ îäíîãî èç âèäîâ (1),
(2) è (3) äëÿ Z x
j
�{ } òîãäà è òîëüêî òîãäà, êîãäà õîòÿ áû äëÿ îäíîé ìàñêè p q, -ðàç-
áèåíèÿ { }l l l l l l l lj j j jp q� � � �1 11 1 1 1
� � � �� � � �| â ðåçóëüòàòå ïðîöåäóðû êëîíèðî-
âàíèÿ åå ïîäôóíêöèé îòíîñèòåëüíî x j �{ }0 1, , ïðåäñòàâëåííûõ ñîâåðøåííûìè ÒÌÔ
Y
j�0 è Y
j�1 , ìîæíî ïîëó÷èòü íå áîëåå äâóõ ìàêñèìàëüíûõ êëîíîâ ýòèõ ïîäôóíêöèé.
Äîêàçàòåëüñòâî òåîðåìû î÷åâèäíî, èñõîäÿ èç îïðåäåëåíèÿ ïîíÿòèÿ ìàêñèìàëü-
íîãî êëîíà è òåîðåìû î ñóùåñòâîâàíèè ïðîñòîé ðàçäåëèòåëüíîé äåêîìïîçèöèè ïî
ìåòîäó q-ðàçáèåíèÿ, ÷òî ìîæíî ïðîèëëþñòðèðîâàòü íà äåêîìïîçèöèîííûõ êàðòàõ
[16], à òàêæå íà îñíîâàíèè òåîðåòèêî-ìíîæåñòâåííîé èíòåðïðåòàöèè ðàçëîæåíèÿ
Øåííîíà îòíîñèòåëüíî îäíîé (â äàííîì ñëó÷àå x j �{ }0 1, ) ïåðåìåííîé ïðîèçâîëü-
íîé áóëåâîé ôóíêöèè f x x xj n( ,... , ,... , )1 . Êðîìå òîãî, â ðàáîòàõ ïî ôóíêöèîíàëüíîé
äåêîìïîçèöèè, îñíîâàííûõ íà ðàçëîæåíèè Øåííîíà [5, 6], ïðèâåäåíû àíàëèòè÷åñ-
êèå äîêàçàòåëüñòâà òåîðåì, óòâåðæäàþùèõ, ÷òî åñëè ïîäôóíêöèÿì ôóíêöèè f ïðè-
ñóùà ïðîñòàÿ ðàçäåëèòåëüíàÿ äåêîìïîçèöèÿ, òî ýòà ôóíêöèÿ áóäåò èìåòü òàêæå è
ïðîñòóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ ñîîòâåòñòâóþùåãî âèäà.
 êà÷åñòâå ïîäòâåðæäåíèÿ âûøåèçëîæåííîãî ðàññìîòðèì ñëåäóþùèé ïðèìåð.
Ïðèìåð 3 [6]. Îïèñàííûìè âûøå ñïîñîáàìè p q, -ðàçáèåíèÿ íàéòè äëÿ àíàëè-
òè÷åñêè çàäàííîé ôóíêöèè f x x x x x x x x x( , , )1 2 3 1 2 3 1 2 3� � äâóõáëî÷íóþ íåðàçäåëè-
òåëüíóþ äåêîìïîçèöèþ âèäà � � �( ( , ), ( , ))1 1 2 2 1 3x x x x (ñì. ðèñ. 2, à).
Ðåøåíèå. Ñëåäóåò çàìåòèòü, ÷òî íåçàâèñèìî îò âûáðàííîé ïàðû ïåðåìåííûõ
äëÿ ðåàëèçàöèè áåç äåêîìïîçèöèè çàäàííîé ôóíêöèè f òðåáóåòñÿ ïÿòü ëîãè÷åñêèõ
(äâóõâõîäîâûõ) ýëåìåíòîâ, à ïðè íåðàçäåëèòåëüíîé äåêîìïîçèöèè — âñåãî òðè, ÷òî
ñîîòâåòñòâóåò ðàâåíñòâó
x x x x x x x x x x x x x x1 2 3 1 2 3 1 2 1 2 1 3 1 3 1 2� � � � �( )( ) � � ,
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
Ðèñ. 3
a á â ã ä
l2 0
0 2
0 0,2
l l1 40
1 � �
�
0
4 � � 1,4,5 �
5 � �
l11
1 3
2 � 1 3
l l1 41
3 �
�
2,7 �
6 � 3,6 �
7 �
0,2 1 3
0 � 0,1,2 3
1,4,5 � �
�
0,2,7 �
2,7 � 1,3,4,5,6 �
3,6 � �
l l
2 3
0,2 1 3
0 � � C1
0
l l l1 3 4
1,4,5 � � � C2
0
2,7 � � C1
1
3,6 � � C2
1
0,2 1 3
0 � 0,2,3 1
1,4,5 � �
�
0,3,6 �
2,7 � � 1,2,4,5,7 �
3,6 �
�
�
�
ãäå �1 1 2 1 2 1 2 1 2( , ) ~x x x x x x x x� � � è �2 1 3 1 3 1 3 1 3( , ) ~x x x x x x x x� � � — ñâÿçû-
âàþùèå ôóíêöèè, à � � �� 1 2 — îñòàòî÷íàÿ ôóíêöèÿ.
Ïðåäñòàâèâ çàäàííóþ ôóíêöèþ f ñîâåðøåííîé ÒÌÔ
Y �
�
�
��
{000,111}
{001,010,011, 110}
1
0100101, ,
, äëÿ ìàñêè { }l l l l1 2 1 3| èìååì:
— ïî ñïîñîáó ðàñøèðåííîãî p q, -ðàçáèåíèÿ
— ïî ñïîñîáó ñæàòîãî p q, -ðàçáèåíèÿ
Íà îñíîâàíèè ìàêñèìàëüíûõ êëîíîâ ïîäôóíêöèé C C
1
0
2
0, è C C
1
1
2
2, îïðåäåëèì
èñêîìûå ìíîæåñòâà ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ çàäàííîé ôóíêöèè f .
Èñïîëüçóÿ äëÿ ýòîé öåëè îïåðàöèþ îáúåäèíåíèÿ (12) { , }
1
0
1
1
2
0
2
1C C C C� � è
{ , }
1
0
2
1
2
0
1
1C C C C� � , ïîëó÷àåì ñëåäóþùèå ðåøåíèÿ:
1. { ,
, ,
, ,
, ,
}0010
00
011011
0111
11
00 0110
�
�
��
�
�
��
�
�
��
�
�
�� . 2. { ,
,
,
, ,
, , ,
0011
0011
0110
0110
00 011011
�
�
��
�
�
��
�
�
��
�
�
��}.
Äëÿ îïðåäåëåíèÿ ñâÿçûâàþùèõ �1 1 2( , )x x , �2 1 3( , )x x è îñòàòî÷íîé � � �( , )1 2
ôóíêöèé íåîáõîäèìî (êàê è ïðè ðàçäåëèòåëüíîé äåêîìïîçèöèè) âûïîëíèòü ïðîöå-
äóðû êîäèðîâàíèÿ è êîíêàòåíèðîâàíèÿ. Ïðè ýòîì çàìåòèì, ÷òî èñêîìàÿ äâóõáëî÷-
íàÿ äåêîìïîçèöèÿ âèäà � � �( ( , ), ( , ))1 1 2 2 1 3x x x x ïîëó÷åíà òîëüêî äëÿ âòîðîãî ðåøå-
íèÿ, ïîñêîëüêó â íåôèêñèðîâàííîì q-êëàññå ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ
ìîæíî âûäåëèòü íå áîëåå äâóõ ìíîæåñòâ ñóáìèíòåðìîâ: {00,11} è {01,10}, ÷òî ïî-
çâîëÿåò êîäèðîâàòü èõ çíà÷åíèÿìè èç ìíîæåñòâà {0,1} â îòëè÷èå îò ïåðâîãî ðåøå-
íèÿ, ãäå òàêèõ ìíîæåñòâ òðè: {00}, {11} è {01,10}. Òàêèì îáðàçîì, ïðèìåíèâ ê
ìíîæåñòâàì ñóáìèíòåðìîâ îáîèõ êëàññîâ óïîìÿíóòûõ êëîíîâ ðàçíûå âàðèàíòû êî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 25
�
�
�
�� 0
1
3121 10}|1111,|1010,|1001,|0100,|0101,|{00
11}|1100,|{00
}|{ llll
qP
;
},{}
10
11
11,
10,11
10{
10}|1111,|1010,|10{
11}|11{
}1|1{
},{}
00,01
01,
01
00
00{
01}|0100,|1001,|{00
00}|{00
}0|0{
1
2
1
1
|
0
1
32
1
0
2
0
1
|
0
1
32
0
3
3
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
� ��
�
�
��
��
�
�
�
�
� �
�
�
�
�
�
��
�
�
��
�
CCll
CCll
clo
clo
;
10}|1,01|1,00|111,|010,|001,|{0
11}|100,|{0
}|{
0
1
321 ��
�
�
�� lllY
qP
};,{}
00,01
01,
01
00
00{}
0,1
1,
1
0
0{
1}|10,|11,|{0
0}|{0
}|{
11}10,{01,
{00}
0
2
0
1
0|
|
0
1
320
1
0
1
1
CC
llY
clo
cloPq
���
�
�
��
�
� �
��
�
�
��
�
�
���
�
�
��
�
�
��
�
�
��
�
�
�
�
��
�
�
��
��
�
�
�
�
�
}.,{}
10
11
11,
10,11
10{}
0
1
1,
0,1
0{
0}|11,|00,|{0
1}|{1
}|{
10}1,0{00,
{11}
1
2
1
1
1|
|
0
1
320
1
1
1
1
CC
llY
clo
cloPq
��
�
�
�
�
�
�
�
�
�
�
� ���
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
äèðîâàíèé âòîðîãî ðåøåíèÿ, ïîëó÷èì ÷åòûðå âîçìîæíûõ ðåøåíèÿ äâóõáëî÷íîé
íåðàçäåëèòåëüíîé äåêîìïîçèöèè âèäà � � �( ( , ), ( , ))1 1 2 2 1 3x x x x (ñì. ðèñ. 2, â):
1 . { , } {�
�
�
�
� � �
2
2
1
2 2
0
0
1
�
�
�
��
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
��
�
�
��
�
�
�
�
�
�
�
�
, }1
2
E , �
1
1 10110�{ }, , �
2
1 10110�{ }, ,
�1 100�{ } ;
2. { , } {�
�
�
�
� � �
2
1
2
0
1
2 2
0
1
0
�
�
�
��
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
��
�
�
��
�
�
�
�
�
�
�
�
, }1
2
E , �
1
1 10110�{ }, , �
2
1 10011�{ }, ,
�1 101�{ } ;
3. { , } {�
�
�
�
� � �
1 2
0
2
1
0
2 2
1
0
1
�
�
�
��
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
��
�
�
��
�
�
�
�
�
�
�
�
, }0
2
E , �
1
1 10011�{ }, , �
2
1 10110�{ }, ,
�1 110�{ } ;
4. { , } {�
�
�
�
� � �
1 2
1
2
0
0
2 2
1
1
0
�
�
�
��
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
��
�
�
��
�
�
�
�
�
�
�
�
, }0
2
E , �
1
1 10011�{ }, , �
2
1 10011�{ }, ,
�1 111�{ } .
3. ÏÐÎÑÒÀß ÍÅÐÀÇÄÅËÈÒÅËÜÍÀß ÔÓÍÊÖÈÎÍÀËÜÍÀß ÄÅÊÎÌÏÎÇÈÖÈß
Èñõîäÿ èõ ââåäåííûõ ïîíÿòèé è òåðìèíîâ, ñôîðìóëèðóåì òåîðåìó î ñóùåñòâî-
âàíèè ïðîñòîé íåðàçäåëèòåëüíîé äåêîìïîçèöèè áóëåâîé ôóíêöèè f îò n ïåðå-
ìåííûõ ìåòîäîì p q, -ðàçáèåíèÿ.
Òåîðåìà 2. Áóëåâà ôóíêöèÿ f x x xn( , ,... , )1 2 , çàäàííàÿ (ñîâåðøåííîé) ÒÌÔ
Y
Y
Y
�
�
�
��
1
0
, äîïóñêàåò ïðîñòóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ òîãäà è òîëüêî òîã-
äà, êîãäà õîòÿ áû äëÿ îäíîé ìàñêè p q, -ðàçáèåíèÿ ëèòåðàëîâ, èìåþùåé â îáîèõ
êëàññàõ îáùèå ýëåìåíòû, ÷òî ñîñòàâëÿþò ìíîæåñòâî Z x x x
c
�{ }� � �1 2
, ,... , ,
c n� �{ }1 2 2, ,... , , ìîæíî â ðåçóëüòàòå ïðîöåäóðû êëîíèðîâàíèÿ ïîëó÷èòü íå áîëåå
äâóõ ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ, ïðè÷åì:
1) åñëè êëîíû p-êëàññà, òî èìååì îäíîáëî÷íóþ íåðàçäåëèòåëüíóþ äåêîìïîçè-
öèþ âèäà � �( ( ), )1 X Xp q ;
2) åñëè êëîíû q-êëàññà, òî èìååì îäíîáëî÷íóþ íåðàçäåëèòåëüíóþ äåêîìïîçè-
öèþ âèäà � �( , ( ))X Xp q
2 ;
3) åñëè êëîíû p- è q-êëàññîâ, òî èìååì äâóõáëî÷íóþ íåðàçäåëèòåëüíóþ äå-
êîìïîçèöèþ âèäà � � �( ( ), ( ))1 2X Xp q .
Äîêàçàòåëüñòâî òåîðåìû 2 (ïî àíàëîãèè ñ òåîðåìîé î ñóùåñòâîâàíèè ðàçäåëè-
òåëüíîé äåêîìïîçèöèè [16]) íåïîñðåäñòâåííî âûòåêàåò èç ñîîòâåòñòâèÿ ìåæäó
óïðîùåííîé äåêîìïîçèöèîííîé êàðòîé, îáðàçîâàííîé ïðîöåäóðîé p q, -ðàçáèåíèÿ
äëÿ ìàñêè ëèòåðàëîâ, èìåþùåé â îáîèõ êëàññàõ íåêîòîðîå êîëè÷åñòâî îáùèõ
ýëåìåíòîâ, è ðàñøèðåííûìè ìàêñèìàëüíûìè êëîíàìè ôóíêöèè f .
Òåîðåìó 2 ìîæíî èñïîëüçîâàòü, ïðîäîëæàÿ ðåøåíèå ïðèìåðà 1.
Ïîñêîëüêó äëÿ êàæäîãî ðåøåíèÿ ïîëó÷åíî ïî äâà ðàñøèðåííûõ ìàêñèìàëüíûõ
êëîíà (ò.å. ìîùíîñòü èõ ìíîæåñòâ k � 2), òî ôèêñèðîâàííûå ìíîæåñòâà ýòèõ êëîíîâ
ìîæíî êîäèðîâàòü çíà÷åíèÿìè 0 è 1. Ýòî ïîçâîëÿåò îáðàçîâàòü ñâÿçûâàþùóþ
ôóíêöèþ �1 1 3 4( , , )x x x , à ïîñëå êîäèðîâàíèÿ ñóáìèíòåðìîâ íåôèêñèðîâàííûõ
ìíîæåñòâ è ïðîöåäóðû êîíêàòåíàöèè — îñòàòî÷íóþ ôóíêöèþ � �( , , )1 2 3x x :
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
1. { , ,
, ,
, , , , ,
, ,
}0 2 7
012
3
13 4 5 6
3
012
1
�
�
��
�
�
��
�
�
��
�
�
�� �
cod
. .{
, ,
,
, ,
}
{
, ,
1
012
3
3
012
0
00 01
1
0
1
1� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
10
11
1
11
00 0110
012 7
12
1�
�
��
�
�
��
�
�
��
�
�
�� �,
, ,
} { , , , }
.
con
.{
, ,
,
, ,
}
{
, ,
� �
1
1
1
0012
3
3
012
1
00 0110
�
�
��
�
�
��
�
�
��
�
�
�� �
�
11
0
11
00 0110
3 4 5 6 1�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
�
�
,
, ,
} { , , , }
con
�
�
�
�
�
�
�
�
;
2. { , ,
, ,
, , , , ,
, ,
}0 3 6
0 2 3
1
12 4 5 7
1
0 2 3
2
�
�
��
�
�
��
�
�
��
�
�
�� �
cod
. .{
, ,
,
, ,
}
{
, ,
1
0 2 3
1
1
0 2 3
0
0010
1
0
1
1� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
11
01
1
01
001011
0 2 3 5
2 2
1�
�
��
�
�
��
�
�
��
�
�
�� �,
, ,
} { , , , }
.
con
.{
, ,
,
, ,
}
{
, ,
� �
1
1
1
00 2 3
1
1
0 2 3
1
001011
�
�
��
�
�
��
�
�
��
�
�
�� �
�
01
0
01
001011
14 6 7 1�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
�
�
,
, ,
} { , , , }
con
�
�
�
�
�
�
�
�
.
Îòñþäà ïîëó÷èì ñîâåðøåííûå ÒÌÔ ñâÿçûâàþùåé �1 1 3 4( , , )x x x è îñòàòî÷íîé
� �( , , )1 2 3x x ôóíêöèé äëÿ âñåõ âîçìîæíûõ ðåøåíèé äåêîìïîçèöèè:
1.1. �
1
1 113 4 5 6�{ }, , , , , �1 1012 7�{ , , , } ; 1.2. �
1
1 10 2 7�{ }, , , �1 13 4 5 6�{ }, , , ;
2.1. �
1
1 112 4 5 7�{ }, , , , , �1 10 2 3 5�{ }, , , ; 2.2. �
1
1 10 3 6�{ }, , , �1 114 6 7�{ }, , , .
Òàêèì îáðàçîì, çàäàííàÿ ôóíêöèÿ f íà îñíîâàíèè òåîðåìû 2 èìååò äëÿ ìàñêè
{ }l l l l l1 3 4 2 3| ïðîñòóþ îäíîáëî÷íóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ (ðèñ. 4) âèäà (1)
� � � �( ( ), ) ( ( , , ), , )1 1 1 3 4 2 3X X x x x x xp q � .
Íà îñíîâàíèè òåîðåìû 2 ìîæíî òàêæå óòâåðæ-
äàòü, ÷òî ðàññìàòðèâàåìàÿ ôóíêöèÿ äîïóñêàåò è
äâóõáëî÷íóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ2
âèäà (3) � � �( ( ), ( ))1 2X Xp q , ïîñêîëüêó åå ðàñøè-
ðåííûå ìàêñèìàëüíûå êëîíû îêàçàëèñü êîìïëåìåí-
òàðíûìè [16], ò.å. èõ íåôèêñèðîâàííûå ìíîæåñòâà
ñóáìèíòåðìîâ, êàê è â ïðèìåðå 3, ìîæíî êîäèðîâàòü
çíà÷åíèÿìè èç {0,1}.  ÷àñòíîñòè, óïîìÿíóòóþ äå-
êîìïîçèöèþ ìîæíî ïîëó÷èòü ïóòåì p q, -ðàçáèåíèÿ ìèíòåðìîâ ÒÌÔ �1 îñòàòî÷íîé
ôóíêöèè � �( , , )1 2 3x x äëÿ ìàñêè { }l l l�1 2 3| . Âûáðàâ äëÿ ýòîãî, íàïðèìåð, ðåøå-
íèå 1.2, íàéäåì ìàêñèìàëüíûå êëîíû q-êëàññà ýòîé ôóíêöèè è âûïîëíèì ñîîòâåò-
ñòâóþùèå ïðîöåäóðû
�1 1011100101110� �{ , , , }
P
q
{ }={0|11,1|00,1|01,1|10}1l l l�1 2 3| �
�
�
��
�
�
��
�
�
��
�
�
�� �
|
{ , , , }
clo cod0
1
3
1
0
012
�
�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
��
�
�cod
121
0
1
1
0
0
1
0
2
0
2
1. . .{ , } {� � ��
�
�
��
�
�
�� �
�
�
��
�
�
��
, } { , }
. . .{ ,
1
0
1 0011
12 2
0
1
1
0
1
2
1
con
� �
2
0 10
1
1
1
0
0 0110
�
�
��
�
�
�� �
�
�
��
�
�
��
�
�
��
�
�
�� �} { , } { , }
con
�
�
�
�
�
�
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 27
2
3
x
x
1
3
4
x
x
x
f�
1�
Ðèñ. 4
2  [1, ñ.133] ýòîãî íå çàìå÷åíî.
Ñîâåðøåííûå ÒÌÔ ñâÿçûâàþùåé �2 2 3( , )x x è îñòàòî÷íîé � � �( , )1 2 ôóíêöèé
äëÿ îáîèõ ðåøåíèé äåêîìïîçèöèè èìåþò ñëåäóþùèé âèä:
1.2.1. � �
2
1 1 1 1012 0 3� �{ } { }, , , , ; 1.2.2. �
2
1 13�{ }, �1 112�{ }, .
Ñëåäîâàòåëüíî, äëÿ çàäàííîé ìàñêè { }l l l l l1 3 4 2 3| äàííàÿ ôóíêöèÿ f èìååò òàêæå
è äâóõáëî÷íóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ âèäà (3) (ðèñ. 5)
� � � � � �( ( ), ( )) ( ( , , ), ( , ))1 2 1 1 3 4 2 2 3X X x x x x xp q � .
Àíàëîãè÷íûì îáðàçîì ìåòîä p q, -ðàçáèåíèÿ ïðèìå-
íèì è äëÿ ïîëó÷åíèÿ íåðàçäåëèòåëüíîé äåêîìïîçèöèè
÷àñòè÷íîé ôóíêöèè f n: , , , ~{ } { }0 1 0 1� . Îòìåòèì, ÷òî
â îòëè÷èå îò ïîëíîé ôóíêöèè â ðåçóëüòàòå îïåðàöèè
îáúåäèíåíèÿ ðàñøèðåííûõ êëîíîâ ìîãóò îáðàçîâàòüñÿ
ïåðåñåêàþùèåñÿ êëîíû, êîòîðûå ïî îïðåäåëåíèþ [16] íå
ÿâëÿþòñÿ ìàêñèìàëüíûìè êëîíàìè ôóíêöèè f . Ïîýòîìó
÷òîáû ïîëó÷èòü ðàñøèðåííûå ìàêñèìàëüíûå êëîíû ÷àñ-
òè÷íîé ôóíêöèè f , íåîáõîäèìî äîïîëíèòåëüíî âûïîëíèòü ïðîöåäóðó îðòîãîíàëèçàöèè
ïåðåñåêàþùèõñÿ ðàñøèðåííûõ êëîíîâ [16, 20].
Ðàññìîòðèì ïðèìåð, êîòîðûé èëëþñòðèðóåò íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ
÷àñòè÷íîé ôóíêöèè f .
Ïðèìåð 4 [1, ñ. 377]. Ïî ìåòîäó p q, -ðàçáèåíèÿ ìèíòåðìîâ íàéòè íåðàçäåëè-
òåëüíóþ äåêîìïîçèöèþ âèäà (1) � �( ( ), )1 X Xp q ÷àñòè÷íîé ôóíêöèè
f x x x x( , , , )1 2 3 4 , çàäàííîé ñîâåðøåííîé ÒÌÔ
Y �
{0000,0011,0100, 000,1001,1111}
{0001,0010,0101,
11
0110,0111,1010,1101,1110}0
�
�
��
,
äëÿ ìàñêè ëèòåðàëîâ { }l l l l l1 2 3 3 4| .
Ðåøåíèå.
{ }
{000|00,001|11,010|00, 00|00,100|01,
l l l l l1 2 3 3 4
1
| �
111|11}
{000|01,001|10,010|01,011|10,011|11,101|10
1
,110|01,111|10}0
�
�
��
�
.
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
2
3
x
x
1
3
4
x
x
x
f�
1�
2�
Ðèñ. 5
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
��
��
��
�
�
�
�
�
��
�
�
��
�
��
��
�
�
��
��
��
�
��
clo
clo
lll
lll
|
0
|
|
0
|
0
1
|
1
|
1
421
1
|
0
|
0
|
0
1
|
|
1
|
1
421
0
(2,3)}|32,|)7,5,1{(
2}|72,|5(2,3),|32,|1{2}|72,|53,|2,3|32,|1{
3}|)7,1{(3}|73,|1{3}|73,|1{
}1|1{
1}|)6,2{(0,1}|61,|21,|{01}|61,|21,|{0
(0,1)}|40,|{(0,2)
(0,1)}|40,|20,|{01}|40,|40,|20,|{0
}0|0{
.
}C,{C}
2,3
3,
2
3
1,5,7{}
2,3
3,
2
1,5,7,
3
1,7{
}C,{C}
0,1
4,
1
0
0,2,6{}
1,0
4,
1
0,2,6,
0
0,2{
1
2
1
1
||
0
2
0
1
||
�
�
�
�
�
�
���
�
�
��
�
� �
��
�
�
��
�
�
���
�
�
��
�
� �
��
�
�
��
�
� �
��
�
�
��
�
�
�
�
���
�
�
��
�
�
���
�
�
��
�
�
���
�
�
��
�
�
���
�
�
��
�
� �
��
�
�
��
�
�
�
�
�
ortclo
ortclo
 ðåçóëüòàòå ïðîöåäóðû îðòîãîíàëèçàöèè (îïåðàòîð �
ort |
) ðàñøèðåííûõ êëîíîâ
è èõ âçàèìíî ïîïàðíîãî îáúåäèíåíèÿ {C C ,C C }
1
0
1
1
2
0
2
1� � è {C C ,C C }
1
0
2
1
2
0
1
1� � ïî-
ëó÷èì ñëåäóþùèå ìíîæåñòâà ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ çàäàííîé ôóíê-
öèè f :
1. { , , , , ,
,
,
, ,
,
,
}012 5 6 7
0 3
12
3 4
01
2 3
�
�
��
�
�
��
�
�
��
�
�
�� ; 2. { , , ,
, ,
, , , ,
, ,
}0 2 3 6
0
12 3
14 5 7
013
2
�
�
��
�
�
��
�
�
��
�
�
�� .
Ñâÿçûâàþùàÿ �1 1 2 3( , , )x x x è îñòàòî÷íàÿ � �( , , )1 3 4x x ôóíêöèè îïðåäåëÿþòñÿ
ïðîöåäóðàìè êîäèðîâàíèÿ è êîíêàòåíèðîâàíèÿ:
1. { , , , , ,
,
,
, , ,
,
,
}012 5 6 7
0 3
12
3 4
01
2 3
�
�
��
�
�
��
�
�
��
�
�
�� �
cod
11
0 3
12
01
2 3
0
0011
1
0
1
1. .{
,
,
,
,
,
}
{
,
� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
0110
1
00 01
1011
0 3 4 5
1
1
,
,
,
,
} { , , , }
.
�
�
��
�
�
��
�
�
��
�
�
�� �
con
2
0 3
12
01
2 3
1
0011
01
1
1
1
0.{
,
,
,
,
,
}
{
,
� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
,
,
,
,
} { , , , }
10
0
00 01
1011
014 7 1�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
�
con
�
�
�
�
�
�
�
�
�
;
2. { , , ,
, ,
, , , ,
, ,
}0 2 3 6
0
12 3
14 5 6
013
2
2
�
�
��
�
�
��
�
�
��
�
�
�� �
cod
. .{
, ,
,
, ,
}
{
,
1
0
12 3
013
2
0
00
011
1
0
1
1� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
011
1
00 0111
10
0 4 5 7
2 2
1
,
,
, ,
} { , , , }
.
�
�
��
�
�
��
�
�
��
�
�
�� �
con
.{
, ,
,
, ,
}
{
, ,
� �
1
1
1
00
12 3
013
2
1
00
0110
�
�
��
�
�
��
�
�
��
�
�
�� �
�
11
0
00 0111
10
013 4 1�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
�
�
,
, ,
} { , , , }
con
�
�
�
�
�
�
�
�
.
Ñîâåðøåííûå ÒÌÔ ñâÿçûâàþùåé �1 1 2 3( , , )x x x è îñòàòî÷íîé � �( , , )1 3 4x x
ôóíêöèé äëÿ ïîëó÷åííûõ ÷åòûðåõ ðåøåíèé íåðàçäåëèòåëüíîé äåêîìïîçèöèè
èìåþò âèä:
1.1. �
1
1 13 4�{ }, , �1 10 3 4 5�{ }, , , ; 1.2. �
1
1 1012 5 6 7�{ }, , , , , , �1 1014 7�{ }, , , ;
2.1. �
1
1 114 5 7�{ }, , , , �1 10 4 5 7�{ }, , , ; 2.2. �
1
1 10 2 3 6�{ }, , , , �1 1013 4�{ }, , , .
Òàêèì îáðàçîì, íà îñíîâàíèè òåîðåìû 2 çàäàííàÿ ôóíêöèÿ f äëÿ ìàñêè
{ }l l l l l1 2 3 3 4| äîïóñêàåò ïðîñòóþ íåðàçäåëèòåëüíóþ îäíîáëî÷íóþ äåêîìïîçèöèþ
(ðèñ. 6) âèäà (1)
� � � �( ( ), ) ( ( , , ), , )1 1 1 2 3 3 4X X x x x x xp q � .
Ïðèâåäåííîå â [1, ñ. 377] åäèíñòâåííîå ðåøåíèå
ñîâïàäàåò ñ ïîëó÷åííûì ðåøåíèåì äåêîìïîçèöèè 1.1.
Ñ óâåëè÷åíèåì çíà÷åíèÿ c ÷èñëî ìàñîê ñ ôèêñè-
ðîâàííûìè çíà÷åíèÿìè ëèòåðàëîâ óâåëè÷èâàåòñÿ êàê
2c , îáðàçóÿ âñëåäñòâèå ïðîöåäóð p q, -ðàçáèåíèÿ è
êëîíèðîâàíèÿ 2c ïîäìíîæåñòâ ðàñøèðåííûõ ðàçáè-
òûõ ìèíòåðìîâ è ñîîòâåòñòâåííî 2c ìíîæåñòâ ðàñ-
øèðåííûõ êëîíîâ çàäàííîé ôóíêöèè f . Äëÿ ñëó÷àÿ ñ � 2 , â ÷àñòíîñòè, ïîëó÷èì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 29
3
4
x
x
1
2
3
x
x
x
f�
1�
Ðèñ. 6
� �
P
i j i j
q
p q
l l l l l l l l{ }� � � �1 1
� � � � � �|
�
� �
�
00
1
0 0
01
1 1 0
0 0 0 0{ } { }l l l l C C
p q
clo
k� � � �� � � � � �| ,... ,
{ } {l l l l C
p q
clo
� � � �1 1
0 1 0 1
1
1��� ��� ��� ��� ��� ��� �| ,... ,C
l l l l
k
clo
p q
1
1 1
1
10
1 0 1 0
}
{ } {� ��� ��� ��� ��� ��� ��� �� � � �| C C
l l l l
k
p
1
2 2
11
2
1 1
1 1 1 1
,... ,
|
}
{� ��� ��� ��� ��� ��� ���� � � �q
clo
k
C C} { }�
�
�
�
�
�
�
�
�
�
�
1
3 3
3
,... ,
. (13)
Çäåñü C C
k1
0 0
0
,... , , C C
k1
1 1
1
,... , , C C
k1
2 2
2
,... , è C C
k1
3 3
3
,... , — óñëîâíûå îáîçíà÷åíèÿ
ðàñøèðåííûõ êëîíîâ äëÿ ñîîòâåòñòâóþùèõ ìàñîê ëèòåðàëîâ, îáùèå ëèòåðàëû li
è l j êîòîðûõ èìåþò â îáîèõ êëàññàõ ðàçáèåíèÿ îäèíàêîâûå çíà÷åíèÿ (â äàííîì
ñëó÷àå l li j, ,�{ }0 1); k k k k0 1 2 3 1 2, , , , ,...�{ } — ìîùíîñòè ìíîæåñòâ ðàñøèðåííûõ
êëîíîâ äëÿ ñ � 2 .
Êàê è â ñëó÷àå ñ �1, ïðè c � 2 ìíîæåñòâà ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ
ôóíêöèè f ôîðìèðóþòñÿ ïóòåì êîìáèíàòîðíîé âûáîðêè ïî îäíîìó êëîíó èç êàæ-
äîãî èõ ìíîæåñòâà (13). Ñôîðìèðîâàííûå äëÿ êàæäîé âûáîðêè ìíîæåñòâà ïðè ñ � 2
ñîäåðæàò ÷åòûðå, ïðè ñ � 3 — âîñåìü, à ïðè ïðîèçâîëüíîì c — âñåãî 2c ðàñøèðåí-
íûõ êëîíîâ.  çàâèñèìîñòè îò ÷èñëà c è ìîùíîñòè ki i-ãî ìíîæåñòâà ðàñøèðåííûõ
êëîíîâ ÷èñëî âîçìîæíûõ âûáîðîê îïðåäåëÿåòñÿ êàê
K
k
k k
s
i
i
i i
c
�
��
�
�
!
0
2 2
1
!
( )!
, k ki i� �1. (14)
Äëÿ ñëó÷àÿ ñ � 2 ÷èñëî âîçìîæíûõ âûáîðîê K s áóäåò îïðåäåëÿòü ïðîèçâåäå-
íèå (14)
k
k k
k
k k
k
k k
0
0 1
1
1 2
2
2 3
!
( )!
!
( )!
!
( )!�
�
�
�
�
è ñîîòâåòñòâóþùåå ÷èñëî ðàñøèðåííûõ
ìàêñèìàëüíûõ êëîíîâ ôóíêöèè f : { },... ,C C
k k k k1111
0123 0123
0 1 2 3
,... , { , , },...C C
k k k k1 11
0123
1
0123
1 0 2 3
�
� �, ,{ , }C C
k k k k11 1
0123
1
0123
2 0 1 3
, … , { , , }C C
k k k k111
0123
1
0123
3 0 1 2
� , … , { , , },...C C
k k k k0 1 2 3111
0123
1
0123
�
... ,{ , }, ...C C
k k k k0 1 2 311
0123
11
0123
� , , { }C C
k k k k0 2 1 31 1
0123
1 1
0123,... , , … ,{ }C C
k k k k0 3 1 211
0123
1 1
0123,... , .
Íåðàçäåëèòåëüíóþ ôóíêöèîíàëüíóþ äåêîìïîçèöèþ äëÿ ñëó÷àÿ ñ � 2 èëëþñò-
ðèðóåò ïðèìåð 5 [1, ñ. 374].
Ïðèìåð 5. Ïî ìåòîäó p q, -ðàçáèåíèÿ ìèíòåðìîâ íàéòè íåðàçäåëèòåëüíóþ äå-
êîìïîçèöèþ âèäà � �( , ( ))X Xp q
2 ïîëíîé áóëåâîé ôóíêöèè f x x x x x( , , , , )1 2 3 4 5 ,
çàäàííîé ñîâåðøåííîé ÒÌÔ Y 1 10 5 6 7 8 914 1519 22 26 31�{ }, , , , , , , , , , , , äëÿ ìàñêè ëèòåðàëîâ
{ }l l l l l l l1 3 4 1 2 3 5| .
Ðåøåíèå.
Y �
{ 00101,00110,00111,01000,01001,01110,0111100000, ,10011,10110,11010,11111}
{00001,00010,00011,00100
1
,01010,01011,01100,01101,10000,10001,10010,
10100,10101,10111,11000,11001,11011,11100,11101,11110}0
�
�
�
�
;
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
�
�
�
�
�
�
�
�
�
0
1
5321431
}1110|1111111,|1101110,|1101101,|1011101,|1001100,|100
1011,|1111011,|1101010,|1101000,|1011001,|1001000,|1000111,|010
0110,|0100101,|0010100,|0010010,|0100001,|0010000,|0010001,|000{
}1111|1111100,|1011010,|1111001,|1010111,|011
0110,|0110101,|0000100,|0000011,|0110010,|0110011,|010,0000|000{
}|{ lllllll
.
Ïîñêîëüêó ìîùíîñòü ìíîæåñòâ ðàñøèðåííûõ êëîíîâ k k k k1 2 3 4 2� � � � , òî
ñîãëàñíî (14) ÷èñëî âîçìîæíûõ ïîýëåìåíòíûõ âûáîðîê îïðåäåëÿåòñÿ êàê
K s � � � �2 2 2 8! ! ! , à â êàæäîì îáðàçîâàâøåìñÿ ìíîæåñòâå áóäåò ïî ÷åòûðå êëîíà.
Òàêèì îáðàçîì, ïîñëå ïðîöåäóðû îáúåäèíåíèÿ ñôîðìèðóåòñÿ âñåãî âîñåìü ìíî-
æåñòâ ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ çàäàííîé ôóíêöèè f :
1. { , }C C
1111
0123
2222
0123 ; 2. { , }C C
1112
0123
2221
0123 ; 3.{ , }C C
1121
0123
2212
0123 ; 4. { , }C C
1122
0123
2211
0123 ;
5. { , }C C
1211
0123
2122
0123 ; 6. { , }C C
1212
0123
2121
0123 ; 7. { , }C C
1221
0123
2112
0123 ; 8. { , }C C
1222
0123
2111
0123 .
 öåëÿõ ñîïîñòàâëåíèÿ ïîëó÷åííîãî ðåçóëüòàòà ñ ðåçóëüòàòîì ðàáîòû
[1, ñ. 374] èç ïîëó÷åííûõ ìíîæåñòâ ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ âûäåëèì
ñåäüìîå ìíîæåñòâî, ïðèâåäåííîå â êà÷åñòâå åäèíñòâåííîãî ðåøåíèÿ íåðàçäåëè-
òåëüíîé äåêîìïîçèöèè çàäàííîé ôóíêöèè f :
7. { } {{ } {C C C C C C C C
1221
0123
2112
0123
1
0
2
1
2
2
1
3
2
0
1
1, ,� � � � � �C C
1
2
2
3� �}}
�
�
�
��
�
�
��{
, , , ,
, ,
, , , , , , , ,
, , ,
0 2 3 5 7
14 6
0 3 4 5 9101215
3
012 4 5 6 7
12 6 7 8111314
, , ,
, , , , , , , }
�
�
��
�
�
�� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 31
|
0
|
0
|
0
1
|
|
1
|
1
524
)}7,6,2(|2{}7|2,6|2,2|2{}7|2,6|2,2|2{
}(2,6,7)|33,|)3,2{(
}7|36,|32,|33,|)3,2{(}7|36,|33,|32,|33,|2{
}10|01{
clo
lll �
�
�
�
�
��
�
�
��
�
��
�
��
�
��
|
0
|
|
0
|
0
1
|
1
|
1
524
)}12,9(|4),13,8(|)5,4{(
}13|(4,5),12|4,9|4,8|)5,4{(}13|5,13|4,12|4,8|5,9|4,8|4{
}(9,12)|5{}12|59,|5{}12|59,|5{
}01|10{
clo
lll �
�
�
�
�
��
�
�
�
��
��
�
�
��
��
|
0
|
|
0
|
0
1
|
1
|
1
524
(0,4,5)}|11,|0,1){(
5}|14,|10,|11,|0,1){(5}|14,|11,|10,|11,|0{
}4,5),0(|0{}5|04,|0,0|0{}5|04,|0,0|0{
}00|00{
clo
lll �
�
�
�
�
��
�
�
�
��
��
�
�
��
��
|
0
|
0
|
|
0
1
|
1
|
1
524
)}14,11(|(6,7)),15,10(|6{}15|6,14|(6,7),11|(6,7),10|6{
}14|7,15|6,14|6,11|7,11|6,10|6{
}(10,15)|7{}15|710,|7{}15|710,|7{
}11|11{
clo
lll �
�
�
�
�
��
�
�
��
�
��
�
��
�
��
.
},{}14,11
7,6
,15,10
6
7
{
},{}12,9
4
5
,13,8
5,4
{
},{}3
3,2
,7,6,2
2
3
{
},{}1
1,0
,5,4,0
1
0
{
3
2
3
1
|
2
2
2
1
|
1
2
1
1
|
0
2
0
1
|
�
�
�
�
�
�
�
�
�
�
�
�
���
�
�
��
�
��
��
�
�
��
�
�
�
���
�
�
��
�
�
��
�
�
��
�
��
�
���
�
�
��
�
�
���
�
�
��
�
�
�
���
�
�
��
�
��
��
�
�
��
�
�
�
CC
CC
CC
CC
clo
clo
clo
clo
Ïîñëå ïðîöåäóð êîäèðîâàíèÿ è êîíêàòåíèðîâàíèÿ ïîëó÷èì ñëåäóþùèå äâà ðå-
øåíèÿ:
�
�
�
��
�
�
��
cod
71
0 2 3 5 7
14 6
3
012 4 5 6 71
1. .{
, , , ,
, ,
,
, , , , , ,
� �
1
0
0 2 3 5 7
14 6
1
3
012 4 5 6
�
�
��
�
�
�� �
�
�
�
��
�
�
��
}
{
, , , ,
, ,
,
, , , , , ,
} { , , , , , }
. .{
, , , ,
, ,
7
0 15 71115 6
72
0 2 3 5 7
14
1�
�
��
�
�
�� �
con
6
3
012 4 5 6 7
0 2 3 5
1
0
1
1� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
,
, , , , , ,
}
{
, , , ,7
14 6
0
3
012 4 5 6 7
1 0 4 6
, ,
,
, , , , , ,
} { , ,
�
�
��
�
�
��
�
�
��
�
�
�� �
con
, , , }1014 7 1
�
�
�
�
�
�
�
�
�
�
�
�
,
äëÿ êîòîðûõ ñîâåðøåííûå ÒÌÔ ñâÿçûâàþùåé ôóíêöèè �1 1 2 3 5( , , , )x x x x èìåþò
âèä
7.1. �
1
1 1�{0,3,4,5,9,10,12,15} ; 7.2. �
1
1 1�{1,2,6,7,8,11,13,14} ,
à ñîâåðøåííûå ÒÌÔ îñòàòî÷íîé ôóíêöèè
� �( , , , )x x x1 3 4 1 îïðåäåëÿþòñÿ êàê
7.1. �1 1�{1,5,6,7,11,15} ;
7.2. �1 �{0,4,6,7,10,14}1.
Òàêèì îáðàçîì, äëÿ ìàñêè p q, -ðàçáèåíèÿ
{ }l l l l l l l1 3 4 1 2 3 5| ïîëó÷èì ïðîñòóþ íåðàçäåëèòåëüíóþ äå-
êîìïîçèöèþ (ðèñ. 7) âèäà (2)
� � � �( , ( )) ( , , , ( , , , ))X X x x x x x x xp q
1 1 3 4 1 1 2 3 5� .
Äàííûé ðåçóëüòàò ñîâïàäàåò ñ ðåøåíèåì äåêîìïîçèöèè â [1, ñ. 374].
4. ÏÎÂÒÎÐÍÀß ÍÅÐÀÇÄÅËÈÒÅËÜÍÀß ÔÓÍÊÖÈÎÍÀËÜÍÀß ÄÅÊÎÌÏÎÇÈÖÈß
Êàê è â ñëó÷àå ðàçäåëèòåëüíîé äåêîìïîçèöèè, ïîâòîðíàÿ íåðàçäåëèòåëüíàÿ äå-
êîìïîçèöèÿ çàäàííîé ôóíêöèè f ïî ìåòîäó p q, -ðàçáèåíèÿ êîíúþíêòåðìîâ è
êëîíèðîâàíèÿ èìååò ìåñòî òîãäà, êîãäà ìîùíîñòü k åå ðàñøèðåííûõ ìàêñèìàëü-
íûõ êëîíîâ áîëüøå äâóõ, ò.å. êîãäà k � 3. Ñóùåñòâîâàíèå ïîâòîðíîé íåðàçäåëè-
òåëüíîé ôóíêöèîíàëüíîé äåêîìïîçèöèè ôîðìóëèðóåò ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 3. Áóëåâàÿ ôóíêöèÿ f x x xn( , ,... , )1 2 , çàäàííàÿ (ñîâåðøåííîé) ÒÌÔ,
äîïóñêàåò ïîâòîðíóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ òîãäà è òîëüêî òîãäà, êîãäà
õîòÿ áû äëÿ îäíîé ìàñêè p q, -ðàçáèåíèÿ ëèòåðàëîâ, èìåþùåé â îáîèõ êëàññàõ îá-
ùèå ýëåìåíòû, ÷òî ñîñòàâëÿåò ìíîæåñòâî Z x x x
c
�{ }� � �1 2
, ,... , , c n� �{ }12 3, ,... , ,
ìîùíîñòü k ìíîæåñòâà åå ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ, ïîëó÷åííûõ â ðå-
çóëüòàòå ïðîöåäóðû êëîíèðîâàíèÿ, ïðèíèìàåò çíà÷åíèå k � 3 , ïðè÷åì:
1) åñëè ýòî óñëîâèå âûïîëíÿåòñÿ äëÿ êëîíîâ p-êëàññà, òî èìååò ìåñòî îäíî-
áëî÷íàÿ ïîâòîðíàÿ íåðàçäåëèòåëüíàÿ äåêîìïîçèöèÿ âèäà � � �( ( ), ( ),...11 12X Xp p
... , ( ), )�1s
p qX X ;
2) åñëè ýòî óñëîâèå âûïîëíÿåòñÿ äëÿ êëîíîâ q-êëàññà, òî èìååò ìåñòî îäíîáëî÷íàÿ ïî-
âòîðíàÿ íåðàçäåëèòåëüíàÿ äåêîìïîçèöèÿ âèäà � �( , ( ),X Xp q
21 � �22 2( ),... , ( ))X Xq
s
q ;
3) åñëè ýòî óñëîâèå âûïîëíÿåòñÿ äëÿ êëîíîâ p- è q-êëàññîâ, òî èìååò ìåñòî
äâóõáëî÷íàÿ ïîâòîðíàÿ íåðàçäåëèòåëüíàÿ äåêîìïîçèöèÿ âèäà
� � � � � �( ( ), ( ),... , ( ), ( ), ( ),...11 12 1 21 221
X X X X Xp p
s
p q q , ( ))�2 2s
qX .
Äîêàçàòåëüñòâî òåîðåìû, êàê è â ñëó÷àå ïîâòîðíîé ðàçäåëèòåëüíîé äåêîìïîçè-
öèè [17], âûòåêàåò íåïîñðåäñòâåííî èç ñîîòâåòñòâèÿ ìåæäó óïðîùåííîé äåêîìïî-
çèöèîííîé êàðòîé, îáðàçîâàííîé ïðîöåäóðîé p q, -ðàçáèåíèÿ äëÿ ìàñêè ëèòåðàëîâ,
èìåþùåé â îáîèõ êëàññàõ íåêîòîðîå êîëè÷åñòâî îáùèõ ýëåìåíòîâ, è ðàñøèðåííû-
ìè ìàêñèìàëüíûìè êëîíàìè çàäàííîé ôóíêöèè f .
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
�
1
3
4
x
x
x
x
x
x
x
5
3
2
1
2�
Ðèñ. 7
x4
x3
x1
f
 äàííîì ñëó÷àå ÷èñëî ðàñøèðåííûõ ÷àñòè÷íûõ êëîíîâ äëÿ êàæäîé ìàñêè ñî-
ñòàëÿåò îò òðåõ è áîëåå, è ñôîðìèðîâàííûå âñëåäñòâèå èõ îáúåäèíåíèÿ ìíîæåñòâà
ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ áóäóò èìåòü ìîùíîñòü k � 3 , à èõ êîëè÷åñòâî
áóäåò îïðåäåëÿòüñÿ êîìáèíàòîðíî ÷èñëîì ðàñøèðåííûõ ÷àñòè÷íûõ êëîíîâ äëÿ
êàæäîé ìàñêè ëèòåðàëîâ ñ ôèêñèðîâàííûì ÷èñëîì c. Óêàçàííóþ îñîáåííîñòü ïî-
âòîðíîé íåðàçäåëèòåëüíîé äåêîìïîçèöèè èëëþñòðèðóåò ñëåäóþùèé ïðèìåð.
Ïðèìåð 6. Ïî ìåòîäó p q, -ðàçáèåíèÿ ìèíòåðìîâ íàéòè íåðàçäåëèòåëüíóþ ïî-
âòîðíóþ äåêîìïîçèöèþ âèäà � � �( , ( ), ( ))X X Xp q q
21 22 ÷àñòè÷íîé ôóíêöèè
f x x x x( , , , )1 2 3 4 , ðàññìîòðåííîé â ïðèìåðå 2, äëÿ ìàñêè ëèòåðàëîâ { }l l l l l1 2 2 3 4| .
Ðåøåíèå.
Ïîñêîëüêó ìîùíîñòè ñôîðìèðîâàííûõ ìíîæåñòâ ðàñøèðåííûõ êëîíîâ
k k0 1 3� � , òî ñîãëàñíî (14) îáùåå ÷èñëî ïîïàðíûõ âûáîðîê K s ýòèõ ìíîæåñòâ
ðàâíî 3!. Ñëåäîâàòåëüíî, ïîñëå îïåðàöèè îáúåäèíåíèÿ êîëè÷åñòâî âîçìîæíûõ ðå-
øåíèé íåðàçäåëèòåëüíîé äåêîìïîçèöèè îïðåäåëÿò ñëåäóþùèå ìíîæåñòâà ðàñøè-
ðåííûõ ìàêñèìàëüíûõ êëîíîâ q-êëàññà çàäàííîé ôóíêöèè f :
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 33
;
1110}1101,1010,0111,0110,0101,0010,{0001,
1111}1001,000,10100,0011,{0000,
0
1
��
�
�
�Y
�
�
�
�
�
�
0
1
43221
110}|11101,|11
010,|10111,|01110,|01101,|01010,|00001,|{00
111}|11001,|10000,|01100,|01011,|00000,|{00
}|{ lllll
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
��
�
�
��
�
�
�
�
�
�
�
��
�
��
�
�
�
�
|
0
|
0
|
|
0
1
|
1
431
1
|
0
|
0
1
|
1
431
0
7}|1(5,6),|)3,1{(7}|16,|)3,1(5,|)3,1{(
6}|35,|37,|16,|15,|1{
7}|34,|1{7}|34,|1{
}1|1{
2}|)2(0,1,|{02}|22,|01,|{0
1)}|3,2|00,|{(0,2)1}|20,|23,|00,|{0
}0|0{
clo
clo
lll
lll
.
}C,C,{C}7
1
3
,6,5
3,1
,4
1
{
}C,C,{C}2
2,0
,1
0
2
,3,0
2,0
{}3
0
,2
2,0
,1
0
2
,0
2,0
{
1
3
1
2
1
1
|
0
3
0
2
0
1
|
�
�
�
�
�
�
���
�
�
��
�
�
��
�
�
��
�
��
��
�
�
��
�
�
�
�
���
�
�
��
�
��
��
�
�
��
�
�
��
�
�
��
�
�
�
���
�
�
��
�
�
���
�
�
��
�
��
��
�
�
��
�
�
��
�
�
��
�
�
�
�
clo
clo
1. }7,2
2,1,0
3
,6,5,1
3,1,0
2
,4,3,0
2,1,0
{}C,C,{C 01
33
01
22
01
11 ��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
�
� ;
2. }6,5,2,7,1
1,0
3,2
,4,3,0
2,1,0
{}C,C,{C 2
2
01
32
01
23
01
11 �
�
�
�
�
�
�
�
��
�
�
��
�
�
��
�
�
��
�
�
�
�
E
;
3. }7,2
2,1,0
3
,4,1
0
2,1
,6,5,3,0
3,1
2,0
{}C,C,{C 01
33
01
21
01
12 ��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
� ;
4. }4,2
2,0
1
,7,1
1,0
3,2
,6,5,3,0
3,1
2,0
{}C,C,{C 01
31
01
23
01
12 ��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
� ;
5. }6,5,2,4,1
0
2,1
,7,3,0
1
3,2,0
{}C,C,{C 2
2
01
32
01
21
01
13 �
�
�
�
�
�
�
�
��
�
�
��
�
�
��
�
�
��
�
�
�
E
;
6. }4,2
2,0
1
,6,5,1
3,1,0
2
,7,3,0
1
3,2,0
{}C,C,{C 01
31
01
22
01
13 ��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
��
�
�
� .
Ñîãëàñíî òåîðåìå 3 çàäàííàÿ ôóíêöèÿ f äëÿ ìàñêè { }l l l l l1 2 2 3 4| äîïóñêàåò ïî-
âòîðíóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ âèäà � � �( , ( ), ( ))X X Xp q q
21 22 , ïî-
ñêîëüêó ìîùíîñòü åå ðàñøèðåííûõ ìàêñèìàëüíûõ êëîíîâ ðàâíà òðåì. ×òîáû îïðå-
äåëèòü ñâÿçûâàþùèå ôóíêöèè �21, �22 è îñòàòî÷íóþ ôóíêöèþ �, âûïîëíèì ïðîöå-
äóðû êîäèðîâàíèÿ è êîíêàòåíèðîâàíèÿ.  äàííîì ñëó÷àå k � 3 . Ñëåäîâàòåëüíî,
òðåáóåòñÿ 2-ðàçðÿäíîå êîäèðîâàíèå ôèêñèðîâàííûõ ìíîæåñòâ ïîëó÷åííûõ êëîíîâ
[17]. Ïðè ýòîì ÷èñëî âîçìîæíûõ âàðèàíòîâ êîäèðîâàíèÿ áóäåò ðàâíî 3 24
4
3!C � .
Äëÿ âûïîëíåíèÿ óïîìÿíóòûõ ïðîöåäóð âûáåðåì èç ïîëó÷åííûõ ìíîæåñòâ ðàñ-
øèðåííûõ ìàêñèìàëüíûõ êëîíîâ ðåøåíèå 2, ïðèìåíèâ îäèí èç âàðèàíòîâ êîäèðî-
âàíèÿ:
{
, ,
, , ,
,
,
, , , ,
012
0 3 4
2 3
01
17 2 5 6
2
2�
�
�
��
�
�
��
�
�
��
�
�
��
�
�E
�
�
�
�
�
�
�
�
�
�
��
�
�
��
�
} {
, ,
,
,
,
cod 012 2 3
0121
0
22
0
21
0
22
1� � � �
�
��
�
�
��
�
�
�
�
�
�
�
�
�, }
E
2
2 21
1
22
0� �
�
�
�
�
��
�
�
��
�
�
��
�
�
��
�
{
, ,
,
,
,
,
00 0110
00
1011
0111
01 10
2
2E�
�
�
�
�
�
�
�} , , , ,
con
{ }0000 0100100010011101 1.
Äëÿ âûáðàííîãî ðåøåíèÿ 2 ñîâåðøåííûå ÒÌÔ
ñâÿçûâàþùèõ �21, �22 è îñòàòî÷íîé � ôóíêöèé
èìåþò âèä
�
21
1 17�{ } , �
22
1 17�{ } , �1 10 4 8 913�{ }, , , , .
Òàêèì îáðàçîì, çàäàííàÿ ôóíêöèÿ f äëÿ ìàñêè
{ }l l l l l1 2 2 3 4| èìååò ïîâòîðíóþ íåðàçäåëèòåëüíóþ îä-
íîáëî÷íóþ äåêîìïîçèöèþ (ðèñ. 8) âèäà
� � � � � �( , ( ), ( )) ( , , ( , , ), (X X X x x x x x xp q q
21 22 1 2 21 2 3 4 22 2� , , ))x x3 4 .
5. ÍÅÐÀÇÄÅËÈÒÅËÜÍÀß ÄÅÊÎÌÏÎÇÈÖÈß ÑÈÑÒÅÌÛ ÔÓÍÊÖÈÉ
Ïîä íåðàçäåëèòåëüíîé äåêîìïîçèöèåé ñèñòåìû m áóëåâûõ ôóíêöèé îò n ïåðå-
ìåííûõ F X f X f X f Xm( ) ( ), ( ),... , ( )�{ }1 2 , X x x xn�{ }1 2, ,... , , áóäåì ïîíèìàòü
ðàçëîæåíèå êàæäîé åå ôóíêöèè fi , i m�12, ,... , , íà ñóïåðïîçèöèþ äâóõ ëèáî òðåõ
ôóíêöèé, ïðåäñòàâëÿåìîé ïî ìåòîäó p q, -ðàçáèåíèÿ êîíúþíêòåðìîâ ñîîòâåòñòâó-
þùèìè âûðàæåíèÿìè àíàëîãè÷íî (1), (2) è (3):
F X X Xp q( ) ( ( ), ),� " "1
(15)
F X X Xp q( ) ( , ( )),� " "2
(16)
F X X Xp q( ) ( ( ), ( )).� " " "1 2
(17)
Çäåñü "1 11 12 1 1
� � �{ }� � �, � d è "2 21 22 2 2
� � �{ }� � �, � d — ìíîæåñòâà ñâÿçûâàþ-
ùèõ ôóíêöèé �1i è �2i , " � � �{ }� � �( ) ( ) ( ),1 2 � m — ìíîæåñòâà îñòàòî÷íûõ ôóíê-
öèé �( )i , ïðè÷åì �1i , �2i è �( )i çàâèñÿò îò ìåíüøåãî ÷èñëà ïåðåìåííûõ, ÷åì fi ;
d1, d2 — êîëè÷åñòâà ñâÿçûâàþùèõ ôóíêöèé ñîîòâåòñòâåííî p- è q-êëàññîâ. Ïðè
ýòîì èìåþò ìåñòî íåðàâåñòâà d q n1 � # �2 â (15), d n q n2 � � # �2 â (16),
d d n1 2� # �2 â (17) , q n� �{ }2 3 2, ,... , ( ) .
Êàæäîå ðàâåíñòâî (15), (16), (17) ðàâíîñèëüíî ñèñòåìå ôóíêöèé fi , i m�12, ,... , ,
ïðåäñòàâëåííûõ ñîîòâåòñòâóþùèì äåêîìïîçèöèîííûì âûðàæåíèåì
f X Xi i i
p q� � �( ) ( ( ), )1 , f X Xi i
p
i
q� � �( ) ( , ( ))2 , f X Xi i i
p
i
q� � � �( ) ( ( ), ( ))1 2 .
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
22�
21�
1
2
x
x
2
3
4
x
x
x
f�
Ðèñ. 8
Çàìåòèì, ÷òî â äàííîì ñëó÷àå ïðèìåíÿþòñÿ âñå íåîáõîäèìûå òåîðåòè÷åñêèå ïî-
ëîæåíèÿ è îïðåäåëåíèÿ ìåòîäà q-ðàçáèåíèÿ êîíúþíêòåðìîâ (â òîì ÷èñëå ôóíê-
öèé, çàäàííûõ â ÄÍÔ), îòíîñÿùèåñÿ ê ðàçäåëèòåëüíîé [16–18] è èçëîæåííîé
âûøå íåðàçäåëèòåëüíîé ôóíêöèîíàëüíîé äåêîìïîçèöèè. Ïîýòîìó íà îñíîâàíèè
óæå ðàññìîòðåííîãî ìîæíî ñôîðìóëèðîâàòü òåîðåìó 4 î ñóùåñòâîâàíèè ñîâìåñò-
íîé ïðîñòîé íåðàçäåëèòåëüíîé äåêîìïîçèöèè è òåîðåìó 5 î ñóùåñòâîâàíèè ñîâ-
ìåñòíîé áëî÷íî-ïîâòîðíîé íåðàçäåëèòåëüíîé äåêîìïîçèöèè ñèñòåìû áóëåâûõ
ôóíêöèé F X( ) .
Òåîðåìà 4. Ñèñòåìà áóëåâûõ ôóíêöèé F X f X f X f Xm( ) ( ), ( ),... , ( )�{ }1 2 ,
X x x xn�{ }1 2, ,... , , çàäàííàÿ ñèñòåìîé ÒÌÔ { }Y Y Ym1
1
2
1 1, ,... , , äîïóñêàåò ñîâìåñòíóþ
ïðîñòóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ òîãäà è òîëüêî òîãäà, êîãäà õîòÿ áû äëÿ
îäíîé ìàñêè p q, -ðàçáèåíèÿ ëèòåðàëîâ, èìåþùåé â îáîèõ êëàññàõ îáùèå ýëåìåíòû,
÷òî ñîñòàâëÿþò ìíîæåñòâî Z x x x
c
�{ }� � �1 2
, ,... , , c n� �{ }12 3, ,... , , ìîùíîñòü ìíî-
æåñòâ ñèñòåìíûõ ðàñøèðåííûõ êëîíîâ åå ôóíêöèé ñîñòàâëÿåò íå áîëüøå äâóõ, à
ìíîæåñòâà èõ ôèêñèðîâàííûõ ñóáìèíòåðìîâ îäèíàêîâû, ïðè÷åì:
1) åñëè êëîíû p-êëàññà, òî èìååì îäíîáëî÷íóþ íåðàçäåëèòåëüíóþ äåêîìïî-
çèöèþ âèäà "( ( ), )�1 X Xp q , ïðè ýòîì â (15) "1 1� � è d1 1� ;
2) åñëè êëîíû q-êëàññà, òî èìååì îäíîáëî÷íóþ íåðàçäåëèòåëüíóþ äåêîìïîçè-
öèþ âèäà "( , ( ))X Xp q�2 , ïðè ýòîì â (16) "2 2� � è d2 1� ;
3) åñëè êëîíû p- è q-êëàññà, òî èìååì äâóõáëî÷íóþ íåðàçäåëèòåëüíóþ äåêîì-
ïîçèöèþ âèäà "( ( ), ( ))� �1 2X Xp q , ïðè ýòîì â (17) "1 1� � , "2 2� � è d d1 2 1� � .
Äîêàçàòåëüñòâî òåîðåìû 4 íåïîñðåäñòâåííî âûòåêàåò èç ðàññìîòðåííûõ ðàíåå
â [18] è èçëîæåííûõ âûøå îïðåäåëåíèé è ïîëîæåíèé, à òàêæå èç òåîðåìû 2 î ñó-
ùåñòâîâàíèè ïðîñòîé íåðàçäåëèòåëüíîé äåêîìïîçèöèè áóëåâîé ôóíêöèè f X( ) êàê
îáîáùåíèå èõ íà ñèñòåìó F X( ) .
Òåîðåìà 5. Ñèñòåìà áóëåâûõ ôóíêöèé F X f X f X f Xm( ) ( ), ( ),... , ( )�{ }1 2 ,
X x x xn�{ }1 2, ,... , , çàäàííàÿ ñèñòåìîé ÒÌÔ { }Y Y Ym1
1
2
1 1, ,... , , äîïóñêàåò ñîâìåñòíóþ
áëî÷íî-ïîâòîðíóþ íåðàçäåëèòåëüíóþ äåêîìïîçèöèþ òîãäà è òîëüêî òîãäà, êîãäà
õîòÿ áû äëÿ îäíîé ìàñêè p q, -ðàçáèåíèÿ ëèòåðàëîâ, èìåþùåé â îáîèõ êëàññàõ îá-
ùèå ýëåìåíòû, ÷òî ñîñòàâëÿþò ìíîæåñòâî Z x x x
c
�{ }� � �1 2
, ,... , , c n� �{ }12 3, ,... , ,
ìîùíîñòü k ìíîæåñòâ ñèñòåìíûõ ðàñøèðåííûõ êëîíîâ ôóíêöèé ðàâíà íå ìåíüøå
òðåõ, ò.å. k � 3, à ìíîæåñòâà èõ ôèêñèðîâàííûõ ñóáìèíòåðìîâ îäèíàêîâû, ïðè÷åì:
1) åñëè êëîíû p-êëàññà, òî èìååì îäíîáëî÷íóþ d1-ïîâòîðíóþ íåðàçäåëèòåëü-
íóþ äåêîìïîçèöèþ âèäà " "( ( ), )1 X Xp q ;
2) åñëè êëîíû q-êëàññà, òî èìååì îäíîáëî÷íóþ d2 -ïîâòîðíóþ íåðàçäåëèòåëü-
íóþ äåêîìïîçèöèþ âèäà " "( , ( ))X Xp q
2 ;
3) åñëè êëîíû p- è q-êëàññîâ, òî èìååì äâóõáëî÷íóþ d d1 2, -ïîâòîðíóþ íåðàç-
äåëèòåëüíóþ äåêîìïîçèöèþ âèäà " " "( ( ), ( ))1 2X Xp q .
Äîêàçàòåëüñòâî òåîðåìû 4 âûòåêàåò íåïîñðåäñòâåííî èç ðàññìîòðåííûõ ðàíåå
â [18] è èçëîæåííûõ âûøå îïðåäåëåíèé è ïîëîæåíèé, à òàêæå èç òåîðåìû 3 î ñó-
ùåñòâîâàíèè áëî÷íî-ïîâòîðíîé íåðàçäåëèòåëüíîé äåêîìïîçèöèè áóëåâîé ôóíêöèè
f X( ) êàê îáîáùåíèå èõ íà ñèñòåìó F X( ) .
Ðàññìîòðèì ïðèìåð [7, 8] ñîâìåñòíîé íåðàçäåëèòåëüíîé äåêîìïîçèöèè ñèñòå-
ìû ÷àñòè÷íûõ áóëåâûõ ôóíêöèé, çàäàííûõ â ÄÍÔ.
Ïðèìåð 7. Ïî ìåòîäó p q, -ðàçáèåíèÿ íàéòè ñîâìåñòíóþ íåðàçäåëèòåëüíóþ äå-
êîìïîçèöèþ âèäà (16) " "( , ( ))X Xp q
2 ñèñòåìû ÷àñòè÷íûõ ôóíêöèé
F X f X f X( ) ( ), ( )�{ }1 2 , X x x x x�{ }1 2 3 4, , , , çàäàííîé òàáëèöåé èñòèííîñòè
(ñì. òàáë. 1) äëÿ ìàñêè { }l l l l l1 4 2 3 4| .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 35
Ðåøåíèå. Òàáëè÷íî çàäàííàÿ ñèñòåìà ÷àñòè÷-
íûõ ôóíêöèé f1 è f2 èìååò òàêóþ ÒÌÔ { }Y Y
1
1
2
1, :
Y1 �
{0000,0001,0010,0101,1000,1001,1010}
{0011,0110
1
,0111,1011,1110,1111}0
�
�
��
;
Y2 �
{0000,0010,0101,0111,1101,1111}
{0110,1000,1010
1
,1110}0
�
�
��
.
Äëÿ f1 èìååì
{ }l l l l l1 4 2 3 4| �
{00|000,01|001,00|010,01|101,10|000,11|001,10|010}
01|011,00|110,01|111,11|011,10|110
1
{ ,11|111}0
�
�
��
�
Ïîñëå âûáîðîê (K s � 2) è îáúåäèíåíèé { }C C C C
1
0
1
1
2
0
2
1� �, è { }C C C C
1
0
2
1
2
0
1
1� �,
ïîëó÷èì äâà ìíîæåñòâà ìàêñèìàëüíûõ ðàñøèðåííûõ êëîíîâ ôóíêöèè f1:
1.1. { , , , , , , }
E
E
2
2
2
2 1012 5 3 6 7
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
; 1.2. {
,
,
, , , ,
,
,
, , }
0 2
13
0 2 3 7
13
0 2
15 6 1
�
�
��
�
�
��
�
�
��
�
�
�� .
Çàìåòèì, ÷òî â îáoèõ ìíîæåñòâàõ îòñóòñòâóåò êëîí
�
�
�
�
��
�
�
��4 , èìåþùèé íåñó-
ùåñòâóþùèå íåôèêñèðîâàííûå ñóáìèíòåðìû. Òàêîé êëîí óñëîâíî íàçîâåì ñâîáîä-
íûì, ïîñêîëüêó åãî ìîæíî ïðèñîåäèíèòü (îïåðàöèåé îáúåäèíåíèÿ) ê ëþáîìó äðó-
ãîìó êëîíó èç òîãî æå ìíîæåñòâà è òåì ñàìûì ñôîðìèðîâàòü îïòèìàëüíóþ ñòðóê-
òóðó ñîâìåñòíîé äåêîìïîçèöèè çàäàííîé ñèñòåìû.
Äëÿ f2 èìååì
{ }
{00|000,00|010,01|101,01|111,11|101,
l l l l l1 4 2 3 4| �
11|111}
{00|110,10|000,10|010,10|110}
1
0
�
�
��
�
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
x1 x2 x
3
x
4
f1 f2
0 0 – 0 1 1
1 0 – 0 1 0
– 0 0 – 1 ~
– – 1 1 0 ~
– 1 1 0 0 0
– 1 – 1 ~ 1
0 – 0 1 1 ~
Ò à á ë è ö à 1
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
���
�
�
��
�
�
�
�
�
�
�
�
��
�
�
�
�
��
�
���
�
�
��
�
��
��
�
�
��
�
�
�
�
�
�
�
��
�
�
�
�
��
�
�
�
��
�
�
��
}{}7,5
3,1
{
}{
(5,7)}|{(1,3)
7}|(1,3)5,|{(1,3)7}|35,|37,|15,|{1
}1|1{
},{}6
2,0
,2,0
2
0
{
}0,2)(|26,|0,2){(}2|20,
|26,|0,2){(}6|22,|20,|26,|0{
(0,2)}|{02}|00,|{02}|00,|{0
}0|0{
1
1
|
0
1
|
|
1
|
1
321
0
2
0
1
|
0
|
0
|
0
1
|
1
|
1
321
Clll
CClll
clo
clo
.
�
�
�
�
�
��
�
�
�
�
�
�
�
�
��
�
�
��
�
�
�
�
��
�
�
��
�
�
��
|
0
|
0
|
0
1
|
1
321
|
0
|
0
1
|
1
|
1
321
}(3,7)|1,3){(}7|(1,3)3,|1,3){(}7|33,|37,|13,|1{
5}|11,|{(1,3)1}|35,|11,|{1
}1|1{
}6|0,2){(}6|26,|0{
(0,2)}|{(0,2)2}|(0,2)0,|{(0,2)2}|0,2|2,2|0,0|{0
}0|0{
clo
clo
lll
lll
.
},{}7,3
3,1
,5,1
3,1
{}7,3
3,1
,5
1
,1
3,1
{
},{}6
2,0
,2,0
2,0
{
1
2
1
1
||
0
2
0
1
|
�
�
�
�
�
�
���
�
�
��
�
��
��
�
�
��
�
�
�
���
�
�
��
�
��
��
�
�
��
�
�
���
�
�
��
�
�
�
�
���
�
�
��
�
��
��
�
�
��
�
�
�
�
CC
CC
addclo
clo
Îòñþäà äëÿ f2 ïîñëå âûáîðîê ( )K s � 2 è îáúåäèíåíèé { , }C C C
1
0
1
1
2
0� è
{ , }C C C
1
0
2
0
1
1� ïîëó÷èì:
2.1. {
, ,
, , , ,
,
}
013
0 2 5 7
0 2
6 2�
�
�
��
�
�
��
��
�
��
�
�
�� ; 2.2. { , ,
,
,
, , }
0
2
0 2
13
0 2
5 6 7 2
�
�
��
�
�
��
�
�
��
�
�
�� .
Ôóíêöèÿ f2 èìååò òðè ñâîáîäíûõ êëîíà:
�
�
�
�
��
�
�
��1 ,
�
�
�
�
��
�
�
��3 è
�
�
�
�
��
�
�
��4 , ïðè÷åì ïîñëåä-
íèé ÿâëÿåòñÿ îáùèì äëÿ îáåèõ ôóíêöèé, ÷òî ïîçâîëÿåò èñêëþ÷èòü åãî èç ñèñòåìû.
Äðóãèå äâà ñâîáîäíûõ êëîíà ôóíêöèè f2 ðàñïðåäåëèì ïî ïîëó÷åííûì âûøå êëî-
íàì, îêîí÷àòåëüíî ñôîðìèðîâàâ òàêèì îáðàçîì ñëåäóþùèå ÷åòûðå ìíîæåñòâà ìàê-
ñèìàëüíûõ ðàñøèðåííûõ êëîíîâ ôóíêöèè f2 :
2.1. {
, ,
, , , , ,
,
,
, }
013
2
012 5 7
13
0 2
3 6 2
�
�
��
�
�
��
�
�
��
�
�
�� ; 2.2. {
, ,
, , , , ,
,
,
, }
013
2
0 2 3 5 7
13
0 2
16 2
�
�
��
�
�
��
�
�
��
�
�
�� ;
2.3. {
, ,
, , , , , ,
,
,
}
013
2
012 3 5 7
13
0 2
6 2
�
�
��
�
�
��
�
�
��
�
�
�� ; 2.4. {
, ,
, , , ,
,
,
, , }
013
2
0 2 5 7
13
0 2
13 6 2
�
�
��
�
�
��
�
�
��
�
�
�� .
Äëÿ ðåàëèçàöèè ñîâìåñòíîé íåðàçäåëèòåëüíîé äåêîìïîçèöèè çàäàííîé ñèñòåìû
íåîáõîäèìî îïðåäåëèòü ÿäðî ñèñòåìû [18], íà îñíîâàíèè êîòîðîãî ñòðîÿòñÿ ñèñòåìíûå
ðàñøèðåííûå êëîíû. ßäðî ñèñòåìû — ýòî îáùåå ìíîæåñòâî ôèêñèðîâàííûõ ñóáìèí-
òåðìîâ ìàêñèìàëüíûõ ðàñøèðåííûõ êëîíîâ ôóíêöèé çàäàííîé ñèñòåìû. Îïðåäåëèòü
åãî ìîæíî ïóòåì ïîïàðíî âçàèìíûõ ïåðåñå÷åíèé ñîîòâåòñòâóþùèõ ìíîæåñòâ ôèêñè-
ðîâàííûõ ñóáìèíòåðìîâ. Îáîçíà÷èì ìíîæåñòâà ôèêñèðîâàííûõ ñóáìèíòåðìîâ ïîëó-
÷åííûõ ìàêñèìàëüíûõ ðàñøèðåííûõ êëîíîâ ôóíêöèé ñèñòåìû:
äëÿ f1: 1.1. A11 012 5�{ }, , , , B11 3 6 7�{ }, , ; 1.2. A12 0 2 3 7�{ }, , , , B12 15 6�{ }, , ;
äëÿ f2 : 2.1. A21 012 5 7�{ }, , , , , B21 3 6�{ }, ; 2.2. A22 0 2 3 5 7�{ }, , , , , B22 16�{ }, ;
2.3. A23 012 3 5 7�{ }, , , , , , B23 6�{ }; 2.4. A24 0 2 5 7�{ }, , , , B24 13 6�{ }, , .
Ïîïàðíî âçàèìíûå ïåðåñå÷åíèÿ îòíîñèòåëüíî âîçìîæíûõ ðåøåíèé ôóíêöèè
f1 äàþò òàêèå ðåçóëüòàòû:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 37
1.
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
��
�
�
�
�
�
��
�
�
�
�
�
�
)5,2,0(
)5,2,1,0(
)5,2,0(
)5,2,1,0(
)7,5,2,0(
)7,5,3,2,1,0(
)7,5,3,2,0(
)7,5,2,1,0(
)5,2,1,0(
24
23
22
21
11
A
A
A
A
A ,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
��
�
�
�
�
�
��
�
�
�
�
�
�
)6,3(
)6(
)6(
)6,3(
)6,3,1(
)6(
)6,1(
)6,3(
)7,6,3(
24
23
22
21
11
B
B
B
B
B ;
2.
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
��
�
�
�
�
�
��
�
�
�
�
�
�
)7,2,0(
)7,3,2,0(
)7,3,2,0(
)7,2,0(
)7,5,2,0(
)7,5,3,2,1,0(
)7,5,3,2,0(
)7,5,2,1,0(
)7,3,2,0(
24
23
22
21
12
A
A
A
A
A ,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
��
�
�
�
�
�
��
�
�
�
�
�
�
)6,1(
)6(
)6,1(
)6(
)6,3,1(
)6(
)6,1(
)6,3(
)6,5,1(
24
23
22
21
12
B
B
B
B
B .
Ïîëó÷åííûå ïåðåñå÷åíèÿ ìàêñèìàëüíîé ìîùíîñòè ñîñòàâëÿþò ÿäðî çàäàííîé
ñèñòåìû, ëåæàùåé â îñíîâå îáùåé ñâÿçûâàþùåé ôóíêöèè �1 2 3 4( , , )x x x äëÿ äâóõ
ðåøåíèé äåêîìïîçèöèè:
1. A A A A A� � � � �11 21 11 23 012 5( , , , ); B B B B B� � � � �11 21 11 24 3 6( , ) ;
2. A A A A A� � � � �12 22 12 23 0 2 3 7( , , , ); B B B B B� � � � �12 22 12 24 16( , ) .
Òåïåðü ñèñòåìíûå ðàñøèðåííûå êëîíû ôóíêöèé çàäàíîé ñèñòåìû äëÿ äâóõ ðå-
øåíèé ñîâìåñòíîé äåêîìïîçèöèè îêîí÷àòåëüíî èìåþò âèä:
äëÿ f1: 1. { , , , , , }
E
E
2
2
2
2 1012 5 3 6
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
; 2. { , , , , , }
E
E
2
2
2
2 10 2 3 7 16
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
;
äëÿ f2 : 1. {
, ,
, , , ,
,
,
, }
013
2
012 5
13
0 2
3 6 2
�
�
��
�
�
��
�
�
��
�
�
�� ; 2. {
, ,
, , , ,
,
,
, }
013
2
0 2 3 7
13
0 2
16 2
�
�
��
�
�
��
�
�
��
�
�
�� .
 ðåçóëüòàòå êîäèðîâàíèÿ è êîíêàòåíèðîâàíèÿ ñîîòâåòñòâóþùèõ ìíîæåñòâ
ñóáìèíòåðìîâ ñèñòåìíûõ ðàñøèðåííûõ êëîíîâ â ñëó÷àå ïåðâîãî ðåøåíèÿ, íàïðè-
ìåð, ïîëó÷èì:
äëÿ f1:
1 012 5 3 6
11
2
2
2
2 1.{ , , , , , }
. .{
E
E
E
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
cod
2
2
1
1
2
2 1
0 2
2
2
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �, } { ,
E
E
E2
1
2
2
1
0
2
2
0 13 5 7
12
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
} { , , , }
. .{ ,
con
E
E
� �
1
1 2
2
2
2
0 1 0 2
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�} { , } { ,
E
E
con
, , }
;
4 6 1
�
�
��
�
�
�
�
äëÿ f2 :
1
01 3
2
012 5
1 3
0 2
3 6 2.{
, ,
, , , ,
,
,
, }
�
�
��
�
�
��
�
�
��
�
�
�� �
cod
�
�
�
��
�
�
��
�
�
��
�
�
�� �
cod
11
013
2
13
0 2
01
1
1
1
0. .{
, ,
,
,
,
} {
,
� �
,
,
,
,
} { , , , , }
. .{
3
2
1
13
0 2
0 1 3 7 2 6
1 2
1�
�
��
�
�
��
�
�
��
�
�
�� �
con
013
2
13
0 2
013
2
0
1
0
1
1, ,
,
,
,
} {
, ,
� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
�
�
�
� ,
,
,
} { , , , , }
.
13
0 2
1 0 2 6 3 7 1
con
Çäåñü ÒÌÔ îáùåé ñâÿçûâàþùåé (÷àñòè÷íîé) ôóíêöèè �1 2 3 4( , , )x x x è îñòàòî÷-
íîé (ïîëíîé) ôóíêöèè � �( , , )x x1 4 1 äëÿ f1 è f2 (ñîîòâåòñòâåííî äëÿ �( )1 è �( )2 )
èìåþò âèä:
1.1. �1
1
0
012 5
3 6
�
�
�
��
{ }, , ,
{ , }
; �( ) , , ,1
113 5 7�{ } ; �( ) , , , ,2
112 3 6 7�{ } ;
1.2. �1
1
0
3 6
012 5
�
�
�
��
{ , }
, , ,
;
{ }
�( ) , , ,1
10 2 4 6�{ } ; �( ) , , , ,2
10 2 3 6 7�{ } .
Òàêèì îáðàçîì, çàäàííàÿ ñèñòåìà (ðèñ. 9) äå-
êîìïîçèðóåòñÿ ê âèäó
" " "( , ( )) ( , , ( , , ))X X x x x x xp q
1 1 4 1 2 3 4� ��
�
�
�
� �
� �
( )
( )
( , , )
( , , )
1 1 4 1
2 1 4 1
x x
x x
.
Ïîëó÷åííûé ðåçóëüòàò ñîâïàäàåò ñ ðåçóëüòàòîì â ðàáîòàõ [5, 6].
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
x
x
x
x
x
4
3
2
4
1
� ( )2
� ( )1
2f
1f
�1
Ðèñ. 9
6. ÂÅÐÈÔÈÊÀÖÈß ÐÅÇÓËÜÒÀÒÎÂ ÔÓÍÊÖÈÎÍÀËÜÍÎÉ ÄÅÊÎÌÏÎÇÈÖÈÈ
×òîáû ñðàâíèòü è ïðîâåðèòü äîñòîâåðíîñòü ðåçóëüòàòîâ äåêîìïîçèöèè, ïîëó÷åí-
íûõ â òåîðåòèêî-ìíîæåñòâåííîì ôîðìàòå ïî ìåòîäó p q, -ðàçáèåíèÿ êîíúþíêòåð-
ìîâ íåêîòîðîé áóëåâîé ôóíêöèè f x x x x xk l n( , ,... , ,... , ,... , )1 2 , ñ ðåçóëüòàòàìè, ïî-
ëó÷åííûìè äðóãèìè àâòîðàìè, èñïîëüçóþùèìè àíàëèòè÷åñêèé ïîäõîä è âûðàæå-
íèÿ, íåîáõîäèìî âûïîëíèòü íåñëîæíûå ïðåîáðàçîâàíèÿ (ïðîöåäóðû) íàä
äâîè÷íûìè ìèíòåðìàìè ÒÌÔ, íàïðèìåð �
1
1, ñâÿçûâàþùåé ôóíêöèè
� � � �1 1 2
( , ,... , )x x x
k
è ÒÌÔ �1 îñòàòî÷íîé ôóíêöèè � � � �( , ,... , )1 2
x x
l
. Ïîñêîëüêó
ðàçðÿäíîñòü äâîè÷íûõ ìèíòåðìîâ ñîâåðøåííûõ ÒÌÔ �
1
1 è ÒÌÔ �1 âñåãäà
ìåíüøå, ÷åì ðàçðÿäíîñòü äâîè÷íûõ ìèíòåðìîâ ñîâåðøåííîé ÒÌÔ Y 1, ò.å.
k l n, , òî ïðåæäå âñåãî íåîáõîäèìî ïðèâåñòè ñîáñòâåííûå êîðòåæè ôóíêöèé �1
è �, ò.å. $ %x x x
k� � �1 2
, ,... , è $ %� � �1 2
, ,... ,x x
l
, ê êîðòåæó çàäàííîé ôóíêöèè f , ò.å.
$ %x x x x xk l n1 2, ,... , ,... , ,... , .  àíàëèòè÷åñêîì ñìûñëå ýòî îçíà÷àåò èñêóññòâåííîå
âíåñåíèå â êîðòåæ ôóíêöèé �1 è � (â êà÷åñòâå íåñóùåñòâåííûõ ïåðåìåííûõ
ýòèõ ôóíêöèé) òåõ ïåðåìåííûõ, êîòîðûå èìååò êîðòåæ ôóíêöèè f . Â ÒÌÔ ýòî
ñîîòâåòñòâóåò íàðàùèâàíèþ ðàçðÿäíîñòè äâîè÷íûõ ìèíòåðìîâ �
1
1 è �1 çà ñ÷åò
âíåñåíèÿ ñèìâîëîâ ïîãëîùåíèÿ «–» è ïðèâåäåíèþ èõ ê âèäó n-ðàçðÿäíûõ ìèíòåð-
ìîâ ñîâåðøåííîé ÒÌÔ Y 1. Ïîñêîëüêó ôóíêöèÿ � èìååò ïåðåìåííóþ �1, êîòîðàÿ
ìîæåò áûòü â ïðÿìîì ëèáî èíâåðñíîì âèäå, òî äëÿ �1 íåîáõîäèìî ïðåäâàðèòåëü-
íî íàéòè ÒÌÔ � �
1
0
2 1
1� En \ . Óêàçàííîìó ïðåîáðàçîâàíèþ � � � �1 1 2
( , ,... , )x x x
k
�
�
�� ���
�
f x x x
f x x x
k n� � � �
� � � �
1 1 2
1 1 2
1
0
( , ,... , , )
( , ,... ,
�
k n, )�� ��
�
�
�� �
ñîîòâåòñòâóåò ïðåîáðàçîâàíèå ÒÌÔ
�
1
1 1
1
1
0
�
�
�
��
ô
ô
, ãäå ô
1
1 è ô
1
0 — ïðåîáðàçîâàííûå ñîâåðøåííûå ÒÌÔ �
1
1 è ÒÌÔ �
1
0 ,
ñîîòâåòñòâóþùèå èñòèííîìó f�1 1� è ëîæíîìó f�1 0� çíà÷åíèÿì ñâÿçûâàþùåé
ôóíêöèè �1 îò n ïåðåìåííûõ.
 îòëè÷èå îò �1 ïðåîáðàçîâàíèå îñòàòî÷íîé ôóíêöèè � ê ôîðìàòó çàäàííîé
ôóíêöèè f âûïîëíÿåòñÿ íåçàâèñèìî îò åå ïîäôóíêöèé (îòíîñèòåëüíî �1 1� )
�� � �1 2
1( , ,... , )x x
l
è (îòíîñèòåëüíî �
� 0) �� � �1 2
0( , ,... , )x x
l
, ò.å. � � � �( , ,... , )1 2
x x
l
�
�
� � �� ���
�
� � � � � �
�
1 2 1 2
1
1
0
( , ,... , ) ( , ,... , , )
(
x x f x x
l l n�
, ,... , ) ( , ,... , , )x x f x x
l l n� � � � �2 1 2
� � �� ��
�
�
�� �
, ÷òî ñîîòâåòñòâóåò ïðåîáðàçî-
âàíèþ ÒÌÔ �
�
�
� �
� �
1
1 1
1 1
1 1
1 1
�
�
�
�
�
�
�
ô
ô
, ãäå ô
�
1 è ô
�
1 — ïðåîáðàçîâàííûå ñîâåðøåííûå
ÒÌÔ ïîäôóíêöèé f�1
è f�1
îñòàòî÷íîé ôóíêöèè � îò n ïåðåìåííûõ.
Ïîñëå âûïîëíåííûõ ýòèõ ïðåîáðàçîâàíèé îïðåäåëÿþòñÿ ïåðåñå÷åíèÿ ìíî-
æåñòâ ô ô
1
1 1
1
�
�
è ô ô
1
0 1
1
�
�
, îáúåäèíåíèå êîòîðûõ îáðàçóåò èñêîìóþ ñîâåðøåí-
íóþ ÒÌÔ Y 1 çàäàííîé ôóíêöèè f :
Y ô ô ô ô1
1
1 1
1
0 1
1 1
� � � �
� �
. (18)
Îïèñàííóþ âûøå òåîðåòèêî-ìíîæåñòâåííóþ ìåòîäèêó ïðîâåðêè ðåçóëüòàòîâ
ôóíêöèîíàëüíîé äåêîìïîçèöèè íà îñíîâå ìåòîäà p q, -ðàçáèåíèÿ ìèíòåðìîâ
èëëþñòðèðóåò ñëåäóþùèé ïðèìåð.
Ïóñòü áóëåâà ôóíêöèÿ f x x x x( , , , )1 2 3 4 çàäàíà ñîâåðøåííîé ÒÌÔ
Y 1 10 3 4 6 8101215�{ }, , , , , , , , â ðåçóëüòàòå ðàçäåëèòåëüíîé äåêîìïîçèöèè êîòîðîé äëÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 39
ìàñêè { }l l l l1 2 3 4| ïîëó÷åíû ñîâåðøåííûå ÒÌÔ �
1
1 112�{ }, ñâÿçûâàþùåé ôóíêöèè
�1 1 2( , )x x è �1 10 3 4 6�{ }, , , îñòàòî÷íîé ôóíêöèè � �( , , )1 3 4x x . Äëÿ ôóíêöèè �1 ïðå-
îáðàçîâàíèå �
�
�
1 1 2
1 1 2
0 1 2
1
1
( , )
( , , , )
( , , , )
x x
f x x
f x x
�
� �
� �
�
�
��
�
�
ñîîòâåòñòâóåò ïðåîáðàçîâàíèþ ÒÌÔ
�
�
1
1 1
1
1 1
1
0 0
1
0
0110 01 10
0011
� � � �� ��
� � �
{ } { }
{ }
, ( ), ( )
,
ô
ô { }( ), ( )00 11 0�� ��
�
�
��
, à äëÿ ôóíêöèè � �( , , )1 3 4x x �
�
� � �
� � �
�
�
� �
� �
1 1
1 1
1
0
3 4 3 4
3 4
( , , ) ( , , , )
( , , ) ( , ,
x x f x x
x x f x3 4, )x
�
�
��
ñîîòâåòñòâóåò ïðåîáðàçîâàíèå ÒÌÔ
�
�
�
� �
�
1
1 1 1
1 1
1 1
1
0010 00 10
0011
�
� � � �� ��
�
{ } { }
{ }
, ( ), ( )
,
ô
� � �� ��
�
�
�
� ô
�1
1 00 11{ }( ), ( )
.
Îïðåäåëèâ ñîãëàñíî (18) ïåðåñå÷åíèÿ
ô ô
1
1 1
1
01 10 00 10 0100 011� � �� �� � �� �� �
�
{ } { } {( ), ( ) ( ), ( ) , 010001010
00 11 00 11
1
0 1
1
, ,
( ), ( ) ( ), (
}
{ } {ô ô� � �� �� � �� ��
�
) , , ,} { }�
�
�
�
� 0000 001111001111
è çàòåì îáúåäèíèâ èõ, ïîëó÷èì èñêîìóþ ñîâåðøåííóþ ÒÌÔ Y 1 10 3 4 6 8101215�{ }, , , , , , , .
 ñëó÷àå íåðàçäåëèòåëüíîé ôóíêöèîíàëüíîé äåêîìïîçèöèè âåðèôèêàöèÿ ïî-
ëó÷åííîãî ðåçóëüòàòà âûïîëíÿåòñÿ àíàëîãè÷íûì îáðàçîì. Ïðîèëëþñòðèðóåì ýòî íà
ðàññìîòðåííîì â ï. 2.1 ïðèìåðå 1 ôóíêöèè f x x x x( , , , )1 2 3 4 , çàäàííîé ñîâåðøåííîé
ÒÌÔ Y 1 10 2 4 71114�{ }, , , , , , íàïðèìåð, äëÿ ñëåäóþùèõ ñîâåðøåííûõ ÒÌÔ ðåøå-
íèÿ 1.2: �
1
1 10 2 7�{ }, , ñâÿçûâàþùåé ôóíêöèè �1 1 3 4( , , )x x x è �1 13 4 5 6�{ }, , , îñòàòî÷-
íîé ôóíêöèè � �( , , )1 2 3x x . Ñîãëàñíî îïèñàííîé âûøå ìåòîäèêå ïîëó÷èì:
äëÿ �1: �
�
�
1 1 3 4
1 1 3 4
0 1 3 4
1
1
( , , )
( , , , )
( , , , )
x x x
f x x x
f x x x
�
�
�
�
� �
���
,
�
�
1
1 1
1
1 1
1
0
000 010111 0 00 0 10 1 11� � � � � �
�
{ } { }, , ( ), ( ), ( )ô
{ } {001011100101110 0 01 0 11 1 000
1
0, , , , ( ), ( ), ( ), (� � � � �ô 1 01 1 10 0� �
�
�
�� ), ( )}
;
äëÿ �: � �
�
�
� �
�
( , , )
( , , ) ( , , , )
( , ,
1 2 3
2 3 2 3
2 3
1 1
1
1
0
x x
x x f x x
x x
�
� � �
) ( , , , )� � �
�
�
�� f x x�1 2 3
,
�
�
� �1 1
1 1
011100101110
100101110 0
1 1� �
� � � �
{ }
{ } {
, , ,
, , (ô 0 01 10
011 11
1 1
1 1
� � � � �
� � � � �
�
�
�
�
), ( ), ( )
( )
}
{ } { }�
� �
ô
;
ô ô
1
1 1
1
0 00 0 10 1 11 00 01 1� � � � � � � � � � �
�
{ } {( ), ( ), ( ) ( ), ( ), ( 0 0000 0100 00101011
0 01 0 11
1
0 1
1
� �
� � � �
) , , ,
( ), ( ),
} { }
{ô ô
�
( ), ( ), ( ) ( ) ,
,
1 00 1 01 1 10 11 01111110� � � � � � �
�
�
�
� } { } { }
à ïîñëå îáúåäèíåíèÿ (18) ïîëó÷èì ñîâåðøåííóþ ÒÌÔ Y 1 10 2 4 71114�{ }, , , , , çàäàí-
íîé ôóíêöèè f .
ÂÛÂÎÄÛ
Íà îñíîâàíèè èçëîæåííûõ òåîðåòè÷åñêèõ ïîëîæåíèé òåîðåòèêî-ìíîæåñòâåííîãî
ïîäõîäà ê íåðàçäåëèòåëüíîé äåêîìïîçèöèè áóëåâûõ ôóíêöèé ðàçíûõ ôîðì çàäà-
íèÿ, â òîì ÷èñëå èõ ñèñòåì, è ñðàâíèòåëüíîãî àíàëèçà ïðèâåäåííûõ (è íå ïðèâå-
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
äåííûõ â íàñòîÿùåé ñòàòüå) ìíîãî÷èñëåííûõ ïðèìåðîâ èç ïóáëèêàöèé ðàçíûõ
àâòîðîâ ìîæíî çàêëþ÷èòü, ÷òî ïðåäëîæåííûé ìåòîä p q, -ðàçáèåíèÿ êîíúþíêòåð-
ìîâ ÿâëÿåòñÿ ýôôåêòèâíûì îïòèìèçàöèîííûì ñðåäñòâîì ëîãè÷åñêîãî ñèíòåçà
êîìáèíàöèîííûõ ñõåì.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. C u r t i s H . A . A new approach to the design of switching circuits. — N.J.; Princeton; Toronto: D. Van
Nostrand Company, Inc., 1962. — 635 p.
2. Ô ð è ä ì à í À . , Ì å í î í Ï . Òåîðèÿ è ïðîåêòèðîâàíèå ïåðåêëþ÷àòåëüíûõ ñõåì. — Ì.: Ìèð, 1978.
— 580 ñ.
3. M i s h c h e n k o A . , S t e i n b a c h B . , P e r k o w s k i M . An algorithm for bi-decomposition of logic
functions / Proc. of DAC 2001, June 18–22, Las Vegas. — Ð. 103–108.
4. S c h o l l C . Functional decomposition with application to FPGA synthesis. — Boston; Dordrecht; Lon-
don: Kluwer Academic Publishers, 2001. — 263 p.
5. S a s a o T . A new expansion of symmetric functions and their application to non-disjoint functional de-
compositions for LUT type FPGAs / Proc. of International Workshop on Logic Synthesis, June 2001, Lake
Tahoe, California, May, 2000. — P. 105–110.
6. S a s a o T . , B u t l e r J . T . On bi-decompositions of logic functions / Proc. ACM/IEEE Internation
Workshop on Logic Synthesis, Takoe City, California, May, 1997. — P. 264–300.
7. R a w s k i M . , N o w i c k a M . , J � z' w i a k L . , Lu b a T . Non-disjoint decomposition of Boolean
functions and its application in FPGA-oriented technology mapping // Proc. 23th EUROMicro Conf.’97,
Sept. 1–4., 1997. — Budapest (Hungary), 1997. — P. 24–30.
8. N o w i c k a M . , R a w s k i M . , /Lu b a T . Non-disjoint decomposition strategy for FPGA-based tech-
nology mapping // Proc. PDS’98, 24–25 Feb., 1998. — Gliwice (Poland), 1998. — P. 159–166.
9. Y a m a s h i t a S . , S a w a d a H . , N a g o y a A . New methods to find optimal non-disjoint bi-decompo-
sitions / Proc. ASP-DAC, Feb., 1998. — P. 59–68.
10. S a w a d a H . , Y a m a s h i t a S . , N a g o y a A . Efficient methods for a simple disjoint decomposition
and a non-disjoint bi-decomposition / PDF {sawada, ger, nagoya}@cslab.kecl.ntt.co.jp
11. Ø å ñ ò à ê î â Å . À . Äåêîìïîçèöèÿ ñèñòåì ÷àñòè÷íûõ áóëåâûõ ôóíêöèé ìåòîäîì òîæäåñòâåííûõ
îòîáðàæåíèé // Ëîãè÷åñêîå ïðîåêòèðîâàíèå. — 1997. — Âûï. 2. — Ñ. 115–124.
12. Ì è ù å í ê î  . À . , À ñ ï è ä î â À . È . ,  è ò å ð  .  . è ä ð . Ëîãè÷åñêîå ïðîåêòèðîâàíèå ÁÈÑ /
Ïîä ðåä. Â.À. Ìèùåíêî. — Ì.: Ðàäèî è ñâÿçü, 1984. — 312 ñ.
13. D u b r o v a E . A polynomial time algorithm for non-disjoint decomposition of multi-valued functions /
Proc. 34th International Symposium on Multi-Valued Logic (ISMVL’04), 2004. — P. 309–314.
14. Z a k r e v s k i j A . Decomposition of boolean functions — recognizing a good solution by traces // Infor-
mation Theories & Applications. — 2007. — 14. — P. 359–365.
15. M a t s u n a g a Y u s u k e . On enumerating non-disjunctive decompositions of logic functions // IEIC
Technical Report (Institute of Electronics, Information and Communication Engineers). — 2000. — 100,
N 36. — P. 33–39.
16. Ð û ö à ð Á . Å . Íîâûé ïîäõîä ê äåêîìïîçèöèè áóëåâûõ ôóíêöèé ìåòîäîì q-ðàçáèåíèé. 1. Ðàçäå-
ëèòåëüíàÿ äåêîìïîçèöèÿ ïîëíûõ è ÷àñòè÷íûõ ôóíêöèé // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2001. — ¹ 5. — Ñ. 38–62.
17. Ð û ö à ð Á . Å . Íîâûé ïîäõîä ê äåêîìïîçèöèè áóëåâûõ ôóíêöèé ìåòîäîì q-ðàçáèåíèé. 2. Ïîâ-
òîðíàÿ äåêîìïîçèöèÿ // Òàì æå. — 2002. — ¹ 1. — Ñ. 54–63.
18. Ð û ö à ð Á . Å . Íîâûé ïîäõîä ê äåêîìïîçèöèè áóëåâûõ ôóíêöèé ìåòîäîì q-ðàçáèåíèé. 3. Ñîâ-
ìåñòíàÿ äåêîìïîçèöèÿ ñèñòåìû ôóíêöèé // Òàì æå. — 2007. — ¹ 2. — Ñ. 39–58.
19. Ê ì å ò ü À . Á . , Ð è ö à ð Á . ª . Äî êëàñèô³êàö³¿ äåêîìïîçèö³é ëîã³êîâèõ ôóíêö³é // Óïðàâëÿþùèå
ñèñòåìû è ìàøèíû. — 2003. — ¹ 6. — Ñ. 21–32.
20. Ð è ö à ð Á . ª . Òåîðåòèêî-ìíîæèííèé ìåòîä îðòîãîíàë³çàö³¿ êîí’þíêòåðì³â áóëîâèõ ôóíêö³é //
Ðàäèîýëåêòðîíèêà è èíôîðìàòèêà. — 2005. — ¹ 3. — Ñ. 125–127.
Ïîñòóïèëà 22.02.2008
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 41
|
| id | nasplib_isofts_kiev_ua-123456789-44365 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:15:43Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Рыцар, Б.Е. 2013-05-31T16:06:48Z 2013-05-31T16:06:48Z 2009 Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения / Б.Е. Рыцар // Кибернетика и системный анализ. — 2009. — № 3. — С. 15-41. — Бібліогр.: 20 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44365 62.519 Розглянуто теоретико-множинний підхід до нерозділювальної декомпозиції бульових функцій від n змінних різних форм задання, що ґрунтується на методі pq, -розбиття кон’юнктермів і понятті декомпозиційних клонів. Описано два шляхи пошуку нерозділювальної функційної декомпозиції. Сформульовано теореми про нерозділювальну декомпозицію повних і частинних функцій, а також їх систем. Запропонований підхід проілюстровано на прикладах. A set-theoretical approach to the non-disjoint decomposition of different forms of representation of Boolean functions of n variables is considered. This approach is based on the method of p,q-partition of conjuncterms and the concept of decomposition clones. Two ways of searching for some non-disjoint functional decomposition are described. Theorems on the non-disjoint decomposition of complete and partial functions and their systems are formulated. The proposed approach is illustrated by examples. Начало см. в № 5, 2001, № 1, 2002, № 2, 2007. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения Новий підхід до декомпозиції бульових функцій. 4. Нерозділювальна декомпозиція: метод p, q-розбиття A new approach to the decomposition of boolean functions. 4. Non-disjoint decomposition: p,q-partition Article published earlier |
| spellingShingle | Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения Рыцар, Б.Е. Кибернетика |
| title | Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения |
| title_alt | Новий підхід до декомпозиції бульових функцій. 4. Нерозділювальна декомпозиція: метод p, q-розбиття A new approach to the decomposition of boolean functions. 4. Non-disjoint decomposition: p,q-partition |
| title_full | Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения |
| title_fullStr | Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения |
| title_full_unstemmed | Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения |
| title_short | Новый подход к декомпозиции булевых функций. 4. Неразделительная декомпозиция: метод p,q-разбиения |
| title_sort | новый подход к декомпозиции булевых функций. 4. неразделительная декомпозиция: метод p,q-разбиения |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44365 |
| work_keys_str_mv | AT rycarbe novyipodhodkdekompoziciibulevyhfunkcii4nerazdelitelʹnaâdekompoziciâmetodpqrazbieniâ AT rycarbe noviipídhíddodekompozicííbulʹovihfunkcíi4nerozdílûvalʹnadekompozicíâmetodpqrozbittâ AT rycarbe anewapproachtothedecompositionofbooleanfunctions4nondisjointdecompositionpqpartition |