colloquium (Коллоквиум), страница 2

∀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. Замкнутая формула ϕ является логическим следствием множества замкнутых формулΓ = {ψ1 , ψ2 }. Какое из утверждений верно?1. ψ1 → (ψ2 → ϕ) — общезначимая формула.2. (ϕ → ψ1 ) → ψ2 — общезначимая формула.3. ϕ → (ψ1 → ψ2 ) — общезначимая формула.4. (ψ1 → ψ2 ) → ϕ — общезначимая формула.Задача 9. Какие из двух формул ϕ = ∀x ∃y (P (x) → P (y)) и ψ = ∃y ∀x (P (x) → P (y)) являютсяобщезначимыми?1. Только формула ϕ.2. Только формула ψ.3. Ни одна из этих двух формул.4. Обе формулы.Задача 10. Известно, что из системы дизъюнктов S резолютивно выводим пустой дизъюнкт.Какие из приведенных ниже утверждений верны?1. Любая замкнутая формула является логическим следствием системы дизъюнктов S.2. Система дизъюнктов S не имеет конечного противоречивого множество основных примеров.3.

Система дизъюнктов S не имеет эрбрановских моделей.4. Система дизъюнктов S непротиворечива.Задача 11. Известно, что замкнутая формула A равносильна формуле B. Какие из приведенныхниже утверждений верны?1. Всякая модель формулы A является моделью формулы B.2. Формулы A и B имеют одинаковую предваренную нормальную форму.3. Всякое логическое следствие формулы A является логическим следствием формулы B.4. Формула A общезначима тогда и только тогда, когда общезначима формула B.Задача 12. Известно, что семантическая таблица h{ψ}; ∅i имеет успешный табличный вывод,каждая ветвь которого завершается закрытой таблицей. Какое из трех утверждений верно?1.

ψ — выполнимая, но необщезначимая формула.2. ψ — невыполнимая формула.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 (E(x) → ¬D(x)) → ¬∃x( E(x) & ∀x D(x)).Задача 3.

Докажите общезначимость приведенной ниже формулы, используя метод резолюций.(∃x P (x) ∨ ∃x R(x)) → ∃x (P (x) ∨ R(x)).Задача 4. Известно, что дизъюнкт D0 является резольвентой дизъюнктов D1 и D2 . Какие изприведенных ниже утверждений верны?1. Система дизъюнктов {D0 , D1 , D2 } непротиворечива.2. Каждая эрбрановская модель для дизъюнкта D0 является моделью для системы дизъюнктов{D1 , D2 }.3. Каждая эрбрановская модель для системы дизъюнктов {D1 , D2 } является моделью для дизъюнкта D0 .Задача 5.

Известно, что любая пара дизъюнктов из множества дизъюнктов S имеет модель.Какие из приведенных ниже утверждений будут всегда верны для любой системы дизъюнктов S,обладающей указанным свойством?1. Система дизъюнктов S непротиворечива.2. Никакие два дизъюнкта системы S не имеют резольвенты.3. Из системы дизъюнктов S нельзя резолютивно вывести пустой дизъюнкт.Задача 6. Какие из двух формул ϕ = ∀x ∀y (P (x) → ¬P (y)) и ψ = ∃x ∃y (P (x) → ¬P (y))являются невыполнимыми?1.

Только формула ϕ.2. Только формула ψ.3. Ни одна из этих двух формул.4. Обе формулы.Задача 7. Предположим, что из непустой системы дизъюнктов S нельзя резолютивно вывестини одного дизъюнкта. Какие из приведенных ниже утверждений верны?1. Cистема дизъюнктов S противоречива.2. Система дизъюнктов S непротиворечива.3. Такой системы дизъюнктов S не существует.Задача 8. Какие из приведенных ниже утверждений справедливы для предваренной нормальнойформы ϕ и соответствующей ей сколемовской стандартной формы ψ?1. Формула ϕ → ψ общезначима.2. Если формула ϕ противоречива, то и формула ψ противоречива.3. Формулы ϕ и ψ равносильны.4. Если формула ψ противоречива, то и формула ϕ противоречива.Задача 9.

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

ϕ — общезначимая формула.2. ϕ — выполнимая формула.3. ϕ — невыполнимая формула.Задача 11. Верно, что существует такое конечное множество предложений Γ = {ϕ1 , ϕ2 , . . . , ϕN },логическим следствием которого1. являются всевозможные замкнутые формулы.2. является бесконечное множество замкнутых формул.3. является формула ¬ϕ1 .Задача 12. Известно, что множество замкнутых формул {ϕ, ψ} не имеет модели. Какое из утверждений в этом случае всегда верны?1.

ψ → ϕ — общезначимая формула.2. ϕ → ¬ψ — общезначимая формула.3. ϕ → ψ — общезначимая формула.4. ψ → ¬ϕ — общезначимая формула.ФАМИЛИЯ И.О.: ____________________ГРУППА: __________ВАРИАНТЗадача 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 (E(x) → ¬D(x)) → ¬(∃x E(x) & ∀x D(x)).Задача 3. Докажите общезначимость приведенной ниже формулы, используя метод резолюций.(∃x P (x) ∨ ∀x R(x)) → ∃x (P (x) ∨ R(x)).Задача 4. Известно, что множество замкнутых формул {ϕ1 , ϕ2 , ψ} не имеет модели. Какие изутверждений в этом случае всегда верны?1. ψ → (¬ϕ1 ∨ ¬ϕ2 ) — общезначимая формула.2. ϕ1 → (¬ψ ∨ ¬ϕ2 ) — общезначимая формула.3. ¬ψ ∨ ¬ϕ2 ∨ ¬ϕ1 — общезначимая формула.4. (ϕ1 &ϕ2 ) → ψ — общезначимая формула.Задача 5.

Известно, что дизъюнкт D0 является логическим следствием дизъюнктов D1 и D2 .Какие из приведенных ниже утверждений верны?1. Система дизъюнктов {D0 , D1 , D2 } непротиворечива.2. Дизъюнкт D0 резолютивно выводим из множества дизъюнктов {D1 , D2 }.3. Система дизъюнктов {D0 , D1 , D2 } имеет хотя бы одну эрбрановскую модель.Задача 6. Какие из приведенных ниже утверждений справедливы для предваренной нормальнойформы ϕ и соответствующей ей сколемовской стандартной формы ψ?1. Какова бы ни была интерпретация I, формула ϕ выполнима в интерпретации I тогда и толькотогда, когда формула ψ выполнима в интерпретации I.2.

Если формула ϕ общезначима, то и формула ψ общезначима.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. Формула ϕ не имеет модели.Задача 10. Какие из трех формул ∀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. Никакие две формулы из этих трех не являются равносильными.Задача 11. Известно, что семантическая таблица h{ϕ}; {ψ}i имеет конечный табличный вывод,некоторые ветви которого не завершаются закрытой таблицей. Какое из трех утверждений вернодля любой пары формул ϕ, ψ?1. ϕ → ψ — общезначимая формула.2. ψ → ϕ — общезначимая формула.3. ϕ → ψ — выполнимая формула.4. ψ → ϕ — выполнимая формула.Задача 12. Верно, что существует такое конечное множество предложений Γ = {ϕ1 , ϕ2 , . . .

, ϕN },логическим следствием которого1. не является ни одна формула.2. являются всевозможные замкнутые формулы.3. является бесконечное множество замкнутых формул.4. является конечное множество формула.ФАМИЛИЯ И.О.: ____________________ГРУППА: __________ВАРИАНТЗадача 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.