Логические задачи

 
 

Федеральное агентство по образованию

Министерство  образования и науки РФ 

Факультет математики и информатики 
 
 
 

Курсовая  работа на тему «Логические задачи» 

Выполнила: студентка 361 группы

                                                                  Глушко П.А

                          Проверил преподаватель:

         Горин Ю.А 
 

Омск 2009 
 

Содержание

                                                                                                                                                Стр.

Введение  …………………………………………………………………1

1.Логические  таблицы…………………………………………..2

2.Графы………………………………………………………………....5

3.Операции  над множествами……………………………...10

4.Выделение элемента множества………………………15

5.Метод  перебора………………………………………………...18

6.Правдолюбцы  и лжецы……………………………………..20

7.Правило  крайнего………………………………………………25

Заключение  …………………………………………………………..27

Библиографический список 
 
 
 

 

 

Введение 

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

Цель  работы: ознакомиться с понятием «логические  задачи», исследовать методы их решения.

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

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

Задачи  логического характера, пожалуй, наиболее важны среди олимпиадных задач, так как в них дух нестандартности, проявляется ярче всего. Но что такое  задача логического характера?

Задачи  логического характера большей  частью связаны с теорией множеств, одни – непосредственно: задачи на логические таблицы, на графы, операции над множествами, выделение элемента множества, правило крайнего, другие – косвенно. Многие задачи логического характера связаны с определённым образом действий: можно ли, и каким образом получить такой-то результат? Для некоторых задач логического характера принципиально важны логические

                     1 
 

  связи между предложениями; типичны  в этом отношении «Правдолюбцы  и лжецы» и «Истинные и ложные  утверждения». Задачи логического  характера, как правило, не  привязаны к определённым темам  школьной программы, а один  и тот же метод решения нередко  можно применять к большему  числу разнообразных задач. Из  общего стиля несколько выпадает  «Метод перебора», поскольку он  демонстрируется главным образом на задачах с целыми числами. Но такой метод следует применять и при решении многих задач логического характера.

1.Логические таблицы

Задачи  на логические таблицы - это задачи на взаимно однозначное соответствие между двумя множествами, где  нахождение такого соответствия производится с помощью специальных таблиц. Применение таблиц значительно ускоряет, почти автоматизирует решение задачи.

Задача 1. Встретились три друга – Белов, Серов и Чернов. Чернов сказал другу, одетому в серый костюм: «Интересно, что на одном из нас белый костюм, на другом – серый и на третьем – чёрный, но на каждом костюм цвета, не соответствующего фамилии». Какой цвет костюма у каждого из друзей?

  Решение: возьмём таблицу 4*4. В левом столбце таблицы напишем фамилии друзей (обозначив каждую своей первой буквой), в верхней строке – цвета их костюмов. По условию на Белове – не белый костюм, на Серове – не серый и на Чернове – не чёрный. Поставим три минуса на пересечении соответствующих строк и столбцов таблицы.  

                                          2 

 
 
 
 

Далее, на Чернове – не серый костюм, так как из условия видно, что  в серый костюм одет один из его  друзей; ставим минус в соответствующей  клетке. Следовательно, на нём может  быть только костюм белого цвета;  поставим в соответствующей клетке таблицы  плюс. Тогда на Серове – не белый  костюм; значит, на нём может быть лишь чёрный костюм. Наконец, на Белове – серый костюм.

Обратим внимание на следующее свойство таблицы, которое остаётся справедливым в  аналогичных задачах на соответствие между двумя множествами, но только лишь в тех случаях, когда эти  множества содержат элементов поровну: в каждой строке таблицы имеется  только один плюс, в каждом столбце  также имеется только один плюс. Следовательно, если в какой-то клетке таблицы стоит плюс, то в остальных  клетках, стоящих в той же строке или в том же столбце, может  быть только минус.

Задача 2. «Пассажиры одного купе». В купе одного из вагонов поезда Москва – Одесса ехали москвич, ленинградец, туляк, киевлянин, харьковчанин и одессит. Их фамилии начинались буквами А , Б, В, Г, Д, Е.

В дороге выяснилось, что А и москвич – врачи;  Д и ленинградец – учителя, а туляк и В – инженеры. Б и Е – участники Отечественной войны, а туляк в армии совсем не служил. Харьковчанин старше А, одессит старше В. Б и москвич сошли сошли в Киеве, а В и харьковчанин в

                                    3 
 

  Виннице. Определите профессию  каждого из них и место жительства.

Решение: задачи такого рода решаются методом  исключения. Перечислим факты, содержащиеся в условии:

1. А и москвич – врачи;
2. Д и ленинградец – учителя;
3. В и туляк – инженеры;
4. Б и Е – участники Отечественной войны, а туляк в армии не служил;
5. Харьковчанин старше А;
6. Одессит старше В;
7. Б и москвич сошли в Киеве;
8. В и харьковчанин сошли в Виннице.

Из  этих фактов, как логические следствия, выявляются скрытые факты. Например, из фактов (1) и (2) следует, что А –  не москвич (1), но А – и не ленинградец (1-2); Д – не ленинградец (2), но Д  – и не москвич(1-2) и т.п.Составим таблицу:

 

Из  таблицы сразу следует, что В – киевлянин (отмечаем звёздочкой). Остальные пассажиры – не киевляне (ставим минусы). Тотчас выясняется местожительство А. Он –

                                    4 
 

одессит. Ставим звёздочку. Продолжая этот приём, устанавливаем окончательно: А –  одессит , Б – ленинградец , В – киевлянин , Г – туляк , Д – харьковчанин , Е – москвич. Теперь легко определяются и специальности пассажиров: А и Е – врачи, Б и Д – учителя, В и Г – инженеры. 

2.Графы

Графом  на плоскости называется конечное множество точек плоскости, некоторые из которых соединены линиями. Эти точки называются вершинами графа, а соединяющие их линии – рёбрами. Число рёбер, исходящих из вершины графа, называется степенью этой вершины. С графами мы встречаемся чаще, чем это, кажется на первый взгляд. Примерами графов могут служить любая карта дорог, электросхема, чертёж многоугольника и т.д. Теория графов возникла в 1736 году, когда Леонард Эйлер (1708 - 1783) опубликовал первую статью о графах. Долгое время считалось, что теория графов применяется главным образом при решении логических задач, а сама теория рассматривалась как часть геометрии. Однако в ХХ веке были найдены широкие приложения теории графов в экономике, биологии, химии, электронике, сетевом планировании и других областях науки и техники. В результате она стала бурно развиваться и превратилась в самостоятельную разветвлённую теорию.

Рассмотрим  задачу на соответствие между двумя  множествами. По существу это те же задачи, которые мы решали с помощью  таблиц.

Задача 1. В пяти корзинах А , Б, В, Г и Д лежат яблоки пяти

                                    5 
 

разных  сортов. В каждой из корзин А и Б находятся яблоки 3-го и 4-го сортов, в корзине В –     2-го и 3-го, в корзине Г – 4-го и 5-го, в корзине Д - 1-го и 5-го. Занумеруйте корзины так, чтобы в корзине №1 имелись яблоки 1-го сорта (по меньшей мере, одно), в корзине №2 – яблоки 2-го сорта и т.д.

Решение: изобразим два множества –  множество корзин и множество  их номеров. В каждом из этих множеств по пять элементов; обозначим их точками (рис).