Практическая работа № 8

Тема:Формулирование задач логического характера и применение средств математической логики для их решения

Цель работы:

1) научиться применять средства математической логики для решения задач логического характера.

Пояснения:

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:

- с помощью рассуждений;

- средствами алгебры логики;

- метод графов;

- табличный.

Способ рассуждений – самый примитивный способ. Этим способом решаются самые простые логические задачи. Его идея состоит в том, что мы проводим рассуждения, используя последовательно все условия задачи, и приходим к выводу, который и будет являться ответом задачи.

Обычно для решения логических задач средствами алгебры логики используется следующая схема решения:

- изучается условие задачи;

- вводится система обозначений для логических высказываний;

- конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

- определяются значения истинности этой логической формулы;

- из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Задачи типа «Кто есть кто?» – это самые что ни на есть логические задачи. Вам даны отношения между предметами и следуя по цепочке этих отношений, вы приходите к правильному результату. Один из способов решения задач типа «Кто есть кто?» – метод графов. Граф – это несколько точек, часть которых соединены друг с другом отрезками или стрелками (в этом случае граф называется ориентированным).

Основной прием, который используется при решении текстовых логических задач, заключается в построении таблиц. Таблицы не только позволяют наглядно представить условие задачи или ее ответ, но в значительной степени помогают делать правильные логические выводы в ходе решения задачи.

Оборудование, аппаратура, материалы и их характеристики:персональные компьютеры с лицензионным программным обеспечением; доска, маркеры; рабочие тетради; раздаточный материал.

Порядок выполнения работы:

Студенты получают задания по вариантам. Метод решения выбирается студентами самостоятельно и зависит от приобретенных в процессе обучения навыков. В процессе выполнения практической работы преподаватель проводит как групповые, так и индивидуальные консультации по вопросам дополнительного разъяснения отдельных понятий и аспектов изученных тем, задания и оформления отчета.

1. В поезде, который идёт из Москвы в Санкт-Петербург, едут пассажиры Иванов, Петров и Сидоров. В поездной бригаде такие же фамилии у машиниста, бригадира поезда и одного из проводников.

Известно, что:

- пассажир Иванов живёт в Москве;

- проводник живёт на полпути между Санкт – Петербургом и Москвой;

- пассажир однофамилец проводника живёт в Санкт – Петербург;

- ближайший по месту проживания проводника пассажир зарабатывает ровно втрое больше, чем проводник;

- пассажир Петров зарабатывает 2000 рублей в месяц;

- Сидоров (из поездной бригады) выиграл у бригадира партию в шахматы.

Как фамилия у машиниста?

2. Шесть учащихся: Алексеев, Гришин, Смирнов, Трещин, Кузин и Фетисов участвовали в школьной математической олимпиаде. Задачу решили двое. На вопрос: «Кто решил?» - участники олимпиады ответили: 1) Алексеев и Смирнов; 2) Гришин и Фетисов; 3) Фетисов и Алексеев; 4) Гришин и Кузин; 5) Трещин и Алексеев.

В четырех из этих ответов указан правильно один из победителей, в одном ответе оба указаны неправильно. Кто решил задачу?

3. Один из трех братьев поставил на скатерть кляксу.

- Витя не ставил кляксу. – сказал Алеша. – Это сделал Боря.

- Ну а, ты что скажешь? – спросила бабушка Борю.

- Это Витя поставил кляксу, – сказал Боря. – А Алеша не пачкал скатерть.

- Я знаю, что Боря не мог это сделать.

- А я сегодня не готовил уроки, – сказал Витя.

Оказалось, что двое мальчиков в каждом из двух случаев сказали правду, а один оба раза сказал неправду. Кто поставил на скатерть кляксу?

4. Для четырёх дружинников, фамилии которых начинаются буквами А, Е, Р, С, необходимо составить график дежурств на четыре вечера подряд, учитывая что: 1) С и Р не могут дежурить в первый вечер в связи с командировкой; 2) если С выйдет во второй вечер или Р – в третий, то Е сможет подежурить в четвёртый; 3) если А не будет дежурить в третий вечер, то Е согласен дежурить во второй вечер; 4) если А или Р будут дежурить во второй вечер, то С сможет пойти в четвёртый вечер; 5) если Р в четвёртый вечер уедет на конференцию, то А придётся дежурить в первый, а С в третий вечер.

5. Один из трёх братьев: Витя, Толя, Коля разбил окно. В разговоре учувствуют ещё двое братьев – Андрей и Дима.

- Это мог сделать только или Витя или Толя, – сказал Андрей.

- Я окно не разбивал, – возразил Витя, – и Коля тоже.

- Вы оба говорите неправду, – заявил Толя.

- Нет, Толя, один из них сказал правду, а другой сказал неправду, – возразил Дима.

- Ты, Дима, не прав, – вмешался Коля.

Их отец, которому, конечно, можно доверить, уверен, что трое братьев сказали правду. Кто разбил окно?

6. Футбольные команды пяти школ города А, Б, В, Г, Д участвуют в розыгрыше кубка. В финал кубка выходят две команды. До соревнований пять болельщиков высказали прогноз, что в финал выйдут команды: Б и Г, В и Д, Б и В, А и Г, Г и Д. Один прогноз оказался полностью не верным, в остальных была названа только одна из команд – финалисток. Какие команды вышли в финал?

7. Шесть спортсменов – Адамов (А), Белов, (Б), Ветров(В), Глебов (Г), Дронов (Д), Ершов (Е), в проходившем соревновании заняли шесть первых мест, причем ни одно место не было разделено между ними. О том, кто какое место занял были получены такие высказывания: 1) « Кажется, первым был Адамов, вторым- Денисов»; 2) «Нет, на первом месте был Ершов, а на втором- Глебов»; 3) «Вот так болельщики! Ведь Глебов был на третьем месте, а Белов на четвертом» ; 4) «И вовсе не так: Белов был пятым, а Адамов – вторым»;5) «Все вы перепутали: пятым был Дронов, перед ним Ветров».

Известно, что в высказываниях каждого болельщика одно утверждение истинное, а другое ложное. Определите, какое место занял каждый из спортсменов.

8. Четверо друзей владельцы моторных лодок, решили провести гонки из четырех заездов, меняясь в каждом заезде лодками. В первом заезде Борис был на лодке Виктора, а во втором Виктор плыл на лодке Олега. Петр выиграл третий заезд на своей лодке «Мотылек», причем он выиграл и все остальные заезды. На «Колибри» во втором заезде плыл Олег, а в четвертом заезде плыл Борис. В четвертом заезде «Колибри» пришла второй после «Стрижа». Кому принадлежит лодка « Шмель»?

9. Для полярной экспедиции из восьми претендентов A, B, C, D, E, F, G и H надо отобрать шесть специалистов: биолога, гидролога, синоптика, радиста, механика, и врача. Обязанности биолога могут выполнять E и G, гидролога – B и F, синоптика – F и G, радиста – C и D, механика – C и H, врача – A и D. Хотя некоторые претенденты владеют двумя специальностями, в экспедиции каждый сможет работать только по одной специальности. Кого и кем следует взять в экспедицию, если E не может ехать без B, D – без H и без C, C не может ехать без одновременно с G, а A не может ехать вместе с B?

10. Имеется шесть кубов, внешне одинаковых. Три из них весят одинаково, три остальных – более легкие, они также весят одинаково. За какое наименьшее число взвешиваний на чашечных весах без гирь можно определить, какие кубы имеют одинаковую массу?

11. Имеется 10 фишек: 2 белых, 2 черных. 2 красных, 2 синих и 2 зеленых. Два игрока A и B ставят по очереди по одной фишке в одной из вершин выпуклого 10-угольника. Игрок A хочет получить пять последовательных вершин всех пяти цветов, а игрок B хочет этому помешать. Игру начинает B. Кто выиграет при правильной игре?

12. В 1918 году закончилась первая мировая война. В день подписания мирового договора три супружеские пары собрались, чтобы отпраздновать это событие за праздничным столом. Каждый муж доводился братом одной из жен, а каждая жена была сестрой одного из мужей, т.е. среди присутствующих можно было указать три родственные пары «брат с сестрой». Элен ровно на 26 недель старше своего мужа, который родился в августе. Сестра мистера Уайта замужем за свояком брата Элен и вышла за него замуж в день своего рождения, в январе. Маргарет Уайт ростом ниже Уильяма Блэка. Сестра Артура красивее, чем Беатрис. Джону исполнилось 50 лет. Как зовут миссис Браун?

13. В течение последних четырёх лет сотрудники НИИЧАВО Привалов, Амперян, Корнеев и Выбегалло получают очередные отпуска в мае, июне, июле и августе. Причём один из них отдыхал в мае, другой – в июне, третий – в июле, а четвёртый – в августе. Каждый из них получал отпуска в разное время. В первые год Корнеев отдыхал в июле, во второй год Корнеев отдыхал в августе, а Привалов в мае. На третий год Выбегалло отдыхал в июне, а Амперян на четвёртый год в июле. В каком месяце отдыхал Привалов в первый год?

14. Один из трех гангстеров, известных в городе М под кличками Арчи, Босс и Весли, Украл кейс с деньгами. На допросе каждый из них сделал три заявления.

Арчи:

1) я не брал кейс.

2) В день кражи я уезжал из города М.

3) Кейс взял Весли.

Босс:

1)Кейс взял Весли.

2)Если бы я и взял его, я бы не сознался.

3)У меня и так много денег

Весли:

1) Я не брал кейс.

2) Я давно ищу хороший кейс.

3) Арчи прав, говоря, что он уезжал из М.

В ходе следствия выяснилось, что из трех заявлений каждого ганстера два верны, а одно неверно. Кто украл кейс.

Требования к отчету: Отчет должен содержать:

- название практической работы;

- формулировку цели работы;

- краткие теоретические сведения по теме работы в виде таблиц, графиков, диаграмм, схем, рисунков и формул;

- результаты решения заданий;

- выводы по работе;

- краткие письменные ответы на контрольные вопросы.

Текст отчета набирается на компьютере. Допускается тип шрифта Times New Roman, размер 12 – 14, межстрочный 1,5 интервал, выравнивание текста по ширине странице, абзацный отступ 1,25.

Контрольные вопросы:

1) Что такое логическая задача?

2) Как решать задачи, используя круги Эйлера?

3) Как решать задачи, используя графы?

4) Как решать задачи, используя логические выражения?

Учебная и специальная литература:

1) Спирина М.С., Спирин В.В. Дискретная математика: Учебник. – М.: Издательский центр «Академия», 2009. – 370 с.

2) Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для высш. учеб. заведений. – М.: Издательский центр «Академия», 2009. – 304 с.

3) Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ – Петербург, 2008. – 352 с.