D:\User\sbornik_38_pdf\2.DVI


Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè è âû÷èñëèòåëüíîé òåõíèêè 38, 8{9, 2012.

Î ìèíèìàëüíûõ è ìàêñèìàëüíî òóïèêîâûõ n-
ðàñïîçíàþùèõ ñèñòåìàõ íàòóðàëüíûõ ÷èñåë

Ñ.Ì.Âàðäàíÿí
Institute for Informatics and Automation Problems of NAS of RA

E-mail:seyranv@ipia.sci.am

Íèæå ðàññìàòðèâàþòñÿ n-ðàñïîçíàþùèå ñèñòåìû â êëàññå äâóõýëåìåíòíûõ
ïîäìíîæåñòâ îòíîñèòåëüíî îïåðàöèé ïåðåñå÷åíèÿ è äîïîëíåíèÿ. Àíîëîãè÷íûå
çàäàè ðàññìîòðåíû â [1-3].

Ïðèâåäåì îñíîâíûå îïðåëåäåíèÿ ïîíÿòèé, èñïîëçóåìûõ íèæå. Ðàññìîòðèì
êîíå÷íîå ìíîæåñòâî [n] = f1 ; 2 ; ¢ ¢ ¢ ; ng, n ¸ 3 . ×åðåç R[n] îáîçíà÷èì ìíîæåñòâî
ïîäìíîæåñòâ ìíîæåñòâà [n]. Ïóñòü n¤ = fA1; A2; ¢ ¢ ¢ ; Akg ÿâëÿåòñÿ ïîäìíîæåñòâîì
ìíîæåñâà R[n].

Îïðåäåëåíèå 1. Áóäåì ãîâîðèòü, ÷òî ñèñòåìà n¤ ðàñïîçíàåò ýëåìåíò i 2 [n],
åñëè ñ ïîìîùüþ îïåðàöèé ïåðåñå÷åíèÿ è äîïîëíåíèÿ (ïî îòíîøåíèþ ê k[n]) èç
ìíîæåñòâ A1; A2; ¢ ¢ ¢ ; Ak ìîæíî ïîëó÷èòü fig.

Îïðåäåëåíèå 2. Áóäåì ãîâîðèòü ÷òî n¤ ÿâëÿåòñÿ n-ðàñïîçíàþùèé ñèñòåìîé,
åñëè ñèñòåìà n¤ ðàñïîçíàåò êàæäûé ýëåìåíò i 2 [n].

Îïðåäåëåíèå 3. n-ðàñïîçíàþùàÿ ñèñòåìà n¤ íàçûâàåòñÿ òóïèêîâûé, åñëè
ëþáîå ñîáñòâåííîå ïîäìíîæåñòâî ìíîæåñòâà n¤ íå ÿâëÿåòñÿ n-ðàñïîçíàþùåé
ñèñòåìîé.

Îïðåäåëåíèå 4. n-ðàñïîçíàþùàÿ ñèñòåìà n¤ íàçûâàåòñÿ ìèíèìàëüíîé, åñëè
íå ñóøåñòâóåò n-ðàñïîçíàþùåé ñèñòåìû ñ ìîùíîñòüþ, ìåíøåé, ÷åì jn¤j.

Îïðåäåëåíèå 5. Äâà ïîäìíîæåñòâà ìíîæåñòâà R[n] íàçûâàþòñÿ èçîìîðô-
íûìè, åñëè ñóøåñòâóåò âçàèìíî-îäíîçíà÷íîå îòîáðàæåíèå ìíîæåñòâà [n] íà [n],
ïåðåâîäÿùåå îäíî èç íèõ â äðóãîå.

Îïðåäåëåíèå 6. Ñèñòåìó n¤ íàçûâàåì ìàêñèìàëüíî òóïèêîâîé, åñëè íå
ñóùåñâóåò òóïèêîâîé n-ðàñïîçíàþùåé ñèñòåìû, ó êîòîðîé êîëè÷åñòâî ìíîæåñòâ
áîëüøå ÷åì ó ñèñòåìû n¤.

Íèæå ðàññìàòðèâàþòñÿ òîëüêî òàêèå n-ðàñïîçíàþùèå ñèñòåìû n¤, äëÿ
êîòîðûõ jAij = 2 ïðè ëþáîì i. Â [4,5] óñòàíàâëèâàþòñÿ ìîùíîñòè ìàêñèìàëüíî
òóïèêîâûõ, à òàêæå ìèíèìàëüíûõ ðàñïîçíàþùèõ ñèñòåì.

Òåîðåìà 1. Ïðè n ´ 0 ( m o d 3 ) è n ¸ 9 ÷èñëî ìèíèìàëüíûõ ïîïàðíî íå
èçîìîðôíûõ n-ðàñïîçíàþùèõ ñèñòåì ðàâíî 7.(Ïðè n = 6 , ýòî ÷èñëî ðàâíî 4,
à ïðè n = 3 îíî ðàâíî 1).

Òåîðåìà 2. Ïðè n ´ 1 ( m o d 3 ) è n ¸ 4 ñóøåñòâóåò åäèíñòâåííàÿ ìèíèìàëíàÿ
n-ðàñïîçíàþùàÿ ñèñòåìà ñ òî÷íîñòüþ äî èçîìîðôèçìà.

Òåîðåìà 3. Ïðè n ´ 2 ( m o d 3 ) è n ¸ 5 ÷èñëî ìèíèìàëüíûõ ïîïîðíî íå
èçîìîðôíûõ n-ðàñïîçíàþùèõ ñèñòåì ðàâíî 2.

Òåîðåìà 4. Ïðè n ¸ 3 , ÷èñëî ïîïàðíî íå èçîìîðôíûõ ìàêñèìàëíî òóïèêîâûõ
n-ðàñïîçíàþùèõ ñèñòåì ðàâíî

h
n
2

i
(ãäå

h
n
2

i
åñòü öåëàÿ ÷àñòü n

2
).

8



Ñ. Âàðäàíÿí 9

Ñïèñîê ëèòåðàòóðû

[1] Ï. Ýðäåù, Äæ. Ñïåíñåð, Âåðîÿòíîñòíûå ìåòîäû â êîìáèíàòîðèêå.
Ìîñêâà, Ìèð 1976.

[2] Ñ.Ì. Âàðäàíÿí, Îá îäíîé çàäà÷å ðàñïîçíàâàíèÿ ìíîæåñòâ, ÄÀÍ Àðì. ÑÑÐ,
òîì 72, ñ. 141-143, 1981.

[3] S. M. Vardanyan, Recognizing sets (systems), Proceedings of the International
Conference ”Computer Science and Information Technologies” CSIT05, pp 161 - 162,
Yerevan, Armenia 2005.

[4] S. M. Vardanyan, On the powers of dead-end recognizing systems in the class
of two-element sets concerning operations of intersection and complement, Mathe-
matical Problems of Computer Sciences, vol.35, pp. 104 - 108, 2011.

[5] Ñ. Ì. Âàðäàíÿí, Î ìèíèìàëüíîñòè íåêîòîðûõ ðàñïîçíàþùèõ ñèñòåì
â êëàññå äâóõýëåìåíòíûõ ïîäìíîæåñòâ îòíîñèòåëíî îïåðàöèé ïåðåñå÷åíèÿ è
äîïîëíåíèÿ, ÄÍÀÍ ÐÀ, òîì 112, N1, ñ.57 - 62, 2012.