2010 коллоквиум (6 вариантов) (1162087), страница 3
Текст из файла (страница 3)
является конечное множество формула.ФАМИЛИЯ И.О.: ____________________ГРУППА: __________ВАРИАНТЗадача 1. Используя только приведенные ниже предикаты• C(x) — «x — квадрат»;• S(x) — «x — шар»;• B(x) — «x — черный предмет»;• W (x) — «x — белый предмет»;• L(x, y) — «предмет x лежит левее предмета y».• U (x, y) — «предмет x лежит ниже предмета y».запишите формулу логики предикатов, выражающую следующее высказывание:«Никакой черный квадрат не лежит ни под одним черным шаром, слева от которого располагаютсявсе белые шары».Задача 2. Докажите общезначимость приведенной ниже формулы, построив успешный табличный вывод для соответствующих семантических таблиц.∃x (∀x P (x) → ¬(R(x) & ∃x (P (x) → ¬R(x)))).Задача 3. Докажите общезначимость приведенной ниже формулы, используя метод резолюций.∃y ((∀x P (x) ∨ R(y)) → ∀x (P (x) ∨ R(y))).Задача 4.
Известно, что замкнутая формула ϕ выполнима в каждой интерпретации, предметнойобластью которой является множество простых натуральных чисел. Какие из приведенных нижеутверждений верны?1. Формула ϕ является логическим следствием любого предложения.2. Логическим следствием формулы ϕ может быть только общезначимая формула.3. Такой формулы ϕ не существует.4. Формула ϕ равносильна формуле ∀x(P (x) ∨ ¬P (x)).Задача 5.
Верно, что существует такое конечное множество предложений Γ = {ϕ1 , ϕ2 , . . . , ϕN },логическим следствием которого1. является бесконечное множество замкнутых формул.2. являются всевозможные замкнутые формулы.3. не является ни одна формула.4. является конечное множество формула.Задача 6. Какие из трех формул ∃yP (y, x), ∃yP (x, y), ∃xP (x, y) являются равносильными?1.
∀yP (y, x) и ∀yP (x, y).2. ∀yP (y, x) и ∀xP (x, y).3. Все три формулы попарно равносильны друг другу.4. Никакие две формулы из этих трех не являются равносильными.Задача 7. Известно, что любое конечное подмножество S 0 бесконечной противоречивой системыдизъюнктов S имеет модель.
Какие из приведенных ниже утверждений будут всегда верны длялюбой системы дизъюнктов S, обладающей указанным свойством?1. Никакие два дизъюнкта системы S не имеют резольвенты.2. Из системы дизъюнктов S резолютивно выводим пустой дизъюнкт.3. Из системы дизъюнктов S нельзя резолютивно вывести пустой дизъюнкт.4.
Такой системы дизъюнктов S не существует.Задача 8. Какие из двух формул ϕ = ∀x ∃y (P (x) → P (y)) и ψ = ∃x ∀y (¬P (x) → ¬P (y))являются общезначимыми?1. Только формула ϕ.2. Только формула ψ.3. Ни одна из этих двух формул.4. Обе формулы.Задача 9. Какие из приведенных ниже утверждений справедливы для предваренной нормальнойформы ϕ и соответствующей ей сколемовской стандартной формы ψ?1. Если формула ϕ общезначима, то и формула ψ общезначима.2.
Если формула ψ общезначима, то и формула ϕ общезначима.3. Формулы ϕ и ψ равносильны.4. Какова бы ни была интерпретация I, формула ϕ выполнима в интерпретации I тогда и толькотогда, когда формула ψ выполнима в интерпретации I.Задача 10. Известно, что дизъюнкт D0 является логическим следствием дизъюнктов D1 и D2 .Какие из приведенных ниже утверждений верны?1. Дизъюнкт D0 резолютивно выводим из множества дизъюнктов {D1 , D2 }.2. Система дизъюнктов {D0 , D1 , D2 } имеет хотя бы одну эрбрановскую модель.3.
Система дизъюнктов {D0 , D1 , D2 } непротиворечива.Задача 11. Известно, что семантическая таблица h{ϕ}; {ψ}i имеет конечный табличный вывод,некоторые ветви которого не завершаются закрытой таблицей. Какое из трех утверждений вернодля любой пары формул ϕ, ψ?1. ϕ → ψ — общезначимая формула.2. ψ → ϕ — общезначимая формула.3. ϕ → ψ — выполнимая формула.4. ψ → ϕ — выполнимая формула.Задача 12.
Известно, что множество замкнутых формул {ϕ1 , ϕ2 , ψ} не имеет модели. Какиеутверждения в этом случае всегда верны?1. ¬ϕ1 ∨ ¬ψ ∨ ¬ϕ2 — общезначимая формула.2. ψ ∨ ¬ϕ2 ∨ ¬ϕ1 — общезначимая формула.3. ¬ψ ∨ ϕ1 ∨ ϕ2 ) — общезначимая формула.4. (¬ϕ1 &¬ϕ2 ) → ψ — общезначимая формула..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
