Математическая логика и теория алгоритмов

Выразить следующие  предикаты формулами указанной  сигнатуры:

а) «плоскости x и y имеют общую точку»,

б) «если плоскости x и y имеют общую точку, то они имеют общую прямую»,

в) «прямые x и y имеют  общую точку»,

г) «прямые x и y параллельны»,

д) «прямые x,y и z образуют треугольник».

В формулах можно  использовать ограниченные кванторы.

 

5. Подберите сигнатуру и представьте следующие рассуждения в виде последовательности формул логики предикатов.

5.1. Некоторые из первокурсников знакомы со всеми второкурсниками, а некоторые из второкурсников – спортсмены. Следовательно, ряд первокурсников знаком с некоторыми спортсменами.

5.2. Членом правления клуба может быть каждый совершеннолетний член клуба. Игорь и Андрей – члены клуба. Игорь – совершеннолетний, а Андрей старше Игоря. Следовательно, Андрей может быть членом правления клуба.

5.3. Таможенные чиновники обыскивают всякого, кто въезжает в страну, кроме высокопоставленных лиц. Некоторые люди, способствующие провозу наркотиков, въезжали в страну и были обысканы исключительно людьми, также способствовавшими провозу наркотиков. Никто из высокопоставленных лиц не способствовал провозу наркотиков. Следовательно, некоторые из таможенников способствовали провозу наркотиков.

 

6. Будут ли равносильны следующие пары формул:

а) ("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));

7. Доказать равносильность формул:

а) Ø($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)).

 

8. Привести к предваренной нормальной форме:

а) ("x)F(x)®("y)G(y);

б) ($x)F(x)® ($x)G(x);

в) ("x)F(x)®($y)G(y);

г) ($x)F(x)®("y)G(y);

 

9. Привести к сколемовской нормальной форме:

а) ($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)].

 

10. Дано утверждение: «Некоторые из первокурсников знакомы с кем-либо из спортсменов. Но ни один из первокурсников не знаком ни с одним любителем подледного лова». Какие из следующих утверждений будут следствием этого и почему:

а) «ни один спортсмен  не является любителями подледного лова»,

б) «некоторые из спортсменов не являются любителем подледного лова»,

в) «найдется  спортсмен, который любит подледный  лов»?

 

11. Докажите нелогичность следующих рассуждений, построив интерпретацию, при которой посылки истинны, а заключение ложно.

11.1 Все студенты нашей группы – члены клуба «Спартак». А некоторые членыклуба «Спартак» занимаются спортом. Следовательно, некоторые студенты нашей группы занимаются спортом.

11.2. Некоторые студенты нашей группы – болельщики «Спартака». А некоторые болельщики «Спартака» занимаются спортом. Следовательно, некоторые студенты нашей группы занимаются спортом.

11.3. Каждый первокурстник знаком с кем-либо из студентов второго курса. А некоторые второкурстники – спортсмены. Следовательно, каждый первокурстник знаком с кем-либо из спортсменов.

 

Варианты  заданий

1. Рассмотрим информационную систему под условным названием «Кадры», которая содержит сведения о сотрудниках некоторой организации. Для представления информации используются атрибуты: ФАМ – фамилия сотрудника, ПОЛ –пол сотрудника, ВОЗР – возраст, ДОЛЖ – должность, НОМ – номер отдела (подразделения) этой организации. Сведения хранятся в виде двух отношений СОТР(ФАМ, НОМ, ДОЛЖ), АНК(ФАМ, ПОЛ, ВОЗР). Первое отношение содержит фамилии сотрудников, их должность и номера отделов, где работают эти сотрудники. Второе отношение хранит анкетные данные: фамилию, пол и возраст сотрудника. Кроме того, система может вычислять отношения Мен(x,y)=«x меньше y», определенное на множестве натуральных чисел, точнее, на домене атрибута ВОЗР.

Перевести следующие  запросы на язык логики первого порядка:

1. Кто из сотрудников–мужчин  старше 40 лет?

2. Кто из сотрудников  старше 40 лет и в каком отделе  работает?

3. Кто из программистов  старше 40 лет и в каком отделе  работает?

4. В каких отделах  все программисты моложе 40 лет?

5. В каких отделах работают пенсионеры?

6. В каких отделах  все программисты – пенсионеры?

 

2. Рассмотрим предметную область, которую можно назвать «Учеба на факультете». Даны следующие множества: СТУД, ПРЕП, ПРЕД, ГР, КУРС, АУД, ДЕНЬ, НАЧ, которые интерпретируются соответственно как множества студентов, преподавателей. изучаемых предметов, групп, курсов, аудиторий, дней недели, времени начала занятий. На этих множествах заданы предикаты ГР(СТУД,ГР), КУРС(ГР,КУРС), РАСП(НАЧ,ДЕНЬ,ГР,ПРЕД,ПРЕП,АУД), РАНЬШЕ(НАЧ,НАЧ). Первый определяет принадлежность студента группе. Второй – группы курсу, третий представляет собой факультетское расписание на неделю (предполагается, что нет поточных лекций, лабораторных занятий с частью группы и что все занятия проводятся каждую неделю). Последний предикат определяет, когда одно занятие проводится раньше другого по времени, в течение одного дня. В сигнатуру можно добавлять константы. Которые интепретируются как элементы указанных множеств. Например, ИВАНОВ – студент, ПЕТРОВ – преподаватель, 03–101 – группа, 09-00 – начало занятий. ФИЗКУЛЬ – физкультура.

Перевести следующие  утверждения:

1. Один и тот  же преподаватель не может  в одно и то же время проводить  занятия в разных аудиториях.

2. Два занятия  по одному предмету в один  и тот же день не проводятся.

3. Занятия физкультурой  проводятся сразу во всех группах.

4. В течение  недели проводятся два занятия  физкультурой.

5. Занятия физкультурой  проводятся последней парой.

6. В субботу  проводится не более трех занятий.

7. У каждой  группы 4 и 5 курсов есть день, свободный от аудиторных занятий.

8. В группе 03–101 каждый день есть не менее трех занятий.

9. Если в группе  в какой то день есть занятие,  то есть, по крайней мере, еще  одно.

 

3. Рассмотрим предметную область, которую условно назовем «Аэропорт». Выбрать сигнатуру многосортной логики для представления следующей информации о (недельном) расписании движения самолетов и выразить указанные утверждения формулами.

1. В Москву  каждый день выполняется не  менее трех рейсов.

2. В Ростов  есть, по крайней мере, три рейса в неделю.

3. Нет двух  рейсов до Минеральных Вод  в один день.

4. В понедельник  рейс до Краснодара выполняется  раньше рейса до Ростова.

5. Первый рейс  до москвы выполняется раньше  рейса до Ростова.

6. Между первыми  двумя рейсами до Москвы есть рейс до Новосибирска.

 

4. Рассмотрим предметную область «Счета в банке». В банке обслуживается  множество клиентов. У каждого клиента есть множество счетов. По счету совершаются определенные операции. Для описания предметной области используются следующие предикаты: КЛИЕНТ(ФИО, ВОЗРАСТ, ПОЛ), СЧЕТ(ФИО, НОМЕР_СЧЕТА, ВАЛЮТА), ОПЕРАЦИЯ(НОМЕР_СЧЕТА, ДАТА, ТИП, СУММА).

Перевести следующие  запросы на язык логики предикатов:

1. Есть ли  клиенты, у которых нет ни  одного счета?

2. Кого из активных клиентов надо поздравить с 8 марта? Активный клиент – это тот, кто совершил хотя бы одну операцию начиная с первого января 2010 года.

3. Кого из активных клиентов надо поздравить с 23 февраля?

4. В какие дни и кто совершал операции в валюте отличной от рублей на суммы более 1 млн.

5. Есть ли пенсионеры, которые открывали счета в евро?

6. Кто совершал  более 1-й операции одного типа  в один день?

 

5. Рассмотрим предметную область «Система заказов». Для описания предметной области используются следующие предикаты: Товар(КОД, НАИМ, ВЕС), ЗАКАЗ(НОМЕР, ДАТА, КЛИЕНТ), ПОЗИЦИЯ_ЗАКАЗА(НОМЕР, КОД, ЦЕНА).

Составить формулы  на языке логики предикатов, которые  позволяют ответить на следующие  вопросы:

1. Какие клиенты  заказывали Кильку в томате  за период от 1 января 2010 до 1 февраля  2010?

2. Какой товар  не заказывали ни разу с  начала текущего года?

3. Какой товар  заказывали более одного раза  с начала текущего года?

4. Есть ли  такие позиции в одном заказе  у которых один товар продается  за разные цены?

5. В каких  заказах встречается товар, который весит больше 100 кг?

6. Какие товары начали заказывать раньше, чем Кильку в томате?

 

6. Рассмотрим предметную область «Бронирование авиабилетов». Для описания предметной области используются следующие предикаты: Бронь(номер, клиент, дата, рейс), Отмена_брони(дата, номер), Оплата брони(дата, номер), маршрут(рейс, дата, город_вылета, город_прилета).

Составить формулы  на языке логики предикатов, которые  проверяют выполнение следующих  условий:

1. Бронь может  быть отменена хотя-бы за 1 день  до вылета.

2. Нельзя оплатить отмененную бронь.

3. Оплаченную  бронь нельзя отменить.

4. Запрещено  бронирование рейсов вылетающих  в Прагу.

5. Нельзя отменить  бронь на рейс вылетающих из  Краснодара.

6. Оплата брони  на рейс в Баку возможна  только в день бронирования.

 

7. Рассмотрим предметную область «Спортивные турниры». Для описания предметной области используются следующие предикаты: Соревнование(код_соревнования, дата, вид спорта), Оценка(код_соревнования, код_спортсмена, судья, оценка), Спортсмен(код_спортсмена,ФИО, страна, возраст).

Составить формулы  на языке логики предикатов, которые  позволяют ответить на следующие  вопросы:

1. В каких  видах спорта выступает Иванов?

2. Есть ли  спортсмены старше 40 лет и получившие  хотя бы один раз оценку  больше 4.

3. Кто из судей  никогда не ставил Российским спортсменам оценки больше 3.

4. Кто из спортсменов  представлял Россию на соревнованиях  проходивших с 1 по 23 февраля 2010 года?

5. Какие страны  участвовали в соревнованиях  по фигурному катанию?

6. Кто из судей  поставил наибольшие оценки Петровой, 20 февраля 2010 года в фигурном катании?

 

Литература

1. Клини С.К.  Математическая логика. – М.: Изд-во  Мир, 1973.

2. Лавров И.А., Максимова Л.Л. Задачи по теории  множеств, математической логике  и теории алгоритмов. – М.:ФИЗМАТЛИТ, 2004.

3. Замятин А.П. Математическая логика и теория алгоритмов: Учебное пособие. – Екатеринбург, УрГУ, 2008. – 273 с.

4. Гэри М., Джонсон  Д. Вычислительные машины и  труднорешаемые задачи. – М.: Изд-во  Мир, 1982.