С.С. Марченков - Избранные главы дискретной математики (1124120), страница 27
Текст из файла (страница 27)
, xi−1 , 1, xi+1 . . . , xn ) ⊕ 1) = 0.3. Ìîæíî ïðîâåðèòü çíà÷åíèÿ ôóíêöèè íà âñåõ ïàðàõ ïðîòèâîïîëîæíûõíàáîðîâ.14. 2. Ïóñòü f (x1 , . . . , xn ) äàííàÿ ôóíêöèÿ. Äëÿ ïðîâåðêè íåëèíåéíîñòè ôóíêöèè f äîñòàòî÷íî íàéòè òàêèå ÷èñëà i, j (1 6 i < j 6 n) èòàêîé íàáîð çíà÷åíèé ïåðåìåííûõ ôóíêöèè f , îòëè÷íûõ îò xi , xj , ÷òî128ïðè ïîäñòàíîâêå ýòèõ çíà÷åíèé â ÄÍÔ ôóíêöèè f îáðàçóåòñÿ íåëèíåéíàÿ ôóíêöèÿ îò ïåðåìåííûõ xi , xj .15.
13.  êàæäîé èç çàäà÷ íåäåòåðìèíèðîâàííî ïîðîæäàåòñÿ òðåáóåìîå ìíîæåñòâî èëè ôóíêöèÿ, à çàòåì äåòåðìèíèðîâàííî è çà ïîëèíîìèàëüíîå âðåìÿ ïðîâåðÿåòñÿ ñîîòâåòñòâèå íàéäåííîãî îáúåêòà èìåþùèìñÿóñëîâèÿì.16. 1. Ïîêàæåì, ÷òî çàäà÷à ÂÛÏ P-ñâîäèòñÿ ê çàäà÷å ÊËÈÊÀ. ÏóñòüK = D1 & D2 & . . . &Ds ÊÍÔ ñ äèçúþíêòàìè Di = ti1 ∨ ti2 ∨ . . . ∨timi . Îáðàçóåì ãðàô G = (V, E). Êàæäîìó ëèòåðàëó tij èç K ñîïîñòàâèìâåðøèíó vij ìíîæåñòâà V . Äàëåå ïîëàãàåì(vi1 j1 , vi2 j2 ) ∈ E ⇔ i1 6= j1 è ti2 j2 6= t̄i1 j1 .Òîãäà ÊÍÔ K áóäåò âûïîëíèìîé â òîì è òîëüêî òîì ñëó÷àå, êîãäà âãðàôå G èìååòñÿ êëèêà ñ s âåðøèíàìè.
Ïðè ýòîì î÷åâèäíî, ÷òî ãðàô Gýôôåêòèâíî ñòðîèòñÿ ïî ÊÍÔ K çà ïîëèíîìèàëüíîå âðåìÿ.2. Óñòàíîâèì P-ñâîäèìîñòü çàäà÷è ÊËÈÊÀ ê çàäà÷å ÂÅÐØÈÍÍÎÅ ÏÎÊÐÛÒÈÅ. Ïóñòü G = (V, E) ãðàô, n = |V | è k íàòóðàëüíîå ÷èñëî.Ðàññìîòðèì ãðàô Ḡ = (V, E 0 ) äîïîëíåíèå ãðàôà G, ãäå ïðè u 6= vèìååì (u, v) ∈ E 0 ⇔ (u, v) ∈/ E. Òîãäà ãðàô G ñîäåðæèò êëèêó ñ kâåðøèíàìè â òîì è òîëüêî òîì ñëó÷àå, êîãäà ãðàô Ḡ èìååò âåðøèííîåïîêðûòèå ñ n − k âåðøèíàìè.17. 1. Ñíà÷àëà çàìåòèì, ÷òî NP-ïîëíîé ÿâëÿåòñÿ çàäà÷à î ñóùåñòâîâàíèè îäíîãî íàáîðà, íà êîòîðîì ÄÍÔ îáðàùàåòñÿ â íóëü.
 ñàìîì äåëå,åñëè K ÊÍÔ, òî K̄ ëåãêî ïðèâîäèòñÿ ê ÄÍÔ D òîãî æå ðàçìåðà. Ïðèýòîì K âûïîëíèìà â òîì è òîëüêî òîì ñëó÷àå, êîãäà ÄÍÔ D îáðàùàåòñÿ â íóëü íà íåêîòîðîì íàáîðå. Ïåðåõîäÿ ê äâóì ïðîòèâîïîëîæíûìíàáîðàì, ïðåäïîëîæèì, ÷òî çàäàíà ÄÍÔ D îò ïåðåìåííûõ x1 , . . . , xn èïåðåìåííûå t, y1 , .
. . , yn îòëè÷íû îò ïåðåìåííûõ x1 , . . . , xn . Ïóñòü ÄÍÔD1 ïîëó÷åíà èç ÄÍÔ D çàìåíîé êàæäîãî ëèòåðàëà x̄i ïåðåìåííîé yi èD0 = t & D1 ∨ x1 & y1 ∨ . . . ∨ xn & yn . Òîãäà ÄÍÔ D îáðàùàåòñÿ â íóëüâ òîì òîëüêî òîì ñëó÷àå, êîãäà ÄÍÔ D0 îáðàùàåòñÿ â íóëü íà ïàðå ïðîòèâîïîëîæíûõ íàáîðîâ.2. Ïóñòü D ÄÍÔ ôóíêöèè, íå ðàâíîé òîæäåñòâåííî íóëþ, t - ïåðåìåííàÿ, êîòîðàÿ íå âñòðå÷àåòñÿ â D.
Òîãäà ÄÍÔ D îáðàùàåòñÿ â íóëü íàíåêîòîðîì íàáîðå â òîì è òîëüêî òîì ñëó÷àå, êîãäà ÄÍÔ ôóíêöèè D & tðåàëèçóåò íåëèíåéíóþ ôóíêöèþ.3. Ïóñòü D è t òàêèå æå, êàê â ïðåäûäóùåé çàäà÷å. Òîãäà ÄÍÔ D îáðàùàåòñÿ â íóëü íà íåêîòîðîì íàáîðå â òîì è òîëüêî òîì ñëó÷àå, êîãäà129ÄÍÔ D ∨ t̄ ðåàëèçóåò íåìîíîòîííóþ ôóíêöèþ.4. Èñïîëüçóåòñÿ êîíñòðóêöèÿ èç çàäà÷è 2.218.
Ôóíêöèþ I2 (x1 , x2 ) ìîæíî, íàïðèìåð, ïîëó÷èòü ïðèìèòèâíîé ðåêóðñèåé è ñóïåðïîçèöèåé èç ôóíêöèé 0, x + 1 è I33 .20. Ìîæíî ñ÷èòàòü, ÷òî d > 1. Ôóíêöèÿ rm(x, d) ïåðèîäè÷åñêàÿ ñïåðèîäîì d. Ëþáàÿ ïåðèîäè÷åñêàÿ ôóíêöèÿ f (x) ñ ïåðèîäîì d ìîæåòáûòü ïîëó÷åíà èç ôóíêöèè rm(x, d) ïîäõîäÿùåé çàìåíîé åå çíà÷åíèé0, 1, .
. . , d − 1 (ñ ïîìîùüþ, íàïðèìåð, óòâåðæäåíèÿ (4.2)).21. Ìîæíî âîñïîëüçîâàòüñÿ íóìåðàöèîííîé ôóíêöèåé c(x, y) (ñì. 9)è îáðàçîâàòü âñïîìîãàòåëüíóþ ôóíêöèþf 0 (x1 , . . . , xn ) = cd+1 (f (x1 , . . . , xn ), . . . , f (x1 , . . . , xn−1 , xn + d)).Ñëåäóåò n ðàç ïðèìåíèòü îïåðàöèþ îðàíè÷åííîãî ñóììèðîâàíèÿê ôóíêöèè sg |P (x1 , . . . , xn ) − Q(x1 , .
. . , xn )|.23. Ïóñòü h(y, z) õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ îòíîøåíèÿ g(z) = y .ÒîãäàXXh(y, i))f (x, y) =(z · sg22.z6xi<z(îïåðàöèÿ i<z îïðåäåëÿåòñÿ òàê æå, êàê è îïåðàöèÿ i6z ).24. Ëåãêî ïîêàçàòü, ÷òî äëÿ âñÿêîãî x ÷èñëî p(x + 1) íå ïðåâîñõîäèòâåëè÷èíû p(x)p(x) . Ïîýòîìó ôóíêöèþ p(x) ìîæíî îïðåäåëèòü ñëåäóþùåéïðèìèòèâíîé ðåêóðñèåé:PP p(0) = 2,p(x + 1) = íàèìåíüøåìó z, òàêîìó, ÷òî p(x) < z 6 p(x)p(x)è Pr(z) èñòèííî.Î÷åâèäíî, ÷òî f (0) = 4. Äàëåå, f (x + 1) ðàâíî òàêîìó (åäèíñòâåííîìó) ÷èñëó a (0 6 a 6 9), ÷òî25.2f (x)af (0)+ . .
. + x+1 + x+2<21+101010è2f (0)f (x)a+11++ . . . + x+1 + x+2> 2.101010Ýòè äâà ñîîòíîøåíèÿ ìîæíî ïåðåïèñàòü â âèäå(10x+2 + f (0) · 10x+1 + . . . + f (x) · 10 + a)2 < 2 · 102(x+2) ,(10x+2 + f (0) · 10x+1 + . . . + f (x) · 10 + a + 1)2 > 2 · 102(x+2) .130Îòñþäà íåòðóäíî óæå ïîëó÷èòü ñõåìó ïðèìèòèâíîé ðåêóðñèè, îïðåäåëÿþùóþ ôóíêöèþ f (x).26. Åñëè g(0, .
. . , 0) = a, òî äëÿ ôóíêöèè f , ïîëó÷åííîé ñîãëàñíî (4.6),èìååì f (0, . . . , 0, a) = 0.27.(µz)(x + z = y) =y − x,åñëè y > x,íå îïðåäåëåíî, åñëè y < x,åñëè y = 0, 0,y/x,åñëè y 6= 0 è y äåëèòñÿ íàöåëî íà x,(µz)(x · z = y) =íå îïðåäåëåíî â îñòàëüíûõ ñëó÷àÿõ,x − y,åñëè x > y,(µz)(x − z = y) =íå îïðåäåëåíî, åñëè x < y,y,åñëè x = 0,(µz)(z − x = y) =íå îïðåäåëåíî, åñëè x 6= 0,(µz)(x/z = y) åñòü íèãäå íå îïðåäåëåííàÿ ôóíêöèÿ,xy,åñëè x 6= 0,(µz)(z/x = y) =íå îïðåäåëåíî, åñëè x = 0.28.29.g1 (x, y) = |x − y|, g2 (x, y) = [x/y] ïðè óñëîâèè, ÷òî [x/0] = 0.Îïðåäåëèì ïðèìèòèâíî ðåêóðñèâíóþ ôóíêöèÿ g(x):g(x) = a1 · sg |x − 1| + . . .
+ as · sg |x − s| + a1 · sg |x − 1| · . . . · sg |x − s|.Îíà ïðèíèìàåò ëèøü çíà÷åíèÿ a1 , . . . , as . Èìååìf (x) = sg((µy)(g(y) = x) + 1).30.31.Èìååì g(x) = sg((µy)(l1 (x, y) = 1) + 1).Ðàñïîëîæèì âñå ïàðû ÷èñåë èç N â ñëåäóþùåì ïîðÿäêå:(0, 0); (0, 1), (1, 0); (0, 2), (1, 1), (2, 0); (0, 3), . . .Ñîîòâåòñòâóþùàÿ ýòîìó ïîðÿäêó íóìåðóþùàÿ ôóíêöèÿ åñòü(x + y)(x + y + 1) (x + y)2 + 3x + yx+=.22¾Îáðàòíûå¿ ôóíêöèè l(v) è r(v) îïðåäåëÿþòñÿ ôîðìóëàìè√ √· 11[8v+1]+1[8v+1]−l(v) = v −·,222131√[ 8v + 1] + 1 ·− (l(v) + 1).r(v) =232. Ïóñòü f (x1 , . . . , xn ) ïðèìèòèâíî ðåêóðñèâíàÿ ôóíêöèÿ, êîòîðàÿâû÷èñëèìà íà ìàøèíå Òüþðèíãà çà ïîëèíîìèàëüíîå âðåìÿ (ïðè äâîè÷íîì êîäèðîâàíèè àðãóìåíòîâ).
Òîãäà îíà, êîíå÷íî, áóäåò âû÷èñëèìà íàïîäõîäÿùåé ìàøèíå Òüþðèíãà M çà ïîëèíîìèàëüíîå âðåìÿ p(x1 , . . . , xn )ïðè êîäèðîâàíèè àðãóìåíòîâ îñíîâíûì êîäîì. Ñëåäîâàòåëüíî, ïðèìèòèâíî ðåêóðñèâíàÿ ôóíêöèÿ Code(x1 , . . . , xn , p(x1 , . . . , xn )) äàñò êîä çàêëþ÷èòåëüíîé êîíôèãóðàöèè ìàøèíû Òüþðèíãà M. Äàëåå, êàê â äîêàçàòåëüñòâå òåîðåìû 4.6, ïðèìèòèâíî ðåêóðñèâíûì îáðàçîì ¾èçâëåêàåì¿èç ýòîãî êîäà çíà÷åíèå ôóíêöèè f .
Òàêàÿ æå èäåÿ ïðèìåíèìà ïðè ðàññìîòðåíèè îòíîøåíèé èç êëàññà NP.33. Ïóñòü ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ f (x1 , . . . , xn ) ïåðå÷èñëÿåòíåïóñòîå ìíîæåñòâî ÷èñåë è a íåêîòîðûé ýëåìåíò ýòîãî ìíîæåñòâà.Òîãäà (ñì. ïðåäñòàâëåíèå Êëèíè â òåîðåìå 4.6) ýòî ìíîæåñòâî ïåðå÷èñëèìî ïðèìèòèâíî ðåêóðñèâíîé ôóíêöèåé f 0 (x1 , . . . , xn , y), îïðåäåëÿåìîéñëåäóþùèìè ðàâåíñòâàìè:G(x1 , . .
. , xn , y), åñëè Hf (x1 , . . . , xn , y) = 0,0f (x1 , . . . , xn , y) =aâ ïðîòèâíîì ñëó÷àå.Ñïèñîê ëèòåðàòóðû[1] Àëåêñååâ Â.Á. Ëåêöèè ïî äèñêðåòíîé ìàòåìàòèêå. Ì.: ÈÍÔÐÀ-Ì,2012. 90 ñ.[2] Âàñèëüåâ Þ.Ë., Âåòóõíîâñêèé Ô.ß., Ãëàãîëåâ Â.Â., Æóðàâëåâ Þ.È.,Ëåâåíøòåéí Â.È., ßáëîíñêèé Ñ.Â. Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè, I. Ì.: Íàóêà, 1974. Ñ. 998.[3] Ãàâðèëîâ Ã.Ï., Ñàïîæåíêî À.À.
Çàäà÷è è óïðàæíåíèÿ ïî äèñêðåòíîéìàòåìàòèêå. Ì.: Ôèçìàòëèò, 2004. 416 ñ.[4] Ãýðè Ì., Äæîíñîí Ä. Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûåçàäà÷è. Ì.: Ìèð, 1982. 416 ñ.[5] Êóê Ñ.À. Ñëîæíîñòü ïðîöåäóð âûâîäà òåîðåì // Êèáåðíåòè÷åñêèéñáîðíèê. Íîâàÿ ñåðèÿ. Âûï. 12. Ì.: Ìèð, 1975. Ñ. 515.[6] Ìàð÷åíêîâ Ñ.Ñ. Îñíîâû òåîðèè áóëåâûõ ôóíêöèé. Ì.: Ôèçìàòëèò,2014.
136 ñ.132[7] ßáëîíñêèé Ñ.Â. Ôóíêöèîíàëüíûå ïîñòðîåíèÿ â k -çíà÷íîé ëîãèêå //Òðóäû Ìàòåì. èí-òà èì. Â.À. Ñòåêëîâà ÀÍ ÑÑÑÐ. 1958. Ò. LI. Ñ.5142.[8] ßáëîíñêèé Ñ.Â. Ââåäåíèå â äèñêðåòíóþ ìàòåìàòèêó. Ì.: Âûñøàÿøêîëà, 2003. 384 ñ.[9] ßíîâ Þ.È., Ìó÷íèê À.À. Î ñóùåñòâîâàíèè k -çíà÷íûõ çàìêíóòûõêëàññîâ, íå èìåþùèõ áàçèñà // ÄÀÍ ÑÑÑÐ. 1959. Ò. 127, 1. Ñ.4446.[10] Post E.L. Introduction to a general theory of elementary propositions// Amer.
J. Math. 1921. V. 43, 4. P. 163185.[11] Post E.L. Two-valued iterative systems of mathematical logic // Annalsof Math. Studies. Princeton Univ. Press, 1941. V. 5. P. 1122.133.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
