Сборник обязательных задач для семинарских занятий

1Формулы логики предикатовУпражнение 1.1. Для приведенных ниже предложений сформируйте, выделив константыи элементарные отношения, алфавит логического языка. Представьте каждое из утвержденийв виде адекватно соответствующей ему формулы логики предикатов.1. Каждый любит сам себя. Значит кто-то кого-то любит.2. Если задача имеет решение, то математик может ее решить. Я - математик, но не могурешить этой задачи.

Значит задача неразрешима.3. Вы можете обманывать всех иногда, вы можете обманывать кого-то всегда, но вы неможете обманывать всех всегда.Обратить внимание на многозначность (полисемантичность) некоторых выражений, допускающую их двоякое истолкование.Упражнение 1.2. Используя приведенные ниже предикаты:• C(x) — «x — квадрат»;• S(x) — «x — шар»;• B(x) — «x — черный предмет»;• W (x) — «x — белый предмет»;• U (x, y) — «предмет x лежит ниже предмета y».напишите формул логики предикатов для следующих утверждений:1. «Хотя бы один предмет, лежащий ниже всех черных квадратов, является шаром»;2. «Нет такого белого квадрата, который лежит под каким-то черным шаром»;3.

«Каков бы ни был черный предмет, либо он является шаром, лежащим выше всех белыхквадратов, либо он является квадратом, лежащим ниже какого-нибудь шара»;4. «Никакой черный квадрат и никакой белый шар не лежат друг над другом»;5. «Если все шары черные, то белых квадратов нет»;6. «Всякая фигура, не являющаяся белым квадратом, лежащим хотя бы под одним шаром,имеет черный цвет и лежит над всеми белыми фигурами».Упражнение 1.3.

Введем следующие предикаты геометрии:• P (x) — x — точка на плоскости;• L(x) — x — прямая на плоскости;• B(x, y) — предмет x лежит на предмете y;• E(x, y) — предмет x совпадает с предметом y.1Записать формулы, выражающие следующие утверждения геометрии:1. Через любые две различные точки плоскости проходит единственная прямая.2. Определение параллельных прямых.3. Через любую точку вне прямой проходит единственная прямая параллельная заданной.Построить геометрические интерпретации, в которых записанные формулы могут быть выполнимыми и невыполнимыми.Упражнение 1.4.

Пусть Σ =< X, S (3) , P (3) > — алфавит арифметики,I =< N, S̄ (3) , P̄ (3) > — интерпретация, где N — множество натуральных чисел 0, 1, 2. . . .(область интерпретации), S̄ (3) (x, y, z) = > ⇐⇒ x + y = z, P̄ (3) (x, y, z) = > ⇐⇒ x × y = z.Записать формулу с одной свободной переменной x, истинную в интерпретации I тогда итолько тогда, когда1.

x = 0;2. x = 1;3. x = 2;4. x — заданное натуральное число n;5. x — четное число;6. x — простое число.Записать формулу с двумя свободными переменными x, y, истинную в интерпретации I тогдаи только тогда, когда1. x = y;2. x < y;3. x кратно y.22Вывод семантических таблицЗакрытая таблица (аксиома):hΓ | ∆i,Γ ∩ ∆ 6= ∅ПРАВИЛА ВЫВОДАh¬A, Γ | ∆ihΓ | ¬A, ∆iL¬R¬hΓ | A, ∆ihA, Γ | ∆ihΓ | A&B, ∆ihA&B, Γ | ∆iR&L&hA, B, Γ | ∆ihΓ | A, ∆i; hΓ | B, ∆ihA ∨ B, Γ | ∆ihΓ | A ∨ B, ∆iL∨R∨hA, Γ | ∆i; h B, Γ | ∆ihΓ | A, B, ∆ihA → B, Γ | ∆ihΓ | A → B, ∆iL→R→hB, Γ | ∆i; hΓ | A, ∆ihA, Γ | B, ∆ihΓ | ∀x A, ∆ih∀x A, Γ | ∆iR∀L∀hA{x/t}, ∀x A, Γ | ∆ihΓ | A{x/c}, ∆iгде переменная x свободнав формуле A для терма tгде константа c не содержитсяв формуле A, а также вформулах множеств Γ и ∆h∃x A, Γ | ∆ihΓ | ∃x A, ∆iL∃R∃hA{x/c}, Γ | ∆ihΓ | A{x/t}, ∃x A, ∆iгде константа c не содержитсяв формуле A, а также вформулах множеств Γ и ∆где переменная x свободнав формуле A для терма tЗдесь A, B — формулы логики предикатов,Γ, ∆ — множества формул логики предикатов,x — предметная переменная,c — константа,t — терм.3Упражнение 2.1.

Установить, являются ли приведенные ниже формулы1. выполнимыми,2. общезначимыми (тождественно истинными),3. невыполнимыми:∃x P (x) & ∃x ¬P (x);∃x P (x) ∨ ∃x ¬P (x);∃x ∀y (P (x) & ¬P (y));P (x) → ∀x P (x);∀x P (x) → P (x);∀y∃x R(x, y) → ∃x∀y R(x, y);(∀x P (x) → ∀x Q(x)) → ∀x (P (x) → Q(x)).Упражнение 2.2.

Применяя табличный вывод, обосновать общезначимость следующихформул:∃x P (x) → ¬∀x ¬P (x);∃x ∀y R(x, y) → ∀y ∃x R(x, y);∀x (P (x) → ∃y R(x, f (y))) → (∃x ¬P (x) ∨ ∀x∃zR(x, z));∀x ∃y ∀z (P (x, y) → P (y, z));∃x ∀y ∃z (P (x, y) → P (y, z));∀x (P (x)&R(x)) → (∀x P (x) & ∀x R(x));(∀x P (x) & ∀x R(x)) → ∀x (P (x)&R(x));∃x (P (x) ∨ R(x)) → (∃x P (x) ∨ ∃x R(x));(∃x P (x) ∨ ∃x R(x)) → ∃x (P (x) ∨ R(x));(∀x P (x) ∨ R(y)) → ∀x (P (x) ∨ R(y));∀x (P (x) ∨ R(y)) → (∀x P (x) ∨ R(y));∃y ∀x Q(x, y) → ∀x ∃y Q(x, y).Упражнение 2.3. Будет ли успешно завершен табличный вывод для следующих формул:∀x (P (x) ∨ Q(x)) → (∀x P (x) ∨ ∀x Q(x));∃x (P (x) ∨ Q(x)) → (∃x P (x) ∨ ∃x Q(x))?Упражнение 2.4.

Существует ли необщезначимая формула, истинная на всякой интерпретации, область которой содержит не менее трех элементов?Упражнение 2.5. Записать формулу, истинную на любой интерпретации, предметная область которой содержит не более пяти элементов.43Нормальные формы и унификацияУпражнение 3.1. Используя правила равносильных преобразований формул, привестиследующие формулы к предваренной нормальной форме.∃x∀y P (x, y) & ∀x∃y P (y, x);∀x ((∃y P (y, x) → ∃y P (x, y)) → Q(x)) → ∃x Q(x);¬∀y(∃xP (x, y) → ∀u(R(y, u) → ¬∀z(P (z, u) ∨ ¬R(z, y))));∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x));∃x∀y (P (x, y) → (¬P (y, x) → (P (x, x) ≡ P (y, y))));∃x(∀xP (x, x) ∨ ∃x¬R(x)) → ∃x(R(x) → ∃yP (f (x), y)).Упражнение 3.2. Используя правило сколемизации, постройте сколемовские стандартныеформы для следующих формул.∀x∃y∀z∃uR(x, y, z, u);¬∀x(∃yR(x, y) → ∀zP (z, x));¬∀y(∃xP (x, y) → ∀u(R(y, u) → ¬∀z(P (z, u) ∨ ¬R(z, y))));∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x));∃x∀y (P (x, y) → (¬P (y, x) → (P (x, x) ≡ P (y, y))));∃x(∀xP (x, x) ∨ ∃x¬R(x)) → ∃x(R(x) → ∃yP (f (x), y)).Упражнение 3.3.

Вычислите композицию подстановок θ1 θ2 , где1. θ1 = {x/f (x), y/g(x, z), u/v, v/f (c)}, θ2 = {x/f (y), y/c, z/g(y, v), v/u};2. θ1 = {x/y}, θ2 = {y/z} {z/x}{x/y}.Упражнение 3.4. Найти наиболее общий унификатор следующих пар атомарных формул(заглавными буквами обозначены переменные, а прописными — константы и функциональные символы):P (c, X, f (X)),P (c, Y, Y );P (f (X, Y ), Z, h(Z, Y )), P (f (Y, X), g(Y ), V );R(Z, f (X, b, Z)),R(h(X), f (g(a), Y, Z));P (X, f (Y ), h(Z, X)),P (f (Y ), X, h(f (Y ), f (Z)));P (X1 , X2 , X3 , X4 ),P (f (c, c), f (X1 , X1 ), f (X2 , X2 ), f (X3 , X3 )).54Метод резолюцийУпражнение 4.1. Найти резольвенту следующих дизъюнктов.¬P (f (x, y), z, h(z, y)) ∨ R(z, v), Q(x) ∨ P (f (y, x), g(y), v);P (x, y, h(y, x)) ∨ R(y, f (x)), ¬P (x, f (x), h(x, y)) ∨ ¬P (y, g(x), h(y, y));Упражнение 4.2.

Построив резолютивный вывод, доказать противоречивость следующихмножеств дизъюнктов.1. S = {D1 , D2 , D3 , D4 , D5 }D1D2D3D4D5=====P (X, f (X)),R(Y, Z) ∨ ¬P (Y, f (a)),¬R(c, X),R(X, Y ) ∨ R(Z, f (Z)) ∨ ¬P (Z, Y ),P (X, X).2. S = {D1 , D2 , D3 , D4 , D5 , D6 , D7 }D1D2D3D4D5D6D7=======E(x) ∨ V (y) ∨ C(f (x)),E(x) ∨ S(x, f (x)),¬E(a),P (a),P (f (x)) ∨ ¬S(y, x),¬P (x) ∨ ¬V (g(x)) ∨ ¬V (y),¬P (x) ∨ ¬C(y);3. S = {D1 , D2 , D3 , D4 }D1D2D3D4====P (y, f (x)),¬Q(y) ∨ ¬Q(z) ∨ ¬P (y, f (z)) ∨ Q(v),Q(b),¬Q(a);Упражнение 4.3.

Используя метод резолюций, обосновать общезначимость следующихформул.∃x P (x) → ¬∀x ¬P (x);∃x ∀y R(x, y) → ∀y ∃x R(x, y);∀x (P (x) → ∃y R(x, f (y))) → (∃x ¬P (x) ∨ ∀x∃zR(x, z));∀x ∃y ∀z (P (x, y) → P (y, z));∃x ∀y ∃z (P (x, y) → P (y, z));∃x∀y(∀z(P (y, z) → P (x, z)) → (P (x, x) → P (y, x))).Упражнение 4.4. Используя формализм логики предикатов и метод резолюций, записатьутверждение о существовании ориентированного маршрута в графе G = h{a, b, c, d}, {(a, b), (b, c), (b, a), (c, d)}iиз вершины a в вершину d и проверить его справедливость.

Разрешается использовать константы a, b, c, d для обозначения вершин орграфа и предикаты R(2) , Q(2) для обозначенияотношений соединения дугой и достижимости соответственно.65Хорновские логические программы. Декларативная иоперационная семантики.Упражнение 5.1. Следующие основные свойства и отношения• мужчина(X),• женщина(Y ),• мать(X, Y ),• отец(X, Y ),• супруги(X, Y )описываются фактами хорновской логической программы, например,мужчина(adam)←;женщина(eve)←;отец(adam,abel)←;мать(eve,cain)←;Продолжите эту логическую программу, создав подходящие программные утверждения, описывающие следующие родственные свойства и отношения:1.

родитель(X, Y );2. дед(X, Y );3. быть_отцом(X);4. брат(X, Y );5. потомок(X, Y );Упражнение 5.2. Создайте логические программы, описывающие следующие свойства термов:list(X) — "Y является списком".elem(X, Y ) — "X является элементом списка Y ",Выяснить, каково множество правильных ответов на следующие запросы, обращенные к построенным программам:1. ? list(a.b.c.nil)2. ? list(a.X.nil)3.

? list(a.b)4. ? elem(X,a.b.c.nil)75. ? elem(a,X)Упражнение 5.3. Постройте SLD-резолютивные вычисления для каждого из запросов,приведенных в упражнении 5.2, обращенных к программам, описывющим предикаты list иelem.Упражнение 5.4. Постройте всевозможные SLD-резолютивные вычисления для запросаG= ? R(Y),P(Z), обращенного к программе P, выделяя в каждом целевом утверждении самуюлевую подцель. Каково множество вычисленных ответов на запрос G к программе P?P: R(Y) ← P(Y),Q(Y);P(a) ← ;P(b) ← ;Q(a) ← ;Q(f(X)) ← Q(X);Упражнение 5.5. Построить логические программы, описывающие следующие свойства иотношения на множестве списков.1.

head(L, X) : Заголовком списка L является элемент X;2. tail(L, X) : Хвостом списка L является список X;3. pref ix(L, X) : Префиксом (начальным подсписком) списка L является список X;4. sublist(L, X) : Список X является подсписком списка L;5. less(X, Y ) : Длина списка X меньше длины списка Y ;6. subset(X, Y ) : Список X состоит только из элементов, содержащихся в списке Y ;7. concat(X, Y, Z) : Список X является конкатенацией (последовательным соединением)списков Y и Z;8. reverse(X, Y ) : Список X является обращением списка Y , т.

е. X состоит из тех жеэлементов, что и список Y , но в списке X эти элементы следуют друг за другом вобратном порядке;9. period(X, Y ) : Список X является периодической последовательностью, полученной врезультате многократного повторения списка Y ;Упражнение 5.6. Натуральные числа X и Y представлены в двоичной системе счисления и их двоичные записи представлены в виде списков. Построить логические программы,описывающие следующие отношения на множестве натуральных чисел.1. less(X, Y ) : Число X меньше числа Y ;2.

sum(X, Y, Z) : Число Z равно сумме чисел X и Y ;86Встроенные функции и предикатыУпражнение 6.1. Используя встроенные предикаты равенства, неравенства и сравнениячисел, написать логические программы решения следующих задач1. Упорядочить целочисленный список L1 .Запрос ? make_ordered(L1 , L2 ).2. Построить бесповторный список L2 , состоящий из всех элементов, содержащихся в списке L1 .Запрос ? single(L1 , L2 ).3. Построить бесповторный список L3 , состоящий из всех элементов, содержащихся как всписке L1 , так и в списке L2 .Запрос ? common(L1 , L2 , L3 ).Упражнение 6.2. Используя оператор вычисления значений, построить логические программы, решающие следующие задачи.1.