Расширенный сборник задач (1131867), страница 6
Текст из файла (страница 6)
Äîêàæèòå, ÷òî H -èíòåðïðåòàöèÿ MP = T I ÿâëÿåòñÿ íàèìåíüøåé (ïî îòíîI∈Iøåíèþ òåîðåòèêî-ìíîæåñòâåííîãî âêëþ÷åíèÿ) ìîäåëüþ äëÿ ïðîãðàììû P .Äîêàæèòå, ÷òî MP = ∅ òîãäà è òîëüêî òîãäà, êîãäà õîðíîâñêàÿ ëîãè÷åñêàÿ ïðîãðàììà P íå ñîäåðæèò íè îäíîãî ôàêòà.Äîêàæèòå, ÷òî äëÿ ëþáîãî îñíîâíîãî àòîìà A0 è äëÿ ëþáîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P ñïðàâåäëèâî ñëåäóþùåå ñîîòíîøåíèå:Óïðàæíåíèå 1.99.Óïðàæíåíèå 1.100.Óïðàæíåíèå 1.101.Óïðàæíåíèå 1.102.PÓïðàæíåíèå 1.103.PÓïðàæíåíèå 1.104.Óïðàæíåíèå 1.105.P |= A0 ⇐⇒ A0 ∈ MP .Ïóñòü t1 , t2 , .
. . , tk ýòî íåêîòîðûé íàáîð îñíîâíûõ òåðìîâ.Äîêàæèòå, ÷òî ïîäñòàíîâêà θ = {Y1 /t1 , . . . , Yk /tk } ÿâëÿåòñÿ ïðàâèëüíûì îòâåòîì íà çàïðîñG =?C1 , C2 , . . . , Cm ê õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììå P òîãäà è òîëüêî òîãäà, êîãäà {C1 θ, . . . , Cm θ} ⊆MP .Äîêàæèòå, ÷òî äëÿ ëþáûõ õîðíîâñêèõ ëîãè÷åñêèõ ïðîãðàìì P1 è P2ñïðàâåäëèâî âêëþ÷åíèåÓïðàæíåíèå 1.106.Óïðàæíåíèå 1.107.MP1 ∪ MP2 ⊆ MP1 ∪P2 .28Ãëàâà 1.ÓÏÐÀÆÍÅÍÈßÏðèâåäèòå ïðèìåð ïðîãðàìì P1 è P2 , äëÿ êîòîðûõ óêàçàííîå âêëþ÷åíèå ÿâëÿåòñÿ ñòðîãèì.Êàêèì èç òðåõ òåîðåòèêî-ìíîæåñòâåííûõ îòíîøåíèé ⊆, =, ⊇ ñâÿçàíû ýðáðàíîâñêèå èíòåðïðåòàöèè MP ∩ MP è MP ∩P ?11.11212Òåîðåìû êîððåêòíîñòè è ïîëíîòû äëÿ õîðíîâñêèõ ëîãè÷åñêèõ ïðîãðàìì.Ñîõðàíÿò ëè ñïðàâåäëèâîñòü òåîðåìû êîððåêòíîñòè è ïîëíîòû äëÿõîðíîâñêèõ ëîãè÷åñêèõ ïðîãðàìì, åñëè â îïðåäåëåíèè ïðàâèëà SLD-ðåçîëþöèè âìåñòî íàèáîëåå îáùåãî óíèôèêàòîðà ðàçðåøèòü èñïîëüçîâàòü ïðîèçâîëüíûé óíèôèêàòîð âûäåëåííîéïîäöåëè çàïðîñà è çàãîëîâêà àêòèâèçèðîâàííîãî ïðîãðàììíîãî óòâåðæäåíèÿ?Îïåðàòîðîì íåïîñðåäñòâåííîãî ñëåäîâàíèÿ TP äëÿ õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P íàçûâàåòñÿ îòîáðàæåíèåÓïðàæíåíèå 1.108.Óïðàæíåíèå 1.109.TP : 2BP → 2BP ,ñîïîñòàâëÿþùåå êàæäîé ýðáðàíîâñêîé èíòåðïðåòàöèè I, I ⊆ BP , ýðáðàíîâñêóþ èíòåðïðåòàöèþ I 0 = TP (I), I 0 ⊆ BP , óäîâëåòâîðÿþùóþ ñëåäóþùåìó ñîîòíîøåíèþ:I 0 = {A0 : D = A0 ← A1 , .
. . , 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 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
