variant09-01 (1158084)
Текст из файла
ÂàðèàíòÇàäà÷à 0 (6 áàëëîâ). Ìíîæåñòâî öåëûõ ÷èñåë íàçûâàåòñÿ ñâîáîäíûì îò ñóìì, åñëè ñóììà ëþáûõ äâóõ ÷èñåë èç ýòîãî ìíîæåñòâà íå ïðèíàäëåæèò óêàçàííîìó ìíîæåñòâó. Ïîñòðîèòü ëîãè÷åñêóþïðîãðàììó, êîòîðàÿ äëÿ çàäàííîãî êîíå÷íîãî ìíîæåñòâà öåëûõ ÷èñåë, ïðåäñòàâëåííîãî ñïèñêîì L, âû÷èñëÿåò ìàêñèìàëüíîå ïî ÷èñëó ýëåìåíòîâ ïîäìíîæåñòâî X , ñâîáîäíîå îò ñóìì. Çàïðîñ ê ïðîãðàììåäîëæåí èìåòü âèä ? G(L, X).Èñïîëüçóÿ êîíñòàíòíûå, ôóíêöèîíàëüíûå è ïðåäèêàòíûå ñèìâîëû àëôàâèòà(ñì. Ïðèëîæåíèå 1), ïîñòðîèòü çàìêíóòóþ ôîðìóëó ëîãèêè ïðåäèêàòîâ, ñîîòâåòñòâóþùóþ ñëåäóþùåìóóòâåðæäåíèþ.¾Íèêàêàÿ îãðàíè÷åííàÿ ïîñëåäîâàòåëüíîñòü äåéñòâèòåëüíûõ ÷èñåë íå èìååò äâóõ ðàçëè÷íûõ ïðåäåëüíûõ òî÷åê¿.Çàäà÷à 1 (3 áàëëà).Äëÿ çàäàííîé ôîðìóëû ϕ âûÿñíèòü, ïðèìåíÿÿ ìåòîä ñåìàíòè÷åñêèõ òàáëèö,ÿâëÿåòñÿ ëè ýòà ôîðìóëà îáùåçíà÷èìîé.Çàäà÷à 2 (3 áàëëà).∃z(∃y¬A(z, y) → ∀xB(x)) → ∀y(B(y) ∨ ∃xA(x, h(x)))Äëÿ çàäàííîé ôîðìóëû ϕ âûÿñíèòü, ïðèìåíÿÿ ìåòîä ðåçîëþöèé, ÿâëÿåòñÿ ëèýòà ôîðìóëà îáùåçíà÷èìîé.Çàäà÷à 3 (3 áàëëà).∃x((∀yP (x, y) ∨ ∃xR(x)) → (∃xP (x, x) ∨ R(x)))Äëÿ çàäàííîãî çàïðîñà G =? P (X, Y ), not(P (X, X)) ê çàäàííîé ëîãè÷åñêîéïðîãðàììå P ïîñòðîèòü íà îñíîâå ñòàíäàðòíîé ñòðàòåãèè âû÷èñëåíèé (ñ èñïîëüçîâàíèåì îïåðàòîðîâîòñå÷åíèÿ è îòðèöàíèÿ) äåðåâî SLD-ðåçîëþòèâíûõ âû÷èñëåíèé è îïðåäåëèòü ìíîæåñòâî âû÷èñëåííûõîòâåòîâ.
Ïðèìå÷àíèå: çàãëàâíûìè áóêâàìè íà÷èíàþòñÿ èìåíà ïåðåìåííûõ è ïðåäèêàòîâ, à ñòðî÷íûìèáóêâàìè èìåíà êîíñòàíò è ôóíêöèé.Çàäà÷à 4 (3 áàëëà).P : P (g(Y ), c)P (g(Y ), X)R(f (X))R(X)Q(b)←←←←←Q(Y ), !, not(R(f (Y )));R(X), Q(Y );Q(X), !, P (X, g(X));;;Êàêîâà ôîðìóëèðîâêà òåîðåìû êîððåêòíîñòè òàáëè÷íîãî âûâîäà äëÿ êëàññè| ∆i÷åñêîé ëîãèêè ïðåäèêàòîâ? Êîððåêòíî ëè ïðàâèëî òàáëè÷íîãî âûâîäà hΓhΓ,| ∀xϕ(x)?∃x¬ϕ(x), ∆iÇàäà÷à 5 (2 áàëëà).Êàê ôîðìóëèðóåòñÿ òåîðåìà êîìïàêòíîñòè Ìàëüöåâà? Ñëåäóåò ëè èç òåîðåìûêîìïàêòíîñòè òåîðåìà Ýðáðàíà?Çàäà÷à 6 (2 áàëëà).Çàäà÷à 7 (2 áàëëà). Êàêîé îòâåò íà çàïðîñ G ê õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììå P íàçûâàåòñÿïðàâèëüíûì? Ñêîëüêî ïðàâèëüíûõ îòâåòîâ ìîæåò èìåòü çàïðîñ G =?A, îáðàùåííûé ê õîðíîâñêîéëîãè÷åñêîé ïðîãðàììå P , â òîì ñëó÷àå, åñëè A îñíîâíîé àòîì?Çàäà÷à 8 (2 áàëëà).
×òî îçíà÷àåò àëãîðèòìè÷åñêàÿ óíèâåðñàëüíîñòü õîðíîâñêîãî ëîãè÷åñêîãî ïðîãðàììèðîâàíèÿ? Âåðíî ëè, ÷òî äëÿ ëþáîé ëîãè÷åñêîé ïðîãðàììû ñ îïåðàòîðàìè îòñå÷åíèÿ è îòðèöàíèÿñóùåñòâóåò òàêàÿ õîðíîâñêàÿ ëîãè÷åñêàÿ ïðîãðàììà (áåç îòñå÷åíèé è îòðèöàíèé), êîòîðàÿ âû÷èñëÿåòòî÷íî òàêîå æå ìíîæåñòâî îòâåòîâ?Êàê îïðåäåëÿåòñÿ îòíîøåíèå âûïîëíèìîñòè I, w |= ϕ â ìîäàëüíîé ëîãèêå?Âåðíî ëè, ÷òî äëÿ ëþáîé ìîäåëè Êðèïêå I è äëÿ ëþáîãî ñîñòîÿíèÿ w åñëè I, w 6|= ¬p, òî I, w |= ♦p ?Çàäà÷à 9 (2 áàëëà).Ïóñòü Γ íåêîòîðîå ìíîæåñòâî çàìêíóòûõ ôîðìóë ëîãèêè ïðåäèêàòîâ.
Âåðíîëè, ÷òî Γ ÿâëÿåòñÿ íåïðîòèâîðå÷èâûì ìíîæåñòâîì òîãäà è òîëüêî òîãäà âñÿêàÿ äèçúþíêöèÿ âèäà¬ϕ1 ∨¬ϕ1 ∨. . .∨¬ϕn , ãäå ϕ1 , ϕ2 , . . . , ϕn ôîðìóëû èç Γ, íå ÿâëÿåòñÿ îáùåçíà÷èìîé. Âàðèàíòû îòâåòîâ:1. Âåðíî, ïîòîìó ÷òî ...2. Íåâåðíî, ïîòîìó ÷òî ...3. Çàâèñèò îò ìíîæåñòâà Γ, è ïîäòâåðæäåíèåì òîìó ñëóæàò äâà ñëåäóþùèõ ïðèìåðà ...Çàäà÷à 10 (3 áàëëà).Ïðåäïîëîæèì, ÷òî â ïðàâèëî ðåçîëþöèè áûëî âíåñåíî ñëåäóþùåå èçìåíåíèå:ðåçîëüâåíòîé äèçúþíêòîâ D1 = D10 ∨L1 è D2 = D20 ∨¬L2 îáúÿâëÿåòñÿ âñÿêèé äèçúþíêò D0 = (D10 ∨D20 )η,ãäå η íåêîòîðûé óíèôèêàòîð (íåîáÿçàòåëüíî íàèáîëåå îáùèé) ëèòåð L1 è L2.
Êàêèå èç ïðèâåäåííûõíèæå óòâåðæäåíèé áóäóò ñïðàâåäëèâû è ïî÷åìó?1. Ïîñëå òàêîãî èçìåíåíèÿ è òåîðåìà êîððåêòíîñòè ðåçîëþòèâíîãî âûâîäà è òåîðåìà ïîëíîòû ðåçîëþòèâíîãî âûâîäà óæå áóäóò íåâåðíû, ïîòîìó ÷òî...2. Ïîñëå òàêîãî èçìåíåíèÿ òåîðåìà êîððåêòíîñòè ðåçîëþòèâíîãî âûâîäà îñòàåòñÿ âåðíîé, à òåîðåìàïîëíîòû ðåçîëþòèâíîãî âûâîäà óæå áóäåò íåâåðíà, ïîòîìó ÷òî...3. Ïîñëå òàêîãî èçìåíåíèÿ òåîðåìà ïîëíîòû ðåçîëþòèâíîãî âûâîäà îñòàåòñÿ âåðíîé, à òåîðåìà êîððåêòíîñòè ðåçîëþòèâíîãî âûâîäà óæå áóäåò íåâåðíà, ïîòîìó ÷òî...4. Ïîñëå òàêîãî èçìåíåíèÿ è òåîðåìà êîððåêòíîñòè ðåçîëþòèâíîãî âûâîäà è òåîðåìà ïîëíîòû ðåçîëþòèâíîãî âûâîäà îñòàþòñÿ âåðíûìè, ïîòîìó ÷òî...Çàäà÷à 11 (3 áàëëà).Çàäà÷à 12 (3 áàëëà).
Ïðåäïîëîæèì, ÷òî íè îäèí îñíîâíîé àòîì íå ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P . Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ñïðàâåäëèâû èïî÷åìó?1. Èíòåðïðåòàöèÿ I = ∅ ÿâëÿåòñÿ ìîäåëüþ ïðîãðàììû P , ïîòîìó ÷òî....2. Ïðîãðàììà P íå èìååò íè îäíîé ìîäåëè, ïîòîìó ÷òî...3. Ëþáàÿ ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ ïðîãðàììû P , ïîòîìó ÷òî...4.
Èñõîäíîå óñëîâèå íåîñóùåñòâèìî, òî åñòü íå ñóùåñòâóåò íè îäíîé òàêîé õîðíîâñêîé ëîãè÷åñêîéïðîãðàììû P , äëÿ êîòîðîé âûïîëíÿëîñü áû óêàçàííîå ïðåäïîëîæåíèå, ïîòîìó ÷òî ...5. Íè îäíî èç óêàçàííûõ óòâåðæäåíèé íå âåðíî, ïîòîìó ÷òî...Èçâåñòíî, ÷òî ôîðìóëà PLTL ϕ èìååò äëèíó n, à êîíå÷íàÿ ìîäåëü (LTS) Mèìååò m ñîñòîÿíèé. Òîãäà ñèñòåìà Õèíòèêêè äëÿ ôîðìóëû ϕ è LTS M ïðåäñòàâëÿåò ñîáîé îðèåíòèðîâàííûé ãðàô, â êîòîðîì ñîäåðæèòñÿ ñàìîå áîëüøåå1. O(nm) âåðøèí, ïîòîìó ÷òî....2. O(mn) âåðøèí, ïîòîìó ÷òî....3. n2O(m) âåðøèí, ïîòîìó ÷òî....4. m2O(n) âåðøèí, ïîòîìó ÷òî....5. 2O(nm) âåðøèí, ïîòîìó ÷òî....Çàäà÷à 13 (3 áàëëà)..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
