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

Глава 1УПРАЖНЕНИЯ1.1Классическая логика предикатов первого порядка: синтаксис и семантикаУпражнение 1.1. В каждой из приведенных ниже сокращенных записей формул КЛПа) восстановите опущенные скобки, руководствуясь соглашением о приоритете логическихопераций;б) определите область действия каждого квантора;в) выделите— все связанные вхождения переменных,— все свободные вхождения переменных.1.

∃x P (x) → ∀y R(x, y);2. ∃y ¬∃x P (x) ∨ ∀x P (x) → P (y);3. ∀x (∃x P (x) → ∀y R(x, y) ∨ ¬P (y)).Упражнение 1.2. Для каждого из приведенных ниже высказываний, состоящих из одногоили более предложенийа) сформируйте подходящую сигнатуру, используя константы для обозначения имен собственных и предикатные символы для обозначения свойств и отношений, фигурирующих в высказывнии;б) используя выбранную сигнатуру, сопоставьте высказыванию замкнутую формулу КЛП,адекватно выражающую смысл этого высказывания.1.

Не все то золото, что блестит.2. Если каждый любит сам себя, то кто-то кого-то любит.12Глава 1. УПРАЖНЕНИЯ3. Вассал моего вассала — не мой вассал.4. Только нечестные воры обкрадывают друг друга.5. Несудившие неподсудны.6. Маленькие богомолы едят друг друга, а большие — нет.7. Все мои друзья знакомы со мной, хотя некоторые мои знакомые со мной не дружат.8. Мне нравится логика и все те, кому нравится то, что нравится мне.9.

Если задача имеет решение, то математик может ее решить. Я - математик, но не могурешить этой задачи. Значит, задача неразрешима.10. Если Василиск существует, то его кто-то видел. Всякий, кто видел Василиска, слеп.Слепой ничего не видит. Значит, Василиска не существует.11. Вы можете обманывать всех иногда, вы можете обманывать кого-то всегда, но вы неможете обманывать всех всегда.Обратите внимание на то, что некоторые из приведенных высказываний могут пониматьсянеоднозначно. Каким образом эта многосмысленность учитывается при построении формулКЛП? Проявляется ли она в построенных формулах?Упражнение 1.3. В этом примере нас будут интересовать только такие интерпретации, вкоторых атомарные формулы выражают следующие свойства и отношения:• C(x) — «x — квадрат»;• S(x) — «x — шар»;• B(x) — «x — черный предмет»;• W (x) — «x — белый предмет»;• U (x, y) — «предмет x лежит ниже предмета y».Используя введенные предикаты, напишите формул логики предикатов для следующих утверждений:1.

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

Классическая логика предикатов первого порядка: синтаксис и семантика3Упражнение 1.4. Какие из утверждений, сформулированные в упражнении 1.3, адекватновыражаются приведенными ниже формулами:1. ∀x (S(x) & B(x) → ¬∃y (W (y) & S(y)));2. ∃x∀y (S(x) & B(x) → (¬W (y) ∨ ¬S(y)));3. ∀x ∀y (W (x) & C(x) → (¬B(y) ∨ ¬S(y) ∨ ¬U (x, y)));4. ¬∃x (W (x) & C(x) → ∃y(B(y) & S(y) & U (x, y))).Упражнение 1.5.

Рассмотрим следующие четыре предиката геометрии:• P (x) — фигура x — это точка на плоскости;• L(x) — фигура x — это прямая на плоскости;• B(x, y) — фигура x лежит на фигуре y;• E(x, y) — фигура x совпадает с фигурой y.Запишите замкнутые формулы (прекдложения) КЛП, выражающие следующие утвержденияпланиметрии:1.

Все прямые пересекаются друг с другом.2. На каждой прямой есть точка, не принадлежащая никакой другой прямой.3. Через любые две различные точки плоскости проходит единственная прямая.4. Каковы бы ни были прямая и точке вне этой прямой, из всех прямых, проходящих череззаданную точку, только одна не имеет общих точек с заданной прямой.Для каждой формулы постройте две геометрические интерпретации, в одной из которыхданная формула выполняется, а в другой - нет.Запишите формулы КЛП, выражающие следующие предикаты:1. отношение параллельности прямых;2. свойство четырех точек образовывать четырехугольник;Упражнение 1.6. Пусть задана сигнатура σ, состоящая из двух трехместных предикатных символов S (3) , P (3) .

Пусть также задана интерпретация I =< N, S̄ (3) , P̄ (3) >. Предметнойобластью интерпретации является множество натуральных чисел N = {0, 1, 2, . . . }. В этойинтерпретации предикатные символы выражают следующие отношения на множестве натуральных чисел:S̄ (3) (m, n, k) = true ⇐⇒ m + n = k,P̄ (3) (m, n, k) = true ⇐⇒ m × n = k.Запишите формулу с одной свободной переменной x, выполнимую в интерпретации I тогдаи только тогда, когда1. значением переменной x является натуральное число 0;4Глава 1. УПРАЖНЕНИЯ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.Запишите формулу с тремя свободными переменными x, y, истинную в интерпретации I тогда и только тогда, когда значение переменной z является наибольшим общим делителемзнаяений переменных x и y.Упражнение 1.7. Пусть R — двухместный предикатный символ, соответствующий некоторому отношению на множестве M . Используя в случае необходимости предикат равенства=, запишите формулы, определяющие следующие свойства двухместного отношения;1. R является рефлексивным отношением;2.

R является транзитивным отношением;3. R является симметричным отношением;4. R является антисимметричным отношением;5. R является асимметричным отношением;6. R является отношением частичного порядка;7. R является отношением эквивалентности;8. R является линейным порядком;9. R является плотным порядком;10. отношение R имеет максимальный элемент.Упражнение 1.8. Предположим, что задана сигнатура σ, состоящая изконстанты 0, представляющей действительное число 0;1-местного функционального символа h, представляющего функцию, вычисляющую модуль действительного числа;1.1. Классическая логика предикатов первого порядка: синтаксис и семантика52-местных функциональных символов +, −, ×, представляющих функции, вычисляющие сумму, разность и произведение действительных чисел;1-местного предикатного символа N , представляющего свойства математического объекта быть натуральным числом;1-местного предикатного символа R, представляющего свойства математического объекта быть действительным числом;1-местного предикатного символа S, представляющего свойства математического объекта быть последовательностью действительных чисел;2-местных предикатных символов <, >, представляющих отношения сравнения действительных и натуральных чисел;предиката равенства =;2-местного предикатного символа L, выражающего следующее отношение: число x является пределом последовательности y;2-местного предикатного символа A, выражающего следующее отношение: число x является предельной точкой последовательности y;3-местного предикатного символа E, выражающего следующее отношение: число x является y-м элементом последовательности z.Используя константные, функциональные и предикатные символы сигнатуры σ, постройтезамкнутые формулы логики предикатов, выражающую следующие утверждения математического анализа.1.

Всякая сходящаяся последовательность действительных чисел ограничена.2. Никакая последовательность ненулевых действительных чисел не имеет положительныхпредельных точек.3. У любой последовательности действительных чисел, содержащей отрицательное число,есть хотя бы одна неположительная предельная точка.4. Какова бы ни была последовательность действительных чисел, найдется отрезок, содержащий все ее предельные точки5. Для любого отрезка [a,b] действительных чисел нет ни одной такой последовательности, состоящей из действительных чисел этого отрезка, у которой была бы хоть однапредельная точка вне этого отрезка.6.

Предел суммы любых двух сходящихся последовательностей действительных чисел равен сумме пределов этих последовательностей.7. Каковы бы ни были две последовательности действительных чисел, если одна из нихсходится к нулю, а другая ограничена, то и произведение этих последовательностейсходится к нулю.8. Нет ни одной такой сходящейся последовательности, которую было бы нельзя представить в виде суммы двух сходящихся последовательностей.6Глава 1. УПРАЖНЕНИЯ9. Если произвольная ограниченная последовательность имеет единственную предельнуюточку, то эта последовательность является сходящейся.10. Каков бы ни был отрезок [a, b] действительных чисел, если почти все элементы произвольной последовательности действительных чисел лежат вне этого отрезка, то и всепредельные точки этой последовательности также лежат вне этого отрезка.11.