Расширенный сборник задач для самостоятельного решения (1157992), страница 7
Текст из файла (страница 7)
Îáðàùåíèå ê ïðîãðàììå äîëæíîèìåò âèä ? 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 , . .
. , xn ) ìîæíî ââåñòè ïðåäèêàòíûé ñèìâîë Pf(n+1) è ïîñòðîèòü òàêóþ õîðíîâñêóþ ëîãè÷åñêóþ ïðîãðàììó Pf , êîòîðàÿíà ëþáîé çàïðîñ G : ? Pf (k1 , . . . , kn , Y )• âû÷èñëÿåò åäèíñòâåííûé îòâåò {Y /m} òîãäà è òîëüêî òîãäà, êîãäà f (k1 , . . . , kn ) = m,• íå èìååò óñïåøíûõ âû÷èñëåíèé òîãäà è òîëüêî òîãäà, êîãäà çíà÷åíèå f (k1 , .
. . , kn ) íåîïðåäåëåíî.Âûÿñíèòå, ìîæíî ëè ïîñòðîèòü àëãîðèòìû, ñïîñîáíûå äëÿ ëþáîéõîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P , ïðîèçâîëüíîãî çàïðîñà G è ïðîèçâîëüíîé ïîäñòàíîâêèθ âûÿñíèòü,Óïðàæíåíèå 1.129.1.13.Àëãîðèòìè÷åñêàÿ ïîëíîòà è àëãîðèòìè÷åñêàÿ íåðàçðåøèìîñòü.331. ÿâëÿåòñÿ ëè äåðåâî SLD-ðåçîëþòèâíûõ âû÷èñëåíèé çàïðîñà G ê ëîãè÷åñêîé ïðîãðàììåP êîíå÷íûì?2. ÿâëÿåòñÿ ëè ïîäñòàíîâêà θ ïðàâèëüíûì îòâåòîì íà çàïðîñ G ê ïðîãðàììå P ?3. ÿâëÿåòñÿ ëè ïîäñòàíîâêà θ âû÷èñëåííûì îòâåòîì íà çàïðîñ G ê ïðîãðàììå P ?4. ñóùåñòâóåò ëè õîòÿ áû îäèí çàïðîñ ê ïðîãðàììå P , äëÿ êîòîðîãî ñóùåñòâóåò óñïåøíîåâû÷èñëåíèå?5.
ñóùåñòâóåò ëè áåñêîíå÷íî ìíîãî ðàçëè÷íûõ óñïåøíûõ âû÷èñëåíèé çàïðîñà G ê ïðîãðàììå P ?6. âåðíî ëè, ÷òî íà çàïðîñ G ïðîãðàììà P âû÷èñëÿåò òî æå ñàìîå ìíîæåñòâî îòâåòîâ, ÷òîè íåêîòîðàÿ çàäàííàÿ õîðíîâñêàÿ ëîãè÷åñêàÿ ïðîãðàììà P 0 ?Äîêàæèòå, ÷òî íè îäíà ñèñòåìà àâòîìàòè÷åñêîãî äîêàçàòåëüñòâà òåîðåì íå ìîæåò ãàðàíòèðîâàòü ðåøåíèÿ ñëåäóþùèõ âîïðîñîâ äëÿ ïðîèçâîëüíûõ ôîðìóë ëîãèêèïðåäèêàòîâ:1. ÿâëÿåòñÿ ëè çàäàííîå ïðåäëîæåíèå ϕ ëîãè÷åñêèì ñëåäñòâèåì çàäàííîãî ìíîæåñòâà ïðåäëîæåíèé Γ?2. ÿâëÿåòñÿ ëè çàäàííàÿ ôîðìóëà ϕ ïðîòèâîðå÷èâîé?3.
ÿâëÿåòñÿ ëè çàäàííàÿ ôîðìóëà ϕ âûïîëíèìîé?4. ÿâëÿåòñÿ ëè âûïîëíèìîé ñèñòåìà äèçúþíêòîâ Γ = {D1 , . . . , DN }, êàæäûé äèçúþíêò Diêîòîðîé ñîäåðæèò íå áîëåå äâóõ ëèòåð?5. èìååò ëè çàäàííîå ïðåäëîæåíèå ϕ êîíå÷íóþ ìîäåëü?6. ÿâëÿþòñÿ ëè äâå ôîðìóëû ëîãèêè ïðåäèêàòîâ ϕ1 è ϕ2 ðàâíîñèëüíûìè?Óïðàæíåíèå 1.130.Àëãîðèòìè÷åñêàÿ íåðàçðåøèìîñòü ïðîáëåìû îáùåçíà÷èìîñòè äëÿ ëîãèêè ïðåäèêàòîâ ïåðâîãî ïîðÿäêà íå îòìåíÿåò âîçìîæíîñòè ïîñòðîåíèÿ àëãîðèòìîâ, ïðîâåðÿþùèõ îáùåçíà÷èìîñòü ôîðìóë ñïåöèàëüíîãî âèäà.Äîêàæèòå, ÷òî ñóùåñòâóåò àëãîðèòì, ïðîâåðÿþùèé îáùåçíà÷èìîñòü ò.
í. ∀-ôîðìóë, ïðåäâàðåííàÿ íîðìàëüíàÿ ôîðìà êîòîðûõ èìååò âèäÓïðàæíåíèå 1.131.∀x1 ∀x2 . . . ∀xn ϕ(x1 , x2 , . . . , xn ).Êàêîâ ýòîò àëãîðèòì?Äîêàæèòå, ÷òî íå ñóùåñòâóåò àëãîðèòìà, ïðîâåðÿþùåãî îáùåçíà÷èìîñòü ò. í. ∃-ôîðìóë, ïðåäâàðåííàÿ íîðìàëüíàÿ ôîðìà êîòîðûõ èìååò âèäÓïðàæíåíèå 1.132.∃x1 ∃x2 . . . ∃xn ϕ(x1 , x2 , . . . , xn ).À ñóùåñòâóåò ëè àëãîðèòì ïðîâåðêè îáùåçíà÷èìîñòè ∃-ôîðìóë, â ìàòðèöå ϕ(x1 , x2 , . . . , xn )êîòîðûõ íå ñîäåðæèòñÿ ôóíêöèîíàëüíûõ ñèìâîëîâ?34Ãëàâà 1.ÓÏÐÀÆÍÅÍÈßÄîêàæèòå, ÷òî íå ñóùåñòâóåò àëãîðèòìà, ïðîâåðÿþùåãî îáùåçíà÷èìîñòü ôîðìóë, ïðåäâàðåííàÿ íîðìàëüíàÿ ôîðìà êîòîðûõ èìååò âèäÓïðàæíåíèå 1.133.∃x1 ∃x2 ∃x3 ∀y1 . .
. ∀yn ϕ(x1 , x2 , x3 , y1 , . . . , yn ),ãäå n ≥ 1.Äèàäè÷åñêîé ëîãèêîé íàçûâàåòñÿ ìíîæåñòâî ôîðìóë ëîãèêè ïðåäèêàòîâ, ñîäåðæàùèõ òîëüêî äâóõìåñòíûå ïðåäèêàòíûå ñèìâîëû. Ïîñòðîéòå àëãîðèòì, êîòîðûéäëÿ ïðîèçâîëüíîé ôîðìóëû ëîãèêè ïðåäèêàòîâ ϕ ñòðîèò òàêóþ ôîðìóëó äèàäè÷åñêîé ëîãèêèϕ∗ , äëÿ êîòîðîé âåðíî ñîîòíîøåíèå:Óïðàæíåíèå 1.134.|= ϕ ⇐⇒ |= ϕ∗ .Äîêàæèòå, ÷òî ïðîáëåìà îáùåçíà÷èìîñòè ôîðìóë äèàäè÷åñêîé ëîãèêè àëãîðèòìè÷åñêè íåðàçðåøèìà.Äîêàæèòå, ÷òî íå ñóùåñòâóåò àëãîðèòìà, ïðîâåðÿþùåãî îáùåçíà÷èìîñòü ôîðìóë äèàäè÷åñêîé ëîãèêè, ïîñòðîåííûõ â ñèãíàòóðå σ = h∅, ∅, {P (2) }i, ò. å.
ôîðìóë íåñîäåðæàùèõ êîíñòàíò è ôóíêöèîíàëüíûõ ñèìâîëîâ è ñîäåðæàùèõ òîëüêî îäèí äâóõìåñòíûéôóíêöèîíàëüíûé ñèìâîë P (2) .Ïîñòðîéòå àëãîðèòì, ïðîâåðÿþùèé îáùåçíà÷èìîñòü ôîðìóë ìîíàäè(1)(1)(1)÷åñêîé ëîãèêè, ò. å. ôîðìóë, êîòîðûå ñòðîÿòñÿ â ñèãíàòóðå σ = h∅, ∅, {P1 , P2 , . . . , PN }i,íå ñîäåðæàùåé êîíñòàíò è ôóíêöèîíàëüíûõ ñèìâîëîâ è ñîäåðæàùåé òîëüêî îäíîìåñòíûåïðåäèêàòíûå ñèìâîëû P1 , P2 , . . .
, PN .Ñîõðàíèòñÿ ëè àëãîðèòìè÷åñêàÿ ðàçðåøèìîñòü ïðîáëåìû îáùåçíà÷èìîñòè äëÿ ôîðìóë, ïîñòðîåííûõ èç îäíîìåñòíûõ ïðåäèêàòîâ, â òîì ñëó÷àå, åñëè â ýòèõ ôîðìóëàõ íàðÿäó ñ ïðåäèêàòàìè ðàçðåøèòü èñïîëüçîâàòü ìíîãîìåñòíûå ôóíêöèîíàëüíûå ñèìâîëû?Óïðàæíåíèå 1.135.Óïðàæíåíèå 1.136..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
