год назад Захаров на консультации про попавших на пересдачу говорил, что они будут как Алиса: чем дальше, тем интереснее и чудесатее 13) Существует ли алгоритм, позволяющий для любой формулы, П.Н.Ф. которой имеет вид Аx1Ax2...Axn(M(x1,...xn)) определить, является она общезначимой или нет? (Ax1 = для любого x1, M(x1,...xn) - К.Н.Ф. без кванторов.) Ответ: да, существует. При построении С.С.Ф. таких функций вместо x1,...xn будут константы -> алгоритм конечен. 8)Какая подстановка является композицией подстановок {x/y} , {y/z}, {z/u}, {u/x} ? 1. композиция подстановок {x/y} и {y/z} - {x/z, y/z} 2. {x/z, y/z}, {z/u} - {x/u, y/u, z/u} 3.{x/u, y/u, z/u} , {u/x} - {y/x, z/x, u/x} 4) Существует ли выполнимая таблица, все формулы которой противоречивы? Ответ: да, существует : <0|false> -------------------------------------------- 1) Системы дизъюнктов S1 и S2 непротиворечивы. И дальше серия вариантов про противоречивость/выполнимость их пересечения и объединения 2) Что такое минимальное предусловие и написать его для конкретного примера (что-то вроде if x > 1 then x2 = x1 - 2 else x2 = x1 - 3 с постусловием x > 0 - за правильность не ручаюсь) 3) Теорема Сколема-Ловенгейма. И вопрос про формулу с предметной областью рациональных чисел 4) Таблица не имеет успешного вывода (фи и пси - замкнутые). Что про них можно сказать (противоречивость, выполнимость, может ли одна быть следствием другой) 5) Есть модель I для программы P. И серия вопросов: а вот если I |= phi или не следует, то будет ли фи правильным ответом и в обратную сторону и что-то в этом роде про другие ситуации -------------------------------------------- 5) Логическое следствие. Пример формулы, не явл. логическим следствием {тут была система формул - ложная}. Ответ - не существует такой формулы, так как из false следуют все формулы. 6) Эрбрановская интерпретация для данной сигнатуры. Сколько существует различных эрбрановских интерпретаций, если в сигнатуре задана одна константа и один предикат. Ответ - две, в одной предикат выполним, в другой нет. 7) SLD-резолютивное вычисление. Известно, что формула (для любого x)P(x) верна. Существует ли хотя бы один sld-рез. ответ для ?P(x)P(f(y)). Ответ - да. 8) Полная стратегия выбора. Пример полной стратегии. 9) Определение выводимости для формулы gUh. Является ли выполнимой формула (что-то)U(что-то) -> Gp. Ответ - нет. 10)Про ПНФ и эрбрановской интерпретации для нее. Надо вспомнить лемму или теорему - система дизъюнктов выполнима тогда и только тогда, когда существует хотя бы одна эрбрановская интерпретация. Потом приводите систему дизъюнктов к ПНФ и все. Там было три правильных ответа. 11)Про пересечение моделей для системы дизъюнктов. Там был фокус в том, что теорема о пересечении эрбрановских моделей в системе дизънктов не работает. 12)Про пересечение всех эрбрановских моделей, которое равно Succ(p) и то, что это множество вложено в любую модель. 13)Какая-то фишка в разрешимостью формулы, в которой все кванторы существования. Ответ - существует. Как док-ся - не знаю. Вроде что-то там можно каким-то методом сделать. ---------------------------------------------- Задача на прологе. Есть слова и есть словарь (список слов) L. Надо в словари X и Y занести слова из L так, чтобы в каждом из них были слова, не имеющие общих букв со словами другого словаря. Запрос в виде ?G(L, X, Y). ---------------------------------------------- Задача 1: Любая расходящаяся последовательность ограничена сверху. Ответ: Любая ограниченная последовательность не может иметь двух различных предельных точек. ---------------------------------------------- 0. Выделить максимальное по включению множество X, свободное от сумм, из множества L. Свободное от сумм множество - это такое, в котором ни один элемент не является суммой двух элементов. 1. Построить формулу "Ни одна ограниченная последовательность действительных чисел не имеет 2 различных предельных точек". 5. Сформулировать теорему компактности Мальцева. Следует ли из нее теорема Эрбрана? (Ответ: да) 6. Что означает алгоритмическая полнота логических программ? Верно ли, что для любой логической программы всегда можно построить другую без операторов отрицания и отсечения, вычисляющую те же правильные ответы? (Ответ: да) 7. Дайте определение правильного ответа на запрос к программе. Какие правильные ответы могут быть на запрос, состоящий из основных атомов? (Ответ: либо один ответ ? (пустая подстановка), либо ни одного) 11. Верно ли что система формул S? = {?1, ..., ?n} противоречива тогда и только тогда, когда формула ¬?1 ? ... ? ¬?n общезначима? (Ответ: да, верно; формула в условии равносильна формуле ? = ¬(?1 & ... & ?n), которая общезначима тогда и только тогда, когда противоречива система формул, входящих в КНФ, а эта система совпадает с S?) 8. Определение корректности табличного вывода. Корректно ли правило вывода <там в первом было слева существует х f(x), а во втором справа - для любого х не f(x)> 9. Определение выполнимости в модальной логике для формулы <квадрат phi>. И еще был очевидный вопрос про две равносильных формулы в этой логике. 12. В резолютивном выводе на каждом шаге берется не НОУ, а произвольный унификатор. Верны ли теоремы корректности и полноты? 13. Кажется так: из программы не следует ни один основной атом. Что можно сказать о модели для этой программы (она существует, пустая подходит, не любая подходит) 14. Что-то про сложность графа для какой-то системы (из последней лекции). Там было про вектор длины n и m состояний, поэтому я ответил O(m^n). ----------------------------------------------- 4) P1, P2 - хороновские логические программы, P - их объединение. - если teta правильный ответ на запрос G к P, то teta - правильный ответ на запрос G к P1 или к P2. - если teta правильный ответ на запрос G к P, то teta - правильный ответ на запрос G к P1 и к P2. - еще 1 не помню - все неверные. ----------------------------------------------- 0) Слово W называется смесью слов V=V1V2 и U=U1U2, если оно имеет вид V1U1V2U2. составить бесповторный список из всех слов списка L, которые не являются смесью других слов этого списка. 1) Любая сходящаяся последовательность положительных чисел монотонно возрастает. 5) Теорема о логическом следствии. [вторую часть не помню, но кажется так] верно ли, что у любого множества замкнутых формул бесконечно много логических следствий. 6) Написать алгоритм поиска НОУ для P(s1,..,sn) и P(x1,...,xn) 7) Выполнимость фиUпси в PLTL. Равносильны ли формулы [фиU(пси1 ИЛИ пси2)] и [(фиUпси1) ИЛИ (фиUпси2)] 8) Определение дерева SLD-вычислений. Как влияет на дерево правило выбора подцелей. 9) Теорема о ССФ. Верно ли, что если ПНФ фи общезначима, то ССФ фи также общезначима. [для задач 10-13 помню только заголовок ] 10) Есть множество формул Г. для каждой формулы фи этого множества таблица <Г/фи | фи> не имеет ни одного успешного вывода. 11) Множество дизъюнктов S и множество основных примеров [S]. и варианты - 1)если из S выводим D, то D выводим и из [S] 2)если из [S] выводим D, то D выводим и из S 3)если I модель для S, то I модель для [S] 4)если I модель для [S], то I модель для S 12) Моделью для лог. программы является эрбрановский базис. 1) ни один запрос не имеет успешных вычислений 2) в программе нет фактов что-то еще 13) Есть цикл while P(x) do ... od. и пусть I - множество всех инвариантов цикла. Вопрос про то, что будет верно для этого множества. -----------------------------------------------