variant09-01 (Старые варианты экзамена)

ÂàðèàíòÇàäà÷à 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 áàëëà)..