Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Сборник задач для самостоятельных занятий

Сборник задач для самостоятельных занятий, страница 3

PDF-файл Сборник задач для самостоятельных занятий, страница 3 Математическая логика и логическое программирование (53211): Другое - 7 семестрСборник задач для самостоятельных занятий: Математическая логика и логическое программирование - PDF, страница 3 (53211) - СтудИзба2019-09-18СтудИзба

Описание файла

PDF-файл из архива "Сборник задач для самостоятельных занятий", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 3 страницы из PDF

Γ2 = { ∀x ¬R(x, x), ∀y∃x R(y, x), ∀x∀y∀z (R(x, y)&R(y, z) → R(x, z)) }.Упражнение 1.31. Пусть ϕ(x) — формула логики предикатов, не содержащая константыc. Докажите, что формула ∀x ϕ(x) является общезначимой тогда и только тогда, когда общезначима формула ϕ(c). Остается ли это утверждение справедливым и в том случае, когдаконстанта c содержится в формуле ϕ(x)?Упражнение 1.32. Известно, что некоторая модель для формулы ϕ не является моделью для формулы ψ.

Какие из приведенных ниже утверждений всегда верны для любыхзамкнутых формул ϕ и ψ ?1. Не существует успешного табличного вывода из таблицы T 0 = h ψ | ϕ i;12Глава 1. УПРАЖНЕНИЯ2. Не существует успешного табличного вывода из таблицы T = h ϕ | ψ i;3. Формула ϕ является логическим следствием формулы ψ;4. Формула ψ является логическим следствием формулы ϕ.Упражнение 1.33. Известно, что для семантической таблицы T = h ϕ | ψ i нельзя построить ни одного успешного табличного вывода.

Какие из приведенных ниже утвержденийвсегда верны для любых замкнутых формул ϕ и ψ?1. Таблица T = h ϕ | ψ i не является выполнимой;2. Для таблицы T 0 = h ψ | ϕ i также не существует ни одного успешного табличного вывода;3. Формула ϕ не является логическим следствием формулы ψ;4. Формула ψ не является логическим следствием формулы ϕ;Упражнение 1.34. Выберите и обоснуйте правильные варианты продолжения следующегоутверждения.

«Формула ϕ логики предикатов первого порядка выполнима тогда и толькотогда, когда...»1. в любом дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i каждая ветвьзавершается закрытой таблицей;2. В любом дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i хотя бы однаветвь завершается закрытой таблицей;3.

Хотя бы в одном дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i каждаяветвь завершается закрытой таблицей;4. Хотя бы в одном дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i хотя быодна ветвь завершается закрытой таблицей.Упражнение 1.35. Пусть известно, что множество замкнутых формул Γ не имеет модели.Какие из приведенных ниже утверждений справедливы и почему?1. Существует успешный табличный вывод для исходной таблицы T = hΓ, ∅i;2.

Существует успешный табличный вывод для исходной таблицы T = h∅, Γi;3. Не существует успешного табличного вывода для исходной таблицы T = hΓ, ∅i;4. Не существует успешного табличного вывода для исходной таблицы T = h∅, Γi.Упражнение 1.36. Пусть известно, что множество предложений Γ не имеет ни одноймодели, предметной областью которой являются строки конечной длины, состоящие из 0 и1. Может ли в этом случае множество предложений Γ быть непротиворечивым?Упражнение 1.37. Докажите, что множество предложений Γ непротиворечиво тогда итолько тогда, когда непротиворечиво каждое конечное подмножество Γ0 , Γ0 ⊆ Γ.1.5. Равносильные формулы и нормальные формы13Упражнение 1.38. Пусть Γ — некоторое множество замкнутых формул логики предикатов. Верно ли, что Γ является непротиворечивым множеством тогда и только тогда всякаядизъюнкция вида ¬ϕ1 ∨ ¬ϕ1 ∨ · · · ∨ ¬ϕn , где ϕ1 , ϕ2 , .

. . , ϕn — формулы из Γ, не являетсяобщезначимой?Упражнение 1.39. Пусть известно, что Γ — это некоторое непустое множество логическихследствий замкнутой формулы ϕ. Пусть также известно, что множество формул Γ не имеет ни одной модели с конечной или счетно-бесконечной областью интерпретации. Какие изприведенных ниже утверждений неверны и почему?1. Формула ϕ не имеет ни одной модели с конечной или счетно-бесконечной областьюинтерпретации.2.

Формула ϕ не имеет вообще ни одной модели.3. Любая формула ψ является логическим следствие формулы ϕ.Упражнение 1.40. Докажите, что в том случае, когда семантическая таблица T = h Γ | ∆ iсостоит из бескванторных формул, любой табличный вывод для T является конечным. Будет ли это утверждение верным и в том случае, когда все формулы таблицы T содержит всовокупности не более одного квантора?1.5Равносильные формулы и нормальные формыУпражнение 1.41. Две формулы ϕ и ψ называются равновыполнимыми, если для любой интерпретации I формула ϕ выполнима в интерпретации I в том и только тоим случае,когда формула ψ выполнима в I.

Докажите замкнутые формулы ϕ и ψ являются равновыполнимыми тогда и только тогда, когда они равносильны. Остаенется ли это утверждениесправедливым и для произвольных формул?Упражнение 1.42. Каково множество формул, равносильных общезначимой формуле ϕ?Упражнение 1.43. Используя правила равносильных преобразований формул, привестиследующие формулы к предваренной нормальной форме.∃x∀y P (x, y) & ∀x∃y P (y, x);∀x ((∃y P (y, x) → ∃y P (x, y)) → Q(x)) → ∃x Q(x);¬∀y(∃xP (x, y) → ∀u(R(y, u) → ¬∀z(P (z, u) ∨ ¬R(z, y))));∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x));∃x∀y (P (x, y) → (¬P (y, x) → (P (x, x) ≡ P (y, y))));∃x(∀xP (x, x) ∨ ∃x¬R(x)) → ∃x(R(x) → ∃yP (f (x), y)).Упражнение 1.44.

Предложите алгоритм, который для любой замкнутой формулы ϕстроит равносильную ПНФ за время O(N ), где N — длина формулы ϕ.14Глава 1. УПРАЖНЕНИЯУпражнение 1.45. Приведите пример замкнутой формулы, любая ПНФ которой имееткванторную приставку, состоящую из чередующихся кванторов всеобщности и существования. Докажите, что никакие равносильные преобразования формул не могут устранить эточередование.Упражнение 1.46. Существуют ли такие формулы, предваренные нормальные формыкоторых имеют разные кванторные приставки? Каким условиям должна удовлетворять замкнутая формула, для того чтобы любая ее ПНФ имела одну и ту же (с точностью до переименования переменных) кванторную приставку.Упражнение 1.47.

Известно, что замкнутая формула ϕ равносильна формуле ψ. Какиеиз приведенных ниже утверждений верны и почему?1. Всякое логическое следствие формулы ϕ является логическим следствием формулы ψ.2. Всякая модель формулы ϕ является моделью формулы ψ.3. Формулы ϕ и ψ имеют одинаковую предваренную нормальную форму.4.

Формула ϕ общезначима тогда и только тогда, когда общезначима формула ψ.Упражнение 1.48. Используя правило сколемизации, постройте сколемовские стандартные формы для следующих формул.∀x∃y∀z∃uR(x, y, z, u);¬∀x(∃yR(x, y) → ∀zP (z, x));¬∀y(∃xP (x, y) → ∀u(R(y, u) → ¬∀z(P (z, u) ∨ ¬R(z, y))));∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x));∃x∀y (P (x, y) → (¬P (y, x) → (P (x, x) ≡ P (y, y))));∃x(∀xP (x, x) ∨ ∃x¬R(x)) → ∃x(R(x) → ∃yP (f (x), y)).Упражнение 1.49.

Пусть известно, что формула ϕ0 является ССФ для формул ψ1 и ψ2 .Верно ли, что в этом случае формулы ψ1 и ψ2 совершенно одинаковы?Упражнение 1.50. Пусть известно, что формула ϕ представлена в ПНФ, а формула ψявляется ССФ, соответствующей формуле ϕ.

Какие из приведенных ниже утверждений верныи почему?1. Если формула ψ невыполнима, то и формула ϕ также невыполнима, потому что....2. Если формула ψ выполнима, то и формула ϕ также выполнима, потому что....3. Если формула ϕ общезначима, то и формула ψ также общезначима, потому что....4. Если формула ψ общезначима, то и формула ϕ также общезначима, потому что....Упражнение 1.51. Пусть известно, что формула ϕ представлена в ПНФ, а формула ψявляется ССФ, соответствующей формуле ϕ. Являются ли формулы ϕ и ψ равносильными?Является ли общезначимой формула ϕ → ψ? Является ли общезначимой формула ψ → ϕ?1.6.

Эрбрановские интерпретации. Теорема Эрбрана1.615Эрбрановские интерпретации. Теорема ЭрбранаУпражнение 1.52. При каких условиях эрбрановский универсум сигнатуры σ являетсяконечным множеством?Упражнение 1.53. Верно ли, что всякая формула ϕ является общезначимой тогда и толькотогда, когда ϕ истинна во всех эрбрановских интерпретациях?Упражнение 1.54.

Верно ли, что всякая формула ϕ сигнатуры σ является выполнимойтогда и только тогда, когда ϕ выполнима в некоторой эрбрановской интерпретации сигнатурыσ?Упражнение 1.55. Пусть ϕ — формула логики предикатов сигнатуры σ, представленная всколемовской стандартной форме. Какие из приведенных ниже утверждений верны и почему?1. Если формула ϕ выполнима, то ϕ выполнима хотя бы в одной эрбрановской интерпретации сигнатуры σ,2.

Если формула ϕ выполнима хотя бы в одной эрбрановской интерпретации сигнатуры σ,то формула ϕ выполнима.3. Если формула ϕ выполнима в каждой эрбрановской интерпретации сигнатуры σ, тоформула ϕ общезначима.4. Если формула ϕ не имеет эрбрановских моделей, то формула ϕ не имеет никаких моделей.Упражнение 1.56. Каждая эрбрановская интерпретация I сигнатуры полностью определяется множеством всех тех основных атомов сигнатуры σ, которые выполняются в интерпретации I. В последующих упражнениях будет использоваться теоретико-множественныйспособ представления эрбрановских интерпретаций, при котором эрбрановская интерпретация I отождествляется с тем множеством основных атомов, которые в ней выполняются,т. е.I = {A : A ∈ Bσ , I |= A}.Предположим, что замкнутая формула ϕ имеет эрбрановские модели I1 и I2 .

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее