Типовые задачи

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

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

Через любые две различные точки плоскости проходит единственная прямая.2. Определение параллельных прямых.3. Через любую точку вне прямой проходит единственная прямая параллельнаязаданной.Построить геометрические интерпретации, в которых записанные формулы могутбыть выполнимыми и невыполнимыми.Задача 3.

Пусть Σ =< 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.Задача 4.Пусть R — двухместный предикатный символ, соответствующий некоторому отношению на множестве M .

Записать формулы, определяющие следующие свойствадвухместного отношения;1. рефлексивность;2. транзитивность;3. симметричность;4. антисимметричность;5. эквивалентность;6. частичный порядок;7. линейный (тотальный) порядок;8. плотный порядок;9. наличие максимального элемента.Задача 5.Выполнимы (общезначимы, противоречивы) ли следующие формулы логики предикатов:1. ∃xP (x) → ∀xP (x);2.

¬(∃xP (x) → ∀xP (x));3. ∃x∀y(Q(x, x)&¬Q(x, y));4. ∃x∃y(P (x)&¬P (y));5. (∀x∃yQ(x, y)) → (∃y∀xQ(x, y));6. (∃y∀xQ(x, y)) → (∀x∃yQ(x, y))Ответ обосновать.ВЫВОД СЕМАНТИЧЕСКИХ ТАБЛИЦАКСИОМЫhΓ | ∆i,Γ ∩ ∆ 6= ∅ПРАВИЛА ВЫВОДАL¬h¬A, Γ | ∆iR¬hΓ | A, ∆iL&hA&B, Γ | ∆ihA, Γ | ∆iR&hA, B, Γ | ∆iL∨hA ∨ B, Γ | ∆ihA → B, Γ | ∆iR∨h∀x A, Γ | ∆iR→R∀hΓ | ∀x A, ∆ihΓ | A{x/c}, ∆iгде переменная x свободнав формуле A для терма th∃x A, Γ | ∆ihΓ | A → B, ∆ihA, Γ | B, ∆ihA{x/t}, ∀x A, Γ | ∆iL∃hΓ | A ∨ B, ∆ihΓ | A, B, ∆ihB, Γ | ∆i; hΓ | A, ∆iL∀hΓ | A&B, ∆ihΓ | A, ∆i; hΓ | B, ∆ihA, Γ | ∆i; h B, Γ | ∆iL→hΓ | ¬A, ∆iгде константа c не содержитсяв формуле A, а также вформулах множеств Γ и ∆R∃hA{x/c}, Γ | ∆iгде константа c не содержитсяв формуле A, а также вформулах множеств Γ и ∆Здесь A, B — формулы логики предикатов,Γ, ∆ — множества формул логики предикатов,x — предметная переменная,c — константа,t — терм.hΓ | ∃x A, ∆ihΓ | A{x/t}, ∃x A, ∆iгде переменная x свободнав формуле A для терма tЗадача 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.

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

Доказать, что формула∃x∀y (P (x, y) → (¬P (y, x) → (P (x, x) ≡ P (y, y))))истинна в любой интерпретации, область которой содержит не более трех элементов.Задача 5. Существует ли необщезначимая формула, истинная на всякой интерпретации, область которой содержит не менее трех элементов?Задача 6. Записать формулу, истинную на любой интерпретации, предметнаяобласть которой содержит не более пяти элементов.МЕТОД РЕЗОЛЮЦИЙЗадача 1. Используя правила равносильных преобразований формул, привестиследующие формулы к предваренной нормальной форме.∃x∀yP (x, y)&∀x∃yP (y, x);∀x((∃yP (y, x) → ∃yP (x, y)) → Q(x)) → ∃xQ(x);¬∀y(∃xP (x, y) → ∀u(R(y, u) → ¬∀z(P (z, u) ∨ ¬R(z, y)))).Задача 2. Привести формулы к стандартной сколемовской форме.∀x∃y∀z∃uR(x, y, z, u);¬∀x(∃yR(x, y) → ∀zP (z, x)).Задача 3.

Найти наиболее общий унификатор следующих атомарных формул,применяя алгоритм унификации.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))).Задача 4. Найти резольвенту следующих дизъюнктов.¬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));Задача 5. Построив резолютивный вывод, доказать противоречивость следующих множеств дизъюнктов.1.

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);2. S = {D1 , D2 , D3 , D4 }D1D2D3D4====P (y, f (x)),¬Q(y) ∨ ¬Q(z) ∨ ¬P (y, f (z)) ∨ Q(v),Q(b),¬Q(a);Задача 6. Используя метод резолюций, обосновать общезначимость следующихформул.∃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))).Задача 7.

Используя формализм логики предикатов и метод резолюций, записать утверждение о существовании ориентированного маршрута в графе 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) для обозначения отношений соединения дугой и достижимости соответственно.ОСНОВНЫЕ ПОНЯТИЯ ЛОГИЧЕСКОГОПРОГРАММИРОВАНИЯЗадача 1.Следующие основные свойства и отношения мать(x, y), отец(x, y), мужчина(x),женщина(y) описываются фактами, например,мужчина(Adam)←;женщина(Eva)←;отец(Adam,Abel)←;Используя данные предикаты, описать программными утверждениями следующие родственные отношения:1. родитель(x, y);2.

дед(x, y);3. быть_отцом(x);4. брат(x, y);5. предок(x, y);6. родственник(x, y);Задача 2.Описать при помощи логических программ следующие отношенияlist(x) — "x является списком".elem(x, y) — "x является элементом списка y",Выяснить, какие ответы будут вычислены при обращении к этим программам сзапросами1.? list(a.b.c.nil)2.? list(a.x.nil)3.? list(a.b)4.? list(a.y)5.? elem(b,a.b.c.nil)6.? elem(x,a.b.c.nil)7.? elem(a,x)Задача 3.Построить дерево вычислений запроса G, обращенного к программе P.G: R(y),P(z);P: R(y) ← P(y),Q(y);P(a) ← ;P(b) ← ;Q(a) ← ;Q(f (x)) ← Q(f(f(x)));Как изменится дерево вычислений, если в теле первого программмного утверждениия изменить порядок расположения атомов?Как изменится дерево вычислений, если в программме поменять местами четвертоеи пятое программные утверждения?Задача 4.Построить логические программы, осуществляющие следующие манипуляции сосписками.1.

Выделить заголовок x списка L.Запрос ? head(L, x).2. Выделить хвост y списка L.Запрос ? tail(L, y).3. Проверить, является ли один список началом другого.Запрос ? check_head_list(x, y).4. Построить конкатенацию (последовательное соединение) списков.Запрос ? concat(x, y, z).5.

Проверить вхождение одного списка в другой в качестве подсписка.Запрос ? chek_sublist(x, y).6. Обратить список.Запрос ? reverse(x, y).7. Проверить, является ли текст палиндромом.Запрос ? palindrom(x).8. Построить пересечение множеств, представленных бесповторными списками.Запрос ? common(x, y, z).9. Построить список L3 , состоящий из всех тех и только тех элементов списка L1 ,которые не содержатся в списке L2Запрос ? sieve(L1 , L2 , L3 ).10. Построить список L2 , состоящий из тех и только тех элементов списка L1 , которыесодержатся в нем однократно.Запрос ? single(L1 , L2 ).Встроенные функции и предикатыЗадача 1.Используя встроенные предикаты сравнения чисел, написать логические программы решения следующих задач1. Проверить, является ли заданный целочисленный список L упорядоченным. Запрос ? ordered(L).2.

Для заданного целочисленного списка L отыскать его наибольший элемент. Запрос? max(L, x).3. Для заданного целочисленного списка L отыскать элемент, следующий по порядкуза его наибольшим элементом. Запрос ? next_max(L, x).4. Упорядочить целочисленный список L. Запрос ? make_ordered(L1 , L2 ).5. Построить список L3 , состоящий из всех элементов списка L1 , не содержащихся всписке L2 . Запрос ? diff(L1 , L2 , L3 ).Задача 2.Используя встроенные арифметические операции и оператор вычисления значения is, написать логические программы решения следующих задач1.