С.С. Марченков - Избранные главы дискретной математики (1124120), страница 2
Текст из файла (страница 2)
Çäåñü îïðåäåëåíû êëàññ ôóíêöèé, âû÷èñëèìûõ íàìàøèíàõ Òüþðèíãà, êëàññ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé è äîêàçàíîñîâïàäåíèå ýòèõ êëàññîâ. Êðîìå òîãî, èìåþòñÿ ïàðàãðàôû, ïîñâÿùåííûåïîíÿòèÿì P-ñâîäèìîñòè è NP-ïîëíîòû.  ÷àñòíîñòè, ïðèâåäåíî äîêàçàòåëüñòâî ñóùåñòâîâàíèÿ NP-ïîëíûõ ïðîáëåì (òåîðåìà Ñ. Êóêà).Ïîñîáèå ñîäåðæèò áîëüøîå êîëè÷åñòâî çàäà÷ è óïðàæíåíèé, ê êîòîðûì äàíû îòâåòû è ðåøåíèÿ.Àâòîð âûðàæàåò áëàãîäàðíîñòü ïðîôåññîðó Â.À. Çàõàðîâó è äîöåíòóÄ.Ñ.
Ðîìàíîâó çà ïîëåçíûå çàìå÷àíèÿ è Å.À. Êîëìàêîâó çà ïîìîùü âîôîðìëåíèè ðèñóíêîâ.6Ãëàâà 1ÔÓÍÊÖÈÈ ÌÍÎÃÎÇÍÀ×ÍÎÉ ËÎÃÈÊÈ 1. Îñíîâíûå ïîíÿòèÿÔóíêöèè ìíîãîçíà÷íîé ëîãèêè ïðåäñòàâëÿþò ñîáîé îáîáùåíèå áóëåâûõ ôóíêöèé. Ïîýòîìó ìíîãèå âîïðîñû äëÿ ôóíêöèé ìíîãîçíà÷íîé ëîãèêè ðàññìàòðèâàþòñÿ è ðåøàþòñÿ ïî àíàëîãèè ñ áóëåâûìè ôóíêöèÿìè.Îäíàêî ñóùåñòâóåò ðÿä îñîáåííîñòåé, êîòîðûå õàðàêòåðíû òîëüêî äëÿôóíêöèé ìíîãîçíà÷íîé ëîãèêè (íà÷èíàÿ ñ ôóíêöèé òðåõçíà÷íîé ëîãèêè) è êîòîðûõ íåò ó áóëåâûõ ôóíêöèé.  ñâÿçè ñ ýòèì òåîðèÿ ôóíêöèé ìíîãîçíà÷íîé ëîãèêè çíà÷èòåëüíî áîãà÷å è ñëîæíåå òåîðèè áóëåâûõôóíêöèé.Ââåäåì ðÿä îïðåäåëåíèé.
Ïóñòü k íàòóðàëüíîå ÷èñëî, k > 2 èEk = {0, 1, . . . , k − 1}. Áóäåì ðàññìàòðèâàòü ôóíêöèè íà ìíîæåñòâå Ek ,ò.å. ôóíêöèè, îòîáðàæàþùèå äåêàðòîâû ñòåïåíè Ek â Ek . Ìíîæåñòâîâñåõ òàêèõ ôóíêöèé îáîçíà÷èì ÷åðåç Pk . Ôóíêöèè èç Pk íàçûâàþòñÿ(ïðè k = 2 ïîëó÷àåìèëè). Åñëè Q ⊆ Pk è n íàòóðàëüíîå ÷èñëî, òî(n)ïóñòü Q îáîçíà÷àåò ìíîæåñòâî âñåõ ôóíêöèé èç Q, çàäàííûõ íà Ekn(ìíîæåñòâî n-ìåñòíûõ ôóíêöèé èç Q).Îáû÷íî ïðè îïðåäåëåíèè n-ìåñòíîé ôóíêöèè f èç Pk çíà÷åíèå ôóíêöèè f íà (óïîðÿäî÷åííîì) íàáîðå (a1 , .
. . , an ) èç Ekn çàïèñûâàþò â âèäå f (a1 , . . . , an ).  ñâÿçè ñ ýòèì n-ìåñòíóþ ôóíêöèèþ f ïðèíÿòî íàçâàòü ôóíêöèåé îò n ïåðåìåííûõ è èçîáðàæàòü â âèäå f (x1 , . . . , xn ), ãäå(x1 , . . . , xn ) óïîðÿäî÷åííàÿ n-êà ïåðåìåííûõ. Ïðè ýòîì ïðåäïîëàãàåòñÿ, ÷òî êàæäàÿ ïåðåìåííàÿ xi (1 6 i 6 n) ïðèíèìàåò çíà÷åíèÿ èç i-ãîñîìíîæèòåëÿ äåêàðòîâîé ñòåïåíè Ekn .  ÷àñòíîñòè, â íàáîðå (a1 , . .
. , an )ïåðåìåííàÿ xi ïðèíèìàåò çíà÷åíèå ai .(n)Íåòðóäíî ïîäñ÷èòàòü ÷èñëî ôóíêöèé â ìíîæåñòâå Pk .  ñàìîì äåëå,(n)âñÿêàÿ ôóíêöèÿ èç Pk îïðåäåëåíà íà ìíîæåñòâå Ekn , ñîñòîÿùåì èç k nýëåìåíòîâ, è ïðèíèìàåò çíà÷åíèÿ â ìíîæåñòâå Ek , èìåþùåì k ýëåìåíòîâ. Òàêèì îáðàçîì, çàäàòü n-ìåñòíóþ ôóíêöèþ èç Pk çíà÷èò ïðèïèñàòüêàæäîìó íàáîðó èç Ekn îäíî èç k âîçìîæíûõ çíà÷åíèé. Ýòî ìîæíî ñäånëàòü ðîâíî k k ñïîñîáàìè.ôóíêöèÿìè k-çíà÷íîé ëîãèêèôóíêöèè àëãåáðû ëîãèêèáóëåâû ôóíêöèè7Äëÿ ëþáîãî n > 1 è ëþáîãî i (1 6 i 6 n) îáîçíà÷èì ÷åðåç eni (x1 , .
. . , xi ,. . . , xn )èç Pk , çíà÷åíèÿ êîòîðîé ñîâïàäàþò ñî çíà÷åíèÿìè ïåðåìåííîé xi . Èíîãäà, åñëè ýòî íå ïðèâîäèò ê íåäîðàçóìåíèþ,âìåñòî ôóíêöèè eni (x1 , . . . , xi , . . . , xn ) áóäåì ïèñàòü ïðîñòî ïåðåìåííóþxi .Ãîâîðÿò, ÷òî ôóíêöèÿ f (x1 , . . . , xi , . . . , xn )îòïåðåìåííîé xi , åñëè íàéäóòñÿ òàêèå çíà÷åíèÿ a1 , . . . , ai−1 , ai+1 , . . . , an ïåðåìåííûõ x1 , .
. . , xi−1 , xi+1 , . . . , xn , ÷òî ôóíêöèÿ îäíîé ïåðåìåííîé f (a1 ,. . . , ai−1 , xi , ai+1 , . . . , xn ) îòëè÷íà îò êîíñòàíòû. Åñëè ôóíêöèÿ f (x1 , . . . ,xn ) ñóùåñòâåííî çàâèñèò îò ïåðåìåííîé xi , òî ïåðåìåííàÿ xi íàçûâàåòñÿôóíêöèè f (x1 , . . . , xn ).  ïðîòèâíîì ñëó÷àåïåðåìåííàÿ xi íàçûâàåòñÿèëèôóíêöèè f (x1 , . .
. , xn ).Èç îïðåäåëåíèÿ ñóùåñòâåííîé çàâèñèìîñòè âèäíî, ÷òî ïðè âû÷èñëåíèè çíà÷åíèé ôóíêöèè ðåàëüíî èñïîëüçóþòñÿ ëèøü çíà÷åíèÿ ñóùåñòâåííûõ ïåðåìåííûõ.  ñâÿçè ñ ýòèì âîçíèêàåò æåëàíèå îñâîáîäèòüñÿ îò¾íåíóæíûõ¿ ôèêòèâíûõ ïåðåìåííûõ. Åñëè, íàïðèìåð, èçâåñòíî, ÷òî ñóùåñòâåííûìè ïåðåìåííûìè ôóíêöèè f (x1 , . . . , xn ) ÿâëÿþòñÿ òîëüêî ïåðåìåííûå x1 , .
. . , xm , òî èçáàâèòüñÿ â ôóíêöèè f (x1 , . . . , xn ) îò ôèêòèâíûõ ïåðåìåííûõ xm+1 , . . . , xn ìîæíî ïî-ðàçíîìó. Ìîæíî, íàïðèìåð, çíà÷åíèÿ ôóíêöèè f ðàññìàòðèâàòü òîëüêî íà íàáîðàõ (a1 , . . . , an ), ó êîòîðûõ am+1 = . . . = an = c, ãäå c ∈ Ek . Ýòî ñîîòâåòñòâóåò ïîäñòàíîâêå êîíñòàíòû c íà ìåñòà âñåõ ïåðåìåííûõ xm+1 , . . .
, xn : f (x1 , . . . , xm , c, . . . , c).Äðóãîé ñïîñîá ñîñòîèò â òîì, ÷òîáû ïðèäàòü âñåì ïåðåìåííûì xm+1 , . . . ,xn çíà÷åíèÿ îäíîé èç ïåðåìåííûõ x1 , . . . , xm , íàïðèìåð, ïåðåìåííîé x1 . Âòàêèõ ñëó÷àÿõ ãîâîðÿò, ÷òî ïåðåìåííûå xm+1 , . . .
, xnñ ïåðåìåííîé x1 : f (x1 , . . . , xm , x1 , . . . , x1 ).Íà ïðàêòèêå ÷àñòî âîçíèêàåò ïîòðåáíîñòü ¾äîáàâèòü¿ ê ôóíêöèè g(x1 ,. . . , xm ) ôèêòèâíûå ïåðåìåííûå xm+1 , . . . , xn . Äëÿ ýòîãî èñêîìóþ ôóíêöèþ f (x1 , . . . , xn ), êàê ïðàâèëî, îïðåäåëÿþò ðàâåíñòâîìñåëåêòîðíóþ ôóíêöèþñóùåñòâåííî çàâèñèòñóùåñòâåííîé ïåðåìåííîéíåñóùåñòâåííîéôèêòèâíîé ïåðåìåííîéîòîæäåñòâëÿþòñÿf (x1 , . . .
, xm , xm+1 , . . . , xn ) = g(x1 , . . . , xm ),êîòîðîå ñ÷èòàåòñÿ âåðíûì ïðè ëþáûõ çíà÷åíèÿõ ïåðåìåííûõ x1 , . . . , xn .Îäíàêî ñ àëãåáðàè÷åñêîé è ôóíêöèîíàëüíîé òî÷åê çðåíèÿ áîëåå îïðàâäàííûì ïðåäñòàâëÿåòñÿ èñïîëüçîâàíèå ñåëåêòîðíûõ ôóíêöèé. Èìåííî,ïåðåõîä îò ôóíêöèè g ê ôóíêöèè f âûïîëíÿåòñÿ ñ ïîìîùüþ ¾ðåãóëÿðíîé¿ ïîäñòàíîâêè ñåëåêòîðíûõ ôóíêöèé â ôóíêöèþ g :f (x1 , . . .
, xm , xm+1 , . . . , xn ) = g(en1 (x1 , . . . , xn ), . . . , enm (x1 . . . , xn )).8ôîð-Ïóñòü Q íåïóñòîå ìíîæåñòâî ôóíêöèé èç Pk . Ââåäåì ïîíÿòèåQ. Îäíîâðåìåííî âñÿêîé ôîðìóëå íàä Q áóäåò ñîïîñòàâëåíàôóíêöèÿ èç Pk , êîòîðàÿ ðåàëèçóåòñÿ ýòîé ôîðìóëîé.Ïðåäïîëîæèì, ÷òî âñå ôóíêöèè èç Q èìåþò èíäèâèäóàëüíûå îáîçíà÷åíèÿ. Åñëè ñèìâîëîì f îáîçíà÷åíà n-ìåñòíàÿ ôóíêöèÿ èç Q, à x1 , . . . , xnñóòü ñèìâîëû ïåðåìåííûõ, òî âûðàæåíèå f (x1 , .
. . , xn ) íàçûâàåòñÿ. Ôîðìóëå f (x1 , . . . , xn ) ñîïîñòàâëÿåì ôóíêöèþ èç Q, èìåþùóþ îáîçíà÷åíèå f . Ãîâîðèì, ÷òî ýòà ôóíêöèÿf (x1 , . . . , xn ).Äàëåå, åñëè ñèìâîëîì g îáîçíà÷åíà ôóíêöèÿ èç Q îò m ïåðåìåííûõ,à Φ1 , . . . , Φm ëèáî ôîðìóëû íàä Q, ëèáî ñèìâîëû ïåðåìåííûõ (íåîáÿçàòåëüíî ðàçëè÷íûå), òî âûðàæåíèå g(Φ1 , . . .
, Φm ) åñòü. Ïðåäïîëîæèì, ÷òî âûðàæåíèÿì Φi , îòëè÷íûì îò ñèìâîëîâ ïåðåìåííûõ, óæå ñîïîñòàâëåíû ôóíêöèè fi . Åñëè âûðàæåíèå Φi ïðåäñòàâëÿåòñîáîé ñèìâîë ïåðåìåííîé xj , òî ñîïîñòàâèì åìó ôóíêöèþ fi (xj ), ðàâíóþ ïåðåìåííîé xj . Òîãäà ôîðìóëå g(Φ1 , . .
. , Φm ) ñîïîñòàâèì ôóíêöèþg(f1 , . . . , fm ),( ýòîì ìåñòå íåîáõîäèìî ïîÿñíèòü, ÷òî ïðåäñòàâëÿåò ñîáîé ôóíêöèÿ,êîòîðàÿ ðåàëèçóåòñÿ, íàïðèìåð, ôîðìóëîéìóëû íàäôîð-ìóëîé íàä Qðåàëèçóåòñÿ ôîðìóëîéôîðìóëà íàäQðåàëèçóåìóþ ýòîé ôîðìóëîé.mg(f1 (x11 , . . . , x1n1 ), . . . , fm (xm1 , . . . , xnm )),(1.1)ãäå ôóíêöèè g, f1 , . . . , fm ñ÷èòàþòñÿ èçâåñòíûìè, à ïåðåìåííûå x11 , . . . ,xmnm íå ïðåäïîëàãàþòñÿ ðàçëè÷íûìè. Áóäåì ñ÷èòàòü, ÷òî ïåðåìåííûåx11 , . . . , xmnm âûáðàíû èç ïîñëåäîâàòåëüíîñòè x1 , x2 , . .
. (â èíûõ ñëó÷àÿõìíîæåñòâî ïåðåìåííûõ x11 , . . . , xmnm ñ÷èòàåì ëèíåéíî óïîðÿäî÷åííûì).Ïóñòü, íàïðèìåð, ýòî ïåðåìåííûå xi1 , . . . , xil , ãäå i1 < . . . < il . Òîãäàôîðìóëà (1.1) ðåàëèçóåò ôóíêöèþ h(xi1 , . . . , xil ), çíà÷åíèÿ êîòîðîé âû÷èñëÿþòñÿ ñëåäóþùèì îáðàçîì.
Äëÿ ïðîèçâîëüíîãî íàáîðà (a1 , . . . , al )èç Ekl (çíà÷åíèå aj ñîîòâåòñòâóåò ïåðåìåííîé xij ) îáðàçóåòñÿ m íàáîðîâ ã1 , . . . , ãm , êîòîðûå îòâå÷àþò íàáîðàì ïåðåìåííûõ (x11 , . . . , x1n1 ), . . . ,m(xm1 , . . . , xnm ). Çàòåì ê íàáîðàì ã1 , . . . , ãm ïðèìåíÿþòñÿ ñîîòâåòñòâåííîôóíêöèè f1 , . . . , fm . Ïîëó÷àåòñÿ íàáîð çíà÷åíèé (b1 , . . . , bm ), ê êîòîðîìó,â ñâîþ î÷åðåäü, ïðèìåíÿåòñÿ ôóíêöèÿ g .)Åñëè ôóíêöèÿ f ðåàëèçóåòñÿ ôîðìóëîé, â ñîñòàâ êîòîðîé ïîìèìî ñèìâîëîâ ïåðåìåííûõ âõîäÿò òîëüêî ñèìâîëû ôóíêöèé f1 , . .
. , fs , òî ãîâîðÿò, ÷òî ôóíêöèÿ f ÿâëÿåòñÿ (èëè îáðàçîâàíà)f1 , . . . , fs . Âîîáùå, ïîä îïåðàöèåéïîíèìàþò (÷àñòè÷íóþ)îïåðàöèþ, êîòîðàÿ, èñïîëüçóÿ ôîðìóëüíóþ âûðàçèìîñòü îäíîé ôóíêöèèñóïåðïîçèöèè9ñóïåðïîçèöèåé ôóíêöèé÷åðåç äðóãèå, ïîçâîëÿåò ïî êîíå÷íîìó íàáîðó ôóíêöèé F îïðåäåëÿòü íîâóþ ôóíêöèþ, ðåàëèçóåìóþ ôîðìóëîé íàä F .Âàæíûì ÷àñòíûì ñëó÷àåì îïåðàöèè ñóïåðïîçèöèè ÿâëÿåòñÿ îòîæäåñòâëåíèå ïåðåìåííûõ. Ãîâîðÿò, ÷òî ôóíêöèÿ g(x1 , .
. . , xj−1 , xj+1 , . . . , xn )ïîëó÷åíà èç ôóíêöèè f (x1 , . . . , xn )(1 6 i < j 6 n), åñëèîòîæäåñòâëåíèåì i-é è j-é ïåðåìåí-íûõg(x1 , . . . , xj−1 , xj+1 , . . . , xn ) = f (x1 , . . . , xj−1 , xi , xj+1 , . . . , xn ).Áîëåå ñëîæíûå ñëó÷àè îòîæäåñòâëåíèÿ íåñêîëüêèõ ïåðåìåííûõ ïîëó÷àþòñÿ ïîñëåäîâàòåëüíûì âûïîëíåíèåì îòîæäåñòâëåíèé äâóõ ïåðåìåííûõ.Êàê âèäíî èç ïðèâåäåííûõ âûøå îïðåäåëåíèé, ââåäåíèå îïåðàöèè ñóïåðïîçèöèè íà îñíîâå ïîíÿòèÿ ôîðìóëû ñîäåðæèò íåêîòîðûå òðóäíîñòè.Ïðåæäå âñåãî, ýòî êàñàåòñÿ îïðåäåëåíèÿ ôóíêöèé, ðåàëèçóåìûõ ôîðìóëàìè âèäà (1.1).
Áûëî áû ãîðàçäî óäîáíåå, íàïðèìåð, ðàññìàòðèâàòüôîðìóëû âèäàg(f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn )).Îäíàêî ïðè ýòîì åñòü ðèñê ïîòåðÿòü â îáùíîñòè: ôóíêöèè f1 , . . . , fmâîâñå íå îáÿçàíû çàâèñåòü îò îäíèõ è òåõ æå ïåðåìåííûõ.Ñóùåñòâóåò ïî ìåíüøåé ìåðå äâà ïóòè âûõîäà èç ýòîãî ïîëîæåíèÿ.Ìîæíî ñ÷èòàòü, ÷òî íàðÿäó ñ êàæäîé ôóíêöèåé ó íàñ èìåþòñÿ âñå ôóíêöèè, ïîëó÷åííûå èç íåå ââåäåíèåì íåñóùåñòâåííûõ ïåðåìåííûõ. Äðóãîéïîäõîä çàêëþ÷àåòñÿ â òîì, ÷òîáû èçíà÷àëüíî (íàïðèìåð, ïðè îïðåäåëåíèè çàìûêàíèÿ) ðàññìàòðèâàòü òîëüêî ñèñòåìû ôóíêöèé, âêëþ÷àþùèåâñå ñåëåêòîðíûå ôóíêöèè. Âòîðîé ïîäõîä ïðåäñòàâëÿåòñÿ áîëåå ¾àëãåáðàè÷åñêèì¿. Îí íå ñîäåðæèò íåêîòîðûõ ïðîòèâîðå÷èé, ïðèñóùèõ ïåðâîìó ïîäõîäó, îäíàêî òðåáóåò íàëè÷èÿ ìíîæåñòâà ¾âñïîìîãàòåëüíûõ¿ñåëåêòîðíûõ ôóíêöèé.Ïóñòü Q ⊆ Pk .ìíîæåñòâà ôóíêöèé Q íàçûâàòñÿ ìíîæåñòâî âñåõ ôóíêöèé, êîòîðûå ìîæíî ðåàëèçîâàòü ôîðìóëàìè íàä Q.Èíûìè ñëîâàìè, çàìûêàíèå ìíîæåñòâà Q ñîñòîèò èç âñåõ ôóíêöèé, êîòîðûå ÿâëÿþòñÿ ñóïåðïîçèöèÿìè ôóíêöèé èç Q.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
