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

ÂàðèàíòÏîñòðîèòü ëîãè÷åñêóþ ïðîãðàììó, êîòîðàÿ äëÿ çàäàííîãî êîíå÷íîãî ìíîæåñòâà íàòóðàëüíûõ ÷èñåë, ïðåäñòàâëåííîãî ñïèñêîì 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.