Главная / Алгоритмы и дискретные структуры / Структуры данных и модели вычислений / Тест 14

Структуры данных и модели вычислений - тест 14

Упражнение 1:

Номер 1

Пусть P и Q - одноместные, а R - двухместный предикатные символы. Какие из перечисленных формул являются тождественно истинными?

Ответ:

(1) ∀x [P(x) ∨ Q(x)]→∀x P(x) ∨ ∃x Q(x)

(2) [∀x P(x) ∨x Q(x)]→∀x [P(x) ∨ Q(x)]

(3) [∀x ∃y R(x, y)→ ∃x ∀y R(x, y)]

Номер 2

Пусть P и Q - одноместные предикатные символы. Какие из перечисленных формул являются тождественно истинными?

Ответ:

(1) ∃x [P(x) & Q(x)] → ∀xP(x) ∨ ∃x Q(x)

(2) [∀x P(x) ∨ ∃x Q(x)] → ∀x [P(x) ∨ Q(x)]

(3) ∃x ∀y R(x, y) → ∀x ∃y R(x, y)

Номер 3

Пусть P - трехместный предикатный символ; f , g - одноместные функциональные символы; x, y, u - переменные; b - константа. Какие из подстановок являются унификаторами атомарных формул P(b, y, f (g(y))) и P(x, f (x), f (u))?

Ответ:

(1) (x/b, y/f (b), u/y)

(2) (x/b, y/f (b), u/g(y))

(3) (x/a, y/f (a), u/g(y))

Упражнение 2:

Номер 1

Пусть P - трехместный предикатный символ; f , g - одноместные функциональные символы; x, y, z - переменные; b - константа. Какие из формул A= P(b, y, f (g(y))), B= P(x, f (z), f (z)) и C= P(x, f (x), f (z)) унифицируемы?

Ответ:

(1) A и B

(2) A и С

(3) С и B

Номер 2

Пусть P и Q - одноместные предикатные символы. Какие из перечисленных формул являются префиксной формой формулы [∀x P(x) ∨ ∀x Q(x)]?

Ответ:

(1) ∀x [P(x)∨ Q(x)]

(2) ∀x ∀y [P(x) ∨ Q(y)]

(3) ∀x ∀z [P(z) ∨ Q(x)]

Номер 3

Пусть P и Q - соответственно одноместный и двухместный предикатные символы. Какие из перечисленных формул являются сколемовской формой формулы ∀x ∃y [P(x)& Q(x,y)]?

Ответ:

(1) ∀x [P(x) ∨ Q(x, f(x))]

(2) ∀x [P(f(x)) ∨ Q(x, f(x))]

(3) ∀z [P(z) ∨ Q(z, f(z))]

Упражнение 3:

Номер 1

Пусть P, Q и  S - одноместные и R - двухместный предикатные символы; a, b - константы. Какие из перечисленных ниже формул могут быть выведены с помощью правила резолюции из формул  P(x) ∨ Q(y) ∨ R(b, x) и P(b) ∨ S(y) ∨ R(y, a)?

Ответ:

(1) P(x) ∨ Q(b) ∨ P(b) ∨ S(y)

(2) P(a) ∨ Q(b) ∨ P(b) ∨ S(b)

(3) P(a) ∨ Q(y) ∨ P(b) ∨ S(b)

Номер 2

Пусть P Q и  S- одноместные и R - двухместный предикатные символы, a, b - константы. Какие из перечисленных ниже формул могут быть выведены с помощью правила резолюции из формул P(x) ∨ Q(y) ∨ R(b, x) и P(b) ∨ S(y) ∨ R(y, a)?

Ответ:

(1) P(x) ∨ Q(b) ∨ P(b) ∨ S(y)

(2) P(a) ∨ Q(b) ∨ P(b) ∨ S(b)

(3) P(a) ∨ Q(y) ∨ P(b) ∨ S(y)

Главная / Алгоритмы и дискретные структуры / Структуры данных и модели вычислений / Тест 14