Сборник обязательных задач для семинарских заданий (1161812)
Текст из файла
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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
