Сборник задач для самостоятельных занятий, страница 3
Описание файла
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 .