Покрытия множеств и отношение толерантности
Досліджено властивості відношення толерантності та відповідних класів толерантності. Показано, що класи толерантності утворюють покриття множини носія. Розглянуто випадок, коли толерантність індукується довільним функціональним відношенням. Доведено умови, за яких має місце збіг класів толерантності...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/72061 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Покрытия множеств и отношение толерантности / С.Н. Герасин, В.В. Шляхов, С.В. Яковлев // Кибернетика и системный анализ. — 2008. — № 3. — С. 29-38. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-72061 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-720612025-02-09T15:33:45Z Покрытия множеств и отношение толерантности Герасин, С.Н. Шляхов, В.В. Яковлев, С.В. Кибернетика Досліджено властивості відношення толерантності та відповідних класів толерантності. Показано, що класи толерантності утворюють покриття множини носія. Розглянуто випадок, коли толерантність індукується довільним функціональним відношенням. Доведено умови, за яких має місце збіг класів толерантності та класів еквівалентності. 2008 Article Покрытия множеств и отношение толерантности / С.Н. Герасин, В.В. Шляхов, С.В. Яковлев // Кибернетика и системный анализ. — 2008. — № 3. — С. 29-38. — Бібліогр.: 7 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72061 51.000.57 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Герасин, С.Н. Шляхов, В.В. Яковлев, С.В. Покрытия множеств и отношение толерантности Кибернетика и системный анализ |
| description |
Досліджено властивості відношення толерантності та відповідних класів толерантності. Показано, що класи толерантності утворюють покриття множини носія. Розглянуто випадок, коли толерантність індукується довільним функціональним відношенням. Доведено умови, за яких має місце збіг класів толерантності та класів еквівалентності. |
| format |
Article |
| author |
Герасин, С.Н. Шляхов, В.В. Яковлев, С.В. |
| author_facet |
Герасин, С.Н. Шляхов, В.В. Яковлев, С.В. |
| author_sort |
Герасин, С.Н. |
| title |
Покрытия множеств и отношение толерантности |
| title_short |
Покрытия множеств и отношение толерантности |
| title_full |
Покрытия множеств и отношение толерантности |
| title_fullStr |
Покрытия множеств и отношение толерантности |
| title_full_unstemmed |
Покрытия множеств и отношение толерантности |
| title_sort |
покрытия множеств и отношение толерантности |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2008 |
| topic_facet |
Кибернетика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/72061 |
| citation_txt |
Покрытия множеств и отношение толерантности / С.Н. Герасин, В.В. Шляхов, С.В. Яковлев // Кибернетика и системный анализ. — 2008. — № 3. — С. 29-38. — Бібліогр.: 7 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT gerasinsn pokrytiâmnožestviotnošenietolerantnosti AT šlâhovvv pokrytiâmnožestviotnošenietolerantnosti AT âkovlevsv pokrytiâmnožestviotnošenietolerantnosti |
| first_indexed |
2025-11-27T11:15:10Z |
| last_indexed |
2025-11-27T11:15:10Z |
| _version_ |
1849941942265184256 |
| fulltext |
ÓÄÊ 51.001.57
Ñ.Í. ÃÅÐÀÑÈÍ, Â.Â. ØËßÕÎÂ, Ñ.Â. ßÊÎÂËÅÂ
1
ÏÎÊÐÛÒÈß ÌÍÎÆÅÑÒÂ È ÎÒÍÎØÅÍÈÅ ÒÎËÅÐÀÍÒÍÎÑÒÈ
Êëþ÷åâûå ñëîâà: îòíîøåíèå òîëåðàíòíîñòè, ñìåæíûå êëàññû è ïðåäêëàñ-
ñû, ïîêðûòèå ìíîæåñòâ, ôóíêöèîíàëüíîå îòíîøåíèå.
ÂÂÅÄÅÍÈÅ
Òðàäèöèîííûé ïîäõîä ê èçó÷åíèþ ñõîäñòâà èëè íåðàçëè÷èìîñòè îáúåêòîâ ñî-
ñòîèò â òîì, ÷òîáû ñíà÷àëà îïðåäåëèòü ìåðó ñõîäñòâà, à çàòåì èññëåäîâàòü
âçàèìíîå ðàñïîëîæåíèå ñõîäíûõ îáúåêòîâ. Àíãëèéñêèé ìàòåìàòèê Ý. Çèìàí
[1], èçó÷àÿ ìîäåëè çðèòåëüíîãî àïïàðàòà, ïðåäëîæèë àêñèîìàòè÷åñêîå îïðåäå-
ëåíèå ñõîäñòâà. Íà îñíîâàíèè ýòîãî ïîÿâèëàñü âîçìîæíîñòü èçó÷àòü ñâîéñòâà
ñõîäñòâà íåçàâèñèìî îò òîãî, íàñêîëüêî êîíêðåòíî îíî çàäàíî â òîé èëè èíîé
ñèòóàöèè: ðàññòîÿíèå ìåæäó îáúåêòàìè, ñîâïàäåíèå êàêèõ-òî ïðèçíàêîâ èëè
ñóáúåêòèâíîå ìíåíèå íàáëþäàòåëÿ.
Åñëè óêàçàíî òîëüêî ñõîäñòâî îáúåêòîâ, òî íåâîçìîæíî ðàçáèòü èõ íà ÷åòêèå
êëàññû òàê, ÷òîáû âíóòðè îäíîãî êëàññà îáúåêòû áûëè ïîõîæè, à ìåæäó îáúåêòà-
ìè ðàçíûõ êëàññîâ ñõîäñòâî îòñóòñòâîâàëî.  ñëó÷àå ñõîäñòâà âîçíèêàåò ðàçìû-
òàÿ ñèòóàöèÿ áåç ÷åòêèõ ãðàíèö. Îäíàêî íàêàïëèâàíèå íåñóùåñòâåííûõ ðàçëè÷èé
ó ñõîäíûõ îáúåêòîâ ìîæåò ïðèâåñòè ê ñîâåðøåííî íåïîõîæèì îáúåêòàì.
Ïðåäïðèíÿòûå ðàíåå èññëåäîâàíèÿ îòíîøåíèÿ òîëåðàíòíîñòè [2–4] â îñíîâíîì
êàñàëèñü òîïîëîãè÷åñêèõ àñïåêòîâ è íåêîòîðûõ ïðèëîæåíèé ê ñåìàíòèêå.  çíà÷è-
òåëüíî ìåíüøåé ñòåïåíè áûëî óäåëåíî âíèìàíèå âàæíîñòè ýòîãî îòíîøåíèÿ ê çàäà-
÷àì ðàñïîçíàâàíèÿ è êëàññèôèêàöèè. Îòìåòèì, ÷òî îòíîøåíèå ýêâèâàëåíòíîñòè ïî-
ðîæäàåò ðàçáèåíèå ìíîæåñòâà íà íåïåðåñåêàþùèåñÿ ñìåæíûå êëàññû, à îòíîøåíèå
òîëåðàíòíîñòè èíäóöèðóåò êëàññû, îáðàçóþùèå ïîêðûòèå èñõîäíîãî ìíîæåñòâà.
Åñòåñòâåííàÿ ñâÿçü ìåæäó îòíîøåíèåì òîëåðàíòíîñòè è îòíîøåíèåì ýêâè-
âàëåíòíîñòè ïðèâîäèò ê âûâîäó, ÷òî ñîîòâåòñòâóþùèå ñìåæíûå êëàññû ýòèõ îò-
íîøåíèé ïðè íåêîòîðûõ äîïîëíèòåëüíûõ óñëîâèÿõ ìîãóò ñîâïàäàòü. Ðåøåíèå
ýòîé çàäà÷è ïîëó÷åíî â ðàáîòå [5].
ÑÒÐÓÊÒÓÐÀ ÊËÀÑÑÎÂ ÒÎËÅÐÀÍÒÍÎÑÒÈ
Ðàññìîòðèì ïðÿìîóãîëüíóþ îáëàñòü D R� 2 , ñîäåðæàùóþ n òî÷åê â óçëàõ ñåòêè ðàç-
ìåðà n n n1 2� � , ò.å. ñîñòîÿùóþ èç n1 òî÷åê ïî âåðòèêàëè è n2 òî÷åê ïî ãîðèçîíòàëè
(ðèñ. 1). Ïîñëå óïîðÿäî÷åííîé íóìåðàöèè ýòè òî÷êè îáðàçóþò ìíîæåñòâî A n� { }12, , ,� .
Äîïóñòèì, ÷òî íà ìíîæåñòâå A çàäàíà öåëî÷èñëåííàÿ ôóíêöèÿ, îáðàçîì êîòîðîé ÿâëÿþòñÿ
äèñêðåòíûå òî÷êè â R, îáðàçóþùèå ïîñëå óïîðÿäî÷åííîé íóìåðàöèè ìíîæåñòâî
B J f Am� �( ) � � �{ }n n m1, , .� Ïóñòü íà ìíîæåñòâå B ñóùåñòâóåò ïîêðûòèå
� B � { }� �
1
B
q
B, ,� , ò.å. � i
B B� , � �i
B
j
B� è
i
q
i
B B
�
�
1
� � , i j� , i s�1, ,
j s�1, . Òîãäà íåòðóäíî çàìåòèòü, ÷òî ôóíêöèÿ f è ïîêðûòèå � B èíäóöèðóþò
íà A áèíàðíîå îòíîøåíèå
E a a
i
B
B
( , )
, ,
1 2
1
�
�åñëè íàéäåòñ õîò áû îäèí ýëåìåíò
äëÿ êî
� �
òîðîãî èìåþò ìåñòî âêëþchåíè
â ïðîòèâí
f a f a i
B( ), ( ) ,1 2
0
��
îì ñëóchàå,
��
�
�
�
(1)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 29
1
© Ñ.Í. Ãåðàñèí, Â.Â. Øëÿõîâ, Ñ.Â. ßêîâëåâ, 2008
ãäå a a A1 2, � , � i
B B� ,
i q�{ }1, ,� , êîòîðîå â êà÷åñ-
òâå îáëàñòè îïðåäåëåíèÿ
èìååò âåñü äåêàðòîâ êâàäðàò
A A� ( )Dom E A A� � è îá-
ëàäàåò ñâîéñòâîì ðåôëåêñèâ-
íîñòè ( ( , )E a a �1 äëÿ ëþáî-
ãî a A� ) è ñèììåòðè÷íîñòè
( ( , ) ( , )E a a E a a1 2 2 1� äëÿ
ëþáûõ ýëåìåíòîâ a1, a A2 � ),
ò.å. ÿâëÿåòñÿ îòíîøåíèåì
òîëåðàíòíîñòè.
Ïðè ýòîì îòíîøåíèå E ðåàëèçóåò ìíîãîçíà÷íîå îòîáðàæåíèå èç A â A, êîòî-
ðîå èíäóöèðóåò êëàññû îáðàçîâ è ïðîîáðàçîâ (òàê íàçûâàåìûå ëåâûå è ïðàâûå
ñìåæíûå êëàññû):
E x A E a xa � � �{ }: ( , ) 1 — êëàññû îáðàçîâ ýëåìåíòà a A� ,
E x A E a xa
� � �1 1{ }: ( , ) — êëàññ ïðîîáðàçîâ ýëåìåíòà a A� .
Íåòðóäíî çàìåòèòü, ÷òî â äàííîì ñëó÷àå ââèäó ñèììåòðè÷íîñòè êëàññû îáðà-
çîâ è ïðîîáðàçîâ ñîâïàäàþò, ïîñêîëüêó
� � � � � � � �
x E E a x E x a x Ea a( , ) ( , )1 1 1.
Ýòà öåïî÷êà ñëåäîâàíèé ñïðàâåäëèâà è â îáðàòíîì ïîðÿäêå. Òîãäà èìååì
E E aa �
1( ) è E Ea a
�1 , ò.å. E Ea a�
1. Ñèñòåìà ýòèõ êëàññîâ ïîðîæäàåò ïî-
êðûòèå � � �A
A
p
A� { }
1
, ,� , òàê êàê ïðîèçâîëüíûé ýëåìåíò a A� òàêæå ïðèíàä-
ëåæèò Ea , ïîñêîëüêó èìååò ìåñòî ðåôëåêñèâíîñòü E a a( , ) �1. Ïðè ýòîì èçâåñòíî
[2], ÷òî ëþáîå îòíîøåíèå òîëåðàíòíîñòè èíäóöèðóåò òàê íàçûâàåìûå ïðåäêëàñ-
ñû è êëàññû òîëåðàíòíîñòè. Îñòàíîâèìñÿ íà ýòîì ïîäðîáíåå.
Îïðåäåëåíèå 1. Ìíîæåñòâî C A� íàçûâàåòñÿ ïðåäêëàññîì òîëåðàíòíîñòè,
åñëè ëþáûå äâà åãî ýëåìåíòà x è y òîëåðàíòíû, ò.å. äëÿ íèõ âûïîëíåíî ñîîòíî-
øåíèå E x y( , ) �1.
 ÷àñòíîñòè çàìåòèì, ÷òî îäíîýëåìåíòíîå ìíîæåñòâî C a{ } äëÿ ëþáîãî a A�
åñòü ïðåäêëàññ òîëåðàíòíîñòè, òàê êàê èìååò ìåñòî ðåôëåêñèâíîñòü.
Îïðåäåëåíèå 2. Ìíîæåñòâî D A� íàçûâàåòñÿ êëàññîì òîëåðàíòíîñòè, åñëè
D åñòü ìàêñèìàëüíûé ïðåäêëàññ, ïîñêîëüêó äëÿ âñÿêîãî ýëåìåíòà z A� è íå âõî-
äÿùåãî â D ñóùåñòâóåò ýëåìåíò x D� , íå òîëåðàíòíûé ê z, ò.å. E x z( , ) � 0.
Ëåãêî ïîêàçàòü, ÷òî â ñëó÷àå, êîãäà A — êîíå÷íîå ìíîæåñòâî (çäåñü èìåííî
òàêàÿ ñèòóàöèÿ) âñÿêèé ïðåäêëàññ òîëåðàíòíîñòè ñîäåðæèòñÿ õîòÿ áû â îäíîì
êëàññå òîëåðàíòíîñòè D. Äåéñòâèòåëüíî, ïóñòü C — ïðåäêëàññ òîëåðàíòíîñòè.
Åñëè C åñòü êëàññ òîëåðàíòíîñòè, òî äîêàçàòåëüñòâî î÷åâèäíî. Åñëè C — íå
êëàññ òîëåðàíòíîñòè, òî îí íå ìàêñèìàëüíûé è íàéäåòñÿ ýëåìåíò z A C� \ , òîëå-
ðàíòíûé êî âñÿêîìó ýëåìåíòó èç C. Ïðèñîåäèíÿåì åãî ê ìíîæåñòâó C (ôàêòè÷åñ-
êè ðàñøèðèì C çà ñ÷åò ýòîãî ýëåìåíòà), ò.å. ðàññìîòðèì ìíîæåñòâî C C z1 � � { }.
Òîãäà C C� 1 è C1 ñíîâà áóäåò ïðåäêëàññîì òîëåðàíòíîñòè. Åñëè C1 íå ñòàë åùå
êëàññîì òîëåðàíòíîñòè, òî ïðîöåññ ðàñøèðåíèÿ, îïèñàííûé âûøå, ìîæåò áûòü
ïðîäîëæåí äî òåõ ïîð, ïîêà êëàññ òîëåðàíòíîñòè íå áóäåò ïîëó÷åí. Ïîñêîëüêó A
êîíå÷íî, òî çà êîíå÷íîå ÷èñëî øàãîâ ïîñòðîåíèå êëàññà òîëåðàíòíîñòè, ñîäåðæà-
ùåãî èñõîäíûé ïðåäêëàññ òîëåðàíòíîñòè, çàêîí÷èòñÿ. Òàêèì îáðàçîì, âûøåñ-
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Ðèñ. 1
ôîðìóëèðîâàííàÿ ïîñûëêà îáîñíîâàíà. Îòñþäà âûòåêàåò, ÷òî ëþáîé ýëåìåíò
a A� ñîäåðæèòñÿ â íåêîòîðîì êëàññå òîëåðàíòíîñòè, ïîñêîëüêó îí êàê îäíîýëå-
ìåíòíîå ïîäìíîæåñòâî A ÿâëÿåòñÿ ïðåäêëàññîì òîëåðàíòíîñòè, à âñÿ ñèñòåìà
êëàññîâ òîëåðàíòíîñòè îáðàçóåò ïîêðûòèå ìíîæåñòâà A, êîòîðîå áóäåì
îáîçíà÷àòü G G GA
A
q
A� { }
1
, ,� .
Îïðåäåëåíèå 3. Ïðîèçâîëüíîå ïîêðûòèå � íàçîâåì ïðàâèëüíûì òîãäà è
òîëüêî òîãäà, êîãäà äëÿ ëþáûõ äâóõ åãî ýëåìåíòîâ �1 è �2 âûïîëíÿþòñÿ ñîîò-
íîøåíèÿ �1 2\ PI � � è �2 1\ PI � �, ãäå � — çíàê ïóñòîãî ìíîæåñòâà.
Óòâåðæäåíèå 1. Êëàññû òîëåðàíòíîñòè îáðàçóþò ïðàâèëüíîå ïîêðûòèå ìíî-
æåñòâà A.
Äîêàçàòåëüñòâî íåñëîæíî ïîëó÷èòü ñëåäóþùèì îáðàçîì. Ïî ñóòè ïðàâèëü-
íîå ïîêðûòèå îáëàäàåò ñëåäóþùèì ñâîéñòâîì: â íåì íå ñóùåñòâóåò äâóõ ýëåìåí-
òîâ �1 è �2 , ñðåäè êîòîðûõ îäèí áûë áû öåëèêîì âëîæåí â äðóãîé, íàïðèìåð
� �1 2� . Ýòèì æå ñâîéñòâîì îáëàäàþò êëàññû òîëåðàíòíîñòè. Äåéñòâèòåëüíî,
åñëè áû C C1 2� , ãäå C C1 2, — êëàññû òîëåðàíòíîñòè, òî C1 íå óäîâëåòâîðÿåò
ñâîéñòâó ìàêñèìàëüíîñòè è ôàêòè÷åñêè ÿâëÿåòñÿ íå êëàññîì òîëåðàíòíîñòè,
à ïðåäêëàññîì. Èìååì ïðîòèâîðå÷èå ñ èñõîäíîé ïîñûëêîé. Òàêèì îáðàçîì, äëÿ
ëþáîé ïàðû êëàññîâ òîëåðàíòíîñòè âëîæåíèå èñêëþ÷àåòñÿ, ÷òî ïî îïðåäåëåíèþ
ñâèäåòåëüñòâóåò î ïðàâèëüíîñòè ïîêðûòèÿ. Óòâåðæäåíèå äîêàçàíî.
Îïðåäåëåíèå 4. Íàçîâåì êàêîé-òî ýëåìåíò ïðîèçâîëüíîãî ïîêðûòèÿ íåïðà-
âèëüíûì, åñëè îí âëîæåí â êàêîé-ëèáî äðóãîé (õîòÿ áû îäèí) ýëåìåíò ïîêðûòèÿ.
Îïðåäåëåíèå 5. Ïðîèçâîëüíîå ïîêðûòèå êîíå÷íîãî ìíîæåñòâà B áóäåì íà-
çûâàòü óïîðÿäî÷åííî-ñâÿçíûì òîãäà, êîãäà ñóùåñòâóåò íóìåðàöèÿ ýëåìåíòîâ
ìíîæåñòâà B, ïðè êîòîðîé ëþáîé ýëåìåíò ïîêðûòèÿ ÿâëÿåòñÿ ñâÿçíûì â òîì
ñìûñëå, ÷òî îí ñîäåðæèò âñå ýëåìåíòû, çàíóìåðîâàííûå ïîäðÿä áåç ïðîïóñêîâ,
ò.å.
� i i i i kb b b� � �{ }, , ,1 � ,
ãäå b b b Bi i i k, , ,� � �1 � , à | |� i k� — ÷èñëî ýëåìåíòîâ ïîêðûòèÿ.
Ðàññìîòðèì ïðèìåð íåóïîðÿäî÷åííî-ñâÿçíîãî ïîêðûòèÿ. Ïóñòü ìíîæåñòâî
B ñîñòîèò èç òðåõ ýëåìåíòîâ: B � { }12 3, , , à �B � { }( , ); ( , ); ( , )12 2 3 13 . Òîãäà íåòðóäíî
çàìåòèòü, ÷òî ïðè ëþáîé ïåðåíóìåðàöèè ýëåìåíòîâ ìíîæåñòâà B èëè ïåðåñòàíîâ-
êå ÷èñåë 1, 2, 3 âñåãäà áóäåò ïðèñóòñòâîâàòü íåñâÿçíûé ýëåìåíò ïîêðûòèÿ ñ
íîìåðàìè 1 è 3 è ïðîïóùåííûì íîìåðîì 2.
Îïðåäåëåíèå 6. Íàçîâåì òðîéêó ïðîèçâîëüíûõ ðàçëè÷íûõ ýëåìåíòîâ ìíî-
æåñòâà B, b b b B1 2 3, , � , ñ çàäàííûì íà íåì ïðîèçâîëüíûì ïîêðûòèåì �B òðàí-
çèòèâíîé, åñëè ëþáàÿ ïàðà ýëåìåíòîâ ýòîé òðîéêè íàõîäèòñÿ õîòÿ áû â îäíîì
ýëåìåíòå ïîêðûòèÿ �B .
Ïðèâåäåííûé âûøå ïðèìåð ïðåäñòàâëÿåò ñîáîé òðàíçèòèâíóþ òðîéêó.
Íåòðóäíî çàìåòèòü, ÷òî â îáùåì ñëó÷àå ëþáàÿ ïàðà � �B B, � (ãäå B —
ìíîæåñòâî è �B — çàäàííîå íà íåì ïðîèçâîëüíîå ïîêðûòèå) èíäóöèðóåò íà
ìíîæåñòâå B îòíîøåíèå òîëåðàíòíîñòè ïî ïðàâèëó, àíàëîãè÷íîìó ðàâåíñòâó (1):
T b b
B
Â
�
�
( , )
, ,
1 2
1
�
åñëè íàéäåòñ õîò áû îäèí ýëåìåíò ïîêðûòè
äëÿ êîòîðîãî èìåþò ìåñòî âêëþchåíè
â ïð
b b i
B
B1 2 2
0
, ; ( )� �� �
îòèâíîì ñëóchàå.
�
�
�
Òîãäà òðàíçèòèâíàÿ òðîéêà îòíîñèòåëüíî ýòîãî îòíîøåíèÿ äåéñòâèòåëüíî ÿâ-
ëÿåòñÿ òðàíçèòèâíîé. Áîëåå òîãî, òîëåðàíòíîñòü T�B
íà òðàíçèòèâíîé òðîéêå
êàê è íà ìíîæåñòâå ïåðåõîäèò â òðèâèàëüíûé ñëó÷àé åäèíè÷íîé ýêâèâàëåí-
òíîñòè � (òîæäåñòâåííî ðàâíîé åäèíèöå), ïîñêîëüêó
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 31
� ( , )b bi j �1 äëÿ ëþáûõ b b b b bi j, , ,�{ }1 2 3 .
Ðàññìîòðèì íåêîòîðûå âàæíûå (â äàëüíåéøåì) ñâîéñòâà ïðàâèëüíûõ è óïî-
ðÿäî÷åííî-ñâÿçíûõ ïîêðûòèé.
Ñâîéñòâî 1. Åñëè ïðîèçâîëüíîå ïîêðûòèå �B ÿâëÿåòñÿ óïîðÿäî÷åííî-ñâÿçíûì
è ïðàâèëüíûì, òî äëÿ ëþáîé ïàðû åãî ðàçëè÷íûõ ýëåìåíòîâ � � �1 2, � B ñóùåñòâó-
åò õîòÿ áû îäíà íåòðàíçèòèâíàÿ òðîéêà { }b b b Bj k1, , � , äëÿ êîòîðîé
{ }b b bj k1
1 2, , � �� � ,
ò.å. ïðèíàäëåæàùàÿ èõ îáúåäèíåíèþ, à èç äâóõ ýëåìåíòîâ, êîòîðûå íå ïðèíàä-
ëåæàò êàêîìó-òî îäíîìó ýëåìåíòó ïîêðûòèÿ (äîïóñòèì, bi è bk ), îäèí ïðèíàä-
ëåæàò � �1 2\ , à äðóãîé — � �2 1\ : b PIi �� 1 2\ , bk �� �2 1\ .
Äîêàçàòåëüñòâî. Ñëåäóåò çàìåòèòü, ÷òî åñëè � 1 è � 2 — îäíîýëåìåíòíû,
òî ýòà ñèòóàöèÿ â êàêîì-òî ñìûñëå «âûðîæäåííàÿ», ïîñêîëüêó äëÿ åäèíè÷íûõ
ýëåìåíòîâ ïîêðûòèÿ îáúåäèíåíèå íå ñîäåðæèò òðîéêè êàê òàêîâîé è ìîæíî ñ÷è-
òàòü, ÷òî òðàíçèòèâíîñòè íå íàáëþäàåòñÿ. Ïîýòîìó áåç îãðàíè÷åíèÿ îáùíîñòè
ìîæíî ñ÷èòàòü, ÷òî îáúåäèíåíèå ñîäåðæèò õîòÿ áû òðè ðàçëè÷íûõ ýëåìåíòà
ìíîæåñòâà B.
Òîãäà âîçìîæíû äâå ñèòóàöèè: � �1 2� � � èëè � �1 2� � �, ïðè ýòîì
ïîêðûòèå ÿâëÿåòñÿ óïîðÿäî÷åííî-ñâÿçíûì. Òîãäà ìîæíî ñ÷èòàòü, ÷òî
� 1
11 1 1 1
� � �{ }b b bi i i k, , ,� , � 2
12 2 2 2
� � �{ }b b bi i i k, , ,� ,
ãäå b b b b Bi i k i i k1 1 1 2 2 2
, , , ,� �� � � , à èõ íîìåðà óäîâëåòâîðÿþò ñëåäóþùåìó
óñëîâèþ:
åñëè � �1 2� � �, òî i k i1 1 2� � ;
åñëè � �1 2� � �, òî ñóùåñòâóåò íîìåð s � 0 òàêîé, ÷òî s k� 1 è
i s i1 2� � .
Áîëåå íàãëÿäíî ýòî ìîæíî ïðåäñòàâèòü ñõåìàìè 1 è 2.
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
bi1
bi1 1� ... bi k1 1� ... bi2
bi2 1� ... bi k2 2�
� �1 2� � �
bi1
... bi s1 1�
bi s1� ... bi k1 1�
bi2
... bi l2 1�
bi l2 � ... bi k2 2�
� �1 2
1 1 1
� � � �{ }b bi s i k, ,�
k s1 1
�
Ñõåìà 2
l ýëåìåíòîâ
Ñõåìà 2
 ñõåìå 2 b b b bi s i i k i l1 2 1 1 2 1� � �
� �, ;� — ýòî ôàêòè÷åñêè îáùèå ýëåìåí-
òû ìíîæåñòâ �1 è �2 . Íåñëîæíî ïîíÿòü, ÷òî â ëþáîì ñëó÷àå äâà ýëåìåíòa:
bi1
è bi k2 2� , ïðèíàäëåæàùèå B, íå ìîãóò áûòü òîëåðàíòíûìè îòíîñèòåëüíî
T�B
, ò.å. T�B
b bi i k( , )
1 2 2
0� � . Äåéñòâèòåëüíî, â ïðîòèâíîì ñëó÷àå, åñëè áû
T�B
b bi i k( , )
1 2 2
1� � , òî íàøåëñÿ áû òðåòèé ýëåìåíò ïîêðûòèÿ �B , à èìåííî
� �3 � B , êîòîðûé èõ ñîäåðæàë áû, ò.å. b bi i k1 2 2
3, � �� . Îäíàêî â ýòîì ñëó-
÷àå � 3 ñîäåðæèò è âñå ïðîìåæóòî÷íûå ïî íîìåðàì ýëåìåíòû ìíîæåñòâà B â
ñèëó ñâîåé ñâÿçíîñòè. Îòñþäà ñëåäóåò ñîîòíîøåíèå � � �1 2 3� � , ÷òî
ïðîòèâîðå÷èò ïðàâèëüíîñòè ïîêðûòèÿ �B . Òàêèì îáðàçîì, T�B
b bi i k( , )
1 2 2
0� � .
Òåïåðü äîáàâèì ê ýòèì äâóì ýëåìåíòàì ëþáîé ýëåìåíò èç � �1 2� \
T { }�B
b bi i k1 2 2
, � � � (ñì. çàìå÷àíèå â íà÷àëå äîêàçàòåëüñòâà) è ïîëó÷èì íåòðàí-
çèòèâíóþ òðîéêó, ïðèíàäëåæàùóþ îáúåäèíåíèþ ïðîèçâîëüíûõ äâóõ ýëåìåíòîâ ïî-
êðûòèÿ �B . Ïðè ýòîì bi1
1 2�� �\ , bi k2 2
2 1
� �� �\ . Ñâîéñòâî 1 äîêàçàíî.
Ñâîéñòâî 2. Åñëè ïðîèçâîëüíîå ïîêðûòèå �B óäîâëåòâîðÿåò óñëîâèþ, ñî-
ãëàñíî êîòîðîìó äëÿ ëþáîé ïàðû � � �1 2, � B ñóùåñòâóåò íåòðàíçèòèâíàÿ
òðîéêà, ïðèíàäëåæàùàÿ èõ îáúåäèíåíèþ, òî ïîêðûòèå �B ÿâëÿåòñÿ ïðàâèëüíûì.
Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, äîïóñòèì ñóùåñòâîâàíèå íåïðàâèëüíîãî
ýëåìåíòà ïîêðûòèÿ �B . Ýòî îçíà÷àåò, ÷òî îí âëîæåí â äðóãîé ýëåìåíò, ò.å.
� � �1 2, � B è � �1 2� . Òîãäà èõ îáúåäèíåíèå � � �1 2 2� � è ëþáûå òðè
ýëåìåíòà ìíîæåñòâà B ïîïàäàþò â îäèí ýëåìåíò ïîêðûòèÿ, ò.å. òðîéêà ïî îïðåäå-
ëåíèþ � ÿâëÿåòñÿ òðàíçèòèâíîé. Ïîëó÷èì ïðîòèâîðå÷èå. Ñâîéñòâî 2 äîêàçàíî.
Ñâîéñòâî 3. Ïðîèçâîëüíîå ðàçáèåíèå êîíå÷íîãî ìíîæåñòâà B ÿâëÿåòñÿ óïî-
ðÿäî÷åííî-ñâÿçíûì ïîêðûòèåì.
Äîêàçàòåëüñòâî.Ôàêòè÷åñêè ýòî ìîæíî äîêàçàòü ïî èíäóêöèè îòíîñèòåëüíî
êîëè÷åñòâà ýëåìåíòîâ ìíîæåñòâà B. Áàçà èíäóêöèè î÷åâèäíî ïðèñóòñòâóåò, ïî-
ñêîëüêó åñëè ìíîæåñòâî B èìååò îäèí èëè äâà ýëåìåíòà, òî ëþáîå ðàçáèåíèå (çà-
ìåòèì, ÷òî ýëåìåíòû ðàçáèåíèÿ íå ïåðåñåêàþòñÿ) ñîñòîèò èç îäíîãî èëè äâóõ ýëå-
ìåíòîâ. Î÷åâèäíî, ÷òî ïðè ëþáîé íóìåðàöèè ýòè ýëåìåíòû ÿâëÿþòñÿ ñâÿçíûìè.
Òåïåðü äîïóñòèì, ÷òî äëÿ âñåõ êîíå÷íûõ ìíîæåñòâ ìîùíîñòè n óêàçàííîå
ñâîéñòâî âûïîëíÿåòñÿ. Ðàññìîòðèì ìíîæåñòâî B, äëÿ êîòîðîãî | |B � n �1, è åãî
ñîáñòâåííîå ïîäìíîæåñòâî C B� ìîùíîñòè n. Äàííîå ðàçáèåíèå îñòàåòñÿ ðàçáè-
åíèåì, ïîêðûâàþùèì ìíîæåñòâî C B b� \ { }, ãäå b — êàêîé-òî ýëåìåíò B, êîòî-
ðûé îòëè÷àåò C îò B, ïîñêîëüêó åãî ìîùíîñòü íà åäèíèöó ìåíüøå. Äîïóñòèì,
÷òî ýëåìåíò b ïðèíàäëåæèò � � — ýëåìåíòó ïåðâîíà÷àëüíîãî ðàçáèåíèÿ �B .
Èçìåíÿåì � �, èñêëþ÷èâ èç íåãî b. Òîãäà íîâîå ðàçáèåíèå ïîêðîåò C è áóäåò óïî-
ðÿäî÷åííî-ñâÿçíûì ïî ïðåäïîëîæåíèþ èíäóêöèè, òàê êàê | |C n� . Çíà÷èò, ñóùåñ-
òâóåò íóìåðàöèÿ ýëåìåíòîâ ìíîæåñòâà C, ïðè êîòîðîé � � \ {b} — ñâÿçíûé
ýëåìåíò:
� � �\ {b} { }b b bi i i s, , ,� �1 � .
Ïðèñâîèì ýëåìåíòó b íîìåð i s� �1, à âñå íîìåðà ýëåìåíòîâ ïîñëå i s� ñäâè-
íåì íà åäèíèöó. Òîãäà ñâÿçíîñòü ëþáîãî ýëåìåíòà ðàçáèåíèÿ íå èçìåíèòñÿ, íî îíî
óæå áóäåò ïîêðûâàòü ìíîæåñòâî B, ìîùíîñòü êîòîðîãî n �1. Òàêèì îáðàçîì, ñïðà-
âåäëèâ èíäóêòèâíûé ïåðåõîä. Ñâîéñòâî 3 äîêàçàíî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 33
ÔÓÍÊÖÈÎÍÀËÜÍÛÅ ÁÈÍÀÐÍÛÅ ÎÒÍÎØÅÍÈß
Îïðåäåëåíèå 7. Íàçîâåì ïðîèçâîëüíîå áèíàðíîå îòíîøåíèå F� ôóíêöèîíàëü-
íûì íà ìíîæåñòâå A, åñëè îíî ñòðîèòñÿ íà áàçå ñëåäóþùåé êîíñòðóêöèè:
à) åñòü íåêîòîðàÿ ôóíêöèÿ g A B: � , B — ïðîèçâîëüíîå ìíîæåñòâî;
á) íà ìíîæåñòâå B çàäàíî ïðîèçâîëüíîå ïîêðûòèå �, òîãäà F a a� ( , ) ,1 2 1�
íàéäåòñÿ õîòÿ áû îäèí ýëåìåíò ïîêðûòèÿ � �� � , äëÿ êîòîðîãî g a( )1 ,
g a( )2 � �� , ãäå a a A1 2, � , g a g a B( ), ( )1 2 � . Èç ýòèõ îïðåäåëåíèé âûòåêàåò, ÷òî
ïðîèçâîëüíîå ôóíêöèîíàëüíîå îòíîøåíèå ÿâëÿåòñÿ îòíîøåíèåì òîëåðàíòíîñòè
(îáðàòíîå óòâåðæäåíèå â îáùåì ñëó÷àå íåâåðíî). Äåéñòâèòåëüíî, èç îïðåäåëåíèÿ
7 î÷åâèäíî ñëåäóåò ðåôëåêñèâíîñòü è ñèììåòðè÷íîñòü îòíîøåíèÿ F� .
Èñõîäíîå îòíîøåíèå, çàäàþùååñÿ ðàâåíñòâîì (1), ÿâëÿåòñÿ ôóíêöèîíàëüíûì.
Óòâåðæäåíèå 2. Ôóíêöèîíàëüíîå
îòíîøåíèå íå èçìåíèòñÿ, åñëè èç ïîêðû-
òèÿ �, åãî èíäóöèðóþùåãî, áóäóò èñ-
êëþ÷åíû âñå íåïðàâèëüíûå ýëåìåíòû.
Äîêàçàòåëüñòâî. Ðàññìîòðèì ïðîèç-
âîëüíûé íåïðàâèëüíûé ýëåìåíò � �� �
(åñëè òàêèõ íå ñóùåñòâóåò, òî äîêàçàò-
åëüñòâà íå òðåáóåòñÿ). Òîãäà íàéäåòñÿ õîòÿ
áû îäèí ýëåìåíò � �� � � , äëÿ êîòîðîãî
èìååò ìåñòî âëîæåíèå � �� � � �. Äîïóñ-
òèì, ÷òî ïîñëå óäàëåíèÿ èç ïîêðûòèÿ � ýëå-
ìåíòà � � äëÿ êàêîé-òî ïàðû a a1 2, ýëåìåí-
òîâ èç A ïðîèçîøëî èçìåíåíèå îòíîøåíèÿ
F , ò.å. F a a F a a� � �( , ) ( , )\{1 2 1 2� �} .
Åñëè ýòî èçìåíåíèå ïðîèçîøëî ñ 0 íà 1,
òî ïðèõîäèì íåïîñðåäñòâåííî ê ïðîòè-
âîðå÷èþ, ïîñêîëüêó g a g a B( ), ( )1 2 �
îäíîâðåìåííî ïðèíàäëåæàëè ðàçíûì
ýëåìåíòàì ïîêðûòèé � è ïîñëå èçúÿòèÿ
ëþáîãî ýëåìåíòà ïîêðûòèÿ îòíîñèòåëü-
íî � � íèêàêèõ èçìåíåíèé íå ïðîèçîé-
äåò. Èçìåíåíèå îòíîøåíèÿ F ñ 1 íà 0
ìîæåò ïðîèçîéòè â ñëó÷àå äîáàâëåíèÿ
êàêîãî-òî ýëåìåíòà, ñîäåðæàùåãî g a( )1
è g a( )2 . Òàêèì îáðàçîì, èçìåíåíèå ìî-
æåò ïðîèçîéòè òîëüêî â òîëåðàíòíûõ
ýëåìåíòàõ îòíîøåíèÿ F� . Çíà÷èò, ñó-
ùåñòâóåò � �� � � � , äëÿ êîòîðîãî
g a g a( ), ( )1 2 � � � �� . Òîãäà åñëè
� �� � � � � � �, òî èçúÿòèå ýëåìåíòà ñè-
òóàöèè íå ìåíÿåò, òàê êàê
g a g a( ), ( )1 2 � �� . Åñëè æå
� �� � � � � � �, òî èçìåíåíèå îòíîøåíèÿ
F ìîæåò ïðîèçîéòè òîëüêî òîãäà, êîãäà
õîòÿ áû îäèí èç ýëåìåíòîâ
g a g a B( ), ( )1 2 � ïîïàäåò â ïåðåñå÷åíèå
� �� � � � �. Ñâîéñòâî ñèììåòðèè îòíîøå-
íèÿ òîëåðàíòíîñòè ïðèâîäèò ê òðåì âà-
ðèàíòàì:
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Ðèñ. 2
a
á
â
1) g a g a( ), ( )1 2 � � � � �� � � �� � � (ðèñ 2, à);
2) g a g a( ), ( )1 2 � � �� � � �� � , g a( )1 � �� � � � � � �� � � (ðèñ 2, á);
3) g a g a( ), ( )1 2 � � � �� , g a( )1 � � � � � � � � �� � � (ðèñ 2, â).
Êàê âèäèì, îòáðàñûâàíèå ýëåìåíòà � � èç ïîêðûòèÿ � ñîõðàíÿåò ýëåìåíò
� � � �, ñîäåðæàùèé g a( )1 è g a( )2 . Òàêèì îáðàçîì, F a a� �\ ( , ){ }� �1 2 1 , ò.å. èç-
ìåíåíèÿ îòíîøåíèÿ F ñ 1 íà 0 òàêæå íå ïðîèçîøëî, ÷òî äîêàçûâàåò èñõîä-
íîå óòâåðæäåíèå.
Èçâåñòíî, ÷òî ëþáîå áèíàðíîå îòíîøåíèå T , çàäàííîå íà êîíå÷íîì ìíî-
æåñòâå A, äîïóñêàåò ïðåäñòàâëåíèå â ìàòðè÷íîì âèäå, ò.å. åìó îäíîçíà÷íî ñîîò-
âåòñòâóåò êâàäðàòíàÿ ìàòðèöà I T( ) ðàçìåðà n n� , ãäå | |A n� — ÷èñëî ýëåìåíòîâ
ìíîæåñòâà èëè åãî ìîùíîñòü. Ïðè ýòîì
I T ij i j n
( ) ( )
, ,
� ��
1
, (3)
ãäå � ij �1 òîãäà è òîëüêî òîãäà, êîãäà T a a j( , )1 1� , ai , a Aj � .
 îáùåì ñëó÷àå, à òàêæå òîãäà, êîãäà îòíîøåíèå T — ôóíêöèîíàëüíî,
êëàññû îáðàçîâ (ïðîîáðàçîâ) è êëàññû òîëåðàíòíîñòè íå ñîâïàäàþò. Ðàññìîòðèì
ñëåäóþùèé ïðèìåð.
Ïðèìåð 1. Âîçüìåì â êà÷åñòâå ìíîæåñòâ A è B ñëåäóþùèå íàáîðû íàòó-
ðàëüíûõ ÷èñåë:
A � {1,2,3,4,5,6}, B � {7,8,9,10,11}.
Çàäàäèì ôóíêöèþ f A B: � , êîòîðóþ ïðåäñòàâèì â òàáëè÷íîì âèäå.
A 1 2 3 4 5 6
f a B( ) � 7 8 9 10 11 11
Çäåñü f ( )1 7� , f ( )2 8� , f ( )3 9� , f ( )4 10� , f f( ) ( )5 6 11� � . Ïðåäñòàâèì òàê-
æå ïîêðûòèå �B � { }� � �
1 2 3
B B B, , , ñîñòîÿùåå èç òðåõ ýëåìåíòîâ, ãäå
�
1
7 8B � { }, , �
2
8 910B � { }, , , �
3
91011B � { }, , . Çàìåòèì, ÷òî ñðàçó çàäàíî ïðàâèëü-
íîå ïîêðûòèå, ïîñêîëüêó, êàê ñëåäóåò èç óòâåðæäåíèÿ 2, áåç îãðàíè÷åíèÿ îá-
ùíîñòè ìîæíî âñåãäà åãî òàêîâûì ñäåëàòü. Òîãäà ïîêðûòèå èíäóöèðóåò
ôóíêöèîíàëüíîå, òîëåðàíòíîå îòíîøåíèå, êîòîðîå ìîæíî ïðåäñòàâèòü òàáëè-
öåé (ðèñ. 3, a) èëè â ìàòðè÷íîì âèäå (ðèñ. 3, á).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 35
Ðèñ. 3
E I j
B� ( , )
A
1 2 3 4 5 6
A
1 1 1 0 0 0 0
2 1 1 1 1 0 0
3 0 1 1 1 1 1
4 0 1 1 1 1 1
5 0 0 1 1 1 1
6 0 0 1 1 1 1
1 1 0 0 0 0
1 1 1 1 0 0
0 1 1 1 1 1
0 1 1 1 1 1
0 0 1 1 1 1
0 0 1 1 1 1
I E
B
( )� �
D1
D2
D3
a á
Äëÿ ýòîãî îòíîøåíèÿ êëàññû îáðàçîâ è ïðîîáðàçîâ, ñîâïàäàþùèå îäèí ñ
äðóãèì (â òåðìèíîëîãèè [6] — ñìåæíûå êëàññû), òàêîâû:
� � � �
� �B B
1 1
1
12{ }, ,
� � � �
� �B B
2 2
1
12 3 4{ }, , , ,
� � � �
� �B B
3 3
1
2 3 4 5 6{ }, , , , ,
||
� � � �
� �B B
4 4
1
2 3 4 5 6{ }, , , , , (4)
� � � �
� �B B
5 5
1
3 4 5 6{ }, , , ,
||
� � � �
� �B B
6 6
1
3 4 5 6{ }, , , ,
à êëàññû òîëåðàíòíîñòè èìåþò âèä
D1 12� { }, , D2 2 3 4� { }, , , D3 3 4 5 6� { }, , , . (5)
Ñðàâíèâàÿ ïîäìíîæåñòâà A, âûðàæåííûå ðàâåíñòâàìè (4), (5), íàáëþäàåì
ëèøü ÷àñòè÷íîå èõ ñîâïàäåíèå îäèí ñ äðóãèì.
Åñòåñòâåííî, âîçíèêàåò âîïðîñ: êîãäà ñìåæíûå êëàññû è êëàññû òîëåðàí-
òíîñòè îòíîøåíèé ñîâïàäàþò, êàêîâûì ÿâëÿåòñÿ èçíà÷àëüíî èíòåðåñóþùåå íàñ
îòíîøåíèå E a a( , )1 2 , çàäàííîå ðàâåíñòâîì èëè óñëîâèåì (1)? Îòâåò äàåò
ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 1. Äëÿ ôóíêöèîíàëüíîãî, òîëåðàíòíîãî îòíîøåíèÿ F
B� , çàäàííîãî
íà ìíîæåñòâå A, èíäóöèðîâàííîì ôóíêöèåé f èç A â íåêîòîðîå ìíîæåñòâî B,
ò.å. f A: �, è íåêîòîðûì óïîðÿäî÷åííî-ñâÿçíûì ïîêðûòèåì �B ìíîæåñòâà B.
Äëÿ ëþáîãî ýëåìåíòà a A� ñìåæíûé êëàññ èëè êëàññ îáðàçîâ è ïðîîáðàçîâ ÿâëÿ-
åòñÿ êëàññîì òîëåðàíòíîñòè òîãäà è òîëüêî òîãäà, êîãäà ïîêðûòèå �B ÿâëÿåòñÿ
ðàçáèåíèåì, ò.å. åãî ýëåìåíòû íå ïåðåñåêàþòñÿ.
Äîêàçàòåëüñòâî. Äîñòàòî÷íîñòü. Ïóñòü �B — ðàçáèåíèå. Ðàññìîòðèì ïðî-
èçâîëüíûé êëàññ îáðàçîâ F
Ba� ëþáîãî ýëåìåíòà a A� è äâà åìó ïðèíàäëåæàùèõ
ïðîèçâîëüíûõ ýëåìåíòà a a F
Ba1 2, � � . Òîãäà, èñõîäÿ èç îïðåäåëåíèÿ êëàññà
îáðàçîâ, èìååì
F a a F a a
B B� �( , ) ( , )1 2 1� � . (6)
Èç ôóíêöèîíàëüíîñòè îòíîøåíèÿ F
B� âûòåêàåò, ÷òî íàéäóòñÿ äâà ýëåìåíòà
ïîêðûòèÿ �B , äîïóñòèì � i
B è � j
B , äëÿ êîòîðûõ
f a f a i
B( ), ( )1 �� , f a f a j
B( ), ( )2 �� . (7)
Ïîñêîëüêó îòîáðàæåíèå f íàõîäèòñÿ â ìíîæåñòâå B, òî ýëåìåíò f a B( ) �
ëåæèò â ïåðåñå÷åíèè � �i
B
j
B� , ÷òî ñëåäóåò èç ïðèíàäëåæíîñòåé (7). Îäíàêî äâà
ýëåìåíòà ðàçáèåíèÿ ïåðåñåêàþòñÿ òîëüêî â ñëó÷àå èõ ñîâïàäåíèÿ. Ýòî îçíà÷àåò,
÷òî � �i
B
j
B� , íî òîãäà f a f a i
B( ), ( )1 2 �� , ò.å. ïðèíàäëåæàò îäíîìó ýëåìåíòó
ïîêðûòèÿ. Îäíàêî ýòî ñâèäåòåëüñòâóåò îá èõ òîëåðàíòíîñòè èëè î òîì, ÷òî êëàññ
îáðàçîâ F
B� ÿâëÿåòñÿ ïðåäêëàññîì, òîëåðàíòíûì ê ýëåìåíòó à. Òîãäà ëþáîå
ìíîæåñòâî, âêëþ÷àþùåå åãî, ñîäåðæèò ýëåìåíò, íå òîëåðàíòíûé ê a, ò.å. íå ÿâëÿ-
åòñÿ ïðåäêëàññîì. Òàêèì îáðàçîì, ïðîèçâîëüíûé êëàññ îáðàçîâ èëè ñìåæíûé
êëàññ ÿâëÿåòñÿ êëàññîì òîëåðàíòíîñòè. Äîñòàòî÷íîñòü äîêàçàíà.
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Íåîáõîäèìîñòü. Äîïóñòèì, ÷òî äëÿ ïðîèçâîëüíîãî ýëåìåíòà a A� êëàññ îá-
ðàçîâ F
Ba� ÿâëÿåòñÿ êëàññîì òîëåðàíòíîñòè. Äîêàæåì, ÷òî â ýòîì ñëó÷àå �B
áóäåò ðàçáèåíèåì.
Äîêàçàòåëüñòâî áóäåì âåñòè îò ïðîòèâíîãî. Ïðåäïîëîæèì, ÷òî �B — íå
ðàçáèåíèå. Òîãäà íàéäóòñÿ äâà íåðàâíûõ ýëåìåíòà � i
B è � j
B ïîêðûòèÿ �B , ïå-
ðåñå÷åíèå êîòîðûõ íå ïóñòî (ò.å. � �i
B
j
B� � �) è êîòîðîå ñîäåðæèò ýëåìåíò
b b Bi
B
j
B� � �� � , . Ïðè ýòîì f A: � R, òîãäà íàéäåòñÿ ýëåìåíò a A� , äëÿ êî-
òîðîãî f a b( ) � , ÷òî îçíà÷àåò
f a i
B
j
B( ) � �� � . (8)
Ñ äðóãîé ñòîðîíû, � �i
B
j
B� è ïîêðûòèå �B — ïðàâèëüíîå è óïîðÿäî÷åí-
íî-ñâÿçíîå. Òîãäà, èñõîäÿ èç ñâîéñòâà 1, äëÿ ýëåìåíòîâ ïîêðûòèÿ � i
B è � j
B íàé-
äåòñÿ íåòðàíçèòèâíàÿ òðîéêà. Ïðè÷åì, êàê âèäíî èç äîêàçàòåëüñòâà ñâîéñòâà 1,
â ñëó÷àå èõ ïåðåñå÷åíèÿ èñêîìàÿ íåòðàíçèòèâíàÿ òðîéêà (ïðè ñîîòâåòñòâóþùåé
íóìåðàöèè) ñîäåðæèò ýëåìåíò b èç ïåðåñå÷åíèÿ � �i
B
j
B� , a òàêæå äâà ýëåìåíòà
— b1 è b2 , êîòîðûå îáëàäàþò ñâîéñòâîì
b b i
B
1, �� , b b j
B
2 , �� . (9)
Ïðè ýòîì íå ñóùåñòâóåò ýëåìåíòà ïîêðûòèÿ �B , êîòîðîìó b1, b2 ïðèíàäëåæà-
ëè áû.
Ýëåìåíòû b1 è b2 èìåþò ïðîîáðàçû ïðè îòîáðàæåíèè f — ýëåìåíòû ìíî-
æåñòâà A. Îáîçíà÷èì èõ a1 è a2 . Äëÿ íèõ áóäóò âûïîëíÿòüñÿ óñëîâèÿ
f a b( )1 1� , f a b( )2 2� . Èç ñîîòíîøåíèé (9) è ïîñëåäíèõ äâóõ ðàâåíñòâ èìå-
åì
F a a F a a
B B� �( , ) ( , )1 2 1� � , F a a
B� ( , )1 2 0� ,
íî ýòî íåâîçìîæíî, ïîñêîëüêó F
Ba� — êëàññ ïðîîáðàçîâ, ñîäåðæàùèé a1 è
a2 , êîòîðûé ÿâëÿåòñÿ êëàññîì òîëåðàíòíîñòè, ò.å. F a a
Ba� ( , )1 2 1� . Òàêèì îá-
ðàçîì, ïîëó÷åíî ïðîòèâîðå÷èå. Íåîáõîäèìîñòü äîêàçàíà.
Íà îñíîâàíèè òåîðåìû 1 ìîæíî ñäåëàòü âàæíûé (íà íàø âçãëÿä) âûâîä: åñëè
îáðàç ôóíêöèè f , ò.å. ìíîæåñòâî B, ðàçáèòî ïðàâèëüíî, à íå ïðîèçâîëüíî ïîêðû-
òî, òî îáúåäèíåíèå ëèíèé óðîâíÿ ïðåäñòàâëÿåò ñîáîé êëàññû òîëåðàíòíîñòè, ò.å.
ìíîæåñòâà, ñõîäíûå ïî êàêèì-òî ïðèçíàêàì. Òàêèå ñèòóàöèè çà÷àñòóþ èìåþò
ìåñòî â çàäà÷àõ êëàññèôèêàöèè è ðàñïîçíàâàíèÿ [7].
Èç òåîðåìû âûòåêàþò î÷åâèäíûå ñëåäñòâèÿ.
Ñëåäñòâèå 1. Äëÿ ëþáîãî ôóíêöèîíàëüíîãî îòíîøåíèÿ, ïîðîæäåííîãî ðàç-
áèåíèåì, ïîíÿòèÿ ñìåæíîãî êëàññà è êëàññà òîëåðàíòíîñòè ñîâïàäàþò. Âåðíî è
îáðàòíîå óòâåðæäåíèå.
Ñëåäñòâèå 2. Äëÿ ëþáîãî ôóíêöèîíàëüíîãî îòíîøåíèÿ ïîêðûòèÿ �A (èç
ñìåæíûõ êëàññîâ) è GA (èç êëàññîâ òîëåðàíòíîñòè) ñîâïàäàþò òîãäà è òîëüêî
òîãäà, êîãäà ýòî îòíîøåíèå ïîðîæäåíî ðàçáèåíèåì.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåííûé â ñòàòüå ïîäõîä îñíîâàí íà ïðåäïîëîæåíèè, ÷òî òîëåðàíòíîñòü
ïîðîæäàåòñÿ íåêîòîðîé ôóíêöèåé íà ìíîæåñòâå, ÷òî ÿâëÿåòñÿ âàæíûì ÷àñ-
òíûì ñëó÷àåì, íî íå ñàìûì îáùèì ñïîñîáîì çàäàíèÿ îòíîøåíèÿ òîëåðàíòíîñ-
òè. Äàííàÿ ðàáîòà ñâÿçàíà ñ èçó÷åíèåì ïîêðûòèé, ïîðîæäàåìûõ îòíîøåíèåì
ñõîäñòâà èëè îòíîøåíèåì òîëåðàíòíîñòè. Ïîäîáíûå âîïðîñû ÷àñòî âîçíèêàþò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 37
â çàäà÷àõ ðàñïîçíàâàíèÿ îáðàçîâ, ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ,
êîìáèíàòîðíîé ãåîìåòðèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ç è ì à í Ý . , Á ü þ í å ì à í Î . Òîëåðàíòíûå ïðîñòðàíñòâà è ìîçã // Íà ïóòè ê òåîðåòè÷åñêîé
áèîëîãèè. — Ì.: Ìèð, 1970. — Ñ. 52–68.
2. Ø ð å é ä å ð Þ . À . Ðàâåíñòâî, ñõîäñòâî, ïîðÿäîê. — Ì.: Ìèð, Íàóêà, 1971. — 254 ñ.
3. Ø ð å é ä å ð Þ . À . Ïðîñòðàíñòâà òîëåðàíòíîñòè // Êèáåðíåòèêà. — 1970. — ¹ 2. — Ñ. 124–128.
4. ß ê ó á î â è ÷ Ñ . Ì . Àêñèîìàòè÷åñêàÿ òåîðèÿ ñõîäñòâà // ÍÒÈ. Ñåð.2. — 1968. — ¹ 10. — Ñ. 15–19.
5. Ã å ð à ñ è í Ñ . Í . , Ñ ê ë ÿ ð Å . Â . , Ø ë ÿ õ î â Â . Â . Îá îäíîì ñâîéñòâå îòíîøåíèÿ òîëåðàíòíîñòè
// Äîï. ÍÀÍ ÓêðàÂíè. — 2003. — ¹ 12. — Ñ. 58–62.
6. Ì à ë ü ö å â À . È . Àëãåáðàè÷åñêèå ñèñòåìû. — Ì.: Íàóêà, 1970. — 392 ñ.
7. Ì à ø ò à ë è ð  . Ï . , Ø ë ÿ õ î â  .  . , ß ê î â ë å â Ñ .  . Ñâîéñòâà ìíîãîçíà÷íûõ îòîáðàæåíèé â
çàäà÷àõ ðàñïîçíàâàíèÿ // Äîï. ÍÀÍ ÓêðàÂíè. — 2000. — ¹ 12. — Ñ. 72–76.
Ïîñòóïèëà 17.04.2007
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
|