Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

Тема 3. Логика предикатов

Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или короче: логика первого порядка.

§1. Предикаты и операции над ними

§2. Формулы логики первого порядка

§3. Интерпретация в логике первого порядка

§4. Равносильность, законы логики первого порядка

§6. Логическое следствие

§7. Нормальные формы

§8. Невыразимость в логике первого порядка

§9. Многосортная логика первого порядка

Задачи

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; x£y>. Показать, что следующие предикаты определяются формулами сигнатуры 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, x£y>. Для каждой из формул:

а) ("y)(y£x®x£y,

б) ($y)(x=y+y),

в) ("u)("v)(x=uy®x=uÚx=v),

г) ($y)("z)(z£x®x£zÚz=y),

д) y£z&x£z&("u)(y£u&x£u®z£u).


Найти предикат из следующего списка, который эта формула определяет: «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; xÎy, 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)=x¹a&("y)(D(y,x)®y=aÚy=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,z)®ØT(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,z)®Q(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(y)®ØS(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. Ни один рейс не имеет более трех посадок.

Ответы, указания и решения

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru