С.С. Марченков - Избранные главы дискретной математики (1124120), страница 12
Текст из файла (страница 12)
, xn ) íåîáõîäèìî èç âûõîäíîé ïîñëåäîâàòåëüíîñòè ôóíêöèèf (ā1 x1 , . . . , ān xn ) èñêëþ÷èòü ïåðâûå l ðàçðÿäîâ. Ïîëüçóÿñü äåòåðìèíèðîâàííîñòüþ ôóíêöèè f , íåòðóäíî óñòàíîâèòü, ÷òî ôóíêöèÿ fā1 ...ān òàêæåÿâëÿåòñÿ äåòåðìèíèðîâàííîé.Íàçîâåìäåòåðìèíèðîâàííîé ôóíêöèè ÷èñëî åå ðàçëè÷íûõ îñòàòî÷íûõ ôóíêöèé. Îòìåòèì, ÷òî âåñ ôóíêöèè ìîæåò áûòü áåñêîíå÷íûì.Âåðíåìñÿ ê ïðèìåðàì à)ã) äåòåðìèíèðîâàííûõ ôóíêöèé. Ó ôóíêöèèfϕ èìååòñÿ òîëüêî îäíà îñòàòî÷íàÿ ôóíêöèÿ îíà ñàìà. Òàêèì îáðàçîì,âåñ ôóíêöèè fϕ ðàâåí 1.
Ôóíêöèÿ ç(x) èìååò k îñòàòî÷íûõ ôóíêöèé:êðîìå ñàìîé ôóíêöèè ç(x) îñòàëüíûå k − 1 ôóíêöèé îòâå÷àþò îäíîáóêâåííûì ñëîâàì 1, 2, . . . , k − 1. Èíûìè ñëîâàìè, åñëè i ∈ {1, 2, . . . , k − 1},äîñòàòî÷íóþ ôóíêöèþäâåñîì53òî ñîîòâåòñòâóþùàÿ ôóíêöèÿ áóäåò ïîëó÷àòüñÿ èç ôóíêöèè ç(ix) èñêëþ÷åíèåì ïåðâîãî âûõîäíîãî ðàçðÿäà. ïðèìåðå â) èìåþòñÿ òîëüêî äâå îñòàòî÷íûå ôóíêöèè: îäíà ôóíêöèÿèñõîäíàÿ (îíà ñîîòâåòñòâóåò ñëó÷àþ, êîãäà â ïåðâûé ðàçðÿä ïåðåíîñ îòñóòñòâóåò), äðóãàÿ ôóíêöèÿ îòâå÷àåò ñëó÷àþ ïåðåíîñà â ïåðâûé ðàçðÿä÷èñëà 1.
Âòîðóþ ôóíêöèþ ìîæíî, íàïðèìåð, ïîëó÷èòü, ðàññìàòðèâàÿñëîæåíèå âèäà (k − 1)x + (k − 1)y (íàïîìíèì, ÷òî ìëàäøèé ðàçðÿä âïîñëåäîâàòåëüíîñòè (k − 1)x ðàâåí k − 1).Äåòåðìèíèðîâàííàÿ ôóíêöèÿ èç ïðèìåðà ã) èìååò áåñêîíå÷íûé âåñ.×òîáû â ýòîì óáåäèòüñÿ, äîñòàòî÷íî, íàïðèìåð, ðàññìîòðåòü áåñêîíå÷íóþ ïîñëåäîâàòåëüíîñòü ñëîâ ā, ñîñòîÿùèõ òîëüêî èç ñèìâîëîâ 0.Íàçîâåì äåòåðìèíèðîâàííóþ ôóíêöèþ, åñëèîíà èìååò êîíå÷íûé âåñ.
Ìíîæåñòâî âñåõ êîíå÷íî-àâòîìàòíûõ ôóíêöèéèç P ,k îáîçíà÷èì ÷åðåç P ,k .Òàê æå, êàê è âûøå, äëÿ êîíå÷íî-àâòîìàòíûõ ôóíêöèé ïðèìåíèìûñïîñîáû çàäàíèÿ ñ ïîìîùüþ êàíîíè÷åñêèõ óðàâíåíèé è äèàãðàìì Ìóðà.Ïóñòü f (x1 , . . . , xn ) êîíå÷íî-àâòîìàòíàÿ ôóíêöèÿ âåñà r è f1 , . . . , fr âñå åå îñòàòî÷íûå ôóíêöèè (ñ÷èòàåì, ÷òî f1 = f ). Ââèäó êîíå÷íîñòèâåñà ôóíêöèè f äëÿ ïîëíîãî çàäàíèÿ ôóíêöèè f äîñòàòî÷íî ïðè ëþáîìi (1 6 i 6 r) è ëþáîì íàáîðå (a1 , . .
. , an ) èç Ekn óêàçàòü, êàêàÿ îñòàòî÷íàÿôóíêöèÿ fj ïîëó÷èòñÿ èç ôóíêöèè fi , åñëè â êà÷åñòâå ïåðâîãî íàáîðàâõîäíîé ïîñëåäîâàòåëüíîñòè (x1 , . . . , xn ) áóäåò ïîäàí íàáîð (a1 , . . . , an ),è êàêîé ñèìâîë ïðè ýòîì áóäåò íà âûõîäå. Ïîýòîìó, åñëè îñòàòî÷íûåôóíêöèè f1 , . . . , fr ñ÷èòàòü ñîñòîÿíèÿìè q1 , . . .
, qr , òî ìû ñðàçó ïðèõîäèìê, çàäàþùèì ôóíêöèþ f :êîíå÷íî-àâòîìàòíîéäêàêàíîíè÷åñêèì óðàâíåíèÿì y(t) = F (x1 (t), . . . , xn (t), q(t − 1)),q(t) = G(x1 (t), . . . , xn (t), q(t − 1)),q(0) = q1 ,(3.3)ãäå ôóíêöèè F è G îòîáðàæàþò ìíîæåñòâî Ekn × {q1 , . . . , qr } â ìíîæåñòâà Ek è {q1 , . . . , qr } ñîîòâåòñòâåííî. Äèàãðàììó Ìóðà ëåãêî ïîñòðîèòüëèáî ïî ïðèâåäåííîìó âûøå çàäàíèþ ôóíêöèè f ÷åðåç åå îñòàòî÷íûåôóíêöèè, ëèáî ïî êàíîíè÷åñêèì óðàâíåíèÿì. Òàê æå, êàê â 2, íà äóãàõ äèàãðàììû Ìóðà áóäóò ïðèñóòñòâîâàòü äâå ïîìåòêè: âõîäíîé íàáîð(x1 (t), .
. . , xn (t)) èç Ekn è ñîîòâåòñòâóþùåå åìó âûõîäíîå çíà÷åíèå y(t)(òàêæå èç ìíîæåñòâà Ek ). êà÷åñòâå ïðèìåðà ïðèâåäåì äèàãðàììû Ìóðà äëÿ ôóíêöèé ç(x) èx + y (â îáîèõ ñëó÷àÿõ k = 2):541, 00, 0 ∗q1q20, 11, 1(0, 0), 0(0, 1), 1 ∗(1, 0), 1(1, 1), 0q1q2(0, 0), 1(0, 1), 0(1, 0), 0(1, 1), 1×òîáû èñïîëüçîâàòü â äàëüíåéøåì òåõíèêó è ðåçóëüòàòû èç òåîðèèáóëåâûõ ôóíêöèé è ôóíêöèé ìíîãîçíà÷íîé ëîãèêè, ìû õîòèì â êàíîíè÷åñêèõ óðàâíåíèÿõ (3.3) ïðèäàòü ôóíêöèÿì F, G áîëåå ¾ñòàíäàðòèçîâàííóþ¿ ôîðìó. Ñ ýòîé öåëüþ âûáåðåì äëÿ äàííîãî ÷èñëà r (êîòîðîåèñïîëüçóåòñÿ â óðàâíåíèÿõ (3.3)) ÷èñëî l ñ óñëîâèåì k l > r.
Çàêîäèðóåìñîñòîÿíèÿ q1 , . . . , qr ñëîâàìè äëèíû l â àëôàâèòå Ek (ïðè ýòîì â ñëó÷àåíåðàâåíñòâà k l > r íåêîòîðûå ñëîâà äëèíû l îêàæóòñÿ ¾íåâîñòðåáîâàííûìè¿). Óäîáíî ñ÷èòàòü, ÷òî êîäîì (íà÷àëüíîãî) ñîñòîÿíèÿ q1 ÿâëÿåòñÿñëîâî 0 . . . 0. Ââîäÿ òåïåðü ïåðåìåííûå q1 (t), . . . , ql (t) äëÿ ñîîòâåòñòâóþùèõ ðàçðÿäîâ êîäà, ïðåîáðàçóåì óðàâíåíèÿ (3.3) â óðàâíåíèÿy(t) = F (x1 (t), . . . , xn (t), q1 (t − 1), . . . , ql (t − 1)), q1 (t) = G1 (x1 (t), . .
. , xn (t), q1 (t − 1), . . . , ql (t − 1)),................................................q (t) = Gl (x1 (t), . . . , xn (t), q1 (t − 1), . . . , ql (t − 1)), lq1 (0) = . . . = ql (0) = 0,(3.4)ãäå F, G1 , . . . , Gl óæå ÿâëÿþòñÿ ôóíêöèÿìè k -çíà÷íîé ëîãèêè (â òåõ ñëó÷àÿõ, êîãäà ïåðåìåííûå q1 (t − 1), . . .
, ql (t − 1) ïîä çíàêàìè ôóíêöèéG1 , . . . , Gl äàþò íàáîð, íå ÿâëÿþùèéñÿ êîäîì ñîñòîÿíèÿ, çíà÷åíèÿ ôóíêöèé G1 , . . . , Gl ìîæíî çàäàòü ïðîèçâîëüíûì îáðàçîì).Äëÿ ôóíêöèé y = ç(x) è y = x1 + x2 (äëÿ âòîðîé ôóíêöèè k = 2)ïðèâåäåì êàíîíè÷åñêèå óðàâíåíèÿ âèäà (3.4): y(t) = q(t − 1),q(t) = x(t),q(0) = 0, y(t) = x1 (t) ⊕ x2 (t) ⊕ q(t − 1),q(t) = x1 (t)x2 (t) ∨ x1 (t)q(t − 1) ∨ x2 (t)q(t − 1),q(0) = 0.ÓÏÐÀÆÍÅÍÈßÏóñòü ôóíêöèÿ y = f (x) ïðèíàäëåæèò êëàññó P2∞ .
Âûÿñíèòü, ÿâëÿåòñÿ ëè îíà äåòåðìèíèðîâàííîé, åñëè:3.551)2)3)4)∞0 è5)y(t) = x(1) ⊕ x(2) ⊕ . . . ⊕ x(t) ïðè t > 1;y(1) = 1 è y(t) = x(t + x(t)) ïðè t > 2;y(t) = 0 ïðè t 6 50 è y(t) = x̄(t − 7) ïðè t > 50;f (x) = 0∞ , åñëè x = 0∞ , è f (x) = 1∞ â ïðîòèâíîì ñëó÷àå (çäåñü1∞ ñîîòâåòñòâåííî íóëåâàÿ è åäèíè÷íàÿ ïîñëåäîâàòåëüíîñòè);f (x) = 1∞ , åñëè x = 0∞ , è y(t) = x̄(t) â ïðîòèâíîì ñëó÷àå (t > 1).4. Íàéòè âñå îñòàòî÷íûå ôóíêöèè ó ôóíêöèè y = f (x), åñëè:1) y(1) = 0 è y(t) = x(t − 1) ⊕ x(t) ïðè t > 2;2) y(t) = x̄(t), åñëè t íå÷åòíî, è y(t) = x(t), åñëè t ÷åòíî;3) y(t) = 0, åñëè t = i2 (i = 2, 3, .
. .), è y(t) = 1 â îñòàëüíûõ ñëó÷àÿõ.5. Âûÿñíèòü, ÿâëÿåòñÿ ëè ôóíêöèÿ f ∈ Pêîíå÷íî-àâòîìàòíîé è,2íàéòè åå âåñ:1) y(1) = 1 è y(t) = ȳ(t − 1) ïðè t > 2;2) y(t) = x1 (1) ïðè t = 1, 2 è y(t) = x1 (t)x2 (t − 1) ïðè t > 2;3) y(t) = x̄2 (t), åñëè t íå÷åòíî, è y(t) = x1 (t − 1) ∨ x2 (t − 1), åñëè t÷åòíî;4) y(t) = 0, åñëè ÷èñëî åäèíèö â ìíîæåñòâå {x1 (1), . . . , xn (1), . . . , x1 (t),. . . , xn (t)} ÷åòíî, è y(t) = 1 â ïðîòèâíîì ñëó÷àå.ä 4. Îïåðàöèè ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçèÒàê æå, êàê äëÿ áóëåâûõ ôóíêöèé è ôóíêöèé ìíîãîçíà÷íîé ëîãèêè,íà ìíîæåñòâå P ,k ìîæíî ââåñòè îïåðàöèþ ñóïåðïîçèöèè.
Ìû áóäåì ååðàññìàòðèâàòü ëèøü â âèäåäf (x1 , . . . , xn ) = g0 (g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )),(3.5)ïîñêîëüêó ïåðåõîä ê îáùåìó âèäó òðóäíîñòåé ïðèíöèïèàëüíîãî õàðàêòåðà íå äîáàâëÿåò.Òåîðåìà 3.3.çèöèè.Êëàññ Pä,k çàìêíóò îòíîñèòåëüíî îïåðàöèè ñóïåðïî-Îáîçíà÷èì ÷åðåç X(t) âåêòîð ïåðåìåííûõ x1 (t), . .
. ,xn (t). Ñîãëàñíî îïðåäåëåíèþ äåòåðìèíèðîâàííîé ôóíêöèè äëÿ âñÿêîãît > 1 ñóùåñòâóþò òàêèå ôóíêöèè Gt0 , Gt1 , . . . , Gtm èç Pk , ÷òî äëÿ âûõîäíûõ ïåðåìåííûõ y0 , y1 , . . . , ym ôóíêöèé g0 , g1 , . . . , gm áóäåì èìåòüÄîêàçàòåëüñòâî.y0 (t) = Gt0 (z1 (1), . . . , zm (1), . . . , z1 (t), . . . , zm (t),yi (t) = Gti (X(1), . . . , X(t)) (1 6 i 6 m).56Òîãäà, îáîçíà÷èâ ÷åðåç y âûõîäíóþ ïåðåìåííóþ ôóíêöèè f èç ðàâåíñòâà(3.5), ïîëó÷èìy(t) = Gt0 (G11 (X(1)), . . . , G1m (X(1)), . . . , Gt1 (X(1), . .
. , X(t)), . . .. . . , Gtm (X(1), . . . , X(t))).Îòñþäà ñëåäóåò äåòåðìèíèðîâàííîñòü ôóíêöèè f . Òåîðåìà äîêàçàíà.Òåîðåìà 3.4.ïîçèöèè.Êëàññ Pêà,k çàìêíóò îòíîñèòåëüíî îïåðàöèè ñóïåð-Âíîâü îãðàíè÷èìñÿ ñóïåðïîçèöèåé âèäà (3.5). Ïóñòüôóíêöèè g0 , g1 , . . . , gm çàäàíû ñëåäóþùìè êàíîíè÷åñêèìè óðàâíåíèÿìè:Äîêàçàòåëüñòâî. y0 (t) = F0 (y1 (t), . . . , ym (t), Q0 (t − 1)),Q (t) = G0 (y1 (t), . .
. , ym (t), Q0 (t − 1)), 0Q0 (0) = 0, yi (t) = Fi (X(t), Qi (t − 1)),Q (t) = Gi (X(t), Qi (t − 1)), iQi (0) = 0,ãäå X(t) åñòü íàáîð ïåðåìåííûõ x1 (t), . . . , xn (t) è 1 6 i 6 m. Èñõîäÿ èçôîðìóëû (3.5), ñòðîèì êàíîíè÷åñêèå óðàâíåíèÿ, îïðåäåëÿþùèå ôóíêöèþ f :y(t) = F0 (F1 (X(t), Q1 (t − 1)), . . . , Fm (X(t), Qm (t − 1)), Q0 (t − 1)),Q0 (t) = G0 (F1 (X(t), Q1 (t − 1)), .
. . , Fm (X(t), Qm (t − 1)), Q0 (t − 1)),Q1 (t) = G1 (X(t), Q1 (t − 1)),...........................Q (t) = Gm (X(t), Qm (t − 1)), mQ0 (0) = Q1 (0) = . . . = Qm (0) = 0.Òåîðåìà äîêàçàíà.Èç äîêàçàòåëüñòâà òåîðåìû 3.4 âèäíî, ÷òî åñëè êîíå÷íî-àâòîìàòíûåôóíêöèè g0 , g1 , . . . , gm èìåþò ñîîòâåòñòâåííî âåñ r0 , r1 , . . . , rm , òî êîíå÷íîàâòîìàòíàÿ ôóíêöèÿ f , îïðåäåëÿåìàÿ ðàâåíñòâîì (3.5), èìååò âåñ, íåïðåâîñõîäÿùèé âåëè÷èíû r0 · r1 · . . . · rm . Íà ñàìîì äåëå ýòà îöåíêà äîñòèæèìà. Íå óãëóáëÿÿñü â äîêàçàòåëüñòâî äîñòèæèìîñòè ýòîé îöåíêè âîáùåì ñëó÷àå, óêàæåì ëèøü íà ïðîñòîé ïðèìåð: l-êðàòíàÿ ñóïåðïîçèöèÿç(. .
. ç(x) . . .) åäèíè÷íîé çàäåðæêè ç(x) èìååò âåñ k l .57Áóäåì ãîâîðèòü, ÷òî äåòåðìèíèðîâàííàÿ ôóíêöèÿ y = f (x1 , . . . , xi ,. . . , xn ) çàâèñèò îò ïåðåìåííîé xi, åñëè ïðè ëþáîì tçíà÷åíèå y(t) çàâèñèò îò çíà÷åíèé xj (1), . . . , xj (t) ïðè j 6= i, îò çíà÷åíèéxi (1), . . . , xi (t − 1) è íå çàâèñèò ñóùåñòâåííî îò çíà÷åíèÿ xi (t).Ñàìûì ïðîñòûì è âàæíûì ïðèìåðîì ôóíêöèè, çàâèñÿùèì îò ïåðåìåííîé ñ çàïàçäûâàíèåì, ÿâëÿåòñÿ åäèíè÷íàÿ çàäåðæêà ç(x).Îòìåòèì, ÷òî â êàíîíè÷åñêèõ óðàâíåíèÿõ äëÿ êîíå÷íî-àâòîìàòíîéôóíêöèè f , çàâèñÿùåé ñ çàïàçäûâàíèåì îò ïåðåìåííîé xi , ïðàâàÿ ÷àñòüóðàâíåíèÿ äëÿ âûõîäíîãî çíà÷åíèÿ y(t) íå çàâèñèò ñóùåñòâåííî îò ïåðåìåííîé xi (t).Ïåðåéäåì ê îïðåäåëåíèþ îïåðàöèè.
Ïóñòü{f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn )} ñèñòåìà äåòåðìèíèðîâàííûõ ôóíêöèé, m > 2 è ôóíêöèÿ fj çàâèñèò ñ çàïàçäûâàíèåì îò ïåðåìåííîé xi . Òîãäà â ñèñòåìå ìîæíî ââåñòè îáðàòíóþ ñâÿçü ïî ïåðåìåííûì xi è yj (¾ïðèñîåäèíèòü¿ âûõîäíóþ ïåðåìåííóþ yj ê âõîäíîé ïåðåìåííîé xi ).  ðåçóëü0,òàòå îáðàçóåòñÿ ñèñòåìà (äåòåðìèíèðîâàííûõ) ôóíêöèé {f10 , . . . , fj−100fj+1 , . . . , fm } îò ïåðåìåííûõ x1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
