2010 коллоквиум (6 2) ответы (Коллоквиум), страница 2

Какова бы ни была интерпретация I, формула ϕ выполнима в интерпретации I тогда и толькотогда, когда формула ψ выполнима в интерпретации I.Задача 10. Известно, что дизъюнкт D0 является логическим следствием дизъюнктов D1 и D2 .Какие из приведенных ниже утверждений верны?Задача 11. Известно, что семантическая таблица h{ϕ}; {ψ}i имеет конечный табличный вывод,некоторые ветви которого не завершаются закрытой таблицей.

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

Известно, что некоторая модель для формулы φ не является моделью для формулы ψ. Какие изприведенных ниже утверждений всегда верны для любых замкнутых формул φ и ψ?2. Не существует успешного табличного вывода из таблицы T = <{φ}, {ψ}>, потому что…(По условию существует интерпретация, в которой формулы φ верны, а ψ - не верны.Следовательно, в этой интерпретации не существует успешного табличного вывода из таблицыT = <{φ}, {ψ}, так как она является выполнимой)Задача 11. Известно, что для семантической таблицы T=<{φ}, {ψ}> нельзя построить ни одногоуспешного табличного вывода.

Какие из приведенных ниже утверждений всегда верны для любыхзамкнутых формул φ и ψ?4. Формула ψ не является логическим следствием формулы φ, потому что… (φ=1 -> ψ=0)Задача 11. Пусть задано некоторое непустое множество дизъюнктов S0. Пусть S1 – это множество всехформул, резолютивно выводимых из множества дизъюнктов S0. Какие из приведенных ниже утвержденийвсегда справедливы и почему?2. Если каждый дизъюнкт множества S1 выполним, то множество дизъюнктов S0 имеетмодель, потому что… из s1 не вывели пустой диз -> s0 имеет модель3. Если множество дизъюнктов S0 имеет модель, то множество дизъюнктов S1 имеетмодель, потому что… так как s0->s1Задача 12. Пусть Р – это хорновская логическая программа, а S – это множество всех дизъюнктов,соответствующих программным утверждениям программы Р.

Известно, что для наименьшей эрбрановскоймодели МР программы Р выполняется соотношение МР = ø. Какие из приведенных ниже утвержденийбудут при этом всегда верны и почему?4. В каждом дизъюнкте из системы S есть хотя бы один атом со связкой отрицания ¬,потому что… (в этой программе нет фактов, так как если в ней есть хотя бы одитн факт,то мэм !=0 -> a0<-a1,…,an переходит в а0 или не а1 или … не аn)Задача 13. Какие из приведенных ниже утверждений справедливы и почему?1. Любая арифметическая функция, вычислимая на машине Тьюринга, может бытьвычислена подходящей хорновской логической программой с использованиемстандартной стратегии вычисленияЗадача 14.

Пусть Г – некоторое множество замкнутых формул логики предикатов. Верно ли, что Гявляется непротиворечивым множеством тогда и только тогда, когда всякая дизъюнкция вида1   2  ...   n , где  i   , не является общезначимой?1. ВерноЗадача 15. Известно, что в программе Р ответ на запрос ?P(х) не имеет успешных вычислений ( былоизначально в варианте: всегда является отрицательным). Каким будет ответ на запрос ?not(P(с))?4. На запрос ?not(P(с))может быть вообще не получено никакого ответа, потому что можетпойти перебор по бесконечной ветви, которая расположена раньше ветви с запросом P(x).Задача 16.

Предположим, что в правило резолюции было внесено следующее изменение: резольвентойдизъюнктов D1=D1’or L1, D2=D2’ or Not(L2) объявляется всякий дизъюнкт D0=(D1’ and D2’)n, где n –унификатор (не обязательно наиболее общий) L1 и L2.После этого изменения Теорема корректности резолютивного вывода (1) и Теорема полнотырезолютивного вывода(2) будут…4. 1,2 верно,Задача 17. Предположим, что ни один основной атом не является логическим следствием хоновскойлогической программы P.4. Исходное условие не осуществимоЗадача 24.

Изветсно, что каждое конечное подмножество D’ бесконечного семейства дизъюнктов Dнепротиворечиво.1. семейство дизъюнктов D будет непротиворечивым.Задача 24. Известно, что их множества дизъюнктов S можно посторить резолют вывод пустого диз.2. Существует успешный табличный вывод для Т=<s,0> в s есть d=falseЗадача 25. Пусть Г – непустое множество логических следствий формулы φ. Г не имеет ни одной модели сконечной или счетной областью интерпретации. Что неверно?2. φ не имеет вообще ни одной модели4.

любая замкнутая формула пси равносильна φЗадача 27. ψ – пнф, φ – ссф для ψ1. φ - невыполнима, то ψ - невыполнима2. φ - выполнима, то ψ - выполнима3. φ - общезначима, то ψ - общезначимаЗадача 19. Формула фи логики предикатов 1го порядка выполнима тогда и только тогда, когда1. В любом дереве табличного вывода для таблицы Т=<фи, 0> каждая ветвь завершается аксиомой2.

В любом дереве табличного вывода для таблицы Т=<фи, 0> хотя бы одна ветвь завершается аксиомой3. Хотя бы в одном дереве табличного вывода для таблицы Т=<фи, 0> каждая ветвь завершается аксиомой4. Хотя бы в одном дереве табличного вывода для таблицы Т=<фи, 0> хотя бы одна ветвь завершаетсяаксиомой5. 1-4 не верно, потому чтоЗадача 22. фи - формула логики предикатов в ссф. Что неверно?1 Если фи выполнима, то фи выполнима хотя бы в одной эрб интерпретации дляформулы фи(нет, так как мы можем взять формулу, которая выполнима в интерп с бескпредметной областью, но не выполнима в интп с конечной – хотя бы одна конст и f)3 Если фи выполнима в каждой эрб интерпретации для формулы фи, то фи общезначима4 Если фи не имеет эрб моделей, то фи не имеет никаких моделей (пример из1).