colloquium (Коллоквиум)

ФАМИЛИЯ И.О.: ____________________ГРУППА: __________ВАРИАНТЗадача 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 }. Какое из утверждений верно?1. ϕ → (ψ1 → ψ2 ) — общезначимая формула.2. (ϕ → ψ1 ) → ψ2 — общезначимая формула.3. ψ1 → (ψ2 → ϕ) — общезначимая формула.4. (ψ1 → ψ2 ) → ϕ — общезначимая формула.Задача 5.

Известно, что семантическая таблица h{ϕ}; ∅i имеет успешный табличный вывод, каждая ветвь которого завершается закрытой таблицей. Какое из трех утверждений верно?1. ϕ — общезначимая формула.2. ϕ — выполнимая, но необщезначимая формула.3. ϕ — невыполнимая формула.Задача 6. Какие из двух формул ϕ = ∀x ∃y (P (x) → P (y)) и ψ = ∃y ∀x (P (x) → P (y)) являютсяобщезначимыми?1. Только формула ϕ.2. Только формула ψ.3. Ни одна из этих двух формул.4. Обе формулы.Задача 7.

Какие из трех приведенных ниже формул представлены в сколемовской стандартнойформе (символы x, y обозначают переменные, а c, e — константы)?1. ∀x ∃y (P (x, f (x)) ∨ P (y, y))2. ∀x (P (x, f (x)) ∨ ∀y P (y, y))3. P (c, f (c)) ∨ P (e, e).Задача 8. Известно, что дизъюнкт D0 является резольвентой дизъюнктов D1 и D2 . Какие изприведенных ниже утверждений верны для любых дизъюнктов D0 , D1 , D2 ?1. Множество формул S = {D0 , D1 , D2 } противоречиво.2.

Множество формул S = {D0 , ¬D1 , ¬D2 } противоречиво.3. Множество формул S = {¬D0 , D1 , D2 } противоречиво.4. Множество формул S = {¬D0 , ¬D1 , ¬D2 } противоречиво.Задача 9. Известно, что из системы дизъюнктов S резолютивно выводим пустой дизъюнкт. Какиеиз приведенных ниже утверждений верны?1. Система дизъюнктов S не имеет эрбрановских моделей.2. Система дизъюнктов S не имеет конечного противоречивого множество основных примеров.3. Система дизъюнктов S непротиворечива.4.

Любая замкнутая формула является логическим следствием системы дизъюнктов S.Задача 10. Верно, что существует такое предложение ϕ, логическим следствием которого1. является любая замкнутая формула.2. не является ни одна замкнутая формула.3. является только конечное число замкнутых формул.Задача 11. Известно, что замкнутая формула ϕ равносильна формуле ψ.

Какие из приведенныхниже утверждений верны?1. Всякое логическое следствие формулы ϕ является логическим следствием формулы ψ.2. Всякая модель формулы ϕ является моделью формулы ψ.3. Формулы ϕ и ψ имеют одинаковую предваренную нормальную форму.4. Формула ϕ общезначима тогда и только тогда, когда общезначима формула ψ.Задача 12. Предположим, что из системы дизъюнктов S можно резолютивно вывести дизъюнктP ∨ ¬P . Какие из приведенных ниже утверждений будут всегда верны?1. В системе дизъюнктов S есть противоречивый дизъюнкт2. Система дизъюнктов S непротиворечива3.

Система дизъюнктов S противоречива4. Такой резольвенты вывести из системы дизъюнктов S невозможноФАМИЛИЯ И.О.: ____________________ГРУППА: __________ВАРИАНТЗадача 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 (P (x) → ¬R(x)) → ¬(∃x P (x) & ∀x R(x)).Задача 3.

Докажите общезначимость приведенной ниже формулы, используя метод резолюций.(∃x P (x) ∨ ∃x R(x)) → ∃x (P (x) ∨ R(x)).Задача 4. Известно, что множество замкнутых формул {ϕ, ψ} не имеет модели. Какие из четырехутверждений верны?1. ϕ → ψ — общезначимая формула.2. ψ → ϕ — общезначимая формула.3. ϕ → ¬ψ — общезначимая формула.4. ψ → ¬ϕ — общезначимая формула.Задача 5. Верно, что существует такое конечное множество предложений Γ = {ϕ1 , ϕ2 , .

. . , ϕN },логическим следствием которого1. является формула ¬ϕ1 .2. являются всевозможные замкнутые формулы.3. является бесконечное множество замкнутых формул.Задача 6. Какие из трех формул P (x), P (y), ∀xP (x) являются равносильными?1. P (x) и P (y).2. P (x) и ∀xP (x).3. Все три формулы попарно равносильны друг другу.4. Никакие две формулы из этих трех не являются равносильными.Задача 7. Какие из приведенных ниже утверждений справедливы для предваренной нормальнойформы ϕ и соответствующей ей сколемовской стандартной формы ψ?1. Формулы ϕ и ψ равносильны.2.

Формула ϕ → ψ общезначима.3. Если формула ϕ противоречива, то и формула ψ противоречива.4. Если формула ψ противоречива, то и формула ϕ противоречива.Задача 8. Предположим, что из непустой системы дизъюнктов S нельзя резолютивно вывестини одного дизъюнкта.

Какие из приведенных ниже утверждений верны?1. Cистема дизъюнктов S противоречива.2. Система дизъюнктов S непротиворечива.3. Такой системы дизъюнктов S не существует.Задача 9. Какие из двух формул ϕ = ∀x ∀y (P (x) → ¬P (y)) и ψ = ∃x ∃y (P (x) → ¬P (y))являются невыполнимыми?1. Только формула ϕ.2. Только формула ψ.3. Ни одна из этих двух формул.4. Обе формулы.Задача 10. Известно, что семантическая таблица h{ϕ}; ∅i имеет конечный табличный вывод, некоторые ветви которого не завершаются закрытой таблицей. Какое из трех утверждений верно длялюбой формулы ϕ?1.

ϕ — общезначимая формула.2. ϕ — выполнимая формула.3. ϕ — невыполнимая формула.Задача 11. Известно, что любая пара дизъюнктов из множества дизъюнктов S имеет модель.Какие из приведенных ниже утверждений будут всегда верны для любой системы дизъюнктов S,обладающей указанным свойством?1. Система дизъюнктов S непротиворечива.2. Никакие два дизъюнкта системы S не имеют резольвенты.3. Из системы дизъюнктов S нельзя резолютивно вывести пустой дизъюнкт.Задача 12. Известно, что дизъюнкт D0 является резольвентой дизъюнктов D1 и D2 .

Какие изприведенных ниже утверждений верны?1. Каждая эрбрановская модель для дизъюнкта D0 является моделью для системы дизъюнктов{D1 , D2 }.2. Каждая эрбрановская модель для системы дизъюнктов {D1 , D2 } является моделью для дизъюнкта D0 .3. Система дизъюнктов {D0 , D1 , D2 } непротиворечива.ФАМИЛИЯ И.О.: ____________________ГРУППА: __________ВАРИАНТЗадача 1. Используя только приведенные ниже предикаты• C(x) — «x — квадрат»;• S(x) — «x — шар»;• B(x) — «x — черный предмет»;• W (x) — «x — белый предмет»;• L(x, y) — «предмет x лежит левее предмета y».• U (x, y) — «предмет x лежит ниже предмета y».запишите формулу логики предикатов, выражающую следующее высказывание:«Каков бы ни был черный шар, лежащий под всеми белыми квадратами, слева от него нет никакихшаров».Задача 2. Докажите общезначимость приведенной ниже формулы, построив успешный табличный вывод для соответствующих семантических таблиц.∃z ¬(∀z B(x) & (A(z) & ∃z (B(z) → ¬A(z)))).Задача 3.

Докажите общезначимость приведенной ниже формулы, используя метод резолюций.(∀x P (x) ∨ ∀y R(y)) → ∀z ∃x(P (z) ∨ R(x)).Задача 4. Верно, что существует такое предложение ψ, логическим следствием которого1. не является ни одна замкнутая формула.2. является только конечное число замкнутых формул.3. является любая замкнутая формула.Задача 5.

Известно, что дизъюнкт D0 является резольвентой дизъюнктов D1 и D2 . Какие изприведенных ниже утверждений верны для любых дизъюнктов D0 , D1 , D2 ?1. Система дизъюнктов S = {¬D0 , ¬D1 , ¬D2 } противоречива.2. Система дизъюнктов S = {D0 , ¬D1 , ¬D2 } противоречива.3.

Система дизъюнктов S = {D0 , D1 , D2 } противоречива.4. Система дизъюнктов S = {¬D0 , D1 , D2 } противоречива.Задача 6. Предположим, что из системы дизъюнктов S можно резолютивно вывести дизъюнктP ∨ ¬P . Какие из приведенных ниже утверждений будут всегда верны?1.

В системе дизъюнктов S есть противоречивый дизъюнкт.2. Такой резольвенты вывести из системы дизъюнктов S невозможно.3. Система дизъюнктов S непротиворечива.4. Система дизъюнктов S противоречива.Задача 7. Какие из трех приведенных ниже формул представлены в сколемовской стандартнойформе (символы x, y обозначают переменные, а c, e — константы)?1.