С.С. Марченков - Избранные главы дискретной математики (1124120), страница 4
Текст из файла (страница 4)
Óìíîæàÿ îáå ÷àñòè ýòîãî ðàâåíñòâà íàb2 , ïðèõîäèì ê ðàâåíñòâó b2 = 0, ÷òî íåâîçìîæíî ïî ïðåäïîëîæåíèþ.Çíà÷èò, ôóíêöèþ j0 íåëüçÿ ðåàëèçîâàòü ïîëèíîìîì íàä êîëüöîì R, èòåîðåìà äîêàçàíà.Ïóñòü R êîëüöî âû÷åòîâ ïî ìîäóëþ k. Òîãäà ñèñòåìàâñåõ ïîëèíîìîâ íàä êîëüöîì R ïîëíà â êëàññå Pk â òîì è òîëüêî òîìñëó÷àå, êîãäà k ïðîñòîå ÷èñëî.ÑëåäñòâèåÓÏÐÀÆÍÅÍÈßÄîêàçàòü, ÷òî ïðè ëþáîì k > 3 ñèñòåìà ôóíêöèé, ïîëó÷åííàÿ èçñèñòåìû (1.4) óäàëåíèåì ôóíêöèé 0, k − 1, J0 , Jk−1 , ïîëíà â êëàññå Pk .· y:3. Îïðåäåëèì ôóíêöèþ x −2.x −· y =x − y, åñëè x > y,0â ïðîòèâíîì ñëó÷àå.· y} ïîëíà â êëàññå P .Äîêàçàòü, ÷òî ïðè ëþáîì k > 2 ñèñòåìà {x̄, x −k4. Äîêàçàòü, ÷òî ïðè ëþáîì k > 2 ñèñòåìà ôóíêöèé {x̄, min(x, y)}ïîëíà â êëàññå Pk .5.
Äîêàçàòü, ÷òî ïðè ëþáîì i ∈ Ek ñèñòåìà ôóíêöèé {1, Ji (x), x +y (mod k)} ïîëíà â Pk .6. Äîêàçàòü, ÷òî ïðè ëþáîì k > 2 ñèñòåìà ôóíêöèé {0, . . . , k −1, J0 , . . . , Jk−1 , max, x · y} ïîëíà â Pk .(1)7. Äîêàçàòü, ÷òî ïðè ëþáîì k > 2 ñèñòåìà ôóíêöèé Pk∪ {x · y}ïîëíà â Pk . 3. Àëãîðèòì ðàñïîçíàâàíèÿ ôóíêöèîíàëüíîé ïîëíîòûàëãîðèòìè÷åñêóþ ïðîáëåìóÑôîðìóëèðóåì ñëåäóþùóþ: ìîæíî ëè ïîïðîèçâîëüíîé êîíå÷íîé ñèñòåìå ôóíêöèé èç Pk óñòàíîâèòü, ÿâëÿåòñÿ ëèäàííàÿ ñèñòåìà ôóíêöèé ïîëíîé â Pk ? Ìû ïðåäïîëàãàåì, ÷òî ôóíêöèèçàäàþòñÿ îäíèì èç ñòàíäàðòíûõ ñïîñîáîâ: ëèáî òàáëè÷íî, ëèáî â âèäåôîðìóë íàä èçâåñòíîé ïîëíîé ñèñòåìîé ôóíêöèé. Òîãäà íàøó ïðîáëåìó ìîæíî óòî÷íèòü ñëåäóþùèì îáðàçîì: ñóùåñòâóåò ëè, íàâõîä êîòîðîãî ïîñòóïàåò ïðîèçâîëüíàÿ êîíå÷íàÿ ñèñòåìà ôóíêöèé èç Pk(ò.å. ñèñòåìà ôîðìàëèçîâàííûõ ïðåäñòàâëåíèé ýòèõ ôóíêöèé) è êîòîðûéàëãîðèòì16äàåò îòâåò ¾äà¿ èëè ¾íåò¿ â çàâèñèìîñòè îò ïîëíîòû èëè íåïîëíîòû ðàññìàòðèâàåìîé ñèñòåìû ôóíêöèé.
Ïîëîæèòåëüíûé îòâåò íà ýòîò âîïðîñáûë ïîëó÷åí Ñ.Â. ßáëîíñêèì [?, ?].  òåîðåìå 1.4 èçëàãàåòñÿ íåñêîëüêîîáîáùåííàÿ âåðñèÿ àëãîðèòìà Ñ.Â. ßáëîíñêîãî.Ñóùåñòâóåò àëãîðèòì, êîòîðûé ïî ïðîèçâîëüíîé êîíå÷íîé ñèñòåìå Q ôóíêöèé èç Pk è ôóíêöèè f èç Pk äàåò îòâåò íàâîïðîñ, ïðèíàäëåæèò ëè ôóíêöèÿ f ìíîæåñòâó [Q].Òåîðåìà 1.4.Ïóñòü çàäàíû êîíå÷íàÿ ñèñòåìà Q = {f1 , . .
. , fs }ôóíêöèé èç Pk è ôóíêöèÿ f ∈ Pk .  öåëÿõ óïðîùåíèÿ ðàññóæäåíèéìîæíî ñ÷èòàòü, ÷òî âñå ôóíêöèè f1 , . . . , fs , f çàâèñÿò îò m ïåðåìåííûõ.Ïî èíäóêöèè îïðåäåëèì ìîíîòîííî íåóáûâàþùóþ (ïî âêëþ÷åíèþ) ïîñëåäîâàòåëüíîñòüÄîêàçàòåëüñòâî.H0 , H1 , . . . , Hr , . . .(1.8)ìíîæåñòâ ôóíêöèé îò ïåðåìåííûõ x1 , .
. . , xm .Ïîëîæèì H0 = ∅. Ïóñòü óæå îïðåäåëåíû ìíîæåñòâà H0 , H1 , . . . , Hr .Äëÿ ëþáîãî i (1 6 i 6 s) ðàññìîòðèì âñåâîçìîæíûå ôîðìóëû âèäàfi (h1 (x1 , x2 , . . . , xm ), . . . , hm (x1 , x2 , . . . , xm )),ãäå ôóíêöèè h1 , . . . , hm ïðèíàäëåæàò ìíîæåñòâómHr ∪ {em1 (x1 , x2 , . . . , xm ), . . . , em (x1 , x2 , . . . , xm )}m(ñåëåêòîðíûå ôóíêöèè em1 , . . . , em çäåñü âûáðàíû ëèøü äëÿ òîãî, ÷òîáûíà êàæäîì øàãå ïîñòðîåíèÿ èñïîëüçîâàòü ôóíêöèè îò m ïåðåìåííûõ; íàñàìîì äåëå âìåñòî ñåëåêòîðíûõ ôóíêöèé ìîæíî ïîäñòàâëÿòü â ôóíêöèèfi ñîîòâåòñòâóþùèå ïåðåìåííûå).
Îáðàçóåì ìíîæåñòâî Hr+1 , äîáàâëÿÿ êìíîæåñòâó Hr âñå ôóíêöèè, ðåàëèçóåìûå óêàçàííûìè ôîðìóëàìè.Î÷åâèäíî, ÷òî ïîñëåäîâàòåëüíîñòü (1.8) ìîíîòîííî íå óáûâàåò. Êðîìå òîãî, èç ïîñòðîåíèÿ íåïîñðåäñòâåííî âèäíî, ÷òî åñëè Hr+1 = Hr , òîHr+2 = Hr+1 (åñëè â êîíñòðóêöèè ìíîæåñòâî Hr çàìåíèòü ðàâíûì åìóìíîæåñòâîì Hr+1 , òî ïîëó÷èì èíîæåñòâî Hr+2 , êîòîðîå áóäåò ðàâíî ìíîæåñòâó Hr+1 ) è, ñëåäîâàòåëüíî, öåïî÷êà ìíîæåñòâ ñòàáèëèçèðóåòñÿ:Hr = Hr+1 = Hr+2 = . . .m êàæäîì èç ìíîæåñòâ Hr íå áîëåå k k ôóíêöèé. Ïîýòîìó, ïðîñìàòðèâàÿ ìíîæåñòâà öåïî÷êè (1.8) è ñðàâíèâàÿ äâà ñîñåäíèõ ìíîæåñòâà, ìûmíå áîëåå ÷åì ÷åðåç k k øàãîâ îáíàðóæèì íàèìåíüøèé íîìåð r0 , íà÷èíàÿ17ñ êîòîðîãî íàñòóïàåò ñòàáèëèçàöèÿ. Î÷åâèäíî, ÷òî ïðîöåññ îïðåäåëåíèÿ÷èñëà r0 ÿâëÿåòñÿ ïîëíîñòüþ ýôôåêòèâíûì.Èòàê, ìû ïîëó÷èëè ñòðîãî âîçðàñòàþùóþ öåïî÷êó ìíîæåñòâH0 ⊂ H1 ⊂ .
. . ⊂ Hr0 .Ðàññìîòðèì ïîñëåäíåå ìíîæåñòâî Hr0 ýòîé öåïî÷êè. Âîçìîæíû äâà ñëó÷àÿ.1. Ôóíêöèÿ f ïðèíàäëåæèò ìíîæåñòâó Hr0 .mÎ÷åâèäíî, ÷òî â ýòîì ñëó÷àå f ∈ [Q] (ôóíêöèè em1 , . . . , em , èñïîëüçóåìûå â ïîñòðîåíèè, êàê îòìå÷àëîñü âûøå, ìîæíî çàìåíèòü ñîîòâåòñòâóþùèìè ïåðåìåííûìè).2. Ôóíêöèÿ f íå ïðèíàäëåæèò ìíîæåñòâó Hr0 .Çäåñü íåîáõîäèìî ïðîâåñòè äîïîëíèòåëüíûå ðàññóæäåíèÿ, ÷òîáû ïîêàçàòü, ÷òî f ∈/ [Q]. Èìåííî, åñëè áû âûïîëíÿëîñü âêëþ÷åíèå f ∈ [Q],òî ôóíêöèþ f ìîæíî áûëî áû ïðåäñòàâèòü â âèäåf (x1 , .
. . , xm ) = fi (Φ1 (x1 , . . . , xm ), . . . , Φm (x1 , . . . , xm )),(1.9)ãäå 1 6 i 6 s, à êàæäîå âûðàæåíèå Φ1 , . . . , Φm åñòü ëèáî ôîðìóëà íàäQ, ëèáî ñèìâîë ïåðåìåííîé èç ÷èñëà x1 , . . . , xm .Ïðîäîëæàÿ äàëåå àíàëèçèðîâàòü âûðàæåíèÿ Φ1 , . . . , Φm , îòëè÷íûå îòñèìâîëîâ ïåðåìåííûõ, ïðèäåì ê ¾ñàìûì ïðîñòûì¿ ïîäôîðìóëàì èç ïðàâîé ÷àñòè ôîðìóëû (1.9), êîòîðûå èìåþò âèäfj (xj1 , .
. . , xjm ),(1.10)ãäå j1 , . . . , jm ∈ {1, 2, . . . , m}. Ôîðìóëà (1.10), î÷åâèäíî, ðåàëèçóåò òó æåôóíêöèþ, ÷òî è ôîðìóëàmfj (emj1 (x1 , . . . , xm ), . . . , ejm (x1 , . . . , xm )).Ïîñëåäíÿÿ ôóíêöèÿ ïî îïðåäåëåíèþ âõîäèò â ìíîæåñòâî H1 . Èç ôîðìóëâèäà (1.10) è ñèìâîëîâ ïåðåìåííûõ â ôîðìóëå (1.9) ñîñòàâëåíû ïîäôîðìóëû ñëåäóþùåãî óðîâíÿ ñëîæíîñòè:fl (Ψ1 (x1 , . . . , xm ), . . . , Ψm (x1 , . . .
, xm )),(1.11)ãäå Ψ1 , . . . , Ψm ëèáî ôîðìóëû âèäà (1.10), ëèáî ñèìâîëû ïåðåìåííûõ.Ïîíÿòíî, ÷òî ôîðìóëû (1.11) ðåàëèçóþò ôóíêöèè èç ìíîæåñòâà H2 èò.ä.  èòîãå ïðèõîäèì ê âûâîäó, ÷òî ìíîæåñòâî Hr0 ñîñòîèò â òî÷íîñòè èç âñåõ ôóíêöèé çàìûêàíèÿ [Q], êîòîðûå çàâèñÿò îò ïåðåìåííûõ18x1 , . . . , xm . Ïîýòîìó íåâõîæäåíèå ôóíêöèè f â ìíîæåñòâî Hr0 ðàâíîñèëüíî åå íåâõîæäåíèþ â ìíîæåñòâî [Q].Èòàê, èñêîìûé àëãîðèòì ðàñïîçíàâàíèÿ ïðèíàäëåæíîñòè ôóíêöèè fìíîæåñòâó [Q] ñîñòîèò â ïîñòðîåíèè âîçðàñòàþùåé öåïî÷êè ìíîæåñòâH0 , H1 , . .
. äî ìîìåíòà r0 åå ñòàáèëèçàöèè è ïðîâåðêå âûïîëíèìîñòè âêëþ÷åíèÿ f ∈ Hr0 . Òåîðåìà äîêàçàíà.Ñóùåñòâóåò àëãîðèòì, êîòîðûé ðàñïîçíàåò ïîëíîòóêîíå÷íûõ ñèñòåì ôóíêöèé â Pk .Ñëåäñòâèå.Äîñòàòî÷íî, íàïðèìåð, â êà÷åñòâå ôóíêöèè f ðàññìîòðåòü ôóíêöèþ Âåááà V (x1 , x2 ).Äîêàçàòåëüñòâî.ÓÏÐÀÆÍÅÍÈßÊàê ìîæåò âûãëÿäåòü àëãîðèòì ðàñïîçíàâàíèÿ ïîëíîòû êîíå÷íûõñèñòåì ôóíêöèé â Pk , êîòîðûå çàâåäîìî ñîäåðæàò êàêóþ-ëèáî èç ôóíê· y?öèé max, min, x + y, x · y, x −8. 4. Òåîðåìà Êóçíåöîâà î ôóíêöèîíàëüíîé ïîëíîòåÀëãîðèòì ðàñïîçíàâàíèÿ ïîëíîòû êîíå÷íûõ ñèñòåì ôóíêöèé, èçëîæåííûé â ïðåäûäóùåì ïàðàãðàôå, òðåáóåò áîëüøîãî îáúåìà âû÷èñëåíèé è ïî ýòîé ïðè÷èíå íà ïðàêòèêå èñïîëüçóåòñÿ êðàéíå ðåäêî. Àëüòåðíàòèâîé ýòîìó ïîäõîäó ñëóæèò ïîäõîä, îñíîâàííûé íà íàõîæäåíèèêîíå÷íîãî ÷èñëà ¾ñâîéñòâ¿, êîòîðûå èñ÷åðïûâàþùèì îáðàçîì õàðàêòåðèçóþò ïîëíûå ñèñòåìû.
Êàê îáíàðóæèëîñü, òàêèìè ñâîéñòâàìè ìîãóòáûòü ñâîéñòâà ïðèíàäëåæíîñòè ñèñòåì çàìêíóòûì êëàññà îïðåäåëåííîãîâèäà. Âïåðâûå ýòîò ïîäõîä áûë ïðåäëîæåí À.Â. Êóçíåöîâûì [?].Ïðåæäå ÷åì ñôîðìóëèðîâàòü è äîêàçàòü òåîðåìó Êóçíåöîâà, ââåäåìíåîáõîäèìûå îïðåäåëåíèÿ è äîêàæåì äâå ëåììû. ÏóñòüG = {g1 (y1 , . . . , yp ), . . . , gr (y1 , . . . , yp )}−êîíå÷íàÿ ñèñòåìà ôóíêöèé èç Pk . Ãîâîðÿò, ÷òî ôóíêöèÿ f (x1 , .
. . , xn )èç Pk, åñëè äëÿ ëþáûõ i1 , . . . , in èç{1, 2, . . . , r} âûïîëíÿåòñÿ ñîîòíîøåíèåñîõðàíÿåò ìíîæåñòâî ôóíêöèé Gf (gi1 (y1 , . . . , yp ), . . . , gin (y1 , . . . , yp )) ∈ G.Ïóñòü F ìíîæåñòâî âñåõ ôóíêöèé èç Pk , êîòîðûåñîõðàíÿþò ìíîæåñòâî ôóíêöèé G. Òîãäà F ÿâëÿåòñÿ çàìêíóòûì êëàññîì, ñîäåðæàùèì âñå ñåëåêòîðíûå ôóíêöèè.Ëåììà 1.1.19Ïðèíàäëåæíîñòü ñåëåêòîðíûõ ôóíêöèé ìíîæåñòâóF ëåãêî ñëåäóåò èç îïðåäåëåíèé. Ïîýòîìó äëÿ äîêàçàòåëüñòâà çàìêíóòîñòè ìíîæåñòâà F äîñòàòî÷íî óáåäèòüñÿ â â òîì, ÷òî èç ïðèíàäëåæíîñòèôóíêöèé f0 , f1 , . .
. , fm ìíîæåñòâó F âûòåêàåò ïðèíàäëåæíîñòü ìíîæåñòâó F ôóíêöèè h, ãäåÄîêàçàòåëüñòâî.h(x1 , . . . , xn ) = f0 (f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn )).Èç âêëþ÷åíèÿ {f1 , . . . , fm } ⊆ F ñëåäóåò, ÷òî äëÿ ëþáûõ i1 , . . . , in èç{1, 2, . . . , r} ôóíêöèèh1 (y1 , . . .
, yp ) = f1 (gi1 (y1 , . . . , yp ), . . . , gin (y1 , . . . , yp )),........................hm (y1 , . . . , yp ) = fm (gi1 (y1 , . . . , yp ), . . . , gin (y1 , . . . , yp ))âõîäÿò â ìíîæåñòâî G. Çíà÷èò, â ìíîæåñòâî G áóäåò âõîäèòü ôóíêöèÿhm (gi1 (y1 , . . . , yp ), . . . , gin (y1 , . . . , yp )) = f0 (h1 (y1 , . . . , yp ), . . . , hm (y1 , . .
. , yp )).Ëåììà äîêàçàíà.Ïóñòü ìíîæåñòâî G ñîäåðæèò ôóíêöèè ep1, . . . , epp, G =[G](p) , à F åñòü ìíîæåñòâî âñåõ ôóíêöèé èç Pk , ñîõðàíÿþùèõ ìíîæåñòâî ôóíêöèé G. Òîãäà F (p) = G.Ëåììà 1.2.Äîêàçàòåëüñòâî.(p)[G]= G ôóíêöèÿÏóñòü gj , gi1 , . . . , gip ∈ G. Òîãäà â ñèëó óñëîâèÿgj (gi1 (y1 , . . . , yp ), . . . , gip (y1 , . . . , yp ))ïðèíàäëåæèò ìíîæåñòâó G. Îòñþäà ñëåäóåò, ÷òî gj ∈ F .pÎáðàòíî, åñëè f ∈ F (p) , òî èç óñëîâèÿ {e1 , . . . , epp } ⊆ G è ðàâåíñòâàf (ep1 (y1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
