2009 экзамен вариант 7 (1162067)
Текст из файла
ÂàðèàíòÏîñòðîèòü ëîãè÷åñêóþ ïðîãðàììó, êîòîðàÿ äëÿ çàäàííîãî êîíå÷íîãî ìíîæåñòâà íàòóðàëüíûõ ÷èñåë, ïðåäñòàâëåííîãî ñïèñêîì L, âû÷èñëÿåò ìàêñèìàëüíîå ïî ÷èñëó ýëåìåíòîâïîäìíîæåñòâî ÷èñåë X , êðàòíûõ îäíîìó è òîìó æå ÷èñëó èç ýòîãî æå ïîäìíîæåñòâà X . Çàïðîñ êïðîãðàììå äîëæåí èìåòü âèä ? G(L, X).Çàäà÷à 0 (6 áàëëîâ).Èñïîëüçóÿ êîíñòàíòíûå, ôóíêöèîíàëüíûå è ïðåäèêàòíûå ñèìâîëû àëôàâèòà(ñì. Ïðèëîæåíèå 1), ïîñòðîèòü çàìêíóòóþ ôîðìóëó ëîãèêè ïðåäèêàòîâ, ñîîòâåòñòâóþùóþ ñëåäóþùåìóóòâåðæäåíèþ.¾Íå âñÿêàÿ ïðåäåëüíàÿ òî÷êà ïðîèçâîëüíîé ñõîäÿùåéñÿ ïîñëåäîâàòåëüíîñòè äåéñòâèòåëüíûõ ÷èñåëÿâëÿåòñÿ ïðåäåëîì ýòîé ïîñëåäîâàòåëüíîñòè¿.Çàäà÷à 1 (3 áàëëà).Äëÿ çàäàííîé ôîðìóëû ϕ âûÿñíèòü, ïðèìåíÿÿ ìåòîä ñåìàíòè÷åñêèõ òàáëèö,ÿâëÿåòñÿ ëè ýòà ôîðìóëà îáùåçíà÷èìîé.Çàäà÷à 2 (3 áàëëà).ϕ = ∀x(¬∃yP (x, y) ∨ R(x)) → ∃x∃y(P (x, y) → R(x))Äëÿ çàäàííîé ôîðìóëû ϕ âûÿñíèòü, ïðèìåíÿÿ ìåòîä ðåçîëþöèé, ÿâëÿåòñÿ ëèýòà ôîðìóëà îáùåçíà÷èìîé.Çàäà÷à 3 (3 áàëëà).∃z(∃y¬A(z, y) → ∀xB(x)) → ∀y(B(y) ∨ ∃xA(x, h(x)))Äëÿ çàäàííîãî çàïðîñà G =? P (Y, X), 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));;;Êàêîâà ôîðìóëèðîâêà òåîðåìû ïîëíîòû òàáëè÷íîãî âûâîäà äëÿ êëàññè÷åñêîéëîãèêè ïðåäèêàòîâ? ×òî ìîæíî ñêàçàòü î âûïîëíèìîñòè ôîðìóëû ϕ, åñëè èçâåñòíî, ÷òî îáå ñåìàíòè÷åñêèå òàáëèöû h{ϕ}, ∅i è h∅, {ϕ}i íå èìåþò óñïåøíîãî òàáëè÷íîãî âûâîäà?Çàäà÷à 5 (2 áàëëà).Ñôîðìóëèðîâàòü îïðåäåëåíèå ýðáðàíîâñêîé èíòåðïðåòàöèè çàäàííîé ñèãíàòóðû σ. Ññêîëüêî èìååòñÿ ðàçëè÷íûõ èíòåðïðåòàöèé ñèãíàòóðû σ, â êîòîðîé Const = {c1, c2}, F unc =∅, P red = {P (2) }?Çàäà÷à 6 (2 áàëëà).Ñôîðìóëèðóéòå îïðåäåëåíèå SLD-ðåçîëþòèâíîãî âû÷èñëåíèÿ çàäàííîãî çàïðîñà G, îáðàùåííîãî ê õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììå P .
Ñóùåñòâóþò ëè òàêèå õîðíîâñêèå ëîãè÷åñêèåïðîãðàììû, êîòîðûå íå èìåþò íè îäíîãî óñïåøíîãî SLD-ðåçîëþòèâíîãî âû÷èñëåíèÿ íè äëÿ êàêèõ çàïðîñîâ?Çàäà÷à 7 (2 áàëëà).Ñôîðìóëèðóéòå òåîðåìó ñèëüíîé ïîëíîòû äëÿ õîðîíîâñêèõ ëîãè÷åñêèõ ïðîãðàìì? Ñîõðàíÿåò ëè ýòà òåîðåìà ñïðàâåäëèâîñòü äëÿ ëîãè÷åñêèõ ïðîãðàìì, ñîäåðæàùèõ îïåðàòîðnot?Çàäà÷à 8 (2 áàëëà).Êàê â èíòóèöèîíèñòñêîé ëîãèêå îïðåäåëÿåòñÿ îòíîøåíèå âûïîëíèìîñòè I, w |=äëÿ èìïëèêàòèâíîé ôîðìóëû? Óêàæèòå, êàêèå èç ôîðìóë p ∨ ¬p è p → p ÿâëÿþòñÿ îáùåçíà÷èìûìè ôîðìóëàìè èíòóèöèîíèñòñêîé ëîãèêè?Çàäà÷à 9 (2 áàëëà).ϕ→ψÏðåäïîëîæèì, ÷òî äàíû äâà òàêèå ìíîæåñòâà çàìêíóòûõ ôîðìóë Γ1 è Γ2,äëÿ êîòîðûõ íå ñóùåñòâóåò íè îäíîãî ïðåäëîæåíèÿ ϕ, óäîâëåòâîðÿþùåãî îäíîâðåìåííî ñîîòíîøåíèÿìΓ1 |= ϕ è Γ2 |= ϕ.
Âûáåðèòå òå óòâåðæäåíèÿ, êîòîðûå â ýòîì ñëó÷àå âñåãäà ñïðàâåäëèâû è îáîñíóéòåñäåëàííûé âûáîð.1. Γ1 ∩ Γ2 = ∅, ïîòîìó ÷òî ...2. Γ1 = ∅ èëè Γ2 = ∅, ïîòîìó ÷òî ...3. Îáà ìíîæåñòâà Γ1 è Γ2 íåïðîòèâîðå÷èâû, ïîòîìó ÷òî ...4. Òàêîé ïàðû ìíîæåñòâ Γ1 è Γ2, óäîâëåòâîðÿþùåé ïðåäïîëîæåíèþ, íå ñóùåñòâóåò, ïîòîìó ÷òî ...5. Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé â îáùåì ñëó÷àå íå âåðíî, ïîòîìó ÷òî...Çàäà÷à 10 (3 áàëëà).Ïðåäïîëîæèì, ÷òî ôîðìóëà ϕ èìååò ïðåäâàðåííóþ íîðìàëüíóþ ôîðìó, à ýòî ñîîòâåòñòâóþùàÿ åé ôîðìóëà â ñêîëåìîâñêîé ñòàíäàðòíîé ôîðìå, ïîëó÷åííàÿ â ðåçóëüòàòåïðèìåíåíèÿ ïðîöåäóðû ñêîëåìèçàöèè ê ôîðìóëå ϕ. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé áóäóòâñåãäà ñïðàâåäëèâû è ïî÷åìó?1.
Ôîðìóëà ϕ → ψ ÿâëÿåòñÿ îáùåçíà÷èìîé, ïîòîìó ÷òî...2. Ôîðìóëà ϕ → ψ ÿâëÿåòñÿ âûïîëíèìîé, ïîòîìó ÷òî...3. Ôîðìóëà ψ → ϕ ÿâëÿåòñÿ îáùåçíà÷èìîé, ïîòîìó ÷òî...4. Ôîðìóëà ψ → ϕ ÿâëÿåòñÿ âûïîëíèìîé, ïîòîìó ÷òî...5. Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé â îáùåì ñëó÷àå íå âåðíî, ïîòîìó ÷òî...Çàäà÷à 11 (3 áàëëà).ψÏðåäïîëîæèì, ÷òî çàïðîñ G1 = ?C1, îáðàùåííûé ê õîðíîâñêîé ëîãè÷åñêîéïðîãðàììå P , èìååò âû÷èñëåííûé îòâåò θ1, à çàïðîñ G2 = ?C2, îáðàùåííûé ê òîé æå ñàìîé õîðíîâñêîéëîãè÷åñêîé ïðîãðàììå P , èìååò âû÷èñëåííûé îòâåò θ2. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèéñïðàâåäëèâû è ïî÷åìó?1.
Çàïðîñ G = ?C1, C2, îáðàùåííûé ê ïðîãðàììå P , îáÿçàòåëüíî èìååò ïðàâèëüíûé îòâåò η = θ2θ1,ïîòîìó ÷òî....2. Çàïðîñ G = ?C1, C2, îáðàùåííûé ê ïðîãðàììå P , îáÿçàòåëüíî èìååò ïðàâèëüíûé îòâåò η = θ1θ2,ïîòîìó ÷òî....3. Âîçìîæíî, ÷òî çàïðîñ G = ?C1, C2, îáðàùåííûé ê ïðîãðàììå P , âîîáùå íå èìååò ïðàâèëüíûõîòâåòîâ, è ïðèìåð òàêîâ....4.
Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé â îáùåì ñëó÷àå íå âåðíî, ïîòîìó ÷òî...Çàäà÷à 12 (3 áàëëà).Çàäà÷à 13 (3 áàëëà).Ïóñòü I ìíîæåñòâî âñåõ ôîðìóë, ÿâëÿþùèõñÿ èíâàðèàíòîì öèêëàP (x) do π od.Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ñïðàâåäëèâû è ïî÷åìó?1. Ìíîæåñòâî ôîðìóë I âñåãäà íåïóñòî, ïîòîìó ÷òî....2. Ìíîæåñòâî ôîðìóë I âñåãäà ñîäåðæèò ïðåäèêàò P (x), ïîòîìó ÷òî....3. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå âûïîëíèìûå ôîðìóëû, ïîòîìó ÷òî....4. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå îáùåçíà÷èìûå ôîðìóëû, ïîòîìó ÷òî....5. Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé â îáùåì ñëó÷àå íå âåðíî, ïîòîìó ÷òî...while.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
