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

Какова бы ни была последовательность действительных чисел и отрезок [a, b] действительных чисел, если бесконечно много элементов этой последовательности содержитсяв данном отрезке, то хотя бы одна предельная точка данной последовательности такжесодержится в этом отрезке.12. Если некоторое действительное число встречается бесконечно часто в произвольной последовательности действительных чисел, то данное число является предельной точкойэтой последовательности.1.2Выполнимые и общезначимые формулыУпражнение 1.9. Выясните, какие из приведенных ниже формул являются выполнимыми,какие являются невыполнимыми, а какие — общезначимыми.1.

∃x P (x) → ∀x P (x);2. ¬(∃x P (x) → ∀x P (x));3. ∃x ∀y (Q(x, x)&¬Q(x, y));4. ∃x (P (x) & ∃x ¬P (x));5. (∀x P (x) → ∀x R(x)) → ∀x (P (x)&R(x));6. ∀x (P (x)&R(x)) → (∀x P (x) & ∀x R(x));7. (∀x P (x) & ∀x R(x)) → ∀x (P (x)&R(x));8. ∃x (P (x)&R(x)) → (∃x P (x) & ∃x R(x));9. (∃x P (x) & ∃x R(x)) → ∃x (P (x)&R(x));10. ∀x ∃y Q(x, y) → ∃y ∀x Q(x, y);11.

∃y ∀x Q(x, y) → ∀x ∃y Q(x, y);12. ∀x (P (x) → ¬R(x)) → ¬(∃x P (x) & ∀x R(x));13. ∀x ∃y ∀z (R(x, y) → R(y, z));14. ∃x ∀y ∃z (R(x, y) → R(y, z));15. ∃x ∀y ∃z ((R(y, z) → R(x, z)) → (R(x, x) → R(y, x)));16. ∀x ∃y P (x, y) & ∀x ∀y (P (x, y) → P (y, x))&∀x ∀y ∀z (P (x, y) → (P (y, z) → P (x, z))).1.2. Выполнимые и общезначимые формулы7Упражнение 1.10. Докажите, что формула∃x∀y (P (x, y) → (¬P (y, x) → ((P (x, x) → P (y, y)) & (P (y, y)to P (x, x)))))истинна в любой интерпретации, область которой содержит не более трех элементов.Упражнение 1.11. Существует ли необщезначимая формула, являющаяся истинной в любой интерпретации, область которой содержит не менее трех элементов?Упражнение 1.12. Запишите необщезначимую формулу, являющуюся истинной в любойинтерпретации, область которой содержит1. не более одного элемента,2.

не более двух элементов,3. не более n элементов, где n — некоторое заданное натуральное число.Упражнение 1.13. Существует ли такое предложение ϕ, логическим следствием которого1. является любая замкнутая формула?2. не является ни одна замкнутая формула?3. является только конечное число замкнутых формул?Упражнение 1.14. Какие формулы являются логическими следствиями1. общезначимой формулы ϕ?2. противоречивой формулы ϕ?Упражнение 1.15. Пусть известно, что выполнимые замкнутые формулы ϕ и ψ не имеютни одной общей модели. Какие из приведенных ниже утверждений всегда верны и почему?1. Существует формула χ, логическим следствием которой являются обе формулы ϕ и ψ;2.

Существует формула χ, которая является логическим следствием обеих формул ϕ и ψ;3. Формулы ¬ϕ и ¬ϕ также не имеют ни одной общей модели;4. Ни одна из формул ϕ, ψ не является общезначимой.Упражнение 1.16. Пусть Γ1 и Γ2 — два различных непротиворечивых множества замкнутых формул.

Какие из приведенных ниже утверждений справедливы? Выбор ответаобосновать.1. Объединение Γ1 ∪ Γ2 и пересечение Γ1 ∩ Γ2 всегда являются непротиворечивыми множествами.8Глава 1. УПРАЖНЕНИЯ2. Объединение Γ1 ∪ Γ2 всегда является непротиворечивым множеством, потому что. . .Однако пересечение Γ1 ∩ Γ2 может оказаться противоречивым множеством.3. Пересечение Γ1 ∩ Γ2 всегда является непротиворечивым множеством, однако, объединение Γ1 ∪ Γ2 может оказаться противоречивым множеством.4. Существуют примеры таких непротиворечивых множеств Γ1 и Γ2 , когда объединениеΓ1 ∪ Γ2 и пересечение Γ1 ∩ Γ2 оказываются противоречивыми множествами.Упражнение 1.17.

Пусть Γ1 и Γ2 — некоторые множества предложений. Обозначим ∆i ,i = 1, 2, множество всех замкнутых формул, являющихся логическими следствиями множества предложений Γi . Каким может быть множество логических следствий совокупностипредложений1. Γ1 ∩ Γ2 ?2.

Γ1 ∪ Γ2 ?Упражнение 1.18. Введем на множествах замкнутых формул отношение следующимобразом: отношение Γ1 Γ2 имеет место для двух множеств замкнутых формул Γ1 , Γ2 тогдаи только тогда, когда любая формула ϕ, ϕ ∈ Γ1 , является логическим следствием множестваформул Γ1 . Какими из перечисленных свойств1. рефлексивность,2. транзитивность,3. симметричность,4. тотальность: для любых множеств замкнутых формул Γ1 , Γ2 верно хотя бы одно изсоотношений Γ1 Γ2 или Γ2 Γ1 ,5. ∪-монотонность: Γ01 Γ02 ∧ Γ001 Γ002 ⇒ Γ01 ∪ Γ001 Γ02 ∪ Γ002 ,6. ∩-монотонность: Γ01 Γ02 ∧ Γ001 Γ002 ⇒ Γ01 ∩ Γ001 Γ02 ∩ Γ002 ,обладает отношение ?1.3Табличный выводУпражнение 1.19.

Докажите общезначимость приведенных ниже формул, построив успешный табличный вывод для соответствующих семантических таблиц.1. ∀x P (x) → ∀y P (y)2. ¬∃xP (x) → ∀x¬P (x);3. ∀x¬P (x) → ¬∃xP (x);4. ∀x (P (x)&R(x)) → (∀x P (x) & ∀x R(x));1.3. Табличный вывод95. (∀x P (x) & ∀x R(x)) → ∀x (P (x)&R(x));6. ∃x (P (x) ∨ R(x)) → (∃x P (x) ∨ ∃x R(x));7. (∃x P (x) ∨ ∃x R(x)) → ∃x (P (x) ∨ R(x));8. (∀x P (x) ∨ R(y)) → ∀x (P (x) ∨ R(y));9.

∀x (P (x) ∨ R(y)) → (∀x P (x) ∨ R(y));10. ∃y ∀x Q(x, y) → ∀x ∃y Q(x, y);11. ∀x((∃x¬P (x) → ∃xR(x)) → ∃y(P (x) ∨ R(y)));12. ∀x (P (x) → ∃y R(x, f (y))) → (∃x ¬P (x) ∨ ∀x∃zR(x, z));13. ∀x ∃y ∀z (R(x, y) → R(y, z));14. ∃x ∀y ∃z (R(x, y) → R(y, z));15.

∃x (R(x) & ∃x (P (x) → ¬R(x)) → ¬∀x P (x));16. ∃x ((∀y P (x, y) ∨ ∃x R(x)) → (∃x P (x, x) ∨ R(x)));17. ∃x (∀x P (x) → ¬(R(x) & ∃x (P (x) → ¬R(x))));18. ∃x (∃y ¬P (x, y) → ∀x R(x)) → ∀x (R(x) ∨ ∃x P (x, f (x)));19. ∀x∃u (∃v∀y ((E(u, y) → H(y, v)) & ∃w∀x (H(w, y) → ¬H(x, v))) → ∃y ¬E(x, y));20. ∀x (∀y∃v∀u ((A(u, v) → B(y, u)) & (¬∃w A(w, u) → ∀w A(w, v))) → ∃y B(x, y)).Упражнение 1.20. Докажите, что в том случае, если для таблицы T = h ϕ | ∅i существуетуспешный вывод, то формула ϕ невыполнима.Упражнение 1.21.

Пусть Γ ⊆ CF orm и ϕ ∈ CF orm. Докажите, что существование успешного табличного вывода для таблицы T = h Γ | ϕ i свидетельствует о том, что формула ϕявляется логическим множества формул Γ.Упражнение 1.22. Докажите, что невыполнимость таблицы h ϕ1 , . . . , ϕn | ψ1 , . . . , ψm iраносильна общезначимости формулы (ϕ1 & . . . &ϕn ) → (ψ1 ∨ · · · ∨ ψm ).Упражнение 1.23. Докажите, используя исчисление семантических таблиц, что формула∃z L(z, Даша) логически следует из совокупности предложенийL(Даша, Саша),L(Саша, пиво),L(Паша, пиво),∀x (∃y (L(Паша, y)&L(x, y)) → L(Паша, x)).Упражнение 1.24.

Выясните, применяя табличный вывод, какие из приведенных нижеформул являются выполнимыми, какие являются невыполнимыми, а какие — общезначимыми.10Глава 1. УПРАЖНЕНИЯ1. ¬(∃x P (x) → ∀x P (x));2. ∃x ∀y (Q(x, x)&¬Q(x, y));3. ∃x (P (x) & ∃x ¬P (x));4. ∀x (P (x) & ∀x ¬P (x));5. (∃x P (x) & ∃x R(x)) → ∃x (P (x)&R(x));6.

(∀x P (x) & ∀x R(x)) → ∀x (P (x)&R(x)).Упражнение 1.25. Пусть известно, что семантическая таблица h Γ | ∅ i имеет табличныйвывод, одна из ветвей которого заканчивается такой семантической таблицей T = h Γ0 | ∆0 i,что Γ0 ∩ ∆0 = ∅ и при этом ни одно правило табличного вывода не применимо к таблице T .Какие из приведенных ниже утверждений наверняка справедливы и почему?1. Множество формул Γ не имеет модели;2. Множество формул Γ имеет модель с бесконечной предметной областью;3.

В множестве формул Γ обязательно есть хотя бы одна общезначимая формула;4. В множестве формул Γ обязательно есть хотя бы одна противоречивая формула.Упражнение 1.26. Пусть известно, что семантическая таблица T = h Γ | ∆ i имеет успешный табличный вывод. Какие из приведенных ниже утверждений при этом условии будутвсегда справедливы и почему?1. Хотя бы одна формула из множества формул ∆ является общезначимой;2. Хотя бы одна формула из множества формул ∆ является выполнимой;3. Хотя бы одна формула из множества формул ∆ является противоречивой;4. Множество формул Γ имеет модель;5. Множество формул Γ не имеет модели.Упражнение 1.27.

Известно, что семантическая таблица T = h ϕ | ψ i невыполнима. Какиеиз приведенных ниже утверждений всегда верны для любых замкнутых формул ϕ и ψ?1. Формула ϕ является логическим следствием формулы ψ;2. Формула ψ является логическим следствием формулы ϕ;3. Не существует успешного табличного вывода из семантической таблицы T ;4. Формула ϕ → ψ является противоречивой.T0Упражнение 1.28.

Какие из перечисленных ниже правил табличного вывода T T,0T и T121являются корректными?1.4. Полнота табличного вывода1.h Γ, ϕ → ψ | ∆ i;h Γ, ¬ϕ, ψ | ∆ i2.h Γ, ∀x ϕ(x) | ∆ i;h Γ, ϕ(x) | ∆ i3.h Γ1 , Γ2 | ∆ 1 , ∆ 2 i;h Γ1 | ∆1 i, h Γ2 | ∆2 i4.h Γ1 , Γ2 | ∆ i;h Γ1 | ∆ i, h Γ2 | ∆ i5.h Γ | ∆1 , ∆2 i;h Γ | ∆1 i, h Γ | ∆2 i6.h Γ1 , Γ2 | ∆ 1 , ∆ 2 i;h Γ1 | ∆1 , Φ i, h Γ2 , Φ | ∆2 i1.411Полнота табличного выводаУпражнение 1.29. Используя исчисление семантических таблиц и стратегию построениятабличного вывода, описанную в доказательстве теоремы полноты, проверьте выполнимостьприведенных ниже семантических таблиц.1.

T1 = h ∀x P (c, x, x), ∀x∀y∀z (P (x, y, z) → P (f (x), y, f (z))) | P (f (c), c, f (c)) i;2. T2 = h ∀x P (c, x, x), ∀x∀y∀z (P (x, y, z) → P (f (x), y, f (z))) | ∃z P (f (c), z, f (f (c))) i;3. T3 = h ∀x∀y∀z (P (x, y) & P (y, z) → P (x, z)), ∀x ¬(P (x, x) | ∀x∀y (P (x, y) → ¬P (y, x)) i;4. T4 = h ∃x (P (x) & R(x)), ∀x (P (y) → Q(y)) | ∃z (Q(z) ∨ R(z)) i.Упражнение 1.30. Какие из приведенных ниже множеств формул являются непротиворечивыми? Используйте для проверки непротиворечивости исчисление семантических таблиц.1. Γ1 = { ∀x ¬R(x, x), ∃x P (x), ∀x∃y R(x, y), ∀x (P (x) → R(y, x)) };2.