Расширенный сборник задач для самостоятельного решения (1157992), страница 6
Текст из файла (страница 6)
Äåêëàðàòèâíàÿ è îïåðàöèîííàÿ ñåìàíòèêè.27Äëÿ îáîçíà÷åíèÿ òîãî ôàêòà, ÷òî ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿ ïðîãðàììû P áóäåò èñïîëüçîâàòüñÿ ñîêðàùåííàÿ çàïèñü I |= P .Äîêàæèòå, ÷òî H -èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿ õîðíîâñêîéëîãè÷åñêîé ïðîãðàììû P òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî îñíîâíîãî ïðèìåðà ïðîãðàììíîãî óòâåðæäåíèÿ D0 = A00 ← A01 , . . . , A0n , D0 ∈ [P] âåðíîÓïðàæíåíèå 1.98.{A01 , . .
. , A0n } ⊆ I ⇒ A00 ∈ I.Äîêàæèòå, ÷òî êàæäàÿ õîðíîâñêàÿ ëîãè÷åñêàÿ ïðîãðàììà P èìååò õîòÿáû îäíó ýðáðàíîâñêóþ ìîäåëü.Äîêàæèòå, ÷òî H -èíòåðïðåòàöèÿ BH ÿâëÿåòñÿ ìîäåëüþ äëÿ ëþáîéõîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P . Ïðèâåäèòå ïðèìåð ïðîãðàììû, ìîäåëüþ êîòîðîé ÿâëÿåòñÿ èíòåðïðåòàöèÿ I = ∅. Êàê äîëæíà áûòü óñòðîåíà ïðîãðàììà P äëÿ òîãî, ÷òîáû èíòåðïðåòàöèÿ I = ∅ áûëà åå ìîäåëüþ?Äîêàæèòå, ÷òî åñëè H -èíòåðïðåòàöèè I1 è I2 ÿâëÿþòñÿ ìîäåëÿìèäëÿ õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P , òî H -èíòåðïðåòàöèÿ I0 = I1 ∩ I2 òàêæå ÿâëÿåòñÿìîäåëüþ äëÿ P .Ðàññìîòðèì ìíîæåñòâî IP âñåõ ýðáðàíîâñêèõ ìîäåëåé äëÿ ëîãè÷åñêîé ïðîãðàììû P . Äîêàæèòå, ÷òî H -èíòåðïðåòàöèÿ MP = T I ÿâëÿåòñÿ íàèìåíüøåé (ïîI∈Iîòíîøåíèþ òåîðåòèêî-ìíîæåñòâåííîãî âêëþ÷åíèÿ) ìîäåëüþ äëÿ ïðîãðàììû P .Ðàññìîòðèì ìíîæåñòâî IP âñåõ ýðáðàíîâñêèõ ìîäåëåé äëÿ îãè÷åñêîéïðîãðàììû P . Äîêàæèòå, ÷òî 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
