С.С. Марченков - Избранные главы дискретной математики (1124120), страница 11
Текст из файла (страница 11)
. . ān â âèäå êîíêàòåíàöèè çíà÷åíèéîñòàòî÷íûõ ôóíêöèé ôóíêöèè ϕ íà ñëîâàõ ā1 , . . . , ān . Èìåííî, ïî îïðåäåëåíèþ îñòàòî÷íîé ôóíêöèè ϕā1 ñïðàâåäëèâî ðàâåíñòâîϕ(ā1 ā2 . . . ān ) = ϕ(ā1 )ϕā1 (ā2 . . . ān ).Ôóíêöèÿ ϕā1 òàêæå ÿâëÿåòñÿ äåòåðìèíèðîâàííîé. Ïîýòîìó áóäåò âûïîïîëíÿòüñÿ ðàâåíñòâîϕā1 (ā2 . . . ān ) = ϕā1 (ā2 )ψā2 (ā3 . . . ān ),ãäå ψā2 îñòàòî÷íàÿ ôóíêöèÿ ôóíêöèè ϕā1 . Îäíàêî, êàê ëåãêî ñëåäóåòèç îïðåäåëåíèÿ îñòàòî÷íîé ôóíêöèè, ψā2 = ϕā1 ā2 .
Çíà÷èò,ϕā1 (ā2 . . . ān ) = ϕā1 (ā2 )ϕā1 ā2 (ā3 . . . ān ).Ïðîäîëæàÿ ýòîò ïðîöåññ ïî èíäóêöèè, ïðèäåì ê ñîîòíîøåíèþϕ(ā) = ϕ(ā1 ā2 . . . ān ) = ϕ(ā1 )ϕā1 (ā2 )ϕā1 ā2 (ā3 ) . . . ϕā1 ...ān−1 (ān ).âåñîì(3.1)Íàçîâåìäåòåðìèíèðîâàííîé ôóíêöèè ÷èñëî åå ðàçëè÷íûõ îñòàòî÷íûõ ôóíêöèé. Îòìåòèì, ÷òî âåñ äåòåðìèíèðîâàííîé ôóíêöèè ìîæåòáûòü áåñêîíå÷íûì.Äëÿ êîíå÷íî-àâòîìàòíûõ ôóíêöèé ñìûñë îñòàòî÷íûõ ôóíêöèé âïîëíåî÷åâèäåí. Åñëè ôóíêöèÿ ϕ ðåàëèçóåòñÿ àâòîìàòîì A, òî ôóíêöèÿ ϕā , êàêëåãêî âèäåòü, ðåàëèçóåòñÿ àâòîìàòîì (A, B, Q, f, g, qj ), ãäå qj òî ñîñòîÿíèå àâòîìàòà A, â êîòîðîå îí ïåðåõîäèò èç ñîñòîÿíèÿ q1 ïîä äåéñòâèåìâõîäíîãî ñëîâà ā.
Èç ýòîãî ðàçúÿñíåíèÿ ñðàçó ñëåäóåò, ÷òî äëÿ êîíå÷íîãîàâòîìàòà A ñ r ñîñòîÿíèÿìè ÷èñëî îñòàòî÷íûõ ôóíêöèé íå ïðåâîñõîäèòr. Òàêèì îáðàçîì, âåñ êîíå÷íî-àâòîìàòíîé ôóíêöèè êîíå÷åí è íå ïðåâîñõîäèò ÷èñëà ñîñòîÿíèé ðåàëèçóþùåãî åå êîíå÷íîãî àâòîìàòà.Îáíàðóæåííóþ ñâÿçü ìåæäó îñòàòî÷íûìè ôóíêöèÿìè è ñîñòîÿíèÿìè êîíå÷íîãî àâòîìàòà ìîæíî ïîëîæèòü â îñíîâó îïðåäåëåíèÿ êîíå÷íîàâòîìàòíîé ôóíêöèè ÷åðåç åå îñòàòî÷íûå ôóíêöèè. Èòàê, ïóñòü äåòåðìèíèðîâàííàÿ ôóíêöèÿ ϕ : A∗ → B ∗ èìååò âåñ r.
Âûøå ìû óñëîâèëèñü49ñ÷èòàòü, ÷òî êîíå÷íî-àâòîìàòíàÿ ôóíêöèÿ ïåðåâîäèò ïóñòîå ñëîâî â ïóñòîå ñëîâî. Ïîýòîìó áóäåì ïðåäïîëàãàòü, ÷òî ϕ(Λ) = Λ.  ýòèõ ïðåäïîëîæåíèÿõ îïðåäåëèì àâòîìàò A = (A, B, Q, f, g, q1 ) ñ r ñîñòîÿíèÿìè,êîòîðûé ðåàëèçóåò ôóíêöèþ ϕ.Ïóñòü äëÿ ôóíêöèè ϕ âñå îñòàòî÷íûå ôóíêöèè ñóòü ϕā1 , . . . ϕār , ãäåñëîâà ā1 , .
. . , ār âûáðàíû, íàïðèìåð, ñ íàèìåíüøèìè âîçìîæíûìè äëèíàìè. Ìîæíî ñ÷èòàòü, ÷òî ā1 = Λ, è, ñëåäîâàòåëüíî, ϕā1 = ϕ. Áóäåìïðåäïîëàãàòü òàêæå, ÷òî ñîñòîÿíèÿ q1 , . . . , qr àâòîìàòà A ñîîòâåòñòâóþòñëîâàì ā1 , . . . , ār (è ôóíêöèÿì ϕā1 , . . . , ϕār ).
Ôóíêöèþ ïåðåõîäîâ f àâòîìàòà A îïðåäåëèì ñëåäóþùèì îáðàçîì: åñëè ai ∈ A, òî f (ai , qj ) = ql ,ãäå ϕāl = ϕāj ai . Èç àíàëîãè÷íûõ ñîîáðàæåíèé îïðåäåëÿåì ôóíêöèþ g :g(ai , qj ) = ϕāj (ai ).Ïðîâåðèì, ÷òî òàê îïðåäåëåííûé àâòîìàò A äåéñòâèòåëüíî ðåàëèçóåòôóíêöèþ ϕ. Âîçüìåì ïðîèçâîëüíîå ñëîâî ā = ai1 . . . ain â àëôàâèòå A.Åñëè â ñîîòíîøåíèè (3.1) ïîëîæèòü ā1 = ai1 , .
. . , ān = ain , òî áóäåì èìåòüϕ(ā) = ϕ(ai1 )ϕai1 (ai2 )ϕai1 ai2 (ai3 ) . . . ϕai1 ...ain−1 (ain ).(3.2)Îäíàêî â ñèëó îïðåäåëåíèÿ àâòîìàòà A èìååìϕ(ai1 ) = ϕā1 (ai1 ) = g(ai1 , q1 ).Äàëåå, ā1 = Λ è ā1 ai1 = ai1 . Ïóñòü ôóíêöèÿ ϕai1 èìååò îáîçíà÷åíèå ϕāj2 .Òîãäàf (ai1 , q1 ) = qj2 ,ϕai1 (ai2 ) = g(ai2 , qj2 ).Âîîáùå, ïðåäïîëîæèì, ÷òî ñëîâà ai1 . . . ais è ai1 . . . ais ais+1 çàäàþò òå æåîñòàòî÷íûå ôóíêöèè, ÷òî è ñëîâà ājs+1 è ājs+2 (íàïîìíèì, ÷òî ñëîâó ai1ó íàñ ñîîòâåòñòâóåò ñëîâî āj2 ).
Òîãäà â ñèëó îïðåäåëåíèÿ ôóíêöèé f, gáóäåì èìåòüf (ais+1 , qjs+1 ) = qjs+2 ,ϕai1 ...ais (ais+1 ) = g(ais+1 , qjs+1 ).Òàêèì îáðàçîì, ïðàâóþ ÷àñòü ðàâåíñòâà (3.2) ìîæíî ïåðåïèñàòü â âèäåg(ai1 , q1 )g(ai2 , qj2 ) . . . g(ain , qjn ),ãäå ñîñòîÿíèÿ qj2 , . . . , qjn àâòîìàòà A ïîëó÷àþòñÿ èç ñîñòîÿíèÿ q1 ïîñëåäîâàòåëüíûì ïðèìåíåíèåì ôóíêöèè ïåðåõîäîâ f . Èíûìè ñëîâàìè, ϕ(ā)åñòü ðåçóëüòàò ïðèìåíåíèÿ àâòîìàòà A ê ñëîâó ā.Ïîäâåäåì èòîã íàøèõ èññëåäîâàíèé â âèäå òåîðåìû.Êëàññ äåòåðìèíèðîâàííûõ ôóíêöèé êîíå÷íîãî âåñàñîâïàäàåò ñ êëàññîì êîíå÷íî-àâòîìàòíûõ ôóíêöèé.Òåîðåìà 3.2.50ÓÏÐÀÆÍÅÍÈßÍàéòè âåñ àâòîìàòíîé ôóíêöèè ϕ, çàäàííîé ñëåäóþùåé äèàãðàììîé Ìóðà:2.0, 1∗q11, 0q41, 01, 10, 10, 0q20, 0q31, 1 3.
Êîíå÷íûå àâòîìàòû íà ñâåðõñëîâàõ ýòîì è â ñëåäóþùèõ äâóõ ïàðàãðàôàõ ìû õîòèì ðàññìîòðåòü êîíå÷íûå àâòîìàòû ñ âûõîäîì, êîòîðûå îïåðèðóþò ñ áåñêîíå÷íûìè ïîñëåäîâàòåëüíîñòÿìè (ñâåðõñëîâàìè). Ïåðåõîä ê ñâåðõñëîâàì ïîçâîëÿåòâçãëÿíóòü íà êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè ñ íîâîé òî÷êè çðåíèÿ, îïðåäåëèòü êîíå÷íî-àâòîìàòíûå ôóíêöèè, áëèçêèå ê íåïðåðûâíûìôóíêöèÿì äåéñòâèòåëüíûõ ïåðåìåííûõ, è óñòàíîâèòü êîíå÷íóþ ïîðîæäàåìîñòü êëàññà êîíå÷íî-àâòîìàòíûõ ôóíêöèé.Ïóñòü A, B êîíå÷íûå àëôàâèòû. Îáîçíà÷èì ÷åðåç A∞ ìíîæåñòâîâñåõ ñ÷åòíî-áåñêîíå÷íûõ ïîñëåäîâàòåëüíîñòåé (ñâåðõñëîâ), óïîðÿäî÷åííûõ ïî òèïó íàòóðàëüíûõ ÷èñåë. Åñëè àëôàâèò A ñîäåðæèò íå ìåíåå äâóõáóêâ, òî ìíîæåñòâî A∞ ñîñòîèò èç êîíòèíóàëüíîãî ÷èñëà ïîñëåäîâàòåëüíîñòåé (ñâåðõñëîâ). Ñâåðõñëîâî a ∈ A∞ áóäåì çàïèñûâàòü â âèäå a =a(1)a(2) .
. ., ãäå a(t) ∈ A ïðè t = 1, 2, . . .. Ïåðåìåííóþ x, ïðèíèìàþùóþçíà÷åíèÿ â ìíîæåñòâå A∞ , òàêæå çàïèñûâàåì â âèäå x = x(1)x(2) . . ., ãäåïåðåìåííàÿ x(t) ïðèíèìàþò çíà÷åíèÿ óæå â ìíîæåñòâå A.Áóäåì ðàññìàòðèâàòü ôóíêöèè f (x1 , . . . , xn ), îòîáðàæàþùèå ìíîæåñòâî (A∞ )n â ìíîæåñòâî B ∞ . Êëàññ âñåõ òàêèõ ôóíêöèé îáîçíà÷èì ÷åðåç∞∞PA,B. Åñëè àëôàâèòû A è B ñîâïàäàþò, òî âìåñòî PA,Bïèøåì PA∞ . Äëÿñòàíäàðòíîãî k -ýëåìåíòíîãî àëôàâèòà A = {0, 1, . . . , k − 1} âìåñòî PA∞∞áóäåì ïèñàòü Pk∞ . Ïî ðÿäó ïðè÷èí ôóíêöèþ f (x1 , . . . , xn ) èç êëàññà PA,B51óäîáíî èçîáðàæàòü ñ âûõîäíîé ïåðåìåííîé: y = f (x1 , .
. . , xn ), ãäå ïåðåìåííàÿ y ïðèíèìàåò çíà÷åíèÿ â ìíîæåñòâå B ∞ .Òàê æå, êàê â 2, ïåðâûì ïðèáëèæåíèåì ê êîíå÷íî-àâòîìàòíûì ôóíêöèÿì íà ñâåðõñëîâàõ áóäóò äåòåðìèíèðîâàííûå ôóíêöèè. Îáîçíà÷èì ÷å∞ðåç X âåêòîð ïåðåìåííûõ x1 , . . . , xn . Ôóíêöèþ y = f (X) èç êëàññà PA,Bíàçîâåì, åñëè äëÿ ëþáûõ äâóõ âåêòîð-ñâåðõñëîâ a, bèç (A∞ )n è ëþáîãî t > 1 èç ñîîòíîøåíèéäåòåðìèíèðîâàííîéc = f (a),d = f (b),a(1) = b(1), .
. . , a(t) = b(t)ñëåäóþò ñîîòíîøåíèÿc(1) = d(1), . . . , c(t) = d(t).Èíûìè ñëîâàìè, ïðè ëþáîì t çíà÷åíèå y(t) çàâèñèò òîëüêî îò çíà÷åíèéX(1), . . . , X(t). Êëàññ âñåõ äåòåðìèíèðîâàííûõ ôóíêöèé èç Pk∞ îáîçíà÷èì ÷åðåç P ,k .Íåòðóäíî çàìåòèòü, ÷òî ââåäåííîå ïîíÿòèå äåòåðìèíèðîâàííîé ôóíêöèè òåñíî ñâÿçàíî ñ ïîíÿòèåì äåòåðìèíèðîâàííîé ôóíêöèè èç 2. Òàê,íàïðèìåð, åñëè f (x) äåòåðìèíèðîâàííàÿ ôóíêöèÿ èç 2, òî íà åå îñíîâå ëåãêî ñîçäàòü äåòåðìèíèðîâàííóþ ôóíêöèþ òèïà A∞ → B ∞ , åñëèäëÿ êàæäîãî ñâåðõñëîâà a èç A∞ ïîñëåäîâàòåëüíî âû÷èñëÿòü çíà÷åíèÿôóíêöèè f íà íà÷àëàõ ā ñëîâà a.
Îáðàòíî, åñëè f (x) äåòåðìèíèðîâàííàÿ ôóíêöèÿ òèïà A∞ → B ∞ , òî çíà÷åíèå ôóíêöèè f íà ñâåðõñëîâåa ìîæíî åñòåñòâåííûì îáðàçîì èíòåðïðåòèðîâàòü êàê çíà÷åíèÿ äåòåðìèíèðîâàííîé ôóíêöèè òèïà A∗ → B ∗ íà âñåõ íà÷àëàõ äàííîãî ñâåðõñëîâà a.Èç îïðåäåëåíèÿ êëàññà P ,k íåòðóäíî âûâåñòè, ÷òî ïðîèçâîëüíàÿ ôóíêöèÿ f (x1 , . . . , xn ) èç P ,k ïîëíîñòüþ îïðåäåëÿåòñÿ ïîñëåäîâàòåëüíîñòüþ{F1 , F2 , . . .} ôóíêöèé k -çíà÷íîé ëîãèêè, ãäåäääF1 = F1 (x1 (1), . .
. , xn (1)), F2 = F2 (x1 (1), . . . , xn (1), x1 (2), . . . , xn (2)), . . .. . . , Ft = Ft (x1 (1), . . . , xn (1), . . . , x1 (t), . . . , xn (t)), . . . .Îòñþäà ñðàçó ñëåäóåò, ÷òî ïðè ëþáîì k > 2 è ëþáîì n > 1 ÷èñëî âñåõn-ìåñòíûõ ôóíêöèé êëàññà P ,k êîíòèíóàëüíî.Ðàññìîòðèì íåñêîëüêî ïðèìåðîâ äåòåðìèíèðîâàííûõ ôóíêöèé èç êëàññà P ,k .à) Ïóñòü ϕ(x1 , . . . , xn ) ïðîèçâîëüíàÿ ôóíêöèÿ k -çíà÷íîé ëîãèêè.Îïðåäåëèì äåòåðìèíèðîâàííóþ ôóíêöèþ y = fϕ (x1 , . . . , x) ðàâåíñòâàìèääy(t) = ϕ(x1 (t), .
. . , xn (t)),52t = 1, 2, . . . .èñòèííîñòíûõÔóíêöèè âèäà fϕ íîñÿò íàçâàíèåôóíêöèé.á) Çàäàäèì ôóíêöèþ y = ç(x) ñëåäóþùèìè ðàâåíñòâàìè:y(1) = 0,Ôóíêöèÿ ç(x) íàçûâàåòñÿòàêò.y(t) = x(t − 1) ïðè t > 2.åäèíè÷íîé çàäåðæêîé èëè çàäåðæêîé íà îäèíâ) Ñëîæåíèå äâóõ ÷èñåë, çàäàííûõ â k -è÷íîé ñèñòåìå ñ÷èñëåíèÿ.Ðàññìîòðèì ôóíêöèþ z = x + y , ãäå k -è÷íûå ïîñëåäîâàòåëüíîñòèx, y ñêëàäûâàþòñÿ ïî îáû÷íûì ïðàâèëàì ñëîæåíèÿ ÷èñåë, çàïèñàííûõâ k -è÷íîé ñèñòåìå ñ÷èñëåíèÿ. Òàê, z(1) = x(1) + y(1) (mod k), z(2) =x(2)+y(2)+q(2) (mod k), ãäå q(2) ¾ïåðåíîñ¿ âî âòîðîé ðàçðÿä: q(2) = 0,åñëè x(1) + y(1) < k , è q(2) = 1, åñëè x(1) + y(1) > k , è ò.ä.
Ïîíÿòíî,÷òî ðàçðÿä z(t) çàâèñèò òîëüêî îò ðàçðÿäîâ x(s), y(s), ãäå s = 1, 2, . . . , t.ã) Ïî àíàëîãèè ñî ñëîæåíèåì ðàññìîòðèì ôóíêöèþ âîçâåäåíèÿ â êâàäðàò: y = x2 . Èñïîëüçóÿ ¾øêîëüíûé¿ àëãîðèòì óìíîæåíèÿ, ëåãêî óáåäèòüñÿ, ÷òî äëÿ ôóíêöèè y = x2 ðàçðÿä y(t) çàâèñèò òîëüêî îò ðàçðÿäîâx(1), . . . , x(t).Äàëåå ìû áóäåì ðàññìàòðèâàòü äåòåðìèíèðîâàííûå ôóíêöèè òîëüêîèç êëàññà P ,k . Ïóñòü f (x1 , . . . , xn ) ∈ P ,k è ā1 = a1 (1) . . . a1 (l), .
. . , ān =an (1) . . . an (l) ïðîèçâîëüíûå ñëîâà äëèíû l â àëôàâèòå Ek . Îïðåäåëèìy = fā1 ...ān (x1 , . . . , xn ), îòâå÷àþùóþ ñëîâàìā1 , . . . , ān , ïîëàãàÿ y(t) ðàâíûì (l + t)-ó ðàçðÿäó âûõîäíîé ïîñëåäîâàòåëüíîñòè ôóíêöèè f (ā1 x1 , . . . , ān xn ), ãäå ïîä āi xi ïîíèìàåòñÿ ïîñëåäîâàòåëüíîñòü ai (1) . . . ai (l)xi (1)xi (2) . . . .Ìîæíî ñêàçàòü, ÷òî â ïîñëåäîâàòåëüíîñòè āi xi ïîäïîñëåäîâàòåëüíîñòüxi ¾çàäåðæàíà¿ íà l òàêòîâ, à ïåðâûå åå l ïîçèöèé çàíÿòû ñëîâîì āi . Ñîîòâåòñòâåííî, äëÿ îïðåäåëåíèÿ âûõîäíîé ïîñëåäîâàòåëüíîñòè ôóíêöèèfā1 ...ān (x1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
