Расширенный сборник задач для самостоятельного решения, страница 6

. . , Ak ∈ [P], {A1 , . . . , Ak } ⊆ I}.Äîêàæèòå, ÷òî äëÿ ëþáîé ýðáðàíîâñêîé ìîäåëè I äëÿ õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû Pèíòåðïðåòàöèÿ TP (I) òàêæå ÿâëÿåòñÿ ìîäåëüþ äëÿ ïðîãðàììû P .Ïóñòü çàäàíà õîðíîâñêàÿ ëîãè÷åñêàÿ ïðîãðàììàP : P(f(X)) ← P(X);ñèãíàòóðû Σ = hConst = {c}, F unc = {f }, P red = {P }i, ñîñòîÿùàÿ èç îäíîãî-åäèíñòâåííîãîïðîãðàììíîãî óòâåðæäåíèÿ.Êàêèå ýðáðàíîâñêèå èíòåðïðåòàöèè ÿâëÿþòñÿ çíà÷åíèÿìè îïåðàòîðà íåïîñðåäñòâåííîãî ñëåäîâàíèÿ TP (∅) è TP (BP ?Ïóñòü çàäàíà õîðíîâñêàÿ ëîãè÷åñêàÿ ïðîãðàììàP : P(X) ← R(X), P(c);Óïðàæíåíèå 1.110.Óïðàæíåíèå 1.111.R(b) ← P(a);R(a);P(c);Âû÷èñëèòå çíà÷åíèÿ îïåðàòîðà íåïîñðåäñòâåííîãî ñëåäîâàíèÿ TP (∅), TP (TP (∅)), TP (TP (TP (∅)))?Äîêàæèòå, ÷òî äëÿ ëþáîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P îïåðàòîð íåïîñðåäñòâåííîãî ñëåäîâàíèÿ TP îáëàäàåò ñâîéñòâîì ìîíîòîííîñòè, ò.

å. äëÿ ëþáûõýðáðàíîâñêèõ èíòåðïðåòàöèé I, J ñïðàâåäëèâî ñîîòíîøåíèåÓïðàæíåíèå 1.112.1.12.29Ñòðàòåãèè âû÷èñëåíèÿ ëîãè÷åñêèõ ïðîãðàìì.I ⊆ J =⇒ TP (I) ⊆ TP (J) .Äîêàæèòå, ÷òî ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿõîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P â òîì è òîëüêî òîì ñëó÷àå, êîãäà TP (I) ⊆ I .Óïðàæíåíèå 1.113.Óñëîâèìñÿ n-êðàòíóþ êîìïîçèöèþ îïåðàòîðà íåïîñðåäñòâåííîãî ñëåäîâàíèÿ îáîçíà÷àòü TPn , ò. å.

TPn (I) = T| P (TP{z(. . . TP}(I) . . . )).n ðàçÄîêàæèòå, ÷òî äëÿ ëþáîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P èìååò ìåñòî ñëåäóþùàÿ öåïî÷êà âêëþ÷åíèéÓïðàæíåíèå 1.114.TP0 (∅) ⊆ TP1 (∅) ⊆ TP2 (∅) ⊆ · · · ⊆ TPi (∅) ⊆ TPi+1 (∅) ⊆ . . . ⊆ MP .Äîêàæèòå, ÷òî ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ S TPi (∅) ÿâëÿåòñÿ ìîäåi=0ëüþ äëÿ õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P .∞Óïðàæíåíèå 1.115.Äîêàæèòå,÷òî äëÿ ëþáîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P èìååò∞Siìåñòî ðàâåíñòâî MP = TP (∅).Óïðàæíåíèå 1.116.i=0Äîêàæèòå, ÷òî äëÿ ëþáîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P èëþáîãî îñíîâíîãî àòîìà A çàïðîñ ?A ê ïðîãðàììå P èìååò óñïåøíîå SLD-ðåçîëþòèâíîå âû÷èñëåíèå òîãäà è òîëüêî òîãäà, êîãäà A ∈ MP .Óïðàæíåíèå 1.117.Äîêàæèòå, ÷òî äëÿ ëþáîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P çàïðîññ ìíîæåñòâîì öåëåâûõ ïåðåìåííûõ Y1 , Y2 , .

. . , Ym , îáðàùåííûé ê ïðîãðàììå èìååò õîòÿ áû îäíî óñïåøíîå SLD-ðåçîëþòèâíîå âû÷èñëåíèå â òîì è òîëüêî òîì ñëó÷àå,êîãäà èìååò ìåñòî ëîãè÷åñêîå ñëåäñòâèå P |= ∃Y1 ∃Y2 . . . ∃Ym (C1 &C2 & . . . &Cn ).Óïðàæíåíèå 1.118.G =?C1 , C2 , . . . , CnPÂåðíî ëè, ÷òî äëÿ ëþáîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P èàòîìà A ëîãè÷åñêîå ñëåäñòâèå P |= ∀Y1 ∀Y2 . . .

∀Ym A èìååò ìåñòî òîãäà è òîëüêî òîãäà, êîãäàâûïîëíÿåòñÿ âêëþ÷åíèå [A] ⊆ MP ?Óïðàæíåíèå 1.119.1.12Ñòðàòåãèè âû÷èñëåíèÿ ëîãè÷åñêèõ ïðîãðàìì.Ïîñòðîéòå äåðåâî SLD-ðåçîëþòèâíûõ âû÷èñëåíèé äëÿ çàïðîñà G= ?îáðàùåííîãî ê ïðîãðàììå P , èñïîëüçóÿ ñòàíäàðòíîå ïðàâèëî âûáîðà ïîäöåëåé.Óïðàæíåíèå 1.120.P(X,b),:P P(X,Z) ← Q(X,Y),P(Y,Z);P(X,X) ← ;Q(a,b) ← ;30Ãëàâà 1.ÓÏÐÀÆÍÅÍÈßÏðåäïîëîæèì, ÷òî â òåëå ïåðâîãî ïðîãðàììíîãî óòâåðæäåíèÿ P(X,Z) ← Q(X,Y),P(Y,Z);ïðîãðàììèñò ïîìåíÿë ìåñòàìè àòîìû Q(X,Y) è P(Y,Z). Êàê èçìåíèòñÿ â ýòîì ñëó÷àå äåðåâîSLD-ðåçîëþòèâíûõ âû÷èñëåíèé çàïðîñà G?Ïîñòðîéòå äåðåâî SLD-ðåçîëþòèâíûõ âû÷èñëåíèé äëÿ çàïðîñà G= ?îáðàùåííîãî ê ïðîãðàììå P , èñïîëüçóÿ ñòàíäàðòíîå ïðàâèëî âûáîðà ïîäöåëåé.Óïðàæíåíèå 1.121.R(Y),P(Z),:P R(Y) ← P(Y),Q(Y);P(a) ← ;P(b) ← ;Q(a) ← ;Q(f(X)) ← Q(X);Ïðåäïîëîæèì, ÷òî â òåëå ïåðâîãî ïðîãðàììíîãî óòâåðæäåíèÿ R(Y) ← P(Y),Q(Y); ïðîãðàììèñò ïîìåíÿë ìåñòàìè àòîìû P(Y) è Q(Y).

Êàê èçìåíèòñÿ â ýòîì ñëó÷àå äåðåâî SLD-ðåçîëþòèâíûõâû÷èñëåíèé çàïðîñà G?Èìååò ëè çàïðîñ G= ? P(a,c), îáðàùåííûé ê ïðîãðàììå P , õîòÿ áûîäíî óñïåøíîå SLD-ðåçîëþòèâíîå âû÷èñëåíèå?P : P(a,b) ← ;Óïðàæíåíèå 1.122.P(c,b) ← ;P(X,Z) ← P(X,Y),P(Y,Z);P(X,Y) ← P(Y,X);Ïîêàæèòå, ÷òî â òîì ñëó÷àå, åñëè èç óêàçàííîé ïðîãðàììû óäàëèòü õîòÿ áû îäíî ïðîãðàììíîåóòâåðæäåíèå, òî çàïðîñ G íå áóäåò èìåòü íè îäíîãî ïðàâèëüíîãî îòâåòà.

Ïîêàæèòå, ÷òî ðóêîâîäñòâóÿñü ñòàíäàðòíîé ñòðàòåãèåé âû÷èñëåíèé íåëüçÿ âû÷èñëèòü íè îäèí îòâåò íà çàïðîñG, îáðàùåííûé ê ïðîãðàììå P . Êàêîé äîëæíà áûòü ñòðàòåãèÿ âû÷èñëåíèé, ïîçâîëÿþùàÿâû÷èñëèòü õîòÿ áû îäèí îòâåò íà çàïðîñ G ê ïðîãðàììå P .Ïðèâåäèòå ïðèìåð òàêîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P è òàêîãî çàïðîñà G, äëÿ êîòîðûõ ñóùåñòâóþò äâà óñïåøíûõ âû÷èñëåíèÿ, íî ïðè ýòîì íèêàêîåïðàâèëî âûáîðà ïîäöåëåé íå ïîçâîëÿåò ïîñòðîèòü, ðóêîâîäñòâóÿñü ïðîöåäóðîé ïîèñêà â ãëóáèíó ñ âîçâðàòîì, îáà óñïåøíûõ âû÷èñëåíèÿ.Óïðàæíåíèå 1.123.Cîçäàéòå õîðíîâñêèå ëîãè÷åñêèå ïðîãðàììû, êîòîðûå ðåøàþò ñëåäóþùèå çàäà÷è.1.

Ïðîãðàììà ïîðîæäàåò âñåâîçìîæíûå ïåðåñòàíîâêè ýëåìåíòîâ çàäàííîãî ñïèñêà L. Îáðàùåíèå ê ïðîãðàììå äîëæíî èìåò âèä ? permut(L,X).2. Ïðîãðàììà ïîðîæäàåò âñåâîçìîæíûå ïðåôèêñû çàäàííîãî ñëîâà L, ïðåäñòàâëåííîãîñïèñêîì áóêâ. Îáðàùåíèå ê ïðîãðàììå äîëæíî èìåò âèä ? all_prefixes(L,X).Óïðàæíåíèå 1.124.1.13.31Àëãîðèòìè÷åñêàÿ ïîëíîòà è àëãîðèòìè÷åñêàÿ íåðàçðåøèìîñòü.3.

Ïðîãðàììà ïîðîæäàåò âñåâîçìîæíûå ñóôôèêñû çàäàííîãî ñëîâà L, ïðåäñòàâëåííîãîñïèñêîì áóêâ. Îáðàùåíèå ê ïðîãðàììå äîëæíî èìåò âèä ? all_suffixes(L,X).4. Ïðîãðàììà ïîðîæäàåò ñïèñîê âñåõ áóêâ çàäàííîãî êîíå÷íîãî àëôàâèòà A = {a1 , a2 , . . . , an },ñîäåðæàùèõñÿ â ñïèñêå L îäíîêðàòíî. Îáðàùåíèå ê ïðîãðàììå äîëæíî èìåò âèä ?single(L,X).5.

Ïðîãðàììà ïîðîæäàåò ñïèñîê âñåõ áóêâ çàäàííîãî êîíå÷íîãî àëôàâèòà A = {a1 , a2 , . . . , an },ñîäåðæàùèõñÿ â ñïèñêå L ìíîãîêðàòíî. Îáðàùåíèå ê ïðîãðàììå äîëæíî èìåò âèä ?multiple(L,X).6. Ïðîãðàììà ïîðîæäàåò ñïèñîê âñåõ áóêâ çàäàííîãî êîíå÷íîãî àëôàâèòà A = {a1 , a2 , . . . , an },ñîäåðæàùèõñÿ â ñïèñêå L1 è íå ñîäåðæàùèõñÿ â ñïèñêå L2 . Îáðàùåíèå ê ïðîãðàììåäîëæíî èìåò âèä ? filter(L1,L2,X).7. Ïðîãðàììà ïîðîæäàåò âñåâîçìîæíûå ñî÷åòàíèÿ ýëåìåíòîâ çàäàííîãî áåñïîâòîðíîãî ñïèñêà L1 . Îáðàùåíèå ê ïðîãðàììå äîëæíî èìåò âèä ? combination(L1,X).8. Ïðîãðàììà ïîðîæäàåò âñåâîçìîæíûå ñî÷åòàíèÿ ýëåìåíòîâ çàäàííîãî áåñïîâòîðíîãî ñïèñêà L1 , äëèíà êîòîðûõ ðàâíà äëèíå çàäàííîãî ñïèñêà L2 . Îáðàùåíèå ê ïðîãðàììå äîëæíîèìåò âèä ? combination2(L1,L2,X).9.

Ïðîãðàììà ïîðîæäàåò âñåâîçìîæíûå ñî÷åòàíèÿ c ïîâòîðåíèåì ýëåìåíòîâ çàäàííîãî áåñïîâòîðíîãî ñïèñêà L1 , äëèíà êîòîðûõ ðàâíà äëèíå çàäàííîãî ñïèñêà L2 . Îáðàùåíèå êïðîãðàììå äîëæíî èìåò âèä ? combination_repit(L1,L2,X).1.13Àëãîðèòìè÷åñêàÿ ïîëíîòà è àëãîðèòìè÷åñêàÿ íåðàçðåøèìîñòü.Âîçüìèòå ëåíòî÷íóþ êîíôèãóðàöèþ α0 , ïðåäñòàâëåííóþ íà ðèñ.

, èïîñòðîéòå äåðåâî SLD-ðåçîëþòèâíûõ âû÷èñëåíèé äëÿ çàïðîñà ? P (lef t(α0 ), right(α0 ), X, Y ),îáðàùåííîãî ê ëîãè÷åñêîé ïðîãðàììå Pπ , ïðåäñòàâëåííîé íà ðèñ. .Êàêîå óñòðîéñòâî èìåþò äåðåâüÿ SLD-ðåçîëþòèâíûõ âû÷èñëåíèé çàïðîñîâ ? P (lef t(α), right(α), X, Y ), îáðàùåííûõ ê ëîãè÷åñêèì ïðîãðàììàì Pπ , ñîîòâåòñòâóþùèì äåòåðìèíèðîâàííûì ïðîãðàììàì ìàøèí Òüþðèíãà.Ïóñòü π ïðîèçâîëüíàÿ ïðîãðàììà ìàøèíû Òüþðèíãà, α ëåíòî÷íàÿ êîíôèãóðàöèÿ, ÿâëÿþùàÿñÿ çàêëþ÷èòåëüíîé äëÿ ïðîãðàììû π.

Êàêîâî ìíîæåñòâîâû÷èñëåííûõ îòâåòîâ íà çàïðîñ ? P (X, Y, lef t(α), right(α)) ê ëîãè÷åñêîé ïðîãðàììå Pπ ?×àñòè÷íî-ðåêóðñèâíîé ôóíêöèåé íàçûâàåòñÿ âñÿêàÿ ÷àñòè÷íî îïðåäåëåííàÿ ôóíêöèÿ íàòóðàëüíîãî àðãóìåíòà f (n) : Nn0 → N0 , êîòîðàÿ ìîæåò áûò ïîñòðîåíà èçáàçîâûõ ôóíêöèé• êîíñòàíòû 0,• ôóíêöèè ñëåäîâàíèÿ s(1) (x) = x + 1,Óïðàæíåíèå 1.125.????Óïðàæíåíèå 1.126.Óïðàæíåíèå 1.127.Óïðàæíåíèå 1.128.32Ãëàâà 1.ÓÏÐÀÆÍÅÍÈßñåëåêòîðíûõ ôóíêöèé I (n) (x1 , x2 , . . . , xn ) = xm , n ≥ 1, 1 ≤ m ≤ n,ïðè ïîìîùè ñëåäóþùèõ îïåðàöèé:1. ñóïåðïîçèöèÿ : äëÿ ëþáîé ôóíêöèè f (n) è íàáîðà èç n ôóíêöèé g1(m) , .

. . , gn(m) , â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèè ñóïåðïîçèöèè S[f, g1 , . . . , gn ] îáðàçóåòñÿ ôóíêöèÿ•Sh(m) (x1 , . . . , xm ) = f (g1 (x1 , . . . , xm ), . . . , gn (x1 , . . . , xm ));2.: äëÿ ëþáîé ïàðû ôóíêöèé f (n) è g(n+2) â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèè ïðèìèòèâíîé ðåêóðñèè Π[f, g] îáðàçóåòñÿ ôóíêöèÿ h(n+1) (x1 , . .

. , xn , xn+1 ),óäîâëåòâîðÿþùàÿ äëÿ ëþáîãî íàáîðà çíà÷åíèé ïåðåìåíííûõ x1 , . . . , xn è ëþáîãî íàòóðàëüíîãî ÷èñëà k ñëåäóþùèì äâóì ðàâåíñòâàì:ïðèìèòèâíàÿ ðåêóðñèÿΠh(x1 , . . . , xn , 0) =h(x1 , . . . , xn , k + 1) =3.f (x1 , . . . , xn ),g(x1 , . . .

, xn , k, h(x1 , . . . , xn , k));: äëÿ ëþáîé ôóíêöèè f (n) , n ≥ 1 â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèè íåîãðàíè÷åííîé ìèíèìèçàöèè µ[f ] îáðàçóåòñÿ ôóíêöèÿ h(n) (x1 , . . . , xn ),çíà÷åíèå êîòîðîé äëÿ ëþáîãî íàáîðà çíà÷åíèé ïåðåìåíííûõ x1 , . . . , xn−1 , xn óäîâëåòâîðÿåò ñëåäóþùåìó ñîîòíîøåíèþ:k,åñëè ñóùåñòâóåò òàêîå íàòóðàëüíîå ÷èñëî k, ÷òîi) âûïîëíÿåòñÿ ðàâåíñòâî f (x1 , .

. . , xn−1 , k) = xn ,ii) äëÿ ëþáîãî m, 0 ≤ m ≤ k − 1,çíà÷åíèå ôóíêöèè f (x1 , . . . , xn−1 , m)h(x1 , . . . , xn−1 , xn ) =îïðåäåëåíî è îòëè÷íî îò xn ,íåîïðåäåëåíî â ïðîòèâíîì ñëó÷àå.íåîãðàíè÷åííàÿ ìèíèìèçàöèèµÈç òåçèñà ×åð÷à ñëåäóåò, ÷òî êëàññ ýôôåêòèâíî âû÷èñëèìûõ àðèôìåòè÷åñêèõ ôóíêöèé ñîâïàäàåò ñ êëàññîì ÷àñòè÷íî-ðåêóðñèâíûõ ôóíêöèé.

Ïîýòîìó äëÿ äîêàçàòåëüñòâà àëãîðèòìè÷åñêîé ïîëíîòû õîðíîâñêèõ ëîãè÷åñêèõ ïðîãðàìì äîñòàòî÷íî ïîêàçàòü, ÷òî âñå ÷àñòè÷íîðåêðñèâíûå ôóíêöèè ìîãóò áûòü âû÷èñëåíû ëîãè÷åñêèìè ïðîãðàììàìè.Óñëîâèìñÿ ïðåäñòàâëÿòü íàòóðàëüíûå ÷èñëà â âèäå ñïèñêîâ: ïóñòîé ñïèñîê nil áóäåò îáîçíà÷àòü ÷èñëî 0, îäíîýëåìåíòíûé ñïèñîê nil.nil ÷èñëî 1, ñïèñîê nil.nil.nil ÷èñëî 2 è ò. ä.Ñïèñîê, ñîîòâåòñòâóþùèé íàòóðàëüíîìó ÷èñëó k, áóäåì îáîçíà÷àòü k.Ïîêàæèòå, ÷òî äëÿ êàæäîé ÷àñòè÷íî-ðåêóðñèâíîé ôóíêöèè f (x1 , . . .