2009 экзамен вариант 8 (Старые варианты экзамена)

PDF-файл 2009 экзамен вариант 8 (Старые варианты экзамена), который располагается в категории "к экзамену/зачёту" в предмете "математическая логика и логическое программирование" изседьмого семестра. 2009 экзамен вариант 8 (Старые варианты экзамена) - СтудИзба 2019-09-18 СтудИзба

Описание файла

Файл "2009 экзамен вариант 8" внутри архива находится в следующих папках: Старые варианты экзамена, Варианты экзамена 2009. PDF-файл из архива "Старые варианты экзамена", который расположен в категории "к экзамену/зачёту". Всё это находится в предмете "математическая логика и логическое программирование" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст из PDF

ÂàðèàíòÑëîâî ýòî êîíå÷íûé íåïóñòîé ñïèñîê áóêâ ôèêñèðîâàííîãî êîíå÷íîãî àëôàâèòà. Òåêñò ýòî êîíå÷íûé íåïóñòîé ñïèñîê ñëîâ. Ñëîâî 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.

Свежие статьи
Популярно сейчас