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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

, 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..

Характеристики

Список файлов книги