2009 - 2008 Экз. вопросы 2009 ((1-2-4-7-8-9-9.1) 2008 (1-2-3-4) (конкатенация) (1162062), страница 6
Текст из файла (страница 6)
 ïðîãðàììå P íåò íè îäíîãî ôàêòà, ïîòîìó ÷òî...3. Òàêîé õîðíîâñêîé ëîãè÷åñêîé ïðîãðàììû P íå ñóùåñòâóåò, ïîòîìó ÷òî...4. Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé, âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ âåðíûì, ïîòîìó ÷òî...Çàäà÷à 12 (3 áàëëà).Задача 12 (3 балла).
Известно, что запрос ? P (x) к программе P имеет успешное SLD-резолютивноеопровержение, в результате которого в качестве ответа вычисляется подстановка {x/f (y)}. Какие изприведенных ниже утверждений будут всегда справедливы, независимо от программы P и атома P (x)и модели I? Ответ обосновать.1. P |= ∀x P (x), потому что...2. P |= ∃x P (x), потому что...3. P |= ∀y P (f (y)), потому что...4. P |= ∃y P (f (y)), потому что...5. Ни одно из приведенных выше утверждений в общем случае не верно.Задача 12.
Пусть G - запрос к хорновской логической программы P. Какие из приведенных ниже утверждений справедливы и почему?1. Каждый правильный ответ на запрос G к программе P является вычисленным ответом, потому что...2. Каждый вычисленный ответ на запрос G к программе P является правильным ответом, потому что...3. Некоторые (но не все) правильные ответы на запрос G к программе P является вычисленным, потомучто...4. Некоторые (но не все) вычисленные ответы на запрос G к программе P является правильными, потомучто...Задача 12 (3 балла). Пусть P — это хорновская логическая программа. Пусть также известно, чтодля наименьшей эрбрановской модели MP программы P выполняется соотношение MP = ∅.
Какие изприведенных ниже утверждений будут при этом всегда верны и почему?1. Для каждого основного атома A запрос G =?A к программе P имеет хотя бы одно успешноевычисление, потому что...2. Существует основной атом A, для которого запрос G =?A к программе P обязательно имеетуспешное вычисление, потому что...3. Система дизъюнктов S, соответствующих утверждениям программы P, является противоречивой, потому что...4. Такой хорновской логической программы P не существует, потому что...5. Все приведенные выше утверждения, вообще говоря, неверны, потому что...Задача 12 (3 балла). Пусть ϕ — замкнутая формула логики предикатов, а ψ — ее сколемовскаястандартная форма. Какие из приведенных ниже утверждений всегда верны и почему?1.
Если формула ϕ общезначима, то ψ также общезначима, потому что...2. Какова бы ни была интерпретация I, если I |= ϕ, то I |= ψ, потому что...3. Какова бы ни была интерпретация I, если I |= ψ, то I |= ϕ, потому что...4. Если формула ψ общезначима, то ϕ также общезначима, потому что...5. Все приведенные выше утверждения неверны.Задача 12 (3 балла). Предположим, что ни один основной атом не является логическим следствием хорновской логической программы P. Какие из приведенных ниже утверждений справедливы ипочему?1. Интерпретация I = ∅ является моделью программы P, потому что....2.
Программа P не имеет ни одной модели, потому что...3. Любая эрбрановская интерпретация I является моделью программы P, потому что...4. Исходное условие неосуществимо, то есть не существует ни одной такой хорновской логическойпрограммы P, для которой выполнялось бы указанное предположение, потому что ...5. Ни одно из указанных утверждений не верно, потому что...Задача 12 (3 балла). Пусть P0 , P1 и P2 — три хорновские логические программы и при этомP0 = P1 ∪ P2 . Пусть θ — некоторый ответ на запрос G.
Какие из приведенных ниже утвержденийверны и почему?1. Если подстановка θ является правильным ответом на запрос G, обращенный к программе P0 , толибо θ является правильным ответом на запрос G, обращенный к программе P1 , либо θ являетсяправильным ответом на запрос G, обращенный к программе P2 , потому что...2.
Если подстановка θ является правильным ответом на запрос G, обращенный к программе P0 , то θявляется правильным ответом на запрос G, обращенный как к программе P1 , так и к программеP2 , потому что...3. Если подстановка θ является правильным ответом на запрос G, обращенный к программе P0 ,но не является правильным ответом на запрос G, обращенный к программе P1 , то запрос Gθ,обращенный к программе P2 , имеет успешное вычисление, потому что...4. Ни одно из приведенных выше утверждений в общем случае не является верным, потому что...,Задача 13 (3 балла).
Какие из приведенных ниже утверждений справедливы и почему?1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычисленаподходящей хорновской логической программы с использованием стандартной стратегиивычисления, потому что...2. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычисленаподходящей логической программой, но лишь с использованием нестандартной стратегиивычисления, потому что...3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычисленаподходящей логической программы с использованием стандартной стратегии вычисления, нолишь при добавлении операторов is и not, потому что...4. Существуют арифметическая функция, вычислимая на машине Тьюринга, для вычислениякоторой нет логической программы даже в случае использования операторов is и not, потомучто...Задача 13 (3 балла).
Известно, что запрос ? P (x) к логической программе P не имеет успешныхвычислений. Каким может быть ответ на запрос ?not(P (c)) к логической программе P ? Выберите изпредложенных вариантов ответа на этот вопрос правильные и обоснуйте их.1. Ответ на запрос ? not(P (c)) всегда будет положительный независимо от программы P, потомучто....2. Ответ на запрос ? not(P (c)) всегда будет отрицательный независимо от программы P, потомучто....3. Ответ на запрос ? not(P (c)) может быть как положительным, так и отрицательным, взависимости от программы P, потому что.....4. На запрос ? not(P (c)) может быть вообще не получено никакого ответа, потому что....Задача 13.
Из логической программы P (содержащей операторы отсечения и отрицания) с запросомG были удалены все операторы отсечения, в результате чего образовалась новая программа P 0 . Какиеиз приведенных ниже утверждений будут всегда верны и почему?1. Всякое успешное вычисление запроса G к программе P будет также являться успешным вычислением запроса G к программе P 0 , потому что...2. Всякое успешное вычисление запроса G к программе P 0 будет также являться успешным вычислением запроса G к программе P, потому что...3.
Всякий вычислимый ответ на запрос G к программе P будет также являться вычислимым ответомна запрос G к программе P , потому что...4. Всякий вычислимый ответ на запрос G к программе P 0 будет также являться вычислимым ответом на запрос G к программе P, потому что...5. Ни одно из приведенных выше утверждений в общем случае неверно.Ïóñòü I ìíîæåñòâî âñåõ ôîðìóë, ÿâëÿþùèõñÿ èíâàðèàíòîì öèêëà.Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ñïðàâåäëèâû è ïî÷åìó?1. Ìíîæåñòâî ôîðìóë I âñåãäà íåïóñòî, ïîòîìó ÷òî....2. Ìíîæåñòâî ôîðìóë I âñåãäà ñîäåðæèò ïðåäèêàò P (x), ïîòîìó ÷òî....3. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå âûïîëíèìûå ôîðìóëû, ïîòîìó ÷òî....4. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå îáùåçíà÷èìûå ôîðìóëû, ïîòîìó ÷òî....5.
Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé â îáùåì ñëó÷àå íå âåðíî, ïîòîìó ÷òî...Çàäà÷à 13 (3 áàëëà).whileP (x)doπodÏóñòü I ìíîæåñòâî âñåõ ôîðìóë, ÿâëÿþùèõñÿ èíâàðèàíòîì öèêëà.Êàêèå èç ïðèâåäåííûõ íèæå óòâåðæäåíèé ñïðàâåäëèâû è ïî÷åìó?1. Ìíîæåñòâî I âñåãäà ñîäåðæèò áåñêîíå÷íî ìíîãî ðàçëè÷íûõ ôîðìóë, ïîòîìó ÷òî....2. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå âûïîëíèìûå ôîðìóëû, ïîòîìó ÷òî....3. Ìíîæåñòâî ôîðìóë I ñîäåðæèò âñå îáùåçíà÷èìûå ôîðìóëû, ïîòîìó ÷òî....4. Ìíîæåñòâî ôîðìóë I âñåãäà ñîäåðæèò ïðåäèêàò P (x), ïîòîìó ÷òî....5. Íè îäíî èç ïðèâåäåííûõ âûøå óòâåðæäåíèé â îáùåì ñëó÷àå íå âåðíî.Çàäà÷à 13 (3 áàëëà).whileP (x)doπodЗадача 13 (3 балла). Какие из приведенных ниже утверждений справедливы и почему?1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей хорновской логической программы с использованием стандартной стратегии вычисления, потому что...2.
Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой, но лишь с использованием нестандартной стратегии вычисления, потому что...3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программы с использованием стандартной стратегии вычисления, но лишьпри добавлении операторов is и not, потому что...4. Существуют арифметическая функция, вычислимая на машине Тьюринга, для вычисления которой нет логической программы даже в случае использования операторов is и not, потому что...Задача 13.
Известно, что логическая программа P 0 получена из хорновской логической программы Pв результате применения следующего преобразования: в конце каждого программного утверждения (будьто процедура или факт) D : A0 ← A1 , . . . , Am был поставлен оператор отсечения так, что образовалосьутверждение D : A0 ← A1 , . .
. , Am , !. Какие из приведенных ниже утверждений всегда справедливы ипочему?1. При обращении с любым запросом G к программе P 0 стандартная стратегия вычисления выдаст те жесамые ответы, что и при обращении с запросом G к программе P, потому что...2. При обращении с любым запросом G к программе P 0 стандартная стратегия вычисления выдасттолько самый первый ответ из тех, которые выдает стандартная стратегия вычисления на запрос G кпрограмме P, потому что...3.
При обращении с любым запросом G к программе P 0 стандартная стратегия вычисления выдаст толькосамый последний ответ из тех, которые выдает стандартная стратегия вычисления на запрос G кпрограмме P, потому что...4. Ни одно из приведенных выше утверждений в общем случае неверно, потому что...Задача 13 (3 балла). Какие из приведенных ниже утверждений справедливы и почему?1.
Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей хорновской логической программы с использованием стандартной стратегии вычисления, потому что...2. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой, но лишь с использованием нестандартной стратегии вычисления, потому что...3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программы с использованием стандартной стратегии вычисления, но лишьпри добавлении операторов is и not, потому что...4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
