ВАРИАНТ 21 (Экзаменационные варианты)

ВАРИАНТ 1 .

Задача 1. Используя константные, функциональные и предикатные символы алфавита (см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующему утверждению.

“ Какова бы ни была убывающая последовательность положительных действительных чисел, она имеет неотрицательный предел ”.

Задача 2. Для заданной формулы  выяснить, применяя метод семантических таблиц, является ли эта формула общезначимой.

x P(x)  (x (P(x)  Q(x))  y Q(y))

Задача 3. Для заданной формулы  выяснить, применяя метод резолюций, является ли эта формула общезначимой.

x (P(x)  Q(x))  ( y Q(y)   x P(x))

Задача 4. Для заданного запроса G=? P(x), R(x) к заданной логической программе  построить на основе стандартной стратегии вычислений (с использованием операторов отсечения и отрицания) дерево SLD-резолютивных вычислений и определить множество вычислимых ответов.

: P(b)  ;

P(f(c))  R(b), !;

P(c)  ;

R(x)  not(P(f(x)));

R(c)  P(c);

R(b)  P(b);

Вопрос 5. Привести определение следующего понятия: интерпретация для языка логики предикатов первого порядка.

Вопрос 6. Как вычисляется композиция  подстановок  = { x₁/t₁ ,…, x_n/t_n} и  = { y₁/s₁ ,…, y_m/s_m} ?

Вопрос 7. Привести определение следующего понятия: SLD-резольвента запроса G к логической программе .

Вопрос 8. Как определяется операционная семантика оператора is, используемого для вычисления значения термов?

Вопрос 9. В описании правила табличного вывода R (см. Приложение 1.) предусматривается, что константа c, которую следует подставить вместо переменной x, не содержится в формулах верхней таблицы. Какими из перечисленных обстоятельств обусловлено это ограничение?

1. Для соблюдения синтаксической правильности формул таблицы, потому что....

2. Для повышения эффективности (сокращения размера) вывода, потому что...

3. Это ограничение несущественно и может быть беспрепятственно устранено, потому что...

4. Ни одно из перечисленных объяснений недостоверно, а настоящая причина состоит в том, что...

Вопрос 10. Известно, что из множества дизъюнктов S можно построить резолютивный вывод пустого дизъюнкта  . Какие из приведенных ниже утверждений справедливы и почему?

1. Существует успешный табличный вывод для исходной таблицы T = , S  , потому что….

2. Существует успешный табличный вывод для исходной таблицы T =  S, , потому что….

3. Не существует успешного табличного вывода для исходной таблицы T = , S  , потому что….

4. Не существует успешного табличного вывода для исходной таблицы T =  S,, потому что….

5. Ни одно из приведенных утверждений в общем случае не верно.

Вопрос 11. Известно, что хорновская программа  получена из хорновской логической программы  за счет добавления непустого множества программных утверждений. Какие из приведенных ниже утверждений справедливы и почему?

1. lfp( T_ )  lfp( T_ ), потому что...

2. lfp( T_)  lfp( T_ ), потому что...

3. Выполнимость или невыполнимость указанных включений зависит от программ  и .

Вопрос 12. Известно, что запрос ? P(x) к хорновской логической программе  не имеет успешных вычислений. Каким может быть ответ на запрос ? not(P(c)) к программе  ? Выберите из предложенных вариантов ответа на этот вопрос правильные и обоснуйте их.

1. Ответ на запрос ? not(P(c)) будет положительный независимо от программы , потому что....

2. Ответ на запрос ? not(P(c)) будет отрицательный независимо от программы , потому что....

3. Ответ на запрос ? not(P(c)) может быть как положительным, так и отрицательным, в зависимости от программы , потому что....

4. На запрос ? not(P(c)) может быть вообще не получено никакого ответа, потому что....