2009 экзамен вариант 8 (1162068)
Текст из файла
ÂàðèàíòÑëîâî ýòî êîíå÷íûé íåïóñòîé ñïèñîê áóêâ ôèêñèðîâàííîãî êîíå÷íîãî àëôàâèòà. Òåêñò ýòî êîíå÷íûé íåïóñòîé ñïèñîê ñëîâ. Ñëîâî W íàçûâàåòñÿ ñìåñüþ ñëîâ U è V , åñëèU = U1 U2 äëÿ íåêîòîðûõ ñëîâ U1 è U2 , V = V1 V2 äëÿ íåêîòîðûõ ñëîâ V1 è V2 , è W = U1 V1 U2 V2 . Íàïðèìåð, ñëîâî ¾ëåãåíäà¿ ÿâëÿåòñÿ ñìåñüþ ïàðû ñëîâ ¾ëåä¿ è ¾ãåíà¿. Ïîñòðîèòü ëîãè÷åñêóþ ïðîãðàììó,êîòîðàÿ äëÿ çàäàííîãî òåêñòà L âû÷èñëÿåò áåñïîâòîðíûé ñïèñîê X âñåõ ñëîâ òåêñòà L, íå ÿâëÿþùèõñÿñìåñüþ íèêàêîé ïàðû ñëîâ òåêñòà L. Çàïðîñ ê ïðîãðàììå äîëæåí èìåòü âèä ?G(L, X).Çàäà÷à 0 (6 áàëëîâ).Èñïîëüçóÿ êîíñòàíòíûå, ôóíêöèîíàëüíûå è ïðåäèêàòíûå ñèìâîëû àëôàâèòà(ñì. Ïðèëîæåíèå 1), ïîñòðîèòü çàìêíóòóþ ôîðìóëó ëîãèêè ïðåäèêàòîâ, ñîîòâåòñòâóþùóþ ñëåäóþùåìóóòâåðæäåíèþ.¾Âñÿêàÿ ñõîäÿùàÿñÿ ïîñëåäîâàòåëüíîñòü ïîëîæèòåëüíûõ äåéñòâèòåëüíûõ ÷èñåë ìîíîòîííî âîçðàñòàåò¿Çàäà÷à 1 (3 áàëëà).Äëÿ çàäàííîé ôîðìóëû ϕ âûÿñíèòü, ïðèìåíÿÿ ìåòîä ñåìàíòè÷åñêèõ òàáëèö,ÿâëÿåòñÿ ëè ýòà ôîðìóëà îáùåçíà÷èìîé.Çàäà÷à 2 (3 áàëëà).ϕ = ∀x(P (x, x) → ∀x(R(x) → ∃x(∃xP (x, x) & R(x))))Äëÿ çàäàííîé ôîðìóëû ϕ âûÿñíèòü, ïðèìåíÿÿ ìåòîä ðåçîëþöèé, ÿâëÿåòñÿ ëèýòà ôîðìóëà îáùåçíà÷èìîé.Çàäà÷à 3 (3 áàëëà).(∃y¬P (y) → R(f (c))) → ∀x∃y(P (f (x)) ∨ R(y))Äëÿ çàäàííîãî çàïðîñà G =? A(X, Y ), not(A(X, X)) ê çàäàííîé ëîãè÷åñêîéïðîãðàììå P ïîñòðîèòü íà îñíîâå ñòàíäàðòíîé ñòðàòåãèè âû÷èñëåíèé (ñ èñïîëüçîâàíèåì îïåðàòîðîâîòñå÷åíèÿ è îòðèöàíèÿ) äåðåâî SLD-ðåçîëþòèâíûõ âû÷èñëåíèé è îïðåäåëèòü ìíîæåñòâî âû÷èñëåííûõîòâåòîâ.
Ïðèìå÷àíèå: çàãëàâíûìè áóêâàìè íà÷èíàþòñÿ èìåíà ïåðåìåííûõ è ïðåäèêàòîâ, à ñòðî÷íûìèáóêâàìè èìåíà êîíñòàíò è ôóíêöèé.Çàäà÷à 4 (3 áàëëà).P : A(X, c)A(X, Y )B(g(X))B(X)E(b)←←←←←E(X), !, not(B(X));B(g(X)), E(Y );!, E(g(X));B(g(X));;Ñôîðìóëèðóéòå òåîðåìó î ëîãè÷åñêîì ñëåäñòâèè äëÿ êëàññè÷åñêîé ëîãèêèïðåäèêàòîâ. Âåðíî ëè, ÷òî âñÿêîå ìíîæåñòâî çàìêíóòûõ ôîðìóë èìååò áåñêîíå÷íî ìíîãî ðàçëè÷íûõëîãè÷åñêèõ ñëåäñòâèé?Çàäà÷à 5 (2 áàëëà).Çàäà÷à 6 (2 áàëëà). Ñôîðìóëèðóéòå òåîðåìó î ñêîëåìîâñêîé ñòàíäàðòíîé ôîðìå? Âåðíî ëè, ÷òîåñëè ôîðìóëà ϕ â ïðåäâàðåííîé íîðìàëüíîé ôîðìå ÿâëÿåòñÿ îáùåçíà÷èìîé ôîðìóëîé, òî è ñîîòâåòñòâóþùàÿ åé ñêîëåìîâñêàÿ ñòàíäàðòíàÿ ôîðìà òàêæå áóäåò îáùåçíà÷èìîé ôîðìóëîé?Îïèøèòå àëãîðèòì âû÷èñëåíèÿ íàèáîëåå îáùåãî óíèôèêàòîðà äâóõ àòîìîâè P (s1, s2, .
. . , sn).Çàäà÷à 7 (2 áàëëà).P (t1 , t2 , . . . , tn )×òî íàçûâàåòñÿ äåðåâîì SLD-ðåçîëþòèâíûõ âû÷èñëåíèé çàïðîñà G, îáðàùåííîãî ê õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììå P ? Çàâèñèò ëè óñòðîéñòâî äåðåâà SLD-ðåçîëþòèâíûõ âû÷èñëåíèé îò ïðàâèëà âûáîðà ïîäöåëåé?Çàäà÷à 8 (2 áàëëà).Çàäà÷à 9 (2 áàëëà). Êàê îïðåäåëÿåòñÿ îòíîøåíèå âûïîëíèìîñòè I, t |= ϕUψ â òåìïîðàëüíîé ëîãèêåPLTL? Âåðíî ëè, ÷òî ôîðìóëû ϕU(ψ1 ∨ ψ2) è (ϕUψ1) ∨ (ϕUψ2) ÿâëÿþòñÿ ðàâíîñèëüíûìè ôîðìóëàìèëîãèêè PLTL?Ïðåäïîëîæèì, ÷òî áåñêîíå÷íîå ìíîæåñòâî çàìêíóòûõ ôîðìóë Γ îáëàäàåò òåìñâîéñòâîì, ÷òî äëÿ ëþáîé ôîðìóëû ϕ, ϕ ∈ Γ, ñåìàíòè÷åñêàÿ òàáëèöà hΓ \ {ϕ}, {ϕ}i íå èìååò íè îäíîãîóñïåøíîãî òàáëè÷íîãî âûâîäà.
Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé âñåãäà âåðíû äëÿ óêàçàííîãîìíîæåñòâà Γ ?1. Íå ñóùåñòâóåò óñïåøíîãî òàáëè÷íîãî âûâîäà èç òàáëèöû hΓ, ∅i, ïîòîìó ÷òî...2.  ìíîæåñòâå Γ íåò îáùåçíà÷èìûõ ôîðìóë, ïîòîìó ÷òî...3. Ìíîæåñòâî ôîðìóëà Γ íå èìååò ìîäåëè, ïîòîìó ÷òî...4. Òàêîãî ìíîæåñòâà ôîðìóë Γ, óäîâëåòâîðÿþùåãî óêàçàííûì óñëîâèÿì, íå ñóùåñòâóåò, ïîòîìó÷òî...5. Âñå ïðèâåäåííûå âûøå óòâåðæäåíèÿ â îáùåì ñëó÷àå íåâåðíû.Çàäà÷à 10 (3 áàëëà).Ïóñòü S - ýòî íåêîòîðîå ìíîæåñòâî äèçúþíêòîâ, à [S] - ýòî ìíîæåñòâî âñåõîñíîâíûõ ïðèìåðîâ äèçúþíêòîâ èç ìíîæåñòâà S. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé âñåãäàñïðàâåäëèâû è ïî÷åìó?1.
Åñëè äèçúþíêò D ðåçîëþòèâíî âûâîäèì èç ìíîæåñòâà äèçúþíêòîâ S , òî ýòîò æå äèçúþíêò Dðåçîëþòèâíî âûâîäèì èç ìíîæåñòâà îñíîâíûõ ïðèìåðîâ äèçúþíêòîâ [S], ïîòîìó ÷òî...2. Åñëè äèçúþíêò D ðåçîëþòèâíî âûâîäèì èç ìíîæåñòâà îñíîâíûõ ïðèìåðîâ äèçúþíêòîâ [S], òîýòîò æå äèçúþíêò D ðåçîëþòèâíî âûâîäèì èç ìíîæåñòâà äèçúþíêòîâ S , ïîòîìó ÷òî...3.
Åñëè ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿ ìíîæåñòâà äèçúþíêòîâ S , òî ýòà æåýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿ ìíîæåñòâà îñíîâíûõ ïðèìåðîâ äèçúþíêòîâ[S], ïîòîìó ÷òî...4. Åñëè ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿ ìíîæåñòâà îñíîâíûõ ïðèìåðîâ äèçúþíêòîâ [S], òî ýòà æå ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿ ìíîæåñòâà äèçúþíêòîâ S , ïîòîìó ÷òî...Çàäà÷à 11 (3 áàëëà).Ïóñòü èçâåñòíî, ÷òî ýðáðàíîâñêèé áàçèñ BP õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P ÿâëÿåòñÿ ìîäåëüþ äëÿ ýòîé ïðîãðàììû. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé áóäóò âñåãäàñïðàâåäëèâû è ïî÷åìó?1. Âñÿêèé çàïðîñ, îáðàùåííûé ê ïðîãðàììå P , íå èìååò íè îäíîãî óñïåøíîãî âû÷èñëåíèÿ, ïîòîìó÷òî...2.  ïðîãðàììå P íåò íè îäíîãî ôàêòà, ïîòîìó ÷òî...3.
Òàêîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P íå ñóùåñòâóåò, ïîòîìó ÷òî...4. Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé, âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ âåðíûì, ïîòîìó ÷òî...Çàäà÷à 12 (3 áàëëà).Ïóñòü I ìíîæåñòâî âñåõ ôîðìóë, ÿâëÿþùèõñÿ èíâàðèàíòîì öèêëà.Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ñïðàâåäëèâû è ïî÷åìó?1. Ìíîæåñòâî I âñåãäà ñîäåðæèò áåñêîíå÷íî ìíîãî ðàçëè÷íûõ ôîðìóë, ïîòîìó ÷òî....2. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå âûïîëíèìûå ôîðìóëû, ïîòîìó ÷òî....3. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå îáùåçíà÷èìûå ôîðìóëû, ïîòîìó ÷òî....4.
Ìíîæåñòâî ôîðìóë I âñåãäà ñîäåðæèò ïðåäèêàò P (x), ïîòîìó ÷òî....5. Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé â îáùåì ñëó÷àå íå âåðíî.Çàäà÷à 13 (3 áàëëà).whileP (x)doπod.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
