20xx - коллок ответы (1162116), страница 2
Текст из файла (страница 2)
Формула ψ не является логическим следствием формулы ϕ, потому что...Задача 10. Известно, что выполнимые замкнутые формулы ϕ и ψ не имеют ни одной общей модели.Какие из приведенных ниже утверждений всегда верны и почему?1. Существует формула χ, логическим следствием которой являются обе формулы ϕ и ψ, потомучто ... χ - false2. Существует формула χ, которая является логическим следствием обеих формул ϕ и ψ, потомучто ...
χ - общезначимаÇàäà÷à 10 (3 áàëëà).Γ1 Γ2ϕΓ1 |= ϕ Γ2 |= ϕÏðåäïîëîæèì, ÷òî äàíû äâà òàêèå ìíîæåñòâà çàìêíóòûõ ôîðìóë è ,äëÿ êîòîðûõ íå ñóùåñòâóåò íè îäíîãî ïðåäëîæåíèÿ , óäîâëåòâîðÿþùåãî îäíîâðåìåííî ñîîòíîøåíèÿìè. Âûáåðèòå òå óòâåðæäåíèÿ, êîòîðûå â ýòîì ñëó÷àå âñåãäà ñïðàâåäëèâû è îáîñíóéòå|= ϕ, ϕ - общнезначимаñäåëàííûé âûáîð.4. Òàêîé ïàðû ìíîæåñòâ Γ1 è Γ2, óäîâëåòâîðÿþùåé ïðåäïîëîæåíèþ, íå ñóùåñòâóåò, ïîòîìó ÷òî ...Çàäà÷à 10 (3 áàëëà). Ïðåäïîëîæèì, ÷òî áåñêîíå÷íîå ìíîæåñòâî çàìêíóòûõ ôîðìóë Γ îáëàäàåò òåìñâîéñòâîì, ÷òî äëÿ ëþáîé ôîðìóëû ϕ, ϕ ∈ Γ, ñåìàíòè÷åñêàÿ òàáëèöà hΓ \ {ϕ}, {ϕ}i íå èìååò íè îäíîãîóñïåøíîãî òàáëè÷íîãî âûâîäà.
Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé âñåãäà âåðíû äëÿ óêàçàííîãîìíîæåñòâà Γ ?иначе при ϕ - общезн. → успешный вывод2.  ìíîæåñòâå Γ íåò îáùåçíà÷èìûõ ôîðìóë, ïîòîìó ÷òî...Задача 10. Пусть известно, что семантическая таблица hΓ, ∅i для классической логики предикатов имееттабличный вывод, одна из ветвей которого заканчивается такой семантической таблицей hΓ0 , ∆0 i, что Γ0 ∩∆0 =∅ и при этом ни одно правило табличного вывода не применимо к таблице hΓ0 , ∆0 i.
Какие из приведенныхниже утверждений наверняка справедливы и почему?имеет модель → ∞ модель2. Множество формул Γ имеет модель с бесконечной предметной областью, потому что...Задача 10 (3 балла). Пусть Γ — некоторое множество замкнутых формул логики предикатов. Верноли, что Γ является непротиворечивым множеством тогда и только тогда всякая дизъюнкция вида¬ϕ1 ∨¬ϕ1 ∨. . .∨¬ϕn , где ϕ1 , ϕ2 , . . . , ϕn — формулы из Γ, не является общезначимой. Варианты ответов:1. Верно, потому что ...
Пусть ϕ - общезн. → <∅,ϕ>, успеш табл вывод. Соответственно<ϕ1…ϕn|∅ > - усп. табл вывод. Получили противоречиеЗадача 11 (3 балла). Пусть задано некоторое непустое множество дизъюнктов S0 . Пусть S1 — этомножество всех формул, резолютивно выводимых из множества дизъюнктов S0 . Какие из приведенныхниже утверждений всегда справедливы и почему?2. Если каждый дизъюнкт множества S1 выполним, то множество дизъюнктов S0 имеет модель,потому что.... не вывели □→ имеет модель3. Если множество дизъюнктов S0 имеет модель, то множество дизъюнктов S1 имеет модель, потомучто....
S0→S1Задача 11 (3 балла). Предположим, что в правило резолюции было внесено следующее изменение:резольвентой дизъюнктов D1 = D10 ∨L1 и D2 = D20 ∨¬L2 объявляется всякий дизъюнкт D0 = (D10 ∨D20 )η,где η — некоторый унификатор (необязательно наиболее общий) литер L1 и L2 . Какие из приведенныхниже утверждений будут справедливы и почему?2. После такого изменения теорема корректности резолютивного вывода остается верной, а теоремаполноты резолютивного вывода уже будет неверна, потому что...Задача 11.
Известно, что из множества непустых дизъюнктов S = {D1 , D2 , . . . , DN } можно построить резолютивный вывод пустого дизъюнкта . Какие из приведенных ниже утверждений всегдасправедливы и почему?Всегда false ______________2. Существует успешный табличный вывод для исходной таблицы T = h{D1 &D2 & . . . &DN }, ∅i, потому что. . . .Çàäà÷à 11 (3 áàëëà).ϕψϕÏðåäïîëîæèì, ÷òî ôîðìóëà èìååò ïðåäâàðåííóþ íîðìàëüíóþ ôîðìó, à ýòî ñîîòâåòñòâóþùàÿ åé ôîðìóëà â ñêîëåìîâñêîé ñòàíäàðòíîé ôîðìå, ïîëó÷åííàÿ â ðåçóëüòàòåïðèìåíåíèÿ ïðîöåäóðû ñêîëåìèçàöèè ê ôîðìóëå .
Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé áóäóòПо теореме о том, что приâñåãäà ñïðàâåäëèâû è ïî÷åìó?2. Ôîðìóëà ϕ → ψ ÿâëÿåòñÿ âûïîëíèìîé, ïîòîìó ÷òî... сколемизации выполнимость3. Ôîðìóëà ψ → ϕ ÿâëÿåòñÿ îáùåçíà÷èìîé, ïîòîìó ÷òî... сохраняется + у пнф моделей больше,4. Ôîðìóëà ψ → ϕ ÿâëÿåòñÿ âûïîëíèìîé, ïîòîìó ÷òî... чем у ссф. 4 следует из 3.Çàäà÷à 11 (3 áàëëà). Ïóñòü S - ýòî íåêîòîðîå ìíîæåñòâî äèçúþíêòîâ, à [S] - ýòî ìíîæåñòâî âñåõîñíîâíûõ ïðèìåðîâ äèçúþíêòîâ èç ìíîæåñòâà S. Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé âñåãäàрв рвñïðàâåäëèâû è ïî÷åìó?S→[S]→D2. Åñëè äèçúþíêò D ðåçîëþòèâíî âûâîäèì èç ìíîæåñòâà îñíîâíûõ ïðèìåðîâ äèçúþíêòîâ [S], òîýòîò æå äèçúþíêò D ðåçîëþòèâíî âûâîäèì èç ìíîæåñòâà äèçúþíêòîâ S , ïîòîìó ÷òî...4.
Åñëè ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿ ìíîæåñòâà îñíîâíûõ ïðèìåðîâ äèçúþíêòîâ [S], òî ýòà æå ýðáðàíîâñêàÿ èíòåðïðåòàöèÿ I ÿâëÿåòñÿ ìîäåëüþ äëÿ ìíîæåñòâà äèçúþíêòîâ S , ïîòîìó ÷òî...Задача 11 (3 балла). Выберите и мотивируйте правильные продолжения следующего утверждения.«Формула ϕ логики предикатов первого порядка выполнима тогда и только тогда, когда...»2. В любом дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i хотя бы одна ветвь завершается аксиомой, потому что ....4. Хотя бы в одном дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i хотя бы однаветвь завершается аксиомой, потому что ....4 следует из 2trueЗадача 11. Предположим, что из системы дизъюнктов S можно резолютивно вывести дизъюнкт P ∨ ¬P .Какие из приведенных ниже утверждений будут всегда верны и почему? резольвента Pv¬P и Q&¬Q - □5.
Ни одно из приведенных выше утверждений в общем случае несправедливо, потому что. . .Задача 11 (3 балла). Пусть A(X) — атом, P — хорновская логическая программа, I — эрбрановскаямодель для логической программы P. Какие из приведенных ниже утверждений всегда справедливыи почему? Все четыре ответа?Задача 12 (3 балла). Пусть P — это хорновская логическая программа. Пусть также известно,что ни один запрос к программе P не имеет успешных SLD-резолютивных вычислений.
Какие изприведенных ниже утверждений будут при этом всегда верны и почему?2. В программе P нет ни одного факта, потому что... P(x) → P(x)Задача 12 (3 балла). Известно, что запрос ? P (x) к программе P имеет успешное SLD-резолютивноеопровержение, в результате которого в качестве ответа вычисляется подстановка {x/f (y)}. Какие изприведенных ниже утверждений будут всегда справедливы, независимо от программы P и атома P (x)и модели I? Ответ обосновать.2. P |= ∃x P (x), потому что...Задача 12. Предположим, что для хорновской логической программы P выполняется соотношениеTP (∅) = ∅, где TP — оператор непосредственного логического следования для программы P. Какие изприведенных ниже утверждений справедливы и почему?3. Любая эрбрановская интерпретация I является моделью программы P, потому что...Задача 12.
Пусть G - запрос к хорновской логической программы P. Какие из приведенных ниже утверждений справедливы и почему?Т. Полноты1. Каждый правильный ответ на запрос G к программе P является вычисленным ответом, потому что...Т корректности2. Каждый вычисленный ответ на запрос G к программе P является правильным ответом, потому что...Задача 12 (3 балла). Пусть ϕ — замкнутая формула логики предикатов, а ψ — ее сколемовскаястандартная форма.
Какие из приведенных ниже утверждений всегда верны и почему?3. Какова бы ни была интерпретация I, если I |= ψ, то I |= ϕ, потому что...4. Если формула ψ общезначима, то ϕ также общезначима, потому что...По теореме о том, что при сколемизации выполнимостьсохраняется + у пнф моделей больше, чем у ссф. 4 следует из 3.Задача 12 (3 балла). Предположим, что ни один основной атом не является логическим следствием хорновской логической программы P. Какие из приведенных ниже утверждений справедливы ипочему?Вечный фейл2. Программа Р не имеет ни одной модели, потому что...Задача 12 (3 балла).
Пусть P0 , P1 и P2 — три хорновские логические программы и при этомP0 = P1 ∪ P2 . Пусть θ — некоторый ответ на запрос G. Какие из приведенных ниже утвержденийверны и почему?4. Ни одно из приведенных выше утверждений в общем случае не является верным, потому что...,объединение программ может использовать правила из любой, в общем случае ни однаиз объединенных может не давать ответаЗадача 13 (3 балла). Какие из приведенных ниже утверждений справедливы и почему?1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычисленаподходящей хорновской логической программы с использованием стандартной стратегииПо Т. Черчавычисления, потому что...Задача 13 (3 балла). Известно, что запрос ? P (x) к логической программе P не имеет успешныхвычислений.
Каким может быть ответ на запрос ?not(P (c)) к логической программе P ? Выберите изпредложенных вариантов ответа на этот вопрос правильные и обоснуйте их.Зациклится4. На запрос ? not(P (c)) может быть вообще не получено никакого ответа, потому что....Задача 13. Из логической программы P (содержащей операторы отсечения и отрицания) с запросомG были удалены все операторы отсечения, в результате чего образовалась новая программа P 0 . Какиеиз приведенных ниже утверждений будут всегда верны и почему? без отсечения больше ответов1. Всякое успешное вычисление запроса G к программе P будет также являться успешным вычислением запроса G к программе P 0 , потому что...3.
Всякий вычислимый ответ на запрос G к программе P будет также являться вычислимым ответомна запрос G к программе P , потому что...Çàäà÷à 13 (3 áàëëà).Iwhile P (x) do π odÏóñòü ìíîæåñòâî âñåõ ôîðìóë, ÿâëÿþùèõñÿ èíâàðèàíòîì öèêëà.Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ñïðàâåäëèâû è ïî÷åìó?1. Ìíîæåñòâî ôîðìóë I âñåãäà íåïóñòî, ïîòîìó ÷òî....4. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå îáùåçíà÷èìûå ôîðìóëû, ïîòîìó ÷òî....Задача 13. Известно, что логическая программа P 0 получена из хорновской логической программы Pв результате применения следующего преобразования: в конце каждого программного утверждения (будьто процедура или факт) D : A0 ← A1 , .
. . , Am был поставлен оператор отсечения так, что образовалосьутверждение D : A0 ← A1 , . . . , Am , !. Какие из приведенных ниже утверждений всегда справедливы ипочему?2. При обращении с любым запросом G к программе P 0 стандартная стратегия вычисления выдасттолько самый первый ответ из тех, которые выдает стандартная стратегия вычисления на запрос G котсечение убивает бэктрекингпрограмме P, потому что...Задача 13 (3 балла).
Докажите, что существует алгоритм, проверяющий общезначимость формуллогики предикатов, предваренная нормальная форма которых имеет видМетод резолюцийКаков этот алгоритм?∀x1 ∀x2 . . . ∀xn ϕ(x1 , x2 , . . . , xn )..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
