1. Какой из кванторов определяется следующими выражениями: «для всякого x истинно F(x)», «F(x) при произвольном x», «найдется x, такой что F(x)», «для подходящего x верно F(x)»,»всегда имеет место F(x)», «каждый элемент обладает свойством F», «найдется, по крайней мере, один x такой, что F(x)», «существует не менее одного x, что F(x) «, «свойство F присуще всем», «каким бы ни был x F(x истинно», «хотя бы для одного x верно F(x) «.
2. Дана алгебраическая структура <N; xy>. Показать, что следующие предикаты определяются формулами сигнатуры s=():
а) «x меньше y»,
б) «y равно x+1»,
в) «x равно 1»,
г) «x равно 2»,
д) «y лежит между x и z».
3. Дана алгебраическая структура <N; x|y>. Показать, что следующие предикаты определяются формулами сигнатуры s=(|) (x|y означает, что x делит y нацело):
а) «x равно 1»,
б) «z есть HOD(x,y)»,
в) «z есть HOK(x,y)»,
г) «x – простое число»
Можно ли определить предикаты «x – четное число», «x меньше y» формулой этой же сигнатуры?
4. Рассмотрим алгебраическую структуру <N; x+y, xy, xy>. Для каждой из формул:
а) (y)(yxxy,
б) (y)(x=y+y),
в) (u)(v)(x=uyx=ux=v),
г) (y)(z)(zxxzz=y),
д) yzxz(u)(yuxuzu).
Найти предикат из следующего списка, который эта формула определяет: «x – простое число или x равно 1»,
б) «x – четное число»,
в) «x равно 1»,
г) «z есть наибольшее из чисел x и y»,
д) «x принадлежит {1,2}».
5. На множестве М задан одноместный предикат P(x). Выразить следующие утверждения формулами сигнатуры s=(P):
а) «существует не менее одного элемента x, удовлетворяющего предикату P(x)»
б) «существует не более одного элемента x, удовлетворяющего предикату P(x)»
в) «существует точно один элемент x, удовлетворяющий предикату P(x)»,
г),д),е) – утверждения а),б),в) с заменой «один» на «два»
6. Пусть М – множество всех точек, прямых и плоскостей трехмерного пространства. Рассмотрим алгебраическую систему < M; xy, p(x), l(x), pl(x) >, где – отношение принадлежности, p(x) означает, что x есть точка, I(x) – x есть прямая, pI(x) – x есть плоскость.
Выразить следующие предикаты формулами указанной сигнатуры:
а) «плоскости x и y имеют общую точку»,
б) «если плоскости x и y имеют общую точку, то они имеют общую прямую»,
в) «прямые x и y имеют общую точку»,
г) «прямые x и y параллельны»,
д) «прямые x,y и z образуют треугольник».
В формулах можно использовать ограниченные кванторы.
7. Подберите сигнатуру и представьте следующие рассуждения в виде последовательности формул логики предикатов.
7.1. Некоторые из первокурсников знакомы со всеми второкурсниками, а некоторые из второкурсников – спортсмены. Следовательно, ряд первокурсников знаком с некоторыми спортсменами.
7.2. Членом правления клуба может быть каждый совершеннолетний член клуба. Игорь и Андрей – члены клуба. Игорь – совершеннолетний, а Андрей старше Игоря. Следовательно, Андрей может быть членом правления клуба.
7.3. Таможенные чиновники обыскивают всякого, кто въезжает в страну, кроме высокопоставленных лиц. Некоторые люди, способствующие провозу наркотиков, въезжали в страну и были обысканы исключительно людьми, также способствовавшими провозу наркотиков. Никто из высокопоставленных лиц не способствовал провозу наркотиков. Следовательно, некоторые из таможенников способствовали провозу наркотиков.
8. Пусть F(x,y)=P(x,y)&(z)(P(x,z)&P(z,y)) и M={1,2,3,4,5}. Найти предикаты, которые соответствуют формуле F(x,y) при следующих интерпретациях:
а) (jP)(x,y)=«x меньше y «,
б) (jP)(x,y)=«x меньше или равно y «,
в) (jP)(x,y)=«x делит y нацело и x¹y»,
г) (jP)(x,y)=«y равно x+1».
9. Пусть F(x)=xa&(y)(D(y,x)y=ay=x) и M={1,…,9}. Найти предикаты, которые соответствуют формуле F(x) при следующих интерпретациях:
а) (jD)(x)= «x делит y нацело», j(a)=1;
б) (jD)(x)= «x меньше или равно y «, j(a)=1;
в) (jD)(x)= «x делит y нацело», j(a)=2.
10. Пусть F(x)=P(x)Q(a,g(x)), M={0,1}. Найти предикаты, которые соответствуют формуле F(x) при следующих интепретациях:
а) P(x)=«x не равно 0», Q(x,y)=«x меньше y», a=0, g(x)=x+1, где + – сложение по модулю 2.
б) P(x)=«x не равно 1», Q(x,y)=«x меньше y», a=0, g(x)=0,
в) P(x)=«x не равно 1», Q(x,y)=«x меньше y», a=1, g(x)=x+1.
11. Пусть F(x)=P(x)&(y)(P(y)D(x,y)), M={2,3,4,6,9}. Найти предикаты, которые соответствуют F(x) при следующих интерпретациях:
а) P(x)=«x – простое число», D(x,y)=«x меньше или равно y»;
б) P(x)=«x – нечетное число», D(x,y)=«x делит y»,
в) P(x)=«x не равно 4», D(x,y)=«x меньше или равно y».
Существует ли интерпретация, при которой формуле F(x) соответствуют предикаты:
а) «x=4»,
б) «x – четное число?»
12. Будут ли равносильны следующие пары формул:
а) (x)(F(x)G(x)) и (x)F(x)(x)G(x);
б) (x)(F(x)&G(x)) и (x)F(x)&(x)G(x);
в) (x)(F(x)G(x)) и (x)F(x)(x)G(x);
г) (x)F(x) (x)G(x) и (x)(y)(F(x)G(y));
д)(x)(F(x)G(x)) и (x)F(x) (x)G(x);
е) (x)F(x) (x)G(x) и (x)(y)(F(x)G(y));
ж) (x)(F(x)G(x) и (x)F(x)(x)G(x);
з)(x)(F(x)G(x)) и (x)F(x)(x)G(y).
13. Доказать равносильность формул:
а) (x)[(y)P(x,y)(z)(P(z,z)Q(z)))] и (x)(y)(z)[P(x,y)&P(z,z)&Q(z)];
б) (x)[T(x)($y)(z)(R(y,z)&T(z)R(z,z)] и (x)(y)(z)[T(x)&R(z,z)&(R(y,zT(z))];
в) (x)[y)P(x,y)(z)(P(x,z)&Q(z)] и (x)(u)[P(x,u)Q(u)];
г) F=x)[(y)T(x,y)(z)(S(x,z)Q(z))] и G=(x)(y)(z)[T(x,y)&S(x,zQ(z))]
д) F=(x)[(y)T(x,y) (z)(T(x,z)&Q(z))] и G=(x)(u)(T(x,u) &Q(u)).
14. Привести к предваренной нормальной форме:
а) (x)F(x)(y)G(y);
б) (x)F(x) (x)G(x);
в) (x)F(x)(y)G(y);
г) (x)F(x)(y)G(y);
д) (x)P(x,y)(z)[P(x,z)(u)(Q(u)P(z,z))].
15. Привести к сколемовской нормальной форме:
а) (x)[P(x)&(y)(S(y)T(x,y))],
б) (x)[Q(x)(y)(u)(R(x,y)&S(y,u))],
в) (x)(y)(z)(u)(v)[L(x,y,z)&M(z,u,v)
г) (x)[(y)P(x,y)(z)(Q(x,z)&R(z))]
д) (x)[(y)P(x,y) (z)(Q(x,z) P(z))]
е) (x)[(y)P(x,y)(z)Q(x,z)].
16. Показать, что формула G не является логическим следствием множества формул K:
а) G=(x)R(x), K={ (x)R(x)(x)Q(x), ØQ(a) };
б) G=(x)R(x,x), K={(x)(y)(R(x,y)R(y,x)), (x)(y)(z)(R(x,y)&R(y,z)R(x,z))};
в) G=(x)(P(x)&R(x)), K={(x)[P(x)(y)(Q(y)&S(x,y))], (x)[R(x)&(y)(Q(yS(x,y)], (x)P(x)}.
17. Дано утверждение: «Некоторые из первокурсников знакомы с кем-либо из спортсменов. Но ни один из первокурсников не знаком ни с одним любителем подледного лова». Какие из следующих утверждений будут следствием этого и почему:
а) «ни один спортсмен не является любителями подледного лова»,
б)»некоторые из спортсменов не являются любителем подледного лова»,
в) «найдется спортсмен, который любит подледный лов»?
18. Докажите нелогичность следующих рассуждений, построив интерпретацию, при которой посылки истинны, а заключение ложно.
18.1 Все студенты нашей группы – члены клуба «Спартак». А некоторые члены клуба «Спартак» занимаются спортом. Следовательно, некоторые студенты нашей группы занимаются спортом.
18.2. Некоторые студенты нашей группы – болельщики «Спартака». А некоторые болельщики «Спартака» занимаются спортом. Следовательно, некоторые студенты нашей группы занимаются спортом.
18.3. Каждый первокурсник знаком с кем-либо из студентов второго курса. А некоторые второкурсники – спортсмены. Следовательно, каждый первокурсник знаком с кем-либо из спортсменов.
19. Рассмотрим информационную систему под условным названием «Кадры», которая содержит сведения о сотрудниках некоторой организации. Для представления информации используются атрибуты: ФАМ – фамилия сотрудника, ПОЛ –пол сотрудника, ВОЗР – возраст, ДОЛЖ – должность, НОМ – номер отдела (подразделения) этой организации. Сведения хранятся в виде двух отношений СОТР(ФАМ, НОМ, ДОЛЖ), АНК(ФАМ, ПОЛ, ВОЗР). Первое отношение содержит фамилии сотрудников, их должность и номера отделов, где работают эти сотрудники. Второе отношение хранит анкетные данные: фамилию, пол и возраст сотрудника. Кроме того, система может вычислять отношения Мен(x,y)=«x меньше y», определенное на множестве натуральных чисел, точнее, на домене атрибута ВОЗР.
Формализуем систему «Кадры» в многоосновной логике предикатов. Введем пять сортов переменных (по количеству атрибутов), для каждого атрибута – свои сорта. Переменные будут принимать значения в доменах соответствующих атрибутов. Эти домены и будут являться основами. Переменные синтаксически можно не различать. А область изменения переменной указывать с помощью принадлежности домену соответствующего атрибута. Каждому из отношений поставим в соответствие предикат той же местности, что и отношение, с соответствующими типами переменных. Сигнатура будет содержать три символа предиката:
={СОТР(x,y,z), АНК(x,y,z), МЕН(x,y)}.
К можно добавлять константы, интепретируемые как элементы доменов.
Перевести следующие запросы на язык логики первого порядка сигнатуры .
1. Кто из сотрудников–мужчин старше 40 лет?
2. Кто из сотрудников старше 40 лет и в каком отделе работает?
3. Кто из программистов старше 40 лет и в каком отделе работает?
4. В каких отделах все программисты моложе 40 лет?
5. В каких отделах работают пенсионеры7
6. В каких отделах все программисты – пенсионеры?
20. Рассмотрим предметную область, которую условно назовем «Механическая обработка деталей». Эта область состоит из следующих множеств: деталей, станков операций, типов деталей, типов станков, типов операций, которые мы будем обозначать соответственно как ДЕТ, СТ, ОПЕР, ТИПДЕТ, ТИПСТ, ТИПОПЕР. Введем еще и множество моментов времени – ВРЕМЯ. Будем предполагать, что время измеряется в некоторых единицах, например, в минутах. И отождествим множество ВРЕМЯ с множеством натуральных чисел. Зафиксируем сигнатуру, состоящую из предиката и функции + на множестве ВРЕМЯ и следующих одноместных функций:
дет: ОПЕРДЕТ,
ст: ОПЕРСТ,
нач: ОПЕРВРЕМЯ,
кон: ОПЕРВРЕМЯ,
тип дет: ДЕТТИПДЕТ,
типст: СТТИПСТ,
типопер: ОПЕРТИПОПЕР.
В сигнатуру можно добавлять константы, интепретируемые как элементы указанных множеств. Например, ствал – ступенчатый вал (элементы множества ТИПДЕТ), фрст – фрезерный станок (элемент множества ТИПСТ), токобр – токарная обработка (элемент множества ТИПОПЕР), 6 – шесть моментов времени (шесть минут), дет1 – деталь 1, ст2 – станок 2, опз – операция 3.
Записать в виде формул многосортной логики предикатов следующие предложения (обозначения сортов переменных не зафиксированы, поэтому для того, чтобы ограничить область изменения переменной x, скажем, множеством деталей, можно употреблять запись xДЕТ).
1. Деталь ДЕТ1 обрабатывается на станке ст2.
2. Операция ОПЕР1 совершается над деталью ДЕТ2 в течение 10 моментов времени.
3. Фрезерование шлицев длится 6, а фрезерование резьбы 9 моментов времени.
4. Токарная обработка ступенчатого вала длится 10 моментов времени.
5. Операция ОПЕР3 совершается на фрезерном станке в течение 6 моментов времени.
6. Каждая деталь должна сначала пройти фрезерование торцов, а затем – фрезерование шлицев.
7. Каждый вал со шлицами должен сначала пройти токарную обработку, а затем фрезерование шлицев.
8. До операции долбление зубьев вал–шестерня должен пройти токарную обработку.
9. Первая оперция для всех деталей – фрезерование торцов.
10. Последняя операция для всех типов деталей – фрезерование резьбы или закалка.
11. Между операциями фрезерование торцов и фрезерование резьбы проводится токарная обработка.
21. Операции дет, ст, нач, кон, типопер из предыдущей задачи заменим на
предикат ОПЕР(ДЕТ,СТ,ВРНАЧ,ВРКОН,ТИПОПЕР), где ВРНАЧ и ВРКОН – время начала и окончания операции. Предикат и функции , типдет, типст оставим. Записать формулами измененной сигнатуры утверждения 1.3–4, 6–11.
22. Расмотрим предметную область, которую можно назвать «Учеба на факультете». Для представления информации об этой предметной области введем два языка многосортной логики предикатов. Первый содержит следующие имена основных множеств: СТУД, ПРЕП, ПРЕД, ГР, КУРС, АУД, ДЕНЬ, НАЧ, которые интерпретируются соответственно как множества студентов. Преподавателей. Изучаемых предметов, групп, курсов, аудиторий, рабочих дней недели, времени начала занятий. На этих множествах заданы предикаты ГР(СТУД,ГР), КУРС(ГР,КУРС), РАСП(НАЧ,ДЕНЬ,ГР,ПРЕД,ПРЕП,АУД), РАНЬШЕ(НАЧ,НАЧ). Первый определяет принадлежность студента группе. Второй – группы курсу, третий представляет собой факультетсткое расписание н анеделю (предполагается, что нет поточных лекций, лабораторных занятий с частью группы и что все занятия проводятся каждую неделю. Последний предикат определяет. Когда одно занятие проводится раньше другого по времени 9в течение одного дня). В сигнатуру можно добавлять константы. Которые интепретируются как элементы указанных множеств. Например, ИВАНОВ – студент, ПЕТРОВ – преподаватель, МТ–101 – группа, 9.00 – начало занятий. ФИЗКУЛЬ – физкультура.
Второй язык. Кроме указанных выше имен основных множеств. Содержит множество ЗАН, которое интепретируется как множество занятий на факультете, т.е. как объединение множеств занятий, проведенных в группах факультета за неделю. Сигнатура второго языка содержит прежний предикат РАНЬШЕ (НАЧ,НАЧ) и следующие одноместные функции:
нач: ЗАННАЧ,
день: ЗАНДЕНЬ,
гр: ЗАНГР,
пред: ЗАНПРЕД,
преп: ЗАНПРЕП,
ауд: ЗАНАУД,
номгр: СТУДГР,
номк: ГРКУРС.
С естественной интерпретацией. Например, функция нач ставит в соответствие занятию время его начала, а функция пред предмет, который изучается на этом занятии.
Перевести на каждый из языков следующие утверждения.
1. Один и тот же преподаватель не может в одно и то же время проводить занятия в разных аудиториях.
2. Два занятия по одному предмету в один и тот же день не проводятся.
3. Занятия физкультурой проводятся сразу во всех группах.
4. В течение недели проводятся два занятия физкультурой.
5. Занятия физкультурой проводятся последней парой.
6. В субботу проводится не более трех занятий.
7. У каждой группы 4 и 5 курсов есть день, свободный от аудиторных занятий.
8. В группе МТ–101 каждый день есть не менее трех занятий.
9. Если в группе в какой то день есть занятие, то есть, по крайней мере, еще одно.
23. Рассмотрим предметную область, которую условно назовем «Аэропорт». Выбрать сигнатуру многосортной логики для представления следующей информации о (недельном) расписании движения самолетов и выразить указанные утверждения формулами.
1. В Москву каждый день выполняется не менее трех рейсов.
2. В Ростов есть, по крайней мере, три рейса в неделю.
3. Нет двух рейсов до Минеральных Вод в один день.
4. В понедельник рейс до Краснодара выполняется раньше рейса до Ростова.
5. Первый рейс до москвы выполняется раньше рейса до Ростова.
6. Между первыми двумя рейсами до Москвы есть рейс до Новосибирска.
Каким образом можно расширить выбранную сигнатуру. Чтобы представить следующую информацию о промежуточных посадках?
7. Рейс до Якутска имеет две посадки.
8. Ни один рейс не имеет более трех посадок.
Ответы, указания и решения
2. Приведем соответствующие формулы:
а) xy&yx,
б) x<y&(z)(x<z&zyz=y),
в) (y)(xy),
г) (z)(y)[zy&(u)(z<u&uu=x)]
д) (x<y&y<z)(z<y&y<x).
3. Приведем соответствующие формулы:
а) (y)(x|y),
б) z|x&z|y&(u)(u|x&u|yu|z),
в) x|z&y|z&(u)(x|u&y|uz|u),
г) (x=1)&(y)(y|xy=1y=x).
Предикаты «x – четное число» и «x меньше y» невыразимы формулой сигнатуры s. Докажем это. Пусть P – множество простых чисел. Рассмотрим отображениеj:P®P такое, что j(2)=3, j(3)=2 и j(p)=p для всех простых чисел p, отличных от 2 и 3. Отображение j расширим на все множество натуральных чисел N следующим образом: Пусть n=2a3bp1g1…pkgk, где p1,…,pk – простые числа, отличные от 2 и 3. Положим:
j(n)=3a2bp1g1…pkgk и j(1)=1.
Например, j(2)=3, j(12)=18, j(42)=42, j(60)=90. Отображение j сохраняет предикат делимости. Это означает, что
u|vj(u)|j(v)
для любых u,v N. Индукцией по построению формулы можно доказать, что для любой формулы F(x1,…xn) сигнатуры s и любых натуральных чисел а1,…аnвысказывание F(а1,…аn) истинно тогда и только тогда, когда истинно F(j(a1),…,j(an)). Предположим теперь, что предикат «x – четное число» определяется формулой G(x). Тогда высказывание G(2) истинно тогда и только тогда, когда G(3) истинно. Но G(2) истинно, а G(3) ложно. Полученное противоречие доказывает, что предикат «x – четное число» невыразим формулой сигнатуры s. Аналогично доказывается невыразимость предиката «x меньше y».
4. Соответствие формул предикатам содержится в следующей таблице:
| Формула | а | б | в | г | д |
| Предикат | в | б | а | д | г |
5. Приведем соответствующие формулы:
а) (x)P(x),
б) (x)(y)(P(x)&P(y)x=y),
в) (x)[P(x)&(y)P(y)x=y)],
г) x)(y)[xy2&P(x)&P(y)],
д) (x)(y)(z)[P(x)&P(y)&P(z)&x=yx=zy=z],
е) (x)(y)[xy&P(x)&P(y)&(z)(P(z)x=zy=z)].
6. Приведем соответствующие формулы:
а) pl(x)&pl(y)&(z)(p(z)&zx&zy),
б)pl(x))&pl(y)&[(z)p(z)&zx&zy)(u)(l(u)&ux&uy)],
в)l(x)&l(y)&(z)(p(z)&zx&zy),
г) l(x)&l(y)&(u)(pl(u)&xu&yu)&(v)(p(v)&vx&vy),
д)l(x)&l(y)&l(z)&(u)(v)(w)[p(u)&p(v)&p(w)&ux&uy&vx&vz&wy&wz&uv&uw&vw].
7. Приведем решение задачи 7.3. Пусть T(x) означает «x – таможенник», B(x) –»x въезжает в страну», Л(x) – «x высокопоставленное лицо», H(x) – «x способствует провозу наркотиков», O(x,y) – «x обыскивает y». Тогда рассуждение 7.3 может быть переведено на язык логики первого порядка
F1=(x)[B(x)&Л(x)(y)(T(y)&O(y,x))],
F2=(x)[B(x)&H(x)&(y)(O(y,x)H(y))],
F3=(x)[Л(x)&H(x)),
G=(x)(T(x)&H(x).
8. Формуле F(x,y) соответствуют следующие предикаты:
а) «x меньше y и между ними находится в точности один элемент»,
б) «x меньше или равно y»,
в) «x=1 и y=4»,
г) «xx», т.е. тождественно ложный предикат.
9. Формуле F(x) соответствуют следующие предикаты:
а)»x – простое число»,
б) «x – равно 2»,
в) «x равно 1».
10. Формуле F(x) соответствуют следующие предикаты:
а) «x – равно 0»,
б) «x – равно 1»,
в) «x – равно 1».
11. Формуле F(x) соответствуют следующие предикаты:
а) «x – равно 2»,
б) «x – равно 3»,
в) «x – равно 2».
Предикат «x=4» соответствует формуле F(x) при интерпретации P(x)=«x=4», D(x,y)=«x больше или равно y», а предикат «x – четное число» соответствует этой формуле при интепретации P(x)=«x – четное число» и D(x,y)=«x=x».
12. Формулы равносильны только в случаях г и е.
13. Приведем решение задачи 13в. Пусть
F=(x)[(y)P(x,y)(z)(P(x,z)&Q(z))] и
G=(x)(u)[P(x,u)Q(u)].
Применим к формуле F последовательно законы 20 и 26, получим формулу
F1=(x)[(y)P(x,y)(z)(P(x,z)&Q(z).
Затем, пользуясь законом 33, в формуле (y)P(x,y) y заменим на u, а в формуле (z)(P(x,z)&Q(z)) z заменим тоже на u. Формула F1 после этих замен превратится в формулу
F2=(x)[(u)ØP(x,u)(u)(P(x,u)&Q(u))].
Применив закон 23, вынесем квантор вперед:
F3=(x)(u)[P(x,u)(P(x,u)&Q(u))]
Используя последовательно законы 12,16 и 1, получим формулу:
F4=(x)(u)[P(x,u)Q(u)].
Осталось заметить, что в силу закона 20 формула P(x,u)Q(u) равносильна формуле P(x,u)Q(u). Равносильность F и G доказана.
14. Указание. Воспользоваться алгоритмом приведения к ПНФ (см.§6).
15. Указание. Воспользоваться алгоритмом приведения к СНФ (см.§6).
16. Приведем решение задачи 16в. Надо построить интерпретацию, при которой формулы из K истинны, а формула из G ложна. Рассмотрим множество M={1,2,3} и интерпретацию j:(jP)(x)=«x=1», (jQ)(x)=«x=2», (jR)(x)=«x=1 или x=2», (jS)(x,y)=«x=1 и y=2». Легко проверить, что j – искомая интерпретация.
17. Логическим следствием будет только утверждение б.
18. Приведем решение задачи 18.1. Пусть St(x) означает, что «x – студент
нашей группы», M(x) – «x – член клуба «Спартак»«, Sp(x) – «x занимается спортом». Тогда рассуждение 18.1 переводится на язык логики первого порядка последовательностью формул:
F1=(x)(St(x)M(x)),
F2=(x)(M(x)&Sp(x)),
G=(x)(St(x)&Sp(x)).
Рассмотрим множество M={1,2,3} и интерпретацию j: (jSt)(x)=«x=1», (jM)(x)=«x=1 или x=2», (jSp)(x)=«x=2». Легко видеть, что j(F1)=j(F2)=1 и j(G)=0.