Применение графов к решению логических задач

Государственное автономное профессиональное образовательное учреждение Чувашской Республики «Алатырский технологический колледж» Министерства образования и молодежной политики Чувашской Республики

Исследовательская работа:

 «Применение графов к решению логических задач»

Автор работы: Шугурова Ольга

II курс, специальности 38.02.01

Руководитель: Фирсова Н.А.

Алатырь – 2019 г.

 План

 Введение………………………………………………………………………………3

1.  Понятие логической задачи ……………………………………………………. 4  

2.    Применение графов к решению логических задач…………………………….5

     2.1 Основные понятия и теоремы теории графов……………………………….5

     2.2 Примеры решения задач с помощью графов…………………………………6

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

Литература……………………………………………………………….....................14

Введение

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

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

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

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

Предметом исследования в данной работе является решение логических задач при помощи графов.

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

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

Задачи исследования:

• изучить литературу по данной теме;
• научиться переводить задачи на язык графов.
• рассмотреть решение задач при помощи графов;
• определить преимущества данного метода при решении логических задач.

1. Понятие логической задачи.

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

При этом часть утверждений условия задачи может выступать с различной истинной оценкой (быть истиной или ложной).

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

В учебно-методической литературе используются и такие классификации логических задач:

·   по содержанию мыслительной операции, задействованной в процессе решения (это задачи на: аналогию; сравнение; умозаключение.классификацию; анализ и синтез; абстрагирование; обобщение);

·   по характеру требований (нахождение искомого, построение или преобразование, отыскание процесса);

·   по приемам, задействованным в процессе решения (с помощью рассуждений, таблиц, графов, блок-схем, и др.)

Известно несколько различных приемов решения логических задач:

·        словесное рассуждение;

·        построение графов;

·        построение блок-схем;

·        построение таблицы;

Каждый из этих способов обладает своими достоинствами.

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

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

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

Решение многих логических задач с помощью графов вполне доступно уже младшим школьникам. Для этого им достаточно иметь лишь интуитивные представления о графах и самых очевидных их свойствах.

2 Применение графов к решению логических задач.

2.1 Основные понятия и теоремы теории графов.

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Примерами графов могут служить схемы авиалиний, метро, дорог, электросхемы, чертежи многоугольников.

Рисунок 1

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

Теорема: Любой граф содержит четное число нечетных вершин.

  Есть еще одно важное понятие, относящееся к графам – понятие связности.

Граф называется связным, если любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер.

Эйлеров граф

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

Рисунок 3.

Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Рисунок 4.

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

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

2.2 Примеры решения задач с помощью графов.

Рассмотрим примеры использования графов при решении некоторых известных задач. При этом объекты будем изображать точками, а отношения между ними – отрезками (положения точек и длины отрезков произвольны).

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

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

Задача 1. На рисунке изображен интересный пример лабиринта в саду Хемптон Корт:

Рисунок 5.                                                                                  Рисунок 6.

Построим соответствующий ему граф. Коридоры лабиринта – это ребра графа, а перекрестки, тупики, входы и выходы – это вершины.  (Рисунок 6.)

Теперь хорошо видно, что в центр лабиринта можно попасть, следуя по следующим вершинам:                                              1 - 4 - 7 - 10 - 9 - 11 - 12 - 13.

И, соответственно, выйти из центра лабиринта по маршруту:

13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

 Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?

Рисунок 7.

Решение: Занумеруем последовательно клетки доски:

 Рисунок 8.

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

возможен.                                      Рисунок 9.

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным. Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.     Ответ. Соединить телефоны таким образом невозможно.

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

 Рисунок 10.

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Рассмотрим одну из простейших задач: «Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G1 (рис.11).

                      Рисунок 11.                                                           Рисунок 12.

Далее достраиваем граф по следующему правилу: поскольку в короб может лежать ровно один карандаш, то из каждой точки должны выходить одна сплошная линия и три пунктирные. Получается граф, дающий решение задачи (рис.12).

Во всех рассмотренных задачах точки и отрезки как бы берут на себя труд думать за нас. Решение задач с помощью графов можно сравнивать с решением задач методом уравнений: после составления уравнения мы забываем на время условие задачи и действуем «механически» по правилам решения уравнений. Эта особенность метода сохраняется при рассмотрении и других логических задач, которые предусматривают анализ нескольких возможностей. Приведем пример.

Задача  №5 « Задачи на перебор вариантов или задачи про рыцарей и лжецов»

Во всех рассмотренных задачах точки и отрезки как бы берут на себя труд думать за нас. Решение задач с помощью графов можно сравнивать с решением задач методом уравнений: после составления уравнения мы забываем на время условие задачи и действуем «механически» по правилам решения уравнений. Эта особенность метода сохраняется при рассмотрении и других логических задач, которые предусматривают анализ нескольких возможностей. Приведем пример.

Задача 7. Четыре спортсменки Аня, Валя, Галя и Даша заняли первые четыре места в соревнованиях по гимнастике, причем никакие две из них не делили между собой эти места. На вопрос, какое место заняла каждая из них, трое болельщиков высказали предположения:

1. Аня — II место, Даша — III место;

2. Аня — I место, Валя — II место;

3. Галя — II место, Даша — IV место.

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

Решение. На рисунке 14 точки «верхнего» множества соответствуют именам спортсменок, а «нижнего» — занятым местам.

Рисунок 13

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

Предположим, например, что Валя заняла II место, тогда неверными должны быть высказывания; «Аня заняла I место», «Аня заняла II место», «Галя заняла II место». Отрезки, соответствующие ложному высказыванию, будем перечеркивать

Рисунок 14

В таком случае Даша займет III и IV места, что по условию задачи невозможно. Следовательно, предположение, что Валя заняла II место, неверно; верным будет высказывание

«Аня заняла I место» (рис. 15). Но тогда зачеркиваем отрезки АН и ВП, оставляя ДIII. Далее зачеркнем отрезок Д  IV.

Рисунок 15

Итак, Аня заняла I место, Даша — III, Галя —II , Валя —IV.

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

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

Задача 5. Маша, Лида, Женя и Катя умеют играть на разных инструментах (виолончели, рояле, гитаре и скрипке], но каждая только на одном. Они же владеют разными иностранными языками (английским, французским, немецким и испанским), но каждая только одним. Известно:

1. девушка, которая играет на гитаре, говорит по-испански;

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;

4. девушка, которая говорит по-немецки, не играет  на виолончели;

5. Женя знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный  язык знает?

Условию задачи соответствует граф, изображенный на рисунке 10.

Рисунок 16

Обозначения и принцип решения здесь такие же, как и в задаче 4. Проведем последовательно следующие сплошные отрезки: КС, ВЖ, ВФ, АК (рис.11).

Рисунок 17

Тем самым образуются два «сплошных» треугольника ЖВФ и КСА. Проводим еще сплошной отрезок РН. Теперь убеждаемся, что условия задачи не обеспечивают однозначности выбора третьей точки для каждой из пар РН и ГИ. Возможны следующие варианты «сплошных» треугольников: МГИ и ЛРН или ЛГИ и МРН. Таким образом, задача имеет два решения.

Заключение

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

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

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

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

Литература

1. Судоплотов С.В. Овчинникова Е.В. Дискретная математика.  Учебник -2-е изд., перераб. – М.: ИНФРА; Новосибирск: Изд-во   МГТУ, 2005.
2. Занимательная математика. 5 - 11 классы. (Как сделать уроки математики не скучными)/ Авт.-сост. Т. Д. Гаврилова. - Волгоград: Учитель, 2005. -96 с.
3. Лихтарников Л. М., Сукачева Т.Г. Математическая логика /Курс лекций / Оформление обложки А. Олексенко, С. Шапиро. - СПб.: Издательство "Лань",1998. - 288с.
4. Лыскова В.Ю., Ракитина Е.А. Логика в информатике. - М.: Лаборатория базовых знаний, 2001. - 160 с.: ил. Серия "Информатика".

Интернет ресурсы

5. (http://festival.1september.ru/articles/312793/)
6.  (http://wiki.iteach.ru/index.php/Способы_решения_логических_задач)
7.  (http://fourty.on.ufanet.ru/zagadka.htm)
8. Сборник задач (http://ptil2006.narod.ru/math_calc.html)