2010 коллоквиум (6 2) ответы (Коллоквиум)

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

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

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

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

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

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

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

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

Верно, что существует такое предложение ψ, логическим следствием которого3. является любая замкнутая формула.Задача 5. Известно, что дизъюнкт D0 является резольвентой дизъюнктов D1 и D2 . Какие изприведенных ниже утверждений верны для любых дизъюнктов D0 , D1 , D2 ?2. Система дизъюнктов S = {D0 , ¬D1 , ¬D2 } противоречива.4. Система дизъюнктов S = {¬D0 , D1 , D2 } противоречива.Задача 6. Предположим, что из системы дизъюнктов S можно резолютивно вывести дизъюнктP ∨ ¬P . Какие из приведенных ниже утверждений будут всегда верны?Задача 7. Какие из трех приведенных ниже формул представлены в сколемовской стандартнойформе (символы x, y обозначают переменные, а c, e — константы)?3.

P (c, f (c)) ∨ P (e, e).Задача 8. Замкнутая формула ϕ является логическим следствием множества замкнутых формулΓ = {ψ1 , ψ2 }. Какое из утверждений верно?1. ψ1 → (ψ2 → ϕ) — общезначимая формула.Задача 9. Какие из двух формул ϕ = ∀x ∃y (P (x) → P (y)) и ψ = ∃y ∀x (P (x) → P (y)) являютсяобщезначимыми?4.

Обе формулы.Задача 10. Известно, что из системы дизъюнктов S резолютивно выводим пустой дизъюнкт.Какие из приведенных ниже утверждений верны?1. Любая замкнутая формула является логическим следствием системы дизъюнктов S.3. Система дизъюнктов S не имеет эрбрановских моделей.Задача 11. Известно, что замкнутая формула A равносильна формуле B. Какие из приведенныхниже утверждений верны?1.

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

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

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

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

ψ → ¬ϕ — общезначимая формула.5Задача 4. Известно, что множество замкнутых формул {ϕ1 , ϕ2 , ψ} не имеет модели. Какие изутверждений в этом случае всегда верны?1. ψ → (¬ϕ1 ∨ ¬ϕ2 ) — общезначимая формула.2. ϕ1 → (¬ψ ∨ ¬ϕ2 ) — общезначимая формула.3. ¬ψ ∨ ¬ϕ2 ∨ ¬ϕ1 — общезначимая формула.Задача 5. Известно, что дизъюнкт D0 является логическим следствием дизъюнктов D1 и D2 .Какие из приведенных ниже утверждений верны?Задача 6. Какие из приведенных ниже утверждений справедливы для предваренной нормальнойформы ϕ и соответствующей ей сколемовской стандартной формы ψ?1.

Какова бы ни была интерпретация I, формула ϕ выполнима в интерпретации I тогда и толькотогда, когда формула ψ выполнима в интерпретации I.2. Если формула ϕ общезначима, то и формула ψ общезначима.3. Если формула ψ общезначима, то и формула ϕ общезначима.Задача 7. Известно, что любое конечное подмножество S 0 бесконечной противоречивой системыдизъюнктов S имеет модель. Какие из приведенных ниже утверждений будут всегда верны длялюбой системы дизъюнктов S, обладающей указанным свойством?3. Из системы дизъюнктов S нельзя резолютивно вывести пустой дизъюнкт.Задача 8. Какие из двух формул ϕ = ∀x ∃y (P (x) → P (y)) и ψ = ∃x ∀y (¬P (x) → ¬P (y))являются общезначимыми?4. Обе формулы.Задача 9.

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

Верно, что существует такое конечное множество предложений Γ = {ϕ1 , ϕ2 , . . . , ϕN },логическим следствием которого2. являются всевозможные замкнутые формулы.3. является бесконечное множество замкнутых формул.6Задача 4. Известно, что замкнутая формула ϕ выполнима в каждой интерпретации, предметнойобластью которой является множество простых натуральных чисел.

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

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