С.С. Марченков - Избранные главы дискретной математики (1124120), страница 13
Текст из файла (страница 13)
. . , xi−1 , xi+1 , . . . , xn .Ôîðìàëüíî çíà÷åíèÿ ôóíêöèé fl0 âû÷èñëÿþòñÿ ñëåäóþùèì îáðàçîì.Âîçüìåì íàáîð ïåðåìåííûõñ çàïàçäûâàíèåìââåäåíèÿ îáðàòíîé ñâÿçèx1 (1), . . . , xi−1 (1), xi+1 (1), . . . , xn (1).(3.6)Ïîñêîëüêó ôóíêöèÿ fj çàâèñèò îò ïåðåìåííîé xi ñ çàïàçäûâàíèåì, çíà÷åíèå yj (1) ìîæíî âû÷èñëèòü íà îñíîâå íàáîðà ïåðåìåííûõ (3.6).
Ñëåäîâàòåëüíî, ñîãëàñíî îïðåäåëåíèþ îáðàòíîé ñâÿçè, ïðè l 6= j çíà÷åíèåyl0 (1) áóäåò ÿâëÿòüñÿ ôóíêöèåé îòx1 (1), . . . , xi−1 (1), yj (1), xi+1 (1), . . . , xn (1),ò.å. îò âåëè÷èí (3.6).Âîîáùå, åñëè çíà÷åíèå yj (t) (â èñõîäíîé ñèñòåìå ôóíêöèé) âû÷èñëÿåòñÿ ÷åðåç çíà÷åíèÿ ïåðåìåííûõ xl (v), ãäå v = 1, . . . , t ïðè l 6= j èv = 1, .
. . , t − 1 ïðè l = j , òî ïîñëå ââåäåíèÿ îáðàòíîé ñâÿçè ïî ïåðåìåííûì xi è yj çíà÷åíèå yl0 (t) ïðè l 6= j áóäåò ÿâëÿòüñÿ ôóíêöèåé îòx1 (1), . . . , xn (1), . . . , x1 (t − 1), . . . , xn (t − 1), x1 (t), . . . , xi−1 (t),yj (t), xi+1 (t), . . . , xn (t),ò.å. îò çíà÷åíèé ïåðå÷èñëåííûõ ïåðåìåííûõ xl (v), îòëè÷íûõ îò ïåðåìåííîé xi (t).58000}, fj+1, .
. . , fmÎïèñàííûé ïðîöåññ âû÷èñëåíèÿ ôóíêöèé {f10 , . . . , fj−1ïîêàçûâàåò, ÷òî ýòè ôóíêöèè òàêæå áóäóò ÿâëÿòüñÿ äåòåðìèíèðîâàííûìè ôóíêöèÿìè.Åñëè f1 , . . . , fm êîíå÷íî-àâòîìàòíûå ôóíêöèè, òî îïåðàöèþ ââåäåíèÿ îáðàòíîé ñâÿçè ëåãêî îïðåäåëèòü ñ èñïîëüçîâàíèåì êàíîíè÷åñêèõóðàâíåíèé.  ñàìîì äåëå, åñëè âûõîä yj (t) îïðåäåëÿåòñÿ óðàâíåíèåìyj (t) = Fj (x1 (t), . . . , xi−1 (t), xi+1 (t), . . .
, xn (t), q1 (t − 1), . . . , ql (t − 1)),(3.7)òî ïðàâóþ ÷àñòü ýòîãî óðàâíåíèÿ íåîáõîäèìî ïîäñòàâèòü âìåñòî ïåðåìåííîé xi (t) âî âñå îñòàëüíûå óðàâíåíèÿ ñèñòåìû. Ïðè ýòîì óðàâíåíèå (3.7)èç ñèñòåìû âû÷åðêèâàåòñÿ. Îáðàçîâàâøàÿñÿ ñèñòåìà êàíîíè÷åñêèõ óðàâ00íåíèé áóäåò îïðåäåëÿòü (êîíå÷íî-àâòîìàòíûå) ôóíêöèè {f10 , . . . , fj−1, fj+1,0. .
. , fm }, ïîëó÷åííûå â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèè ââåäåíèÿ îáðàòíîé ñâÿçè ïî ïåðåìåííûì xi è yj . ×òîáû óáåäèòüñÿ â ýòîì, äîñòàòî÷íî00,, fj+1åùå ðàç ïðîñìîòðåòü àëãîðèòì âû÷èñëåíèÿ ôóíêöèé {f10 , . . . , fj−10. . . , fm }, èçëîæåííûé âûøå äëÿ ïðîèçâîëüíûõ äåòåðìèíèðîâàííûõ ôóíêöèé.Êàê âèäíî èç ïðîâåäåííûõ ðàññóæäåíèé, îïåðàöèÿ ââåäåíèÿ îáðàòíîéñâÿçè íå ïðèâîäèò ê óâåëè÷åíèþ âåñà ôóíêöèè.Ïîëó÷åííûå âûøå ðåçóëüòàòû ìû ïîäûòîæèì â âèäå òåîðåìû.Êëàññû Pä,k è Pêà,k çàìêíóòû îòíîñèòåëüíî îïåðàöèèââåäåíèÿ îáðàòíîé ñâÿçè.Òåîðåìà 3.5.ÓÏÐÀÆÍÅÍÈßÄëÿ ñóïåðïîçèöèè f (x) = f1 (f2 (x)) ïîñòðîèòü êàíîíè÷åñêèå óðàâíåíèÿ è îïðåäåëèòü âåñ ïîëó÷åííîé ôóíêöèè:6. y1 (t) = q̄1 (t − 1), y2 (t) = q2 (t − 1),1) f1 :q (t) = q1 (t − 1) → x1 (t),f2 :q (t) = x̄2 (t), 1 2q1 (0) = 0,q2 (0) = 0; y1 (t) = x1 (t) · q1 (t − 1),y2 (1) = 1,2) f1 :q1 (t) = q̄1 (t − 1),f2 :y2 (t) = x2 (t) ⊕ y2 (t − 1), t > 2;q1 (0) = 0,y(1)=0, 1 y2 (t) = q2 (t − 1) → x2 (t),3) f1 :y (t) = x1 (t − 1) → y1 (t − 1),f2 :q (t) = x2 (t), 1 2t > 2,q2 (0) = 1.59Ïîñòðîèòü êàíîíè÷åñêèå óðàâíåíèÿ è íàéòè âåñ êîíå÷íî-àâòîìàòíîéôóíêöèè, ïîëó÷àþùåéñÿ èç ôóíêöèè f ââåäåíèåì îáðàòíîé ñâÿçè ïî ïåðåìåííûì xi , yj :7.y1 (t) = x1 (t) · q(t − 1) ∨ x2 (t),y2 (t) = x2 (t),i = 1, j = 2;1) f :q(t)=(x(t)→x(t))∨q(t−1),12q(0) = 0,y1 (t) = x1 (t) ⊕ q1 (t − 1) · q2 (t − 1), y2 (t) = x2 (t) → q2 (t − 1),q1 (t) = q1 (t − 1) ⊕ q2 (t − 1),2) f :q (t) = x1 (t) ⊕ q1 (t − 1), 2q1 (0) = q2 (0) = 0,à) i = 1, j = 2;á) i = 2, j = 1. 5.
Êîíå÷íàÿ ïîðîæäàåìîñòü êëàññà êîíå÷íî-àâòîìàòíûõôóíêöèé. Íåñâîäèìîñòü îïåðàöèè ââåäåíèÿ îáðàòíîé ñâÿçè êîïåðàöèè ñóïåðïîçèöèè 3 áûëî îïðåäåëåíî ñîîòâåòñòâèå ìåæäó ôóíêöèÿìè ϕ k -çíà÷íîéëîãèêè è èñòèííîñòíûìè ôóíêöèÿìè fϕ èç êëàññà P ,k . Íåòðóäíî âèäåòü, ÷òî ýòî ñîîòâåòñòâèå ñîõðàíÿåòñÿ ïðè îïåðàöèè ñóïåðïîçèöèè. Â÷àñòíîñòè, åñëè ñèñòåìà ôóíêöèé {ϕ1 , . . . , ϕm } ïîëíà (îòíîñèòåëüíî ñóïåðïîçèöèè) â êëàññå Pk , òî ñèñòåìà ôóíêöèé {fϕ1 , . . . , fϕm } áóäåò ïîëíîéâ ìíîæåñòâå âñåõ èñòèííîñòíûõ ôóíêöèé èç P ,k .Ìû õîòèì ïðîäîëæèòü èññëåäîâàíèå â ýòîì íàïðàâëåíèè è ïîëó÷èòüêîíå÷íóþ ïîëíóþ ñèñòåìó âî âñåì êëàññå P ,k . Îäíàêî, êàê ìû óâèäèì ïîçæå, îäíîé òîëüêî îïåðàöèåé ñóïåðïîçèöèè â ýòîì ñëó÷àå îáîéòèñü íåâîçìîæíî, òðåáóåòñÿ èñïîëüçîâàòü è îïåðàöèþ ââåäåíèÿ îáðàòíîéñâÿçè.êàêàêàÏðè ëþáîì k > 2 êëàññ Pêà,k ñîäåðæèò êîíå÷íóþñèñòåìó ôóíêöèé, ïîëíóþ îòíîñèòåëüíî îïåðàöèé ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçè.Òåîðåìà 3.6.Âîçüìåì êàêóþ-ëèáî ñèñòåìó ôóíêöèé {ϕ1 , .
. . ,ϕm }, ïîëíóþ â êëàññå Pk îòíîñèòåëüíî îïåðàöèè ñóïåðïîçèöèè. Ïóñòüf (x1 , . . . , xn ) ïðîèçâîëüíàÿ ôóíêöèÿ èç P ,k , êîòîðàÿ îïðåäåëÿåòñÿÄîêàçàòåëüñòâî.êà60ñèñòåìîé êàíîíè÷åñêèõ óðàâíåíèé (4). Ìû íå èçìåíèì ôóíêöèþ, îïðåäåëÿåìóþ ñèñòåìîé óðàâíåíèé (3.4), åñëè â ïðàâûõ ÷àñòÿõ óðàâíåíèé(3.4) âìåñòî ôóíêöèé F, G1 , . . .
, Gl áóäåì ðàññìàòðèâàòü ñîîòâåòñòâóþùèå èñòèííîñòíûå ôóíêöèè fF , fG1 , . . . , fGl . Êàê îòìå÷åíî âûøå, äàííûå ôóíêöèè ìîæíî ðåàëèçîâàòü ñóïåðïîçèöèÿìè èñòèííîñòíûõ ôóíêöèé {fϕ1 , . . . , fϕm }. Èç ñèñòåìû óðàâíåíèé (3.4) îáðàçóåì ñèñòåìóy(t) = fF (x1 (t), . . . , xn (t), ç(q1 )(t), . .
. , ç(ql )(t)),q1 (t) = fG1 (x1 (t), . . . , xn (t), ç(q10 )(t), . . . , ç(ql0 )(t)),................................................ql (t) = fGl (x1 (t), . . . , xn (t), ç(q10 )(t), . . . , ç(ql0 )(t)),(3.8)ãäå íàðÿäó ñ ïåðåìåííûìè x1 , . . . , xn ðàññìàòðèâàþòñÿ òàêæå íîâûå âõîäíûå ïåðåìåííûå q10 , . . . , ql0 è ¾íîâûå¿ âûõîäíûå ïåðåìåííûå q1 , . . . , ql .Ñðàâíèâàÿ ñèñòåìû (3.4) è (3.8), çàìå÷àåì, ÷òî ñèñòåìà (3.8) áóäåò êîððåêòíî îïðåäåëÿòü ôóíêöèþ f , åñëè ïåðåìåííûå q10 , . . .
, ql0 çàìåíèòü ñîîòâåòñòâåííî ïåðåìåííûìè q1 , . . . , ql (çíà÷åíèÿ ïåðåìåííûõ q1 , . . . , ql ïðèt = 0 ó÷èòûâàþòñÿ â îïðåäåëåíèè åäèíè÷íîé çàäåðæêè ç). Âìåñòå ñ òåì,êàê âèäíî èç óðàâíåíèé ñèñòåìû (3.8), ôóíêöèè q1 , . . . , ql çàâèñÿò ñ çàïàçäûâàíèåì îò ïåðåìåííûõ q10 , . . . , ql0 . Ýòî çíà÷èò, ÷òî óêàçàííóþ çàìåíóïåðåìåííûõ ìîæíî âûïîëíèòü, åñëè ïîñëåäîâàòåëüíî ââîäèòü îáðàòíóþñâÿçü ïî ïàðàì ïåðåìåííûõ (q1 , q10 ), . .
. , (ql , ql0 ). Òàêèì îáðàçîì, ïî îòíîøåíèþ ê îïåðàöèÿì ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçè ïîëíîé âêëàññå P ,k áóäåò ñèñòåìà {fϕ1 , . . . , fϕm , ç}. Òåîðåìà äîêàçàíà.Íàïîìíèì, ÷òî ÷åðåç V (x1 .x2 ) ìû îáîçíà÷èëè ôóíêöèþ Âåááà, êîòîðàÿ îáðàçóåò ïîëíóþ â Pk ñèñòåìó.êàÏðè ëþáîì k > 2 ñèñòåìà ôóíêöèé {fV , ç} ïîëíà â êëàññå Pêà,k îòíîñèòåëüíî îïåðàöèé ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçè.Ïðè ëþáîì k > 2 â êëàññå Pêà,k èìååòñÿ òàêàÿ ôóíêöèÿ f (x1, x2, x3, x4), ÷òî ñèñòåìà {f } ïîëíà â êëàññå Pêà,k îòíîñèòåëüíî îïåðàöèé ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçè.Ñëåäñòâèå.Òåîðåìà 3.7.Äîêàçàòåëüñòâî.Ðàññìîòðèì ñëåäóþùóþ ôóíêöèþ F èç êëàññà Pk :F (x1 , x2 , x3 , x4 ) = max(x1 x4 + x3 (1 − x4 ), x2 ) + 1 (mod k).Èç îïðåäåëåíèÿ ñëåäóåò, ÷òîF (x1 , x2 , x1 , x4 ) = max(x1 , x2 ) + 1 = V (x1 , x2 ), F (1, 0, 0, x4 ) = x4 + 1.(3.9)61Ïîëîæèìf (x1 , x2 , x3 , x4 ) = fF (x1 , x2 , x3 , ç(x4 )).Ñîîòíîøåíèÿ (3.9) ïîêàçûâàþò, ÷òî ñóïåðïîçèöèÿìè ôóíêöèè f ìîæíîïîëó÷èòü ôóíêöèè fV , f0 , f1 , fx+1 .
Ñëåäîâàòåëüíî, ìîæíî òàêæå ïîëó÷èòü ôóíêöèþ ç(x) + 1 è, çíà÷èò, ôóíêöèþ ç(x). Îáðàùåíèå ê ñëåäñòâèþèç òåîðåìû 3.6 çàâåðøàåò äîêàçàòåëüñòâî òåîðåìû. ñâÿçè ñ äîêàçàííîé òåîðåìîé 3.6 âîçíèêàåò âîïðîñ: ìîæíî ëè â äàííîé òåîðåìå îòêàçàòüñÿ îò îïåðàöèè ââåäåíèÿ îáðàòíîé ñâÿçè? Äðóãèìèñëîâàìè: íåëüçÿ ëè îïåðàöèþ ââåäåíèÿ îáðàòíîé ñâÿçè âûðàçèòü ÷åðåçîïåðàöèþ ñóïåðïîçèöèè? Ìû ïîêàæåì, ÷òî îòâåò íà ýòè âîïðîñû îòðèöàòåëüíûé. îñíîâå ïðîâîäèìûõ íèæå äîêàçàòåëüñòâ ëåæèò ñëåäóþùèé íåòðóäíî äîêàçûâàåìûé ôàêò: åñëè f (X) êîíå÷íî-àâòîìàòíàÿ ôóíêöèÿ âåñàr, à A ïåðèîäè÷åñêàÿ ïîñëåäîâàòåëüíîñòü ñ äëèíîé ïåðèîäà p, òî f (A) òàêæå ïåðèîäè÷åñêàÿ ïîñëåäîâàòåëüíîñòü ñ äëèíîé ïåðèîäà r1 p, ãäår1 6 r. Ïîýòîìó, åñëè èìåþòñÿ êîíå÷íî-àâòîìàòíûå ôóíêöèè ñ âåñàìè,íå ïðåâîñõîäÿùèìè r, òî ëþáàÿ ñóïåðïîçèöèÿ ýòèõ ôóíêöèé ïðè ïðèìåíåíèè ê ïåðèîäè÷åñêîé ïîñëåäîâàòåëüíîñòè ñ äëèíîé ïåðèîäà p áóäåò äàâàòü ïåðèîäè÷åñêóþ ïîñëåäîâàòåëüíîñòü ñ äëèíîé ïåðèîäà âèäàr1 ·.
. .·rs ·p, ãäå âñå ÷èñëà r1 , . . . , rs íå ïðåâîñõîäÿò r. Îòñþäà óæå íåòðóäíîâûâåñòè ñóùåñòâîâàíèå êîíå÷íî-àâòîìàòíîé ôóíêöèè, íå ïðåäñòàâèìîéâ âèäå ñóïåðïîçèöèè äàííûõ ôóíêöèé.Êàê è âûøå, ïîñðåäñòâîì X îáîçíà÷àåì íàáîð ïåðåìåííûõ x1 , . . . , xn .Ïóñòü f (X) êîíå÷íî-àâòîìàòíàÿ ôóíêöèÿ âåñà r, A ïåðèîäè÷åñêàÿ ïîñëåäîâàòåëüíîñòü ñ äëèíîé ïåðèîäà p è B = f (A).Òîãäà ïîñëåäîâàòåëüíîñòü B ïåðèîäè÷åñêàÿ ñ äëèíîé ïåðèîäà r1p, ãäåÒåîðåìà 3.8.r1 6 r.Èç óñëîâèÿ ïåðèîäè÷íîñòè ïîñëåäîâàòåëüíîñòè Añëåäóåò, ÷òî äëÿ íåêîòîðîãî t0 ïðè âñåõ t > t0 âûïîëíÿåòñÿ ðàâåíñòâîÄîêàçàòåëüñòâî.A(t + p) = A(t).Âîçüìåì äëÿ ôóíêöèè f äèàãðàììó Ìóðà ñ r âåðøèíàìè q1 , .
. . , qr . Îáîçíà÷èì ÷åðåç q(t) âåðøèíó, êîòîðàÿ îáðàçóåòñÿ â äèàãðàììå â ìîìåíòâðåìåíè t ïðè ïîäà÷å íà âõîä ïîñëåäîâàòåëüíîñòè A. Ðàññìîòðèì ïîñëåäîâàòåëüíîñòü èç r + 1 ñîñòîÿíèéq(t0 ), q(t0 + p), . . . , q(t0 + rp).62Ïîñêîëüêó ôóíêöèÿ q ïðèíèìàåò ëèøü r çíà÷åíèé, ýòà ïîñëåäîâàòåëüíîñòü ñîäåðæèò ïîâòîðåíèÿ. Ïóñòü, íàïðèìåð,q(t0 + ip) = q(t0 + jp),ãäå 0 6 i < j 6 r.Ïîëîæèì r1 = j − i. Òîãäà, êîíå÷íî, r1 6 r.
Äàëåå, â ñèëó ïåðèîäè÷íîñòèïîñëåäîâàòåëüíîñòè A (ñ äëèíîé ïåðèîäà p) ïîñëåäîâàòåëüíîñòüq(t0 + ip), q(t0 + ip + 1), . . . , q(t0 + jp), . . .áóäåò òàêæå ïåðèîäè÷åñêîé ñ äëèíîé ïåðèîäà r1 p. À òîãäà è ïîñëåäîâàòåëüíîñòü B áóäåò ïåðèîäè÷åñêîé ñ òîé æå ñàìîé äëèíîé ïåðèîäà. Òåîðåìà äîêàçàíà.Ïóñòü f0, f1, . .
. , fm êîíå÷íî-àâòîìàòíûå ôóíêöèèñ âåñàìè r0, r1, . . . , rm, íå ïðåâîñõîäÿùèìè r,Òåîðåìà 3.9.f (X) = f0 (f1 (X), . . . , fm (X)), ïåðèîäè÷åñêàÿ ïîñëåäîâàòåëüíîñòü, äëèíà ïåðèîäà êîòîðîé ñîäåðæèò ëèøü ïðîñòûå ñîìíîæèòåëè, íå ïðåâîñõîäÿùèå r, è B = f (A).Òîãäà B ïåðèîäè÷åñêàÿ ïîñëåäîâàòåëüíîñòü, äëèíà ïåðèîäà êîòîðîéñîäåðæèò ëèøü ïðîñòûå ñîìíîæèòåëè, íå ïðåâîñõîäÿùèå r.AÄîêàçàòåëüñòâî.ÏîëîæèìB1 = f1 (A), .
. . , Bm = fm (A).Ñîãëàñíî òåîðåìå 3.8 ïîñëåäîâàòåëüíîñòè B1 , . . . , Bm ïåðèîäè÷åñêèå, ïðè0÷åì äëÿ íåêîòîðûõ ÷èñåë r10 , . . . , rm, íå ïðåâîñõîäÿùèõ r, äëèíû ïåðèî0äîâ ýòèõ ïîñëåäîâàòåëüíîñòåé èìåþò âèä r10 p, . . . , rmp, ãäå p äëèíà ïåðèîäà ïîñëåäîâàòåëüíîñòè A. Ïîíÿòíî, ÷òî âåêòîð-ïîñëåäîâàòåëüíîñòü(B1 , . .
. , Bm ) òàêæå ïåðèîäè÷åñêàÿ, ïðè÷åì äëèíà åå ïåðèîäà ðàâíà0p0 = ÍÎÊ(r10 p, . . . , rmp). ÷àñòíîñòè, âñå ïðîñòûå ñîìíîæèòåëè ÷èñëà p0 íå ïðåâîñõîäÿò r. Ïîëîæèì C = f0 (B1 , . . . , Bm ). Âíîâü îáðàùàÿñü ê òåîðåìå 3.8, âèäèì, ÷òîïîñëåäîâàòåëüíîñòü C ïåðèîäè÷åñêàÿ è äëèíà åå ïåðèîäà èìååò âèä r00 p0 ,ãäå r00 6 r0 . Òåîðåìà äîêàçàíà.Êëàññ Pêà,k íå ñîäåðæèò êîíå÷íîé ñèñòåìû ôóíêöèé, ïîëíîé îòíîñèòåëüíî îïåðàöèè ñóïåðïîçèöèè.Òåîðåìà 3.10.63Ïðåäïîëîæèì, íàïðîòèâ, ÷òî òàêàÿ ñèñòåìà ôóíêöèé {f1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
